SHADE算法在無線傳感器網(wǎng)絡(luò)節(jié)點分布優(yōu)化的應(yīng)用

張建波，王金玉

(東北石油大學(xué)電氣信息工程學(xué)院，黑龍江 大慶 163318)

0 引言

無線傳感器網(wǎng)絡(luò)(wireless sensor networks,WSN)是一種分布式傳感網(wǎng)絡(luò)，由部署在監(jiān)測區(qū)域內(nèi)的大量微型傳感器節(jié)點組成[1]。無線傳感器網(wǎng)絡(luò)目前廣泛應(yīng)用于標量數(shù)據(jù)采集。隨著電子工業(yè)的發(fā)展，WSN在抗震救災(zāi)、醫(yī)療保健方面發(fā)揮著越來越重要的作用。

WSN的高效穩(wěn)定性主要依賴于傳感器節(jié)點分布，使之能夠以最少的傳感器節(jié)點感知最大的目標區(qū)域。文獻[2]對人工魚群算法進行了改進，采用適應(yīng)度值對魚群進行分類，針對適應(yīng)值差的魚群，引入變異因子。文獻[3]將混沌運動引入粒子群算法，幫助粒子群逃逸局部最優(yōu)，但迭代次數(shù)過多，平均覆蓋率不高。文獻[4]針對人工蜂群算法中雇傭蜂的搜索方式在高維問題進化速度慢的問題，引入差分進化算法，提高了算法運行速度。文獻[5]將分層機制引入蜂群算法，可提高網(wǎng)絡(luò)覆蓋率，但迭代次數(shù)過多。

針對無線傳感器節(jié)點優(yōu)化問題，本文以網(wǎng)絡(luò)覆蓋率為目標函數(shù)，采用基于歷史成功的自適應(yīng)參數(shù)差分進化算法對目標函數(shù)進行求解。為了驗證本文所提算法的有效性和高效性，通過MATLAB仿真，分別與人工蜂群差分進化(SSDE)算法和差分進化(differential evolution,DE)算法進行對比。

1 WSN覆蓋模型

將二維被測區(qū)域S離散化為(m×n)個網(wǎng)格點，設(shè)網(wǎng)格點的坐標Ki=(xi,yi),i=1,2,…,m×n。若有N個無線傳感器節(jié)點位于WSN網(wǎng)絡(luò)中，則任意節(jié)點的坐標Lj=(xj,yj)，j=1,2,…,N，且傳感器監(jiān)測半徑均為r。網(wǎng)格點Ki到傳感器節(jié)點Lj的距離為:

(1)

本文采用布爾感知模型[6]，則傳感器節(jié)點Lj感知任意網(wǎng)格點Ki的概率為：

(2)

WSN中所有傳感器節(jié)點的覆蓋行為相互獨立。一個傳感器節(jié)點可以被多個傳感器節(jié)點同時感知。因此，對于被測區(qū)域中的網(wǎng)格點，被WSN覆蓋的聯(lián)合概率為:

(3)

被測區(qū)域每個網(wǎng)格點的覆蓋狀態(tài)均可由式(3)計算得到。由于WSN網(wǎng)絡(luò)中每個傳感器節(jié)點的覆蓋范圍呈圓形分布[7]，為了簡化計算，將WSN覆蓋的所有網(wǎng)格點與離散后的所有網(wǎng)格點數(shù)的比值定義為被測區(qū)域的覆蓋率。WSN覆蓋模型的目標函數(shù)如式(4)所示。

(4)

2 自適應(yīng)參數(shù)差分進化算法

基于歷史成功的自適應(yīng)參數(shù)差分進化(success-history based parameter adaptation for differential evolution,SHADE)算法是DE算法的一種高級變體，它使用了成功的控制參數(shù)設(shè)置的歷史記憶來指導(dǎo)未來控制參數(shù)值的選擇[8]。這使得采用SHADE算法求解非線性優(yōu)化問題時能夠精確和快速收斂到全局最優(yōu)。標準DE算法的迭代有四個基本步驟：初始化，變異，交叉和選擇。

2.1 初始化

DE優(yōu)化過程的第一步是通過為每個個體的決策向量分配隨機值，來創(chuàng)建候選解的初始種群。這些值必須位于決策向量的可行范圍內(nèi)(最大值和最小值之間)。初始化第i個決策向量的第j個分量為：

(5)

式中：randi,j[0,1]為0到1之間均勻分布的隨機數(shù)；上標0表示初始化。

2.2 變異

(6)

(7)

2.3 交叉

(8)

式中:K為{1,2，...，d}中的任意自然數(shù)。

2.4 選擇

(9)

在本文中，針對網(wǎng)絡(luò)覆蓋目標函數(shù)，為了使網(wǎng)絡(luò)節(jié)點覆蓋率最大化，適應(yīng)度函數(shù)表示為：

(10)

2.5 自適應(yīng)參數(shù)交叉率和比例因子

(11)

(12)

控制參數(shù)如表1所示。SHADE算法保留H條參數(shù)，以便在搜索過程中引導(dǎo)控制參數(shù)實現(xiàn)自適應(yīng)。即使某些子代的SCR、SF含有一組較差的值，存儲在前一代存儲器中的參數(shù)也不會受到影響。按式(13)～式(14)更新歷史存儲器M。

