多無人機(jī)輔助通信中用戶匹配與頻譜資源聯(lián)合優(yōu)化方法*

吳 迪,錢鵬智,陳 勇,2

(1.國防科技大學(xué)第六十三研究所,南京 210007;2.陸軍工程大學(xué) 通信工程學(xué)院,南京 210007)

0 引 言

新一代無線通信網(wǎng)絡(luò)有望在任何時間任何地點為數(shù)十億設(shè)備提供更大容量、更低延遲、更高可靠性和穩(wěn)定性的通信服務(wù)[1-2],然而在某些特殊情況下,例如自然災(zāi)害后需快速恢復(fù)信息服務(wù),部署地面無線基礎(chǔ)設(shè)施具有相當(dāng)大的挑戰(zhàn)性。無人機(jī)由于其移動性、靈活性和可控性等優(yōu)勢可以不受地形影響大幅度提高通信的覆蓋范圍、用戶的服務(wù)質(zhì)量,因此,將無人機(jī)作為基站為用戶提供臨時服務(wù)可以克服地面固定無線基礎(chǔ)設(shè)施的局限性[3-6]。

然而,設(shè)計有效的無人機(jī)通信網(wǎng)絡(luò)具有一定的挑戰(zhàn)性[3]。首先,針對不同類型無人機(jī)通信的信道建模是一項重要挑戰(zhàn),因為無人機(jī)和地面用戶之間的空對地(Air-to-Ground,A2G)通信信道必須考慮潛在的視距和非視距傳播概率。其次,無人機(jī)在三維空間的位置部署和與服務(wù)用戶的匹配問題對無人機(jī)能量消耗和用戶通信質(zhì)量都有著顯著的影響。最后,如何高效地分配有限頻譜資源,例如信道和功率等,對無人機(jī)通信網(wǎng)絡(luò)的性能至關(guān)重要。

近年來,針對無人機(jī)輔助通信的場景,學(xué)者們已經(jīng)進(jìn)行了大量研究。Xi等人[7]聯(lián)合優(yōu)化用戶關(guān)聯(lián)和無人機(jī)位置最大化下行用戶的總速率。由于原問題是混合整數(shù)非凸優(yōu)化問題,作者將其分解為整數(shù)的用戶關(guān)聯(lián)問題和非凸的無人機(jī)位置優(yōu)化問題,然后交替迭代求得次優(yōu)解。Huang等人[8]以地面用戶最小平均速率最大化為目標(biāo),研究了無人機(jī)飛行軌跡和連續(xù)帶寬分配的問題,利用交替優(yōu)化技術(shù)求得問題的相對最優(yōu)解。Nguyen等人[9]以最大化用戶的最小傳輸速率為目標(biāo),考慮子信道分配和無人機(jī)軌跡控制的聯(lián)合優(yōu)化,采用交替優(yōu)化方法直到得到相對最優(yōu)解。但是以上工作都只考慮了單無人機(jī)場景的資源分配與部署優(yōu)化,不存在頻譜復(fù)用及共信道干擾。為此,Cai等人[10]考慮了共信道干擾,但是其僅研究了存在一架無人機(jī)和一架干擾機(jī)的無線網(wǎng)絡(luò)問題,通過對發(fā)射功率、子信道分配進(jìn)行聯(lián)合優(yōu)化,以實現(xiàn)系統(tǒng)能量效率的最大化。張遼平[11]考慮了共信道干擾,以吞吐量為性能優(yōu)化指標(biāo),聯(lián)合優(yōu)化多小區(qū)網(wǎng)絡(luò)中子信道分配和功率分配,但是其子信道分配方式僅采用單信道分配,即當(dāng)信道數(shù)大于用戶數(shù)時,用戶只能選擇接入性能更好的信道而不能接入多個信道,制約了其傳輸速率的提升。

鑒于當(dāng)前多無人機(jī)輔助通信下動態(tài)頻譜分配面臨的挑戰(zhàn)與不足,本文提出了一種用戶匹配與頻譜資源聯(lián)合優(yōu)化算法,通過不同參數(shù)下的性能分析和算法對比,證明其可以有效提升用戶的傳輸速率,保證用戶通信的公平性。

