基于量子粒子群優化的多波束衛星聯合資源分配算法

摘 要：當使用元啟發式算法求解多波束衛星聯合資源分配問題時，時延約束和容量約束會導致計算復雜度增大，且算法難以收斂。對此，通過在目標函數中引入懲罰機制，在無效解的目標函數值加入了懲罰值，使得算法的優化解自適應地滿足這兩個約束。在此基礎上，提出了基于量子粒子群優化的聯合資源分配算法。仿真結果表明，懲罰策略的引入解決了應用元啟發式算法時，難以處理時延約束和容量約束的問題，而帶有懲罰機制的量子粒子群算法在分配公平性指數、總系統容量上均優于已有聯合分配算法。

關鍵詞：多波束衛星；聯合資源分配；量子粒子群優化；懲罰策略；約束處理

中圖分類號：TN929.5 文獻標志碼：A

文章編號：1001－3695（2023）03－037－0868－06

doi：10.19734/j.issn.1001-3695.2022.06.0384

Joint resource allocation algorithm for multi-beam satellite based on

quantum-behaved particle swarm optimization

Gao Wei，Wang Lei，Qu Lianzheng

（College of Information amp; Communication，National University of Defense Technology，Wuhan 430014，China）

Abstract：When the meta-heuristic algorithm solves the joint resource allocation problem of multi-beam satellites，the computational complexity increases and the algorithm is difficult to converge due to the time delay constraint and capacity constraint.This paper introduced a penalty mechanism in the objective function，and added a penalty value to the objective function of the invalid solution，so that the optimized solution adaptively satisfied these two constraints.Based on this，this paper proposed a joint resource allocation algorithm based on quantum-behaved particle swarm optimization.Simulation results show that the introduction of the penalty strategy solves the problem of difficulty in handling the delay constraint and capacity constraint when applying the meta-heuristic algorithm.The quantum-behaved particle swarm optimization algorithm with penalty mechanism outperforms the existing joint allocation algorithm in terms of allocation fairness index and total system capacity.

Key words：multibeam satellite；joint resource allocation；quantum-behaved particle swarm optimization；penalty mechanism；constraint handling0 引言

隨著通信業務需求的迅猛增長，高通量衛星系統的資源分配問題成為當今空間通信技術領域的一大研究熱點。由于衛星天線的增益受到波束寬度的限制，衛星信號在接收端的信號較弱，例如對地球同步軌道衛星來說，提供全球覆蓋的天線增益不超過20 dB［1］。為了解決這一問題，多波束技術在現代衛星通信系統中得到了廣泛應用，該技術通過波束間的頻率復用獲得較高的頻率利用率，較高的發射端EIRP和接收端G/T值，但也會帶來波束間的干擾，因此多波束體制下的資源優化分配方法成為了減小干擾的途徑［2］。傳統的帶寬和功率分配采取固定平均分配策略，導致每個波束提供的容量相等，不符合各波束需求差異性較大的實際情況，資源利用率也較低［3］。由于衛星平臺的通信資源有限且昂貴，如何根據不同波束的通信需求和信道條件，優化衛星通信資源的分配，以滿足通信需求、提高資源利用率、降低波間干擾就顯得尤為重要。

目前學術界在單一功率/帶寬資源優化分配方面研究較多。文獻［4］研究了多波束衛星功率分配問題，考慮了時延約束和信道系數，以最大化總容量和分配公平性作為目標函數，采用拉格朗日乘子算法進行求解，但沒有考慮波間干擾。文獻［5］研究了多波束寬帶衛星的功率優化分配算法，采用拉格朗日對偶和次梯度法進行求解，既兼顧了分配公平性和最大化系統容量，又考慮了波束的服務質量（QoS）需求，但同樣沒有考慮相鄰波束干擾。文獻［6］在帶寬固定平均分配基礎上，提出了基于用戶需求度的max-min動態分配算法，優化了多波束衛星的載波功率分配。文獻［7，8］分別在固定平均功率（帶寬）條件下，基于拉格朗日對偶和次梯度法提出了考慮波束間干擾的帶寬（功率）資源優化分配算法。文獻［9］以最小化分配功率之和為目標，研究了多波束衛星的資源分配問題，并使用粒子群算法進行求解，但沒有考慮帶寬的優化分配。文獻［10］研究了考慮波間干擾的多波束衛星功率分配問題，并提出了基于改進遺傳算法的功率分配優化算法。

