基于自適應算子與非支配排序的星地網絡多目標優化方法

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

(1.西安交通大學 信息與通信工程學院,陜西 西安 710049;2.香港理工大學 電子計算學系,香港 999077;3.東南大學 移動通信國家重點實驗室,江蘇 南京 210096)

0 引言

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

近年來,大量研究聚焦在星地網絡資源調度優化問題上。文獻[5]針對非理想動態環境,設計了基于Meta-Critic Learning的算法,提升星地系統資源調度決策的泛化性能。文獻[6]采用啟發式優化算法對多波束低軌衛星的帶寬和功率進行聯合分配。文獻[7]介紹了動態多目標優化的研究現狀以及性能評估的指標,包括進化算法、遺傳算法、粒子群算法、模擬退火算法等。這些算法通過改進適應度函數、引入自適應參數、增加多樣性保持機制等方法來適應動態環境,提高算法的性能。文獻[8]闡述了多種多目標優化評估指標。文獻[9]研究了基于自然梯度的Actor-Critic強化學習方法在低軌衛星網絡服務功能鏈部署問題中的應用。

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

1 星地網絡系統模型

1.1 系統模型

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

圖1 星地網絡系統模型示意圖Fig.1 Illustrative scenario for a satellite-terrestrial system

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

(1)

(2)

式(1)表示在星地網絡系統的一個時隙內,發射端-終端鏈路組g中的每個終端k最多接收來自一個低軌衛星的數據,而式(2)表示,一個時隙內,發射端-終端鏈路組g中的每個LEOn服務不超過一個地面終端。受式(1)和式(2)的限制,星地網絡發射端-終端鏈路g組在t時隙的地面終端k的SINR和每時隙傳輸的數據分別表示為:

(3)

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

(4)

式中:pn為LEOn的發射功率,hk,n,t為在t時隙發射端n與地面終端k之間的信道狀態信息,φ為每個時隙的持續時間,B為低軌衛星的固定帶寬。

1.2 信道模型

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

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

(5)

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

(6)

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

(7)

式中:χ單位為dB/km,表示信號通過云雨的衰減,h為低軌衛星距離海平面的高度。

2 優化問題建模

本文研究了一個星地網絡下行鏈路中的過載場景,即資源有限,T時隙內無法成功服務全部終端以及滿足全部數據傳輸請求。本節針對鏈路組-時隙調度的優化問題,進行建模求解,用以服務盡可能多的地面終端并傳輸盡可能多的數據。二進制變量x=[x1,1,…,xg,t,…,xG,T]T表示鏈路組-時隙的調度,其中:

(8)

在實際場景中,考慮到終端數據請求過于密集導致星地網絡系統過載,系統可能無法滿足每個終端的數據需求Dk,本文設計了一個復合效用函數式(9),并定義當滿足閾值時D′k(D′k≤Dk),系統被認為已服務一個終端k,即fk(x)=1。例如,終端k請求高分辨率數據(如1080P)傳輸,系統無法完全滿足該請求,轉而在T時隙暫時以中低分辨率數據(如360P)服務終端k,達到定義的傳輸閾值。

(9)

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

(10)

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

多目標優化問題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)

通過加權求和的方式可將多目標優化問題轉換為單目標優化問題作為比較基準,因此該單目標優化問題P2表示為:

(18)

式中:w0,w1,…,wk是各優化目標的權重。

式(14)表示在滿足式(1)和式(2)的基礎上,一個時隙最多調度一個鏈路組g。

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

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

3 求解方法

3.1 單目標優化問題P2的最優求解

(19)

(20)

(21)

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

(22)

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

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

圖2 基于權值遍歷的單目標優化結果示意圖Fig.2 Illustrative results for single-objective optimization P2

3.2 多目標優化問題P1的求解方法NSA-MOO

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

3.2.1 快速非支配排序

