灾区无人机救援系统中基于凸包理论的无人机部署算法

魏 妍，魏长宝

(1 驻马店幼儿师范高等专科学校计算机系，河南 驻马店 463000；2 河南大学教育科学学院，河南 开封 475004;3 黄淮学院信息工程学院，河南 驻马店 463000)

0 引言

无人机(UAV)已在电讯、救援等应用领域广泛使用[1]。在基于UAV的灾区救援中，UAV为灾区内的地面终端用户(GT)提供通信服务。如何为这些GT提供实时、高效的通信服务是此类应用的关键。

UAV的部署对通信服务质量有直接影响。文献[2-10]分析了UAV的部署问题。其中文献[2-4]只讨论了单UAV部署问题，而文献[5-10]讨论了多UAV部署场景。例如，文献[5]提出了基于分布式算法部署UAV，进而保证局部优化覆盖。文献[6]提出了基于粒子群优化的UAV部署算法，以最小化UAV数。此外，为了最小化UAV与GT间的平均距离，文献[7]提出了优化覆盖质量的UAV部署算法(OQCV)。

然而，上述研究均假设GT的位置信息是已知信息。但在真实的应用环境中，获取所有GT的位置信息是非常困难的。

为此，针对灾区救援场景，提出基于测距的分布式UAV部署算法(RDUM)。RDUM算法不再假设GT的位置为已知信息，而是先通过接收信号强度估计UAV与GT间的距离(测距)。再基于测距信息，并结合凸包理论，部署UAV，使GT与UAV间平均距离最小，进而GT端获取较大的信息容量。

1 系统模型及测距

1.1 系统模型

考虑如图1所示的网络系统，其有N个地面终端用户，它们形成GT集MGT={u1,u2,…,uj,…,uN}。假定GT是静态的，但其位置未知。令wj表示第j个GT在水平面上(地面)的二维位置，且wj∈R2×1,j=1,2,…,N。

图1 系统模型

网络还部署了K个UAV，它们形成UAV集MUAV={n1,n2,…,ni,…,nK}。令Hi表示第i个UAV在空中的高度。令Di表示第i个UAV在水平面上的位置坐标，即Di=(xi,yi)，其中i=1,2,…,K。

假定UAV与GT间通信为视距链路。UAV与GT间的信道增益服从自由空间路径衰减模型。衰减强弱与两者间距离密切相关。

第i个UAV与第j个GT间距离可表示为：

(1)

(2)

1.2 测距

尽管GT位置为未知信息，但是UAV通过接收信号强度(received signal strength indicator, RSSI)[11]值, 估计离其周围GT的距离。具体而言，每个UAV知晓离集Ui内所有用户的距离。

(3)

式中：ni为部署的第i个UAV；Ui表示由离ni最近的GT所组成的GT集；uj为Ui集中的第j个GT。依据式(3)可知，对于Ui内任意一个GT而言，ni是离它最近的UAV。采用扩展Kalman滤波[12-13]估计UAV与GT间距离。令pij表示ni从第j个GT所接收的信号强度值，其表达式为：

pij=poi-10ξlog2dij+εi

(4)

式中：poi表示传输功率；εi表示由环境决定的不确定性带来的测量误差；ξ表示由环境决定的衰减因子；dij表示ni与uj间距离。

2 问题描述

为提高UAV对GT的服务质量，即优化UAV部署，以最少的UAV数覆盖GT。假定UAV与GT间通信信道在视距环境[14]，路径衰耗是影响覆盖质量的主要因素。因此，通过缩短GT与UAV间距离减少路径衰耗，最终提高覆盖质量。

换而言之，目标函数就是搜索UAV的位置，致使GT离其最近的UAV的平均最小距离为：

(5)

值得注意的是：GT位置是未知信息，UAV也不知道它们自己位置。无需GT的具体位置，只需要UAV与GT的距离信息，这是RDUM算法的一个显著特点。

在基于视距链路的前提下，无论GT在哪里，只要GT与为该GT服务的UAV间的距离相等，GT所接收的服务质量就相同。换而言之，服务质量取决于GT与UAV间的相对距离，而不是相对位置。因此，RDUM算法只需测距，进而避免了估计GT的位置所产生的通信开销或者计算开销。

3 RDUM算法

3.1 凸包理论的引入

凸包(convex hull)是数学概念[15]，它的数学定义为：在一个向量空间V中，对于给定集合X，所有包含X的凸集的交集S被称为X的凸包。而点集Q的凸包是指一个最小凸多边形，满足Q中的点或者在多边形边上或者在其内。图2中由红色线段围成的多边形就是点集Q={p0,p1,…,p12}。

图2 点集Q的凸包示例

(6)

证明：引入函数：

(7)

对式(7)进行展开，可得：

(8)

3.2 求解GT离其最近的UAV的平均最小距离

依据命题1，为了求解式(5)，将GT划分多个区。每个区的质心作为UAV的位置。具体而言，依据式(3)对Ui的定义，以每个Ui所包含的所有GT构成的空间为一个区，UAV部署于该区的质心位置。

接下来，需要解决的问题是如何将UAV移动至这些区的质心位置。部署过程分两步。

步骤1：在时刻t∈[t0,t1]期间，先随机选择N个位置作为UAV的水平位置，即给D1(t),…,Di(t),…,DN(t)∈W值赋予初始值。其中Di(t)表示第i个UAV在时刻t的位置。

步骤2：对于任意一个UAV，在tk(k=1,2,…)时，执行以下3子步。

(9)

式中：xi(τk),yi(τk)分别表示τk时刻的ni横坐标、纵坐标；xi(tk),yi(tk)分别表示在tk时刻的ni横坐标、纵坐标。

再构建直线方程：

(10)

(11)

