李道國，李連杰

(1.杭州電子科技大學(xué)信息工程學(xué)院，浙江 杭州 310018；2.杭州電子科技大學(xué)管理學(xué)院，浙江 杭州 310018)

?

基于混合免疫算法的TD-LTE網(wǎng)絡(luò)基站選址研究

李道國1，李連杰2

(1.杭州電子科技大學(xué)信息工程學(xué)院，浙江 杭州 310018；2.杭州電子科技大學(xué)管理學(xué)院，浙江 杭州 310018)

TD-LTE網(wǎng)絡(luò)基站選址優(yōu)化是提高移動(dòng)通信服務(wù)質(zhì)量，降低建站成本的重要手段.首先概述了TD-LTE網(wǎng)絡(luò)基站選址應(yīng)該遵循的原則、目標(biāo)和主要的方法以及所面臨的困難，進(jìn)而剖析了TD-LTE網(wǎng)絡(luò)基站選址經(jīng)典模型存在的一些不足，通過融合協(xié)同進(jìn)化算法和人工免疫算法的優(yōu)點(diǎn)，提出了一種新穎的TD-LTE基站選址優(yōu)化協(xié)同進(jìn)化免疫算法LCIA.仿真結(jié)果表明，與經(jīng)典的協(xié)同算法和人工免疫算法相比，建站成本更低、網(wǎng)絡(luò)覆蓋率和網(wǎng)絡(luò)容量更高，且具有更好的收斂性.

TD-LTE網(wǎng)絡(luò)基站；協(xié)同進(jìn)化算法；人工免疫算法；混合免疫算法

0　引　言

近年來，4G網(wǎng)絡(luò)的技術(shù)研究正在緊鑼密鼓地進(jìn)行[1].2013年12月，工信部向中國移動(dòng)、中國電信以及中國聯(lián)通發(fā)放了TD-LTE牌照，正式開啟了我國的4G時(shí)代.由于在2G與3G時(shí)代，已經(jīng)建立了非常多的基站，通信業(yè)務(wù)量不斷增加，人們對(duì)服務(wù)質(zhì)量的要求也越來越高，從而導(dǎo)致基站站址資源變得越來越稀缺.因此TD-LTE基站的選址優(yōu)化問題成為國內(nèi)外研究者以及運(yùn)營商共同關(guān)注并且亟待解決的問題.

采用人工免疫算法求解基站選址問題時(shí)，雖然具有模型簡單、收斂速度快等優(yōu)點(diǎn)，但也存在收斂精度比較低、在解決大規(guī)模問題時(shí)易陷入局部最優(yōu)從而導(dǎo)致早熟收斂等缺點(diǎn)[2-3].為了避免算法出現(xiàn)過早收斂的情況，本文將協(xié)同進(jìn)化算法與免疫算法進(jìn)行混和，提出了分層協(xié)同進(jìn)化免疫算法(Layered Coevolution Immune Algorithm ，LCIA)，能夠加快求解時(shí)間，避免算法陷入早熟.在實(shí)際工程應(yīng)用中，為基站的選址提供了一種相對(duì)科學(xué)的方案.

1　TD-LTE基站選址優(yōu)化的數(shù)學(xué)模型

根據(jù)TD-LTE網(wǎng)絡(luò)基站的選址原則可知，選擇的站址要盡量滿足理想的蜂窩結(jié)構(gòu)，優(yōu)先考慮業(yè)務(wù)量大的地區(qū)，即熱點(diǎn)區(qū)域.為方便構(gòu)建模型，本文設(shè)定了4個(gè)假設(shè)：1)基站的選址區(qū)域不包括特殊的敏感區(qū)域，并且都是理想的無干擾平坦地形；2)在Matlab仿真條件下，設(shè)待選基站站址的集合為S={1,2,…,N}，測(cè)試點(diǎn)集合為Stest={1,2,…,M}；3)如果某個(gè)測(cè)試點(diǎn)被覆蓋，就表示熱點(diǎn)地區(qū)被覆蓋；4)對(duì)于TD-LTE網(wǎng)絡(luò)的容量，功率控制和碼資源十分充足.

