無線傳感器網(wǎng)絡(luò)中的分布式Voronoi覆蓋控制算法

徐鵬飛，陳志剛，鄧曉衡

(1. 中南大學(xué) 信息科學(xué)與工程學(xué)院，湖南 長沙 410083；2. 湖南師范大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，湖南 長沙 410081)

1 引言

傳感器網(wǎng)絡(luò)是由部署在目標(biāo)區(qū)域內(nèi)的大量廉價(jià)、微型傳感器節(jié)點(diǎn)，通過自組織構(gòu)成一個(gè)無中心控制、無基礎(chǔ)設(shè)施的無線網(wǎng)絡(luò)系統(tǒng)，廣泛運(yùn)用于軍事、環(huán)境監(jiān)測等領(lǐng)域[1]；傳感器節(jié)點(diǎn)通過能量有限的電池供電，節(jié)能成為傳感器網(wǎng)絡(luò)的重要研究內(nèi)容[1,2]。覆蓋控制是選擇部分節(jié)點(diǎn)活躍工作(即活躍節(jié)點(diǎn))，將其余節(jié)點(diǎn)(即冗余節(jié)點(diǎn))轉(zhuǎn)入能耗較低的睡眠狀態(tài)，是一種提高網(wǎng)絡(luò)能量效率、延長網(wǎng)絡(luò)生存時(shí)間的有效策略[2,3]。

為了保證傳感器網(wǎng)絡(luò)的感知、通信等服務(wù)質(zhì)量，活躍節(jié)點(diǎn)應(yīng)維持網(wǎng)絡(luò)原有覆蓋范圍與連通性，綜合考慮節(jié)點(diǎn)能量、控制方式等因素[3]。在傳感器網(wǎng)絡(luò)覆蓋部分目標(biāo)區(qū)域的假設(shè)條件下，本文提出一種維持網(wǎng)絡(luò)原有覆蓋范圍、連通性的分布式Voronoi覆蓋控制算法(DVC, distributed voronoi coverage algorithm)。仿真實(shí)驗(yàn)表明，DVC活躍節(jié)點(diǎn)的數(shù)量與覆蓋度接近集中式算法，優(yōu)于一般的分布式算法；而活躍節(jié)點(diǎn)的平均能量和算法性能更加具有優(yōu)勢。

本文組織如下：第2節(jié)介紹相關(guān)研究工作；第3節(jié)定義網(wǎng)絡(luò)覆蓋模型；第4節(jié)詳細(xì)描述算法與有關(guān)結(jié)論；第5節(jié)為仿真實(shí)驗(yàn)；第6節(jié)是結(jié)束語。

2 相關(guān)研究

分布式覆蓋控制包括冗余識(shí)別與冗余調(diào)度2個(gè)基本問題[4]；其中冗余識(shí)別判斷節(jié)點(diǎn)是否為冗余節(jié)點(diǎn)，冗余調(diào)度確定將哪些冗余節(jié)點(diǎn)轉(zhuǎn)入睡眠狀態(tài)。文獻(xiàn)[4]使用扇區(qū)并集近似描述節(jié)點(diǎn)間重疊的覆蓋范圍，提出隨機(jī)時(shí)間退避的冗余調(diào)度規(guī)則。文獻(xiàn)[5]將節(jié)點(diǎn)覆蓋范圍劃分為虛擬網(wǎng)格，每個(gè)網(wǎng)格至少被一個(gè)鄰居覆蓋時(shí)為冗余節(jié)點(diǎn)，提出令牌驅(qū)動(dòng)的冗余調(diào)度規(guī)則。文獻(xiàn)[6]將節(jié)點(diǎn)覆蓋范圍簡化為覆蓋圓盤的邊界，提出圓周覆蓋的概念。文獻(xiàn)[7]通過實(shí)例說明圓周覆蓋可能將節(jié)點(diǎn)誤識(shí)為冗余節(jié)點(diǎn)，提出相應(yīng)規(guī)則降低誤識(shí)率，運(yùn)用支配集進(jìn)行冗余調(diào)度。上述文獻(xiàn)只能近似維持網(wǎng)絡(luò)原有覆蓋范圍，冗余識(shí)別復(fù)雜度、冗余調(diào)度收斂性與節(jié)點(diǎn)密度相關(guān)，目標(biāo)區(qū)域邊界附近的活躍節(jié)點(diǎn)過多。

實(shí)際上，每個(gè)節(jié)點(diǎn)原則上只要覆蓋目標(biāo)區(qū)域內(nèi)與自己最近的點(diǎn)，為此國內(nèi)外學(xué)者提出使用計(jì)算幾何的Voronoi劃分研究冗余識(shí)別[8～11]。文獻(xiàn)[8]使用Voronoi區(qū)域的面積閾值識(shí)別冗余節(jié)點(diǎn)，很難有效維持網(wǎng)絡(luò)原有覆蓋范圍。文獻(xiàn)[9]通過重構(gòu)剔除節(jié)點(diǎn)后的 Voronoi劃分來識(shí)別冗余節(jié)點(diǎn)，計(jì)算復(fù)雜度為O(n2lgn)；文獻(xiàn)[8]與文獻(xiàn)[9]通過集中方式實(shí)現(xiàn)。文獻(xiàn)[10]與文獻(xiàn)[11]基于Voronoi劃分的冗余識(shí)別規(guī)則相對比較簡單，可以使用隨機(jī)時(shí)間退避、支配集等方式進(jìn)行分布式冗余調(diào)度。但是上述基于Voronoi劃分的冗余識(shí)別要求網(wǎng)絡(luò)覆蓋整個(gè)目標(biāo)區(qū)域；事實(shí)上，隨機(jī)部署網(wǎng)絡(luò)覆蓋整個(gè)目標(biāo)區(qū)域時(shí)將導(dǎo)致高冗余度[12]，節(jié)點(diǎn)能量耗盡也可能導(dǎo)致網(wǎng)絡(luò)不能覆蓋整個(gè)目標(biāo)區(qū)域[13]。

本文主要工作：1) 在網(wǎng)絡(luò)覆蓋部分目標(biāo)區(qū)域的假設(shè)條件下，提出一種基于局部Voronoi區(qū)域的冗余識(shí)別規(guī)則，其計(jì)算復(fù)雜度與節(jié)點(diǎn)密度無關(guān)，完善已有的Voronoi覆蓋理論；2) 提出一種能量優(yōu)先的Voronoi調(diào)度規(guī)則，通信相鄰、局部Voronoi不相鄰的節(jié)點(diǎn)可以同步執(zhí)行冗余識(shí)別，提高分布式調(diào)度的收斂性。3) 通過仿真實(shí)驗(yàn)，分析隨機(jī)均勻部署網(wǎng)絡(luò)的覆蓋質(zhì)量以及本文算法的有效性。

3 問題描述

定義1（假設(shè)條件） 給定目標(biāo)區(qū)域R2內(nèi)n(≥3)個(gè)互不重疊的傳感器節(jié)點(diǎn)集S。

1) 假設(shè)節(jié)點(diǎn)具有相同傳感半徑 Rs，節(jié)點(diǎn) u∈S的覆蓋范圍是以節(jié)點(diǎn)u為圓心、Rs為半徑的圓盤，記為覆蓋圓Cu；當(dāng)且僅當(dāng)點(diǎn)p∈R2滿足||up||≤Rs(即p∈Cu)時(shí)，節(jié)點(diǎn)u覆蓋點(diǎn)p或點(diǎn)p被節(jié)點(diǎn)u覆蓋；其中||·||表示2個(gè)點(diǎn)之間的歐氏距離。

