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

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

有向傳感器,如視頻傳感器,紅外傳感器,超聲波傳感器等,在諸多領(lǐng)域有著廣泛的應(yīng)用,如可將傳感器節(jié)點(diǎn)部署在重要管道沿線以監(jiān)視針對(duì)管道的破壞活動(dòng),或者部署在敵營(yíng)周邊監(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ǎng)絡(luò)一個(gè)研究熱點(diǎn)[1-4]。

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

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

圖1 柵欄空洞

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

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

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

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

研究有向柵欄修補(bǔ)問題之前,有如下假設(shè):

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

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

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

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

定義2轉(zhuǎn)動(dòng)修補(bǔ)區(qū)域 柵欄空洞

定義3有向節(jié)點(diǎn)運(yùn)動(dòng)能耗 有向節(jié)點(diǎn)運(yùn)動(dòng)能耗由移動(dòng)能耗和轉(zhuǎn)動(dòng)能耗組成。移動(dòng)能耗是指有向移動(dòng)節(jié)點(diǎn)運(yùn)動(dòng)到目標(biāo)位置的能耗,轉(zhuǎn)動(dòng)能耗是指節(jié)點(diǎn)轉(zhuǎn)動(dòng)到目標(biāo)感知方向的能耗。

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

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

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

2 理論分析

2.1 轉(zhuǎn)動(dòng)修補(bǔ)區(qū)域

圖2 修補(bǔ)過程

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

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

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

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

2.2 節(jié)點(diǎn)的修補(bǔ)目標(biāo)位置和目標(biāo)方向

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

對(duì)于目標(biāo)位置在轉(zhuǎn)動(dòng)修補(bǔ)區(qū)域內(nèi)的節(jié)點(diǎn),設(shè)其與左端點(diǎn)的連線方向角為θl,與右端點(diǎn)的連線方向角為θr。如圖2(b)中的點(diǎn)L,θl、θr分別為L(zhǎng)B、LD的方向角。圖2(b)黑色的虛扇形表示節(jié)點(diǎn)感知方向?yàn)棣萺+α/2,扇形區(qū)域的一條邊與LD重合,另一條邊在LB的左側(cè)。圖2(b)黑色的虛扇形節(jié)點(diǎn)感知方向?yàn)棣萳-α/2,扇形區(qū)域的一條邊與LB重合,另一條邊在LD的右側(cè)。節(jié)點(diǎn)可以順時(shí)針或者逆時(shí)針旋轉(zhuǎn),兩個(gè)可能的感知方向中,能耗較少的轉(zhuǎn)動(dòng)方向?yàn)閷?shí)際轉(zhuǎn)動(dòng)方向。

綜合起來,節(jié)點(diǎn)修補(bǔ)目標(biāo)位置位于柵欄空洞BD下方時(shí),目標(biāo)方向可用式(1)計(jì)算。如果位于上方,節(jié)點(diǎn)的目標(biāo)感知方向?yàn)槭?2)。

(1)

(2)

(3)

(4)

2.3 修補(bǔ)能耗

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

Er=|βt-β|*Jr

(5)

(6)

2.4 柵欄壽命

假設(shè)一條柵欄由Nb個(gè)節(jié)點(diǎn)組成,第i個(gè)節(jié)點(diǎn)的能量為Ei,柵欄節(jié)點(diǎn)的單位能耗為em,柵欄初始?jí)勖缡?7)所示。

(7)

3 基于轉(zhuǎn)動(dòng)修補(bǔ)區(qū)域的高效的有向柵欄修補(bǔ)算法

3.1 算法的基本思想

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

3.2 算法具體過程

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

表1 變量及意義

圖3 算法偽代碼

柵欄修補(bǔ)算法EBarR的基本步驟如下:

Step 1 計(jì)算柵欄壽命

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

Step 2 找到柵欄空洞

Step 3 確定轉(zhuǎn)動(dòng)修補(bǔ)區(qū)域。

如果d

Step 3.1 確定節(jié)點(diǎn)目標(biāo)位置

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

Step 3.2 確定節(jié)點(diǎn)目標(biāo)方向

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

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

按照式(5)計(jì)算節(jié)點(diǎn)的轉(zhuǎn)動(dòng)能耗,按照式(6)確定節(jié)點(diǎn)的總能耗。

Step 3.4 確定修補(bǔ)節(jié)點(diǎn)

總能耗最少的節(jié)點(diǎn)修補(bǔ)柵欄。

Step 4 只有兩個(gè)目標(biāo)位置時(shí)

如果d=r,兩個(gè)端點(diǎn)就是修補(bǔ)節(jié)點(diǎn)的目標(biāo)位置按照式(3)、式(4)確定目標(biāo)方向,確定其運(yùn)動(dòng)修補(bǔ)能耗,選擇運(yùn)動(dòng)修補(bǔ)能耗最少的節(jié)點(diǎn)移動(dòng)到相應(yīng)的目標(biāo)位置,轉(zhuǎn)動(dòng)到相應(yīng)的目標(biāo)方向,修補(bǔ)柵欄。

Step 5 直接由父節(jié)點(diǎn)選擇修補(bǔ)節(jié)點(diǎn)

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

Step 6 輸出結(jié)果

柵欄修補(bǔ)運(yùn)行后,按照式(7)計(jì)算修補(bǔ)后的柵欄壽命,計(jì)算修補(bǔ)總能耗,平均能耗,最大能耗,輸出結(jié)果。

3.3 算法的復(fù)雜度分析

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

4 仿真結(jié)果

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

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

4.1 柵欄修補(bǔ)實(shí)現(xiàn)

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

圖4 柵欄修補(bǔ)結(jié)果

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

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

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

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

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

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

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

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

4.3 修補(bǔ)節(jié)點(diǎn)數(shù)的影響

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

圖9 修補(bǔ)節(jié)點(diǎn)數(shù)VS柵欄壽命

圖10 感知角度VS柵欄壽命

4.4 感知角度的影響

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

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

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

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

這是因?yàn)?在修補(bǔ)過程中,一旦有節(jié)點(diǎn)剩余能量過低就會(huì)有另外一個(gè)節(jié)點(diǎn)來修補(bǔ)替換它,而且EBarR修補(bǔ)算法盡量采用節(jié)點(diǎn)的轉(zhuǎn)動(dòng)能力,修補(bǔ)能耗較少。

圖11 不同算法VS柵欄壽命

5 結(jié)論

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

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

型,如何節(jié)能高效地構(gòu)建和維護(hù)概率柵欄也是下一步要研究的內(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)絡(luò)覆蓋控制算法[J]. 軟件學(xué)報(bào),2011,22(10):2315-2332.

[4] 李靖,王汝傳,黃海平,等. 有向傳感器網(wǎng)絡(luò)覆蓋控制策略[J]. 通信學(xué)報(bào),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] 王林,劉文遠(yuǎn),王琳,等. 基于有向傳感器網(wǎng)絡(luò)的強(qiáng)柵欄覆蓋優(yōu)化策略[J]. 小型微型計(jì)算機(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é)點(diǎn)運(yùn)動(dòng)的分布式有向強(qiáng)柵欄構(gòu)建算法[J]. 計(jì)算機(jī)研究與發(fā)展,2017,54(1):221-231.

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

[12] 車志聰,范興剛. 一種基于目標(biāo)圓的有向強(qiáng)柵欄構(gòu)建算法[J]. 傳感技術(shù)學(xué)報(bào),2016,29(3):390-396.

[13] 范興剛,王超. 一種基于選擇框的有向K-柵欄構(gòu)建算法[J]. 計(jì)算機(jī)學(xué)報(bào),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.