在滿足以上4個(gè)假設(shè)的前提下，本文將多目標(biāo)的TD-LTE基站的選址問題分解為3個(gè)子目標(biāo).即在滿足覆蓋率盡可能高，容量盡可能大的前提下，成本盡可能低廉.假設(shè)成本函數(shù)為f1(x)，覆蓋函數(shù)為f2(x)，容量函數(shù)為f3(x).數(shù)學(xué)模型如下：

s.t.fi(x)≥Ni(i=1,2,3)，

(1)

式中，Ni表示對(duì)應(yīng)函數(shù)取值的下限.此問題的求解是尋找x={x1,x2,x3}，使得f(x)在滿足約束的同時(shí)達(dá)到最優(yōu).

第1個(gè)目標(biāo)函數(shù)是基站建設(shè)總代價(jià).為降低建站成本，優(yōu)先考慮可以與已有的2G/3G站點(diǎn)共站的情況.已知候選基站集為S={1,2,…,N}.基站i的建站代價(jià)為di(i∈D).已有基站為E={1,2,…,W}.已有基站j被選用共址的代價(jià)為ej(j∈E).測(cè)試點(diǎn)集為Stest={1,2,…,M}.候選基站i被選中的情況為xi∈{0,1}(i∈D).已有基站j被共址的情況為yj∈{0,1}(j∈D).建站成本目標(biāo)函數(shù)如下：包括新建基站的代價(jià)和2G/3G共址的代價(jià)：

(2)

第2個(gè)目標(biāo)函數(shù)是測(cè)試點(diǎn)的覆蓋率[4].若測(cè)試點(diǎn)k從基站i接到的信號(hào)強(qiáng)度大于某個(gè)閾值δ，則認(rèn)為該測(cè)試點(diǎn)k被基站i覆蓋.設(shè)每個(gè)基站的發(fā)射功率均為θ.基站i到測(cè)試點(diǎn)k的距離為lik.在傳播路徑上消耗的功率為λlik.測(cè)試點(diǎn)k被覆蓋情況為gk(k∈G)，即：

(3)

覆蓋率目標(biāo)函數(shù)為：

(4)

其中，m為測(cè)試點(diǎn)總的個(gè)數(shù).

第3個(gè)目標(biāo)函數(shù)是網(wǎng)絡(luò)容量，可表示為測(cè)試點(diǎn)可以容納的用戶數(shù).采用文獻(xiàn)[5]的方法進(jìn)行計(jì)算：

(5)

式中，R為信息速率.W為碼片速率.Eb/Io=比特能力/噪聲功率密度.s為接收信號(hào)功率.η為熱噪音.f=小區(qū)內(nèi)干擾/小區(qū)外干擾.Gv為話音活動(dòng)增益，Gs為扇區(qū)增益.

2　TD-LTE網(wǎng)絡(luò)基站選址模型的算法流程

2.1種群的初始化和編碼方案

對(duì)于本文給出的TD-LTE網(wǎng)絡(luò)基站選址模型，待選基站站址只有被選和未選兩種情況.因此本文采用二進(jìn)制編碼.抗體編碼Ab表示為：Ab=(b1,b2,…,bN).N是待選基站的個(gè)數(shù)，bi(i∈N)表示第i個(gè)基站的被選情況，即：

(6)

2.2抗體親和度評(píng)價(jià)函數(shù)

本文給出的TD-LTE基站選址模型是一個(gè)多目標(biāo)優(yōu)化模型.為了方便求解，采用權(quán)重法.為每一個(gè)子目標(biāo)設(shè)置一個(gè)權(quán)重值，將其轉(zhuǎn)換為單目標(biāo)問題求解.即抗體親和度評(píng)價(jià)函數(shù)為：

f(Ab)=φ1f1+φ2f2+φ3f3，

(7)

式中，φ1+φ2+φ3=1，φ1，φ2，φ3是各子目標(biāo)函數(shù)的權(quán)重系數(shù).f(Ab)∈[0,1].抗體親和度的值越大，基站選址的方案越好.

