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

(重慶郵電大學(xué) 通信與信息工程學(xué)院，重慶 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]等進(jìn)行分步求解。此外，將用戶與基站的關(guān)聯(lián)轉(zhuǎn)化為二部圖形式，使用匈牙利算法求得最優(yōu)解[4]，或者在匹配理論的基礎(chǔ)上修改二部圖的雙邊匹配權(quán)重，求得次優(yōu)解[5]，然而該情況并沒有考慮同一子信道中傳輸用戶的干擾，并且雙邊匹配權(quán)重并不能使得系統(tǒng)函數(shù)達(dá)到最優(yōu)。針對復(fù)雜的關(guān)聯(lián)情況，常采用融合算法進(jìn)行求解[6-8]，常見的基于分布式算法和遺傳算法的基礎(chǔ)上提出兩種算法的混合迭代算法，基于蟻群的遺傳算法和量子遺傳算法等。算法、基于蟻群的遺傳算法、量子遺傳算法進(jìn)行比較分析[10]，但是此算法僅考慮了用戶與基站匹配，并且可能因?yàn)榉N群多樣性減少陷入局部最優(yōu)。

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

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

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

兩層的超密集異構(gòu)網(wǎng)絡(luò)(HetNet)模型，如圖1所示。A區(qū)域?yàn)楹昊?MBS)的有效覆蓋范圍，MBS內(nèi)均勻分布著若干微基站(SCBSs)。設(shè)基站表示為k，k∈{1，2，…K}， 當(dāng)k=1時表示為宏基站；在A區(qū)域內(nèi)隨機(jī)分布的若干用戶表示為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)模型

因?yàn)轭l譜資源的有限性，現(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ù)，因?yàn)槎紝儆诙兞?，可以定義為

(9)

(10)

(11)

因?yàn)槟繕?biāo)函數(shù)最終結(jié)果取決于系數(shù)βk,u和γn,u取值關(guān)系，那么目標(biāo)函數(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ǔ)知識

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

2.2 算法設(shè)計(jì)

2.2.1 初始化參數(shù)

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

給定各項(xiàng)參數(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的真實(shí)映射，矩陣B2為用戶i與子信道n的真實(shí)映射。假設(shè)有6個用戶，1個宏基站，3個小基站，4個子信道，那么可得出矩陣B， 用戶在基站和子信道的映射關(guān)系如圖3所示。

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

2.2.2 編碼與解碼

(1)點(diǎn)乘矩陣

因?yàn)橛脩粼诤昊緝?nèi)是隨機(jī)生成的，而宏基站和微基站是有一定的有效覆蓋范圍的，為了保證初始化矩陣生成的匹配在有效覆蓋范圍內(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)方式下的資源分配的編碼表示。因?yàn)橛脩襞c基站和子信道關(guān)聯(lián)屬于三維匹配，取矩陣LA為用戶與基站不同關(guān)聯(lián)方式下的染色體序列， 矩陣LB為用戶與子信道不同關(guān)聯(lián)方式下的染色體序列。為了計(jì)算染色體的適應(yīng)度，需要將染色體映射到資源分配矩陣之中，所以將LA的染色體序列映射到矩陣E中；將矩陣LB的染色體序列映射到矩陣F中；進(jìn)而得出用戶分別與基站和子信道不同關(guān)聯(lián)情況。如圖4所示用戶分別與基站和子信道不同關(guān)聯(lián)情況下映射的資源分配染色。

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

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

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

(13)

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

F(h)=Fmax-φ(h)

(14)

2.2.4 遺傳算子

遺傳算法是一種模擬生物種群DNA遺傳變異的算法。通過隨機(jī)生成的種群個體組成染色體開始遺傳變異，根據(jù)種群的適應(yīng)度函數(shù)的變化選擇種群后代，從而不斷地選擇出優(yōu)異子代，淘汰劣勢個體。一般情況下，遺傳算法的流程包括4個步驟：隨機(jī)產(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)解，此時需要在選擇子代匹配時將隨機(jī)選擇和確定性選擇相結(jié)合，既能確保遺傳變異的優(yōu)者生存法則，又能防止系統(tǒng)匹配陷入局部最優(yōu)解。

3 仿真分析

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

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

圖5在子信道的數(shù)目為10,基站的數(shù)目為6，用戶數(shù)為30的條件下，迭代次數(shù)對系統(tǒng)容量的變化。采用改進(jìn)的遺傳算法求解用戶與基站和子信道關(guān)聯(lián)的迭代過程圖。從圖中可以看出，隨著迭代次數(shù)的不斷增加，系統(tǒng)總?cè)萘坎粩嘣黾?，但是在迭代一定次?shù)的時候，出現(xiàn)了由于種群多樣性減少而陷入局部最優(yōu)解，此時利用算法的隨機(jī)性和確定性精英個體的選擇機(jī)制，可以跳出局部最優(yōu)，從而達(dá)到全局最優(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)逐漸下降的趨勢，這是因?yàn)閭鹘y(tǒng)遺傳算法的種群必須有一定的范圍，隨著用戶數(shù)量的不斷增加，種群數(shù)量也在增加，當(dāng)種群數(shù)量超出一定范圍就不再適用此方法了；貪婪算法類似于窮舉，其解接近于最優(yōu)，但是復(fù)雜度很高。

圖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)取值上三者都很接近，但是復(fù)雜度上明顯低于貪婪算法。

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

圖8給出了在用戶u的數(shù)目為30個、基站k的數(shù)目為6個的條件下，子信道的變化對系統(tǒng)容量的影響。從圖中可以看出，子信道數(shù)量的增加，小區(qū)間和小區(qū)內(nèi)的干擾不斷減小，使得系統(tǒng)總?cè)萘坎粩嘣黾?。本文提出的算法可以在降低?fù)雜度的情況下使系統(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)有文獻(xiàn)針對用戶關(guān)聯(lián)的三維匹配都是分解為二維匹配進(jìn)行求解，本文通過使用一種改進(jìn)遺傳算法求解用戶與基站和子信道的三維匹配問題，為了減少系統(tǒng)復(fù)雜度，設(shè)計(jì)一種多維映射過程，防止算法陷入局部最優(yōu)，在種群多樣性設(shè)計(jì)方面增加了隨機(jī)性和確定性染色體的精英選擇機(jī)制，從而求得全局最優(yōu)。針對資源分配問題，用戶與基站和子信道的關(guān)聯(lián)影響著系統(tǒng)分配資源，但是在用戶匹配之后，基站如何給覆蓋范圍內(nèi)的用戶分配合適的功率也影響著系統(tǒng)資源，所以針對用戶功率分配問題將作為下一步的工作方向。