移動傳感器k柵欄覆蓋研究*

劉 帥， 李克清， 戴 歡， 張 騫

(1.蘇州大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 蘇州 215006;2.常熟理工學(xué)院 計(jì)算機(jī)科學(xué)與工程學(xué)院，江蘇 常熟 215500)

0 引 言

無線傳感器網(wǎng)絡(luò)在軍事和環(huán)境領(lǐng)域具有廣泛應(yīng)用[1,2]，如,將傳感器節(jié)點(diǎn)部署在國際邊境線用以檢測非法入侵;將傳感器節(jié)點(diǎn)部署在化學(xué)工廠的周圍用以檢測致命化學(xué)藥物的擴(kuò)散等。在上述應(yīng)用中，傳感器節(jié)點(diǎn)都是部署在狹長的帶狀區(qū)域中，此時柵欄覆蓋使用的傳感器節(jié)點(diǎn)更少，更加符合實(shí)際應(yīng)用。

柵欄覆蓋是近年來無線傳感器網(wǎng)絡(luò)研究的重要問題之一。Kumar S等人[3]研究了在靜態(tài)傳感器網(wǎng)絡(luò)中，判斷監(jiān)控區(qū)域是否是柵欄覆蓋的方法。Ai Chen A等人[4]研究了將帶狀區(qū)域分成若干長的片段，每個片段內(nèi)實(shí)現(xiàn)柵欄覆蓋的本地化柵欄覆蓋算法。Bhattacharya B等人[5]提出了在邊界上形成1柵欄覆蓋的近似算法，即節(jié)點(diǎn)從初始時部署在監(jiān)控區(qū)域內(nèi)部最優(yōu)的移動到監(jiān)控區(qū)域的邊界形成柵欄覆蓋。Shen C等人[6]設(shè)計(jì)實(shí)現(xiàn)了1柵欄覆蓋集中式再部署算法CBarrier，為所有節(jié)點(diǎn)再部署計(jì)算最優(yōu)位置，但是CBarrier算法所有節(jié)點(diǎn)參與移動，消耗大量能量。班冬松等人[7]研究了基于監(jiān)控區(qū)域的網(wǎng)格劃分模型，實(shí)現(xiàn)1柵欄覆蓋的GBGB(grid baseline grid barrier)算法和實(shí)現(xiàn)k柵欄覆蓋的GBIGB(grid baseline and isolation grid barrier)算法，但是這2種算法要對監(jiān)控區(qū)域進(jìn)行網(wǎng)格劃分，計(jì)算復(fù)雜度高。

本文針對狹長帶狀監(jiān)控區(qū)域內(nèi)隨機(jī)部署的無線傳感器網(wǎng)絡(luò)，利用移動節(jié)點(diǎn)，提出基于CBarrier的改進(jìn)算法MCBarrier，能夠能量高效的構(gòu)建1柵欄覆蓋。本文考慮了分治算法，設(shè)計(jì)了移動節(jié)點(diǎn)再部署算法kMCBarrier，能量高效的實(shí)現(xiàn)k柵欄覆蓋。

1 網(wǎng)絡(luò)模型與問題描述

1.1 網(wǎng)絡(luò)模型

定義1:穿越路徑:在監(jiān)控區(qū)域A中，移動目標(biāo)從頂部或底部向?qū)?yīng)一端穿越得到的任意軌跡，這條軌跡就是穿越路徑。

定義2:k柵欄覆蓋:當(dāng)移動目標(biāo)的穿越路徑經(jīng)過至少k個傳感器節(jié)點(diǎn)的感應(yīng)區(qū)域時，則認(rèn)為監(jiān)控區(qū)域是k柵欄覆蓋。

1.2 柵欄覆蓋中節(jié)點(diǎn)重部署最小移動距離之和

通過引入移動節(jié)點(diǎn)，對整個傳感器網(wǎng)絡(luò)進(jìn)行重部署，就可以使整個監(jiān)控區(qū)域能夠形成1或k柵欄覆蓋。但是傳感器節(jié)點(diǎn)移動會消耗大量能量，且傳感器節(jié)點(diǎn)的總體能量有限，因此,節(jié)點(diǎn)進(jìn)行重部署時在保證柵欄覆蓋的情況下要盡量減少節(jié)點(diǎn)的移動距離，降低節(jié)點(diǎn)移動時的能量消耗，最終延長網(wǎng)絡(luò)的生存周期。本文將節(jié)點(diǎn)重新部署使能量消耗最少，找到柵欄的最佳位置問題稱為柵欄覆蓋中節(jié)點(diǎn)重部署最小移動距離之和(BCRMS)問題。

下面對BCRMS問題進(jìn)行形式化的數(shù)學(xué)描述。

