基于博弈論的多無人機覆蓋策略研究

謝祥洲， 謝 玲， 羅一欣

(1.電子科技大學機械與電氣工程學院，成都 611000； 2.重慶城市管理職業(yè)學院，重慶 401000；3.吉林省教育學院，長春 130000)

0 引言

無人機(UAV)以其體積小、機動性強、通信成本低等特點在軍事和民用領域得到了廣泛應用，然而單架UAV往往不能滿足復雜任務的需要[1-2]。為了解決這一問題,需要組建一個多UAV協(xié)作小組來提高效率，特別是在信息收集和處理方面，UAV之間的協(xié)作已成為UAV網(wǎng)絡發(fā)展的關鍵技術之一[3-4]。

目前UAV研究熱點主要集中在區(qū)域覆蓋問題上，目的是使UAV更好地完成偵察、通信、測繪等任務[5]。文獻[6]提出了一種無人機網(wǎng)絡覆蓋優(yōu)化算法，通過對最少無人機節(jié)點數(shù)目和熱點區(qū)域覆蓋范圍進行估計，并應用改進的布谷鳥算法重構(gòu)優(yōu)化目標函數(shù)，從而實現(xiàn)熱點區(qū)域覆蓋概率的重點優(yōu)化;文獻[7]提出了一種基于相對距離的無人機基站傳感器網(wǎng)絡部署方法，通過感知地面的未覆蓋區(qū)域，以及覆蓋邊界或障礙物的位置實現(xiàn)按需覆蓋，并在3個相對距離的影響下保持穩(wěn)定的無線電覆蓋，有效提高無人機網(wǎng)絡覆蓋效率。但上述方法難以最大程度地提高覆蓋質(zhì)量以及覆蓋區(qū)域，并難以最小化發(fā)射功率，不能實現(xiàn)無人機輔助的無縫覆蓋。文獻[8]提出了一種基于飛行時間約束的無人機無線通信性能優(yōu)化策略，通過使用最佳運輸理論數(shù)學框架，提出了一種基于梯度的優(yōu)化算法，用于根據(jù)用戶的分布、飛行時間和無人機的位置對地理區(qū)域進行最佳劃分，從而最大程度地提高覆蓋質(zhì)量、覆蓋區(qū)域；文獻[9]提出了一種用于無人機基站(UAV-BS)的最佳放置算法，在垂直和水平方向上解耦UAV-BS的部署問題，并將UAV-BS在水平維度上的部署建模為圓形放置問題，從而使用最小發(fā)射功率達到最大化用戶覆蓋數(shù)量；文獻[10]提出一種無人機蜂群中紫外光隱秘通信能耗均衡路由算法，在保持UAV編隊的基礎上，根據(jù)無線紫外光散射通信的優(yōu)點，在網(wǎng)絡選擇過程中結(jié)合通信鏈路損耗和節(jié)點剩余能量構(gòu)建權值函數(shù)，從而平衡無人機蜂群節(jié)點的能耗，有效延長無人機蜂群的生命周期。但上述研究僅對發(fā)射功率進行了優(yōu)化，未考慮無人機在推進過程中的能量消耗，與無人機網(wǎng)絡通信的實際服務時間存在較大偏差，實用性較差。

為更好地解決在節(jié)能通信場景下UAV區(qū)域覆蓋的問題，本文提出了一種基于博弈論的多無人機覆蓋部署策略。

1 系統(tǒng)模型構(gòu)建

圖1所示為本文所探討的多UAV合作覆蓋示意圖。對于任務單元i，假設某個給定UAVj的覆蓋概率為qj,i，則采用軟覆蓋的概念計算網(wǎng)絡中任務單元i的覆蓋概率qi為qi=1-(1-q1,i)×(1-q2,i)×(1-q3,i)，該式表明探測到的UAV越多，任務單元的覆蓋概率qi越高。

圖1 任務區(qū)多UAV覆蓋示意圖

考慮到天線增益和路徑損耗等因素，如何準確地描述任務點的覆蓋效用是一個值得思考的問題。本文建立了由多UAV組成的空對地網(wǎng)絡，連續(xù)區(qū)域I∈R2被均勻地劃分成離散單元。UAVn的狀態(tài)定義為sn={ln,pn}，其中，ln和pn分別表示UAVn的水平位置(xn，yn)和載波傳輸功率。假設固定翼UAV在固定的低空平臺上水平飛行，UAV的定向天線波束寬度用θ表示，與均勻平面陣列(Uniform Planar Array,UPA)下的天線方向圖相對應，從而得到了UAV的天線增益為

