改进的贪婪算法在无人机组网中的研究与应用

逯建琦， 南建国， 李 雪

(空军工程大学航空工程学院， 西安， 710038)

随着无人机技术的发展，无人机正向着军事化、小型化的方向迈进。早在2016年，美军就测试成功了“灰山鹑”无人机蜂群，这种无人机相对于普通无人机在体型上有明显减小，可直接在军用飞机上发射并进行协同作战。由于通信范围有限，此类小型无人机完成一次数据传输常需多个节点转发实现，为保证各节点的信息交互，一般采用构建无线自组网的方式。

移动无线自组网(Mobile Ad-hoc Network)，是一种不依赖于现有基础通信设备、网络无中心、各节点平等且可以自由交流的自组织网络，适用于无人机集群通信[1-5]。研究者们在网络层上对自组网的研究多集中于路由算法的设计，高效的路由算法能够提高数据包的传输效率，对自组网的应用具有重要意义。

传统路由算法大多采用单一权值的路径选择标准，如Dijkstra算法，选择路径最短的路由；动态DSR[6-8]，选择跳数最少的路由；Bellman-Ford算法则是一种基于泛洪的路由。这些算法的权值选择过于单一，无法兼顾到网络的整体性能。

相比于传统算法，一些新型路由算法虽然在某些方面能显示出良好性能，但大都是针对传感器、车辆等平台设计的。本文在小型军用无人机集群组网的应用背景下，在AODV的基础上对路由算法进行改进。利用优化参数过滤掉边缘节点和低能节点，再用Dijkstra算法对能量-拥塞复合路径权值进行更新，最后选择权值最小的路径进行数据传输。

1 Dijkstra算法

1.1 Dijkstra算法简述

Dijkstra是一种常用的最短路径算法，可用于计算源节点到目的节点的最短路径，常以源节点为中心，层层向外扩展，直到扩展到目的节点为止[9]。设Q0表示源节点，Qn表示目的节点，Qi表示其他节点。

步骤1在节点通信范围内，设节点间通信路由长度为lij，建立单向有源最短路径矩阵G，用于存放各节点之间的有向距离，当Q0与Qn两节点距离超出通信阈值时，矩阵中对应元素g0n为∞。

步骤2建立一个一维数组Dis用于存放各节点到Q0的路径长度。初始时刻除Q0的邻居节点外，其余节点与Q0的路径长度定义为∞。因此Dis数组中仅Q0邻居节点对应的元素dis为常数，其余均为无穷大。

步骤3对路径进行搜索，当搜索到矩阵G中两节点间路由长度存在：l0i=g01+g12+…+gmi

步骤4遍历整个网络，并记录路径，直到找到目的节点Qn与源节点Q0之间的最短路径长度disn，所记录的路径即为最短路径。

1.2 Dijkstra算法在路由方面的研究与应用

由于Dijkstra算法能够找到最优解，且原理简单，编程方便，因此很多研究者将它的最优化理念运用于路由算法中。传统Dijkstra算法按照最短距离选择路径，在此基础上进行改进，形成了将不同变量作为路径选择权值的改进路由算法。

文献[10]将改进后的Dijkstra算法应用在WOBAN网络中，形成最小时延算法(MDRA)。MDRA算法不会每次都向所有节点发送广播，而是结合Dijkstra算法利用数据包的发送情况来预测整个网络的链路状态，达到简化DARA算法的目的。文献[11]提出一种能量高效均衡的图路由算法，通过构建一种适用于无线HART图路由的新型层次化网络拓扑结构，将流量负载指标和链路传输能耗加入到贪婪算法中，利用改进的Dijkstra算法为节点分配子图路由，达到平衡网络中节点能量分布的目的。文献[12]针对节点约束型路径问题，将一维平面结构划分为多层，分别在每一层中寻找约束点。该算法利用分层结构保存搜索进度和方便回溯的优势，来寻找局部最优路径以达到全局最优或次优路径，虽然增加了空间复杂度，但可以减小Dijkstra算法的调用次数。

在当前改进的Dijkstra路由算法中，大多数是将时延和能量进行结合的路由算法[13-15]，很少考虑到节点的运动和数据流量情况，所以并不适合无人机组网。因此，研究一种路由算法能减小节点运动和数据流量对Qos造成的影响，有重要意义。

2 网络优化参数

问题分析：①高速军用无人机位置的移动会造成网络拓扑的频繁变化，出现通信链路断裂的情况，因此路由算法要尽量避免选用边缘节点;②无人机不能保证能量实时供应，部分节点会出现担任中继任务多能量消耗过快的情况。针对上述问题，本文提出网络优化参数如下：

2.1 边界评价因子

处于节点i最大通信范围边缘的节点j虽然可与i进行直接通信，但短时间内飞离i通信范围的概率较大。因此本文设立边界评价因子[16]来界定链路中不稳定的节点：

(1)

式中：Mij为i点与j点之间的边界评价因子;R为最大通信距离;Lij为两点之间的距离，可通过信号功率求得。Mij越大表明节点之间脱离通信范围的概率越大。

