災(zāi)區(qū)無(wú)人機(jī)救援系統(tǒng)中基于凸包理論的無(wú)人機(jī)部署算法

魏 妍，魏長(zhǎng)寶

(1 駐馬店幼兒師范高等?？茖W(xué)校計(jì)算機(jī)系，河南 駐馬店 463000；2 河南大學(xué)教育科學(xué)學(xué)院，河南 開(kāi)封 475004;3 黃淮學(xué)院信息工程學(xué)院，河南 駐馬店 463000)

0 引言

無(wú)人機(jī)(UAV)已在電訊、救援等應(yīng)用領(lǐng)域廣泛使用[1]。在基于UAV的災(zāi)區(qū)救援中，UAV為災(zāi)區(qū)內(nèi)的地面終端用戶(GT)提供通信服務(wù)。如何為這些GT提供實(shí)時(shí)、高效的通信服務(wù)是此類應(yīng)用的關(guān)鍵。

UAV的部署對(duì)通信服務(wù)質(zhì)量有直接影響。文獻(xiàn)[2-10]分析了UAV的部署問(wèn)題。其中文獻(xiàn)[2-4]只討論了單UAV部署問(wèn)題，而文獻(xiàn)[5-10]討論了多UAV部署場(chǎng)景。例如，文獻(xiàn)[5]提出了基于分布式算法部署UAV，進(jìn)而保證局部?jī)?yōu)化覆蓋。文獻(xiàn)[6]提出了基于粒子群優(yōu)化的UAV部署算法，以最小化UAV數(shù)。此外，為了最小化UAV與GT間的平均距離，文獻(xiàn)[7]提出了優(yōu)化覆蓋質(zhì)量的UAV部署算法(OQCV)。

然而，上述研究均假設(shè)GT的位置信息是已知信息。但在真實(shí)的應(yīng)用環(huán)境中，獲取所有GT的位置信息是非常困難的。

為此，針對(duì)災(zāi)區(qū)救援場(chǎng)景，提出基于測(cè)距的分布式UAV部署算法(RDUM)。RDUM算法不再假設(shè)GT的位置為已知信息，而是先通過(guò)接收信號(hào)強(qiáng)度估計(jì)UAV與GT間的距離(測(cè)距)。再基于測(cè)距信息，并結(jié)合凸包理論，部署UAV，使GT與UAV間平均距離最小，進(jìn)而GT端獲取較大的信息容量。

1 系統(tǒng)模型及測(cè)距

1.1 系統(tǒng)模型

考慮如圖1所示的網(wǎng)絡(luò)系統(tǒng)，其有N個(gè)地面終端用戶，它們形成GT集MGT={u1,u2,…,uj,…,uN}。假定GT是靜態(tài)的，但其位置未知。令wj表示第j個(gè)GT在水平面上(地面)的二維位置，且wj∈R2×1,j=1,2,…,N。

圖1 系統(tǒng)模型

網(wǎng)絡(luò)還部署了K個(gè)UAV，它們形成UAV集MUAV={n1,n2,…,ni,…,nK}。令Hi表示第i個(gè)UAV在空中的高度。令Di表示第i個(gè)UAV在水平面上的位置坐標(biāo)，即Di=(xi,yi)，其中i=1,2,…,K。

假定UAV與GT間通信為視距鏈路。UAV與GT間的信道增益服從自由空間路徑衰減模型。衰減強(qiáng)弱與兩者間距離密切相關(guān)。

第i個(gè)UAV與第j個(gè)GT間距離可表示為：

(1)

(2)

1.2 測(cè)距

盡管GT位置為未知信息，但是UAV通過(guò)接收信號(hào)強(qiáng)度(received signal strength indicator, RSSI)[11]值, 估計(jì)離其周圍GT的距離。具體而言，每個(gè)UAV知曉離集Ui內(nèi)所有用戶的距離。

(3)

