基于勢博弈的多QoS無人機基站空間優化部署

蘆方旭,米志超,*,馬駿,李艾靜,王海

1.陸軍工程大學 通信工程學院,南京 210007 2.中國電子科技集團公司第二十八研究所,南京 210007

隨著第五代(5G)移動通信技術的普及,萬物互聯的時代悄然而至,如今,物聯網(IoT)中需要連接的設備數量呈爆炸式增長,預計至2030年,全球IoT設備的數量將達到驚人的800億臺,基于此,泛在網的發展要求更多的基站部署,但諸多現實困難滯緩了地面基站的建設,特別是在運營成本居高不下的偏遠地區和遭遇自然災害導致基站損毀的受災地區。

無人機由于其靈活性強、部署迅速、視距信道(LoS)的高魯棒性等優點,將通信單元安裝在無人機上,構成無人機基站,可以提供緊急通信服務。與地面基站相比,無人機基站可以在極端環境和復雜地形下使用,其優異的靈活性與機動性,可以快速部署到目標區域,例如今年河南省暴雨造成的通信阻隔,通過一架固定翼無人機提供緊急通信服務,這讓無人機基站的緊急覆蓋通信逐步成為現實,但單機的覆蓋時間有限,區域較小,固定翼無人機基站無法懸停且造價高昂。試想采用造價更加低廉的多架旋轉翼無人機基站來實現覆蓋區域更大,更加靈活的本地按需部署。但在同一區域部署過多無人機基站,一方面會造成資源的浪費,特別是在應急救災的環境中,多一架無人機基站就可以連通一大片區域的受災群眾,這對安定人心就有重要意義；另一方面從通信效果來看,過多的無人機基站部署在同一片區域,會造成相互的干擾,相互的影響之下,反而造成通信效用降低,影響接入的用戶。因此需要采用一種更加快速高效的方式來實現合適數量的無人機基站的部署。

在目前對無人機基站的研究中,文獻[4]對無人機進行地空路徑損耗建模,建立了視距(LoS)鏈路和非距線(NLoS)鏈路的通信模型；文獻[5]推導了單個無人機基站在空間部署時,滿足通信閾值條件下的最佳部署高度；文獻[6]主要研究了存在同頻干擾時2個無人機基站的最佳部署距離來最大化覆蓋范圍；文獻[7]采用通過改進的遺傳算法來實現三維空間部署單個無人機基站,旨在最大化覆蓋用戶數量；文獻[8]研究了多個無人機基站在熱點區域采用k-means算法來尋找的無人機三維空間的最佳覆蓋位置。博弈論比起其他帶約束條件的傳統方法,更加便于理解和分析,因此也廣泛應用于無人機領域。文獻[9]把無人機建模為享樂博弈(Hedonic Game)的合作模型去找尋任務分配的納什均衡點,但是享樂博弈需要更多時間才能到達所有無人機的納什均衡點；文獻[10]中使用的是非合作博弈模型,最后也能取得競爭關系的平衡,但該方案不適用于所有類型的無人機網絡；文獻[11]使用博弈論建模無人機基站覆蓋問題,研究了在多無人機基站的覆蓋,發生無人機基站故障時,快速恢復覆蓋通信的能力。

與之前工作不同之處在于,根據局部互利博弈的相關定義,證明了無人機基站部署符合勢博弈模型,并且在純啟發式算法的基礎上,提出一種基于勢博弈的超啟發式算法,用來求解多無人機基站滿足用戶不同QoS需求下的所需的最少無人機數量以及快速覆蓋部署問題。

本文的主要工作如下：

1) 在滿足最高通信閾值的要求下,使用Karush-Kuhn-Tucker(KKT)條件計算出無人機基站的最大覆蓋半徑、最佳高度。

2) 證明無人機基站部署是勢博弈過程,該過程至少具有一個納什均衡(Nash Equilibrium,NE)點,并且該納什均衡點是全局或局部最優解。

3) 在第一步最大覆蓋半徑的基礎上,計算理論上所需無人機基站數量的下限值,采用基于勢博弈的超啟發式灰狼算法(Hyperheuristic Gray Wolf Optimize,HGWO),通過迭代來逼近無人機基站最大覆蓋要求下的納什均衡點,實現無人機基站的最優部署,若能全覆蓋地面用戶,此為全覆蓋用戶要求的最少無人機基站數量,如若不能,增加無人機基站數量。

