一種高效的有向柵欄修補算法*

王森一,范興剛,王友好,陳 偉

(浙江工業(yè)大學計算機科學與技術學院,杭州 310023)

有向傳感器,如視頻傳感器,紅外傳感器,超聲波傳感器等,在諸多領域有著廣泛的應用,如可將傳感器節(jié)點部署在重要管道沿線以監(jiān)視針對管道的破壞活動,或者部署在敵營周邊監(jiān)視敵方的兵力部署和武器配備情況等。在上述列舉的應用中,有向傳感器節(jié)點被部署于寬度小于感知半徑的狹長的帶狀區(qū)域內(nèi),對監(jiān)控區(qū)域的移動目標進行檢測,這種技術被稱為柵欄覆蓋,柵欄覆蓋是有向傳感網(wǎng)絡一個研究熱點[1-4]。

許多學者致力于有向柵欄覆蓋構建的研究。Ssu等人[5]選擇靜態(tài)節(jié)點組建柵欄,初始節(jié)點選擇最優(yōu)的中繼節(jié)點向左右兩個方向延伸柵欄,直到邊界。陶丹等人[6]提出一種用最少的轉動角度實現(xiàn)強1-有向柵欄的方法。王林等人[7]采用圖論找到最小旋轉角度強柵欄覆蓋路徑,再通過貪婪算法尋找連接路徑形成柵欄。Cheng等人[8]提出D-TrBR算法,利用節(jié)點的轉動能力,分布式構建柵欄。該算法選擇具有最大柵欄貢獻的轉動節(jié)點,選擇轉動能耗最小的轉動方向,有效構建有向柵欄覆蓋。該算法充分利用節(jié)點的轉動能力有效構建柵欄。以上是利用節(jié)點的轉動能力構建柵欄,在利用節(jié)點的移動能力構建柵欄方面,Wang等人[9]研究了混合有向網(wǎng)絡的柵欄覆蓋,根據(jù)靜態(tài)節(jié)點之間的距離構建權重柵欄圖WBG,再運用頂點不相交的路徑算法選擇K-柵欄路徑,后才用匈牙利算法選擇最優(yōu)節(jié)點連接,行成柵欄。此算法利用圖論的方法找到移動距離最小的節(jié)點構建柵欄,但是該算法的復雜度高,耗費時間長。根據(jù)節(jié)點之間的鄰居關系,范興剛等人[10-11]選擇能耗最少的節(jié)點分布式構建有向強柵欄,此算法中,單個節(jié)點的最大貢獻也只是感知半徑,都沒有考慮感知角度較大時,如何利用增大的感知區(qū)域構建柵欄。為了充分利用節(jié)點的轉動能力和運動能力,車志聰?shù)热薣12]提出一種基于目標圓的分布式有向強柵欄構建方法。為了利用最少的節(jié)點構建柵欄,范興剛等人[13]提出基于有向節(jié)點選擇框的有向強K-柵欄覆蓋構建算法DSBCSB。這些算法可以有效構建柵欄,Tian等人[14-15]研究了如何延長柵欄壽命,先構建多條柵欄,再周期輪換調度柵欄,多條柵欄輪流工作,來延長網(wǎng)絡壽命。

以上這些創(chuàng)造性的工作,都沒有考慮柵欄空洞問題。如圖1,節(jié)點A、B、C組成有向柵欄,在運行過程中,節(jié)點C因能量耗盡而死亡,導致柵欄出現(xiàn)空洞。柵欄空洞降低柵欄覆蓋質量。如果廢棄整條柵欄,又會浪費能量。本文研究柵欄空洞的性質,利用周圍鄰居節(jié)點對其進行能量高效的分布式修補,從而提高柵欄覆蓋質量,延長網(wǎng)絡壽命。

圖1 柵欄空洞

本文余下章節(jié)安排如下:第1節(jié)描述網(wǎng)絡模型。第2節(jié)詳細介紹柵欄空洞修補的理論分析。第3節(jié)詳細介紹柵欄空洞修補算法。第4節(jié)通過仿真實驗對提出的算法進行性能評估。第5節(jié)總結全文并介紹下一步工作。

1 相關模型和定義

[13],有向傳感器節(jié)點方向可調感知模型可以采取四元組表示,其中P=(x,y)表示節(jié)點的位置坐標,r表示節(jié)點的感知半徑,β表示節(jié)點的感知方向,為相對于x正半軸的方向角,取值范圍為0≤β≤2π。α表示節(jié)點的感知角度。

