王 超,范興剛,王 恒,楊靜靜

(浙江工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,杭州 310023)

?

一種高效強(qiáng)K-柵欄覆蓋構(gòu)建算法*

王 超,范興剛*,王 恒,楊靜靜

(浙江工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,杭州 310023)

K-柵欄覆蓋是無(wú)線傳感器網(wǎng)絡(luò)覆蓋控制的研究熱點(diǎn)之一。本文構(gòu)建了強(qiáng)柵欄覆蓋模型,提出了分區(qū)強(qiáng)K-柵欄覆蓋構(gòu)建算法PMNSB,用最少的節(jié)點(diǎn)形成強(qiáng)柵欄。首先把監(jiān)控區(qū)域分成多個(gè)子區(qū)域,通過(guò)匈牙利算法選用移動(dòng)距離之和最少的網(wǎng)格集合為基準(zhǔn)1-柵欄覆蓋,缺少移動(dòng)節(jié)點(diǎn)的子區(qū)域,選擇附近區(qū)域的剩余移動(dòng)節(jié)點(diǎn)修補(bǔ)形成1-柵欄覆蓋。水平相鄰的兩個(gè)子區(qū)域之間構(gòu)建豎直柵欄,這些1-柵欄合起來(lái)構(gòu)成強(qiáng)K-柵欄覆蓋。仿真結(jié)果證明了該方法的有效性,本文的研究對(duì)提升無(wú)線傳感器網(wǎng)絡(luò)的性能具有重要的理論與實(shí)際意義。

無(wú)線傳感器網(wǎng)絡(luò);PMNSB;基準(zhǔn)1-柵欄覆蓋;豎直柵欄;匈牙利算法;修補(bǔ)策略;最小移動(dòng)距離

無(wú)線傳感器網(wǎng)絡(luò)在諸多領(lǐng)域有著廣泛的應(yīng)用,如將可將無(wú)線傳感器節(jié)點(diǎn)部署在污染源周圍檢測(cè)致命化學(xué)物的擴(kuò)散,將無(wú)線傳感器節(jié)點(diǎn)布撒在森林邊緣以監(jiān)測(cè)火災(zāi)發(fā)生和火情蔓延情況或放置在重要管道沿線以監(jiān)視針對(duì)管道的破壞活動(dòng),以及在敵營(yíng)周邊布設(shè)無(wú)線傳感器節(jié)點(diǎn)來(lái)監(jiān)視敵方的兵力部署和武器配備情況等。在上述列舉的應(yīng)用中,傳感器節(jié)點(diǎn)被部署于寬度小于感知半徑的狹長(zhǎng)的帶狀區(qū)域內(nèi),對(duì)監(jiān)控區(qū)域的移動(dòng)目標(biāo)進(jìn)行檢測(cè),這種技術(shù)被稱為柵欄覆蓋,是無(wú)線傳感器網(wǎng)絡(luò)領(lǐng)域的一個(gè)研究熱點(diǎn)[1]。

柵欄覆蓋目前已有一些研究工作[2-14]。Kumar定義了強(qiáng)柵欄,弱柵欄[2]。曹瑩瑩將影響柵欄覆蓋生命期的因素描述為一個(gè)多目標(biāo)優(yōu)化問(wèn)題[3]。楊濤研究了柵欄構(gòu)筑算法DPA,構(gòu)筑多條柵欄,實(shí)現(xiàn)多柵欄覆蓋[4]。羅卿采用概率性感知模型,提出一種柵欄覆蓋控制算法,調(diào)度傳感器使冗余節(jié)點(diǎn)睡眠,達(dá)到減少能耗和延長(zhǎng)網(wǎng)絡(luò)壽命的目的[5]。Li L研究了無(wú)線傳感器網(wǎng)絡(luò)(WSN)一維K-覆蓋問(wèn)題,分析k-coverage比例、全k-coverage概率和部分k-coverage概率[6]。秦寧寧提出了一種兼顧安全和時(shí)效兩種性能的啟發(fā)式軌跡算法,對(duì)劃分軌跡的準(zhǔn)確性進(jìn)行了研究[7]。孫繼忠解決無(wú)線傳感器網(wǎng)絡(luò)中柵欄覆蓋最佳路徑的問(wèn)題[8]。班冬松研究了全移動(dòng)傳感器網(wǎng)絡(luò)K-柵欄覆蓋問(wèn)題,提出了一種能量高效的柵欄覆蓋構(gòu)建算法CBIGB[9]。Jie Tian研究了兩維的柵欄覆蓋[10],Zhibo Wang研究了有向網(wǎng)絡(luò)的柵欄覆蓋[11]。郭新明研究了保證傳感柵欄貫通的前提下,盡可能降低柵欄整體的能耗方法[12]。張美燕研究了最大K有向覆蓋問(wèn)題,設(shè)計(jì)了一種分布式啟發(fā)式算法,在一跳鄰居范圍內(nèi)對(duì)傳感器節(jié)點(diǎn)的感知方向進(jìn)行協(xié)同調(diào)度,使得目標(biāo)集合被有向K覆蓋的時(shí)間最大[13]。針對(duì)井下無(wú)線傳感器網(wǎng)絡(luò)k(k=2)重覆蓋問(wèn)題,胡照鵬提出一種基于矩形分區(qū)覆蓋的節(jié)點(diǎn)確定部署策略。在只給出網(wǎng)絡(luò)規(guī)模和節(jié)點(diǎn)感應(yīng)半徑的條件下,求出網(wǎng)絡(luò)所需最少節(jié)點(diǎn)個(gè)數(shù)和節(jié)點(diǎn)間距[14]。

