基于自適應(yīng)算子與非支配排序的星地網(wǎng)絡(luò)多目標(biāo)優(yōu)化方法

李浩輝,周 雨,2,田金今,趙曉輝,雷 磊,3*

(1.西安交通大學(xué) 信息與通信工程學(xué)院,陜西 西安 710049;2.香港理工大學(xué) 電子計(jì)算學(xué)系,香港 999077;3.東南大學(xué) 移動(dòng)通信國(guó)家重點(diǎn)實(shí)驗(yàn)室,江蘇 南京 210096)

0 引言

隨著低軌 (Low Earth Orbit,LEO) 衛(wèi)星通信技術(shù)的不斷發(fā)展,低軌衛(wèi)星可在大尺度覆蓋空間中為用戶提供高速、穩(wěn)定、低延遲的通信服務(wù),從而滿足用戶對(duì)于星地高速通信的需求?；诖?低軌衛(wèi)星通信在5G和6G網(wǎng)絡(luò)的應(yīng)用場(chǎng)景不斷拓展[1]。在大規(guī)模星地網(wǎng)絡(luò)優(yōu)化運(yùn)營(yíng)中,待服務(wù)用戶數(shù)量的激增以及差異化的用戶數(shù)據(jù)服務(wù)請(qǐng)求可能導(dǎo)致星地網(wǎng)絡(luò)出現(xiàn)負(fù)載不均、超載和擁擠等問(wèn)題[2]。為了提高網(wǎng)絡(luò)性能和用戶體驗(yàn),對(duì)低軌衛(wèi)星和地面系統(tǒng)多維資源進(jìn)行聯(lián)合優(yōu)化調(diào)度被認(rèn)為是具有成本效益的解決方案之一[3]。傳統(tǒng)的低軌衛(wèi)星網(wǎng)絡(luò)資源管理方法通常采用單目標(biāo)優(yōu)化策略,即只考慮單一指標(biāo)(如網(wǎng)絡(luò)吞吐量、延遲等)的優(yōu)化;而實(shí)際中,多個(gè)指標(biāo)優(yōu)化過(guò)程中的資源分配策略和資源競(jìng)爭(zhēng)程度,可影響系統(tǒng)整體性能[4]。因此,研究基于多目標(biāo)優(yōu)化的6G低軌衛(wèi)星網(wǎng)絡(luò)資源調(diào)度管理方法對(duì)提升星地網(wǎng)絡(luò)整體性能指標(biāo)有著積極的意義。

近年來(lái),大量研究聚焦在星地網(wǎng)絡(luò)資源調(diào)度優(yōu)化問(wèn)題上。文獻(xiàn)[5]針對(duì)非理想動(dòng)態(tài)環(huán)境,設(shè)計(jì)了基于Meta-Critic Learning的算法,提升星地系統(tǒng)資源調(diào)度決策的泛化性能。文獻(xiàn)[6]采用啟發(fā)式優(yōu)化算法對(duì)多波束低軌衛(wèi)星的帶寬和功率進(jìn)行聯(lián)合分配。文獻(xiàn)[7]介紹了動(dòng)態(tài)多目標(biāo)優(yōu)化的研究現(xiàn)狀以及性能評(píng)估的指標(biāo),包括進(jìn)化算法、遺傳算法、粒子群算法、模擬退火算法等。這些算法通過(guò)改進(jìn)適應(yīng)度函數(shù)、引入自適應(yīng)參數(shù)、增加多樣性保持機(jī)制等方法來(lái)適應(yīng)動(dòng)態(tài)環(huán)境,提高算法的性能。文獻(xiàn)[8]闡述了多種多目標(biāo)優(yōu)化評(píng)估指標(biāo)。文獻(xiàn)[9]研究了基于自然梯度的Actor-Critic強(qiáng)化學(xué)習(xí)方法在低軌衛(wèi)星網(wǎng)絡(luò)服務(wù)功能鏈部署問(wèn)題中的應(yīng)用。

