無(wú)線視頻傳感網(wǎng)絡(luò)k-柵欄實(shí)時(shí)覆蓋算法*

樊　婷，白光偉，沈　航，馬　丁

（南京工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系，南京211816）

無(wú)線視頻傳感網(wǎng)絡(luò)k-柵欄實(shí)時(shí)覆蓋算法*

樊婷，白光偉*，沈航，馬丁

（南京工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系，南京211816）

在多目標(biāo)入侵的場(chǎng)景下，由于入侵時(shí)間的不確定性，傳統(tǒng)柵欄覆蓋方法中有些傳感節(jié)點(diǎn)并未覆蓋目標(biāo)卻一直保持工作狀態(tài)，造成額外能量損耗的同時(shí)降低了覆蓋效果。針對(duì)該問(wèn)題，提出了實(shí)時(shí)旋轉(zhuǎn)傳感節(jié)點(diǎn)實(shí)現(xiàn)k柵欄覆蓋的算法（VSRA:Visual Sensors Rotating Algorithm），將整個(gè)監(jiān)測(cè)區(qū)域劃分為不同分區(qū)，在有入侵的分區(qū)，實(shí)時(shí)將傳感節(jié)點(diǎn)向權(quán)值較大的感知方向旋轉(zhuǎn)從而在滿足一定k柵欄覆蓋要求的同時(shí)達(dá)到提高節(jié)點(diǎn)利用率的目的。仿真結(jié)果表明，VSRA能提高覆蓋性能，延長(zhǎng)網(wǎng)絡(luò)生存周期。

無(wú)線視頻傳感網(wǎng)；k柵欄覆蓋；區(qū)域監(jiān)測(cè)；權(quán)值比較；實(shí)時(shí)旋轉(zhuǎn)

EEACC:7230doi:10.3969/j.issn.1004-1699.2015.09.022

無(wú)線視頻傳感網(wǎng)（WVSNs）中k柵欄覆蓋是指在狹長(zhǎng)的帶狀區(qū)域內(nèi)部署一系列傳感節(jié)點(diǎn)使得試圖穿越的入侵者都能被k個(gè)不同的傳感節(jié)點(diǎn)覆蓋到，其中k值的選取是根據(jù)區(qū)域不同等級(jí)的警戒度人為設(shè)定的，它不僅是無(wú)線傳感網(wǎng)絡(luò)中的重要應(yīng)用也是軍事和國(guó)防安全應(yīng)用中的關(guān)鍵技術(shù)，可以用來(lái)監(jiān)測(cè)試圖要穿越區(qū)域且未經(jīng)授權(quán)的入侵者［4］。

無(wú)線視頻傳感器比起標(biāo)量傳感器有了視頻捕捉的能力并加強(qiáng)了對(duì)入侵目標(biāo)的監(jiān)測(cè)力度。近年來(lái)研究人員針對(duì)如何在固定區(qū)域內(nèi)構(gòu)建柵欄覆蓋提出了多種方案。王超提出了用最少的節(jié)點(diǎn)構(gòu)建分區(qū)強(qiáng)k-柵欄覆蓋的PMNSB［5］算法。Chang C Y提出了將監(jiān)測(cè)區(qū)域劃分為均勻網(wǎng)格后構(gòu)建k-柵欄覆蓋的算法。通過(guò)網(wǎng)格的覆蓋程度來(lái)選擇最優(yōu)的傳感器覆蓋集合并保留候選集合，提高了覆蓋可靠性［6］。但該算法沒(méi)有考慮節(jié)點(diǎn)能耗的問(wèn)題。Cheng C F提出了一種關(guān)于k-柵欄覆蓋的分布式算法［7］，傳感器間通過(guò)廣播尋找剩余能量最大的節(jié)點(diǎn)作為初始節(jié)點(diǎn)，并由其縱向?qū)ふ夷苄纬蒶柵欄覆蓋的k-1個(gè)起始節(jié)點(diǎn)，從第k個(gè)初始節(jié)點(diǎn)開(kāi)始依次向左右拓展喚醒節(jié)點(diǎn)，多次回溯迭代后形成柵欄。這種由回溯法形成的柵欄耗時(shí)長(zhǎng)，計(jì)算量大又太過(guò)依賴于初始節(jié)點(diǎn)，會(huì)影響捕捉目標(biāo)的成功率。

