延迟容忍网络中紧急状态驱动的多摆渡机飞行控制算法

张小亮，王立松，刘 亮

(南京航空航天大学 计算机科学与技术学院，南京 210000)E-mail ：zhangxiaoliangnjit@163.com

1 引 言

多无人机相互协作被应用于工业、农业、军事、抢险救灾等领域，而多无人机的通信是多无人机系统的设计的最重要的问题之一.基于如地面中继站、卫星等的基础设施实现网络有很多限制，一般采用飞行自组织网络(Flying Ad-Hoc Networks—FANET)实现多无人机之间的通信[1-3].由于无人机快速移动的特性，导致无人机自组网会出现随机的频繁的中断.延时容忍网络(Delay-tolerant Networking—DTN)原则上能够解决这个问题.DTN因为具有“存储—携带—转发”的特性，所以适用在节点间没有端到端通信的情况[4,5].

智能的路径规划配合路由协议能够有效的减少包的损失和消息延迟等[6].关于摆渡节点的路径规划问题，近年来有不少研究.文献[7]中首先提出了MF机制，并针对普通节点是静止的情况设计一个摆渡节点路线.指出该问题是旅行商(TSP)问题，并用通用方法解决TSP问题.文献[8]中在文献[7]中提出的消息摆渡机制的基础上进行扩展.根据摆渡节点或者普通节点主动运动，将消息摆渡机制分为普通节点发起消息摆渡机制、摆渡节点发起消息摆渡机制.文献[9]对DTN中多摆渡节点路线进行设计.将摆渡节点间交互的方式分为三种情况提出算法来求解路径.文献[10]中将移动的任务节点按照地理位置进行分簇，然后设计摆渡节点路线穿过簇的中心.文献[11]中每次都用最小概率去和每个移动节点接触.移动节点-摆渡节点接触概率又反过来决定了下一轮的摆渡节点的路线.文献[12]中是基于图像获取率的奖励函数来选取无人机的中继航路点，然后还是转化TSP问题求解路径.文献[13]提出基于预测和地理位置信息的路由算法，针对典型搜救场景这一小型任务进行模拟实验，摆渡机按照预设的航路点在执行任务区域和地面站之间乒乓方式飞行.文献[14]针对无人机采集图像任务，采用了静态和在线的路径设计方法.

我们发现，目前摆渡节点的路径设计方法主要针对稀疏节点的网络[7-9，12]，且在TSP求解航路点问题基础上提出.在设计出航路点后，摆渡节点通常按照航路点作简单循环方式飞行.但是该飞行方式下，摆渡机无法根据网络中任务机节点的拥塞状况及位置信息做出及时调整，从而导致平均消息延迟过长.在时间关键任务中，数据传输延迟是考虑的关键因素[15].然而在小型搜救任务等小面积网络中，我们可以应用基于一跳的低通量网络传递更多的控制指令等消息来进行实时控制[13，16].所以在设计出摆渡机航路点之后，对于飞行方式进一步优化是有必要的.

本文针对无人机的典型搜救任务设计了一个小面积DTN的单播消息摆渡模型，在已有的航路点基础上设计了一种紧急状态驱动的摆渡机飞行控制机制.通过地面站的调度和分配，实时控制摆渡机的飞行方向.从而缓解了该场景下的拥塞问题，降低了消息平均延迟.本文主要分为以下几个部分：第二节介绍了小面积DTN的网络模型.第三节从地面站端和摆渡机端介绍了紧急状态驱动的摆渡机飞行控制算法.第四节针对任务机移动场景进行仿真实验并分析实验结果.第五节对全文进行总结.

2 网络模型

2.1 混合网络技术

本文参考已有的混合网络技术设计小面积DTN的整体网络构架.文献[13,16]中采用了高通量和低通量混合网络技术进行无线通讯.其中低通量网络传递较小的数据量，如GPS数据，控制消息，还有本文的紧急信号等.高通量网络能传递较大的数据量，如图像数据.

低通量网络可以采用XBee-PRO(IEEE 802.15.4)技术.它的覆盖半径长达1.5km，低通量(小于80kbit/s，所有无人机共享)能传递控制消息，遥感数据，消息接收确认等消息.XBee-PRO将所有无人机和地面站连接，所有无人机的GPS数据(经度，维度，高度)，方向，速度等数据在无人机和地面站范围内按照一定频率广播.

高通量网络可以采用Wi-Fi(IEEE 802.11n)技术.它是一种范围短，高通量的通信技术.其通信范围为200-300m，UDP通量为80-100Mbit/s.为了防止和XBee-PRO干扰，Wi-Fi频率可以与XBee-PRO设置不同的频率.高通量网络主要传递图像等较大的数据.

2.2 场景建模

