車志聰，范興剛，徐俊超（浙江工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，杭州310023）

?

一種基于目標(biāo)圓的有向強(qiáng)柵欄構(gòu)建算法*

車志聰，范興剛*，徐俊超
（浙江工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，杭州310023）

摘要：K-柵欄覆蓋是有向傳感器網(wǎng)絡(luò)覆蓋控制的研究熱點(diǎn)之一。提出一種基于目標(biāo)圓的分布式有向強(qiáng)柵欄構(gòu)建方法（DBCTC）。首次構(gòu)建了節(jié)點(diǎn)目標(biāo)圓和能耗比2個(gè)模型。以節(jié)點(diǎn)感知區(qū)域內(nèi)橫坐標(biāo)最大的點(diǎn)為圓心，以感知半徑為半徑的圓就是目標(biāo)圓。節(jié)點(diǎn)的運(yùn)動(dòng)能耗和柵欄增益的比值就是能耗比。前一個(gè)節(jié)點(diǎn)根據(jù)目標(biāo)圓模型選擇后一個(gè)節(jié)點(diǎn)的最佳目標(biāo)位置。從附近移動(dòng)節(jié)點(diǎn)中選擇能耗比最少的移動(dòng)節(jié)點(diǎn)構(gòu)建有向強(qiáng)柵欄。仿真結(jié)果證明，該柵欄構(gòu)建方法比其他算法降低60%左右的能耗。

關(guān)鍵詞：有向柵欄覆蓋；目標(biāo)圓；節(jié)點(diǎn)目標(biāo)方向；下一個(gè)節(jié)點(diǎn)，能耗比

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

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

利用節(jié)點(diǎn)的移動(dòng)能力構(gòu)建全向柵欄已有一些研究工作。班冬松研究了全向移動(dòng)傳感器網(wǎng)絡(luò)K-柵欄覆蓋問(wèn)題，提出了一種能量高效的柵欄覆蓋構(gòu)建算法CBIGB［2］。Wang研究了節(jié)點(diǎn)存在定位誤差時(shí)的柵欄覆蓋問(wèn)題［3］。He研究了多次移動(dòng)節(jié)點(diǎn)構(gòu)建柵欄覆蓋［4］。范興剛研究了全向強(qiáng)柵欄構(gòu)建，提出了PMNSB算法［5］。在有向柵欄研究中，Ma研究了最少的有向視頻節(jié)點(diǎn)組建柵欄問(wèn)題［6］；Zhang利用有向節(jié)點(diǎn)的轉(zhuǎn)動(dòng)能力構(gòu)建強(qiáng)柵欄［7］；Wang選擇有向節(jié)點(diǎn)組建視線柵欄，構(gòu)建有向傳感陣列監(jiān)視入侵者［8］；Wang研究了混合有向網(wǎng)絡(luò)的柵欄覆蓋［9-10］，根據(jù)網(wǎng)絡(luò)拓?fù)錁?gòu)建權(quán)重柵欄圖WBG，再運(yùn)用頂點(diǎn)不相交的路徑算法構(gòu)造K-柵欄。以上這些方法都是集中式的，都需要知道整個(gè)網(wǎng)絡(luò)的拓?fù)?。Shih研究了分布式柵欄構(gòu)建算法，利用可能柵欄行中的鄰居節(jié)點(diǎn)通過(guò)柵欄信息構(gòu)建柵欄［11］。Tao利用鄰居節(jié)點(diǎn)的位置信息，選擇具有最多鄰居的節(jié)點(diǎn)構(gòu)建柵欄［12］。

Amac基于移動(dòng)能耗和轉(zhuǎn)動(dòng)能耗，研究了有向網(wǎng)絡(luò)的覆蓋增強(qiáng)［13］。利用附近節(jié)點(diǎn)之間的位置關(guān)系，分布式的選擇節(jié)點(diǎn)構(gòu)建柵欄。我們研究了NSDBC算法［14］。在此基礎(chǔ)上，本文研究如何利用鄰居節(jié)點(diǎn)目標(biāo)圓，根據(jù)運(yùn)動(dòng)能耗與柵欄增加的長(zhǎng)度比值，調(diào)度節(jié)點(diǎn)的運(yùn)動(dòng)，節(jié)能高效的構(gòu)建有向強(qiáng)K-柵欄覆蓋，提出一種基于目標(biāo)圓的分布式有向強(qiáng)柵欄構(gòu)建方法DBCTC （Distributing Directional Strong Barrier Construction Based on Target Circle）。主要貢獻(xiàn)如下：①首次創(chuàng)建了節(jié)點(diǎn)目標(biāo)圓模型，節(jié)點(diǎn)根據(jù)自己的目標(biāo)圓和周圍的移動(dòng)節(jié)點(diǎn)，確定下一個(gè)節(jié)點(diǎn)的目標(biāo)位置；②提出了能耗比模型，每一個(gè)節(jié)點(diǎn)根據(jù)能耗比選擇可移動(dòng)節(jié)點(diǎn)運(yùn)動(dòng)到目標(biāo)位置構(gòu)建有向強(qiáng)柵欄；

