晁迎，覃錫忠，曹傳玲，鄧?yán)?，劉漢興

(1.新疆大學(xué)信息科學(xué)與工程學(xué)院，新疆烏魯木齊830046；2.中國(guó)移動(dòng)通信集團(tuán)新疆有限公司，新疆烏魯木齊830063)

0 引言

移動(dòng)互聯(lián)網(wǎng)迅速發(fā)展，移動(dòng)用戶數(shù)量飛速增長(zhǎng)，為了獲得更好的通信服務(wù)質(zhì)量，移動(dòng)通信網(wǎng)絡(luò)需要不斷的擴(kuò)展和延伸，必須建設(shè)大量的新基站，基站分布的規(guī)劃優(yōu)化成了一個(gè)重要的問(wèn)題.合理的分布規(guī)劃能夠降低成本、提高服務(wù)質(zhì)量.

目前國(guó)內(nèi)外研究人員提出了很多方法來(lái)優(yōu)化基站分布.文獻(xiàn)[1]提出了一種基于粒子群算法（Particle Swarm Optimization Algorithm,PSO）的規(guī)劃方法，該算法應(yīng)用在較小網(wǎng)絡(luò)規(guī)模上能提高優(yōu)化效率，但對(duì)于較大網(wǎng)絡(luò)規(guī)模的規(guī)劃效果不理想.文獻(xiàn)[2]采用了傳統(tǒng)遺傳算法，雖然傳統(tǒng)遺傳算法解決了多目標(biāo)優(yōu)化規(guī)劃問(wèn)題，具有全局尋優(yōu)的優(yōu)勢(shì)，但是也存在容易陷入局部最優(yōu)解的問(wèn)題，算法運(yùn)行的速度慢造成算法效率較低.文獻(xiàn)[3]提出一種將多目標(biāo)優(yōu)化問(wèn)題轉(zhuǎn)化為單目標(biāo)的方法，考慮覆蓋率、業(yè)務(wù)量和成本等影響因素，但是沒(méi)有考慮環(huán)境干擾因素，得出的規(guī)劃方案不能滿足實(shí)際要求.文獻(xiàn)[4]提出了基于免疫計(jì)算的方法,雖具有全局尋優(yōu)的優(yōu)勢(shì)，但是該算法的優(yōu)化時(shí)間性能較差.這些算法的應(yīng)用雖然為基站位置分布優(yōu)化研究奠定了一定的基矗 但是在優(yōu)化精度、效率方面仍有不足，算法容易陷入局部最優(yōu)，不易找到全局最優(yōu)值，全局優(yōu)化穩(wěn)健性不高.文獻(xiàn)[5]提出一種網(wǎng)絡(luò)基站選址優(yōu)化方案，雖然算法有效，較小的建站成本，但是不能獲得更高的網(wǎng)絡(luò)覆蓋率.

加速遺傳算法是遺傳算法的改進(jìn)，表現(xiàn)出比遺傳算法更好的特性，用于多目標(biāo)優(yōu)化具有很強(qiáng)的優(yōu)勢(shì).加速遺傳算法在解決非線性問(wèn)題時(shí)與其它算法相比具有尋優(yōu)速度快，不易陷入局部最優(yōu)，優(yōu)化精度高，全局穩(wěn)健性高等優(yōu)點(diǎn).文章利用加速遺傳算法在解決多目標(biāo)優(yōu)化問(wèn)題上的靈活性，提出了一種網(wǎng)絡(luò)基站分布規(guī)劃方法.為了設(shè)計(jì)出更符合工程實(shí)際的規(guī)劃方法，本文在綜合考慮網(wǎng)絡(luò)覆蓋和干擾因素影響的基礎(chǔ)上，設(shè)計(jì)了基站規(guī)劃多目標(biāo)組合優(yōu)化模型，并利用加速遺傳算法求解最優(yōu)規(guī)劃方案.仿真表明，加速遺傳算法在解決復(fù)雜優(yōu)化問(wèn)題時(shí)是極其有效的，能夠得到較優(yōu)的基站位置分布方案.

