無線傳感器網絡動態覆蓋的CVT 算法*

劉志強，沈廼桐，毛 強，魏洪興

(1.內蒙古工業大學 信息工程學院，內蒙古 呼和浩特010051;2.北京航空航天大學 機械工程及自動化學院，北京100191)

0 引 言

網絡覆蓋是無線傳感器網絡研究的基本問題之一，它決定了無線傳感器網絡對目標區域的監測能力，通過覆蓋控制可以使資源得到合理配置。針對無線傳感器網絡的目標區域覆蓋問題，前人已做了一些深入的研究。文獻［1］提出了一種虛擬力算法(virtual force algorithm)，通過隨機節點的相互作用，實現網絡覆蓋范圍最大化。文獻［2］提出了一種基于蜂窩網格的傳感器節點部署算法。文獻［3］提出基于貪婪算法和Voronoi 圖的多媒體節點傳感方向調整方案，并為有效降低無線多媒體傳感器網絡能耗，提出一種基于多目標遺傳優化的節能覆蓋方法。文獻［4］基于Voronoi 圖特性和自適應有向傳感器節點，提出了一種分布式貪婪算法，它能夠提高有向無線傳感器網絡的覆蓋效率。文獻［5］針對二維靜態隨機分布的無線傳感器網絡，提出了一種通過Voronoi 圖判定網絡的覆蓋性能并在需要時添加覆蓋補救節點的方法。文獻［6］詳細介紹了集中式Voronoi 網格細分(centralized Voronoi tessellation，CVT)算法原理并給出了其在圖像壓縮、動物領地等方面中的應用。文獻［7］基于CVT 方法，提出了一種多傳感器節點網絡系統算法，通過調節節點分布密度函數使得各個傳感器節點按需求分布。然而，面對較復雜的無線傳感器網絡區域環境，無線傳感器網絡覆蓋問題需要進一步研究。

受Voronoi 圖和CVT 的啟發，本文提出了一種基于CVT 的無線傳感器網絡動態覆蓋算法。與文獻［6，7］通過改變區域分布密度的方法不同，本文結合Voronoi 圖特性，不斷縮放覆蓋區域邊界至目標覆蓋區域，系統協同調動各傳感器節點至目標位置，從而完成目標區域的覆蓋，仿真驗證了該算法的有效性和可行性。

1 基于CVT 的無線傳感器網絡覆蓋模型和算法分析

1.1 無線傳感器網絡覆蓋假設

本文主要針對二維平面區域的無線傳感器網絡覆蓋進行研究，網絡模型和基本假設如下:

1)各個傳感器節點初始隨機分布在任意二維封閉區域內。

2)各個傳感器節點能夠隨時確定自身的位置和方向，并能準確移動至指定的目標位置，能感知以節點為中心，以Rs為半徑的圓形區域。

3)各個傳感器節點是同構的，有相同的通信和覆蓋能力。

4)Rc≥2Rs，即各個傳感器節點的通信半徑Rc不小于2 倍的傳感器感知半徑Rs。

1.2 理論基礎

覆蓋程度C:是指在目標覆蓋區域內，所有傳感器節點覆蓋的總面積與目標區域總面積的比值。計算公式為

其中，A 為目標覆蓋區域總面積，N 為傳感器節點總數，Ai為第i 只傳感器節點的覆蓋面積。

有效覆蓋效率(effective coverage efficiency，ECE)用來衡量傳感器節點覆蓋范圍的利用率，用來反映有效覆蓋區域的情況，定義為目標覆蓋區域中，所有傳感器節點有效覆蓋區域的并集與所有傳感器節點覆蓋區域之和的比值，計算公式為

Voronoi 圖是由俄國數學家Georgy Fedoseevich Voronoi建立的空間分割算法，它是一種簡單有效的能夠將二維幾何區域用多邊形離散化的方法［8］。Voronoi 多邊形邊界是由任意兩點垂直平分線連接而成，可以對二維空間進行劃分，能夠表示各個節點的鄰近關系，Voronoi 圖具有勢力范圍特性、側向鄰近特性、線性特性、局域動態特性、與Delaunay 三角網對偶(dual of Delaunay triangulation)等特性［9］。

CVT:質心Voronoi 結構是Voronoi 結構的一種特殊形式。當Voronoi 結構的質心點與構造Voronoi 結構的初始點重合時，這樣的Voronoi 結構稱為質心Voronoi 結構［6］。

1.3 覆蓋區域模型分析

在一定區域內，根據實際環境需求，需要使各個無線傳感器網絡節點能夠感知目標區域信息，實現全局最優覆蓋。這里根據目標覆蓋區域邊界的變動與否，將覆蓋分為兩類:1)靜態邊界區域覆蓋;2)動態邊界區域覆蓋。這里主要分析無線傳感器網絡動態邊界區域覆蓋，以初始正方形邊界覆蓋區域縮放成長方形為例。