本文余下章節(jié)安排如下：第1節(jié)描述網(wǎng)絡(luò)模型；第2節(jié)詳細(xì)介紹DBCTC方法；第3節(jié)通過(guò)仿真實(shí)驗(yàn)對(duì)提出的算法進(jìn)行性能評(píng)估；第4節(jié)總結(jié)全文并介紹下一步工作。

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

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

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

研究有向柵欄問(wèn)題之前，有如下假設(shè)：①所有傳感器的感知半徑和感知角度均相同。②所有傳感器的轉(zhuǎn)動(dòng)能耗和移動(dòng)功耗均相同，參考文獻(xiàn)［15］，傳感器每轉(zhuǎn)動(dòng)180°耗能為1.8 J，每移動(dòng)1 m耗能為3.6 J。③傳感器監(jiān)視范圍內(nèi)的信號(hào)強(qiáng)度相同，且能在范圍內(nèi)以100%的可能性監(jiān)測(cè)到事件。

有向節(jié)點(diǎn)的目標(biāo)位置，有向節(jié)點(diǎn)運(yùn)動(dòng)能耗和節(jié)點(diǎn)密度定義分別參考文獻(xiàn)［14］中的定義1，2，3。

定義1有向節(jié)點(diǎn)的目標(biāo)感知方向。移動(dòng)到目標(biāo)位置的有向節(jié)點(diǎn)的感知方向就是有向節(jié)點(diǎn)的目標(biāo)感知方向。有向節(jié)點(diǎn)的目標(biāo)感知方向由移動(dòng)到該位置的移動(dòng)節(jié)點(diǎn)的初始感知方向決定。

定義2目標(biāo)圓。以一個(gè)節(jié)點(diǎn)感知區(qū)域內(nèi)橫坐標(biāo)最大的點(diǎn)為圓心，以r為半徑的圓就是目標(biāo)圓。目標(biāo)圓外的移動(dòng)節(jié)點(diǎn)只要移動(dòng)到目標(biāo)圓上，再轉(zhuǎn)動(dòng)有限的角度，就可能與前一個(gè)節(jié)點(diǎn)形成柵欄鏈接。

定義3能效比。假設(shè)移動(dòng)節(jié)點(diǎn)的運(yùn)動(dòng)能耗為Ei，柵欄增加的長(zhǎng)度為li，則能效比為λi=Ei/li，能效比越小，形成柵欄耗費(fèi)的能量越小，柵欄形成算法越高效。

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

2　基于目標(biāo)圓的分布式有向強(qiáng)柵欄構(gòu)建算法（DBCTC）

Wang［10］提出了optimal scheme算法，構(gòu)建加權(quán)圖，采用頂點(diǎn)不重復(fù)的K條路徑圖論算法找到形成柵欄的目標(biāo)位置，然后移動(dòng)節(jié)點(diǎn)和這些目標(biāo)位置進(jìn)行最佳匹配。運(yùn)用節(jié)點(diǎn)之間的位置關(guān)系，在形成柵欄的節(jié)點(diǎn)集合中，按照從左到右的節(jié)點(diǎn)順序，按照節(jié)點(diǎn)對(duì)柵欄貢獻(xiàn)盡量最大原則，由前一個(gè)節(jié)點(diǎn)確定節(jié)點(diǎn)的目標(biāo)位置，并選擇能耗最少的節(jié)點(diǎn)移動(dòng)到目標(biāo)位置。從而構(gòu)建有向強(qiáng)柵欄。這是分布式基于鄰居節(jié)點(diǎn)運(yùn)動(dòng)的分布式有向柵欄構(gòu)建算法（NSDBC）［14］。

