无人机自组网中AODV路由协议的改进

梁 青, 张文飞, 上官艺伟, 熊 伟

(1.西安邮电大学 电子工程学院， 陕西 西安 710121； 2.西京学院 信息工程学院， 陕西 西安 710123)

由车载自组网[1-2]发展而来的无人机自组网[3]，通过动态组网方式完成无人机之间的通信，具有高动态拓扑、自组织、无中心以及多跳性等特点[4-5]，但链路容易断裂，难以满足军用无人机[6]对网络性能的要求。采用AODV路由协议[7-8]的无人机自组网，受节点移动速度和能量[9]的局限，易发生链路中断，且链路生存期限低，丢包率严重[10]。

针对无人机自组织网络路由问题，已有不少改进措施。基于能量改进型的AODV-E路由协议[11]选择跳数少、节点能量高的链路进行数据传输，以避免断裂问题，但没有从根本上降低节点能量的耗费。基于认知的AODV路由协议[12]选择平均邻居节点数多的链路发送数据，以提高链路修复的成功率，但增加了存储空间。基于局部路由修复的AODV路由协议[13]采用两跳本地修复机制，以节约资源和减少端到端的时延，但链路的修复方式受断裂位置的限制，且修复速度慢。这些改进措施主要针对节点移动速度低的网络，不适用于移动速度快的无人机自组网。为最大程度地延长链路的生命周期，在综合考虑各种因素的同时，利用邻居节点的特性改进链路的修复很必要。

本文针对节点间能耗大、链路连接不稳定和链路维护效率低等问题，拟给出一种新的改进型AODV(I_AODV)路由协议，综合考虑路由开销、平均邻节点数量及链路失效时间这三个因素[14-15]，以建立稳定的链路，并在链路断裂时，通过断裂处上下游节点能量最高的共同邻居节点进行链路的快速修复，使其更好地适应高速变动的网络环境。

1 AODV协议

1.1 AODV路由协议

AODV路由协议是一种按需式路由协议，综合了目的节点序列距离矢量(destination sequenced distance vector，DSDV) 路由协议、动态源路由 (dynamic source routing，DSR) 协议的优点[16]，不仅按照DSDV协议为每个节点维护了一个单调递增的计数器，以更新路由缓存中相关项目，可以更有效地利用网络中的带宽资源，防止产生环路，还根据DSR形成了链路发现和链路维护过程，通过路由表象的动态建立，使节点可以维护最新的路由信息。

AODV路由协议的控制消息包括路由请求(route request，RREQ)、路由回复(route reply，RREP)和路由错误(route error，RERR)等。

1.2 链路发现

当源节点需要发送数据到目标节点时，先检查路由表是否有到目标节点的链路，若有到目标节点的链路，直接发送数据；否则，广播路由请求，建立到达目标节点的链路，并建立反向链路。目标节点或者含有到目标节点路径的中间节点收到路由请求，沿着反向链路发送路由回复；同时，建立正向路径，源节点收到路由回复，会沿着此链路发送数据。

1.3 链路维护

活动路由上的节点会周期性地广播消息“HELLO”给邻节点，以判断链路的连接状况。若某节点发送“HELLO”后，在设定时间内未收到任何邻居节点广播消息“HELLO”，说明此条链路已断裂。节点断裂处距目标节点近，则启用本地修复机制进行修复；在设定的时间内本地修复不成功，或断裂处距源节点近，断裂处上游节点会发送消息“RERR”给源节点，重新建立链路。

1.4 AODV路由协议缺点分析

AODV路由协议在建立链路的过程中，由于网络中节点的移动性和能量的消耗，两节点间已建立的链路易断裂，链路的生存时间短。中间节点和目的节点仅对第一次收到的RREQ做出反应，以建立反向链路和发送RREP，造成大量RREQ不能得到充分利用，极大地浪费资源。

节点的路由表中维护了一条到达目的节点的链路，当链路发生断裂时，只能依据断裂处距目的节点的距离进行本地修复或发送RERR给源节点，重新建立链路。链路频繁断裂，导致RREQ的广播量和传输延时大，且断裂处上游节点缓存数据包的压力大，数据包丢失的概率较大。

2 改进的AODV路由协议

链路发现阶段：综合考虑路由消耗、节点间链路失效时间及节点的邻居节点数建立稳定的链路。目的节点后续收到RREQ，不再简单地丢弃。

链路维护阶段：根据邻居节点的特性，通过断裂处上下游节点的共同邻居节点对链路进行快速修复。

2.1 链路权值计算

无人机自组网中链路的稳定性受多种因素的影响。无人机节点的移动速度较快，且每个节点负载及耗能状况不同，各个节点间链路的稳定性也不同，所以建立一条稳定且维持时间较长的链路比较困难，且断裂链路重建概率不高。在通信时选择路由开销小，节点间链路失效时间长的路由，可以提高链路的稳定性，延长网络的寿命。邻居节点数量，在一定程度上反映了网络的状况，可以充分利用路由开销、节点间链路失效时间及节点的平均邻居节点数等信息设计路由算法。