2) 如果存在點(diǎn) p∈R2與任意節(jié)點(diǎn) u∈S滿足||up||＞Rs，則傳感器節(jié)點(diǎn)集S僅覆蓋部分目標(biāo)區(qū)域，即部分覆蓋網(wǎng)絡(luò)；否則，傳感器節(jié)點(diǎn)集S可以覆蓋整個(gè)目標(biāo)區(qū)域，即完全覆蓋網(wǎng)絡(luò)。在部分覆蓋網(wǎng)絡(luò)中，不能被任意節(jié)點(diǎn)覆蓋的點(diǎn)簡稱覆蓋盲點(diǎn)，覆蓋盲點(diǎn)的集合簡稱覆蓋盲區(qū)。

3) 將目標(biāo)區(qū)域 R2簡化為整個(gè)平面，任意覆蓋圓在目標(biāo)區(qū)域R2內(nèi)，所有覆蓋圓的并集構(gòu)成網(wǎng)絡(luò)的原有覆蓋范圍C；本文研究部分覆蓋網(wǎng)絡(luò)下的覆蓋控制，這種簡化不影響問題的分析，即將目標(biāo)區(qū)域R2內(nèi)除覆蓋范圍 C外的子區(qū)域作為網(wǎng)絡(luò)的覆蓋盲區(qū)；若無特別說明，本文區(qū)域R2是指整個(gè)平面。

4) 假設(shè)節(jié)點(diǎn)具有相同通信半徑Rc，且Rc≥2Rs（注意，本文的實(shí)例分析假設(shè)Rc=2Rs。）；相互位于通信半徑范圍的節(jié)點(diǎn)互為通信鄰居或通信相鄰。

定義 2（Voronoi劃分[14]） 給定平面 R2內(nèi) n(≥3)個(gè)互不重疊的節(jié)點(diǎn)集S。

1) 點(diǎn)p∈R2與節(jié)點(diǎn)集S中的節(jié)點(diǎn)u最近，當(dāng)且僅當(dāng)點(diǎn) p 與任意節(jié)點(diǎn) x∈S(x≠u)滿足||up||≤||px||。

2) 平面R2內(nèi)所有與節(jié)點(diǎn)u∈S最近點(diǎn)的集合構(gòu)成節(jié)點(diǎn)u的Voronoi區(qū)域V(R2,S,u)，

3) 節(jié)點(diǎn)u、x∈S之間的垂直平分線記為L(u,x)，以垂直平分線L(u,x)為界、包含節(jié)點(diǎn)u的半平面記為H(u,x)；任意點(diǎn)p∈R2，當(dāng)且僅當(dāng)滿足||up||≤||px||與 u≠x時(shí)有 p∈H(u,x)，則

4) 將平面R2內(nèi)每個(gè)點(diǎn)劃分到節(jié)點(diǎn)集S中最近的節(jié)點(diǎn)，即所有Voronoi區(qū)域的并集，構(gòu)成節(jié)點(diǎn)集S在平面R2內(nèi)唯一的Voronoi劃分V(R2,S)。

定義 3（Voronoi覆蓋） 對目標(biāo)區(qū)域 R2內(nèi)的傳感器節(jié)點(diǎn)集S求解Voronoi劃分V(R2,S)。

1) 當(dāng)且僅當(dāng)任意點(diǎn) p∈V(R2,S,u)滿足||up||≤Rs時(shí)，V(R2,S,u)或節(jié)點(diǎn)u滿足Voronoi覆蓋；換言之，V(R2,S,u)滿足 Voronoi覆蓋，當(dāng)且僅當(dāng)節(jié)點(diǎn)u∈S覆蓋目標(biāo)區(qū)域R2內(nèi)所有與自己最近的點(diǎn)。

2) 當(dāng)且僅當(dāng)節(jié)點(diǎn)集S中每個(gè)節(jié)點(diǎn)滿足Voronoi覆蓋時(shí)，V(R2,S)滿足Voronoi覆蓋；換言之，V(R2,S)滿足Voronoi覆蓋，當(dāng)且僅當(dāng)目標(biāo)區(qū)域R2內(nèi)任意點(diǎn)被節(jié)點(diǎn)集S中的最近節(jié)點(diǎn)覆蓋。

定義 4（局部 Voronoi覆蓋） 給定目標(biāo)區(qū)域R2內(nèi)的傳感器節(jié)點(diǎn)集S與傳感半徑Rs。

1) 設(shè)節(jié)點(diǎn)u∈S與其2Rs范圍內(nèi)的鄰居為N(u)，則V(R2,N(u),u)為節(jié)點(diǎn)u的局部Voronoi區(qū)域。

2) 當(dāng)且僅當(dāng)任意點(diǎn) p∈V(R2,N(u),u)滿足||up||≤Rs(即 V(R2,N(u),u)位于覆蓋圓 Cu內(nèi))時(shí)，V(R2,N(u),u)或節(jié)點(diǎn)u滿足局部Voronoi覆蓋。

例如，圖 1(a)給出節(jié)點(diǎn)集 S={u1,…,u12}的Voronoi劃分 V(R2,S)，圖 1(b)給出每個(gè)節(jié)點(diǎn)的局部Voronoi區(qū)域，其中實(shí)線圍成包含一個(gè)節(jié)點(diǎn)的凸區(qū)域即為該節(jié)點(diǎn)的(局部)Voronoi區(qū)域。

定義 5（Voronoi性質(zhì)[14]） 給定 Voronoi劃分V(R2,S)。

1) Voronoi區(qū)域的邊界簡稱 Voronoi邊；如果V(R2,S,u)與V(R2,S,k)存在公共的Voronoi邊，則節(jié)點(diǎn)u、k∈S(u≠k)共享 Voronoi邊或互為 Voronoi鄰居（即Voronoi相鄰）。

2) 節(jié)點(diǎn)u∈S滿足u∈V(R2,S,u)、且不在Voronoi邊上；任意節(jié)點(diǎn) k∈S(u≠k)滿足 k?V(R2,S,u)。

圖1 Voronoi劃分與Voronoi覆蓋

3) 如果點(diǎn)p∈V(R2,S,u)不在Voronoi邊上，則任意節(jié)點(diǎn) k∈S(k≠u)滿足||kp||＞||pu||。

4) 設(shè)節(jié)點(diǎn)u的所有Voronoi鄰居為Vn(R2,S,u)，當(dāng)且僅當(dāng) k∈Vn(R2,S,u)時(shí)有 u∈Vn(R2,S,k)。

5) 當(dāng)且僅當(dāng) V(R2,S,u)∩L(u,k)≠φ，節(jié)點(diǎn) u、k∈S(u≠k)共享 Voronoi邊(V(R2,S,u)∩L(u,k))。

6) Voronoi區(qū)域是由Voronoi邊圍成的凸多邊形區(qū)域，即

定義6 給定局部Voronoi區(qū)域V(R2,N(u),u)與局部Voronoi鄰居Vn(R2,N(u),u)，將區(qū)域V(R2,N(u),u)內(nèi)每個(gè)點(diǎn)劃分到節(jié)點(diǎn)集 Vn(R2,N(u),u)中，最近節(jié)點(diǎn)后的Voronoi劃分為V(V(R2,N(u),u),Vn(R2,N(u),u))。

定義7（冗余） 當(dāng)且僅當(dāng)任意點(diǎn)p∈Cu存在節(jié)點(diǎn)k∈(S-u)滿足||kp||≤Rs時(shí)，節(jié)點(diǎn)u為冗余節(jié)點(diǎn)或節(jié)點(diǎn)u滿足冗余[9]；換言之，節(jié)點(diǎn)u滿足冗余，當(dāng)且僅當(dāng)任意點(diǎn)p∈Cu被節(jié)點(diǎn)集S-u中最近的節(jié)點(diǎn)覆蓋。

4 部分覆蓋網(wǎng)絡(luò)下的分布式Voronoi覆蓋控制

4.1 基于局部Voronoi區(qū)域的冗余識(shí)別規(guī)則