1 系統模型與問題描述

1.1 系統模型

考慮在復雜地形環境下發生戰爭或者自然災害,地面基站損毀,目標區域內密集分布各種通信設備,緊急部署無人機基站,對地面所有用戶提供通信服務,目標是要實現盡可能少的無人機基站覆蓋地面用戶,系統模型如圖1所示。

圖1 系統模型圖Fig.1 System model

對用戶接收功率建模,用戶的接收信號功率′由視距連接和非視距連接2部分組成,具體表示為

(1)

式中：′為無人機基站的發射功率；為用戶到無人機基站鏈路上的路徑損耗指數；為由于非視距連接而產生的附加衰減因子；為用戶到無人機基站水平位置投影點的距離；為無人機基站的垂直高度。

采用地空信道模型,LoS傳輸的概率和仰角的表達式為

(2)

(3)

式中：、是由環境決定的路徑損耗參數。NLoS傳輸的概率為=1-。

由式(1)和式(2)可以得到用戶的接收功率為

(4)

用戶的信干噪比(Signal to Interference plus Noise Ratio, SINR)可表示為

(5)

假設所處區域的用戶存在個不同的服務質量(Quality of Service,QoS)需求,即用戶的通信閾值存在個不同的值,只有滿足SINR≥時,用戶與無人機基站連通,為不同QoS需求用戶的通信閾值。因此構造指示函數,表示為

(6)

即當用戶被無人機基站覆蓋時,,=1,否則,=0。

無人機基站覆蓋通信的用戶數量可表示為

(7)

式中：表示部署區域的用戶總數。

目標區域內,個無人機基站通信覆蓋用戶數量為

(8)

1.2 問題描述

優化目標是用盡可能少的無人機基站覆蓋整個區域,即用最少的個無人機基站覆蓋個不同通信閾值的個用戶。該優化問題表述為

(9a)

s.t.

=

(9b)

,∈{0,1}, ?∈,∈

(9c)

(9d)

≤≤

(9e)

(9f)

SINR≥, ?∈,?∈

(9g)

約束條件(9b)表示目標區域內個用戶被基站全覆蓋；約束條件(9c)指定了指示函數的取值范圍；式(9d)表示任意用戶至多與一個無人機基站連通；約束條件(9e)是對無人機的部署高度進行限制；約束條件(9f)表示單個無人機基站覆蓋的用戶數量要小于無人機基站允許連通的最大用戶數量；約束條件(9g)表示,滿足被無人機基站的覆蓋條件是接收信干噪比要大于通信閾值。

2 解決方案

2.1 計算最少無人機基站數量的下限值

用和分別表示無人機基站的覆蓋半徑與部署高度,優化目標是用最少的無人機基站進行目標區域的覆蓋,當無人機基站的覆蓋半徑最大時,部署的無人機基站數量最少。求解滿足用戶通信閾值的單個無人機基站最大的覆蓋半徑,該問題可以表示為

(10)

把P2問題簡化,用戶的不同通信閾值統記為,使用KKT條件來求解該約束條件的最優化問題。因此結合式(3)該問題可以轉化為

為了表述簡單,定義以下變量來表述函數

根據KKT條件,參數需要滿足以下條件：

利用KKT條件分類討論求解,可以得到

(11)

此覆蓋半徑是理論上的最大覆蓋半徑。

2.2 無人機基站部署的博弈模型

用最少的無人機基站進行目標區域的覆蓋,就必須要確保給定的無人機基站放置在最佳部署位置。因此首要解決的問題是給定無人機基站來快速尋求最大覆蓋用戶的部署位置,該問題可以表示為

P4: max

s.t.

(12)

為了解決最大覆蓋問題,無人機基站的部署使用博弈論建模,將模型記為={,,},其中:是部署的無人機基站；是無人機基站部署位置合集,分為近點與遠點,近點是無人機基站在周邊的27個位置,簡單描述為{原點、前、后、左、右、上、以及各自的對角位置}；遠點表示無人機基站的全局搜索位置,以更遠的部署為遠點。如圖2 所示,紅色小球表示無人機基站的當下位置,五角星所在的空間位置表示近點位置,其余空間表示遠點位置。是效用函數,定義為任意基站和其相鄰基站的覆蓋用戶數：

