基于水波優(yōu)化算法的無線傳感器網(wǎng)絡(luò)覆蓋研究

王 毅,神顯豪,唐超塵,3,曹惠茹,劉 敏

(1.廣州工程技術(shù)職業(yè)學(xué)院 信息工程學(xué)院,廣東 廣州 510075;2.桂林理工大學(xué) 信息科學(xué)與工程學(xué)院,廣西 桂林 541004;3.西安電子科技大學(xué) 通信工程學(xué)院,陜西 西安 710071;4.西南石油大學(xué) 信息學(xué)院,四川 成都 610500)

無線傳感器網(wǎng)絡(luò)(Wireless sensor network,WSN)憑借其布網(wǎng)方便且組網(wǎng)靈活等優(yōu)勢廣泛用于各種物聯(lián)網(wǎng)領(lǐng)域。WSN可以滿足大規(guī)模物聯(lián)網(wǎng)設(shè)備的連網(wǎng)需要,但是由于WSN的節(jié)點(diǎn)數(shù)量眾多,WSN應(yīng)用的組網(wǎng)問題和能耗問題變得嚴(yán)峻[1]。為了滿足WSN監(jiān)測需要,在待監(jiān)測的目標(biāo)區(qū)域內(nèi)需要實(shí)現(xiàn)網(wǎng)絡(luò)感知的全覆蓋,根據(jù)單個(gè)節(jié)點(diǎn)的感知范圍和監(jiān)測區(qū)域內(nèi)的目標(biāo)節(jié)點(diǎn)數(shù)計(jì)算所需要的傳感節(jié)點(diǎn)數(shù)。一般將區(qū)域覆蓋率作為評價(jià)的主要標(biāo)準(zhǔn),通過優(yōu)化算法對傳感節(jié)點(diǎn)進(jìn)行坐標(biāo)優(yōu)化部署,用盡可能少的傳感節(jié)點(diǎn)來保證區(qū)域覆蓋率需求,降低傳感節(jié)點(diǎn)冗余率。

當(dāng)前,關(guān)于WSN的節(jié)點(diǎn)覆蓋的研究較多。徐欽帥等[2]采用蟻獅算法對WSN進(jìn)行覆蓋優(yōu)化,并進(jìn)行了效率改進(jìn),能夠獲得較高的覆蓋率性能;王振東等[3]采用改進(jìn)差分算法進(jìn)行WSN覆蓋,通過節(jié)點(diǎn)參數(shù)差分運(yùn)算進(jìn)行WSN節(jié)點(diǎn)定位,能夠?qū)崿F(xiàn)小規(guī)模節(jié)點(diǎn)精確定位;張亮等[4]采用模糊粒子群進(jìn)行WSN節(jié)點(diǎn)定位,雖能夠滿足大區(qū)域節(jié)點(diǎn)定位覆蓋,但優(yōu)化性能并不高。

作為近期提出的一種基于淺水波理論的新型智能進(jìn)化算法,水波優(yōu)化(Water wave optimization,WWO)算法能夠模擬自然界淺水波的傳播運(yùn)動(dòng)機(jī)制,相比于其他啟發(fā)式群體智能優(yōu)化算法,具有控制參數(shù)少、操作簡單、容易實(shí)現(xiàn)等優(yōu)點(diǎn)。Zhu等[5]利用多目標(biāo)WWO算法來求解作業(yè)車間調(diào)度問題,獲得了較好的優(yōu)化效果。傳感節(jié)點(diǎn)區(qū)域覆蓋的優(yōu)化問題與作業(yè)車間調(diào)度求解一樣,其本質(zhì)都是多目標(biāo)優(yōu)化問題,因此,本文嘗試采用WWO算法對傳感節(jié)點(diǎn)區(qū)域覆蓋進(jìn)行優(yōu)化。以區(qū)域覆蓋率為適應(yīng)度函數(shù),通過傳感節(jié)點(diǎn)坐標(biāo)集構(gòu)建水波個(gè)體,執(zhí)行水波的傳播、折射和碎波操作,對傳感節(jié)點(diǎn)坐標(biāo)進(jìn)行優(yōu)化,以提高區(qū)域網(wǎng)絡(luò)覆蓋率。

1 無線傳感器網(wǎng)絡(luò)覆蓋

