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

吴 双,李德识,刘鸣柳,徐 婵

(武汉大学电子信息学院,湖北 武汉 430072)

1 引言

我国国土面积大,地质和气候情况多样,地震等重大自然灾害频发,这类灾害的发生往往会导致地面公共通信网络等基础设施的大面积损毁,少量未被损坏的基站无法满足灾区内所有用户的通信需求,带来了应急搜救和信息传输的困难。应急通信网络的快速部署和覆盖,对应急救援和通信服务具有重要意义。由于灾害现场环境复杂,传统的通信保障车以及卫星通信设备难以快速到达到各受灾区域。无人机因其高移动性,可灵活部署,覆盖范围大等特性,可搭载微型基站应用于救灾区域的网络部署,为灾区用户提供临时网络服务。

针对灾害救援的通信需求,研究者在无人机基站部署方面开展了相关研究。文献[1-3]中分别通过优化带宽、网络容量等参数对无人机基站进行静态部署,减小网络部署成本。然而,由于载荷、能量和通信距离等的限制,单无人机难以实现对大面积区域的网络覆盖。利用多无人机进行动态部署和协同链接覆盖,可显著提高通信服务能力。文献[4-8]中分别依据用户的移动性、地面采集点位置等信息来对多无人机进行轨迹规划,以优化无人机的覆盖率和带宽,提高无人机的部署效率。然而无论是静态部署还是动态飞行,均需要保证无人机基站在覆盖过程中的回程通信链路连接。文献[9]中通过多个中继无人机实现回程连通,文献[3]中通过静态部署大量无人机进行网格化连接来实现无人机之间的连通性,以更大的资源代价换取链路连通性。

如何在提高无人机基站资源利用率的同时,实现多无人机的协同飞行,从而保证通信链路连通性和网络覆盖率,是需要解决的关键问题。本文面向应急通信服务,针对上述问题,提出一种多无人机协同飞行部署规划方案和多无人机协同飞行轨迹规划算法,对空中临时基站群的协同部署轨迹进行优化。系统框图如图1所示,基于链路连通约束条件对部署场景进行建模,通过本文所提出的多无人机协同飞行轨迹规划算法得到应急通信服务的多无人机基站部署轨迹。论文的主要贡献如下:

图1 多无人机应急通信服务协同飞行规划框图

1) 对多无人机部署场景进行建模,根据通信链路连通约束计算场景所需的无人机部署数量和时隙数,使多无人机基站在提供网络覆盖的同时可与地面基站保持连通,保证数据回传的时效性;

2) 提出一种多无人机协同飞行轨迹规划算法,在保证无人机通信链路连通的前提下,对多个无人机的飞行轨迹进行规划,在优化无人机对用户覆盖率的同时,可减小移动时间开销,有效提高无人机资源的利用率。

2 系统模型和问题表述

2.1 系统模型

2.1.1 场景模型

考虑到灾害场景下用户移动受限以及安全问题,假设受灾用户具有较小的移动范围。设受灾用户数为N,用户坐标可表示为(xn,yn,0),n=1,2,…,N,搭载微型基站参与部署的无人机数量为M,出于飞行安全以及覆盖范围的考虑,假设空中不存在障碍物,所有无人机在移动时保持匀速,飞行速率记为v,飞行高度均为H,对地网络覆盖半径为r,邻近无人机之间的干扰可通过接入控制协议有效避免。地面基站数量为Q,对地覆盖半径为R(R>r),基站天线高度为h,坐标可表示为(Xq,Yq,h),q=1,2,…,Q;基站使用全向天线。无人机之间的有效通信半径为d,无人机与地面基站之间的有效通信半径为D。

如图2所示,无人机U2可通过无人机U1中继与地面基站建立回传链路,U1、U2通过协同飞行部署来完成对受灾区域内的用户提供临时网络覆盖。

图2 多无人机空中基站协同飞行场景

2.1.2 信道模型分析

由于无人机基站构建的临时网络包含多种类型的通信链路,包括视距(Line-of-Sight,LoS)和非视距(None-Line-of-Sight,NLoS)链路,本文将针对这两类链路的信号传输特性,对信道质量分别展开分析。

1) 空对空信道模型

