基于非穩態MAB 的LEO 衛星跳波束時隙分配算法

林敏，闞鵬程，趙柏，程銘，楊綠溪

（1.南京郵電大學通信與信息工程學院，江蘇 南京 210003；2.東南大學信息科學與工程學院，江蘇 南京 211189）

0 引言

針對6G 網絡中“泛在連接”的技術愿景，衛星通信因其通信覆蓋范圍大、不受地理條件限制、組網靈活等優點，被產業界和學術界認為是實現6G技術愿景的一種重要的通信方式[1]。在衛星通信中，低地球軌道（LEO,low earth orbit）衛星通信憑借其傳輸時延短、建設成本相對較低等特點，在近幾年得到了較多的關注和發展[2]。隨著SpaceX、OneWeb等公司低軌衛星星座建設計劃的提出與實施，以及我國低軌衛星互聯網星座的研究和部署，LEO 衛星通信成為衛星通信領域研究的焦點。

跳波束（BH,beaming hopping）技術以業務需求為驅動，通過在同一時刻只激活部分波束覆蓋相應的地面小區，實現系統資源的合理分配和靈活調度，一經提出便得到了廣泛的關注和研究[3-4]。文獻[5-6]綜合考慮了跳波束系統中波束重訪時間和分簇尺寸等因素，以n階差分容量最小化為目標建立相應的優化問題，采用凸優化方法求解得到時隙分配結果，并通過時隙分配進一步緩解了多波束衛星的同頻干擾問題。然而，該方法采用離線靜態資源分配，并不能很好地適應用戶業務需求動態變化的場景。文獻[7]則基于貪婪算法根據用戶業務的需求分布靈活地分配星載資源，但是該算法未考慮服務公平性問題。文獻[8]則在保證每個波束服務公平性的前提下，建立了最小化實時性服務數據包時延以及最大化非實時性服務數據包吞吐量的多目標優化問題，并基于深度強化學習實現了該多目標優化問題的動態求解。該方法雖然能很好地適應用戶業務需求動態變化的場景，但仍然存在學習模型復雜度較高、對計算資源需求較高的問題。

多臂賭博機（MAB,multi-armed bandit）模型作為強化學習中實現探索和利用平衡的一類經典模型，因其具有在未知環境信息條件下也能實現動態優化的特點，在信道選擇、推薦系統等領域得到了廣泛的應用[9-11]。傳統的MAB 模型依賴于平穩的獎勵分布，文獻[12]進一步研究了非穩態MAB 模型并提出了相應的求解算法，并且通過理論和實踐證明，該求解算法能在保證收斂性的情況下很好地應用于獎勵分布未知且隨時間動態變化的場景，同時相比于深度強化學習等人工智能算法，其對計算資源的需求更低。

本文考慮LEO 跳波束衛星系統中地面小區業務需求分布不均以及動態變化的場景，在滿足小區業務需求量的基礎上建立以二階差分容量為目標的最小化問題。由于小區業務需求的時變性，所建立的優化問題難以直接求解，因此本文首先提出波束等級組合方案生成算法以生成所有可能的波束等級組合方案；然后在固定波束等級組合方案的情況下，通過非穩態MAB 模型完成時隙的動態分配；最后以二階差分容量最小化為準則選擇最優波束等級組合方案，從而完成時隙分配與波束等級匹配的聯合優化。由仿真結果可知，與單一等級方案和單一波束方案相比，本文算法能夠進一步降低跳波束系統業務處理的歸一化平均冗余度；同時相比于其余的時隙分配方案，本文算法在總業務需求量變化的同時能達到較高的系統吞吐量，并保持相對較低的波束平均重訪時間。

1 系統模型

如圖1 所示，本文研究LEO 跳波束衛星通信系統的前向鏈路傳輸場景，它由網絡控制中心、配備跳波束控制器的LEO 衛星和地面小區組成，并采用兼容DVB-S2/S2X 協議的跳波束工作方式。綜合考慮LEO 衛星所處的軌道高度以及移動性，本文將LEO 衛星在飛行過程中的總體覆蓋區域劃分為不同的觀察窗口，并且在每個觀察窗口內能夠服務N個地面小區。為了提高系統的頻譜利用效率，LEO 衛星在當前觀察窗口內以全頻率復用的方式同時生成K個點波束服務N個小區。由于星載資源較有限，在跳波束衛星通信系統中通常假設點波束數目遠小于小區數目，即K?N。基于上述的LEO衛星跳波束通信場景，本文將分別詳細介紹小區業務模型、信道模型以及分等級波束模型。

