認知超密集網絡用戶關聯與資源分配聯合優化遺傳算法

張俊杰，仇潤鶴*

（1.東華大學 信息科學與技術學院，上海 201620；2.數字化紡織服裝技術教育部工程研究中心（東華大學），上海 201620）

0 引言

超密集網絡（Ultra-Dense Network，UDN）［1］源自異構網絡（Heterogeneous Network），是5G 時代提升系統容量、提高網絡覆蓋、降低能耗的新型組網技術。認知無線電（Cognitive Radio，CR）［2］用于緩解頻譜資源緊張導致的同頻干擾問題，由于該技術具備頻譜感知與分配的功能，能為非授權用戶提供額外的增益良好的授權信道，CR 技術可以成為UDN 中降低干擾、提高頻譜利用率的有效技術。已有學者將認知技術與超密集網絡結合并展開了研究。

文獻［3-4］結合CR 與UDN，提出了在多種場景下的CRUDN 模型，并對比了遺傳算法與圖著色算法在不同應用場景下資源分配的優劣。文獻［5］中提出了在通用衰弱信道下考慮CR-UDN 的干擾分析模型。文獻［6-7］中采用分布式算法，利用認知技術將用戶分為宏基站（Macrocell Base Station，MBS）服務的宏基站用戶和毫微微基站（Femtocell Base Station，FBS）服務的毫微微基站用戶；通過FBS 間的磋商進行信道資源的交易，并使用凸近似算法進行功率分配。文獻［8-9］中使用拉格朗日對偶方程與卡羅需-庫恩-塔克（Karush-Kuhn-Tucker，KKT）條件聯合優化了非完美信道、非完美感知下的異構CR-UDN 中的資源分配與功率分配問題。文獻［10］中提出了用戶基站分布密度均較大時的CR-UDN干擾分析，設計了一種考慮公平性的基于用戶分簇的資源分配算法。文獻［11］中使用精英保留策略的遺傳算法求得次用戶最大帶寬。

以上文獻的研究重點均為資源分配與功率分配問題，隨著低功率基站密集化部署，開始出現大量基站覆蓋范圍的重疊，以用戶所在小區劃分基站用戶的服務關系的方法已不再適用，研究者們開始關注用戶關聯（User Association，UA）問題，即確定用戶與基站間的連接關系。傳統網絡中一般基于最優參考信號接收功率（Reference Signal Received Power，RSRP）實現UA，但RSRP 使得大量用戶傾向接入發射功率更大的MBS，因此不適用于異構網絡。在異構超密集網絡的研究中，已有研究將UA 問題建模為0/1 背包問題或匹配問題，文獻［12］中提出將二部圖聯合動態規劃求解異構網絡UA問題，縮小了解的搜索空間，配合拉格朗日對偶方程與KKT條件聯合優化資源與功率分配。文獻［13］中用MOSEK 求解器和二分類方法解得UA 矩陣，用拉格朗日乘子法解決功率分配問題。文獻［14］中基于匹配理論為用戶方和基站方各自生成對方的偏好列表，由雙方的選擇和拒絕操作建立連接關系。文獻［15］中提出了一種基于累計分布函數聯合優化UA 和資源分配的算法，為同一基站下的不同用戶分配時隙資源，最大化系統內用戶的長期吞吐量。文獻［16］中將UA與資源分配的問題拆分為兩個二維匹配問題，采用自適應的遺傳算子最大化系統內總吞吐量。

