基于蜂窩網格的確定性節點部署算法

趙小敏，蔣雙雙

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

?

基于蜂窩網格的確定性節點部署算法

趙小敏，蔣雙雙

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

摘要：如何有效的部署節點是傳感器網絡應用系統設計中首要考慮的問題，它直接關系到系統的成本和服務質量.針對含有透明障礙物環境中無線傳感器網絡的節點部署問題，提出一種基于蜂窩網格的確定性節點部署算法CG-deployment，通過計算幾何法確定并修復由于透明障礙物的存在而造成的覆蓋空洞.仿真結果表明：在對目標監測區域實現全覆蓋的情況下，CG-deployment算法所需要的節點數目比DT-Score算法和隨機部署方法更少，有效的節約了網絡的部署成本.

關鍵詞：蜂窩網格；無線傳感器網絡；節點部署；障礙物

無線傳感器網絡(Wireless sensor networks, WSN)是由部署在監測區域內大量的微型無線傳感器節點組成，已在工業監控、環境監測、智能家居等領域有著廣泛的應用[1-2].WSN節點如何部署，關系到是否可以有效感知所關心的區域、部署成本高低和如何避免覆蓋盲區等重要問題，它直接影響著無線傳感器網絡的服務質量，是建立無線傳感器網絡實際應用系統必須要解決的關鍵問題之一.目前大多數的節點部署研究都是考慮理想環境的情況，然而在真實的環境中，例如樹、墻、建筑物等障礙物都會影響節點之間的網絡連通性，從而造成覆蓋空洞.目前對有障礙物遮擋環境中傳感器節點的部署研究較少.DT-Score[3]是一種節點部署的啟發式貪婪算法，用來最大化障礙物環境下的覆蓋率.DT-Score算法分為兩階段，第一階段沿邊界和障礙物等高線部署節點，以避免死角無法覆蓋，第二階段根據Delaunay三角剖分在未覆蓋區域添加傳感器節點，直到滿足覆蓋率或達到限定的節點覆蓋的最大數目.TAN等[4]提出基于計算幾何的確定性完全覆蓋部署方法，適用于規則或不規則的障礙物和區域.文獻[5-6]提出在存在透明和不透明的障礙物環境下，利用計算幾何中平面掃描算法(Sweep line algorithm)和雙向鏈接邊表(DCEL)，評估目標區域的覆蓋情況并提出冗余節點的檢測和消除方法.DVFA(Distributed virtual forces algorithm)算法[7]提出在存在障礙物的情況下，將障礙物視為排斥力，來重新部署傳感器節點.KHOUFI等[8]提出一種簡單的基于二維投影的方法來最小化覆蓋區域所需的無線傳感器節點的數目.

針對含有障礙物遮擋環境下的WSN節點部署問題，將網絡的覆蓋問題抽象成圓覆蓋問題，提出一種基于六邊形蜂窩網格的確定性節點部署算法，并利用計算幾何的方法確定并修復覆蓋空洞.算法假設已知障礙物的具體位置，首先用正六邊形對平面進行無縫拼接，正六邊形外接圓的圓心為節點部署的位置，由于透明障礙物的存在，落入透明障礙物內部的節點無法與其他節點進行通信，從而產生覆蓋空洞.對被屏蔽節點的內接正六邊形與障礙物進行布爾差運算，得到近似空洞的多邊形，找到其對應最小覆蓋圓，再確定新增節點的位置，最終實現目標區域的完全覆蓋.

1部署問題分析描述

1.1　感知模型

假定監測區域A為二維平面，所有節點同構且不可移動.各節點感知半徑為rs，通信半徑為rc，為了保證網絡的連通性rc≥2rs，即保證網絡在充分覆蓋時是連通的.

節點感知模型為二元感知模型，該模型是一個以傳感節點為圓心，節點監測半徑rs為模型半徑的一個概率圓.即以Si節點為感知區域圓心，以節點的監測半徑rs作為圓形感知區域半徑.若事件P(x，y)發生在圓形感知區域內，則被監測的概率Cp(Si)為1，否則概率為0.d(P，Si)為節點Si到P(x，y)的歐式距離.其公式為

(1)

1.2　部署問題描述