無線傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)部署過程中,根據(jù)需要覆蓋的區(qū)域大小及區(qū)域內(nèi)需要監(jiān)測的目標(biāo)節(jié)點(diǎn)數(shù)量,可以靈活采取覆蓋方式,主要有點(diǎn)覆蓋和區(qū)域覆蓋2種方式,根據(jù)不同的覆蓋方式選擇合適的覆蓋優(yōu)化模型。

1.1 點(diǎn)覆蓋與區(qū)域覆蓋

點(diǎn)覆蓋方式主要用于監(jiān)測的目標(biāo)區(qū)域小且節(jié)點(diǎn)固定的情況,通過在目標(biāo)節(jié)點(diǎn)周圍部署一定量的傳感節(jié)點(diǎn)可以完成所有目標(biāo)節(jié)點(diǎn)的監(jiān)測。具體結(jié)構(gòu)如圖1所示。

圖1 點(diǎn)覆蓋結(jié)構(gòu)圖

在圖1的待監(jiān)測正方形區(qū)域內(nèi),分布了多個(gè)目標(biāo)節(jié)點(diǎn),需要進(jìn)行傳感監(jiān)測,圓形代表每個(gè)傳感節(jié)點(diǎn)的感知范圍。在節(jié)點(diǎn)部署時(shí),充分結(jié)合節(jié)點(diǎn)能耗及通訊數(shù)據(jù)量來選擇合適數(shù)量的傳感節(jié)點(diǎn)。圖1中至少需要4個(gè)傳感節(jié)點(diǎn)才能完成對目標(biāo)區(qū)域所有目標(biāo)節(jié)點(diǎn)的監(jiān)測。這種監(jiān)測方式稱為局部監(jiān)測,不適合區(qū)域內(nèi)目標(biāo)節(jié)點(diǎn)動(dòng)態(tài)變化的情況。若目標(biāo)節(jié)點(diǎn)數(shù)量不固定,可以考慮用區(qū)域覆蓋的方式,在節(jié)點(diǎn)部署時(shí)對區(qū)域內(nèi)所有像素點(diǎn)完成感知覆蓋。區(qū)域覆蓋根據(jù)區(qū)域面積和區(qū)域內(nèi)的目標(biāo)節(jié)點(diǎn)數(shù)來選擇傳感節(jié)點(diǎn)數(shù),其要求是部署的傳感節(jié)點(diǎn)的感知范圍能夠覆蓋區(qū)域內(nèi)的每一個(gè)像素坐標(biāo),實(shí)現(xiàn)區(qū)域內(nèi)節(jié)點(diǎn)的全感知,其主要結(jié)構(gòu)如圖2所示。

圖2 區(qū)域覆蓋結(jié)構(gòu)圖

圖2完成了正方形目標(biāo)區(qū)域的全覆蓋,圖2中至少需要9個(gè)節(jié)點(diǎn)便能完成區(qū)域覆蓋,根據(jù)通信數(shù)據(jù)量和能耗可以增加傳感節(jié)點(diǎn)。在實(shí)際的無線傳感器網(wǎng)絡(luò)覆蓋應(yīng)用中,區(qū)域覆蓋使用范圍廣泛,常被用于各種領(lǐng)域的無線傳感器網(wǎng)絡(luò)監(jiān)測,因此本文以區(qū)域覆蓋為研究對象,優(yōu)化區(qū)域內(nèi)的目標(biāo)節(jié)點(diǎn)數(shù)。

1.2 數(shù)學(xué)模型

設(shè)需要進(jìn)行傳感節(jié)點(diǎn)布置的區(qū)域?yàn)槎S平面Area,在區(qū)域上投放的傳感節(jié)點(diǎn)數(shù)為N,每個(gè)節(jié)點(diǎn)的通信和感知半徑分別為R和r,R=2r,傳感節(jié)點(diǎn)集為Node={x1,x2,…xN},nodei={xi,yi,r},傳感點(diǎn)坐標(biāo)(xi,yi),將Area數(shù)字化離散為l×m個(gè)像素點(diǎn),像素點(diǎn)坐標(biāo)為p=(x,y),則2個(gè)節(jié)點(diǎn)的距離為[6]

(1)

像素點(diǎn)被傳感節(jié)點(diǎn)nodei覆蓋的概率P為

(2)

考慮到環(huán)境因素干擾,引入正態(tài)分布擾動(dòng),式(2)變?yōu)閇7]

P(x,y,nodei)=

(3)

