基于Voronoi圖的無線傳感器網絡柵欄覆蓋算法設計

郭新明　張瑾　陳偉　李康

摘? ?要：針對無線傳感器網絡中柵欄構建的問題，提出了一種基于監測區域Voronoi圖劃分的無線節點柵欄構建算法。仿真結果顯示，網絡中無線節點部署地越多，柵欄形成的可能性和組建柵欄的節點平均數量也會隨之增加。該算法能夠在無線傳感器網絡節點覆蓋密度較低且不均，已經形成了少量柵欄空洞的情況下快速實現監測區域的柵欄覆蓋，但空洞修復還需要進一步研究。

關鍵詞：無線傳感器網絡;柵欄覆蓋;Voronoi圖

中圖分類號：TP393? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?文獻標識碼：A

Design of Wireless Sensor Network Barrier Covering

Algorithm Based on Voronoi Diagram

GUO Xin-ming？覮，ZHANG Jin，CHEN Wei，LI Kang

（School of Computer，Xianyang Normal University，Xianyang，Shaanxi 712000，China）

Abstract：Aiming at the problem of barrier construction in wireless sensor network，a wireless sensor network barrier construction algorithm based on Voronoi graph division of monitoring area is proposed. Simulation results show that the more wireless nodes deployed in the network，the possibility of barrier formation and the average number of barrier nodes will increase. The algorithm can quickly realize the barrier coverage of the monitoring area when the wireless sensor network node coverage is low and uneven，and a few barrier holes have been formed，but the cavity repair needs further research.

Key words：wireless sensor networks（WSN）;barrier coverage;Voronoi diagram

隨著微電子技術、傳感技術、網絡技術的不斷進步，無線傳感器網絡技術及應用迅速成為當下WSN的熱點研究問題，柵欄覆蓋是WSN目標檢測中一個重要的研究方向，主要研究如何能有效監測移動目標穿越WSN覆蓋區域的問題[1]。柵欄覆蓋技術如今已經被廣泛地應用到軍事監測、工業和農業控制、安全防御等范疇[2]。柵欄覆蓋的概念是由Gage在機器人領域首次提出的[3]，Kumar等首次將柵欄覆蓋分為強柵欄和弱柵欄兩種覆蓋方式[4]。柵欄覆蓋研究中強柵欄覆蓋[5-9]和弱柵欄覆蓋[10-11]均取得了一些研究成果。文獻[12]中基于監測區域的 Voronoi圖劃分，可快速查找出WSN中的覆蓋漏洞，在只關注鄰近傳感器節點影響的寬松覆蓋條件下，論證出利用該圖生成的最小暴露進攻軌跡逼近于理想情況。文獻[13]運用監測區域的Voronoi 圖劃分整個部署區域，提出了基于 Voronoi 圖的無線傳感器網絡柵欄覆蓋策略，并監測部署區域是否存在柵欄覆蓋空洞，以決定節點是否通過有限移動重新部署空洞區域，實現了對柵欄部署區域的有效覆蓋。

針對WSN的柵欄覆蓋問題，提出了一種基于Voronoi圖的柵欄覆蓋構建算法，該算法能夠在WSN中節點覆蓋密度較低且不均，已經出現少量柵欄空洞的情況下快速實現監測區域的柵欄覆蓋，從而有效追蹤監測區域移動目標的移動軌跡。

1? ?模型構建及問題概述

1.1? ?網絡模型

仿真平臺是一個長L寬W的矩形監測區域，在該監測區域中隨機部署n個無線傳感器節點，所有無線節點同構，且部署后位置不再變化。

無線傳感器節點的感知模型可用一個二元組表示，其中Pi =（xi，yi）表示其在監測區域中的相對位置;r為無線節點的最大感知半徑，在該模型中若移動目標出現在節點的感知范圍內即可被感知，否則不能被感知，如圖1所示。

圖1? ?傳感器節點感知模型

定義1? ?起點集合和終點集合

起點集合：在覆蓋區域中，如果某個Voronoi多邊形的一條邊和覆蓋區域的左邊界重合，那么這個Voronoi多邊形中的傳感器節點屬于起點集合，該節點稱為起始無線節點，該Voronoi多邊形也稱為起始Voronoi多邊形。