在如搜救之类的任务中，任务区域通常是远离地面站的一片区域.执行任务的任务机在此任务区域内的一小片区域按照一定轨迹飞行来收集该子区域的图像或者其他数据.摆渡机按照规定的路线在任务区域和地面站之间来回飞行，最终将任务机收集到的消息传递到地面站.针对典型搜救场景，我们设计了小面积DTN单播消息摆渡(Message Ferrying-MF)模型.MF机制首先在文献[7]提出，为了解决高度分区网络中摆渡节点的路径规划问题.我们认为在诸如搜救等任务中可以借用该思想，但是和之前的MF机制又有区别.

假设N=1,2,…，k是k个收集消息且需要将传递消息到地面站g的任务机的集合.F=f1，f2，…，fl是l个负责将任务机消息传递到地面站的摆渡机的集合.无人机的高通量网络的通讯半径为r.D=D1，D，…，Dk是所有任务机的移动区域的集合.任务机飞行区域的最小外接圆为E，半径为R，圆心为e.网络示意图如图1所示.

图1 小面积DTN中消息摆渡模型Fig.1 Message ferrying model in small-area DTN

小面积DTN的单播MF网络有以下性质：

性质1.地面站g距离任务机飞行区域D的最远距离Rmax小于等于低通量网络的覆盖半径Rl，记为：Rmax≤Rl.

性质2.摆渡机一次循环飞行，通讯圆覆盖的面积Ac小于等于覆盖区域D的最小外接圆面积Ae，记为：Ac≤Ae.

2.3 延迟建模

假设ft(i)是t时间分配给任务机i的摆渡机，摆渡机按照Tft(i)路线飞行，wig是任务机i等待摆渡机飞至任务机附近将消息全部接收的等待时间，cij是摆渡机从任务机i到地面站的时间，Δd表示由于任务机移动带来的时间差.如果任务机i的消息不经过其他节点而完全由摆渡机传递到地面站g，则任务机节点i的最大消息延迟的digmax可以表示为：

digmax=wig+cig+Δd

(1)

因为任务机在传播过程中能通过其他无人机进行消息摆渡，所以则任务机节点i的消息延迟dig和digmax有如下关系：

dig≤digmax

(2)

假设lft(i)iTft(i)表示摆渡机ft(i)按照Tft(i)路线从当前位置到任务机i的距离，ligTft(i)表示摆渡机ft(i)按照Tft(i)路线从任务机i到地面站g的距离，无人机的飞行速度为v，由(1)得：

(3)

由于Δd是任务机移动带来的时间差，任务机是执行主要收集数据任务的无人机，我们一般不能改变.所以本文考虑优化公式(3)中前两项的值.

3 基于紧急状态的多摆渡机飞行控制方法

3.1 基本思想

图2 算法示意图Fig.2 Algorithm diagram

如本文的飞行控制算法是指摆渡机的飞行轨迹控制算法.如图2所示，假设G、A、B是摆渡机的航路点.其中G为地面站，即消息的目的地.Si表示任务机.Fi表示摆渡机.r为摆渡机的通讯半径，a、b是以S1为圆心，r为半径做出的圆与AB的交点.Rl表示低通量网络的覆盖圆半径，地面站能够接收到该圆内节点发送的GPS数据和本文中的紧急信号等消息.摆渡机F1按照G→A→B→G路径顺时针方向循环飞行，F2按照G→D→B→G路径顺时针方向循环飞行.任务机的消息数在不停的增长，如果不及时往地面站方向转移，则会导致消息的平均延迟过长.我们研究的问题是在各航路点已定的前提下对飞行方式进行优化，从而来减少消息的平均延迟.

传统方式采用丢包或者接收速度的方法来处理DTN中的拥塞[17].本文利用主动使摆渡机飞行的方法来缓解拥塞.算法基本思想如下：

首先，对于单架摆渡机本身，如果摆渡机F1此时在(3，0)顺时针飞行.若按照原方向做循环飞行，那么将S1任务机的消息接收到返回地面站G需要走12的路程.在本文方法中，当S1中的消息数超过预警值时，S1此时置为紧急状态.然后使与其配对的摆渡机此时调转方向，即按路径F1→B→b.将消息接收后，然后再选择一个最短距离路径，即b→B→G，那么该消息到达地面站总共所走的距离为7.所以该实时控制的方法，大大减少了时间.

(4)

易证明，digmax+≤digmax.从而证明及时调整航向有利于减少消息延迟.

其次，我们借用了操作系统中的先来先服务的调度思想来处理多架任务机紧急的情况.当此时有多个紧急状态的任务机需要分配摆渡机，那么地面站优先分配为发生时间较早的那一架任务机分配摆渡机.如果同时发生紧急状态，优先为分配编号较小的那一架任务机分配摆渡机.

图3 单位时间处理时序图Fig.3 Processing sequence diagram in unit of time