表1 控制參數(shù)

(13)

(14)

式中：MEANWA(SCR)和MEANWL(SF)分別為SCR的權(quán)重均值和SF的權(quán)重Lehmer均值。

初始化索引k=1，每當有一對新的SCR和SF插入存儲器時，索引k=k+1。當t代所有個體都不能產(chǎn)生比父代更好的試驗向量時，存儲器不更新。

2.6 SHADE算法在WSN優(yōu)化中的主要步驟

SHADE算法在WSN優(yōu)化中的主要步驟如下。

①初始化算法。設(shè)定種群規(guī)模Np、最大進化代數(shù)Tmax、決策變量維數(shù)d等基本參數(shù)。

③按照式(10)計算適應(yīng)度值。

⑤停止標準。判斷是否達到最大進化代數(shù)Tmax。如果是，則停止并輸出最優(yōu)解；如果不是，則轉(zhuǎn)到步驟②。

3 試驗仿真

3.1 參數(shù)設(shè)置

通過MATLAB進行仿真，采用SHADE算法對WSN優(yōu)化目標模型求解。被測區(qū)域S為100 m×100 m的正方形區(qū)域，區(qū)域離散化步長為1 m；假設(shè)有50個傳感器分布在被測區(qū)域S內(nèi)，每個傳感器節(jié)點的感知半徑為10 m。SHADE初始化參數(shù)：種群規(guī)模Np為200，Tmax為500，決策向量維度d為5，CR和F為0.5。為了驗證本文算法優(yōu)越性，分別采用SSDE和DE對WSN優(yōu)化問題進行對比，被測區(qū)域S不變，l為100，Gmax為500。

3.2 算法性能分析

分別采用SHADE、SSDE和DE對WSN優(yōu)化目標函數(shù)進行求解，三種算法收斂曲線如圖1所示。

圖1 三種算法收斂曲線

由圖1可知，應(yīng)用DE算法迭代次數(shù)最多且覆蓋率最低，這是因為DE原理簡單，控制參數(shù)少但是算法局部搜索能力較弱，在有限時間內(nèi)很難保證獲得全局最優(yōu)解。SSDE在DE算法中引入人工蜂群搜索策略，使其快速跳出局部最優(yōu)；但該方法存在疏于開發(fā)的問題，收斂速度較慢。SHADE所需迭代次數(shù)在三種算法中最少，同時覆蓋率也最高。這是因為該方法采用歷史存儲器M來儲存控制參數(shù)，避免陷入局部最優(yōu)解，加快了算法收斂速度。

為了進一步驗證算法性能，改變WSN中傳感器節(jié)點數(shù)目，得到三種算法覆蓋率隨節(jié)點變化曲線，如圖2所示。

圖2 覆蓋率隨節(jié)點變化曲線

從圖2可以看出，隨著節(jié)點數(shù)目的變化，SHADE覆蓋率均高于SSDE和DE。當節(jié)點數(shù)為60時，SHADE的覆蓋率達到99.8%，而SSDE和DE分別為94.4%和91.3%。

3.3 優(yōu)化結(jié)果分析

將三種算法各運行500次，統(tǒng)計其平均覆蓋率、最差覆蓋率、覆蓋率標準差以及達到最優(yōu)解時平均迭代次數(shù)，所得優(yōu)化結(jié)果如表2所示。

表2 三種算法優(yōu)化結(jié)果

SHADE優(yōu)化前后分布結(jié)果如圖3所示。

圖3 SHADE優(yōu)化前后分布結(jié)果圖

從表2可以看出，SHADE在三種算法中的每項指標都優(yōu)于SSDE和DE。SHADE的平均覆蓋率對比SSDE和DE分別提高了1.88%、5.17%。這是因為SHADE能夠避免算法早熟、快速跳出局部最優(yōu)值，提高了算法魯棒性，獲得較高的覆蓋率。另外,SHADE的平均迭代次數(shù)分別是SSDE的47.3%、DE的34.6%。優(yōu)化結(jié)果證明了SHADE能夠快速收斂到全局最優(yōu)解，并能保障算法精度。初始節(jié)點網(wǎng)絡(luò)中存在大量盲區(qū)和節(jié)點覆蓋冗余。經(jīng)過SHADE對節(jié)點優(yōu)化之后，傳感器節(jié)點能夠基本覆蓋被測區(qū)域，進一步保障了WSN的服務(wù)質(zhì)量。

4 結(jié)束語

本文利用SHADE算法對無線傳感網(wǎng)絡(luò)分布優(yōu)化問題進行了研究，通過仿真結(jié)果驗證了其有效性和高效性。SHADE通過保存交叉率和比例因子，自適應(yīng)地引導(dǎo)差分進化算法，提高了算法的魯棒性。針對無線傳感器網(wǎng)絡(luò)優(yōu)化問題，SHADE能夠在較少的迭代次數(shù)下獲得較高的覆蓋率，并可在節(jié)點數(shù)為60時，實現(xiàn)99.8%的目標區(qū)域覆蓋。未來將考慮WSN中傳感器節(jié)點自組織能力，使其能夠更好地適應(yīng)實際需要。