為了簡便描述，將左右邊界分別假設(shè)為虛擬節(jié)點(diǎn)S0和Sn+1，所以，x0=0,xN+1=L。節(jié)點(diǎn)Si與Sj之間的歐氏距離如下

所以，BCRMS的目標(biāo)是

(1)

約束條件為

(2)

(3)

?i(0

(4)

(5)

目標(biāo)函數(shù)式(1)是使傳感器移動距離之和最小化。約束條件式(2)與約束條件式(3)是使每一個節(jié)點(diǎn)在X軸方向上有一個感知范圍之內(nèi)的左鄰居和右鄰居。矩形區(qū)域的左右邊界的覆蓋通過式(4)，式(5)2個不等式來保證。通過這些約束條件，最終重新部署的傳感器節(jié)點(diǎn)可以在監(jiān)控區(qū)域內(nèi)形成一個柵欄。

2 柵欄覆蓋構(gòu)筑算法

2.1 CBarrier算法

在文獻(xiàn)[6]中，集中式算法CBarrier通過傳感器節(jié)點(diǎn)重部署到相應(yīng)的位置來形成一條直線柵欄。在CBarrier設(shè)計(jì)，做出了如下假設(shè)：

3)左右邊界被覆蓋，則假設(shè)

CBarrier的核心是為節(jié)點(diǎn)計(jì)算節(jié)點(diǎn)重部署后的位置。BCRMS的目標(biāo)是使移動距離最小化，設(shè)

所以,對F(a，b)的最小化等同于函數(shù)式(1)的目標(biāo)，由極值原理得到

(6)

由式(6)展開

(7)

解方程組式(7)，得解如下

(8)

2.2 改進(jìn)的CBarrier算法

根據(jù)CBarrier算法，可以得到形成的直線柵欄是要求所有節(jié)點(diǎn)都參與構(gòu)筑柵欄，如圖1所示。從圖1可以得出，當(dāng)節(jié)點(diǎn)數(shù)量很多的時候，節(jié)點(diǎn)的感知區(qū)域會互相重疊。因此，可以選取監(jiān)控區(qū)域內(nèi)若干節(jié)點(diǎn)部署在基準(zhǔn)直線柵欄位置上，如圖2所示，監(jiān)控區(qū)域保證形成的柵欄情況下所需的節(jié)點(diǎn)數(shù)最少。

圖1 CBarrier柵欄覆蓋

圖2 改進(jìn)CBarrier柵欄覆蓋

此時需要節(jié)點(diǎn)任意Si和Sj滿足如下式子

即任意2個節(jié)點(diǎn)之間距離為2Rs。

節(jié)點(diǎn)最優(yōu)移動就是二部圖賦權(quán)匹配問題[8]，即X中各個節(jié)點(diǎn)初始位置移動對應(yīng)Y中各個節(jié)點(diǎn)的初始位置，使得移動距離之和最小。利用匈牙利算法[9]對二部圖賦權(quán)匹配問題求解，即移動節(jié)點(diǎn)移動進(jìn)行最優(yōu)的重部署，最終整體移動距離最短。

2.3 k柵欄覆蓋構(gòu)建算法

在大規(guī)模的傳感器網(wǎng)絡(luò)中，節(jié)點(diǎn)數(shù)目眾多，判斷整個區(qū)域是否形成k柵欄覆蓋需要獲取網(wǎng)絡(luò)的全局信息，因此，會造成大量的通信和計(jì)算開銷。

本文通過考慮分治算法來避免節(jié)點(diǎn)獲知整個網(wǎng)絡(luò)的全局信息，從而降低能量消耗，主要方法如下：

1)監(jiān)控區(qū)域A劃分成kv個相同大小的子區(qū)域，子區(qū)域的長和寬分別為ls=L/v，ws=w/k。

2)每個子區(qū)域分別獨(dú)立地執(zhí)行KMCBarrier算法。

3)當(dāng)所有的子區(qū)域都執(zhí)行完成算法以后，整個重部署的網(wǎng)絡(luò)就形成了k柵欄覆蓋。

kMCBarrier算法在水平方向上按照CBarrier算法選取直線柵欄，垂直方向選取子區(qū)域最右側(cè)的與右邊界相交的節(jié)點(diǎn)所在的垂直線為柵欄，消除2個子區(qū)域的鄰接處可能存在間隙。如圖3，kMCBarrier相對于CBarrier,增加了區(qū)域右側(cè)的一列垂直柵欄。圖3是各個子區(qū)域執(zhí)行完算法后，在監(jiān)控區(qū)域內(nèi)形成3柵欄覆蓋。

圖3 3柵欄覆蓋

3 仿真實(shí)驗(yàn)分析