圖1 LEO 跳波束衛星通信系統模型

假設跳波束衛星通信系統的跳波束周期為TW，而衛星在跳波束周期內的每個時隙以數據包的形式向地面小區提供業務數據，且數據包大小均為Xbit/s。同時假設各個小區在t時隙到達的數據包個數為A(t)=[a1(t),a2(t),…,aN(t)]T，其中數據包的到達數量an(t)服從均值為λn(n=1,2,…,N)的泊松分布，則在該觀察窗口中各個小區在一個跳波束周期內的業務需求量為

此外，各小區數據包達到后若不能及時處理則進入緩沖區隊列等待，并將t時隙的緩沖區數據量表示為

在傳統的跳波束衛星通信系統中，其單波束業務數據處理能力較固定，這可能會導致在跳波束時隙分配過程中存在以下2 種固有問題。1)當某些小區的業務需求量較大以至于接近甚至超過了單波束最大業務數據處理能力時，便需要衛星波束長期照射這些小區，這會導致其他小區業務處理不及時、數據包等待時延過長；2) 當某幾個相鄰小區的總業務需求量較低時，如果仍然使用單一等級波束在這些小區間進行跳變，則會占用過多的跳波束時隙，導致其余小區的業務需求量難以得到滿足。針對上述問題，本文采用波束分級方法來進一步提高跳波束LEO 衛星通信系統的資源利用率[13-14]。具體來講，本文考慮采用3 種等級的波束處理小區的業務數據包，如圖2 所示。

圖2 分等級波束示意

本文考慮3 種等級的波束，并分別記為L1、L2和L3。其中，L1等級波束覆蓋1 個小區，L2等級波束覆蓋7 個小區，L3等級波束覆蓋19 個小區。綜合考慮分等級波束增益差異性、衛星信號傳播過程中的自由空間傳輸損耗以及雨衰等因素的影響，衛星下行信道可建模為[14]

圖3 波束3 dB 角度計算示意

根據式(3)可以得出t時隙被Li等級波束k服務的小區n的輸出信干噪比（SINR,signal to interference plus noise ratio）表達式為

其中，PT表示衛星發射功率；σ2=κTnoiseW表示噪聲功率，其中κ、Tnoise和W分別表示玻耳茲曼常數、噪聲溫度和載波帶寬；In(t)表示該小區在當前時隙受到來自其他被照射小區的同頻干擾，其具體表達式為

其中，K為當前工作的波束集合，為波束k'服務的小區集合。進一步地，可以得到t時隙針對被照射小區n的數據包處理能力為

于是小區n經過一個跳波束周期后的總業務數據處理量為

2 問題建立與求解

2.1 問題建立

由小區業務模型和分等級波束模型可知，當部分小區業務數據量需求量較大時，應盡量采用L1等級波束以盡可能滿足其業務需求；當部分小區業務數據量較小時，可考慮優先采用L2等級波束或L3等級波束對這部分小區進行合并，從而將更多的時隙資源分配給其余業務需求量較大的小區。因此，需要通過聯合優化時隙分配與波束等級匹配以盡可能滿足各小區在一個跳波束周期內的業務需求，本文以二階差分容量最小化為目標函數，建立如下形式的聯合優化問題

其中，C1 限定了每個小區的波束等級選取范圍；C2 限定了時隙分配矩陣中每個元素的取值范圍；C3 中表示小區n選擇的Li等級波束所覆蓋的小區數目，因此C3 表示在同一時隙服務地面小區的波束數不能超過多波束衛星的最大波束數目。

由于該問題為非線性整數規劃問題，且由于小區業務需求的動態變化，直接求解該問題將變得十分困難。因此本文首先提出波束等級組合方案生成算法以生成所有可能的波束等級組合方案；然后在固定波束等級組合方案的情況下，通過非穩態MAB模型完成時隙的動態分配；最后根據二階差分容量最小化為準則選擇最優波束等級組合方案，從而完成時隙分配和波束等級匹配的聯合優化。

2.2 波束等級組合方案生成算法

由于跳波束周期通常較短，且LEO 衛星過境時間有限，因此為了避免LEO 衛星波束等級的頻繁切換，本文假設在一個跳波束周期中，每個小區只可以固定選擇一種等級的波束。基于該假設，本文提出一種波束等級組合方案的生成算法以生成各個小區在一個跳波束周期內所有可能的波束等級組合，從而為后續的動態時隙分配提供先驗知識。