移動(dòng)節(jié)點(diǎn)重新部署形成柵欄的過(guò)程中,節(jié)點(diǎn)移動(dòng)將消耗大量能量,如何設(shè)計(jì)具有較小通信和計(jì)算開(kāi)銷的K-柵欄構(gòu)建算法仍是一個(gè)難點(diǎn)。借鑒上述文獻(xiàn)中的分區(qū)策略,本文主要研究如何用盡量少的節(jié)點(diǎn)形成強(qiáng)K-柵欄覆蓋,貢獻(xiàn)如下:①確定強(qiáng)K-柵欄基準(zhǔn),采用的匈牙利算法最佳匹配移動(dòng)節(jié)點(diǎn)與每一行。選用移動(dòng)距離之和最少的行為基準(zhǔn)1-柵欄。②為了形成強(qiáng)柵欄覆蓋,水平相鄰的兩個(gè)子區(qū)域之間縱向形成豎直柵欄。③缺少移動(dòng)節(jié)點(diǎn)的子區(qū)域,調(diào)動(dòng)附近區(qū)域的移動(dòng)節(jié)點(diǎn)修補(bǔ)形成1-柵欄。

本文余下章節(jié)安排如下:第1節(jié)描述網(wǎng)絡(luò)模型,定義MNSB問(wèn)題。第2節(jié)詳細(xì)介紹分區(qū)強(qiáng)柵欄構(gòu)建方法。第3節(jié)通過(guò)仿真實(shí)驗(yàn)對(duì)提出的兩種算法進(jìn)行性能評(píng)估。第4節(jié)總結(jié)全文并介紹下一步工作。

1 強(qiáng)柵欄覆蓋模型

假設(shè)在長(zhǎng)度為L(zhǎng),寬度為W區(qū)域中,隨機(jī)部署N個(gè)節(jié)點(diǎn)。節(jié)點(diǎn)具有移動(dòng)能力,節(jié)點(diǎn)能夠獲知自身地理位置信息。節(jié)點(diǎn)的感知半徑為R。需要在這個(gè)區(qū)域中形成K-強(qiáng)柵欄。

定義1 最少節(jié)點(diǎn)的強(qiáng)柵欄MNSB(Minimum Node Strong Barrier) 如果監(jiān)控區(qū)域A中存在一個(gè)從左到右傳感器節(jié)點(diǎn)集合:

S={s1,s2,…,sm},m≤N

(1)

x1≤x2≤…≤xm-1≤xm

(2)

形成一條水平強(qiáng)柵欄,每個(gè)節(jié)點(diǎn)的最大感知半徑在水平方向,則水平方向形成1條MNSB。

定義2 節(jié)點(diǎn)的最大感知半徑 節(jié)點(diǎn)的最大感知半徑為節(jié)點(diǎn)的感知區(qū)域內(nèi)存在的兩點(diǎn)間的最大距離。

定義3 節(jié)點(diǎn)密度 節(jié)點(diǎn)的數(shù)量與區(qū)域面積的比值為節(jié)點(diǎn)密度。節(jié)點(diǎn)密度對(duì)柵欄的形成有重要的影響,后面的仿真會(huì)進(jìn)一步分析節(jié)點(diǎn)密度對(duì)柵欄的影響。

