范興剛 任勇默 車志聰 王 超

(浙江工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院 杭州 310023)(xgfan@zjut.edu.cn)

一種基于鄰居節(jié)點運動的分布式有向柵欄構(gòu)建算法

范興剛 任勇默 車志聰 王 超

(浙江工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院 杭州 310023)(xgfan@zjut.edu.cn)

K-柵欄覆蓋是有向傳感器網(wǎng)絡(luò)的研究熱點之一.目前為止，很少從移動和轉(zhuǎn)動能耗相結(jié)合考慮有向柵欄構(gòu)建.提出一種基于鄰居節(jié)點運動的分布式有向強柵欄構(gòu)建方法(distributed directional strong barrier construction based on neighbor actuation, DBCNA).在形成柵欄的節(jié)點集合中，若在前一個感知區(qū)域內(nèi)部存在節(jié)點，橫坐標最大的節(jié)點就是節(jié)點的目標位置.如果感知區(qū)域內(nèi)部沒有節(jié)點，則令前一個節(jié)點正右方向一個半徑距離處作為下一節(jié)點的目標位置.有向節(jié)點的目標感知方向由移動到該位置的移動節(jié)點的初始感知方向決定.若初始感知方向0≤β≤α2或2π-α2≤β≤2π，目標感知方向就是節(jié)點的初始感知方向；若α2≤β≤π，目標感知方向為β=α2；若π<β<2π-α2，目標感知方向為β=2π-α2.仿真結(jié)果證明了該柵欄構(gòu)建方法比其他方法節(jié)省40%的節(jié)點，平均能耗降低了40%～50%，具有重要的理論與實際意義.

有向柵欄覆蓋；目標位置；感知方向；下一個節(jié)點；運動能耗

有向傳感器，如視頻傳感器、超聲傳感器和紅外傳感器等在諸多領(lǐng)域有著廣泛的應(yīng)用，如可將傳感器節(jié)點部署在重要管道沿線以監(jiān)視針對管道的破壞活動，以及在敵營周邊布設(shè)無線傳感器節(jié)點來監(jiān)視敵方的兵力部署和武器配備情況等.在上述列舉的應(yīng)用中，有向傳感器節(jié)點被部署于感興趣區(qū)域的邊界，對進入感興趣區(qū)域的移動目標進行檢測，這種技術(shù)被稱為柵欄覆蓋.如何實現(xiàn)柵欄覆蓋是有向傳感網(wǎng)絡(luò)的一個研究熱點[1].

利用節(jié)點的移動能力構(gòu)建全向柵欄已有一些研究工作.班冬松等人[2]研究了全向移動傳感器網(wǎng)絡(luò)K-柵欄覆蓋問題，提出了一種能量高效的柵欄覆蓋構(gòu)建算法CBIGB.王志波等人[3]研究了節(jié)點存在定位誤差時的柵欄覆蓋問題.賀詩波等人[4]多次移動節(jié)點構(gòu)建柵欄覆蓋.Saipulla等人[5]構(gòu)建柵欄過程中，考慮了節(jié)點移動能力的有限性.在有向柵欄研究中，馬華東等人[6]研究了最少的有向視頻節(jié)點組建柵欄問題；Zhang等人[7]利用有向節(jié)點的轉(zhuǎn)動能力構(gòu)建強柵欄；Wang等人[8]選擇有向節(jié)點組建視線柵欄，構(gòu)建有向傳感陣列監(jiān)視入侵者；王志波等人[9-10]研究了混合有向網(wǎng)絡(luò)的柵欄覆蓋，根據(jù)網(wǎng)絡(luò)拓撲構(gòu)建權(quán)重柵欄圖WBG，再運用頂點不相交的路徑算法構(gòu)造K-柵欄.以上這些方法都是集中式的，都需要知道整個網(wǎng)絡(luò)的拓撲.Shih等人[11]研究了分布式柵欄構(gòu)建算法，利用可能柵欄行中的鄰居節(jié)點通過柵欄信息構(gòu)建柵欄.陶丹等人[12]利用鄰居節(jié)點的位置信息，選擇具有最多鄰居的節(jié)點構(gòu)建柵欄.Zhang等人[13]等人研究了概率均值聚類在大數(shù)據(jù)環(huán)境下的應(yīng)用.