1 基于加速遺傳算法的基站分布規(guī)劃建模

1.1 加速遺傳算法

加速遺傳算法(Accelerating Genetic Algorithm,AGA)是一種仿生學(xué)算法，其原理是模仿生物界中的“物競(jìng)天擇，適者生存”的演化法則，擁有搜索能力強(qiáng)、收斂性好等優(yōu)點(diǎn)，同時(shí)算法對(duì)建立數(shù)學(xué)模型的要求較低，已經(jīng)廣泛應(yīng)用于實(shí)際優(yōu)化問(wèn)題中[6].遺傳算法的基本思想是在初始變化區(qū)間內(nèi)隨機(jī)生成一組父代個(gè)體作為初始解，經(jīng)過(guò)選擇、雜交及變異，生成子代個(gè)體，通過(guò)目標(biāo)函數(shù)評(píng)價(jià)個(gè)體的好壞，優(yōu)勝劣汰產(chǎn)生優(yōu)秀個(gè)體，并作為新的父代個(gè)體，如此循環(huán)迭代，使個(gè)體的適應(yīng)度能力不斷提高，不斷向最優(yōu)點(diǎn)逼近.加速遺傳算法是遺傳算法的改進(jìn)算法，增強(qiáng)了遺傳算法的自適應(yīng)尋優(yōu)功能，它克服了遺傳算法對(duì)搜索空間差、計(jì)算量大、容易出現(xiàn)早熟收斂、全局優(yōu)化速度較慢等實(shí)際問(wèn)題.它利用在運(yùn)行過(guò)程中產(chǎn)生的優(yōu)秀個(gè)體，逐步調(diào)整優(yōu)化變量搜索范圍[6,7].本文基于加速遺傳算法建立基站分布規(guī)劃模型.

1.2 基站分布規(guī)劃模型的建立

在保證網(wǎng)絡(luò)覆蓋的前提下，如何盡可能降低成本是網(wǎng)絡(luò)規(guī)劃問(wèn)題的關(guān)鍵.本文著重分析移動(dòng)通信網(wǎng)絡(luò)中的基站分布規(guī)劃問(wèn)題.

(1)基站分布規(guī)劃問(wèn)題：多目標(biāo)優(yōu)化問(wèn)題是多個(gè)優(yōu)化目標(biāo)在約束條件下同時(shí)得到最佳的解[8]，基站分布規(guī)劃就是要尋找各種影響因素的最優(yōu)組合解，即在所有的待定參數(shù)中找到滿足約束條件的解.考慮到多目標(biāo)優(yōu)化問(wèn)題的復(fù)雜性，將總體目標(biāo)函數(shù)設(shè)置為各種影響因素的加權(quán)，這樣就簡(jiǎn)化為單目標(biāo)優(yōu)化問(wèn)題.因此如果算法在得到較大目標(biāo)函數(shù)值的同時(shí)時(shí)間復(fù)雜度越校 說(shuō)明算法越合理.在基站選址過(guò)程中，合理的基站分布是保證網(wǎng)絡(luò)性能和服務(wù)質(zhì)量的關(guān)鍵，同時(shí)要充分兼顧未來(lái)網(wǎng)絡(luò)的發(fā)展，以便于分期建設(shè)滿足不同時(shí)期用戶的需求.目前，考慮的影響因素有建網(wǎng)成本、網(wǎng)絡(luò)覆蓋率、業(yè)務(wù)量、信號(hào)頻率等.網(wǎng)絡(luò)覆蓋率越高，網(wǎng)絡(luò)性能越好.外界電磁干擾如微波通信、直放站等是影響網(wǎng)絡(luò)質(zhì)量的一個(gè)重要因素，會(huì)產(chǎn)生通話質(zhì)量差、上網(wǎng)速度慢的問(wèn)題.因此，外界電磁干擾和覆蓋率是基站分布規(guī)劃問(wèn)題的首要考慮因素，要求網(wǎng)絡(luò)具有最小干擾和最大覆蓋率.加速遺傳算法能夠利用種群進(jìn)化在問(wèn)題空間中進(jìn)行大規(guī)模搜索，在較短的時(shí)間內(nèi)找到最優(yōu)解，目前已經(jīng)被應(yīng)用在各個(gè)領(lǐng)域.