通常監(jiān)測(cè)區(qū)域內(nèi)布置的傳感節(jié)點(diǎn)是由電池供應(yīng)能量，生命時(shí)間有限，在滿足覆蓋要求的情況下盡可能減少傳感節(jié)點(diǎn)能耗的問(wèn)題有很大的研究意義。借鑒上述文獻(xiàn)中由網(wǎng)格劃分構(gòu)建1柵欄的策略［6］，本文主要研究如何在k-柵欄覆蓋的基礎(chǔ)上實(shí)時(shí)旋轉(zhuǎn)相關(guān)節(jié)點(diǎn)方向達(dá)到提高節(jié)點(diǎn)利用率以延長(zhǎng)整個(gè)網(wǎng)絡(luò)生命周期的目的。主要工作包括:①用（BA:Basic Approach For Construct Barrier Coverage）算法［6］構(gòu)建1-柵欄覆蓋后將監(jiān)測(cè)區(qū)域分塊并在入侵邊界布置標(biāo)量傳感節(jié)點(diǎn)，根據(jù)目標(biāo)入侵位置更新網(wǎng)格優(yōu)先級(jí)。②依據(jù)網(wǎng)格優(yōu)先級(jí)將候選節(jié)點(diǎn)覆蓋網(wǎng)格的情況比例化，由VSRA得出節(jié)點(diǎn)各個(gè)感知方向的權(quán)值，實(shí)時(shí)調(diào)動(dòng)相應(yīng)分區(qū)內(nèi)的候選節(jié)點(diǎn)旋轉(zhuǎn)達(dá)到對(duì)入侵目標(biāo)的k覆蓋要求的同時(shí)減少節(jié)點(diǎn)能耗。

本文余下章節(jié)安排如下:第1節(jié)描述網(wǎng)絡(luò)模型和問(wèn)題描述；第2節(jié)以構(gòu)建2柵欄覆蓋為例，詳細(xì)描述了VSRA的實(shí)現(xiàn)過(guò)程；第3節(jié)通過(guò)仿真實(shí)驗(yàn)對(duì)VSRA進(jìn)行性能分析；最后第4節(jié)總結(jié)全文。

1　問(wèn)題的提出

1.1模型和假設(shè)

本文考慮包含一定數(shù)量的視頻傳感器節(jié)點(diǎn)和標(biāo)量傳感器節(jié)點(diǎn)以及若干入侵目標(biāo)的WVSNs的網(wǎng)絡(luò)環(huán)境。監(jiān)測(cè)區(qū)域B的面積為L(zhǎng)×H，其中Lp、Ld、Lf、Lg，分別表示區(qū)域B的上下左右邊界。

入侵目標(biāo)在WVSNs中的有效穿越路徑是指目標(biāo)從區(qū)域的下方邊界Ld連續(xù)移動(dòng)到上方邊界Lp的移動(dòng)軌道。區(qū)域被k-柵欄覆蓋是指試圖以任意有效路徑穿越區(qū)域B的目標(biāo)都能被k個(gè)視頻節(jié)點(diǎn)同時(shí)監(jiān)測(cè)到［6］，其中BCk表示柵欄防御度為k。

假設(shè)視頻傳感節(jié)點(diǎn)是隨機(jī)拋灑的，每個(gè)視頻傳感器節(jié)點(diǎn)都有①唯一的ID標(biāo)識(shí)并且能通過(guò)GPS單元或者其他定位機(jī)制獲取自身的位置信息；②可以與鄰節(jié)點(diǎn)交換信息獲得通信范圍內(nèi)傳感節(jié)點(diǎn)ID和其覆蓋目標(biāo)的信息；③相同的初始能量，并且消耗后不能補(bǔ)充；④相同的感知距離和通信距離；⑤相同的感知角度和旋轉(zhuǎn)模式（與文獻(xiàn)［8］類似，如圖1（a）和圖1（b）所示）。

本文中使用到的符號(hào)如表1所示。

圖1　視頻傳感節(jié)點(diǎn)模型

表1　本文中使用的符號(hào)

1.2問(wèn)題的提出

k-柵欄覆蓋是指任意穿越檢測(cè)區(qū)域的目標(biāo)am能夠被k個(gè)不同的傳感器同時(shí)覆蓋到［9］。如圖2所示若要將連續(xù)的網(wǎng)格2覆蓋則需要part1與part2內(nèi)的傳感器同時(shí)喚醒形成覆蓋路徑。一方面在無(wú)目標(biāo)入侵的part2區(qū)域也需要保持2-柵欄覆蓋的傳感器喚醒，會(huì)造成此區(qū)域傳感器節(jié)點(diǎn)能量的損耗，等下一次入侵目標(biāo)從part2區(qū)域穿越時(shí)，能量已被消耗無(wú)法實(shí)現(xiàn)本次柵欄覆蓋的要求。另一方面節(jié)點(diǎn)拋灑后的位置和感知方向是隨機(jī)的，隨著k值的提高，柵欄覆蓋的成功率也得不到相應(yīng)的保證。