定理 在沒(méi)有障礙物的前提下,如果存在一個(gè)節(jié)點(diǎn)集合Asz,水平相鄰兩個(gè)節(jié)點(diǎn)的感知區(qū)域有且僅有一個(gè)相切點(diǎn),相切點(diǎn)的連線與K-柵欄的方向重合,則這個(gè)集合構(gòu)成一條MNSB。

證明 由于全向節(jié)點(diǎn)的最大感知半徑為2R,相鄰的兩個(gè)相切點(diǎn)的距離也為2R,即相鄰的兩個(gè)節(jié)點(diǎn)對(duì)柵欄的貢獻(xiàn)最大,由于所有的節(jié)點(diǎn)都是依次相切,對(duì)柵欄的貢獻(xiàn)都是最大,形成的柵欄需要的節(jié)點(diǎn)數(shù)最少。即集合S滿足下列條件:

d(i-1,i)=d(i,i+1)=2R

(3)

其中d(·)表示兩個(gè)節(jié)點(diǎn)間的歐式距離,R表示節(jié)點(diǎn)的感知半徑。所以集合S構(gòu)成一條MNSB。

如圖1所示,有4個(gè)節(jié)點(diǎn)集合,集合一、三是強(qiáng)柵欄,節(jié)點(diǎn)集合四是弱柵欄。節(jié)點(diǎn)集合二不是強(qiáng)柵欄,也不是弱柵欄。柵欄一由13個(gè)節(jié)點(diǎn)構(gòu)成,柵欄三用了10個(gè)節(jié)點(diǎn),弱柵欄四也是由13個(gè)節(jié)點(diǎn)構(gòu)成。由此可見(jiàn),節(jié)點(diǎn)集合三節(jié)點(diǎn)之間的距離正好是2R,構(gòu)成強(qiáng)柵欄。如果集合2的節(jié)點(diǎn)進(jìn)行有限的移動(dòng)也可以形成MNSB。

圖1 柵欄覆蓋

我們研究的問(wèn)題就是:在區(qū)域A中,移動(dòng)節(jié)點(diǎn)密度不同的情況下,如何高效構(gòu)建強(qiáng)K-柵欄,使每個(gè)節(jié)點(diǎn)對(duì)柵欄的貢獻(xiàn)最大。

2 強(qiáng)K-柵欄覆蓋構(gòu)建算法

要構(gòu)建K-柵欄覆蓋,以節(jié)點(diǎn)為頂點(diǎn),節(jié)點(diǎn)的最近距離為權(quán)值,構(gòu)建有向圖,選擇兩個(gè)端點(diǎn),運(yùn)用Dijkstra算法[15]求兩點(diǎn)間的最短路徑。這個(gè)最短路徑上的節(jié)點(diǎn)就是柵欄基準(zhǔn)位置。大于節(jié)點(diǎn)的最大感知半徑的兩個(gè)節(jié)點(diǎn)之間需要移動(dòng)節(jié)點(diǎn)修補(bǔ),從而構(gòu)成柵欄。我們稱這種方法為RVSB算法,這種方法可以形成柵欄,但會(huì)消耗大量的通信資源。要減少通信和計(jì)算開(kāi)銷,可以把這個(gè)區(qū)域構(gòu)造K-柵欄這個(gè)復(fù)雜的問(wèn)題分成小問(wèn)題,先在小的子區(qū)域構(gòu)造1MNSB,這些1-柵欄合起來(lái)就是強(qiáng)K-柵欄,從而減少通信和計(jì)算開(kāi)銷。班冬松提出的基于CBIGB算法的強(qiáng)K-柵欄覆蓋構(gòu)建算法[9]就是分區(qū)的柵欄構(gòu)建方法,但是CBIGB算法在相鄰的子區(qū)域之間選擇整個(gè)豎直列為基準(zhǔn),需要較多節(jié)點(diǎn),消耗更多能量。而且這個(gè)算法沒(méi)有提到節(jié)點(diǎn)修補(bǔ),如果子區(qū)域的節(jié)點(diǎn)數(shù)不夠,而相鄰的子區(qū)域有相鄰的節(jié)點(diǎn)的情況下,就不能形成強(qiáng)柵欄。

結(jié)合兩個(gè)方法的優(yōu)缺點(diǎn),我們進(jìn)一步提出PMNSB算法(PartitioningConstructionofStrongBarrierofMinimumNode)。