利用附近節(jié)點之間的位置關(guān)系，可以選擇最優(yōu)的節(jié)點構(gòu)建柵欄.我們研究了全向強柵欄構(gòu)建，提出了PMNSB算法[14].Guvensan等人[15]基于移動能耗和轉(zhuǎn)動能耗研究了有向網(wǎng)絡(luò)的覆蓋增強.在此基礎(chǔ)上，本文研究如何利用節(jié)點之間的位置關(guān)系，調(diào)度節(jié)點的運動，節(jié)能高效地構(gòu)建強K-柵欄覆蓋，提出一種基于鄰居節(jié)點運動的分布式有向強柵欄構(gòu)建方法(distributed directional strong barrier construction based on neighbor actuation, DBCNA).在形成柵欄的節(jié)點集合中，按照從左到右的節(jié)點順序，確定節(jié)點的目標位置，并選擇能耗最少的節(jié)點移動到目標位置，構(gòu)建有向強柵欄.

1 相關(guān)模型和定義

Fig. 1 Model of rotatable directional sensor 圖1 可旋轉(zhuǎn)有向傳感器的傳感模型

研究有向柵欄問題之前，有3條假設(shè)：

1) 所有傳感器的感知半徑和感知角度均相同.

2) 所有傳感器的轉(zhuǎn)動能耗和移動功耗均相同，參考文獻[15]，傳感器每轉(zhuǎn)動180°耗能為1.8 J，每移動1 m耗能為3.6 J.

3) 傳感器監(jiān)視范圍內(nèi)的信號強度相同,且能在范圍內(nèi)以100%的可能性監(jiān)測到事件.

定義1. 有向節(jié)點的目標位置.形成強柵欄的有向節(jié)點的目標位置坐標就是有向節(jié)點的目標位置.有向節(jié)點只要移動到這個位置才有可能形成柵欄.有向節(jié)點的目標位置由形成柵欄的前一個節(jié)點決定.

定義2. 有向節(jié)點的目標感知方向.移動到目標位置的有向節(jié)點的感知方向就是有向節(jié)點的目標感知方向.有向節(jié)點的目標感知方向由移動到該位置的移動節(jié)點的初始感知方向決定.

定義3. 有向節(jié)點運動能耗.有向節(jié)點運動能耗是指有向移動節(jié)點運動到目標位置的能耗，由移動能耗和轉(zhuǎn)動能耗組成.第i(i≥2)個節(jié)點的轉(zhuǎn)動能耗如式(1)所示，運動能耗如式(2)所示，其中的參數(shù)見后面的表1.式(1)標明，若0≤β≤α2，或者2π-α2≤β≤2π，則不進行轉(zhuǎn)動；若α2≤β≤π，轉(zhuǎn)至β=α2處；若π<β<2π-α2，轉(zhuǎn)至β=2π-α2處.式(2)中，表示節(jié)點移動到目標位置的最小距離，移動能耗和轉(zhuǎn)動能耗之和就是有向節(jié)點運動能耗.

(1)

(2)

定義4. 節(jié)點密度.節(jié)點是隨機分布的，服從強度為γ泊松點分布，則γ稱為節(jié)點密度.節(jié)點密度對柵欄的形成有重要的影響，后面的仿真會進一步分析節(jié)點密度對柵欄的影響.

定義5. 能耗標準差.假設(shè)組成柵欄的節(jié)點總個數(shù)是Nb，第i個節(jié)點的能耗為ei，平均能耗為Em，構(gòu)建K條柵欄能耗標準差為D(K)，反映了構(gòu)建柵欄的過程中節(jié)點的能量波動，反映了柵欄的持續(xù)壽命與穩(wěn)定性.

(3)

有向強柵欄的定義見文獻[10]的定義6，我們研究的問題就是：在狹長區(qū)域中隨機部署的有向移動節(jié)點密度為γ的情況下，如何分布式地調(diào)度移動節(jié)點，以盡量少的運動能耗構(gòu)建有向強柵欄覆蓋.

2 分布式有向強柵欄構(gòu)建算法(DBCNA)

