基于混合遺傳算法的無線回傳網(wǎng)絡(luò)部署

張然++溫向明++路兆銘

摘要：隨著移動通信終端的爆發(fā)式增長和異構(gòu)蜂窩網(wǎng)絡(luò)的發(fā)展，無線回傳網(wǎng)絡(luò)的部署面臨著越來越多的挑戰(zhàn)。本文提出一種全新的小區(qū)內(nèi)無線回傳部署模型，該模型同時考慮回傳網(wǎng)絡(luò)的可靠性和小區(qū)內(nèi)的能耗。通過混合遺傳算法（hybrid Generic Algorithm）對該模型進(jìn)行求解，得到最優(yōu)化的回傳網(wǎng)絡(luò)部署方案。仿真結(jié)果表明，本文所提的算法與其他算法相比具有較為明顯的優(yōu)勢。

關(guān)鍵詞：通信與信息系統(tǒng)；可靠性；無線回傳網(wǎng)絡(luò)；混合遺傳算法

中圖分類號：TP393

文獻(xiàn)標(biāo)識碼：A

DOI：10.3969/j.issn.1003-6970.2015.12.006

本文著錄格式：張然，溫向明，路兆銘.基于混合遺傳算法的無線回傳網(wǎng)絡(luò)部署[J].軟件，2015，36（12）：25-300

引言

21世紀(jì)以來隨著通信技術(shù)的不斷發(fā)展，社會經(jīng)濟(jì)發(fā)展水平與人們的生活品質(zhì)也在不斷提高。據(jù)全球移動通信系統(tǒng)聯(lián)盟（GSMA，Global System forMobile Communications Alliance）報告，到2020年移動互聯(lián)網(wǎng)用戶總數(shù)將達(dá)到38億，大約占據(jù)未來一半的全球人口。智能手機(jī)、平板電腦等終端的快速普及也帶來了數(shù)量龐大的用戶群體，隨著接入終端以及業(yè)務(wù)類型的增加，為了盡可能的覆蓋所有用戶對象并保障網(wǎng)絡(luò)性能，需要在小區(qū)中實(shí)現(xiàn)異構(gòu)蜂窩網(wǎng)絡(luò)的部署。異構(gòu)蜂窩網(wǎng)絡(luò)的關(guān)鍵思想是在宏基站小區(qū)覆蓋范圍內(nèi)加入多個低發(fā)射功率小基站，這些基站擁有較小的發(fā)射功率和物理大小，通過這種方式可以增加一個地區(qū)的小區(qū)數(shù)，提高單位面積的頻譜效率，這樣就增加了蜂窩網(wǎng)絡(luò)的系統(tǒng)容量，并且降低了宏基站的負(fù)載。當(dāng)前無線業(yè)務(wù)需求以指數(shù)快速增長，這就要求了蜂窩系統(tǒng)的不斷擴(kuò)容。宏基站較大的發(fā)射功率和物理大小以及能安裝的地理位置限制，導(dǎo)致存在一些地理區(qū)域的信號強(qiáng)度很小，甚至出現(xiàn)中斷。各種小基站的覆蓋和擴(kuò)展能夠以非常低的成本完成對整個區(qū)域的無縫覆蓋。

日益增多的小基站給用戶帶來更加完善接入，同時也帶來另外的問題。大量小基站的密集部署，使得連接基站和核心網(wǎng)的移動回傳網(wǎng)絡(luò)結(jié)構(gòu)趨于多層次和復(fù)雜化。如何連接小基站到核心網(wǎng)以及蜂窩小區(qū)回傳網(wǎng)絡(luò)部署的目標(biāo)是什么，這些都是在異構(gòu)蜂窩網(wǎng)絡(luò)規(guī)劃中首先要考慮的問題。移動回傳網(wǎng)絡(luò)作為移動網(wǎng)絡(luò)中重要的組成，一旦失效或者故障將會影響大量用戶的正常通信。因此在研究未來小基站密集部署的環(huán)境下，如何對無線回傳網(wǎng)絡(luò)的部署進(jìn)行合理規(guī)劃具有重要的研究意義。這類網(wǎng)絡(luò)規(guī)劃問題一般從保障可靠性的規(guī)劃目標(biāo)出發(fā)，通常這類網(wǎng)絡(luò)規(guī)劃都規(guī)約為NP-complete問題。因此，設(shè)計出高效的網(wǎng)絡(luò)規(guī)劃算法是問題的關(guān)鍵。本文提出一種全新的以可靠性和能效為規(guī)劃目標(biāo)的網(wǎng)絡(luò)規(guī)劃模型。下面詳細(xì)描述所提出的問題，并在后續(xù)的仿真中將所提遺傳算法與其他可行的算法進(jìn)行對比研究。