2.1 算法的基本思想

將傳感器節(jié)點(diǎn)按照不同密度隨機(jī)部署在監(jiān)控區(qū)域。要形成K-柵欄,先將監(jiān)控區(qū)域進(jìn)行劃分,垂直方向?yàn)镵,水平方向?yàn)閂共K·V個(gè)相同大小的子矩形區(qū)域。再對(duì)監(jiān)控區(qū)域網(wǎng)格劃分,網(wǎng)格的內(nèi)切圓半徑為節(jié)點(diǎn)的感知半徑,即節(jié)點(diǎn)的最大感知半徑的一半。如果子區(qū)域內(nèi),某一行網(wǎng)格上,每一個(gè)網(wǎng)格有且僅有一個(gè)節(jié)點(diǎn),則節(jié)點(diǎn)兩兩相切。根據(jù)第2節(jié)的定理,這一行上的節(jié)點(diǎn)形成一條MNSB。運(yùn)用這個(gè)思想,強(qiáng)K-柵欄覆蓋構(gòu)建算法PMNSB在每一個(gè)子區(qū)域,利用匈牙利算法[15]對(duì)目標(biāo)點(diǎn)和移動(dòng)節(jié)點(diǎn)進(jìn)行最佳匹配,選擇基準(zhǔn)1-柵欄;對(duì)于缺少移動(dòng)節(jié)點(diǎn)的子區(qū)域,利用附近區(qū)域的移動(dòng)節(jié)點(diǎn)進(jìn)行修補(bǔ);水平相鄰的子區(qū)域之間通過(guò)豎直柵欄連接起來(lái),形成強(qiáng)K-柵欄覆蓋。我們稱這個(gè)算法為PMNSB算法。

2.2 算法具體過(guò)程

PMNSB算法的偽代碼如圖2。參數(shù)的定義如表1所示。

PMNSB算法具體步驟為:

步驟1 初始化。對(duì)區(qū)域網(wǎng)格化,進(jìn)行子區(qū)域劃分,得到子區(qū)域的節(jié)點(diǎn)集合Nsz,以網(wǎng)格為單位的子區(qū)域的長(zhǎng)度l,寬度w。

步驟2 選擇每一行的目標(biāo)網(wǎng)格。如果子區(qū)域Asz左側(cè)區(qū)域存在柵欄覆蓋,且柵欄所在的行為rs(z-1),對(duì)于第t行網(wǎng)格,p=|rs(z-1)-t|,則選取相應(yīng)的豎直柵欄目標(biāo)網(wǎng)格VGt(見(jiàn)圖3),t行的目標(biāo)網(wǎng)格為Gt=(gt1,…,gtl,…,gttm),其中tm=l+p。如果子區(qū)域中移動(dòng)節(jié)點(diǎn)數(shù)目小于基準(zhǔn)柵欄需求,直接選取與左邊子區(qū)域一樣的基準(zhǔn)柵欄行rsz=rs(z-1)。

步驟3 確定基準(zhǔn)柵欄,選擇節(jié)點(diǎn)構(gòu)建柵欄。對(duì)于區(qū)域Asz的第t行的Gt按照式(4)進(jìn)行矩陣賦值操作。運(yùn)用匈牙利算法,得出節(jié)點(diǎn)最小總移動(dòng)距離Dt。選取Dt最小的行作為子區(qū)域的基準(zhǔn)網(wǎng)格柵欄行rsz(如圖3),對(duì)應(yīng)的可移動(dòng)節(jié)點(diǎn)移動(dòng)到目標(biāo)位置構(gòu)建柵欄。

圖2 PMNSB偽代碼

圖3 豎直柵欄網(wǎng)格的選取

表1 參數(shù)定義

步驟4 柵欄修補(bǔ)。如果子區(qū)域中移動(dòng)節(jié)點(diǎn)數(shù)目小于基準(zhǔn)柵欄需求,移動(dòng)節(jié)點(diǎn)先移動(dòng)到相應(yīng)的基準(zhǔn)柵欄位置,移動(dòng)節(jié)點(diǎn)加到集合MS中,移動(dòng)距離加到TMov,沒(méi)有移動(dòng)的節(jié)點(diǎn)集合保存到一個(gè)集合RS中。RS和未部署的網(wǎng)格RG進(jìn)行匹配修補(bǔ)(修補(bǔ)效果見(jiàn)圖4)。移動(dòng)節(jié)點(diǎn)加到集合MS中,移動(dòng)距離加到TMov。并計(jì)算平均移動(dòng)距離AMov。

