基于免疫計(jì)算的mike80216j網(wǎng)絡(luò)選址優(yōu)化方案

基于免疫計(jì)算的mike80216j網(wǎng)絡(luò)選址優(yōu)化方案

2009年7月，批準(zhǔn)了ue802.16j標(biāo)準(zhǔn)，并由ie發(fā)布。與單通道無(wú)線網(wǎng)絡(luò)的引入相比，引入中間站，使ie802.16j多跳網(wǎng)絡(luò)具有更高的成本效益，并且具有很大的擴(kuò)展能力。這一優(yōu)勢(shì)吸引了移動(dòng)通信運(yùn)營(yíng)商。在802.16j網(wǎng)絡(luò)基礎(chǔ)設(shè)施和基礎(chǔ)設(shè)施建設(shè)的布局優(yōu)化問(wèn)題引起了人們的廣泛關(guān)注。在文獻(xiàn)中，設(shè)計(jì)了一個(gè)基于自治機(jī)制的理想覆蓋方案模型，但該模型中沒(méi)有考慮容量問(wèn)題。文獻(xiàn)使用合作中繼技術(shù)來(lái)解決疊加站點(diǎn)在802.16j網(wǎng)絡(luò)環(huán)境下的布局優(yōu)化問(wèn)題，但合作中繼是802.16j網(wǎng)絡(luò)的可選功能，許多網(wǎng)絡(luò)應(yīng)用可能不使用。在文獻(xiàn)中，基于遺傳理論的基站布局優(yōu)化方案提出。本文認(rèn)為,基站中繼站選址優(yōu)化問(wèn)題是一個(gè)約束多目標(biāo)優(yōu)化問(wèn)題,也是眾所周知NP難問(wèn)題.由于免疫優(yōu)化算法具有尋優(yōu)能力強(qiáng)、收斂性能好等優(yōu)點(diǎn),近幾年得到了迅速的應(yīng)用推廣.基于此,本文構(gòu)造了一種基于免疫計(jì)算的802.16j基站中繼站選址優(yōu)化方案.1中繼站市場(chǎng)前景模型當(dāng)IEEE802.16j中繼系統(tǒng)在透明中繼模式下時(shí),移動(dòng)站(subscriberstation,SS)從基站(basestation,BS)接收同步信息和幀頭信息,從中繼站(relaystation,RS)接收數(shù)據(jù),在用戶看來(lái)好像沒(méi)有中繼站,即對(duì)用戶透明.這個(gè)模式要求移動(dòng)站必須處在基站的覆蓋范圍內(nèi)以保證能中繼傳播.透明中繼模式主要用于增強(qiáng)802.16j網(wǎng)絡(luò)的小區(qū)容量,由于小區(qū)覆蓋范圍有限,一般把IEEE802.16j中繼系統(tǒng)設(shè)計(jì)成兩跳網(wǎng)絡(luò),即一個(gè)小區(qū)至多存在一個(gè)中繼站.那么在網(wǎng)絡(luò)優(yōu)化時(shí)需要確定的是:某個(gè)特定區(qū)域的移動(dòng)站是直接與一個(gè)基站建立關(guān)聯(lián)還是通過(guò)一個(gè)中繼站與一個(gè)基站間接建立關(guān)聯(lián),即移動(dòng)臺(tái)如何選擇路徑.802.16j網(wǎng)絡(luò)中存在3種鏈路:移動(dòng)臺(tái)到中繼站之間的鏈路(記作SS-RS)、移動(dòng)臺(tái)到基站之間的鏈路(記作SS-BS)和中繼站到基站之間的鏈路(記作RS-BS).本文采用評(píng)估法為每個(gè)鏈路賦一個(gè)權(quán)重,并規(guī)定移動(dòng)臺(tái)總是選擇累積權(quán)重最小的路徑.本文關(guān)注的問(wèn)題是802.16j兩跳網(wǎng)絡(luò)基站中繼站選址優(yōu)化問(wèn)題,即從給定的基站和中繼站候選站址集合中確定一個(gè)以最低代價(jià)滿足用戶需求的站址子集合.本文定義的系統(tǒng)輸入?yún)?shù)如下.一個(gè)站(基站或中繼站)的覆蓋范圍受該站與測(cè)試點(diǎn)之間的鏈路權(quán)重所影響,函數(shù)g(w)被用來(lái)確定一個(gè)測(cè)試點(diǎn)被一個(gè)站覆蓋情況,該函數(shù)定義如下:g(w)={0,w=∞;1,w≠∞.g(w)={0,w=∞;1,w≠∞.當(dāng)測(cè)試點(diǎn)不在基站的覆蓋范圍內(nèi)時(shí),該測(cè)試點(diǎn)與基站之間的鏈路權(quán)重w取無(wú)窮大.測(cè)試點(diǎn)(或中繼站)被站覆蓋情況如下.yi,j=g(wi,j)(i∈T,j∈R):測(cè)試點(diǎn)i被中繼站j覆蓋;yi,k=g(wi,k)(i∈T,k∈B):測(cè)試點(diǎn)i被基站k覆蓋;yj,k=g(wj,k)(j∈R,k∈B):中繼站j被基站k覆蓋;本文使用了7個(gè)決策變量,定義如下.xi,j∈{0,1}(i∈T,j∈R):測(cè)試點(diǎn)i與中繼站j之間鏈路的存在性;xi,k∈{0,1}(i∈T,k∈B):測(cè)試點(diǎn)i與基站k之間鏈路的存在性;xj,k∈{0,1}(j∈R,k∈B):中繼站j與基站k之間鏈路的存在性;xi,j,k∈{0,1}(i∈T,j∈R,k∈B):測(cè)試點(diǎn)i、中繼站j與基站k之間路徑的存在性;rj∈{0,1}(j∈R):中繼站j被選中情況;bk∈{0,1}(k∈B):基站k被選中情況;qj,k∈{0,1}(j∈R,k∈B):中繼站j與基站k之間鏈路的存在性掩碼,用于確保每個(gè)中繼站只與一個(gè)基站關(guān)聯(lián).本文建立的數(shù)學(xué)模型如下:其中,目標(biāo)函數(shù)中的第1部分是基站和中繼站的建站總代價(jià),第2部分為總路徑損耗;式(1)保證每個(gè)基站的負(fù)載不超過(guò)最大負(fù)載Ω;式(2)保證每一個(gè)與中繼站關(guān)聯(lián)的測(cè)試點(diǎn)必須處在基站和中繼站覆蓋范圍內(nèi);式(3)和式(4)保證每個(gè)與中繼站直接關(guān)聯(lián)的測(cè)試點(diǎn)必須在一個(gè)基站的覆蓋范圍中;式(5)保證一個(gè)測(cè)試點(diǎn)只與一個(gè)中繼站或一個(gè)基站關(guān)聯(lián);式(6)和式(7)保證若一個(gè)中繼站被選中,該中繼站只能和一個(gè)基站關(guān)聯(lián);式(8)和式(9)保證每個(gè)測(cè)試點(diǎn)或中繼站只能和一個(gè)被選中的基站關(guān)聯(lián).在模型求解時(shí),通過(guò)消除與不可行鏈路關(guān)聯(lián)的決策變量,可以大大地縮減決策變量的數(shù)目.例如,?i∈T,?j∈R,?k∈B,當(dāng)wi,j,k≥wi,k時(shí),可移除決策變量xi,j,k.2基于免疫計(jì)算的布局優(yōu)化方案2.1選取情況.由于在選址優(yōu)化中每個(gè)候選站址只有被選中與沒(méi)被選中兩種情況,采用二進(jìn)制編碼是適宜的.在免疫算法中,把要解決的問(wèn)題看作抗原,把問(wèn)題的解看作抗體.每個(gè)抗體對(duì)應(yīng)一種選址優(yōu)化方案,每個(gè)候選站址對(duì)應(yīng)基因座的值表示該站址被選中情況.設(shè)候選站址集為S,每個(gè)候選站址i(i∈S)被選中情況如式(10)所示:ui={1,站址i被選中；0,其他.(10)ui={1,站址i被選中；0,其他.(10)為了便于處理,把基站候選站址放在中繼站候選站址的前面.抗體記作Ab=(b1,b2,…,bn,r1,r2,…,rm),其中,bk∈{0,1}(k=1,2,…,n)為第k個(gè)基站站址被選中情況,n為基站候選站址數(shù)目;rj∈{0,1}(j=1,2,…,m)為第j個(gè)中繼站站址被選中情況,m為中繼站候選站址數(shù)目.免疫算法必須要有一個(gè)初始種群,最常用的方法是隨機(jī)產(chǎn)生整個(gè)初始種群.由于免疫算法能夠迭代地改進(jìn)現(xiàn)有的解,那么就可以根據(jù)問(wèn)題的先驗(yàn)知識(shí)或歷史數(shù)據(jù)得到一些潛在的較好解,填入初始種群.本文采用的種群初始化方式為一部分抗體來(lái)自免疫記憶庫(kù)(歷史數(shù)據(jù)),剩余的抗體采用隨機(jī)方式生成.利用已有的先驗(yàn)解作為啟發(fā)式信息指導(dǎo)種群進(jìn)化,可以提高收斂速度;隨機(jī)產(chǎn)生的抗體保證了初始化過(guò)程的種群多樣性.2.2cbbck至kxj,kxj,kxj,kxj,kxj,kxj,kxj,kxj,kxj,kxj,kxj,kxj,kxj,kxj,kxj,kxj,kxj,kxj,kxj,kxj,kxj,kxj,kxj,kxj,kj,kxj,kxj,kxj,kxj,kj,kxj,kxj,kxj,kxj,kxj,kj,kj,kj,kj,kxj,kxj,kj,kxj,kj,kxj,kj,kj,kj,kj,kxj,kxj,kj,kxj,kxj,kxj,kxj,kxj,kxj,kxj,kxj,kxj,kxj,kxj,kxj,kj,kj,kj,kj,kj,kj,k把優(yōu)化問(wèn)題看作抗原,把問(wèn)題的解看作抗體,則抗體-抗原親和度是衡量解質(zhì)量的一個(gè)主要指標(biāo).本文設(shè)計(jì)的抗體-抗原親和度評(píng)價(jià)函數(shù)如式(11)所示:f(Ab)=λ1(m∑j=1crjrj+n∑k=1cbkbk)+λ2(m∑j=1n∑k=1lj,kxj,k+p∑i=1m∑j=1n∑k=1li,j,kxi,j,k).(11)f(Ab)=λ1(∑j=1mcrjrj+∑k=1ncbkbk)+λ2(∑j=1m∑k=1nlj,kxj,k+∑i=1p∑j=1m∑k=1nli,j,kxi,j,k).(11)2.3計(jì)算公式相關(guān)參數(shù)從抗體形式可以看出,抗體是由基站優(yōu)化部分和中繼站優(yōu)化部分組成的.兩個(gè)抗體的差異性表現(xiàn)為基站部分的差異及中繼站部分的差異的累加,因此本文把抗體編碼中差異累加值作為兩個(gè)抗體間的距離,其計(jì)算公式如式(12)所示:dist_Abs(Abp,Abq)=n+m∑i=1|Abp[i]-Abq[i]|.(12)鄰居抗體指與某抗體的距離小于某個(gè)閾值θ的抗體,如式(13)所示:neighbor(Abp,Abq)={1,ifdist_Abs(Abp,Abq)<θ;0,otherwise.(13)抗體的濃度指在抗體種群中抗體的鄰居數(shù)目與抗體種群規(guī)模的比值,如式(14)所示:concentration(Abp)=pop_size∑q=1neighbors(Abp,Abq)/pop_size,(14)其中pop_size為抗體種群的規(guī)模.2.4抗體有效性檢測(cè)在免疫進(jìn)化過(guò)程中可能產(chǎn)生不可行解,對(duì)抗體進(jìn)行有效性檢測(cè)是必須的,抗體有效性檢測(cè)的方法如下:對(duì)抗體進(jìn)行解碼,得到被選中的基站及中繼站;確定決策變量的值;逐個(gè)驗(yàn)證約束條件滿足情況,只有滿足全部約束條件的抗體才是有效的.2.5abp.2克隆選擇本文算法使用了克隆增殖、低頻變異和克隆選擇3個(gè)算子:1)克隆增殖.對(duì)抗體Abp產(chǎn)生M個(gè)克隆副本,記作Ab(1)p,Ab(2)p,…,Ab(Μ)p.2)低頻變異.對(duì)抗體Abp的某個(gè)克隆副本Ab(i)p(i=1,2,…M),隨機(jī)選擇一個(gè)基因座位置k(k=1,2,…,n+m),把該基因座的值取反,而其他n+m-1個(gè)基因座的值保持不變,得到Ab(i)′p.3)克隆選擇.采用輪盤法進(jìn)行概率選擇,每個(gè)抗體被選中進(jìn)入下一代的概率按照式(15)計(jì)算:probability(Abp)=f(Abp)pop_size∑q=1f(Abq).(15)2.6u3000各抗體間的親和度及有效性檢測(cè)本文設(shè)計(jì)的算法框架如下:Step1.輸入抗體種群規(guī)模N、記憶庫(kù)種群規(guī)模W、克隆母體種群規(guī)模X和克隆副本個(gè)數(shù)M.Step2.初始化抗體種群.若抗體記憶庫(kù)Ab_Member為空(首次處理),則隨機(jī)產(chǎn)生N個(gè)抗體構(gòu)成初始種群;否則,由Ab_Member中的W個(gè)抗體和隨機(jī)產(chǎn)生的N-W個(gè)抗體共同構(gòu)成初始種群A(0).Step3.計(jì)算第t代種群A(t)中每個(gè)抗體的親和度,并按親和度值降序排序.Step4.選擇A(t)中的前X個(gè)抗體構(gòu)成克隆母體種群B(t)={Ab1,Ab2,…,AbX}.Step5.利用克隆增殖算子對(duì)B(t)中抗體Abp(p=1,2,…,X)繁殖M個(gè)克隆副本,記作:Ab(1)p,Ab(2)p,…,Ab(Μ)p.Step6.對(duì)B(t)中每個(gè)抗體的所有克隆副本進(jìn)行低頻變異,得到集合C(t)=∪{Ab(i)′p}(p=1,2,…,X,i=1,2,…,M).Step7.計(jì)算A(t)∪B(t)∪C(t)中每種抗體的濃度及親和度,并對(duì)抗體進(jìn)行有效性檢測(cè).Step8.對(duì)通過(guò)有效性檢測(cè)的抗體按照親和度值降序排列,選取親和度高的一些抗體去替換記憶庫(kù)Ab_Member部分抗體.若滿足終止條件,則輸出記憶庫(kù)Ab_Member中親和度最高的那個(gè)抗體,算法結(jié)束;否則轉(zhuǎn)到Step9.Step9.從A(t)∪B(t)∪C(t)中選取濃度較低且親和度較高的N個(gè)抗體組成新一代抗體種群,置t←t+1,轉(zhuǎn)到Step3.3記憶庫(kù)運(yùn)行情況為了驗(yàn)證本文算法的性能,采用文獻(xiàn)的實(shí)驗(yàn)數(shù)據(jù),解決一個(gè)3km×3km區(qū)域、20個(gè)基站候選站址、200個(gè)中繼站候選站址、500個(gè)測(cè)試點(diǎn)的選址優(yōu)化問(wèn)題.兩種算法的種群規(guī)模均取100,最大進(jìn)化代數(shù)均取1200,個(gè)體均采用二進(jìn)制編碼,編碼長(zhǎng)度為220b.文獻(xiàn)算法的變異概率取0.1,交叉功率取0.8;本文算法的抗體間距離閾值θ取30,記憶庫(kù)種群規(guī)模W取20,克隆母體種群規(guī)模X取10,克隆副本個(gè)數(shù)M取5.實(shí)驗(yàn)1.比較文獻(xiàn)算法與本文算法的性能.在Pentium42.0GHz主頻的CPU、2GB內(nèi)存的IBM兼容機(jī)器上,依次對(duì)文獻(xiàn)算法和本文算法各運(yùn)行10次,取平均值,其中本文算法首次運(yùn)行時(shí)記憶庫(kù)為空,后9次是在記憶庫(kù)非空情況下運(yùn)行的.兩種算法運(yùn)行時(shí)間的比較結(jié)果如圖1所示.從圖1可以看出:文獻(xiàn)算法的運(yùn)行時(shí)間與候選站數(shù)目呈指數(shù)關(guān)系,隨著候選站數(shù)目的增多,運(yùn)行時(shí)間指數(shù)級(jí)增加;而本文算法的運(yùn)行時(shí)間與問(wèn)題規(guī)模幾乎呈線性關(guān)系.這說(shuō)明本文算法收斂性能優(yōu)于文獻(xiàn)算法.無(wú)線電波沿著路徑傳播過(guò)程中功率損耗折合成貨幣單位后,把基站與中繼站優(yōu)化問(wèn)題的建站代價(jià)與路徑損耗之和稱為優(yōu)化方案代價(jià).兩種算法的平均優(yōu)化方案代價(jià)隨進(jìn)化代數(shù)的變化曲線,如圖2所示:從圖2可以看出:隨進(jìn)化代數(shù)的增加,本文算法的平均優(yōu)化方案代價(jià)下降速度較快,這再次說(shuō)明了本文算法的收斂性能優(yōu)于文獻(xiàn)算法.另一個(gè)重要的度量指標(biāo)是中繼站帶來(lái)的小區(qū)容量增益.兩種算法的小區(qū)平均容量增益隨進(jìn)化代數(shù)的變化曲線如圖3所示:從圖3可以看出,兩種算法曲線差異較小,其原因是:對(duì)于兩跳中繼網(wǎng)絡(luò)來(lái)說(shuō),由于一個(gè)基站最多只能關(guān)聯(lián)一個(gè)中繼站,只要能選擇較合理的基站與中繼站位置,小區(qū)容量增益差異很小.也就是說(shuō)兩種算法在網(wǎng)絡(luò)容量增益方面的貢獻(xiàn)幾乎相當(dāng).實(shí)驗(yàn)2.驗(yàn)證記憶庫(kù)對(duì)算法性能的影響.在記憶庫(kù)為空和非空兩種情況下,各運(yùn)行10次本文算法,結(jié)果如表1所示:從表1可以看出:使用記憶庫(kù)后,本文算法的收斂速度得到了明顯的提高(不使用記憶庫(kù)進(jìn)化1200代才收斂,使用記憶庫(kù)后縮減為800代),解的質(zhì)量也提高了很多(優(yōu)化方案代價(jià)從1.26×107元縮減為1.21×107元,小區(qū)容量增益從42.3%增至44.1%).主要原因是當(dāng)記憶庫(kù)為空時(shí),算法模擬的是抗體對(duì)抗原的初次免疫應(yīng)答過(guò)程,免疫細(xì)胞的克隆增殖及對(duì)抗原進(jìn)行應(yīng)答過(guò)程需要一段時(shí)間,所以算法在進(jìn)化較多的代數(shù)后才收斂;