與現(xiàn)有研究相比,本文的主要貢獻(xiàn)與創(chuàng)新如下:

1)構(gòu)建了多無人機(jī)作為臨時基站輔助地面用戶進(jìn)行通信的場景,為了保證用戶通信的公平性,在考慮頻譜復(fù)用和共信道干擾的情況下,以最大化地面用戶最小傳輸速率為目標(biāo),提出了一種用戶匹配與頻譜資源聯(lián)合優(yōu)化算法。該算法將混合整數(shù)非線性規(guī)劃(Non-linear-optimization Problem,MINLP)問題分解為多個子問題,從無人機(jī)-地面用戶匹配、子信道分配和功率分配三個方面進(jìn)行求解,并最終得到原問題的一個相對最優(yōu)解。

2)對于無人機(jī)-用戶匹配子問題,通過K均值聚類算法(K-Means Algorithm,KMA)進(jìn)行優(yōu)化,確保每一個地面用戶到其服務(wù)無人機(jī)的距離最小,最大程度減少傳輸速率的路徑損耗。在確定無人機(jī)-用戶匹配后,所求優(yōu)化問題仍然高度非凸,因此通過塊坐標(biāo)下降(Block Coordinate Descent,BCD)法將原始的優(yōu)化問題分解成兩個子問題,對信道分配和功率分配進(jìn)行迭代交替優(yōu)化,即固定一個變量優(yōu)化另一個變量,從而得到一個較為理想的局部最優(yōu)解。對于信道分配子問題,采用遺傳算法(Genetic Algorithm,GA)進(jìn)行求解,通過引入精英保留策略,確保每次進(jìn)化的最佳個體都被保留下來;對于非凸功率優(yōu)化子問題,采用幾何規(guī)劃算法對非凸子問題進(jìn)行凸化,并應(yīng)用CVX進(jìn)行求解。

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

考慮圖1所示的系統(tǒng)模型,目標(biāo)區(qū)域中的蜂窩基站由于自然災(zāi)害發(fā)生故障,在上空部署多架旋翼無人機(jī)(可以在空中懸停)作為臨時基站為地面用戶設(shè)備提供通信服務(wù),其集合可以表示為無人機(jī)M={1,2…,M},地面用戶K={1,2…,K},信道N={1,2…,N},并且滿足M

1.1 無人機(jī)與地面用戶匹配

給定地面用戶分布后,首先要確定無人機(jī)與地面用戶的匹配問題,即地面用戶要按照無人機(jī)數(shù)量進(jìn)行分簇,由簇頭無人機(jī)提供本簇內(nèi)所有用戶的通信服務(wù)。相應(yīng)的決策變量定義為

(1)

為了保證用戶的持續(xù)通信,任意地面用戶都要有且僅有一架無人機(jī)提供服務(wù),即有如下約束條件:

(2)

1.2 信道分配

其次要確定為每個地面用戶分配的信道,假設(shè)每個信道的帶寬為B,相應(yīng)的決策變量定義為

(3)

由于無人機(jī)服務(wù)地面用戶采用正交頻分多址技術(shù),其通信鏈路可以占用多個信道;同時為了保證用戶的持續(xù)通信,每個用戶至少占用一個信道。約束條件如下:

(4)

同時存在約束,對于任意給定無人機(jī),一個信道僅能服務(wù)一個地面用戶,這就導(dǎo)致了無人機(jī)-用戶匹配矩陣與信道分配矩陣的耦合,表示為

(5)

1.3 功率分配

當(dāng)分配無人機(jī)用戶m為地面用戶k服務(wù)時,其通信鏈路可以占用多個信道以不同功率進(jìn)行傳輸。用Pm,n表示無人機(jī)m在信道n中的傳輸功率,要滿足一架無人機(jī)在所有信道中的發(fā)射功率不超過自身發(fā)射功率上限,表示為

