基于遺傳算法求解三維匹配的資源分配問題

龍 懇，魯江麗，李 偉，蔣明均

(重慶郵電大學 通信與信息工程學院，重慶 400065)

0 引 言

為了提高系統頻譜利用效率并增加用戶接入量，非正交多址技術被納入討論[1]；同時，為了提供更高的吞吐量和頻譜效率，HUDN引起了廣泛的研究興趣[2]。

針對超密集異構網絡和NOMA的研究主要集中在以下幾個方面：用戶關聯、子信道分配、功率分配、用戶功率分配等等。關于用戶關聯和子信道分配，現有研究都是基于匹配理論、博弈論、匈牙利算法、凸優化無限逼近[3]等進行分步求解。此外，將用戶與基站的關聯轉化為二部圖形式，使用匈牙利算法求得最優解[4]，或者在匹配理論的基礎上修改二部圖的雙邊匹配權重，求得次優解[5]，然而該情況并沒有考慮同一子信道中傳輸用戶的干擾，并且雙邊匹配權重并不能使得系統函數達到最優。針對復雜的關聯情況，常采用融合算法進行求解[6-8]，常見的基于分布式算法和遺傳算法的基礎上提出兩種算法的混合迭代算法，基于蟻群的遺傳算法和量子遺傳算法等。算法、基于蟻群的遺傳算法、量子遺傳算法進行比較分析[10]，但是此算法僅考慮了用戶與基站匹配，并且可能因為種群多樣性減少陷入局部最優。

眾所周知，用戶、基站和子信道的三維匹配問題屬于NP-hard問題，人們處理多維匹配問題，都是通過將多維匹配分解為二維的匹配[11,12]，但是這種分解方法是通過降低系統的準確度為代價。針對以上情況，本文提出一種智能遺傳算法求解三維用戶匹配問題，通過設計一種多維染色體映射關系，將用戶與基站和子信道的關聯問題轉化為染色體進行遺傳變異，從而得出最佳匹配。

1 網絡模型與問題描述

1.1 網絡模型

兩層的超密集異構網絡(HetNet)模型，如圖1所示。A區域為宏基站(MBS)的有效覆蓋范圍，MBS內均勻分布著若干微基站(SCBSs)。設基站表示為k，k∈{1，2，…K}， 當k=1時表示為宏基站；在A區域內隨機分布的若干用戶表示為u，u∈{1，2，…U}； 用戶與基站之間傳輸信息所使用的子載波表示為n，n∈{1,2,…N}。 設定MBS分配給微基站k的功率表示為Ptk， 微基站k通過子信道n分配給用戶u的功率表示為Pk,n,u。

圖1 超密集異構網絡(HetNet)模型

因為頻譜資源的有限性，現有的基站共享公用已有的頻譜資源，假設已知完美的信道狀態信息，采用非正交多址接入技術，在同一時刻，每個用戶只能接入一個基站和一個子信道，而同一個基站可以同時發送多個用戶的信息，同一個子載波也可以同時傳輸多個用戶，并且子載波之間是相互正交，使得不同子載波上傳輸的用戶互不干擾。

由系統模型和NOMA原理可知，假設基站k可以通過子信道n同時向與其相關聯的用戶發送疊加信號xk,n， 那么基站k的發射信號xk,n可以表示為

(1)

(2)

(3)

Ik,n,u=∑i∈{Sk,n|gk,n,i>gk,n,u}Pk,i,ngk,n,u

(4)

(5)

(6)

用戶u的吞吐量為

(7)

那么系統的總容量為

(8)

由此可知，用戶在同一個基站的同一個子信道中傳輸時，子信道n可以連接很多個用戶，在同一信道中傳輸的用戶會對用戶u造成用戶之間的干擾；另外，由于同一個用戶u接入子信道n時，其它同層基站與宏基站也可能會使用同一個子信道n，這就使得同層的其它基站和宏基站對用戶u產生干擾。所以用戶關聯對系統容量的影響很重要。

1.2 問題描述

如圖2所示，用戶關聯問題可以建模為一個三維一對一匹配問題，即用戶、基站和子信道如何分配。眾所周知，三維匹配屬于NP-hard問題。針對用戶關聯從而使得整體系統最優，可以等價為用戶如何關聯求取系統總容量最大。

圖2 用戶關聯三維匹配模型

假設βk,u為用戶u與基站k關聯系數，γn,u為用戶u與子信道n關聯系數，因為都屬于二元變量，可以定義為

(9)

(10)

(11)

因為目標函數最終結果取決于系數βk,u和γn,u取值關系，那么目標函數可以改寫為

(12)