功率帶寬聯合優化分配方面，文獻［11］針對多波束GEO衛星的功率和載波聯合分配問題，將其分解為功率分配和載波分配兩個子問題，并使用逐次凸逼近法進行求解。文獻［12］采用波間干擾矩陣表示波束間的干擾情況，簡化了鏈路容量的計算，并使用拉格朗日對偶和次梯度法對帶寬功率聯合分配進行求解。但算法在最大化系統總容量的同時，降低了容量分配的公平性。文獻［13～15］研究了考慮波間干擾、時延和信道條件差異的帶寬功率聯合分配，并使用拉格朗日對偶和次梯度法求解。

現有研究的特點為：a）對聯合資源分配算法的研究較少，現有的幾種聯合分配算法不能很好地兼顧有效性和公平性；b）不同的多波束衛星資源分配模型所考慮的因素相差較大，例如文獻［4，5，7］沒有考慮波間干擾，文獻［5～9，11～13］沒有考慮時延約束等；c）對拉格朗日對偶和次梯度法等凸優化方法的研究較多，雖然求解速度快，但所得解一般是局部最優解，且不便于擴展和應對復雜約束。采用元啟發式算法（meta-heuristic algorithm）進行帶寬功率聯合優化分配時，在每一次迭代都需要處理不滿足約束的無效解，導致計算復雜度過高、算法難以收斂，因此對于應用元啟發式算法時如何進行約束處理的研究較少。針對現有研究的不足，本文主要做了以下工作：

a）系統總結了問題模型的表示。對基于香農公式的多波束衛星資源分配問題模型做了系統的梳理，構建了考慮波間干擾、雨衰、業務延遲、信道條件差異等因素的多波束衛星聯合資源分配模型。

b）提出了帶懲罰策略的量子粒子群算法。設計了粒子的實數編碼方案，采取比例縮放策略來處理模型的資源總量約束。設計了加入懲罰策略的目標函數，將約束對優化解的限制由種群進化環節轉移到種群評價環節，降低了算法的計算復雜度，使優化解自適應地滿足最大容量約束和時延約束，提升了算法效率和優化解質量。

c）通過實例仿真結果驗證了本文算法的性能和懲罰策略的有效性。結果表明，在相同算例下，本文方案和目前幾種代表性算法在公平性指數、系統總容量指標上均取得了改善。

1 系統模型

1.1 多波束衛星通信系統模型

本文考慮由Ka頻段GEO衛星平臺為主體構成的多波束衛星通信系統模型，配備多個固定點波束，張角為0.8°［2］。系統模型如圖1所示。

系統模型的基本假設為：a）一個點波束只有一個載波，不考慮波束內載波間的功率或帶寬分配；b）某個時刻波束內用戶的通信需求合并為該波束的總需求；c）模型主要表示某一時刻或某一短周期內面向各波束需求進行資源分配的問題，實時資源分配問題不在本文研究范圍之內。

1.3 考慮業務時延和波間干擾的容量計算

在實際應用中，許多實時性較強的業務，例如音頻通話、視頻會議對系統的延遲性能十分敏感，因此必須在系統的資源分配問題中考慮到這一因素。設ei表示波束i的通信鏈路的包錯誤率（packet error rate，PER），tdi表示波束的平均穩定時延，則滿足如下關系［4］：

2.2 粒子編碼及轉換方法