(2)基站分布規(guī)劃的建模

隨機(jī)設(shè)置基站初始位置，通過(guò)加速遺傳算法的尋優(yōu)過(guò)程，在適應(yīng)度函數(shù)取得最優(yōu)解時(shí)得到每個(gè)基站分布參數(shù).基站規(guī)劃區(qū)域是二維平面，在該區(qū)域上規(guī)劃N個(gè)基站，且半徑均為r,每個(gè)基站的覆蓋模型可以表示為以節(jié)點(diǎn)坐標(biāo)為圓心，r為半徑的圓.基站點(diǎn)集為Ci=(c1,c2,...,cN)，其中ci為第i個(gè)基站的覆蓋模型，(xj,yj)是第j個(gè)基站的坐標(biāo)，將點(diǎn)(x,y)被基站所覆蓋的事件定義為ri,該事件發(fā)生的概率P{ri}為點(diǎn)(x,y)被基站所覆蓋的概率p{ri}=p(x,y,ci),此概率為一個(gè)二值函數(shù)，即

若點(diǎn)(x,y)到第i個(gè)基站的距離不大于r,該點(diǎn)(x,y)被基站覆蓋，且：

其中為ri的補(bǔ)，表示(x,y)沒(méi)有被基站i所覆蓋這一事件，如果ri和rj無(wú)關(guān)，則：

只要有一個(gè)基站覆蓋了點(diǎn)(x,y)，就認(rèn)為該點(diǎn)被覆蓋.所以，點(diǎn)(x,y)被基站集覆蓋的概率為ri的并集，則基站集C的覆蓋率可以用(4)式表示計(jì)算：

式(4)表明，如果所有的基站都沒(méi)有覆蓋到點(diǎn)(x,y),點(diǎn)(x,y)為未被覆蓋點(diǎn)，否則，便認(rèn)為點(diǎn)(x,y)被基站集覆蓋.

其中，?S為網(wǎng)格單位面積，S為網(wǎng)格總面積之和，N為網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù).

電磁波的速度采用光速c，在真空中的傳播速度約為3×108m/s，其計(jì)算公式如下：

電磁波在自由空間傳輸時(shí)，其強(qiáng)度因能量的擴(kuò)散而衰減，在距離d2l.i處，天線的輻射功率密度ρ為：

接收天線所接收的發(fā)射點(diǎn)之和，其計(jì)算方法如公式(7)：

其中N為節(jié)點(diǎn)總數(shù)，Pi為節(jié)點(diǎn)i所受到其它發(fā)射節(jié)點(diǎn)干擾之和，Pt為節(jié)點(diǎn)發(fā)射功率，Gtx為增益系數(shù)且為1為發(fā)射節(jié)點(diǎn)與節(jié)點(diǎn)i之間的歐氏距離.區(qū)域干擾定義為

N為發(fā)射、接收兩節(jié)點(diǎn)連線所經(jīng)過(guò)的區(qū)域的個(gè)數(shù).

干擾率目標(biāo)函數(shù)為

本文適應(yīng)度函數(shù)如下：

其中w1為覆蓋率的權(quán)重系數(shù)；w2為覆蓋區(qū)域的干擾的權(quán)重系數(shù).

1.3 算法實(shí)現(xiàn)

加速遺傳算法包括以下幾個(gè)步驟：

