面向应急通信服务的多无人机协同飞行规划.pdf

47第40 卷第6 期2023年6 月机真计仿算文章编号：10 0 6-9 348（2 0 2 3)0 6-0 0 47-0 7面向应急通信服务的多无人机协同飞行规划吴双，李德识,刘鸣柳，徐婵（武汉大学电子信息学院，湖北武汉430 0 7 2）摘要：针对灾害发生导致的大面积通信网络中断区域内应急通信网络部署问题，提出一种多无人机协同飞行部署规划方案和多无人机协同飞行轨迹规划算法，通过未损毁基站构建连通链路，以提高空中临时基站群的网络覆盖能力，可得到多无人机基站协同飞行优化部署轨迹。仿真结果表明，所提出的多无人机协同飞行覆盖轨迹规划算法在提高无人机基站用户覆盖率的同时，可显著减小多无人机区域覆盖部署的移动时延，并减少了无人机资源配置数量。关键词：应急通信网络；多无人机协同；无人机轨迹规划；网络覆盖中图分类号：TP391.9文献标识码：BMulti-UAV Cooperative Trajectory Planningfor Emergency Communication ServicesWU Shuang,LI De-shi,LIU Ming-liu,XU Chan(School of Electronic Information,Wuhan University,Hubei Wuhan 430072,China)ABSTRACT:Aiming at the problem that emergency communication network deployment in areas where a large areaof communication network is disconnected caused by disasters,the paper proposed a multi-UAV cooperative deploy-ment plan and a multi-UAV cooperative trajectory planning algorithm,and built connected links through undamagedbase stations to improve the network coverage of temporary air stations,so that the optimized deployment trajectory forcoordinated flight of multi-UAV base stations can be obtained.The simulation results show that the proposed multi-UAV cooperative coverage trajectory planning algorithm can increase the user coverage of UAV base stations,and sig-nificantly reduce the movement delay of multi-UAVs and the allocation number of UAV resource.KEYWORDS:Emergency communication network;Multi-UAV cooperation;UAV trajectory planning;Network cov-erage1引言我国国土面积大，地质和气候情况多样，地震等重大自然灾害频发，这类灾害的发生往往会导致地面公共通信网络等基础设施的大面积损毁，少量未被损坏的基站无法满足灾区内所有用户的通信需求，带来了应急搜救和信息传输的困难。应急通信网络的快速部署和覆盖，对应急救援和通信服务具有重要意义。由于灾害现场环境复杂，传统的通信保障车以及卫星通信设备难以快速到达到各受灾区域。无人机因其高移动性，可灵活部署，覆盖范围大等特性，可搭载微型基站应用于救灾区域的网络部署，为灾区用户提供临时网络服务。针对灾害救援的通信需求，研究者在无人机基站部署方收稿日期：2 0 2 1-10-0 8修回日期：2 0 2 1-11-0 2面开展了相关研究。文献1-3 中分别通过优化带宽、网络容量等参数对无人机基站进行静态部署，减小网络部署成本。然而，由于载荷、能量和通信距离等的限制，单无人机难以实现对大面积区域的网络覆盖。利用多无人机进行动态部署和协同链接覆盖，可显著提高通信服务能力。文献4-8中分别依据用户的移动性、地面采集点位置等信息来对多无人机进行轨迹规划，以优化无人机的覆盖率和带宽，提高无人机的部署效率。然而无论是静态部署还是动态飞行，均需要保证无人机基站在覆盖过程中的回程通信链路连接。文献9 中通过多个中继无人机实现回程连通，文献3 中通过静态部署大量无人机进行网格化连接来实现无人机之间的连通性，以更大的资源代价换取链路连通性。如何在提高无人机基站资源利用率的同时，实现多无人机的协同飞行，从而保证通信链路连通性和网络覆盖率，是需要解决的关键问题。本文面向应急通信服务，针对上述问48题，提出一种多无人机协同飞行部署规划方案和多无人机协同飞行轨迹规划算法，对空中临时基站群的协同部署轨迹进行优化。系统框图如图1所示，基于链路连通约束条件对部署场景进行建模，通过本文所提出的多无人机协同飞行轨迹规划算法得到应急通信服务的多无人机基站部署轨迹。论文的主要贡献如下：1）对多无人机部署场景进行建模，根据通信链路连通约束计算场景所需的无人机部署数量和时隙数，使多无人机基站在提供网络覆盖的同时可与地面基站保持连通，保证数据回传的时效性；2）提出一种多无人机协同飞行轨迹规划算法，在保证无人机通信链路连通的前提下，对多个无人机的飞行轨迹进行规划，在优化无人机对用户覆盖率的同时，可减小移动时间开销，有效提高无人机资源的利用率。多无人机部署1多无人机协同飞行场景建模轨迹规划-多无人机应急通信服务无人机数量计算部署点矩阵协同飞行轨迹部署时隙数计算飞行移动规则图1多无人机应急通信服务协同飞行规划框图2系统模型和问题表述2.1系统模型2.1.1场景模型考虑到灾害场景下用户移动受限以及安全问题，假设受灾用户具有较小的移动范围。设受灾用户数为N,用户坐标可表示为（xn，y 0），n=1,2，,N,搭载微型基站参与部署的无人机数量为M，出于飞行安全以及覆盖范围的考虑，假设空中不存在障碍物，所有无人机在移动时保持匀速，飞行速率记为，飞行高度均为H,对地网络覆盖半径为r，邻近无人机之间的干扰可通过接人控制协议有效避免。地面基站数量为Q,对地覆盖半径为R（R r）,基站天线高度为h,坐标可表示为（X，Y，h），9=1,2，,Q;基站使用全向天线。无人机之间的有效通信半径为d,无人机与地面基站之间的有效通信半径为D。如图2 所示，无人机U,可通过无人机U，中继与地面基站建立回传链路，U、U，通过协同飞行部署来完成对受灾区域内的用户提供临时网络覆盖。2.1.2信道模型分析由于无人机基站构建的临时网络包含多种类型的通信链路，包括视距（Line-of-Sight,LoS）和非视距（None-Line-of-Sight,NLoS)链路，本文将针对这两类链路的信号传输特性，对信道质量分别展开分析。1）空对空信道模型基站天线均部署在一定高度，因此可以将无人机基站之间的传输以及无人机基站与地面基站之间的空中传输链路UUUU,H未损坏地面地面基站网络通信中断区域受灾用户基站覆盖范围商广无人机基站通信链路无人机基站对地覆盖范围图2多无人机空中基站协同飞行场景看作视距传输（如图3所示），传输仅考虑距离的影响所带来的衰减，路径损耗PLas由自由空间路径损耗和额外损耗nLos组成PLlos=20log+mLos(1)CLoSLoSHINLoS/LoSNLoS/LoSh02R图3信道分析2）空对地信道模型由于基站与用户之间会存在障碍物（建筑、树木等），基站在对用户进行网络覆盖时的信道变化会更加复杂。受到障碍物影响所进行的传输为非视距传输，记其产生的额外损耗为nNLes，计算方法如下(4元f.dPLNLos=20log+mNLOS(2)C其中nias,nNlos由环境决定,c为光速，f。为载波频率,d表示传输发送端与接收端的欧氏距离由于用户的位置不同且障碍物分布未知，难以直接确定空对地传输链路是否为视距链路，因此本文将空对地信道传输过程中的路径损耗表示为平均路径损耗PL=P(LoS)*PLos+P(NLoS)*PLNLos(3)式中P(LoS）,P(NLo S)分别表示形成两种传输链路的概率，国际电信联盟给出其计算方法1P(LoS)=(4)(1801+aexp2*0a)TP(NLoS)=1-P(LoS)(5)49n，式中和6 为常量值，其数值大小与环境（农村、城市、密集城市等）有关，是用户对于基站天线的仰角，可由=arctan(ho得到，h。表示基站天线高度，r。表示基站对地覆盖To半径。将式(1)(2)（4)（5)代人到式（3)中可得到平均路径损耗：mLos一nNLoSPL(dB)+10log(hg+r)（18 01+aexp0*T4T+20l1og+mNLoS(6)C假设基站以功率P，发射信号，则接收端的接收功率为P,=P,-PL(7)为了保证传输链路的稳定性，假设接收端接收功率必须大于阈值Pmin，可以据此划定基站对地覆盖半径以及基站之间的有效通信半径，也即在该距离范围内，接收端的路径损耗最大值为PLmax=P,-Pmin，由此可以确定各距离参数（其中Pu,Pz分别为地面基站和无人机基站的发射功率)：地面基站对地覆盖半径RnLos-nNLoSPul-Pr201og4mf(（)rminnNLoS1+aexpR=V1010一h2(8)无人机对地覆盖半径rLOS-nNLoSPt2-Prmin20log(（一）-nNLoS1010一H(9)地面基站与无人机之间有效通信半径DPia-PrminLosc*1020D(10)4f无人机基站之间有效通信半径dPa-Prminnlosc*1020d=(11)4f2.2问题表述2.2.1悬停-飞行轨迹模型假设无人机m的部署轨迹由点集P，表示P,=iPmo，Pml,Pmk.,m=1,.,M。假设所有无人机出发点Pmo相同，K，表示无人机m总部署点数；对无人机基站设置两种飞行状态：移动状态和悬停状态，在悬停状态下，每个无人机为地面用户提供可靠的网络覆盖，并等待其它无人机到达同个时隙里相应部署点，通过邻近悬停的无人机多跳中继来与地面基站连通，完成数据回传。因此，要求进行连通的多个无人机在相同时间段内同步悬停,将所有K设为相同值K(K1）,则每个无人机的部署时间将划分为K个时隙(t(1)，t(2),t(K)I,每个无人机在第k个时隙里完成从第（k-1)个部署点到第k个部署点的移动以及在第个部署点的悬停，整个部署过程按照这种时隙分布完成对受灾用户的网络覆盖。t(1)t(2)t(k)t(K)m=1移动悬停m-ml移动悬停.m-=M移动悬停图4时隙规划示意图图4给出了时隙规划的示意图，图中每个横向表示单个无人机的K个时隙，虚线为移动和悬停时间开销的分界线。每个时隙内无人机的总时间开销与该时隙里所有无人机里最大移动时间以及在该时隙的悬停时间（假设每个用户需要回传的数据量相同，则将该值设置为与该时隙里覆盖用户数成正比)有关，因此相同时隙内的无人机具有相同的总时间开销，而不同时隙内的无人机时间开销则不一定保持一致。由此可以确定每个时隙的时间开销，将第k个时隙大小表示为t(k)=t(k)+t(k)(12)(dk-1,)max()=(12a)(k)为所有无人机在该时隙里的最大移动时间开销，由该时隙里无人机的最大移动距离（d-1,）mx 来决定，t（k）为该无人机在该时隙部署点的最小悬停时间，与该时隙的覆盖用户数成正比。2.2.2问题建模无人机基站的动态部署是为了在灾害发生短时间内服务到更多受灾用户，移动部署总用户覆盖率为C=一Kk=1，n=n(m,k),n(m,k）为无人机m在第k个N部署点的覆盖用户数，8 mm用于指示未被覆盖过的用户n是否被无人机m覆盖(1,1（x n,y n),Pm k/r8(13)nm(0,1(xn,yn),Pmk/Tn(m,h)=ZM(14)m=1n.m优化目标为Cmax(15)50s.t.C Co(15a)I(X,Y,),PluI D,Vk(156)I pik,P(i+1)/d,iM-1,Vk(15c)式（15）表示无人机总用户覆盖率与部署过程移动时间开销的比值，由于悬停时间t（k）与覆盖用户数成正比（覆盖用户数越多，悬停时间越长，故不对其进行优化），可以通过对（15）的优化来实现无人机资源利用率的提高，上述问题中（15a），（15b），（15c）分别表示总覆盖率的最小阈值C。以及对回程距离的约束。3多无人机协同飞行轨迹规划上述优化问题是一个NP问题，可以使用传统的粒子群算法（Particle swarm optimization，PSO）求解。但是该算法对于具有较大搜索空间大的问题进行优化时时间复杂度高，且上述优化问题需要对多个目标位置点进行搜索，因此本节对PSO算法进行改进，提出一种多无人机协同飞行轨迹规划算法，提高无人机部署点的搜索效率。通过搜索单个时隙里M个无人机连通的最优悬停位置（覆盖用户数最多），保证该时隙里多无人机在连通情况下用户覆盖率最大化，将该算法扩展到K个时隙，最终求出每个无人机的K个部署点，得到多无人机的移动部署轨迹。1）搜索空间优化为了更高效地确定多个无人机的部署位置，首先需要依据场景信息选定无人机基站的部署区域，如图5中（1）到(2)所示。接下来针对(2)中的区域来对无人机基站进行部署，假设所划分的矩形区域边长为L，根据区域边界建立二维坐标系,则两个地面基站的坐标可分别表示为Q（R,R），Q 2（L-R,L-R）。记无人机对地覆盖直径为2 r,则根据区域两基站连线的对角线方向的飞行投影距离可求得无人机的部署数量为V2L-4RM=(16)2T为取整符号,其中d2r；以地面基站的连线为某时隙无人机部署点的方向轴z1，然后分别以两个基站所处位置为圆心，通过顺时针方向旋转（如（3)中箭头所示）得到各时隙的部署方向（z1,z2，z k）（逆时针箭头表示协同飞行的返回过程），为了保证整体用户覆盖率，每个时隙内无人机的可部署位置需要控制在方向轴两侧的一定角度范围内，则无人机部署时隙数可根据区域垂直方向的飞行投影距离以及无人机通信半径来确定L-2RK。=2r(17)由于部署区域关于z，对称，固此，总的部署时隙可表达为K=2K。-1(18)同时可以得到每个时隙的部署区间6。=K-1(19)记,为Q,Q，与Q2，（0,L)两直线之间的夹角（如图5(2)所示),0,T。0无人机部署场景选择受灾区域基站分布(2)(1)未损坏地面地面基站网络无人机基站对地多无人机协同飞行轨迹设计基站覆盖范围覆盖范围(3)网络无人机部署方向轴旋转方向轴两侧中断区域方向轴方向角度区间图5算法实现过程2）无人机协同部署轨迹计算针对目标部署区域，首先利用PSO算法，通过M次搜索得到单个时隙里的M个部署点，并将该过程扩展到K个时隙里，搜索过程需保证每个时隙里的初始位置在地面基站的有效通信距离D内，其余各部署点之间的距离小于无人机有效通信半径d，以实现每个时隙里各部署点之间的回程连通，每个粒子的适应度需满足在粒子的距离内受灾用户总数最多，以最大化最终得到的各部署点的用户覆盖率，由此，算51法经过多次循环迭代得到每个部署点的最优可部署位置；其次，计算出每个时隙里各部署点相对于无人机出发点的距离dm，将每个时隙里的各部署点顺序按照dm大小进行排序，以确定每个无人机在每个时隙里的部署顺序，将调整后的每个时隙里的第一个部署点的纵坐标表示为ys，将各个时隙(P.Pkl的部署顺序按照y大小进行排序，从而最小化相邻时隙之间的（dk-1,）mx，使得总部署移动时间开销最小,最终形成多无人机的部署点矩阵Akm=|Pmlkm，其中元素Pmk表示第k个时隙的第m个部署点。如下为多无人机协同飞行轨迹规划算法流程：多无人机协同飞行轨迹规划算法输入:Q1(R,R),Q2(L-R,L-R),(xn,yn),n=1,2,.,N),M,K,9o,R,r,v,D,d,Co,(Zk,.k=1,.,K)输出：部署点矩阵AkxM=(PmkkxM流程：1:fork=1,2,.,Kdo2:form=1,2,.,Mdo3：ifkK+1then24:ifm=1then5:(pikQ2z)号and lpikQllD6:max n(1,m)-P1k,dik=llpik,Oll7：else8:2(pmkQz,zk)gandllpmk.Q2ll/d9:maxn(m,k)pmk,dmk=llpmk,ll10:elseifm=1then11:(pikQ1,z)andlpk,QillD12:max n(1,k)-P1k,dik=llpik,oll13:else14:L(pmkQi,z)gand Ipmk,Qilld15:max n(m,k)-pmk,dmk=llpmk,ll16:endfor17:end for18:fork=1,2,.,Kdo19:sort(diko.,dmk)-sort(p1k.Pmk)20:endfor22:AkMPmkKM根据部署点矩阵可得到每个无人机的轨迹部署点，将相对无人机出发点距离最小的时隙（该时隙里的最远部署点相对其它时隙距离出发点最近）里的各部署点作为各无人机的第一个部署点，无人机基站根据钟摆式飞行移动规则沿各自的轨迹部署点协同部署，返回到第一个部署点时即完成一个周期的临时网络部署。4算法仿真结果与性能对比为验证本文所提方案的可行性以及算法的有效性，本节对上述轨迹规划算法进行仿真实现，并与PSO随机部署算法对比分析。运用Spyder平台实现仿真，表1为仿真参数。表1仿真参数参数数值地面基站最大发射功率Pt1/dBm36无人机基站最大发射功率Pe/dBm33参数数值载频f/CHz2地面基站天线高度h/m40无人机基站天线高度H/m50无人机基站最小接收功率P.1/dBm-60用户设备最小接收功率Pz/dBm-75无人机飞行速率v/（m/s）10覆盖率最小阈值C。90%(a,b,nLos,nNLos)(9.61,0.16,1,20)3根据仿真参数以及信道模型公式求得R=457m，r=200m，D=6 7 0 m，d=47 5m。假设部署区域大小为3km3km，该区域内用户总数为2 0 0,用户坐标已知，地面基站数量Q=2,坐标分别为（457,457），（2 543,2 543），可确定被地面基站覆盖的用户数为2 8，因此求得断开网络连接的受灾用户数N=172,在该区域内对无人机基站进行动态部署，无人机基站部署数量根据式（16)求得M=6,部署时隙数根据式（17)(18)求得K=9,每个时隙部署区间根据式（19)求得8=14。根据轨迹设计算法得到6 个无人机在9 个时隙的各部署点，上图6 为其中的3个时隙里无人机部署点位置图，图中2 0 0 个红色圆点代表用户位置，2 个蓝色圆点代表地面基站位置，其中，蓝色实线与虚线所覆盖的区域分别对应地面基站对地覆盖范围与地面基站对无人机的有效通信范围,绿userdistribution300026002000150010005002000150020020000(a)第1个时隙（对角线方向轴）userdistribution100025002000150010005001000150025003000X(b)第5个时隙52userdistribution30002500200015001000500100015002000200Do0(c)第9 个时隙图6不同时隙下的多无人机部署结果色圆点表示无人机部署位置，红色实线表示无人机基站的对地覆盖范围。由此得到6 个无人机的轨迹图如图7（a）所示，仿真中，无人机部署的总服务用户数为156，因此，多无人机协同通信的用户覆盖率为9 0.7%，令所有无人机出发点Pmo为坐标原点，则无人机一个部署周期的移动时间开销为136 4.2 s。与此同时，利用PSO随机部署算法，在相同的区域内部署相同数量的无人机，所得到的无人机轨迹图如图7（b）所示，服务用户的总数为138，用户覆盖率为8 0.2 3%，一个部署userdistribution300025002000150030005005001000150020025003000X(a)多无人机协同飞行轨迹图userdistribution3000250020001500100050010001500200025003000X(b)PSO随机部署算法轨迹图图7多无人机飞行轨迹对比周期的移动时间开销为140 9.8 s。相对于本文提出的算法，无人机的整体覆盖率较低且需要更多的移动部署时间，这主要是因为无人机轨迹之间存在交叉，可能造成无人机之间的碰撞等问题。图8 给出了不同部署时隙数下，多无人机协同飞行轨迹规划算法的用户平均被覆盖次数对比，横坐标表示移动时间开销（以9 个部署时隙的一个移动周期为基准），纵坐标表示用户的平均被覆盖次数。可以看到，随着时间变化，在保证用户整体覆盖率的前提下，设置9 个部署时隙的用户平均被覆盖次数大于其它两种时隙数部署，即表示算法在设置9 个部署时隙时无人机部署的覆盖效率最大，与多无人机协同飞行轨迹规划算法的时隙计算结果吻合，从而验证了算法的有效性。2.0017个时隙1.7519个时隙11个时隙1.501.250075Q.500.25Q:001/93/95/97/9周期图8不同部署时隙数的平均覆盖次数对比图9 为两种算法仿真结果中用户覆盖率随时间变化的对比图，横坐标表示移动时间开销（同样以协同飞行轨迹规划算法仿真结果的移动周期为基准），纵坐标为无人机的用户覆盖率，由结果可知，在保证整体覆盖率不小于阈值的前提下，协同飞行轨迹规划算法在相同的移动时间开销内可以服务更多的用户。100多无人机协同飞行轨迹规划算法PSO随机部署算法80%/巢盛田40201/9395/97/9周期图9用户覆盖率对比图图10 为两种算法部署不同数量无人机的用户覆盖率对比，该图中横坐标表示无人机数量，纵坐标为用户覆盖率，由该图可知，在保证覆盖率不小于阈值的前提下，协同飞行轨迹规划算法的覆盖率均大于PSO随机部署算法，并且当无人53机部署数量为6 时，无人机的平均覆盖率相比其它部署数量最大。由此可知本文提出的算法相对于PSO随机部署算法提高了无人机移动部署的平均用户覆盖率，优化了无人机资源的利用效率。10080%/巢盛田8020多无人机协同飞行轨迹规划算法PSO随机部署算法5678无人机数量/个图10不同无人机数量的用户覆盖率5结论本文针对灾害发生导致大面积通信网络中断的应急通信网络服务需求，采用无人机作为临时空中基站进行网络部署，提出多无人机协同飞行部署规划方案，以提高多无人机基站部署过程中的网络覆盖能力；提出一种多无人机协同飞行轨迹规划算法，以保证多无人机协同飞行部署中的高用户覆盖率和回传链路连接；仿真结果表明，所提出的轨迹规划算法在保证用户覆盖率的前提下，可有效拓展网络服务范围，提升用户覆盖率，减小多无人机区域覆盖部署的移动时延和无人机资源配置数量。参考文献：1 Hua Qu,Wen na Zhang,el al.Rapid Deployment of UAVs Basedon Bandwidth Resources in Emergency Scenarios C.2020 Infor-mation Communication Technologies Conference(ICTC),2020.2Pei ming li,Jie Xu.UAV-Enabled Cellular Networks with Multi-Hop Backhauls:Placement Optimization and Wireless ResourceAllocation C.2018 IEEE International Conference on Communi-cation Systems(ICCS),2018,10.1109/ICCS.2018.3王花.无人机空中基站的覆盖部署方法研究D.西安理工大学，2 0 2 0.4Tatsuaki Kimura;Masaki Ogura.Distributed Collaborative 3D-De-ployment of UAV Base Stations for On-Demand Coverage C.IEEE INFOCOM 2020 IEEE Conference on Computer Communica-tions.2020,10.5Xiao Liu,Yuan wei Liu,el al.Reinforce-Learning in Multiple-UAV Networks:Deployment and Movement Design J.IEEETransactions on Vehicular Technology,2019,68(8):8036-8049.6黄颖茜，崔苗，张广驰.具有回程约束的多无人机基站的带宽功率与轨迹优化J.计算机应用研究，2 0 2 0：8 31-8 35,8 40.7Zheng rui Huang,Chong cheng Chen,el al.Multi-objective UAVPath Planning for emergency Information Collection andTransmissionJ.IEEE Internet of Things Journal,2020,7(8):6993-7009.8Yi xin Zhang,Wenchi Cheng.Trajectory and Power Optimizationfor Multi-UAV Enabled Emergency Wireless Communications Net-works C.2019 IEEE International Conference on CommunicationsWorkshops（ICCWo r k s h o p s),2 0 19,10.110 9/ICCW.2 0 19.9武云龙，张博等.基于动态规划的多无人机通信连通性保持研究J.中国科学（技术科学），2 0 2 0,50（5）：538-550.10Chen Wu,Hao Zhang,et al.Research on Key Technology of E-mergency Communication System in Post-Earthquake DisasterRelief C.2018 IEEE International Conference of SafetyProduce Information(IICSPI),2018,10.1109/IICSPI.2018.11Chen Wu,Hao Zhang,et al.Research on Key Technology of E-mergency Communi-cation System in Post-Earthquake DisasterRelief C.2018 IEEE Intermational Conference of Safety ProduceInformation(ICSPI),2018,10.作者简介吴双（19 9 7-），女（汉族），湖北黄冈人，硕士研究生，主要研究方向为无人机通信网络。李德识（19 6 8-），男（汉族），山东临沂人，教授，博导，主要研究方向为无线通信技术、传感器网络、智能系统、SOC软硬件协同设计。刘鸣柳（19 9 2-），女（汉族），湖北鄂州人，博士后，主要研究方向为物联网实时搜索、无线传感器网络。徐婵（19 9 4-），女（汉族），湖北天门人，博士研究生，主要研究方向为无人机通信网络，凸优化算法。