如圖1 所示，區域邊界用外側實線框線表示，其中最外層為初始覆蓋區域邊界，最內層實線框線為目標覆蓋區域邊界，中間的虛線框線為邊界迭代縮放過程中的覆蓋區域邊界。虛線圓代表傳感器節點的感知覆蓋范圍。

圖1 正方形邊界區域縮放為長方形邊界區域Fig 1 A rectangle border region scaled from square boundary region

1.4 無線傳感器網絡動態邊界區域覆蓋算法

1.4.1 算法分析

目標區域覆蓋控制算法描述如下:

1)設定初始目標覆蓋區域參數，如，節點區域初始覆蓋邊界、目標覆蓋區域邊界、目標覆蓋區域節點個數、各節點距離誤差閾值Tol、節點初始位置和方向(區域內隨機分布)、最大迭代次數等;

2)根據節點位置生成Voronoi 圖，并計算各個對應多邊形的質心;

3)計算各個節點距離邊界的距離矩陣D，D 中為節點距離各邊界的距離;

4)根據各個傳感器節點位置P 和迭代區域邊界，生成邊界虛擬節點R_P，并合并R_P 和P;

5)根據R_P 和P 生成對應的Voronoi 圖，并計算對應各個Voronoi 圖多邊形的質心Pc;

6)用質心位置Pc更新節點位置P，即P=Pc;

7)計算DistMin，DistMin 為各節點距離邊界的最小值，同時縮放迭代區域邊界，縮放值為(DistMin－1)(防止節點落在目標區域邊界上);

8)計算Pc與P 的誤差Err，若誤差Err 小于Tol 或迭代次數大于最大迭代次數，則輸出節點位置;否則，跳到步驟(2)繼續執行。

其中，步驟(1)、步驟(5)、步驟(6)運用式(3)～式(5)，步驟(8)運用式(6)計算:

1)Voronoi 圖生成與質心計算［7］

對于一個Voronoi 多邊形來說，其面積

2)質心位置距離誤差計算［10］

其中，Ω 為邊界區域，|Ω|為對應邊界區域的面積，Vy為對應節點Voronoi 多邊形的面積，y，yc分別為對應節點位置及其質心位置。

1.4.2 邊界縮放算法

邊界縮放算法描述如下:

1)根據任務需求和環境條件，設定目標覆蓋區域和相應參數，如，節點區域初始覆蓋邊界R_I、節點區域目標覆蓋邊界R_T、節點個數、各節點距離誤差、節點位置和方向(區域內隨機分布)、最大迭代次數等;

2)取區域R_I 的并集R_U，并計算各個節點距離R_U邊界的最小距離DistMin;

3)縮放各個子區域，使各個子區域邊界向各自子區域中心縮放(DistMin－1)的距離(防止節點落在區域邊界上)，得到縮放后的虛擬子區域并集R_Z;

4)比較R_Z 和R_T，若區域R_Z 為區域R_T 的子集，則將當前縮放區域R_Z 設定為R_C;否則，將目標區域R_T設定為R_C;

5)執行Lloyd 算法，更新各個節點位置;

6)返回到步驟(2)繼續執行。

2 仿真實驗結果與分析

2.1 仿真實驗參數

為了驗證控制算法的有效性，本文做了Matlab 實驗仿真，假設在初始400 m×400 m 的區域內，隨機散布一定數量的感知半徑為50 m 的傳感器節點，分別就不同類型覆蓋區域進行仿真實驗分析。基于以上算法，對靜態邊界的正方形覆蓋和正方形—圓形障礙覆蓋以及動態邊界的正方形—長方形邊界覆蓋、正方形—十字形邊界覆蓋、正方形—H 形邊界覆蓋進行了仿真。假設誤差Tol 為10－3m，每種類型覆蓋區域對應節點數仿真100 次的統計結果。由于篇幅所限，在此僅以靜態邊界問題中的正方形覆蓋和動態邊界的長方形覆蓋為例。

2.2 區域覆蓋仿真實驗結果

2.2.1 靜態邊界區域覆蓋仿真結果

如圖2 所示，為正方形靜態邊界區域覆蓋仿真結果圖，其中，實心點代表傳感器節點，虛線圓代表每個傳感器節點的感知區域。仿真實驗中，覆蓋區域邊界不變，通過Lloyd算法，實現了各個節點在對應目標覆蓋區域的覆蓋。

圖2 正方形靜態邊界區域覆蓋Fig 2 Area coverage of square static boundary

2.2.2 動態邊界區域覆蓋仿真結果