FNS是多目標優化中應用廣泛的一種策略,用于將解的集合劃分為不同的Pareto等級。FNS策略的基本思想是通過快速排序和二分查找的方式,對解集合進行遞歸劃分,將解集合劃分為不同的Pareto等級,算法的流程如下:

① 初始化:將所有解的支配計數設為0,并創建一個空的前沿列表。

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

③ 對于每個zA,如果其支配計數為0,則將其標記為第一級前沿,并將其添加到前沿列表中。

④ 對于同一級Pareto前沿解,利用擁擠度大小進行排序,擁擠度為當前解與其相鄰解之間的距離。

⑤ 對于每個前沿,重復上述步驟,通過精英保留策略獲得M個精英個體。每次迭代時,前一級前沿中的解被標記為下一級前沿。

3.2.2 自適應算子調整策略

(23)

(24)

(25)

(26)

(27)

式中:γ1>γ2>γ3≥0表示根據不同情況所設置的獎勵,HV(·)為超體積指標(Hypervolume,HV)的計算公式[9],該指標用于衡量解的質量,HV越大,解的質量越好。基于上述獎勵,策略權重可以被自適應更新為:

(28)

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

(29)

3.2.3 NSA-MOO算法流程

NSA-MOO算法的流程圖如圖3所示,隨機產生大小為M的初始種群。如果當前迭代次數d小于最大迭代次數,則依次執行FNS與AOA策略,并進入下一輪迭代。如果當前算法已達最大迭代次數則終止。

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

4 仿真驗證

本節通過單目標優化和多目標優化方法對過載場景下的星地網絡系統資源優化問題進行求解,并分析對比其性能。仿真中,覆蓋區域的衛星數量為2,區域內的終端數量為25,時隙個數為8,時隙持續時間為0.1 s,低軌衛星發射功率為100 W,Ka波段的頻率為30 GHz,信道帶寬為400 MHz,低軌衛星高度為500 km。

圖4為單目標優化結果與多目標優化結果的對比圖。可以看出,成功服務的地面終端數量與星地系統總體傳輸數據量這兩個優化目標相互沖突。如果單目標優化中權重分配不當,可能導致各項指標惡化,如圖4橫坐標區間5～7時傳輸數據量下降,以及橫坐標區間9～12時,系統無法成功服務多于9個用戶。相較之下NSA-MOO在Pareto前沿解的多樣性上明顯優于單目標優化。同時NSA-MOO優化的結果相較于單目標優化來說在成功服務地面終端數量為5～9時,系統的整體傳輸數據量更多。表明了NSA-MOO算法在處理本模型問題時,所得到的優化結果無論是在多樣性還是收斂性上都優于單目標優化處理的結果。

圖4 單目標優化結果與NSA-MOO結果對比Fig.4 Result of single-objective optimization and NSA-MOO

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

圖5 NSA-MOO與NSGA-Ⅱ算法GD指標對比Fig.5 Comparison of GD between NSA-MOO and NSGA-II algorithm

由上述分析可知,本文提出的NSA-MOO算法在處理星地網絡系統資源調度優化問題時相較于單目標優化具有更優的性能,在所得到Pareto前沿解的多樣性和收斂性上都優于單目標優化。而對比NSGA-Ⅱ算法,NSA-MOO算法具有更快的收斂速率。

5 結論

本文研究了6G低軌衛星星地網絡通信系統中的一類資源調度優化問題,用于同時提高終端接入數量和多用戶吞吐量的性能指標。首先,基于加權求和的單目標優化方法對資源調度優化問題進行求解,通過分配不同權重,產生一組解作為性能比較的基準方案之一;隨后,提出基于非支配排序與自適應算子調整的多目標優化算法NSA-MOO得到一組非支配帕累托解并與NSGA-Ⅱ算法進行對比。仿真結果表明,NSA-MOO算法在本文研究的星地網絡場景下相較于單目標優化與NSGA-Ⅱ算法具有一定的優越性。