綜上文獻所述，目前異構網絡中的研究多數圍繞資源分配與功率分配進行優化，而將UA 作為一個孤立的子問題單獨考慮，且多數限于同構網絡。同時UA 與資源分配問題間具有較強的耦合性，分步優化會降低算法求解的準確性。目前少有在異構網絡中考慮干擾的同時將UA 和資源分配聯合優化的研究。因此，對認知超密集網絡下的UA 與資源分配的聯合優化問題的研究順應了當前用戶基站密集化的發展趨勢，具有重要研究意義。從上述文獻中還能看出，遺傳算法因其不依賴其他先驗知識且并行搜索的優勢常被用在UA或資源分配這些離散問題的求解中；然而傳統遺傳算法存在弊端，如對初始種群敏感，迭代出現非法解、收斂慢以及早熟等問題，都會嚴重影響優化結果。針對上述問題，本文在異構CR-UDN 模型下提出一種改進的遺傳算法對UA 和資源分配問題進行聯合優化。首先依據基站的覆蓋范圍和用戶類型構建用戶可用基站鏈表和用戶可用信道鏈表；編碼階段采取符號編碼，將染色體分為用戶-基站部分和用戶-信道部分；適應度計算階段，為降低同頻干擾的計算復雜度，以信道為單位計算吞吐量；選擇階段保存動態數量的最優個體，其余部分使用輪盤賭保留，保證遺傳算法的種群多樣性和收斂性；交叉和變異階段分別使用多點隨機交叉和位移置換算子，并動態變化變異概率，避免早熟而收斂至局部最優。

本文算法的編碼方式縮小了最優解的搜索空間，降低了計算復雜度，且使染色體在交叉變異后仍符合約束。遺傳算子的設計使得在較少的迭代次數下保證了收斂性，并避免了早熟，有效提高了網絡中用戶的吞吐量。

1 系統模型與問題描述

1.1 系統模型

本文考慮下行的異構CR-UDN 模型，模型如圖1。網絡中存在1 個MBS，K個FBS，若干融合中心，M條信道，N個用戶。考慮到用戶基站間的碰撞體積，將用戶分為兩部分，第一部分用戶按照硬核泊松點過程［17］分布在MBS 的覆蓋范圍內；第二部分為熱點區域用戶［3］，在隨機FBS 的覆蓋范圍內按硬核泊松點分布，其中熱點區域用戶占比為a。FBS 覆蓋范圍外的用戶由MBS 提供服務，依此將用戶分為宏小區用戶（Macrocell User，MU）和毫微微小區用戶（Femtocell User，FU）。FU 可在保證MU 正常通信的情況下伺機接入MU 占用的頻段。

圖1 異構認知超密集網絡模型Fig.1 Heterogeneous cognitive radio ultra-dense network model

可將用戶n的信干噪比rn表示為：

其中：gk，n，m表示基站用戶信道的邏輯連接向量，當gk，n，m=1 時認為基站k用戶n與信道m建立連接關系，為0 則未建立連接；Pk，n，m為基站k在信道m向用戶n發射的功率；hk，n，m為增益，有：

其中：wk，n是基站k到用戶n的大尺度衰弱，與基站用戶間的距離有關且成反比；Gk，n，m為小尺度衰弱，對不同的k、n、m是獨立的同分布復高斯隨機變換；Ik′，n，m為用戶n受到來自基站k′造成的同頻干擾。

其中：N0為高斯白噪聲。由于異構網絡中基站發射功率的量級差別，為保障資源分配階段的公平性，本文引入MBS 補償系數mr，有：

其中：補償系數mr的含義為MBS 最大發射功率與FBS 最大發射功率之比與單FBS 小區內最大用戶數與MBS 用戶數比值之積。當信號的發射基站為MBS 時，為其發射功率乘上補償系數mr。

1.2 問題描述

1.2.1 目標函數

本文將對異構CR-UDN 進行聯合優化用戶關聯與資源分配，并將網絡中總吞吐量作為目標函數。據香農公式，當載波間隔為W時，目標函數可寫為：

1.2.2 基站連接上限約束

基站連接的用戶數需小于等于天線數Lmax，需滿足：

1.2.3 用戶接入約束

本文為以網絡為中心的模型，信道接入方式為正交頻分復用（Orthogonal Frequency-Division Multiplexing，OFDM），即同一時間一個用戶僅可與一條信道一個基站連接，需滿足：

優化問題可建立為：