(6)

1.4 通信模型

實際通信場景中,空對地鏈路會受到障礙物的阻擋,所以本文考慮載頻為2 GHz時的A2G信道模型[12],即無人機(jī)m到地面用戶k的通信鏈路由視距鏈路和非視距鏈路組成,其信道增益系數(shù)hUm,k可由式(7)～(9)表示:

hUm,k=PLoS×dUm,k-αu+PNLoS×ηdUm,k-αu,

(7)

(8)

(9)

式中:PLoS為視距鏈路傳輸概率;PNLoS=1-PLoS為非視距鏈路傳輸概率;a和b是常數(shù)取決于傳播環(huán)境;η為非視距鏈路的衰減因子;αu為空對地路徑損耗指數(shù);H為無人機(jī)飛行高度;dUm,k為無人機(jī)m到地面用戶k的水平距離。

根據(jù)香農(nóng)公式,無人機(jī)m在信道n上服務(wù)地面用戶k的可達(dá)傳輸速率為

(10)

式中:B為信道帶寬;N0為背景噪聲功率;IU為不同簇之間的共信道干擾,具體表示為

(11)

式中:i∈M且i≠m,代表除無人機(jī)m之外的其他無人機(jī);j∈K且j≠k代表除地面用戶k之外的其他地面用戶。

1.5 問題構(gòu)建

(12a)

(12b)

(12c)

(12d)

(12e)

C5:Pm,n≥0,?m,n;

(12f)

(12g)

C7:ωm,k∈{0,1},?m,k;

(12h)

C8:bk,n∈{0,1},?k,n。

(12i)

式中:C1表示任意地面用戶在所有信道內(nèi)傳輸速率之和都大于目標(biāo)函數(shù)μ;C2表示一個地面用戶只能由一個無人機(jī)服務(wù);C3表示無人機(jī)至少占用一個信道為地面用戶提供服務(wù);C4表示對于給定無人機(jī),一個信道只允許分配一個地面用戶;C5表示任意無人機(jī)在信道中的功率不為負(fù);C6表示任意無人機(jī)在所有信道發(fā)射功率的總和不超過自身最大發(fā)射功率;C7表示無人機(jī)-用戶匹配矩陣中各元素的取值范圍為0或1;C8表示信道分配矩陣中各元素的取值范圍為0或1。

2 問題求解

由于目標(biāo)函數(shù)涉及到二進(jìn)制變量ωm,k,bk,n和連續(xù)變量Pm,n,因此公式(12)是一個MINLP問題,很難直接求解全局最優(yōu)解,一般只能求得次優(yōu)解。本文通過將原始優(yōu)化問題分解成多個子優(yōu)化問題,然后分別提出求解算法。通過聚類算法求解無人機(jī)-地面用戶匹配子問題,而子信道分配和功率分配是相互影響的,兩者相互制約,因此利用BCD算法交替迭代優(yōu)化信道分配和功率分配直到收斂,得到一個次優(yōu)解。

2.1 優(yōu)化無人機(jī)-地面用戶匹配

由于距離是影響地面用戶傳輸速率的一個重要因素,受文獻(xiàn)[11]啟發(fā),利用K-Means聚類算法根據(jù)用戶位置將其劃分為M個簇,并得到簇頭無人機(jī)的最優(yōu)位置,使簇內(nèi)用戶到簇頭無人機(jī)的距離最短,即確保路徑損耗的傳輸速率最小。

基于K-Means的無人機(jī)-用戶匹配算法(算法1)具體步驟如下:

輸入:無人機(jī)數(shù)M,地面用戶位置坐標(biāo)(X1,Y1),(X2,Y2)…(XK,YK)

1初始化:r=0,隨機(jī)從用戶位置中產(chǎn)生M個不同種子做為聚類中心(XU1,YU1),(XU2,YU2)…(XUM,YUM);

2循環(huán):

3r=r+1;

