一種有向傳感器網(wǎng)絡(luò)柵欄覆蓋增強(qiáng)算法*

任勇默，范興剛，車志聰，王 超

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

一種有向傳感器網(wǎng)絡(luò)柵欄覆蓋增強(qiáng)算法*

任勇默，范興剛*，車志聰，王 超

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

K-柵欄覆蓋是有向傳感器網(wǎng)絡(luò)覆蓋控制的研究熱點(diǎn)之一。提出一種基于鄰居節(jié)點(diǎn)運(yùn)動的有向強(qiáng)柵欄構(gòu)建算法（NSDBC）。在形成柵欄的節(jié)點(diǎn)集合中，按照從左到右的節(jié)點(diǎn)順序，依次確定每一個節(jié)點(diǎn)的目標(biāo)位置，前一個節(jié)點(diǎn)確定后一個鄰居節(jié)點(diǎn)的目標(biāo)位置，后一個節(jié)點(diǎn)的選取僅與前一個節(jié)點(diǎn)有關(guān)。后一個節(jié)點(diǎn)從前一個節(jié)點(diǎn)附近節(jié)點(diǎn)中選擇能耗最少的節(jié)點(diǎn)運(yùn)動到目標(biāo)位置，從而構(gòu)建有向強(qiáng)柵欄。仿真結(jié)果證明了該柵欄構(gòu)建方法能夠用較低能耗和較少節(jié)點(diǎn)構(gòu)建有向柵欄。本文的研究對提升無線傳感器網(wǎng)絡(luò)的性能具有重要的理論與實(shí)際意義。

有向柵欄覆蓋；NSDBC；目標(biāo)位置；鄰居節(jié)點(diǎn)；運(yùn)動能耗

有向傳感器，如視頻傳感器，在諸多領(lǐng)域有著廣泛的應(yīng)用，如可將傳感器節(jié)點(diǎn)部署在重要管道沿線以監(jiān)視針對管道的破壞活動，以及在敵營周邊布設(shè)無線傳感器節(jié)點(diǎn)來監(jiān)視敵方的兵力部署和武器配備情況等。在上述列舉的應(yīng)用中，有向傳感器節(jié)點(diǎn)被部署于寬度小于感知半徑的狹長的帶狀區(qū)域內(nèi)，對監(jiān)控區(qū)域的移動目標(biāo)進(jìn)行檢測，這種技術(shù)被稱為柵欄覆蓋，如何利用有向節(jié)點(diǎn)的移動能力實(shí)現(xiàn)k-柵欄覆蓋是有向傳感網(wǎng)絡(luò)一個研究熱點(diǎn)［1］。

柵欄覆蓋目前已有一些研究工作［2-14］。Kumar定義了強(qiáng)柵欄，弱柵欄［2］；曹瑩瑩將影響柵欄覆蓋生命期的因素描述為一個多目標(biāo)優(yōu)化問題［3］；楊濤運(yùn)用柵欄構(gòu)筑算法DPA，構(gòu)筑多條柵欄，實(shí)現(xiàn)多柵欄覆蓋［4］；羅卿在概率性感知模型基礎(chǔ)上，提出一種柵欄覆蓋控制算法，調(diào)度傳感器使冗余節(jié)點(diǎn)睡眠，達(dá)到減少能耗和延長網(wǎng)絡(luò)壽命的目的［5］；Li L研究了無線傳感器網(wǎng)絡(luò)（WSN）一維K-覆蓋問題，分析kcoverage比例、全k-coverage概率和部分k-coverage概率［6］；班冬松研究了全向移動傳感器網(wǎng)絡(luò)K-柵欄覆蓋問題，提出了一種能量高效的柵欄覆蓋構(gòu)建算法CBIGB［7］；Jie Tian研究了兩維的柵欄覆蓋［8］。