(1)

式中：Gm為主瓣增益；N0為天線元數(shù)。覆蓋概率由路徑損耗、位置、載波傳輸功率和環(huán)境等因素綜合決定。此時，空對地通信的路徑損耗LdB為

(2)

式中：n0為路徑損耗指數(shù)；fc為UAV的載頻；c為電磁波速度；di,n為UAVn與任務單元i之間的距離。

無線網(wǎng)絡傳輸存在有視距和無視距鏈路。具體來說，UAVn的有視距概率表示為PLoS,n，而無視距概率表示為PNLoS，n。單架UAVn相對任務單元i覆蓋概率qi(Sn)可表示為

(3)

式中：pn為UAVn的載機傳輸功率；pmin為成功檢測時最小功率要求；μLoS，σLoS和μNLoS，σNLoS分別為有視距和無視距鏈路陰影衰減的均值和方差。

為了研究整個任務區(qū)的總覆蓋率影響程度，本文引入了任務區(qū)重要性的概念。據(jù)此，任務單元i的UAV網(wǎng)絡覆蓋能力gi,N可表示為

(4)

式中：N表示無人機集合；σi表示任務單元i的重要性。因此，進一步推導出UAV全局覆蓋效用U0為

(5)

載波傳輸能力和能量消耗是多UAV是否能完成任務的關鍵，受UAV通信能效設計的啟發(fā)[11]，UAV網(wǎng)絡的總能量效率G0為

(6)

式中：τ為給定任務要求的覆蓋閾值；G0表示覆蓋效用的單位功率，G0值越高，表示傳輸功率越小，覆蓋效用越高。因此，該模型可優(yōu)化為尋找UAV的最優(yōu)狀態(tài)Sopt，即

P∶Sopt=arg maxG0。

(7)

2 合作博弈論框架

文獻[12]中建立了一個小型網(wǎng)絡集中分布式優(yōu)化體系結(jié)構(gòu)，并將物理小區(qū)網(wǎng)絡映射為云中的虛擬決策網(wǎng)絡，受該方案的啟示，本文采用降維的方法來求解該模型。首先，將任務區(qū)的環(huán)境參數(shù)和所有UAV的位置、機載發(fā)射功率等信息報告給地面中心，由地面中心負責將UAV網(wǎng)絡映射到虛擬決策網(wǎng)絡;然后，設計了一種優(yōu)化方法來解決該問題;最后，將得到的決策結(jié)果Sopt分發(fā)給UAV，它將根據(jù)Sopt調(diào)整載波傳輸功率并傳輸?shù)街付ㄎ恢谩?/p>

2.1 降維求解過程

由于多維策略(位置和傳輸功率)的存在，求解問題P具有挑戰(zhàn)性，通過將P劃分為P1和P2來降低策略選擇的復雜性，具體降維方法如下。

(8)

(9)

2.2 UAV覆蓋最大化中的合作博弈

問題P1和P2是離散優(yōu)化問題和NP-hard問題，傳統(tǒng)集中式算法不能有效解決這些問題，特別是當任務單元的數(shù)量很大時更困難。為了應對這一挑戰(zhàn)，本文采用博弈論這一有效的分布式多決策問題解決方法，來消除個體決定帶來的相互影響。

在節(jié)能多UAV覆蓋部署模型的博弈論框架中，覆蓋問題被建模為R(N，{Sn,n∈N}，{Un,n∈N})，其中，Sn為UAVn的狀態(tài)。為方便起見，將位置ln和傳輸功率pn設置為S1,n和S2,n，即S1,n?S2,n=SnS，其中，S1,n和S2,n分別為ln和pn的集合，?表示笛卡爾積。UAVn的覆蓋效用函數(shù)Un可以表示為Un=U1,n?U2,n，其中，U1,n和U2,n分別為覆蓋最大化和功率控制的效用函數(shù)。

另外，sn,u1,n和u2,n分別表示Sn,U1,n和U2,n的一個單元。同時，將s-n定義為一組除了第n架UAV外的所有UAV的操作配置文件。因此，提出的節(jié)能型多UAV覆蓋部署模型是一個合作博弈模型，在該模型中，參與者(UAVn)的效用屬于網(wǎng)絡中參與者和其他UAV的狀態(tài)。