另一方面，以節(jié)點(diǎn)感知區(qū)域內(nèi)橫坐標(biāo)最大的點(diǎn)為圓心，以r為半徑的圓就是目標(biāo)圓，移動(dòng)節(jié)點(diǎn)只要移動(dòng)到這個(gè)目標(biāo)圓上，再轉(zhuǎn)動(dòng)有限的角度，就可以與前一個(gè)節(jié)點(diǎn)形成柵欄鏈接。這就是DBCTC算法的基本思路。

2.1理論分析

要形成柵欄，重點(diǎn)和難點(diǎn)是確定節(jié)點(diǎn)目標(biāo)位置。有向節(jié)點(diǎn)的目標(biāo)位置由形成柵欄的前一個(gè)節(jié)點(diǎn)決定。

在第i(i≥1)個(gè)節(jié)點(diǎn)調(diào)度完畢后，若在其感知區(qū)域內(nèi)部存在節(jié)點(diǎn)，橫坐標(biāo)最大的節(jié)點(diǎn)就是第i+1個(gè)節(jié)點(diǎn)的目標(biāo)位置。例如，在圖2（a）、2（b）中，節(jié)點(diǎn)A中，節(jié)點(diǎn)C的橫坐標(biāo)比節(jié)點(diǎn)D大，則節(jié)點(diǎn)C的坐標(biāo)就是下一個(gè)節(jié)點(diǎn)的坐標(biāo)，圓心為C的虛扇形就是第i+1個(gè)節(jié)點(diǎn)的目標(biāo)位置。在圖2（a）中，α/2≤β≤π，節(jié)點(diǎn)C的目標(biāo)方向?yàn)棣?α/2處。在圖2（b）中，π<β<2π-α/2，節(jié)點(diǎn)C的目標(biāo)方向?yàn)棣?2π-α/2。

對(duì)于節(jié)點(diǎn)感知區(qū)域外的移動(dòng)節(jié)點(diǎn)，則要構(gòu)造目標(biāo)圓來(lái)確定節(jié)點(diǎn)的目標(biāo)位置。以感知區(qū)域內(nèi)橫坐標(biāo)最大的點(diǎn)為圓心，以r為半徑，構(gòu)造目標(biāo)圓。如果目標(biāo)圓內(nèi)有移動(dòng)節(jié)點(diǎn)，下一節(jié)點(diǎn)的目標(biāo)位置就是其坐標(biāo)，這個(gè)節(jié)點(diǎn)再以最小的轉(zhuǎn)動(dòng)角度調(diào)整感知方向，使其與前一個(gè)節(jié)點(diǎn)形成柵欄銜接。例如，在圖2（c）中，節(jié)點(diǎn)A中沒(méi)有節(jié)點(diǎn)，則以節(jié)點(diǎn)A的感知區(qū)域內(nèi)，找到橫坐標(biāo)最大的堤岸B，以點(diǎn)B為圓心構(gòu)造節(jié)點(diǎn)A的目標(biāo)圓，節(jié)點(diǎn)C在目標(biāo)圓內(nèi)，則節(jié)點(diǎn)C的坐標(biāo)就是下一個(gè)節(jié)點(diǎn)的目標(biāo)位置，其目標(biāo)感知方向?yàn)榧t色的虛線扇形。

由幾何知識(shí)可知，兩點(diǎn)之間的直線距離最短，對(duì)于目標(biāo)圓外的移動(dòng)節(jié)點(diǎn)，移動(dòng)節(jié)點(diǎn)與目標(biāo)圓的圓心的連線與目標(biāo)圓的交點(diǎn)就是下一節(jié)點(diǎn)目標(biāo)位置。移動(dòng)節(jié)點(diǎn)沿著與目標(biāo)圓圓心的連線，用最短的移動(dòng)距離與前一個(gè)節(jié)點(diǎn)形成柵欄銜接。

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

