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

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

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

0 引 言

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

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

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

1 網(wǎng)絡(luò)模型與問題描述

1.1 網(wǎng)絡(luò)模型

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

圖1 超密集異構(gòu)網(wǎng)絡(luò)(HetNet)模型

因為頻譜資源的有限性，現(xiàn)有的基站共享公用已有的頻譜資源，假設(shè)已知完美的信道狀態(tài)信息，采用非正交多址接入技術(shù)，在同一時刻，每個用戶只能接入一個基站和一個子信道，而同一個基站可以同時發(fā)送多個用戶的信息，同一個子載波也可以同時傳輸多個用戶，并且子載波之間是相互正交，使得不同子載波上傳輸?shù)挠脩艋ゲ桓蓴_。

由系統(tǒng)模型和NOMA原理可知，假設(shè)基站k可以通過子信道n同時向與其相關(guān)聯(lián)的用戶發(fā)送疊加信號xk,n， 那么基站k的發(fā)射信號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)

那么系統(tǒng)的總?cè)萘繛?/p>

(8)

由此可知，用戶在同一個基站的同一個子信道中傳輸時，子信道n可以連接很多個用戶，在同一信道中傳輸?shù)挠脩魰τ脩魎造成用戶之間的干擾；另外，由于同一個用戶u接入子信道n時，其它同層基站與宏基站也可能會使用同一個子信道n，這就使得同層的其它基站和宏基站對用戶u產(chǎn)生干擾。所以用戶關(guān)聯(lián)對系統(tǒng)容量的影響很重要。

1.2 問題描述

如圖2所示，用戶關(guān)聯(lián)問題可以建模為一個三維一對一匹配問題，即用戶、基站和子信道如何分配。眾所周知，三維匹配屬于NP-hard問題。針對用戶關(guān)聯(lián)從而使得整體系統(tǒng)最優(yōu)，可以等價為用戶如何關(guān)聯(lián)求取系統(tǒng)總?cè)萘孔畲蟆?/p>

圖2 用戶關(guān)聯(lián)三維匹配模型

假設(shè)βk,u為用戶u與基站k關(guān)聯(lián)系數(shù)，γn,u為用戶u與子信道n關(guān)聯(lián)系數(shù)，因為都屬于二元變量，可以定義為

(9)

(10)

(11)

因為目標函數(shù)最終結(jié)果取決于系數(shù)βk,u和γn,u取值關(guān)系，那么目標函數(shù)可以改寫為

(12)

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

2 問題求解

2.1 基礎(chǔ)知識

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

2.2 算法設(shè)計

2.2.1 初始化參數(shù)

(1)初始化基礎(chǔ)參數(shù)

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

(2)初始化種群參數(shù)

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

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

2.2.2 編碼與解碼

(1)點乘矩陣

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

(2)編碼與解碼過程

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

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

2.2.3 適應(yīng)度函數(shù)

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

(13)

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

F(h)=Fmax-φ(h)

(14)

2.2.4 遺傳算子

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

2.2.5 判斷算法是否收斂

是否滿足最大迭代時間Tmax， 若迭代時間大于Tmax， 則算法終止，否則繼續(xù)迭代。此外，用戶的平均適應(yīng)度函數(shù)是否趨于穩(wěn)定狀態(tài)，在一段時間內(nèi)平均適應(yīng)度函數(shù)穩(wěn)定，則算法收斂。

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

3 仿真分析

本文研究場景是在超密集異構(gòu)網(wǎng)絡(luò)下，一個宏基站的有效覆蓋區(qū)域A內(nèi)均勻分布k-1個微基站和隨機分布若干個用戶。具體的仿真參數(shù)見表1。

表1 系統(tǒng)仿真參數(shù)

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

圖5 迭代次數(shù)對系統(tǒng)容量變化的影響

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

圖6 用戶數(shù)量的變化對系統(tǒng)容量的影響

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

圖7 不同基站數(shù)量的變化對系統(tǒng)容量的影響

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

圖8 子信道數(shù)量的變化對系統(tǒng)容量的影響

4 結(jié)束語

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