式中：J表示無人機基站的相鄰無人機基站的集合；(,J)=,?∈,即(,J)表示無人機基站的覆蓋用戶數。相鄰無人機基站即兩無人機基站的中心位置在水平方位的距離小于基站的最大覆蓋范圍。

圖2 無人機基站部署位置示意圖Fig.2 UAV-BS deployment location schematic

如果存在一個勢函數對于任意的參與者的狀態由變為′若滿足

(′,-)-(,-)=(′,-)-(,-)

則該博弈稱為精確勢博弈。即勢博弈中任意參與者單方面改變策略導致的效用函數變化量等于勢函數的變化量。

無人機基站的部署模型是一個精確勢博弈,至少有一個納什均衡點。

構造勢函數

式中:-表示除參與者之外的其他參與者的狀態集合；勢函數(,-)為式(8)表示的整個區域的無人機基站的覆蓋數量。

在無人機基站的狀態集合中,任意無人機基站的部署位置的變化都只會影響相鄰無人機基站的用戶覆蓋。因此,對于任意的無人機基站由位置變為′,勢函數的變化為

(′,-)-(,-)=(′,J)+

任意無人機基站的位置變動,都只會影響相鄰的無人機基站覆蓋下的用戶,即

可以得出：

(′,-)-(,-)=(′,-)-(,-)

由定義可知,該過程是一個精確勢博弈過程。

由勢博弈的諸多性質可得,勢博弈至少有一個納什均衡點,并且該點是勢函數的全局或局部最優解。

2.3 算法設計

由于無人機基站的部署還要考慮當下部署位置與相鄰無人機基站的關系,相互之間存在耦合關系,所以很難求得精確的納什均衡點。因此,本文提出一種超啟發式灰狼算法(Hyperheuristic Gray Wolf Optimize,HGWO),通過迭代的方式去逼近無人機基站部署博弈的納什均衡點,從而實現無人機基站的部署優化。

超啟發式灰狼算法可以產生既適應參與者狀態又適應博弈動態的策略。提出的算法的基本思路是將問題的搜索空間分為近點與遠點搜索兩大類擴大搜索空間,目標函數映射為博弈的效用函數,通過多次迭代來逼近納什均衡解,同時使用啟發式算法思想根據博弈的結構來動態調整選擇策略,以期望用最小的代價快速求得最優解。

計算遠點效用函數值,選擇使用灰狼優化算法(Gray Wolf Optimizer,GWO),該算法是受到了灰狼捕食獵物活動的啟發而開發的一種優化搜索方法。在野外的狼群具有一定的社會性,狼群的捕食行為主要是在首領的帶領下協作完成,把眾多的普通狼個體稱為搜索因子,具有全局搜索的能力,主要的逼近獵物(目標函數)是由幾個首領(按效用函數排序)完成的。該算法結構簡單,初始搜索空間大,并且由于后續搜索空間不斷減少,收斂速度快。

(13)

(14)

(15)

(16)

超啟發式灰狼算法的概率更新公式為

(17)

由Δ(′)的更新公式可得,只有無人機基站選擇變動部署位置才會更新效用差值,否則保持不變。

具體算法框架如圖3所示。實現過程如算法1所示。

圖3 超啟發式算法流程圖Fig.3 Flow chart of hyperheuristic methodology