圖3 為正方形—長方形動態邊界區域覆蓋仿真結果，其中實心點代表各個傳感器節點的迭代軌跡，對應的有各個Voronoi 多邊形迭代變化。仿真實驗中，結合Lloyd 算法，由正方形區域縮放至長方形目標覆蓋區域，實現了各個節點目標覆蓋區域的動態變化。

圖3 正方形—長方形動態邊界區域覆蓋Fig 3 Rectangle-shaped area coverage with square dynamic boundary

2.3 區域覆蓋仿真實驗分析

覆蓋區域形狀、節點數、平均覆蓋程度的統計結果如圖4所示，在覆蓋區域一定的情況下，隨著節點數的不斷增加，目標覆蓋區域平均覆蓋程度不斷增加至100%，即完成目標區域的全覆蓋，同時，在覆蓋區域改變的過程中，隨著傳感器節點數量的增加，長方形目標覆蓋區域的平均覆蓋程度增加速度比H 形目標覆蓋區域、十字形目標覆蓋區域速度快;在覆蓋區域不變的情況下，隨著傳感器節點數量的增加，正方形—圓形障礙區域覆蓋程度增加速度比正方形目標覆蓋區域增加速度快。

圖4 平均覆蓋程度隨節點數變化的曲線Fig 4 Curve of average coverage level change with number of nodes

覆蓋區域形狀、節點數、平均覆蓋效率的統計結果如圖5所示，在覆蓋區域一定的情況下，隨著節點數的不斷增加，目標覆蓋區域平均覆蓋效率不斷減小，即目標區域內K重覆蓋的重數增加，同時，在覆蓋區域改變的過程中，隨著傳感器節點數量的增加，長方形目標覆蓋區域的平均覆蓋效率的減小速度比H 形目標覆蓋區域、十字形目標覆蓋區域速度快，十字形目標覆蓋區域平均覆蓋效率的減小速度比H 形目標覆蓋區域快。與平均覆蓋程度進行比較，當節點數較少時，盡管平均覆蓋效率高，但相應的覆蓋程度低，同樣，若平均覆蓋效率低，覆蓋程度高。

圖5 平均覆蓋效率隨節點數變化的曲線Fig 5 Curve of average coverage rate change with number of nodes

3 結 論

本文圍繞無線傳感器網絡覆蓋控制進行了研究，基于Voronoi 圖和CVT 理論，結合Lloyd 算法，提出了一種無線傳感器網絡動態覆蓋算法，分別實現了多種無線傳感器網絡目標靜態邊界區域和動態邊界區域的有效覆蓋，對控制算法的有效性進行了驗證。通過對不同目標覆蓋區域形狀、節點數量、覆蓋程度進行了分析可知，在目標覆蓋區域一定的情況下，隨著粒子數的增多，區域平均覆蓋程度逐漸趨近于100%，覆蓋冗余度越高，對應K 重覆蓋重數越高;反之，亦然。實際應用中需要根據環境和任務需求，在覆蓋程度和覆蓋效率之間進行平衡或有所側重。

［1］ Zou Y，Chakrabarty K.Sensor deployment and target localization based on virtual forces［C］∥Twenty－Second Annual Joint Conference of the IEEE Computer and Communications INFOCOM 2003，IEEE Societies，2003:1293－1303.

［2］ 凡志剛，郭文生，桑 楠.一種基于蜂窩網格的傳感器節點部署算法［J］.傳感器與微系統，2008，27(4):15－17.

［3］ 沙 超.無線多媒體傳感器網絡節能關鍵技術研究［D］.南京:南京郵電大學，2011.

［4］ Sung T，Yang C.Voronoi－based coverage improvement approach for wireless directional sensor networks［J］.Journal of Network and Computer Applications，2014，39(3):202－213.

［5］ Lin J W，Chen Y T.Improving the coverage of randomized scheduling in wireless sensor networks［J］.IEEE Transactions on Wireless Communications，2008，7(12):4807－4812.

［6］ Du Q，Faber V，Gunzburger M.Centroidal voronoi tessellations:Applications and algorithms［J］.SIAM Review，1999，41(4):637－676.

［7］ Cortes J，Martinez S，Karatas T，et al.Coverage control for mobile sensing networks［C］∥Proceedings of IEEE International Conference on Robotics and Automation，ICRA’02，IEEE，2002:1327－1332.

［8］ 陳 軍.Voronoi 動態空間數據模型［M］.1 版.北京:測繪出版社，2002.

［9］ Okabe A，Boots B，Sugihara K，et al.Spatial tessellations:Concepts and applications of Voronoi diagrams［M］.Now York:John Wiley＆Sons，2009.

［10］Talischi C，Paulino G H，Pereira A，et al.PolyMesher:A generalpurpose mesh generator for polygonal elements written in Matlab［J］.Structural and Multidisciplinary Optimization，2012，45(3):309－328.