當(dāng)網(wǎng)絡(luò)覆蓋部分目標(biāo)區(qū)域時(shí)，任意節(jié)點(diǎn)根據(jù)其2Rs范圍的鄰居求解局部Voronoi區(qū)域后，至少有一個(gè)節(jié)點(diǎn)不滿足局部Voronoi覆蓋[15]。

4.1.1 節(jié)點(diǎn)不滿足局部Voronoi覆蓋

通過分析Voronoi區(qū)域V(R2,S,u)與局部Voronoi區(qū)域V(R2,N(u),u)的關(guān)系，然后給出節(jié)點(diǎn)u在不滿足局部Voronoi覆蓋時(shí)的冗余識(shí)別規(guī)則。

引理 1 任意Voronoi區(qū)域V(R2,S,u)與局部Voronoi區(qū)域 V(R2,N(u),u)滿足 V(R2,S,u)?V(R2,N(u),u)[15]。

證明 依據(jù)式(2)將V(R2,S,u)改寫為

依據(jù)式(2)有 V(R2,N(u),u)=∩x∈(N(u)-u)H(u,x)，將其代入式(3)后有

式(4)表明 V(R2,S,u)?V(R2,N(u),u)。證畢。

推論 1 如果 V(R2,N(u),u)不滿足局部 Voronoi覆蓋，則V(R2,S,u)不滿足Voronoi覆蓋。

證明 依據(jù)引理 1，V(R2,S,u)與 V(R2,N(u),u)滿足下列情況之一。1) V(R2,S,u)=V(R2,N(u),u)：則V(R2,S,u)不滿足Voronoi覆蓋；2) V(R2,S,u)? V(R2,N(u),u)：V(R2,S,u)位于區(qū)域 V(R2,N(u),u)內(nèi)，V(R2,S,u)至少有一條 Voronoi邊 e與V(R2,N(u),u)的任意Voronoi邊不重疊(否則，將有 V(R2,S,u)=V(R2,N(u),u))，依據(jù)Voronoi性質(zhì) 5)設(shè) e=V(R2,S,u)∩L(u,k)，則 e≠φ；設(shè)V(R2,N(u),u)∩L(u,k)=λ，已知V(R2,S,u)?V(R2,N(u),u)，則有 e?λ與λ≠φ；如果 k∈N(u)，V(R2,N(u),u)依據(jù)Voronoi性質(zhì)5)將有Voronoi邊λ，這樣Voronoi邊e與V(R2,N(u),u)的Voronoi邊λ重疊，與假設(shè)“Voronoi邊e與V(R2,N(u),u)的任意Voronoi邊不重疊”矛盾，即 只 能 有 k?N(u)與||uk||＞2Rs； 點(diǎn) p∈e 滿 足p∈V(R2,S,u)、p∈L(u,k)，垂直平分線 L(u,k)上的點(diǎn) p滿足||up||≥||uk||/2＞Rs，即存在點(diǎn) p∈V(R2,S,u)滿足||up||＞Rs，V(R2,S,u)不滿足 Voronoi覆蓋。綜合上述，當(dāng) V(R2,N(u),u)不滿足局部 Voronoi覆蓋時(shí)，必有V(R2,S,u)不滿足Voronoi覆蓋。證畢。

推論2 如果V(R2,S,u)不滿足Voronoi覆蓋，則節(jié)點(diǎn)u必定不滿足冗余。

證明 V(R2,S,u)不滿足 Voronoi覆蓋時(shí)，將存在點(diǎn)q∈V(R2,S,u)滿足q?Cu；節(jié)點(diǎn)u為覆蓋圓Cu的圓心，線段uq與覆蓋圓Cu的邊界交于一點(diǎn)p，則有||pu||=Rs(即 p∈Cu)與 p∈uq(p≠q, p≠u)；依據(jù) Voronoi性質(zhì)2)，節(jié)點(diǎn)u∈V(R2,S,u)不在Voronoi邊上，則線段uq在區(qū)域V(R2,S,u)內(nèi)、與V(R2,S,u)的任意Voronoi邊不重疊，也就是點(diǎn)p∈V(R2,S,u)不在Voronoi邊上；依據(jù) Voronoi性質(zhì) 3)，任意節(jié)點(diǎn) k∈S(k≠u)滿足||kp||＞||pu||與||kp||＞Rs。綜合上述，V(R2,S,u)不滿足 Voronoi覆蓋時(shí)，存在點(diǎn) p∈Cu與任意節(jié)點(diǎn) k∈(S-u)滿足||kp||＞Rs，節(jié)點(diǎn)u不滿足冗余。證畢。

定理 1 如果 V(R2,N(u),u)不滿足局部 Voronoi覆蓋，則節(jié)點(diǎn)u必定不滿足冗余。

證明 依據(jù)推論1與推論2可知。

4.1.2 節(jié)點(diǎn)滿足局部Voronoi覆蓋

當(dāng)V(R2,N(u),u)滿足局部Voronoi覆蓋時(shí)，區(qū)域V(R2,N(u),u)位于覆蓋圓Cu內(nèi)，覆蓋圓Cu劃分為不相交的子集：V(R2,N(u),u)與Cu-V(R2,N(u),u)；依據(jù)定義7，當(dāng)且僅當(dāng)這2個(gè)區(qū)域內(nèi)任意點(diǎn)都能被節(jié)點(diǎn)集S-u中最近的節(jié)點(diǎn)覆蓋時(shí)，節(jié)點(diǎn)u滿足冗余。

推論 3 任意點(diǎn) q∈(Cu-V(R2,N(u),u))存在節(jié)點(diǎn)m∈S(m≠u)滿足||mq||≤Rs與 q∈V(R2,N(m),m)。

證明 已知 q?V(R2,N(u),u)與 q∈Cu，則有||uq||≤Rs與 q∈R2；若 q∈R2，依據(jù)式(1)存在節(jié)點(diǎn) m∈S滿足q∈V(R2,S,m)；若q?V(R2,N(u),u)，依據(jù)引理1有q?V(R2,S,u)，則有 m≠u；若 q∈V(R2,S,m)，依據(jù)式(1)有||mq||≤||uq||，則有||mq||≤Rs；依據(jù)引理 1有 V(R2,S,m)?V(R2,N(m),m)，則有 q∈V(R2,N(m),m)。證畢。

推論4 如果V(R2,N(u),u)滿足局部Voronoi覆蓋，則V(R2,S,u)=V(R2,N(u),u)、Vn(R2,S,u)=Vn(R2, N(u), u)。

證明 V(R2,N(u),u)滿足Voronoi覆蓋時(shí)，任意點(diǎn) p∈V(R2,N(u),u)滿 足 ||up||≤ Rs； 任 意 節(jié) 點(diǎn)x∈(S-N(u))滿足 u≠x 與||ux||＞2Rs，也就有||up||＜||ux||/2與 p∈H(u,x)，則有 p∈(∩x∈(S-N(u))H(u,x))；綜合上述，有 V(R2,N(u),u)?(∩x∈(S-N(u))H(u,x))，依據(jù)式(4)有V(R2,S,u)=V(R2,N(u),u)，根據(jù)Voronoi鄰居定義又有Vn(R2,S,u)=Vn(R2,N(u),u)。證畢。

引理2 如果點(diǎn)p∈V(R2,S,u)與節(jié)點(diǎn)集Vn(R2,S,u)中最近的節(jié)點(diǎn)為k，則點(diǎn)p與節(jié)點(diǎn)集S-u中最近的節(jié)點(diǎn)仍是k。

證明 詳細(xì)見文獻(xiàn)[11]的引理5.3證明。

推論5 當(dāng)V(R2,N(u),u)滿足局部Voronoi覆蓋時(shí)，如果任意點(diǎn) p∈V(R2,N(u),u)被節(jié)點(diǎn)集Vn(R2,N(u),u)中最近的節(jié)點(diǎn)覆蓋，則節(jié)點(diǎn) u滿足冗余；否則，節(jié)點(diǎn)u不滿足冗余。