根據(jù)勢博弈的基本定義，勢博弈要求參與者在分布式多主體系統(tǒng)中進行合作控制，使每個參與者的局部效用與全局效用相互關聯(lián)。以下定義用來分析所建立的博弈論框架的性質(zhì)。

定義1(納什均衡(NE))。

(10)

定義2(嚴格勢博弈)。

對于效用函數(shù)u(sn，s-n)，如果存在一個勢函數(shù)φ，當任意策略的選擇從sn變?yōu)閟′n時，存在如下關系

μ(sn,s-n)-μ(s′n,s′-n)=φ(sn,s-n)-φ(s′n,s′-n)

(11)

那么這個博弈稱為嚴格勢博弈(Exact Potential Game，EPG)，它至少有一個NE點。

在覆蓋最大化階段，假設該模型主要針對合作型UAV，那么存在重疊檢測區(qū)域的UAV往往具有合作行為。

定義In為UAVn的可探測區(qū)域，若In∩Jn≠0，則Jn為UAVn的鄰居的集合。同時定義J′n為經(jīng)過n次新位置選擇后的UAVn的新鄰居。需要注意的是，所有UAV都有其最大的發(fā)射功率，覆蓋最大化中基于合作覆蓋博弈的效用函數(shù)為

(12)

G1:maxu1，n(Sn,SJn) ?n∈N

(13)

式中，根據(jù)目標G1，UAVn的最優(yōu)局部效用由其水平位置確定。

定理1將多UAV覆蓋問題描述為一個合作覆蓋博弈問題，參與者采用式(12)的效用函數(shù)。合作覆蓋博弈G1是一個EPG，并至少有一個純策略納什均衡點。另外，覆蓋最大化的最優(yōu)解P1是G1的純策略納什均衡點。

證明 首先，將整個覆蓋效用構(gòu)造為勢函數(shù)，即

(14)

假設任意一架UAVn的狀態(tài)從sn變?yōu)閟′n，則由個體策略選擇引起的勢函數(shù)變化如下

φe(Sn,S-n)-φe(S′n,S-n)=

(15)

直觀地說，當UAV不在J1，n集合時，其完全不受上述策略變化的影響。那么式(15)中最后兩項的結(jié)果等于零。此時，根據(jù)式(12)和式(15)可得

u1，n(sn,sJn)-u1，n(s′n,sJn)=φe(sn,s-n)-φe(s′n,s-n) 。

(16)

由式(16)可知，當任意UAV改變其行動策略時，其局部效用函數(shù)和勢函數(shù)的變化值是相同的。由此證明了局部利他博弈G1是一個EPG，并且根據(jù)定義2具有至少一個純策略納什均衡點。而且，設計的勢函數(shù)對全局覆蓋都具有效用，它保證了每個參與者當前的局部效用與全局覆蓋效用相互進行關聯(lián)，因此P1的最優(yōu)解變?yōu)镚1的純策略納什均衡點。

2.3 UAV功率控制中的勢博弈

從式(3)中可以看出，地面單元的覆蓋概率不僅由UAV的位置決定，還與載波傳輸功率有關。圖2為給定UAV地面任務單元的覆蓋概率與發(fā)射功率之間的關系，從圖2比較兩個不同位置的UAV可知，地面單元的覆蓋概率隨著UAV發(fā)射功率增加而增加，且隨著傳輸功率的增加，覆蓋概率將一直接近峰值并逐漸平緩。

圖2 覆蓋概率隨發(fā)射功率的變化

注意在當前固定的UAV部署下，一架UAV的功率選擇會影響其可探測的任務區(qū)域單元的覆蓋概率。因此，功率控制問題是一個潛在的博弈問題。為此構(gòu)建了UAVn的個體效用函數(shù)，以捕獲最優(yōu)傳輸功率分配，即

(17)

式(17)表示UAVn在固定的最優(yōu)位置下的最佳能效，其由UAVn的載波傳輸功率決定；在這個過程中，效用函數(shù)也滿足勢博弈的特點，其使每一架UAV的本地效用與全局效用相關聯(lián)。式中，In為UAVn的探測區(qū)域。因此，設計的UAV功率控制模型可以建立一個勢博弈模型目標，即

G2:maxu2，n(pn,p-n) ?n∈N。

(18)

定理2針對UAV最優(yōu)功率控制問題，以式(15)作為其單獨效用函數(shù)，那么UAV勢博弈G2是一個EPG，并至少有一個納什均衡點。此外,問題P2的最優(yōu)解是G2的純策略納什均衡點。