粒子采用實數編碼，以粒子在解空間的位置向量對應資源分配向量，以資源分配向量所計算的目標函數值對應粒子的適應度值。設種群數量為N，粒子維度為D，并令D=2M（M為波束個數），則粒子個體和粒子種群可以表示為

2.4 算法流程及復雜度分析

本文提出的帶懲罰策略的量子粒子群優化算法（quantum-behaved particle swarm optimization with penalty strategy，QPSOPS）的步驟如下：

a）初始化。設置算法參數，按照式（32）～（34）生成粒子初始種群。

b）粒子向分配向量轉換。按照式（35）～（39）進行粒子種群向資源分配矩陣的轉換。

c）計算適應度值。根據資源分配矩陣，按照式（40）～（42）計算每個資源分配向量的FIWP值，并作為粒子的適應度值。

d）粒子種群進化。按照式（25）～（27）更新粒子的個體最優位置、全局最優位置和吸引子位置，按照式（29）～（31）實現粒子種群的進化迭代。

e）判斷終止條件。若滿足則終止算法，輸出最優的粒子位置向量；若不滿足終止條件則重復進行步驟b）～e），直至滿足條件。本文設置最大迭代次數為終止條件。

f）計算優化結果。根據最優粒子位置向量，計算對應的帶寬、功率分配向量，并以此計算容量分配結果和公平性指數、系統總容量等指標。

可見，本文算法的計算復雜度是線性的，整體計算復雜度較低。

3 仿真分析

3.1 仿真參數設置

仿真分析采用的系統參數主要參考文獻［14］，如表2所示。為了驗證本文算法的性能，使用以下算法進行對比：

a）固定平均分配算法（average bandwidth and average power allocation algorithm，ABAP）。

b）凸優化典型算法。考慮干擾和時延的功率帶寬聯合分配算法（optimal power and bandwidth co-allocation with interfe-rence and delay constraint，OPBID），由文獻［14］提出的基于拉格朗日對偶和次梯度法的功率帶寬聯合優化分配算法。

c）遺傳算法（genetic algorithm，GA）。由文獻［10］提出的功率優化分配算法，在本文中使用時帶寬可采用按需求比例分配或平均分配策略。

d）QPSOPS算法。本文提出的帶懲罰策略的量子粒子群優化算法。仿真所使用的算法參數如表3所示。

3.2 算法綜合性能對比

為了全面分析本文算法在FI、TSC指標上的綜合性能，使用4種算法及其改進型進行測試對比，測試算法的名稱及采取的策略如表4所示（表中“比例”指按照波束需求比例分配相應資源）。為了方便直觀地比較，縱軸采用1/FI作為公平性指數，橫軸采用系統總容量TSC，分布點越靠近右上方則綜合性能越好，結果如圖3所示（圖中三角形、正方形、圓形符號分別表示采用AB、PB和OB策略的算法，五角星符號表示本文提出的QPSOPS算法）。圖3給出了12種不同算法在（1/FI）、TSC兩個指標上的分布情況。

由圖3可知：a）比較12種算法，采用比例帶寬分配和優化帶寬分配的算法在公平性指數（1/FI）上要全部優于采用平均帶寬分配的算法，比較采用平均帶寬分配的4種算法，只有GA（ABOP）算法能夠通過優化功率分配來改善TSC，但也無法改善（1/FI），以上說明帶寬的優化分配在公平性指數（1/FI）上起著主要作用；b）比較PBAP、PBPP 與QPSOPS（PBOP），可以看出通過將功率分配逐步由AP調整為PP和OP，算法的綜合性能也逐步加強，說明合適的功率優化分配模式能夠較好地改善公平性指數（1/FI），同時提升TSC；c）公平性指數性能最佳的算法有QPSOPS（OBOP）、QPSOPS（OBPP）、OPBID以及GA（PBOP）算法，其中QPSOPS（OBPP）與OPBID兩者性能基本相當，而QPSOPS（OBOP）算法在以公平性指數為目標函數時，仍能在兩項指標上都達到最優，說明QPSOPS（OBOP）算法具備最佳的綜合性能。