为了更加清楚的表达本文所提方法的工作原理，我们用SysML对算法执行过程进行建模.网络中有3个对象：地面站，任务机，摆渡机.每个单位时间中，首先各无人机检测本身的消息存储数，在本机进行判断紧急或非紧急.并通过低通量网络发送紧急或者非紧急信号至地面站.地面站更新各无人机的状态并根据先来先服务的思想为任务机分配摆渡机，然后将改变Locked位指令信息发送至摆渡机.最后摆渡机根据飞行控制算法做出调整后飞行△t时间.时序图如图3所示.下文将给出相关定义并围绕时序图中的地面站更新紧急任务列表算法，先来先服务思想的分配算法以及摆渡机中飞行控制算法等方面进行详细的阐述.

3.2 地面站集中式处理算法

本文采用地面站集中式结构管理整个网络无人机的紧急状态以及做出相应的控制.随着时间的推移，每架无人机的状态会发生改变，更新紧急状态是摆渡机飞行控制的基础.地面站控制算法中所提到的相关数据结构以及相关名词解释如下：

定义1.紧急任务机列表(emergeSearchList) 是按照紧急状态产生时间顺序存放当前网络中所有的紧急状态的任务机编号的列表.

定义2.紧急任务机-摆渡机配对列表(emergeMap)是存放紧急状态任务机编号以及与其配对的摆渡机编号的键值对列表.

定义3.紧急摆渡机列表(emergeFerryList)是存放紧急状态摆渡机编号的列表.

定义4.紧急状态是无人机中消息存储数超过预警值后无人机所处的状态.

定义5.Locked位是任务机和摆渡机相互间是否能够配对的标志位.当摆渡机分配给紧急状态任务机时，摆渡机和任务机的Locked位置为true.当摆渡机中的消息存储数超过预警值，则将摆渡机和原先与之配对的任务机解锁，即将任务机和摆渡机的Locked位置为false.

3.2.1 更新紧急列表算法

更新算法主要分为取消非紧急状态项和增添紧急状态项两部分.原先紧急状态的无人机中的消息数降低到0，我们将取消各列表中相应的紧急状态项.当无人机中的消息数超过规定的预警值，而且之前不在列表中，将要添加相应的项.

添加紧急状态项分为以下步骤.

1)更新emergeFerryList.在emergeFerryList中添加新项时，我们需要作出特殊处理.因为当摆渡机中的消息数过多，如果前一时刻自身分配给任务机，此时应该解除分配关系，使得摆渡机立刻飞向地面站.原先紧急的任务机在下一个时刻重新分配摆渡机.

2)更新emergeSearchList.根据无人机的紧急信号更新emergeSearchList.

3)更新emergeMap.根据任务机和摆渡机配对算法更新emergeMap.添加紧急状态项算法示意图如图4所示.

图4 添加紧急状态项算法Fig.4 Adding emergency term algorithm

3.2.2 任务机和摆渡机配对算法

利用操作系统中先来先服务的调度思想，我们首先根据紧急状态发生的时间顺序在emergeSearchList尾部插入新项.然后从前往后遍历emergeSearchList，利用任务机和摆渡机配对算法为每架紧急任务机找到摆渡机，最后摆渡机根据飞行控制算法飞行.

一架摆渡机可以将一架或者多架任务机的消息传递到地面站.同样一架任务机也可能由多架摆渡机来传递消息.假设任务机i对应的摆渡机集合Fi，F是网络中所有摆渡机的集合，则Fi⊆F.Fi(t-Δt)为前一时刻Fi中还未分配的摆渡机集合.ft(i)为t时间与任务机i配对的摆渡机，是距离紧急状态任务机i最近的未配对的摆渡机.ft(i)可以表示为：

(5)

3.3 紧急状态驱动的摆渡机飞行控制算法

无人机的运动模型可以参考高斯-马尔科夫运动模型，它意味着摆渡机前后时刻的运动是有联系的，不是完全随机的[18].该算法在摆渡机上执行，为每架摆渡机提供实时控制.另外需要强调的是，该算法是建立在已有航路点基础上的.飞行控制算法的思想为：如果摆渡机被分配给紧急状态的任务机，则摆渡机朝着紧急状态任务机飞行，建立通讯之后再朝向地面站飞行.如果摆渡机自身紧急，那么朝着地面站方向飞行.如果摆渡机自身不紧急，也没有分配给任务机，那么按照简单的循环方式飞行.综上，摆渡机飞行控制算法总共有三种飞行模式：循环飞行、朝地面站飞行、朝紧急任务机飞行.摆渡机的飞行控制算法伪代码如下：

算法1.flyControl Algorithm.

1：//摆渡机按照飞行控制算法，每次飞行Δt时间

2：procedureflyControl (Δt)

3：//如果摆渡机没有和其他任务机建立配对且该机不紧急

4：//表现为摆渡机上的Locked位为false

