基于分布估計算法的無線傳感器網(wǎng)絡(luò)覆蓋問題優(yōu)化

李慧凱,王筱萍,高慧敏

(嘉興學(xué)院：a.機電工程學(xué)院;b.商學(xué)院,浙江嘉興314001)

0 引言

無線傳感網(wǎng)絡(luò) (Wireless Sensor Net works,WSN,也稱傳感器網(wǎng)絡(luò))由大量具有感知能力、計算能力和通信能力的微型傳感器以自組織方式構(gòu)成,在新一代網(wǎng)絡(luò)中具有關(guān)鍵性角色。但由于應(yīng)用規(guī)模大,能量、計算能力和通信能力受限等特點,在監(jiān)測區(qū)域內(nèi)要對傳感器節(jié)點進行大規(guī)模、高密度冗余部署,這就造成部署代價與部署質(zhì)量、節(jié)點能量受限以及網(wǎng)絡(luò)生存時間之間的矛盾,而覆蓋控制通過對節(jié)點感知能力的建模,使無線傳感器網(wǎng)絡(luò)的空間資源得到優(yōu)化分配,進而更好地完成環(huán)境感知、信息獲取和有效傳輸?shù)娜蝿?wù).

任豐原等詳細(xì)闡述了包括低功耗路由技術(shù)和介質(zhì)訪問控制方法在內(nèi)等熱點研究問題.[1]班慶奇等給出了傳感器節(jié)點的感知模型,從不同角度對覆蓋問題進行分類,闡述覆蓋控制算法的評價指標(biāo),介紹覆蓋問題和連通問題的典型算法,并對覆蓋和連通問題的研究方向進行了展望.[2]王偉等分析無線傳感器網(wǎng)絡(luò)的網(wǎng)絡(luò)特征以及影響網(wǎng)絡(luò)覆蓋的重要因素,總結(jié)和評估近年來提出的覆蓋機制,同時對該領(lǐng)域尚存問題以及發(fā)展趨勢進行了討論.[3]呂廣輝等對遺傳算法中的適應(yīng)度函數(shù)公式做了改進,將多重覆蓋率和覆蓋率的組合作為適應(yīng)度函數(shù).根據(jù)遺傳算法的相關(guān)內(nèi)容和流程圖,利用遺傳算法對覆蓋策略做仿真模擬,證明了所選用方法的正確和優(yōu)越性.[4]張西紅等研究了在滿足覆蓋性和連通性要求的基礎(chǔ)上,選擇最少數(shù)量的工作節(jié)點以及計算同時滿足覆蓋要求和連通性要求的問題.[5]

分布估計算法 (EDAs)是一類基于概率模型的進化算法,與傳統(tǒng)的進化算法不同,它不使用交叉和變異算子,而是根據(jù)當(dāng)前種群的概率分布來產(chǎn)生下一代的種群,即先從當(dāng)前種群中按照一定的選擇方式選出一部分適應(yīng)度較好的個體,根據(jù)他們建立概率分布模型,再利用所建分布模型產(chǎn)生新的個體,如此迭代直到滿足終止條件.基于概率的分布估計算法是一種來自于統(tǒng)計學(xué)的進化算法,比傳統(tǒng)的進化算法有更強的理論基礎(chǔ)以及較強的收斂性,操作性也更強.[6-7]周樹德等根據(jù)概率模型的復(fù)雜性,按照變量無關(guān)、雙變量相關(guān)、多變量相關(guān)等三類分別介紹了相應(yīng)的分布估計算法.[8]

算法實施流程如圖1所示.

本文提出一種基于加權(quán)分布估計算法的覆蓋優(yōu)化策略,它能快速實現(xiàn)最優(yōu)節(jié)點集的選取,從而降低能耗、延長網(wǎng)絡(luò)生存時間.

圖1 分布估計算法流程圖

1 覆蓋問題建模

1.1 相關(guān)假設(shè)

1.2 覆蓋問題模型

無線傳感器網(wǎng)絡(luò)優(yōu)化覆蓋問題是一個典型的目標(biāo)優(yōu)化問題.傳感器網(wǎng)絡(luò)有效覆蓋率 (Cov Area)、工作節(jié)點數(shù)目 (nu m_wor ksen)是衡量工作節(jié)點集選取的重要指標(biāo).為計算Cov Area,將目標(biāo)區(qū)域A劃分為m×n個網(wǎng)格,以網(wǎng)格中心被覆蓋的程度代表網(wǎng)格被覆蓋的程度,Δs表示每個網(wǎng)格的面積,As表示目標(biāo)區(qū)域A的總面積,則有：