3.3 算法公平性指數性能對比

根據3.2節分析，本節使用基礎固定分配算法ABAP，以及綜合表現最好的3種算法GA（PBOP）、OPBID（OBOP）以及QPSOPS（OBOP）進行帶寬和功率資源的優化分配，并比較分析算法在公平性指數上的性能差異。對迭代運行結果取平均值，數值結果如表5所示，各點波束的FI和TSC的分布結果如圖4、5所示。

本節中，在不引起歧義的情況下對算法取簡稱，不再標注算法的策略。圖4給出了不同算法對各點波束的公平性指數結果，各波束的FI值越小、分布越平穩，且系統總的FI值越小，則公平性越好。由圖4結合表5可以看出：a）ABAP由于固定平均分配，不考慮各波束需求和信道條件的差異，所以系統FI值最高，公平性最低；b）GA相比ABAP在系統總的FI值上有改善，但各波束間FI值相差較大；c）OPBID算法的系統FI值相比ABAP大幅優化，相比GA也有改善，而QPSOPS算法能夠取得比OPBID更好的系統FI值，說明QPSOPS具有更佳的公平性指數性能；d）從波束的FI值分布來看，相比OPBID算法，QPSOPS算法在波束3、6降低了FI，而在波束7～10小幅增加了FI。綜合來看，QPSOPS算法在FI指標上的性能更優。

圖5給出了不同算法對各點波束分配容量的結果。由圖5結合表5可知：a）相比于固定分配的ABAP，OPBID、GA和QPSOPS均能夠更好地擬合各波束的容量需求，3種算法均增加了對需求較高的波束6～10分配的容量，而相應減少對需求較少的波束1～5分配的容量；b）優化算法能夠適應信道條件的差異，對于信道條件較差的波束4、5，OPBID、GA和QPSOPS算法均能夠大幅減少分配的容量，以節省帶寬功率資源分配給其他信道條件較好的波束，而OPBID、QPSOPS適應性相比GA更優，能夠將分配給波束4、5的容量降低到最低需求；c）GA由于沒有考慮時延約束Ｃ2，所以對于波束1分配的容量低于最低容量需求；d）TSC指標上性能最優的為OPBID和QPSOPS算法，兩者比較，QPSOPS算法在波束3、6大幅增加了分配容量，而在波束7～10小幅減小了分配容量，結合表5中結果，總容量較大提升的同時公平性也有所提升，可見QPSOPS算法的全局尋優能力更強，綜合性能更優。

3.4 懲罰策略的效果分析

為了驗證懲罰策略在滿足問題約束上的有效性，本節使用不采用懲罰策略的算法GA（PBOP）、QPSO（OBOP）以及采用懲罰策略的算法GAPS（PBOP）、QPSOPS（OBOP）進行對比驗證。由于ABAP和OPBID為確定性優化算法，無法加入懲罰策略，所以在本節的分析中沒有考慮。各波束的FI值等高線分布如圖6、7所示，算法運算結果如圖8和表6所示。

圖6、7給出了各點波束的公平指數值分別在采用和不采用懲罰策略情況下的等高線分布示意圖。由圖6可知：a）在不使用懲罰策略的情況下，容量分配超過波束需求時，公平性指數值全部為0，對于優化算法來說則完全無法區別；b）在最小容量需求邊界處，不能夠有效地顯示出是否滿足時延約束的區別，因此也就不能夠有效地引導算法；c）波束1～5的公平性指數相對較小，因此可以推測波束1～5可能出現不滿足時延約束的分配結果（圖8的結果驗證了這一推測）。由圖7對比圖6可知，通過加入懲罰策略使得不滿足約束區域的公平性指數值增大，且在邊界處形成明顯的梯度，從而能夠對算法的搜索活動產生正確的引導。