算法1 基于HGWO的快速部署算法初始化 地面用戶在目標區域隨機分布;計算最大覆蓋半徑和無人機基站數量的下限M;隨機生成無人機基站位置;設置迭代次數t=0。循環開始:步驟1 設置無人機基站數量為計算所需無人機基站數量的下限M。步驟2 設置迭代次數t=1。步驟3 任選一個無人機基站,對所有無人機基站依次執行步驟4 ～步驟11。步驟4 隨機生成ζ個搜索代理的位置;判斷選定的無人機基站和生成的搜索代理的位置是否超出區域邊界,高度是否在限制條件內,若否則調整至該區域內。步驟5 搜索遠點位置:用搜索代理位置依次替換無人機基站位置,分別計算效用函數ui,選取效用函數最大的3個位置標記為3個首領位置α、β、δ,根據式(16)和式(17)計算遠點選擇位置。步驟6 搜索近點位置:計算無人機基站的近點位置的效用函數,計算效用函數值最大的近點選擇位置。步驟7 比較近點與遠點的效用函數值,根據式(18)的概率選擇一個部署位置。步驟8 根據式(14)和式(15)調整A→、C→2個參數;根據3個首領位置α、β、δ和最終選擇的部署位置,根據式(16)更新搜索代理的位置。步驟9 調整迭代次數,t=t+1。步驟10 判斷迭代次數t是否達到最大迭代次數,若是,則記錄效用函數值,計算覆蓋率;否則返回步驟3。步驟11 若達設置迭代次數后,此時覆蓋率為1,記錄無人機基站數量,循環結束;若此時覆蓋率不為1,無人機基站數量設置為M=M+1,返回步驟2。

2.4 算法分析

多無人機基站的精確通信覆蓋,用盡量少的通信資源取得最大的覆蓋效果,這對于救災搶險甚至是軍事斗爭都具有現實意義。

使用所提的超啟發式灰狼算法,無人機基站的部署博弈以概率1收斂至納什均衡點。

根據以上對超啟發式灰狼算法的描述可知,任意無人機基站的效用函數在迭代過程中都是非減的。由于無人機基站部署博弈是精確勢博弈,任意參與者單方面改變策略導致的效用函數變化量與勢函數的變化量一樣,因此整個區域的總覆蓋率在迭代過程中也是非減的。而對于一個用戶數量有限的靜止網絡,其通信覆蓋數量會有上界并且是確定的。因此,使用所提的超啟發式灰狼算法,多個無人機基站的部署必然會收斂至一個穩定狀態,使得任意無人機基站單方面改變其部署位置無法提升其自身效用值或全網覆蓋率,根據定義1,該穩定狀態即為納什均衡點。證畢。

啟發式算法往往可以快速、高效地尋得一個比較好的解,但是也容易出現過早收斂,陷入局部最優解,而放棄尋找全局最優解。為了克服傳統啟發式算法陷入過早收斂,使用近點搜索和策略選擇概率對納什均衡點施加一定的擾動,使其偏離原納什均衡點,接著由各無人機基站按照原搜索策略動態恢復到新的納什均衡點。不斷重復這樣的擾動恢復過程直至搜尋到更優的納什均衡點,近點搜索的擾動在最優部署位置附近擾動幅度較小,因此當擾動范圍小于一定數量,根據定理2,該過程一定會最終收斂到納什均衡點。同時由于部署區域遠大于博弈探索算法中的移動探索距離,再增加全局搜索位置之后,算法收斂速度明顯加快。

3 仿真結果與性能分析

本節對無人機基站的部署進行仿真分析,由環境影響的信道參數=9.61,=0.16,用戶的數量為500個,共有4種不同的信道容量需求,隨機分布在區域大小為4 km×4 km的目標區域內,單個無人機的最大覆蓋用戶數設置為80個,其他仿真參數的設置如表1所示。

表1 部分仿真參數的設置Table 1 Setting of part of simulation parameters

3.1 無人機初始化設置

在仿真的設置中,用戶的通信閾值設定參考文獻[17]。為突出算法的針對性,選取通信閾值較為接近的多種用戶類型,來討論無人機基站的覆蓋性,設置如表2所示。

表2 用戶設置Table 1 User’s settings

在目標地區部署不同QoS需求的用戶,用戶的位置是隨機的,并且無人機覆蓋用戶數量也會因為不同QoS需求而不同,因此,引入松弛條件,假設該地區覆蓋的用戶服務質量只有一種類型,用戶的最高通信閾值記為,用戶的最低通信閾值記為,討論在與下,無人機基站部署的數量。在確定通信閾值的情況下,無人機的初始高度與最大的覆蓋半徑如圖4所示。

圖4 無人機的高度與接收信噪比關系Fig.4 Relationship between height of UAV and received SINR