其中：C1 表示單基站最大連接數約束；C2 表示用戶僅與一個基站和一個信道建立連接關系；C3 表示g為基站-用戶-信道的是否建立連接關系的三維0/1 矩陣。該問題是一個三維非線性混合整數規劃問題，是一個離散的NP（Non-deterministic Polynomial）難問題，求解難度較高。本文將通過確定基站-用戶和用戶-信道的匹配關系，最大化網絡總吞吐量。

2 基于改進遺傳算法的聯合優化算法

該優化問題為一個三維的非線性離散優化問題，直接求解難度較高；故本文以最大化網絡總吞吐量為目標，提出一種改進的遺傳算法對上述問題中的用戶關聯與資源分配進行聯合優化。本文算法的主要思路與改進如下：

1）預處理。構建用戶可用基站鏈表和用戶可用信道鏈表。

2）編碼。采取符號編碼，三維匹配信息拆分為用戶-基站和用戶-信道兩個二維匹配信息。

3）適應度計算。計算網絡中總吞吐量。

4）選擇。依據適應度擇優保留一部分個體，其余部分使用輪盤賭保留，在保證種群多樣性的前提下提高了收斂速度。

5）交叉。采取多點隨機交叉算子。

6）變異。加入早熟判決算子，防止算法陷入局部最優。

2.1 預處理

受文獻［12，18］的啟發，5G 時代的FBS 使用毫米波頻段，具有視距傳輸（Line Of Sight，LOS）的特性。如圖2左側所示，將在用戶視距范圍內的基站定義為該用戶的可用基站，而非視距傳輸（Non Line Of Sight，NLOS）范圍內的基站為不可用基站，若視距傳輸范圍內無可用FBS，則該用戶由MBS 服務（MBS 默認編號為1）；不同用戶因其運營商、辦理業務的差異，有其對應的可用信道。如圖2 右側所示，建立用戶可用基站和可用信道列表，并保證每個用戶至少有一個可用基站和可用信道，預處理操作將解空間縮小為所有可行解的集合。用戶終端（User Equipment，UE）作為MU和FU的統稱。

圖2 預處理Fig.2 Preprocessing

2.2 編碼

本文為以基站為中心的網絡，具有一用戶僅連接一基站、一信道，而同一基站或信道可被不同用戶復用的特性。故采用符號編碼，針對兩種資源分別建立一條長度為N的數組BU和UC，每個數組的下標為用戶編號，數組中所填符號為對應用戶選擇基站/信道的編號，如圖3 所示。

圖3 符號編碼Fig.3 Symbol coding

例如BU（1）=3，表示用戶1 與基站3 建立連接關系。UC（2）=8，表示用戶2 與信道8 建立連接關系。BU和UC中的序號取自2.2 節預處理中生成的可用基站和可用信道列表。將BU與UC合并為一條長數組BUC作為算法的染色體輸入，每一條染色體均表示一種用戶關聯和資源分配的方案。

相比使用二部圖或者0/1 編碼的遺傳算法，符號編碼冗余較小，且本文的編碼方式使得搜索空間為全部可行解，染色體基因與每個用戶有直接的對應關系，確保每個用戶均能分配到可用資源。相比0/1 編碼的傳統遺傳算法，本文算法不會將迭代次數、交叉操作、變異機會浪費在不合約束的種群中（即出現一用戶多基站或者用戶分配不到基站的情況，盡管可以通過添加懲罰函數使得這些情況的適應度值足夠低，但交叉變異操作后仍可能出現不合約束的染色體）。

2.3 低復雜度的適應度函數

遺傳算法通過適應度函數不斷篩選優質群體［19］，從而使種群不斷進化，適應度越高，該染色體被選擇保留至下一代的概率越大。本文采取系統內FU 總吞吐量作為適應度函數。傳統遺傳算法在計算效用前，有一染色體解碼的步驟，即將每條染色體映射回基站-用戶-信道關聯矩陣。參考式（1）（3）（5）可見，同頻干擾Ik′，n，m是吞吐量計算的一個難點，無法直接使用矩陣乘法求出。為計算同頻干擾需搜索每一個用戶所在信道以及使用該信道的所有用戶，再搜索這些同頻用戶的服務基站到當前用戶的增益，其中搜索同頻用戶的操作中出現了大量重復操作，時間復雜度較高。本文將所有用戶吞吐量之和的計算改寫為所有信道吞吐量之和，在不改變適應度計算結果的前提下降低計算復雜度，且不對染色體做映射處理，種群適應度計算步驟如下。