證明 依據(jù)推論3，區(qū)域(Cu-V(R2,N(u),u))內(nèi)任意點(diǎn)必被節(jié)點(diǎn)集S-u中最近的節(jié)點(diǎn)覆蓋，節(jié)點(diǎn)u是否冗余取決于，區(qū)域V(R2,N(u),u)內(nèi)任意點(diǎn)是否被節(jié)點(diǎn)集S-u中最近的節(jié)點(diǎn)覆蓋；設(shè)點(diǎn)p∈V(R2,N(u),u)與節(jié)點(diǎn)集 Vn(R2,N(u),u)中最近的節(jié)點(diǎn)為 k。已知V(R2,N(u),u)滿足 Voronoi覆蓋，依據(jù)推論 4有V(R2,S,u)=V(R2,N(u),u)與 Vn(R2,S,u)=Vn(R2,N(u),u)，則點(diǎn) p∈V(R2,S,u)與節(jié)點(diǎn)集 Vn(R2,S,u)中最近的節(jié)點(diǎn)為k；依據(jù)引理2，點(diǎn)p與節(jié)點(diǎn)集S-u中最近的節(jié)點(diǎn)為 k；換言之，任意點(diǎn) p∈V(R2,N(u),u)被節(jié)點(diǎn)集Vn(R2,N(u),u)中最近的節(jié)點(diǎn)k覆蓋，點(diǎn)p必被節(jié)點(diǎn)集S-u中最近的節(jié)點(diǎn)k覆蓋，節(jié)點(diǎn)u滿足冗余；否則，存在點(diǎn) p∈V(R2,N(u),u)不能被節(jié)點(diǎn)集 Vn(R2,N(u),u)中最近的節(jié)點(diǎn)k覆蓋，點(diǎn)p也不能被節(jié)點(diǎn)集S-u中最近的節(jié)點(diǎn)k覆蓋，節(jié)點(diǎn)u不滿足冗余。證畢。

定理 2（Voronoi冗余） 當(dāng) V(R2,N(u),u)滿足Voronoi覆蓋時(shí)，如果V(V(R2,N(u),u)、Vn(R2,N(u),u))滿足Voronoi覆蓋，則節(jié)點(diǎn)u滿足冗余，簡稱Voronoi冗余；否則，節(jié)點(diǎn)u不滿足冗余。

證明 如果 V(V(R2,N(u),u)、Vn(R2,N(u),u))滿足Voronoi覆蓋，則任意點(diǎn) p∈V(R2,N(u),u)被節(jié)點(diǎn)集Vn(R2,N(u),u)中最近的節(jié)點(diǎn)覆蓋，依據(jù)推論5有節(jié)點(diǎn)u滿足冗余；否則，存在點(diǎn)p∈V(R2,N(u),u)不能被節(jié)點(diǎn)集 Vn(R2,N(u),u)中最近的節(jié)點(diǎn)覆蓋，依據(jù)推論 5將有節(jié)點(diǎn)u不滿足冗余。證畢。

定理 2與文獻(xiàn)[11]的區(qū)別是，任意滿足局部Voronoi覆蓋的節(jié)點(diǎn)可以進(jìn)行Voronoi冗余識(shí)別，不管其他節(jié)點(diǎn)是否滿足局部 Voronoi覆蓋，即定理 2允許網(wǎng)絡(luò)覆蓋部分目標(biāo)區(qū)域；文獻(xiàn)[11]要求網(wǎng)絡(luò)覆蓋整個(gè)目標(biāo)區(qū)域，此時(shí)所有節(jié)點(diǎn)滿足局部 Voronoi覆蓋[15]；因此，文獻(xiàn)[9]與文獻(xiàn)[11]是定理2的特例情況，定理1與定理2將進(jìn)一步完善文獻(xiàn)[9]與文獻(xiàn)[11]的Voronoi覆蓋理論。

例如圖 1(b)，節(jié)點(diǎn) ui(i=3,…,11)不滿足局部Voronoi覆蓋，節(jié)點(diǎn)u1、u2滿足局部Voronoi覆蓋，依據(jù)定理2可知節(jié)點(diǎn)u1、u2滿足Voronoi冗余，如圖2(a)所示；從圖1可以發(fā)現(xiàn)節(jié)點(diǎn)u1、u2確實(shí)為冗余節(jié)點(diǎn)。

圖2 Voronoi冗余實(shí)例

4.2 能量優(yōu)先的Voronoi調(diào)度規(guī)則

任意節(jié)點(diǎn)根據(jù)2Rs范圍的鄰居，定理 1與定理2可以獨(dú)自確定是否冗余。為了維持網(wǎng)絡(luò)原有覆蓋范圍，不滿足冗余的節(jié)點(diǎn)只能為活躍(Active)狀態(tài)，不能轉(zhuǎn)入睡眠(Sleep)狀態(tài)[9]；一個(gè)冗余節(jié)點(diǎn)能否轉(zhuǎn)入 Sleep狀態(tài)，應(yīng)根據(jù)其他節(jié)點(diǎn)的狀態(tài)來確定。為此，本文提出一種能量優(yōu)先的Voronoi調(diào)度策略。

4.2.1 調(diào)度算法描述

假設(shè)節(jié)點(diǎn)通過消息交互維護(hù)2Rs范圍內(nèi)的鄰居位置、能量與狀態(tài)等信息。首先，將N(u)中所有節(jié)點(diǎn)標(biāo)記為Unset狀態(tài)；然后，節(jié)點(diǎn)u通過調(diào)度策略確定最終狀態(tài)(Active或Sleep)后，向N(u)中所有鄰居廣播最終狀態(tài)消息；最后，如果節(jié)點(diǎn)u為Active狀態(tài)，則繼續(xù)接收鄰居的狀態(tài)消息，直到N(u)中所有鄰居確定最終狀態(tài)，以維護(hù)活躍鄰居信息。

其調(diào)度策略如下：1) V(R2,N(u),u)不滿足局部Voronoi覆蓋：節(jié)點(diǎn)u依據(jù)定理1將不滿足冗余，設(shè)置為Active狀態(tài)。2) V(R2,N(u),u)滿足局部Voronoi覆蓋：節(jié)點(diǎn)u先接收N(u)中鄰居的狀態(tài)消息，標(biāo)記N(u)中的Active節(jié)點(diǎn)、剔除N(u)中的Sleep節(jié)點(diǎn)；當(dāng)Vn(R2,N(u),u)中包含Sleep節(jié)點(diǎn)時(shí)，重構(gòu)剔除Sleep節(jié)點(diǎn)后的V(R2,N(u),u)；當(dāng)Vn(R2,N(u),u)中所有能量較低(若能量相同，則節(jié)點(diǎn) ID 值較小)節(jié)點(diǎn)確定為Active狀態(tài)后，節(jié)點(diǎn)u使用定理2進(jìn)行冗余識(shí)別；如果節(jié)點(diǎn)u滿足Voronoi冗余，則為Sleep狀態(tài)；否則為Active狀態(tài)。

其算法詳細(xì)步驟如圖3所示，節(jié)點(diǎn)的任務(wù)/狀態(tài)轉(zhuǎn)換如圖4所示(注意：為了簡化問題描述，下文假設(shè)任意2個(gè)節(jié)點(diǎn)的能量不同)。

圖3 DVC算法

圖4 調(diào)度的任務(wù)/狀態(tài)轉(zhuǎn)換

4.2.2 調(diào)度實(shí)例分析