馬華東研究了視頻傳感器網(wǎng)絡(luò)中的，最少的有向視頻節(jié)點(diǎn)組建柵欄問題［9］；陶丹研究如何調(diào)整有向節(jié)點(diǎn)的感知方向組建有向強(qiáng)柵欄的問題［10］；Zhang等研究轉(zhuǎn)動有向節(jié)點(diǎn)的構(gòu)建強(qiáng)柵欄［11］；Zhibo Wang研究了混合有向網(wǎng)絡(luò)的柵欄覆蓋［12］，根據(jù)網(wǎng)絡(luò)拓?fù)錁?gòu)建權(quán)重柵欄圖WBG，再運(yùn)用頂點(diǎn)不相交的路徑算法構(gòu)造K-柵欄。Amac基于移動能耗和轉(zhuǎn)動能耗，研究了有向網(wǎng)絡(luò)的覆蓋增強(qiáng)［13］。張美燕研究了最大K有向覆蓋問題，設(shè)計(jì)了一種分布式啟發(fā)式算法，在一跳鄰居范圍內(nèi)對傳感器節(jié)點(diǎn)的感知方向進(jìn)行協(xié)同調(diào)度，使得目標(biāo)集合被有向K覆蓋的時間最大［14］。

利用附近節(jié)點(diǎn)之間的位置關(guān)系，可以選擇最優(yōu)的節(jié)點(diǎn)構(gòu)建柵欄。我們研究了全向強(qiáng)柵欄構(gòu)建，提出了PMNSB算法［15］。在此基礎(chǔ)上，本文研究如何利用節(jié)點(diǎn)之間的位置關(guān)系，調(diào)度節(jié)點(diǎn)的運(yùn)動，節(jié)能高效的構(gòu)建強(qiáng)K-柵欄覆蓋，提出一種基于鄰居節(jié)點(diǎn)運(yùn)動的有向強(qiáng)柵欄構(gòu)建算法（Distributing Directional Strong Barrier Construction Based on Next Node Sports，NSDBC）。本論文的主要貢獻(xiàn)如下：根據(jù)周圍鄰節(jié)點(diǎn)信息，分布式的確定節(jié)點(diǎn)的目標(biāo)位置，并選擇運(yùn)動能耗最少的節(jié)點(diǎn)移動到目標(biāo)位置，構(gòu)建有向強(qiáng)柵欄。

本文余下章節(jié)安排如下：第1節(jié)描述網(wǎng)絡(luò)模型。第2節(jié)詳細(xì)介紹分布式有向強(qiáng)柵欄構(gòu)建方法（NSDBC）。第3節(jié)通過仿真實(shí)驗(yàn)對提出的算法進(jìn)行性能評估。第4節(jié)總結(jié)全文并介紹下一步工作。

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

有向傳感器節(jié)點(diǎn)方向可調(diào)感知模型可以采取四組表示＜P,r,a,β＞，如圖1所示。其中P=（x,y）表示節(jié)點(diǎn)的位置坐標(biāo)，r表示節(jié)點(diǎn)的感知半徑，β表示節(jié)點(diǎn)在t時刻的工作方向（或感知方向），取值范圍為0≤β≤2π，α表示節(jié)點(diǎn)的感知角度，為相對于x正半軸的方向角。則當(dāng)α=2π時，此時有向感知模型則變成了全向感知模型，是有向感知模型的一個特例。

圖1 可旋轉(zhuǎn)有向傳感器的傳感模型

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

①所有傳感器的感知半徑和感知角度均相同。

②所有傳感器的轉(zhuǎn)動功率和平地上的單位距離功耗均相同。

③傳感器監(jiān)視范圍內(nèi)的信號強(qiáng)度相同，且能在范圍內(nèi)以100%的可能性監(jiān)測到事件。

定義2 有向節(jié)點(diǎn)運(yùn)動能耗 有向節(jié)點(diǎn)運(yùn)動能耗是指有向移動節(jié)點(diǎn)運(yùn)動到目標(biāo)位置的能耗，由移動能耗和轉(zhuǎn)動能耗組成。第i（i≥2）個節(jié)點(diǎn)的轉(zhuǎn)動能耗如式（1），運(yùn)動能耗如式（2）所示，其中的參數(shù)見表1，式（1）標(biāo)明，若0≤β≤α/2，或者2π-α/2≤β≤2π，則不進(jìn)行轉(zhuǎn)動；若α/2≤β≤π，轉(zhuǎn)至β=α/2處；若π＜β＜2π-α/2，轉(zhuǎn)至 β=2π-α/2處。式（2）表明移動能耗和轉(zhuǎn)動能耗之和就是有向節(jié)點(diǎn)運(yùn)動能耗。

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