由式 (1)可知網(wǎng)格G(xl,yw)被節(jié)點ci覆蓋的概率為：

網(wǎng)格被節(jié)點集覆蓋的概率為：

則工作點集C的區(qū)域覆蓋率Cov Area(C)為節(jié)點集覆蓋面積與目標(biāo)區(qū)域總面積的比值,即：

另外,若工作節(jié)點的數(shù)量為num_wor ksen,則節(jié)點利用率Sen Rat(C)為：

2 基于加權(quán)分布估計算法的覆蓋優(yōu)化策略

2.1 編碼方式

在分布估計算法中,選擇合適的編碼方式并將最優(yōu)化問題的解空間和編碼空間相互映射是一個關(guān)鍵問題.在無線傳感器網(wǎng)絡(luò)中,傳感器節(jié)點是隨機分布的,由此在分布估計算法中一個個體應(yīng)代表在一個固定位置的傳感器節(jié)點,同時編碼方式需要突出每個節(jié)點的工作狀態(tài).這里采用0～1編碼的方式,染色體用一串二進制數(shù)表示,其中每一位代表一個節(jié)點,節(jié)點的位序表示傳感器的序號,用1代表節(jié)點為工作狀態(tài),用0代表節(jié)點為靜默狀態(tài).即覆蓋問題的解由位串a(chǎn)=(a1,a2,…,aN)表示,其中：

2.2 基于加權(quán)的適應(yīng)度函數(shù)設(shè)計

工作節(jié)點集的網(wǎng)絡(luò)覆蓋率子目標(biāo)函數(shù)為：

若作用點高度保持一致，對同一種品種而言，不同的作用點高度(由于實驗系統(tǒng)測量范圍的限制，一般作用點高度在第2節(jié)間之上)，測量T以及a值，觀測其曲線變化，亦可定量地了解同一單株小麥莖稈不同節(jié)間的機械強度變化，回彈力T值越大，莖節(jié)間莖稈機械強度越強。該評價指標(biāo)也適用于其他莖稈作物，如玉米、水稻和谷物等。

節(jié)點利用率子目標(biāo)函數(shù)為：

本文中將覆蓋率函數(shù)f1(x)與節(jié)點利用率函數(shù)f2(x)作為子目標(biāo)函數(shù),總體目標(biāo)函數(shù)是這兩個子目標(biāo)函數(shù)的變換加權(quán)和.總體目標(biāo)函數(shù)可定義為：

其中w1和w2為子目標(biāo)函數(shù)對應(yīng)的權(quán)值,其值取決于設(shè)計者對該傳感器網(wǎng)絡(luò)指標(biāo)的綜合要求.權(quán)值滿足條件ω1+w2=1,則總體目標(biāo)函數(shù)值介于0～1之間.通過式 (10),可綜合評估各種節(jié)點部署方案的優(yōu)劣.

3 實驗及分析

本文采用Matlab 7.0軟件進行仿真.軟件運行環(huán)境Windows 7系統(tǒng),CPU主頻2.1 GHz.實驗一為半定點半隨機區(qū)域覆蓋,實驗二為隨機節(jié)點區(qū)域覆蓋,實驗三為隨機點覆蓋.每個實驗均獨立運行50次,取其平均值.

設(shè)定目標(biāo)區(qū)域大小為100×100,傳感器節(jié)點數(shù)目N為50,感知半徑R為20,覆蓋率子目標(biāo)函數(shù)權(quán)重w1為0.7,節(jié)點利用率子目標(biāo)函數(shù)權(quán)重w2為0.3,群體規(guī)模為10,進化代數(shù)為30.

3.1 實驗一

50個傳感器節(jié)點由14個確定位置的傳感器節(jié)點和36個位置隨機產(chǎn)生.14個確定位置的最優(yōu)覆蓋傳感器節(jié)點坐標(biāo)由文獻 [3]和文獻 [4]提供的 “六邊形法則”確定.算法運行15代,觀察不同代數(shù)的節(jié)點分布.

