一種增強(qiáng)型事件驅(qū)動(dòng)策略的覆蓋空洞補(bǔ)償算法

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

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

一種增強(qiáng)型事件驅(qū)動(dòng)策略的覆蓋空洞補(bǔ)償算法

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

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

針對(duì)無線傳感器網(wǎng)絡(luò)體系在隨機(jī)部署過程中出現(xiàn)覆蓋空洞的現(xiàn)象，借助于概率模型提出了一種CHCAEDS（基于事件驅(qū)動(dòng)策略的覆蓋空洞補(bǔ)償算法）。該算法首先對(duì)隨機(jī)部署的特性進(jìn)行驗(yàn)證，給出隨機(jī)部署表示形式；然后利用概率相關(guān)知識(shí)對(duì)監(jiān)測(cè)區(qū)域內(nèi)覆蓋期望和節(jié)點(diǎn)數(shù)量進(jìn)行求解，以達(dá)到使用最少數(shù)量的節(jié)點(diǎn)覆蓋最大的面積。仿真實(shí)驗(yàn)表明，與其他算法相比，CHCAEDS在網(wǎng)絡(luò)生存周期和算法運(yùn)行時(shí)間上分別提高了12.59%和10.82%。

無線傳感器網(wǎng)絡(luò)；覆蓋質(zhì)量；覆蓋空洞；事件驅(qū)動(dòng)策略

0 引 言

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

在節(jié)點(diǎn)覆蓋過程中主要解決以下幾個(gè)問題：（1）不要求對(duì)整個(gè)監(jiān)測(cè)區(qū)域進(jìn)行完全覆蓋，而是對(duì)所關(guān)注的目標(biāo)節(jié)點(diǎn)進(jìn)行有效地覆蓋；（2）采用隨機(jī)投撒方式部署傳感器節(jié)點(diǎn)時(shí)，如何避免在監(jiān)測(cè)區(qū)域內(nèi)出現(xiàn)覆蓋空洞現(xiàn)象；（3）如何合理部署節(jié)點(diǎn)，抑制節(jié)點(diǎn)能量的快速消耗，同時(shí)以最少的傳感器節(jié)點(diǎn)數(shù)量完成對(duì)監(jiān)測(cè)區(qū)域的有效覆蓋，以達(dá)到延長(zhǎng)網(wǎng)絡(luò)生存周期的目的。

1 覆蓋質(zhì)量

為了進(jìn)一步研究無線傳感器網(wǎng)絡(luò)覆蓋問題，并使問題簡(jiǎn)單化和易操作化，本文對(duì)所提出的CHCAEDS（基于事件驅(qū)動(dòng)策略的覆蓋空洞補(bǔ)償算法）作了如下4種假設(shè)：

假設(shè)1：初始時(shí)刻所有傳感器節(jié)點(diǎn)的感知半徑與通信半徑均為圓盤型，各節(jié)點(diǎn)能量相同。

假設(shè)2：感知半徑遠(yuǎn)小于正方形監(jiān)測(cè)區(qū)域的邊長(zhǎng)，忽略對(duì)監(jiān)測(cè)區(qū)域的邊界效應(yīng)。

假設(shè)3：各節(jié)點(diǎn)具有唯一標(biāo)識(shí)碼，且不依賴于某種定位算法。

假設(shè)4：各節(jié)點(diǎn)工作期間，其形態(tài)為同形異構(gòu)，并且時(shí)間上也同步。

定義1：當(dāng)目標(biāo)節(jié)點(diǎn)被有限個(gè)傳感器節(jié)點(diǎn)連續(xù)覆蓋時(shí)，稱為有效覆蓋；有效覆蓋的所有工作節(jié)點(diǎn)的覆蓋面積與監(jiān)測(cè)區(qū)域面積的比值稱為有效覆蓋率CP。

式中，si和sj分別為第i個(gè)和第j個(gè)傳感器節(jié)點(diǎn)的覆蓋面積，S為監(jiān)測(cè)區(qū)域面積。

定義2：當(dāng)目標(biāo)節(jié)點(diǎn)被k個(gè)傳感器節(jié)點(diǎn)所覆蓋時(shí)，稱之為k度覆蓋。定義3：由覆蓋節(jié)點(diǎn)組成的集合稱之為覆蓋集。定理1：隨機(jī)部署傳感器節(jié)點(diǎn)服從于節(jié)點(diǎn)密度為λ、隨機(jī)變量為N（s）的泊松分布。