圖2　監(jiān)測(cè)區(qū)域的2-柵欄覆蓋

針對(duì)以上現(xiàn)象，可以將監(jiān)測(cè)區(qū)域劃分為不同的區(qū)域，在有入侵的分區(qū)實(shí)現(xiàn)k-柵欄覆蓋，而未入侵的分區(qū)保持1-柵欄覆蓋的節(jié)點(diǎn)工作，這樣不僅可以減少傳感節(jié)點(diǎn)的能耗還能提高k-柵欄覆蓋的成功率。

為了便于描述，給出如下定義:

定義1網(wǎng)絡(luò)生存周期，即系統(tǒng)監(jiān)測(cè)時(shí)長(zhǎng)當(dāng)?shù)趜次入侵時(shí)存在任意入侵目標(biāo)am∈A無(wú)法達(dá)到k覆蓋要求時(shí)，意味著當(dāng)前k-柵欄覆蓋生命結(jié)束。

定義2k覆蓋路徑［8］已知入侵目標(biāo)集合A和節(jié)點(diǎn)感知方向集合D，路徑節(jié)點(diǎn)集合C是D的子集，使得A中任意目標(biāo)都被C中元素覆蓋且符合相應(yīng)k覆蓋要求。該集合C則可為A的一組k覆蓋路徑。

定義3網(wǎng)格全覆蓋已知網(wǎng)格集合G和節(jié)點(diǎn)感知方向集合D，若節(jié)點(diǎn)感知方向集合中存在D的子集將網(wǎng)格各個(gè)頂點(diǎn)都包含在內(nèi)，則此網(wǎng)格被全覆蓋了。

1.3k覆蓋問(wèn)題及旋轉(zhuǎn)示例描述

由上所述可知，對(duì)監(jiān)測(cè)區(qū)域的k柵欄覆蓋可簡(jiǎn)化為傳感集合Df（si，j）對(duì)區(qū)域從左至右邊界相鄰網(wǎng)格的連續(xù)k覆蓋。

將目標(biāo)與網(wǎng)格被k覆蓋的問(wèn)題表示如下:

A=｛am|m=1…M｝，S=｛si|i=1…N｝

K=｛km|m=1…M｝

每個(gè)網(wǎng)格的頂點(diǎn)坐標(biāo)為:

若視頻傳感節(jié)點(diǎn)方向di，j覆蓋到網(wǎng)格gm，n則可表示為:

若網(wǎng)格gmn被k覆蓋，有

如圖2所示，當(dāng)區(qū)域內(nèi)的一輪入侵中只有目標(biāo)a1時(shí)為了構(gòu)建2柵欄覆蓋，需要s1～s12共12個(gè)頻傳感節(jié)點(diǎn)一起工作。而在節(jié)點(diǎn)感知方向［10］可旋轉(zhuǎn)的情況下，如圖3所示，達(dá)到上述要求只需要旋轉(zhuǎn)s3（圖中加粗部分為s3旋轉(zhuǎn)后的方向）并讓｛s1，s4，s6，s8，s10｝共6節(jié)點(diǎn)工作即可，這樣可以節(jié)省傳感節(jié)點(diǎn)的使用數(shù)量，從而延長(zhǎng)網(wǎng)絡(luò)的生存周期。

圖3　旋轉(zhuǎn)后實(shí)現(xiàn)對(duì)目標(biāo)的2覆蓋

2　算法描述

BA算法可以從邊界左邊到右邊形成一條1柵欄覆蓋的工作傳感節(jié)點(diǎn)方向集合Df（si，j）與候選工作傳感節(jié)點(diǎn)方向集合Df*（si，j）。在此基礎(chǔ)上，我們?cè)O(shè)計(jì)VSRA以實(shí)現(xiàn)對(duì)監(jiān)測(cè)區(qū)域的k柵欄覆蓋具體算法如下。

2.1目標(biāo)入侵時(shí)網(wǎng)格優(yōu)先級(jí)的確定

首先在目標(biāo)入侵的區(qū)域邊界布置一系列標(biāo)量傳感器，這些傳感器總能感知到入侵的目標(biāo)并能及時(shí)發(fā)送其所在的網(wǎng)格位置信息給所屬分區(qū)內(nèi)的視頻傳感節(jié)點(diǎn)。再以每個(gè)分區(qū)目標(biāo)am入侵所在的網(wǎng)格位置為對(duì)稱中心，分別向左右拓展得到網(wǎng)格集合:

然后，覆蓋到這些網(wǎng)格集合的傳感節(jié)點(diǎn)將這些網(wǎng)格的優(yōu)先級(jí)PRm，n均加上1并標(biāo)記為Ginvadef。在前面形成1柵欄覆蓋的算法中，被工作視頻傳感節(jié)點(diǎn)集合連續(xù)覆蓋的網(wǎng)格集合G（si，j）的優(yōu)先級(jí)均為1且表示為BG1（si，j∈Df（si，j）），那么BG1與剛剛優(yōu)先級(jí)加1的拓展網(wǎng)格Ginvadef的交集形成了優(yōu)先級(jí)為2的矩形網(wǎng)格區(qū)域，其網(wǎng)格集合表示為:

BG2=Ginvadef?G（si，j），f=1，2...F，Si，j∈Df（Si，j）（6）

把BG2作為視頻傳感節(jié)點(diǎn)實(shí)時(shí)旋轉(zhuǎn)的最優(yōu)區(qū)域，BG1網(wǎng)格集合為視頻傳感節(jié)點(diǎn)旋轉(zhuǎn)的次優(yōu)區(qū)域，統(tǒng)稱為關(guān)鍵區(qū)域。在多目標(biāo)入侵的情況下，會(huì)有網(wǎng)格優(yōu)先級(jí)發(fā)生沖突，解決方法如下:若分塊內(nèi)出現(xiàn)關(guān)鍵區(qū)域BG1與BG2重合的情況，則高優(yōu)先級(jí)默認(rèn)覆蓋低優(yōu)先級(jí)即重疊區(qū)域優(yōu)先級(jí)為BG2，各個(gè)感知方向上的權(quán)值計(jì)算方法不變。

一次入侵后，待越區(qū)目標(biāo)被視頻傳感節(jié)點(diǎn)k覆蓋后，拓展網(wǎng)格Ginvadef的優(yōu)先級(jí)會(huì)被清零，等待下一次的入侵重新確定拓展網(wǎng)格。

2.2視頻節(jié)點(diǎn)感知方向選擇

由上節(jié)可知當(dāng)目標(biāo)入侵partf時(shí)布置在邊界的標(biāo)量傳感器

可感知目標(biāo)的信息，并且視頻傳感節(jié)點(diǎn)能通過(guò)相鄰節(jié)點(diǎn)知曉優(yōu)先級(jí)高的網(wǎng)格信息。

如圖1（b）所示隨機(jī)拋灑的視頻節(jié)點(diǎn)有4個(gè)感知方向且每個(gè)方向視域?yàn)?0°。候選工作傳感節(jié)點(diǎn)方向集合Df*（si，j）需要判斷如何旋轉(zhuǎn)方向以實(shí)現(xiàn)對(duì)關(guān)鍵區(qū)域的覆蓋最大化。

我們考慮兩種算法。第一種是基于網(wǎng)格覆蓋率下的貪心（GREEDY）算法，視頻傳感節(jié)點(diǎn)優(yōu)先選擇對(duì)關(guān)鍵區(qū)域網(wǎng)格面積覆蓋率大的感知方向。第二種是VSRA，節(jié)點(diǎn)根據(jù)其4個(gè)感知方向?qū)﹃P(guān)鍵區(qū)域整體覆蓋的情況設(shè)定不同的權(quán)值，通過(guò)比較權(quán)值大小來(lái)選擇最優(yōu)旋轉(zhuǎn)方向最終得到覆蓋路徑集合。本節(jié)從傳感節(jié)點(diǎn)對(duì)關(guān)鍵區(qū)域的覆蓋成功率方面將GREEDY算法和VSRA作比較。

2.2.1GREEDY算法

該算法隨機(jī)確定k覆蓋要求，候選工作集合Df*（si，j）中的視頻傳感節(jié)點(diǎn)將其不同方向?qū)﹃P(guān)鍵區(qū)域的覆蓋面積比率量化為相應(yīng)數(shù)值，每輪通過(guò)比較各個(gè)感知方向量化數(shù)值的大小，確定傳感節(jié)點(diǎn)方向的優(yōu)先級(jí)。具體步驟如下:

視頻節(jié)點(diǎn)si的第j個(gè)方向di，j在partf對(duì)優(yōu)先級(jí)為e的區(qū)域的格覆蓋率為:

其中BGe，i，j表示傳感節(jié)點(diǎn)si第j個(gè)方向?qū)?yōu)先級(jí)為e網(wǎng)格的覆蓋面積，BGe表示優(yōu)先級(jí)為e網(wǎng)格的面積。

依據(jù)dij對(duì)關(guān)鍵區(qū)域的覆蓋率，設(shè)定不同傳感方向上的比例值Oi，j，具體方式如下:

候選節(jié)點(diǎn)集合Df*（si，j）在目標(biāo)入侵partf后被喚醒，并向具有最大比例值Oij的方向旋轉(zhuǎn)。如果不同傳感節(jié)點(diǎn)的不同傳感方向都有最大的比例值，則比較它們各個(gè)方向比例總值，優(yōu)先選擇總值大的方向旋轉(zhuǎn)。每輪去掉已覆蓋網(wǎng)格區(qū)域后重新計(jì)算比例值，如此迭代選出旋轉(zhuǎn)工作集合Df（si，j）。迭代的終止條件是指partf區(qū)域中入侵目標(biāo)被k覆蓋了。

2.2.2VSRA

該算法在GREEDY的基礎(chǔ)上做出改進(jìn)，先得出候選工作集合Df*（si，j）不同方向的比例值Oij后，再根據(jù)不同傳感節(jié)點(diǎn)各個(gè)傳感方向總體的比例值，參考文獻(xiàn)［11］權(quán)值的計(jì)算方法得到每個(gè)傳感方向的權(quán)值。傳感節(jié)點(diǎn)方向選擇的計(jì)算方法如下:

感知方向調(diào)節(jié)算法（VSRA）

當(dāng)有目標(biāo)am入侵partf時(shí)，根據(jù)VSRA依次喚醒候選集合Df*（si，j）中傳感節(jié)點(diǎn)工作，得到partf中可實(shí)現(xiàn)k柵欄覆蓋的傳感節(jié)點(diǎn)集合Df（si，j）。

如圖4所示，矩形監(jiān)測(cè)域內(nèi)畫(huà)出的窄長(zhǎng)關(guān)鍵區(qū)域的中間部分網(wǎng)格代表最優(yōu)區(qū)域BG2，其左右兩端部分網(wǎng)格則代表次優(yōu)區(qū)域。傳感節(jié)點(diǎn)s1～s4按照如上算法實(shí)時(shí)旋轉(zhuǎn)傳感節(jié)點(diǎn)的方向，實(shí)現(xiàn)對(duì)入侵目標(biāo)的k覆蓋要求。圖表中只列出2個(gè)傳感方向，但目標(biāo)數(shù)和權(quán)值計(jì)算是結(jié)合4個(gè)傳感方向得來(lái)的，具體步驟見(jiàn)表2與表3。

圖4　傳感節(jié)點(diǎn)旋轉(zhuǎn)方向選擇的例子

表2　GREEDY選取旋轉(zhuǎn)工作集合步驟

表3　VSRA選取旋轉(zhuǎn)工作集合步驟

結(jié)合上述例子，通過(guò)對(duì)比GREEDY與VSRA可知若采用前者會(huì)出現(xiàn)關(guān)鍵區(qū)域漏覆蓋與傳感節(jié)點(diǎn)s4被閑置的情況，而采用本文提出的VSRA后，可以最大化關(guān)鍵區(qū)域覆蓋，滿足任意入侵目標(biāo)被k覆蓋要求的同時(shí)提高節(jié)點(diǎn)利用率。

3　仿真實(shí)驗(yàn)與結(jié)果分析

3.1實(shí)驗(yàn)環(huán)境和參數(shù)設(shè)置

本文在MATLAB平臺(tái)上實(shí)現(xiàn)了在多目標(biāo)入侵的場(chǎng)景下對(duì)監(jiān)測(cè)區(qū)域的k-柵欄覆蓋，并設(shè)計(jì)了一系列仿真實(shí)驗(yàn)。區(qū)域內(nèi)隨機(jī)拋灑300～600個(gè)視頻傳感節(jié)點(diǎn)，各個(gè)節(jié)點(diǎn)位置固定不變，初始能量相同并隨機(jī)部署多目標(biāo)沿有效路徑穿越監(jiān)測(cè)區(qū)域。