步驟5 輸出柵欄,總移動(dòng)距離,平均移動(dòng)距離。

參數(shù)進(jìn)一步解釋如圖3,l=6,w=5,子區(qū)域Asz左側(cè)區(qū)域的基準(zhǔn)柵欄行rs(z-1)=3,針對(duì)t=1,豎直柵欄目標(biāo)列VG1=(vg1,vg2),p=2,l+p=8。對(duì)于區(qū)域Asz的第t行的目標(biāo)網(wǎng)格與移動(dòng)節(jié)點(diǎn)進(jìn)行距離計(jì)算公式如下:

(4)

式中,(xi,yi)表示第t行目標(biāo)網(wǎng)格中的第i個(gè)網(wǎng)格gi(0≤i≤tm)的位置信息,(xj,yj)表示節(jié)點(diǎn)sj的位置信息。

2.3 算法的復(fù)雜性分析

在子區(qū)域Asz中,傳感器節(jié)點(diǎn)的個(gè)數(shù)為Nsz。在這個(gè)區(qū)域中,可能形成1-柵欄的目標(biāo)位置最大個(gè)數(shù)為l+w-1,只要Nsz≥l+w-1,子區(qū)域就能形成MNSB。整個(gè)區(qū)域要形成K-柵欄,目標(biāo)位置的最大個(gè)數(shù)為(l+w-1)·K·V,也就是說(shuō)在修補(bǔ)策略下,只要節(jié)點(diǎn)總個(gè)數(shù)N≥(l+w-1)·K·V,PMNSB就一定能形成強(qiáng)K-柵欄。

(5)

由于算法的復(fù)雜度主要和節(jié)點(diǎn)數(shù)N,柵欄數(shù)K,V有關(guān)。如果沒(méi)有進(jìn)行子區(qū)域劃分,每一個(gè)網(wǎng)格與每一個(gè)節(jié)點(diǎn)都要進(jìn)行匹配對(duì)比,算法復(fù)雜度算法總的復(fù)雜度為:

(6)

由于每個(gè)節(jié)點(diǎn)都要與中心節(jié)點(diǎn)通信,這是的通信開(kāi)銷為O(N),中心節(jié)點(diǎn)把結(jié)果通知給移動(dòng)節(jié)點(diǎn),通信開(kāi)銷最多為O(N),總的通信開(kāi)銷為O(N)。分區(qū)域以后,節(jié)點(diǎn)只需要與分區(qū)域的中心節(jié)點(diǎn)通信,假設(shè)節(jié)點(diǎn)均勻分布,這時(shí)候,通信開(kāi)銷僅為O(N/K×V)。很顯然分區(qū)以后,計(jì)算和通信開(kāi)銷都大大降低。

3 仿真結(jié)果

本文運(yùn)用MATLAB7.0對(duì)此算法進(jìn)行仿真,如果沒(méi)有特別指明,實(shí)驗(yàn)的默認(rèn)參數(shù)如表2所示。為了體現(xiàn)PMNSB算法在傳感器節(jié)點(diǎn)的使用數(shù)量和移動(dòng)距離上的優(yōu)勢(shì),我們對(duì)3種算法PMNSB、CBIGB,RVSB進(jìn)行性能比較。在保證能形成柵欄的前提下,相對(duì)較少的節(jié)點(diǎn)分布更能體現(xiàn)出各算法的優(yōu)劣性,因?yàn)?.005的節(jié)點(diǎn)密度不能使CBIGB形成6柵欄覆蓋,因此此處我們選擇0.006作為節(jié)點(diǎn)分布的密度。

表2 實(shí)驗(yàn)參數(shù)

圖4為傳感器節(jié)點(diǎn)的初始分布圖,以及運(yùn)行CBIGB算法、RVSB算法、PMNSB算法后2-柵欄覆蓋節(jié)點(diǎn)分布圖,它們分別用78,87,52個(gè)節(jié)點(diǎn)形成了2-柵欄覆蓋,可見(jiàn)PMNSB算法用最少的節(jié)點(diǎn)形成了柵欄。

