張建波，王金玉

(東北石油大學(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)用于標(biāo)量數(shù)據(jù)采集。隨著電子工業(yè)的發(fā)展，WSN在抗震救災(zāi)、醫(yī)療保健方面發(fā)揮著越來越重要的作用。

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

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

1 WSN覆蓋模型

將二維被測區(qū)域S離散化為(m×n)個網(wǎng)格點，設(shè)網(wǎng)格點的坐標(biāo)Ki=(xi,yi),i=1,2,…,m×n。若有N個無線傳感器節(jié)點位于WSN網(wǎng)絡(luò)中，則任意節(jié)點的坐標(biāo)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覆蓋模型的目標(biāo)函數(shù)如式(4)所示。

(4)

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

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

2.1 初始化

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

(5)

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

2.2 變異

(6)

(7)

2.3 交叉

(8)

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

2.4 選擇

(9)

在本文中，針對網(wǎng)絡(luò)覆蓋目標(biāo)函數(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，每當(dāng)有一對新的SCR和SF插入存儲器時，索引k=k+1。當(dāng)t代所有個體都不能產(chǎn)生比父代更好的試驗向量時，存儲器不更新。

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

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

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

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

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

3 試驗仿真

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

通過MATLAB進(jìn)行仿真，采用SHADE算法對WSN優(yōu)化目標(biāo)模型求解。被測區(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)化問題進(jìn)行對比，被測區(qū)域S不變，l為100，Gmax為500。

3.2 算法性能分析

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

圖1 三種算法收斂曲線

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

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

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

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

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

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

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

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

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

從表2可以看出，SHADE在三種算法中的每項指標(biāo)都優(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ū)域，進(jìn)一步保障了WSN的服務(wù)質(zhì)量。

4 結(jié)束語

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