2.2 能量均衡参数

在无人机集群中，中介中间性好的节点会因转发数据造成能量消耗过快，导致其生命周期缩短[17]。为缓解“热点”问题，本文提出能量均衡参数来避免中继节点能量过快消耗的问题：

(2)

式中：EBPi为能量均衡参数；Eave为节点i与邻居节点的平均剩余能量；Ei为i的剩余能量。EBPi越大，表明i点相对剩余能量越少。为防止节点过早死亡，应尽量避免选择EBP大的节点作为中继。具体过程见图1。

图1 能量均衡原理图

由于图中节点4广泛性最好，因此担任中继节点的次数最多，计算可知EBP4较大，为保证网络节点能量均衡，改选用0→1→3→5路径对数据包进行转发。

3 路由算法描述

无人机自组网除节点的移动性外，通信效果还受节点剩余能量、拥塞度的影响。选择剩余能量小的路径进行传输，会导致路径上的低能节点增多，加速死亡；选择拥塞度大的节点，会增加传输时延、降低数据包的投递率，因此本文算法引入这2个参数。

3.1 边权值的相关参数

1)节点剩余能量参数δen。无人机集群组网中节点是靠无线电进行通信的，通信时除了源节点和目的节点分别只发送和只接收数据包外，路径中的其他节点都要接收并转发数据包，我们定义节点能量消耗模型如下：

(3)

式中：ETi为节点i发送数据包消耗的能量；ERi为节点i接收数据包消耗的能量；Eelec为发射电路和接收电路消耗的能量，一般取Eelec=50 nJ/bit；L表示两节点之间的距离；μ1、μ2分别为发射和接收数据包的比特数；ε是常数，一般取ε=10 pJ/(bit·m-2)。节点能耗表示为:

(4)

本文用节点剩余能量参数来衡量节点的能量状况：

δen=Ei0/Ei

(5)

式中：Ei0为节点i初始时刻的能量；Ei为节点当前的剩余能量，可根据式(4)求得。δen值小的节点表明从初始时刻到现在，节点能量开销较小。

2)节点拥塞度参数δco。缓存队列越长的节点，新来的数据包需等待时间越久。当节点缓存已满时，甚至会丢弃新来的数据包。为完成数据传输，节点需再次发送数据包，在增大时延的同时增加了额外开销。为此设立节点拥塞度δco来衡量节点是否处于饱和状态：

(6)

(7)

3.2 复合权值计算

复合型权值综合考虑了δen、δco，由于衡量参数的量纲不同，因此在进行复合权值计算时要消除量纲差异，本文利用min-max原理对2个参数进行标准化，计算如下：

(8)

式中：定义相关参数X、X*为标准化后的参数指标，Xmin、Xmax分别为参数X在理想条件下的最小值和最大值。经过标准化处理后，所有参数指标都映射到[0，1]。i点的复合权值计算公式如下：

(9)

式中：λ是各参数的加权系数，λ的大小代表参数的重要程度，系数满足λe+λc=1。

3.3 流程及算法描述

1)根据neighborlist中信息，建立邻接矩阵。G(E，V)，E是所有节点集合，V是节点间链路。ω(i，j)表示i点到j点的路径权值，当i与j没有建立路径时，ω(i，j)为无穷大。网络中每个节点建立一个statelist，包括2个字段，即记录字段(记录源节点和上一跳节点)和权值字段(记录源节点到当前节点的权值之和，中间节点按照固定周期计算更新自身权值)。

2)向路由维护中的hello消息包中添加节点自身的能量信息，节点定期将自身能量信息告知邻居节点，并收集邻居节点能量信息，判断自身是否为“热点”。

3)当源节点i要向目的节点j发送数据时，节点i先查看j是否在neighborlist中，若是，则直接利用与j已建立的路由进行数据发送；若否，执行下一步；

4)源节点发送RREQ路由消息包，其中主要包括消息包序号、源节点和目的节点编号、路由跳数、消息包经过的路径权值ω(i，j)。中间节点接收到消息包后，首先判断是否已转发相同序号的RREQ消息包，若有且跳数小于等于此前的RREQ包，则根据Dijkstra算法，更新statelist，只保留ω(i，j)最小的反向路由，并再次转发RREQ包。在这一过程中，转发条件的限制可以避免循环重复发送RREQ，防止出现路由环路。由于一段时间内可能会发现权值更优的反向路径，因此需要发送多个RREQ让下游节点也进行反向路径权值的更新，转发节点每次对权值进行比较后，只保留最优权值。

5)若中间节点没转发过序号相同的RREQ包，则节点根据消息包功率大小，判断是否超出边界评价因子，若超出，则不转发消息包，若未超出且自身不是“热点”，更新statelist后进行转发；

6)目的节点接收到RREQ后，发送RREP应答包，携带目的节点和源节点编号以及经过路径的权值，当中间节点接收到RREP后，根据statelist中信息，为RREP分配权值小的上游路径，每个中间节点至多转发一次RREP；