在節(jié)點(diǎn)較少的情況下,如果沒(méi)有修補(bǔ),就可能形不成柵欄,如圖5所示,在密度為0.003的情況下,如果沒(méi)有修補(bǔ)就不能形成3-柵欄,而用附近的節(jié)點(diǎn)修補(bǔ)以后,就可以形成3-柵欄?？梢?jiàn)修補(bǔ)策略是非常有必要的。

影響柵欄構(gòu)建的主要參數(shù)是節(jié)點(diǎn)數(shù)N,柵欄數(shù)K,參數(shù)V。我們進(jìn)一步詳細(xì)分析這些參數(shù)對(duì)柵欄形成的影響,所有的實(shí)驗(yàn)結(jié)果都是50次實(shí)驗(yàn)的平均值。評(píng)價(jià)指標(biāo)是形成K-柵欄的節(jié)點(diǎn)數(shù),總移動(dòng)距離和平均移動(dòng)距離3個(gè)指標(biāo)。形成K-柵欄節(jié)點(diǎn)數(shù)越少,說(shuō)明算法的效率越高,由于移動(dòng)會(huì)消耗能量,總移動(dòng)距離越少,整個(gè)網(wǎng)絡(luò)的耗能就越少,網(wǎng)絡(luò)的工作時(shí)間就越長(zhǎng)。平均移動(dòng)距離越小,節(jié)點(diǎn)的能耗越均勻。

圖4 隨機(jī)部署VS柵欄部署的節(jié)點(diǎn)分布

圖5 柵欄修補(bǔ)對(duì)比圖

3.1 節(jié)點(diǎn)密度的影響

圖6 節(jié)點(diǎn)密度VS總移動(dòng)距離

節(jié)點(diǎn)密度影響如圖6～圖8所示。由圖可以看出隨著密度的增加,3種算法總移動(dòng)距離,平均移動(dòng)距離都在降低,PMNSB算法的節(jié)點(diǎn)平均移動(dòng)距離明顯低于其他兩種算法,也就是說(shuō)PMNSB算法節(jié)點(diǎn)能耗更加均勻。PMNSB算法和CBIGB算法形成柵欄的節(jié)點(diǎn)數(shù)基本不變,RVSB算法節(jié)點(diǎn)數(shù)隨著密度的增加而增加。3個(gè)指標(biāo)都是PMNSB算法最低,在低密度下,總移動(dòng)距離PMNSB算法比CBIGB算法、RVSB算法低40%多,50%。平均移動(dòng)距離低30%,50%。節(jié)點(diǎn)數(shù)分別相差60%,50%～70%。

圖7 節(jié)點(diǎn)密度VS平均移動(dòng)距離

圖8 節(jié)點(diǎn)密度VS形成柵欄所需節(jié)點(diǎn)數(shù)

3.2 不同柵欄數(shù)的影響

柵欄數(shù)K值影響如圖9～圖11所示。由圖9和圖10可以看出,隨著柵欄數(shù)的增加,3種算法的3個(gè)指標(biāo)都增加。如圖9所示,形成1-柵欄,6-柵欄,PMNSB算法分別需要總移動(dòng)距離150 m,1 400 m,平均距離為6 m,9 m;CBIGB算法分別需要總移動(dòng)距離400 m,1 800 m,平均距離為8 m,12 m。K的增大導(dǎo)致相應(yīng)子區(qū)域內(nèi)的可選擇的傳感器節(jié)點(diǎn)數(shù)量減少,使得平均移動(dòng)距離和總移動(dòng)距離變大。

圖9 K值VS移動(dòng)總距離

圖10 K值VS平均移動(dòng)距離

PMNSB算法用最少的節(jié)點(diǎn)生成的K-柵欄。如圖11所示,形成1-柵欄,6-柵欄,PMNSB算法分別需要30,140,CBIGB算法分別需要60,160個(gè)。所以同樣的節(jié)點(diǎn)數(shù),PMNSB算法形成的柵欄數(shù)最多。RVSB形成的柵欄數(shù)最少,當(dāng)K增加到4時(shí),RVSB算法形成4-柵欄覆蓋的幾率小于1,當(dāng)K增加到5時(shí),基本無(wú)法再形成柵欄覆蓋,說(shuō)明RVSB算法對(duì)區(qū)域內(nèi)的傳感器節(jié)點(diǎn)數(shù)量要求比較高。

圖11 K值VS形成柵欄所需節(jié)點(diǎn)

3.3 不同柵欄基準(zhǔn)的影響