證明：設(shè)單個(gè)傳感器節(jié)點(diǎn)的覆蓋面積為s，根據(jù)概率相關(guān)知識(shí)中的二項(xiàng)式定理可知，由k個(gè)傳感器節(jié)點(diǎn)共同完成對(duì)目標(biāo)節(jié)點(diǎn)覆蓋時(shí)的聯(lián)合概率為

式中，p為任意節(jié)點(diǎn)覆蓋率，即p=|s|/S；N為所有傳感器節(jié)點(diǎn)數(shù)量；CkN為二次式系數(shù)。

對(duì)于整個(gè)監(jiān)測(cè)區(qū)域而言，傳感器節(jié)點(diǎn)密度為

將節(jié)點(diǎn)覆蓋率和式（3）代入式（2），化簡(jiǎn)后可得：

當(dāng)傳感器節(jié)點(diǎn)數(shù)量趨于無窮，即N→∞時(shí)，化簡(jiǎn)式（4）可得：

證明完畢。

監(jiān)測(cè)區(qū)域內(nèi)傳感器節(jié)點(diǎn)冗余節(jié)點(diǎn)的數(shù)量直接影響覆蓋質(zhì)量，如何采用最少節(jié)點(diǎn)完成對(duì)監(jiān)測(cè)區(qū)域的有效覆蓋，是本文討論的另一個(gè)重點(diǎn)問題。當(dāng)移動(dòng)目標(biāo)在監(jiān)測(cè)區(qū)域內(nèi)被多個(gè)傳感器節(jié)點(diǎn)覆蓋N次后，其N+1次覆蓋期望值決定于后繼覆蓋的優(yōu)劣，因此，本文引入了定理2。

定理2：完成對(duì)有效區(qū)域覆蓋時(shí)，所需傳感器節(jié)點(diǎn)數(shù)量最小值為N=S ln（1-p）/（πr2），式中，r為傳感器節(jié)點(diǎn)的感知半徑。

證明：任意節(jié)點(diǎn)在監(jiān)測(cè)區(qū)域內(nèi)的覆蓋率為p= πr2/S，未被覆蓋的概率為q=1-πr2/S。根據(jù)定理1可知，在整個(gè)監(jiān)測(cè)區(qū)域內(nèi)，沒有被任意節(jié)點(diǎn)所覆蓋的聯(lián)合概率為

化簡(jiǎn)后可得：

監(jiān)測(cè)區(qū)域內(nèi)，任意位置被覆蓋的概率為

將節(jié)點(diǎn)密度λ=N/S代入公式（8），兩邊取對(duì)數(shù)得：

因此，當(dāng)完成對(duì)監(jiān)測(cè)區(qū)域有效覆蓋時(shí)，所需最少傳感器節(jié)點(diǎn)數(shù)量為N=S ln（1-p）/（πr2），證明完畢。

2 體系評(píng)估

為了更好地體現(xiàn)仿真效果，現(xiàn)對(duì)仿真參數(shù)作如下說明，如表1所示。

表1 仿真參數(shù)說明

實(shí)驗(yàn)1：本文采用MATLAB7軟件對(duì)網(wǎng)絡(luò)生存周期和算法運(yùn)行時(shí)間進(jìn)行了仿真實(shí)驗(yàn)，以節(jié)點(diǎn)密度參數(shù)λ作為仿真對(duì)象。在網(wǎng)絡(luò)生存周期實(shí)驗(yàn)中，本文采用的監(jiān)測(cè)區(qū)域平臺(tái)分別為100×100和200× 200；在測(cè)定算法運(yùn)行時(shí)間的實(shí)驗(yàn)中，本文采用的監(jiān)測(cè)區(qū)域平臺(tái)為300×300。仿真實(shí)驗(yàn)環(huán)境為WIN XP、RAM 2 G和CPU雙核1.7 G。

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

圖1 100×100傳感器節(jié)點(diǎn)數(shù)量與網(wǎng)絡(luò)生存周期對(duì)比

圖2 100×100目標(biāo)節(jié)點(diǎn)數(shù)量與網(wǎng)絡(luò)生存周期對(duì)比

實(shí)驗(yàn)2：以λ=0.3和0.8為基準(zhǔn)參數(shù)，對(duì)300× 3 00監(jiān)測(cè)區(qū)域初始時(shí)刻的傳感器節(jié)點(diǎn)數(shù)量和CH-CAEDS優(yōu)化后的傳感器節(jié)點(diǎn)數(shù)量進(jìn)行仿真實(shí)驗(yàn)。

圖3 200×200傳感器節(jié)點(diǎn)數(shù)量與網(wǎng)絡(luò)生存周期對(duì)比

圖4 200×200目標(biāo)節(jié)點(diǎn)數(shù)量與網(wǎng)絡(luò)生存周期對(duì)比