5計算各聚類的類中心,類中心的橫坐標(biāo)是聚類中所有元素橫坐標(biāo)的平均值,縱坐標(biāo)類似,并將種子移至其類中心處,得到新的種子坐標(biāo)(XU1*,YU1*),(XU2*,YU2*)…(XUM*,YUM*);

否則,返回循環(huán);

其中,關(guān)于第一次選擇種子點一定要選擇地面用戶位置處,如果不這樣會在結(jié)果中出現(xiàn)某一個聚類的成員數(shù)量為0,顯示不符合要分為K類的要求。

2.2 優(yōu)化信道分配策略

令Wf和Pf作為固定變量,Bf作為決策變量,則式(12)中MINLP問題轉(zhuǎn)化為整數(shù)規(guī)劃問題,可描述為

(13)

該整數(shù)非凸優(yōu)化問題的求解難度較大,因此本文提出了一種基于GA的信道分配算法(算法2),具體求解步驟如下:

輸入:地面用戶數(shù)K,可用信道數(shù)N,無人機(jī)-地面用戶匹配矩陣Wf,功率分配矩陣Pf

2 循環(huán):

3r=r+1;

4 為了保證種群的多樣性,進(jìn)行基因交叉、基因變異操作,產(chǎn)生新的個體;

5 為了防止經(jīng)過步驟4后產(chǎn)生多個不符合條件的個體,進(jìn)行基因修正和基因篩選操作;

6 根據(jù)適應(yīng)度函數(shù)μ計算種群中個體適應(yīng)度,按輪盤賭策略進(jìn)行選擇,控制種群數(shù)目為初始種群數(shù)λ,并保留最優(yōu)個體;

7 算法執(zhí)行達(dá)到預(yù)先所設(shè)置的代數(shù),則結(jié)束;

否則返回循環(huán);

算法的關(guān)鍵步驟說明如下:

1)基因編碼:首先對信道分配矩陣Bf進(jìn)行基因拉直,即將K×N矩陣轉(zhuǎn)化為1×KN的行向量,作為種群中的一個個體。

2)初始種群:隨機(jī)生成一個λ×KN的二維矩陣,其中λ為種群中的個體數(shù)量。

3)基因交叉:將種群中的λ個個體以隨機(jī)的方式進(jìn)行配對組成λ/2對配對基因組,然后再對配對基因組中的兩個基因進(jìn)行交叉。本文中采用單點交叉法,即根據(jù)給定交叉概率pc在交叉點處互相交換對方基因,從而產(chǎn)生新的編碼向量。

4)基因變異:為了在尋找最優(yōu)解過程中優(yōu)化局部搜索能力和保持種群的多樣性,防止出現(xiàn)早熟收斂。即根據(jù)給定變異概率pm對基因中的一個或多個變異點值進(jìn)行取反操作,從而產(chǎn)生新的編碼向量。

5)基因修正、篩選:在對種群中個體進(jìn)行選擇前,按照問題(13)中的約束條件對經(jīng)過基因交叉和變異的個體進(jìn)行修正和篩選,防止種群中存在過多不滿足條件的基因個體。

6)適應(yīng)度函數(shù):適應(yīng)度函數(shù)代表種群中個體的適應(yīng)能力,本算法中即為問題(13)的優(yōu)化目標(biāo)μ。

7)選擇策略:這里采用的選擇策略是輪盤賭選擇法。該方法的選擇依據(jù)是個體適應(yīng)度的大小,如果個體適應(yīng)值小它就很有可能被丟棄,如果個體的適應(yīng)值大,它被選中的概率就大。通過選擇策略,將種群數(shù)目控制在初始種群數(shù)λ。同時,為了保證最佳個體在選擇和交叉的過程中不被丟失,在算法的實施過程中還引入了精英保留策略,即保存每一代的最佳個體到下一代,提高了算法的收斂速度。

2.3 優(yōu)化功率分配策略

將Wf和Bf作為固定變量,Pf作為決策變量,則式(12)中MINLP問題轉(zhuǎn)化為非整數(shù)規(guī)劃問題,可描述為

(14)