有向柵欄是滿足以下要求的一個節(jié)點集合:①集合只有一個起始節(jié)點和一個終止節(jié)點;②起始節(jié)點與監(jiān)控區(qū)域左邊界至少有一個交點,終止節(jié)點與監(jiān)控區(qū)域右邊界至少一個交點;③起始節(jié)點終止節(jié)點只與一個節(jié)點相連;④除了這兩個節(jié)點之外,其余的節(jié)點都與兩個節(jié)點相連,一個是它的父節(jié)點,一個是它的中繼節(jié)點(也稱子節(jié)點)。

研究有向柵欄修補問題之前,有如下假設:

①節(jié)點可以轉動到任意方向,也可以移動。所有節(jié)點的轉動能耗和移動功耗均相同,單個傳感器節(jié)點每轉動180°耗能為1.8 J,每移動1 m耗能為3.6 J。

②柵欄中,所有節(jié)點的監(jiān)控能耗相等。

③入侵者隨機進入監(jiān)控區(qū)域,在其入侵路徑上的柵欄節(jié)點消耗能量。如圖1所示,入侵者進入節(jié)點A、B和C組成的柵欄時,只有節(jié)點C消耗能量。

定義1柵欄空洞 節(jié)點覆蓋區(qū)域由無數(shù)個覆蓋點組成,一個柵欄死亡節(jié)點的父節(jié)點覆蓋區(qū)域內(nèi)的覆蓋點與其子節(jié)點覆蓋區(qū)域內(nèi)覆蓋點的最短距離就是柵欄空洞。

定義2轉動修補區(qū)域 柵欄空洞

定義3有向節(jié)點運動能耗 有向節(jié)點運動能耗由移動能耗和轉動能耗組成。移動能耗是指有向移動節(jié)點運動到目標位置的能耗,轉動能耗是指節(jié)點轉動到目標感知方向的能耗。

定義4柵欄壽命 從柵欄形成時刻算起,到出現(xiàn)柵欄節(jié)點死亡,且這個死亡節(jié)點形成的空洞不再被修補為止,這段時間稱為柵欄壽命。

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

我們研究的問題就是:針對柵欄運行過程中可能出現(xiàn)的有向柵欄空洞,如何分布式地找到轉動修補區(qū)域,調度移動節(jié)點,以最少的運動能耗修補有向柵欄空洞。

2 理論分析

2.1 轉動修補區(qū)域

圖2 修補過程

定理以柵欄空洞的端點為圓心,r為半徑的兩圓相交區(qū)域,和兩個三角形外接圓區(qū)域的差(也就是圖2(a)中陰影區(qū)域)即為轉動修補區(qū)域。

總之,在這個陰影區(qū)域內(nèi)任意節(jié)點,到柵欄空洞兩個端點的距離小于節(jié)點感知半徑,與這個空洞兩端形成的角度小于感知角度。根據(jù)扇形的幾何性質,這個節(jié)點只要經(jīng)過旋轉,一定可以完全修補柵欄空洞。證畢

轉動修補區(qū)域內(nèi)的任意一個節(jié)點,不需要移動,只需要轉到就可以形成柵欄。轉動修補區(qū)域外的節(jié)點,則需要移動和轉動才能完成柵欄修補。如圖2(b)中的節(jié)點S只需要轉動就可以修補柵欄,而節(jié)點R需要移動到點L,再轉動才能修補柵欄。

當感知角度不變時,轉動修補區(qū)域隨著臨近死亡節(jié)點的父節(jié)點和子節(jié)點之間的距離的增大而減少,當這個距離等于r時,轉動修補區(qū)域變成兩個端點(如圖2(c)所示)。

2.2 節(jié)點的修補目標位置和目標方向

根據(jù)上面的定理,轉動修補區(qū)域內(nèi)的節(jié)點,不需要移動,只要轉動就可以修補柵欄空洞,因此其修補時的目標位置就是其初始位置。如圖2(b)中的節(jié)點S的目標位置就是其初始位置。對于轉動修補區(qū)域外部的節(jié)點,目標位置在轉動修補區(qū)域上。如圖2(b)中的節(jié)點R,它的目標位置為點L,它移動到點L,再經(jīng)過轉動就可修補柵欄空洞。