将最优路由选择问题转化为路由开销C、节的平均邻居节点数N和链路失效时间T最优的问题，具体是路由开销小，节点的平均邻居节点数多和链路失效时间长。

为了方便计算，将上述3个条件转化为权值计算，表示为

(1)

路由开销越小，节点的邻居节点数越多，节点间链路维持的时间越长，选择的链路越稳定，协议对动态网络的适应能力越强，所以,权值越小建立的链路越稳定。

(1) 路由开销

网络中链路上节点能量的大小及能量消耗的快慢对链路质量起着决定性作用，链路越短，缓冲数据包越少，节点能量消耗越小，数据传输时延越小，所以，路由开销可用公式表示为

(2)

其中，hc表示跳数，q表示链路中节点缓存数据包的最大数目，e表示链路中节点剩余的最小能量值，由式(2)知，路由开销越小，链路的生存时间越长。

(2) 平均邻居节点数

节点的邻居节点数可以反映出网络的状态信息，节点的邻居节点数越多，链路断裂时，链路重建概率越高。通过平均邻居节点数来判断链路的整体状态。所以，平均邻居节点数可以表示为

(3)

其中，NT表示源节点到当前节点的所有邻居节点数之和，hc表示节点转发的跳数。由式(3)知，平均邻居节点数越多，链路断裂时修复成功的概率越大。

(3) 节点间链路失效时间

由于节点的移动速度快，导致节点间链路不稳定，所以，链路上节点间链路失效时间是必须考虑的因素。节点间链路失效时间是通过节点位置及其移动速度计算得出的(通过GPS定位系统获得节点的位置和移动速度)。表示为

(4)

其中

a=V1cosθ1-V2cosθ2,b=Xm-Xx,c=V1sinθ1-V2sinθ2,d=Ym-Yx。

(Xm,Ym)为节点m的坐标，(Xx,Yx)为节点x的坐标。V1为节点m的速度，V2为节点x的速度，θ1为节点m的方向角，θ2为节点x的方向角。由式(4)知，链路失效时间的值越大，说明链路越稳定，维持的时间越长。

2.2 链路发现机制

源节点需要给目的节点发送数据时，源节点没有到目标节点的路由，就会广播RREQ进行链路建立。RREQ中记录着节点的跳数，节点剩余能量、邻居节点总数和链路中节点缓存数据包的数目以及计算出的路由开销、平均邻居节点数、链路失效时间的值。建立链路时，RREQ每转发一次，其数据包中的变量会相应更新。

中间节点收到RREQ，根据路由表及邻居列表中维护的相关信息计算并更新路由开销、平均邻居节点数及链路失效时间的值，同时计算权值。

目标节点或含有目标节点的中间节点收到RREQ后，选择权值最小的链路回复RREP，源节点收到RREP后，沿此链路发送数据。之后目标节点收到RREQ，判断其权值是否小于已回复给源节点的RREQ中的权值，若小于，则向源节点发送RREP，通知其切换链路，否则，直接丢弃。

路由发现流程如图1所示。

图1 路由发现流程

2.3 链路维护机制

由于节点的移动性及网络拓扑变化性，活动路由上的节点会周期性发送消息“HELLO”检测链路的连接状况。如果节点在一定的时间内未收到下游节点发送的消息，说明链路发生断裂。断裂处上游节点会缓存源节点发送的数据，寻找断裂处上下游节点的共同邻居节点重新建立链路，恢复数据的传输。

寻找断裂处上下游节点的共同邻居节点时，定义一个数组“common[ ]”来记录所有共同邻居节点。遍历断裂处上游节点的邻居，如果其也存在于断裂处下游节点的邻居列表，说明该节点是断裂处上下游节点的共同邻居节点，将其存放到数组中。遍历数组中的元素即可找到能量最大的共同邻居节点。

I_AODV协议中引入了通知消息包，在本文中的应用是断裂处上游节点B发送通知消息给断裂处上下游节点的共同邻居节点E，告知其目的节点是断裂处下游节点C。链路修复过程如图2所示。

图2 链路修复

当链路正在传输数据时，节点B与节点C之间发生断裂，会启动链路修复机制，检查节点C的能量，如果大于0，查找节点B和C能量最强的共同邻居节点E来进行链路的重建。

链路建立的步骤如下。

(1)节点B通过查看自己邻居列表的信息，找到所有的邻居节点。

(2)遍历节点B的所有邻居节点，若节点B的邻居节点同时也是节点C的邻居节点，说明该节点是节点B和C的共同邻居节点，将其存放在数组“common[ ]”中。