可以看出功率分配子問題是一個非凸優(yōu)化問題,可以通過幾何規(guī)劃[13]將其轉(zhuǎn)化為一個凸優(yōu)化問題。

證明如下:

(15)

(16a)

(16b)

(16c)

2.4 總體算法及收斂性

基于前面三小節(jié)的部分結(jié)果,本文提出了用戶匹配與頻譜資源聯(lián)合優(yōu)化算法(算法4),具體步驟如下:

輸入:無人機(jī)數(shù)M,地面用戶數(shù)K,可用信道數(shù)N,地面用戶位置坐標(biāo)(X1,Y1),(X2,Y2)…(XK,YK)

2 通過算法1優(yōu)化最優(yōu)無人機(jī)-地面用戶匹配;

3 循環(huán):

6 更新r=r+1;

7 終止:μr+1-μr≤ζ或者達(dá)到最大迭代次數(shù)rmax,則結(jié)束;否則,返回循環(huán)

其中,在步驟2通過算法1得到最優(yōu)無人機(jī)-地面用戶匹配后,原優(yōu)化問題仍然高度非凸,因此本文利用BCD算法,將原優(yōu)化問題分為兩個子問題進(jìn)行求解,對信道分配和功率分配進(jìn)行交替優(yōu)化,即固定一個變量優(yōu)化另一個變量,從而得到一個較為理想的局部最優(yōu)解,對應(yīng)算法4中步驟3～6的循環(huán)部分。而對于BCD算法中每個子問題的求解,則是對應(yīng)步驟4和步驟5。

在確定最優(yōu)無人機(jī)-用戶匹配矩陣后,基于BCD算法對信道分配與功率分配進(jìn)行迭代優(yōu)化,直到目標(biāo)函數(shù)的增長值小于給定的閾值ζ。由于每一個子問題的優(yōu)化結(jié)果都是遞增的,而傳輸速率作為優(yōu)化目標(biāo),其值一定存在一個上限,所以算法4必定收斂到一個可行解。

圖2為算法4的流程示意圖。

圖2 用戶匹配與頻譜資源聯(lián)合優(yōu)化算法流程

2.5 復(fù)雜度分析

首先根據(jù)用戶分布情況,利用K-Means算法進(jìn)行用戶劃分和無人機(jī)位置確定。設(shè)K-Means算法的最大迭代次數(shù)為T1,地面用戶數(shù)為K,簇數(shù)為M,則其復(fù)雜度為O1(KMT1)。接下來是基于BCD的信道分配和功率分配的聯(lián)合迭代優(yōu)化過程。基于GA的信道分配中,GA的復(fù)雜度取決于其適應(yīng)度函數(shù)O22(μ)的復(fù)雜度,假設(shè)最大迭代次數(shù)為T2,種群數(shù)量為λ,則復(fù)雜度為O2(T2×λ×O22(μ));基于凸優(yōu)化求解功率優(yōu)化問題的復(fù)雜度為O3(M(N)4.5lb(1/ζ))[13]。設(shè)T為算法4的外層迭代次數(shù),則聯(lián)合優(yōu)化算法的復(fù)雜度為O(O1+T(O2+O3))。

3 仿真與分析

仿真參數(shù)設(shè)置如表1所示[15-16]。

表1 仿真參數(shù)設(shè)置

圖3展示了無人機(jī)-地面用戶匹配優(yōu)化后的位置分布圖,黑色五角星代表經(jīng)過優(yōu)化后的無人機(jī)最佳位置,地面用戶的不同顏色代表經(jīng)過聚類算法優(yōu)化后用戶與不同的無人機(jī)進(jìn)行匹配?？梢钥闯鰞?yōu)化后,每個用戶到其中心無人機(jī)的距離都為最短,即可以保證由于路徑損耗的傳輸速率最小。

圖3 無人機(jī)-地面用戶匹配優(yōu)化后位置分布