對于目標位置在轉動修補區(qū)域內(nèi)的節(jié)點,設其與左端點的連線方向角為θl,與右端點的連線方向角為θr。如圖2(b)中的點L,θl、θr分別為LB、LD的方向角。圖2(b)黑色的虛扇形表示節(jié)點感知方向為θr+α/2,扇形區(qū)域的一條邊與LD重合,另一條邊在LB的左側。圖2(b)黑色的虛扇形節(jié)點感知方向為θl-α/2,扇形區(qū)域的一條邊與LB重合,另一條邊在LD的右側。節(jié)點可以順時針或者逆時針旋轉,兩個可能的感知方向中,能耗較少的轉動方向為實際轉動方向。

綜合起來,節(jié)點修補目標位置位于柵欄空洞BD下方時,目標方向可用式(1)計算。如果位于上方,節(jié)點的目標感知方向為式(2)。

(1)

(2)

(3)

(4)

2.3 修補能耗

節(jié)點轉動能耗如式(5)所示,總能耗為轉動能耗和移動能耗之和,如式(6)所示,其中,dnin為節(jié)點與目標位置的直線距離,如圖2(b)所示,dnin表示節(jié)點R的初始位置與目標位置L的歐式距離。

Er=|βt-β|*Jr

(5)

(6)

2.4 柵欄壽命

假設一條柵欄由Nb個節(jié)點組成,第i個節(jié)點的能量為Ei,柵欄節(jié)點的單位能耗為em,柵欄初始壽命如式(7)所示。

(7)

3 基于轉動修補區(qū)域的高效的有向柵欄修補算法

3.1 算法的基本思想

要修補柵欄空洞,移動節(jié)點可以移動到死亡節(jié)點的原位置,轉動到原感知方向修補柵欄。這個方法簡單直觀,但可能會導致較大的能耗。為了充分利用節(jié)點的轉動能力高效修補柵欄,先根據(jù)幾何知識,找到柵欄空洞的轉動修補區(qū)域,確定周圍移動節(jié)點修補空洞的目標位置和目標方向;再選擇能耗最少的節(jié)點移動到目標位置,從而有效修補有向柵欄,這樣的修補過程稱為基于轉動修補區(qū)域的高效柵欄修補算法EBarR(Effective Barrier repairing scheme based RRR)。

3.2 算法具體過程

為了描述方便,采用表1所示的變量,算法偽代碼如圖3所示。

表1 變量及意義

圖3 算法偽代碼

柵欄修補算法EBarR的基本步驟如下:

Step 1 計算柵欄壽命

按照式(7),計算柵欄壽命。

Step 2 找到柵欄空洞

Step 3 確定轉動修補區(qū)域。

如果d

Step 3.1 確定節(jié)點目標位置

對于轉動修補區(qū)域內(nèi)部節(jié)點,其目標位置就是本身初始位置,對于外部節(jié)點,其目標位置仍在轉動修補區(qū)域,而且移動距離最小。如圖2(b)所示,節(jié)點R的目標位置為轉動修補區(qū)域上的位置L。

Step 3.2 確定節(jié)點目標方向

計算移動節(jié)點目標位置與左端點的連線方向角θl,與右端點的連線方向角θr。并根據(jù)式(1)或者式(2)確定目標方向。

Step 3.3 確定節(jié)點能耗

按照式(5)計算節(jié)點的轉動能耗,按照式(6)確定節(jié)點的總能耗。

Step 3.4 確定修補節(jié)點

總能耗最少的節(jié)點修補柵欄。

Step 4 只有兩個目標位置時

如果d=r,兩個端點就是修補節(jié)點的目標位置按照式(3)、式(4)確定目標方向,確定其運動修補能耗,選擇運動修補能耗最少的節(jié)點移動到相應的目標位置,轉動到相應的目標方向,修補柵欄。

Step 5 直接由父節(jié)點選擇修補節(jié)點

如果d>r,先由父節(jié)點選擇中繼節(jié)點組建柵欄,再回到Step 2。

Step 6 輸出結果

柵欄修補運行后,按照式(7)計算修補后的柵欄壽命,計算修補總能耗,平均能耗,最大能耗,輸出結果。

3.3 算法的復雜度分析

假設柵欄空洞的個數(shù)為H,冗余移動節(jié)點的數(shù)目為O(Nm+2),分布式修補策略時間復雜度為O(H*Nm)。臨近死亡節(jié)點需要廣播覆蓋空洞,移動節(jié)點都要廣播自己的優(yōu)先級結果,所以通信復雜度為O(Nm+1)。

4 仿真結果

本文運用MATLAB 7.0對此算法進行仿真,每組實驗數(shù)據(jù)采用重復500次獨立實驗取平均值的方式獲得。如果沒有特別指明,實驗的默認參數(shù)如表2所示。當修補節(jié)點數(shù)量達到Nr時,算法停止運行。