我們研究的問題就是：在狹長區(qū)域中，隨機(jī)部署的有向移動節(jié)點(diǎn)密度為 ρ的情況下，如何分布式地調(diào)度移動節(jié)點(diǎn)，以盡量少的運(yùn)動能耗構(gòu)建有向強(qiáng)柵欄覆蓋。

2 基于鄰居節(jié)點(diǎn)運(yùn)動的有向強(qiáng)柵欄構(gòu)建算法（NSDBC）

Zhibo Wang考查區(qū)域內(nèi)的所有靜態(tài)節(jié)點(diǎn)組成的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，采用頂點(diǎn)不重復(fù)的K條路徑的圖論算法找到形成柵欄的目標(biāo)位置，然后移動節(jié)點(diǎn)和這些目標(biāo)位置進(jìn)行最佳匹配，這需要全局拓?fù)湫畔ⅲㄐ藕烷_銷較大，而且不適用于要減少通信和計(jì)算開銷，PMNSB算法把構(gòu)造K-柵欄這個復(fù)雜的問題分成小問題，先在小的子區(qū)域構(gòu)造1MNSB，這些1-柵欄合起來就是強(qiáng)K-柵欄。但PMNSB算法不能用于有向強(qiáng)柵欄的構(gòu)建，在有向柵欄中，有向節(jié)點(diǎn)感知不再是圓形，而是扇形，單獨(dú)的圓心不能確定一個有向節(jié)點(diǎn)的位置。而且PMNSB算法僅考慮節(jié)點(diǎn)的移動，沒有考慮節(jié)點(diǎn)的轉(zhuǎn)動，而轉(zhuǎn)動節(jié)點(diǎn)是解決有向覆蓋問題的主要方法。在此基礎(chǔ)上，我們提出一種分布式基于鄰居節(jié)點(diǎn)運(yùn)動的有向強(qiáng)柵欄構(gòu)建算法（distributing directional strong barrier construction based on next node sports，NSDBC）。

2.1 算法的基本思想

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

2.2 算法具體過程

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

圖2 NSDBC算法偽代碼

NSDBC算法具體步驟如下：

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

在投撒傳感器完畢后，分別統(tǒng)計(jì)各個區(qū)間段0≤y≤2r、2r≤y≤4r、4r≤y≤6r、…、2nr≤y≤W內(nèi)的節(jié)點(diǎn)個數(shù)（n為某個整數(shù)，且W-2nr≤2r）。選取節(jié)點(diǎn)個數(shù)最多的區(qū)間段作為第1條柵欄形成的預(yù)選區(qū)域，若出現(xiàn)個數(shù)并列最多的區(qū)間段，則選取其中縱坐標(biāo)方差最小的區(qū)間段作為預(yù)選區(qū)域。這是因?yàn)閰^(qū)間段內(nèi)節(jié)點(diǎn)縱坐標(biāo)方差小時，柵欄在縱向上發(fā)生的偏離程度更小，柵欄位置更為穩(wěn)定。

步驟2 確定有向強(qiáng)柵欄的第一個節(jié)點(diǎn)。

表1 參數(shù)定義

步驟3 確定第二個節(jié)點(diǎn)的目標(biāo)位置，并選擇節(jié)點(diǎn)運(yùn)動。