式中：ni為部署的第i個(gè)UAV；Ui表示由離ni最近的GT所組成的GT集；uj為Ui集中的第j個(gè)GT。依據(jù)式(3)可知，對(duì)于Ui內(nèi)任意一個(gè)GT而言，ni是離它最近的UAV。采用擴(kuò)展Kalman濾波[12-13]估計(jì)UAV與GT間距離。令pij表示ni從第j個(gè)GT所接收的信號(hào)強(qiáng)度值，其表達(dá)式為：

pij=poi-10ξlog2dij+εi

(4)

式中：poi表示傳輸功率；εi表示由環(huán)境決定的不確定性帶來(lái)的測(cè)量誤差；ξ表示由環(huán)境決定的衰減因子；dij表示ni與uj間距離。

2 問(wèn)題描述

為提高UAV對(duì)GT的服務(wù)質(zhì)量，即優(yōu)化UAV部署，以最少的UAV數(shù)覆蓋GT。假定UAV與GT間通信信道在視距環(huán)境[14]，路徑衰耗是影響覆蓋質(zhì)量的主要因素。因此，通過(guò)縮短GT與UAV間距離減少路徑衰耗，最終提高覆蓋質(zhì)量。

換而言之，目標(biāo)函數(shù)就是搜索UAV的位置，致使GT離其最近的UAV的平均最小距離為：

(5)

值得注意的是：GT位置是未知信息，UAV也不知道它們自己位置。無(wú)需GT的具體位置，只需要UAV與GT的距離信息，這是RDUM算法的一個(gè)顯著特點(diǎn)。

在基于視距鏈路的前提下，無(wú)論GT在哪里，只要GT與為該GT服務(wù)的UAV間的距離相等，GT所接收的服務(wù)質(zhì)量就相同。換而言之，服務(wù)質(zhì)量取決于GT與UAV間的相對(duì)距離，而不是相對(duì)位置。因此，RDUM算法只需測(cè)距，進(jìn)而避免了估計(jì)GT的位置所產(chǎn)生的通信開(kāi)銷或者計(jì)算開(kāi)銷。

3 RDUM算法

3.1 凸包理論的引入

凸包(convex hull)是數(shù)學(xué)概念[15]，它的數(shù)學(xué)定義為：在一個(gè)向量空間V中，對(duì)于給定集合X，所有包含X的凸集的交集S被稱為X的凸包。而點(diǎn)集Q的凸包是指一個(gè)最小凸多邊形，滿足Q中的點(diǎn)或者在多邊形邊上或者在其內(nèi)。圖2中由紅色線段圍成的多邊形就是點(diǎn)集Q={p0,p1,…,p12}。

圖2 點(diǎn)集Q的凸包示例

(6)

證明：引入函數(shù)：

(7)

對(duì)式(7)進(jìn)行展開(kāi)，可得：

(8)

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

依據(jù)命題1，為了求解式(5)，將GT劃分多個(gè)區(qū)。每個(gè)區(qū)的質(zhì)心作為UAV的位置。具體而言，依據(jù)式(3)對(duì)Ui的定義，以每個(gè)Ui所包含的所有GT構(gòu)成的空間為一個(gè)區(qū)，UAV部署于該區(qū)的質(zhì)心位置。

接下來(lái)，需要解決的問(wèn)題是如何將UAV移動(dòng)至這些區(qū)的質(zhì)心位置。部署過(guò)程分兩步。

步驟1：在時(shí)刻t∈[t0,t1]期間，先隨機(jī)選擇N個(gè)位置作為UAV的水平位置，即給D1(t),…,Di(t),…,DN(t)∈W值賦予初始值。其中Di(t)表示第i個(gè)UAV在時(shí)刻t的位置。

步驟2：對(duì)于任意一個(gè)UAV，在tk(k=1,2,…)時(shí)，執(zhí)行以下3子步。

(9)

式中：xi(τk),yi(τk)分別表示τk時(shí)刻的ni橫坐標(biāo)、縱坐標(biāo)；xi(tk),yi(tk)分別表示在tk時(shí)刻的ni橫坐標(biāo)、縱坐標(biāo)。

再構(gòu)建直線方程：

(10)

(11)

