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

1、2010年8月Journal on CommunicationsAugust 2010第31卷第8期 通 信 學(xué) 報(bào) V ol.31 No.8無線傳感器網(wǎng)絡(luò)中的分布式Voronoi 覆蓋控制算法徐鵬飛1,2，陳志剛1，鄧曉衡1(1. 中南大學(xué) 信息科學(xué)與工程學(xué)院，湖南 長沙 410083；2. 湖南師范大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，湖南 長沙 410081摘 要：以覆蓋部分目標(biāo)區(qū)域的傳感器網(wǎng)絡(luò)為研究背景，在通信半徑不小于2倍傳感半徑的條件下，提出了一種維持網(wǎng)絡(luò)原有覆蓋范圍、連通性的分布式V oronoi 覆蓋控制算法。首先，提出了一種基于局部Voronoi 區(qū)域的冗余識(shí)別規(guī)則，其計(jì)算復(fù)雜度與節(jié)點(diǎn)

2、密度無關(guān)；然后，提出了一種能量優(yōu)先的V oronoi 調(diào)度規(guī)則，通信相鄰、局部Voronoi 不相鄰的節(jié)點(diǎn)可以同步執(zhí)行冗余識(shí)別，提高分布式調(diào)度的收斂性。仿真實(shí)驗(yàn)表明，所提算法求解活躍節(jié)點(diǎn)的數(shù)量、平均覆蓋度與集中式算法接近，優(yōu)于一般的分布式算法，而在活躍節(jié)點(diǎn)的平均能量、算法性能等方面更加具有優(yōu)勢。關(guān)鍵詞：無線傳感器網(wǎng)絡(luò)；部分覆蓋；V oronoi 劃分；覆蓋盲點(diǎn)中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1000-436X(201008-0016-10Distributed Voronoi coverage algorithm inwireless sensor networksXU Pe

3、ng-fei1,2, CHEN Zhi-gang1, DENG Xiao-heng1(1. College of Information Science and Engineering, Central South University, Changsha 410083, China; 2. College of Mathematics and Computer Science, Hunan Normal University, Changsha 410081, ChinaAbstract: On the hypothesis conditions that wireless sensor n

4、etworks only covered partial target region and the commu-nication radius was no less than twice of the sensing radius, a coverage-preserved and connected distributed Voronoi cov-erage algorithm was presented. Firstly, a method of detecting coverage redundancy sensors based on the local Voronoi re-gi

5、ons was proposed, whose computational complexity was unconcerned with the density of sensors. Then, an en-ergy-prior self-scheduling strategy based on local Voronoi neighbors was proposed, where those sensors that were com-munication neighbors but not local Voronoi neighbors could synchronously exec

6、ute self-scheduling, which improved the astringency of distributed scheduling. The simulation results show that the average number and coverage-degree of active sensors produced by the proposed algorithm are close to the centralized algorithm and smaller than the general distributed algorithm, while

7、 the proposed algorithm has more advantages in terms of active sensors average energy, scheduling as-tringency and runtime.Key words: wireless sensor networks; partial coverage; Voronoi tessellation; coverage blind-point收稿日期：2008-09-26；修回日期：2010-05-05基金項(xiàng)目：國家自然科學(xué)基金資助項(xiàng)目(60873082, 60903058, 60973129；教育

8、部博士點(diǎn)新教師基金資助項(xiàng)目(200805331109；湖南師范大學(xué)青年基金資助項(xiàng)目(60901Foundation Items: The National Natural Science Foundation of China (60873082, 60903058, 60973129; The Research Fund for the Youth Schoolars of the Doctoral Program of Ministry of Education of China (200805331109; The Youth Scientific Research Fund of Hu

9、nan Normal University (60901第8期 徐鵬飛等：無線傳感器網(wǎng)絡(luò)中的分布式V oronoi 覆蓋控制算法 ·17·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ò)

10、原有覆蓋范圍與連通性，綜合考慮節(jié)點(diǎn)能量、控制方式等因素3。在傳感器網(wǎng)絡(luò)覆蓋部分目標(biāo)區(qū)域的假設(shè)條件下，本文提出一種維持網(wǎng)絡(luò)原有覆蓋范圍、連通性的分布式V oronoi 覆蓋控制算法(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í)別判斷

11、節(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é)者提出使用

12、計(jì)算幾何的V oronoi 劃分研究冗余識(shí)別811。文獻(xiàn)8使用V oronoi 區(qū)域的面積閾值識(shí)別冗余節(jié)點(diǎn)，很難有效維持網(wǎng)絡(luò)原有覆蓋范圍。文獻(xiàn)9通過重構(gòu)剔除節(jié)點(diǎn)后的V oronoi 劃分來識(shí)別冗余節(jié)點(diǎn)，計(jì)算復(fù)雜度為O(n 2lg n ；文獻(xiàn)8與文獻(xiàn)9通過集中方式實(shí)現(xiàn)。文獻(xiàn)10與文獻(xiàn)11基于V oronoi 劃分的冗余識(shí)別規(guī)則相對比較簡單，可以使用隨機(jī)時(shí)間退避、支配集等方式進(jìn)行分布式冗余調(diào)度。但是上述基于V oronoi 劃分的冗余識(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ò)覆

13、蓋部分目標(biāo)區(qū)域的假設(shè)條件下，提出一種基于局部V oronoi 區(qū)域的冗余識(shí)別規(guī)則，其計(jì)算復(fù)雜度與節(jié)點(diǎn)密度無關(guān)，完善已有的V oronoi 覆蓋理論；2 提出一種能量優(yōu)先的V oronoi 調(diào)度規(guī)則，通信相鄰、局部V oronoi 不相鄰的節(jié)點(diǎn)可以同步執(zhí)行冗余識(shí)別，提高分布式調(diào)度的收斂性。3 通過仿真實(shí)驗(yàn)，分析隨機(jī)均勻部署網(wǎng)絡(luò)的覆蓋質(zhì)量以及本文算法的有效性。3 問題描述定義1（假設(shè)條件） 給定目標(biāo)區(qū)域R 2內(nèi)n (3 個(gè)互不重疊的傳感器節(jié)點(diǎn)集S 。1 假設(shè)節(jié)點(diǎn)具有相同傳感半徑R s ，節(jié)點(diǎn)u S 的覆蓋范圍是以節(jié)點(diǎn)u 為圓心、R s 為半徑的圓盤，記為覆蓋圓C u ；當(dāng)且僅當(dāng)點(diǎn)p R 2滿足|u

14、p |R s (即p C u 時(shí)，節(jié)點(diǎn)u 覆蓋點(diǎn)p 或點(diǎn)p 被節(jié)點(diǎn)u 覆蓋；其中|·|表示2個(gè)點(diǎn)之間的歐氏距離。2 如果存在點(diǎn)p R 2與任意節(jié)點(diǎn)u S 滿足|up |>R s ，則傳感器節(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ū)域R 2簡化為整個(gè)平面，任意覆蓋圓在目標(biāo)區(qū)域R 2內(nèi)，所有覆蓋圓的并集構(gòu)成網(wǎng)絡(luò)的原有覆蓋范圍C ；本文研究部分覆蓋網(wǎng)絡(luò)下的覆蓋控制，這種簡化不影響問題的分析，即將目標(biāo)區(qū)域R 2內(nèi)除覆蓋范圍C 外的

15、子區(qū)域作為網(wǎng)絡(luò)的覆蓋盲區(qū)；若無特別說明，本文區(qū)域R 2是指整個(gè)平面。4 假設(shè)節(jié)點(diǎn)具有相同通信半徑R c ，且R c 2R s （注意，本文的實(shí)例分析假設(shè)R c =2R s 。）；相互位于通信半徑范圍的節(jié)點(diǎn)互為通信鄰居或通信相鄰。定義2（V oronoi 劃分14） 給定平面R 2內(nèi)n (3 個(gè)互不重疊的節(jié)點(diǎn)集S 。·18· 通 信 學(xué) 報(bào) 第31卷1 點(diǎn)p R 2與節(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 平面R 2內(nèi)所有與節(jié)點(diǎn)u S 最近點(diǎn)的集合構(gòu)成節(jié)點(diǎn)u 的V oronoi 區(qū)域V (R 2, S , u ，V

16、(R 2, S , u =p R 2 | |up |px |, x (S u (13 節(jié)點(diǎn)u 、x S 之間的垂直平分線記為L (u , x ，以垂直平分線L (u , x 為界、包含節(jié)點(diǎn)u 的半平面記為H (u , x ；任意點(diǎn)p R 2，當(dāng)且僅當(dāng)滿足|up |px |與u x 時(shí)有p H (u , x ，則V (R 2, S , u =x (S u H (u , x (24 將平面R 2內(nèi)每個(gè)點(diǎn)劃分到節(jié)點(diǎn)集S 中最近的節(jié)點(diǎn)，即所有V oronoi 區(qū)域的并集，構(gòu)成節(jié)點(diǎn)集S 在平面R 2內(nèi)唯一的V oronoi 劃分V (R 2, S 。 定義3（V oronoi 覆蓋） 對目標(biāo)區(qū)域R 2內(nèi)

17、的傳感器節(jié)點(diǎn)集S 求解V oronoi 劃分V (R 2, S 。 1 當(dāng)且僅當(dāng)任意點(diǎn)p V (R 2, S , u 滿足|up |R s時(shí)，V (R 2, S , u 或節(jié)點(diǎn)u 滿足V oronoi 覆蓋；換言之，V (R 2, S , u 滿足V oronoi 覆蓋，當(dāng)且僅當(dāng)節(jié)點(diǎn)u S 覆蓋目標(biāo)區(qū)域R 2內(nèi)所有與自己最近的點(diǎn)。2 當(dāng)且僅當(dāng)節(jié)點(diǎn)集S 中每個(gè)節(jié)點(diǎn)滿足V oronoi 覆蓋時(shí)，V (R 2, S 滿足V oronoi 覆蓋；換言之，V (R 2, S 滿足V oronoi 覆蓋，當(dāng)且僅當(dāng)目標(biāo)區(qū)域R 2內(nèi)任意點(diǎn)被節(jié)點(diǎn)集S 中的最近節(jié)點(diǎn)覆蓋。定義4（局部V oronoi 覆蓋） 給定

18、目標(biāo)區(qū)域R 2內(nèi)的傳感器節(jié)點(diǎn)集S 與傳感半徑R s 。1 設(shè)節(jié)點(diǎn)u S 與其2R s 范圍內(nèi)的鄰居為N (u ，則V (R 2, N (u , u 為節(jié)點(diǎn)u 的局部V oronoi 區(qū)域。2 當(dāng)且僅當(dāng)任意點(diǎn)p V (R 2, N (u , u 滿足|up |R s (即V (R 2, N (u , u 位于覆蓋圓C u 內(nèi) 時(shí)，V (R 2, N (u , u 或節(jié)點(diǎn)u 滿足局部V oronoi 覆蓋。例如，圖1(a給出節(jié)點(diǎn)集S =u 1, , u 12的V oronoi 劃分V (R 2, S ，圖1(b給出每個(gè)節(jié)點(diǎn)的局部V oronoi 區(qū)域，其中實(shí)線圍成包含一個(gè)節(jié)點(diǎn)的凸區(qū)域即為該節(jié)點(diǎn)的(

19、局部V oronoi 區(qū)域。 定義5（V oronoi 性質(zhì)14） 給定V oronoi 劃分V (R 2, S 。1 Voronoi 區(qū)域的邊界簡稱V oronoi 邊；如果V (R 2, S , u 與V (R 2, S , k 存在公共的V oronoi 邊，則節(jié)點(diǎn)u 、k S (u k 共享V oronoi 邊或互為V oronoi 鄰居（即V oronoi 相鄰）。2 節(jié)點(diǎn)u S 滿足u V (R 2, S , u 、且不在V oronoi 邊上；任意節(jié)點(diǎn)k S (u k 滿足k V (R 2, S , u 。(a 全局 (b局部 圖1 Voronoi 劃分與V oronoi 覆蓋3

20、 如果點(diǎn)p V (R 2, S , u 不在V oronoi 邊上，則任意節(jié)點(diǎn)k S (k u 滿足|kp |>|pu |。 4 設(shè)節(jié)點(diǎn)u 的所有V oronoi 鄰居為V n (R 2, S , u ，當(dāng)且僅當(dāng)k V n (R 2, S , u 時(shí)有u V n (R 2, S , k 。5 當(dāng)且僅當(dāng)V (R 2, S , u L (u , k ，節(jié)點(diǎn)u 、k S (u k 共享V oronoi 邊(V (R 2, S , u L (u , k 。6 Voronoi 區(qū)域是由V oronoi 邊圍成的凸多邊形區(qū)域，即22(, , (, , (, nx V R S u V R S u H

21、u x =I 。 定義6 給定局部V oronoi 區(qū)域V (R 2, N (u , u 與局部V oronoi 鄰居V n (R 2, N (u , u ，將區(qū)域V (R 2, N (u , u 內(nèi)每個(gè)點(diǎn)劃分到節(jié)點(diǎn)集V n (R 2, N (u , u 中，最近節(jié)點(diǎn)后的V oronoi 劃分為V (V (R 2, N (u , u , V n(R 2, N (u , u 。 定義7（冗余） 當(dāng)且僅當(dāng)任意點(diǎn)p C u 存在節(jié)點(diǎn)k (S u 滿足|kp |R s 時(shí)，節(jié)點(diǎn)u 為冗余節(jié)點(diǎn)或節(jié)點(diǎn)u 滿足冗余9；換言之，節(jié)點(diǎn)u 滿足冗余，當(dāng)且僅當(dāng)任意點(diǎn)p C u 被節(jié)點(diǎn)集S u 中最近的節(jié)點(diǎn)覆蓋。4

22、部分覆蓋網(wǎng)絡(luò)下的分布式V oronoi 覆蓋控制 4.1 基于局部Voronoi 區(qū)域的冗余識(shí)別規(guī)則當(dāng)網(wǎng)絡(luò)覆蓋部分目標(biāo)區(qū)域時(shí)，任意節(jié)點(diǎn)根據(jù)其2R s 范圍的鄰居求解局部V oronoi 區(qū)域后，至少有一個(gè)節(jié)點(diǎn)不滿足局部V oronoi 覆蓋15。 4.1.1 節(jié)點(diǎn)不滿足局部V oronoi 覆蓋通過分析V oronoi 區(qū)域V (R 2, S , u 與局部V oronoi區(qū)域V (R 2, N (u , u 的關(guān)系，然后給出節(jié)點(diǎn)u 在不滿足局部V oronoi 覆蓋時(shí)的冗余識(shí)別規(guī)則。引理 1 任意V oronoi 區(qū)域V (R 2, S , u 與局部V oronoi區(qū)域V (R 2, N

23、(u , u 滿足V (R 2, S , u V (R 2, N (u , u 15。 證明 依據(jù)式(2將V (R 2, S , u 改寫為V (R 2, S , u = (x (N (u u H (u , x (x (S N (u H (u , x (3 依據(jù)式(2有V (R 2, N (u , u =x (N (u u H (u , x ，將其代入式(3后有第8期 徐鵬飛等：無線傳感器網(wǎng)絡(luò)中的分布式V oronoi 覆蓋控制算法 ·19·V (R 2, S , u = V (R 2, N (u , u (x (S N (u H (u , x (4式(4表明V (R 2,

24、 S , u V (R 2, N (u , u 。證畢。 推論1 如果V (R 2, N (u , u 不滿足局部V oronoi 覆蓋，則V (R 2, S , u 不滿足V oronoi 覆蓋。證明 依據(jù)引理1，V (R 2, S , u 與V (R 2, N (u , u 滿足下列情況之一。1 V (R 2, S , u =V (R 2, N (u , u ：則V (R 2, S , u 不滿足V oronoi 覆蓋；2 V (R 2, S , u V (R 2, N (u , u ：V (R 2, S , u 位于區(qū)域V (R 2, N (u , u 內(nèi)，V (R 2, S , u 至

25、少有一條V oronoi 邊e 與V (R 2, N (u , u 的任意V oronoi 邊不重疊(否則，將有V (R 2, S , u =V (R 2, N (u , u ，依據(jù)V oronoi 性質(zhì)5 設(shè)e=V(R 2, S , u L (u , k ，則e ；設(shè)V (R 2, N (u , u L (u , k =，已知V (R 2, S , u V (R 2, N (u , u ，則有e 與；如果k N (u ，V (R 2, N (u , u 依據(jù)V oronoi 性質(zhì)5 將有V oronoi 邊，這樣V oronoi 邊e 與V (R 2, N (u , u 的V oronoi

26、邊重疊，與假設(shè)“V oronoi 邊e 與V (R 2, N (u , u 的任意V oronoi 邊不重疊”矛盾，即只能有k N (u 與|uk |>2R s ；點(diǎn)p e 滿足p V (R 2, S , u 、p L (u , k ，垂直平分線L (u , k 上的點(diǎn)p 滿足|up |uk |/2>R s ，即存在點(diǎn)p V (R 2, S , u 滿足|up |>R s ，V (R 2, S , u 不滿足V oronoi 覆蓋。綜合上述，當(dāng)V (R 2, N (u , u 不滿足局部V oronoi 覆蓋時(shí)，必有V (R 2, S , u 不滿足V oronoi 覆蓋。證

27、畢。推論2 如果V (R 2, S , u 不滿足V oronoi 覆蓋，則節(jié)點(diǎn)u 必定不滿足冗余。證明 V (R 2, S , u 不滿足V oronoi 覆蓋時(shí)，將存在點(diǎn)q V (R 2, S , u 滿足q C u ；節(jié)點(diǎn)u 為覆蓋圓C u 的圓心，線段uq 與覆蓋圓C u 的邊界交于一點(diǎn)p ，則有|pu |=R s (即p C u 與p uq (p q , pu ；依據(jù)V oronoi 性質(zhì)2 ，節(jié)點(diǎn)u V (R 2, S , u 不在V oronoi 邊上，則線段uq 在區(qū)域V (R 2, S , u 內(nèi)、與V (R 2, S , u 的任意V oronoi 邊不重疊，也就是點(diǎn)p V

28、 (R 2, S , u 不在V oronoi 邊上；依據(jù)V oronoi 性質(zhì)3 ，任意節(jié)點(diǎn)k S (k u 滿足|kp |> |pu |與|kp |>R s 。綜合上述，V (R 2, S , u 不滿足V oronoi 覆蓋時(shí)，存在點(diǎn)p C u 與任意節(jié)點(diǎn)k (S u 滿足|kp |>R s ，節(jié)點(diǎn)u 不滿足冗余。證畢。定理1 如果V (R 2, N (u , u 不滿足局部V oronoi 覆蓋，則節(jié)點(diǎn)u 必定不滿足冗余。證明 依據(jù)推論1與推論2可知。 4.1.2 節(jié)點(diǎn)滿足局部V oronoi 覆蓋當(dāng)V (R 2, N (u , u 滿足局部V oronoi 覆蓋時(shí)，

29、區(qū)域V (R 2, N (u , u 位于覆蓋圓C u 內(nèi)，覆蓋圓C u 劃分為不相交的子集：V (R 2, N (u , u 與C u V (R 2, 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 (C u V (R 2, N (u , u 存在節(jié)點(diǎn)m S (m u 滿足|mq |R s 與q V (R 2, N (m , m 。證明 已知q V (R 2, N (u , u 與q C u ，則有|uq |R s 與q R 2；若q R 2，依據(jù)式(1存在節(jié)點(diǎn)m S 滿足q V (R 2, S , m ；

30、若q V (R 2, N (u , u ，依據(jù)引理1有q V (R 2, S , u ，則有m u ；若q V (R 2, S , m ，依據(jù)式(1有|mq |uq |，則有|mq |R s ；依據(jù)引理1有V (R 2, S , m V (R 2, N (m , m ，則有q V (R 2, N (m , m 。證畢。推論4 如果V (R 2, N (u , u 滿足局部V oronoi 覆蓋，則V (R 2, S , u =V (R 2, N (u , u 、V n (R 2, S , u =V n (R 2, N (u , u 。證明 V (R 2, N (u , u 滿足V oronoi

31、 覆蓋時(shí)，任意點(diǎn)p V (R 2, N (u , u 滿足|up |R s ；任意節(jié)點(diǎn)x (S N (u 滿足u x 與|ux |>2R s ，也就有|up |<|ux |/2與p H (u , x ，則有p (x (SN (u H (u , x ；綜合上述，有 V (R 2, N (u , u (x (SN (u H (u , x ，依據(jù)式(4有V (R 2, S , u =V (R 2, N (u , u ，根據(jù)V oronoi 鄰居定義又有V n (R 2, S , u =V n (R 2, N (u , u 。證畢。引理2 如果點(diǎn)p V (R 2, S , u 與節(jié)點(diǎn)集V

32、n (R 2, 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 (R 2, N (u , u 滿足局部V oronoi 覆蓋時(shí)，如果任意點(diǎn)p V (R 2, N (u , u 被節(jié)點(diǎn)集V n (R 2, N (u , u 中最近的節(jié)點(diǎn)覆蓋，則節(jié)點(diǎn)u 滿足冗余；否則，節(jié)點(diǎn)u 不滿足冗余。證明 依據(jù)推論3，區(qū)域(C u V (R 2, N (u , u 內(nèi)任意點(diǎn)必被節(jié)點(diǎn)集S u 中最近的節(jié)點(diǎn)覆蓋，節(jié)點(diǎn)u 是否冗余取決于，區(qū)域V (R 2, N (u , u 內(nèi)任意點(diǎn)是否被節(jié)點(diǎn)集S u 中最近的節(jié)點(diǎn)覆蓋；設(shè)點(diǎn)p V (

33、R 2, N (u , u 與節(jié)點(diǎn)集V n (R 2, N (u , u 中最近的節(jié)點(diǎn)為k 。已知V (R 2, N (u , u 滿足V oronoi 覆蓋，依據(jù)推論4有V (R 2, S , u =V (R 2, N (u , u 與V n (R 2, S , u =V n (R 2, N (u , u ，則點(diǎn)p V (R 2, S , u 與節(jié)點(diǎn)集V n (R 2, S , u 中最近的節(jié)點(diǎn)為k ；依據(jù)引理2，點(diǎn)p 與節(jié)點(diǎn)集S u 中最近的節(jié)點(diǎn)為k ；換言之，任意點(diǎn)p V (R 2, N (u , u 被節(jié)點(diǎn)集V n (R 2, N (u , u 中最近的節(jié)點(diǎn)k 覆蓋，點(diǎn)p 必被節(jié)點(diǎn)集S

34、 u 中最近的節(jié)點(diǎn)k 覆蓋，節(jié)點(diǎn)u 滿足冗余；否則，存在點(diǎn)p V (R 2, N (u , u 不能被節(jié)點(diǎn)集V n (R 2, N (u , u 中最近的節(jié)點(diǎn)k 覆蓋，點(diǎn)p 也不能被節(jié)點(diǎn)集S u 中最近的節(jié)點(diǎn)k 覆蓋，節(jié)點(diǎn)u 不滿足冗余。證畢。定理2（V oronoi 冗余） 當(dāng)V (R 2, N (u , u 滿足V oronoi 覆蓋時(shí)，如果V (V (R 2, N (u , u 、V n (R 2, N (u , u ·20· 通 信 學(xué) 報(bào) 第31卷滿足V oronoi 覆蓋，則節(jié)點(diǎn)u 滿足冗余，簡稱V oronoi 冗余；否則，節(jié)點(diǎn)u 不滿足冗余。證明 如果V (

35、V (R 2, N (u , u 、V n (R 2, N (u , u 滿足V oronoi 覆蓋，則任意點(diǎn)p V (R 2, N (u , u 被節(jié)點(diǎn)集V n (R 2, N (u , u 中最近的節(jié)點(diǎn)覆蓋，依據(jù)推論5有節(jié)點(diǎn)u 滿足冗余；否則，存在點(diǎn)p V (R 2, N (u , u 不能被節(jié)點(diǎn)集V n (R 2, N (u , u 中最近的節(jié)點(diǎn)覆蓋，依據(jù)推論5將有節(jié)點(diǎn)u 不滿足冗余。證畢。定理2與文獻(xiàn)11的區(qū)別是，任意滿足局部V oronoi 覆蓋的節(jié)點(diǎn)可以進(jìn)行V oronoi 冗余識(shí)別，不管其他節(jié)點(diǎn)是否滿足局部V oronoi 覆蓋，即定理2允許網(wǎng)絡(luò)覆蓋部分目標(biāo)區(qū)域；文獻(xiàn)11要求網(wǎng)絡(luò)

36、覆蓋整個(gè)目標(biāo)區(qū)域，此時(shí)所有節(jié)點(diǎn)滿足局部V oronoi 覆蓋15；因此，文獻(xiàn)9與文獻(xiàn)11是定理2的特例情況，定理1與定理2將進(jìn)一步完善文獻(xiàn)9與文獻(xiàn)11的V oronoi 覆蓋理論。 例如圖1(b，節(jié)點(diǎn)u i (i =3,11 不滿足局部V oronoi 覆蓋，節(jié)點(diǎn)u 1、u 2滿足局部V oronoi 覆蓋，依據(jù)定理2可知節(jié)點(diǎn)u 1、u 2滿足V oronoi 冗余，如圖2(a所示；從圖1可以發(fā)現(xiàn)節(jié)點(diǎn)u 1、u 2確實(shí)為冗余節(jié)點(diǎn)。 (a 節(jié)點(diǎn)u 1、u 2滿足V oronoi 冗余 (b 節(jié)點(diǎn)u 12不滿足V oronoi 冗余圖2 Voronoi 冗余實(shí)例4.2 能量優(yōu)先的Voronoi 調(diào)

37、度規(guī)則任意節(jié)點(diǎn)根據(jù)2R s 范圍的鄰居，定理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ù)2R s 范圍內(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 狀

38、態(tài)，則繼續(xù)接收鄰居的狀態(tài)消息，直到N (u 中所有鄰居確定最終狀態(tài)，以維護(hù)活躍鄰居信息。其調(diào)度策略如下：1 V (R 2, N (u , u 不滿足局部V oronoi 覆蓋：節(jié)點(diǎn)u 依據(jù)定理1將不滿足冗余，設(shè)置為Active 狀態(tài)。2 V(R 2, N (u , u 滿足局部V oronoi 覆蓋：節(jié)點(diǎn)u 先接收N (u 中鄰居的狀態(tài)消息，標(biāo)記N (u 中的Active 節(jié)點(diǎn)、剔除N (u 中的Sleep 節(jié)點(diǎn)；當(dāng)V n (R 2, N (u , u 中包含Sleep 節(jié)點(diǎn)時(shí)，重構(gòu)剔除Sleep 節(jié)點(diǎn)后的V (R 2, N (u , u ；當(dāng)V n (R 2, N (u , u 中所有能量較

39、低(若能量相同，則節(jié)點(diǎn)ID 值較小 節(jié)點(diǎn)確定為Active 狀態(tài)后，節(jié)點(diǎn)u 使用定理2進(jìn)行冗余識(shí)別；如果節(jié)點(diǎn)u 滿足V oronoi 冗余，則為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)換第8期 徐鵬飛等：無線傳感器網(wǎng)絡(luò)中的分布式V oronoi 覆蓋控制算法 ·21·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í)，不滿足局部V oronoi 覆蓋的節(jié)點(diǎn)u i (i =3

40、,11 設(shè)置為Active 狀態(tài)，滿足局部V oronoi 覆蓋的節(jié)點(diǎn)u 1、u 2、u 12進(jìn)入While /Unset 循環(huán)；第1輪，節(jié)點(diǎn)u 1、u 2退出While /Unset 循環(huán)，執(zhí)行V oronoi 冗余識(shí)別后為Sleep 狀態(tài)，如圖2(a所示；第2輪，節(jié)點(diǎn)u 12收到節(jié)點(diǎn)u 1、u 2的睡眠消息，重構(gòu)局部V oronoi 區(qū)域、退出While /Unset 循環(huán)，執(zhí)行V oronoi 冗余識(shí)別后為Active 狀態(tài)，如圖2(b所示。每輪調(diào)度的節(jié)點(diǎn)狀態(tài)變化如表1所示。 表1 DVC 調(diào)度實(shí)例第i 輪Unset Active Sleep 初始化u 1, u 2, u 12 u 3,

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

42、目標(biāo)區(qū)域調(diào)度實(shí)例4.2.3 算法正確性分析結(jié)論1 通信相鄰、局部V oronoi 不相鄰的節(jié)點(diǎn)可以同步執(zhí)行V oronoi 冗余識(shí)別。證明 設(shè)V (R 2, N (u , u 滿足局部V oronoi 覆蓋，任意局部V oronoi 鄰居k V n (R 2, N (u , u 滿足k V n (R 2, S , u (推論4 ，則有u V n (R 2, S , k (Voronoi 性質(zhì)4 ；節(jié)點(diǎn)u 執(zhí)行V oronoi 冗余識(shí)別時(shí)，V (R 2, N (k , k 有下列情況之一。1 不滿足局部V oronoi 覆蓋：節(jié)點(diǎn)k 在初始化時(shí)已經(jīng)設(shè)置為Active 狀態(tài)。2 滿足局部V oro

43、noi 覆蓋：依據(jù)推論4有V n (R 2, N (k , k =V n (R 2, S , k ，則有u V n (R 2, N (k , k ；若k . E >u . E ，節(jié)點(diǎn)k 至少要收到節(jié)點(diǎn)u 的狀態(tài)消息后執(zhí)行V oronoi 冗余識(shí)別，即節(jié)點(diǎn)k 處于While /Unset 循環(huán)；否則，節(jié)點(diǎn)u 至少要收到節(jié)點(diǎn)k 的狀態(tài)消息后執(zhí)行V oronoi 冗余識(shí)別，即節(jié)點(diǎn)k 為Active 狀態(tài)(若為Sleep 狀態(tài)，則已從N (u 剔除了節(jié)點(diǎn)k ，有k V n (R 2, N (u , u 。綜合上述，節(jié)點(diǎn)u 執(zhí)行V oronoi 冗余識(shí)別時(shí)，其任意局部V oronoi 鄰居k 或處

44、于While /Unset 循環(huán)或?yàn)锳ctive 狀態(tài)，不會(huì)轉(zhuǎn)入睡眠狀態(tài)；換言之，局部V oronoi 相鄰節(jié)點(diǎn)異步執(zhí)行V oronoi 冗余識(shí)別，局部V oronoi 鄰居為通信鄰居的子集，即通信相鄰、局部V oronoi 不相鄰的節(jié)點(diǎn)可以同步執(zhí)行V oronoi冗余識(shí)別。證畢。例如，根據(jù)圖1(b可知節(jié)點(diǎn)u 1、u 2滿足通信相鄰、局部V oronoi 不相鄰；根據(jù)表1，節(jié)點(diǎn)u 1、u 2同步執(zhí)行V oronoi 冗余識(shí)別后轉(zhuǎn)入睡眠狀態(tài)。 推論6 如果V (R 2, N (u , u 滿足局部V oronoi 覆蓋，點(diǎn)p V (R 2, N (u , u 與節(jié)點(diǎn)集V n (R 2, N (u

45、 , u 中最近的節(jié)點(diǎn)為k ，則有p V (R 2,(N (k u , k 。 證明 依據(jù)推論5的證明，點(diǎn)p 與節(jié)點(diǎn)集S u 中最近的節(jié)點(diǎn)仍是k ，依據(jù)式(1有p V (R 2,(S u , k ；顯然，(N (k u 為(S u 的子集，依據(jù)引理1有V (R 2,(S u , k V (R 2,(N (k u , k ，則有p V (R 2,(N (k u , k 。證畢。結(jié)論2 DVC 可以維持網(wǎng)絡(luò)原有的覆蓋范圍。 證明 設(shè)V (R 2, N (u , u 滿足局部V oronoi 覆蓋，節(jié)點(diǎn)u 執(zhí)行V oronoi 冗余識(shí)別后轉(zhuǎn)入睡眠狀態(tài)。1 任意點(diǎn)p V (R 2, N (u , u

46、：節(jié)點(diǎn)集V n (R 2, 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 后的局部V oronoi 區(qū)域?qū)c(diǎn)p (推論6 ；節(jié)點(diǎn)k 在后繼調(diào)度過程中，只有其局部V oronoi 鄰居覆蓋點(diǎn)p 的情況下，才有可能轉(zhuǎn)入睡眠狀態(tài)。 2 任意點(diǎn)q (C u V (R 2, N (u , u ：存在節(jié)點(diǎn)m S (m u 滿足q V (R 2, N (m , m 與|mq |R s (推論3 ；若節(jié)點(diǎn)m 為活躍狀

47、態(tài)，節(jié)點(diǎn)m 在任何時(shí)刻都可以覆蓋點(diǎn)q ；否則，將有V (R 2, N (m , m 滿足局部Voronoi 覆蓋，節(jié)點(diǎn)m 只有在其局部Voronoi 鄰居覆蓋點(diǎn)q V (R 2, N (m , m 的情況下，才有可能轉(zhuǎn)入睡眠狀態(tài)。·22· 通 信 學(xué) 報(bào) 第31卷綜上所述，V oronoi 冗余節(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 如果R c 2R s 、V (R 2, S 滿足V oronoi 覆蓋，則節(jié)點(diǎn)集S 構(gòu)成連通網(wǎng)絡(luò)。證明 V (R 2, S 的直線對偶圖D (S 為連通圖，圖D (S

48、 中任意邊關(guān)聯(lián)的節(jié)點(diǎn)u 、k 共享V oronoi 邊e 14；依據(jù)V oronoi 性質(zhì)5 設(shè)e =V (R 2, S , u L (u , k ，點(diǎn)p e 滿足p V (R 2, S , u 、p L (u , k ；若V (R 2, S 滿足V oronoi 覆蓋，有V (R 2, S , u 滿足V oronoi 覆蓋，則有|up |R s ；垂直平分線L (u , k 上的點(diǎn)p 滿足|uk |2|up |，則有|uk |R c ；因此，連通圖D (S 的任意邊即為一條通信鏈路，節(jié)點(diǎn)集S 構(gòu)成連通網(wǎng)絡(luò)。證畢。推論8 任意節(jié)點(diǎn)u 、k S (k u 存在節(jié)點(diǎn)m V n (R 2, S ,

49、 u (m u 滿足|km |<|ku |。證明 根據(jù)V oronoi 性質(zhì)2 有k V (R 2, S , u ；設(shè)k =p ，則有p V (R 2, S , u ；如果任意節(jié)點(diǎn)x V n (R 2, S , u 滿足p H (u , x ，根據(jù)V oronoi 性質(zhì)6 有p V (R 2, S , u ，與“p V (R 2, S , u ”矛盾；即存在節(jié)點(diǎn)m V n (R 2, S , u 滿足m u 與p H (u , m ，則有|up |>|pm |，即|km |<|ku |。證畢。結(jié)論3 如果R c 2R s ，則DVC 可以保持網(wǎng)絡(luò)原有連通性。證明 設(shè)V (R

50、2, N (u , u 滿足局部V oronoi 覆蓋，節(jié)點(diǎn)u 執(zhí)行V oronoi 冗余識(shí)別后轉(zhuǎn)入睡眠狀態(tài)；依據(jù)定理2有V (V (R 2, N (u , u , V n (R 2, N (u , u , u 滿足V oronoi 覆蓋，不會(huì)轉(zhuǎn)入睡眠狀態(tài)的節(jié)點(diǎn)集V n (R 2, N (u , u (結(jié)論1的證明 構(gòu)成連通子網(wǎng)(推論7 ；節(jié)點(diǎn)u 的任意通信鄰居k (即|ku |R c 存在節(jié)點(diǎn)m V n (R 2, S , u 滿足|km |<|ku |與|km |R c (推論8 ；根據(jù)推論5有V n (R 2, S , u =V n (R 2, N (u , u ；綜上所述，節(jié)點(diǎn)u

51、 的任意2個(gè)通信鄰居可以通過節(jié)點(diǎn)集V n (R 2, N (u , u 連通，即V oronoi 冗余節(jié)點(diǎn)轉(zhuǎn)入睡眠狀態(tài)后不影響網(wǎng)絡(luò)原有連通性。證畢。引理3 給定n 個(gè)節(jié)點(diǎn)，求解任意V oronoi 區(qū)域的計(jì)算復(fù)雜度為O (n 15。結(jié)論4 V oronoi 冗余識(shí)別的計(jì)算復(fù)雜度為O (1，與節(jié)點(diǎn)密度無關(guān)。證明 V oronoi 邊的交點(diǎn)簡稱V oronoi 頂點(diǎn)，節(jié)點(diǎn)滿足V oronoi 覆蓋等價(jià)于其所有V oronoi 頂點(diǎn)在覆蓋圓內(nèi)9,11,15；V (R 2, N (u , u 的局部V oronoi 鄰居與局部V oronoi 頂點(diǎn)的平均值為6，與節(jié)點(diǎn)數(shù)量無關(guān)14。分別求解V (R 2

52、, N (u , u 滿足局部V oronoi 覆蓋與V (V (R 2, N (u , u , V n (R 2, N (u , u 滿足V oronoi 覆蓋的計(jì)算復(fù)雜度均為O (1。綜合上述，V oronoi 冗余識(shí)別的計(jì)算復(fù)雜度為O (1，與節(jié)點(diǎn)密度無關(guān)。證畢。結(jié)論5 DVC 的計(jì)算復(fù)雜度為O (m 2 ，其中m 為2R s 范圍內(nèi)的鄰居數(shù)。證明 根據(jù)引理3，初始化求解V n (R 2, N (u , u 、While /Unset 循環(huán)重構(gòu)V (R 2, N (u , u 的計(jì)算復(fù)雜度均為O (m ；V n (R 2, N (u , u 中能量較低節(jié)點(diǎn)確定為Active 狀態(tài)后退出W

53、hile /Unset 循環(huán)，V n (R 2, N (u , u 為N (u 的子集，循環(huán)次數(shù)不會(huì)超過m ，即While /Unset 循環(huán)的計(jì)算復(fù)雜度為O (m 2 ；Finalize 過程中V oronoi 冗余識(shí)別的計(jì)算復(fù)雜度為O (1。綜上所述，DVC 的計(jì)算復(fù)雜度為O (m 2 。結(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ù)2R s 范圍內(nèi)的鄰居信息，確定最終狀態(tài)后向2R s 范圍內(nèi)的鄰居廣播1個(gè)狀態(tài)消息；即DVC 的消息復(fù)雜度為O (1，整個(gè)網(wǎng)絡(luò)的消息復(fù)雜度為O (n 。證畢。5 仿真實(shí)驗(yàn)分

54、析本文利用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 (即部署密度 、傳感半徑R s (設(shè)R c =2R s 對活躍節(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 、RC

55、T 小于100%時(shí)，網(wǎng)絡(luò)覆蓋部分目標(biāo)區(qū)域。1 隨機(jī)均勻部署5002 000個(gè)節(jié)點(diǎn)后： 當(dāng)R s =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)R s =100時(shí)，網(wǎng)絡(luò)覆蓋目標(biāo)區(qū)域的面積比率RCT 已經(jīng)超過99%；直到n >1 000，完全覆蓋網(wǎng)絡(luò)的比率PCC 才收斂于100%；如圖6(b所示。第8期 徐鵬飛等：無線傳感器網(wǎng)絡(luò)中的分布式V oronoi 覆蓋控制算法 ·23· 圖6 覆蓋質(zhì)量分析2 隨機(jī)均勻

56、部署n 個(gè)節(jié)點(diǎn)，隨著傳感半徑R s 的增大，覆蓋整個(gè)目標(biāo)區(qū)域的概率增大。當(dāng)n =1 000、R s 100時(shí)，完全覆蓋網(wǎng)絡(luò)的比率PCC 收斂于100%，如圖6(c所示；當(dāng)n =1 500、R s 80時(shí)，完全覆蓋網(wǎng)絡(luò)的比率PCC 收斂于100%，如圖6(d所示；當(dāng)n 1 000、R s 50時(shí)，網(wǎng)絡(luò)覆蓋目標(biāo)區(qū)域的面積比率RCT 已經(jīng)超過99.8%。 3 設(shè)覆蓋點(diǎn)p R 2的節(jié)點(diǎn)數(shù)為K (p ，覆蓋度22( p R K p R 是衡量網(wǎng)絡(luò)能量效率、覆蓋冗余程度的一個(gè)指標(biāo)9。隨機(jī)均勻部署網(wǎng)絡(luò)的覆蓋度，隨著節(jié)點(diǎn)數(shù)量n 近似線性增長，隨著傳感半徑R s 近似指數(shù)增長，如圖7所示；當(dāng)網(wǎng)絡(luò)覆蓋目標(biāo)區(qū)域的面

57、積比率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)R s =50時(shí)，DVC 活躍節(jié)點(diǎn)將隨著節(jié)點(diǎn)數(shù)量n 近似收斂于282，如圖8(a所示；當(dāng)R s =100時(shí)，DVC 活躍節(jié)點(diǎn)將隨著節(jié)點(diǎn)數(shù)量n 近似收斂于75，如圖8(b所示；隨機(jī)均勻部署n 個(gè)節(jié)點(diǎn)后，隨著傳感半徑R s 的增大，DVC 活躍節(jié)點(diǎn)將逐漸減少，如R s =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)，主要由傳感半徑R s 確定；總的來說，隨著節(jié)點(diǎn)數(shù)量n 或傳感半徑R s 的增大，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.13.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)，但是