卢 成 杰
(哈尔滨工程大学 信息与通信工程学院，哈尔滨150001)
近年来，无人机在诸多领域受到越来越密切的关注，在军事和民用领域如情报侦察、远程精准打击、农业植保、灾害救援[1-4]等方面有着广泛应用.无人机自组网(Flying Ad Hoc Networks，FANET)的出现使得无人机可以摆脱基础设施的限制，相比于单架无人机，多架无人机协同通信执行任务具有生存性强、扩展性高[5]、雷达有效截面更小[6]等优势.合适的路由协议是实现无人机群稳定可靠的通信的基础.基于地理位置的路由协议通常被认为是无状态的路由，因为它们不需要时刻维护路由表[7]，转发数据时只需要获取邻居的位置信息，能够应对节点的快速移动，在路由开销上也更有优势.但是现有的地理路由大多是适用于MANET场景的二维平面路由，因此设计针对无人机自组网的三维地理路由具有重要意义.
贪婪周边无状态路由协议(GPSR)[8]是一种经典的地理路由协议，具有贪婪转发和周边转发两种模式.Mohamed Aissani等人[9]针对GPSR协议路由空洞问题，设计了考虑两跳节点信息，以最短路径绕过空洞区域的方法.X.Li等人[10]提出了GPSR-ABPP协议，针对信标消息频繁交换的问题设计了模糊控制器，输入预测误差，输出信标发送间隔，实现信标频率的自适应调节.YiNing Chen等人[11]针对密集流量下的网络拥塞问题，结合Q学习提出TQNGPSR协议，基于对多条路径的评估做出路由决策，引入最小角以减少切换为周边转发的次数，减少了时延和丢包.
综上所述，本文旨在设计适用于无人机自组网的地理路由协议，所设计的路由协议能够适应无人机在三维空间的自由运动和网络拓扑的频繁变动，提升数据分组投递率和网络吞吐量，降低端到端时延.
1.1 网络模型
一般地，我们将无人机投放在感兴趣的区域执行任务.无人机随机均匀分布在三维空间内.将无人机看作空间中的一个节点，每架无人机都有唯一的ID标识自己，所有的无人机按照随机路点模型(RWP)运动.假设所有无人机都配备有全球定位系统(GPS)，可以实时获取自身的位置和速度信息；
无人机配备全向天线，可以与空间中的邻居节点广播、发送和接收消息.
将无人机通信范围假设为一个球体，最大通信距离为R，即图中球体的半径.无人机通过周期性地广播HELLO消息来更新自身的位置和速度信息同时可以获取一跳邻居无人机的ID、位置、速度和移动方向等信息.
1.2 候选区域设计
GPSR算法在贪婪转发时通常选择距离目的节点最近的邻居节点作为下一跳.但是在高动态的无人机网络中，这样选出的下一跳节点往往处于通信范围的边缘，在传输数据时该节点有可能移动出通信范围造成链路断开和路由失败.为了将贪婪转发算法适用于高动态网络，避免这样的路由失败风险，且尽可能保证数据包朝着目的节点方向转发，本文引入候选区域的概念.通过限制转发区域来增加候选最佳下一跳节点的数量，再利用当前节点、候选节点和目的节点的夹角最终确定下一跳节点，达到优中选优的效果.
如图1所示，S为当前持有数据包的节点，D为目的节点，无人机A、B、C、E、F和G是无人机S传输范围内的邻居节点，其中无人机A是距离当前节点S最远、距离目的节点D最近的节点.假设当前节点S位置坐标为(xS,yS,zS)，节点A的坐标是(xA,yA,zA)，节点D的位置坐标为(xD,yD,zD)，则定义节点D、A即离目的节点最近的邻居节点到目的节点之间的距离l为：
图1 候选区域示意图
(1)
定义节点S、D即源节点到目的节点的距离f为：
(2)
为了限定候选节点区域，这里定义最大跳距h为：
h=l+λ(f-l)
(3)
式(3)中，λ的取值范围[0,1].候选区域的大小与λ曲直有关.λ取值增加候选区域也会随之变大，候选节点数量也会增多，部分候选节点会偏离转发方向比较多，造成跳数增加；
如果λ很小，候选节点数量会减少，当λ为0时只有一个候选节点，此时相当于原始GPSR协议的贪婪转发.
根据最大跳距h和通信距离R就可以定义候选区域.如图2，以D为球心、h为半径的球体和以S为球心、R为半径的球体有一块重叠区域，该区域即为候选区域CA(CandidateArea)，CA的定义方式为：
CA(Uc)={Ui|Dist(Uc,Ui)<
R∩Dist(Ui,UD) (4) 其中：Dist表示两节点之间的距离，h表示当前节点最大跳距，N(Uc)表示当前节点Uc的一跳邻居集合. 图2 转发角示意图 如图2所示，候选区域内除了有节点A还有节点B和E，这里将三者视为具有同等地位的候选下一跳.为了在A、B和E中选出最终的下一跳节点，我们考虑当前节点、候选节点和邻居节点的夹角θ，来选出最合适的下一跳节点.为了方便解释这里以平面图示意.在已知节点S、A、B、E和D的位置坐标的情况下，根据余弦定理可以求出： (5) (6) (7) 通过比较三个余弦值，选择余弦值最大的也就是夹角最小的作为最终的下一跳节点.这样选出的节点既在一定程度上避免了节点处于通信范围边缘的情况，又能保证节点沿着最靠近目的节点的方向贪婪转发. 无人机自组网中节点时刻在高速移动，位置在不断变化，当前时刻无人机获取的邻居信息可能不是最新的，确定的候选节点有可能在下一时刻移动出了候选区域甚至可能已经不在通信范围，为了实时掌握邻居节点的位置信息，有必要对邻居节点做移动性预测.由随机路点模型可知，无人机在短暂时间内做线性运动，所以本文采用线性运动方程式对候选节点的位置进行预测，预测所需的邻居节点的信息可以通过HELLO包来获取. 假设当前时刻tc持有数据包的节点为i，其位置为(xi,yi,zi)，速度为(vix,viy,viz)，节点j为节点i已知的邻居节点，节点i收到节点j的HELLO包时刻为tl，记录的节点j的位置为(xjl,yjl,zjl)，速度为(vjx,vjy,vjz)，由此节点i可以预测节点j在当前时刻tc的位置，根据线性运动方程式可得： (8) 其中：(xjc,yjc,zjc)分别是节点i预测的节点j在当前时刻的位置坐标.我们可以根据预测出的位置，判断节点是否已经移动出了候选下一跳区域以及在不在通信范围内，如果不在候选区域，就将其从候选下一跳集合中剔除； HELLO包是CA-GPSR的重要组成部分，网络中的各节点通过周期性地产生和发送HELLO包，可以获取邻居节点的信息并动态地更新这些信息.与传统GPSR协议不同，CA-GPSR协议除了需要邻居的位置信息还需要速度信息，所以需要重新设计HELLO包格式. 新设计的HELLO包格式包括标识HELLO包唯一性的序列号、节点ID、节点的位置坐标和速度矢量以及发送HELLO包的时间.HELLO包的发送周期为τ，由于网络拓扑不断更新，τ值太大会造成信息更新不及时； 通过设计候选区域和引入移动性预测机制改进原始GPSR协议的贪婪转发过程，使其能够应对无人机的快速运动.改进后的贪婪转发选取下一跳的方法如图3所示. 传统的GPSR协议在周边转发时使用右手规则绕过路由空洞.使用右手规则的前提是需要在全网构造平面子图(RNG或GG)，但是这种方法并不适合在三维场景中使用.针对这种情况，本文借鉴DSR算法按需路由的思想，通过泛洪的方式寻找可以恢复贪婪转发的中间节点以绕过路由空洞，实现数据的成功转发. 本章提出的CA-GPSR协议仅在周边转发阶段引入DSR按需路由的思想，采用泛洪寻路的方式寻找可以在三维空间中绕过路由空洞、恢复贪婪转发的节点.这里将发起RREQ包的节点称为贪婪失败节点，RREQ的目的节点的可以恢复贪婪转发的节点，这里将其称为恢复节点，RREQ中携带的路由路径称为恢复路径.修改后的RREQ和RREP消息格式如表1、2. 表1 RREQ消息格式 表2 RREP消息格式 贪婪转发失败节点广播发送RREQ请求包，在RREQ包中记录请求包序列号、贪婪失败节点的ID、贪婪失败位置和恢复路径.通过比较序列号的大小可以确认收到的RREQ包是不是最新的以及是不是第一次收到该RREQ包.贪婪失败节点ID会作为RREP的目的地址.通过计算贪婪失败节点到目的节点的距离，便于找到可以恢复贪婪转发的节点.收到RREQ包的节点首先判断该RREQ是不是最新的，如果不是就丢弃RREQ.如果是最新的，再判断自己的地址是否存在于已有的恢复路径，若存在说明有路由环路，也丢弃该RREQ.若无路由环路，节点比较自身到目的节点的距离是否小于贪婪失败节点到目的节点的距离，如果小于说明找到了恢复节点，将自身ID加入到RREQ包的恢复路径中，恢复节点沿着恢复路径的反向路径将RREP包发给贪婪失败节点.反之，如果该节点不是恢复节点，就将自身ID加入恢复路径，继续广播RREQ包.由于贪婪失败节点收到RREP包后选择跳数最少的一条恢复路径进行周边转发.恢复节点收到数据包后继续判断自己能否进行贪婪转发，依次循环，直至将数据发送到目的节点.见图3. 图3 基于候选区域和移动预测的下一跳选取流程图 本文基于OMNeT++ 5.6.2和INET3.0框架对所提出的CA-GPSR协议进行仿真验证.仿真区域设置为1 500 m×1 500 m×1 000 m，无人机移动模型为随机路径点模型，通信半径设为250 m，HELLO包的发送间隔为1 s，数据包大小为512bytes，无人机个数为80，无人机移动速度为10～80 m/s，步长为10.统计仿真结果取20次仿真的平均值. 本文从端到端时延、分组投递率、网络吞吐量和重传次数四个方面对所提出的CA-GPSR协议的性能进行仿真验证.平均端到端时延反应了数据分组从源节点到目的节点经过的时间.分组投递率表示目的节点受到的数据包占源节点产生的数据包的比例.网络吞吐量表示单位时间内全网成功传输的数据包比特数.本文仿真了另一种三维地理路由协议PSPFP作为对照协议. 如图4所示，在速度较低为10m/s左右时，二者的端到端时延相差不大，但是随着无人机移动速度的增加，二者端到端时延都呈现逐渐增加的趋势，因为移动速度的增加会削弱无人机之间通信链路的保持能力.不同的是，随着速度的加快，CA-GPSR的端到端时延缓慢增大，而PSPFP的时延呈现快速增加的趋势，这是因为CA-GPSR中采取了候选区域设计和移动性预测机制，增加了贪婪转发阶段的稳定性，可以保证数据分组朝着目的方向快速传输.而PSPFP算法在贪婪转发阶段仅仅考虑最大进度，没有移动预测机制. 图4 平均端到端时延与节点速度的关系 如图5所示，随着移动速度的增加，两种协议的数据分组投递率都在下降，不过CA-GPSR的分组投递率始终高于PSPFP.即使在速度为80m/s时，CA-GPSR仍然有55.3%的分组投递率，而PSPFP仅有38.2%的分组投递率.显然，CA-GPSR在面对高动态网络时具有更好的适应性.这主要是因为CA-GPSR算法的移动性预测机制可以预判邻居节点的失效，及时选出稳定的下一跳，避免了链路断开带来的影响.候选区域的设计也可以使选取的下一跳能朝向目的方向稳定传输. 图5 分组投递率和节点速度关系 图6为网络吞吐量与节点速度的关系.随着无人机移动速度加快，两种路由协议下的网络吞吐量都都有下降，不过CA-GPSR的吞吐量始终要优于PSPFP，提高了10%以上.这是因为CA-GPSR有位置预测机制，能够剔除即将失效的邻居节点，又因为考虑了链路连通时间，能够选出更稳定的下一跳，进而使得网络在单位时间内处理的数据分组更多. 图6 网络吞吐量与节点速度的关系 为了使GPSR适用于无人机的三维组网场景，本文提出了基于候选区域设计的三维CA-GPSR协议.提出最大跳距概念设计了候选区域，同时对邻居节点的位置做移动性预测，使得贪婪转发过程更加稳定可靠.结合DSR按需路由的思想改进了周边转发过程，解决了三维场景下的路由空洞问题.仿真结果表明，CA-GPSR协议适用于高动态的无人机三维组网场景.
1.3 无人机移动性预测
还要判断是否有新的邻居节点进入候选区域，如果有，就将它视为候选下一跳，和其他候选下一跳一起参与下一跳的竞选.确定预测节点在不在候选区域的方法是：首先分别计算预测的节点位置到当前节点的距离dij和它到目的节点的距离djD，如果dij1.4 HELLO包格式设计
τ值太小，HELLO消息发送过于频繁，会占用网络带宽，所以要选择合适的HELLO包发送周期，这里设置τ为1 s.为了尽可能避免冲突和碰撞，这里为τ设置一个抖动时延，抖动时延的大小为0.5τ，所以τ的抖动范围[0.5τ,1.5τ].每个节点在本地创建一个一跳邻居列表来保存邻居的相关信息用于选择下一跳节点.该列表为每个邻居创建一个独立的条目，每个条目保存对应邻居所需的信息.当节点收到了邻居列表中的节点发来的新的HELLO包就更新其对应的邻居条目，如果一段时间一直没有收到某个邻居的HELLO包，默认该邻居已经不在通信范围，删除其对应的邻居条目.同样地，如果有邻居列表之外的节点发来了HELLO包，就为其创建一个新的邻居条目，并以相同的方式更新其信息.
3.1 仿真参数设置
3.2 仿真结果分析
