一種增強型事件驅動策略的覆蓋空洞補償算法

孫澤宇，高春玲，曹仰杰2，邢蕭飛3，聶雅琳

（1.洛陽理工學院計算機與信息工程學院，河南洛陽 471023； 2.鄭州大學軟件學院，鄭州 450001；3.廣州大學計算機與軟件教育學院，廣州 510006）

一種增強型事件驅動策略的覆蓋空洞補償算法

孫澤宇1，高春玲1，曹仰杰2，邢蕭飛3，聶雅琳1

（1.洛陽理工學院計算機與信息工程學院，河南洛陽 471023； 2.鄭州大學軟件學院，鄭州 450001；3.廣州大學計算機與軟件教育學院，廣州 510006）

針對無線傳感器網絡體系在隨機部署過程中出現覆蓋空洞的現象，借助于概率模型提出了一種CHCAEDS（基于事件驅動策略的覆蓋空洞補償算法）。該算法首先對隨機部署的特性進行驗證，給出隨機部署表示形式；然后利用概率相關知識對監測區域內覆蓋期望和節點數量進行求解，以達到使用最少數量的節點覆蓋最大的面積。仿真實驗表明，與其他算法相比，CHCAEDS在網絡生存周期和算法運行時間上分別提高了12.59%和10.82%。

無線傳感器網絡；覆蓋質量；覆蓋空洞；事件驅動策略

0 引 言

隨著信息技術的快速進步，無線傳感器網絡得到前所未有的發展，已被廣泛應用于軍事國防［1-2］、衛生醫療、交通運輸［3-4］、環境監測、災難救援［5-6］和智能家居等各種工程領域。近幾年，國內外專家學者針對無線傳感器網絡的覆蓋問題做了大量研究工作。文獻［7］提出一種基于Voronoi（泰森多邊形分割法）的有效覆蓋區域空洞修補算法，該算法在滿足一定覆蓋質量的提前下，對覆蓋空洞進行合理地增加工作節點以提高當前的覆蓋率，同時尋找合理的修補位置信息，以保證整個網絡的連通性。文獻［8］提出了ETCA（節能目標覆蓋算法），其基本思想是利用線性規劃原理完成對監測區域的有效覆蓋。文獻［9］給出了一種ECAPM（基于概率模型的增強型覆蓋算法），該算法的基本思想是將節點的能量以鏈表形式加以表示，同時對鏈表中的各個節點的能量進行計算，最終完成對監測區域的有效覆蓋。

在節點覆蓋過程中主要解決以下幾個問題：（1）不要求對整個監測區域進行完全覆蓋，而是對所關注的目標節點進行有效地覆蓋；（2）采用隨機投撒方式部署傳感器節點時，如何避免在監測區域內出現覆蓋空洞現象；（3）如何合理部署節點，抑制節點能量的快速消耗，同時以最少的傳感器節點數量完成對監測區域的有效覆蓋，以達到延長網絡生存周期的目的。

1 覆蓋質量

為了進一步研究無線傳感器網絡覆蓋問題，并使問題簡單化和易操作化，本文對所提出的CHCAEDS（基于事件驅動策略的覆蓋空洞補償算法）作了如下4種假設：

假設1：初始時刻所有傳感器節點的感知半徑與通信半徑均為圓盤型，各節點能量相同。

假設2：感知半徑遠小于正方形監測區域的邊長，忽略對監測區域的邊界效應。

假設3：各節點具有唯一標識碼，且不依賴于某種定位算法。

假設4：各節點工作期間，其形態為同形異構，并且時間上也同步。

定義1：當目標節點被有限個傳感器節點連續覆蓋時，稱為有效覆蓋；有效覆蓋的所有工作節點的覆蓋面積與監測區域面積的比值稱為有效覆蓋率CP。

式中，si和sj分別為第i個和第j個傳感器節點的覆蓋面積，S為監測區域面積。

定義2：當目標節點被k個傳感器節點所覆蓋時，稱之為k度覆蓋。定義3：由覆蓋節點組成的集合稱之為覆蓋集。定理1：隨機部署傳感器節點服從于節點密度為λ、隨機變量為N（s）的泊松分布。

證明：設單個傳感器節點的覆蓋面積為s，根據概率相關知識中的二項式定理可知，由k個傳感器節點共同完成對目標節點覆蓋時的聯合概率為