判斷剩余的所有節(jié)點(diǎn)中，是否有節(jié)點(diǎn)在第1個節(jié)點(diǎn)扇形區(qū)域內(nèi)部。若有，選出扇形區(qū)域內(nèi)橫坐標(biāo)最大的節(jié)點(diǎn)（即最靠右的節(jié)點(diǎn)）作為第2個節(jié)點(diǎn)，不進(jìn)行移動。只將其按照式（1）調(diào)整方向角，并計(jì)算運(yùn)動能耗。例如，在圖3（a）中，節(jié)點(diǎn)A為第一個節(jié)點(diǎn)，圓心為B的虛扇形為第二個節(jié)點(diǎn)的目標(biāo)位置，圓心為B的節(jié)點(diǎn)主要轉(zhuǎn)動到虛線位置即成為構(gòu)建柵欄的第二個節(jié)點(diǎn)。若沒有節(jié)點(diǎn)在第1個節(jié)點(diǎn)扇形區(qū)域內(nèi)部，則先判斷第1個節(jié)點(diǎn)對應(yīng)的扇形區(qū)域中，節(jié)點(diǎn)自身的坐標(biāo)、對應(yīng)扇形區(qū)域的兩個端點(diǎn)坐標(biāo)、弧上的中點(diǎn)坐標(biāo)這4個坐標(biāo)中哪個點(diǎn)對應(yīng)的橫坐標(biāo)最大，將其中橫坐標(biāo)最大的點(diǎn)作為第2個節(jié)點(diǎn)需要移動的目標(biāo)位置，若選出的目標(biāo)位置超出矩形檢測區(qū)域，或出現(xiàn)同時有2個點(diǎn)橫坐標(biāo)并列最大的情況，則認(rèn)為此次選擇無效，重新將第1個節(jié)點(diǎn)自身的坐標(biāo)作為第2個節(jié)點(diǎn)的目標(biāo)位置。選定目標(biāo)位置后，找出剩余所有節(jié)點(diǎn)中與目標(biāo)位置之間歐氏距離最短的節(jié)點(diǎn)作為第2個節(jié)點(diǎn)，并沿著最短路徑移動至目標(biāo)位置，并按照式（1）調(diào)整方向角，并記錄總能耗E=E+E2。例如，在圖3（b）中，節(jié)點(diǎn)A為第一個節(jié)點(diǎn)，圓心為B的虛扇形為第二個節(jié)點(diǎn)的目標(biāo)位置，C為移動節(jié)點(diǎn)。

圖3 第二個節(jié)點(diǎn)的選擇

圖4 節(jié)點(diǎn)的選擇

步驟4 確定其余所需節(jié)點(diǎn)的目標(biāo)位置，并選擇節(jié)點(diǎn)移動。

在第i（i≥2）個節(jié)點(diǎn)調(diào)度完畢后，若在其感知區(qū)域內(nèi)部存在節(jié)點(diǎn)，橫坐標(biāo)最大的節(jié)點(diǎn)就是第i+1個節(jié)點(diǎn)的坐標(biāo)。例如，在圖4（a）中，節(jié)點(diǎn)A中，節(jié)點(diǎn)C的橫坐標(biāo)比節(jié)點(diǎn)D大，則節(jié)點(diǎn)C的坐標(biāo)就是下一個節(jié)點(diǎn)的坐標(biāo)，圓心為C的虛扇形就是第i+1個節(jié)點(diǎn)的目標(biāo)位置。如果感知區(qū)域內(nèi)部沒有節(jié)點(diǎn)，則令第i（i≥2）個節(jié)點(diǎn)正右方向一個半徑距離處作為下一節(jié)點(diǎn)的坐標(biāo)位置，然后選出剩余所有節(jié)點(diǎn)中與其歐氏距離最短的節(jié)點(diǎn)，將其沿最短路徑移動至與目標(biāo)位置重合，并按式（1）方法調(diào)整方向角。例如，在圖4b中，節(jié)點(diǎn)A中沒有節(jié)點(diǎn)，則節(jié)點(diǎn)A的正右方向一個半徑距離處端點(diǎn)B作為下一個節(jié)點(diǎn)的坐標(biāo)位置，節(jié)點(diǎn)C的距離端點(diǎn)B最近，則圓心為B的虛扇形為下一個節(jié)點(diǎn)的目標(biāo)位置。則節(jié)點(diǎn)C運(yùn)動到目標(biāo)位置。統(tǒng)計(jì)當(dāng)前的運(yùn)動總能耗E=E+Ei。

步驟5 形成第1條柵欄。

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

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

2.3 算法的理論分析

由于在形成柵欄的過程中，需要通過減少節(jié)點(diǎn)移動距離和轉(zhuǎn)動角度來降低能耗，從而延長柵欄的壽命。因此需在投撒節(jié)點(diǎn)完畢之后，選出一個節(jié)點(diǎn)個數(shù)最多，且分布較為集中的區(qū)域段作為柵欄的預(yù)選區(qū)域，分布式地調(diào)度附近節(jié)點(diǎn)形成柵欄。這樣可以使得節(jié)點(diǎn)在參與調(diào)度形成柵欄的過程中盡可能地減少移動距離，降低能耗。

在轉(zhuǎn)動過程中，NSDBC算法可以在移動完畢后，將轉(zhuǎn)動能耗降至最低，使柵欄長度得到最大限度的增長。同時能夠用較少的節(jié)點(diǎn)構(gòu)建柵欄，從而在一定程度上降低對投撒密度的要求，節(jié)約節(jié)點(diǎn)，降低通信開銷。