例如，在圖2（d）中，節(jié)點(diǎn)A的目標(biāo)圓中沒(méi)有節(jié)點(diǎn)。移動(dòng)節(jié)點(diǎn)D在目標(biāo)圓外，BD與目標(biāo)圓的交點(diǎn)C就是下一個(gè)節(jié)點(diǎn)的目標(biāo)位置，其感知方向?yàn)榧t色的虛線扇形。直線CB與X軸的夾角為θ，逆時(shí)針轉(zhuǎn)動(dòng)的節(jié)點(diǎn)C，使其與目標(biāo)感知方向一直。根據(jù)文獻(xiàn)［15］的定義2，計(jì)算節(jié)點(diǎn)C的運(yùn)動(dòng)能耗，這個(gè)時(shí)候柵欄增加的長(zhǎng)度為l=xC-xA。

確定了節(jié)點(diǎn)的運(yùn)動(dòng)能耗和柵欄增益長(zhǎng)度后，定義3給出了移動(dòng)節(jié)點(diǎn)的能耗比。選出能效比最大的移動(dòng)節(jié)點(diǎn)，移動(dòng)到相應(yīng)的目標(biāo)位置，并以最小的轉(zhuǎn)動(dòng)能耗調(diào)整感知方向，形成柵欄。

2.2算法的詳細(xì)過(guò)程

算法所用參數(shù)如表1所示。

表1　相關(guān)參數(shù)

DBCTC算法偽代碼如圖3，DBCTC算法具體步驟如下。

圖3　DBCTC算法偽代碼

Step 1：確定有向強(qiáng)柵欄的第一個(gè)節(jié)點(diǎn)。

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

Step 2：確定下一個(gè)節(jié)點(diǎn)的目標(biāo)位置。Step 2.1：前一個(gè)節(jié)點(diǎn)感知區(qū)域內(nèi)的移動(dòng)節(jié)點(diǎn)。

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

圖4感知區(qū)域內(nèi)節(jié)點(diǎn)的選擇

Step 2.2：前一個(gè)節(jié)點(diǎn)感知區(qū)域外的移動(dòng)節(jié)點(diǎn)。

Step 2.2.1：前一個(gè)節(jié)點(diǎn)目標(biāo)圓內(nèi)的移動(dòng)節(jié)點(diǎn)。

若沒(méi)有節(jié)點(diǎn)在第1個(gè)節(jié)點(diǎn)扇形區(qū)域內(nèi)部，則將其中橫坐標(biāo)最大的點(diǎn)作為圓心，構(gòu)造目標(biāo)圓。如果有移動(dòng)節(jié)點(diǎn)在目標(biāo)圓內(nèi)，下一節(jié)點(diǎn)的目標(biāo)位置就是其坐標(biāo)，以最小的轉(zhuǎn)動(dòng)角度調(diào)整感知方向，使其與前一個(gè)節(jié)點(diǎn)形成柵欄銜接。計(jì)算移動(dòng)節(jié)點(diǎn)構(gòu)建柵欄的能耗，和柵欄的延伸長(zhǎng)度，計(jì)算能耗比。

Step 2.2.2：前一個(gè)節(jié)點(diǎn)目標(biāo)圓外的移動(dòng)節(jié)點(diǎn)。

如果目標(biāo)圓內(nèi)沒(méi)有移動(dòng)節(jié)點(diǎn)，對(duì)目標(biāo)圓周圍的移動(dòng)節(jié)點(diǎn)進(jìn)行如下的操作：先確定移動(dòng)節(jié)點(diǎn)形成柵欄的的目標(biāo)位置和目標(biāo)感知方向，移動(dòng)節(jié)點(diǎn)和圓心的連線與目標(biāo)圓的交點(diǎn)就是下一個(gè)節(jié)點(diǎn)的目標(biāo)位置，再根據(jù)圖2確定節(jié)點(diǎn)的目標(biāo)感知方向。計(jì)算移動(dòng)節(jié)點(diǎn)構(gòu)建柵欄的能耗，和柵欄的延伸長(zhǎng)度，計(jì)算能耗比。

Step 3：確定移動(dòng)節(jié)點(diǎn)的目標(biāo)方向。

根據(jù)定義1確定節(jié)點(diǎn)的目標(biāo)方向。

Step 4：確定移動(dòng)節(jié)點(diǎn)的運(yùn)動(dòng)能耗。

根據(jù)文獻(xiàn)［14］的定義2確定節(jié)點(diǎn)的運(yùn)動(dòng)能耗。

Step 5：能耗比最高的可移動(dòng)節(jié)點(diǎn)形成柵欄。

選擇能耗比最高的節(jié)點(diǎn)運(yùn)動(dòng)到目標(biāo)位置，與前一個(gè)節(jié)點(diǎn)形成柵欄銜接。