不同的柵欄基準(zhǔn),效果是不一樣的,我們把本算法和文獻(xiàn)[9]的BGBS2,BGBS3比較,結(jié)果如圖12～圖15所示。

圖12 節(jié)點(diǎn)密度VS總移動(dòng)距離

圖13 節(jié)點(diǎn)密度VS平均移動(dòng)距離

圖14 K值VS總移動(dòng)距離

圖15 K值VS平均移動(dòng)距離

由圖可知,在節(jié)點(diǎn)密度0.004時(shí),PMNSB,BGBS2,BGBS3算法形成2-柵欄需要的總移動(dòng)距離為420 m、480 m、430 m,平均移動(dòng)距離為8.5 m、9.5 m、8.8 m。無(wú)論在密度一樣的情況下還是K值一樣的情況下,PMNSB性能都優(yōu)于BGBS2和BGBS3算法,不過(guò)PMNSB的計(jì)算復(fù)雜度高于BGBS2和BGBS3,但是由于使用PMNSB能有效減少傳感器節(jié)點(diǎn)移動(dòng)距離,因此PMNSB策略更優(yōu)。BGBS2和BGBS3是人為指定的目標(biāo)位置,而PMNSB是采用匈牙利匹配算法選擇節(jié)點(diǎn)形成K-柵欄。盡管3種算法需要的節(jié)點(diǎn)數(shù)一樣,但PMNSB算法移動(dòng)距離最小。

3.4 不同V值對(duì)結(jié)果的影響

我們進(jìn)一步分析了不同的V值對(duì)PMNSB算法的仿真結(jié)果影響,如圖16、圖17所示。當(dāng)V值為2,3,4時(shí),形成2-柵欄需要的總移動(dòng)距離為830 m、880 m、880 m,平均移動(dòng)距離為17 m、18 m、18 m。V越大子區(qū)域越小,子區(qū)域內(nèi)的節(jié)點(diǎn)數(shù)目就越少,使得節(jié)點(diǎn)的選擇變少,有可能會(huì)增加總移動(dòng)距離和平均移動(dòng)距離;另一方面,V越大導(dǎo)致水平方向上的子區(qū)域增多,因此一整條柵欄中基準(zhǔn)柵欄位置的選擇增大,能一定程度降低總移動(dòng)距離和平均移動(dòng)距離。但當(dāng)節(jié)點(diǎn)密度較少時(shí),不同的V的取值對(duì)于移動(dòng)距離的影響很小。

圖16 V值VS平均移動(dòng)距離

圖17 V值VS總移動(dòng)距離

4 結(jié)論

本文主要研究強(qiáng)K-柵欄覆蓋構(gòu)建方法PMNSB。先在子區(qū)域選擇移動(dòng)距離之和最少的基準(zhǔn)1-柵欄覆蓋位置。移動(dòng)節(jié)點(diǎn)移動(dòng)到此位置。缺少移動(dòng)節(jié)點(diǎn)的子區(qū)域,附近區(qū)域的移動(dòng)節(jié)點(diǎn)修補(bǔ)形成1-柵欄覆蓋。水平相鄰的兩個(gè)子區(qū)域之間形成隔離柵欄。這些子區(qū)域合拼,構(gòu)成強(qiáng)K-柵欄覆蓋。

仿真結(jié)果證明,PMNSB可以用最少的節(jié)點(diǎn),高效節(jié)能的構(gòu)建K-柵欄。柵欄形成以后,如何節(jié)能高效的工作是下一步要研究的內(nèi)容。

[1] 任彥,張思東,張宏科.無(wú)線傳感器網(wǎng)絡(luò)中覆蓋控制理論與算法[J].軟件學(xué)報(bào),2006,17(3):422-433.

[2]Kumar S,Lai T H,Arora A.Barrier Coverage with Wireless Sensors[C]//Proc of the 11th Annual International Conference on Mobile Computing and Networking,2005:284-298.

[3]曹瑩瑩,黃劉生,朱立才,等.一種協(xié)作的異構(gòu)傳感器最優(yōu)柵欄覆蓋模型[J].小型微型計(jì)算機(jī)系統(tǒng),2012,33(11):2457-2462.

[4]楊濤,慕德俊.無(wú)線傳感器網(wǎng)絡(luò)多柵欄覆蓋構(gòu)建算法研究[J].彈箭與制導(dǎo)學(xué)報(bào),2012,32(2):173-176.

