基于Voronoi盲區(qū)的差分進化WSN部署算法

宋鑫宏+張樂+方光輝

摘要：為提高差分進化算法在無線傳感器網(wǎng)絡(luò)中的部署能力，提出了一種改進的差分進化部署算法。算法利用Voronoi圖的頂點可以確定盲區(qū)位置的特性，用盲區(qū)位置替代差分進化算法中變異操作的一個隨機向量，引導(dǎo)節(jié)點向盲區(qū)移動。仿真實驗結(jié)果表明，算法覆蓋效果明顯提升，該改進方法為群體智能算法在覆蓋部署上的應(yīng)用提供了新思路。

關(guān)鍵詞：無線傳感器網(wǎng)絡(luò)；差分進化；Voronoi圖；覆蓋部署

DOI：10.11907/rjdk.162754中圖分類號：TP312文獻標(biāo)識碼：A

文章編號：16727800（2017）004005902

0引言 由于無線傳感器網(wǎng)絡(luò)（Wireless Sensor Networks，WSN）中傳感器節(jié)點的數(shù)量巨大且大多部署于人員不易到達(dá)的區(qū)域，故可采用無人機隨機拋撒的形式將傳感器節(jié)點部署于監(jiān)測區(qū)域。隨機部署的傳感器節(jié)點，其初始化位置的網(wǎng)絡(luò)覆蓋率和連通性不可靠，節(jié)點冗余度高。針對該問題，使用具有移動能力的傳感器節(jié)點，使其按照一定的部署算法在監(jiān)測區(qū)域自動部署展開，達(dá)到一個合適的網(wǎng)絡(luò)覆蓋率后，可以使WSN正常工作完成感知任務(wù)。無人機攜帶可以運行部署算法的嵌入式處理器，傳感器節(jié)點只負(fù)責(zé)接收移動位置信息進行移動，以節(jié)省傳感器節(jié)點的制造成本與功耗，從而延長網(wǎng)絡(luò)生命周期。 WSN的覆蓋部署問題與群體智能行為中的自組織能力有緊密聯(lián)系，所以許多學(xué)者將群體智能算法應(yīng)用于該問題。群體智能算法只要給定優(yōu)化目標(biāo)，不需依賴優(yōu)化問題的特征信息，依靠算法本身的隨機搜索機制與進化機制即能在解空間內(nèi)進行搜索，并向全局最優(yōu)解逼近。群體智能算法的引入拓展了覆蓋控制問題的解決思路。文獻[1]提出通過增強因子對局部最優(yōu)粒子進行擾動的分簇粒子群算法；文獻[2]在魚群算法的聚群行為和追尾行為之后加入混沌搜索，提出了一種混沌魚群算法；文獻[3]提出了一種差分蜂群算法，將差分進化算法的變異與交叉操作作為附加成分加入到蜂群算法搜索過程中。在覆蓋部署問題中，僅依靠群體智能算法本身的隨機搜索機制尋優(yōu)，存在收斂速度慢、覆蓋效率不高等缺陷。本文的優(yōu)化思路是利用傳感器節(jié)點的Voronoi圖提取覆蓋部署問題中的特征信息，引導(dǎo)算法在監(jiān)測區(qū)域的盲區(qū)內(nèi)進行隨機搜索，提升差分進化算法的收斂速度和覆蓋率。

1問題描述