式中，p為任意節點覆蓋率，即p=|s|/S；N為所有傳感器節點數量；CkN為二次式系數。

對于整個監測區域而言，傳感器節點密度為

將節點覆蓋率和式（3）代入式（2），化簡后可得：

當傳感器節點數量趨于無窮，即N→∞時，化簡式（4）可得：

證明完畢。

監測區域內傳感器節點冗余節點的數量直接影響覆蓋質量，如何采用最少節點完成對監測區域的有效覆蓋，是本文討論的另一個重點問題。當移動目標在監測區域內被多個傳感器節點覆蓋N次后，其N+1次覆蓋期望值決定于后繼覆蓋的優劣，因此，本文引入了定理2。

定理2：完成對有效區域覆蓋時，所需傳感器節點數量最小值為N=S ln（1-p）/（πr2），式中，r為傳感器節點的感知半徑。

證明：任意節點在監測區域內的覆蓋率為p= πr2/S，未被覆蓋的概率為q=1-πr2/S。根據定理1可知，在整個監測區域內，沒有被任意節點所覆蓋的聯合概率為

化簡后可得：

監測區域內，任意位置被覆蓋的概率為

將節點密度λ=N/S代入公式（8），兩邊取對數得：

因此，當完成對監測區域有效覆蓋時，所需最少傳感器節點數量為N=S ln（1-p）/（πr2），證明完畢。

2 體系評估

為了更好地體現仿真效果，現對仿真參數作如下說明，如表1所示。

表1 仿真參數說明

實驗1：本文采用MATLAB7軟件對網絡生存周期和算法運行時間進行了仿真實驗，以節點密度參數λ作為仿真對象。在網絡生存周期實驗中，本文采用的監測區域平臺分別為100×100和200× 200；在測定算法運行時間的實驗中，本文采用的監測區域平臺為300×300。仿真實驗環境為WIN XP、RAM 2 G和CPU雙核1.7 G。

圖1～圖6分別給出了本文提出的CHCAEDS、ETCA和ECAPM的傳感器節點和目標節點數量與網絡生存周期以及算法運行時間的對比仿真結果。圖1和圖3分別給出了監測區域平臺為100×100和200×200時傳感器節點數量與網絡生存周期的對比。從圖中可以看出，隨著傳感器節點數量的增加，網絡生存周期也在穩步提升，當傳感器節點數量分別為50和150時，CHCAEDS的網絡生存周期的平均值高于另外兩種算法12.59%。圖2和圖4分別給出了監測區域平臺為100×100和200×200時目標節點數量與網絡生存周期的對比。從圖中可以看出，當目標節點數量增加時，所需覆蓋目標節點的工作傳感器節點數量隨之增加，網絡的能耗加大，因此整個網絡的生存周期有所下降，當λ=0.8時，CHCAEDS的下降速度較為平緩，與另外兩種算法相比，延長了網絡生存周期，其平均值為10.82%。圖5和圖6分別給出了監測區域平臺為300×300時傳感器節點和目標節點數量與算法運行時間的對比。從圖中可以看出，當傳感器節點數量增加時，算法的運行時間也會增加，但CHCAEDS的運行時間小于ECAPM，其原因在于，ECAPM忽略了冗余節點的存在，僅依賴于傳感器節點數量的增加來提高對監測區域的覆蓋，從而達到有效覆蓋的目的；而CHCAEDS則是利用節點之間的轉換來達到覆蓋的平衡。

圖1 100×100傳感器節點數量與網絡生存周期對比

圖2 100×100目標節點數量與網絡生存周期對比

實驗2：以λ=0.3和0.8為基準參數，對300× 3 00監測區域初始時刻的傳感器節點數量和CH-CAEDS優化后的傳感器節點數量進行仿真實驗。

圖3 200×200傳感器節點數量與網絡生存周期對比

圖4 200×200目標節點數量與網絡生存周期對比

圖5 300×300傳感器節點數量與算法運行時間對比

圖6 300×300目標節點數量與算法運行時間對比

圖7～圖10給出了傳感器節點在初始時刻與CHCAEDS優化后的布置示意圖。從圖中可以看出，λ=0.3和λ=0.8時，初始時刻監測區域內存在大量的冗余節點，通過CHCAEDS優化后，抑制了冗余節點的產生，使其轉入休眠狀態，保存了整個網絡的能量，延長了網絡生存周期。

圖7 λ=0.3時，初始時刻傳感節點部署示意圖

