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

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

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

?

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)

x1≤x2≤…≤xm-1≤xm

(2)

形成一條水平強(qiáng)柵欄,每個節(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)密度對柵欄的形成有重要的影響,后面的仿真會進(jìn)一步分析節(jié)點(diǎn)密度對柵欄的影響。

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

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

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

(3)

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

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

圖1 柵欄覆蓋

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

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

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

結(jié)合兩個方法的優(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個相同大小的子矩形區(qū)域。再對監(jiān)控區(qū)域網(wǎng)格劃分,網(wǎng)格的內(nèi)切圓半徑為節(jié)點(diǎn)的感知半徑,即節(jié)點(diǎn)的最大感知半徑的一半。如果子區(qū)域內(nèi),某一行網(wǎng)格上,每一個網(wǎng)格有且僅有一個節(jié)點(diǎn),則節(jié)點(diǎn)兩兩相切。根據(jù)第2節(jié)的定理,這一行上的節(jié)點(diǎn)形成一條MNSB。運(yùn)用這個思想,強(qiáng)K-柵欄覆蓋構(gòu)建算法PMNSB在每一個子區(qū)域,利用匈牙利算法[15]對目標(biāo)點(diǎn)和移動節(jié)點(diǎn)進(jìn)行最佳匹配,選擇基準(zhǔn)1-柵欄;對于缺少移動節(jié)點(diǎn)的子區(qū)域,利用附近區(qū)域的移動節(jié)點(diǎn)進(jìn)行修補(bǔ);水平相鄰的子區(qū)域之間通過豎直柵欄連接起來,形成強(qiáng)K-柵欄覆蓋。我們稱這個算法為PMNSB算法。

2.2 算法具體過程

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

PMNSB算法具體步驟為:

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

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

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

圖2 PMNSB偽代碼

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

表1 參數(shù)定義

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

步驟5 輸出柵欄,總移動距離,平均移動距離。

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

(4)

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

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

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

(5)

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

(6)

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

3 仿真結(jié)果

本文運(yùn)用MATLAB7.0對此算法進(jìn)行仿真,如果沒有特別指明,實(shí)驗(yàn)的默認(rèn)參數(shù)如表2所示。為了體現(xiàn)PMNSB算法在傳感器節(jié)點(diǎn)的使用數(shù)量和移動距離上的優(yōu)勢,我們對3種算法PMNSB、CBIGB,RVSB進(jìn)行性能比較。在保證能形成柵欄的前提下,相對較少的節(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個節(jié)點(diǎn)形成了2-柵欄覆蓋,可見PMNSB算法用最少的節(jié)點(diǎn)形成了柵欄。

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

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

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

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

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

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

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

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

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

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

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

圖9 K值VS移動總距離

圖10 K值VS平均移動距離

PMNSB算法用最少的節(jié)點(diǎn)生成的K-柵欄。如圖11所示,形成1-柵欄,6-柵欄,PMNSB算法分別需要30,140,CBIGB算法分別需要60,160個。所以同樣的節(jié)點(diǎn)數(shù),PMNSB算法形成的柵欄數(shù)最多。RVSB形成的柵欄數(shù)最少,當(dāng)K增加到4時,RVSB算法形成4-柵欄覆蓋的幾率小于1,當(dāng)K增加到5時,基本無法再形成柵欄覆蓋,說明RVSB算法對區(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總移動距離

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

圖14 K值VS總移動距離

圖15 K值VS平均移動距離

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

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

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

圖16 V值VS平均移動距離

圖17 V值VS總移動距離

4 結(jié)論

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

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

[1] 任彥,張思東,張宏科.無線傳感器網(wǎng)絡(luò)中覆蓋控制理論與算法[J].軟件學(xué)報,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ī)系統(tǒng),2012,33(11):2457-2462.

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

[5]羅卿,林亞平,王雷,等.傳感器網(wǎng)絡(luò)中基于數(shù)據(jù)融合的柵欄覆蓋控制研究[J].電子與信息學(xué)報,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ǎng)絡(luò)啟發(fā)式移動軌跡策略的研究[J].電子與信息學(xué)報,2008,30(3):707-711.

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

[9]班冬松,溫俊,蔣杰,等.移動無線傳感器網(wǎng)絡(luò)K-柵欄覆蓋的構(gòu)建算法[J].軟件學(xué)報,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ǎng)絡(luò)強(qiáng)k-柵欄覆蓋節(jié)能算法[J].計算機(jī)應(yīng)用,2013,33(8):2104-2107.

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

[14]胡照鵬,張長森.基于矩形分區(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ǎng)絡(luò);

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

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

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

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