節點部署方法一般有確定性部署和自組織部署.前者是指手工部署節點，一般適合規模較小、環境狀況良好、人工可以到達的區域，其特點是環境已知、網絡相對固定，預先配置節點位置，并根據目標區域的具體情況確定網絡拓撲、傳感器節點密度和預定探測概率情況下的節點數目.已知含有障礙物的目標監測區域范圍確定且規模較小，決定采用確定性部署.障礙物分為透明障礙物(Transparentobstacles)和不透明障礙物(Opaqueobstacles)[5].如圖1所示，透明障礙物只阻礙節點間的通信，但不影響節點對目標區域的感知；不透明障礙物則阻礙節點間的通信，從而使節點喪失感知能力.下文只考慮透明障礙物的情形，所指的障礙物都是指透明障礙物，其位置和大小信息可從初始化配置文件中獲取.

假設目標監測區域為二維確定性區域，用A表示，含有透明障礙物n個，透明障礙物i所占的區域為Obsi，O=∪i=[1,n]Obsi表示障礙物的集合.需要節點監測的區域為A-O.提出一種基于蜂窩網格的部署算法(CG-depolyment，deploymentbasedoncellulargrid)，使得存在障礙物的目標監測區域內實現全覆蓋所需要的節點數目最少.

圖1　不同障礙物對傳感器節點感知的影響Fig.1　The influence of the sensors in a region containing transparent and opaque obstacles

2部署算法

2.1　基于蜂窩網格的初始化部署

圖2　基于蜂窩網格的初始化部署Fig.2　Initial deployment based on cellular grid

圖3　邊界最佳部署Fig.3　Optimal deployment along a border

圖4　6個交點構成蜂窩Fig.4　Cellular grid made of 6 points of intersection

2.2　修復覆蓋空洞

假設空洞邊緣節點1~7互為感知鄰居，這些節點互相連接圍成空洞，a~g為空洞邊緣交叉點，如圖5所示.由空洞邊緣交叉點所圍成的多邊形，近似于空洞，包含多邊形最小圓的圓心坐標就是修復空洞的節點部署的最佳位置.

圖5　覆蓋空洞的界定Fig.5　Definition of coverage holes

這里的覆蓋空洞有兩種，一是節點放置在目標檢測區域的外部而造成的空洞，二是節點放置在障礙物內部造成的空洞.由于環境中含有透明障礙物，第二種空洞邊緣交叉點是由空洞邊緣節點和障礙物共同圍成.初始化部署時假設障礙物不存在，基于蜂窩網格劃分，節點分布均勻.如圖6所示，深灰色區域為近似于空洞的多邊形，近似于覆蓋空洞大小的多邊形PL可以看成Nobs對應的Hobs與障礙物Obsi之間的布爾差運算所得到的結果，深灰色區域就是PL的頂點坐標所圍成的多邊形，PL.

圖6　由障礙物造成的覆蓋空洞Fig.6　The coverage holes caused by transparent obstacles

對于第一種空洞情況，如圖7(a)所示，AB為邊界，節點C位于目標檢測區域的外部，做節點位置C到邊界AB的正交投影，投影點為C′，此時C′為節點重新部署的位置.如圖7(b)所示，當節點C正交投影點落在目標監測區域外部時(這種情況發生在右上角最后一個節點的部署上)，以C為圓心的圓與上邊界交于A點，B為邊界的頂點，此時線段AB的中點C′作為節點重新部署的位置.對于第二種空洞，首先確定近似覆蓋空洞大小的多邊形PL，再確定包含PL的最小圓圓心O的坐標(x，y)及半徑r0.由于PL是其對應的Hobs的一部分，所以r0肯定小于等于感知半徑.如圖8所示，若圓心O位于障礙物ABCD的內部(不包括邊界)，則分別做圓心O到障礙物邊(到圓心O的距離小于感知半徑的邊)的正交投影點O′，O′為新增節點部署的位置.反之，若圓心O在障礙物外部，此時圓心O為新增節點部署的位置.

圖7　投影的兩種情況Fig.7　Two cases of projection

判斷交點的凹凸性是關鍵，根據不同的相交情況分為四種情況，如圖9所示.

圖8　圓心在障礙物內部的情況Fig.8　Center of the circle inside the transparent obstacle

圖9　交點的凹凸性Fig.9　Definition of concave & convex point of intersection

算法1確定近似空洞的多邊形.

1) 對于A多邊形的每條邊e1和B多邊形的每條邊e2，如果e1和e2存在交點，則將交點順序插入兩個多邊形頂點的集合中，使得A多邊形頂點的集合及其交點成逆時針排列，B多邊形頂點集合及其交點成順時針排列.