1）搜索染色體的UC部分，記使用信道m的用戶集合為rum。

2）搜索BU部分找到rum的對應基站集合rbm，求得該信道下對rum中所有用戶的期望增益hn′和除用戶集rum的服務基站外的所有rbm到rum中每個用戶的干擾增益之和Ithn′，如圖4。

圖4 同信道吞吐量計算Fig.4 Calculation of throughput in the same channel

3）按式（9）計算信道m內所有用戶的吞吐量Rm。

4）按式（10）對所有信道的吞吐量求和。

其中：為FBS 的平均發射功率，當信號的發射基站為MBS，為其乘上MBS 補償系數mr。本算法使得在計算單個信道的吞吐量時只需搜索一次該信道內的同頻用戶，極大降低了時間復雜度。

2.4 選擇、交叉與變異

1）選擇算子——動態擇優保留+輪盤賭。

選擇算子依據適應度挑選優秀個體。由于遺傳算法不依賴梯度等輔助信息，且本文處理的是非連續離散問題，收斂困難。加上該問題種群適應度無明顯差異，僅使用輪盤賭選擇算子效率較低；而僅采用擇優保留的精英主義［11，16］又容易使種群過早收斂，陷入局部最優。綜合兩種方法的利弊，本文在選擇階段采取動態擇優復制保留+輪盤賭選擇機制，進行選擇操作時挑選子代中最高適應度的染色體復制G_num條保留至新種群，為確保新舊種群規模相同，剩余L_num-G_num條采用輪盤賭抽取保留。本文將G_num設為變量，與當前迭代次數有關，有：

其中：L_num為染色體條數，frame為總迭代次數，i為當前迭代次數，ρ為0～1 中的擇優比例常數,為向下取整。設計該動態的擇優保留策略能保證在迭代前期僅犧牲較少種群多樣性，在后期收斂至一穩定值。

2）交叉算子——多點隨機交叉。

遺傳算法中的交叉算子提供全局搜索性能，本文采取多點隨機交叉作為交叉算子，當兩條染色體滿足交叉條件時，選擇p個隨機不同位置進行交叉，p的取值為1～2N中任意值。為防止交叉操作陷入循環，所有染色體經過交叉判決后，將種群中所有染色體的順序隨機排列。

3）變異算子——早熟避免。

變異算子為遺傳算法搜尋提供局部搜索性能，本文采用位移置換作為變異算子。當滿足變異條件時，將染色體的當前資源改寫為該用戶可用資源鏈表中當前資源的下一個資源（見圖3）。考慮到存在可用資源數量僅為1 的用戶，進行變異判決時將跳過這些用戶，如圖3 中的BU（3）。由于選擇階段采取了啟發式算子，可能會使結果過早收斂。為了避免出現早熟而陷入局部最優，在變異階段開始前，添加一個早熟判決，當同時滿足下列兩個條件時，認為出現早熟，開始動態調節變異概率Pm。

①當前迭代次數i還未達到迭代上限frame的一半。

②種群適應度最大值與平均值之差小于一閾值。

當上述兩個條件均滿足時，每迭代一輪，即倍增當前變異概率（滿足Pm＜1），迭代至不滿足上述條件時停止倍增操作，并復位變異概率，如圖5。

圖5 避免早熟的變異算子Fig.5 Mutation operators for avoiding premature

本文算法框架與迭代過程如圖6。

圖6 聯合優化算法框架Fig.6 Joint optimization algorithm framework

3 仿真分析