1) 設(shè)圖1(b)所示網(wǎng)絡(luò)的目標(biāo)區(qū)域?yàn)檎麄€(gè)平面，節(jié)點(diǎn)能量為其編號(hào)。初始化時(shí)，不滿足局部Voronoi覆蓋的節(jié)點(diǎn)ui(i=3,…,11)設(shè)置為Active狀態(tài)，滿足局部Voronoi覆蓋的節(jié)點(diǎn)u1、u2、u12進(jìn)入While/Unset循環(huán)；第1輪，節(jié)點(diǎn)u1、u2退出While/Unset循環(huán)，執(zhí)行 Voronoi冗余識(shí)別后為 Sleep狀態(tài)，如圖 2(a)所示；第2輪，節(jié)點(diǎn)u12收到節(jié)點(diǎn)u1、u2的睡眠消息，重構(gòu)局部Voronoi區(qū)域、退出While/Unset循環(huán)，執(zhí)行Voronoi冗余識(shí)別后為Active狀態(tài)，如圖2(b)所示。每輪調(diào)度的節(jié)點(diǎn)狀態(tài)變化如表1所示。

表1 DVC調(diào)度實(shí)例

2) 如果目標(biāo)區(qū)域?yàn)檎麄€(gè)平面，則不滿足局部Voronoi覆蓋的節(jié)點(diǎn)稱為邊界節(jié)點(diǎn)[15]；當(dāng)目標(biāo)區(qū)域?yàn)橛薪鐓^(qū)域時(shí)，應(yīng)將有界目標(biāo)區(qū)域與節(jié)點(diǎn)的局部Voronoi區(qū)域進(jìn)行交集操作[9]，這樣一些邊界節(jié)點(diǎn)有可能滿足局部Voronoi冗余。例如圖5 (a)所示，目標(biāo)區(qū)域?yàn)檎麄€(gè)平面時(shí)，邊界節(jié)點(diǎn)u1、u2、u3不是冗余節(jié)點(diǎn)；如果目標(biāo)區(qū)域的邊界為圖5(a)的實(shí)線方框，則節(jié)點(diǎn)u1滿足Voronoi冗余，如圖5(b)所示。

圖5 有界目標(biāo)區(qū)域調(diào)度實(shí)例

4.2.3 算法正確性分析

結(jié)論 1 通信相鄰、局部 Voronoi不相鄰的節(jié)點(diǎn)可以同步執(zhí)行Voronoi冗余識(shí)別。

證明 設(shè)V(R2,N(u),u)滿足局部Voronoi覆蓋，任意局部 Voronoi鄰居 k∈Vn(R2,N(u),u)滿足k∈Vn(R2,S,u)(推論 4)，則有 u∈Vn(R2,S,k)(Voronoi性質(zhì)4))；節(jié)點(diǎn)u執(zhí)行Voronoi冗余識(shí)別時(shí)，V(R2,N(k),k)有下列情況之一。

1) 不滿足局部Voronoi覆蓋：節(jié)點(diǎn)k在初始化時(shí)已經(jīng)設(shè)置為Active狀態(tài)。

2) 滿足局部 Voronoi覆蓋：依據(jù)推論 4有Vn(R2,N(k),k)=Vn(R2,S,k)，則有 u∈Vn(R2,N(k),k)；若k.E＞u.E，節(jié)點(diǎn)k至少要收到節(jié)點(diǎn)u的狀態(tài)消息后執(zhí)行Voronoi冗余識(shí)別，即節(jié)點(diǎn)k處于While/Unset循環(huán)；否則，節(jié)點(diǎn) u至少要收到節(jié)點(diǎn) k的狀態(tài)消息后執(zhí)行Voronoi冗余識(shí)別，即節(jié)點(diǎn)k為Active狀態(tài)(若為Sleep狀態(tài)，則已從 N(u)剔除了節(jié)點(diǎn) k，有 k?Vn(R2,N(u),u))。

綜合上述，節(jié)點(diǎn)u執(zhí)行Voronoi冗余識(shí)別時(shí)，其任意局部Voronoi鄰居k或處于While/Unset循環(huán)或?yàn)锳ctive狀態(tài)，不會(huì)轉(zhuǎn)入睡眠狀態(tài)；換言之，局部Voronoi相鄰節(jié)點(diǎn)異步執(zhí)行Voronoi冗余識(shí)別，局部Voronoi鄰居為通信鄰居的子集，即通信相鄰、局部 Voronoi不相鄰的節(jié)點(diǎn)可以同步執(zhí)行 Voronoi冗余識(shí)別。證畢。

例如，根據(jù)圖1(b)可知節(jié)點(diǎn)u1、u2滿足通信相鄰、局部 Voronoi不相鄰；根據(jù)表 1，節(jié)點(diǎn) u1、u2同步執(zhí)行Voronoi冗余識(shí)別后轉(zhuǎn)入睡眠狀態(tài)。

推論6 如果V(R2,N(u),u)滿足局部Voronoi覆蓋，點(diǎn)p∈V(R2,N(u),u)與節(jié)點(diǎn)集Vn(R2,N(u),u)中最近的節(jié)點(diǎn)為k，則有p∈V(R2,(N(k)-u),k)。

證明 依據(jù)推論5的證明，點(diǎn)p與節(jié)點(diǎn)集S-u中最近的節(jié)點(diǎn)仍是k，依據(jù)式(1)有p∈V(R2,(S-u),k)；顯然，(N(k)-u)為(S-u)的子集，依據(jù)引理 1有V(R2,(S-u),k)?V(R2,(N(k)-u),k)，則有 p∈V(R2,(N(k)-u),k)。證畢。

結(jié)論2 DVC可以維持網(wǎng)絡(luò)原有的覆蓋范圍。

證明 設(shè)V(R2,N(u),u)滿足局部Voronoi覆蓋，節(jié)點(diǎn)u執(zhí)行Voronoi冗余識(shí)別后轉(zhuǎn)入睡眠狀態(tài)。

1) 任意點(diǎn) p∈V(R2,N(u),u)：節(jié)點(diǎn)集 Vn(R2,N(u),u)中與點(diǎn)p最近的節(jié)點(diǎn)k可以覆蓋點(diǎn)p(推論5)。若節(jié)點(diǎn)k為活躍狀態(tài)，則節(jié)點(diǎn)k在任何時(shí)刻都可以覆蓋點(diǎn)p；否則，處于While/Unset循環(huán)的節(jié)點(diǎn)k(結(jié)論1的證明)在收到節(jié)點(diǎn)u的睡眠消息后，重構(gòu)剔除節(jié)點(diǎn)u后的局部Voronoi區(qū)域?qū)c(diǎn)p(推論6)；節(jié)點(diǎn)k在后繼調(diào)度過程中，只有其局部Voronoi鄰居覆蓋點(diǎn)p的情況下，才有可能轉(zhuǎn)入睡眠狀態(tài)。

2) 任意點(diǎn) q∈(Cu-V(R2,N(u),u))：存在節(jié)點(diǎn) m∈S(m≠u)滿足 q∈V(R2,N(m),m)與||mq||≤Rs(推論 3)；若節(jié)點(diǎn)m為活躍狀態(tài)，節(jié)點(diǎn)m在任何時(shí)刻都可以覆蓋點(diǎn)q；否則，將有V(R2,N(m),m)滿足局部Voronoi覆蓋，節(jié)點(diǎn)m只有在其局部Voronoi鄰居覆蓋點(diǎn)q∈V(R2,N(m),m)的情況下，才有可能轉(zhuǎn)入睡眠狀態(tài)。

綜上所述，Voronoi冗余節(jié)點(diǎn)轉(zhuǎn)入睡眠狀態(tài)后，其覆蓋圓內(nèi)任意點(diǎn)可以被其他節(jié)點(diǎn)覆蓋，不會(huì)轉(zhuǎn)變?yōu)楦采w盲點(diǎn)，即可以維持網(wǎng)絡(luò)原有覆蓋范圍。證畢。

推論 7 如果 Rc≥2Rs、V(R2,S)滿足 Voronoi覆蓋，則節(jié)點(diǎn)集S構(gòu)成連通網(wǎng)絡(luò)。

