認(rèn)知超密集網(wǎng)絡(luò)用戶關(guān)聯(lián)與資源分配聯(lián)合優(yōu)化遺傳算法

張俊杰，仇潤鶴*

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

0 引言

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

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

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

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

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

1 系統(tǒng)模型與問題描述

1.1 系統(tǒng)模型

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

圖1 異構(gòu)認(rèn)知超密集網(wǎng)絡(luò)模型Fig.1 Heterogeneous cognitive radio ultra-dense network model

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

其中：gk，n，m表示基站用戶信道的邏輯連接向量，當(dāng)gk，n，m=1 時(shí)認(rèn)為基站k用戶n與信道m(xù)建立連接關(guān)系，為0 則未建立連接；Pk，n，m為基站k在信道m(xù)向用戶n發(fā)射的功率；hk，n，m為增益，有：

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

其中：N0為高斯白噪聲。由于異構(gòu)網(wǎng)絡(luò)中基站發(fā)射功率的量級(jí)差別，為保障資源分配階段的公平性，本文引入MBS 補(bǔ)償系數(shù)mr，有：

其中：補(bǔ)償系數(shù)mr的含義為MBS 最大發(fā)射功率與FBS 最大發(fā)射功率之比與單FBS 小區(qū)內(nèi)最大用戶數(shù)與MBS 用戶數(shù)比值之積。當(dāng)信號(hào)的發(fā)射基站為MBS 時(shí)，為其發(fā)射功率乘上補(bǔ)償系數(shù)mr。

1.2 問題描述

1.2.1 目標(biāo)函數(shù)

本文將對(duì)異構(gòu)CR-UDN 進(jìn)行聯(lián)合優(yōu)化用戶關(guān)聯(lián)與資源分配，并將網(wǎng)絡(luò)中總吞吐量作為目標(biāo)函數(shù)。據(jù)香農(nóng)公式，當(dāng)載波間隔為W時(shí)，目標(biāo)函數(shù)可寫為：

1.2.2 基站連接上限約束

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

1.2.3 用戶接入約束

本文為以網(wǎng)絡(luò)為中心的模型，信道接入方式為正交頻分復(fù)用（Orthogonal Frequency-Division Multiplexing，OFDM），即同一時(shí)間一個(gè)用戶僅可與一條信道一個(gè)基站連接，需滿足：

優(yōu)化問題可建立為：

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

2 基于改進(jìn)遺傳算法的聯(lián)合優(yōu)化算法

該優(yōu)化問題為一個(gè)三維的非線性離散優(yōu)化問題，直接求解難度較高；故本文以最大化網(wǎng)絡(luò)總吞吐量為目標(biāo)，提出一種改進(jìn)的遺傳算法對(duì)上述問題中的用戶關(guān)聯(lián)與資源分配進(jìn)行聯(lián)合優(yōu)化。本文算法的主要思路與改進(jìn)如下：

1）預(yù)處理。構(gòu)建用戶可用基站鏈表和用戶可用信道鏈表。

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

3）適應(yīng)度計(jì)算。計(jì)算網(wǎng)絡(luò)中總吞吐量。

4）選擇。依據(jù)適應(yīng)度擇優(yōu)保留一部分個(gè)體，其余部分使用輪盤賭保留，在保證種群多樣性的前提下提高了收斂速度。

5）交叉。采取多點(diǎn)隨機(jī)交叉算子。

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

2.1 預(yù)處理

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

圖2 預(yù)處理Fig.2 Preprocessing

2.2 編碼

本文為以基站為中心的網(wǎng)絡(luò)，具有一用戶僅連接一基站、一信道，而同一基站或信道可被不同用戶復(fù)用的特性。故采用符號(hào)編碼，針對(duì)兩種資源分別建立一條長度為N的數(shù)組BU和UC，每個(gè)數(shù)組的下標(biāo)為用戶編號(hào)，數(shù)組中所填符號(hào)為對(duì)應(yīng)用戶選擇基站/信道的編號(hào)，如圖3 所示。

圖3 符號(hào)編碼Fig.3 Symbol coding

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

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

2.3 低復(fù)雜度的適應(yīng)度函數(shù)

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

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

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

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

3）按式（9）計(jì)算信道m(xù)內(nèi)所有用戶的吞吐量Rm。

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

其中：為FBS 的平均發(fā)射功率，當(dāng)信號(hào)的發(fā)射基站為MBS，為其乘上MBS 補(bǔ)償系數(shù)mr。本算法使得在計(jì)算單個(gè)信道的吞吐量時(shí)只需搜索一次該信道內(nèi)的同頻用戶，極大降低了時(shí)間復(fù)雜度。

2.4 選擇、交叉與變異

1）選擇算子——?jiǎng)討B(tài)擇優(yōu)保留+輪盤賭。

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

其中：L_num為染色體條數(shù)，frame為總迭代次數(shù)，i為當(dāng)前迭代次數(shù)，ρ為0～1 中的擇優(yōu)比例常數(shù),為向下取整。設(shè)計(jì)該動(dòng)態(tài)的擇優(yōu)保留策略能保證在迭代前期僅犧牲較少種群多樣性，在后期收斂至一穩(wěn)定值。