星地融合網(wǎng)絡(luò)的資源調(diào)度優(yōu)化問(wèn)題本質(zhì)上是一類多約束和多維度的大規(guī)模復(fù)雜優(yōu)化決策問(wèn)題。在實(shí)際運(yùn)營(yíng)中,通常需要同時(shí)優(yōu)化多個(gè)性能指標(biāo)如吞吐量、接入終端數(shù)量等,而多個(gè)目標(biāo)在優(yōu)化過(guò)程中,往往相互沖突。如何在多個(gè)指標(biāo)間達(dá)到較好的折中,對(duì)星地網(wǎng)絡(luò)資源高效、高質(zhì)量的調(diào)度優(yōu)化有著重要意義。本文針對(duì)星地網(wǎng)絡(luò)如何同時(shí)提高終端接入數(shù)量與提高多用戶吞吐的優(yōu)化問(wèn)題,進(jìn)行基于單目標(biāo)和多目標(biāo)優(yōu)化的建模。首先,產(chǎn)生不同權(quán)重并對(duì)單目標(biāo)優(yōu)化問(wèn)題進(jìn)行最優(yōu)求解,產(chǎn)生多組優(yōu)化結(jié)果作為性能比較的基準(zhǔn)方案之一;隨后,提出基于快速非支配排序與自適應(yīng)算子調(diào)整的高效多目標(biāo)優(yōu)化(Non-Dominated Sorting and Adaptive Operator Adjustment Based Multi-Objective Optimization,NSA-MOO)算法,同時(shí)對(duì)多個(gè)目標(biāo)函數(shù)進(jìn)行優(yōu)化。仿真結(jié)果表明,所提算法與加權(quán)單目標(biāo)優(yōu)化和傳統(tǒng)多目標(biāo)優(yōu)化算法如非支配排序遺傳(Non-dominated Sorting Genetic Algorithm-II,NSGA-II)算法相比,可有效提升整體優(yōu)化性能。

1 星地網(wǎng)絡(luò)系統(tǒng)模型

1.1 系統(tǒng)模型

本文考慮星地網(wǎng)絡(luò)下行鏈路場(chǎng)景,如圖1所示。該系統(tǒng)模型由多顆低軌衛(wèi)星和一組地面終端構(gòu)成。由于地面終端請(qǐng)求激增和系統(tǒng)通信資源有限,該系統(tǒng)模型的主要優(yōu)化目標(biāo)是利用有限的資源盡可能服務(wù)更多的地面終端和滿足差異化的終端數(shù)據(jù)請(qǐng)求[10]。地面終端的集合表示為K={1,…,k,…,K},低軌衛(wèi)星發(fā)射端的集合表示為N={1,…,n,…,N}。由于低軌衛(wèi)星超高移動(dòng)性帶來(lái)的有限服務(wù)時(shí)間的影響,場(chǎng)景中假設(shè)星地間的傳輸任務(wù)應(yīng)在T個(gè)時(shí)隙內(nèi)完成,即T={1,…,t,…,T}。在數(shù)據(jù)傳輸中,每個(gè)發(fā)射端n以單播模式服務(wù)地面終端k,即一個(gè)發(fā)射端-地面終端鏈路(n,k)。在一個(gè)時(shí)隙內(nèi),可存在多個(gè)發(fā)射端-地面終端鏈路同時(shí)傳輸數(shù)據(jù),形成一個(gè)鏈路組。

圖1 星地網(wǎng)絡(luò)系統(tǒng)模型示意圖Fig.1 Illustrative scenario for a satellite-terrestrial system

定義G={1,…,g,…,G}表示所有可能的發(fā)射端-地面終端鏈路組的集合,并引入二進(jìn)制參數(shù)αk,n,g來(lái)表示一個(gè)鏈路組中被激活的鏈路,其中αk,n,g=1表示發(fā)射端-終端鏈路(n,k)在鏈路組g中被激活,αk,n,g=0則表示未被激活。本文通過(guò)枚舉所有可能的鏈路組,并根據(jù)單播約束定義二進(jìn)制參數(shù)αk,n,g:

(1)

(2)

式(1)表示在星地網(wǎng)絡(luò)系統(tǒng)的一個(gè)時(shí)隙內(nèi),發(fā)射端-終端鏈路組g中的每個(gè)終端k最多接收來(lái)自一個(gè)低軌衛(wèi)星的數(shù)據(jù),而式(2)表示,一個(gè)時(shí)隙內(nèi),發(fā)射端-終端鏈路組g中的每個(gè)LEOn服務(wù)不超過(guò)一個(gè)地面終端。受式(1)和式(2)的限制,星地網(wǎng)絡(luò)發(fā)射端-終端鏈路g組在t時(shí)隙的地面終端k的SINR和每時(shí)隙傳輸?shù)臄?shù)據(jù)分別表示為:

(3)

Rk,g,t=φBlb(1+γk,g,t),

(4)

式中:pn為L(zhǎng)EOn的發(fā)射功率,hk,n,t為在t時(shí)隙發(fā)射端n與地面終端k之間的信道狀態(tài)信息,φ為每個(gè)時(shí)隙的持續(xù)時(shí)間,B為低軌衛(wèi)星的固定帶寬。

1.2 信道模型

在星地網(wǎng)絡(luò)下行鏈路系統(tǒng)模型中,假設(shè)由低軌衛(wèi)星高速運(yùn)動(dòng)引起的多普勒頻移可以在已知地面終端位置、衛(wèi)星軌道和衛(wèi)星速度的情況下得到有效的預(yù)(后)補(bǔ)償[11-12]。在時(shí)隙t中,地面終端k和發(fā)射端n之間的信道狀態(tài)可以建模為:

hk,n,t=GT·GC·GR,

(5)

式中:GT和GR分別為發(fā)射天線和接收天線的增益,GC表示信道損耗,假設(shè)單天線地面終端具有相同的接收天線增益GR。對(duì)于低軌衛(wèi)星到地面終端的信道,GC建模為萊斯衰落信道,包括自由空間路徑損耗、俯仰角衰落、大氣衰落、萊斯小尺度衰落[13],可表示為:

(6)

式中:c為光速,d為低軌衛(wèi)星與地面終端之間的傳播距離,fc為低軌衛(wèi)星的載波頻率,GH為俯仰角衰落,φ為萊斯衰落因子,A(d)為大氣損失,表示為:

(7)

式中:χ單位為dB/km,表示信號(hào)通過(guò)云雨的衰減,h為低軌衛(wèi)星距離海平面的高度。

2 優(yōu)化問(wèn)題建模

本文研究了一個(gè)星地網(wǎng)絡(luò)下行鏈路中的過(guò)載場(chǎng)景,即資源有限,T時(shí)隙內(nèi)無(wú)法成功服務(wù)全部終端以及滿足全部數(shù)據(jù)傳輸請(qǐng)求。本節(jié)針對(duì)鏈路組-時(shí)隙調(diào)度的優(yōu)化問(wèn)題,進(jìn)行建模求解,用以服務(wù)盡可能多的地面終端并傳輸盡可能多的數(shù)據(jù)。二進(jìn)制變量x=[x1,1,…,xg,t,…,xG,T]T表示鏈路組-時(shí)隙的調(diào)度,其中:

(8)

在實(shí)際場(chǎng)景中,考慮到終端數(shù)據(jù)請(qǐng)求過(guò)于密集導(dǎo)致星地網(wǎng)絡(luò)系統(tǒng)過(guò)載,系統(tǒng)可能無(wú)法滿足每個(gè)終端的數(shù)據(jù)需求Dk,本文設(shè)計(jì)了一個(gè)復(fù)合效用函數(shù)式(9),并定義當(dāng)滿足閾值時(shí)D′k(D′k≤Dk),系統(tǒng)被認(rèn)為已服務(wù)一個(gè)終端k,即fk(x)=1。例如,終端k請(qǐng)求高分辨率數(shù)據(jù)(如1080P)傳輸,系統(tǒng)無(wú)法完全滿足該請(qǐng)求,轉(zhuǎn)而在T時(shí)隙暫時(shí)以中低分辨率數(shù)據(jù)(如360P)服務(wù)終端k,達(dá)到定義的傳輸閾值。