表2 實驗參數(shù)

4.1 柵欄修補實現(xiàn)

在默認參數(shù)下,柵欄修補結果如圖4所示。初始柵欄如圖4(a)所示,經(jīng)過一段時間運行,出現(xiàn)的柵欄空洞如圖4(b)所示。圖4(c)表示采用EBarR算法進行修補后的結果。藍色節(jié)點組成初始柵欄,15個綠色扇形是修補節(jié)點的初始位置,15個紅色扇形是節(jié)點修補柵欄后的位置,其中,7個轉動修補,8個移動加轉動修補。圖4表明,EBarR算法可以有效修補柵欄空洞。

圖4 柵欄修補結果

4.2 節(jié)點密度影響

在不同節(jié)點密度下,運用NSDBC算法[10]生成有向柵欄,入侵者隨機進入感興趣區(qū)域。入侵者路徑上的節(jié)點產(chǎn)生數(shù)據(jù),傳輸數(shù)據(jù),消耗5 J的能量。節(jié)點初始能量為100 J,節(jié)點剩余能量小于10 J為臨近死亡節(jié)點,需要對其產(chǎn)生的空洞進行修補。修補節(jié)點數(shù)達到15時的能耗和壽命如圖5～圖8所示。其中,“10,EBarR算法”表示節(jié)點半徑為10,采用EBarR算法對產(chǎn)生的空洞進行修補。

圖5 節(jié)點密度VS節(jié)點總能耗

圖6 節(jié)點密度VS節(jié)點平均能耗

圖7 節(jié)點密度VS節(jié)點最大能耗

圖8 節(jié)點密度VS柵欄壽命

由于隨著密度的增加,轉動修補區(qū)域的節(jié)點數(shù)量增加,僅通過轉動就可以柵欄空洞的節(jié)點數(shù)量增加,原來需要通過移動修補的柵欄空洞只需要轉動就可以得到修補,使得修補能耗下降,導致修補總能耗隨著節(jié)點密度的增加而減少,而柵欄壽命隨著節(jié)點密度的增加而加大。隨著節(jié)點半徑的增加,節(jié)點感知區(qū)域增大,轉動修補區(qū)域相應增大,原來需要移動才能修補的節(jié)點變成僅靠轉動就可以修補柵欄空洞,降低了修補能耗。因此,隨著節(jié)點半徑的增加,節(jié)點修補總能耗也在下降。由于節(jié)點要通過移動才有可能到達臨近死亡節(jié)點的原位置,而在EBarR算法中,這些節(jié)點很有可能只需要調整感知方向,就可以修補柵欄。因此,EBarR算法要比移動到原位置的修補算法節(jié)省能量,降低修補總能耗。

由于修補增加了柵欄節(jié)點,使得柵欄中最低能量節(jié)點變成了能量較大的節(jié)點。相比與原柵欄,修補后的柵欄壽命顯著增大。由于EBarR算法盡可能利用節(jié)點的轉動能力修補柵欄,有效降低了修補能耗。采用EBarR算法修補后的柵欄壽命要大于移動到原位置修補的柵欄壽命。

4.3 修補節(jié)點數(shù)的影響

修補節(jié)點數(shù)是指修補節(jié)點的數(shù)量,其影響如圖9 所示。結果表明,修補后的柵欄壽命顯著增加,因為柵欄修補以后,柵欄中能量最小的節(jié)點及時得到補償,根據(jù)式(7),柵欄壽命也相應增加。如果原來柵欄里的節(jié)點按照能量大小排序,小的在前,大的在后。由于柵欄壽命是由柵欄中能量最小的節(jié)點決定,Nr個柵欄節(jié)點被替換后,網(wǎng)絡壽命由原來柵欄里第Nr+1個節(jié)點決定。所以修補節(jié)點數(shù)量越多,柵欄壽命越大。由于隨著修補節(jié)點數(shù)的增加,移動到臨近死亡節(jié)點的原位置的節(jié)點數(shù)相應增加,而這些節(jié)點很有可能只要轉動感知方向,就可以修補柵欄。因此,EBarR算法要比移動到原位置的修補算法節(jié)省能量,從而增加網(wǎng)絡壽命。

圖9 修補節(jié)點數(shù)VS柵欄壽命

圖10 感知角度VS柵欄壽命

4.4 感知角度的影響