首先考慮2 種特殊波束等級組合方案，即單一等級方案和單一波束方案。在這2 種方案中，各個小區在一個跳波束周期內均采用同一種波束等級（L1等級或L3等級），不存在多種波束等級并存的場景，此時，退化為傳統的跳波束時隙分配問題或單波束場景。

然后考慮更一般的情況，即部分小區選擇L2等級波束，而部分小區選擇L1等級波束。此時對波束等級組合方案的分析將變得復雜，因為盡管在一個跳波束周期中各個小區只能選擇一種等級的波束，但是小區對L2等級波束的選擇可能在不同時隙上存在重疊，如圖4 所示。

圖4 混合波束等級示意

從圖4 可知，從單個時隙來看，當1～7 號小區選擇L2等級波束時，其余小區均只可以選擇L1等級波束。從整個跳波束周期來看，12～14 號小區對應的波束等級依然有可能為L2等級波束，因為它們的波束與1～7 號小區對應的波束并不在同一個時隙被照射。因此，該波束等級組合方案依然是可行的。波束等級組合方案生成算法首先要處理混合波束等級在不同時隙下的重疊問題。對此，本文首先提出關鍵小區和有效關鍵小區的概念。

關鍵小區為可能處于波束覆蓋中心且波束等級的選擇將影響周圍小區波束等級選擇的小區。以圖4 為例，當1 號小區在一個跳波束周期內對應的波束等級為L2等級時，可以通過L2等級波束覆蓋方式得出，其周圍2～7 號小區將至少有3 個小區選擇L2等級波束，并且1 號小區可以處在波束覆蓋中心，因此認為1 號小區為關鍵小區。同理，2～7 號小區均可作為關鍵小區。

有效關鍵小區為在一個跳波束周期中能夠處于波束覆蓋中心的關鍵小區。仍然以圖4 為例，盡管1～7 號小區為關鍵小區，但是在圖4 所示的波束等級組合方案中，有效關鍵小區只有1 號小區和4 號小區，因為它們在一個跳波束周期中能夠處于波束覆蓋中心。

通過有效關鍵小區的概念可知，圖4 中重疊問題來自在一個跳波束周期中選擇了2 個關鍵小區，同時也可以借此計算出混合了L2等級波束的所有可能的波束等級組合方案的數量。具體來講，當有效關鍵小區數量為1 時，可能的波束組合方案數量為對應的7 種方案分別是1～7 號小區各自作為選擇L2等級波束的有效關鍵小區，而其余小區選擇L1等級波束。因此通過改變有效關鍵小區的數量，可以得出混合了L2等級波束的所有可能的波束組合方案的數量應為

本文提出的波束等級組合方案生成算法的基本流程如下。首先，確定有效關鍵小區集合C以及集合元素個數M；然后，依次從集合C中選取1 個元素、2 個元素等，直到M個元素全部被取出，并根據每次選取結果確定其余小區的波束等級組合；最后，將所有波束等級組合匯總，得出所有的波束組合方案集合S。需要說明的是，盡管前文在引入關鍵小區時以混合了L2等級波束小區的情況為例，但是通過改變有效關鍵小區集合C中的元素，該算法仍然適用于前文所述的2 種特殊波束組合方案的生成。該算法流程如算法1 所示。

算法1波束等級組合方案生成算法

初始化有效關鍵小區集合C，集合C元素數量M，波束等級組合方案集合S

2.3 動態時隙分配算法

當生成波束等級組合方案集合S后，本節將針對集合S中的每個具體波束等級組合方案s進行跳波束時隙分配。由于小區業務需求量是動態變化的，因此傳統的凸優化求解方法將不再適用。本文提出基于非穩態MAB 模型的求解算法。與傳統MAB 模型類似，在非穩態MAB 模型的動作空間中也包含多個搖臂，而玩家每次只能從動作空間中選擇一個搖臂，并獲得相應的獎勵。因此，在正式求解非穩態MAB 模型之前，應首先定義該模型的動作空間以及獎勵設置，具體如下。

1) 動作空間