王志波等人[9-10]根據(jù)感知區(qū)域內(nèi)所有靜態(tài)節(jié)點組成的網(wǎng)絡(luò)拓撲結(jié)構(gòu)構(gòu)建加權(quán)圖，采用頂點不重復(fù)的K條路徑圖論算法找到形成柵欄的目標位置，然后移動節(jié)點和這些目標位置進行最佳匹配，這需要全局拓撲信息，通信和開銷較大，而且不適用于要減少通信和計算開銷.PMNSB算法把構(gòu)造K-柵欄這個復(fù)雜的問題分成小問題，先在小的子區(qū)域構(gòu)造1MNSB，這些1-柵欄合起來就是強K-柵欄.但PMNSB算法不能用于有向強柵欄的構(gòu)建，在有向柵欄中，有向節(jié)點感知不再是圓形而是扇形，單獨的圓心不能確定一個有向節(jié)點的位置.而且PMNSB算法僅考慮節(jié)點的移動，沒有考慮節(jié)點的轉(zhuǎn)動，而轉(zhuǎn)動節(jié)點是解決有向覆蓋問題的主要方法.在此基礎(chǔ)上，我們提出一種分布式基于鄰居節(jié)點運動的分布式有向強柵欄構(gòu)建算法(DBCNA).

2.1 理論分析

DBCNA算法的基本思想如下：運用節(jié)點之間的位置關(guān)系，在形成柵欄的節(jié)點集合中，按照從左到右的節(jié)點順序，按照節(jié)點對柵欄貢獻盡量最大原則，分布式地確定節(jié)點的目標位置，為了保證形成柵欄，節(jié)點的目標位置只與前一個節(jié)點有關(guān)，不僅如此，前一個節(jié)點還根據(jù)自己周圍的節(jié)點分布情況，進一步確定運動到目標位置的移動節(jié)點，并選擇能耗最少的節(jié)點移動到目標位置，從而構(gòu)建有向強柵欄.

要形成柵欄，先依次找到目標位置，再由前一個節(jié)點選擇最優(yōu)的移動節(jié)點運動到目標位置，再調(diào)整這個節(jié)點的感知方向，形成柵欄.

Fig. 2 Selection of nodes圖2 節(jié)點的選擇

移動到目標位置的有向節(jié)點的感知方向就是有向節(jié)點的目標感知方向.有向節(jié)點的目標感知方向由移動到該位置的移動節(jié)點的初始感知方向決定.如果初始感知方向0≤β≤α2或者2π-α2≤β≤2π，則有向節(jié)點的目標感知方向就是節(jié)點的初始感知方向；如果α2≤β≤π，有向節(jié)點的目標感知方向為β=α2處；如果π<β<2π-α2，有向節(jié)點的目標感知方向為β=2π-α2.式(2)中，表示節(jié)點移動到目標位置的最小距離，移動能耗和轉(zhuǎn)動能耗之和就是有向節(jié)點的運動能耗.如圖2(a)和圖2(c)所示，點C是節(jié)點的目標位置，由于節(jié)點C的初始感知方向為α2≤β≤π，則運動到目標位置點C的目標感知方向就是β=α2.如圖2(b)和圖2(d)所示，點C是節(jié)點的目標位置，由于節(jié)點C的初始感知方向為π<β<2π-α2，則運動到目標位置點C的目標感知方向就是β=2π-α2.

有向節(jié)點的目標感知方向，除節(jié)點1外，感知方向在[-α2,α2]之間.節(jié)點1的感知方向見2.2節(jié).

2.2 算法的詳細過程

參數(shù)的定義如表1所示:

Table 1 The Parameters

DBCNA算法步驟描述如下：

1) 確定柵欄形成區(qū)域

在投撒n個傳感器完畢后(n為某個整數(shù))，從縱坐標最大的節(jié)點開始(即最上方的節(jié)點，設(shè)為y1)，劃分區(qū)域的上邊界y=y1，將上邊界正下方2r處直線y=y1-2r作為區(qū)域的下邊界.依縱坐標從大至小的順序向下，以此類推，直至劃定完第n個區(qū)域.統(tǒng)計各個區(qū)間段內(nèi)的節(jié)點個數(shù)，選取節(jié)點個數(shù)最多的區(qū)間段作為第1條柵欄形成的預(yù)選區(qū)域.

2) 確定有向強柵欄的節(jié)點1

選出預(yù)選區(qū)域中橫坐標最小的節(jié)點.若其橫坐標大于半徑r，則先令其向左平行移動至橫坐標等于半徑，并用最少的轉(zhuǎn)動能耗調(diào)整其感知方向，使其在[π-α2,π+α2]之間；若其橫坐標小于半徑r，判斷扇形區(qū)域與左邊界x=0是否有公共點.若已有公共點，不進行轉(zhuǎn)動；若無公共點，選擇需要轉(zhuǎn)動角度較小的那個方向，轉(zhuǎn)至其扇形區(qū)域恰與左邊界x=0有一個公共點.該節(jié)點調(diào)度完畢后作為該條柵欄的節(jié)點1.