式中：dij(t)表示在t時(shí)刻ni與uj間距離。

因此，在tk+1時(shí)刻ni的位置Di(tk+1)可表示為：

(12)

3)ni沿著直線段從Di(tk)移動(dòng)到Di(tk+1)。

4 性能分析

4.1 仿真參數(shù)

在1 000 m×1 000 m水平區(qū)域內(nèi)部署N個(gè)GT和K個(gè)UAV。每個(gè)UAV的高度是固定的，且在20～40 m區(qū)間?？紤]文獻(xiàn)[17]的路徑衰耗模型。對(duì)于任意一個(gè)GT，其視距鏈路的損耗模型為：

(13)

式中：fc表示載波頻率；光速c=3×108m/s；ηLoS表示關(guān)于視距鏈路的損耗因子。

因此，uj端所接收的信號(hào)功率為S=Pt-P，其中Pt表示傳輸功率。假定所有GT的傳輸功率相同。此外，uj端所獲取的信息容量為：

(14)

式中：|Ui|表示由ni覆蓋的GT數(shù)；SNR(j)表示uj端的信噪比，且SNR(j)=S/N0，其中N0表示噪聲；B表示帶寬。這些參數(shù)在仿真中的取值為：ηLoS=1，fc=1 GHz，Pt=24 dBm，N0=-104 dBm，B=5 MHz。

4.2 UAV的部署性能

首先，分析RDUM算法對(duì)UAV的部署性能。假定500個(gè)GT隨機(jī)分布于區(qū)域內(nèi)。最初，先隨機(jī)部署15個(gè)UAV，它們的初始位置如圖3(a)所示。再通過(guò)執(zhí)行3.2節(jié)的部署步驟，UAV分別移動(dòng)至局部最優(yōu)位置，如圖3(b)所示。圖中的紅色曲線表示UAV的移動(dòng)軌跡；藍(lán)色的點(diǎn)表示UAV；黑色的小圓點(diǎn)表示GT。

圖3 UAV的部署示例

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

由原理分析可知，當(dāng)UAV高度固定時(shí)，F(xiàn)(D)值越小，視距路徑越短，UAV對(duì)GT的覆蓋性能越好。圖4給出UAV數(shù)對(duì)F(D)的影響，其中N=500。

圖4 F(D)隨無(wú)人機(jī)數(shù)的變化曲線

從圖4可知，隨著無(wú)人機(jī)數(shù)的增加，F(xiàn)(D)迅速下降。原因在于：無(wú)人機(jī)數(shù)越大，每個(gè)無(wú)人機(jī)需要覆蓋的GT越少，無(wú)人機(jī)離GT更近。當(dāng)無(wú)人機(jī)數(shù)增加至GT數(shù)時(shí)，每個(gè)無(wú)人機(jī)只需為一個(gè)GT服務(wù)，這時(shí)的F(D)最短。

圖5給出了UAV數(shù)對(duì)信息容量C的性能影響。信息容量C反映了GT端的信噪比，信號(hào)質(zhì)量越好，信息容量C就越大，性能越好。

圖5 C隨無(wú)人機(jī)數(shù)的變化曲線

由圖5可知，無(wú)人機(jī)數(shù)和GT數(shù)均影響了信息容量C。通常，無(wú)人機(jī)數(shù)的增加，有利于信息容量C的增加。原因在于：無(wú)人機(jī)數(shù)越多，擁有的帶寬資源越多，這有利于提高信息容量C。而隨著GT數(shù)的增加，信息容量C會(huì)下降。原因在于：GT數(shù)越多，分享帶寬資源的用戶數(shù)越多。

然而，F(xiàn)(D)隨無(wú)人機(jī)數(shù)的下降率和信息容量C隨無(wú)人機(jī)數(shù)的增加率均隨無(wú)人機(jī)數(shù)的增加變緩慢。這說(shuō)明，在無(wú)人機(jī)數(shù)與GT所獲取的服務(wù)性能間存在平衡。因此，網(wǎng)絡(luò)供應(yīng)商可依據(jù)GT對(duì)服務(wù)性能要求部署無(wú)人機(jī)數(shù)。