在柵欄的形成過程中，若有節(jié)點(diǎn)處于已調(diào)度完畢節(jié)點(diǎn)扇形區(qū)域的內(nèi)部，則為了較大程度上節(jié)省該節(jié)點(diǎn)的能耗，同時盡可能地延長柵欄的已有長度，NSDBC算法選取扇形區(qū)域內(nèi)最靠右的節(jié)點(diǎn)。由于傳感器節(jié)點(diǎn)的橫坐標(biāo)在x軸方向上服從隨機(jī)分布，因此在已知有節(jié)點(diǎn)處于扇形區(qū)域內(nèi)部的情況下，該節(jié)點(diǎn)橫坐標(biāo)的期望值應(yīng)為扇形區(qū)域?qū)?yīng)節(jié)點(diǎn)的橫坐標(biāo)+r/2（由于有多個節(jié)點(diǎn)同時位于同一個扇形內(nèi)部的幾率極低，在這里忽略不計(jì)，僅考慮只有一個節(jié)點(diǎn)位于扇形區(qū)域內(nèi)部的情況）。又因?yàn)閱蝹€傳感器節(jié)點(diǎn)每轉(zhuǎn)動π耗能為1.8 J，每移動1 m耗能為3.6 J，所以為了節(jié)省該節(jié)點(diǎn)的能耗，NSDBC算法對區(qū)域內(nèi)節(jié)點(diǎn)僅進(jìn)行轉(zhuǎn)動，期望在柵欄已有長度基礎(chǔ)上增加r 2的長度。

在形成柵欄的過程中，可能會出現(xiàn)部分節(jié)點(diǎn)的扇形區(qū)域有一部分超出矩形監(jiān)測區(qū)域的情況。因此NSDBC算法在選擇第2個節(jié)點(diǎn)的目標(biāo)位置時，確保目標(biāo)位置位于第1個節(jié)點(diǎn)監(jiān)測區(qū)域內(nèi)，從第3個節(jié)點(diǎn)開始，只要柵欄未形成完畢，目標(biāo)位置一定處于監(jiān)測區(qū)域內(nèi)，即可保證柵欄形成過程的可連續(xù)性。

在時間復(fù)雜度方面，由于計(jì)算一個節(jié)點(diǎn)的運(yùn)動能耗所花費(fèi)的時間一定，考慮在最壞情況下，有大量的節(jié)點(diǎn)落在扇形區(qū)域內(nèi)，恰巧使用了投撒區(qū)域內(nèi)全部的節(jié)點(diǎn)形成了K條柵欄，在柵欄形成過程中，設(shè)總共有n個節(jié)點(diǎn)，則需要從這n個節(jié)點(diǎn)中選中第1個節(jié)點(diǎn)，然后從n-1個節(jié)點(diǎn)中選出第2個節(jié)點(diǎn)，以此類推，直至柵欄形成完畢，時間復(fù)雜度為：O（n2）。

3 仿真結(jié)果

本文運(yùn)用Matlab7.0對此算法進(jìn)行仿真，每組實(shí)驗(yàn)數(shù)據(jù)采用重復(fù)50次獨(dú)立實(shí)驗(yàn)取平均值的方式獲得。參考文獻(xiàn)［13，15］，實(shí)驗(yàn)的默認(rèn)參數(shù)如表2所示，其中單個傳感器節(jié)點(diǎn)每轉(zhuǎn)動180°耗能為1.8 J，每移動1 m耗能為3.6 J。

我們選取了文獻(xiàn)［12］中的strong optimal算法、strong greedy算法與本文中的NSDBC算法進(jìn)行了仿真比較。

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

在默認(rèn)參數(shù)下，給定相同的初始投撒結(jié)果，節(jié)點(diǎn)隨機(jī)分布如圖5所示。

圖5 節(jié)點(diǎn)隨機(jī)分布圖

NSDBC算法的形成的柵欄如圖6所示，strong optimal算法的形成的柵欄如圖7所示。

圖6 NSDBC算法

圖7 Strong optimal算法

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

