一种动态规划下的无人机消息传输路径优化方法

朱霏霏，王立松，刘 亮，葛子渊

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

1 引 言

无人机是全球新一轮科技革命和产业革命的热点，其产业发展关乎国家利益.对于很多需要无人机的任务，往往需要一个无人机组协同作业完成任务[1].此时，如何根据无人机组网络特性运用路由策略将消息快速传回到地面站就成了一个重要的技术问题[2].

无人机间通过无线传输建立高吞吐量链路，形成一个临时的、多跳的区域连接，是一种移动自组织网络[3].然而，由于无人机的高速不断运动，无人机的网络拓扑结构变化频繁.传统的MANET路由方法运用在无人机上出现投递率低、消息传输时间延迟大等问题，大大影响网络性能[4].

因此有必要对无人机网络路由策略提出更高的要求，有针对性地开展相关研究.由于现阶段利用无人机的很多场景都是基于任务驱动的[5]，人为地事先规划好无人机的运动轨迹，无人机只需按照规划好的轨迹运动即可[6]，现有很多方法[7，8]仅考虑无人机的当前位置状态，没有充分考虑现阶段的无人机基于任务驱动的这一特性，导致难以找到消息传输的最优对象.

针对以上问题，对于无人机基于任务驱动每时刻位置可知的情况，本文充分利用该特性提出了一种动态规划下的无人机消息传输路径优化方法，该方法通过全局考虑所有无人机每一时刻的位置，得到每一时刻消息传输的最优对象，进而得到消息到达目的节点的最优路径，减少消息传输的“乒乓效应”从而达到减少时间延迟的目的.此外，由于该方法避免了消息的很多不必要传输，使得更多消息能到达地面站，达到提高消息传输投递率的目的.

2 相关工作

针对无人机组的拓扑结构频繁变化的网络特性，很多研究者对其进行了研究，路由方法主要包括：

1)传统的无线自组织路由方法：文献[9]将传统的路由协议OLSR等运用在两个微型飞机和地面站的网络中，结果表明由于无人机的高速运动，传统的路由协议无法适应和快速应对快速变化的拓扑结构.主要原因在于传统的移动自组织路由协议都需要一定程度的链路稳定性来收敛[10]，而无人机的网络拓扑变化极快、链路的建立和断裂极度频繁，难以在极短的连接时间内改变传输对象，使得消息传输的对象很可能不是最优传输对象，造成传输效率低下[11].

2)DTN路由算法：由于无人机的消息允许存储携带，另一类方法是基于DTN网络考虑[12]，DTN玩过是一种适用间歇性连接的方法，纯粹的DTN路由方法如Epidemic Routing、Spray and Wait算法，通常适用于移动节点的有限泛洪且网络处于长时间断开状态[13]，使得网络中节点携带很多不必要的信息，易造成网络拥堵，同时也增大消息传输的开销，造成很大的时间延迟，不利于消息的传输[14].

3)基于地理位置的路由方法：文献[15]中将地理位置路由和DTN算法相结合，提出DTNgeo算法，将消息转发给空间上离目的节点更近的点，但此方法只考虑无人机当前位置，易造成消息的来回传输，实验显示“乒乓比例”很大.结合无人机运动信息可用的特点，文献[15]另外提出两个启发式算法DTNclose、DTNload，根据无人机当前的运动状态预测很短时间之后的未来时刻位置[16]，将消息转发给未来离目的节点较近的邻居节点，以达到消息尽早到达地面站的目的[17].这两种启发式算法仅仅只考虑下一时刻的位置信息，没有尽可能多的考虑以后时刻的位置，消息传输给目的节点的路径可能仍不是最优传输路径，实验结果显示“乒乓效应”比例仍然很大，时间延迟仍有可优化空间.

3 无人机消息传输的时间消耗模型

基于无人机消息传输的特点，建立无人机消息传输消耗时间的数学模型如下：

minT=F(x，t)

(1)

其中x表示无人机ID，x的范围为[1，N](N为执行任务的无人机的个数)，特别地，我们定义地面站的ID为0；t表示某一时刻；F表示在t时刻x无人机上携带的消息最早到达地面站的时刻.

特别地，当消息到达地面站时，消息传输过程结束，由此可以得到公式(1)的一个特殊值：

F(0，t)=t

(2)

此外，无人机在执行任务过程中，即使消息没法以多跳的形式传输给地面站，在任务结束时也会飞回地面站将消息带回，所以消息最晚到达地面站的时刻为任务结束时刻，即：

