無(wú)線傳感器網(wǎng)絡(luò)動(dòng)態(tài)覆蓋的CVT 算法*

劉志強(qiáng)，沈廼桐，毛 強(qiáng)，魏洪興

(1.內(nèi)蒙古工業(yè)大學(xué) 信息工程學(xué)院，內(nèi)蒙古 呼和浩特010051;2.北京航空航天大學(xué) 機(jī)械工程及自動(dòng)化學(xué)院，北京100191)

0 引 言

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

受Voronoi 圖和CVT 的啟發(fā)，本文提出了一種基于CVT 的無(wú)線傳感器網(wǎng)絡(luò)動(dòng)態(tài)覆蓋算法。與文獻(xiàn)［6，7］通過(guò)改變區(qū)域分布密度的方法不同，本文結(jié)合Voronoi 圖特性，不斷縮放覆蓋區(qū)域邊界至目標(biāo)覆蓋區(qū)域，系統(tǒng)協(xié)同調(diào)動(dòng)各傳感器節(jié)點(diǎn)至目標(biāo)位置，從而完成目標(biāo)區(qū)域的覆蓋，仿真驗(yàn)證了該算法的有效性和可行性。

1 基于CVT 的無(wú)線傳感器網(wǎng)絡(luò)覆蓋模型和算法分析

1.1 無(wú)線傳感器網(wǎng)絡(luò)覆蓋假設(shè)

本文主要針對(duì)二維平面區(qū)域的無(wú)線傳感器網(wǎng)絡(luò)覆蓋進(jìn)行研究，網(wǎng)絡(luò)模型和基本假設(shè)如下:

1)各個(gè)傳感器節(jié)點(diǎn)初始隨機(jī)分布在任意二維封閉區(qū)域內(nèi)。

2)各個(gè)傳感器節(jié)點(diǎn)能夠隨時(shí)確定自身的位置和方向，并能準(zhǔn)確移動(dòng)至指定的目標(biāo)位置，能感知以節(jié)點(diǎn)為中心，以Rs為半徑的圓形區(qū)域。

3)各個(gè)傳感器節(jié)點(diǎn)是同構(gòu)的，有相同的通信和覆蓋能力。

4)Rc≥2Rs，即各個(gè)傳感器節(jié)點(diǎn)的通信半徑Rc不小于2 倍的傳感器感知半徑Rs。

1.2 理論基礎(chǔ)

覆蓋程度C:是指在目標(biāo)覆蓋區(qū)域內(nèi)，所有傳感器節(jié)點(diǎn)覆蓋的總面積與目標(biāo)區(qū)域總面積的比值。計(jì)算公式為

其中，A 為目標(biāo)覆蓋區(qū)域總面積，N 為傳感器節(jié)點(diǎn)總數(shù)，Ai為第i 只傳感器節(jié)點(diǎn)的覆蓋面積。

有效覆蓋效率(effective coverage efficiency，ECE)用來(lái)衡量傳感器節(jié)點(diǎn)覆蓋范圍的利用率，用來(lái)反映有效覆蓋區(qū)域的情況，定義為目標(biāo)覆蓋區(qū)域中，所有傳感器節(jié)點(diǎn)有效覆蓋區(qū)域的并集與所有傳感器節(jié)點(diǎn)覆蓋區(qū)域之和的比值，計(jì)算公式為

Voronoi 圖是由俄國(guó)數(shù)學(xué)家Georgy Fedoseevich Voronoi建立的空間分割算法，它是一種簡(jiǎn)單有效的能夠?qū)⒍S幾何區(qū)域用多邊形離散化的方法［8］。Voronoi 多邊形邊界是由任意兩點(diǎn)垂直平分線連接而成，可以對(duì)二維空間進(jìn)行劃分，能夠表示各個(gè)節(jié)點(diǎn)的鄰近關(guān)系，Voronoi 圖具有勢(shì)力范圍特性、側(cè)向鄰近特性、線性特性、局域動(dòng)態(tài)特性、與Delaunay 三角網(wǎng)對(duì)偶(dual of Delaunay triangulation)等特性［9］。

CVT:質(zhì)心Voronoi 結(jié)構(gòu)是Voronoi 結(jié)構(gòu)的一種特殊形式。當(dāng)Voronoi 結(jié)構(gòu)的質(zhì)心點(diǎn)與構(gòu)造Voronoi 結(jié)構(gòu)的初始點(diǎn)重合時(shí)，這樣的Voronoi 結(jié)構(gòu)稱為質(zhì)心Voronoi 結(jié)構(gòu)［6］。