圖8、表6給出了GA類、QPSO類算法分別在采用和不采用懲罰策略情況下，對各點波束分配容量的結果。由圖8結合表6可知：a）不使用懲罰策略的QPSO算法取得了最佳的性能表現，但該結果并不滿足時延約束條件；b）實際上QPSO和GA等價于在不考慮時延約束條件下的算法，對比文獻［14］給出的不考慮時延約束條件的算法（OPBND），GA算法在FI指標上與OPBND基本相當，而總容量結果更好，QPSO算法在FI和TSC兩個指標上的結果均好于GA和OPBND，但這建立在給波束1、2、5分配容量為0的基礎上，因此對波束的最小分配容量進行限制（即時延約束）是必要的；c）對比GAPS與GA、QPSOPS與QPSO算法，可見在不使用懲罰策略時，GA在波束1以及QPSO在波束1、5分配的容量均不滿足約束Euclid Math TwoCAp2，而加入懲罰策略均能夠保證優化解滿足約束條件。以上分析說明：a）QPSO算法的全局優化性能優于GA和基于對偶問題轉換的凸優化算法OPBND；b）懲罰策略的引入能夠使算法在不改變基本架構的前提下，使算法的優化解滿足時延約束條件，并且在GA和QPSO算法上均可引入，說明該策略具有良好的移植性。

4 結束語

本文提出了基于量子粒子群優化的多波束衛星帶寬功率聯合分配算法并進行了研究。首先對多波束衛星資源分配問題做了梳理，建立了以最優化分配公平性指數為目標函數，考慮波間干擾、雨衰、業務時延和信道條件系數的多波束衛星聯合資源分配模型。然后，提出了加入懲罰策略的量子粒子群算法，通過設計粒子的編碼方法和資源分配向量轉換方法，將資源分配優化問題轉換為最優粒子的求解問題。為使算法的優化解滿足問題模型的約束，設計了加入懲罰策略的目標函數，通過改進公平性指數的計算方式，使優化問題在不改變算法優化模式的情況下，自適應地滿足最大容量約束和時延約束。最后，通過仿真實驗分析了本文算法的性能。實驗結果表明，在相同算例下，本文算法和目前幾種代表性算法相比，可以在公平性指數最優的同時獲得最大的系統總容量，展現了較好的綜合性能。

本文的研究工作為使用元啟發式算法解決多波束衛星聯合資源分配問題提供了參考。結果表明，元啟發式算法能獲得全局性更好的優化解。下一步的研究方向為：考慮到不同目標函數之間的相互影響，將對衛星聯合資源分配問題的多目標優化開展研究，以更好地在不同的目標函數之間取得平衡，實現系統效能最佳。

參考文獻：

［1］Maral G，Bousquet M.Satellite communications systems：systems，techniques and technology［M］.5th ed.New York：Wiley，2009：1-18.

［2］Ippolito L J.Satellite communications systems engineering：atmospheric effects，satellite link design and system performance［M］.2nd ed.New York：Wiley，2017：49-74.

［3］Efrem C N，Panagopoulos A D.Dynamic energy-efficient power allocation in multibeam satellite systems［J］.IEEE Wireless Communications Letters，2020，9（2）：228－231.

［4］Choi J P，Chan V.Optimum power and beam allocation based on traffic demands and channel conditions over satellite downlinks［J］.IEEE Trans on Wireless Communications，2005，4（6）：2983－2993.

［5］李廣俠，馮琦，馮少棟.多點波束寬帶衛星系統波束間功率優化分配算法［J］.解放軍理工大學學報：自然科學版，2013，14（1）：1－6.（Li Guangxia，Feng Qi，Feng Shaodong.Optimal inter-beam power allocation algorithm for multi-beam broadband satellite systems［J］.Journal of PLA University of Science and Technology：Natural Science Edition，2013，14（1）：1－6.）

［6］胡圓圓，宋高俊.Ka頻段下多波束衛星通信的資源分配［J］.通信技術，2013，46（10）：22－25.（Hu Yuanyuan，Song Gaojun.Resource allocation of Ka band multi-beam satellite communication［J］.Communications Technology，2013，46（10）：22－25.）

