基于Memetic算法的無線傳感網(wǎng)絡(luò)覆蓋優(yōu)化-論文.pdf

《基于Memetic算法的無線傳感網(wǎng)絡(luò)覆蓋優(yōu)化-論文.pdf》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、第27卷第2期河南工程學(xué)院學(xué)報(自然科學(xué)版)Vo1．27．No．22015年6月JOURNALOFHENANINSⅡTUrE0FENGINEERINGJun．2015基于Memetic算法的無線傳感網(wǎng)絡(luò)覆蓋優(yōu)化陳偉佳，關(guān)健(1．閩江學(xué)院數(shù)學(xué)系，福建福州350108；2．閩江學(xué)院現(xiàn)代教育技術(shù)中心，福建福州350108)摘要：針對無線傳感網(wǎng)絡(luò)覆蓋優(yōu)化中工作節(jié)點集難以選取的問題，提出了一種基于Memetic的覆蓋優(yōu)化算法．該算法主要由選擇算子、交叉算子、變異算子、禁忌局部搜索算法和種群更新策略組成．利用相鄰節(jié)點間的區(qū)域覆蓋關(guān)系，減少局部搜索中鄰域的目標(biāo)函數(shù)值計算量、提高計算速度，并利用隨

2、機和貪婪的策略構(gòu)造一個質(zhì)量較好的初始種群．仿真結(jié)果表明，該算法具有較強的搜索能力，能快速收斂于優(yōu)秀解、實現(xiàn)工作節(jié)點集的優(yōu)化選取、降低網(wǎng)絡(luò)冗余和能耗、延長網(wǎng)絡(luò)的生存時間．關(guān)鍵詞：無線傳感網(wǎng)絡(luò)；覆蓋優(yōu)化；禁忌搜索算法；Memetic中圖分類號：TP391文獻標(biāo)志碼：A文章編號：1674—330X(2015)02—0073—05無線傳感網(wǎng)絡(luò)(WSNs)在軍工和民用領(lǐng)域有著廣泛的應(yīng)用，如戰(zhàn)場偵察、機械故障診斷、生物檢測、家庭安防等?．由于無線傳感網(wǎng)絡(luò)通常應(yīng)用在偏遠無人值守的地方、電池更換不便，所以能耗控制是無線傳感網(wǎng)絡(luò)應(yīng)用一個重要的研究方向．由于無線傳感網(wǎng)絡(luò)節(jié)點的高密度部署會帶來大量的節(jié)點

3、冗余，所以需要進行網(wǎng)絡(luò)覆蓋優(yōu)化，從大量的傳感節(jié)點中合理地選取一組節(jié)點進入工作狀態(tài)，以保證區(qū)域充分覆蓋．覆蓋優(yōu)化通過降低網(wǎng)絡(luò)冗余，節(jié)省了能源并延長了網(wǎng)絡(luò)的生存時間，是一種非常有效的能耗控制技術(shù)．近年來，學(xué)者們陸續(xù)提出不同的智能優(yōu)化算法求解無線傳感網(wǎng)絡(luò)的覆蓋優(yōu)化問題，如遺傳算法J、粒子群算法J、魚群算法L6等．遺傳算法(GA)具有搜索速度快、并行搜索能力強的特點，但是容易陷入“早熟”收斂和局部最優(yōu)，不利于找到全局最優(yōu)解．禁忌搜索算法(rI’S)具有較強的“爬山”能力，在搜索過程中可以接受劣解，從而跳出局部最優(yōu)解、轉(zhuǎn)向其他區(qū)域搜索更好的解或全局最優(yōu)解，但收斂速度慢，較難滿足動態(tài)節(jié)點選取的

4、實時性要求．Memetic算法是一種將全局尋優(yōu)與局部搜索相結(jié)合的算法框架J，兼顧廣度和深度．基于Memetic算法框架，融合了遺傳算法和禁忌算法，采用禁忌搜索算法作為局部搜索來增強遺傳算法的搜索能力，并通過改進目標(biāo)函數(shù)值的計算公式來提高算法的運算速度，同時利用隨機和貪婪的策略構(gòu)造較優(yōu)的初始種群，仿真實驗表明該算法是可行、有效的．1WSNs覆蓋模型假定在一個形狀規(guī)則的二維監(jiān)測區(qū)域中投放Ⅳ個傳感節(jié)點，各傳感節(jié)點參數(shù)相同、坐標(biāo)可知且相互獨立．定義1監(jiān)測區(qū)域離散化為mxn個像素，則整個監(jiān)測區(qū)域記為像素集A={(，Y)I∈{1，2，?，m}，Y∈{1，2，?，／／,}}，(，Y)為像素點．定

5、義2傳感節(jié)點C的坐標(biāo)為(，Y)，有效感知半徑為r，則該傳感節(jié)點記為圓c=，Y，r}，E{1，2，?，Ⅳ}，所有節(jié)點記為C={c，C，?，C}．1．1網(wǎng)絡(luò)節(jié)點利用率用布爾向量S={s。，s，?，s一，s}標(biāo)志各傳感節(jié)點的狀態(tài)，si=1表示節(jié)點c。處于工作狀態(tài)，s=0表示節(jié)點c處于休眠狀態(tài)，則網(wǎng)絡(luò)節(jié)點利用率收稿日期：2015—03—01基金項目：閩江學(xué)院科研育苗項目(YKY12009)；大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練項目(201410395029)作者簡介：陳偉佳(1993一)，男，福建泉州人，本科生，主要從事智能算法的研究．通信作者：關(guān)健(1984一)，男，福建莆田人，工程師，主要從事網(wǎng)絡(luò)通信技

6、術(shù)與智能算法的研究．E—mail：gjian_mail@163．tom．·74·河南工程學(xué)院學(xué)報(自然科學(xué)版)2015生∑．s()=．(1)1．2網(wǎng)絡(luò)有效覆蓋率像素點(，Y)被傳感節(jié)點c覆蓋的事件記為h(，Y)，i∈{1，2，?，Ⅳ}．當(dāng)像素點(，Y)與傳感節(jié)點c圓心的距離不大于半徑r且傳感節(jié)點c處于工作狀態(tài)時，像素點(，Y)被傳感節(jié)點c覆蓋，記P{h(，Y)}=1，否則像素點(，Y)未被傳感節(jié)點c覆蓋，記P{h(，Y)}=0．事件h發(fā)生的概率P{h(，Y)}為一個二值函數(shù)：Pc，y={：．+y—yi’≤r且’c2，像素點(，Y)被節(jié)點集c中各節(jié)點覆蓋的事件是相互獨立的，則(，Y)

7、被節(jié)點集C覆蓋的概率P{h(x，Y)}=P{h(，Y)}=1一P{[1h(，Y)}．(3)傳感節(jié)點集C中工作節(jié)點所覆蓋的像素點之和即為該節(jié)點集的覆蓋區(qū)域，記為ⅣA(c)，有NA(c)=∑∑Pt(，y)}，(4)則網(wǎng)絡(luò)有效覆蓋率)=．(5)1．3覆蓋優(yōu)化數(shù)學(xué)模型WSNs覆蓋優(yōu)化的目標(biāo)是在保證網(wǎng)絡(luò)有效覆蓋率盡可能大的情況下努力減少節(jié)點的利用率，可以通過加權(quán)將有效覆蓋率和節(jié)點利用率兩個子目標(biāo)函數(shù)轉(zhuǎn)化為總體目標(biāo)函數(shù)，作為算法求解的適應(yīng)值，定義為廠06(S)=∞1(1一())+