圖4為基于遺傳算法的信道分配求解,初始種群設(shè)為60,最大代數(shù)為100,交叉概率0.95,變異概率0.1。結(jié)果顯示當(dāng)進(jìn)化達(dá)到43代時,種群的平均適應(yīng)度即地面用戶的最小傳輸速率達(dá)到穩(wěn)定。

圖4 基于遺傳算法的信道分配

圖5展示了可用信道數(shù)為10,不同地面用戶數(shù)下的用戶最小傳輸速率對比,結(jié)果表明隨著地面用戶數(shù)的增加,用戶最小傳輸速率在減小。這是由于為了滿足每個用戶的通信需求,會有多個用戶占用同一信道,共信道干擾增加。此外,無人機(jī)數(shù)目越多,用戶最小用戶傳輸速率越大。這是因為當(dāng)大量無人機(jī)服務(wù)特定數(shù)量的地面用戶時,無人機(jī)與地面用戶的距離較小。但是由于地面用戶數(shù)量越來越多,簇間干擾越強(qiáng),不同無人機(jī)數(shù)場景下的傳輸速率差異越小。

圖5 用戶最小傳輸速率隨地面用戶數(shù)變化

圖6展示了地面用戶數(shù)為12,不同信道數(shù)下的用戶最小傳輸速率對比,可以看出用戶最小傳輸速率幾乎隨著信道數(shù)的增加呈線性增加。此外,無人機(jī)數(shù)目越多,用戶最小傳輸速率也越大,并且隨著信道數(shù)的增加差異會變得越來越明顯。

圖6 用戶最小傳輸速率隨可接入信道數(shù)變化

圖7分別展示了聯(lián)合資源優(yōu)化算法在不同場景下的收斂曲線,可以看出目標(biāo)函數(shù)值在迭代過程中不斷增加,同時隨著無人機(jī)數(shù)、信道數(shù)的增加,聯(lián)合優(yōu)化算法的復(fù)雜度增加,其所需的迭代次數(shù)也隨之增加。

圖7 聯(lián)合資源優(yōu)化算法收斂對比

為了進(jìn)一步驗證本文所提算法在多無人機(jī)輔助通信場景中的有效性,與聯(lián)合最大權(quán)匹配[11]和功率優(yōu)化算法、信道優(yōu)化算法和功率優(yōu)化算法進(jìn)行了對比。最大權(quán)匹配算法通過進(jìn)行多次單信道接入方式的頻譜分配,確保每個用戶都占用一個信道。該算法中用戶可以選擇更高質(zhì)量的信道,從而提高傳輸速率。圖8展示了5架無人機(jī),12個地面戶場景下的四種方案性能對比,可以看出本文所提出的聯(lián)合優(yōu)化算法性能優(yōu)于單一信道優(yōu)化算法和功率優(yōu)化算法,聯(lián)合最大權(quán)匹配和功率優(yōu)化算法在信道數(shù)超過用戶數(shù)時就不能大幅度提升其傳輸速率。這是因為其無法為地面用戶繼續(xù)分配信道,只能根據(jù)新增信道的情況,將其調(diào)整為最佳信道。而本文算法可以降低已使用信道中的發(fā)射功率,繼續(xù)使用新的信道資源,使吞吐量獲得較大提升。

圖8 不同方案的性能對比

4 結(jié) 論

本文主要研究了多無人機(jī)輔助通信場景中,無人機(jī)群作為空中基站為地面設(shè)備提供臨時服務(wù)的動態(tài)頻譜分配問題。為保證用戶通信公平性,在考慮頻譜復(fù)用和共信道干擾的情況下,以最大化地面用戶最小傳輸速率為目標(biāo),提出了一種用戶匹配與頻譜資源聯(lián)合優(yōu)化算法來解決上述混合整數(shù)非線性優(yōu)化問題,通過聚類算法優(yōu)化無人機(jī)與地面用戶的最佳匹配,通過塊坐標(biāo)下降法迭代優(yōu)化子信道分配和功率分配。實驗結(jié)果證明了該算法的有效性,提升了用戶的傳輸速率,保證了用戶的通信公平性。