re(0

λ1=re-r+d(nodei,p)

(4)

λ2=re+r-d(nodei,p)

(5)

在Area區(qū)域內(nèi)像素被傳感節(jié)點(diǎn)集覆蓋的概率為

(6)

根據(jù)傳感節(jié)點(diǎn)對像素節(jié)點(diǎn)的覆蓋情況,可以求解傳感節(jié)點(diǎn)對Area區(qū)域的覆蓋率,計(jì)算方法為[8]

(7)

在傳感網(wǎng)絡(luò)節(jié)點(diǎn)覆蓋優(yōu)化時(shí),根據(jù)網(wǎng)絡(luò)節(jié)點(diǎn)的能量及在感知范圍一定的情況下,盡可能保證Rarea(Node)最大。

2 基于WWO的傳感器網(wǎng)絡(luò)節(jié)點(diǎn)覆蓋

2.1 WWO

設(shè)問題解的維度為D,其中第d維水波x(d)執(zhí)行一次傳播得到x′(d),表示方法為[9]

x′(d)=x(d)+rand(-1,1)·λL(d)

(8)

式中:λ表示波長,L(d)表示第d維空間的搜索范圍,rand(-1,1)是[-1,1]隨機(jī)數(shù),x′表示新水波。若f(x′)>f(x),則用x′代替原水波x,將x′的水波高度設(shè)置為hmax,否則不替換原x,單波高變?yōu)閔max-1,波長也發(fā)生變化,變化方式為[10]

λ=λ·α-(f(x)-fmin+ε)/(fmax-fmin+ε)

(9)

式中:fmax和fmin分別為適應(yīng)度最大值和最小值,α表示水波衰減系數(shù),為了防止出現(xiàn)fmin和fmax相等時(shí)式(9)無意義,引入ε參數(shù),ε>0且無限趨近于0。

(10)

x′的波高重新設(shè)置為hmax,波長更新方法為[12]

(11)

在水波的能量不斷蓄積過程中,波高不斷增加,會發(fā)生碎波現(xiàn)象,1個(gè)水波會分解成多個(gè)獨(dú)立波。隨機(jī)選擇D中的k維對水波x*執(zhí)行碎波操作,產(chǎn)生的獨(dú)立波位置更新方法為[13]

x′(d)=x(d)+N(0,1)·βL(d)

(12)

式中:β表示碎波系數(shù),取值范圍[0.001,0.01];L(d)表示第d維長度。計(jì)算所有獨(dú)立波的適應(yīng)度值,與水波x*的適應(yīng)度值比較,取兩者中的最大值作為新的最優(yōu)水波x*。

2.2 WWO的傳感節(jié)點(diǎn)覆蓋流程

采用傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的網(wǎng)絡(luò)覆蓋率Rarea(Node)作為WWO的適應(yīng)度函數(shù)f(x)。首先隨機(jī)設(shè)置傳感節(jié)點(diǎn)集坐標(biāo),每一組坐標(biāo)作為1個(gè)水波Node。根據(jù)式(6)、(7)計(jì)算每個(gè)水波的適應(yīng)度值,然后執(zhí)行水波傳播、折射和碎波操作。根據(jù)水波的位置變化不斷更新適應(yīng)度值,記錄適應(yīng)度值最大的水波節(jié)點(diǎn)。不斷執(zhí)行水波的運(yùn)動(dòng)操作,直至傳感網(wǎng)絡(luò)節(jié)點(diǎn)的覆蓋率達(dá)到需求,或者更新迭代次數(shù)達(dá)到閾值。具體流程如圖3所示。

圖3 WWO的WSN節(jié)點(diǎn)覆蓋流程圖

3 實(shí)驗(yàn)仿真

為了驗(yàn)證WWO在無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)覆蓋中的性能,進(jìn)行實(shí)例仿真。仿真區(qū)域?qū)ο鬄?0 m*60 m,傳感節(jié)點(diǎn)參數(shù)r=5 m,N區(qū)間為[40,60],R=10 m,WWO默認(rèn)迭代次數(shù)200。首先采用WWO對WSN傳感節(jié)點(diǎn)的覆蓋性能進(jìn)行仿真;其次差異化設(shè)置N,驗(yàn)證不同N和迭代次數(shù)對應(yīng)的覆蓋性能;最后采用常用WSN覆蓋算法和本文算法分別進(jìn)行WSN節(jié)點(diǎn)覆蓋仿真,對比不同算法的覆蓋性能。

3.1 傳感節(jié)點(diǎn)覆蓋可視化