4.4 對(duì)比分析

為了更好地分析RDUM算法的性能，選擇文獻(xiàn)[7]提出的優(yōu)化覆蓋質(zhì)量的UAV部署算法(OQCV)作為參照。OQCV算法中UAV知曉GT的位置。為了準(zhǔn)確地分析GT位置信息對(duì)F(D)的影響，OQCV算法分別考慮20%、60%和100%的GT位置是已知信息的3種情況，將這三種情況分別標(biāo)記為OQCV-20%，OQCV-60%和OQCV-100%

圖6給出RDUM算法和OQCV算法的F(D)性能對(duì)比，其中N=500，K=15。從圖可知，RDUM算法和OQCV算法收斂后，RDUM算法的F(D)值低于OQCV-20%，OQCV-60%的F(D)，但是高于OQCV-100%的F(D)值。

圖6 RDUM算法和OQCV算法的F(D)隨無(wú)人機(jī)數(shù)的變化曲線

此外，相比于OQCV算法，RDUM算法降低了收斂速度。原因在于：OQCV算法中GT的位置信息是已知的，而RDUM算法需要估計(jì)UAV與GT間的距離。

圖7進(jìn)一步分析了OQCV算法和RDUM算法的F(D)性能。從圖7可知，只有94%的GT的位置信息是已知時(shí)，OQCV算法的F(D)值才低于RDUM算法的F(D)。當(dāng)達(dá)到100%的GT的位置信息為已知時(shí)，OQCV算法的F(D)為96 m，而RDUM算法的F(D)為98.4 m。在這種情況下，OQCV算法的性能優(yōu)于RDUM算法，但是估計(jì)GT的位置增加了通信開(kāi)銷和計(jì)算成本。

圖7 已知GT位置信息的比例對(duì)F(D)的影響

上述分析是假定所測(cè)量的UAV與GT間距離(測(cè)距)是準(zhǔn)確的。然而，在實(shí)際環(huán)境中，測(cè)距可能存在誤差。因此，分析RDUM算法對(duì)測(cè)距誤差的魯棒性是十分必要的。假定在測(cè)距過(guò)程中存在0～20 m的測(cè)距誤差。圖8顯示了F(D)隨測(cè)距誤差變化曲線。

從圖8可知，F(xiàn)(D)隨測(cè)距誤差的增加而緩慢增加。例如，當(dāng)用戶數(shù)為200、測(cè)距誤差為20 m時(shí)，F(xiàn)(D)只比無(wú)測(cè)距誤差提升了0.8 m。這說(shuō)明，RDUM算法對(duì)測(cè)距誤差具有較強(qiáng)的魯棒性。此外，用戶數(shù)越多，測(cè)距誤差對(duì)F(D)的影響越小。原因在于：對(duì)于給定的用戶數(shù)而言，測(cè)距誤差會(huì)影響F(D)。但所有的用戶都計(jì)算F(D)，這就降低了測(cè)距誤差對(duì)F(D)的影響。這也解釋了為什么用戶數(shù)越多，測(cè)距誤差對(duì)F(D)的影響越小。

圖8 測(cè)距誤差對(duì)F(D)的影響

5 結(jié)束語(yǔ)

為了提高UAV對(duì)災(zāi)區(qū)中GT的服務(wù)質(zhì)量，研究了UAV的部署問(wèn)題，并提出了RDUM算法。RDUM算法通過(guò)縮短UAV與GT間距離，提高UAV的服務(wù)質(zhì)量?？紤]到估計(jì)GT的位置信息的計(jì)算成本，RDUM算法只需測(cè)距，無(wú)需定位。仿真結(jié)果表明，RDUM算法的性能逼近OQCV-100%算法的性能。

文中假定UAV的高度不變，在部署UAV時(shí)沒(méi)有考慮UAV的高度信息。后期，將考慮的UAV的高度信息，對(duì)RDUM算法進(jìn)行改進(jìn)。