1 系統(tǒng)模型

回傳網(wǎng)絡(luò)的連接方式一般有有線光纖連接和毫米波、微波無線連接方式，本問題的場景圖如Fig.2所示，宏基站利用光纖實(shí)現(xiàn)有線回傳，小基站與宏基站之間利用無線回傳方式連接。在一個宏基站小區(qū)內(nèi)的無線回傳網(wǎng)絡(luò)定義為有向圖G=（V，E），其中包括有光纖回程的宏基站（編號為0），還有n個通過無線鏈路回程的小基站（編號為1，2，…，n，組成點(diǎn)集U）。整個宏基站小區(qū)拓?fù)涞泥徑泳仃嚍閇b_ij]（n+1）×（n+1）。這里假設(shè)回傳網(wǎng)絡(luò)拓?fù)涞男问綖闃湫谓Y(jié)構(gòu)，這也是回傳網(wǎng)絡(luò)最常見的拓?fù)浣Y(jié)構(gòu)。

2 遺傳算法概述

遺傳算法是20世紀(jì)70年代由密歇根大學(xué)的John Holland提出的，它的主要思想基于達(dá)爾文的適者生存，可以把遺傳算法看做生物的進(jìn)化過程，首先對問題所求的解進(jìn)行編碼，這些編碼即是個體的染色體基因，將求解空間表示成由各種染色體個體組成的種群。針對種群進(jìn)行一系列自然選擇，交叉，變異操作，經(jīng)過一代代的進(jìn)化，逐步提高種群個體的適應(yīng)值，最終獲得符合要求的解。

2.1 遺傳算法的求解流程

2.1.1 問題解的編碼

編碼是設(shè)計遺傳算法的第一步，也是極為重要的一步。在應(yīng)用過程中，編碼方式大致可分為三類：二進(jìn)制編碼，浮點(diǎn)數(shù)編碼，符號編碼。在本文的問題中，采用符號編碼方式獲得較低維度的解編碼。

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

遺傳算法搜索就是根據(jù)適應(yīng)度函數(shù)值來對染色體進(jìn)行評估。在很多遺傳算子的操作中會用到適應(yīng)度值。適應(yīng)度函數(shù)通常都是算法的目標(biāo)函數(shù)，或者與目標(biāo)函數(shù)有關(guān)。適應(yīng)度函數(shù)值愈大表示該個體的適應(yīng)程度愈好，被遺傳到下一代的可能性更高。

2.1.3 遺傳算子

遺傳操作通常有三種：選擇，交叉，變異。通過這三種算子的操作保證進(jìn)化的下一代的個體攜帶更加優(yōu)良的基因編碼，更加接近問題的最優(yōu)解。具體的操作過程如下所述：

（l）選擇算子

選擇算子體現(xiàn)進(jìn)化過程中自然選擇的特點(diǎn)，把當(dāng)前代種群的優(yōu)秀個體保存到下一代中。同時，淘汰了種群中適應(yīng)度差的個體，選擇算子根據(jù)適應(yīng)度函數(shù)值執(zhí)行選擇操作。以下是經(jīng)常用到的選擇算子操作方法：

輪盤賭算法，該方法求出個體與所有個體適應(yīng)

最佳個體保存法，這種方法將群體中適應(yīng)度高的個體直接保存到下一代種群中，這樣操作可以保證交叉和變異不會破壞適應(yīng)函數(shù)值較高的個體。

（2）交叉算子

交叉算子是指把父代個體的染色體對應(yīng)的基因進(jìn)行交換或者覆蓋操作以便獲取基因重組，然后能獲得子代的新的染色體。單點(diǎn)交叉是常見的交叉算子，當(dāng)使用二進(jìn)制編碼時，單點(diǎn)交叉操作如下圖所示：

（3）變異算子

變異算子在遺傳算法中相當(dāng)重要。前面提及的交義算子的豐要作用是用來牛成新的子代個體，這樣交義算子可以保證遺傳算法在整個種群中的搜索能力。當(dāng)采用二進(jìn)制編碼時，其具體操作如下圖所示：

2.1.4 終止條件

遺傳算法需要預(yù)先設(shè)定終止條件來判斷進(jìn)化過程是否結(jié)束。終止條件可以可以設(shè)定為種群的平均適應(yīng)度值或者最優(yōu)的適應(yīng)度函數(shù)值的變化幅度，例如0.01，0.001等，也可以設(shè)定為種群的最大進(jìn)化代數(shù)。