證明 V(R2,S)的直線對偶圖D(S)為連通圖，圖D(S)中任意邊關(guān)聯(lián)的節(jié)點(diǎn)u、k共享Voronoi邊e[14]；依據(jù) Voronoi性質(zhì) 5)設(shè) e=V(R2,S,u)∩L(u,k)，點(diǎn)p∈e滿足 p∈V(R2,S,u)、p∈L(u,k)；若 V(R2,S)滿足 Voronoi覆蓋，有 V(R2,S,u)滿足 Voronoi覆蓋，則有||up||≤Rs；垂直平分線 L(u,k)上的點(diǎn) p滿足||uk||≤2||up||，則有||uk||≤Rc；因此，連通圖 D(S)的任意邊即為一條通信鏈路，節(jié)點(diǎn)集S構(gòu)成連通網(wǎng)絡(luò)。證畢。

推論 8 任意節(jié)點(diǎn) u、k∈S(k≠u)存在節(jié)點(diǎn) m∈Vn(R2, S,u) (m≠u)滿足||km||＜||ku||。

證明 根據(jù) Voronoi性質(zhì) 2)有 k?V(R2,S,u)；設(shè)k=p，則有p?V(R2,S,u)；如果任意節(jié)點(diǎn)x∈Vn(R2,S,u)滿足 p∈H(u,x)，根據(jù) Voronoi性質(zhì) 6)有 p∈V(R2,S,u)，與“p?V(R2,S,u)”矛盾；即存在節(jié)點(diǎn)m∈Vn(R2,S,u)滿足m≠u與 p?H(u,m)，則有||up||＞||pm||，即||km||＜||ku||。證畢。

結(jié)論3 如果Rc≥2Rs，則DVC可以保持網(wǎng)絡(luò)原有連通性。

證明 設(shè)V(R2,N(u),u)滿足局部Voronoi覆蓋，節(jié)點(diǎn)u執(zhí)行Voronoi冗余識(shí)別后轉(zhuǎn)入睡眠狀態(tài)；依據(jù)定理 2有 V(V(R2,N(u),u),Vn(R2,N(u),u),u)滿足Voronoi覆蓋，不會(huì)轉(zhuǎn)入睡眠狀態(tài)的節(jié)點(diǎn)集Vn(R2,N(u),u)(結(jié)論1的證明)構(gòu)成連通子網(wǎng)(推論7)；節(jié)點(diǎn) u的任意通信鄰居 k(即||ku||≤Rc)存在節(jié)點(diǎn)m∈Vn(R2,S,u)滿足||km||＜||ku||與||km||≤Rc(推論 8)；根據(jù)推論5有Vn(R2,S,u)=Vn(R2,N(u),u)；綜上所述，節(jié)點(diǎn) u的任意 2個(gè)通信鄰居可以通過節(jié)點(diǎn)集Vn(R2,N(u),u)連通，即Voronoi冗余節(jié)點(diǎn)轉(zhuǎn)入睡眠狀態(tài)后不影響網(wǎng)絡(luò)原有連通性。證畢。

引理3 給定n個(gè)節(jié)點(diǎn)，求解任意Voronoi區(qū)域的計(jì)算復(fù)雜度為O(n)[15]。

結(jié)論 4 Voronoi冗余識(shí)別的計(jì)算復(fù)雜度為O(1)，與節(jié)點(diǎn)密度無關(guān)。

證明 Voronoi邊的交點(diǎn)簡稱Voronoi頂點(diǎn)，節(jié)點(diǎn)滿足Voronoi覆蓋等價(jià)于其所有Voronoi頂點(diǎn)在覆蓋圓內(nèi)[9,11,15]；V(R2,N(u),u)的局部Voronoi鄰居與局部Voronoi頂點(diǎn)的平均值為 6，與節(jié)點(diǎn)數(shù)量無關(guān)[14]。分別求解 V(R2,N(u),u)滿足局部 Voronoi覆蓋與V(V(R2,N(u),u),Vn(R2,N(u),u))滿足 Voronoi覆蓋的計(jì)算復(fù)雜度均為 O(1)。綜合上述，Voronoi冗余識(shí)別的計(jì)算復(fù)雜度為O(1)，與節(jié)點(diǎn)密度無關(guān)。證畢。

結(jié)論5 DVC的計(jì)算復(fù)雜度為O(m2)，其中m為2Rs范圍內(nèi)的鄰居數(shù)。

證明 根據(jù)引理3，初始化求解Vn(R2,N(u),u)、While/Unset循環(huán)重構(gòu) V(R2,N(u),u)的計(jì)算復(fù)雜度均為O(m)；Vn(R2,N(u),u)中能量較低節(jié)點(diǎn)確定為Active狀態(tài)后退出While/Unset循環(huán)，Vn(R2,N(u),u)為N(u)的子集，循環(huán)次數(shù)不會(huì)超過m，即While/Unset循環(huán)的計(jì)算復(fù)雜度為O(m2)；Finalize過程中Voronoi冗余識(shí)別的計(jì)算復(fù)雜度為 O(1)。綜上所述，DVC的計(jì)算復(fù)雜度為O(m2)。

結(jié)論6 DVC的消息復(fù)雜度為O(1)，整個(gè)網(wǎng)絡(luò)的消息復(fù)雜度為O(n)，其中n為網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)。

證明 每個(gè)節(jié)點(diǎn)初始化時(shí)通過 1個(gè)消息維護(hù)2Rs范圍內(nèi)的鄰居信息，確定最終狀態(tài)后向2Rs范圍內(nèi)的鄰居廣播1個(gè)狀態(tài)消息；即DVC的消息復(fù)雜度為O(1)，整個(gè)網(wǎng)絡(luò)的消息復(fù)雜度為O(n)。證畢。

5 仿真實(shí)驗(yàn)分析

本文利用 C++進(jìn)行算法實(shí)現(xiàn)與仿真，與 CVT算法[9]、ECC算法[7]進(jìn)行比較。實(shí)驗(yàn)環(huán)境為 P4 2.4GHz CPU與512MB內(nèi)存；實(shí)驗(yàn)場景如下：在目標(biāo)區(qū)域1 000×1 000內(nèi)隨機(jī)均勻部署n個(gè)互不重疊的節(jié)點(diǎn)，分析節(jié)點(diǎn)數(shù)量n(即部署密度)、傳感半徑Rs(設(shè)Rc=2Rs)對活躍節(jié)點(diǎn)與算法性能的影響；其中每個(gè)n值隨機(jī)產(chǎn)生500個(gè)網(wǎng)絡(luò)拓?fù)洌總€(gè)網(wǎng)絡(luò)拓?fù)潆S機(jī)分配50個(gè)能量方案(節(jié)點(diǎn)能量≤10)。

5.1 隨機(jī)均勻部署網(wǎng)絡(luò)的覆蓋質(zhì)量

為了分析隨機(jī)均勻部署網(wǎng)絡(luò)的覆蓋質(zhì)量，統(tǒng)計(jì)500個(gè)網(wǎng)絡(luò)拓?fù)渲型耆采w網(wǎng)絡(luò)的比率(PCC)、覆蓋目標(biāo)區(qū)域的面積比率(RCT)以及網(wǎng)絡(luò)覆蓋度；當(dāng)PCC、RCT小于100%時(shí)，網(wǎng)絡(luò)覆蓋部分目標(biāo)區(qū)域。