(3)遍历数组中的节点，找出能量最强的节点，即节点B和C能量最强的共同邻居节点E。

(4)节点B查看自身路由表，是否存在与节点E之间的路由。若存在，节点B先发送通知消息给节点E，告知其目的节点是节点C，然后发送数据给节点E；若不存在，直接建立节点B到节点E之间路由，因为节点E是节点B的邻居节点，节点B的邻居列表中含有节点E的信息，故可直接建立节点B与节点E之间的路由。节点B发送通知消息给节点E，告知其目的节点是节点C，然后发送数据给节点E。

(5)当节点E收到通知消息时，查看其路由表，是否有到节点C的路由。 若存在，节点E直接发送数据给节点C，节点C继续传输，直至到达目的节点；若不存在，节点E建立到节点C的路由,然后发送数据给节点C，直至发送到目的节点。

若断裂处上下游节点的共同邻居节点不存在或者共同邻居节点存在但能量为0，或断裂处下游节点能量为0，依据断裂处距离目的节点的距离，进行原始本地修复或者发送RERR消息给源节点，重新建立链路。

I_AODV路由协议链路修复的流程如图3所示。

图3 I_AODV路由协议链路修复流程

节点B与节点E之间链路一旦建立，节点B就会发送数据给节点E,以缓解节点B缓存数据的压力，降低节点B的消耗，同时也可降低丢包率。

如图2所示，I_AODV协议的链路修复时间为t1+t2,而AODV协议的链路修复时间为t1+t2+t3+t4，可知I_AODV协议缩短了链路修复时间。此外，如果节点A和B之间发生断裂，则AODV协议不能进行链路修复，只能发送RERR消息重新建立链路，而I_AODV协议仍可进行链路修复。可见，I_AODV协议链路修复方法不受链路断裂位置限制，且所建链路上节点的邻居节点数多，断裂链路修复的概率较高，数据传输延时小。

3 仿真与分析

利用在16.04版Ubuntu下安装的ns-2.35对AODV、I_AODV协议进行仿真。仿真的环境为1 km ×1 km的矩形区域，随机产生为50个节点，节点的能量为40 J，仿真时间为200 s，传输距离为250 m，发送速率为1 包/s，最大连接数为30个，传输功率为0.660 W，接收功率为0.035 W，随机中子数为1，节点的传输模型为TwoRayGround。对节点速度为10～100 m/s区域内的节点的丢包率、端到端的延时、节点平均剩余能量及路由发现频率进行仿真，使用trace文件记录仿真数据，用awk程序提取和处理数据，使用gnuplot工具画图分析。

仿真主要从不同节点速度下对丢包率、端到端的时延、节点平均剩余能量及路由发现频率等4个方面评价两种协议的性能。两种协议在不同速度下的性能对比结果如图4所示。

由图4(a)可知，随着节点速度的增大丢包率也随之变高。相同速度下I_AODV路由协议低于AODV协议的丢包率。其原因在于，I_AODV建立的链路更稳定，降低了链路断裂的几率，且链路断裂时修复的速度更快。

由图4(b)可见，随着速度的加快，节点端到端的延时也随着变大，相同速度下I_AODV路由协议低于AODV端到端的延时。这是因为，I_AODV路由协议建立的链路稳定，不易断裂，且断裂链路的修复速度快。即使断裂处距离源节点近，也不发送RERR消息重建链路而是进行链路修复，减少了大量延时。

由图4(c)可知，随着速度的增大，节点的平均剩余能量随着减小，I_AODV路由协议的节点平均剩余能量大。这是由于，改进后的路由协议所建链路性能更稳定，路由开销小，且断裂链路修复时，断裂处上下游节点的共同邻居节点可以分担断裂处上游节点缓存的数据包，降低了节点的消耗。

由图4(d)可知，I_AODV路由协议路由发现频率低于AODV协议。这是因为，链路建立时考虑邻居节点数、路由开销及链路失效时间，所建链路比较稳定，而且，断裂链路的修复不受链路断裂位置的限制，链路修复时不需要广播路由请求消息。

图4 协议改进前后不同速度下的性能对比

4 结语

针对无人机自组网不稳定的问题，提出新的I_AODV协议算法。在链路建立的过程中，综合路由开销，节点的平均邻居节点数以及链路失效时间来建立稳定的链路，且在链路断裂时由断裂处上下游节点与其能量最大的共同邻居节点快速建立链路进行修复，不受链路断裂位置的限制，且链路修复速度快。仿真表明，在端到端的时延、丢包率、节点平均剩余能量及路由发现频率方面均优于原始AODV；与原始AODV协议相比，有效的改善了链路的稳定性，降低了节点的能量耗费，增加了节点的生存时间，延长了网络的生存周期。但是，还需要进一步增强链路的稳定性，以适应节点速度更快的网络环境。