由于strong optimal算法、strong greedy算法對于節(jié)點(diǎn)數(shù)量的要求比較高，在保證能形成柵欄的前提下，本文采用0.003作為起始節(jié)點(diǎn)密度進(jìn)行仿真比較，其余實(shí)驗(yàn)參數(shù)均與表2中的默認(rèn)參數(shù)一致。仿真結(jié)果如圖8～圖10所示。

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

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

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

從圖8中可以發(fā)現(xiàn)，隨著節(jié)點(diǎn)密度的增加，3種算法所對應(yīng)的總能耗均呈顯著性下降，在節(jié)點(diǎn)密度較低的情況下，NSDBC算法的總能耗明顯低于strong optimal算法和strong greedy算法。從圖9可以發(fā)現(xiàn)，NSDBC算法形成柵欄所需的節(jié)點(diǎn)數(shù)明顯低于strong optimal算法與strong greedy算法形成柵欄所需的節(jié)點(diǎn)數(shù)。從圖10中可以發(fā)現(xiàn)，隨著節(jié)點(diǎn)密度的增加，三種算法相應(yīng)的平均能耗均呈顯著性下降，但NSDBC算法對應(yīng)的平均能耗始終明顯低于strong optimal算法與strong greedy算法對應(yīng)的平均能耗。將圖9和圖10中的數(shù)據(jù)進(jìn)行綜合比較可以得出結(jié)論：由于節(jié)點(diǎn)的平均能耗明顯比NSDBC算法中節(jié)點(diǎn)的平均能耗高，且形成柵欄所需的節(jié)點(diǎn)數(shù)明顯地多于NSDBC算法中形成柵欄所需的節(jié)點(diǎn)數(shù)，導(dǎo)致參與調(diào)度過程的節(jié)點(diǎn)中，有節(jié)點(diǎn)耗能極高的可能性進(jìn)一步增加，而在柵欄中耗能最高的節(jié)點(diǎn)耗能的高低直接決定柵欄壽命的長短。因此在柵欄形成完畢后，按照NSDBC算法形成柵欄的壽命明顯高于按照strong optimal算法與strong greedy算法形成柵欄的壽命。

3.2 柵欄數(shù)的影響

柵欄數(shù)K的影響如圖11～圖13所示。從圖11中可以看出，三種算法的節(jié)點(diǎn)總能耗均隨K增大而增大，當(dāng)K＞3時，隨著K的增大，NSDBC算法的節(jié)點(diǎn)總能耗將越來越低于同等條件下strong optimal算法與strong greedy算法中的節(jié)點(diǎn)總能耗。

圖11 柵欄數(shù)VS節(jié)點(diǎn)總能耗

從圖12可以看出，隨著K的增大，NSDBC算法形成柵欄所需的節(jié)點(diǎn)數(shù)隨K的增長率明顯低于同等條件下的strong optimal算法與strong greedy算法，當(dāng)K不斷增大時，NSDBC算法形成柵欄所需節(jié)點(diǎn)數(shù)將越來越少于同等條件下的strong optimal算法與strong greedy算法。圖13表明，隨著K的增大，而NSDBC算法的節(jié)點(diǎn)平均能耗的上升趨勢比于strong optimal算法、strong greedy算法較為微弱，且上升幅度遠(yuǎn)低于strong optimal算法與strong greedy算法在同等情況下的上升幅度。

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

圖13 柵欄數(shù)VS節(jié)點(diǎn)平均能耗

3.3 傳感器感知角度的影響

由于傳感器的感知角度發(fā)生變化時，會使得節(jié)點(diǎn)位于傳感器扇形監(jiān)測區(qū)域的幾率發(fā)生變化。不同的傳感器感知角度影響效果如圖14～圖16所示。

圖14 感知角度VS總能耗

圖15 感知角度VS形成柵欄所需的節(jié)點(diǎn)個數(shù)

圖16 感知角度VS節(jié)點(diǎn)平均能耗

從圖15可以看出，感知角度增大時，節(jié)點(diǎn)位于扇形區(qū)域內(nèi)部的幾率也隨之增大，導(dǎo)致形成柵欄所需的節(jié)點(diǎn)數(shù)也隨感知角度的增大而增大，當(dāng)K＞1時，由于受到K的放大影響，形成柵欄所需的節(jié)點(diǎn)數(shù)在感知角度增大時的漲幅也會得到一定程度的放大。