2) 從A多邊形的某一交點I出發，根據A多邊形中以該交點為終點的矢量與B多邊形中以該交點為起點的矢量判定該點的凹凸性.若為凸點，則沿B多邊形遍歷，若為凹點，則繼續沿著A多邊形遍歷.每遇到一個凸點，轉向另一個多邊形，否則繼續遍歷當前多邊形，在遍歷的過程中，A多邊形的遍歷方向始終保持逆時針，B多邊形的遍歷方向始終保持順時針.直到再次遇到交點I，結束本次遍歷.從I開始至I結束的多邊形即為差集的一部分.重復上述過程，直到遍歷完所有交點，每次循環都是A與B的差值的結果.

3) 上一步驟所得到的差集?C即為空洞邊緣交叉點所圍成的多邊形的集合，包含多邊形最小圓的圓心為空洞的填補點.

算法2確定包含多邊形的最小圓.

1) 確定多邊形中兩兩頂點之間距離最遠的線段為長軸L.

2) 計算多邊形各頂點到長軸的距離，最遠點與長軸構成三角形ABC，外接圓為O，半徑為r.

3) 計算多邊形各頂點到外接圓圓心的距離，若距離的最大值小于r，則該外接圓為包含多邊形的最小圓.反之，則轉至步驟4).

4) 取步驟3)距離最大值的點p，計算點p到三角形ABC各頂點的距離，p點取代距離最近的點作新的三角形，計算最小外接圓，返回第2)步繼續迭代.

5) 獲得最小圓的半徑r0和圓心O坐標(x0，y0)后，判斷圓心與離它最近的障礙物Obsi之間的位置關系，若圓心在在障礙物外部(包括邊界上)，則算法結束，圓心的位置即為新增節點部署位置，反之，轉至下一步.

6) 若圓心O位于障礙物內部，則做圓心到距圓心距離小于感知半徑的障礙物邊的正交投影，投影點為O′，此時O′的位置為新增節點部署的位置.

3仿真實驗與結果分析

為了驗證算法的有效性，假設在100 m×100 m的監測區域內，使用matlab對無障礙物和含有障礙物的情況分別進行節點部署仿真實驗，將CG-depolyment算法與DT-Score算法[3]以及隨機部署Random算法做比較，實驗結果都為50次仿真實驗的平均值.

在無障礙物的情況下，隨著感知半徑的變化，達到指定的覆蓋率所需的節點數目如圖10所示.在同一覆蓋率要求下，隨機部署算法需要的節點數目最多，由于節點部署的隨機性，很難達到100%的覆蓋率要求.即使在100%覆蓋率要求的情況下，CG-depolyment算法和DT-Score算法所需的節點數也比覆蓋率要求只為90%的隨機部署算法所需的節點數目少.在覆蓋率要達到100%的要求下，CG-depolyment算法比DT-Score算法所需的節點數目少.圖11為感知半徑為3 m，覆蓋率為100%時CG-depolyment算法和DT-Score算法的部署結果.DT-Score算法實現完全覆蓋所需的節點數目為531個，而CG-depolyment算法僅需460個節點就可達到完全覆蓋，減少了13.4%.在無障礙物的情況下，CG-depolyment算法實質上是基于蜂窩網格的傳感器節點部署算法，充分利用了每個傳感器節點的覆蓋圓盤，即節點之間的重疊面積最小，使得目標區域內節點最少.

圖10　無障礙物時感知半徑不同所需節點數目變化情況Fig.10　The number of sensor nodes change with sensing radius when there is no obstacle

圖11　無障礙物時的節點部署結果Fig.11　The result of sensors deployment configured without obstacles

假設監測區域內含有10個障礙物，其位置信息可以從初始化的配置文件讀取.當傳感器節點的感知半徑為3 m，覆蓋率為100%要求下，CG-depolyment算法和DT-Score算法的部署結果如圖12所示.在有障礙物的環境中，DT-Score算法實現完全覆蓋需要472個節點，而CG-depolyment算法只需448個節點即可實現完全覆蓋，節點數減少了5.1%.當傳感器感知半徑不同時，實現指定的覆蓋率所需節點數目的變化情況如圖13所示.CG-depolyment算法達到完全覆蓋所需要的節點數目少于DT-Score算法，也遠小于隨機算法達到90%覆蓋率所需節點數.在CG-depolyment算法中，當傳感器節點在平面內呈正三角形覆蓋，節點之間構成正六邊形蜂窩網格，有效覆蓋率達到最高.采用計算幾何的方法能快速求出Nobs對應的Hobs與障礙物Obsi之間的布爾差，得到近似空洞的多邊形，再求出覆蓋近似空洞的多邊形的最小圓，圓心即為新增節點部署的位置.CG-depolyment算法與DT-Score算法相比,算法簡單，易于實現，而DT-Score算法在初始邊界線部署完成后，每次選取候選節點都需要進行Delaunay三角剖分，時間復雜度較高.CG-depolyment算法使得節點在目標監測區域內分布均勻，在使用較少的節點數時就可以達到最優的覆蓋率，大大降低了部署成本.