Step 6：依次確定其余節(jié)點(diǎn)的目標(biāo)位置，并選擇能耗比最高的節(jié)點(diǎn)移動(dòng)。

Step 7：根據(jù)右邊界位置，確定形成第1條柵欄。第i+1個(gè)節(jié)點(diǎn)調(diào)度完后，判斷≥L是否滿足。若是，則該條柵欄已經(jīng)形成完畢，轉(zhuǎn)入Step 8；若否，則轉(zhuǎn)到Step 2。

Step 8：構(gòu)建其余K-1條柵欄。

若K>1，從剩余的移動(dòng)節(jié)點(diǎn)中選擇橫坐標(biāo)最小的節(jié)點(diǎn)，重復(fù)Step 2至Step 7的操作，形成第2條柵欄。同理，依次形成第3條、第4條…第K條柵欄，算法結(jié)束。

2.3算法的特點(diǎn)分析

如何降低柵欄形成過(guò)程中的能耗，是柵欄構(gòu)建算法要重點(diǎn)考慮的問(wèn)題。DBCTC算法通過(guò)以下措施降低能耗，高效構(gòu)建柵欄：①在構(gòu)建有向柵欄的節(jié)點(diǎn)集合中，由前一個(gè)節(jié)點(diǎn)根據(jù)其目標(biāo)圓確定下一個(gè)節(jié)點(diǎn)的目標(biāo)位置，不同的節(jié)點(diǎn)有不同的目標(biāo)位置。而NSDBC算法只把前一個(gè)節(jié)點(diǎn)感知區(qū)域內(nèi)最大的橫坐標(biāo)位置作為下一節(jié)點(diǎn)的坐標(biāo)位置。②DBCTC算法根據(jù)節(jié)點(diǎn)的運(yùn)動(dòng)能耗和柵欄增益長(zhǎng)度的比值選擇移動(dòng)節(jié)點(diǎn)運(yùn)動(dòng)到目標(biāo)位置。而NSDBC算法只選擇運(yùn)動(dòng)能耗最小的節(jié)點(diǎn)運(yùn)動(dòng)到目標(biāo)位置。

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

3　仿真結(jié)果

本文運(yùn)用MATLAB 7.0對(duì)此算法進(jìn)行仿真，區(qū)域大小為300 m×200 m。每組實(shí)驗(yàn)數(shù)據(jù)采用重復(fù)50次獨(dú)立實(shí)驗(yàn)取平均值的方式獲得。如果沒(méi)有特別指明，實(shí)驗(yàn)的默認(rèn)參數(shù)為K =2，r=10 m，a=π/4，γ=0.006，J1=3.6 J/m，J1=1.8 J/m。目前為止，最新的有向柵欄構(gòu)建算法研究是文獻(xiàn)［10］和［14］，我們選取了文獻(xiàn)［10］的strong optimal算法，文獻(xiàn)［14］中的NSDBC算法與本文DBCTC算法進(jìn)行了仿真比較。主要的性能參數(shù)是：形成的柵欄的總能耗，平均能耗，節(jié)點(diǎn)數(shù)。默認(rèn)情況下取100次實(shí)驗(yàn)的平均值。

在默認(rèn)參數(shù)下，給定相同的初始投撒結(jié)果，DBCTC算法如圖5所示。NSDBC算法的形成的柵欄如圖6所示，strongoptimal算法的形成的柵欄如圖7所示。NSDBC算法僅用60～70個(gè)節(jié)點(diǎn)就構(gòu)建了2條柵欄，而strongoptimal算法需要用110～125個(gè)節(jié)點(diǎn)才能構(gòu)建兩條柵欄。DBCTC算法用了80～90個(gè)節(jié)點(diǎn)形成兩條柵欄。DBCTC算法的節(jié)點(diǎn)數(shù)要比NSDBC算法多，這是因?yàn)镹SDBC算法僅僅以±α/2或者π±α/2為目標(biāo)方向。而DBCTC算法目標(biāo)方向是不確定的。

圖5　DBCTC算法

圖6　NSDBC算法

圖7　strong optimal算法

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