5：ifLocked==falsethen

6： circleMove(Δt) ▷循环飞行

7：else

8：//当摆渡机因为自身的消息数超过预警值，即本机紧急

9：ifmsgNumber>ferryTriggerthen

10： moveToStation(Δt) ▷朝地面站飞行

11：//当摆渡机和任务机建立配对关系

12：else

13：//摆渡机和紧急任务机无法建立高通量联系

14：ifcan not connecting emerge SearchHostthen

15： moveToEmerge(Δt) ▷朝紧急任务飞行

16：else

17： moveToStation(Δt) ▷朝地面站飞行

18：endif

19：endif

20：endif

21：endprocedure

4 仿真实验及其实验结果分析

4.1 实验场景及参数设置

本文实验是在TheOne模拟器中进行.TheOne是一个机会网络环境模拟器，它可以模拟不同路由协议，不同的运动模型的DTN网络的消息传输，还可以实时交互式可视化模拟和结果.我们在任务机移动场景中分别以简单循环飞行方式和本文提出的基于紧急状态量驱动飞行方式两种飞行方式进行模拟实验，从而对比两种算法的优劣.

实验场景如图5所示.假设有4架摆渡机(f10-f13)，9架任务机(u1-u9)和1个地面站(g0).其中任务机按照Z型路线循环飞行，任务机按照图示路线飞行.各无人机从各自按照轨迹循环飞行.

图5 任务机移动场景Fig.5 Moving search UAV scene

其他试验参数设置如表1所示.

表1 实验参数Table 1 Experimental parameters

4.2 实验结果及其分析

本文算法由无人机的消息存储量触发无人机的紧急状态.因为任务机和摆渡机可以分别设置预警值，为了分析不同预警值对传递消息的各个指标的影响，我们采用控制变量法进行实验.我们先设摆渡机的预警值为无穷大，设置不同的任务机的预警值进行实验.然后从中选取合适的任务机预警值固定不变，再去改变摆渡机的预警值进行实验.任务机移动场景实验数据如图6-图9所示.

分析以上实验结果可以发现：

1)本文提出的紧急状态量驱动的摆渡机飞行方法的投递率、消息平均延迟与简单循环在动态场景下相比均有提升. 在该动态场景下，各任务机节点按照一定的运动轨迹运动，任务机节点之间有一定的概率发生通讯.如图6-图7，紧急信号量驱动的飞行方式相较与简单循环飞行方式，仅任务机设置预警值时，投递率相近，平均消息延迟减少约20%.如图8-图9，任务机选取600的紧急预警值固定不变，改变摆渡机的预警值时，平均消息延迟减少约47%.而且加入摆渡机预警值是防止网络负载过高时，摆渡机无法及时返回地面站造成网络拥塞，增强了算法的鲁棒性.平均消息延迟平均值对比如表2所示.其中+表示提高，-表示降低.

图6 单预警值紧急驱动与简单循环方式投递率比较Fig.6 Deliveryratecompa-risonofsinglewarningvalueemergency-driveandsimplecycle图7 单预警值紧急驱动与简单循环方式平均消息延迟比较Fig.7 Delaycomparisonofsinglewarningvalueemer-gency-driveandsimplecycle

图8 单/双预警值紧急驱动与简单循环投递率比较Fig.8 Deliveryratecomparisonofsingle/doublewarningvalueemergency-driveandsimplecycle图9 单/双预警值紧急驱动与简单循环投递率比较Fig.9 Delaycomparisonofsingle/doublewarningvalueemergency-driveandsimplecycle

表2 平均消息延迟平均值对比Table 2 Average delay comparison

2) 当设置预警值过小时，性能表现不佳;预警值足够大时，其运动方式和简单循环方式相同.如果任务机的预警值设置过小时，摆渡机会很快地向任务机靠近，并将消息摆渡到地面站.导致一次摆渡的消息数量较小，从而导致消息在任务机上堆积.如果摆渡机的预警值设置过小时，摆渡机接收的消息不多就往地面站飞行，导致消息在任务机上堆积.所以预警值不能设置过小.当预警值设置很大时，将不会触发紧急状态，所以紧急状态驱动飞行方式将和简单循环飞行方式相同.

5 总 结

本文针对典型的搜救场景，提出了小面积延迟容忍网络下的单播消息摆渡模型.并在简单循环飞行方式基础上提出了一种基于紧急状态的摆渡机飞行控制策略.当消息数超过一定的预警值，无人机将变为紧急状态，然后通过地面站的调度和分配来驱动摆渡机飞行.实验证明，当选取合适的预警值时，紧急状态驱动摆渡机的飞行方式会使消息的投递率和平均延时表现提升.本文是在基于范围较小的低通量网络中实现了紧急状态驱动的飞行控制算法，未来考虑扩展到范围更大的网络中.