約束條件C1表示用戶分配的功率滿足基站總功率的約束；約束條件C2表示用戶的吞吐量滿足QoS的最低要求；約束條件C3表示用戶關聯取值范圍，取值為1表示與基站關聯，取值為0表示用戶與基站不關聯；約束條件C4表示用戶關聯基站，在同一個時間內，一個用戶只能關聯一個基站；約束條件C5表示用戶與子信道關聯取值范圍，取值為1表示與子信道關聯，取值為0表示用戶與子信道不關聯；約束條件C6表示用戶關聯子信道，在同一個時間內，每個用戶只能關聯1個子信道。

2 問題求解

2.1 基礎知識

遺傳算法就是仿照自然界生物進化的機制，通過染色體不斷地遺傳和變異，使用“適者生存”不斷淘汰劣勢群體，從而使得種群不斷進化，達到全局最優的一種智能算法。由于遺傳算法的本質就是通過并行處理染色體，不斷地遺傳變異，屬于一種高效快速的全局搜索算法，所以相比較于其它算法，遺傳算法不用考慮其內部協同關系，僅依靠一個統一的評價標準(即適應度函數)就可以否定劣勢群體，具有很強的靈活性和搜索速度，快速趨于穩定狀態。

2.2 算法設計

2.2.1 初始化參數

(1)初始化基礎參數

給定各項參數，用戶u的個數、子信道n的個數、基站k的個數、用戶的信道增益矩陣g、 基站功率Ptk等參數。定義矩陣A為用戶i在基站k和子信道n的有效覆蓋范圍，矩陣A中的元素aij， 若aij=1表示用戶i在基站k或者子信道n的有效覆蓋范圍，否則用戶i不在有效覆蓋范圍內。令矩陣A=[A1?A2]， 其中矩陣A1為用戶i與基站k的映射情況，矩陣A2為用戶i與子信道n的映射情況。

(2)初始化種群參數

初始化種群為M， 第i個種群在三維搜索空間中的位置向量xi=(xi1,xi2)，i=1，2，…M， 種群的個體極值為Pi=(Pi1,Pi2…,PiM)， 整個粒子群的全局極值Pg， 交叉概率Pc、 變異概率Pm， 最大迭代次數Tmax等參數。定義匹配矩陣B=[B1?B2], 其中，矩陣B1為用戶i與基站k的真實映射，矩陣B2為用戶i與子信道n的真實映射。假設有6個用戶，1個宏基站，3個小基站，4個子信道，那么可得出矩陣B， 用戶在基站和子信道的映射關系如圖3所示。

圖3 用戶在基站和子信道的映射

2.2.2 編碼與解碼

(1)點乘矩陣

因為用戶在宏基站內是隨機生成的，而宏基站和微基站是有一定的有效覆蓋范圍的，為了保證初始化矩陣生成的匹配在有效覆蓋范圍內，設定矩陣C=A·*B， 矩陣C中的元素cij為矩陣A和矩陣B中對應元素相乘而得，只有兩個矩陣同時為1，那么cij=1， 即cij=aij*bij。

(2)編碼與解碼過程

解決方案對應于染色體，染色體為每個用戶分別與基站和子信道不同關聯方式下的資源分配的編碼表示。因為用戶與基站和子信道關聯屬于三維匹配，取矩陣LA為用戶與基站不同關聯方式下的染色體序列， 矩陣LB為用戶與子信道不同關聯方式下的染色體序列。為了計算染色體的適應度，需要將染色體映射到資源分配矩陣之中，所以將LA的染色體序列映射到矩陣E中；將矩陣LB的染色體序列映射到矩陣F中；進而得出用戶分別與基站和子信道不同關聯情況。如圖4所示用戶分別與基站和子信道不同關聯情況下映射的資源分配染色。

圖4 染色體映射到資源分配矩陣模型

2.2.3 適應度函數

適應度函數是指在種群的遺傳變異產生的后代種群中，會由于“適者生存”而舍棄一部分后代個體，而這個“合適”的標準就是用適應度函數進行衡量的。適應度函數作為衡量一個個體是否適應自然界的一個量化指標，其數值的大小直接決定了個體的生存狀態的好壞，一般情況下，適應程度越高，解決方案質量越好，選擇個體的概率越大。因此，適應度函數的選取非常重要，它直接影響遺傳算法的收斂速度和最優解的建立概率。此外，因為優化目標函數屬于非線性有約束條件的，懲罰函數的思想是將約束優化問題轉化為無約束優化問題，可以使用在目標函數中添加(或減去)一定的值來實現，所以本文需要引入懲罰函數φ(h)將含有約束條件的目標函數轉化為無約束優化問題進行求解

(13)

其中，μk為足夠大的懲罰因子。定義Fmax=max{φ(h)|h=1,2,…}， 那么適應度函數可以變化為