3 無線回傳網(wǎng)絡(luò)部署問題的遺傳算法設(shè)計

遺傳算法可以有效地解決大部分最優(yōu)化問題，但是在某些情況下，標(biāo)準(zhǔn)的遺傳算法容易出現(xiàn)早熟，局部搜索能力差等問題。在上述模型中，約束條件首先要求保證所有解對應(yīng)的是樹形拓?fù)?，并且含有樹的度約束和高度約束條件，還要符合發(fā)射功率的限制條件。這些的約束條件對于遺傳算法的應(yīng)用帶來了很大的挑戰(zhàn)，如何合理處理約束條件，在可行解域提高搜索效率并且保證搜索的健壯性是求解這個問題的關(guān)鍵。有些學(xué)者提出了混合遺傳算法，比如將爬山法，模擬退火算法等加入到遺傳算法的某一步驟中，這種與遺傳算法的互補(bǔ)結(jié)合來解決約束條件顯示出比標(biāo)準(zhǔn)遺傳算法更優(yōu)越的性能。

3.1 基于Prufer的編碼

Cayley定理告訴我們有n個頂點(diǎn)的完全圖，它的生成樹有n^n-1個。Prufer對n-2個l～n的數(shù)的排列與樹的一一對應(yīng)關(guān)系給出了結(jié)構(gòu)化的證明。每一組Prufer數(shù)都對應(yīng)著獨(dú)一無二的一棵樹。因此，再進(jìn)行交叉，變異這些遺傳算子操作時，所得到的還是一棵樹，在不考慮其他約束條件（例如，度的限制，高度的限制等）不會產(chǎn)生不可行解。

從樹到Prufer的編碼過程如下：

Stepl）對樹T的n個節(jié)點(diǎn)進(jìn)行編碼

Step2）選擇樹T中編號最小的葉子節(jié)點(diǎn)i，寫出與它相連的節(jié)點(diǎn)j.把j的編號作為編碼的第一位，這里是從左往右進(jìn)行編碼

Step3）刪除節(jié)點(diǎn)i以及與i相連的邊

Step4）重復(fù)上述操作直到只有一條邊為止

從以上樹T的Prufer數(shù)（編碼）知，樹T中頂點(diǎn)i的度等于i在樹T的Prufer數(shù)中出現(xiàn)的次數(shù)加一。下圖是一個編碼Prufer數(shù)的例子，這棵樹T所對于的Prufer數(shù)P=（66551）。首先頂點(diǎn)2是最小的葉子，頂點(diǎn)6和2相連，這樣6是Prufer數(shù)中第一個數(shù)；然后從T中刪除點(diǎn)2和邊（2，6），重復(fù)這一過程直到剩下邊（l，7）

從Prufer到樹的解碼過程：

Step l）P是原始的Prufer序列碼，是沒有出現(xiàn)在Prufer序列碼中的節(jié)點(diǎn)的集合。

Step 2）假設(shè)j是中編號最小所對應(yīng)的節(jié)點(diǎn)，k是P中最左邊編號所對應(yīng)的節(jié)點(diǎn)，將j和k相連，并將其在所在集合中刪去。重復(fù)操作直到P集合中沒有編碼。

Step 3）如果沒有編碼在P集合中，應(yīng)該在中還有兩個點(diǎn)集r和s，并將r和s相連接，這樣就構(gòu)成了n-l條邊的樹。

運(yùn)用以上的步驟將Prufer數(shù)P=（6 6 5 5 1）解碼成上圖的一棵樹。因?yàn)轫旤c(diǎn)2，3，4和7不包括在P中，因此=（2 3 4 7），注意到中最小的數(shù)字是2，P中最左邊的數(shù)字是6，因而把變（2，6）添加到樹中。同時從中刪除點(diǎn)2，P中刪除6，這樣剩下的P=（6 5 5 1），=（3 4 7）。重復(fù)以上過程直到P為空，最好把中剩余的1和7作為邊（1，7）加到樹中就構(gòu)成了上圖。

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

