宋鑫宏+張樂+方光輝

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

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

DOI：10.11907/rjdk.162754中圖分類號：TP312文獻(xiàn)標(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é)接收移動位置信息進(jìn)行移動，以節(jié)省傳感器節(jié)點的制造成本與功耗，從而延長網(wǎng)絡(luò)生命周期。 WSN的覆蓋部署問題與群體智能行為中的自組織能力有緊密聯(lián)系，所以許多學(xué)者將群體智能算法應(yīng)用于該問題。群體智能算法只要給定優(yōu)化目標(biāo)，不需依賴優(yōu)化問題的特征信息，依靠算法本身的隨機搜索機制與進(jìn)化機制即能在解空間內(nèi)進(jìn)行搜索，并向全局最優(yōu)解逼近。群體智能算法的引入拓展了覆蓋控制問題的解決思路。文獻(xiàn)[1]提出通過增強因子對局部最優(yōu)粒子進(jìn)行擾動的分簇粒子群算法；文獻(xiàn)[2]在魚群算法的聚群行為和追尾行為之后加入混沌搜索，提出了一種混沌魚群算法；文獻(xiàn)[3]提出了一種差分蜂群算法，將差分進(jìn)化算法的變異與交叉操作作為附加成分加入到蜂群算法搜索過程中。在覆蓋部署問題中，僅依靠群體智能算法本身的隨機搜索機制尋優(yōu)，存在收斂速度慢、覆蓋效率不高等缺陷。本文的優(yōu)化思路是利用傳感器節(jié)點的Voronoi圖提取覆蓋部署問題中的特征信息，引導(dǎo)算法在監(jiān)測區(qū)域的盲區(qū)內(nèi)進(jìn)行隨機搜索，提升差分進(jìn)化算法的收斂速度和覆蓋率。

1問題描述

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

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

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

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

[2]李顯，劉明生，李燕，等.基于混沌魚群改進(jìn)算法的無線傳感網(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é)任編輯：黃健）