［7］Wang Heng，Liu Aijun，Pan Xiaofeng，et al.Optimal bandwidth allocation for multi-spot-beam satellite communication systems［C］//Proc of International Conference on Mechatronic Sciences，Electric Enginee-ring and Computer.Piscataway，NJ：IEEE Press，2013：2794－2798.

［8］Wang Heng，Liu Aijun，Pan Xiaofeng，et al.Optimization of power allocation for a multibeam satellite communication system with inter-beam interference［J］.Journal of Applied Mathematics，2014，2014（1）：article ID 469437.

［9］Durand F R，Abrao T.Power allocation in multibeam satellites based on particle swarm optimization［J］.International Journal of Electronics and Communications，2017，78（8）：124-133.

［10］邵晴.多波束寬帶衛星通信系統資源分配及調度算法研究［D］.西安：西安科技大學，2021.（Shao Qing.Research on resource allocation and scheduling algorithm of multi-beam broadband satellite communication system［D］.Xi’an：Xi’an University of Science and Technology，2021.）

［11］Abdu T S，Kisseleff S，Lagunas E，et al.Flexible resource optimization for GEO multibeam satellite communication system［J］.Trans on Wireless Communications，2021，20（12）：7888-7902.

［12］賈錄良，孟艷，郭道省，等.多波束衛星通信功率帶寬聯合優化算法［J］.信號處理，2014，30（8）：973－978.（Jia Luliang，Meng Yan，Guo Daosheng，et al.A joint optimization algorithm of power and bandwidth for multi-beam satellite communication system［J］.Journal of Signal Processing，2014，30（8）：973－978.）

［13］劉銘.Ka波段多波束衛星功率分配算法研究［D］.哈爾濱：哈爾濱工程大學，2019.（Liu Ming.Research on Ka-band multi-beam satellite power allocation algorithms［D］.Harbin：Harbin Engineering University，2019.）

［14］楊宇龍.多波束衛星通信系統的資源分配算法研究［D］.哈爾濱：哈爾濱工程大學，2020.（Yang Yulong.Research on resource allocation algorithm for multi-beam satellite communication system［D］.Harbin：Harbin Engineering University，2020.）

［15］司闖，李鵬，史傳勝，等.多波束衛星通信系統波束干擾下的資源分配策略研究［J］.南京信息工程大學學報：自然科學版，2022，14（2）：233－240.（Si Chuang，Li Peng，Shi Chuansheng，et al.Research on resource allocation strategy under beam interference of multi-beam satellite communication system［J］.Journal of Nanjing University of Information Science amp; Technology：Natural Science Edition，2022，14（2）：233－240.）

［16］Barcelo-Llado J E，Vazquez-Castro M A，Lei J，et al.Distributed power and carrier allocation in multibeam satellite uplink with individual SINR constraints［C］//Proc of IEEE Global Telecommunications Conference.Piscataway，NJ：IEEE Press，2009：1－6.

［17］Sun Jun，Feng Bin，Xu Wenbo.Particle swarm optimization with particles having quantum behavior［C］//Proc of IEEE Congress on Evolutionary Computation.Piscataway，NJ：IEEE Press，2004：325－331.

［18］孫俊.量子行為粒子群優化算法研究［D］.無錫：江南大學，2009.（Sun Jun.Particle swarm optimization with particles having quantum behavior［D］.Wuxi：Jiangnan University，2009.）

收稿日期：2022－06－21；修回日期：2022－08－30 基金項目：國防預研項目

作者簡介：高威（1993－），男，湖北應城人，碩士，主要研究方向為衛星資源調度、智能優化算法等；王磊（1989－），男，山西大同人，副研究員，博士，主要研究方向為任務規劃、衛星資源調度等；瞿連政（1976－），男（通信作者），湖北廣水人，副研究員，碩導，博士，主要研究方向為需求分析、效能評估、衛星資源調度等（qlzsmile@163.com）．