Fmax(x，t)=Final

(3)

结合无人机消息传输的特性，在t时刻无人机x消息的传输策略为如下两种之一：

1)transmit：若将消息传输给其某个邻居节点可以使消息更早到达地面站，则t时刻将该消息transmit给它的那个邻居节点.

2)carry：若当前节点相比其邻居节点可以使消息更早到达地面站，则carry.

t时刻的消息传输策的略选择只要考虑该策略使消息到达地面站的时间顺序，选择消息到达地面站时间较早的作为t时刻无人机x的消息传输对象.由此我们可以得到：

(4)

4 DPTM算法

基于第3节的无人机消息传输的时间消耗模型，这一节介绍一种动态规划下的无人机消息传输路径优化方法——DPTM算法.首先，介绍DPTM算法中用到的几个变量及其含义如表1所示.

表1 变量含义表Table 1 Meaning table of variables

对于计算任意i无人机每一时刻的消息传输对象next(i，T)，DPTM算法的具体步骤如下：

步骤1.定义状态函数，得到状态转移方程及状态转移方程的边界条件.

由上一节无人机消息传输的时间消耗模型，得到无人机i在t时刻的状态函数：F(i，t)；

由公式(4)，得出无人机i的状态转移方程：

(5)

其中，ζi为t时刻i无人机的邻居节点集合.

此外，根据公式(2)(3)得到i无人机的状态转移方程的边界条件：

F(0，t)=t

(6)

Fmax(i，t)=Final

(7)

步骤2.采集所有无人机每一时刻的位置.

由于无人机的运动轨迹由地面站实现规划好，所以地面站可以得到所有无人机每一时刻的位置，得到location(N，T).

步骤3.计算无人机间的距离，得到i无人机t时刻可通信的邻居节点.

计算t时刻i无人机与其余任意j无人机的距离d(i，j)，将i与其他无人机间距离记录至d(N，N).若∀j∈N，d(i，j)≤Range，则无人机i与无人机j可进行通信，将j并入集合ζi，最终得到无人机i在t时刻的邻居节点集合ζi.

步骤4.根据状态转移方程(5)得到当前时刻的传输下一跳，直至迭代更新完所有时刻，得到无人机每一时刻的最优消息传输对象.

根据公式(5)-公式(7)，首先比较当前时刻与下一时刻的状态函数值，若下一时刻的状态函数值F较小，则将消息carry.当F(i，t+1)

更新完F(N，T)和next(N，T)后，令t=t+1，并判断是否到达Final时刻，若t

随着时间的推移，该算法最终迭代收敛得到无人机在每一时刻的消息传输对象next(N，T)，具体算法如表2所示.

表2 DPTM算法Table 2 DPTM algorithm

无人机组在执行任务过程中按照DPTM算法得到的传输对象进行传输，在执行过程中若当前无法与其通信，则carry，直到可与该传输对象进行通信才transmit.

5 仿真实验及其分析

5.1 仿真设置

本文用The ONE仿真器实现对DTNgeo、DTNclose、DTNload和DPTM的路由算法仿真.仿真场景为基于任务驱动的典型场景-侦查搜救，为了尽快找到目标人物并解救，由地面站事先规划好每个无人机的运动轨迹，收集地面消息并快速传输回地面站[18].仿真实验借用文献[15]中无人机数目最多的情况，如图1所示.

图1 仿真实验场景图Fig.1 Simulation experiment scene graph

其中Ground为地面站，MAV7-11为searching MAV，执行搜寻任务并收集信息，同时也可以作为消息传输的中继；MAV2-5为ferry MAV，只作为中继，帮助searching MAV将消息快速传输到地面站.搜寻轨迹如图中所示，无人机间相互协作将搜寻到的消息尽快传输到地面站Ground，由地面站拼凑出正片区域内的地形地貌，找到目标人物所在位置.

此外，实验过程中的具体参数设置如表3所示.

表3 实验参数表Table 3 Experimental parameters

5.2 仿真结果和分析

实验中分别针对不同大小的时间间隔F进行实验，根据The one仿真实验的数据，以投递率、平均时间延迟、平均跳数、乒乓比例作为评价指标，整理分析得到DPTM与DTNgeo、DTNclose和DTNload算法的结果.

1)不同算法在不同间隔实验中的投递率比较