為驗證本文算法的有效性，將本文算法與文獻［16］的三維匹配的遺傳算法、傳統遺傳算法（使用符號編碼），文獻［12］二部圖+文獻［20］圖著色的兩階段算法進行對比，并對比仿真結果。仿真中默認設置1 個MBS，20 個FBS，50 個用戶，20 條信道。遺傳算法中包含300 條染色體，200 次迭代，500 次重復實驗，假設認知基站完美感知信道狀態，參考文獻［3-4］，仿真參數如表1。

表1 仿真參數Tab.1 Simulation parameters

3.1 有效性分析

仿真圖7 表示用戶規模從20～80 變化與系統吞吐量的關系，迭代趨于平穩時說明收斂到最優值。系統吞吐量隨用戶數量的增長而提高，迭代平穩所需的迭代次數也隨之增加。這是由于用戶數量N的增長直接延長了染色體長度（染色體長度為2N），解的搜索空間呈指數增長，收斂所需迭代次數增多。用戶數量的增加導致了更多的同頻干擾，故吞吐量增長趨勢會逐漸趨于平緩。

圖7 迭代次數隨用戶數而變化Fig.7 Number of iterations varying with user number

圖8 為不同變異概率下吞吐量的變化，可見適應度函數隨變異概率的增長有一個先增后減的趨勢。變異算子為遺傳算法提供了局部搜索能力，變異概率Pm過小，獲得變異機會的基因少，局部搜索能力弱，需要更多迭代次數尋找最優解；Pm過大，染色體大范圍出現變異，可能導致潛在的最優解被破壞，導致系統難以在迭代上限次數內收斂。圖像在區間0.02～0.04 趨于平穩，在0.03 處存在峰值，故本文將0.03 設為默認變異概率。

圖8 吞吐量隨變異概率而變化Fig.8 Total throughput varying with probability of mutation

系統總吞吐量的比較如圖9 所示，比較隨著熱點區域用戶占比a的提高，本文算法與其他三種算法在系統總吞吐量上的變化。

熱點區域用戶的占比a，即FBS 服務對象占總用戶數的比例。由圖9 可見，系統內總吞吐量隨著a的提高而提高；這是因為將MBS 用戶卸載至距用戶更近的FBS 減小了同頻干擾。此外，分步算法的吞吐量隨熱點用戶占比的增長快速接近傳統遺傳算法；這是因為當a越接近1，FU 數量越多，該網絡模型就越接近同構網絡，這體現了圖著色算法在同構網絡中低復雜度高性能的優越性和在異構網絡中的局限性。本文算法與其他兩種遺傳算法在a較低處（即更接近異構網絡時）仍有較高的吞吐量，這是由于聯合優化算法具有更強的全局搜索能力，不易陷入局部最優；而遺傳算法是一種基于種群隨機搜索的算法，對于各種類型的網絡模型有較高的普適性。加上本文在適應度計算階段考慮到MBS 與FBS 發射功率的差異性，引入了MBS 功率補償系數mr，使得本文算法對異構網絡具有更強的適應性。

圖9 總吞吐量隨熱點用戶占比而變化Fig.9 Total throughput varying with the proportion of users in hotspots

圖10 為FU 吞吐量隨信道數增長的變化，可用信道的增加，降低了系統中的同頻干擾，FU 吞吐量與信道數成正比關系。可以看到本文算法略優于三維匹配遺傳算法與傳統遺傳算法，明顯優于傳統遺傳算法和二部圖+圖著色的分步算法。經計算，本文算法比上述算法在總吞吐量方面分別提高了7.2%、43.5%和132.0%，在認知用戶吞吐量方面分別提高了1.23%、34.3%和195.0%。這是由于處理的是非連續離散問題，傳統遺傳算法在選擇階段未保護最優值，且染色體間的效用值無明顯差別，輪盤賭選擇算子效率較低，收斂較慢，未能在迭代上限及時收斂至最優值，而本文采取動態擇優保留+輪盤賭的策略，保護了種群多樣性同時提高了收斂速度；三維匹配的遺傳算法采取啟發式的擇優保留的策略，但是沒有考慮啟發式算子導致的早熟問題，針對該問題本文加入了早熟判決算子，檢測到早熟時，將在每次迭代后倍增變異概率，直至出現更優值；分步算法由于單一優化的局限性，其性能遠不如聯合優化算法。可見本文算法對FU吞吐量的提升具有顯著的優勢，全局搜索性能更強。