圖12　存在透明障礙物時節點部署結果Fig.12　The result of sensors deployment configured with transparent obstacles

圖13　存在障礙物時感知半徑不同所需節點數目變化情況Fig.13　The number of sensor nodes change with sensing radius when configured with obstacles

4結論

針對含有障礙物環境中的節點部署問題，提出

了一種基于蜂窩網格的確定性部署算法CG-deployment，修復了由于透明障礙物的存在而造成的覆蓋空洞問題，并且確定近似空洞的多邊形的最小覆蓋圓的圓心，通過部署新增的傳感器節點，使得節點對目標監測區域達到100%完全覆蓋.下一步的研究工作主要考慮網絡動態運行中的空洞修復以及如何進一步延長網絡生命周期等問題.

參考文獻：

[1]周曉，李杰，邊裕挺.基于無線傳感器網絡的環境溫度監測系統設計[J]．浙江工業大學學報，2013，41(4)：440-443．

[2]周曉，邊裕挺，李杰．基于Android智能終端的WSN監控系統[J]．浙江工業大學學報，2013，41(5)：558-5610．

[3]WU C H, LEE K C, CHUNG Y C. A delaunay triangulation based method for wireless sensor network deployment[J]. Computer communications，2007，30(14)：2744-2752．

[4]TAN H, WANG Y, HAO X, et al. Arbitrary obstacles constrained full coverage in wireless sensor networks[M]. Halifax: Springer Berlin Heidelberg，2010：1-10．

[5]FOTOUHI A, RAZZAZI M. Redundancy and coverage detection in wireless sensor networks in the presence of obstacles[C]//Proceedings of the 34th International Convention on MIPRO. Opatija: IEEE，2011：541-546．

[6]RAZZAZI M, FOTOUHI A. Coverage of wireless sensor networks in the presence of transparent obstacles[C]//Proceedings of International Conference on Software, Telecommunications and Computer Networks (SoftCOM). Split: IEEE，2010：209-213．

[7]MAHFOUDH S, KHOUFI I, MINET P, et al. Relocation of mobile wireless sensors in the presence of obstacles[C]//Proceedings of 20th International Conference on Telecommunications (ICT). Casablanca: IEEE，2013：1-5．

[8]KHOUFI I, MINET P, LAOUITI A, et al. A simple method for the deployment of wireless sensors to ensure full coverage of an irregular area with obstacles[C]//Proceedings of the 17th ACM International Conference on Modeling, Analysis and Simulation of Wireless and Mobile Systems. New York: ACM，2014：203-210．

[9]ROY S B, DAS G, DAS S. Computing best coverage path in the presence of obstacles in a sensor field[M]. Halifax: Springer Berlin Heidelberg，2007：577-588．

(責任編輯：劉巖)

Deterministic node deployment algorithm based on cellular grid

ZHAO Xiaomin, JIANG Shuangshuang

(College of Computer Science and Technology, Zhejiang University of Technology, Hangzhou 310023, China)

Abstract:How to effectively deploy sensor nodes is a primary consideration in wireless sensor network application system, which influences the cost and quality of service. For wireless sensor network node deployment problem in a region containing transparent obstacles, the paper proposed a node deployment method, named as CG-deployment, based on cellular grid. The algorithm uses computational geometry techniques to identify and fix coverage hole caused by transparent obstacles. The simulation results show that, in the case of the target to achieve full coverage of the monitoring area, the proposed algorithm requires fewer nodes than DT-Score and random deployment methods. It can effectively save the cost of network deployment.

Keywords:cellular grid; wireless sensor network; node deployment; obstacles

中圖分類號：TP391

文獻標志碼：A

文章編號：1006-4303(2016)01-0039-06

作者簡介：趙小敏(1976—)，男，浙江文成人，副教授，博士，研究方向為無線傳感器網絡和信息安全，E-mail：zxm@zjut.edu.cn．

收稿日期：2015-09-04