2.3抗體濃度調(diào)節(jié)

根據(jù)初始種群的編碼方式，將2個(gè)抗體的差異性，用抗體間的距離表示.本文采用了海明距離來計(jì)算抗體之間的距離[5].其計(jì)算公式如下：

(8)

如果抗體之間的距離D(Abp,Abq)<δ，Ne則表示兩個(gè)抗體相鄰.其公式如下：

(9)

抗體Abp=相鄰抗體數(shù)目/種群規(guī)模.其濃度Den的表達(dá)式如下：

(10)

其中，Psize為種群的規(guī)模.

2.4算子設(shè)計(jì)

為了提高算法的性能，克服早熟收斂等缺陷，本文對(duì)以下算子進(jìn)行了改進(jìn)：克隆擴(kuò)增、克隆變異、免疫選擇、最優(yōu)保存和種群更新操作等算子.下面簡要說明主要的算子設(shè)計(jì).

1)克隆擴(kuò)增算子qi

(11)

2)變異算子

就TD-LTE網(wǎng)絡(luò)基站選址優(yōu)化問題而言，本論文采用了Inver_over變異算子.文獻(xiàn)[3]的結(jié)論已經(jīng)證明了該方法較之傳統(tǒng)方法更具優(yōu)越性，比如：OX，PMX，CX等.

(12)

4)最優(yōu)保存算子

為了避免算法陷入早熟收斂，需要進(jìn)行最優(yōu)抗體保留.即對(duì)之前進(jìn)行了一系列操作的抗體，將其最優(yōu)的抗體進(jìn)行保留.

3　仿真實(shí)驗(yàn)與結(jié)果分析

3.1仿真實(shí)驗(yàn)參數(shù)設(shè)置

仿真實(shí)驗(yàn)環(huán)境設(shè)置：在一個(gè)區(qū)域內(nèi)，存在N=12個(gè)候選基站，候選基站集合S={1,2,…,12}；存在M=25個(gè)測(cè)試點(diǎn)，測(cè)試點(diǎn)集合Stest={1,2,…,25}.基站和測(cè)試點(diǎn)分布如圖1所示.其中綠色圓圈代表測(cè)試點(diǎn).藍(lán)色正方形的小方塊代表候選基站.

實(shí)驗(yàn)參數(shù)設(shè)置：種群規(guī)模為Psize=100.最大進(jìn)化代數(shù)為Gm=100.抗體編碼長度為D=30.抗體初始化概率為0.6.變異概率都為Pm=0.6.交叉概率都為Pc=0.6.抗體之間距離的閾值δ=30.記憶庫種群規(guī)模CM=30.克隆母體種群規(guī)模CL=60.克隆系數(shù)a=10.

3.2結(jié)果分析

采用本文中提出的LCIA算法，進(jìn)行TD-LTE網(wǎng)絡(luò)基站的選址仿真，最終得到基站站址方案如圖1所示.從圖1中可以看出，在12個(gè)候選基站中，選出了6個(gè)TD-LTE網(wǎng)絡(luò)基站，這6個(gè)基站的分布非常合理.

為了清楚地顯示改進(jìn)算法的優(yōu)越性，首先對(duì)算法的收斂性進(jìn)行對(duì)比.收斂性用算法的平均親和度來表示.將改進(jìn)后的算法和文獻(xiàn)[5]算法各自獨(dú)立運(yùn)行100次，收斂曲線如圖2所示.

圖1　基站站址分布圖

圖2　算法親和度函數(shù)值比較

從圖2可知，改進(jìn)的LCIA算法的平均親和度函數(shù)值高于文獻(xiàn)[5]算法.算法收斂速度更快.說明改進(jìn)后的算法在解決TD-LTE基站選址問題上面更加具有優(yōu)越性.