3) 確定節(jié)點2的目標位置并選擇節(jié)點運動

根據(jù)文獻[10]的定義1，判斷剩余節(jié)點中是否有節(jié)點在節(jié)點1扇形區(qū)域內(nèi)部.若有，選出扇形區(qū)域內(nèi)橫坐標最大的節(jié)點作為節(jié)點2，不進行移動,只將其按照式(1)調(diào)整方向角，并計算運動能耗.例如，在圖3(a)中，節(jié)點A為節(jié)點1，圓心為B的虛扇形為節(jié)點2的目標位置，圓心為B的節(jié)點主要轉(zhuǎn)動到虛線位置即成為構(gòu)建柵欄的節(jié)點2.

Fig. 3 Selection of the second node圖3 節(jié)點2的選擇

定理1. 在感知區(qū)域內(nèi)有1個節(jié)點的概率為P1=0.5γr2αe-0.5γr2α.

證畢.

若沒有節(jié)點在節(jié)點1扇形區(qū)域內(nèi)部，則將節(jié)點1扇形區(qū)域中橫坐標最大的點作為節(jié)點2需要移動的目標位置，若此目標位置超出整個區(qū)域，則認為此次選擇無效，重新將節(jié)點1自身的坐標作為節(jié)點2的目標位置.選定目標位置后，找出剩余所有節(jié)點中與目標位置之間歐氏距離最短的節(jié)點作為節(jié)點2，節(jié)點沿著最短路徑移動至目標位置，并按照式(1)調(diào)整方向角.例如，在圖3(b)中，節(jié)點A為節(jié)點1，圓心為B的虛扇形為節(jié)點2的目標位置，C為移動節(jié)點.

4) 以此確定其余所需節(jié)點的目標位置并選擇節(jié)點移動

在節(jié)點i(i≥2)調(diào)度完畢后，若在其感知區(qū)域內(nèi)部存在節(jié)點，橫坐標最大的節(jié)點就是第i+1個節(jié)點的目標位置.如果感知區(qū)域內(nèi)部沒有節(jié)點，則令節(jié)點i(i≥2)正右方向一個半徑距離處作為下一節(jié)點的坐標位置，然后選出剩余所有節(jié)點中與其歐氏距離最短的節(jié)點，將其沿最短路徑移動至與目標位置重合.有向節(jié)點的目標感知方向根據(jù)定義2和式(1)確定.形成柵欄的有向節(jié)點的移動距離越小，算法的效率越高.

下面的定理2 說明了節(jié)點的移動距離和密度的關(guān)系.

定理2. 節(jié)點移動到目標位置，移動距離為1 m的概率為P=(1-P1)e-γ πγπ.

證畢.

5) 根據(jù)右邊界位置確定形成第1條柵欄

6) 構(gòu)建其余K-1條柵欄

若K>1，從剩余的區(qū)域段中找出節(jié)點個數(shù)最多的區(qū)域段(之前參與形成柵欄的節(jié)點不再計入)，重復(fù)步驟2～5，形成第2條柵欄.同理，依次形成第3條、第4條、……、第K條柵欄，算法結(jié)束.

DBCNA算法的偽代碼如算法1所示：

算法1. DBCNA算法.

輸入:N,K,J1,J2;

輸出:K條柵欄、總能耗、平均能耗、最大能耗、柵欄節(jié)點數(shù).

For (每一條需構(gòu)建的柵欄)

選擇節(jié)點數(shù)目最大的區(qū)域作為柵欄分區(qū);

確定柵欄的第1個節(jié)點N1，坐標記作(x1,y1);

If (x1>r)

x1=r;

End If

End If

j=2;

While (柵欄右邊界未接觸區(qū)域右邊界)

If (在傳感器Nj-1的感知范圍內(nèi)存在其它傳感器)

Nj=Nj-1感知范圍內(nèi)X坐標最大的傳 感器;

Else

End If

j++;

End While

End For

計算總能耗、平均能耗、最大能耗、柵欄節(jié)點數(shù).

2.3 算法的特點分析

如何降低柵欄形成過程中的能耗，是柵欄構(gòu)建算法要重點考慮的問題.DBCNA算法通過以下措施降低能耗，高效構(gòu)建柵欄：