視頻節(jié)點(diǎn)所消耗的能量主要來(lái)自數(shù)據(jù)處理過(guò)程、感知過(guò)程和傳輸過(guò)程。根據(jù)文獻(xiàn)［12］，節(jié)點(diǎn)的能量消耗根據(jù)工作模式的不同而變化。我們假設(shè)當(dāng)路徑序列中的節(jié)點(diǎn)工作時(shí)，處理和感知過(guò)程為活動(dòng)模式，傳輸過(guò)程為空閑模式。假設(shè)每個(gè)視頻節(jié)點(diǎn)的初始能量為200 J，期望工作時(shí)間為3 120 s。仿真過(guò)程基本參數(shù)設(shè)置詳見(jiàn)表4。

為了提高實(shí)驗(yàn)結(jié)果的參考價(jià)值，每組實(shí)驗(yàn)結(jié)果都是進(jìn)行了多次隨機(jī)試驗(yàn)后求得的平均值。

表4　實(shí)驗(yàn)參數(shù)設(shè)置

3.2實(shí)驗(yàn)結(jié)果分析

本節(jié)主要從k-柵欄覆蓋成功率和節(jié)點(diǎn)剩余能量百分比這些方面考察算法的性能。通過(guò)改變目標(biāo)入侵次數(shù)、目標(biāo)入侵?jǐn)?shù)量以及區(qū)域分塊個(gè)數(shù)得到不同的網(wǎng)絡(luò)場(chǎng)景來(lái)考察BA與VSRA的性能。

VSRA、GREEDY算法與BA算法在目標(biāo)入侵速度不同的情況下實(shí)現(xiàn)k-柵欄覆蓋的成功率如圖5所示。實(shí)驗(yàn)取2-柵欄與3-柵欄覆蓋為例，由于節(jié)點(diǎn)入侵的速度是隨機(jī)不同的，在穿越距離固定的情況下，各個(gè)目標(biāo)入侵的完成時(shí)間與其穿越速度是成反比的，那么可以通過(guò)觀察橫軸的入侵完成時(shí)間來(lái)體現(xiàn)多目標(biāo)整體穿越的速度。BA在目標(biāo)入侵前開(kāi)啟了要實(shí)現(xiàn)k-柵欄覆蓋所需的傳感器集合并一直工作等待入侵。VSRA是根據(jù)目標(biāo)入侵的位置，計(jì)算出關(guān)鍵區(qū)域，并調(diào)動(dòng)入侵分區(qū)的候選傳感節(jié)點(diǎn)實(shí)時(shí)旋轉(zhuǎn)以達(dá)到覆蓋要求。實(shí)際情況下目標(biāo)的入侵完成時(shí)間總是大于3 s，從圖5可以看出在3柵欄覆蓋要求下，橫軸時(shí)間點(diǎn)在接近3 s時(shí)，VSRA的成功率超過(guò)傳統(tǒng)BA算法并穩(wěn)定增長(zhǎng)直至高于其18.91%左右。同理在2柵欄覆蓋要求下成功率可以比于原BA算法大于7.1%～16.88%左右。

圖5　入侵速度對(duì)柵欄覆蓋成功率的影響

由BC3與BC2的情況對(duì)比可知隨著柵欄覆蓋k值越高，VSRA與GREEDY需要配置的時(shí)間越長(zhǎng)，待花費(fèi)時(shí)間到達(dá)一定上限的時(shí)候VSRA的成功率會(huì)趨于平穩(wěn)。雖然GREEDY算法也是實(shí)時(shí)旋轉(zhuǎn)的，但是其會(huì)在節(jié)點(diǎn)方向選擇的時(shí)候出現(xiàn)漏覆蓋的情況，所以成功率相對(duì)VSRA較低，并且隨著k覆蓋要求的提高，漏覆蓋情況會(huì)更加嚴(yán)重。

圖6顯示出VSRA和BA算法在固定的時(shí)間段內(nèi)，多目標(biāo)同時(shí)對(duì)監(jiān)測(cè)區(qū)域入侵時(shí)，觀察改變目標(biāo)數(shù)量對(duì)節(jié)點(diǎn)剩余能量的影響，以此反應(yīng)節(jié)點(diǎn)能耗情況。如圖6所示相比較BA而言VSRA受目標(biāo)數(shù)目影響較大。在區(qū)域分塊數(shù)目固定的情況下，當(dāng)入侵目標(biāo)較少時(shí)，只有較少的分區(qū)需要喚醒候選節(jié)點(diǎn)，其余分區(qū)均保持形成1柵欄的節(jié)點(diǎn)工作而B(niǎo)A算法每個(gè)分區(qū)一直都要保持形成2柵欄的節(jié)點(diǎn)工作，因此其節(jié)點(diǎn)的平均剩余能量在開(kāi)始時(shí)要低于VSRA 9.7%左右，但隨著入侵目標(biāo)的不斷增加，涉及的分區(qū)不斷增加，分區(qū)內(nèi)的候選節(jié)點(diǎn)相繼工作，節(jié)點(diǎn)的平均能耗也逐漸增加。當(dāng)多目標(biāo)遍及整個(gè)區(qū)域時(shí)，節(jié)點(diǎn)的平均剩余能量逐漸接近于BA算法。