(9)

式中:I(ο)是一個(gè)指示函數(shù),表示為:

(10)

通過(guò)引入輔助變量y=[y1,…,yk,…,yK]T和線性約束式(15),將非線性函數(shù)fk(x)轉(zhuǎn)換為線性函數(shù),其中yk=fk(x)。

多目標(biāo)優(yōu)化問(wèn)題P1可以表示為:

(11)

(12)

minf1(x,y),f2(x,y)

?k∈K,g∈G,t∈T,

(13)

(14)

(15)

xg,t∈{0,1},?g∈G,t∈T,

(16)

yk∈{0,1},?k∈K。

(17)

通過(guò)加權(quán)求和的方式可將多目標(biāo)優(yōu)化問(wèn)題轉(zhuǎn)換為單目標(biāo)優(yōu)化問(wèn)題作為比較基準(zhǔn),因此該單目標(biāo)優(yōu)化問(wèn)題P2表示為:

(18)

式中:w0,w1,…,wk是各優(yōu)化目標(biāo)的權(quán)重。

式(14)表示在滿足式(1)和式(2)的基礎(chǔ)上,一個(gè)時(shí)隙最多調(diào)度一個(gè)鏈路組g。

式(15)中,如果地面終端k被成功服務(wù),即yk=1,終端k接收到的數(shù)據(jù)量應(yīng)該大于成功服務(wù)的最小要求D′k,與式(8)的效果一致。

式(16)～(17)為變量xg,t,yk的二進(jìn)制約束。

3 求解方法

3.1 單目標(biāo)優(yōu)化問(wèn)題P2的最優(yōu)求解

(19)

(20)

(21)

式中:E為全1矩陣,并且

(22)

P2屬于0-1型二次整數(shù)規(guī)劃(Quadratic Integer Programming,QIP)問(wèn)題。因P2的對(duì)稱矩陣半正定,所以其松弛問(wèn)題為凸。

基于上述結(jié)論,單目標(biāo)優(yōu)化問(wèn)題P2的全局最優(yōu)解可以通過(guò)分支定界法(Branch and Bound)進(jìn)行求解[15],因其松弛問(wèn)題為凸,固每一輪可求解一個(gè)凸優(yōu)化問(wèn)題。如圖2所示,通過(guò)盡可能遍歷權(quán)值w0,w1,…,wk,可獲得不同的優(yōu)化結(jié)果即圖中的圓形點(diǎn)與叉形點(diǎn),最終,連續(xù)的圓形點(diǎn)形成一條近似的邊界可作為基于加權(quán)單目標(biāo)優(yōu)化的一組最優(yōu)解,作為性能基準(zhǔn)之一,可與多目標(biāo)優(yōu)化的結(jié)果進(jìn)行后續(xù)比較。

圖2 基于權(quán)值遍歷的單目標(biāo)優(yōu)化結(jié)果示意圖Fig.2 Illustrative results for single-objective optimization P2

3.2 多目標(biāo)優(yōu)化問(wèn)題P1的求解方法NSA-MOO

對(duì)于P1的求解,實(shí)驗(yàn)中發(fā)現(xiàn)傳統(tǒng)的多目標(biāo)優(yōu)化算法如遺傳算法易陷入局部最優(yōu)和偏離Pareto前沿[16]。針對(duì)上述問(wèn)題,采用NSA-MOO算法對(duì)多目標(biāo)優(yōu)化問(wèn)題進(jìn)行求解。相較于遺傳算法,NSA-MOO針對(duì)問(wèn)題特性,設(shè)計(jì)了快速非支配排序(Fast Non-dominated Sorting,FNS)以及自適應(yīng)算子調(diào)整(Adaptive Operator Adjustment,AOA)的策略,以保證所得到的Pareto前沿解的多樣性和有效性[17]。