1) 選擇節(jié)點數(shù)最多、分布較為集中的區(qū)段作為柵欄的預(yù)選區(qū)域，這樣可以使得節(jié)點在參與調(diào)度形成柵欄的過程中盡可能地減少移動距離，降低能耗.

Fig. 4 Distribution of node圖4 節(jié)點分布圖

3) 如果處在目標位置的節(jié)點工作方向在[-α2,α2]之間，則節(jié)點的感知方向不調(diào)整，否則轉(zhuǎn)動盡量少的角度，調(diào)整為-α2，α2兩者之一，使節(jié)點沿柵欄方向有最大感知距離.

形成柵欄的節(jié)點集合中，只有節(jié)點1的坐標可能是下一個節(jié)點的目標位置,其余節(jié)點若扇形區(qū)域內(nèi)部沒有節(jié)點，則下一個節(jié)點的目標位置都在感知圓弧上，這是因為DBCNA算法把其余節(jié)點的感知方向都轉(zhuǎn)動到[-α2,α2]之間.

在柵欄形成的過程中，只要節(jié)點數(shù)量多于柵欄需要的節(jié)點數(shù)，即γLW≥βKLR，所以，只要節(jié)點密度，DBCNA算法就可以形成柵欄.β為經(jīng)驗參數(shù)，如圖4所示，一般取1.1.

在柵欄形成的過程中，可能會出現(xiàn)部分節(jié)點的感知區(qū)域超出監(jiān)測區(qū)域的情況.因此DBCNA算法要確保節(jié)點2的目標位置位于節(jié)點1監(jiān)測區(qū)域內(nèi)，從節(jié)點3開始，只要柵欄未形成完畢，目標位置一定處于監(jiān)測區(qū)域內(nèi)，即可保證柵欄形成過程的可連續(xù)性.

在柵欄形成過程中，設(shè)起始為n個節(jié)點，則需要先從n個節(jié)點中選中節(jié)點1，然后從n-1個節(jié)點中選出節(jié)點2，以此類推，直至柵欄形成完畢.因此在整體上，時間復(fù)雜度會隨著所需節(jié)點的增加而增加.最壞情況：在形成K條柵欄的過程中，若出現(xiàn)最壞情況，則形成K條柵欄用盡了投撒區(qū)域內(nèi)的全部n個節(jié)點.此時，時間復(fù)雜度為O(n2).

3 實驗結(jié)果與分析

本文運用Matlab 7.0對此算法進行仿真，區(qū)域大小為300 m×200 m.每組實驗數(shù)據(jù)采用重復(fù)50次獨立實驗取平均值的方式獲得.如果沒有特別指明，實驗的默認參數(shù)為K=2，r=10 m，a=π3，γ=0.006，J1=3.6Jm，J2=1.8Jπ.目前為止，最新的有向柵欄構(gòu)建算法研究是文獻[10]，我們選取了其中的Strong Optimal算法、Strong Greedy算法與本文中的DBCNA算法進行了仿真比較.主要的性能參數(shù)是：形成柵欄的總能耗、平均能耗、節(jié)點數(shù)、單節(jié)點的最大能耗、能耗標準差(如定義5).默認情況下取100次實驗的平均值.總能耗、平均能耗、能耗標準差越小，節(jié)點數(shù)越少，柵欄形成算法越高效，最大能耗越小，柵欄的壽命越長.

在默認參數(shù)下，給定相同的初始投撒結(jié)果，節(jié)點隨機分布如圖4(a)所示；DBCNA算法形成的柵欄如圖4(b)所示；Strong Optimal算法形成的柵欄如圖4(c)所示.DBCNA算法僅用60～70個節(jié)點就構(gòu)建了2條柵欄，而Strong Optimal算法需要用110～125個節(jié)點才能構(gòu)建2條柵欄，可見DBCNA算法顯著提高了效率.相比Strong Optimal算法，DBCNA算法顯著降低了需求的節(jié)點個數(shù)，可以用盡量少的節(jié)點達到同樣的柵欄覆蓋效果.而隨機部署的節(jié)點可能互相重疊，在Strong Optimal算法中，先根據(jù)節(jié)點分布情況選擇最佳的基準柵欄，基準柵欄中的節(jié)點不動，相鄰節(jié)點之間的空洞與周圍的移動節(jié)點形成最佳匹配，構(gòu)建柵欄.