證明 首先能量效率效用可以表示為勢函數(shù)，即

(19)

式中，對于任意傳輸功率選擇從pn變?yōu)閜′n，計算出的勢函數(shù)變化如下

(20)

應該指出的是，任務區(qū)域不在UAV探測范圍內(nèi)，其完全不受上述策略變化的影響。因此可得

(21)

注意在式(20)和式(21)中，對于任一架UAVn，其勢函數(shù)和個體效用函數(shù)之間的變化值與UAVn的變化一樣，其傳輸功率策略可表示為

φ(pn,p-n)-φ(p′n,p-n)=u2，n(pn,p-n) -u2，n(p′n,p-n)。

(22)

由式(22)可以看出，G2是根據(jù)定義1得出的EPG，并且至少有一個純策略納什均衡點。另外，設計的勢函數(shù)針對的是整個覆蓋效用，它保證了每個參與的UAV的當前個體效用與整體覆蓋效用相關聯(lián)。因此，問題P2的最優(yōu)解是G2的純策略納什均衡點。

2.4 空間自適應博弈的多UAV節(jié)能覆蓋部署算法

由于多UAV節(jié)能覆蓋部署問題被描述為一個EPG問題，因此需要應用學習算法來探索博弈的納什均衡，以防止UAV策略陷入局部最優(yōu)狀態(tài)。基于空間自適應博弈(Spatial Adaptive Play，SAP)的多UAV節(jié)能覆蓋部署算法的實現(xiàn)過程如下。

算法1：基于SAP的多無人機節(jié)能覆蓋部署算法。

目標：在覆蓋效用限制下最大限度地減少工作功率建立UAV狀態(tài)剖面的參數(shù)，Sn={ln，pn}，n∈N，和任務區(qū)域I的狀態(tài)(σ)，設置合理的迭代次數(shù)。

/*步驟1：在最大載波傳輸功率下的最大覆蓋部署*/

While：未達到預定的最大迭代次數(shù) do

隨機選擇一架UAVj，將其工作功率調(diào)至最大。

從受約束位置S1，n中選擇一個位置狀態(tài)lj(t)，產(chǎn)生sj(t)的變化。

選定的UAVj計算任務區(qū)域的當前本地覆蓋效用u1，j(sj(t)，sJj(t))和期望效用u1，j(s′j(t)，sJj(t))

UAVj根據(jù)式(23)選擇一個狀態(tài)，并更新其狀態(tài)sj(t+1)。

t=t+1。

End while

計算當前UAV網(wǎng)絡的全局覆蓋效用U0，如果U0>τ，則保存并利用UAV更新后的狀態(tài)數(shù)據(jù)Sn，將Sn輸入到以下算法中；否則，結(jié)束程序并返回。

/*步驟2：在最大覆蓋下的最優(yōu)功率控制*/

While：未達到預定的最大迭代次數(shù) do

在每次迭代中隨機選擇一架UAVn。

所有其他UAV重復先前的功率選擇，即pk(t+1)=pk(t),k∈Jn。

為選擇UAVn，計算其效用函數(shù)

u2，n(p′n(t),p-n(t))，不同功率選擇p′n∈S2，n/pn，以及電流效用函數(shù)u2，n(pn(t),p-n(t)) 。

UAVn根據(jù)式(24)更新其功率選擇策略。t=t+1。

End While

二進制對數(shù)線性學習被證明能保證收斂到最優(yōu)納什均衡，用于探索UAV的最優(yōu)覆蓋部署[13]。UAV的行動選擇概率函數(shù)為

(23)

式中，t表示迭代次數(shù)?？紤]到多智能體決策的復雜性，采用了一種分布式學習算法用于功率控制。因此，采用空間自適應博弈方法可將傳輸功率收斂到穩(wěn)定的分配狀態(tài)，UAVn的功率選擇概率函數(shù)為

qn(t)=

(24)

式中，β為學習參數(shù),β>0。

3 實驗結(jié)果與分析

本章將進行模擬實驗以評估所提出方法的有效性。實驗中，將UAV通信網(wǎng)絡的載波頻率設置為2000 MHz，其中，μLoS=1 dB，μNLoS=20 dB，n0=2.5。此外,假設每架UAV都配備了16根天線，即N0=16?？紤]到四旋翼UAV的實際需求[13]，設置了一些合理的離散傳輸功率選擇，即pn∈{32，34，36，38，40，42，44，46，48，50}(單位為dBm)，n∈N。另外，設置覆蓋閾值τ=0.6，即在不確定策略下的全局覆蓋效用必須大于或等于0.6以滿足通信要求，根據(jù)算法設計模擬過程將其分為兩個步驟進行計算。