圖10 FU吞吐量隨信道數而變化Fig.10 FU throughput varying with the number of channels

吞吐量與FBS 分布密度的關系如圖11 所示，三種方法的吞吐量均呈增加的趨勢。當FBS 密度較低時，存在大量MBS 用戶，同頻干擾嚴重；隨基站密度增加，MBS 用戶逐漸選擇接入FBS，降低了MBS 層的同頻干擾；在實現全覆蓋的基礎上基站密度繼續增加，大范圍出現FBS 覆蓋范圍的重疊，用戶有機會選擇距離更近的FBS 接入，跨層干擾降低，因距離產生的衰弱減小，吞吐量繼續增加。

圖11 FU吞吐量隨FBS分布密度而變化Fig.11 FU throughput varying with FBS distribution density

3.2 算法復雜度分析

本文在計算適應度時將計算所有用戶吞吐量之和改寫為所有信道吞吐量之和（見2.3 節），避免了計算同頻干擾時重復搜索同頻用戶的操作，降低了適應度計算階段的復雜度。本文算法的各個階段的復雜度如下：適應度計算O(L_num·C·N)；擇優操作O(L_num)；交叉操作O(L_num·N)；變異操作O(L_num·N)，共經歷frame次迭代。故本文算法的計算復雜度可表示為：O(frame·L_num·N·C)。

文獻［16］的三維匹配遺傳算法和傳統遺傳算法由于在適應度計算階段的解碼處理和累加用戶容量導致復雜度較高，該階段的復雜度為O(L_num)+O(L_num·N2·C·K)，復雜度之和均可表示為O(frame·L_num·N2·C·K)。

分步優化算法中文獻［11］二部圖和文獻［20］圖著色算法的復雜度之和為O(K·N+C·N)，復雜度較低；但由于將用戶關聯與資源分配拆分成了兩個子問題分別優化，其吞吐量遠小于聯合優化算法。

其中L_num為染色體條數，frame為迭代次數，N為用戶總數，C為信道總數，K為FBS 總數。

通過分析異構CR-UDN 模型中用戶規模、熱點區域用戶占比、信道數量、FBS 分布密度對系統總吞吐量和FU 總吞吐量的影響，本文算法在收斂速度、計算復雜度上要優于文獻［16］的改進遺傳算法，相較于傳統遺傳算法不易陷入局部最優，在對異構網絡的適應性上要優于二部圖+圖著色的分步優化算法。

4 結語

本文針對CR-UDN 異構網絡總吞吐量優化進行研究，提出一種聯合優化用戶關聯與資源分配的改進遺傳算法。首先構建用戶可用基站鏈表和用戶可用信道鏈表；其次采取符號編碼，將染色體分為用戶-基站部分和用戶-信道部分；然后以信道為單位計算適應度函數，采用動態擇優復制+輪盤賭進行選擇保留；最后將多點隨機交叉作為交叉算子，并設計了避免早熟的動態變異算子。本文算法避開了傳統遺傳算法解碼時的映射問題，使得解合乎約束的同時保證了迭代時的種群多樣性和收斂性，避免了遺傳算法的早熟問題；相較于圖著色算法，本文算法在異構網絡中有良好的適用性。仿真結果表示，本文算法有較好的收斂性，大幅提高了網絡的吞吐量；然而在以提高吞吐量為目標的多約束優化問題中，用戶關聯、資源分配的優化與功率分配的優化有較強的耦合關系。下一步工作將重點研究聯合優化場景下用戶關聯、資源分配算法與功率分配算法如何更好地實現解耦。