基站天线均部署在一定高度,因此可以将无人机基站之间的传输以及无人机基站与地面基站之间的空中传输链路看作视距传输(如图3所示),传输仅考虑距离的影响所带来的衰减,路径损耗PLLoS由自由空间路径损耗和额外损耗ηLoS组成

图3 信道分析

(1)

2) 空对地信道模型

由于基站与用户之间会存在障碍物(建筑、树木等),基站在对用户进行网络覆盖时的信道变化会更加复杂。受到障碍物影响所进行的传输为非视距传输,记其产生的额外损耗为ηNLoS,计算方法如下

(2)

其中ηLoS,ηNLoS由环境决定,c为光速,fc为载波频率,d表示传输发送端与接收端的欧氏距离。

由于用户的位置不同且障碍物分布未知,难以直接确定空对地传输链路是否为视距链路,因此本文将空对地信道传输过程中的路径损耗表示为平均路径损耗

PL=P(LoS)*PLLoS+P(NLoS)*PLNLoS

(3)

式中P(LoS),P(NLoS)分别表示形成两种传输链路的概率,国际电信联盟给出其计算方法

(4)

P(NLoS)=1-P(LoS)

(5)

将式(1)(2)(4)(5)代入到式(3)中可得到平均路径损耗:

(6)

假设基站以功率Pt发射信号,则接收端的接收功率为

Pr=Pt-PL

(7)

为了保证传输链路的稳定性,假设接收端接收功率必须大于阈值Prmin,可以据此划定基站对地覆盖半径以及基站之间的有效通信半径,也即在该距离范围内,接收端的路径损耗最大值为PLmax=Pt-Prmin,由此可以确定各距离参数(其中Pt1,Pt2分别为地面基站和无人机基站的发射功率):

地面基站对地覆盖半径R

(8)

无人机对地覆盖半径r

(9)

地面基站与无人机之间有效通信半径D

(10)

无人机基站之间有效通信半径d

(11)

2.2 问题表述

2.2.1 悬停-飞行轨迹模型

假设无人机m的部署轨迹由点集Pm表示Pm={pm0,pm1,…,pmKm},m=1,…,M。假设所有无人机出发点pm0相同,Km表示无人机m总部署点数;对无人机基站设置两种飞行状态:移动状态和悬停状态,在悬停状态下,每个无人机为地面用户提供可靠的网络覆盖,并等待其它无人机到达同个时隙里相应部署点,通过邻近悬停的无人机多跳中继来与地面基站连通,完成数据回传。因此,要求进行连通的多个无人机在相同时间段内同步悬停,将所有Km设为相同值K(K>1),则每个无人机的部署时间将划分为K个时隙{t(1),t(2),…,t(K)},每个无人机在第k个时隙里完成从第(k-1)个部署点到第k个部署点的移动以及在第k个部署点的悬停,整个部署过程按照这种时隙分布完成对受灾用户的网络覆盖。

图4给出了时隙规划的示意图,图中每个横向表示单个无人机的K个时隙,虚线为移动和悬停时间开销的分界线。每个时隙内无人机的总时间开销与该时隙里所有无人机里最大移动时间以及在该时隙的悬停时间(假设每个用户需要回传的数据量相同,则将该值设置为与该时隙里覆盖用户数成正比)有关,因此相同时隙内的无人机具有相同的总时间开销,而不同时隙内的无人机时间开销则不一定保持一致。由此可以确定每个时隙的时间开销,将第k个时隙大小表示为

图4 时隙规划示意图

t(k)=tf(k)+th(k)

(12)

tf(k)为所有无人机在该时隙里的最大移动时间开销,由该时隙里无人机的最大移动距离(dk-1,k)max来决定,th(k)为该无人机在该时隙部署点的最小悬停时间,与该时隙的覆盖用户数成正比。

2.2.2 问题建模

(13)

(14)

优化目标为

(15)

s.t.C≥C0

(15a)

|(Xq,Yq),p1k|≤D,∀k

(15b)

|pik,p(i+1)k|≤d,i≤M-1,∀k

(15c)