由于strongoptimal算法對(duì)于節(jié)點(diǎn)數(shù)量的要求比較高，在保證能形成柵欄的前提下，本文采用0.003作為起始節(jié)點(diǎn)密度進(jìn)行仿真比較，其余實(shí)驗(yàn)參數(shù)均為默認(rèn)參數(shù)。仿真結(jié)果如圖8～圖10所示。隨著節(jié)點(diǎn)密度的增加，會(huì)有更多的節(jié)點(diǎn)位于目標(biāo)圓中，從而使得DBCTC算法中不需要移動(dòng)的點(diǎn)增加，而轉(zhuǎn)動(dòng)所消耗的能量要遠(yuǎn)小于移動(dòng)，這導(dǎo)致DBCTC算法的平均能耗和總能耗會(huì)隨密度的增加而減小，圖8和圖10表現(xiàn)了這一趨勢(shì)。同時(shí)，由于移動(dòng)節(jié)點(diǎn)對(duì)柵欄的期望貢獻(xiàn)要略大于只進(jìn)行轉(zhuǎn)動(dòng)的節(jié)點(diǎn)，從而只需要更少的節(jié)點(diǎn)構(gòu)建柵欄，所以當(dāng)節(jié)點(diǎn)密度增加時(shí)，DBCTC算法的節(jié)點(diǎn)個(gè)數(shù)會(huì)略微增加，圖9表現(xiàn)了這一趨勢(shì)。此外，由于DBCTC算法引入了目標(biāo)圓，使得每一個(gè)節(jié)點(diǎn)的目標(biāo)位置不在固定，因而在最優(yōu)情況下DBCTC算法中每一個(gè)節(jié)點(diǎn)相交于NSDBC算法均少移動(dòng)了一個(gè)感知距離的長(zhǎng)度，但實(shí)際情況中，無(wú)法達(dá)到最優(yōu)情況，而圖10表明，相同密度下，DBCTC算法的平均能耗要比NSDBC算法低15 J～20 J，即每個(gè)節(jié)點(diǎn)平均少移動(dòng)大約0.4～0.6個(gè)感知距離。

圖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)平均能耗

3.2柵欄數(shù)的影響

柵欄數(shù)K的影響如圖11～圖13所示。從圖11中可以看出，3種算法的節(jié)點(diǎn)總能耗均隨K增大而增大，當(dāng)K>3時(shí)，隨著K的增大，DBCTC算法的節(jié)點(diǎn)總能耗將越來(lái)越低于同等條件下strong optimal算法與NSDBC算法中的節(jié)點(diǎn)總能耗。從圖12中可以看出，隨著K的增大，DBCTC算法形成柵欄所需的節(jié)點(diǎn)數(shù)隨K的增長(zhǎng)率明顯低于同等條件下的strong optimal算法，但高于NSDBC算法。圖13表明，隨著K的增大，而DBCTC算法的節(jié)點(diǎn)平均能耗的上升幅度遠(yuǎn)低于strong optimal算法與NSDBC算法。相比strong optimal算法，NSDBC算法，DBCTC算法的平均能耗分別下降了83%，60%。

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

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

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

3.3傳感器感知角度的影響

傳感器感知角度改變時(shí)，對(duì)柵欄構(gòu)建的影響主要在于改變了單個(gè)節(jié)點(diǎn)對(duì)柵欄的貢獻(xiàn)。NSDBC算法中大部分節(jié)點(diǎn)對(duì)柵欄的貢獻(xiàn)都是固定的，因而無(wú)法有效利用感知角度增加時(shí)節(jié)點(diǎn)感知區(qū)域增加的部分，從而導(dǎo)致其總能耗、平均能耗以及節(jié)點(diǎn)數(shù)均變化很小，如圖14～圖16所示。

圖14　感知角度VS總能耗

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

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

而DBCTC則有效的利用了感知角度增加時(shí)節(jié)點(diǎn)感知區(qū)域增加的部分，因而，雖然在低感知角度下，DBCTC算法中單個(gè)節(jié)點(diǎn)對(duì)柵欄的貢獻(xiàn)要小于NSDBC算法，但隨著感知角度的增加，DBCTC算法中單個(gè)節(jié)點(diǎn)對(duì)柵欄的貢獻(xiàn)會(huì)逐漸增加，直至超過(guò)NSDBC算法，這就導(dǎo)致了圖15中低感知角度下DBCTC的節(jié)點(diǎn)個(gè)數(shù)比NSDBC算法高，而隨著角度的增加，DBCTC的節(jié)點(diǎn)個(gè)數(shù)要逐漸減少直至低于NSDBC算法。同時(shí)其降低的幅度要大于strong op?timal算法，可知DBCTC算法對(duì)單個(gè)節(jié)點(diǎn)的利用要更充分。