將覆蓋率子目標(biāo)函數(shù)權(quán)重w1分別更改為0.5、0.3,相應(yīng)的權(quán)重w2變?yōu)?.5、0.7,分別進行實驗.統(tǒng)計40次運行的結(jié)果,權(quán)重不同時對適應(yīng)度、覆蓋率及節(jié)點利用率的影響如圖2～4所示.

從3個圖不難看出,覆蓋率函數(shù)的權(quán)重變大,最優(yōu)節(jié)點集的覆蓋率變大,相應(yīng)的節(jié)點利用率的權(quán)重變低,因而造成節(jié)點利用率增大,使傳感器節(jié)點數(shù)增加.

因此,可以根據(jù)實際需求,通過調(diào)節(jié)權(quán)重,使最優(yōu)節(jié)點集側(cè)重于工作節(jié)點數(shù)目減少抑或覆蓋面積增加.

3.2 實驗二

將節(jié)點部署方式改為全隨機部署,節(jié)點感知半徑分別設(shè)置為15、20、25進行實驗.同樣統(tǒng)計50次實驗結(jié)果,感知半徑時對適應(yīng)度、覆蓋率及節(jié)點利用率的影響如圖5～7所示.

由實驗二的結(jié)果可知,對于相同數(shù)目的傳感器節(jié)點,在同樣做到冗余覆蓋的情況下,節(jié)點感知半徑更大的傳感器網(wǎng)絡(luò),由本文策略進化出的最優(yōu)節(jié)點集能夠?qū)崿F(xiàn)更好的網(wǎng)絡(luò)覆蓋質(zhì)量.

圖2 權(quán)重對適應(yīng)度的影響圖

圖3 權(quán)重對覆蓋率的影響圖

圖4 權(quán)重對節(jié)點利用率的影響圖

圖5 感知半徑對適應(yīng)度的影響圖

圖6 感知半徑對覆蓋率的影響圖

圖7 感知半徑對節(jié)點利用率的影響圖

3.3 實驗三

假設(shè)區(qū)域內(nèi)有200個隨機感知點,有100個傳感器隨機可行點,若感知點在傳感器的覆蓋范圍內(nèi),則此感知點被覆蓋,如何在可行放置點上部署最少數(shù)量的節(jié)點,使得所有感知點都被覆蓋而任兩個節(jié)點間的距離不小于距離閾值.如何通過調(diào)整節(jié)點的感知半徑實現(xiàn)能量高效覆蓋.

令w1=0.4,w2=0.6,在100×100的區(qū)域內(nèi)部署,感知半徑為10.圖8為150個傳感器全部開啟時的覆蓋情況,圖9～10分別為第10、25代優(yōu)化傳感器覆蓋圖.圖11為適應(yīng)度、覆蓋率及節(jié)點利用率的進化軌跡.

圖8 150個傳感器全部開啟時的覆蓋情況

圖9 第10代傳感器覆蓋圖

圖10 第25代傳感器覆蓋圖

圖11 三個函數(shù)的進化軌跡

由圖11可知,最優(yōu)解時覆蓋率為0.7920,適應(yīng)度為0.8051,節(jié)點利用率為0.1893,即用28個傳感器,覆蓋了200個被測點中的79.20%.

分析適應(yīng)函數(shù)知,適應(yīng)度最大為1(因為覆蓋率理想值為1,節(jié)點利用率w1+w2=1),適應(yīng)度越接近1,獲得的解越接近最優(yōu)解.

調(diào)節(jié)適應(yīng)度函數(shù)中覆蓋率和節(jié)點利用率權(quán)重,增加節(jié)點利用率的權(quán)重,即增大w2,減小w1,發(fā)現(xiàn)覆蓋率會下降變差,節(jié)點利用率減小變好,同理,增大w1,減小w2,覆蓋率會增大變好,節(jié)點利用率增大變差.

調(diào)節(jié)感知半徑的大小,半徑越大,每個傳感器能覆蓋更多的點,節(jié)點數(shù)越小,節(jié)點利用率降低,因此,當(dāng)半徑增大時,為了滿足要求,求得最優(yōu)適應(yīng)解的權(quán)重w2要增大.同理,當(dāng)半徑減小時,w2也要適當(dāng)減小.

當(dāng)感知半徑擴大為原來的2倍,即r=20時,實驗發(fā)現(xiàn),w2=0.7時覆蓋率為0.9310,適應(yīng)度為0.8925,節(jié)點利用率為0.1240.即只用12個傳感器,覆蓋率達到93.1%,結(jié)果最理想,見圖12.