終點集合：在覆蓋區域中，如果某個Voronoi多邊形的一條邊和覆蓋區域的右邊界重合，那么這個Voronoi多邊形中的傳感器節點屬于終點集合，該節點稱為終止無線節點，該Voronoi多邊形也稱為終止Voronoi多邊形。

定義2? ?穿越路徑

在矩形覆蓋區域中，任意經過該區域上下邊界的曲線段稱一個穿越路徑。

定義3? ?鄰居節點

在覆蓋區域中，由部署在該區域中的節點生成的Voronoi圖中，如果任意兩個Voronoi多邊形有一條公共邊，那么這兩個多邊形中的傳感器節點互為鄰居節點。

定義4? ?Voronoi柵欄

以任一起始Voronoi多邊形開始和任一終止Voronoi多邊形結束的，由若干相鄰Voronoi多邊形彼此依次連接形成的柵欄稱為一條Voronoi柵欄。

1.2? ?Voronoi柵欄覆蓋問題

基于Voronoi圖的WSN柵欄覆蓋問題是針對WSN中節點覆蓋密度偏低且不均，已經形成了少量柵欄空洞的情況下通過修復空洞來實現覆蓋柵欄重構的一種策略。本文提出的基于Voronoi圖的無線傳感器網絡柵欄覆蓋算法，只涉及Voronoi柵欄覆蓋的構建，Voronoi柵欄覆蓋構建后的空洞修復問題將是下一步的研究內容。

2? ?基于Voronoi圖的WSN柵欄構建算法

設計

2.1? ?算法設計思想

在監測區域內隨機部署n個無線傳感器節點，利用Voronoi圖的幾何原理為每個節點生成一個Voronoi多邊形，這樣就可以將監測區域劃分成n個子區域。即每一個子區域內有且只有一個無線傳感器節點。再根據這n個Voronoi多邊形的鄰接關系，運用弗洛伊德算法[14]尋找起始Voronoi多邊形和終止Voronoi多邊形間的最短路徑，并將此路徑作為Voronoi柵欄。

2.2? ?基于Voronoi圖的無線傳感器網絡柵欄覆蓋

算法

本課題中有關監測區域的Voronoi圖劃分，主要采用文獻[15]中的算法進行，算法的具體步驟如下：

步驟1? ?遍歷監測區域中的所有無線節點，對監測區域進行Voronoi圖劃分，按照定義3建立所有節點的鄰接矩陣，相鄰節點的權值均為1。

步驟2? ?根據定義1建立起點集合與終點集合。

步驟3? ?分別遍歷起點集合與終點集合，采用弗洛伊德算法查找每對起始無線節點和終止無線節點間的最短路徑，如果最短路徑存在，則執行步驟4，否則執行步驟5。

步驟4? ?將步驟3中求得的最短路徑存入Voronoi柵欄集，執行步驟5。

步驟5? ?若起點集合與終點集合遍歷結束執行步驟6，否則執行步驟3。

步驟6? ?清理Voronoi柵欄集，若多條Voronoi柵欄存在共同的Voronoi多邊形，則保存其中Voronoi多邊形數量最少的一條，其余的Voronoi柵欄刪除。

步驟7? ?返回清理后的Voronoi柵欄集。

3? ?仿真實驗與數據分析

3.1? ?實驗平臺構建

仿真平臺使用Eclipse進行構建，實驗環境為一個1366×768m的矩形監測區域，該區域內部署若干無線傳感器節點。如圖2所示，仿真平臺為監測區域的一個Voronoi劃分圖。

圖2? ?仿真實驗平臺效果圖

3.2? ?算法實現

仿真實驗發現，傳感器節點的網絡覆蓋率隨著節點數目的增加發生著變化。如圖3至圖6所示，分別為部署了50、100、150、200個傳感器節點的Voronoi柵欄覆蓋實驗效果圖。

圖3? ?部署50個傳感器節點的柵欄覆蓋圖

圖4? ?部署100個傳感器節點的柵欄覆蓋圖

圖5? ?部署150個傳感器節點的柵欄覆蓋圖