2）交叉算子——多點(diǎn)隨機(jī)交叉。

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

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

變異算子為遺傳算法搜尋提供局部搜索性能，本文采用位移置換作為變異算子。當(dāng)滿足變異條件時(shí)，將染色體的當(dāng)前資源改寫為該用戶可用資源鏈表中當(dāng)前資源的下一個(gè)資源（見圖3）?？紤]到存在可用資源數(shù)量僅為1 的用戶，進(jìn)行變異判決時(shí)將跳過這些用戶，如圖3 中的BU（3）。由于選擇階段采取了啟發(fā)式算子，可能會(huì)使結(jié)果過早收斂。為了避免出現(xiàn)早熟而陷入局部最優(yōu)，在變異階段開始前，添加一個(gè)早熟判決，當(dāng)同時(shí)滿足下列兩個(gè)條件時(shí)，認(rèn)為出現(xiàn)早熟，開始動(dòng)態(tài)調(diào)節(jié)變異概率Pm。

①當(dāng)前迭代次數(shù)i還未達(dá)到迭代上限frame的一半。

②種群適應(yīng)度最大值與平均值之差小于一閾值。

當(dāng)上述兩個(gè)條件均滿足時(shí)，每迭代一輪，即倍增當(dāng)前變異概率（滿足Pm＜1），迭代至不滿足上述條件時(shí)停止倍增操作，并復(fù)位變異概率，如圖5。

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

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

圖6 聯(lián)合優(yōu)化算法框架Fig.6 Joint optimization algorithm framework

3 仿真分析

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

表1 仿真參數(shù)Tab.1 Simulation parameters

3.1 有效性分析

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

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

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

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

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

熱點(diǎn)區(qū)域用戶的占比a，即FBS 服務(wù)對(duì)象占總用戶數(shù)的比例。由圖9 可見，系統(tǒng)內(nèi)總吞吐量隨著a的提高而提高；這是因?yàn)閷BS 用戶卸載至距用戶更近的FBS 減小了同頻干擾。此外，分步算法的吞吐量隨熱點(diǎn)用戶占比的增長快速接近傳統(tǒng)遺傳算法；這是因?yàn)楫?dāng)a越接近1，F(xiàn)U 數(shù)量越多，該網(wǎng)絡(luò)模型就越接近同構(gòu)網(wǎng)絡(luò)，這體現(xiàn)了圖著色算法在同構(gòu)網(wǎng)絡(luò)中低復(fù)雜度高性能的優(yōu)越性和在異構(gòu)網(wǎng)絡(luò)中的局限性。本文算法與其他兩種遺傳算法在a較低處（即更接近異構(gòu)網(wǎng)絡(luò)時(shí)）仍有較高的吞吐量，這是由于聯(lián)合優(yōu)化算法具有更強(qiáng)的全局搜索能力，不易陷入局部最優(yōu)；而遺傳算法是一種基于種群隨機(jī)搜索的算法，對(duì)于各種類型的網(wǎng)絡(luò)模型有較高的普適性。加上本文在適應(yīng)度計(jì)算階段考慮到MBS 與FBS 發(fā)射功率的差異性，引入了MBS 功率補(bǔ)償系數(shù)mr，使得本文算法對(duì)異構(gòu)網(wǎng)絡(luò)具有更強(qiáng)的適應(yīng)性。

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

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

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

吞吐量與FBS 分布密度的關(guān)系如圖11 所示，三種方法的吞吐量均呈增加的趨勢。當(dāng)FBS 密度較低時(shí)，存在大量MBS 用戶，同頻干擾嚴(yán)重；隨基站密度增加，MBS 用戶逐漸選擇接入FBS，降低了MBS 層的同頻干擾；在實(shí)現(xiàn)全覆蓋的基礎(chǔ)上基站密度繼續(xù)增加，大范圍出現(xiàn)FBS 覆蓋范圍的重疊，用戶有機(jī)會(huì)選擇距離更近的FBS 接入，跨層干擾降低，因距離產(chǎn)生的衰弱減小，吞吐量繼續(xù)增加。

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

3.2 算法復(fù)雜度分析

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

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

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

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

通過分析異構(gòu)CR-UDN 模型中用戶規(guī)模、熱點(diǎn)區(qū)域用戶占比、信道數(shù)量、FBS 分布密度對(duì)系統(tǒng)總吞吐量和FU 總吞吐量的影響，本文算法在收斂速度、計(jì)算復(fù)雜度上要優(yōu)于文獻(xiàn)［16］的改進(jìn)遺傳算法，相較于傳統(tǒng)遺傳算法不易陷入局部最優(yōu)，在對(duì)異構(gòu)網(wǎng)絡(luò)的適應(yīng)性上要優(yōu)于二部圖+圖著色的分步優(yōu)化算法。

4 結(jié)語

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