Fig. 5 The effect of node density圖5 節(jié)點密度的影響

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

由于Strong Optimal算法、Strong Greedy算法對于節(jié)點數(shù)量的要求較高，在保證能形成柵欄的前提下，本文采用0.003作為起始節(jié)點密度進行仿真比較，其余實驗參數(shù)均為默認參數(shù).仿真結(jié)果如圖5所示.從圖5(a)中可以發(fā)現(xiàn)，隨著節(jié)點密度的增加，3種算法的總能耗均呈顯著性下降.從圖5(b)中可以發(fā)現(xiàn)，DBCNA算法形成柵欄所需的節(jié)點數(shù)明顯低于Strong Optimal算法與Strong Greedy算法形成柵欄所需的節(jié)點數(shù).從圖5(c)中可以發(fā)現(xiàn)，隨著節(jié)點密度的增加，3種算法相應(yīng)的平均能耗均呈顯著性下降，但DBCNA算法對應(yīng)的平均能耗始終明顯低于Strong Optimal算法與Strong Greedy算法對應(yīng)的平均能耗，大約降低了30%～40%.將圖5(b)和圖5(c)中的數(shù)據(jù)進行綜合比較可以得出結(jié)論：由于節(jié)點的平均能耗明顯比DBCNA算法中節(jié)點的平均能耗高，且形成柵欄所需的節(jié)點數(shù)明顯多于DBCNA算法中形成柵欄所需的節(jié)點數(shù)，導(dǎo)致參與調(diào)度過程的節(jié)點中有節(jié)點耗能極高的可能性進一步增加，而在柵欄中耗能最高的節(jié)點耗能的高低直接決定柵欄壽命的長短.因此在柵欄形成完畢后，按照DBCNA算法形成柵欄的壽命明顯高于按照Strong Optimal算法與Strong Greedy算法形成柵欄的壽命.圖5(d)和圖5(e)表明，節(jié)點的最大能耗與能耗標準差隨著密度的增大而降低，密度越大，算法的差距越小.這是由于密度增大，可選擇的移動節(jié)點增多，從而降低了最大能耗和能耗標準差.相比于Strong Optimal算法和Strong Greedy算法，DBCNA算法中節(jié)點的最大能耗、能耗標準差最大可降低32%，29%，這說明 DBCNA算法形成的柵欄壽命長、穩(wěn)定性好.

Fig. 6 The effect of K圖6 柵欄數(shù)K的影響

3.2 柵欄數(shù)的影響

柵欄數(shù)K的影響如圖6所示.從圖6(a)中可以看出，3種算法的節(jié)點總能耗均隨K的增大而增大，當K>3時，隨著K的增大，DBCNA算法的節(jié)點總能耗將越來越低于同等條件下Strong Optimal算法與Strong Greedy算法中的節(jié)點總能耗，當K=5時總能耗降低了25%左右.從圖6(b)可以看出，隨著K的增大，DBCNA算法形成柵欄所需的節(jié)點數(shù)隨K的增長率明顯低于同等條件下的Strong Optimal算法與Strong Greedy算法，當K不斷增大時DBCNA算法形成柵欄所需節(jié)點數(shù)將越來越少于同等條件下的Strong Optimal算法與Strong Greedy算法.圖6(c)表明，隨著K的增大，DBCNA算法的節(jié)點平均能耗的上升趨勢比Strong Optimal算法、Strong Greedy算法較為微弱，且上升幅度遠低于Strong Optimal算法與Strong Greedy算法在同等情況下的上升幅度.圖6(d)和圖6(e)表明，隨著K值的增大而緩慢增大，Strong Optimal算法和Strong Greedy算法的節(jié)點最大能耗都是指數(shù)增加的，而DBCNA算法的能耗標準差只是略有增加，基本保持不變.3種算法中，Strong Greedy算法的節(jié)點最大能耗增加幅度最大，DBCNA算法最小.這是因為隨著K值的增大，移動的節(jié)點增多，單節(jié)點的最大能耗也會相應(yīng)地增加，DBCNA算法局部選擇最優(yōu)的節(jié)點構(gòu)建柵欄，故能耗標準差相差不大.相比于Strong Optimal算法和Strong Greedy算法，DBCNA算法的節(jié)點最大能耗可分別降低 35%，60%，能耗標準差最大可降低37%，50%.這說明DBCNA算法形成的柵欄壽命長、穩(wěn)定性好.