對(duì)于覆蓋率選用與文獻(xiàn)[6]算法進(jìn)行比較.根據(jù)TD-LTE基站的選址的子目標(biāo)，即在高覆蓋率的前提下成本最小，因此對(duì)成本與覆蓋率之間的關(guān)系進(jìn)行了比較，如圖3所示.

這里用選擇的基站個(gè)數(shù)作為基站的成本.從圖3中可以看出，在成本一定的條件下，改進(jìn)后的算法可以得到更高的覆蓋率.

本文用接入TD-LTE網(wǎng)絡(luò)基站的人數(shù)來評(píng)估容量函數(shù).對(duì)于容量函數(shù)，同樣用與文獻(xiàn)[6]算法進(jìn)行對(duì)比實(shí)驗(yàn).得到結(jié)果如圖4所示.

從圖4中可以看出，在覆蓋率一定的條件下，改進(jìn)后的算法能夠接入更多的用戶.說明本文算法比文獻(xiàn)[6]算法更優(yōu).

圖3　覆蓋率與基站個(gè)數(shù)的關(guān)系

圖4　覆蓋率與容量關(guān)系示意圖

4　結(jié)束語

本文通過構(gòu)建符合實(shí)際情況的TD-LTE網(wǎng)絡(luò)基站選址數(shù)學(xué)模型，對(duì)協(xié)同進(jìn)化算法與人工免疫算法進(jìn)行了混合研究.但本文僅僅考慮了成本、容量以及覆蓋面積三個(gè)方面的參數(shù)，沒有考慮其他參數(shù)對(duì)基站選址的影響.在后續(xù)的研究中，將更多的影響因素考慮在內(nèi)，使基站選址方案更加合理.

[1]張海軍,李欣.4G通信技術(shù)的研究與應(yīng)用[J].產(chǎn)業(yè)與科技論壇,2014(3):74-75.

[2]吳建輝.混合免疫優(yōu)化理論與算法及其應(yīng)用研究[D].長沙:湖南大學(xué),2013.

[3]牟曉曄.改進(jìn)的并行遺傳算法在基站選址中的應(yīng)用[J].電腦知識(shí)與技術(shù),2010,6(33):9529-9532.

[4]朱思峰.基于免疫計(jì)算的無線通信網(wǎng)絡(luò)資源優(yōu)化[D].西安:西安電子科技大學(xué),2012.

[5]朱思峰,劉芳,柴爭(zhēng)義.基于免疫計(jì)算的TD-SCDMA網(wǎng)絡(luò)基站選址優(yōu)化[J].通信學(xué)報(bào),2011,32(1):106-110.

[6]周玉光.改進(jìn)粒子群算法及其在基站優(yōu)化選址中的應(yīng)用研究[D].廣州：廣東工業(yè)大學(xué),2014.

A Study on Optimizing TD-LTE Base Station Location Based on Hybrid Immune Algorithm

LI Daoguo1, LI Lianjie2

(1.SchoolofInformationEngineering,HangzhouDianziUniversity,HangzhouZhejiang310018,China;2.SchoolofManagement,HangzhouDianziUniversity,HangzhouZhejiang310018,China)

To improve the services-quality of mobile communication and reduce the cost of establishing stations, the location optimization of the TD-LTE network base station is an important means. Firstly, the principles, objectives, the main methods and difficulties of TD-LTE network base station location selection are summarized in this paper, and then some disadvantages of TD-LTE network base station location models are analyzed. By combining the advantages of co-evolution algorithm and artificial immune algorithm, a new TD-LTE network base station location optimization co-evolutionary immune algorithm LCIA is proposed. Simulation results show that proposed algorithm has not only brought lower station-building cost and higher network coverage and capacity than the classical co-evolution algorithm and artificial immune algorithm, but it also has better convergence.

TD-LTE network stations; co-evolutionary algorithm; artificial immune algorithm; hybrid immune algorithm

10.13954/j.cnki.hdu.2016.05.011

2016-03-14

浙江省自然基金資助項(xiàng)目(LY12G01002)

李道國(1965-)，男，浙江杭州人，教授，電子商務(wù).

TP301.6

A

1001-9146(2016)05-0057-05