[5]羅卿,林亞平,王雷,等.傳感器網(wǎng)絡(luò)中基于數(shù)據(jù)融合的柵欄覆蓋控制研究[J].電子與信息學(xué)報(bào),2012,34(4):825-831.

[6]Li L,Zhang B,Zheng J.A Study on One-Dimensional K-Coverage Problem in Wireless Sensor Networks[J].Wireless Communica-tions and Mobile Computing,2013,13(1):1-11.

[7]秦寧寧,張林,山秀明,等.無(wú)線傳感器網(wǎng)絡(luò)啟發(fā)式移動(dòng)軌跡策略的研究[J].電子與信息學(xué)報(bào),2008,30(3):707-711.

[8]孫繼忠,馬永強(qiáng),胡艷,等.分布式Delaunay三角剖分在柵欄覆蓋中的應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用,2010,46(26):76-79.

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

[10]Tian Jie,Zhang Wensheng,Wang Guiling,et al.2D K-Barrier Duty-Cycle Scheduling for Intruder Detection in Wireless Sensor Networks[J].Computer communications,2014,4(3):31-42.

[11]Wang Zhibo,Liao Jilong,Cao Qing,et al.Achieving K-Barrier Coverage in Hybrid Directional Sensor Networks[J].IEEE Transactions on Mobile Computing,2014,13(7):1443-1455.

[12]郭新明.高效無(wú)線傳感器網(wǎng)絡(luò)強(qiáng)k-柵欄覆蓋節(jié)能算法[J].計(jì)算機(jī)應(yīng)用,2013,33(8):2104-2107.

[13]張美燕,蔡文郁.無(wú)線視頻傳感器網(wǎng)絡(luò)有向感知K覆蓋控制算法研究[J].傳感技術(shù)學(xué)報(bào),2013,26(5):728-733.

[14]胡照鵬,張長(zhǎng)森.基于矩形分區(qū)覆蓋的節(jié)點(diǎn)確定部署策略[J].傳感技術(shù)學(xué),2013,26(3):411-413.

[15]王海英,黃強(qiáng),李傳濤.圖論算法及其MATLAB實(shí)現(xiàn)[M].北京:北京航空航天大學(xué)出版社,2010.

An Effective Realization Scheme for Strong K-Barrier Coverage in WSN*

WANGChao,FANXinggang*,WANGHeng,YANGJingjing

(College of Computer Science and Technology,Zhejiang University of Technology,Hangzhou 310023,China)

K-barrier coverage is one of the hot spot in the wireless sensor network.This paper mainly proposes PMNSB(partitioning construction of strong barrier of minimum node).First,it divides the interested area into several subareas,1-barrier coverage benchmark are determined by Hungary algorithm in each subarea.Second,according to this benchmark,mobile nodes in this subarea move to its destination to build 1-barrier coverage.If it is lack of mobile node in one subarea,the residual mobile node near this subarea repair the hole of barrier benchmark.Third,there is vertical barrier between two horizontal adjacent subarea.Finally,these 1-barriers are merged into strong K-barrier coverage.Simulation results show our method could effectively constitute K-barrier coverage,and enhance the coverage performance of WSN.This research has important theoretical and practical significance.

WSN;PMNSB;1-barrier coverage benchmark;vertical barrier;Hungary algorithm;Repairing scheme;Minimum sum of moving distance

王 超(1993-),男,本科生,主要研究領(lǐng)域?yàn)闊o(wú)線傳感器網(wǎng)絡(luò);

范興剛(1974-),男,浙江工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院副教授,工學(xué)博士,研究領(lǐng)域?yàn)閭鞲衅骶W(wǎng)絡(luò),網(wǎng)絡(luò)通信、實(shí)時(shí)通信,分布式實(shí)時(shí)系統(tǒng)的設(shè)計(jì),xgfan@zjut.edu.cn;

楊靜靜(1990-),男,碩士生,主要研究領(lǐng)域?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)。

項(xiàng)目來(lái)源:“十二五”國(guó)家科技支撐計(jì)劃項(xiàng)目(2012BAD10B01);浙江省大學(xué)生科技創(chuàng)新活動(dòng)計(jì)劃(新苗人才計(jì)劃)

2014-10-06 修改日期:2014-11-24

C:6150P;6210;7230

10.3969/j.issn.1004-1699.2015.02.014

TP273

A

1004-1699(2015)02-0227-07