步驟1：初始化空間的離散與編碼：a為編碼的長(zhǎng)度，則a位二進(jìn)制串,可以表示2a個(gè)數(shù)，將定義范圍離散為2a均等的區(qū)域.經(jīng)編碼后，變量的搜索范圍離散成了(2a)b個(gè)網(wǎng)格點(diǎn),它對(duì)應(yīng)b個(gè)變量的可能的一種取值狀態(tài).

步驟2:群體初始化：群體每個(gè)個(gè)體參數(shù)是在初始范圍內(nèi)產(chǎn)生的隨機(jī)數(shù)，使得在演化迭代前期保持充分搜索范圍.利用編碼映射，建立加速遺傳算法中的初始群體.設(shè)目標(biāo)區(qū)域?yàn)?

其中，L和W分別為目標(biāo)區(qū)域的長(zhǎng)和寬.種群由M個(gè)體組成，算法中的每個(gè)個(gè)體的染色體均由N個(gè)基因組構(gòu)成.

初始化種群為：

步驟3:復(fù)制和選擇：在復(fù)制過(guò)程中個(gè)體位串根據(jù)目標(biāo)函數(shù)進(jìn)行自我復(fù)制.復(fù)制的第一步是計(jì)算適應(yīng)度.本文中每個(gè)個(gè)體的適值即是其目標(biāo)函數(shù)，如式(8)所示.在簡(jiǎn)單遺傳算法中，通常采用隨機(jī)選擇法，本文采用輪盤(pán)賭法，其結(jié)構(gòu)如下：獨(dú)立的候選解圍成一個(gè)圈，每個(gè)個(gè)體被挑選的概率與個(gè)體的適值成正比.

步驟4:交叉：將產(chǎn)生的個(gè)體位串隨機(jī)兩兩配對(duì)；隨機(jī)選擇交叉點(diǎn)，對(duì)配對(duì)的位串進(jìn)行交叉繁殖，產(chǎn)生一對(duì)新的位串.首先我們?cè)O(shè)置一個(gè)10位的二進(jìn)制比特串，10位代表位置劃分為十個(gè)格子（通過(guò)算法，可以反推出二維空間的位置），1代表在這個(gè)格子上有基站分布.那么有基站的位置序號(hào)為：父本為2,4,5,8,9,母本為3,4,6,8,10.隨機(jī)生成一個(gè)數(shù)（0-1）小于交叉概率Pc，則進(jìn)行交叉，交叉點(diǎn)這樣設(shè)置找出位置序號(hào)重合的位置序號(hào).比如位置8，然后進(jìn)行交叉.

父本

母本

父本為2,4,5,8,10，母本為3,4,6,8,9，則變?yōu)椋?/p>

父本

母本

步驟5：變異：從一個(gè)舊種群中選擇生命力弱（選擇概率校 的個(gè)體位串產(chǎn)生新種群的過(guò)程.

生成一個(gè)隨機(jī)數(shù)，如果小于變異系數(shù)，則我們?nèi)我馓暨x為1的基站序號(hào)，如1,2,8,9中的5，讓5的網(wǎng)格為0再剩下為0網(wǎng)格的位置任意挑選一個(gè)變成1.生成新序列為：

步驟6：加速循環(huán)：標(biāo)準(zhǔn)遺傳算法受初始區(qū)間影響很大，假如能隨進(jìn)化而逐漸縮小搜索范圍可使搜索速率加快.加速遺傳算法就是搜索到的優(yōu)秀個(gè)體的子群體來(lái)調(diào)整搜索范圍的.每一次加速循環(huán)中，根據(jù)目標(biāo)函數(shù)值，選出優(yōu)秀個(gè)體的百分之二十，交叉然后生成子代再變異.

2 仿真結(jié)果與分析