式中：dij(t)表示在t时刻ni与uj间距离。

因此，在tk+1时刻ni的位置Di(tk+1)可表示为：

(12)

3)ni沿着直线段从Di(tk)移动到Di(tk+1)。

4 性能分析

4.1 仿真参数

在1 000 m×1 000 m水平区域内部署N个GT和K个UAV。每个UAV的高度是固定的，且在20～40 m区间。考虑文献[17]的路径衰耗模型。对于任意一个GT，其视距链路的损耗模型为：

(13)

式中：fc表示载波频率；光速c=3×108m/s；ηLoS表示关于视距链路的损耗因子。

因此，uj端所接收的信号功率为S=Pt-P，其中Pt表示传输功率。假定所有GT的传输功率相同。此外，uj端所获取的信息容量为：

(14)

式中：|Ui|表示由ni覆盖的GT数；SNR(j)表示uj端的信噪比，且SNR(j)=S/N0，其中N0表示噪声；B表示带宽。这些参数在仿真中的取值为：ηLoS=1，fc=1 GHz，Pt=24 dBm，N0=-104 dBm，B=5 MHz。

4.2 UAV的部署性能

首先，分析RDUM算法对UAV的部署性能。假定500个GT随机分布于区域内。最初，先随机部署15个UAV，它们的初始位置如图3(a)所示。再通过执行3.2节的部署步骤，UAV分别移动至局部最优位置，如图3(b)所示。图中的红色曲线表示UAV的移动轨迹；蓝色的点表示UAV；黑色的小圆点表示GT。

图3 UAV的部署示例

4.3 RDUM算法的F(D)和信息容量C性能

由原理分析可知，当UAV高度固定时，F(D)值越小，视距路径越短，UAV对GT的覆盖性能越好。图4给出UAV数对F(D)的影响，其中N=500。

图4 F(D)随无人机数的变化曲线

从图4可知，随着无人机数的增加，F(D)迅速下降。原因在于：无人机数越大，每个无人机需要覆盖的GT越少，无人机离GT更近。当无人机数增加至GT数时，每个无人机只需为一个GT服务，这时的F(D)最短。

图5给出了UAV数对信息容量C的性能影响。信息容量C反映了GT端的信噪比，信号质量越好，信息容量C就越大，性能越好。

图5 C随无人机数的变化曲线

由图5可知，无人机数和GT数均影响了信息容量C。通常，无人机数的增加，有利于信息容量C的增加。原因在于：无人机数越多，拥有的带宽资源越多，这有利于提高信息容量C。而随着GT数的增加，信息容量C会下降。原因在于：GT数越多，分享带宽资源的用户数越多。

然而，F(D)随无人机数的下降率和信息容量C随无人机数的增加率均随无人机数的增加变缓慢。这说明，在无人机数与GT所获取的服务性能间存在平衡。因此，网络供应商可依据GT对服务性能要求部署无人机数。

4.4 对比分析

为了更好地分析RDUM算法的性能，选择文献[7]提出的优化覆盖质量的UAV部署算法(OQCV)作为参照。OQCV算法中UAV知晓GT的位置。为了准确地分析GT位置信息对F(D)的影响，OQCV算法分别考虑20%、60%和100%的GT位置是已知信息的3种情况，将这三种情况分别标记为OQCV-20%，OQCV-60%和OQCV-100%

图6给出RDUM算法和OQCV算法的F(D)性能对比，其中N=500，K=15。从图可知，RDUM算法和OQCV算法收敛后，RDUM算法的F(D)值低于OQCV-20%，OQCV-60%的F(D)，但是高于OQCV-100%的F(D)值。

图6 RDUM算法和OQCV算法的F(D)随无人机数的变化曲线

此外，相比于OQCV算法，RDUM算法降低了收敛速度。原因在于：OQCV算法中GT的位置信息是已知的，而RDUM算法需要估计UAV与GT间的距离。

图7进一步分析了OQCV算法和RDUM算法的F(D)性能。从图7可知，只有94%的GT的位置信息是已知时，OQCV算法的F(D)值才低于RDUM算法的F(D)。当达到100%的GT的位置信息为已知时，OQCV算法的F(D)为96 m，而RDUM算法的F(D)为98.4 m。在这种情况下，OQCV算法的性能优于RDUM算法，但是估计GT的位置增加了通信开销和计算成本。

图7 已知GT位置信息的比例对F(D)的影响

上述分析是假定所测量的UAV与GT间距离(测距)是准确的。然而，在实际环境中，测距可能存在误差。因此，分析RDUM算法对测距误差的鲁棒性是十分必要的。假定在测距过程中存在0～20 m的测距误差。图8显示了F(D)随测距误差变化曲线。

从图8可知，F(D)随测距误差的增加而缓慢增加。例如，当用户数为200、测距误差为20 m时，F(D)只比无测距误差提升了0.8 m。这说明，RDUM算法对测距误差具有较强的鲁棒性。此外，用户数越多，测距误差对F(D)的影响越小。原因在于：对于给定的用户数而言，测距误差会影响F(D)。但所有的用户都计算F(D)，这就降低了测距误差对F(D)的影响。这也解释了为什么用户数越多，测距误差对F(D)的影响越小。

图8 测距误差对F(D)的影响

5 结束语

为了提高UAV对灾区中GT的服务质量，研究了UAV的部署问题，并提出了RDUM算法。RDUM算法通过缩短UAV与GT间距离，提高UAV的服务质量。考虑到估计GT的位置信息的计算成本，RDUM算法只需测距，无需定位。仿真结果表明，RDUM算法的性能逼近OQCV-100%算法的性能。

文中假定UAV的高度不变，在部署UAV时没有考虑UAV的高度信息。后期，将考虑的UAV的高度信息，对RDUM算法进行改进。