文中使用Matlab對1柵欄覆蓋算法和k柵欄覆蓋算法進(jìn)行仿真與實(shí)驗(yàn)分析，仿真結(jié)果都是獨(dú)立運(yùn)行50次后取得平均值。

圖4是將傳感器起點(diǎn)部署在長為100 m，寬為10 m的監(jiān)控區(qū)域，節(jié)點(diǎn)感知半徑為2 m，節(jié)點(diǎn)數(shù)目從30個增加到75個，MCBarrier移動距離之和不會隨著節(jié)點(diǎn)數(shù)的增多而增加，而CBarrier移動節(jié)點(diǎn)移動距離之和是隨著節(jié)點(diǎn)數(shù)的增多而不斷增大的。所以，MCBarrier與CBarrier相比，能夠移動更短的距離形成柵欄。

圖4 MCBarrier算法與CBarrier算法

圖5是在監(jiān)控區(qū)域長度為1 000 m，寬為100 m，節(jié)點(diǎn)感知半徑為5 m，節(jié)點(diǎn)數(shù)目從120個增加到180個，MCBarrier比GBGB構(gòu)筑1柵欄覆蓋總體移動距離比較，可以看到在一定范圍內(nèi)，MCBarrier更優(yōu)。

圖5 MCBarrier算法與GBGB算法

圖6是傳感器節(jié)點(diǎn)部署在長為1 000 m，寬為60 m的監(jiān)控區(qū)域，節(jié)點(diǎn)密度為0.09，節(jié)點(diǎn)感知半徑為1 m。從圖6可以得出，區(qū)域長度從1 000 m增加到1 800 m時，監(jiān)控區(qū)域內(nèi)形成3柵欄覆蓋中KMCBarrier算法與文獻(xiàn)[7]中GBIGB在k柵欄覆蓋構(gòu)建算中，兩者總體平均移動距離變化不大，但是在這個范圍內(nèi)，KMCBarrier總體上還是更優(yōu)。

圖6 平均移動距離與區(qū)域長度

從圖6中還可以得到，kMCBarrier的平均移動距離不隨著區(qū)域長度的增大，即網(wǎng)絡(luò)規(guī)模的擴(kuò)大而增加，說明kMCBarrier算法可擴(kuò)展性好，能夠適應(yīng)于大規(guī)模傳感器網(wǎng)絡(luò)的應(yīng)用。

4 結(jié) 論

無線傳感器網(wǎng)絡(luò)中柵欄覆蓋是一種高效覆蓋模型。本文研究了在監(jiān)控區(qū)域內(nèi)隨機(jī)部署移動傳感器節(jié)點(diǎn)時，如何能量高效地實(shí)現(xiàn)k柵欄覆蓋。本文提出了實(shí)現(xiàn)1柵欄覆蓋的MCBarrier算法和實(shí)現(xiàn)k柵欄覆蓋的基于分治算法的kMCBarrier算法。

仿真實(shí)驗(yàn)證明了這2種算法得有效性，并且kMCBarrier可以在大規(guī)模的隨機(jī)部署的傳感器網(wǎng)絡(luò)中k柵欄覆蓋的構(gòu)建具有擴(kuò)展性。

參考文獻(xiàn):

[1] 孫利民,李建中,陳 渝,等.無線傳感器網(wǎng)絡(luò)[M].北京:清華大學(xué)出版社,2005.

[2] Akyildiz I F,Su W,Sankarasubramaniam Y,et al.A survey on sensor networks[J].IEEE Communications Magazine,2002,40(8):101-114.

[3] Kumar S,Lai T H,Arora A.Barrier coverage with wireless sensor-s[C]∥Proceedings of the 11th Annual International Conference on Mobile Computing and Networking,ACM,2005:284-298.

[4] Ai Chen A,Kumar S,Lai T H.Designing localized algorithms for barrier coverage[C]∥Proc of ACM MOBICOM,2007:63-74.

[5] Bhattacharya B,Burmester B,Hu Y,et al.Optimal movement of mobile sensors for barrier coverage of a planar region[C]∥Combinatorial Optimization and Applications,Berlin Heidelberg:Springer,2008:103-115.

[6] Shen C,Cheng W,Liao X,et al.Barrier coverage with mobile sensors[C]∥IEEE International Symposium on Parallel Architectures,Algorithms,and Networks,2008:99-104.

[7] 班冬松,溫 俊,蔣 杰,等.移動無線傳感器網(wǎng)絡(luò) k柵欄覆蓋構(gòu)建算法[J].軟件學(xué)報(bào),2011,22(9):2089-2103.

[8] 謝金星,刑文訓(xùn).網(wǎng)絡(luò)優(yōu)化[M].北京：清華大學(xué)出版社,2000.

[9] Lawler E L.Combinatorial optimization:Networks and matroid-s[M].Mineola,NY:Dover Publications Inc,2001.