圖8 λ=0.3時，CHCAEDS傳感節點部署示意圖

圖9 λ=0.8時，初始時刻傳感節點部署示意圖

圖10 λ=0.8時，CHCAEDS傳感節點部署示意圖

3 結束語

本文在對無線傳感器網絡覆蓋問題進行分析的基礎上提出了一種覆蓋空洞補償算法。首先，利用概率相關知識給出了部署在監測區域內的傳感器節點分布形態；而后對傳感器節點覆蓋期望值和最少節點數量的函數關系進行求解，給出了覆蓋監測區域內所需最少傳感器節點數量的求解方法；最后，通過仿真實驗驗證了CHCAEDS與ETCA、ECAPM在不同監測區域內的網絡生存周期和運行時間的對比過程，證明了本文算法的有效性和穩定性。

今后的工作重點將主要集中在具有邊界效應的非線性覆蓋和參數可調的有效覆蓋。

［1］ 孫澤宇，伍衛國，王換招.無線傳感器網絡中一種增強型覆蓋控制算法［J］.電子學報，2015，43（3）：466-474.

［2］ 邢蕭飛，謝東青，鄭瑾.無線傳感器網絡k度覆蓋控制算法［J］.中南大學學報：自然科學版，2014，45（11）：3832-3839.

［3］ 李猛，丁代榮，郭廷立.一種無線傳感器網絡節點隨機部署策略［J］.計算機工程，2012，38（5）：99-101.

［4］ 孫澤宇，趙國增.基于節點調度策略的能量有效覆蓋算法［J］.光通信研究，2012，（6）：52-55.

［5］ 孟凡治，王換招，何暉.基于聯合感知模型的無線傳感器網絡連通性覆蓋協議［J］.電子學報，2011，39 （4）：772-779.

［6］ Mini S，Siba K U，Samrat L S.Sensor deployment and scheduling for target coverage problem in wireless sensor networks［J］.IEEE Sensros Journal，2014，14 （3）：636-644.

［7］ 趙春江，吳華瑞，劉強.基于Voronoi的無線傳感器網絡控制優化策略［J］.通信學報，2013，34（9）：115-122.

［8］ Xing Xiaofei，Wang Guojun，Li Jie.Poly-type target coverage scheme for heterogeneous wireless sensor networks using linear programming［J］.Wireless Communications and Mobile Computing，2014，14（8）：1397-1408.

［9］ Sun Zeyu，Wang Huanzhao，Wu Weiguo.ECAPM：An enhanced coverage algorithm in wireless sensor network based on probability model［J］.International Journal of Distributed Sensor Networks，2015，15（1）：1-11.

An Enhance Event-Driven Strategy Coverage Holes Compensation Algorithms

SUN Ze-yu1，GAO Chun-ling1，CAO Yang-jie2，XING Xiao-fei3，NIE Ya-lin1
（1.School of Computer and Information Engineering，Luoyang Institute of Science Technology，Luoyang 471023，China；2.School of Software，Zhengzhou University，Zhengzhou 450001，China；3.School of Computer Science and Software Education，Guangzhou University，Guangzhou 510006，China）

Coverage holes phenomena is appeared in the process of random deployment of wireless sensor network systems. This paper presents a probabilistic model by means of event-driven policy coverage holes compensation method（Coverage Holes Compensation Algorithms Based on Event-Driven Strategy，CHCAEDS）.Firstly，the characteristics of random deployment are verified and the representation of random deployment is given.Then，based on the probabilistic method，the desired coverage and the number of nodes within the surveillance area are solved in order to achieve maximum coverage area using minimum number of nodes.Finally，the simulation result show that the CHCAEDS can improvethe network life cycle and the algorithm running time by 12.59%and 10.82%when comparing with other algorithms.

wireless sensor networks；coverage quality；coverage holes；event-driven strategy

TP393

A

1005-8788（2016）03-0022-04

10.13756/j.gtxyj.2016.03.008

2016-01-06

國家自然科學基金資助項目（U1304603，61503174）；國家博士后基金資助項目（2014M562153）；河南省科技攻關重點資助項目（142102210471，1421002210568，162102210113）；河南省教育廳自然科學重點基金資助項目（14B520099，16A520063）；廣州市自然科學基金資助項目（1201430560）

孫澤宇（1977-），男，吉林長春人。副教授，博士，主要研究方向為無線傳感器網絡與物聯網。