為了驗(yàn)證算法的正確性，對(duì)100km×100km目標(biāo)區(qū)域進(jìn)行規(guī)劃.每個(gè)基站覆蓋區(qū)域?yàn)閳A形，采用自由空間傳播模型，經(jīng)計(jì)算可得出覆蓋半徑為11km.算法的參數(shù)設(shè)置為：種群規(guī)模為100，進(jìn)化代數(shù)為100，交叉概率為0.9，變異概率為0.1，w1和w2為相應(yīng)的目標(biāo)函數(shù)對(duì)應(yīng)的權(quán)值，對(duì)于不同的應(yīng)用場(chǎng)合可以選取不同的權(quán)值[3]，w1+w2=1[4]，根據(jù)選取的不同權(quán)值，通過(guò)式(11)評(píng)價(jià)基站分布方案優(yōu)劣，目標(biāo)函數(shù)f1的權(quán)重系數(shù)為0.9，目標(biāo)函數(shù)f2的權(quán)重系數(shù)為0.1.仿真結(jié)果如圖1，圖2.

圖1 傳統(tǒng)算法優(yōu)化的基站分布

圖2 加速遺傳算法優(yōu)化的基站分布

為了驗(yàn)證加速遺傳算法的性能，將它與傳統(tǒng)退火算法進(jìn)行對(duì)比實(shí)驗(yàn)，在同樣實(shí)驗(yàn)仿真環(huán)境下，兩種算法的目標(biāo)函數(shù)值迭代次數(shù)的變化比較如圖3所示.

圖3 加速遺傳算法和傳統(tǒng)算法適應(yīng)度比較

圖4 兩種算法的50次最優(yōu)值的比較

從圖1，2可以看出，傳統(tǒng)算法優(yōu)化的基站的覆蓋率很低，加速遺傳算法優(yōu)化基站的覆蓋率比較高，說(shuō)明應(yīng)用加速遺傳算法得到的基站位置分布更合理；從圖3可以看出，加速遺傳算法的適應(yīng)度值比傳統(tǒng)算法的適應(yīng)度值明顯高很多，說(shuō)明其全局尋優(yōu)能力強(qiáng)，不易陷入局部最優(yōu)；從圖3可以看出，加速遺傳算法的收斂速度比傳統(tǒng)算法的收斂速度快，最優(yōu)適應(yīng)值較大，能夠找到與網(wǎng)絡(luò)建設(shè)要求相符合的最優(yōu)規(guī)劃方案；從圖4可以看出，經(jīng)過(guò)50次最優(yōu)值的比較，加速遺傳算法的適應(yīng)度值大，最優(yōu)解比較穩(wěn)定.

3 結(jié)論

為了能夠獲得更好的通信網(wǎng)絡(luò)服務(wù)質(zhì)量，本文提出一種基于加速遺傳算法的基站規(guī)劃優(yōu)化方法，該方法在基站分布規(guī)劃中同時(shí)考慮覆蓋率和干擾兩個(gè)因素，設(shè)計(jì)了具體的實(shí)現(xiàn)流程，在同樣的參數(shù)條件下，進(jìn)行了仿真和對(duì)比試驗(yàn).加速遺傳算法的優(yōu)化過(guò)程包含了復(fù)制、交叉、變異等，使得搜索效率提高了許多，迅速的得到最優(yōu)解.仿真結(jié)果表明規(guī)劃方法的有效性，加速遺傳算法能夠找到與無(wú)線網(wǎng)絡(luò)建設(shè)要求相符合的基站位置分布方案，與傳統(tǒng)規(guī)劃優(yōu)化方法相比，基于加速遺傳算法的基站分布規(guī)劃得到的適應(yīng)度值更大，收斂速度更快，具有全局尋優(yōu)優(yōu)勢(shì)，優(yōu)化時(shí)間性能較好，優(yōu)化方案中的基站分布更合理，網(wǎng)絡(luò)服務(wù)質(zhì)量得到顯著提高，具有重要的實(shí)用價(jià)值和進(jìn)一步研究的意義.