根據式(4)和式(12)和圖4可得,影響用戶接收功率的因素主要是2個,一是無人機基站到用戶的仰角,進而影響到視距與非視距鏈路的連接概率；二是無人機基站到用戶的連接距離。當無人機基站的高度較低時以視距(LoS)連接鏈路為主,高度較高時,以非視距(NLoS)鏈路連接為主,當無人機基站的高度逐步升高時,會存在主要接收信號從視距鏈路到非視距鏈路的變化,此時存在臨界點,即為無人機基站的最大接收信號時的高度,因此,高度與接收信號的閾值關系即先升后降。在本節中,滿足最高通信閾值的最大覆蓋半徑為471 m,最低通信閾值的最大覆蓋半徑為692 m,進而求出無人機基站的下限為9個。

3.2 不同算法空間部署示意

在模擬中,選擇基于K均值的布局(K-means)算法,基于改進遺傳算法的純啟發式多種群遺傳算法(Multi-Population Genetic Algorithm,MPGA)、原始的灰狼算法(Gray Wolf Optimizer,GWO)作為基準方案。

K-means聚類算法對用戶進行快速聚類,從使用最少無人機基站開始,檢查是否滿足無人機基站的服務半徑和服務能力約束。如果不是,則添加一架無人機基站并重復上述步驟,直到所有用戶都滿足約束條件為止。

MPGA算法和原始灰狼算法采用改進的純啟發式算法,對比提出的HGWO算法,容易陷入局部最優,多次仿真求平均值后,算法性能不穩定。

圖5中,地面不同顏色的符號表示不同QOS地面用戶隨機分布的位置,分別使用本文提出的HGWO算法、MPGA算法、GWO算法、K-means算法進行多次仿真的穩定值。紅色小球表示在該算法下無人機基站的部署位置,三維空間中無人機基站在、平面的投影位置用橙色和紫羅蘭色表示。本文提出的HGWO算法比起傳統的GWO算法在無人機基站部署數量方面減少約18%。

3.3 算法收斂性

圖6表示9個無人機基站覆蓋下的算法收斂過程,與定理2描述的一樣,本文所提HGWO算法最終收斂到納什均衡點。勢博弈探索算法(Potential Game Exploration algorithm,PGE)是把無人機基站下一步的運動位置建模在周圍一定距離內,通過式(17)選擇動作的概率,來逐步尋找最佳部署位置。

圖6 算法的收斂性Fig.6 Convergence of algorithms

與本文所提HGWO算法對比,由于部署的區域遠大于PGE算法中的移動探索距離,依一定概率探索選擇最佳部署位置,算法的收斂速度較為緩慢,而本文所提算法,在近點周邊搜索的基礎上,加以啟發式算法進行遠點的全局搜索,算法收斂速度明顯加快。

3.4 無人機基站部署數量

圖7(a)表示區域長度為2 km,4種算法下覆蓋用戶數量變化對全覆蓋所需的無人機數量的影響,當區域一定,用戶數量較少時,無人機數量相對少一些,但是當用戶多到一定數量時,無人機基站受到最大連通數的限制,用戶數量增加,無人機基站的數量也持續增加。

圖7(b)表示用戶數量為500個,4種算法下覆蓋區域大小對全覆蓋所需的無人機數量的影響。當用戶數量一定時,目標區域越小,無人機基站在允許的最大覆蓋數量內,覆蓋范圍越集中,覆蓋用戶所需的無人機基站數量越接近于理論值；但隨著目標區域的變大,用戶分布密度變小,考慮到無人機基站覆蓋半徑的限制,需要更多的無人機基站來覆蓋用戶,覆蓋用戶所需的無人機基站數量與理論值之間的差距變得越來越明顯。

4 結 論

考慮到用戶不同的服務質量要求和無人機的接收干擾問題,以無人機作為通信基站,為地面用戶提供服務,求解全覆蓋用戶的條件下最少無人機基站的最優部署問題。首先,通過KKT條件求解滿足通信閾值的無人機的最大服務半徑；其次,將無人機基站部署建模為局部互利博弈模型,并證明該博弈是精確勢博弈,至少具有一個納什均衡點；再次,在此基礎上,提出了一種超啟發式灰狼算法,通過迭代來逼近無人機基站最大覆蓋要求下的納什均衡點,實現最少無人機基站數量的最優部署；最后,仿真結果表明,所提出的解決方案在最小化無人機基站數量和加快收斂速度方面具有顯著的優勢。