感知角度的影響如圖10所示。仿真結果表明,隨著感知角度的增大,柵欄壽命變化不大。這是因為雖然隨著感知角度的增大,轉動修補區(qū)域變大,導致修補能耗降低。但它的剩余能量要比其他節(jié)點能量多。而且柵欄壽命柵欄由能量最小的節(jié)點決定,與剩余能量較多的修補節(jié)點無關。

4.5 與傳統(tǒng)方法的比較

[15],先生成2條柵欄,兩條柵欄周期輪換工作稱為SCAN算法。同樣條件下,生成一條柵欄,按照EBarR算法對柵欄進行修補。

同樣分布60個節(jié)點,一邊形成兩條柵欄(一條30個)。一邊形成一條柵欄(30個節(jié)點)再用剩余節(jié)點(30個)按EBarR算法修補柵欄。柵欄壽命結果如圖11所示。仿真結果表明,相比SCAN算法,EBarR修補算法有效增加了網(wǎng)絡壽命。

這是因為,在修補過程中,一旦有節(jié)點剩余能量過低就會有另外一個節(jié)點來修補替換它,而且EBarR修補算法盡量采用節(jié)點的轉動能力,修補能耗較少。

圖11 不同算法VS柵欄壽命

5 結論

本文主要研究有向強柵欄修補問題,提出EBarR修補算法,利用節(jié)點之間的鄰居關系,找到柵欄空洞;構造柵欄空洞的虛擬圓和外接圓,找到轉動修補區(qū)域;確定修補目標位置和目標感知方向,分布式選擇能耗最小節(jié)點修補柵欄空洞,延長網(wǎng)絡壽命。仿真結果證明,EBarR修補算法可以節(jié)能高效地修補有向柵欄空洞,延長柵欄壽命。

本文只對長方形區(qū)域的有向柵欄修補進行了研究,環(huán)形、直線型區(qū)域的柵欄如何修補下一步要研究的內(nèi)容之一。概率感知模型是更符合實際的感知模

型,如何節(jié)能高效地構建和維護概率柵欄也是下一步要研究的內(nèi)容。

[1] Tao D,Wu T. A Survey on Barrier Coverage Problem in Directional Sensor Networks[J]. IEEE Sensors Journal,2015,15(2):876-885.

[2] K Wu F,Gui Y,Wang Z B,et al. A Survey on Barrier Coverage with Sensors[J]. Frontiers of Computer Science,2016,10(6):968-984.

[3] 陶丹,馬華東. 有向傳感器網(wǎng)絡覆蓋控制算法[J]. 軟件學報,2011,22(10):2315-2332.

[4] 李靖,王汝傳,黃海平,等. 有向傳感器網(wǎng)絡覆蓋控制策略[J]. 通信學報,2011,32(8):118-127.

[5] Ssu K F,Wang W T,F K W,et al.K-Barrier Coverage with a Directional Sensing Model[J]. International Journal on Smart Sensing and Intelligent Systems,2009,2(1):75-93.

[6] Tao D,Tang S J,Zhang H T,et al. Strong Barrier Coverage in Directional Sensor Networks[J]Computer Communications,2012,35(8):895-905.

[7] 王林,劉文遠,王琳,等. 基于有向傳感器網(wǎng)絡的強柵欄覆蓋優(yōu)化策略[J]. 小型微型計算機系統(tǒng),2014,35(4):740-745.

[8] 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.

[9] Wang Z B,Liao J L,Cao Q,et al. Achievingk-Barrier Coverage in Hybrid Directional Sensor Networks[J]. IEEE Transactions on Mobile Computing,2014,13(7):1443-1455.

[10] 范興剛,任勇默. 一種基于鄰居節(jié)點運動的分布式有向強柵欄構建算法[J]. 計算機研究與發(fā)展,2017,54(1):221-231.

[11] 任勇默,范興剛. 一種有向傳感器網(wǎng)絡柵欄覆蓋增強算法[J]. 傳感技術學報,2015,28(7):1051-1057.

[12] 車志聰,范興剛. 一種基于目標圓的有向強柵欄構建算法[J]. 傳感技術學報,2016,29(3):390-396.

[13] 范興剛,王超. 一種基于選擇框的有向K-柵欄構建算法[J]. 計算機學報,2016,39(5):946-960.

[14] Tian J,Zhang W,Wang G. Duty-Cycle Scheduling for Intruder Detection in Wireless Sensor Networks[J]. Group,the Conference of PDCS,2012:22-29.

[15] Tian J,Zhang W,Wang G,et al. 2Dk-Barrier Duty-Cycle Scheduling for Intruder Detection in Wireless Sensor Networks[J]. Computer Communications,2014,4(3):31-42.