F(h)=Fmax-φ(h)

(14)

2.2.4 遺傳算子

遺傳算法是一種模擬生物種群DNA遺傳變異的算法。通過隨機生成的種群個體組成染色體開始遺傳變異，根據種群的適應度函數的變化選擇種群后代，從而不斷地選擇出優異子代，淘汰劣勢個體。一般情況下，遺傳算法的流程包括4個步驟：隨機產生種群、選擇、交叉和變異。

2.2.5 判斷算法是否收斂

是否滿足最大迭代時間Tmax， 若迭代時間大于Tmax， 則算法終止，否則繼續迭代。此外，用戶的平均適應度函數是否趨于穩定狀態，在一段時間內平均適應度函數穩定，則算法收斂。

總之，用戶在多維空間中，通過不斷地遺傳變異，挑選出系統容量最大的匹配組合。但是可能會由于遺傳變異的局限性使得系統容量穩定在局部最優解，此時需要在選擇子代匹配時將隨機選擇和確定性選擇相結合，既能確保遺傳變異的優者生存法則，又能防止系統匹配陷入局部最優解。

3 仿真分析

本文研究場景是在超密集異構網絡下，一個宏基站的有效覆蓋區域A內均勻分布k-1個微基站和隨機分布若干個用戶。具體的仿真參數見表1。

表1 系統仿真參數

圖5在子信道的數目為10,基站的數目為6，用戶數為30的條件下，迭代次數對系統容量的變化。采用改進的遺傳算法求解用戶與基站和子信道關聯的迭代過程圖。從圖中可以看出，隨著迭代次數的不斷增加，系統總容量不斷增加，但是在迭代一定次數的時候，出現了由于種群多樣性減少而陷入局部最優解，此時利用算法的隨機性和確定性精英個體的選擇機制，可以跳出局部最優，從而達到全局最優解的收斂情況。

圖5 迭代次數對系統容量變化的影響

圖6給出了在子信道n的數目為10個、基站k的數目為6個的條件下，用戶數目的變化對系統容量的變化情況。隨著小區覆蓋范圍內用戶數量的不同，系統容量也是不斷變化的，從圖中可以看出，隨著用戶數量的不斷增加，系統總容量不斷增加，但是在迭代一定次數的時候，傳統的遺傳算法由于自身因素的限制，會出現逐漸下降的趨勢，這是因為傳統遺傳算法的種群必須有一定的范圍，隨著用戶數量的不斷增加，種群數量也在增加，當種群數量超出一定范圍就不再適用此方法了；貪婪算法類似于窮舉，其解接近于最優，但是復雜度很高。

圖6 用戶數量的變化對系統容量的影響

圖7給出了在用戶u的數目為30個、子信道n的數目為6個的條件下，基站數目的變化對系統容量的影響。圖7(a)使用傳統GA算法的效果明顯低于其它算法，而OMA中沒有區分子信道使得在同一個帶寬中傳輸的用戶數量增多，增大了用戶間的干擾。圖7(b)為本文提出的算法、貪婪算法和匹配算法之間的對比，從中可以看出，本文提出的算法在最優取值上三者都很接近，但是復雜度上明顯低于貪婪算法。

圖7 不同基站數量的變化對系統容量的影響

圖8給出了在用戶u的數目為30個、基站k的數目為6個的條件下，子信道的變化對系統容量的影響。從圖中可以看出，子信道數量的增加，小區間和小區內的干擾不斷減小，使得系統總容量不斷增加。本文提出的算法可以在降低復雜度的情況下使系統容量數值接近于貪婪算法，且明顯優于凸優化取整算法，傳統遺傳算法會陷入局部最優，其最終結果類似于OMA。

圖8 子信道數量的變化對系統容量的影響

4 結束語

在超密集異構網絡模型中，由于引入了NOMA技術，使得小區間和小區內的用戶干擾減少，那么用戶在基站的有效覆蓋范圍內，如何選擇基站，以及用戶選擇在哪個頻帶中傳輸成為至關重要的問題之一。在此背景下，目前現有文獻針對用戶關聯的三維匹配都是分解為二維匹配進行求解，本文通過使用一種改進遺傳算法求解用戶與基站和子信道的三維匹配問題，為了減少系統復雜度，設計一種多維映射過程，防止算法陷入局部最優，在種群多樣性設計方面增加了隨機性和確定性染色體的精英選擇機制，從而求得全局最優。針對資源分配問題，用戶與基站和子信道的關聯影響著系統分配資源，但是在用戶匹配之后，基站如何給覆蓋范圍內的用戶分配合適的功率也影響著系統資源，所以針對用戶功率分配問題將作為下一步的工作方向。