一種基于目標圓的有向強柵欄構建算法*
2016-05-03 12:35:26車志聰范興剛徐俊超浙江工業大學計算機科學與技術學院杭州310023
傳感技術學報 2016年3期
車志聰，范興剛，徐俊超（浙江工業大學計算機科學與技術學院，杭州310023）
?
一種基于目標圓的有向強柵欄構建算法*
車志聰，范興剛*，徐俊超
（浙江工業大學計算機科學與技術學院，杭州310023）
摘要：K-柵欄覆蓋是有向傳感器網絡覆蓋控制的研究熱點之一。提出一種基于目標圓的分布式有向強柵欄構建方法（DBCTC）。首次構建了節點目標圓和能耗比2個模型。以節點感知區域內橫坐標最大的點為圓心，以感知半徑為半徑的圓就是目標圓。節點的運動能耗和柵欄增益的比值就是能耗比。前一個節點根據目標圓模型選擇后一個節點的最佳目標位置。從附近移動節點中選擇能耗比最少的移動節點構建有向強柵欄。仿真結果證明，該柵欄構建方法比其他算法降低60%左右的能耗。
關鍵詞：有向柵欄覆蓋；目標圓；節點目標方向；下一個節點，能耗比
項目來源：“十二五”國家科技支撐計劃項目（2012BAD10B01）
有向傳感器，如視頻傳感器，超聲傳感器和紅外傳感器等，在諸多領域有著廣泛的應用，如可將傳感器節點部署在重要管道沿線以監視針對管道的破壞活動，以及在敵營周邊布設無線傳感器節點來監視敵方的兵力部署和武器配備情況等。在上述列舉的應用中，有向傳感器節點被部署于感興趣區域的邊界，對進入感興趣區域的移動目標進行檢測，這種技術被稱為柵欄覆蓋。如何實現柵欄覆蓋是有向傳感網絡一個研究熱點［1］。
利用節點的移動能力構建全向柵欄已有一些研究工作。班冬松研究了全向移動傳感器網絡K-柵欄覆蓋問題，提出了一種能量高效的柵欄覆蓋構建算法CBIGB［2］。Wang研究了節點存在定位誤差時的柵欄覆蓋問題［3］。He研究了多次移動節點構建柵欄覆蓋［4］。范興剛研究了全向強柵欄構建，提出了PMNSB算法［5］。在有向柵欄研究中，Ma研究了最少的有向視頻節點組建柵欄問題［6］；Zhang利用有向節點的轉動能力構建強柵欄［7］；Wang選擇有向節點組建視線柵欄，構建有向傳感陣列監視入侵者［8］；Wang研究了混合有向網絡的柵欄覆蓋［9-10］，根據網絡拓撲構建權重柵欄圖WBG，再運用頂點不相交的路徑算法構造K-柵欄。以上這些方法都是集中式的，都需要知道整個網絡的拓撲。Shih研究了分布式柵欄構建算法，利用可能柵欄行中的鄰居節點通過柵欄信息構建柵欄［11］。Tao利用鄰居節點的位置信息，選擇具有最多鄰居的節點構建柵欄［12］。
Amac基于移動能耗和轉動能耗，研究了有向網絡的覆蓋增強［13］。利用附近節點之間的位置關系，分布式的選擇節點構建柵欄。我們研究了NSDBC算法［14］。在此基礎上，本文研究如何利用鄰居節點目標圓，根據運動能耗與柵欄增加的長度比值，調度節點的運動，節能高效的構建有向強K-柵欄覆蓋，提出一種基于目標圓的分布式有向強柵欄構建方法DBCTC （Distributing Directional Strong Barrier Construction Based on Target Circle）。主要貢獻如下：①首次創建了節點目標圓模型，節點根據自己的目標圓和周圍的移動節點，確定下一個節點的目標位置；②提出了能耗比模型，每一個節點根據能耗比選擇可移動節點運動到目標位置構建有向強柵欄；
本文余下章節安排如下：第1節描述網絡模型；第2節詳細介紹DBCTC方法；第3節通過仿真實驗對提出的算法進行性能評估；第4節總結全文并介紹下一步工作。
1 相關模型和定義
有向傳感器節點方向可調感知模型可以采取四組表示
圖1 可旋轉有向傳感器的傳感模型
研究有向柵欄問題之前，有如下假設：①所有傳感器的感知半徑和感知角度均相同。②所有傳感器的轉動能耗和移動功耗均相同，參考文獻［15］，傳感器每轉動180°耗能為1.8 J，每移動1 m耗能為3.6 J。③傳感器監視范圍內的信號強度相同，且能在范圍內以100%的可能性監測到事件。
有向節點的目標位置，有向節點運動能耗和節點密度定義分別參考文獻［14］中的定義1，2，3。
定義1有向節點的目標感知方向。移動到目標位置的有向節點的感知方向就是有向節點的目標感知方向。有向節點的目標感知方向由移動到該位置的移動節點的初始感知方向決定。
定義2目標圓。以一個節點感知區域內橫坐標最大的點為圓心，以r為半徑的圓就是目標圓。目標圓外的移動節點只要移動到目標圓上，再轉動有限的角度，就可能與前一個節點形成柵欄鏈接。
定義3能效比。假設移動節點的運動能耗為Ei，柵欄增加的長度為li，則能效比為λi=Ei/li，能效比越小，形成柵欄耗費的能量越小，柵欄形成算法越高效。
有向強柵欄的定義見文獻［10］的定義6，我們研究的問題就是：在狹長區域中，隨機部署的有向移動節點密度為γ的情況下，如何分布式地調度移動節點，以盡量少的運動能耗構建有向強柵欄覆蓋。
2 基于目標圓的分布式有向強柵欄構建算法（DBCTC）
Wang［10］提出了optimal scheme算法，構建加權圖，采用頂點不重復的K條路徑圖論算法找到形成柵欄的目標位置，然后移動節點和這些目標位置進行最佳匹配。運用節點之間的位置關系，在形成柵欄的節點集合中，按照從左到右的節點順序，按照節點對柵欄貢獻盡量最大原則，由前一個節點確定節點的目標位置，并選擇能耗最少的節點移動到目標位置。從而構建有向強柵欄。這是分布式基于鄰居節點運動的分布式有向柵欄構建算法（NSDBC）［14］。
另一方面，以節點感知區域內橫坐標最大的點為圓心，以r為半徑的圓就是目標圓，移動節點只要移動到這個目標圓上，再轉動有限的角度，就可以與前一個節點形成柵欄鏈接。這就是DBCTC算法的基本思路。
2.1理論分析
要形成柵欄，重點和難點是確定節點目標位置。有向節點的目標位置由形成柵欄的前一個節點決定。
在第i(i≥1)個節點調度完畢后，若在其感知區域內部存在節點，橫坐標最大的節點就是第i+1個節點的目標位置。例如，在圖2（a）、2（b）中，節點A中，節點C的橫坐標比節點D大，則節點C的坐標就是下一個節點的坐標，圓心為C的虛扇形就是第i+1個節點的目標位置。在圖2（a）中，α/2≤β≤π，節點C的目標方向為β=α/2處。在圖2（b）中，π<β<2π-α/2，節點C的目標方向為β=2π-α/2。
對于節點感知區域外的移動節點，則要構造目標圓來確定節點的目標位置。以感知區域內橫坐標最大的點為圓心，以r為半徑，構造目標圓。如果目標圓內有移動節點，下一節點的目標位置就是其坐標，這個節點再以最小的轉動角度調整感知方向，使其與前一個節點形成柵欄銜接。例如，在圖2（c）中，節點A中沒有節點，則以節點A的感知區域內，找到橫坐標最大的堤岸B，以點B為圓心構造節點A的目標圓，節點C在目標圓內，則節點C的坐標就是下一個節點的目標位置，其目標感知方向為紅色的虛線扇形。
由幾何知識可知，兩點之間的直線距離最短，對于目標圓外的移動節點，移動節點與目標圓的圓心的連線與目標圓的交點就是下一節點目標位置。移動節點沿著與目標圓圓心的連線，用最短的移動距離與前一個節點形成柵欄銜接。
圖2 節點的選擇
例如，在圖2（d）中，節點A的目標圓中沒有節點。移動節點D在目標圓外，BD與目標圓的交點C就是下一個節點的目標位置，其感知方向為紅色的虛線扇形。直線CB與X軸的夾角為θ，逆時針轉動的節點C，使其與目標感知方向一直。根據文獻［15］的定義2，計算節點C的運動能耗，這個時候柵欄增加的長度為l=xC-xA。
確定了節點的運動能耗和柵欄增益長度后，定義3給出了移動節點的能耗比。選出能效比最大的移動節點，移動到相應的目標位置，并以最小的轉動能耗調整感知方向，形成柵欄。
2.2算法的詳細過程
算法所用參數如表1所示。
表1 相關參數
DBCTC算法偽代碼如圖3，DBCTC算法具體步驟如下。
圖3 DBCTC算法偽代碼
Step 1：確定有向強柵欄的第一個節點。
選出預選區域中橫坐標最小的節點。若其橫坐標大于半徑r，則先令其向左平行移動至橫坐標等于半徑，并用最少的轉動能耗調整其感知方向，使其在[π-α/2,π+α/2]之間。若其橫坐標小于半徑，判斷扇形區域與左邊界x=0是否有公共點。若已有公共點，不進行轉動；若無公共點，選擇需要轉動角度較小的那個方向，轉至其扇形區域恰與左邊界x=0有一個公共點。該節點調度完畢后作為該條柵欄的第1個節點。
Step 2：確定下一個節點的目標位置。Step 2.1：前一個節點感知區域內的移動節點。
根據文獻［10］的定義1，判斷剩余節點中，是否有節點在第1個節點扇形區域內部。若有，選出扇形區域內橫坐標最大的節點作為第2個節點，不進行移動。只將其按照文獻［14］的式（1）調整方向角，并計算運動能耗。例如，在圖4中，節點A為第一個節點，圓心為B的虛扇形為第二個節點的目標位置，圓心為B的節點主要轉動到虛線位置即成為構建柵欄的第二個節點。
圖4感知區域內節點的選擇
Step 2.2：前一個節點感知區域外的移動節點。
Step 2.2.1：前一個節點目標圓內的移動節點。
若沒有節點在第1個節點扇形區域內部，則將其中橫坐標最大的點作為圓心，構造目標圓。如果有移動節點在目標圓內，下一節點的目標位置就是其坐標，以最小的轉動角度調整感知方向，使其與前一個節點形成柵欄銜接。計算移動節點構建柵欄的能耗，和柵欄的延伸長度，計算能耗比。
Step 2.2.2：前一個節點目標圓外的移動節點。
如果目標圓內沒有移動節點，對目標圓周圍的移動節點進行如下的操作：先確定移動節點形成柵欄的的目標位置和目標感知方向，移動節點和圓心的連線與目標圓的交點就是下一個節點的目標位置，再根據圖2確定節點的目標感知方向。計算移動節點構建柵欄的能耗，和柵欄的延伸長度，計算能耗比。
Step 3：確定移動節點的目標方向。
根據定義1確定節點的目標方向。
Step 4：確定移動節點的運動能耗。
根據文獻［14］的定義2確定節點的運動能耗。
Step 5：能耗比最高的可移動節點形成柵欄。
選擇能耗比最高的節點運動到目標位置，與前一個節點形成柵欄銜接。
Step 6：依次確定其余節點的目標位置，并選擇能耗比最高的節點移動。
Step 7：根據右邊界位置，確定形成第1條柵欄。第i+1個節點調度完后，判斷≥L是否滿足。若是，則該條柵欄已經形成完畢，轉入Step 8；若否，則轉到Step 2。
Step 8：構建其余K-1條柵欄。
若K>1，從剩余的移動節點中選擇橫坐標最小的節點，重復Step 2至Step 7的操作，形成第2條柵欄。同理，依次形成第3條、第4條…第K條柵欄，算法結束。
2.3算法的特點分析
如何降低柵欄形成過程中的能耗，是柵欄構建算法要重點考慮的問題。DBCTC算法通過以下措施降低能耗，高效構建柵欄：①在構建有向柵欄的節點集合中，由前一個節點根據其目標圓確定下一個節點的目標位置，不同的節點有不同的目標位置。而NSDBC算法只把前一個節點感知區域內最大的橫坐標位置作為下一節點的坐標位置。②DBCTC算法根據節點的運動能耗和柵欄增益長度的比值選擇移動節點運動到目標位置。而NSDBC算法只選擇運動能耗最小的節點運動到目標位置。
在柵欄形成過程中，設起始為n個節點，則需要先從n個節點中選中第1個節點，然后從（n-1）個節點中選出第2個節點…以此類推，直至柵欄形成完畢。因此在整體上，時間復雜度會隨著所需節點的增加而增加。最壞情況：在形成K條柵欄的過程中，若出現最壞情況，則形成K條柵欄用盡了投撒區域內全部n個節點。此時，時間復雜度O(n2)。
3 仿真結果
本文運用MATLAB 7.0對此算法進行仿真，區域大小為300 m×200 m。每組實驗數據采用重復50次獨立實驗取平均值的方式獲得。如果沒有特別指明，實驗的默認參數為K =2，r=10 m，a=π/4，γ=0.006，J1=3.6 J/m，J1=1.8 J/m。目前為止，最新的有向柵欄構建算法研究是文獻［10］和［14］，我們選取了文獻［10］的strong optimal算法，文獻［14］中的NSDBC算法與本文DBCTC算法進行了仿真比較。主要的性能參數是：形成的柵欄的總能耗，平均能耗，節點數。默認情況下取100次實驗的平均值。
在默認參數下，給定相同的初始投撒結果，DBCTC算法如圖5所示。NSDBC算法的形成的柵欄如圖6所示，strongoptimal算法的形成的柵欄如圖7所示。NSDBC算法僅用60～70個節點就構建了2條柵欄，而strongoptimal算法需要用110～125個節點才能構建兩條柵欄。DBCTC算法用了80～90個節點形成兩條柵欄。DBCTC算法的節點數要比NSDBC算法多，這是因為NSDBC算法僅僅以±α/2或者π±α/2為目標方向。而DBCTC算法目標方向是不確定的。
圖5 DBCTC算法
圖6 NSDBC算法
圖7 strong optimal算法
3.1節點密度的影響
由于strongoptimal算法對于節點數量的要求比較高，在保證能形成柵欄的前提下，本文采用0.003作為起始節點密度進行仿真比較，其余實驗參數均為默認參數。仿真結果如圖8～圖10所示。隨著節點密度的增加，會有更多的節點位于目標圓中，從而使得DBCTC算法中不需要移動的點增加，而轉動所消耗的能量要遠小于移動，這導致DBCTC算法的平均能耗和總能耗會隨密度的增加而減小，圖8和圖10表現了這一趨勢。同時，由于移動節點對柵欄的期望貢獻要略大于只進行轉動的節點，從而只需要更少的節點構建柵欄，所以當節點密度增加時，DBCTC算法的節點個數會略微增加，圖9表現了這一趨勢。此外，由于DBCTC算法引入了目標圓，使得每一個節點的目標位置不在固定，因而在最優情況下DBCTC算法中每一個節點相交于NSDBC算法均少移動了一個感知距離的長度，但實際情況中，無法達到最優情況，而圖10表明，相同密度下，DBCTC算法的平均能耗要比NSDBC算法低15 J～20 J，即每個節點平均少移動大約0.4～0.6個感知距離。
圖8 節點密度VS節點總能耗
圖9 節點密度VS形成柵欄所需的節點數
圖10 節點密度VS節點平均能耗
3.2柵欄數的影響
柵欄數K的影響如圖11～圖13所示。從圖11中可以看出，3種算法的節點總能耗均隨K增大而增大，當K>3時，隨著K的增大，DBCTC算法的節點總能耗將越來越低于同等條件下strong optimal算法與NSDBC算法中的節點總能耗。從圖12中可以看出，隨著K的增大，DBCTC算法形成柵欄所需的節點數隨K的增長率明顯低于同等條件下的strong optimal算法，但高于NSDBC算法。圖13表明，隨著K的增大，而DBCTC算法的節點平均能耗的上升幅度遠低于strong optimal算法與NSDBC算法。相比strong optimal算法，NSDBC算法，DBCTC算法的平均能耗分別下降了83%，60%。
圖11 柵欄數VS節點總能耗
圖12 柵欄數VS形成柵欄所需的節點數
圖13 柵欄數VS節點平均能耗
3.3傳感器感知角度的影響
傳感器感知角度改變時，對柵欄構建的影響主要在于改變了單個節點對柵欄的貢獻。NSDBC算法中大部分節點對柵欄的貢獻都是固定的，因而無法有效利用感知角度增加時節點感知區域增加的部分，從而導致其總能耗、平均能耗以及節點數均變化很小，如圖14～圖16所示。
圖14 感知角度VS總能耗
圖15 感知角度VS形成柵欄所需的節點個數
圖16 感知角度VS節點平均能耗
而DBCTC則有效的利用了感知角度增加時節點感知區域增加的部分，因而，雖然在低感知角度下，DBCTC算法中單個節點對柵欄的貢獻要小于NSDBC算法，但隨著感知角度的增加，DBCTC算法中單個節點對柵欄的貢獻會逐漸增加，直至超過NSDBC算法，這就導致了圖15中低感知角度下DBCTC的節點個數比NSDBC算法高，而隨著角度的增加，DBCTC的節點個數要逐漸減少直至低于NSDBC算法。同時其降低的幅度要大于strong op?timal算法，可知DBCTC算法對單個節點的利用要更充分。
仿真結果表明，DBCTC算法大大降低了形成柵欄節點能耗，提高了算法效率，增加了柵欄壽命。
4 結論
本文主要研究有向強柵欄覆蓋問題，提出DBCTC算法，利用目標圓確定節點的目標位置。從附近節點中選擇能耗比最少的節點運動到目標位置，從而分布式構建有向強柵欄。仿真結果證明DBCTC算法可以用大大降低能耗，更為高效節能地構建有向K-柵欄覆蓋。
概率感知模型是更符合實際的感知模型，如何節能高效地構建概率柵欄是下一步要研究的內容。
參考文獻：
［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］班冬松，溫俊，蔣杰，等.移動無線傳感器網絡K-柵欄覆蓋的構建算法［J］.軟件學報，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］王超，范興剛.一種高效強K—柵欄覆蓋構建算法［J］.傳感技術學報，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，France，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］陶丹，陳后金.視角受限傳感器網絡強柵欄覆蓋判定算法［J］.北京交通大學學報，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］任勇默，范興剛.一種有向傳感器網絡柵欄覆蓋增強算法［J］.傳感技術學報，2015，28（7）：10511057.
車志聰（1995-），男，本科生，主要研究領域為無線傳感器網絡；
范興剛（1974-），男，副教授，工學博士，研究領域為傳感器網絡，網絡通信、實時通信，分布式實時系統的設計，xgfan@zjut. edu.cn；
徐俊超（1995-），男，本科生，主要研究領域為無線傳感器網絡。
A Construction Scheme for Directional Barrier Based on Target Circle*
CHE Zhicong，FAN 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
中圖分類號：TP273
文獻標識碼：A
文章編號：1004-1699（2016）03-0390-07