3Voronoi差分進化算法改進直接將DE算法用于WSN的覆蓋部署問題雖然能夠產(chǎn)生較優(yōu)解集，但算法中缺乏引導(dǎo)傳感器節(jié)點向盲區(qū)移動的機制，算法的收斂速度和尋優(yōu)能力還有待改進。Voronoi圖是傳感器節(jié)點連線構(gòu)成的Delaunay三角網(wǎng)作垂直平分線得到的網(wǎng)狀圖，Voronoi圖頂點的覆蓋情況能夠有效確定盲區(qū)位置[6]。在改進的Voronoi差分進化算法（Voronoi Differential Evolution， VDE）中，讓未覆蓋的Voronoi圖頂點參與變異操作，引導(dǎo)算法在盲區(qū)進行隨機搜索。算法步驟如下：步驟1：在監(jiān)測區(qū)域內(nèi)隨機部署N個節(jié)點，節(jié)點的位置集合為S={s1，s2，…，sN}，si=（xi，yi），并計算初始覆蓋率C。步驟2 ：對監(jiān)測區(qū)域進行Voronoi圖劃分[6]，Voronoi圖未覆蓋頂點的位置集合為V={vor1，vor2，…，vorN}。步驟3： 根據(jù)節(jié)點位置集合和Voronoi圖未覆蓋頂點位置的集合進行變異操作，vi，g=xr0，g+F（xr1，g-vorr2，g），得到所有節(jié)點的變異向量種群。步驟4： 根據(jù)式（5）對變異向量種群進行交叉操作，得到試驗向量種群。步驟5： 根據(jù)式（1）～式（3）計算試驗向量位置和當(dāng)前節(jié)點位置的覆蓋率，根據(jù)式（6）進行選擇操作，取較高覆蓋率的節(jié)點位置更新當(dāng)前節(jié)點位置，并相應(yīng)更新覆蓋率，直至所有節(jié)點比較結(jié)束。步驟6： 重復(fù)步驟2～步驟5進行迭代，直至滿足停止迭代條件。

4實驗仿真為驗證VDE的覆蓋效果，本文在Matlab平臺下進行了3組仿真實驗。實驗的監(jiān)測區(qū)域為二維平面，節(jié)點間可相互通信，傳感器節(jié)點的感知半徑Rs為2.5m。實驗中兩種算法的變異操作權(quán)重均取0.85，交叉概率均取0.5。實驗一在該監(jiān)測區(qū)域內(nèi)隨機拋灑30個節(jié)點，使用VDE尋優(yōu)某一次部署過程。圖1為隨機拋撒的傳感器節(jié)點的初始化位置，此時覆蓋率為76.41%。圖2為運行VDE迭代200次后的節(jié)點位置，此時覆蓋率為99.09%，部署過程中的覆蓋率變化如圖3所示。

實驗二取30個節(jié)點在30種隨機初始化位置下將VDE與DE進行覆蓋部署，兩種算法的平均覆蓋率變化如圖4所示。VDE的最終平均覆蓋率為99.29%，DE的最終平均覆蓋率為99.14%。實驗三取不同節(jié)點數(shù)量在30種隨機初始化位置下將VDE與DE進行覆蓋部署，得到的平均覆蓋率如表1所示，100%覆蓋成功的次數(shù)如表2所示。結(jié)果表明，VDE的平均覆蓋率與100%覆蓋監(jiān)測區(qū)域的次數(shù)都優(yōu)于DE。

5結(jié)語 本文針對WSN的覆蓋部署問題進行了研究，借助Voronoi圖提出了VDE算法。VDE算法利用Voronoi圖探測到傳感器節(jié)點周圍的盲區(qū)位置，用盲區(qū)位置替換節(jié)點位置參與DE算法的變異操作。在變異操作中有了盲區(qū)位置的引導(dǎo)，有效改進了DE算法局部搜索能力不強、收斂速度慢的缺點。下一步工作擬將VDE算法應(yīng)用于異構(gòu)WSN的覆蓋部署問題中，并把部署算法移植到無人機攜帶的嵌入式處理器中進行實際部署研究。

參考文獻：[1]丁旭，吳曉蓓，黃成.基于改進粒子群算法和特征點集的無線傳感器網(wǎng)絡(luò)覆蓋問題研究[J].電子學(xué)報，2016（4）：967973.

[2]李顯，劉明生，李燕，等.基于混沌魚群改進算法的無線傳感網(wǎng)覆蓋優(yōu)化[J].激光雜志，2015（1）：98101.

[3]熊偉麗，劉欣，陳敏芳，等.基于差分蜂群算法的無線傳感器網(wǎng)絡(luò)節(jié)點分布優(yōu)化[J].控制工程，2014（6）：10361040.

[4]宋鑫宏，方偉，熊偉麗.形心導(dǎo)向虛擬力的無線傳感器網(wǎng)絡(luò)部署算法[J].江南大學(xué)學(xué)報：自然科學(xué)版，2015（5）：549555.

[5]PRICE K.Differential evolution：a practical approach to global optimization[M].NewYork：SpringerVerlag，2007：3843.

[6]方偉，宋鑫宏.基于Voronoi圖盲區(qū)的無線傳感器網(wǎng)絡(luò)覆蓋控制部署策略[J].物理學(xué)報，2014（22）：132141.（責(zé)任編輯：黃?。?