當固定一種波束等級組合方案后，動作空間為該方案下所有跳波束圖案構成的集合，每種跳波束圖案對應該動作空間中的一個動作（搖臂）。以圖5 為例，假設本文選擇的波束等級組合方案為1～7 號小區在整個跳波束周期內選擇L2等級波束，而其余小區選擇L1等級波束，同時假設每個時隙可同時服務的最大波束數量K=3，則圖5(a)～圖5(c)均為該波束等級組合方案下可能的3 種跳波束圖案，該波束等級組合方案下所有可能的跳波束圖案數量應為種，即從8～19 號小區中任選2 個L1等級波束小區與1～7 號小區相組合的組合數量。

圖5 動作空間示例

2) 獎勵設置

獎勵設置直接影響非穩態MAB 模型的決策效果。考慮到跳波束時隙分配的基本要求是盡可能滿足每個小區的實際業務需求，因此本文的獎勵設置將圍繞小區實際業務需求量和數據包處理量來展開。具體來講，假設所選定的動作空間中包含Q個搖臂，且在t時隙選擇了第q個搖臂，且該搖臂中包含的小區n的當前緩沖區數據包個數為φn（t），同時該小區新到達數據包個數為an(t)，且在當前搖臂下計算出該小區的數據包處理能力為，則針對該小區的瞬時獎勵的具體表達式為

其中，β為大于 1 的乘性系數；Cn=為該小區在當前動作空間下的參考數據包處理能力。同時，由于單個搖臂通常包含多個小區，因此需要進一步對這些小區的瞬時獎勵求平均以得到該搖臂的歸一化動作獎勵，則第q個搖臂在t時隙的獎勵表達式為

其中，Numq表示該搖臂包含的小區數量。

3) 非穩態MAB 模型的求解

首先，給定動作空間A，該動作空間包含的搖臂數量為QA，則基于前文的獎勵設置，通過折扣上界置信區間（D-UCB,discounted upper confidence bound）算法進行非穩態MAB 決策，從而得出該動作空間下的時隙分配方案[12]。

具體來講，首先，在t時隙計算出該動作空間下第q個搖臂的折扣期望獎勵為

2.4 最優波束等級組合方案選擇

利用D-UCB 算法可得出給定動作空間下的最優時隙分配方案。在這之前，需要選擇最優動作空間以確定最優波束等級組合方案。本節考慮以二階差分容量最小化為準則選擇最優波束等級組合方案。具體流程如下。首先，從波束等級組合方案集合S中選擇一種波束等級組合方案s；然后，基于非穩態MAB 模型完成該方案下的時隙分配；接著，根據時隙分配結果計算方案s下小區業務需求量和實際處理量的二階差分容量，即最后，選擇二階差分容量最小的方案作為最優波束等級組合方案，從而完成時隙分配與波束等級匹配的聯合優化。

考慮到不同波束等級組合方案s下的時隙分配是互相獨立的，因此可以并行執行動態時隙分配。最終，可將本文所提時隙分配和波束等級聯合優化算法流程總結為圖6。

圖6 時隙分配和波束等級匹配聯合優化算法流程

3 仿真結果與分析

3.1 場景和參數設置

本文采用的仿真工具為MATLAB R2022a，并且在仿真時，假設LEO 衛星工作于Ka 頻段，覆蓋區域內包含19 個小區。其余仿真參數如表1 所示。

表1 仿真參數

3.2 仿真結果與分析

在進行仿真結果分析之前，本文先引入以下性能評估指標。

系統吞吐量。每輪實驗中傳輸的數據包總數。

波束重訪時間。跳波束所分配的時隙之間的間隔時間，重訪時間過長將會影響用戶終端的同步[4]。

系統歸一化平均冗余度。當方案s完成時隙分配后，通過計算該方案下實際業務處理量與實際業務需求量的差值并在歸一化后取平均，即可得出該方案下的系統歸一化平均冗余度，該指標可以直觀反映出系統資源的利用情況，其表達式為

1) 混合波束等級方案優勢分析

首先，為了體現混合波束等級帶來的優勢，本文考慮了以下6 種場景。①所有小區需求均較低；②所有小區需求均較高，但都未超過單一等級波束最大處理能力；③大部分小區需求較低，剩余小區需求較高；④大部分小區需求較高，剩余小區需求較低；⑤中心小區需求較低，剩余小區需求較高；⑥中心小區需求較高，剩余小區需求較低。

然后，分別繪制了不同場景下混合波束等級方案、單一波束方案和單一等級（L1）方案下的系統歸一化平均冗余度曲線，如圖7 所示。

圖7 不同場景下系統歸一化平均冗余度對比

