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

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

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

中圖分類號(hào)：TP393

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

DOI：10.3969/j.issn.1003-6970.2015.12.006

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

引言

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

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

1 系統(tǒng)模型

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

2 遺傳算法概述

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

2.1 遺傳算法的求解流程

2.1.1 問(wèn)題解的編碼

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

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

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

2.1.3 遺傳算子

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

（l）選擇算子

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

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

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

（2）交叉算子

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

（3）變異算子

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

2.1.4 終止條件

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

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

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

3.1 基于Prufer的編碼

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

從樹(shù)到Prufer的編碼過(guò)程如下：

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

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

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

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

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

從Prufer到樹(shù)的解碼過(guò)程：

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

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

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

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

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

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

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

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

本問(wèn)題算法過(guò)程如下：

4 仿真分析

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

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

4.2 仿真結(jié)果分析

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

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

5 結(jié)論

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