图2结果表明在实验时间8min中，这四种路由算法的投递率都很高，均在85%以上，DPTM相比较其他算法，投递率上升到90%.由于DPTM算法能得到消息的最优传输路径，避免了其他算法过程中很多不必要的传输，使得更多消息能到达地面站.

2)不同算法在不同间隔实验中的平均时间延迟比较图3结果表明，DPTM算法较其他几个算法，在不同的F下时间延迟均得到了减少.原因在于DPTM算法根据所有无人机每一时刻的位置信息，得到消息能尽快到达地面站的最优路径.DTNgeo只考虑当前时刻的位置信息，DTNclose和DTNload也都只考虑了下一时刻的位置，如此得到的消息传输对象对于当前的网络拓扑结构来说是最优的，然而对于不断变化的无人机网络，某一时刻最优的对象对于整个过程来说很可能不是最优，所以造成较大的平均时间延迟.

图2 DPTM与DTNgeo、DTNclose和DTNload算法的投递率对比图Fig.2 ComparisonofdeliveryratiobetweenDPTMandDTNgeo,DTNcloseandDTNloadalgorithms图3 DPTM与DTNgeo、DTNclose和DTNload算法的平均时间延迟对比图Fig.3 ComparisonofaveragedelaybetweenDPTMandDTNgeo,DTNcloseandDTNloadalgorithms

3)不同算法在不同间隔实验中的平均跳数比较

图4结果表明，DPTM算法较其他几个算法，在不同的F下跳数均得到了减少.原因在于DPTM算法根据所有无人机每一时刻的位置信息，事先规划好最优传输路径，让无人机记住每一时刻的传输对象，若能建立通信链路则传输，否则携带，这样减少了消息传输的不必要来回“乒乓”，从而得到较少的平均跳数.DTNgeo只考虑当前时刻的位置信息，DTNclose和DTNload也都只考虑了下一时刻的位置，如此得到的消息传输对象对于当前的网络拓扑结构来说是最优的，然而对于不断变化的无人机网络，消息很可能在未来某一时刻又被重新传回来，这就导致不必要的来回“乒乓”传输，造成平均跳数增加.

4)不同算法在不同间隔实验中的乒乓比例比较

图4 DPTM与DTNgeo、DTNclose和DTNload算法的平均跳数对比图Fig.4 ComparisonofaveragehopcountbetweenDPTMandDTNgeo,DTNcloseandDTNloadalgorithms图5 DPTM与DTNgeo、DTNclose和DTNload算法的乒乓比例对比图Fig.5 Comparisonofping-pongratiobetweenDPTMandDTNgeo,DTNcloseandDTNloadalgorithms

图5结果表明DPTM算法能使乒乓比例大幅下降至5%以下.根据DPTM算法的理论分析，该算法能找到最优传输路径、完全消除乒乓比例.然而在无人机实际执行任务过程中，消息传输速率虽快，但也需消耗时间，所以对于一些连接时间极短、负载过多的情况，有无人机可能不能将消息按照规划全部传输给当前规划好的下一跳，使部分消息错过最优对象可能造成小比例的乒乓.即便如此DPTM算法还是大幅的降低了乒乓比例，减少了时间延迟.

6 总 结

本文提出一种动态规划下的无人机消息传输路径优化方法，通过全局考虑所有无人机每一时刻的位置，得到每一时刻消息传输的最优对象，进而得到消息到达目的节点的最优路径，达到降低乒乓比例、减少时间延迟和减少能源损耗的目的.通过仿真实验将DPTM与DTNgeo、DTNclose和DTNload算法相比较，结果表明DPTM算法在消息投递率方面稍有提高；在平均时间延迟上有了近6%的降低，当传输重要数据比如本文中提到的搜救场景中目标人物的周边消息时，6%的降低可给搜救节省很多的时间，提高人物的得救率；在平均跳数方面，平均跳数降低至4.8以下，减少传递跳数，可减少无人机用于传输过程中的能量浪费，使其将更多的能量用于搜索信息方面；在乒乓比例方面，乒乓比例有了明显的降低，降低至5%以下，使无人机将尽可能多的能量用于执行任务，较少能源浪费.

由于现阶段很多无人机的应用场景都是由地面站事先规划好运动轨迹，如本文中实验的侦查搜救场景，无人机只需按地面站事先规划好的轨迹运动即可，所以该算法在现阶段的无人机组通信中具有重要意义.