遺傳算法求解非約束型問題的求解應(yīng)用廣泛，但是對于本文問題中的約束條件處理存在一定的難度。等式約束條件由于編碼方式的選擇已經(jīng)得到了保證，關(guān)鍵在于不等式約束條件的處理，常見的對約束條件的處理，有罰函數(shù)法，對不可行解的拒絕策略，對遺傳算子進(jìn)行改進(jìn)從而將不可行解轉(zhuǎn)變?yōu)榭尚薪狻Ｍǔ２捎昧P函數(shù)的方法，該方法將背離約束條件的程度用罰函數(shù)來表示，將其加到適應(yīng)度函數(shù)后面，從而將有約束問題轉(zhuǎn)化為無約束問題。在本章所提的模型當(dāng)中，約束條件（4）（5）（6）有很多，而且樹形拓?fù)涞募s束條件很難選擇合適的罰函數(shù)對約束背離程度進(jìn)行合理的度量，這也是罰函數(shù)法處理多約束最優(yōu)化問題的局限性。第一種方式，對不可行解的拒絕策略等減少了種群的多樣性，這樣不利于算法的全局搜索，容易出現(xiàn)早熟現(xiàn)象。第二種處理方式，改進(jìn)算子增加了算法的不確定性，而且改進(jìn)算子的單一化也容易導(dǎo)致算法搜索方向的單一性。為了將遺傳算法合理地應(yīng)用到本章的問題當(dāng)中，結(jié)合模擬退火算法，提出一種退火函數(shù)，將其添加到適應(yīng)度函數(shù)當(dāng)中，通過模擬退火方式來自動調(diào)節(jié)不可行解的懲罰，這是一種混合遺傳算法。

模擬退火借用了統(tǒng)計力學(xué)的思想，目標(biāo)函數(shù)類比于系統(tǒng)的內(nèi)能E，引入?yún)⒖紲囟萒。初始化時，令T取一個較大的值，如果AEO，則以概率

隨著種群個體的不斷更新演進(jìn)，退火溫度呈幾何級數(shù)降低，最終導(dǎo)致不符合約束條件的解將被舍棄。同時，當(dāng)算法剛開始執(zhí)行時，為了保證種群的多樣性，不舍棄但是具有潛力的不可行解，這些解將會參與種群的演進(jìn)過程而被充分利用。這樣的做法，即處理了數(shù)量較多的約束條件，又保證了種群的多樣性，防止陷入局部最優(yōu)解當(dāng)中。

本問題算法過程如下：

4 仿真分析

4.1 仿真環(huán)境和參數(shù)配置

問題的仿真環(huán)境是基于MATLAB 2013a，運(yùn)行在Pentium 4 CPU，4GB內(nèi)存的PC機(jī)上，算法采用了MATLAB中的遺傳算法工具箱。

4.2 仿真結(jié)果分析

本文將所提算法的通過與其他算法（分支定界，粒子群）對比，得到下面的仿真結(jié)果圖： 上圖描述了采用不同算法的情況下，小區(qū)內(nèi)無線回傳網(wǎng)絡(luò)平均吞吐量（Throughp ut Expectation）與小區(qū)內(nèi)基站部署數(shù)目之間的關(guān)系。從圖中可以看出，平均吞吐量（Throughput Expectation）隨著小區(qū)內(nèi)的基站數(shù)目呈明顯的增加趨勢。此外，通過三種算法的對比，可以明顯看出本文采用的算法所部屬的網(wǎng)絡(luò)總的功耗（Throughput Expectation）更大，優(yōu)于其他的兩種算法（分支邊界、粒子群）。

在上圖中，隨著小區(qū)內(nèi)的基站數(shù)目的增加，小區(qū)總的能效（Energy Efficiency）也在增加，這也說明大規(guī)模部署小基站帶來提高小區(qū)內(nèi)的能效這一顯著的優(yōu)勢。另一方面，與其他兩種算法相比，本文所提算法能夠能效更高，具有更明顯的優(yōu)勢。

5 結(jié)論

本文給出了一種基于混合遺傳算法（hybridgenetic algorithin）的無線回傳網(wǎng)絡(luò)部署方法。在獲得基站各項(xiàng)參數(shù)和信道傳播特性的條件下，建立無線回傳網(wǎng)絡(luò)部署的0-1整數(shù)規(guī)劃模型，將問題轉(zhuǎn)化為搜索0-1整數(shù)空間的最優(yōu)解。針對所建立模型的特點(diǎn)，提出了一種新型的遺傳算法，通過該算法，模型解空間中原先的0-1編碼變?yōu)榛赑rufer的編碼，大大減少了最優(yōu)解搜索的難度，同時利用模擬退火解決解對約束條件的滿足問題，進(jìn)而得出了符合收斂條件的近似最優(yōu)解。為了驗(yàn)證算法的性能，搭建仿真環(huán)境進(jìn)行了實(shí)驗(yàn)。實(shí)驗(yàn)表明本文所提算法在無線回傳網(wǎng)絡(luò)部署中，可以明顯提高小區(qū)內(nèi)回傳網(wǎng)絡(luò)的可靠性，同時也保障了回傳網(wǎng)絡(luò)可靠性與小區(qū)能耗之間的平衡。