7)源节点从接收到的前2个RREP中选择权值最小的路径进行数据包传输,另一条可作为备份，见图2。

图2 节点示意图

其中，节点0为源节点，节点1、2、3、4、5、9为其邻居节点，源节点0广播RREQ后，经过步骤4)、5)，根据边界评价因子，节点4不作为中继节点，根据能量均衡参数，节点3不作为中继节点，节点1、2、5、9对RREQ进行转发；根据式(9)，确定0→1→8路径权值为11，0→2→8为9，根据Dijkstra，更新节点8的statelist表，记录字段为0、2，权值字段为9，建立起8→2→0反向路由。

算法流程见图3。

图3 算法流程图

部分伪代码如下：

输入：Source i，Destination j

输出：Route path

While i need to send data to j do

If j is in the neighborlist of i\查找是否可以直接进行通信

Then return route path

Else i broadcasts RREQ

While j doesn’t receive RREQ do

If RREQ is old and route hops are low

Then intermediate nodes update statelists in Dijkstra and broadcast RREQ

\按照Dijkstra规则进行路径权值更新

Else if RREQ is new and intermediate nodes satisfy M and EBP\利用优化参数进行优化

Then update statelists and broadcast RREQ

Else throw RREQ

End If

End

j returns RREP with reverse path

i choose route path with smallest ω

Return route path

End

3.4 路由维护

无人机自组网中节点i每隔周期T向外广播hello数据包来检验与邻居节点之间的链路是否连通。若邻居节点收到i节点的数据包，则证明链路通畅，直接将i节点的信息放入neighborlist中，若超过规定时间未收到i节点的hello包，则认为i节点已经脱离通信范围，将i节点从neighborlist中删除。

在i节点向目的节点传输数据包的过程中，若路径上i的邻居节点j由于移动导致i与j之间的链路断裂，无法继续传输，则i向上游节点发送RERR，并将j节点信息从neighborlist中删除，上游节点收到RERR后，重新规划路径。

4 仿真分析

为验证本文算法有效性，将本文算法与传统算法进行对比验证，仿真环境设置见表1,结果见图4。

表1 仿真环境参数设置

图4 仿真结果

1)投递成功率

投递成功率是指一定时间内正确接收的报文数量与发送报文总量的比值，是衡量网络传输效率的重要指标。如图4(a)所示，随着节点移动速度的增大，网络拓扑结构变化频繁，导致3种算法的投递成功率均有所下降。相比之下CWRA算法的投递成功率较高，是因为算法中引入的边界评价因子能够避免选用处于通信范围边缘的节点，克服了边缘效应，一定程度上可以减小链路断裂的概率；权值中的拥塞度参数能避免选择拥堵路径，防止出现因节点缓存已满导致数据包丢失的情况。

2)归一化路由开销

归一化路由开销是指每发送一个数据分组所需要的控制分组的数量，它可以反映网络传输效率，从图4(b)中可以看出，当节点速度较小时，相比于AODV，CWRA需要节点更多的信息，因此开销相对较大。随着节点速度的增长，3种算法的路由开销均有所增加，CWRA算法上升趋势较缓，是因为速度的增大导致另外2种算法路径出现断裂，产生额外的路由发现开销。边界评价因子的引入使得CWRA所选路径对拓扑变化的适应性变强，减小了路由发现频率。

3)端到端时延

端到端时延主要包括路由发现时延、数据包在接口队列中的等待时延、发送时延、重传时延等，时延在一定程度上影响着工作效能的发挥，结果如图4(c)所示。随着流量负载的增加，3种算法的时延都有明显上升，是因为负载的增大导致部分节点出现拥塞。CWRA算法在权值中加入节点拥塞度，可以缓解拥塞路径的传输压力，减小数据包在接口队列中的等待时延，达到减小端到端时延的效果。

4)网络生存周期

网络生存周期的定义为：网络中出现第1个能量耗尽节点的时间。网络生存周期能够反映出网络中节点能量均衡性，网络体系越完整，对无人机集群任务的完成越有利。从图4(d)中可以看出，随着发包速率的增加网络生存周期呈下降趋势，CWRA算法在权值中加入的节点剩余能量参数使得源节点在选择路径的过程中可以选择能量状况良好的路径，另外优化参数中的能量均衡参数可以避免相对能量低的节点出现在回溯路径中，延长低能节点的生命周期。

5 结语

针对无人机集群组网的特点，本文在贪婪算法的基础上提出能量-拥塞复合权值，能够在兼顾时延的基础上，筛选出稳定性较高的路径。引入的网络优化参数有效地提高了路径对拓扑变化的适应性和网络能量的均衡性。实验结果表明，相比于另外2种路由算法，CWRA算法在投递成功率、网络生命周期、端到端时延、路由开销等方面都有良好性能，这对于小型军用无人机集群组网路由算法的研究和实际应用具有一定的参考价值。