圖5 300×300傳感器節(jié)點(diǎn)數(shù)量與算法運(yùn)行時(shí)間對(duì)比

圖6 300×300目標(biāo)節(jié)點(diǎn)數(shù)量與算法運(yùn)行時(shí)間對(duì)比

圖7～圖10給出了傳感器節(jié)點(diǎn)在初始時(shí)刻與CHCAEDS優(yōu)化后的布置示意圖。從圖中可以看出，λ=0.3和λ=0.8時(shí)，初始時(shí)刻監(jiān)測(cè)區(qū)域內(nèi)存在大量的冗余節(jié)點(diǎn)，通過CHCAEDS優(yōu)化后，抑制了冗余節(jié)點(diǎn)的產(chǎn)生，使其轉(zhuǎn)入休眠狀態(tài)，保存了整個(gè)網(wǎng)絡(luò)的能量，延長(zhǎng)了網(wǎng)絡(luò)生存周期。

圖7 λ=0.3時(shí)，初始時(shí)刻傳感節(jié)點(diǎn)部署示意圖

圖8 λ=0.3時(shí)，CHCAEDS傳感節(jié)點(diǎn)部署示意圖

圖9 λ=0.8時(shí)，初始時(shí)刻傳感節(jié)點(diǎn)部署示意圖

圖10 λ=0.8時(shí)，CHCAEDS傳感節(jié)點(diǎn)部署示意圖

3 結(jié)束語

本文在對(duì)無線傳感器網(wǎng)絡(luò)覆蓋問題進(jìn)行分析的基礎(chǔ)上提出了一種覆蓋空洞補(bǔ)償算法。首先，利用概率相關(guān)知識(shí)給出了部署在監(jiān)測(cè)區(qū)域內(nèi)的傳感器節(jié)點(diǎn)分布形態(tài)；而后對(duì)傳感器節(jié)點(diǎn)覆蓋期望值和最少節(jié)點(diǎn)數(shù)量的函數(shù)關(guān)系進(jìn)行求解，給出了覆蓋監(jiān)測(cè)區(qū)域內(nèi)所需最少傳感器節(jié)點(diǎn)數(shù)量的求解方法；最后，通過仿真實(shí)驗(yàn)驗(yàn)證了CHCAEDS與ETCA、ECAPM在不同監(jiān)測(cè)區(qū)域內(nèi)的網(wǎng)絡(luò)生存周期和運(yùn)行時(shí)間的對(duì)比過程，證明了本文算法的有效性和穩(wěn)定性。

今后的工作重點(diǎn)將主要集中在具有邊界效應(yīng)的非線性覆蓋和參數(shù)可調(diào)的有效覆蓋。

［1］ 孫澤宇，伍衛(wèi)國(guó)，王換招.無線傳感器網(wǎng)絡(luò)中一種增強(qiáng)型覆蓋控制算法［J］.電子學(xué)報(bào)，2015，43（3）：466-474.

［2］ 邢蕭飛，謝東青，鄭瑾.無線傳感器網(wǎng)絡(luò)k度覆蓋控制算法［J］.中南大學(xué)學(xué)報(bào)：自然科學(xué)版，2014，45（11）：3832-3839.

［3］ 李猛，丁代榮，郭廷立.一種無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)隨機(jī)部署策略［J］.計(jì)算機(jī)工程，2012，38（5）：99-101.

［4］ 孫澤宇，趙國(guó)增.基于節(jié)點(diǎn)調(diào)度策略的能量有效覆蓋算法［J］.光通信研究，2012，（6）：52-55.

［5］ 孟凡治，王換招，何暉.基于聯(lián)合感知模型的無線傳感器網(wǎng)絡(luò)連通性覆蓋協(xié)議［J］.電子學(xué)報(bào)，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］ 趙春江，吳華瑞，劉強(qiáng).基于Voronoi的無線傳感器網(wǎng)絡(luò)控制優(yōu)化策略［J］.通信學(xué)報(bào)，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

國(guó)家自然科學(xué)基金資助項(xiàng)目（U1304603，61503174）；國(guó)家博士后基金資助項(xiàng)目（2014M562153）；河南省科技攻關(guān)重點(diǎn)資助項(xiàng)目（142102210471，1421002210568，162102210113）；河南省教育廳自然科學(xué)重點(diǎn)基金資助項(xiàng)目（14B520099，16A520063）；廣州市自然科學(xué)基金資助項(xiàng)目（1201430560）

孫澤宇（1977-），男，吉林長(zhǎng)春人。副教授，博士，主要研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)與物聯(lián)網(wǎng)。