當(dāng)r=25時,若仍取w2=0.7,覆蓋率為0.98,節(jié)點利用率為0.10,適應(yīng)度為0.924.若取w2=0.75,則覆蓋率達到0.99,節(jié)點利用率仍為0.10,適應(yīng)度為0.925,后者好于前者.實驗結(jié)果見圖13.

4 結(jié)論

對于本文算法所求解的問題,本文所描述的算法可以收斂于全局最優(yōu)解.統(tǒng)計多次實驗結(jié)果表明,覆蓋率函數(shù)的權(quán)重增加,會引起求解出的最優(yōu)工作節(jié)點集覆蓋率增加,總體適應(yīng)度增加,同時造成該節(jié)點集的節(jié)點利用率增加,傳感器節(jié)點數(shù)目增多;對于傳感器節(jié)點總數(shù)相同的傳感器網(wǎng)絡(luò)冗余覆蓋,若傳感器感知半徑越大,則進化所得最優(yōu)工作節(jié)點集工作傳感器節(jié)點數(shù)目更少,從而實現(xiàn)更好的網(wǎng)絡(luò)覆蓋質(zhì)量;此外,在原始算法中采用精英保留策略,可以加快收斂速度,同時能夠改進收斂結(jié)果.

圖12 r=20時,三個函數(shù)的變化軌跡

圖13 r=25時三個函數(shù)的變化軌跡

[1]任豐原,黃海寧,林闖.無線傳感器網(wǎng)絡(luò) [J].軟件學(xué)報,2003,14(7)：1282-1291.

[2]班慶奇,陳志剛.無線傳感器網(wǎng)絡(luò)覆蓋和連通問題概述 [J].電腦與信息技術(shù),2010,18(03)：39-40.

[3]王偉,林鋒,周激流.無線傳感器網(wǎng)絡(luò)覆蓋問題的研究進展 [J].計算機應(yīng)用研究,2010,27(01)：32-35.

[4]呂廣輝,崔遜學(xué),侯戰(zhàn)勝.一種基于遺傳算法的無線傳感器網(wǎng)絡(luò)覆蓋模型 [J].微型機與應(yīng)用,2010,29(15)：59-62.

[5]張西紅,妙文亮,高彥彥.無線傳感器網(wǎng)絡(luò)的覆蓋問題研究 [J].計算機工程,2009,35(16)：109-111.

[6]ZHANG Q.On stability of fixed point of li mit models of univariate marginal distribution Part 1,binry parameter[J].lecture notes in co mputer science.Berlin,Ger many：Springer-Verlag,1996,1141,Parallel Problem Solving from Nature-PPSN：178-187.

[7]ZHANG Q,Mühliebei H.On t he convergence of class of esti mation of distribution algorit h ms[J].IEEE Trans on Evolutionar y Co mputation,2004,8(2)：127-136.

[8]周樹德,孫增圻.分布估計算法綜述 [J].自動化學(xué)報,2007,33(2)：113-124.

[9]賈杰,陳劍,常桂然,趙林亮,王光興.無線傳感器網(wǎng)絡(luò)中基于遺傳算法的優(yōu)化覆蓋機制 [J].控制與決策,2007,22(11)：1289-1292,1301.

[10]郭小清,謝忠紅.無線傳感器網(wǎng)絡(luò)覆蓋性能研究 [J].計算機科學(xué),2011,38(10 A)：364-366.

[11]HONGHAI ZHANG,JENNIFER C HOU.Maintaining sensing coverage and connectivity in large sensor net wor ks[J].Wireless Ad Hoc and Sensor Net wor k,2005,1(1)：89-124.

[12]毛蔦池,陳力軍,陳道蓄.無線傳感器網(wǎng)絡(luò)覆蓋控制技術(shù)研究 [J].計算機科學(xué),2007,34(3)：20-22.

[13]KUMAR S,LAI T H,BALOGH J.On k-Coverage in a Mostly Sleeping Sensor Net wor k[C].Proceedings of ACM MOBICOM,2004.

[14]景勃,孫勇,張劼.智能網(wǎng)絡(luò)傳感器與無線傳感網(wǎng)絡(luò)[M].北京：國防工業(yè)出版社,2011.

[15]HHANG C F,TSENG Y C.The Coverage Proble min a Wireless Sensor Net wor k[J].Mobile net nor ks and applications,2005,10：519-528.