1.3 覆蓋區(qū)域模型分析

在一定區(qū)域內(nèi)，根據(jù)實(shí)際環(huán)境需求，需要使各個(gè)無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)能夠感知目標(biāo)區(qū)域信息，實(shí)現(xiàn)全局最優(yōu)覆蓋。這里根據(jù)目標(biāo)覆蓋區(qū)域邊界的變動(dòng)與否，將覆蓋分為兩類:1)靜態(tài)邊界區(qū)域覆蓋;2)動(dòng)態(tài)邊界區(qū)域覆蓋。這里主要分析無(wú)線傳感器網(wǎng)絡(luò)動(dòng)態(tài)邊界區(qū)域覆蓋，以初始正方形邊界覆蓋區(qū)域縮放成長(zhǎng)方形為例。

如圖1 所示，區(qū)域邊界用外側(cè)實(shí)線框線表示，其中最外層為初始覆蓋區(qū)域邊界，最內(nèi)層實(shí)線框線為目標(biāo)覆蓋區(qū)域邊界，中間的虛線框線為邊界迭代縮放過(guò)程中的覆蓋區(qū)域邊界。虛線圓代表傳感器節(jié)點(diǎn)的感知覆蓋范圍。

圖1 正方形邊界區(qū)域縮放為長(zhǎng)方形邊界區(qū)域Fig 1 A rectangle border region scaled from square boundary region

1.4 無(wú)線傳感器網(wǎng)絡(luò)動(dòng)態(tài)邊界區(qū)域覆蓋算法

1.4.1 算法分析

目標(biāo)區(qū)域覆蓋控制算法描述如下:

1)設(shè)定初始目標(biāo)覆蓋區(qū)域參數(shù)，如，節(jié)點(diǎn)區(qū)域初始覆蓋邊界、目標(biāo)覆蓋區(qū)域邊界、目標(biāo)覆蓋區(qū)域節(jié)點(diǎn)個(gè)數(shù)、各節(jié)點(diǎn)距離誤差閾值Tol、節(jié)點(diǎn)初始位置和方向(區(qū)域內(nèi)隨機(jī)分布)、最大迭代次數(shù)等;

2)根據(jù)節(jié)點(diǎn)位置生成Voronoi 圖，并計(jì)算各個(gè)對(duì)應(yīng)多邊形的質(zhì)心;

3)計(jì)算各個(gè)節(jié)點(diǎn)距離邊界的距離矩陣D，D 中為節(jié)點(diǎn)距離各邊界的距離;

4)根據(jù)各個(gè)傳感器節(jié)點(diǎn)位置P 和迭代區(qū)域邊界，生成邊界虛擬節(jié)點(diǎn)R_P，并合并R_P 和P;

5)根據(jù)R_P 和P 生成對(duì)應(yīng)的Voronoi 圖，并計(jì)算對(duì)應(yīng)各個(gè)Voronoi 圖多邊形的質(zhì)心Pc;

6)用質(zhì)心位置Pc更新節(jié)點(diǎn)位置P，即P=Pc;

7)計(jì)算DistMin，DistMin 為各節(jié)點(diǎn)距離邊界的最小值，同時(shí)縮放迭代區(qū)域邊界，縮放值為(DistMin－1)(防止節(jié)點(diǎn)落在目標(biāo)區(qū)域邊界上);

8)計(jì)算Pc與P 的誤差Err，若誤差Err 小于Tol 或迭代次數(shù)大于最大迭代次數(shù)，則輸出節(jié)點(diǎn)位置;否則，跳到步驟(2)繼續(xù)執(zhí)行。

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

1)Voronoi 圖生成與質(zhì)心計(jì)算［7］

對(duì)于一個(gè)Voronoi 多邊形來(lái)說(shuō)，其面積

2)質(zhì)心位置距離誤差計(jì)算［10］

其中，Ω 為邊界區(qū)域，|Ω|為對(duì)應(yīng)邊界區(qū)域的面積，Vy為對(duì)應(yīng)節(jié)點(diǎn)Voronoi 多邊形的面積，y，yc分別為對(duì)應(yīng)節(jié)點(diǎn)位置及其質(zhì)心位置。

1.4.2 邊界縮放算法

邊界縮放算法描述如下:

1)根據(jù)任務(wù)需求和環(huán)境條件，設(shè)定目標(biāo)覆蓋區(qū)域和相應(yīng)參數(shù)，如，節(jié)點(diǎn)區(qū)域初始覆蓋邊界R_I、節(jié)點(diǎn)區(qū)域目標(biāo)覆蓋邊界R_T、節(jié)點(diǎn)個(gè)數(shù)、各節(jié)點(diǎn)距離誤差、節(jié)點(diǎn)位置和方向(區(qū)域內(nèi)隨機(jī)分布)、最大迭代次數(shù)等;

2)取區(qū)域R_I 的并集R_U，并計(jì)算各個(gè)節(jié)點(diǎn)距離R_U邊界的最小距離DistMin;

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

4)比較R_Z 和R_T，若區(qū)域R_Z 為區(qū)域R_T 的子集，則將當(dāng)前縮放區(qū)域R_Z 設(shè)定為R_C;否則，將目標(biāo)區(qū)域R_T設(shè)定為R_C;

5)執(zhí)行Lloyd 算法，更新各個(gè)節(jié)點(diǎn)位置;

6)返回到步驟(2)繼續(xù)執(zhí)行。

2 仿真實(shí)驗(yàn)結(jié)果與分析

2.1 仿真實(shí)驗(yàn)參數(shù)

為了驗(yàn)證控制算法的有效性，本文做了Matlab 實(shí)驗(yàn)仿真，假設(shè)在初始400 m×400 m 的區(qū)域內(nèi)，隨機(jī)散布一定數(shù)量的感知半徑為50 m 的傳感器節(jié)點(diǎn)，分別就不同類型覆蓋區(qū)域進(jìn)行仿真實(shí)驗(yàn)分析?；谝陨纤惴ǎ瑢?duì)靜態(tài)邊界的正方形覆蓋和正方形—圓形障礙覆蓋以及動(dòng)態(tài)邊界的正方形—長(zhǎng)方形邊界覆蓋、正方形—十字形邊界覆蓋、正方形—H 形邊界覆蓋進(jìn)行了仿真。假設(shè)誤差Tol 為10－3m，每種類型覆蓋區(qū)域?qū)?yīng)節(jié)點(diǎn)數(shù)仿真100 次的統(tǒng)計(jì)結(jié)果。由于篇幅所限，在此僅以靜態(tài)邊界問(wèn)題中的正方形覆蓋和動(dòng)態(tài)邊界的長(zhǎng)方形覆蓋為例。

2.2 區(qū)域覆蓋仿真實(shí)驗(yàn)結(jié)果

2.2.1 靜態(tài)邊界區(qū)域覆蓋仿真結(jié)果

如圖2 所示，為正方形靜態(tài)邊界區(qū)域覆蓋仿真結(jié)果圖，其中，實(shí)心點(diǎn)代表傳感器節(jié)點(diǎn)，虛線圓代表每個(gè)傳感器節(jié)點(diǎn)的感知區(qū)域。仿真實(shí)驗(yàn)中，覆蓋區(qū)域邊界不變，通過(guò)Lloyd算法，實(shí)現(xiàn)了各個(gè)節(jié)點(diǎn)在對(duì)應(yīng)目標(biāo)覆蓋區(qū)域的覆蓋。

圖2 正方形靜態(tài)邊界區(qū)域覆蓋Fig 2 Area coverage of square static boundary

2.2.2 動(dòng)態(tài)邊界區(qū)域覆蓋仿真結(jié)果

圖3 為正方形—長(zhǎng)方形動(dòng)態(tài)邊界區(qū)域覆蓋仿真結(jié)果，其中實(shí)心點(diǎn)代表各個(gè)傳感器節(jié)點(diǎn)的迭代軌跡，對(duì)應(yīng)的有各個(gè)Voronoi 多邊形迭代變化。仿真實(shí)驗(yàn)中，結(jié)合Lloyd 算法，由正方形區(qū)域縮放至長(zhǎng)方形目標(biāo)覆蓋區(qū)域，實(shí)現(xiàn)了各個(gè)節(jié)點(diǎn)目標(biāo)覆蓋區(qū)域的動(dòng)態(tài)變化。

圖3 正方形—長(zhǎng)方形動(dòng)態(tài)邊界區(qū)域覆蓋Fig 3 Rectangle-shaped area coverage with square dynamic boundary

2.3 區(qū)域覆蓋仿真實(shí)驗(yàn)分析