3.2.1 快速非支配排序

FNS是多目標(biāo)優(yōu)化中應(yīng)用廣泛的一種策略,用于將解的集合劃分為不同的Pareto等級(jí)。FNS策略的基本思想是通過(guò)快速排序和二分查找的方式,對(duì)解集合進(jìn)行遞歸劃分,將解集合劃分為不同的Pareto等級(jí),算法的流程如下:

① 初始化:將所有解的支配計(jì)數(shù)設(shè)為0,并創(chuàng)建一個(gè)空的前沿列表。

② 對(duì)于每個(gè)解zA={f1(x,y),f2(x,y)},遍歷整個(gè)解集,比較zA與zB的支配關(guān)系:如果zA支配zB,則將zB的支配計(jì)數(shù)加1;如果zB支配zA,則將zA添加到zB的支配列表中。

③ 對(duì)于每個(gè)zA,如果其支配計(jì)數(shù)為0,則將其標(biāo)記為第一級(jí)前沿,并將其添加到前沿列表中。

④ 對(duì)于同一級(jí)Pareto前沿解,利用擁擠度大小進(jìn)行排序,擁擠度為當(dāng)前解與其相鄰解之間的距離。

⑤ 對(duì)于每個(gè)前沿,重復(fù)上述步驟,通過(guò)精英保留策略獲得M個(gè)精英個(gè)體。每次迭代時(shí),前一級(jí)前沿中的解被標(biāo)記為下一級(jí)前沿。

3.2.2 自適應(yīng)算子調(diào)整策略

(23)

(24)

(25)

(26)

(27)

式中:γ1>γ2>γ3≥0表示根據(jù)不同情況所設(shè)置的獎(jiǎng)勵(lì),HV(·)為超體積指標(biāo)(Hypervolume,HV)的計(jì)算公式[9],該指標(biāo)用于衡量解的質(zhì)量,HV越大,解的質(zhì)量越好?；谏鲜霆?jiǎng)勵(lì),策略權(quán)重可以被自適應(yīng)更新為:

(28)

式中:ξ∈(0,1)是一個(gè)更新系數(shù)。

(29)

3.2.3 NSA-MOO算法流程

NSA-MOO算法的流程圖如圖3所示,隨機(jī)產(chǎn)生大小為M的初始種群。如果當(dāng)前迭代次數(shù)d小于最大迭代次數(shù),則依次執(zhí)行FNS與AOA策略,并進(jìn)入下一輪迭代。如果當(dāng)前算法已達(dá)最大迭代次數(shù)則終止。

圖3 NSA-MOO算法流程圖Fig.3 Flowchart of NSA-MOO algorithm

4 仿真驗(yàn)證

本節(jié)通過(guò)單目標(biāo)優(yōu)化和多目標(biāo)優(yōu)化方法對(duì)過(guò)載場(chǎng)景下的星地網(wǎng)絡(luò)系統(tǒng)資源優(yōu)化問(wèn)題進(jìn)行求解,并分析對(duì)比其性能。仿真中,覆蓋區(qū)域的衛(wèi)星數(shù)量為2,區(qū)域內(nèi)的終端數(shù)量為25,時(shí)隙個(gè)數(shù)為8,時(shí)隙持續(xù)時(shí)間為0.1 s,低軌衛(wèi)星發(fā)射功率為100 W,Ka波段的頻率為30 GHz,信道帶寬為400 MHz,低軌衛(wèi)星高度為500 km。

