基于Voronoi盲區的差分進化WSN部署算法

宋鑫宏+張樂+方光輝

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

關鍵詞：無線傳感器網絡；差分進化；Voronoi圖；覆蓋部署

DOI：10.11907/rjdk.162754中圖分類號：TP312文獻標識碼：A

文章編號：16727800（2017）004005902

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

1問題描述

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

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

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

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

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

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

[3]熊偉麗，劉欣，陳敏芳，等.基于差分蜂群算法的無線傳感器網絡節點分布優化[J].控制工程，2014（6）：10361040.

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

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

[6]方偉，宋鑫宏.基于Voronoi圖盲區的無線傳感器網絡覆蓋控制部署策略[J].物理學報，2014（22）：132141.（責任編輯：黃健）