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

徐鵬飛，陳志剛，鄧曉衡

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

1 引言

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

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

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

2 相關(guān)研究

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

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

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

3 問題描述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖1 Voronoi劃分與Voronoi覆蓋

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

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

5) 當且僅當 V(R2,S,u)∩L(u,k)≠φ，節(jié)點 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)每個點劃分到節(jié)點集 Vn(R2,N(u),u)中，最近節(jié)點后的Voronoi劃分為V(V(R2,N(u),u),Vn(R2,N(u),u))。

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

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

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

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

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

通過分析Voronoi區(qū)域V(R2,S,u)與局部Voronoi區(qū)域V(R2,N(u),u)的關(guān)系，然后給出節(jié)點u在不滿足局部Voronoi覆蓋時的冗余識別規(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； 點 p∈e 滿 足p∈V(R2,S,u)、p∈L(u,k)，垂直平分線 L(u,k)上的點 p滿足||up||≥||uk||/2＞Rs，即存在點 p∈V(R2,S,u)滿足||up||＞Rs，V(R2,S,u)不滿足 Voronoi覆蓋。綜合上述，當 V(R2,N(u),u)不滿足局部 Voronoi覆蓋時，必有V(R2,S,u)不滿足Voronoi覆蓋。證畢。

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

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

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

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

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

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

推論 3 任意點 q∈(Cu-V(R2,N(u),u))存在節(jié)點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é)點 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覆蓋時，任意點 p∈V(R2,N(u),u)滿 足 ||up||≤ Rs； 任 意 節(jié) 點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 如果點p∈V(R2,S,u)與節(jié)點集Vn(R2,S,u)中最近的節(jié)點為k，則點p與節(jié)點集S-u中最近的節(jié)點仍是k。

證明 詳細見文獻[11]的引理5.3證明。

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

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

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

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

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

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

圖2 Voronoi冗余實例

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

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

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

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

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

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

圖3 DVC算法

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

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

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

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

2) 如果目標區(qū)域為整個平面，則不滿足局部Voronoi覆蓋的節(jié)點稱為邊界節(jié)點[15]；當目標區(qū)域為有界區(qū)域時，應將有界目標區(qū)域與節(jié)點的局部Voronoi區(qū)域進行交集操作[9]，這樣一些邊界節(jié)點有可能滿足局部Voronoi冗余。例如圖5 (a)所示，目標區(qū)域為整個平面時，邊界節(jié)點u1、u2、u3不是冗余節(jié)點；如果目標區(qū)域的邊界為圖5(a)的實線方框，則節(jié)點u1滿足Voronoi冗余，如圖5(b)所示。

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

4.2.3 算法正確性分析

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

證明 設(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é)點u執(zhí)行Voronoi冗余識別時，V(R2,N(k),k)有下列情況之一。

1) 不滿足局部Voronoi覆蓋：節(jié)點k在初始化時已經(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é)點k至少要收到節(jié)點u的狀態(tài)消息后執(zhí)行Voronoi冗余識別，即節(jié)點k處于While/Unset循環(huán)；否則，節(jié)點 u至少要收到節(jié)點 k的狀態(tài)消息后執(zhí)行Voronoi冗余識別，即節(jié)點k為Active狀態(tài)(若為Sleep狀態(tài)，則已從 N(u)剔除了節(jié)點 k，有 k?Vn(R2,N(u),u))。

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

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

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

證明 依據(jù)推論5的證明，點p與節(jié)點集S-u中最近的節(jié)點仍是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)絡原有的覆蓋范圍。

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

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

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

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

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

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

推論 8 任意節(jié)點 u、k∈S(k≠u)存在節(jié)點 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é)點x∈Vn(R2,S,u)滿足 p∈H(u,x)，根據(jù) Voronoi性質(zhì) 6)有 p∈V(R2,S,u)，與“p?V(R2,S,u)”矛盾；即存在節(jié)點m∈Vn(R2,S,u)滿足m≠u與 p?H(u,m)，則有||up||＞||pm||，即||km||＜||ku||。證畢。

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

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

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

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

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

結(jié)論5 DVC的計算復雜度為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)的計算復雜度均為O(m)；Vn(R2,N(u),u)中能量較低節(jié)點確定為Active狀態(tài)后退出While/Unset循環(huán)，Vn(R2,N(u),u)為N(u)的子集，循環(huán)次數(shù)不會超過m，即While/Unset循環(huán)的計算復雜度為O(m2)；Finalize過程中Voronoi冗余識別的計算復雜度為 O(1)。綜上所述，DVC的計算復雜度為O(m2)。

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

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

5 仿真實驗分析

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

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

為了分析隨機均勻部署網(wǎng)絡的覆蓋質(zhì)量，統(tǒng)計500個網(wǎng)絡拓撲中完全覆蓋網(wǎng)絡的比率(PCC)、覆蓋目標區(qū)域的面積比率(RCT)以及網(wǎng)絡覆蓋度；當PCC、RCT小于100%時，網(wǎng)絡覆蓋部分目標區(qū)域。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5.6 算法性能分析

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

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

5.6.2 時間性能

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

圖12 算法性能分析

6 結(jié)束語

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

[1] 孫利民, 李建中, 陳渝. 無線傳感器網(wǎng)絡[M]. 北京∶ 清華大學出版社,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)絡中覆蓋控制理論與算法[J].軟件學報, 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)絡最小連通覆蓋問題求解算法[J]. 軟件學報, 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)絡中的數(shù)據(jù)收集問題研究[D]. 中國科學技術(shù)大學, 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)絡中無需地理信息的空洞填補算法[J].計算機學報, 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.