Fig. 7 The effect of sensing angle圖7 感知角度的影響

3.3 傳感器感知角度的影響

由于傳感器的感知角度發(fā)生變化時，會使得節(jié)點位于傳感器扇形監(jiān)測區(qū)域的幾率發(fā)生變化.不同的傳感器感知角度影響效果如圖7所示.從圖7中可以看出，感知角度增大時，節(jié)點位于扇形區(qū)域內(nèi)部的幾率也隨之增大，導(dǎo)致形成柵欄所需的節(jié)點數(shù)也隨感知角度的增大而增大；當K>1時，由于受到K的放大影響，形成柵欄所需的節(jié)點數(shù)在感知角度增大時的漲幅也會得到一定程度的放大.圖7表明隨著感知角度的增大，由于節(jié)點位于扇形區(qū)域內(nèi)部的幾率增加，平均能耗呈明顯的下降趨勢，且發(fā)生波動的頻率與幅度不斷減小.圖7(d)和圖7(e)表明，節(jié)點的最大能耗、能耗標準差基本不受感知角度的影響.

仿真結(jié)果表明，DBCNA算法顯著降低了需求的節(jié)點個數(shù),可以用盡量少的節(jié)點達到同樣的柵欄覆蓋效果.在Strong Optimal算法中，先根據(jù)節(jié)點分布情況選擇最佳的節(jié)點構(gòu)建基準柵欄，相鄰節(jié)點之間的空洞與周圍的移動節(jié)點形成最佳匹配，移動節(jié)點移動到相應(yīng)的位置構(gòu)建有向柵欄.而在DBCNA算法中，后一個節(jié)點由前一個節(jié)點決定.DBCNA算法不僅考慮了節(jié)點的移動，也考慮了節(jié)點的轉(zhuǎn)動，減少了柵欄中節(jié)點之間的重疊面積.從而DBCNA算法結(jié)果要比Strong Optimal算法更優(yōu)，形成的柵欄壽命長，穩(wěn)定性好.

4 結(jié)束語

本文主要研究有向強柵欄覆蓋問題，提出DBCNA算法，利用相鄰節(jié)點之間的關(guān)系，按照從左到右的節(jié)點順序，依次確定每一個節(jié)點的目標位置，前一個節(jié)點確定后一個節(jié)點的目標位置，并從附近節(jié)點中選擇運動能耗最少的節(jié)點運動到目標位置，節(jié)點的目標感知方向由預(yù)定的移動節(jié)點決定，從而分布式構(gòu)建有向強柵欄.仿真結(jié)果證明DBCNA算法可以用較少的節(jié)點高效節(jié)能地構(gòu)建有向K-柵欄覆蓋.

概率感知模型更符合實際情景，如何節(jié)能高效地構(gòu)建概率柵欄是下一步要研究的內(nèi)容.

[1]Tao Dan, Wu Tinyu. A survey on barrier coverage problem in directional sensor networks[J]. IEEE Sensors Journal, 2015, 15(2): 876-885

[2]Ban Dongsong, Wen Jun, Jiang Jie, et al. Constructingk-barrier coverage in mobile wireless sensor networks[J]．Journal of Software, 2011, 22(9): 2089-2103 (in Chinese)(班冬松, 溫俊, 蔣杰, 等. 移動無線傳感器網(wǎng)絡(luò)k-柵欄覆蓋的構(gòu)建算法[J]. 軟件學(xué)報, 2011, 22(9): 2089-2103)

[3]Wang Zhibo, Chen Honglong, Cao Qing, et al. Fault tolerant barrier coverage in wireless sensor networks[C]Proc of IEEE INFOCOM 2014. Piscataway, NJ: IEEE, 2014: 1869-1877

[4]He Shibo, Chen Jiming, Li Xu, et al. Cost-effective barrier coverage by mobile sensor networks[C]Proc of IEEE INFOCOM 2012. Piscataway, NJ: IEEE, 2012: 819-827

[5]Saipulla B Y, Liu G L, Xing X W, et al. Barrier coverage with sensors of limited mobility[C]Proc of ACM MobiHoc 2010. New York: ACM, 2010: 201-210

[6]Ma Huadong, Yang Meng, Li Deying, et al. Minimum camera barrier coverage in wireless camera sensor networks[C]Proc of IEEE INFOCOM 2012. Piscataway, NJ: IEEE, 2012: 217-225