圖6　入侵目標(biāo)數(shù)對(duì)節(jié)點(diǎn)剩余能量的影響

圖7是表示在區(qū)域分塊可變的情況下，一次入侵3～10個(gè)目標(biāo)考察形成2柵欄覆蓋后節(jié)點(diǎn)剩余能量百分?jǐn)?shù)的變化。由實(shí)驗(yàn)可知節(jié)點(diǎn)的剩余能量在BA算法下基本不受區(qū)域分塊的影響而在VSRA下是隨著區(qū)域的分塊數(shù)量而變化的。一方面監(jiān)測(cè)區(qū)域的分塊數(shù)目越多，節(jié)點(diǎn)的處理能耗越高，另一方面固定區(qū)域的分塊數(shù)目越少，目標(biāo)穿越時(shí)喚醒的傳感節(jié)點(diǎn)越多，節(jié)點(diǎn)的傳感能耗越高，節(jié)點(diǎn)剩余能量越少。分塊數(shù)為8時(shí)可以看出節(jié)點(diǎn)的能耗較低，此時(shí)節(jié)點(diǎn)剩余能量的達(dá)到一定的峰值點(diǎn)，比傳統(tǒng)BA算法的節(jié)點(diǎn)剩余能量高出7%左右。

圖7　區(qū)域分塊數(shù)對(duì)節(jié)點(diǎn)能耗的影響

從表5可以看出在一次入侵1～3個(gè)目標(biāo)且入侵次數(shù)變化的情況下，BA與VSRA節(jié)點(diǎn)平均能耗和能耗方差的對(duì)比。VSRA在1柵欄覆蓋的基礎(chǔ)上待一次入侵后，實(shí)時(shí)關(guān)閉旋轉(zhuǎn)的候選節(jié)點(diǎn)等待下一次入侵，節(jié)省了節(jié)點(diǎn)的能耗，延長(zhǎng)了網(wǎng)絡(luò)的生命時(shí)間。但從表5可以看出隨著多目標(biāo)入侵次數(shù)的增加，兩種算法的方差都在不斷變大，這是由于一直開(kāi)啟的節(jié)點(diǎn)能量在持續(xù)損耗，特別是VSRA中實(shí)時(shí)旋轉(zhuǎn)的節(jié)點(diǎn)與保持1-柵欄一直工作的節(jié)點(diǎn)會(huì)出現(xiàn)能耗不均衡現(xiàn)象。

表5　入侵次數(shù)改變時(shí)節(jié)點(diǎn)平均剩余能量和剩余能量方差比較

4　總結(jié)

本文提出了WVSNs中k-柵欄實(shí)時(shí)覆蓋算法VSRA。通過(guò)將整個(gè)監(jiān)測(cè)區(qū)域合理分塊后，在1-柵欄覆蓋的基礎(chǔ)上，提出根據(jù)目標(biāo)入侵的位置，用VSRA得到候選節(jié)點(diǎn)各個(gè)感知方向的權(quán)值，實(shí)時(shí)觸發(fā)其向目標(biāo)最有可能出現(xiàn)的網(wǎng)格區(qū)域旋轉(zhuǎn)，提高了節(jié)點(diǎn)利用率。最后通過(guò)一系列仿真實(shí)驗(yàn)，對(duì)其性能進(jìn)行分析和評(píng)價(jià)，仿真結(jié)果表明:VSRA能提高覆蓋性能，節(jié)省傳感節(jié)點(diǎn)的能耗，延長(zhǎng)了網(wǎng)絡(luò)生存周期。

［1］ Halawani S，Khan A W.Sensors Lifetime Enhancement Techniques in Wireless Sensor Networks-A Survey［J］.Journal of Computing，2010，2（5）:34-47.

［2］ Lee I，Shaw W，Park J H.On Prolonging the Lifetime for Wireless Video Sensor Networks［J］.Mobile Networks and Applications，2010，15（4）:575-588.

