2020, Vol. 35
2. 解放军94619部队，安徽 六安 237132;
3. 南京中医药大学 信息技术学院，南京 210016
2. Unit 94619 of PLA, Lu'an 237132, China;
3. College of Information Technology, Nanjing University of Chinese Medicine, Nanjing 210016, China
微型无人机是一种小型的无人机, 重量仅有几公斤, 已广泛应用于航拍、农保、灾害救援、军事等领域.微型无人机通常搭载计算、无线通信、传感器和摄像机等设备, 可以收集信息并将数据传输到地面站[1-2], 具有成本低、携带方便、机动性高、无人员伤亡风险等优点, 已成为全球新的科技研究和产业应用的热点.
受限于能耗、飞行距离、通信范围等因素, 单个微型无人机的能力相对较弱, 需要无人机集群协同工作才能完成较复杂的任务.无人机间通过无线链路建立连接, 形成一个多跳的自组织网络, 实现无人机之间以及无人机到地面的数据通信.但是, 无人机的运动将引起网络拓扑的动态变化, 增加了数据传输的丢包率和时延.国内外对无人机自组织网络技术已进行广泛的研究, 并且获得了很多成果, Lva等在文献[3]中进行了详细综述.
现有的无人机网络研究大都假设无人机的运动是未知的、不可控制的, 即网络拓扑是动态变化且不可预测的.在实际应用中, 无人机集群通常是高度任务驱动的[4-5].由于GPS导航定位、惯性陀螺仪等的应用, 无人机的地理位置信息是可感知的.人们通常事先做好任务规划, 让无人机按照规划好的轨迹去执行任务[6].
无人机集群协同航迹规划是任务规划的重要组成部分, 其目的是在无人机飞行性能、飞行环境、任务协同要求等约束条件下, 为每架无人机设计出可行的飞行航迹, 使其在给定的性能指标下达到总体最优或者较优[7].无人机的协同航迹规划方法可以分为确定性方法和启发式方法两类.确定性方法主要有几何航迹规划方法[8]、障碍回避的航迹规划方法[9]、动态航迹规划方法[10]等.启发式方法主要采用各类智能算法[11-13], 如蚁群算法、进化算法、蜂群算法等.启发式方法利用贪婪等启发式思想[14], 对问题的解空间进行搜索以求得最优解.然而, 大部分航迹规划都是面向任务约束和环境约束的[15-17], 忽略了无人机集群的通信连接要求, 导致规划好的无人机集群在运行过程中出现网络连接中断的现象.无人机集群在执行任务时, 节点之间需要进行数据传输, 网络连接的中断会导致数据的丢失, 造成较大的传输时延.
文献[18]考虑了微型无人机集群在搜索与营救任务中的应用场景, 每架无人机将拍摄的照片传输到地面站进行分析以期发现搜索目标.文献[18]采用短距离高吞吐量无线通信技术(WiFi 802.11n)传递大尺寸的图像数据, WiFi 802.11n无线技术的传输距离在200 m左右, 当无人机与地面站或者无人机之间的距离超出通信范围时, 图像数据的传输产生中断.为了解决此类间断性网络的数据传输问题, 文献[18]引入了“摆渡” (Ferry)无人机在不连通的子网之间来回运动, 将各子网的无人机产生的数据通过多跳传送回地面站.但是, 该方案会导致较大的数据传输时延(甚至高达2 min, 而整个微型无人机集群搜索过程通常在10 min左右), 不适用于对时延要求较高的应用.
针对通信连接不能得到保证的网络, 实现数据传输通常使用延迟容忍组网(delay tolerant networking, DTN)[18-19]的方法, 然而这类方法会带来很大的时延.在搜索与营救等对时延要求较高的场景中[20], 为了确保数据能通过多跳传输快速传回地面站, 需要维持整个无人机网络的连通性.为了保持网络的连通性, 必须保证任意时刻所有无人机(包括地面站)都至少与一个其他无人机(或地面站)能够通信(即两个节点在彼此的通信范围之内), 因此, 如何部署无人机节点位置以及规划航迹尤为重要.本文研究发现, 合理地部署节点的初始位置, 并控制好无人机的运动轨迹, 可以保证网络经常处于连通状态.本文提出节点非均匀部署方法, 并设计同步与异步运动策略, 理论分析与仿真结果均表明, 经过规划后的无人机网络满足网络连通性要求, 具有很高的包传输成功率, 可极大地降低时延, 并且获得很好的节点负载均衡.
1 问题模型在搜索与营救场景中, 无人机拍摄一个区域, 并将图像数据通过短距离高吞吐量的无线WiFi通信技术传回地面.假定无人机集群部署在一定高度(如100 m)的空中平面, 可以在该平面上自由运动(即该平面上没有障碍物), 每台无人机(以及地面站)都知道自己及其他无人机的位置信息.地面站保持静止, 并且一般部署在搜索区域边界上(如边界中点位置). WiFi无线技术的传输距离在200 m左右, 离地面站较远的搜救无人机无法直接与地面站发送图像数据.本文将无人机群组成无中心的无线自组织网络, 让图像数据通过多跳传输到地面站. WiFi是一种多信道的无线通信技术, 在同一通信范围内的不同节点可以选择不同的信道来降低或消除干扰.即使是使用同一信道, CSMA/CA等无线MAC协议也很好地解决了冲突检测和避免等问题.因此本文在组网规划时并未考虑干扰因素.
微型无人机的运动约束主要包括飞行时间、飞行速度、转弯半径、无人机间的距离限制等.假设最大飞行时长为Tmax, 搜索时一般用巡航速度Vcruise, 可得最长飞行距离为Lmax=Tmax×Vcruise, 因此单个无人机的搜索区域是有限的, 记最大搜索面积为Ssearch.假设搜索区域为矩形, 横边长为X, 纵边长为Y, 则任务区域面积为Smission=X×Y.若实际搜索区域不为矩形, 则将其最小包围矩形(minimum bounding rectangle, MBR)作为搜索区域.假设地面站部署在横边中点位置, 使用WiFi传输图像数据, 其最大传输距离为Dmax.假设无人机之间允许的最小安全距离为Dmin, 则无人机之间的距离为d∈[Dmin, Dmax].转弯半径对航迹规划有一定的影响, 但不是主要因素, 因此本文在航迹规划时忽略了转弯半径因素.实际应用中, 只要将航迹进行转弯设计优化即可解决该问题.
容易得出, 在给定的Tmax搜索时间内, 集群实现搜索全覆盖的无人机数量下界是
为了使数据能尽快传回地面站, 需要无人机网络时刻保持连通.这里的“时刻保持连通”是指在任意时刻, 每台无人机(还有地面站G)的通信范围内至少有一台无人机(或者地面站), 下面是形式化定义.设某台无人机Vi(i∈{1, 2, …, N})在t时刻的位置Vi(t)=(xi(t), yi(t), zi(t)), Dist(Vi(t), Vj(t))表示在t时刻无人机i与无人机j之间的距离, 设地面站为V0, V0(t)=(x0(t), y0(t), z0(t)), 则无人机网络时刻连通性保证条件为
|
(1) |
在确保集群实现对任务区域搜索全覆盖的情况下, 不同的搜索方法需要不同数量的无人机来保证网络时刻处于连通状态.卷地毯式搜索是一种常用的搜索方法, 从矩形搜索区域的一边搜索到另一边, 如果有需要, 则在两边之间来回搜索.
假设无人机采用卷地毯式搜索策略, 从左边搜索到右边, 地面站在横边中点上.在初始时刻, 无人机在左边界(纵向)时, 边界无人机通信需要
为了与地面站保持时刻通信, 在横向上还要加通信中继.当
可以求得需要通信中继无人机的数量为
综上所述, 采用卷地毯式搜索时, 在初始时刻实现搜索全覆盖并保证网络连通需要的无人机数量为搜索无人机与中继无人机之和.通过合理的航迹规划, 初始时刻连通的网络在运动过程中可以保持连通.因此网络时刻连通需要的无人机数量下界为
|
|
(2) |
以上给出的下界并不是在任意情况下实现搜索全覆盖并保证网络时刻连通所需的最少的无人机数量, 而仅是采用卷地毯式搜索方法的下界.
如果采用其他搜索方法, 也可以求解出相应的最少无人机数量.搜索方法主要可以分为3类: 1)穷举覆盖式, 如扫描线式的往复搜索模式[21]、卷地毯式搜索[22]、Z字形平行搜索[23]等, 均实现对搜索区域的无遗漏覆盖; 2)启发式搜索, 如基于威胁度的搜索方法[24]、基于分布式模型预测控制框架与粒子群优化相结合的算法[25]等, 不需要对整个区域进行覆盖, 有效地降低了搜索问题求解规模; 3)随机搜索, 如协同区域随机搜索方法[26]等, 采用某种随机策略对区域进行搜索.
穷举式搜索很容易求出所需无人机数量的下界, 因为搜索总任务量是固定的, 而且单台无人机能完成的任务量也容易求解.启发式搜索和随机搜索由于很难事先确定搜索过程的任务量, 因此较难确定无人机数量的下界.由于这两类方法的搜索量一般小于给定的总任务量, 可以参考穷举式搜索方法, 给出无人机数量下界的一个“上限值”, 即这两类方法的无人机数量下界一般小于穷举式搜索方法.
例1 假设任务区域大小为X×Y = 800 m×800 m, 最大通信范围Dmax=200 m.单个微型无人机最大飞行时长为8 min, 巡航速度为5 m/s, 则最长飞行距离Lmax= 2 400 m.采用卷地毯式搜索方法, 边界无人机通信需要
当无人机的数量达到
当无人机的数量达到lower bound时, 可以实现搜索全覆盖并保证网络时刻连通, 此时影响网络连通性的因素为无人机节点的位置, 主要包括节点初始位置和节点在运动过程中的位置.初始位置由节点部署决定, 而运动过程中的位置由航迹规划决定.本节从节点的部署规划和节点运动规划两方面, 研究不同部署策略下网络中的负载情况, 以及不同运动策略下如何保证网络时刻连通性.
无人机群采用无线WiFi信号进行通信, WiFi技术及MAC协议已经很好地解决了干扰、冲突检测与避免等问题.在研究无人机部署问题时, 一般不将干扰问题作为重点因素[1, 13, 18], 所以本文重点考虑通信范围限制, 而并未考虑干扰问题.忽略干扰问题会导致理论分析结果与实际存在偏差, 实际应用中需要对本文的理论分析结果进行修正.
2.1 节点部署策略设搜索区域为矩形, 横边长为X, 纵边长为Y.使用卷地毯式搜索方法, 则横向的无人机一般距离较远, 不在通信范围内.数据首先沿纵向传输到横边, 然后通过通信中继传输到地面站.为了简化分析, 忽略在同一行之内的横向数据传输.由于无人机之间的避碰要求和通信约束等限制, 每一行可以部署的无人机的数量x∈[a, b](a≥ 1且a≤ b, a、b为正整数), 可以部署无人机的行数n∈[c, d](c≥ 1且c≤ d, c、d为正整数).
假设总共部署了n行无人机, 第i行部署了xi台无人机, 总共有
网络的总体负载表征的是无人机集群数据传输的负担, 而方差表征的是无人机节点的负载均衡性.定义一个评价指标
引理1 无人机总数为固定值时, 行数越少, 总体负载L的值越小.
证明 
由引理1可得节点部署规则1:在部署无人机时, 应该尽量减少行数来降低网络总体负载.
引理2 在行数固定和无人机数量固定的前提下, 非均匀部署(离地面站远的行无人机数量少, 离地面站近的行无人机数量多)可降低网络的总体负载.
证明 假设当前部署n行, 总体负载为L.减少第k层无人机的数量.若将该层无人机放到第k+1层以上(远离地面站的行), 则网络总体负载增加; 若将该层无人机放到第k-1层以下(靠近地面站的行), 则网络总体负载降低.由此可知:离地面站越远, 无人机数量越少, 网络总体负载越小; 离地面站越近, 无人机数量越多, 网络总体负载越小.
由引理2可得节点部署规则2:在部署无人机时, 在行数和无人机总数已知的情况下, 应该采取非均匀部署策略降低网络总体负载.当每行无人机数量有限制, 如x∈[a, b](a≥ 1且a≤ b, a、b为正整数)时, 让后面的行(i= n, n-1, …)取b, 而让前面的行(i=1, 2, …)取a, 且中间的行取值尽量小, 这样L才能取得最小值.
引理3 采用非均匀部署(离地面站远的行无人机数量少, 离地面站近的行无人机数量多)策略, 呈等比增长时节点负载的方差最小.
证明 仔细观察平均负载lk, l1=l为定值.当k>1时, 
由
由引理3可得节点部署规则3:尽量让非均匀部署呈等比增长, 可以降低节点负载方差, 让网络负载更加均衡.
当k=2时, 
综合引理2和引理3容易得出, 采用非均匀部署(离地面站远的行无人机数量少, 离地面站近的行无人机数量多), 既可以降低网络总体负载, 又可以优化无人机节点的负载均衡.
2.2 节点运动策略如果初始时刻节点采用均匀部署策略, 则节点分配到的任务区域大小相等, 在无人机速度保持相等的情况下, 无人机集群同步运动且运动轨迹相似, 则网络拓扑保持稳定(和初始状态保持一致).只要保证初始时刻无人机的网络是连通的, 那么网络的时刻连通性就容易得到保证, 但是在非均匀部署中, 无人机的相对位置将随着运动发生改变.
首先考虑如图 1(a)中的节点布置1-2-4-8, 每行之间的距离为Dmax.在这种布置下, 节点能获得最优的数据包负载均衡与较优的总体负载.为了保持网络的时刻连通性, 必须引进非同步运动策略.在初始时刻T0, 最左边的4个节点(A、B、C、D)是连通的, 并通过最下一行无人机和地面站通信.然后4台无人机同步向右搜索, 其他无人机保持悬停.在T1时刻, 节点A运动到靠近节点E时, 节点A停止运动(悬停在空中), 节点E接替节点A继续向右运动, 即仍然是4台无人机同步向右搜索, 而其他无人机保持悬停.这种异步的策略, 核心思想是当某台无人机靠近同一行的下一个无人机时就停止运动, 由下一个无人机“接力”.这样就能保证全程都有4台无人机在向右搜索, 并且网络的时刻连通性也得到了保证.
|
图 1 非均匀部署 |
接下来考虑如图 1(b)中的节点布置2-3-4-5, 在这种布置下, 节点能获得较好的数据包负载均衡和较优的总体负载.在这种布置下, 如果要采取“接力”的方法也是可以实现的.但是接力场景中部分无人机需要悬停等待, 浪费了搜索时间, 而让无人机节点同步运动可以减少搜索时间的浪费.
考虑到通信约束, 即网络需要时刻保持连通.如图 1(b)所示, 横向无人机均匀部署, 一般都超过通信距离Dmax.这时若要实现连通, 则要求纵向无人机之间要能够通信, 即两行之间的无人机在任何时刻的距离不能超过Dmax.
由于无人机同步运动, 同一行的无人机之间的距离保持一定.假设某一行两台无人机之间距离为a, 两行无人机之间允许的最大行距为hmax.为了实现纵向通信, 第i行的无人机至少要与第i+1行的一台无人机能够通信, 即距离小于Dmax.如图 2所示, 当第i行无人机处于第i+1行两台无人机连线的中垂线上时, 与这两台无人机的距离最远, 记为dmax, 可得
|
(3) |
|
图 2 无人机距离 |
例2 给定Dmax=200 m, X=800 m, 无人机节点采用如图 2所示的2-3-4-5非均匀部署方法.第2行布置3个节点, 
采用满足式(3)的不同行距hmax, 即可实现节点在同步运动的情况下仍然保证无人机集群的时刻连通性.若让无人机保持相同的速度, 则不同的行的搜索时间不一致, 节点数多的行搜索比较快.若让不同的行搜索时间保持一致, 则可以让无人机采用不同的速度, 即不同的行采用不同的速度, 让节点数少的行运动快一点, 而节点数多的行运动慢一点.
3 仿真实验仿真实验采用文献[18]设置的条件, 使用NS-3网络仿真模拟器进行实验, 该仿真软件很好地实现了无线通信模块的仿真.就本文采用的Wi-Fi模块而言, NS-3软件实现了基于IEEE802.11标准的无线网络接口控制器. WiFi模块包括各种传播损耗模型(如Friis、LogDistance、FixedRss、Random等)、传播延迟模型、速率控制算法、物理层、队列等, 其MAC模型实现了IEEE 802.11分布式协调函数, 根据网络实际来决定退避或者占用传输介质进行传输, 其传播损耗模型充分考虑了距离、干扰等因素, 如本文采用的自由传播损耗模型Friis.
假设搜索区域大小为800 m×800 m, 则任务区域面积Smission=640 000 m2.地面站在横边中点位置, 所有的无人机稳定在约100 m高的空中飞行.假设无人机通过WiFi 802.11n使用5 GHz频段进行图像数据传输, 最大通信距离为200 m.每台无人机每秒产生5个消息, 每个消息大小1 400字节(数据率为56 kbit/s)发送给地面站.
假设无人机最长飞行时间为8 min, 飞行速度为5 m/s, 则最大飞行长度Lmax=2 400 m, 无人机的运动使用路径点模型.在保证搜索全覆盖的情况下, 实现网络时刻连通所需的无人机下界lower bound=6台(具体求解见式(2)).本文研究6~16台无人机在不同的部署方法和航迹规划下的结果, 部分参数如表 1所示.
|
表 1 实验参数 |
本文使用以下几个指标评价经过节点位置部署和运动规划后的无人机网络的性能, 经过规划的网络满足式(1)的网络时刻连通性通信约束, 本文称之为通信约束网络(communication constraint network, CCN网络).
1) 包投递成功率(delivery ratio).包投递成功率定义为成功到达目的地的数据包占所有节点产生的发往该目的地的数据包的比率, 该比例表明了网络的可靠性.
2) 时延(delay).时延是指数据包成功到达目的地的时刻减去该数据包产生的时刻之差, 即数据包传输耗费的时间.该时延包括传输时延、传播时延、排队时延、携带时延等的和, 是衡量数据传输的重要指标.
3) 实际负载评价.本文中采用
4) 搜索效率.定义无人机网络完成的搜索区域面积占总任务区域的比率为任务完成率, 用来衡量任务完成情况.定义无人机网络完成的搜索区域面积与无人机群理论上最大可完成的搜索面积的比值为无人机利用率, 用来衡量无人机群的利用情况.
5) 时间代价.无人机网络完成搜索所需的时间, 即从开始到所有搜索无人机完成分配给它的任务所用的时间.
3.1 与DTN网络的比较通过仿真实验与文献[18]中的延迟容忍网络(delay tolerant network, DTN网络)比较, 从而验证本文CCN网络的性能.
3.1.1 节点数较少的情况图 3表示的是6台无人机下的CCN网络与DTN网络. 图 3(a)的CCN网络中节点为非均匀部署, 并且采用“接力”方法异步运动. 图 3(b)的DTN网络采用文献[18]中的方法, 2台搜索无人机加4台摆渡无人机(ferry MAVs).其中search标识的无人机代表搜寻无人机, 每个搜寻无人机覆盖200 m×200 m的范围进行数据收集, 无人机的移动轨迹如图 3所示. ferry标识为摆渡无人机, 它们按照指定的虚线轨迹移动来回运动, 用以连接子网并将数据传输到地面站.
|
图 3 节点较少的部署情况 |
1) 包投递成功率如图 4所示. DTN网络的包投递成功率呈锯齿状波动, 波峰与波谷的差距较为明显.因为DTN网络中能和地面站直接通讯的只有4台摆渡无人机, 而且摆渡无人机的摆渡路径都很长, 大部分时间都在地面站的通信范围之外, 所以摆渡期间会有大量的报文积累造成投递率逐渐降低.当摆渡无人机进入地面站通信范围时, 大量报文也随之完成投递, 投递率也会迅速提升形成一个峰值. DTN网络的最大投递成功率仅为82 %左右, 最低甚至达到11 %, 而CCN网络保持着将近100 %的投递成功率.总体而言, CCN网络大大优于DTN网络, 在整个480 s的仿真过程中, 两个算法的投递率最大差距会到达88 %左右, 最小差距也有17 %.
|
图 4 包投递成功率(6个节点) |
2) 时延概率累积分布函数如图 5所示(注意横轴为对数轴).在DTN网络中, 40 %的数据包的时延在几十秒, 35 %的数据包时延达到一百多秒, 9 %的数据包甚至达到两百多秒, 而在1 s之内的不到15 %.在CCN网络中, 99.9 %的数据包的时延在10 ms之内, 100 %的数据包的时延在50 ms之内.总体而言CCN网络相比DTN网络极大地降低了时延.
|
图 5 时延概率累积分布函数(6个节点) |
图 6表示的是12台搜索无人机下的CCN网络和13台无人机下的DTN网络. 图 6(a)的CCN网络中节点为均匀部署, 4行无人机, 每行3台, 并且采用同步运动. 图 6(b)的DTN网络采用文献[18]中的方法, 9台搜索无人机加4台“摆渡”无人机.
|
图 6 节点较多的部署情况 |
1) 包投递成功率如图 7所示. DTN网络的包投递成功率呈锯齿状波动, 波峰与波谷的差距较为明显. DTN网络的最大投递成功率为95 %左右, 最低甚至达到30 %.而CCN网络则保持着将近100 %的投递成功率.总体而言, CCN网络大大优于DTN网络, 在整个480 s的仿真过程中, 两个算法的投递率最大差距会到达70 %左右, 最小差距也有5 %.
|
图 7 包投递成功率(CCN网络12个节点, DTN网络13个节点) |
2) 时延概率累积分布函数如图 8所示(注意横轴为对数轴).可以看出, DTN网络中, 约60 %的数据包的时延在几十秒, 2 %甚至达到一百多秒, 而在1 s之内的不到28%.在CCN网络中, 99.9 %的数据包的时延在10 ms之内, 只有极个别数据包时延在10 ms以上, 最大时延为1 s左右.总体而言, CCN网络相比DTN网络极大地降低了时延.
|
图 8 时延概率累积分布函数图(CCN网络12个节点, DTN网络13个节点) |
综合比较不同数量节点下的网络, 下面分析搜索效率与时间代价, 如图 9所示.
|
图 9 搜索效率和时间代价 |
图 9(a)显示的是任务完成率.对CCN网络而言, 搜索任务接近100 %完成.而对DTN网络而言, 由于搜索节点只负责固定的搜索子区域, 在节点数少时, 任务完成率低, 节点数多时, 任务完成率提高.相比之下, CCN网络的任务完成率都高于DTN网络, 尤其是在节点数较少时.
图 9(b)显示的是无人机利用率.对CCN网络而言, 节点数较少时利用率较高, 节点数较多时利用率较低, 这是由于节点数较多时, 为了保持通信连通性使得重叠搜索率较高引起的.对DTN网络而言, 节点数多的无人机利用率高.相比之下, 节点数少时, DTN网络由于任务完成率低导致无人机利用率也低.而节点数多时, 由于DTN网络里面重叠搜索率较低, 无人机利用率甚至会略高于CCN网络.
图 9(c)显示的是时间代价.节点数的增加减少了完成搜索所需要的时间.对CCN网络而言, 由于完成的任务量一样, 节点数少时时间长, 而节点数多时时间短.对DTN网络而言, 由于不考虑完成的任务量, 只考虑单个无人机完成各自子区域搜索的时间, 在不同节点数的情况下, 时间保持一致.相比之下, CCN网络的时间比DTN网络长, 这是由于CCN网络完成的任务量大.但是在节点数较多时, CCN网络的搜索时间也下降到接近DTN网络.
3.2 与均匀部署策略的比较下面比较第2节中提出的不同节点部署和运动策略给网络带来的影响. 图 6(a)为12台无人机采用3-3-3-3均匀部署同步运动, 图 1(b)为14台无人机采用2-3-4-5非均匀部署同步运动, 图 1(a)为15台无人机采用1-2-4-8非均匀部署异步运动, 图 10为16台无人机采用4-4-4-4均匀部署同步运动.
|
图 10 CCN网络16个节点部署图 |
1) 包投递成功率. 3-3-3-3网络是99.9 %, 2-3-4-5网络是99.99 %, 1-2-4-8网络是99.9 %, 4-4-4-4网络是99.92 %.所有CCN网络都保持着极高的包投递成功率.
2) 时延概率累积分布函数如图 11所示(注意到横轴为对数轴).所有4种CCN网络中, 99.9 %的数据包的时延在10 ms之内, 只有极个别数据包时延在10 ms以上, 最大时延为1 s左右.所有CCN网络都保持着较低的时延.
|
图 11 不同CCN网络的时延概率累积分布函数 |
3) 节点负载如图 12所示(注意横轴中矩形表示不同的节点).可以看出, 在3-3-3-3和4-4-4-4等均匀部署的网络中, 存在个别节点负载远远高于其他节点.易知该节点为网络运行过程中离地面站最近的节点, 这将导致该节点传递数据的能耗特别高而较快死亡, 使网络发生中断, 降低无人机网络的整体寿命.而在2-3-4-5和1-2-4-8等非均匀部署的网络中, 节点的负载相对比较均衡, 不存在负载特别高的节点, 这样即可提高无人机网络的整体寿命.
|
图 12 不同CCN网络的节点负载 |
使用方差D、网络总体负载L以及
|
|
表 2 不同CCN网络的负载评价 |
就方差D角度而言, 非均匀部署网络的节点方差较小, 反映了其节点负载较为均衡.
就总体负载L角度而言, 非均匀部署网络能有效降低网络负载, 比如1-2-4-8网络有15个节点, 网络总体负载却比只有12个节点的3-3-3-3网络低.
就平均负载角度而言, 非均匀部署网络确实降低了网络的负载, 比如2-3-4-5网络有14个节点, 虽然总体负载比只有12个节点的3-3-3-3网络高, 但是平均负载却比它低, 说明负载降低了.
就评价指标V角度而言, 非均匀网络在有效降低网络负载的同时, 也获得了较好的节点负载均衡.同时验证了引理2和引理3, 即离地面站近的行无人机数量越多、离地面站远的行无人机数量越少(节点部署越不均匀), 网络的总体负载越少, 且节点负载均衡性越好.
4) 搜索效率(任务完成率)如图 13(a)所示, CCN网络的完成率都接近100 %(没有等于100 %的原因是网络中存在丢包现象). 图 13(b)显示的是无人机利用率, 均匀部署策略的利用率会比非均匀部署策略高, 这是因为非均匀部署的网络中无人机有时需要悬停等待或者其重叠搜索率较高.
|
图 13 不同CCN网络的搜索效率和时间代价 |
5) 时间代价如图 13(c)所示. 1-2-4-8网络的时间特别长, 原因是无人机的搜索区域不一样大, 个别节点需要搜索的面积太大而导致总体任务完成时间较长. 4-4-4-4网络的时间最短, 原因是其单个无人机的搜索区域最小. 2-3-4-5网络与3-3-3-3网络搜索时间一致, 原因是两个网络中的单个无人机的最大搜索区域一样.
4 结论本文以搜索和营救场景为例, 研究了在增加通信约束条件下, 无人机网络的规划问题.首先, 考虑了如何进行节点初始位置部署, 研究了不同节点部署策略(主要包括均匀和非均匀策略)的特点; 其次, 研究了如何进行运动规划, 在同步和异步策略下如何满足通信约束条件; 最后, 通过仿真实验验证了CCN网络有着极高的数据包传递成功率和较低的时延, 且本文提出的非均匀部署策略可以降低网络的总体负载以及优化节点的负载均衡性.
在非均匀部署策略中, 存在着无人机节点搜索任务量不同的问题.在异步运动策略中, 让无人机悬停则会浪费无人机的搜索时间.如何在优化网络负载与任务分配之间作一个权衡是值得研究的一个问题.
本文假设无人机是在自由空间中运动的, 采用的是卷地毯式的搜索方法.然而, 现实的空间大部分都属于障碍空间或威胁空间, 飞行是受限的.在受限空间中, 卷地毯式搜索可能不适用, 为了满足通信约束, 采用什么样的搜索方法、如何进行节点的位置部署和航迹规划方法都是值得研究的问题.
要保证网络时刻连通需要一定数量的无人机.当无人机数量不足以实现网络时刻连通时, 网络必然会出现间断, 如何尽可能地满足通信约束, 降低网络的中断时间是值得研究的.当无人机数量较多时, 通信约束比较容易得到满足, 网络中可能存在多条路径, 可以研究利用多径路由来优化节点负载等问题.
文献[18]首次在户外实际部署多达3台旋翼无人机进行无人机组网实验, 获得了与NS-3网络仿真软件一致的结果, 验证了NS-3仿真软件的有效性.受此激励, 本文也采用NS-3仿真软件对无人机部署进行了仿真, 验证了本文提出的网络规划方法的有效性.但是, 由于缺少足够数量的无人机, 本文并没有在实际的无人机群上进行部署.下一步作者将积极申请经费来购置足够数量的无人机进行实际部署, 并根据实验结果修改并完善本文的理论分析.
| [1] |
Asadpour M, Van den Bergh M, Giustiniano D, et al. Micro aerial vehicle networks: An experimental analysis of challenges and opportunities[J]. IEEE Communications Magazine, 2014, 52(7): 141-149. DOI:10.1109/MCOM.2014.6852096 |
| [2] |
Andre T. Application-driven design of aerial communication networks[J]. IEEE Communications Magazine, 2014, 52(5): 129-137. DOI:10.1109/MCOM.2014.6815903 |
| [3] |
Lav Gupta, Raj Jain, Gabor Vaszkun. Survey of important issues in UAV communication networks[J]. IEEE Communications Surveys and Tutorials, 2016, 18(2): 1123-1152. DOI:10.1109/COMST.2015.2495297 |
| [4] |
Samira Hayat, Evsen Yanmaz, Raheeb Muzaffar. Survey on unmanned aerial vehicle networks for civil applications: A communications viewpoint[J]. IEEE Communications Surveys and Tutorials, 2016, 18(4): 2624-2661. DOI:10.1109/COMST.2016.2560343 |
| [5] |
Muzaffar R, Yanmaz E. Trajectory-aware ad hoc routing protocol for micro aerial vehicle networks[C]. International Micro Air Vehicle Conference and Competition. Delft: Delft University of Technology, 2014: 1-7.
|
| [6] |
Anantapalli M K, Li W. Multipath multihop routing analysis in mobile ad hoc networks[J]. Wireless Networks, 2010, 16(2): 573-575. |
| [7] |
Li W, Cassandras C G. Centralized and distralized and distributed cooperative receding horizon control of autonoumous vehicle missions[J]. Mathematical and Computer Modelling, 2006, 43(9/10): 1208-1228. |
| [8] |
Pettersen K Y, Lefebe E. Waypoint tracking control of chips[C]. Proceedings of the 40th IEEE Conference on Decision and Control. IEEE, 2001: 940-945.
|
| [9] |
Lapierre L, Soetanto D P. A nonlinear path following with applications to the control of autonomous underwater vehicles[C]. Proceedings of the 42nd IEEE Conference on Decision and Control. Piscataway: IEEE, 2003: 1256-1261.
|
| [10] |
Kim B, Tsiotras P. Time-invariant stabilization of a unicycletype mobile robot: Theory and experiments[C]. IEEE Conference on Control Applications. Piscataway: IEEE, 2000: 443-448.
|
| [11] |
姚鹏, 王宏伦. 基于改进流体扰动算法与灰狼优化的无人机三维航路规划[J]. 控制与决策, 2016, 31(4): 701-708. (Yao P, Wang H L. Three-dimensional path planning for UAV based on improved interfered fluid dynamicla system and grey wolf optimizer[J]. Control and Decision, 2016, 31(4): 701-708.) |
| [12] |
夏瑞, 赵磊, 吴书宇, 等. 基于人工蜂群算法的无人机协同路径规划[J]. 无线互联科技, 2018, 15(13): 13-21. (Xia R, Zhao L, Wu S Y, et al. Drone cooperative path planning based on artificial bee colony algorithm[J]. Wireless Internet Technology, 2018, 15(13): 13-21.) |
| [13] |
尹高扬, 周绍磊, 吴青坡. 基于改进RRT算法的无人机航迹规划[J]. 电子学报, 2017, 45(7): 1764-1769. (Yin G Y, Zhou S L, Wu Q P. An improved RRT algorithm for UAV path planning[J]. Acta Electronica Sinica, 2017, 45(7): 1764-1769.) |
| [14] |
刘雨坤, 侯捷. 无人机航迹规划群智能优化算法综述[J]. 电子测试, 2017(24): 48-50. (Liu Y K, Hou J. A Summary of intelligent optimization algorithm for UAV path planning[J]. Electronic Test, 2017(24): 48-50.) |
| [15] |
Jin Y, Liao Y, Minai A A, et al. Balancing search and target response in cooperative unmanned aerial vehicle (UAV) teams[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetcis, 2006, 36(3): 571-587. DOI:10.1109/TSMCB.2005.861881 |
| [16] |
Dolgov D, Durfee E H. Satisficing strategies for resource — Limited policy search in dynamic environments[C]. The 1st International Joint Conference on Autonomous Agents and Multi-agent Systems, Part 3: Table of Contents. New York: ACM, 2002: 1325-1332.
|
| [17] |
Antonios Tsourdos, Brian White, Madhavan Shanmugavel. Cooperative path planning of unmanned aerial vehicles[M]. New York: John Wiley & Sons, Ltd, 2011.
|
| [18] |
Asadpour M, Hummel K A, Giustiniano D, et al. Route or carry: Motion-driven packet forwarding in micro aerial vehicle networks[J]. IEEE Transactions on Mobile Computing, 2017, 16(3): 843-856. DOI:10.1109/TMC.2016.2561291 |
| [19] |
Asadpour M, Egli S, Hummel K A, et al. Routing in a fleet of micro aerial vehicles: First experimental insights[C]. Proceedings 3rd ACM MobiHoc Workshop Airborne Networks and Communications. New York: ACM, 2014: 9-10.
|
| [20] |
Asadpour M, Giustiniano D, Hummel K A, et al. Now or later? — Delaying data transfer in time-critical aerial communication[C]. Proceedings of the 9th ACM Conference on Emerging Networking Experiments and Technologies. New York: ACM, 2013: 127-132. %21
|
| [21] |
Niu S, Zhang J, Zhang F, et al. A method of UAVs route optimization based on the structure of the highway network[J]. International Journal of Distributed Sensor Networks, 2015, 2015(1): 1667-1670. |
| [22] |
Svennebring J, Koenig S. Building terrain-covering ant robots: A feasibility study[J]. Autonomous Robots, 2004, 16(3): 313-332. DOI:10.1023/B:AURO.0000025793.46961.f6 |
| [23] |
于驷男, 周锐, 夏洁, 等. 多无人机协同搜索区域分割与覆盖[J]. 北京航空航天大学学报, 2015, 41(1): 167-173. (Yu S N, Zhou R, Xia J, et al. Decomposition and coverage of multi-UAV cooperative search area[J]. Journal of Beijing University of Aeronautics and Astronautics, 2015, 41(1): 167-173.) |
| [24] |
Polycarpou M M. A cooperative search framework for distributed agents[C]. IEEE International Symposium on Intelligent Control. Piscataway: IEEE, 2001: 1-6.
|
| [25] |
Trodden P, Richards A G. Multi-vehicle cooperative search using distributed model predictive control[J]. AIAA Guidance, Navigation and Control Conference and Exhibit. Honolulu: AIAA, 2008, 1-11. |
| [26] |
王玉, 谢晓梅, 陈敏, 等. 协同区域搜索算法仿真研究[J]. 声学技术, 2018, 21(10): 275-276. (Wang Y, Xie X M, Chen M, et al. Research on simulation of cooperative regional search algorithm[J]. Technical Acoustics, 2018, 21(10): 275-276.) |