仿真結(jié)果表明，DBCTC算法大大降低了形成柵欄節(jié)點(diǎn)能耗，提高了算法效率，增加了柵欄壽命。

4　結(jié)論

本文主要研究有向強(qiáng)柵欄覆蓋問(wèn)題，提出DBCTC算法，利用目標(biāo)圓確定節(jié)點(diǎn)的目標(biāo)位置。從附近節(jié)點(diǎn)中選擇能耗比最少的節(jié)點(diǎn)運(yùn)動(dòng)到目標(biāo)位置，從而分布式構(gòu)建有向強(qiáng)柵欄。仿真結(jié)果證明DBCTC算法可以用大大降低能耗，更為高效節(jié)能地構(gòu)建有向K-柵欄覆蓋。

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

參考文獻(xiàn)：

［1］Tao D，Wu T Y. A Survey on Barrier Coverage Problem in Direc?tional Sensor Networks［J］. IEEE Sensors Journal，2015，15（2）：876-885.

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

［3］Wang Z B，Chen H L，Cao Q，et al. Fault Tolerant Barrier Cover?age in Wireless Sensor Networks［C］. Proceedings of IEEE INFO? COM，Toronto，Canada，2014：1869-1877.

［4］He S B，Chen J M，Li X，et al. Cost-effective Barrier Coverage by Mobile Sensor Networks［C］. Proceedings of IEEE INFOCOM. Or?lando，USA，2012：819-827.

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

［6］Ma H，Yang M，Li D，et al. Minimum Camera Barrier Coverage in Wireless Camera Sensor Networks［C］. Proceeding of IEEE INFO?COM，Orlando，USA，2012：217-225.

［7］Zhang L，Tang J，Zhang W. Strong Barrier Coverage With Direc?tional Sensors［C］. Proceedings of IEEE Globe Com，Honolulu，USA，2009：1-6.

［8］Wang Y，Cao G. Barrier Coverage In Camera Sensor Networks ［C］. Proceedingof ACM MobiHoc，Paris，F(xiàn)rance，2011：12.

［9］Wang Z B，Liao J L，Cao Q，et al. Barrier Coverage in Hybrid Di?rectional Sensor Networks［C］. Proceedings of IEEE MASS. Hang?hou，China，2013：222-230.

［10］Wang Z B，Liao J L，Cao Q，et al. Achieving k-barrier Coverage in Hybrid Directional Sensor Networks［J］. IEEE Transactions on Mobile Computing，2014，13（7）：1443-1455.

［11］Shih K P，Chou C M，Liu I H，et al. On Barrier Coverage in Wire?less Camera Sensor Networks［C］. Proceeding of 24th IEEE AT?MA，Perth，England，2010：873-879.

［12］陶丹，陳后金.視角受限傳感器網(wǎng)絡(luò)強(qiáng)柵欄覆蓋判定算法［J］.北京交通大學(xué)學(xué)報(bào)，2010，35（5）：8-11.

［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ò)柵欄覆蓋增強(qiáng)算法［J］.傳感技術(shù)學(xué)報(bào)，2015，28（7）：10511057.

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

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

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

A Construction Scheme for Directional Barrier Based on Target Circle*

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

Abstract：K-barrier coverage is one of the hot spot in directional wireless sensor network. This paper proposes a dis?tributing directional barrier construction based on target circle（DBCTC）. Two novel models：target circle and ener?gy consumption ratio are created for the first time. The center of target circle is just the point with maximum X coor?dinate within the sensing region of the preceding node. Its radius is always the sensing radius. The energy consump?tion ratio is the ratio of actuating energy consumption to barrier gain. Target location is determined by target circle. The mobile node with minimum energy consumption ratio moves to target next node location. Simulation results show this method could decrease 60% energy consumption than other method.

Key words：Directional barrier coverage；target circle；target workingdirection；next node；energy consumption ratio

doi：EEACC：6150P；6210；723010.3969/j.issn.1004-1699.2016.03.015

收稿日期：2015-09-28修改日期：2015-11-23

中圖分類號(hào)：TP273

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1004-1699（2016）03-0390-07