［3］ 孫超，趙路路，張影，等.無(wú)線傳感器網(wǎng)絡(luò)分簇拓?fù)涞母采w區(qū)域節(jié)點(diǎn)調(diào)度優(yōu)化算法研究［J］.傳感技術(shù)學(xué)報(bào)，2010，23（1）:116-121.

［4］ Ssu K F，Wang W T，Wu F K，et al.K-Barrier Coverage with a Directional Sensing Model［J］.International Journal on Smart Sensing and Intelligent Systems，2009，2（1）:75-93.

［5］ 王超，范興剛，王恒，等.一種高效強(qiáng)K-柵欄覆蓋構(gòu)建算法［J］.傳感技術(shù)學(xué)報(bào)，2015（2）:227-233.

［6］ Chang C Y，Hsiao C Y.The K-Barrier Coverage Mechanism in Wireless Visual Sensor Networks［C］//Proceedings of IEEE Wireless Communications and Networking Conference（WCNC）.Pairs: WCNC，2012:2318-2322.

［7］ Cheng C F，Tsai K T.Distributed Barrier Coverage in Wireless Visual Sensor Networks with β-QoM［J］.IEEE Sensors Journal，2012，12（6）:1726-1735.

［8］ Cai Y，Lou W，Li M，et al.Energy Efficient Target-Oriented Scheduling in Directional Sensor Networks［J］.IEEE Transactions on Computers，2009，58（9）:1259-1274.

［9］ Saipulla A，Liu B，Xing G，et al.Barrier Coverage with Sensors of Limited Mobility［C］//Proceedings of the Eleventh ACM International Symposium on Mobile ad hoc Networking and Computing. Chicago:MobiHoc，2010:201-210.

［10］Costa D G，Guedes L A.The Coverage Problem in Video-Based Wireless Sensor Networks:A Survey［J］.Sensors，2010，10（9）: 8215-8247.

［11］Munishwar V P，Abu-Ghazaleh N B.Coverage Algorithms for Visual Sensor Networks［J］.ACM Transactions on Sensor Networks （TOSN），2013，9（4）:293-314.

［12］Wang B.Coverage Problems in Sensor Networks:A Survey［J］. ACM Computing，2011，43（4）:87-88.

樊婷（1991-），女，碩士研究生，主要研究方向?yàn)闊o(wú)線多媒體傳感器網(wǎng)絡(luò)，傳感網(wǎng)絡(luò)柵欄覆蓋技術(shù)，648364417@qq.com；

白光偉（1961-），男，博士，教授，博士生導(dǎo)師，CCF高級(jí)會(huì)員（E200012029S），主要研究方向?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)，移動(dòng)互聯(lián)網(wǎng)，網(wǎng)絡(luò)體系結(jié)構(gòu)和協(xié)議，網(wǎng)絡(luò)系統(tǒng)性能分析和評(píng)價(jià)，多媒體網(wǎng)絡(luò)服務(wù)質(zhì)量等，bai@njtech.edu.cn。

The Real Time Algorithm on K-Barrier Coverage in Wireless Visual Sensor Networks*

FAN Ting，BAI Guangwei*，SHEN Hang，MA Ding
（Department of Computer Science and Technology，Nanjing Tech University，Nanjing 211816，China）

In the case of uncertain intruding time in a multi-target invasion scenario，some sensors maintain actuated state though cannot cover the targets，which leads to the reduction of coverage impact and consuming sensors extra energy.To address this problem，this paper proposes a Visual Sensors Rotating Algorithm（VSRA）to improve the utilization of sensors，which can also satisfy real-time k-barrier coverage requirement.It divides the surveillance area into several regions and Sensors rotate to directions with higher weight in invaded regions.Our simulation results show that the proposed VSRA can improve the energy efficiency of sensors and prolong the network lifetime.

wireless visual sensor networks；k-barrier coverage；area monitoring；weight comparison；real-time rotation scheme

TP393

A

1004-1699（2015）09-1395-07

項(xiàng)目來(lái)源:國(guó)家自然科學(xué)基金項(xiàng)目（60673185，61073197）；江蘇省自然科學(xué)基金項(xiàng)目（BK2010548）；江蘇省科技支撐計(jì)劃（工業(yè)）項(xiàng)目（BE2011186）；江蘇省未來(lái)網(wǎng)絡(luò)前瞻性研究項(xiàng)目（BY2013095-4-09）；南京郵電大學(xué)寬帶無(wú)線通信與傳感網(wǎng)技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室開(kāi)放研究基金課題項(xiàng)目（NYKL201304）；江蘇省六大高峰人才基金（第八批）課題項(xiàng)目

2015-04-10修改日期:2015-06-18