1) 隨機(jī)均勻部署500～2 000個(gè)節(jié)點(diǎn)后：① 當(dāng)Rs=50時(shí)，不能保證每個(gè)網(wǎng)絡(luò)拓?fù)涓采w整個(gè)目標(biāo)區(qū)域，但是網(wǎng)絡(luò)覆蓋目標(biāo)區(qū)域的面積比率RCT已經(jīng)超過 97%，覆蓋盲區(qū)的面積不到 3%；特別是n＜1 000時(shí)，完全覆蓋網(wǎng)絡(luò)的比率PCC接近0，如圖 6(a)所示；② 當(dāng) Rs=100時(shí)，網(wǎng)絡(luò)覆蓋目標(biāo)區(qū)域的面積比率RCT已經(jīng)超過99%；直到n＞1 000，完全覆蓋網(wǎng)絡(luò)的比率 PCC才收斂于 100%；如圖6(b)所示。

圖6 覆蓋質(zhì)量分析

2) 隨機(jī)均勻部署n個(gè)節(jié)點(diǎn)，隨著傳感半徑Rs的增大，覆蓋整個(gè)目標(biāo)區(qū)域的概率增大。當(dāng)n=1 000、Rs≥100時(shí)，完全覆蓋網(wǎng)絡(luò)的比率PCC收斂于 100%，如圖 6(c)所示；當(dāng) n=1 500、Rs≥80時(shí)，完全覆蓋網(wǎng)絡(luò)的比率PCC收斂于100%，如圖6(d)所示；當(dāng)n≥1 000、Rs≥50時(shí)，網(wǎng)絡(luò)覆蓋目標(biāo)區(qū)域的面積比率RCT已經(jīng)超過99.8%。

3) 設(shè)覆蓋點(diǎn) p∈R2的節(jié)點(diǎn)數(shù)為 K(p)，覆蓋度是衡量網(wǎng)絡(luò)能量效率、覆蓋冗余程度的一個(gè)指標(biāo)[9]。隨機(jī)均勻部署網(wǎng)絡(luò)的覆蓋度，隨著節(jié)點(diǎn)數(shù)量n近似線性增長，隨著傳感半徑Rs近似指數(shù)增長，如圖7所示；當(dāng)網(wǎng)絡(luò)覆蓋目標(biāo)區(qū)域的面積比率RCT接近99.99%時(shí)，覆蓋度大約為13，如圖7的圓圈所示；當(dāng)網(wǎng)絡(luò)覆蓋整個(gè)目標(biāo)區(qū)域時(shí)，覆蓋度已經(jīng)達(dá)到30以上，如圖7的方框所示。

圖7 網(wǎng)絡(luò)平均覆蓋度

5.2 活躍節(jié)點(diǎn)的數(shù)量

當(dāng)Rs=50時(shí)，DVC活躍節(jié)點(diǎn)將隨著節(jié)點(diǎn)數(shù)量n近似收斂于282，如圖8(a)所示；當(dāng)Rs=100時(shí)，DVC活躍節(jié)點(diǎn)將隨著節(jié)點(diǎn)數(shù)量 n近似收斂于 75，如圖8(b)所示；隨機(jī)均勻部署 n個(gè)節(jié)點(diǎn)后，隨著傳感半徑Rs的增大，DVC活躍節(jié)點(diǎn)將逐漸減少，如Rs=200時(shí)的活躍節(jié)點(diǎn)大約減至 20個(gè)，如圖 8(c)、圖 8(d)所示。綜合上述實(shí)驗(yàn)數(shù)據(jù)發(fā)現(xiàn)，DVC活躍節(jié)點(diǎn)數(shù)量基本上與部署密度無關(guān)，主要由傳感半徑Rs確定；總的來說，隨著節(jié)點(diǎn)數(shù)量n或傳感半徑Rs的增大，DVC活躍節(jié)點(diǎn)相對減少，冗余節(jié)點(diǎn)相對增多。

圖8 活躍節(jié)點(diǎn)的數(shù)量

ECC算法不考慮目標(biāo)區(qū)域邊界，簡單地將所有邊界節(jié)點(diǎn)設(shè)置為活躍狀態(tài)，使得ECC活躍節(jié)點(diǎn)大約維持在DVC的1.1～3.5倍；因此，合理使用目標(biāo)區(qū)域的邊界可以有效地降低邊界附近的活躍節(jié)點(diǎn)。網(wǎng)絡(luò)覆蓋整個(gè)目標(biāo)區(qū)域時(shí)，CVT活躍節(jié)點(diǎn)稍微優(yōu)于DVC，其差值不超過DVC活躍節(jié)點(diǎn)的4.5%；網(wǎng)絡(luò)覆蓋部分目標(biāo)區(qū)域時(shí)，盡管存在冗余節(jié)點(diǎn)，但是CVT將所有節(jié)點(diǎn)設(shè)置為活躍狀態(tài)，使得CVT活躍節(jié)點(diǎn)大于DVC與ECC。

5.3 睡眠節(jié)點(diǎn)的比率

初始網(wǎng)絡(luò)節(jié)點(diǎn)中睡眠節(jié)點(diǎn)的比率(RoS)如圖 9所示，DVC將 40%以上的節(jié)點(diǎn)轉(zhuǎn)入睡眠狀態(tài)；當(dāng)RCT收斂到99%時(shí)，DVC將60%的節(jié)點(diǎn)轉(zhuǎn)入睡眠狀態(tài)，如圖9的方框所示；當(dāng)RCT收斂到99.99%時(shí)，DVC將 80%的節(jié)點(diǎn)轉(zhuǎn)入到睡眠狀態(tài)，如圖 9的圓圈所示。總的來說，隨機(jī)均勻部署網(wǎng)絡(luò)覆蓋部分目標(biāo)區(qū)域時(shí)，在維持原有覆蓋質(zhì)量的前提下，仍存在大量的冗余節(jié)點(diǎn)，因此研究部分覆蓋網(wǎng)絡(luò)環(huán)境下的Voronoi覆蓋控制具有重要的意義。

5.4 活躍節(jié)點(diǎn)的平均覆蓋度

活躍節(jié)點(diǎn)的平均覆蓋度與節(jié)點(diǎn)數(shù)量n、傳感半徑Rs的關(guān)系如圖10所示。DVC活躍節(jié)點(diǎn)的平均覆蓋度大約維持在2.5，基本上與節(jié)點(diǎn)數(shù)量n、傳感半徑Rs無關(guān)。網(wǎng)絡(luò)覆蓋整個(gè)目標(biāo)區(qū)域時(shí)，CVT活躍節(jié)點(diǎn)的平均覆蓋度稍微優(yōu)于 DVC，其差值小于 0.1；網(wǎng)絡(luò)覆蓋部分目標(biāo)區(qū)域時(shí)，CVT活躍節(jié)點(diǎn)的平均覆蓋度明顯大于DVC。ECC將邊界節(jié)點(diǎn)設(shè)置為活躍狀態(tài)，隨著節(jié)點(diǎn)數(shù)量n或傳感半徑Rs的增大，ECC活躍節(jié)點(diǎn)的平均覆蓋度呈上揚(yáng)趨勢，大于DVC。

圖9 睡眠節(jié)點(diǎn)的比率

圖10 活躍節(jié)點(diǎn)的平均覆蓋度

5.5 活躍節(jié)點(diǎn)的平均能量

設(shè)DVC活躍節(jié)點(diǎn)數(shù)量為x，選擇x個(gè)能量最大節(jié)點(diǎn)的平均值作為活躍節(jié)點(diǎn)的最佳能量；圖 11給出實(shí)驗(yàn)場景Rs=100與n=1 000中活躍節(jié)點(diǎn)的平均能量、最佳能量以及初始網(wǎng)絡(luò)的節(jié)點(diǎn)平均能量。

圖11 活躍節(jié)點(diǎn)的平均能量

