災區無人機救援系統中基于凸包理論的無人機部署算法

魏 妍，魏長寶

(1 駐馬店幼兒師范高等?？茖W校計算機系，河南 駐馬店 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算法進行改進。