覆蓋區(qū)域形狀、節(jié)點(diǎn)數(shù)、平均覆蓋程度的統(tǒng)計(jì)結(jié)果如圖4所示，在覆蓋區(qū)域一定的情況下，隨著節(jié)點(diǎn)數(shù)的不斷增加，目標(biāo)覆蓋區(qū)域平均覆蓋程度不斷增加至100%，即完成目標(biāo)區(qū)域的全覆蓋，同時(shí)，在覆蓋區(qū)域改變的過(guò)程中，隨著傳感器節(jié)點(diǎn)數(shù)量的增加，長(zhǎng)方形目標(biāo)覆蓋區(qū)域的平均覆蓋程度增加速度比H 形目標(biāo)覆蓋區(qū)域、十字形目標(biāo)覆蓋區(qū)域速度快;在覆蓋區(qū)域不變的情況下，隨著傳感器節(jié)點(diǎn)數(shù)量的增加，正方形—圓形障礙區(qū)域覆蓋程度增加速度比正方形目標(biāo)覆蓋區(qū)域增加速度快。

圖4 平均覆蓋程度隨節(jié)點(diǎn)數(shù)變化的曲線Fig 4 Curve of average coverage level change with number of nodes

覆蓋區(qū)域形狀、節(jié)點(diǎn)數(shù)、平均覆蓋效率的統(tǒng)計(jì)結(jié)果如圖5所示，在覆蓋區(qū)域一定的情況下，隨著節(jié)點(diǎn)數(shù)的不斷增加，目標(biāo)覆蓋區(qū)域平均覆蓋效率不斷減小，即目標(biāo)區(qū)域內(nèi)K重覆蓋的重?cái)?shù)增加，同時(shí)，在覆蓋區(qū)域改變的過(guò)程中，隨著傳感器節(jié)點(diǎn)數(shù)量的增加，長(zhǎng)方形目標(biāo)覆蓋區(qū)域的平均覆蓋效率的減小速度比H 形目標(biāo)覆蓋區(qū)域、十字形目標(biāo)覆蓋區(qū)域速度快，十字形目標(biāo)覆蓋區(qū)域平均覆蓋效率的減小速度比H 形目標(biāo)覆蓋區(qū)域快。與平均覆蓋程度進(jìn)行比較，當(dāng)節(jié)點(diǎn)數(shù)較少時(shí)，盡管平均覆蓋效率高，但相應(yīng)的覆蓋程度低，同樣，若平均覆蓋效率低，覆蓋程度高。

圖5 平均覆蓋效率隨節(jié)點(diǎn)數(shù)變化的曲線Fig 5 Curve of average coverage rate change with number of nodes

3 結(jié) 論

本文圍繞無(wú)線傳感器網(wǎng)絡(luò)覆蓋控制進(jìn)行了研究，基于Voronoi 圖和CVT 理論，結(jié)合Lloyd 算法，提出了一種無(wú)線傳感器網(wǎng)絡(luò)動(dòng)態(tài)覆蓋算法，分別實(shí)現(xiàn)了多種無(wú)線傳感器網(wǎng)絡(luò)目標(biāo)靜態(tài)邊界區(qū)域和動(dòng)態(tài)邊界區(qū)域的有效覆蓋，對(duì)控制算法的有效性進(jìn)行了驗(yàn)證。通過(guò)對(duì)不同目標(biāo)覆蓋區(qū)域形狀、節(jié)點(diǎn)數(shù)量、覆蓋程度進(jìn)行了分析可知，在目標(biāo)覆蓋區(qū)域一定的情況下，隨著粒子數(shù)的增多，區(qū)域平均覆蓋程度逐漸趨近于100%，覆蓋冗余度越高，對(duì)應(yīng)K 重覆蓋重?cái)?shù)越高;反之，亦然。實(shí)際應(yīng)用中需要根據(jù)環(huán)境和任務(wù)需求，在覆蓋程度和覆蓋效率之間進(jìn)行平衡或有所側(cè)重。

［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］ 凡志剛，郭文生，桑 楠.一種基于蜂窩網(wǎng)格的傳感器節(jié)點(diǎn)部署算法［J］.傳感器與微系統(tǒng)，2008，27(4):15－17.

［3］ 沙 超.無(wú)線多媒體傳感器網(wǎng)絡(luò)節(jié)能關(guān)鍵技術(shù)研究［D］.南京:南京郵電大學(xué)，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，F(xiàn)aber 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 動(dòng)態(tài)空間數(shù)據(jù)模型［M］.1 版.北京:測(cè)繪出版社，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.