首先差異化設(shè)置N值,分別采用WWO對WSN進(jìn)行節(jié)點(diǎn)覆蓋仿真,其MATLAB的可視化覆蓋結(jié)構(gòu)如圖4所示。從可視化的圖4(e)發(fā)現(xiàn),在未采用WWO算法進(jìn)行節(jié)點(diǎn)部署之前,覆蓋率較低,出現(xiàn)了較嚴(yán)重的區(qū)域內(nèi)覆蓋不均衡的情況,而圖4(f)相比于其對應(yīng)的圖4(e),覆蓋效果更好,所有節(jié)點(diǎn)能夠較均勻地分布在區(qū)域內(nèi)。橫向?qū)Ρ劝l(fā)現(xiàn),當(dāng)N=50時(shí),優(yōu)化后的節(jié)點(diǎn)覆蓋圖最優(yōu);N=40時(shí),區(qū)域內(nèi)出現(xiàn)了較多未覆蓋到的空白;而N=60時(shí),雖然覆蓋率有緩慢提升,但明顯出現(xiàn)了節(jié)點(diǎn)冗余的情況,覆蓋區(qū)域內(nèi)出現(xiàn)了多處重疊。因此,從可視化圖4中發(fā)現(xiàn),選擇N=50進(jìn)行區(qū)域覆蓋更加合適。

圖4 MATLAB的可視化覆蓋結(jié)構(gòu)圖

3.2 不同N的覆蓋性能

3.2.1 不同N的覆蓋率

對不同N對應(yīng)的覆蓋率值進(jìn)行仿真統(tǒng)計(jì),結(jié)果如表1所示。

表1 不同N的覆蓋率表

從表1可知,N對區(qū)域的覆蓋性能影響明顯,隨著N增加,區(qū)域內(nèi)的覆蓋率提高。N從30增加至60時(shí),覆蓋率均值從0.665 8上升到了0.953 7。但當(dāng)N大于50后,覆蓋率的提升效果非常有限。N從50增加至60時(shí),覆蓋率均值僅提升了0.001 2,但是這10個(gè)節(jié)點(diǎn)數(shù)的增加明顯提升了成本和能耗,因此選擇N=50比較合適。

3.2.2 不同迭代次數(shù)的覆蓋率

本文默認(rèn)的迭代次數(shù)為200,前文仿真性能均為迭代次數(shù)為200的條件下獲得的結(jié)果,現(xiàn)差異化設(shè)置迭代次數(shù),N=50,驗(yàn)證覆蓋性能。從表2可知,隨著迭代次數(shù)的增加,覆蓋率先增加后達(dá)到穩(wěn)定。覆蓋率最高均值為0.968 1。從表2可以判斷,本文WWO覆蓋算法的收斂次數(shù)為300～400。

表2 不同迭代次數(shù)的覆蓋率表

3.3 不同算法的覆蓋性能

為了進(jìn)一步驗(yàn)證本文算法在WSN覆蓋中的性能,分別采用蟻群[14]、人工魚群[15]、粒子群[16]算法和本文WWO覆蓋算法對60 m*60 m區(qū)域進(jìn)行覆蓋性能仿真,N=50,r=5 m,仿真結(jié)果如圖5所示。

圖5 4種不同算法的覆蓋率性能圖

從圖5得,在覆蓋率性能方面,本文算法最優(yōu),達(dá)到穩(wěn)定時(shí)可以獲得95%左右的區(qū)域覆蓋率,粒子群次之,蟻群算法最差。從收斂性能方面看,蟻群算法最快,本文算法次之。綜合比較,本文算法相比于其他3種WSN覆蓋優(yōu)化算法,具有更優(yōu)的覆蓋性能。

4 結(jié)束語

采用WWO算法應(yīng)用于WSN節(jié)點(diǎn)覆蓋,能夠獲得較高的區(qū)域覆蓋率。選擇合適數(shù)量的傳感節(jié)點(diǎn)數(shù)和WWO迭代次數(shù),相比于常用WSN節(jié)點(diǎn)覆蓋優(yōu)化算法,本文算法能夠獲得更高的覆蓋率性能。后續(xù)研究將進(jìn)一步優(yōu)化WWO覆蓋算法關(guān)鍵步驟,以進(jìn)一步提高節(jié)點(diǎn)覆蓋優(yōu)化效率,提高大規(guī)模WSN節(jié)點(diǎn)布網(wǎng)的適用性。