圖4為單目標(biāo)優(yōu)化結(jié)果與多目標(biāo)優(yōu)化結(jié)果的對(duì)比圖。可以看出,成功服務(wù)的地面終端數(shù)量與星地系統(tǒng)總體傳輸數(shù)據(jù)量這兩個(gè)優(yōu)化目標(biāo)相互沖突。如果單目標(biāo)優(yōu)化中權(quán)重分配不當(dāng),可能導(dǎo)致各項(xiàng)指標(biāo)惡化,如圖4橫坐標(biāo)區(qū)間5～7時(shí)傳輸數(shù)據(jù)量下降,以及橫坐標(biāo)區(qū)間9～12時(shí),系統(tǒng)無(wú)法成功服務(wù)多于9個(gè)用戶。相較之下NSA-MOO在Pareto前沿解的多樣性上明顯優(yōu)于單目標(biāo)優(yōu)化。同時(shí)NSA-MOO優(yōu)化的結(jié)果相較于單目標(biāo)優(yōu)化來(lái)說(shuō)在成功服務(wù)地面終端數(shù)量為5～9時(shí),系統(tǒng)的整體傳輸數(shù)據(jù)量更多。表明了NSA-MOO算法在處理本模型問(wèn)題時(shí),所得到的優(yōu)化結(jié)果無(wú)論是在多樣性還是收斂性上都優(yōu)于單目標(biāo)優(yōu)化處理的結(jié)果。

圖4 單目標(biāo)優(yōu)化結(jié)果與NSA-MOO結(jié)果對(duì)比Fig.4 Result of single-objective optimization and NSA-MOO

圖5為NSA-MOO算法與NSGA-Ⅱ多目標(biāo)優(yōu)化算法在世代距離(Generational Distance,GD)指標(biāo)的比較圖。NSA-MOO算法相較于NSGA-Ⅱ算法引進(jìn)了AOA機(jī)制以獲得更快的收斂速率以及更加寬廣的多樣性。在評(píng)估達(dá)到7 000多次時(shí)NSA-MOO算法的GD指標(biāo)基本達(dá)到收斂,而NSGA-Ⅱ算法在評(píng)估次數(shù)達(dá)到10 000時(shí),GD指標(biāo)才接近于收斂。圖5表明NSA-MOO算法在此模型上的性能在整體上收斂速率優(yōu)于NSGA-Ⅱ。

圖5 NSA-MOO與NSGA-Ⅱ算法GD指標(biāo)對(duì)比Fig.5 Comparison of GD between NSA-MOO and NSGA-II algorithm

由上述分析可知,本文提出的NSA-MOO算法在處理星地網(wǎng)絡(luò)系統(tǒng)資源調(diào)度優(yōu)化問(wèn)題時(shí)相較于單目標(biāo)優(yōu)化具有更優(yōu)的性能,在所得到Pareto前沿解的多樣性和收斂性上都優(yōu)于單目標(biāo)優(yōu)化。而對(duì)比NSGA-Ⅱ算法,NSA-MOO算法具有更快的收斂速率。

5 結(jié)論

本文研究了6G低軌衛(wèi)星星地網(wǎng)絡(luò)通信系統(tǒng)中的一類資源調(diào)度優(yōu)化問(wèn)題,用于同時(shí)提高終端接入數(shù)量和多用戶吞吐量的性能指標(biāo)。首先,基于加權(quán)求和的單目標(biāo)優(yōu)化方法對(duì)資源調(diào)度優(yōu)化問(wèn)題進(jìn)行求解,通過(guò)分配不同權(quán)重,產(chǎn)生一組解作為性能比較的基準(zhǔn)方案之一;隨后,提出基于非支配排序與自適應(yīng)算子調(diào)整的多目標(biāo)優(yōu)化算法NSA-MOO得到一組非支配帕累托解并與NSGA-Ⅱ算法進(jìn)行對(duì)比。仿真結(jié)果表明,NSA-MOO算法在本文研究的星地網(wǎng)絡(luò)場(chǎng)景下相較于單目標(biāo)優(yōu)化與NSGA-Ⅱ算法具有一定的優(yōu)越性。