[7]Zhang Li, Tang Jian, Zhang Weiyi. Strong barrier coverage with directional sensors[C]Proc of IEEE GlobeCom 2012. Piscataway, NJ: IEEE, 2009: 1-6

[8]Wang Yi, Cao Guohong. Barrier coverage in camera sensor networks[C]Proc of ACM MobiHoc 2011. New York: ACM, 2011: 3967-3974

[9]Wang Zhibo, Liao Jilong, Cao Qing, et al. Barrier coverage in hybrid directional sensor networks[C]Proc of IEEE MASS 2013. Piscataway, NJ: IEEE, 2013: 222-230

[10]Wang Zhibo, Liao Jilong, Cao Qing, et al. Achievingk-barrier coverage in hybrid directional sensor networks[J]. IEEE Trans on Mobile Computing, 2014, 13(7): 1443-1455

[11]Shih K P, Chou C M, Liu I H, et al, On barrier coverage in wireless camera sensor networks[C]Proc of the 24th IEEE ATMA. Piscataway, NJ: IEEE, 2010: 873-879

[12]Tao Dan, Chen Houjin. Strong barrier coverage detection algorithm for directional field of view sensor networks[J]. Journal of Beijing Jiaotong University, 2010, 35(5): 8-11 (in Chinese)(陶丹, 陳后金. 視角受限傳感器網(wǎng)絡(luò)強柵欄覆蓋判定算法[J]. 北京交通大學(xué)學(xué)報， 2010, 35(5): 8-11)

[13]Zhang Qingchen, Chen Zhihui. A weighted kernel possibilistic c-means algorithm based on cloud computing for clustering big data[J]. International Journal of Communication Systems, 2014, 27(9): 1378-1391

[14]Wang Chao, Fan Xinggang, Wang Heng, et al. An effective realization scheme for strong K-barrier coverage in WSN[J]. Chinese Journal of Sensors and Actuators, 2015, 28(2): 227-233 (in Chinese)(王超, 范興剛, 王恒, 等. 一種高效強K-柵欄覆蓋構(gòu)建算法[J]. 傳感技術(shù)學(xué)報, 2015, 28(2): 227-233)

[15]Guvensan M A, Yavuz A G. Hybrid movement strategy in self-orienting directional sensor networks[J]. Ad Hoc Networks, 2013, 11(3): 1075-1090

Fan Xinggang, born in 1974. Associate professor and PhD. His main research interests include wireless sensor networks, parallel computing and machine learning.

Ren Yongmo, born in 1994. Undergraduate. His main research interests include wireless sensor networks.

Che Zhicong, born in 1995. Undergraduate. His main research interests include wireless sensor networks.

Wang Chao, born in 1993. Undergraduate. His main research interests include wireless sensor networks.

A Distributed Directional Barrier Construction Scheme Based on Neighbor Sport

Fan Xinggang, Ren Yongmo, Che Zhicong, and Wang Chao

(CollegeofComputerScienceandTechnology,ZhejiangUniversityofTechnology,Hangzhou310023)

K-barrier coverage is one of the hotspots in directional sensor network. However, there are few directional barrier construction schemes considering both movement and rotation until now. This paper proposes a distributed directional strong barrier construction based on neighbor actuation (DBCNA) to create directional barrier coverage with minimum actuation energy consumption, which is the total of mobility and motility energy consumption. It is just the preceding node that determines the target node location of the next node. If there is a node in the sensing region of the preceding node, the node with the largestXcoordinate is selected as the next node. If not, the point sensing radius distance from the preceding node in the horizontal direction is selected as the target location of the next node in barrier, of which the target working direction is determined by its original working direction. If this original sensing direction is in [α2,π] (αis the sensing angle), the target working direction of node isβ=α2. On the contrary, if this original sensing direction is in [π,2π-α2], the target working direction of node isβ=2π-α2. This paper also first adopts the maximum energy consumption of a single node and the mean square error of energy consumption to evaluate the performance besides energy consumption. Simulation results show this method can save 50% nodes and decrease 40%-50% mean energy consumption than other methods. This research has important theoretical and practical significance.

directional barrier coverage; target location; working direction; next node; actuation energy consumption

2015-06-09；

2016-02-16

國家自然科學(xué)基金項目(40241461,11405145) This work was supported by the National Natural Science Foundation of China(40241461, 11405145).

TP391