隨著節(jié)點(diǎn)數(shù)量n或傳感半徑Rs的增大，DVC活躍節(jié)點(diǎn)相對減少，使得最佳能量逐漸增大；DVC將能量較低節(jié)點(diǎn)轉(zhuǎn)入睡眠狀態(tài)，使得活躍節(jié)點(diǎn)的平均能量逐漸接近最佳能量，優(yōu)于ECC、CVT活躍節(jié)點(diǎn)的平均能量。ECC活躍節(jié)點(diǎn)相對減少，但是邊界節(jié)點(diǎn)比率相對增多，邊界節(jié)點(diǎn)的能量不一定最優(yōu)，使得ECC活躍節(jié)點(diǎn)的平均能量先逐步增大、后呈下降趨勢，但優(yōu)于初始網(wǎng)絡(luò)的節(jié)點(diǎn)平均能量。CVT以最小活躍節(jié)點(diǎn)數(shù)量為目標(biāo)，沒有考慮節(jié)點(diǎn)能量因素，CVT活躍節(jié)點(diǎn)的平均能量稍低于初始網(wǎng)絡(luò)的節(jié)點(diǎn)平均能量。

5.6 算法性能分析

5.6.1 分布式調(diào)度收斂性

通信相鄰、局部Voronoi不相鄰的節(jié)點(diǎn)可以同步執(zhí)行Voronoi冗余識(shí)別，通信相鄰的節(jié)點(diǎn)異步執(zhí)行ECC的冗余識(shí)別，使得DVC調(diào)度收斂性(即節(jié)點(diǎn)確定最終狀態(tài)的循環(huán)迭代次數(shù))優(yōu)于 ECC；例如，圖 12(a)、圖 12(b)給出實(shí)驗(yàn)場景 Rs=100、n=1 000中DVC與ECC的循環(huán)迭代次數(shù)；隨著節(jié)點(diǎn)數(shù)量n或傳感半徑Rs的增加，通信鄰居數(shù)量將顯著增加，DVC與ECC的迭代次數(shù)分別增多；其中，DVC的最大、平均迭代次數(shù)分別不超過42、9，而ECC的最大、平均迭代次數(shù)分別大于、接近通信鄰居數(shù)量。

5.6.2 時(shí)間性能

假設(shè)不考慮消息交互、等待時(shí)間，使用所有節(jié)點(diǎn)的計(jì)算時(shí)間總和分析算法時(shí)間性能；隨著節(jié)點(diǎn)數(shù)量n或傳感半徑Rs的增大，通信鄰居數(shù)量顯著增加，延長了DVC、ECC的計(jì)算時(shí)間；但是Voronoi冗余識(shí)別與節(jié)點(diǎn)密度無關(guān)，使得DVC計(jì)算時(shí)間略優(yōu)于ECC，如圖12(c)、圖12(d)所示。CVT基于Voronoi劃分的冗余識(shí)別時(shí)間與節(jié)點(diǎn)數(shù)量相關(guān)、與傳感半徑Rs無關(guān)，CVT計(jì)算時(shí)間隨著節(jié)點(diǎn)數(shù)量n近似指數(shù)增長，如圖12 (c)所示；網(wǎng)絡(luò)覆蓋整個(gè)目標(biāo)區(qū)域后，傳感半徑Rs基本上不影響CVT計(jì)算時(shí)間，如圖12 (d)所示；總的來說，CVT計(jì)算時(shí)間要大于DVC與ECC。

圖12 算法性能分析

6 結(jié)束語

在傳感器網(wǎng)絡(luò)覆蓋部分目標(biāo)區(qū)域的假設(shè)條件下，提出一種基于局部Voronoi區(qū)域的冗余識(shí)別規(guī)則，其計(jì)算時(shí)間復(fù)雜度與節(jié)點(diǎn)密度無關(guān)；在維持網(wǎng)絡(luò)原有覆蓋質(zhì)量的情況下，提出一種能量優(yōu)先的Voronoi調(diào)度規(guī)則，對算法正確性進(jìn)行了理論分析。仿真實(shí)驗(yàn)表明，本文算法求解活躍節(jié)點(diǎn)的數(shù)量、平均覆蓋度，接近集中式CVT算法、優(yōu)于分布式ECC算法；而活躍節(jié)點(diǎn)的平均能量、調(diào)度收斂性以及算法時(shí)間性能優(yōu)于CVT算法與ECC算法。下一步將重點(diǎn)考慮Rc＜2Rs、k度覆蓋(k≥2)以及三維環(huán)境下的Voronoi覆蓋控制問題。

[1] 孫利民, 李建中, 陳渝. 無線傳感器網(wǎng)絡(luò)[M]. 北京∶ 清華大學(xué)出版社,2005.SUN L M, LI J Z, CHEN Y. Wireless Sensor Networks[M]. Beijing∶Tsinghua University Press, 2005.

[2] YICK J, MUKHERJEE B. Wireless sensor network survey[J]. Computer Networks, 2008, 52∶2292-2330.

[3] 任彥, 張思東. 無線傳感器網(wǎng)絡(luò)中覆蓋控制理論與算法[J].軟件學(xué)報(bào), 2006,17(3)∶422-433.REN Y, ZHANG S D. Theories and algorithms of coverage control for wireless sensor networks[J]. Journal of Software, 2006, 17(3)∶422-433.

[4] TIAN D, GEORGANAS N D. A coverage-preserved node scheduling scheme for large wireless sensor networks[A]. Proc of First International Workshop on Wireless Sensor Networks and Applications[C].2002. 32-41.

[5] YI Z, KRISHNENDU C. A distributed coverage and connectivity-centric technique for selecting active nodes in wireless sensor networks[J]. IEEE Transactions on Computer, 2005, 54(8)∶978-991.

[6] HUANG C F, TSENG Y C. The coverage problem in a wireless sensor networks[A]. Proc of the ACM Int'1 Workshop on Wireless Sensor Networks and Applications[C]. 2003.115-121.

[7] NURCAN T, WANG W Y. Effective coverage and connectivity preserving in wireless sensor networks[A]. Proc of IEEE Conf on Communication and Networks[C]. 2007. 3388-3393.

[8] VIERA M A M, VIERA L F M. Scheduling nodes in wireless sensor networks∶ a voronoi approach[A]. Proc of 28th Annual IEEE International Conf on Local Computer Networks[C]. 2003.423-429.

[9] 蔣杰,方力.無線傳感器網(wǎng)絡(luò)最小連通覆蓋問題求解算法[J]. 軟件學(xué)報(bào), 2006,17(2)∶175-184.JIANG J, FANG L. An algorithm for minimal connected cover set problem in wireless sensor networks[J]. Journal of Software, 2006,17(2)∶175-184.

[10] CARBUNAR B, GRAMA A. Coverage preserving redundancy elimination in sensor networks[A]. Proc of First Annual IEEE Communications Society Conf on Sensor and Ad Hoc Communications and Networks[C]. 2004.377-386.

[11] 陸克中. 無線傳感器網(wǎng)絡(luò)中的數(shù)據(jù)收集問題研究[D]. 中國科學(xué)技術(shù)大學(xué), 2007.70-76.LU K Z. Research on Data Collection in Wireless Sensor Networks[D].University of Science and Technology of China, 2007.70-76.

[12] BALISTER P, ZHENG Z. Allowing coverage holes of bounded diameter in wireless sensor networks[A]. Proc of IEEE INFOCOM[C].2009.136-144.

[13] 蘇瀚, 汪蕓. 傳感器網(wǎng)絡(luò)中無需地理信息的空洞填補(bǔ)算法[J].計(jì)算機(jī)學(xué)報(bào), 2009, 32(10)∶1957-1970.SU H, WANG Y. A self-healing algorithm without location information in sensor networks[J]. Chinese Journal of Computer, 2009,32(10)∶1957-1970.

[14] OKABE A, BOOTS B. Spatial Tessellations∶ Concepts and Applications of Voronoi Diagram[M]. New York∶ John Wiley & Sons, 1999.

[15] ZHANG C, ZHANG Y C. Localized algorithms for coverage boundary detection in wireless sensor networks[J]. Wireless Networks, 2009,15(1)∶3-20.