式(15)表示无人机总用户覆盖率与部署过程移动时间开销的比值,由于悬停时间th(k)与覆盖用户数成正比(覆盖用户数越多,悬停时间越长,故不对其进行优化),可以通过对(15)的优化来实现无人机资源利用率的提高,上述问题中(15a),(15b),(15c)分别表示总覆盖率的最小阈值C0以及对回程距离的约束。

3 多无人机协同飞行轨迹规划

上述优化问题是一个NP问题,可以使用传统的粒子群算法(Particle swarm optimization,PSO)求解。但是该算法对于具有较大搜索空间大的问题进行优化时时间复杂度高,且上述优化问题需要对多个目标位置点进行搜索,因此本节对PSO算法进行改进,提出一种多无人机协同飞行轨迹规划算法,提高无人机部署点的搜索效率。通过搜索单个时隙里M个无人机连通的最优悬停位置(覆盖用户数最多),保证该时隙里多无人机在连通情况下用户覆盖率最大化,将该算法扩展到K个时隙,最终求出每个无人机的K个部署点,得到多无人机的移动部署轨迹。

1) 搜索空间优化

为了更高效地确定多个无人机的部署位置,首先需要依据场景信息选定无人机基站的部署区域,如图5中(1)到(2)所示。接下来针对(2)中的区域来对无人机基站进行部署,假设所划分的矩形区域边长为L,根据区域边界建立二维坐标系,则两个地面基站的坐标可分别表示为Q1(R,R),Q2(L-R,L-R)。记无人机对地覆盖直径为2r,则根据区域两基站连线的对角线方向的飞行投影距离可求得无人机的部署数量为

图5 算法实现过程

(16)

[ ]为取整符号,其中d>2r;

以地面基站的连线为某时隙无人机部署点的方向轴z1,然后分别以两个基站所处位置为圆心,通过顺时针方向旋转(如(3)中箭头所示)得到各时隙的部署方向(z1,z2,…,zK)(逆时针箭头表示协同飞行的返回过程),为了保证整体用户覆盖率,每个时隙内无人机的可部署位置需要控制在方向轴两侧的一定角度范围内,则无人机部署时隙数可根据区域垂直方向的飞行投影距离以及无人机通信半径来确定

(17)

由于部署区域关于z1对称,固此,总的部署时隙可表达为

K=2K0-1

(18)

同时可以得到每个时隙的部署区间θ0

(19)

记θ1为Q1Q2与Q2,(0,L)两直线之间的夹角(如图5(2)所示),θ1≤π。

2)无人机协同部署轨迹计算

针对目标部署区域,首先利用 PSO算法,通过M次搜索得到单个时隙里的M个部署点,并将该过程扩展到K个时隙里,搜索过程需保证每个时隙里的初始位置在地面基站的有效通信距离D内,其余各部署点之间的距离小于无人机有效通信半径d,以实现每个时隙里各部署点之间的回程连通,每个粒子的适应度需满足在粒子的r距离内受灾用户总数最多,以最大化最终得到的各部署点的用户覆盖率,由此,算法经过多次循环迭代得到每个部署点的最优可部署位置;其次,计算出每个时隙里各部署点相对于无人机出发点的距离dmk,将每个时隙里的各部署点顺序按照dmk大小进行排序,以确定每个无人机在每个时隙里的部署顺序,将调整后的每个时隙里的第一个部署点的纵坐标表示为yk,将各个时隙{P1,…,PK}的部署顺序按照yk大小进行排序,从而最小化相邻时隙之间的(dk-1,k)max,使得总部署移动时间开销最小,最终形成多无人机的部署点矩阵AK×M={pmk}K×M,其中元素pmk表示第k个时隙的第m个部署点。如下为多无人机协同飞行轨迹规划算法流程:

根据部署点矩阵可得到每个无人机的轨迹部署点,将相对无人机出发点距离最小的时隙(该时隙里的最远部署点相对其它时隙距离出发点最近)里的各部署点作为各无人机的第一个部署点,无人机基站根据钟摆式飞行移动规则沿各自的轨迹部署点协同部署,返回到第一个部署点时即完成一个周期的临时网络部署。

4 算法仿真结果与性能对比

为验证本文所提方案的可行性以及算法的有效性,本节对上述轨迹规划算法进行仿真实现,并与PSO随机部署算法对比分析。运用Spyder平台实现仿真,表1为仿真参数。