3.1 覆蓋效用分析

假設任務區(qū)的信息已知，在此將任務區(qū)統(tǒng)一劃分為50×50個單元(每個單元的長度為200 m)，任務區(qū)的設計概率密度函數(shù)服從正態(tài)分布。圖3所示為不同的UAV數(shù)量時的全局覆蓋效用U0的變化。當部署5架或更多UAV時，結(jié)果可以最終收斂到穩(wěn)定狀態(tài)。但當部署4架UAV時，覆蓋概率小于0.6，不能滿足通信需求，無法進行功率控制。

圖3 不同的UAV數(shù)量時的總覆蓋效用

3.2 基于SAP算法最優(yōu)覆蓋部署分析

前文的計算都是在UAV的數(shù)量預先給定的情況下進行的，為了更好地評價所提出方法的效果，將UAV的數(shù)量設置為8來驗證仿真的有效性，結(jié)果見圖4。

圖4 8架無人機最優(yōu)覆蓋部署

圖4(a)為8架UAV在最大載波傳輸功率下最優(yōu)覆蓋部署的覆蓋概率分布圖。從圖中可以看出，單架UAV離某一特定區(qū)域越近，其覆蓋性能就越高，而且UAV重疊檢測區(qū)域的顏色較深，表明多UAV協(xié)同檢測可以提高檢測概率。同時，如果沒有緊密部署不同類型的UAV，會導致覆蓋效用不足。圖4(b)是計算全局覆蓋效用U0的收斂性隨著迭代次數(shù)的變化。為了消除偶然性影響，本文在步驟1中進行了10次計算(見圖4(b)中opt.1～opt.10)。從圖4(b)中曲線可以看出，總覆蓋效用總會收斂到某個特定值，該結(jié)果表明此方法至少存在一個納什均衡點。

3.3 基于SAP算法的最優(yōu)功率控制分析

由于仿真結(jié)果滿足通信要求，接下來對UAV高效節(jié)能的輸電功率分配進行了研究。從圖4(b)的放大圖中可以看出，選擇算法中執(zhí)行步驟2得到的第10條曲線，其結(jié)果也收斂于一個穩(wěn)定的解τ=0.6。這表明根據(jù)上述理論分析，提出的SAP算法可以將結(jié)果收斂到納什均衡點。圖5(a)給出了最優(yōu)部署下最優(yōu)功率控制覆蓋概率分布圖。同時，圖5(b)給出了UAV發(fā)射功率選擇的收斂狀態(tài)，其中每條曲線代表UAV選擇的不同發(fā)射功率。從圖5(b)可以看出，在大約110次迭代之后，每條曲線都收斂于穩(wěn)定狀態(tài)，證明了提出的功率控制方法至少有一個納什均衡點。

圖5 SAP算法的最優(yōu)功率控制分析

圖6為所有UAV的傳輸功率收斂情況，圖7為迭代過程中UAV總能量效率G0的變化情況。圖6和圖7的結(jié)果說明了SAP算法的正確性、有效性和收斂性。更重要的是，在探索最優(yōu)功率選擇策略以使UAV網(wǎng)絡總能量效率最大化的同時，UAV的總傳輸功率也趨向于收斂到最小的結(jié)果。

圖6 所有UAV載波傳輸功率的收斂圖

圖7 在迭代過程中UAV總能量效率的變化

4 結(jié)論

針對UAV協(xié)同覆蓋和節(jié)能通信技術方面存在的問題，本文提出了一種基于博弈論的多UAV覆蓋部署策略，通過計算得到如下結(jié)論：

1) 通過準確描述UAV之間的協(xié)作關系，構(gòu)建了一個多UAV協(xié)同覆蓋部署模型，通過仿真模擬實驗驗證了該方法的有效性和模型的可靠性；

2) 采用集中分布式優(yōu)化體系結(jié)構(gòu)，將多維策略問題分為覆蓋最大化和功率控制兩個步驟，并采用基于空間自適應博弈的多UAV節(jié)能覆蓋部署算法證明了納什均衡點的存在；

3) 通過引入能量效率，構(gòu)建了UAV覆蓋場景來解決能量短缺問題，可使覆蓋場景更加可靠和有效，在實際的多UAV協(xié)同通信場景中具有很大的應用潛力。