由圖7 可知，在各種場景下，混合波束等級方案均保持了較低的系統平均冗余度。在場景①中，由于所有小區業務需求均較低，因此單一波束方案即可滿足要求；在場景②中，由于所有小區需求均較高且都未超過單一等級波束最大處理能力，因此場景②下采用單一等級（L1）波束進行跳變即可達到最低系統歸一化平均冗余度；在其余場景中，由于混合等級波束方案可以通過波束等級匹配來空出時隙以滿足其余業務需求量較大的小區，因此當小區間業務差距較大時，混合波束等級方案依然可以表現出較低的系統歸一化平均冗余度。

2) D-UCB 算法參數分析

對于D-UCB 算法來說，折扣因子γ的選取將直接影響該算法的性能。當γ=1.0時，D-UCB 算法將退化為傳統UCB 算法，并適用于獎勵分布穩定已知的情況；當γ=0時，D-UCB 算法則完全依賴于歷史的獎勵，只根據瞬時獎勵做出決策。因此本文分別考慮了γ=0、γ=0.5以及γ=1.0這3種典型情況下系統吞吐量隨總業務需求量的變化情況，如圖8 所示。

圖8 不同折扣因子下系統吞吐量變化對比

由圖8 可知，當γ=0時，D-UCB 算法在總業務需求量較高時難以保證穩定的性能，且系統吞吐量始終難以滿足業務需求量的要求；當γ=0.5和γ=1.0時，D-UCB 算法下的系統吞吐量均能保持穩定增長，且前者性能相對更高，這也反映出當獎勵非穩定時，通過對歷史獎勵的選擇性利用，可以讓D-UCB 算法保持較好的效果。

3) 不同算法性能對比分析

為了驗證本文所提出的基于非穩態MAB 模型的動態時隙分配算法的性能，本節考慮將該算法與平均時隙分配算法、貪婪時隙分配算法以及ε時隙分配算法進行對比，其中對比算法的具體介紹如下。

平均時隙分配算法。在跳波束周期中的每個時隙依次選擇一個小區進行時隙分配。

貪婪時隙分配算法。在跳波束周期中的每個時隙選擇當前緩沖區數據包數量最大的小區進行時隙分配。

ε時隙分配算法。在跳波束周期中的每個時隙按照1-ε的概率對D-UCB 算法進行時隙分配，否則依舊選擇當前小區進行時隙分配。

最后，本文對比了不同算法下系統吞吐量情況，如圖9 所示。

圖9 不同算法下系統吞吐量對比

由圖9 可知，隨著總業務需求量的增加，平均時隙分配算法不能充分實現波束等級和時隙資源的靈活分配，因此其系統吞吐量始終較低；貪婪時隙分配算法只注重當前時隙的緩沖區數據情況，其決策從整個跳波束周期來看未必最優，因此其吞吐量相對較低；ε時隙分配算法的性能在總業務需求量較低時比較接近本文算法，但由于其決策時仍然存在一定的隨機性，因此該算法仍然存在一定的性能損失；相比這3 種算法，本文算法的系統吞吐量隨著總業務需求量的增加仍然能保持較穩定的增長，同時在總業務需求量較高時也能保持相對較好的性能。

4) 波束重訪時間變化分析

波束重訪時間也是衡量跳波束系統性能的一個重要指標。為了衡量本文算法的波束重訪時間，本節進行了50 次實驗，并統計每次實驗下的波束平均重訪時間，最終結果如圖10 所示。

圖10 波束平均重訪時間變化

由圖10 可知，本文算法的波束平均重訪時間始終保持在300 ms 以內，且大部分情況下可以保持在250 ms 左右，因此能夠基本滿足跳波束系統的同步性能要求[5]。

4 結束語

本文研究了LEO 跳波束衛星系統中的時隙分配和波束等級聯合優化問題，從而在小區業務需求時變性和空間不均勻性的情況下實現衛星資源的靈活分配。相比于已有的跳波束算法，本文借助于非穩態MAB 模型實現了在不依賴于環境信息以及較高計算資源下的動態時隙分配，且通過采用分等級波束技術實現了波束覆蓋范圍與小區業務需求的匹配。仿真結果表明，相比單一波束方案和單一等級波束方案，本文所提混合波束等級方案的系統平均冗余度均不超過20%；當總業務需求量從1 200 Mbit/s 增長到3 600 Mbit/s 時，本文所提動態時隙分配算法依然能保證較高的系統吞吐量，并將波束平均重訪時間控制在300 ms 以內，從而提高了LEO跳波束衛星系統的資源利用率。