表1 仿真参数

根据仿真参数以及信道模型公式求得R=457m,r=200m,D=670m,d=475m。假设部署区域大小为3km×3km,该区域内用户总数为200,用户坐标已知,地面基站数量Q=2,坐标分别为(457,457),(2543,2543),可确定被地面基站覆盖的用户数为28,因此求得断开网络连接的受灾用户数N=172,在该区域内对无人机基站进行动态部署,无人机基站部署数量根据式(16)求得M=6,部署时隙数根据式(17)(18)求得K=9,每个时隙部署区间根据式(19)求得θ0=14°。

根据轨迹设计算法得到6个无人机在9个时隙的各部署点,上图6为其中的3个时隙里无人机部署点位置图,图中200个红色圆点代表用户位置,2个蓝色圆点代表地面基站位置,其中,蓝色实线与虚线所覆盖的区域分别对应地面基站对地覆盖范围与地面基站对无人机的有效通信范围,绿色圆点表示无人机部署位置,红色实线表示无人机基站的对地覆盖范围。

图6 不同时隙下的多无人机部署结果

由此得到6个无人机的轨迹图如图7(a)所示,仿真中,无人机部署的总服务用户数为156,因此,多无人机协同通信的用户覆盖率为90.7%,令所有无人机出发点pm0为坐标原点,则无人机一个部署周期的移动时间开销为1364.2s。

图7 多无人机飞行轨迹对比

与此同时,利用PSO随机部署算法,在相同的区域内部署相同数量的无人机,所得到的无人机轨迹图如图7(b)所示,服务用户的总数为138,用户覆盖率为80.23%,一个部署周期的移动时间开销为1409.8s。相对于本文提出的算法,无人机的整体覆盖率较低且需要更多的移动部署时间,这主要是因为无人机轨迹之间存在交叉,可能造成无人机之间的碰撞等问题。

图8给出了不同部署时隙数下,多无人机协同飞行轨迹规划算法的用户平均被覆盖次数对比,横坐标表示移动时间开销(以9个部署时隙的一个移动周期为基准),纵坐标表示用户的平均被覆盖次数。可以看到,随着时间变化,在保证用户整体覆盖率的前提下,设置9个部署时隙的用户平均被覆盖次数大于其它两种时隙数部署,即表示算法在设置9个部署时隙时无人机部署的覆盖效率最大,与多无人机协同飞行轨迹规划算法的时隙计算结果吻合,从而验证了算法的有效性。

图8 不同部署时隙数的平均覆盖次数对比

图9为两种算法仿真结果中用户覆盖率随时间变化的对比图,横坐标表示移动时间开销(同样以协同飞行轨迹规划算法仿真结果的移动周期为基准),纵坐标为无人机的用户覆盖率,由结果可知,在保证整体覆盖率不小于阈值的前提下,协同飞行轨迹规划算法在相同的移动时间开销内可以服务更多的用户。

图9 用户覆盖率对比图

图10为两种算法部署不同数量无人机的用户覆盖率对比,该图中横坐标表示无人机数量,纵坐标为用户覆盖率,由该图可知,在保证覆盖率不小于阈值的前提下,协同飞行轨迹规划算法的覆盖率均大于PSO随机部署算法,并且当无人机部署数量为6时,无人机的平均覆盖率相比其它部署数量最大。由此可知本文提出的算法相对于PSO随机部署算法提高了无人机移动部署的平均用户覆盖率,优化了无人机资源的利用效率。

图10 不同无人机数量的用户覆盖率

5 结论

本文针对灾害发生导致大面积通信网络中断的应急通信网络服务需求,采用无人机作为临时空中基站进行网络部署,提出多无人机协同飞行部署规划方案,以提高多无人机基站部署过程中的网络覆盖能力;提出一种多无人机协同飞行轨迹规划算法,以保证多无人机协同飞行部署中的高用户覆盖率和回传链路连接;仿真结果表明,所提出的轨迹规划算法在保证用户覆盖率的前提下,可有效拓展网络服务范围,提升用户覆盖率,减小多无人机区域覆盖部署的移动时延和无人机资源配置数量。