圖16表明隨著感知角度的增大，由于節(jié)點(diǎn)位于扇形區(qū)域內(nèi)部的幾率增加，平均能耗整體上呈明顯的下降趨勢，且發(fā)生波動的頻率與幅度不斷減小。

4 結(jié)論

本文主要研究有向強(qiáng)柵欄覆蓋問題，提出NSDBC算法，利用相鄰節(jié)點(diǎn)之間的關(guān)系，按照從左到右的節(jié)點(diǎn)順序，依次確定每一個節(jié)點(diǎn)的目標(biāo)位置，前一個節(jié)點(diǎn)確定后一個節(jié)點(diǎn)的目標(biāo)位置，后一個節(jié)點(diǎn)的坐標(biāo)僅與前一個節(jié)點(diǎn)有關(guān)。從附近節(jié)點(diǎn)中選擇能耗最少的節(jié)點(diǎn)運(yùn)動到目標(biāo)位置，從而分布式構(gòu)建有向強(qiáng)柵欄。仿真結(jié)果證明NSDBC算法可以用較少的節(jié)點(diǎn)，更為高效節(jié)能地構(gòu)建有向K-柵欄覆蓋。

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

［1］ 任彥，張思東，張宏科.無線傳感器網(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ǎ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 Communications and Mobile Computing，2013，13（1）：1-11.

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

［8］ Jie Tian，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.

［9］ Ma H，Yang M，Li D，et al.Minimum Camera Barrier Coverage in Wireless Camera Sensor Networks［C］//Proc IEEE INFOCOM，Orlando，F(xiàn)L，USA，2012：217-225.

［10］Tao D，Tang S，Zhang H，et al.Strong Barrier Coverage in Directional Sensor Networks［C］//Comput Commun，2012，35（8）：895-905.

［11］Zhang L，Tang J，Zhang W.Strong Barrier Coverage with Directional Sensors［C］//ProcIEEEGlobeCom，Honolulu，HI，USA，2009：1-6.

［12］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.

［13］Amac Guvensan，Gokhan Yavuz.Hybrid Movement Strategy in Self-Orienting Directional Sensor Networks［J］.Ad Hoc Networks，2013，11（3）：1075-1090.

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

［15］王超，范興剛.一種高效強(qiáng)K-柵欄覆蓋構(gòu)建算法［J］.傳感技術(shù)學(xué)報(bào)，2015，28（2）：227-233.

任勇默（1994-），男，本科生，主要研究領(lǐng)域?yàn)闊o線傳感器網(wǎng)絡(luò)；

范興剛（1974-），男，副教授，工學(xué)博士，研究領(lǐng)域?yàn)閭鞲衅骶W(wǎng)絡(luò)，網(wǎng)絡(luò)通信、實(shí)時通信，分布式實(shí)時系統(tǒng)的設(shè)計(jì)，xgfan@ zjut.edu.cn；

車志聰（1995-），男，本科生，主要研究領(lǐng)域?yàn)闊o線傳感器網(wǎng)絡(luò)；

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

An Distributing Scheme for Directional Barrier Coverage Enhancing in DSN*

REN Yongmo，F(xiàn)AN Xinggang*，CHE Zhicong，WANG Chao
（College of Computer Science and Technology，Zhejiang University of Technology，Hangzhou 310023，China）

K-barrier coverage is one of the hot spot in directional wireless sensor network.This paper proposes a distributing directional strong barrier construction scheme based on next node sports（NSDBC）to create directional barrier coverage with lower energy consumption.It is only the previous node that determines the next target node position for barrier；the target node position is constituted by the coordinate of center and working direction of sensing sector.The previous node finds node in its vicinity that moves to target next node location with minimum moving energy consumption and adjusts its working directional to target direction with minimum rotating energy consumption. Simulation results show this method could effectively constitute K-barrier coverage，and enhance the coverage performance of DSN.This research has important theoretical and practical significance.

directional barrier coverage；NSDBC；target position；neighbor node；sports energy consumption EEACC：7230

TP273

A

1004-1699（2015）07-1051-07

10.3969/j.issn.1004-1699.2015.07.019

項(xiàng)目來源：“十二五”國家科技支撐計(jì)劃項(xiàng)目（2012BAD10B01）

2015-02-19 修改日期：2015-05-13