圖6? ?部署200個傳感器節點的柵欄覆蓋圖

3.3? ?實驗數據分析

根據仿真實驗結果可知，隨著監測區域中部署節點數量的增加，構成柵欄覆蓋的Voronoi多邊形數量也會隨之增多。圖7是監測區域部署的傳感器節點數與柵欄覆蓋的Voronoi多邊形平均數之間的變化關系，圖8反映了監測區域部署的傳感器節點數與構造的Voronoi柵欄數間的變化關系。

圖7? ?部署節點數與構成柵欄的Voronoi

多邊形平均數關系圖

圖8? ?部署節點數與Voronoi柵欄數目關系圖

從實驗結果可以看出，構成柵欄覆蓋的Voronoi多邊形數目隨著部署傳感器節點數量的增加呈遞增趨勢，當部署傳感器節點的數量增多時，柵欄的數目也隨之增加。

4? ?結? 論

針對WSN的柵欄覆蓋問題，提出了一種基于Voronoi圖的WSN柵欄構建算法。從實驗數據分析可知，構成柵欄的Voronoi多邊形數目隨著部署傳感器節點數量的增加而增加，當部署傳感器節點的密度升高，構建的柵欄數目也呈遞增趨勢。該算法能夠在無線傳感器網絡節點覆蓋密度較低且不均，已經形成了少量柵欄空洞的情況下快速實現監測區域的柵欄覆蓋，為下一步開展空洞修復研究奠定基礎。

參考文獻

[1]? ? PARK D J，KIM K，LEE P J.Public key encryption withconjunctive field keyword search[M]//Information Security Applications. Berlin/Heidelberg：Springer，2004：73—86.

[2]? ? HOU J C，YAU D K Y，MA C Y T，et al.Coverage in wireless sensor networks[J]. Guide to Wirdless Sensor Networks，2009，3（5）：47—79.

[3]? ? GAGE D W.Command control for many-robot systems[J].Unmanned Systems，1992，10（4）：28—34.

[4]? ? KUMAR S，LAI T H，ARORA A.Barrier coverage with wireless sensors[C]//MobiCom 2005：Proceedings of the 11th Annual International Conference on Mobile Computing and Networking.NewYork：ACM，2005：284—298.

[5]? ? 郭新明.高效無線傳感器網絡強k-柵欄覆蓋節能算法[J].計算機應用，2013，33（8）：2014—2017.

[6]? ? 韓睿松.無線多媒體傳感器網絡覆蓋增強與拓撲控制技術研究[D].北京：北京交通大學，2018.

[7]? ? 范興剛，王超，楊靜靜，等.一種基于選擇框的有向K-柵欄構建算法[J].計算機學報，2016，39（5）：946—960.

[8]? ? 郭新明，王宇，魏浩，等.視角受限的無線傳感器網絡強柵欄覆蓋算法設計[J].咸陽師范學院學報，2016，31（6）：58—61.

[9]? ? 鄧緋.無線傳感器網絡柵欄覆蓋的研究與仿真[J].西南師范大學學報：自然科學版，2015，40（5）：94—100.

[10]? 吳菊英，馮秀芳.有向傳感器網絡中弱柵欄覆蓋構建算法[J].計算機工程與設計，2016，37（10）：2685—2689.

[11]? 郭新明，李康，陳偉，等.有向無線傳感器網絡弱柵欄覆蓋構建算法設計[J].咸陽師范學院學報，2018，33（6）：53—56.

[12]? 秦寧寧，蓋祎，張林，等. Voronoi圖在無線傳感器網絡柵欄覆蓋中的應用研究[J]. 計算機應用研究，2008，25（3）：863—865.

[13]? 黨小超，馬如倉，郝占軍.基于Voronoi的無線傳感器網絡柵欄覆蓋策略[J].計算機工程與應用，2018，54（2）：91—96.

[14]? 嚴蔚敏，吳偉民.數據結構（C語言版）[M].北京：清華大學出版社，2007：190—192.

[15]? 周培德.計算幾何——算法設計、分析與應用[M].第5版.北京：清華大學出版社，2016：146—147.