基于卡尔曼-DNN预测的UANET路由协议
时间：2023-03-09 23:40:01 来源：千叶帆 本文已影响人
徐一航，王 傲，杨锦彬，李大鹏
(南京邮电大学 通信与信息工程学院，江苏 南京 210003)
无人机自组织网络(Unmanned Aerial Vehicles Ad Hoc Network,UANET)具有灵活动态组网、自愈性与抗攻击强的特点[1-3]，它将每个无人机作为通信节点[4]，用于各个无人机之间实现各种信息交互，是大规模无人机作战效能的根本保障。在高速移动的无人机场景下，UANET具有链路变化快[5]、时延敏感的特点，导致了UANET拓扑变化频繁，路由信息易丢失。传统的路由协议用于高速运动的无人机自组网时会导致链路中断，将严重影响集群飞行控制与集群编队任务的完成[6]，需要在原有路由协议的基础上设计新的路由协议。
目前，国内外对于移动自组织网络的研究主要集中于路由协议的优化，而基于移动自组织网络衍生出的无人机自组织网络与传统移动自组织网络的不同在于各节点移动速度较高[7]。受制于各无人机节点通信距离的限制，快速移动的无人机节点会严重影响数据包分组到达率、端到端时延等关键性能指标，传统的网络协议无法适用[8-9]。李玉龙等人[10]提出了基于移动预测与链路保持的路由协议，该协议综合考量了节点位置与链路质量来选择下一跳，减缓了节点高速移动带来的不利因素；
郭科兵等人[11]对节点已有路径进行贪婪转发，进行偏移地修正，能有效减少控制包开销；
王广彧等人[12]使用了基于卡尔曼滤波的位置预测模型来预测邻居节点的位置；
文献[13-15]基于机器学习技术提出了节点位置预测算法，此类算法的预测精度较传统算法有了一定的提升；
白晓萌等人[16]提出了改进的周界无状态路由算法,该算法考虑了节点的速度和方向,并根据节点的当前速度计算之后某一时间内节点的位置选择最佳中继节点；
王沁飞等人[17]使用了灰度预测-WNN联合预测模型来获得节点移动状态评价因子，并综合该因子设计了一个分簇路由协议。
为了提高邻居节点信息的准确性，加强节点间链路的稳定性，兼顾预测模型的复杂度，本文提出了一个基于卡尔曼-DNN位置预测的路由协议。
卡尔曼-DNN位置预测模型由两部分组成：第一部分是卡尔曼滤波对节点位置进行预测，第二部分是基于DNN神经网络修正卡尔曼预测的位置。
1.1 基于卡尔曼的节点位置预测
s(n)=[x,vx,y,vy]T。
(1)
无人机的运动模型[18]为：
(2)
式(2)中，设：
(3)
(4)
式中，Ti为UANET协议中离散时间事件处理的时间间隔，θ为无人机节点在n时刻的相对偏转角。则状态转移矩阵A可根据式(4)表示为：
(5)
卡尔曼观测向量即为n时刻实际的位置与速度向量x(n)。x(n)可由观测系数矩阵C、独立同分布的零均值白噪声向量w(n)与k(n)表示为：
x(n)=C·s(n)+k(n)。
(6)
s(n+1|n+1)=A·s(n|n)+w(n)。
(7)
设n时刻预测输出误差协方差矩阵为P(n)，白噪声过程w(n)与k(n)的协方差矩阵分别为COVw和COVk，则有：
P(n)=A·U(n)·AT+COVw,
(8)
U(n)可由卡尔曼增益Gn：
Gn=P(n)·CT·[C·P(n)·CT+COVk]-1,
(9)
表示为：
U(n)=[I-C·Gn]·P(n)。
(10)
则卡尔曼最佳预测输出s(n+1|n+1)可表示为：
s(n+1|n+1)=A·s(n|n)+
Gn·[x(n)-A·C·s(n|n)]。
(11)
1.2 DNN修正卡尔曼的预测值
H=f(w·s+b)。
(12)
当前层的输出即为下一层的输入。按照式(12)进行前向传播最终得到DNN的输出On。本文使用Sigmoid激活函数：
(13)
神经网络的训练使用样本空间u且以最小均方误差E为准则进行：
(14)
式中，p为节点在下一时刻的实际位置。设网络的学习率为lr,则反向传播过程中权值更新公式可表示为：
(15)
在节点工作阶段，当节点的位置信息经卡尔曼滤波计算获得预测值后，输入到DNN神经网络中，再经过DNN的前向传播，最终获得节点在下一时刻位置预测修正值[x″,y″]T。
1.3 模型结构
图1 基于卡尔曼-DNN的位置预测模型Fig.1 Structure diagram of prediction model
1.4 复杂度分析
定义以下3种矩阵运算的复杂度：
① 矩阵乘法。S∈Rn×m,V∈Rm×k，S·V的复杂度为nmk;
② 矩阵加法。S∈Rn×m,V∈Rn×m，S+V的复杂度为nm;
③ 矩阵的逆运算。S∈Rn×n，S-1的复杂度为n3。
根据上述矩阵运算复杂度的定义，对卡尔曼滤波复杂度、卡尔曼-DNN复杂度以及RNN循环神经网络的复杂度进行计算。为简便分析，设卡尔曼输入的维度为n×1，状态转移矩阵A的维度为n×n；
DNN的输入为n个神经元，隐藏层有两层，分别有i个神经元与j个神经元；
循环神经网络RNN输入为k个神经元，隐藏层设u。复杂度计算结果如表1所示。
表1 模型复杂度Tab.1 Model complexity
文中，卡尔曼的输入为4×1，因此n为4；
DNN隐藏层i设为12，j设为4。则卡尔曼复杂度为388，卡尔曼-DNN复杂度为492。相较于卡尔曼预测模型，卡尔曼-DNN预测模型复杂度增加了104。
现有的路由算法中，邻居节点大多依靠周期的广播路由信令包来获取邻居节点信息。若在广播周期内，节点快速移动，邻居节点可能已经离开本节点的通信范围，但本节点并不能探测到这种情况。基于此，本文以GPSR路由协议为基础，根据卡尔曼-DNN节点位置预测结果更新邻居表与路由信息。
2.1 基于位置预测的邻居发现方法
假设无人机节点工作在二维平面。各个无人机节点开机后，每个节点首先广播Hello包发现邻居。Hello包中含发送节点的节点号、邻居表、节点的位置与速度信息、链路质量值PQ。当无人机节点收到自身一跳邻居的发现信令后，如果邻居表中没有对应的节点号，节点会为该邻居建立邻居表，并根据Hello包中的邻居表建立本节点的两跳邻居信息。此外节点还会额外建立一个记录各邻居节点位置与速度信息的表Ta(x,vx,y,vy)；
如果收到的Hello包对应的节点已经存在与本节点的邻居表中，则更新PQ值与位置信息。
(16)
计算与邻居节点的距离。设节点当前的位置为(x,y)，如果D小于某个阈值th，则暂时不广播Hello包；
如果D>th则判定该一跳邻居在下一时刻失效，节点会启动一个定时器，定时的时长t为：
(17)
式中，V为节点移动的速度。当定时器超时事件发生后，节点删除失效的一跳邻居节点；
若D大于2th，同样删除失效的两跳邻居节点。更新完成后，节点需要广播包含新邻居信息的Hello包，其他节点在接收到该Hello包后更新相关邻居信息，并重新计算PQ值。PQ值将作为路由转发的依据，PQ值的定义为:
(18)
式中，PQ0为当前节点邻居表中对应的邻居节点所记录的PQ值，PQ1为邻居信令包中存储的PQ值。信令包中存储的PQ值为该邻居节点内的PQ值。除了本节点到本节点的PQ初始值设置设为PQ_MAX以外，本节点到其他节点的PQ值均设为PQ_MIN。每当节点收到Hello包时，PQ值会根据式(18)进行更新；
如果PQ大于等于存储于本节点路由表所对应的信令包源节点的PQ值，表示该链路质量更优，使用该PQ值替换当前节点一跳邻居表内的PQ0。
如果某个节点的邻居一直没有超出通信范围，该节点将长时间不广播Hello包。当一个新的节点移动到本节点的通信范围内，会导致这个新加入的节点长时间收不到自身邻居节点的信令而无法更新该节点的邻居信息。因此需要设置一个定时器，当节点在定时时间TIMER_UPDATE_MSG内都没有邻居节点更新事件发生，则广播一个Hello包，其他节点收到该Hello包后按照上述方式决定是否更新邻居表与PQ值。
基于卡尔曼-DNN位置预测的邻居发现流程如图2所示。
图2 基于卡尔曼-DNN位置预测的邻居发现流程Fig.2 Flowchart of neighbor tablediscovery based on Kalman and DNN
2.2 路由转发策略
本文在GPSR协议的基础上通过基于位置预测的邻居发现方法，以贪婪模式与周边模式完成数据分组的转发，提高了数据分组传输的可靠性。各节点转发数据分组的步骤如下：
① 节点存在待发送的数据分组时，判断目的节点是否在本节点的一跳邻居范围内；
若是则将该数据分组发送至目的节点，否则转到②。
② 检查邻居节点是否存在路由空洞，若存在，根据一跳与两跳邻居表寻找比该邻居节点到目的节点更近的节点，若没有找到这样的节点，根据周边转发寻找下一跳。若不存在路由空洞，则按照贪婪模式，结合邻居节点中较大的PQ值寻找节点的下一跳地址。按照上述方式，若寻找到下一跳地址，转到④；
否则，转到③。
③ 将该数据分组存入到节点待发送数据队列中。当存在邻居节点加入到本节点的一跳邻居范围时，转到①。
④ 数据分组转发至下一跳。沿用上述转发策略直至数据分组到达目的节点。
本文使用QualNet平台对基于卡尔曼-DNN位置预测的路由协议(KDPR)进行仿真验证，并与GPSR协议以及基于卡尔曼滤波预测的路由协议(KFN)进行对比分析。节点的移动方式采用随机移动(Random Waypoint)；
通信方式采用跳频模式。具体参数如表2所示。
表2 仿真参数配置Tab.2 Simulation parameter settings
实验中以仿真方式模拟节点在2 km×2 km的区域中移动。首先收集在该区域内节点移动的信息，接着将位置信息作为卡尔曼滤波的输入，经卡尔曼滤波处理后得到预测输出向量s=[x′,v′x,y′,v′y]T，即DNN的训练输入，并根据观测值更新卡尔曼相关参数。DNN神经网络将下一刻节点位置的实际值作为神经网络训练的标签p=[x,y]T，则[s,p]构成了DNN的训练集。找到网络收敛最佳的训练次数并保存网络权值参数w，b。
本文使用3个指标衡量基于KDPR的路由协议的性能：端到端时延、分组投递率和邻居错误率。设jm为节点m的所有邻居个数，im为节点m邻居表中不是m的邻居但没有被删除的节点的个数，平均邻居错误率AVGNER定义为：
(19)
图3表示对一个节点的10个连续离散时刻位置使用卡尔曼、卡尔曼-DNN和RNN三种预测模型产生的预测误差。设RNN的输入k为2，隐藏层u为28，根据表1可计算RNN的复杂度为1 652。从图3可以看出，卡尔曼-DNN与RNN的平均预测误差相较于卡尔曼预测误差有所降低。卡尔曼-DNN平均预测误差为2.24，RNN平均预测误差为1.87，二者预测精度相差0.37 m，而卡尔曼-DNN模型复杂度相较于RNN模型降低了1 160。在预测精度相差不大的情况下，相较于RNN预测模型，卡尔曼-DNN在模型复杂度上的优势较为明显。
图3 预测误差Fig.3 Error of prediction
图4表示无人机移动速度在10～40 m/s时的邻居错误率。在不同的节点移动速度场景下，基于KDPR的路由协议相较于KFN协议与GPSR协议降低了邻居发现的错误率。由于加入了邻居预测机制，使得KDPR协议与KFN协议能够更准确地发现将要离开自身一跳、两跳范围的邻居节点。
图4 邻居平均错误率Fig.4 Average neighbor error rate
图5表示无人机移动速度在10～40 m/s时的分组投递率，由图中可以看出，KDPR路由相较于GPSR与KFN提高了网络整体的分组投递率。在节点移动速度较高时，节点在链路预测机制的作用下减少了分组的转发次数，相较于其他两种算法有一定的性能优势。而GPSR没有对邻居节点进行预测，这导致在节点移动速度较高时，转发数据分组无法找到本节点的中继节点，需要重新发送信令包寻路，影响网络整体的分组投递率。
图5 分组投递率Fig.5 Packet delivery fraction
图6表示无人机移动速度在10～40 m/s时不同协议端到端的传输时延。随着节点移动速度的升高，端到端时延不断增加。移动速度较低时，相较于KFN算法并没有明显改善。但在节点移动速度相对较高时，由于KDPR路由协议提高了链路选择的准确性，因此，平均端到端时延相较于GPSR算法与KFN算法有了一定的改善。
图6 端到端时延Fig.6 End-to-end delay
在对场景进行仿真实验可以看出，算法在平均邻居发现错误率上要优于经典算法和相关改进算法，表明在使用节点预测后的协议可以提升协议的性能。此外，由于邻居被正确的发现，提高了路由正确率，降低了邻居信息的错误概率，特别是在邻居节点移动速度较高时较为明显。但每当节点预测自己的邻居节点发生变化时，都需要向自身的邻居节点发送Hello包，而如果某个节点在预测周期内都产生了邻居更新事件，那么频繁地发送Hello包将会加重路由的开销。未来需要对上述问题进行分析。
本文在现有的节点位置预测路由协议研究与分析的基础上，提出了一种新的节点位置预测模型，并设计了KDPR路由协议。在协议工作的过程中，每个节点根据自身的邻居节点特性预测各邻居的位置，能够改善因节点快速移动导致链路中断的问题。最后，分析了本协议相较于其他协议的优点，同时提出了本研究存在的问题以及后续需要进一步攻关的方向。
猜你喜欢 卡尔曼复杂度路由 状态变换扩展卡尔曼平滑算法在AUV水下航迹修正中的应用中国惯性技术学报(2020年2期)2020-07-24铁路数据网路由汇聚引发的路由迭代问题研究铁道通信信号(2020年9期)2020-02-06奥登—卡尔曼歌剧脚本《酒神的伴侣》中的“神话方法”英美文学研究论丛(2020年2期)2020-02-06多点双向路由重发布潜在问题研究太原学院学报(自然科学版)(2019年3期)2019-09-23一种基于虚拟分扇的簇间多跳路由算法太原科技大学学报(2019年3期)2019-08-05卡尔曼滤波在雷达目标跟踪中的应用智富时代(2019年5期)2019-07-05卡尔曼滤波在雷达目标跟踪中的应用智富时代(2019年5期)2019-07-05一种低复杂度的惯性/GNSS矢量深组合方法中国惯性技术学报(2019年6期)2019-03-04路由重分发时需要考虑的问题科技与创新(2018年1期)2018-12-23求图上广探树的时间复杂度中央民族大学学报（自然科学版）(2017年2期)2017-06-11 相关热词搜索：卡尔，路由协议，预测，
