無線傳感器網(wǎng)絡(luò)中基于Voronoi覆蓋及Delaunay三角剖分圖的最小剛性拓?fù)淇刂扑惴?/h1>
2016-11-10 05:21:22薛亮陳晰趙繼軍黎作鵬關(guān)新平
自動(dòng)化學(xué)報(bào) 2016年10期
薛亮 陳晰 趙繼軍 黎作鵬 關(guān)新平
無線傳感器網(wǎng)絡(luò)中基于Voronoi覆蓋及Delaunay三角剖分圖的最小剛性拓?fù)淇刂扑惴?/p>
薛亮1，2陳晰1趙繼軍1，2黎作鵬1關(guān)新平3
為同時(shí)滿足覆蓋與節(jié)能應(yīng)用需求，本文提出了無線傳感器網(wǎng)絡(luò)中一種最小剛性拓?fù)淇刂扑惴∕RTc（Minimal rigid topology control algorithm based on Voronoi coverage and Delaunay triangulation）.該算法基于Voronoi覆蓋機(jī)制，準(zhǔn)確控制節(jié)點(diǎn)工作狀態(tài)，實(shí)現(xiàn)活動(dòng)節(jié)點(diǎn)對(duì)目標(biāo)區(qū)域的完全覆蓋.在此基礎(chǔ)上，MRTc利用Delaunay三角剖分圖的特點(diǎn)，構(gòu)建出適用于無線傳感器網(wǎng)絡(luò)的最小剛性拓?fù)浣Y(jié)構(gòu).該結(jié)構(gòu)有效約束了網(wǎng)絡(luò)平均節(jié)點(diǎn)度，且同時(shí)具有容錯(cuò)性、覆蓋性和稀疏性.此外，MRTc引入節(jié)點(diǎn)功率控制策略，在維持網(wǎng)絡(luò)完全覆蓋的基礎(chǔ)上最小化節(jié)點(diǎn)能耗.仿真結(jié)果進(jìn)一步驗(yàn)證了本文提出的MRTc算法的有效性.
無線傳感器網(wǎng)絡(luò)，拓?fù)淇刂疲钚傂?，Voronoi覆蓋，Delaunay三角剖分圖
引用格式薛亮，陳晰，趙繼軍，黎作鵬，關(guān)新平.無線傳感器網(wǎng)絡(luò)中基于Voronoi覆蓋及Delaunay三角剖分圖的最小剛性拓?fù)淇刂扑惴?自動(dòng)化學(xué)報(bào)，2016，42（10）:1570-1584
降低網(wǎng)絡(luò)能耗、限制網(wǎng)絡(luò)平均節(jié)點(diǎn)度以及提高網(wǎng)絡(luò)容錯(cuò)性是無線傳感器網(wǎng)絡(luò)（Wireless sensor networks，WSNs）中的重要問題，而拓?fù)淇刂扑惴ǖ闹饕蝿?wù)是在滿足網(wǎng)絡(luò)連通性和覆蓋性的前提下，使得網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)依據(jù)給定的規(guī)則從它的物理鄰居節(jié)點(diǎn)間選取合適的邏輯鄰居節(jié)點(diǎn)，形成一個(gè)優(yōu)化的網(wǎng)絡(luò)結(jié)構(gòu)，以達(dá)到降低網(wǎng)絡(luò)能耗［1-4］，限制平均節(jié)點(diǎn)度，提高網(wǎng)絡(luò)容錯(cuò)性的目的.
降低網(wǎng)絡(luò)能耗是能量受限網(wǎng)絡(luò)協(xié)議設(shè)計(jì)的首要目標(biāo).由于傳感器節(jié)點(diǎn)的體積限制，其可用能量必然有限［5］，因此，對(duì)于能量受限的無線傳感器網(wǎng)絡(luò)來說降低網(wǎng)絡(luò)能耗是構(gòu)建拓?fù)浣Y(jié)構(gòu)需要考慮的首要因素.目前，拓?fù)淇刂萍夹g(shù)中主要有兩種節(jié)能策略：1）通過調(diào)節(jié)網(wǎng)絡(luò)中各節(jié)點(diǎn)的傳輸功率實(shí)現(xiàn)降低網(wǎng)絡(luò)能耗的目的；2）是將網(wǎng)絡(luò)中部分節(jié)點(diǎn)調(diào)節(jié)為休眠狀態(tài)以達(dá)到降低網(wǎng)絡(luò)能耗的目標(biāo).本文為進(jìn)一步降低網(wǎng)絡(luò)能耗，采用睡眠調(diào)度與功率控制方案，以更好地實(shí)現(xiàn)節(jié)能降耗目標(biāo).
有效限制平均節(jié)點(diǎn)度是拓?fù)淇刂萍夹g(shù)中的另一個(gè)重要設(shè)計(jì)指標(biāo).網(wǎng)絡(luò)節(jié)點(diǎn)度是指與該節(jié)點(diǎn)存在直接通信鏈路的一跳鄰居節(jié)點(diǎn)的數(shù)目.在無線傳感器網(wǎng)絡(luò)中，高的網(wǎng)絡(luò)平均節(jié)點(diǎn)度需要在MAC（Media access control）層設(shè)計(jì)相應(yīng)的接入訪問控制機(jī)制，節(jié)點(diǎn)度過高時(shí)還可能引發(fā)訪問沖突和數(shù)據(jù)碰撞，浪費(fèi)節(jié)點(diǎn)有限的能量.因此，密集部署的無線傳感器網(wǎng)絡(luò)中，限制網(wǎng)絡(luò)的平均節(jié)點(diǎn)度是十分必要的.
網(wǎng)絡(luò)的容錯(cuò)性能是拓?fù)錁?gòu)建過程中需要考慮的另一個(gè)重要指標(biāo).無線傳感器網(wǎng)絡(luò)經(jīng)常部署于惡劣的環(huán)境中，一旦網(wǎng)絡(luò)中某個(gè)節(jié)點(diǎn)遭到破壞或能量耗盡，將可能導(dǎo)致整個(gè)網(wǎng)絡(luò)癱瘓以致其不能正常運(yùn)行.因此，在拓?fù)淇刂扑惴ǖ脑O(shè)計(jì)中需要考慮網(wǎng)絡(luò)的容錯(cuò)性.
基于上述設(shè)計(jì)目標(biāo)，本文提出了一個(gè)基于Voronoi覆蓋及 Delaunay三角剖分圖的無線傳感器網(wǎng)絡(luò)最小剛性拓?fù)淇刂扑惴ǎ∕inimal rigid topology control algorithm based on Voronoi coverage and Delaunay triangulation，MRTc），該算法基于Voronoi原理調(diào)節(jié)節(jié)點(diǎn)的活動(dòng)狀態(tài)，實(shí)現(xiàn)了目標(biāo)區(qū)域的全覆蓋，在此基礎(chǔ)上基于Delaunay三角剖分圖構(gòu)建了最小剛性拓?fù)浣Y(jié)構(gòu).本文的主要貢獻(xiàn)為：1）采用睡眠調(diào)度與功率控制相結(jié)合的方法，在保持網(wǎng)絡(luò)連通的情況下進(jìn)一步降低網(wǎng)絡(luò)能耗；2）提出定理，為構(gòu)建基于Delaunay三角剖分圖的最小剛性拓?fù)涮峁┝死碚撘罁?jù)；3）充分利用最小剛性拓?fù)涞奶匦?，?-容錯(cuò)、稀疏性以及平均節(jié)點(diǎn)度有限等特點(diǎn)，實(shí)現(xiàn)了提高網(wǎng)絡(luò)魯棒性、簡化路由計(jì)算、降低節(jié)點(diǎn)間干擾的目標(biāo).
1 相關(guān)工作
作為無線傳感器網(wǎng)絡(luò)的基礎(chǔ)技術(shù)，拓?fù)淇刂萍夹g(shù)已引起學(xué)者的廣泛關(guān)注［6-15］.通過拓?fù)淇刂疲梢杂行Ы档途W(wǎng)絡(luò)能耗、限制節(jié)點(diǎn)度以及提高網(wǎng)絡(luò)的容錯(cuò)性.
降低網(wǎng)絡(luò)能耗是拓?fù)淇刂扑惴ㄐ枰紫瓤紤]的設(shè)計(jì)目標(biāo).近幾年來，研究人員提出了多種面向節(jié)能應(yīng)用的拓?fù)淇刂扑惴ǎ?-9］，其節(jié)能方案主要有功率控制和睡眠調(diào)度兩種.對(duì)于功率控制而言，其主要思想為通過調(diào)節(jié)網(wǎng)絡(luò)中所有節(jié)點(diǎn)的功率來降低網(wǎng)絡(luò)能耗.例如文獻(xiàn)［6］中的COMPOW（Smallest common power）算法和文獻(xiàn)［7］中的CBTC（Conebased distributed topology-control）算法.COMPOW算法中所有節(jié)點(diǎn)采用能夠保持整個(gè)網(wǎng)絡(luò)連通的最小功率，統(tǒng)一的功率設(shè)置確保了網(wǎng)絡(luò)中鏈路的雙向連通性，且功率的最小化達(dá)到了降低網(wǎng)路能耗的目的.CBTC算法中每個(gè)節(jié)點(diǎn)則通過調(diào)整各自的傳輸功率，使得以該節(jié)點(diǎn)為中心，當(dāng)在任意角度α（α≤5π/6）的扇形區(qū)域內(nèi)至少存在一個(gè)鄰居節(jié)點(diǎn)時(shí)，能夠保持網(wǎng)絡(luò)的連通性，降低網(wǎng)絡(luò)能耗.在睡眠調(diào)度方面，Chen等［8］提出的Span算法其基本思想是：在維持網(wǎng)絡(luò)連通性的前提下，網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)根據(jù)其剩余能量、鄰居節(jié)點(diǎn)個(gè)數(shù)以及節(jié)點(diǎn)效用等多種因素，自適應(yīng)地判定該節(jié)點(diǎn)成為骨干節(jié)點(diǎn)或休眠節(jié)點(diǎn).對(duì)于MSNL（Maximization of sensor network life）算法［9］而言，節(jié)點(diǎn)狀態(tài)可細(xì)分為活動(dòng)、休眠以及過渡狀態(tài).處于過渡狀態(tài)的節(jié)點(diǎn)將進(jìn)行實(shí)時(shí)監(jiān)測，且當(dāng)其發(fā)現(xiàn)自身的監(jiān)測區(qū)域不能被其余處于活動(dòng)狀態(tài)或過渡狀態(tài)的節(jié)點(diǎn)覆蓋時(shí)，此過渡狀態(tài)節(jié)點(diǎn)轉(zhuǎn)化為活動(dòng)狀態(tài).上述4種算法均采用睡眠調(diào)度或功率控制中的一種方案面向節(jié)能設(shè)計(jì)而缺乏對(duì)多種方法的結(jié)合的運(yùn)用.本文針對(duì)上述弊端，提出了基于Voronoi覆蓋的睡眠調(diào)度與功率控制相結(jié)合的方案，進(jìn)一步降低網(wǎng)絡(luò)能耗.
作為拓?fù)淇刂萍夹g(shù)的重要設(shè)計(jì)目標(biāo)之一，節(jié)點(diǎn)度的限制問題已成為國內(nèi)外學(xué)者的研究熱點(diǎn).文獻(xiàn)［10］中，Li等提出了LMST（Local minimum spanning tree）算法，算法中節(jié)點(diǎn)相互獨(dú)立地構(gòu)建局部最小生成樹，并根據(jù)鄰近圖中與之距離最遠(yuǎn)的邏輯鄰居節(jié)點(diǎn)確定自身功率.此外，文獻(xiàn)中證明了LMST算法中每個(gè)節(jié)點(diǎn)的節(jié)點(diǎn)度均不大于6，網(wǎng)絡(luò)的平均節(jié)點(diǎn)度接近于最小生成樹算法，略高于2，可見該算法限制了網(wǎng)絡(luò)的平均節(jié)點(diǎn)度.在LMST算法基礎(chǔ)上，文獻(xiàn)［11］通過定義每條鏈路的臨界能耗，提出一種基于LMST的改進(jìn)算法X-LMST.它旨在以鏈路的能量有效性為指標(biāo)，構(gòu)建局部最小生成樹，網(wǎng)絡(luò)中節(jié)點(diǎn)的度數(shù)不多于6.LMST算法和X-LMST算法雖然限制了網(wǎng)絡(luò)平均節(jié)點(diǎn)度，但是這兩個(gè)算法均是1-容錯(cuò)的，如果網(wǎng)絡(luò)中的某條鏈路因節(jié)點(diǎn)能量耗盡或環(huán)境干擾而意外中斷，將會(huì)導(dǎo)致網(wǎng)絡(luò)失效.Delaunay三角剖分圖和UDG（Unit disk graph）圖相結(jié)合，刪除Delaunay三角剖分圖中不能相互通信的鏈路，構(gòu)建出Udel拓?fù)浣Y(jié)構(gòu)［12］，該拓?fù)涫莟-支撐的，并且經(jīng)Udel算法優(yōu)化后得到的拓?fù)浣Y(jié)構(gòu)的平均節(jié)點(diǎn)度不高于6.然而，該拓?fù)浣Y(jié)構(gòu)是集中式拓?fù)?，需要已知網(wǎng)絡(luò)的全局信息.
容錯(cuò)性是拓?fù)淇刂萍夹g(shù)的另一重要設(shè)計(jì)目標(biāo).目前，已有較多文獻(xiàn)關(guān)注網(wǎng)絡(luò)容錯(cuò)性能的研究.文獻(xiàn)［13］中Xu等提出了一個(gè)典型的睡眠調(diào)度算法GAF（Geographical adaptive fidelity），它以劃分網(wǎng)格的方式將節(jié)點(diǎn)分組，通過睡眠調(diào)度的方法使每個(gè)網(wǎng)格中僅保留一個(gè)活動(dòng)節(jié)點(diǎn)，網(wǎng)格內(nèi)其余節(jié)點(diǎn)則調(diào)節(jié)為休眠狀態(tài)，以降低網(wǎng)絡(luò)能量消耗.理論上，GAF算法是4-容錯(cuò)的，有著良好的容錯(cuò)性能.但是，GAF算法中節(jié)點(diǎn)的平均度數(shù)較大.過高的節(jié)點(diǎn)度會(huì)在節(jié)點(diǎn)間引發(fā)較嚴(yán)重的干擾和沖突，嚴(yán)重時(shí)引起數(shù)據(jù)包重傳，造成不必要的能量浪費(fèi).蘇金樹等［14］提出了一種容錯(cuò)算法，該算法在局部最小生成樹（LMST）的基礎(chǔ)上，通過增添鏈路的方式減少網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中的割邊和割點(diǎn)的數(shù)目，構(gòu)建了一個(gè)2-容錯(cuò)的拓?fù)浣Y(jié)構(gòu).實(shí)驗(yàn)證明，該拓?fù)渚哂幸欢ǖ木W(wǎng)絡(luò)容錯(cuò)性能.然而，該算法在刪除拓?fù)涞母钸吅透铧c(diǎn)時(shí)，需要已知網(wǎng)絡(luò)的全局信息，增加了算法的計(jì)算復(fù)雜度.文獻(xiàn)［15］中提出的FGSSk（Fault-tolerant global spanning subgraph）算法是Kruskal最小生成樹算法在k-容錯(cuò)的網(wǎng)絡(luò)中的推廣，它是一個(gè)集中式的拓?fù)淇刂扑惴?此算法通過插入較短鏈路的方式構(gòu)建了一個(gè)k-容錯(cuò)的拓?fù)浣Y(jié)構(gòu)，由于該算法是集中式算法，網(wǎng)絡(luò)中所有節(jié)點(diǎn)均需了解全局信息，因此，該算法的計(jì)算量較大.
針對(duì)上述算法的局限性，本文綜合考慮了網(wǎng)絡(luò)能耗、平均節(jié)點(diǎn)度以及容錯(cuò)性三方面內(nèi)容，提出了基于Voronoi覆蓋及Delaunay三角剖分圖的無線傳感器網(wǎng)絡(luò)最小剛性拓?fù)淇刂扑惴?該算法首先依據(jù)Voronoi覆蓋原理，判斷網(wǎng)絡(luò)中的覆蓋冗余節(jié)點(diǎn)，在保證網(wǎng)絡(luò)區(qū)域全覆蓋的條件下，將其調(diào)節(jié)為休眠狀態(tài).然后，在活動(dòng)節(jié)點(diǎn)間，構(gòu)建基于Delaunay三角剖分圖的無線傳感器網(wǎng)絡(luò)最小剛性拓?fù)浣Y(jié)構(gòu).算法中睡眠調(diào)度與功率控制相結(jié)合，在保持網(wǎng)絡(luò)連通性的情況下，進(jìn)一步降低網(wǎng)絡(luò)能耗.文中所提出的定理對(duì)于構(gòu)建具有2-容錯(cuò)、稀疏性的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，提高網(wǎng)絡(luò)魯棒性，有效約束平均節(jié)點(diǎn)度，提供了理論依據(jù)和基礎(chǔ).文中第4節(jié)分析證明了MRTc算法的性能；算法性能評(píng)估與結(jié)果分析在第5節(jié)給出.
2 網(wǎng)絡(luò)模型與定義
2.1網(wǎng)絡(luò)模型
在二維空間中，無線傳感器網(wǎng)絡(luò)可用一個(gè)無向圖（Undirected graph）Gu（Vu，εu）來表示.其中，Vu=｛1，2，···，n｝表示無線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)的集合；εu=｛（lu）ji，i∈Vu，j∈Vu｝為網(wǎng)絡(luò)中節(jié)點(diǎn)間可相互通信的鏈路集.在同構(gòu)網(wǎng)絡(luò)中，如果兩個(gè)節(jié)點(diǎn)i和j的歐氏距離滿足（其中，rc為節(jié)點(diǎn)的通信半徑），則稱節(jié)點(diǎn)i與j互為通信鄰居［16］.若兩節(jié)點(diǎn)可相互通信，鏈路本文中，Ni為節(jié)點(diǎn)i的通信鄰居的集合，集合Ni中的元素個(gè)數(shù)（集合Ni的勢）定義為節(jié)點(diǎn)i的度Di（Di=|Ni|，也可簡稱為i的節(jié)點(diǎn)度）.網(wǎng)絡(luò)中所有節(jié)點(diǎn)的度的平均值Dev稱為網(wǎng)絡(luò)平均節(jié)點(diǎn)度
為了方便后文分析，給出以下常用定義.
定義2（稀疏性）［5］.網(wǎng)絡(luò)拓?fù)渖珊?，若拓?fù)渲械逆溌窋?shù)目與節(jié)點(diǎn)數(shù)目滿足線性關(guān)系，則稱該網(wǎng)絡(luò)拓?fù)渚哂邢∈栊?
定義3（區(qū)域完全覆蓋）.如果監(jiān)測區(qū)域內(nèi)的任意一點(diǎn)均能夠被至少一個(gè)活動(dòng)節(jié)點(diǎn)成功感知，則稱該監(jiān)測區(qū)域被完全覆蓋.
本文假設(shè)無線傳感器網(wǎng)絡(luò)是同構(gòu)網(wǎng)絡(luò)，即網(wǎng)絡(luò)中所有節(jié)點(diǎn)的屬性相同，且節(jié)點(diǎn)的位置信息已知.節(jié)點(diǎn)的通信范圍和覆蓋范圍（也稱感知區(qū)域）可以看作以節(jié)點(diǎn)為中心，分別以通信半徑rc和感知半徑rs為半徑的圓盤，并且網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)具有唯一的身份標(biāo)識(shí)ID.
此外，我們引入一種常用于無線傳感器網(wǎng)絡(luò)中的無線傳輸能量消耗模型［16］.在該模型中，節(jié)點(diǎn)的工作能耗由發(fā)送器能耗和放大器能耗兩部分構(gòu)成，接收能耗為接收器能耗.網(wǎng)絡(luò)節(jié)點(diǎn)的發(fā)射消耗與傳輸距離d有關(guān).因此，節(jié)點(diǎn)傳輸k bits的信息所需的發(fā)射能耗為
接收k bits信息的接收能耗為
其中，Eelec為發(fā)射電路和接收電路的能量消耗，k為傳輸數(shù)據(jù)比特?cái)?shù)，εfs為自由空間傳輸模型系數(shù).
2.2Voronoi覆蓋原理
無線傳感器網(wǎng)絡(luò)中，由于大量節(jié)點(diǎn)部署于監(jiān)測區(qū)域內(nèi)，部分區(qū)域可被多個(gè)節(jié)點(diǎn)同時(shí)覆蓋，同一監(jiān)測信息也可被多個(gè)節(jié)點(diǎn)重復(fù)感知，導(dǎo)致大量的冗余感知數(shù)據(jù).針對(duì)該問題，本文采用Voronoi覆蓋方案，將網(wǎng)絡(luò)中的覆蓋冗余節(jié)點(diǎn)調(diào)整為休眠狀態(tài)，在保證網(wǎng)絡(luò)區(qū)域完全覆蓋的前提下降低網(wǎng)絡(luò)能耗.為了清楚地闡述Voronoi覆蓋原理，給出以下定義4～定義7.
定義4（感應(yīng)鄰居）.在網(wǎng)絡(luò)中，如果一個(gè)節(jié)點(diǎn)i的感知區(qū)域和另外一個(gè)節(jié)點(diǎn)j的感知區(qū)域相交（i/=j），則稱這兩個(gè)節(jié)點(diǎn)i，j互為感應(yīng)鄰居.
定義5（Voronoi鄰居）.在二維無線傳感器網(wǎng)絡(luò)中，如果節(jié)點(diǎn)i所形成的Voronoi多邊形與節(jié)點(diǎn)j所形成的Voronoi多邊形共邊，則稱節(jié)點(diǎn)i和節(jié)點(diǎn)j互為Voronoi鄰居.
定義6（2-Voronoi圖）.在網(wǎng)絡(luò)拓?fù)渲校绻サ艄?jié)點(diǎn)i后，由i的Voronoi鄰居構(gòu)成的Voronoi圖稱為節(jié)點(diǎn)i的2-Voronoi圖.節(jié)點(diǎn)i的2-Voronoi圖的頂點(diǎn)稱為2-Voronoi頂點(diǎn)，記為節(jié)點(diǎn)i的 2-Voronoi圖的邊與節(jié)點(diǎn)i自身覆蓋圓盤邊界的交點(diǎn)，稱為2-Voronoi交點(diǎn)，記為
舉例而言，圖1為節(jié)點(diǎn)i的2-Voronoi圖.其中，節(jié)點(diǎn)j，k，m，n均為節(jié)點(diǎn)i的Voronoi鄰居節(jié)點(diǎn).由圖1可知，節(jié)點(diǎn)i的2-Voronoi頂點(diǎn)有兩個(gè)，分別為和節(jié)點(diǎn)i的2-Voronoi交點(diǎn)有4個(gè)，它們分別為和
圖1 節(jié)點(diǎn)i的2-Voronoi圖Fig.1 The 2-Voronoi diagram of node i
定義7（冗余節(jié)點(diǎn)）.如果一個(gè)節(jié)點(diǎn)的感知區(qū)域被其他節(jié)點(diǎn)完全覆蓋，我們就稱該節(jié)點(diǎn)為冗余節(jié)點(diǎn).
為了簡化計(jì)算，我們使用引理1僅根據(jù)節(jié)點(diǎn)感應(yīng)鄰居的信息分布式地判斷節(jié)點(diǎn)的冗余性.文獻(xiàn)［17］證明了引理1的復(fù)雜度僅為O（NlogN），其中，N為單個(gè)節(jié)點(diǎn)的Voronoi鄰居的個(gè)數(shù).
引理1［17］.節(jié)點(diǎn)i是一個(gè)冗余節(jié)點(diǎn)的充分必要條件是節(jié)點(diǎn)i的2-Voronoi頂點(diǎn)和的2-Voronoi交點(diǎn)均被其Voronoi鄰居覆蓋.
然而，在使用引理1判斷冗余節(jié)點(diǎn)時(shí)，如果兩個(gè)冗余節(jié)點(diǎn)互為Voronoi鄰居節(jié)點(diǎn)，同時(shí)將它們調(diào)節(jié)為休眠狀態(tài)后，它們感知區(qū)域的交叉區(qū)域可能不會(huì)被完全覆蓋.為了解決該問題，本文將所有冗余節(jié)點(diǎn)看做一個(gè)新的無向圖其中，為所有冗余節(jié)點(diǎn)的集合，為互為Voronoi鄰居的冗余節(jié)點(diǎn)間的鏈路集.然后計(jì)算圖的最大獨(dú)立集1最大獨(dú)立集:假設(shè)存在一個(gè)無向圖Gu（Vu，Eu），如果集合S?Vu且S/=?，若S中任意頂點(diǎn)在圖Gu中邏輯不相鄰則稱集合S為圖Gu的獨(dú)立集，如果不存在|S′|＞|S|，則稱集合S為圖Gu的最大獨(dú)立集.，最大獨(dú)立集中的節(jié)點(diǎn)即為覆蓋區(qū)域的盲節(jié)點(diǎn).為了保證監(jiān)測區(qū)域的完全覆蓋，將這部分盲節(jié)點(diǎn)調(diào)節(jié)為活動(dòng)狀態(tài)，其余冗余節(jié)點(diǎn)（即覆蓋冗余節(jié)點(diǎn)）進(jìn)入休眠狀態(tài).
綜上所述，Voronoi覆蓋原理可概括為：每個(gè)節(jié)點(diǎn)分布式的收集其感應(yīng)鄰居的信息后構(gòu)建局部的Voronoi圖，然后由其Voronoi鄰居構(gòu)建2-Voronoi圖，并找出所有的2-Voronoi頂點(diǎn)和所有的2-Voronoi交點(diǎn)，并根據(jù)引理1判斷其是否為冗余節(jié)點(diǎn).最后通過計(jì)算圖的最大獨(dú)立集找出網(wǎng)絡(luò)的盲節(jié)點(diǎn)，將其調(diào)節(jié)為活動(dòng)狀態(tài)，其余冗余節(jié)點(diǎn)維持休眠狀態(tài).此方法可保證在監(jiān)測區(qū)域完全覆蓋的基礎(chǔ)上，減少活動(dòng)節(jié)點(diǎn)數(shù)量，因此可以進(jìn)一步降低能耗.
2.3最小剛性拓?fù)?/p>
最小剛性拓?fù)渲忻總€(gè)頂點(diǎn)至少連有兩條鏈路，并且它的鏈路數(shù)與節(jié)點(diǎn)數(shù)滿足線性關(guān)系，它滿足無線傳感器網(wǎng)絡(luò)2-容錯(cuò)的特性以及稀疏性.為了構(gòu)建容錯(cuò)且稀疏的拓?fù)浣Y(jié)構(gòu)，本文在活動(dòng)節(jié)點(diǎn)間構(gòu)建最小剛性拓?fù)?如果對(duì)網(wǎng)絡(luò)拓?fù)渲胁糠宙溌返拈L度加以限制，就可以維持整個(gè)拓?fù)錁?gòu)型不變，那么就稱該網(wǎng)絡(luò)拓?fù)涫且粋€(gè)剛性拓?fù)洌?］.如果一個(gè)拓?fù)洳皇莿傂缘?，則稱該拓?fù)錇榭勺冃瓮負(fù)?圖2（a）和圖2（b）分別為由4個(gè)節(jié)點(diǎn)構(gòu)成的剛性拓?fù)渑c可變形拓?fù)?由圖2易知，組成剛性拓?fù)涞娜我庖粋€(gè)節(jié)點(diǎn)至少連有兩條鏈路.
圖2 剛性拓?fù)浜涂勺冃瓮負(fù)洌ǎ╝）剛性拓?fù)?；（b）可變形拓?fù)?；（c）最小剛性拓?fù)洌〧ig.2 The rigid topology and flexible topology（（a）Rigid topology；（b）Flexible topology；（c）Minimal rigid topology）
如果刪除一個(gè)剛性拓?fù)渲械娜我庖粭l鏈路則會(huì)影響該拓?fù)涞膭傂?，我們稱這樣的拓?fù)錇樽钚傂酝負(fù)?顯然地，最小剛性拓?fù)涫擎溌窋?shù)最少的剛性拓?fù)洌?8］.圖2（c）為二維空間中由4個(gè)節(jié)點(diǎn)構(gòu)成的最小剛性拓?fù)?在二維空間中，給定一個(gè)含有n個(gè)節(jié)點(diǎn)的拓?fù)浣Y(jié)構(gòu)G（V，ε（t）），節(jié)點(diǎn)i位置的時(shí)變函數(shù)為qi（t）=f（xi（t），yi（t））（其中，i=1，2，···，n）.本文假設(shè)每個(gè)節(jié)點(diǎn)的位置函數(shù)qi（t）是可微的.如果拓?fù)渲械娜我庖粭l鏈路滿足||qi（t）-qj（t）||=c（其中，c為正實(shí)數(shù)），則稱該鏈路的移動(dòng)為剛性移動(dòng).在此基礎(chǔ)上，如果該鏈路同時(shí)滿足則稱為該拓?fù)浣Y(jié)構(gòu)的無窮小變形.如果一個(gè)拓?fù)浣Y(jié)構(gòu)的無窮小變形均是由剛性移動(dòng)引起的，那么則稱該拓?fù)浣Y(jié)構(gòu)為無窮小剛性拓?fù)?顯然，無窮小剛性拓?fù)湟彩且粋€(gè)剛性拓?fù)?
本文引入剛性矩陣檢測某個(gè)拓?fù)涫欠窬哂袆傂裕⑤o助生成剛性拓?fù)浣Y(jié)構(gòu).鏈路集ε中的每一條鏈路，均可用于轉(zhuǎn)化并對(duì)應(yīng)生成剛性矩陣中的一個(gè)行向量.設(shè)鏈路集ε中的所有鏈路均可隨機(jī)排序，當(dāng)構(gòu)建一個(gè)剛性矩陣為網(wǎng)絡(luò)拓?fù)渲械逆溌窋?shù)）時(shí)，ε中第k條鏈路對(duì)應(yīng)于剛性矩陣M中第k行元素構(gòu)成的行向量（如式（4）所示）.
以下引理2和引理3分別描述了剛性矩陣與無窮小剛性拓?fù)?、無窮小剛性拓?fù)渑c最小剛性拓?fù)渲g的內(nèi)在聯(lián)系.
引理2［19］.在二維空間中，假設(shè)矩陣M為n個(gè)傳感器節(jié)點(diǎn)所構(gòu)成拓?fù)涞膭傂跃仃?，該拓?fù)涫菬o窮小剛性的當(dāng)且僅當(dāng)Rank（M）=2n-3.
引理3［5］.由n個(gè)傳感器節(jié)點(diǎn)構(gòu)成的鏈路數(shù)為2n-3的無窮小剛性拓?fù)涫亲钚傂酝負(fù)?
以下引理4表明可以分布式地生成最小剛性拓?fù)?
引理4［16］.一個(gè)剛性拓?fù)銰的一個(gè)子拓?fù)銰′被其他剛性拓?fù)銰′′替代后，得到一個(gè)新拓?fù)淠敲葱峦負(fù)涫莿傂缘?
2.4Delaunay三角剖分圖
Delaunay三角剖分圖是由Voronoi鄰居節(jié)點(diǎn)相互連接而成的三角形，其外接圓圓心是與該三角形相關(guān)的Voronoi圖的一個(gè)頂點(diǎn).圖3為由傳感器節(jié)點(diǎn)構(gòu)成Voronoi圖與Delaunay三角剖分圖，其中，虛線表示由節(jié)點(diǎn)構(gòu)成的Voronoi圖，實(shí)線表示由這些節(jié)點(diǎn)構(gòu)成的Delaunay三角剖分圖.以Delaunay三角剖分圖中任意兩個(gè)三角形（如圖3中所示的矩形虛線框內(nèi)的三角形）為例，以下定理1使用數(shù)學(xué)歸納法證明由n（n≥3）個(gè)節(jié)點(diǎn)構(gòu)成的Delaunay三角剖分圖至少含有2n-3條鏈路，并且它是剛性的.
圖3 節(jié)點(diǎn)的Voronoi圖以及Delaunay三角剖分圖Fig.3 The Voronoi graph and Delaunay triangulation of nodes
定理1.在無線傳感器網(wǎng)絡(luò)中，每個(gè)節(jié)點(diǎn)與其n-1（n≥3）個(gè)通信鄰居節(jié)點(diǎn)構(gòu)成的Delaunay三角剖分圖的鏈路數(shù)不小于2n-3，且其是剛性的.
證明.采用數(shù)學(xué)歸納法證明由n（n≥3）個(gè)傳感器節(jié)點(diǎn)構(gòu)成的Delaunay三角剖分圖至少含有2n-3條鏈路.假設(shè)由n個(gè)傳感器節(jié)點(diǎn)構(gòu)成的Delaunay三角剖分圖的鏈路數(shù)為m.
1）當(dāng)n=3時(shí)，Delaunay三角剖分圖的鏈路數(shù)m=3，滿足鏈路數(shù)不小于2n-3；
2）假設(shè)當(dāng)n=k時(shí)，Delaunay三角剖分圖的鏈路數(shù)m≥2k-3；
3）當(dāng)n=k+1時(shí)，根據(jù)生成Delaunay三角剖分圖逐點(diǎn)插入法［20］的原理可知在原來的Delaunay三角剖分圖中任意插入一點(diǎn)Q時(shí)，共包含有兩種情況：
a）插入點(diǎn)Q在三角形的內(nèi)部：如圖4（a）所示，△IJN和△JNM為Delaunay三角剖分圖中相鄰的兩個(gè)三角形，如圖4（a）所示，當(dāng)插入點(diǎn)Q在△IJN的內(nèi)部時(shí)，連接IQ，JQ和NQ，然后逐個(gè)對(duì)它們進(jìn)行外接圓檢測.通過交換對(duì)角線的方法，保證所形成的圖形（如圖4（a）所示）為Delaunay三角剖分圖.因此，在這種情況下增加一點(diǎn)Q后，形成的Delaunay三角剖分圖增加了三條鏈路，即當(dāng)n=k+1時(shí)，Delaunay三角剖分圖的鏈路數(shù)m′=m+3≥2k-3+3=2k≥2（k+1）-3.
圖4 Delaunay三角剖分圖逐點(diǎn)插入法（（a）插入點(diǎn)Q在△IJN的內(nèi)部；（b）插入點(diǎn)Q在邊JN上）Fig.4 Point by point insertion method of Delaunay triangulation（（a）Insertion node Q in the interior of a triangle△IJN；（b）Insertion node Q is on the JN）
b）插入點(diǎn)Q在三角形的邊上：如圖4（b）所示，當(dāng)插入點(diǎn)Q在公共邊JN上時(shí)，連接IQ和MQ，并且JN被分成了兩條鏈路JQ和NQ，然后逐個(gè)對(duì)它們進(jìn)行外接圓檢測，通過交換對(duì)角線的方法來保證所形成的圖形為Delaunay三角剖分圖.因此，在這種情況下增加一點(diǎn)Q后形成的Delaunay三角剖分圖，同樣增加了三條鏈路，即當(dāng)n=k+1時(shí)，Delaunay三角剖分圖的鏈路數(shù)m′=m+3≥2k-3+3=2k≥2（k+1）-3.因此，當(dāng)n=k+1時(shí)，Delaunay三角剖分圖的鏈路數(shù)不小于2n-3.
因此，每個(gè)傳感器節(jié)點(diǎn)與其n-1（n≥3）個(gè)鄰居節(jié)點(diǎn)構(gòu)成的Delaunay三角剖分圖的鏈路數(shù)m滿足m≥2n-3.
以上我們證明了每個(gè)傳感器節(jié)點(diǎn)與其n-1（n≥3）個(gè)鄰居節(jié)點(diǎn)構(gòu)成的Delaunay三角剖分圖的鏈路數(shù)m滿足m≥2n-3.實(shí)際上，Delaunay三角剖分圖是由若干個(gè)三角形構(gòu)成的，根據(jù)引理4可知?jiǎng)傂酝負(fù)銰的一個(gè)子拓?fù)銰′被其他剛性拓?fù)銰′′替代后，得到一個(gè)新拓?fù)涫莿傂缘?，而三角形是一個(gè)最簡單的剛性圖，因此由n（n≥3）個(gè)傳感器節(jié)點(diǎn)構(gòu)成的Delaunay剖分圖是剛性的.
綜上所述，由n（n≥3）個(gè)傳感器節(jié)點(diǎn)構(gòu)成的Delaunay剖分圖至少含有2n-3條鏈路，且其是剛性的.
基于定理1，我們給出了以下定理2，為分布式的生成基于Delaunay三角剖分圖的最小剛性拓?fù)涮峁┝死碚撘罁?jù).
定理2.如果網(wǎng)絡(luò)中任意節(jié)點(diǎn)i與其通信鄰居節(jié)點(diǎn)構(gòu)成基于Delaunay三角剖分圖的最小剛性拓?fù)溆洖镚i（i=1，···，n），Gm（Vm，εm）為網(wǎng)絡(luò)節(jié)點(diǎn)生成的全局最小剛性拓?fù)洌瑒t有以下結(jié)論：
1）若Gi與Gj（i/=j）有公共節(jié)點(diǎn)e和f，如果存在鏈路且那么
2）若Gi與Gj（i/=j）有n個(gè)公共節(jié)點(diǎn)，且Gi或Gj中存在由該n個(gè)節(jié)點(diǎn)構(gòu)成的圈2圈:節(jié)點(diǎn)間鏈路首尾相連構(gòu)成的封閉回路.，如果拓?fù)銰j中存在m（2m≤n）條鏈路（鏈路的頂點(diǎn)均為公共點(diǎn)）滿足但拓?fù)銰i中同樣存在m條鏈路（鏈路的頂點(diǎn)均為公共點(diǎn)）與中任意鏈路均不相同）滿足且m條鏈路的權(quán)值和大于另外m條鏈路那么，將權(quán)值和較小的鏈路代替權(quán)值和較大的鏈路后，再刪除滿足條件1）的鏈路，得到的拓?fù)涫亲钚傂酝負(fù)?
證明.1）假設(shè)Gi與Gj（i/=j）有公共節(jié)點(diǎn)e和f，如果存在且由于最小剛性拓?fù)涫擎溌窋?shù)最少的剛性拓?fù)?因此，連接最小剛性拓?fù)渲腥我鈨蓚€(gè)不存在鏈路的點(diǎn)，得到的拓?fù)渫瑯邮莿傂缘?，故存在是剛性?根據(jù)引理4一個(gè)剛性拓?fù)涞淖油負(fù)溆闪硗庖粋€(gè)剛性拓?fù)浯娴玫降耐負(fù)淙匀皇莿傂缘?因此，可用Gi替換來保持最終拓?fù)淙匀皇莿傂缘?，因此，去掉該鏈路不改變拓?fù)涞膭傂蕴匦?，即得證.
2）假設(shè)Gi與Gj（i/=j）有n個(gè)公共節(jié)點(diǎn)，且Gi或Gj中存在由該n個(gè)節(jié)點(diǎn)構(gòu)成的圈，如果拓?fù)銰j中存在m條鏈路（鏈路的頂點(diǎn)均為公共點(diǎn)）滿足但拓?fù)銰i中存在m 條鏈路（鏈路的頂點(diǎn)均為公共點(diǎn)）（q=1，···，m）與中任意鏈路均不相同）滿足但由于生成Delaunay三角剖分圖時(shí)，在同一個(gè)圈內(nèi)生成三角形的連接鏈路不同，如果直接刪除滿足條件1）的鏈路，即同時(shí)刪除和則圈內(nèi)的剛性不能保證，全局拓?fù)涞膭傂砸膊荒鼙ＷC，因此，則將權(quán)值和較小的鏈路代替權(quán)值和較大的鏈路后，根據(jù)引理4一個(gè)剛性拓?fù)涞淖油負(fù)溆闪硗庖粋€(gè)剛性拓?fù)浯嫔傻男峦負(fù)涫莿傂缘?，由于新拓?fù)渑c原拓?fù)銰i有相同的鏈路，因此拓?fù)涫亲钚傂酝負(fù)?，然后刪除滿足條件1）的鏈路.用Gij（Vij，εij）表示由拓?fù)浜屯負(fù)銰j（Vj，εj）的公共節(jié)點(diǎn)組成的拓?fù)洌渲?，Vij=Vi∩Vj，εij表示兩個(gè)頂點(diǎn)均在Vij中的鏈路，因此有令εij=as∪bs1∪bs2，其中，as表示拓?fù)渑cGj的公共鏈路，bs1和bs2分別表示εij中僅存在于和Gj中的鏈路.同時(shí)刪除bs1和bs2后，每個(gè)子拓?fù)錆M足否則，至少存在一條鏈路使或Gj的鏈路數(shù)超過這與條件或Gj均為最小剛性拓?fù)湎嗝?假設(shè)刪除bs1和bs2后得到的拓?fù)溆谐^2|Vi∪Vj|-3的鏈路，則Gij有|εij|＞2|Vij|-3，這將導(dǎo)致在刪除bs1和bs2之前，或Gj的鏈路數(shù)超過2|Vi|-3或2|Vj|-3，這與條件或Gj均為最小剛性拓?fù)湎嗝埽虼?，得到的拓?fù)錆M足-3.由上述1）可知?jiǎng)h除bs1和bs2后不改變拓?fù)涞膭傂裕虼?，有因此，刪除bs1和 bs2后有，生成的最終拓?fù)錇樽钚傂酝負(fù)?
3 MRTc算法
本節(jié)我們?cè)敿?xì)介紹基于Voronoi覆蓋及Delaun -ay三角剖分圖的最小剛性拓?fù)淇刂扑惴∕RTc.算法執(zhí)行過程可分為以下4個(gè)階段：1）信息收集階段，網(wǎng)絡(luò)中各節(jié)點(diǎn)僅根據(jù)其感知鄰居節(jié)點(diǎn)和通信鄰居節(jié)點(diǎn)的信息構(gòu)建拓?fù)?，可降低網(wǎng)絡(luò)中消息傳送數(shù)量；2）權(quán)值確定階段，利用權(quán)值函數(shù)判定權(quán)值大小，保證拓?fù)浣Y(jié)構(gòu)的唯一性；3）拓?fù)錁?gòu)建階段，網(wǎng)絡(luò)首先分布式確定覆蓋冗余節(jié)點(diǎn)，將其調(diào)節(jié)為休眠狀態(tài)，在保證網(wǎng)絡(luò)監(jiān)測區(qū)域完全覆蓋的條件下，通過減少活動(dòng)節(jié)點(diǎn)數(shù)量，降低網(wǎng)絡(luò)能耗.然后通過構(gòu)建基于Delaunay三角剖分圖的最小剛性拓?fù)浣Y(jié)構(gòu)，提高網(wǎng)絡(luò)容錯(cuò)性，并可限制平均節(jié)點(diǎn)度數(shù)；4）功率調(diào)節(jié)階段，為了進(jìn)一步地降低網(wǎng)絡(luò)能耗，將每個(gè)節(jié)點(diǎn)的功率調(diào)節(jié)為網(wǎng)絡(luò)所需要的最小功率.
3.1信息收集
首先，MRTc算法采用與文獻(xiàn)［5］相同的機(jī)制實(shí)現(xiàn)通信鄰居節(jié)點(diǎn)的收集.通過該機(jī)制，網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)均能獲得其通信鄰居節(jié)點(diǎn)的信息，該信息包含每個(gè)通信鄰居節(jié)點(diǎn)的ID、節(jié)點(diǎn)位置坐標(biāo)以及與其通信鄰居節(jié)點(diǎn)的歐氏距離.通過這些信息，可得知每個(gè)節(jié)點(diǎn)的通信鄰居和感應(yīng)鄰居，也可通過下節(jié)的權(quán)值函數(shù)計(jì)算該節(jié)點(diǎn)與其通信鄰居節(jié)點(diǎn)的鏈路權(quán)值.
3.2權(quán)值函數(shù)的確定
無線傳感器網(wǎng)絡(luò)中保證兩節(jié)點(diǎn)i，j通信所需要的最小傳輸功率［11］為其中，α和 δ為可調(diào)參數(shù)，并且與特定無線通信系統(tǒng)硬件和傳輸環(huán)境有關(guān)，通常有2≤α≤4.顯然，傳輸功率隨著兩節(jié)點(diǎn)間距離的增加而增大.因此，本文用兩點(diǎn)間的距離代表這兩點(diǎn)間鏈路的權(quán)值.然而，在無線傳感器網(wǎng)絡(luò)中，不同節(jié)點(diǎn)間的距離可能相同，這會(huì)導(dǎo)致鏈路不同，但卻擁有相同的權(quán)值，所生成的最終拓?fù)浣Y(jié)構(gòu)不唯一.
為了保證生成拓?fù)涞奈ㄒ恍?，本文采用了以下?quán)值函數(shù).當(dāng)節(jié)點(diǎn)間距離滿足如式（6）～式（8）所示的三個(gè)條件之一時(shí)，即可得鏈路與的權(quán)值函數(shù)滿足
式中，id（i），id（j），id（m），id（n）分別表示節(jié)點(diǎn)i，j，m，n的ID.由于每個(gè)節(jié)點(diǎn)的ID是唯一的，因此該權(quán)值函數(shù)w保證了擁有最小權(quán)值的鏈路具有唯一性，由此可知使用MRTc算法生成的拓?fù)浣Y(jié)構(gòu)也是唯一的.
3.3拓?fù)錁?gòu)建
1）冗余節(jié)點(diǎn)選擇與休眠調(diào)度
監(jiān)測區(qū)域的良好覆蓋性是傳感器網(wǎng)絡(luò)拓?fù)錁?gòu)建的基本要求之一.由于節(jié)點(diǎn)經(jīng)常采用隨機(jī)部署方式，導(dǎo)致部分監(jiān)測區(qū)域可被多個(gè)節(jié)點(diǎn)同時(shí)覆蓋，由此產(chǎn)生大量冗余感知信息.因此，在保證網(wǎng)絡(luò)全覆蓋的前提下，將覆蓋冗余節(jié)點(diǎn)調(diào)節(jié)為休眠狀態(tài)，對(duì)于降低網(wǎng)絡(luò)能耗是必要的.本文第2.2節(jié)中Voronoi覆蓋原理提供了判定覆蓋冗余節(jié)點(diǎn)的理論依據(jù)，它能夠保證在將選出的覆蓋冗余節(jié)點(diǎn)調(diào)節(jié)為休眠狀態(tài)后，活動(dòng)節(jié)點(diǎn)依然能夠保持對(duì)監(jiān)測區(qū)域的完全覆蓋.其具體過程如MRTc算法偽代碼中第4～10行偽代碼所示.
2）基于Delaunay三角剖分圖的最小剛性拓?fù)涞臉?gòu)建
為了提高網(wǎng)絡(luò)的魯棒性，同時(shí)限制網(wǎng)絡(luò)的平均節(jié)點(diǎn)度.本節(jié)基于定理2，將覆蓋冗余節(jié)點(diǎn)調(diào)節(jié)為休眠狀態(tài)后，在活動(dòng)節(jié)點(diǎn)間構(gòu)建了基于Delaunay三角剖分圖的最小剛性拓?fù)浣Y(jié)構(gòu).構(gòu)建該拓?fù)涞牟襟E如下：
步驟1.每個(gè)節(jié)點(diǎn)與其鄰居節(jié)點(diǎn)構(gòu)建Delaunay三角剖分圖；
步驟2.在Delaunay三角剖分圖的基礎(chǔ)上不損失剛性的前提下刪除較長鏈路構(gòu)建局部最小剛性拓?fù)洌?/p>
步驟3.刪除不屬于全局最小剛性拓?fù)涞逆溌?，可?gòu)建全局最小剛性拓?fù)?
3.4功率調(diào)節(jié)
算法的最終階段，為了進(jìn)一步降低網(wǎng)絡(luò)能耗，對(duì)網(wǎng)絡(luò)中活動(dòng)節(jié)點(diǎn)的功率進(jìn)行調(diào)節(jié).功率調(diào)節(jié)時(shí)，每個(gè)節(jié)點(diǎn)將自身功率設(shè)置為能夠覆蓋其全部邏輯鄰居節(jié)點(diǎn)（節(jié)點(diǎn)i的邏輯鄰居節(jié)點(diǎn)即為經(jīng)過MRTc算法優(yōu)化后，仍然與節(jié)點(diǎn)i有通信關(guān)系的節(jié)點(diǎn)）所需要的最小功率，即節(jié)點(diǎn)能與距離其最遠(yuǎn)的邏輯鄰居節(jié)點(diǎn)成功通信的功率.這意味著可將每個(gè)活動(dòng)節(jié)點(diǎn)的通信半徑設(shè)置為與其距離最遠(yuǎn)的邏輯鄰居節(jié)點(diǎn)的距離.節(jié)點(diǎn)通信半徑的公式如下所示.
其中，rc（i）為節(jié)點(diǎn)i的通信半徑，為節(jié)點(diǎn)i的邏輯鄰居節(jié)點(diǎn)的集合.
分布式構(gòu)建基于Voronoi覆蓋與Delaunay三角剖分圖的最小剛拓?fù)浣Y(jié)構(gòu)的MRTc算法的偽代碼如下所示.
首先，節(jié)點(diǎn)通過信息的收集得到節(jié)點(diǎn)的感應(yīng)鄰居集合和通信鄰居節(jié)點(diǎn)集合（行1～2）.接著第3行根據(jù)第3.2節(jié)權(quán)值函數(shù)確定節(jié)點(diǎn)與通信鄰居節(jié)點(diǎn)的權(quán)值.行4～32為拓?fù)涞臉?gòu)建階段，該階段節(jié)點(diǎn)首先根據(jù)覆蓋原理（見第2.2節(jié)Voronoi覆蓋原理）確定網(wǎng)絡(luò)中的覆蓋冗余節(jié)點(diǎn)，并將其調(diào)節(jié)為休眠狀態(tài)（行4～10）.然后，在活動(dòng)節(jié)點(diǎn)間構(gòu)建基于Delaunay三角剖分圖的最小剛性拓?fù)浣Y(jié)構(gòu)，改善網(wǎng)絡(luò)容錯(cuò)性，有效約束網(wǎng)絡(luò)的平均節(jié)點(diǎn)度（行11～32）.算法的最終階段（行33）每個(gè)節(jié)點(diǎn)通過調(diào)節(jié)其傳輸功率來降低網(wǎng)絡(luò)能耗，將功率調(diào)節(jié)為能夠覆蓋所有邏輯鄰居節(jié)點(diǎn)的最小功率，（即）.
4 MRTc算法性能分析
MRTc算法使得網(wǎng)絡(luò)中的覆蓋冗余節(jié)點(diǎn)調(diào)節(jié)為休眠狀態(tài)，并在活動(dòng)節(jié)點(diǎn)間構(gòu)建最小剛性拓?fù)浣Y(jié)構(gòu)，有效降低了網(wǎng)絡(luò)能耗，該算法還具有以下4個(gè)方面的性質(zhì).
性質(zhì)1.由n個(gè)傳感器節(jié)點(diǎn)形成的初始拓?fù)?初始拓?fù)?沒有經(jīng)過任何算法優(yōu)化的起始拓?fù)浣Y(jié)構(gòu)GC（VC，εC），在經(jīng)過MRTc算法優(yōu)化后得到的拓?fù)浣Y(jié)構(gòu)GD（VD，εD）是2-容錯(cuò)的.
證明.通過第2.3節(jié)，我們可知構(gòu)成最小剛性拓?fù)涞娜我庖粋€(gè)節(jié)點(diǎn)至少連有兩條鏈路，由于初始拓?fù)銰C（VC，εC）經(jīng)過MRTc算法優(yōu)化后，得到的拓?fù)涫亲钚傂酝負(fù)?因此，拓?fù)浣Y(jié)構(gòu)GD（VD，εD）中的任意一個(gè)節(jié)點(diǎn)至少連接有兩條鏈路，即拓?fù)渲械娜我夤?jié)點(diǎn)至少含有兩條鏈路，根據(jù)第2.1節(jié)k-容錯(cuò)的定義可知，最終生成的拓?fù)涫?-容錯(cuò)的.
性質(zhì)2.由n個(gè)傳感器節(jié)點(diǎn)形成的初始拓?fù)銰C（VC，εC），在經(jīng)過MRTc算法優(yōu)化后得到的拓?fù)浣Y(jié)構(gòu)GD（VD，εD）滿足區(qū)域完全覆蓋.
證明.根據(jù)第2.2節(jié)覆蓋冗余節(jié)點(diǎn)的定義可知，如果一個(gè)節(jié)點(diǎn)的覆蓋區(qū)域被其他節(jié)點(diǎn)完全覆蓋，則該節(jié)點(diǎn)為覆蓋冗余節(jié)點(diǎn).經(jīng)算法MRTc優(yōu)化后，這些覆蓋冗余節(jié)點(diǎn)被調(diào)節(jié)為休眠狀態(tài)后，它們的覆蓋區(qū)域仍然可以被其他節(jié)點(diǎn)所覆蓋.因此，由n個(gè)傳感器形成的初始拓?fù)銰C（VC，εC），在經(jīng)過MRTc算法優(yōu)化后得到的拓?fù)浣Y(jié)構(gòu)GD（VD，εD）滿足區(qū)域完全覆蓋.
性質(zhì)3.由n個(gè)傳感器節(jié)點(diǎn)形成的初始拓?fù)銰C（VC，εC），在經(jīng)過MRTc算法優(yōu)化后得到的拓?fù)浣Y(jié)構(gòu)GD（VD，εD）是稀疏的.
證明.根據(jù)第2.1節(jié)網(wǎng)絡(luò)稀疏性的定義，可知若拓?fù)錆M足網(wǎng)絡(luò)稀疏性要求，需要網(wǎng)絡(luò)中的鏈路數(shù)量與節(jié)點(diǎn)數(shù)量之間呈線性關(guān)系.又根據(jù)第2.3節(jié)引理3知，由任意n個(gè)節(jié)點(diǎn)構(gòu)成的最小剛性圖有2n-3條鏈路.由于GC（VC，εC）在經(jīng)過MRTc算法優(yōu)化后，得到的拓?fù)浣Y(jié)構(gòu)GD（VD，εD）是一個(gè)最小剛性拓?fù)?，即拓?fù)銰D（VD，εD）中的鏈路數(shù)量和節(jié)點(diǎn)數(shù)量呈線性關(guān)系.所以，經(jīng)過MRTc算法優(yōu)化后得到的拓?fù)浣Y(jié)構(gòu)GD（VD，εD）是稀疏的.
性質(zhì)4.經(jīng)過MRTc算法優(yōu)化后得到的拓?fù)浣Y(jié)構(gòu)GD（VD，εD），其平均節(jié)點(diǎn)度不大于4.
證明.由引理3和定理2可知，經(jīng)MRTc算法優(yōu)化后的拓?fù)浣Y(jié)構(gòu)GD（VD，εD）有2n-3條鏈路.根據(jù)握手定理［21］可知，對(duì)于任意拓?fù)銰（V，ε），網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)度之和為2|ε|，其中|ε|為該拓?fù)渲墟溌返臄?shù)目.因此，拓?fù)浣Y(jié)構(gòu)GD（VD，εD）中所有節(jié)點(diǎn)的節(jié)點(diǎn)度之和為故它的平均節(jié)點(diǎn)度為即拓?fù)浣Y(jié)構(gòu)GD（VD，εD）的平均網(wǎng)絡(luò)節(jié)點(diǎn)度不超過4.
5 MRTc算法性能評(píng)價(jià)
為了分析和評(píng)價(jià)MRTc算法的性能，本文在Matlab R2009a環(huán)境中，使用M語言設(shè)計(jì)了以下4組數(shù)值仿真實(shí)驗(yàn).實(shí)驗(yàn)1分別在均勻和隨機(jī)兩種網(wǎng)絡(luò)中驗(yàn)證睡眠調(diào)度方案的性能；實(shí)驗(yàn)2以52個(gè)節(jié)點(diǎn)為例詳細(xì)介紹了同構(gòu)網(wǎng)絡(luò)拓?fù)涞臉?gòu)建過程；實(shí)驗(yàn)3通過比較4種典型算法，驗(yàn)證了MRTc算法的性能；實(shí)驗(yàn)4對(duì)最小剛性拓?fù)浣Y(jié)構(gòu)下睡眠調(diào)度前后網(wǎng)絡(luò)的總能耗以及活動(dòng)節(jié)點(diǎn)的比例進(jìn)行了詳細(xì)比較.本文所有實(shí)驗(yàn)均假設(shè)監(jiān)測區(qū)域?yàn)?00×100的方形區(qū)域，傳感器節(jié)點(diǎn)的最大感知半徑設(shè)為20.監(jiān)測區(qū)域范圍與節(jié)點(diǎn)感知半徑的大小見文獻(xiàn)［22］.節(jié)點(diǎn)的最大通信半徑為40.在均勻網(wǎng)絡(luò)中，每個(gè)傳感器節(jié)點(diǎn)均位于網(wǎng)格的頂點(diǎn)，網(wǎng)格大小設(shè)置為式中n為監(jiān)測區(qū)域內(nèi)布置的節(jié)點(diǎn)數(shù)目，ra為每個(gè)網(wǎng)格的長度值，rb為每個(gè)網(wǎng)格的寬度值.
5.1實(shí)驗(yàn)1冗余節(jié)點(diǎn)選擇與休眠調(diào)度
降低網(wǎng)絡(luò)能耗是拓?fù)淇刂频闹饕O(shè)計(jì)目標(biāo)，為了實(shí)現(xiàn)該目標(biāo)，本文采用了睡眠調(diào)度方案在保證網(wǎng)絡(luò)監(jiān)測區(qū)域全覆蓋的前提下，將覆蓋冗余節(jié)點(diǎn)調(diào)節(jié)為休眠狀態(tài).為了驗(yàn)證睡眠調(diào)度方案的性能，本實(shí)驗(yàn)分別在均勻網(wǎng)絡(luò)和隨機(jī)網(wǎng)絡(luò)兩種網(wǎng)絡(luò)中進(jìn)行仿真實(shí)驗(yàn).圖5和圖6分別為在均勻網(wǎng)絡(luò)和隨機(jī)網(wǎng)絡(luò)中部署70個(gè)節(jié)點(diǎn)時(shí)，睡眠調(diào)度前后的監(jiān)測區(qū)域覆蓋情況.節(jié)點(diǎn)感知半徑均為20.由這4個(gè)子圖可以看出在經(jīng)過睡眠調(diào)度后，監(jiān)測區(qū)域仍然被活動(dòng)節(jié)點(diǎn)完全覆蓋滿足性質(zhì)2.
圖5 均勻網(wǎng)絡(luò)睡眠調(diào)度（（a）睡眠調(diào)度前；（b）睡眠調(diào)度后）Fig.5 The sleep scheduling in uniform networks（（a）Before the sleep scheduling；（b）After the sleep scheduling）
圖6 隨機(jī)網(wǎng)絡(luò)睡眠調(diào)度（（a）睡眠調(diào)度前；（b）睡眠調(diào)度后）Fig.6 The sleep scheduling in random networks（（a）Before the sleep scheduling；（b）After the sleep scheduling）
當(dāng)節(jié)點(diǎn)數(shù)量分別為49、56、63、70、77時(shí)，算法的覆蓋性能如圖7所示，子圖7（a）、7（b）分別為實(shí)驗(yàn)中冗余節(jié)點(diǎn)的數(shù)目和冗余節(jié)點(diǎn)比例.由圖7（a）、7（b）可知，無論在均勻網(wǎng)絡(luò)中還是冗余網(wǎng)絡(luò)中，冗余節(jié)點(diǎn)的數(shù)目隨著網(wǎng)絡(luò)節(jié)點(diǎn)密度的增大而增加，并且冗余節(jié)點(diǎn)的占比也隨之增大.該結(jié)果表明對(duì)于節(jié)點(diǎn)密度不同的網(wǎng)絡(luò)，該算法均可以起到較好的睡眠調(diào)度效果.
5.2實(shí)驗(yàn)2網(wǎng)絡(luò)拓?fù)涞臉?gòu)建過程
在實(shí)驗(yàn)1的基礎(chǔ)上，我們以52個(gè)節(jié)點(diǎn)為例詳細(xì)介紹網(wǎng)絡(luò)拓?fù)涞臉?gòu)建過程.首先，將52個(gè)感知半徑為20的節(jié)點(diǎn)隨機(jī)部署在100×100的監(jiān)測區(qū)域內(nèi)，節(jié)點(diǎn)的分布情況與監(jiān)測區(qū)域的覆蓋情況如圖8（a）所示.根據(jù)Voronoi覆蓋原理選擇覆蓋冗余節(jié)點(diǎn)，并將覆蓋冗余節(jié)點(diǎn)調(diào)節(jié)為休眠狀態(tài).活動(dòng)節(jié)點(diǎn)對(duì)監(jiān)測區(qū)域的覆蓋情況如圖8（b）所示.由圖8（b）可以看出，在將部分節(jié)點(diǎn)調(diào)節(jié)為休眠節(jié)點(diǎn)后，監(jiān)測區(qū)域內(nèi)的任意一點(diǎn)仍至少被一個(gè)活動(dòng)節(jié)點(diǎn)覆蓋.可見，經(jīng)過睡眠調(diào)度后，網(wǎng)絡(luò)滿足完全覆蓋.在此基礎(chǔ)上，每個(gè)活動(dòng)節(jié)點(diǎn)與其鄰居節(jié)點(diǎn)生成局部的Delaunay三角剖分圖，構(gòu)建局部最小剛性拓?fù)浣Y(jié)構(gòu)如圖9（a）所示，圖中實(shí)線表示兩點(diǎn)間的實(shí)際鏈路，虛線表示可以被刪除的鏈路.每個(gè)節(jié)點(diǎn)在維持剛性的前提下刪除權(quán)重較大的鏈路，與其鄰居節(jié)點(diǎn)構(gòu)建權(quán)重和最小的局部最小剛性拓?fù)淙鐖D9（b）所示.最后根據(jù)定理2，刪除不屬于全局最小剛性拓?fù)涞逆溌罚瑯?gòu)建起全局最小剛性拓?fù)浣Y(jié)構(gòu)，如圖9（c）所示.
由該實(shí)驗(yàn)容易看出，經(jīng)MRTc算法優(yōu)化后的拓?fù)?，即圖9（c）中的任意一個(gè)節(jié)點(diǎn)至少連有兩條鏈路.這意味著該拓?fù)浣Y(jié)構(gòu)是2-容錯(cuò)的，滿足性質(zhì)1.圖9（c）與圖9（a）和圖9（b）相比，圖9（c）中的鏈路數(shù)明顯減少，表明經(jīng)MRTc算法優(yōu)化后的拓?fù)浣Y(jié)構(gòu)，其網(wǎng)絡(luò)平均節(jié)點(diǎn)度明顯小于圖9（a）和圖9（b）拓?fù)涞钠骄?jié)點(diǎn)度，即由MRTc算法優(yōu)化后的拓?fù)浣Y(jié)構(gòu)能夠幫助降低網(wǎng)絡(luò)MAC層干擾.
5.3實(shí)驗(yàn)3重要性能指標(biāo)的橫向比較
為了驗(yàn)證MRTc算法的性能，本實(shí)驗(yàn)選取4種經(jīng)典的拓?fù)淇刂扑惴℅G（Gabriel graph）、RNG（Relative neighborhood graph）、LMST、Udel與本文提出的MRTc算法進(jìn)行比較.首先，實(shí)驗(yàn)對(duì)5種算法生成的拓?fù)浣Y(jié)構(gòu)進(jìn)行對(duì)比.在100×100的區(qū)域內(nèi)隨機(jī)生成30個(gè)節(jié)點(diǎn)，在相同的仿真環(huán)境下，使用上述5種算法來構(gòu)建拓?fù)浣Y(jié)構(gòu)，并對(duì)5種拓?fù)浣Y(jié)構(gòu)進(jìn)行比較.實(shí)驗(yàn)中節(jié)點(diǎn)的感知半徑設(shè)置為20.當(dāng)傳感器節(jié)點(diǎn)的感知半徑和通信半徑滿足rc≥2×rs時(shí)，如果網(wǎng)絡(luò)在給定凸區(qū)域滿足1-覆蓋，則能夠保證網(wǎng)絡(luò)的連通性［23］.因此，本文假設(shè)網(wǎng)絡(luò)節(jié)點(diǎn)的感知半徑和通信半徑滿足rc=2×rs.然后，在相同的仿真環(huán)境中，通過改變傳感器節(jié)點(diǎn)的個(gè)數(shù)，使其在30～100的范圍內(nèi)變動(dòng)，比較5種不同算法的平均節(jié)點(diǎn)度、平均鏈路長度以及網(wǎng)絡(luò)的最大與最小節(jié)點(diǎn)度.通過全面的性能比較，驗(yàn)證本文提出的MRTc算法的性能.
圖7 兩種網(wǎng)絡(luò)中冗余節(jié)點(diǎn)數(shù)目和所占節(jié)點(diǎn)比例的比較（（a）冗余節(jié)點(diǎn)個(gè)數(shù)的比較；（b）冗余節(jié)點(diǎn)比例的比較）Fig.7 The comparison of the number of redundant nodes and the proportion of redundant nodes in the two networks（（a）The comparison of the number of redundant nodes；（b）The comparison of the proportion of the redundant nodes）
圖8 睡眠調(diào)度前后區(qū)域覆蓋情況（（a）睡眠調(diào)度前區(qū)域覆蓋情況；（b）睡眠調(diào)度后區(qū)域覆蓋情況）Fig.8 The area coverage by using the sleep scheduling（（a）The area coverage before sleep scheduling；（b）The area coverage after sleep scheduling）
1）網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)對(duì)比
在相同的仿真環(huán)境下，比較5種不同的拓?fù)淇刂扑惴℅G、RNG、LMST、Udel與MRTc生成的拓?fù)浣Y(jié)構(gòu).圖10顯示了由圖9（c）中的30個(gè)活動(dòng)節(jié)點(diǎn)在100×100的區(qū)域內(nèi)分別使用上述5種方法生成的拓?fù)浣Y(jié)構(gòu).由圖10（d）可以看出算法Udel生成的拓?fù)浣Y(jié)構(gòu)中有67條鏈路，是這5種拓?fù)浣Y(jié)構(gòu)中鏈路數(shù)最多的.該拓?fù)浣Y(jié)構(gòu)的平均節(jié)點(diǎn)度也是最大的.此外，Udel算法是一個(gè)集中式方法，它需要預(yù)先獲知網(wǎng)絡(luò)中所有節(jié)點(diǎn)的信息.相比之下，RNG算法（見圖10（b））和LMST算法（圖10（c））是分布式算法，它們的構(gòu)建過程只需依賴鄰居節(jié)點(diǎn)的信息.由這兩種算法所生成的拓?fù)渲?，鏈路?shù)分別為34和38，平均節(jié)點(diǎn)度過低.過低的節(jié)點(diǎn)度會(huì)導(dǎo)致節(jié)點(diǎn)間的通信鏈路過長，網(wǎng)絡(luò)能耗隨之增大.而本文算法（圖10（e））和GG算法（圖10（a））的鏈路數(shù)分別為57和52，兩者相差不大.然而，由這兩個(gè)子圖容易看出，GG算法擁有的長鏈路數(shù)量較多，這意味著該算法的能耗較大.
圖9 MRTc拓?fù)浣Y(jié)構(gòu)的構(gòu)建過程（（a）構(gòu)建局部Delaunay三角剖分圖；（b）構(gòu)建局部最小剛性拓?fù)?；（c）構(gòu)建全局最小剛性拓?fù)洌〧ig.9 The construction process of MRTc topology（（a）The construction of local Delaunay triangulation；（b）The construction of local minimum rigid topology；（c）The construction of global minimum rigid topology）
圖10 不同算法生成的拓?fù)浣Y(jié)構(gòu)（（a）GG；（b）RNG；（c）LMST；（d）Udel；（e）MRTc）Fig.10 The topological structures of different algorithms（（a）GG；（b）RNG；（c）LMST；（d）Udel；（e）MRTc）
2）其他重要性能指標(biāo)比較
在100×100的監(jiān)測區(qū)域內(nèi)，當(dāng)節(jié)點(diǎn)數(shù)量由30逐漸遞增時(shí)，上述5種算法的平均節(jié)點(diǎn)度、平均傳輸半徑、最大節(jié)點(diǎn)度以及最小節(jié)點(diǎn)度4種性能指標(biāo)如圖11所示.
網(wǎng)絡(luò)的平均節(jié)點(diǎn)度定義為網(wǎng)絡(luò)中所有節(jié)點(diǎn)的節(jié)點(diǎn)度之和與節(jié)點(diǎn)數(shù)量的比值.在無線傳感器網(wǎng)絡(luò)中，高的平均節(jié)點(diǎn)度需要在MAC層特別設(shè)計(jì)接入訪問機(jī)制，嚴(yán)重時(shí)還可引發(fā)訪問干擾和數(shù)據(jù)碰撞，造成非必要的網(wǎng)絡(luò)能耗.反過來，網(wǎng)絡(luò)的平均節(jié)點(diǎn)度過低則會(huì)導(dǎo)致節(jié)點(diǎn)間的鏈路過長，通信能耗值也相應(yīng)地增加.文獻(xiàn)［16］提出網(wǎng)絡(luò)的最優(yōu)平均節(jié)點(diǎn)度為6.根據(jù)實(shí)驗(yàn)2網(wǎng)絡(luò)拓?fù)錁?gòu)建過程可知，經(jīng)過MRTc算法優(yōu)化后減少了網(wǎng)絡(luò)拓?fù)涞逆溌窋?shù).由引理4可知，經(jīng)MRTc算法優(yōu)化后每個(gè)節(jié)點(diǎn)的節(jié)點(diǎn)度也會(huì)相應(yīng)地降低.圖11（a）為GG、RNG、LMST、Udel以及MRTc這5種算法在網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)目在30～100間變化時(shí)，網(wǎng)絡(luò)的平均節(jié)點(diǎn)的比較.由性質(zhì)4知算法MRTc的平均節(jié)點(diǎn)度因此，隨著節(jié)點(diǎn)數(shù)目n的增加，MRTc算法的平均節(jié)點(diǎn)度逐漸增加，且其值接近于4.由圖11（a）知該算法的平均節(jié)點(diǎn)度變化緩慢，說明該算法較穩(wěn)定.相比之下，算法RNG和算法LMST的平均節(jié)點(diǎn)度在3以下，這意味著由這兩種算法生成的拓?fù)浣Y(jié)構(gòu)過于稀疏.而Udel算法的平均節(jié)點(diǎn)度接近于最優(yōu)值6，這與文獻(xiàn)［12］相符合.
傳輸半徑定義為節(jié)點(diǎn)與其最遠(yuǎn)鄰居之間的距離.平均傳輸半徑為網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)的傳輸半徑之和與節(jié)點(diǎn)數(shù)量的比值.網(wǎng)絡(luò)中節(jié)點(diǎn)的平均傳輸半徑越大，網(wǎng)絡(luò)通信能耗也越大.上述5種算法平均傳輸半徑的比較結(jié)果如圖11（b）所示.由第2.3節(jié)2）基于Delaunay三角剖分圖的最小剛性拓?fù)涞臉?gòu)建可知MRTc算法是由刪除Delaunay三角剖分圖的部分較長鏈路得到的.因此，MRTc算法生成的拓?fù)浣Y(jié)構(gòu)具有較小的平均傳輸半徑.由圖11（b）可知，Udel算法和GG算法的平均傳輸半徑均高于MRTc算法.而LMST算法與RNG算法具有更小的平均傳輸半徑.
圖11（c）和（d）分別為5種算法最大節(jié)點(diǎn)度與最小節(jié)點(diǎn)度的比較.網(wǎng)絡(luò)的最大節(jié)點(diǎn)度定義為網(wǎng)絡(luò)中邏輯鏈路［5］最多的節(jié)點(diǎn)的度數(shù).與之類似，網(wǎng)絡(luò)的最小節(jié)點(diǎn)度定義為網(wǎng)絡(luò)中邏輯鏈路最少的節(jié)點(diǎn)的度數(shù).由第2.3節(jié)知最小剛性拓?fù)渲泄?jié)點(diǎn)至少包含兩條鏈路，因此，由MRTc算法生成的拓?fù)浣Y(jié)構(gòu)的最小節(jié)點(diǎn)度不低于2.這意味著由該算法生成的拓?fù)浣Y(jié)構(gòu)是2-容錯(cuò)的，具有較高的魯棒性.由圖11（c）和（d）知算法LMST和RNG的最大節(jié)點(diǎn)度均在最優(yōu)值6以下，進(jìn)一步說明這兩種算法的節(jié)點(diǎn)度過低.且算法LMST、GG和RNG的最小節(jié)點(diǎn)度均可以取值為1，表明這三種算法均是1-容錯(cuò)的.當(dāng)算法中的某條鏈路斷裂時(shí)，其他節(jié)點(diǎn)不能繼續(xù)維持網(wǎng)絡(luò)的連通性，因此網(wǎng)絡(luò)的容錯(cuò)性較差.
圖11 不同算法的性能比較（（a）平均節(jié)點(diǎn)度的比較；（b）平均傳輸半徑的比較；（c）最大節(jié)點(diǎn)度的比較；（d）最小節(jié)點(diǎn)度的比較）Fig.11 The performance comparison of different algorithms（（a）The comparison of average node degree；（b）The comparison of average transmission radius；（c）The comparison of maximum node degree；（d）The comparison of minimum node degree）
綜上所述，MRTc算法在保證網(wǎng)絡(luò)覆蓋性與連通性的同時(shí)，能夠限制網(wǎng)絡(luò)平均節(jié)點(diǎn)度從而降低了網(wǎng)絡(luò)MAC層干擾，并有效地增強(qiáng)了網(wǎng)絡(luò)的魯棒性能，降低了網(wǎng)絡(luò)能耗.另外，該算法具有較強(qiáng)的穩(wěn)定性.然而，此算法也存在不足之處，即當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)密度相同時(shí)，與LMST算法和RNG算法相比，MRTc算法的平均傳輸半徑較大，這表示由MRTc算法優(yōu)化得到的拓?fù)浣Y(jié)構(gòu)中存在部分較長鏈路.
針對(duì)該問題，我們提出下一步的研究方向即為尋找合適的方法，在保證網(wǎng)絡(luò)2-容錯(cuò)性能的前提下，刪除拓?fù)渲休^長鏈路.
5.4實(shí)驗(yàn)4睡眠調(diào)度前后能耗比較
節(jié)約能耗是網(wǎng)絡(luò)拓?fù)淇刂频氖滓繕?biāo)，網(wǎng)絡(luò)中節(jié)點(diǎn)存在休眠和活動(dòng)兩種狀態(tài).本實(shí)驗(yàn)使用最小剛性拓?fù)洌⒁钥偰芎暮痛婊罟?jié)點(diǎn)比例為指標(biāo)，全面深入地比較了網(wǎng)絡(luò)睡眠調(diào)度前、后的能量消耗情況.
計(jì)算睡眠調(diào)度前、后總能耗與活動(dòng)節(jié)點(diǎn)比例實(shí)驗(yàn)的設(shè)置場景如下：假設(shè)70個(gè)傳感器節(jié)點(diǎn)隨機(jī)部署于100×100的方形監(jiān)測區(qū)域內(nèi).每個(gè)節(jié)點(diǎn)擁有相同的初始能量E0=1kJ，且能量無法得到補(bǔ)充.假設(shè)數(shù)據(jù)包的長度為50Bytes，發(fā)射電路和接收電路的能量消耗Eelec=50nJ/bit，自由空間傳輸模型系數(shù)εfs=10pJ/bit/m2.實(shí)驗(yàn)中采用洪泛式路由，當(dāng)數(shù)據(jù)包個(gè)數(shù)變化時(shí)，睡眠調(diào)度前、后最小剛性拓?fù)涞目偰芎囊约盎顒?dòng)節(jié)點(diǎn)比例如圖12（a）和（b）所示.
由圖12（a）和（b）可知，最小剛性拓?fù)湓诮?jīng)由睡眠調(diào)度后，均能降低網(wǎng)絡(luò)的總能耗，提高網(wǎng)絡(luò)中存活節(jié)點(diǎn)的比例.因此，使用基于Voronoi覆蓋的睡眠調(diào)度算法后可有效降低網(wǎng)絡(luò)能耗.
圖12 睡眠調(diào)度前后最小剛性拓?fù)湫阅埽ǎ╝）睡眠調(diào)度前后最小剛性拓?fù)淇偰芎模唬╞）睡眠調(diào)度前后最小剛性拓?fù)浯婊罟?jié)點(diǎn)）Fig.12 The performances of minimum rigid topology before and after sleep scheduling（（a）Total energy consumption of the minimum rigid topology before and after sleep scheduling；（b）The proportion of survival nodes before and after sleep scheduling in minimum rigid topology）
6 結(jié)論
本文提出了一個(gè)基于Voronoi覆蓋與Delaunay三角剖分圖的最小剛性拓?fù)淇刂扑惴?，該算法采用睡眠調(diào)度與功率控制相結(jié)合的方案來降低網(wǎng)絡(luò)能耗.算法中，無線傳感器網(wǎng)絡(luò)通過睡眠調(diào)度在保證監(jiān)測區(qū)域全覆蓋的同時(shí)，可將覆蓋冗余節(jié)點(diǎn)調(diào)整為休眠狀態(tài).進(jìn)一步地，算法在剩余活動(dòng)節(jié)點(diǎn)之間，構(gòu)建基于Delaunay三角剖分圖的最小剛性拓?fù)浣Y(jié)構(gòu).這一方法有效限制了平均節(jié)點(diǎn)度，即網(wǎng)絡(luò)平均節(jié)點(diǎn)度不大于4，且所生成的鏈路數(shù)量滿足稀疏性要求.經(jīng)過MRTc算法優(yōu)化后的網(wǎng)絡(luò)拓?fù)涫?-容錯(cuò)的，提高了網(wǎng)絡(luò)的容錯(cuò)性.
未來工作可進(jìn)一步研究Delaunay三角剖分圖的性能對(duì)算法的影響，進(jìn)而研究該拓?fù)湓诋悩?gòu)網(wǎng)絡(luò)中的構(gòu)建問題；另外，尋找合適的方法，在保證網(wǎng)絡(luò)2-容錯(cuò)性能的前提下，刪除拓?fù)渲休^長鏈路.
References
1 Gui J S，Liu A F.A new distributed topology control algorithm based on optimization of delay and energy in wireless networks.Journal of Parallel and Distributed Computing，2012，72（8）:1032-1044
2 Hong Zhen，Yu Li，Zhang Gui-Jun，Chen You-Rong.Topology construction based on minimum connected dominating set for wireless sensor networks.Journal of Electronics& Information Technology，2012，34（8）:2000-2006（洪榛，俞立，張貴軍，陳友榮.基于最小連通支配集的無線傳感網(wǎng)拓?fù)錁?gòu)建研究.電子與信息學(xué)報(bào)，2012，34（8）:2000-2006）
3 Zhang Y M，He S，Chen J.Data gathering optimization by dynamic sensing and routing in rechargeable sensor networks.In:Proceedings of the 10th Annual IEEE Communications Society Conference on Sensor，Mesh and Ad Hoc Communications and Networks（SECON）.New Orleans，LA:IEEE，2013.273-281
4 Kang Yi-Mei，Li Zhi-Jun，Hu Jiang，Dong Ji-Chang.A lowpower hierarchical wireless sensor network topology control algorithm.Acta Automatica Sinica，2010，36（4）:543-549（康一梅，李志軍，胡江，董吉昌.一種低能耗層次型無線傳感器網(wǎng)絡(luò)拓?fù)淇刂扑惴?自動(dòng)化學(xué)報(bào)，2010，36（4）:543-549）
5 Luo Xiao-Yuan，Yan Yan-Lin，Hao Li-Juan，Li Shao-Bao，Guan Xin-Ping.Based on optimally rigid graph energy efficient distributed topology control algorithm.Journal on Communications，2013，34（12）:1-10（羅小元，閆彥霖，郝麗娟，李紹寶，關(guān)新平.基于最優(yōu)剛性圖的能量有效分布式拓?fù)淇刂扑惴?通信學(xué)報(bào)，2013，34（12）:1-10）
6 Yu C S，Lee B，Youn H Y.Energy efficient routing protocols for mobile ad hoc networks.Wireless Communications and Mobile Computing，2003，3（8）:959-973
7 Li L，Halpern J Y，Bahl P，Wang Y M，Wattenhofer R.A cone-based distributed topology-control algorithm for wireless multi-hop networks.IEEE/ACM Transactions on Networking，2005，13（1）:147-159
8 Chen B J，Jamieson K，Balakrishnan H，Morris R.Span:an energy-efficient coordination algorithm for topology maintenance in ad hoc wireless networks.Wireless Networks，2002，8（5）:481-494
9 Berman P，Calinescu G，Shah C，Zelikovsky A A.Efficient energy management in sensor networks.Ad Hoc and Sensor Networks，Wireless Networks and Mobile Computing.New York:Nova Science Publishers，2005.71-90
10 Li N，Hou J C，Sha L.Design and analysis of an MST-based topology control algorithm.IEEE Transactions on Wireless Communications，2005，4（3）:1195-1206
11 Shang D，Zhang B，Yao Z，Li C.An energy efficient localized topology control algorithm for wireless multihop networks.Journal of Communications and Networks，2014，16（4）:371-377
12 Wang Y，Li X Y.Localized construction of bounded degree and planar spanner for wireless ad hoc networks.Mobile Networks and Applications，2006，11（2）:161-175
13 Xu Y，Heidemann J，Estrin D.Geography-informed energy conservation for ad hoc routing.In:Proceedings of the 7th Annual International Conference on Mobile Computing and Networking.Rome，Italy:ACM，2001.70-84
14 Su Jin-Shu，Guo Wen-Zhong，Yu Zhao-Long，Chen Guo-Long.Fault-toleranceclusteringalgorithmwithloadbalance aware in wireless sensor network.Chinese Journal of Computers，2014，37（2）:445-456（蘇金樹，郭文忠，余朝龍，陳國龍.負(fù)載均衡感知的無線傳感器網(wǎng)絡(luò)容錯(cuò)分簇算法.計(jì)算機(jī)學(xué)報(bào)，2014，37（2）:445-456）
15 Li N，Hou J C.Localized fault-tolerant topology control in wireless ad hoc networks.IEEE Transactions on Parallel and Distributed Systems，2006，17（4）:307-320
16 Luo X Y，Yan Y L，Li S B，Guan X P.Topology control based on optimally rigid graph in wireless sensor networks. Computer Networks，2013，57（4）:1037-1047
18 Luo Xiao-Yuan，Shao Shi-Kai，Guan Xin-Ping，Zhao Yuan-Jie.Dynamic generation and control of optimally persistent formation for multi-agent systems.Acta Automatica Sinica，2013，39（9）:1431-1438（羅小元，邵士凱，關(guān)新平，趙淵潔.多智能體最優(yōu)持久編隊(duì)動(dòng)態(tài)生成與控制.自動(dòng)化學(xué)報(bào)，2013，39（9）:1431-1438）
19 Luo Xiao-Yuan，Yang Fan，Li Shao-Bao，Guan Xin-Ping. Generation of optimally persistent formation for multi-agent systems.Acta Automatica Sinica，2014，40（7）:1311-1319（羅小元，楊帆，李紹寶，關(guān)新平.多智能體系統(tǒng)的最優(yōu)持久編隊(duì)生成策略.自動(dòng)化學(xué)報(bào)，2014，40（7）:1311-1319）
20 Dong Jian，Peng Ren-Can，Zheng Yi-Dong.An improved algorithm of point-by-point interpolation by using local dynamic optimal Delaunay triangulation network.Geomatics and Information Science of Wuhan University，2013，38（5）: 613-617（董箭，彭認(rèn)燦，鄭義東.利用局部動(dòng)態(tài)最優(yōu)Delaunay三角網(wǎng)改進(jìn)逐點(diǎn)內(nèi)插算法.武漢大學(xué)學(xué)報(bào):信息科學(xué)版，2013，38（5）:613-617）
21 Wang Chao-Rui.Graph Theory（3rd Edition）.Beijing:Beijing Institute of Technology Press，2005.15（王朝瑞.圖論（第3版）.北京:北京理工大學(xué)出版社，2005.15）
22 Tian D，Georganas N D.A coverage-preserving node scheduling scheme for large wireless sensor networks.In: Proceedings of the 1st ACM International Workshop on Wireless Sensor Networks and Applications.Atlanta，Georgia，USA:ACM，2002.32-41
23 Xing G L，Wang X R，Zhang Y F，Lu C Y，Pless R，Gill C. Integrated coverage and connectivity configuration for energy conservation in sensor networks.ACM Transactions on Sensor Networks，2005，1（1）:36-72
薛 亮河北工程大學(xué)信息與電氣工程學(xué)院副教授.主要研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)，認(rèn)知無線網(wǎng)絡(luò)技術(shù).
E-mail:lxue@ysu.edu.cn
（XUE LiangAssociate professor at the School of Information and Electrical Engineering，Hebei University of Engineering.His research interest covers wireless sensor networks and cognitive radio networks.）
陳晰河北工程大學(xué)碩士研究生.主要研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)技術(shù).本文通信作者.
E-mail:cx3768255@hotmail.com
（CHEN XiMaster student at Hebei University of Engineering.Her research interest covers wireless sensor networks. Corresponding author of this paper.）
趙繼軍河北工程大學(xué)信息與電氣工程學(xué)院教授.主要研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)，寬帶通信網(wǎng).
E-mail:zjijun@hebeu.edu.cn
（ZHAOJi-JunProfessor at the School of Information and Electrical Engineering，Hebei University of Engineering.His research interest covers wireless sensor networks and broadband communication network.）
黎作鵬河北工程大學(xué)信息與電氣工程學(xué)院講師.主要研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)，物聯(lián)網(wǎng)技術(shù)，納米網(wǎng)絡(luò).
E-mail:lizuopeng@hebeu.edu.cn
（LIZuo-PengLectureratthe School of Information and electrical Engineering，Hebei University of Engineering.His research interest covers wireless sensor networks，internet of things，and nanonetworks.）
關(guān)新平上海交通大學(xué)電子信息與電氣工程學(xué)院教授.主要研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)，認(rèn)知無線電等通信網(wǎng)絡(luò)的控制，復(fù)雜網(wǎng)絡(luò)動(dòng)態(tài)系統(tǒng)的性能分析與控制，非線性時(shí)滯系統(tǒng)的拓?fù)淇刂?，網(wǎng)絡(luò)化控制系統(tǒng)設(shè)計(jì).
E-mail:xpguan@sjtu.edu.cn
（GUAN Xin-PingProfessor at the School of Electronic Information and Electrical Engineering，Shanghai Jiao Tong University.His research interest covers wireless sensor networks，cognitive radio communication network in the control，analysis and control of complex dynamic network system，topology control of nonlinear time-delay systems，and networked control system design.）
A Minimal Rigid Topology Control Algorithm Based on Voronoi Coverage and Delaunay Triangulation in Wireless Sensor Networks
XUE Liang1，2CHEN Xi1ZHAO Ji-Jun1，2LI Zuo-Peng1GUAN Xin-Ping3
This paper proposes a minimal rigid network topology control algorithm called minimal rigid topology control（MRTc），which is based on Voronoi coverage and Delaunay triangulation，to meet application needs of good coverage and for energy saving.MRTc can accurately control node operative modes by which the target sensing area can be completely covered only with active nodes.On the basis of complete coverage，MRTc constructs a topology that is applicable to wireless sensor networks by exploiting the characteristics of Delaunay triangulation.The topology structure can effectively restrict the average node degree，and the structure is characterized by its fault-tolerance，spread ability，and sparsity.Furthermore，MRTc also introduces a power control strategy to minimize the energy consumption of sensor nodes without losing complete coverage in the sensing area.Simulation results are provided to validate this proposal.
Wireless sensor networks（WSNs），topology control，minimal rigid，Voronoi coverage，Delaunay triangulation CitationXue Liang，Chen Xi，Zhao Ji-Jun，Li Zuo-Peng，Guan Xin-Ping.A minimal rigid topology control algorithm based on Voronoi coverage and Delaunay triangulation in wireless sensor networks，2016，42（10）:1570-1584
Manuscript October 26，2015；accepted March 3，2016
10.16383/j.aas.2016.c150702
2015-10-26錄用日期2016-03-03
國家自然科學(xué)基金（61304131，61402147），河北省自然科學(xué)基金（F2016402054，F(xiàn)2014402075），河北省教育廳科學(xué)研究計(jì)劃（BJ2014019，ZD2015087，QN2015046）資助
Supported by National Natural Science Foundation of China（61304131，61402147），Natural Science Foundation of Hebei Province（F2016402054，F(xiàn)2014402075），andtheScientific ResearchPlanProjectsofHebeiEducationDepartment（BJ2014019，ZD2015087，QN2015046）
本文責(zé)任編委趙千川
Recommended by Associate Editor ZHAO Qian-Chuan
1.河北工程大學(xué)信息與電氣工程學(xué)院邯鄲0560382.邯鄲市光纖通信與寬帶接入技術(shù)重點(diǎn)實(shí)驗(yàn)室邯鄲0560383.上海交通大學(xué)系統(tǒng)控制與信息處理教育部重點(diǎn)實(shí)驗(yàn)室上海200240
1.School of Information and Electrical Engineering，Hebei University of Engineering，Handan 0560382.Handan Key Laboratory of Optical Fiber Communication and Broadband Access Technologies，Handan 0560383.System Control and Information Processing Key Laboratory of Ministry of Education，Shanghai Jiao Tong University，Shanghai 200240
猜你喜歡
家紡“全鏈路”升級(jí)紡織科學(xué)研究(2023年9期)2023-10-23 11:18:10 120t轉(zhuǎn)爐降低工序能耗生產(chǎn)實(shí)踐昆鋼科技(2022年2期)2022-07-08 06:36:14 自我革命需要“剛性推進(jìn)”當(dāng)代陜西(2022年5期)2022-04-19 12:10:46 能耗雙控下，漲價(jià)潮再度來襲！當(dāng)代水產(chǎn)(2021年10期)2022-01-12 06:20:28 天空地一體化網(wǎng)絡(luò)多中繼鏈路自適應(yīng)調(diào)度技術(shù)移動(dòng)通信(2021年5期)2021-10-25 11:41:48 探討如何設(shè)計(jì)零能耗住宅建材發(fā)展導(dǎo)向(2021年23期)2021-03-08 01:05:38 加權(quán)p-Laplace型方程的剛性河南科學(xué)(2020年3期)2020-06-02 08:30:10 剛性兌付的法律治理金融法苑(2018年2期)2018-12-07 00:59:52 日本先進(jìn)的“零能耗住宅”華人時(shí)刊(2018年15期)2018-11-10 03:25:26 基于3G的VPDN技術(shù)在高速公路備份鏈路中的應(yīng)用中國交通信息化(2014年3期)2014-06-05 03:07:09
薛亮 陳晰 趙繼軍 黎作鵬 關(guān)新平
無線傳感器網(wǎng)絡(luò)中基于Voronoi覆蓋及Delaunay三角剖分圖的最小剛性拓?fù)淇刂扑惴?/p>
薛亮1，2陳晰1趙繼軍1，2黎作鵬1關(guān)新平3
為同時(shí)滿足覆蓋與節(jié)能應(yīng)用需求，本文提出了無線傳感器網(wǎng)絡(luò)中一種最小剛性拓?fù)淇刂扑惴∕RTc（Minimal rigid topology control algorithm based on Voronoi coverage and Delaunay triangulation）.該算法基于Voronoi覆蓋機(jī)制，準(zhǔn)確控制節(jié)點(diǎn)工作狀態(tài)，實(shí)現(xiàn)活動(dòng)節(jié)點(diǎn)對(duì)目標(biāo)區(qū)域的完全覆蓋.在此基礎(chǔ)上，MRTc利用Delaunay三角剖分圖的特點(diǎn)，構(gòu)建出適用于無線傳感器網(wǎng)絡(luò)的最小剛性拓?fù)浣Y(jié)構(gòu).該結(jié)構(gòu)有效約束了網(wǎng)絡(luò)平均節(jié)點(diǎn)度，且同時(shí)具有容錯(cuò)性、覆蓋性和稀疏性.此外，MRTc引入節(jié)點(diǎn)功率控制策略，在維持網(wǎng)絡(luò)完全覆蓋的基礎(chǔ)上最小化節(jié)點(diǎn)能耗.仿真結(jié)果進(jìn)一步驗(yàn)證了本文提出的MRTc算法的有效性.
無線傳感器網(wǎng)絡(luò)，拓?fù)淇刂疲钚傂?，Voronoi覆蓋，Delaunay三角剖分圖
引用格式薛亮，陳晰，趙繼軍，黎作鵬，關(guān)新平.無線傳感器網(wǎng)絡(luò)中基于Voronoi覆蓋及Delaunay三角剖分圖的最小剛性拓?fù)淇刂扑惴?自動(dòng)化學(xué)報(bào)，2016，42（10）:1570-1584
降低網(wǎng)絡(luò)能耗、限制網(wǎng)絡(luò)平均節(jié)點(diǎn)度以及提高網(wǎng)絡(luò)容錯(cuò)性是無線傳感器網(wǎng)絡(luò)（Wireless sensor networks，WSNs）中的重要問題，而拓?fù)淇刂扑惴ǖ闹饕蝿?wù)是在滿足網(wǎng)絡(luò)連通性和覆蓋性的前提下，使得網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)依據(jù)給定的規(guī)則從它的物理鄰居節(jié)點(diǎn)間選取合適的邏輯鄰居節(jié)點(diǎn)，形成一個(gè)優(yōu)化的網(wǎng)絡(luò)結(jié)構(gòu)，以達(dá)到降低網(wǎng)絡(luò)能耗［1-4］，限制平均節(jié)點(diǎn)度，提高網(wǎng)絡(luò)容錯(cuò)性的目的.
降低網(wǎng)絡(luò)能耗是能量受限網(wǎng)絡(luò)協(xié)議設(shè)計(jì)的首要目標(biāo).由于傳感器節(jié)點(diǎn)的體積限制，其可用能量必然有限［5］，因此，對(duì)于能量受限的無線傳感器網(wǎng)絡(luò)來說降低網(wǎng)絡(luò)能耗是構(gòu)建拓?fù)浣Y(jié)構(gòu)需要考慮的首要因素.目前，拓?fù)淇刂萍夹g(shù)中主要有兩種節(jié)能策略：1）通過調(diào)節(jié)網(wǎng)絡(luò)中各節(jié)點(diǎn)的傳輸功率實(shí)現(xiàn)降低網(wǎng)絡(luò)能耗的目的；2）是將網(wǎng)絡(luò)中部分節(jié)點(diǎn)調(diào)節(jié)為休眠狀態(tài)以達(dá)到降低網(wǎng)絡(luò)能耗的目標(biāo).本文為進(jìn)一步降低網(wǎng)絡(luò)能耗，采用睡眠調(diào)度與功率控制方案，以更好地實(shí)現(xiàn)節(jié)能降耗目標(biāo).
有效限制平均節(jié)點(diǎn)度是拓?fù)淇刂萍夹g(shù)中的另一個(gè)重要設(shè)計(jì)指標(biāo).網(wǎng)絡(luò)節(jié)點(diǎn)度是指與該節(jié)點(diǎn)存在直接通信鏈路的一跳鄰居節(jié)點(diǎn)的數(shù)目.在無線傳感器網(wǎng)絡(luò)中，高的網(wǎng)絡(luò)平均節(jié)點(diǎn)度需要在MAC（Media access control）層設(shè)計(jì)相應(yīng)的接入訪問控制機(jī)制，節(jié)點(diǎn)度過高時(shí)還可能引發(fā)訪問沖突和數(shù)據(jù)碰撞，浪費(fèi)節(jié)點(diǎn)有限的能量.因此，密集部署的無線傳感器網(wǎng)絡(luò)中，限制網(wǎng)絡(luò)的平均節(jié)點(diǎn)度是十分必要的.
網(wǎng)絡(luò)的容錯(cuò)性能是拓?fù)錁?gòu)建過程中需要考慮的另一個(gè)重要指標(biāo).無線傳感器網(wǎng)絡(luò)經(jīng)常部署于惡劣的環(huán)境中，一旦網(wǎng)絡(luò)中某個(gè)節(jié)點(diǎn)遭到破壞或能量耗盡，將可能導(dǎo)致整個(gè)網(wǎng)絡(luò)癱瘓以致其不能正常運(yùn)行.因此，在拓?fù)淇刂扑惴ǖ脑O(shè)計(jì)中需要考慮網(wǎng)絡(luò)的容錯(cuò)性.
基于上述設(shè)計(jì)目標(biāo)，本文提出了一個(gè)基于Voronoi覆蓋及 Delaunay三角剖分圖的無線傳感器網(wǎng)絡(luò)最小剛性拓?fù)淇刂扑惴ǎ∕inimal rigid topology control algorithm based on Voronoi coverage and Delaunay triangulation，MRTc），該算法基于Voronoi原理調(diào)節(jié)節(jié)點(diǎn)的活動(dòng)狀態(tài)，實(shí)現(xiàn)了目標(biāo)區(qū)域的全覆蓋，在此基礎(chǔ)上基于Delaunay三角剖分圖構(gòu)建了最小剛性拓?fù)浣Y(jié)構(gòu).本文的主要貢獻(xiàn)為：1）采用睡眠調(diào)度與功率控制相結(jié)合的方法，在保持網(wǎng)絡(luò)連通的情況下進(jìn)一步降低網(wǎng)絡(luò)能耗；2）提出定理，為構(gòu)建基于Delaunay三角剖分圖的最小剛性拓?fù)涮峁┝死碚撘罁?jù)；3）充分利用最小剛性拓?fù)涞奶匦?，?-容錯(cuò)、稀疏性以及平均節(jié)點(diǎn)度有限等特點(diǎn)，實(shí)現(xiàn)了提高網(wǎng)絡(luò)魯棒性、簡化路由計(jì)算、降低節(jié)點(diǎn)間干擾的目標(biāo).
1 相關(guān)工作
作為無線傳感器網(wǎng)絡(luò)的基礎(chǔ)技術(shù)，拓?fù)淇刂萍夹g(shù)已引起學(xué)者的廣泛關(guān)注［6-15］.通過拓?fù)淇刂疲梢杂行Ы档途W(wǎng)絡(luò)能耗、限制節(jié)點(diǎn)度以及提高網(wǎng)絡(luò)的容錯(cuò)性.
降低網(wǎng)絡(luò)能耗是拓?fù)淇刂扑惴ㄐ枰紫瓤紤]的設(shè)計(jì)目標(biāo).近幾年來，研究人員提出了多種面向節(jié)能應(yīng)用的拓?fù)淇刂扑惴ǎ?-9］，其節(jié)能方案主要有功率控制和睡眠調(diào)度兩種.對(duì)于功率控制而言，其主要思想為通過調(diào)節(jié)網(wǎng)絡(luò)中所有節(jié)點(diǎn)的功率來降低網(wǎng)絡(luò)能耗.例如文獻(xiàn)［6］中的COMPOW（Smallest common power）算法和文獻(xiàn)［7］中的CBTC（Conebased distributed topology-control）算法.COMPOW算法中所有節(jié)點(diǎn)采用能夠保持整個(gè)網(wǎng)絡(luò)連通的最小功率，統(tǒng)一的功率設(shè)置確保了網(wǎng)絡(luò)中鏈路的雙向連通性，且功率的最小化達(dá)到了降低網(wǎng)路能耗的目的.CBTC算法中每個(gè)節(jié)點(diǎn)則通過調(diào)整各自的傳輸功率，使得以該節(jié)點(diǎn)為中心，當(dāng)在任意角度α（α≤5π/6）的扇形區(qū)域內(nèi)至少存在一個(gè)鄰居節(jié)點(diǎn)時(shí)，能夠保持網(wǎng)絡(luò)的連通性，降低網(wǎng)絡(luò)能耗.在睡眠調(diào)度方面，Chen等［8］提出的Span算法其基本思想是：在維持網(wǎng)絡(luò)連通性的前提下，網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)根據(jù)其剩余能量、鄰居節(jié)點(diǎn)個(gè)數(shù)以及節(jié)點(diǎn)效用等多種因素，自適應(yīng)地判定該節(jié)點(diǎn)成為骨干節(jié)點(diǎn)或休眠節(jié)點(diǎn).對(duì)于MSNL（Maximization of sensor network life）算法［9］而言，節(jié)點(diǎn)狀態(tài)可細(xì)分為活動(dòng)、休眠以及過渡狀態(tài).處于過渡狀態(tài)的節(jié)點(diǎn)將進(jìn)行實(shí)時(shí)監(jiān)測，且當(dāng)其發(fā)現(xiàn)自身的監(jiān)測區(qū)域不能被其余處于活動(dòng)狀態(tài)或過渡狀態(tài)的節(jié)點(diǎn)覆蓋時(shí)，此過渡狀態(tài)節(jié)點(diǎn)轉(zhuǎn)化為活動(dòng)狀態(tài).上述4種算法均采用睡眠調(diào)度或功率控制中的一種方案面向節(jié)能設(shè)計(jì)而缺乏對(duì)多種方法的結(jié)合的運(yùn)用.本文針對(duì)上述弊端，提出了基于Voronoi覆蓋的睡眠調(diào)度與功率控制相結(jié)合的方案，進(jìn)一步降低網(wǎng)絡(luò)能耗.
作為拓?fù)淇刂萍夹g(shù)的重要設(shè)計(jì)目標(biāo)之一，節(jié)點(diǎn)度的限制問題已成為國內(nèi)外學(xué)者的研究熱點(diǎn).文獻(xiàn)［10］中，Li等提出了LMST（Local minimum spanning tree）算法，算法中節(jié)點(diǎn)相互獨(dú)立地構(gòu)建局部最小生成樹，并根據(jù)鄰近圖中與之距離最遠(yuǎn)的邏輯鄰居節(jié)點(diǎn)確定自身功率.此外，文獻(xiàn)中證明了LMST算法中每個(gè)節(jié)點(diǎn)的節(jié)點(diǎn)度均不大于6，網(wǎng)絡(luò)的平均節(jié)點(diǎn)度接近于最小生成樹算法，略高于2，可見該算法限制了網(wǎng)絡(luò)的平均節(jié)點(diǎn)度.在LMST算法基礎(chǔ)上，文獻(xiàn)［11］通過定義每條鏈路的臨界能耗，提出一種基于LMST的改進(jìn)算法X-LMST.它旨在以鏈路的能量有效性為指標(biāo)，構(gòu)建局部最小生成樹，網(wǎng)絡(luò)中節(jié)點(diǎn)的度數(shù)不多于6.LMST算法和X-LMST算法雖然限制了網(wǎng)絡(luò)平均節(jié)點(diǎn)度，但是這兩個(gè)算法均是1-容錯(cuò)的，如果網(wǎng)絡(luò)中的某條鏈路因節(jié)點(diǎn)能量耗盡或環(huán)境干擾而意外中斷，將會(huì)導(dǎo)致網(wǎng)絡(luò)失效.Delaunay三角剖分圖和UDG（Unit disk graph）圖相結(jié)合，刪除Delaunay三角剖分圖中不能相互通信的鏈路，構(gòu)建出Udel拓?fù)浣Y(jié)構(gòu)［12］，該拓?fù)涫莟-支撐的，并且經(jīng)Udel算法優(yōu)化后得到的拓?fù)浣Y(jié)構(gòu)的平均節(jié)點(diǎn)度不高于6.然而，該拓?fù)浣Y(jié)構(gòu)是集中式拓?fù)?，需要已知網(wǎng)絡(luò)的全局信息.
容錯(cuò)性是拓?fù)淇刂萍夹g(shù)的另一重要設(shè)計(jì)目標(biāo).目前，已有較多文獻(xiàn)關(guān)注網(wǎng)絡(luò)容錯(cuò)性能的研究.文獻(xiàn)［13］中Xu等提出了一個(gè)典型的睡眠調(diào)度算法GAF（Geographical adaptive fidelity），它以劃分網(wǎng)格的方式將節(jié)點(diǎn)分組，通過睡眠調(diào)度的方法使每個(gè)網(wǎng)格中僅保留一個(gè)活動(dòng)節(jié)點(diǎn)，網(wǎng)格內(nèi)其余節(jié)點(diǎn)則調(diào)節(jié)為休眠狀態(tài)，以降低網(wǎng)絡(luò)能量消耗.理論上，GAF算法是4-容錯(cuò)的，有著良好的容錯(cuò)性能.但是，GAF算法中節(jié)點(diǎn)的平均度數(shù)較大.過高的節(jié)點(diǎn)度會(huì)在節(jié)點(diǎn)間引發(fā)較嚴(yán)重的干擾和沖突，嚴(yán)重時(shí)引起數(shù)據(jù)包重傳，造成不必要的能量浪費(fèi).蘇金樹等［14］提出了一種容錯(cuò)算法，該算法在局部最小生成樹（LMST）的基礎(chǔ)上，通過增添鏈路的方式減少網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中的割邊和割點(diǎn)的數(shù)目，構(gòu)建了一個(gè)2-容錯(cuò)的拓?fù)浣Y(jié)構(gòu).實(shí)驗(yàn)證明，該拓?fù)渚哂幸欢ǖ木W(wǎng)絡(luò)容錯(cuò)性能.然而，該算法在刪除拓?fù)涞母钸吅透铧c(diǎn)時(shí)，需要已知網(wǎng)絡(luò)的全局信息，增加了算法的計(jì)算復(fù)雜度.文獻(xiàn)［15］中提出的FGSSk（Fault-tolerant global spanning subgraph）算法是Kruskal最小生成樹算法在k-容錯(cuò)的網(wǎng)絡(luò)中的推廣，它是一個(gè)集中式的拓?fù)淇刂扑惴?此算法通過插入較短鏈路的方式構(gòu)建了一個(gè)k-容錯(cuò)的拓?fù)浣Y(jié)構(gòu)，由于該算法是集中式算法，網(wǎng)絡(luò)中所有節(jié)點(diǎn)均需了解全局信息，因此，該算法的計(jì)算量較大.
針對(duì)上述算法的局限性，本文綜合考慮了網(wǎng)絡(luò)能耗、平均節(jié)點(diǎn)度以及容錯(cuò)性三方面內(nèi)容，提出了基于Voronoi覆蓋及Delaunay三角剖分圖的無線傳感器網(wǎng)絡(luò)最小剛性拓?fù)淇刂扑惴?該算法首先依據(jù)Voronoi覆蓋原理，判斷網(wǎng)絡(luò)中的覆蓋冗余節(jié)點(diǎn)，在保證網(wǎng)絡(luò)區(qū)域全覆蓋的條件下，將其調(diào)節(jié)為休眠狀態(tài).然后，在活動(dòng)節(jié)點(diǎn)間，構(gòu)建基于Delaunay三角剖分圖的無線傳感器網(wǎng)絡(luò)最小剛性拓?fù)浣Y(jié)構(gòu).算法中睡眠調(diào)度與功率控制相結(jié)合，在保持網(wǎng)絡(luò)連通性的情況下，進(jìn)一步降低網(wǎng)絡(luò)能耗.文中所提出的定理對(duì)于構(gòu)建具有2-容錯(cuò)、稀疏性的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，提高網(wǎng)絡(luò)魯棒性，有效約束平均節(jié)點(diǎn)度，提供了理論依據(jù)和基礎(chǔ).文中第4節(jié)分析證明了MRTc算法的性能；算法性能評(píng)估與結(jié)果分析在第5節(jié)給出.
2 網(wǎng)絡(luò)模型與定義
2.1網(wǎng)絡(luò)模型
在二維空間中，無線傳感器網(wǎng)絡(luò)可用一個(gè)無向圖（Undirected graph）Gu（Vu，εu）來表示.其中，Vu=｛1，2，···，n｝表示無線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)的集合；εu=｛（lu）ji，i∈Vu，j∈Vu｝為網(wǎng)絡(luò)中節(jié)點(diǎn)間可相互通信的鏈路集.在同構(gòu)網(wǎng)絡(luò)中，如果兩個(gè)節(jié)點(diǎn)i和j的歐氏距離滿足（其中，rc為節(jié)點(diǎn)的通信半徑），則稱節(jié)點(diǎn)i與j互為通信鄰居［16］.若兩節(jié)點(diǎn)可相互通信，鏈路本文中，Ni為節(jié)點(diǎn)i的通信鄰居的集合，集合Ni中的元素個(gè)數(shù)（集合Ni的勢）定義為節(jié)點(diǎn)i的度Di（Di=|Ni|，也可簡稱為i的節(jié)點(diǎn)度）.網(wǎng)絡(luò)中所有節(jié)點(diǎn)的度的平均值Dev稱為網(wǎng)絡(luò)平均節(jié)點(diǎn)度
為了方便后文分析，給出以下常用定義.
定義2（稀疏性）［5］.網(wǎng)絡(luò)拓?fù)渖珊?，若拓?fù)渲械逆溌窋?shù)目與節(jié)點(diǎn)數(shù)目滿足線性關(guān)系，則稱該網(wǎng)絡(luò)拓?fù)渚哂邢∈栊?
定義3（區(qū)域完全覆蓋）.如果監(jiān)測區(qū)域內(nèi)的任意一點(diǎn)均能夠被至少一個(gè)活動(dòng)節(jié)點(diǎn)成功感知，則稱該監(jiān)測區(qū)域被完全覆蓋.
本文假設(shè)無線傳感器網(wǎng)絡(luò)是同構(gòu)網(wǎng)絡(luò)，即網(wǎng)絡(luò)中所有節(jié)點(diǎn)的屬性相同，且節(jié)點(diǎn)的位置信息已知.節(jié)點(diǎn)的通信范圍和覆蓋范圍（也稱感知區(qū)域）可以看作以節(jié)點(diǎn)為中心，分別以通信半徑rc和感知半徑rs為半徑的圓盤，并且網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)具有唯一的身份標(biāo)識(shí)ID.
此外，我們引入一種常用于無線傳感器網(wǎng)絡(luò)中的無線傳輸能量消耗模型［16］.在該模型中，節(jié)點(diǎn)的工作能耗由發(fā)送器能耗和放大器能耗兩部分構(gòu)成，接收能耗為接收器能耗.網(wǎng)絡(luò)節(jié)點(diǎn)的發(fā)射消耗與傳輸距離d有關(guān).因此，節(jié)點(diǎn)傳輸k bits的信息所需的發(fā)射能耗為
接收k bits信息的接收能耗為
其中，Eelec為發(fā)射電路和接收電路的能量消耗，k為傳輸數(shù)據(jù)比特?cái)?shù)，εfs為自由空間傳輸模型系數(shù).
2.2Voronoi覆蓋原理
無線傳感器網(wǎng)絡(luò)中，由于大量節(jié)點(diǎn)部署于監(jiān)測區(qū)域內(nèi)，部分區(qū)域可被多個(gè)節(jié)點(diǎn)同時(shí)覆蓋，同一監(jiān)測信息也可被多個(gè)節(jié)點(diǎn)重復(fù)感知，導(dǎo)致大量的冗余感知數(shù)據(jù).針對(duì)該問題，本文采用Voronoi覆蓋方案，將網(wǎng)絡(luò)中的覆蓋冗余節(jié)點(diǎn)調(diào)整為休眠狀態(tài)，在保證網(wǎng)絡(luò)區(qū)域完全覆蓋的前提下降低網(wǎng)絡(luò)能耗.為了清楚地闡述Voronoi覆蓋原理，給出以下定義4～定義7.
定義4（感應(yīng)鄰居）.在網(wǎng)絡(luò)中，如果一個(gè)節(jié)點(diǎn)i的感知區(qū)域和另外一個(gè)節(jié)點(diǎn)j的感知區(qū)域相交（i/=j），則稱這兩個(gè)節(jié)點(diǎn)i，j互為感應(yīng)鄰居.
定義5（Voronoi鄰居）.在二維無線傳感器網(wǎng)絡(luò)中，如果節(jié)點(diǎn)i所形成的Voronoi多邊形與節(jié)點(diǎn)j所形成的Voronoi多邊形共邊，則稱節(jié)點(diǎn)i和節(jié)點(diǎn)j互為Voronoi鄰居.
定義6（2-Voronoi圖）.在網(wǎng)絡(luò)拓?fù)渲校绻サ艄?jié)點(diǎn)i后，由i的Voronoi鄰居構(gòu)成的Voronoi圖稱為節(jié)點(diǎn)i的2-Voronoi圖.節(jié)點(diǎn)i的2-Voronoi圖的頂點(diǎn)稱為2-Voronoi頂點(diǎn)，記為節(jié)點(diǎn)i的 2-Voronoi圖的邊與節(jié)點(diǎn)i自身覆蓋圓盤邊界的交點(diǎn)，稱為2-Voronoi交點(diǎn)，記為
舉例而言，圖1為節(jié)點(diǎn)i的2-Voronoi圖.其中，節(jié)點(diǎn)j，k，m，n均為節(jié)點(diǎn)i的Voronoi鄰居節(jié)點(diǎn).由圖1可知，節(jié)點(diǎn)i的2-Voronoi頂點(diǎn)有兩個(gè)，分別為和節(jié)點(diǎn)i的2-Voronoi交點(diǎn)有4個(gè)，它們分別為和
圖1 節(jié)點(diǎn)i的2-Voronoi圖Fig.1 The 2-Voronoi diagram of node i
定義7（冗余節(jié)點(diǎn)）.如果一個(gè)節(jié)點(diǎn)的感知區(qū)域被其他節(jié)點(diǎn)完全覆蓋，我們就稱該節(jié)點(diǎn)為冗余節(jié)點(diǎn).
為了簡化計(jì)算，我們使用引理1僅根據(jù)節(jié)點(diǎn)感應(yīng)鄰居的信息分布式地判斷節(jié)點(diǎn)的冗余性.文獻(xiàn)［17］證明了引理1的復(fù)雜度僅為O（NlogN），其中，N為單個(gè)節(jié)點(diǎn)的Voronoi鄰居的個(gè)數(shù).
引理1［17］.節(jié)點(diǎn)i是一個(gè)冗余節(jié)點(diǎn)的充分必要條件是節(jié)點(diǎn)i的2-Voronoi頂點(diǎn)和的2-Voronoi交點(diǎn)均被其Voronoi鄰居覆蓋.
然而，在使用引理1判斷冗余節(jié)點(diǎn)時(shí)，如果兩個(gè)冗余節(jié)點(diǎn)互為Voronoi鄰居節(jié)點(diǎn)，同時(shí)將它們調(diào)節(jié)為休眠狀態(tài)后，它們感知區(qū)域的交叉區(qū)域可能不會(huì)被完全覆蓋.為了解決該問題，本文將所有冗余節(jié)點(diǎn)看做一個(gè)新的無向圖其中，為所有冗余節(jié)點(diǎn)的集合，為互為Voronoi鄰居的冗余節(jié)點(diǎn)間的鏈路集.然后計(jì)算圖的最大獨(dú)立集1最大獨(dú)立集:假設(shè)存在一個(gè)無向圖Gu（Vu，Eu），如果集合S?Vu且S/=?，若S中任意頂點(diǎn)在圖Gu中邏輯不相鄰則稱集合S為圖Gu的獨(dú)立集，如果不存在|S′|＞|S|，則稱集合S為圖Gu的最大獨(dú)立集.，最大獨(dú)立集中的節(jié)點(diǎn)即為覆蓋區(qū)域的盲節(jié)點(diǎn).為了保證監(jiān)測區(qū)域的完全覆蓋，將這部分盲節(jié)點(diǎn)調(diào)節(jié)為活動(dòng)狀態(tài)，其余冗余節(jié)點(diǎn)（即覆蓋冗余節(jié)點(diǎn)）進(jìn)入休眠狀態(tài).
綜上所述，Voronoi覆蓋原理可概括為：每個(gè)節(jié)點(diǎn)分布式的收集其感應(yīng)鄰居的信息后構(gòu)建局部的Voronoi圖，然后由其Voronoi鄰居構(gòu)建2-Voronoi圖，并找出所有的2-Voronoi頂點(diǎn)和所有的2-Voronoi交點(diǎn)，并根據(jù)引理1判斷其是否為冗余節(jié)點(diǎn).最后通過計(jì)算圖的最大獨(dú)立集找出網(wǎng)絡(luò)的盲節(jié)點(diǎn)，將其調(diào)節(jié)為活動(dòng)狀態(tài)，其余冗余節(jié)點(diǎn)維持休眠狀態(tài).此方法可保證在監(jiān)測區(qū)域完全覆蓋的基礎(chǔ)上，減少活動(dòng)節(jié)點(diǎn)數(shù)量，因此可以進(jìn)一步降低能耗.
2.3最小剛性拓?fù)?/p>
最小剛性拓?fù)渲忻總€(gè)頂點(diǎn)至少連有兩條鏈路，并且它的鏈路數(shù)與節(jié)點(diǎn)數(shù)滿足線性關(guān)系，它滿足無線傳感器網(wǎng)絡(luò)2-容錯(cuò)的特性以及稀疏性.為了構(gòu)建容錯(cuò)且稀疏的拓?fù)浣Y(jié)構(gòu)，本文在活動(dòng)節(jié)點(diǎn)間構(gòu)建最小剛性拓?fù)?如果對(duì)網(wǎng)絡(luò)拓?fù)渲胁糠宙溌返拈L度加以限制，就可以維持整個(gè)拓?fù)錁?gòu)型不變，那么就稱該網(wǎng)絡(luò)拓?fù)涫且粋€(gè)剛性拓?fù)洌?］.如果一個(gè)拓?fù)洳皇莿傂缘?，則稱該拓?fù)錇榭勺冃瓮負(fù)?圖2（a）和圖2（b）分別為由4個(gè)節(jié)點(diǎn)構(gòu)成的剛性拓?fù)渑c可變形拓?fù)?由圖2易知，組成剛性拓?fù)涞娜我庖粋€(gè)節(jié)點(diǎn)至少連有兩條鏈路.
圖2 剛性拓?fù)浜涂勺冃瓮負(fù)洌ǎ╝）剛性拓?fù)?；（b）可變形拓?fù)?；（c）最小剛性拓?fù)洌〧ig.2 The rigid topology and flexible topology（（a）Rigid topology；（b）Flexible topology；（c）Minimal rigid topology）
如果刪除一個(gè)剛性拓?fù)渲械娜我庖粭l鏈路則會(huì)影響該拓?fù)涞膭傂?，我們稱這樣的拓?fù)錇樽钚傂酝負(fù)?顯然地，最小剛性拓?fù)涫擎溌窋?shù)最少的剛性拓?fù)洌?8］.圖2（c）為二維空間中由4個(gè)節(jié)點(diǎn)構(gòu)成的最小剛性拓?fù)?在二維空間中，給定一個(gè)含有n個(gè)節(jié)點(diǎn)的拓?fù)浣Y(jié)構(gòu)G（V，ε（t）），節(jié)點(diǎn)i位置的時(shí)變函數(shù)為qi（t）=f（xi（t），yi（t））（其中，i=1，2，···，n）.本文假設(shè)每個(gè)節(jié)點(diǎn)的位置函數(shù)qi（t）是可微的.如果拓?fù)渲械娜我庖粭l鏈路滿足||qi（t）-qj（t）||=c（其中，c為正實(shí)數(shù)），則稱該鏈路的移動(dòng)為剛性移動(dòng).在此基礎(chǔ)上，如果該鏈路同時(shí)滿足則稱為該拓?fù)浣Y(jié)構(gòu)的無窮小變形.如果一個(gè)拓?fù)浣Y(jié)構(gòu)的無窮小變形均是由剛性移動(dòng)引起的，那么則稱該拓?fù)浣Y(jié)構(gòu)為無窮小剛性拓?fù)?顯然，無窮小剛性拓?fù)湟彩且粋€(gè)剛性拓?fù)?
本文引入剛性矩陣檢測某個(gè)拓?fù)涫欠窬哂袆傂裕⑤o助生成剛性拓?fù)浣Y(jié)構(gòu).鏈路集ε中的每一條鏈路，均可用于轉(zhuǎn)化并對(duì)應(yīng)生成剛性矩陣中的一個(gè)行向量.設(shè)鏈路集ε中的所有鏈路均可隨機(jī)排序，當(dāng)構(gòu)建一個(gè)剛性矩陣為網(wǎng)絡(luò)拓?fù)渲械逆溌窋?shù)）時(shí)，ε中第k條鏈路對(duì)應(yīng)于剛性矩陣M中第k行元素構(gòu)成的行向量（如式（4）所示）.
以下引理2和引理3分別描述了剛性矩陣與無窮小剛性拓?fù)?、無窮小剛性拓?fù)渑c最小剛性拓?fù)渲g的內(nèi)在聯(lián)系.
引理2［19］.在二維空間中，假設(shè)矩陣M為n個(gè)傳感器節(jié)點(diǎn)所構(gòu)成拓?fù)涞膭傂跃仃?，該拓?fù)涫菬o窮小剛性的當(dāng)且僅當(dāng)Rank（M）=2n-3.
引理3［5］.由n個(gè)傳感器節(jié)點(diǎn)構(gòu)成的鏈路數(shù)為2n-3的無窮小剛性拓?fù)涫亲钚傂酝負(fù)?
以下引理4表明可以分布式地生成最小剛性拓?fù)?
引理4［16］.一個(gè)剛性拓?fù)銰的一個(gè)子拓?fù)銰′被其他剛性拓?fù)銰′′替代后，得到一個(gè)新拓?fù)淠敲葱峦負(fù)涫莿傂缘?
2.4Delaunay三角剖分圖
Delaunay三角剖分圖是由Voronoi鄰居節(jié)點(diǎn)相互連接而成的三角形，其外接圓圓心是與該三角形相關(guān)的Voronoi圖的一個(gè)頂點(diǎn).圖3為由傳感器節(jié)點(diǎn)構(gòu)成Voronoi圖與Delaunay三角剖分圖，其中，虛線表示由節(jié)點(diǎn)構(gòu)成的Voronoi圖，實(shí)線表示由這些節(jié)點(diǎn)構(gòu)成的Delaunay三角剖分圖.以Delaunay三角剖分圖中任意兩個(gè)三角形（如圖3中所示的矩形虛線框內(nèi)的三角形）為例，以下定理1使用數(shù)學(xué)歸納法證明由n（n≥3）個(gè)節(jié)點(diǎn)構(gòu)成的Delaunay三角剖分圖至少含有2n-3條鏈路，并且它是剛性的.
圖3 節(jié)點(diǎn)的Voronoi圖以及Delaunay三角剖分圖Fig.3 The Voronoi graph and Delaunay triangulation of nodes
定理1.在無線傳感器網(wǎng)絡(luò)中，每個(gè)節(jié)點(diǎn)與其n-1（n≥3）個(gè)通信鄰居節(jié)點(diǎn)構(gòu)成的Delaunay三角剖分圖的鏈路數(shù)不小于2n-3，且其是剛性的.
證明.采用數(shù)學(xué)歸納法證明由n（n≥3）個(gè)傳感器節(jié)點(diǎn)構(gòu)成的Delaunay三角剖分圖至少含有2n-3條鏈路.假設(shè)由n個(gè)傳感器節(jié)點(diǎn)構(gòu)成的Delaunay三角剖分圖的鏈路數(shù)為m.
1）當(dāng)n=3時(shí)，Delaunay三角剖分圖的鏈路數(shù)m=3，滿足鏈路數(shù)不小于2n-3；
2）假設(shè)當(dāng)n=k時(shí)，Delaunay三角剖分圖的鏈路數(shù)m≥2k-3；
3）當(dāng)n=k+1時(shí)，根據(jù)生成Delaunay三角剖分圖逐點(diǎn)插入法［20］的原理可知在原來的Delaunay三角剖分圖中任意插入一點(diǎn)Q時(shí)，共包含有兩種情況：
a）插入點(diǎn)Q在三角形的內(nèi)部：如圖4（a）所示，△IJN和△JNM為Delaunay三角剖分圖中相鄰的兩個(gè)三角形，如圖4（a）所示，當(dāng)插入點(diǎn)Q在△IJN的內(nèi)部時(shí)，連接IQ，JQ和NQ，然后逐個(gè)對(duì)它們進(jìn)行外接圓檢測.通過交換對(duì)角線的方法，保證所形成的圖形（如圖4（a）所示）為Delaunay三角剖分圖.因此，在這種情況下增加一點(diǎn)Q后，形成的Delaunay三角剖分圖增加了三條鏈路，即當(dāng)n=k+1時(shí)，Delaunay三角剖分圖的鏈路數(shù)m′=m+3≥2k-3+3=2k≥2（k+1）-3.
圖4 Delaunay三角剖分圖逐點(diǎn)插入法（（a）插入點(diǎn)Q在△IJN的內(nèi)部；（b）插入點(diǎn)Q在邊JN上）Fig.4 Point by point insertion method of Delaunay triangulation（（a）Insertion node Q in the interior of a triangle△IJN；（b）Insertion node Q is on the JN）
b）插入點(diǎn)Q在三角形的邊上：如圖4（b）所示，當(dāng)插入點(diǎn)Q在公共邊JN上時(shí)，連接IQ和MQ，并且JN被分成了兩條鏈路JQ和NQ，然后逐個(gè)對(duì)它們進(jìn)行外接圓檢測，通過交換對(duì)角線的方法來保證所形成的圖形為Delaunay三角剖分圖.因此，在這種情況下增加一點(diǎn)Q后形成的Delaunay三角剖分圖，同樣增加了三條鏈路，即當(dāng)n=k+1時(shí)，Delaunay三角剖分圖的鏈路數(shù)m′=m+3≥2k-3+3=2k≥2（k+1）-3.因此，當(dāng)n=k+1時(shí)，Delaunay三角剖分圖的鏈路數(shù)不小于2n-3.
因此，每個(gè)傳感器節(jié)點(diǎn)與其n-1（n≥3）個(gè)鄰居節(jié)點(diǎn)構(gòu)成的Delaunay三角剖分圖的鏈路數(shù)m滿足m≥2n-3.
以上我們證明了每個(gè)傳感器節(jié)點(diǎn)與其n-1（n≥3）個(gè)鄰居節(jié)點(diǎn)構(gòu)成的Delaunay三角剖分圖的鏈路數(shù)m滿足m≥2n-3.實(shí)際上，Delaunay三角剖分圖是由若干個(gè)三角形構(gòu)成的，根據(jù)引理4可知?jiǎng)傂酝負(fù)銰的一個(gè)子拓?fù)銰′被其他剛性拓?fù)銰′′替代后，得到一個(gè)新拓?fù)涫莿傂缘?，而三角形是一個(gè)最簡單的剛性圖，因此由n（n≥3）個(gè)傳感器節(jié)點(diǎn)構(gòu)成的Delaunay剖分圖是剛性的.
綜上所述，由n（n≥3）個(gè)傳感器節(jié)點(diǎn)構(gòu)成的Delaunay剖分圖至少含有2n-3條鏈路，且其是剛性的.
基于定理1，我們給出了以下定理2，為分布式的生成基于Delaunay三角剖分圖的最小剛性拓?fù)涮峁┝死碚撘罁?jù).
定理2.如果網(wǎng)絡(luò)中任意節(jié)點(diǎn)i與其通信鄰居節(jié)點(diǎn)構(gòu)成基于Delaunay三角剖分圖的最小剛性拓?fù)溆洖镚i（i=1，···，n），Gm（Vm，εm）為網(wǎng)絡(luò)節(jié)點(diǎn)生成的全局最小剛性拓?fù)洌瑒t有以下結(jié)論：
1）若Gi與Gj（i/=j）有公共節(jié)點(diǎn)e和f，如果存在鏈路且那么
2）若Gi與Gj（i/=j）有n個(gè)公共節(jié)點(diǎn)，且Gi或Gj中存在由該n個(gè)節(jié)點(diǎn)構(gòu)成的圈2圈:節(jié)點(diǎn)間鏈路首尾相連構(gòu)成的封閉回路.，如果拓?fù)銰j中存在m（2m≤n）條鏈路（鏈路的頂點(diǎn)均為公共點(diǎn)）滿足但拓?fù)銰i中同樣存在m條鏈路（鏈路的頂點(diǎn)均為公共點(diǎn)）與中任意鏈路均不相同）滿足且m條鏈路的權(quán)值和大于另外m條鏈路那么，將權(quán)值和較小的鏈路代替權(quán)值和較大的鏈路后，再刪除滿足條件1）的鏈路，得到的拓?fù)涫亲钚傂酝負(fù)?
證明.1）假設(shè)Gi與Gj（i/=j）有公共節(jié)點(diǎn)e和f，如果存在且由于最小剛性拓?fù)涫擎溌窋?shù)最少的剛性拓?fù)?因此，連接最小剛性拓?fù)渲腥我鈨蓚€(gè)不存在鏈路的點(diǎn)，得到的拓?fù)渫瑯邮莿傂缘?，故存在是剛性?根據(jù)引理4一個(gè)剛性拓?fù)涞淖油負(fù)溆闪硗庖粋€(gè)剛性拓?fù)浯娴玫降耐負(fù)淙匀皇莿傂缘?因此，可用Gi替換來保持最終拓?fù)淙匀皇莿傂缘?，因此，去掉該鏈路不改變拓?fù)涞膭傂蕴匦?，即得證.
2）假設(shè)Gi與Gj（i/=j）有n個(gè)公共節(jié)點(diǎn)，且Gi或Gj中存在由該n個(gè)節(jié)點(diǎn)構(gòu)成的圈，如果拓?fù)銰j中存在m條鏈路（鏈路的頂點(diǎn)均為公共點(diǎn)）滿足但拓?fù)銰i中存在m 條鏈路（鏈路的頂點(diǎn)均為公共點(diǎn)）（q=1，···，m）與中任意鏈路均不相同）滿足但由于生成Delaunay三角剖分圖時(shí)，在同一個(gè)圈內(nèi)生成三角形的連接鏈路不同，如果直接刪除滿足條件1）的鏈路，即同時(shí)刪除和則圈內(nèi)的剛性不能保證，全局拓?fù)涞膭傂砸膊荒鼙ＷC，因此，則將權(quán)值和較小的鏈路代替權(quán)值和較大的鏈路后，根據(jù)引理4一個(gè)剛性拓?fù)涞淖油負(fù)溆闪硗庖粋€(gè)剛性拓?fù)浯嫔傻男峦負(fù)涫莿傂缘?，由于新拓?fù)渑c原拓?fù)銰i有相同的鏈路，因此拓?fù)涫亲钚傂酝負(fù)?，然后刪除滿足條件1）的鏈路.用Gij（Vij，εij）表示由拓?fù)浜屯負(fù)銰j（Vj，εj）的公共節(jié)點(diǎn)組成的拓?fù)洌渲?，Vij=Vi∩Vj，εij表示兩個(gè)頂點(diǎn)均在Vij中的鏈路，因此有令εij=as∪bs1∪bs2，其中，as表示拓?fù)渑cGj的公共鏈路，bs1和bs2分別表示εij中僅存在于和Gj中的鏈路.同時(shí)刪除bs1和bs2后，每個(gè)子拓?fù)錆M足否則，至少存在一條鏈路使或Gj的鏈路數(shù)超過這與條件或Gj均為最小剛性拓?fù)湎嗝?假設(shè)刪除bs1和bs2后得到的拓?fù)溆谐^2|Vi∪Vj|-3的鏈路，則Gij有|εij|＞2|Vij|-3，這將導(dǎo)致在刪除bs1和bs2之前，或Gj的鏈路數(shù)超過2|Vi|-3或2|Vj|-3，這與條件或Gj均為最小剛性拓?fù)湎嗝埽虼?，得到的拓?fù)錆M足-3.由上述1）可知?jiǎng)h除bs1和bs2后不改變拓?fù)涞膭傂裕虼?，有因此，刪除bs1和 bs2后有，生成的最終拓?fù)錇樽钚傂酝負(fù)?
3 MRTc算法
本節(jié)我們?cè)敿?xì)介紹基于Voronoi覆蓋及Delaun -ay三角剖分圖的最小剛性拓?fù)淇刂扑惴∕RTc.算法執(zhí)行過程可分為以下4個(gè)階段：1）信息收集階段，網(wǎng)絡(luò)中各節(jié)點(diǎn)僅根據(jù)其感知鄰居節(jié)點(diǎn)和通信鄰居節(jié)點(diǎn)的信息構(gòu)建拓?fù)?，可降低網(wǎng)絡(luò)中消息傳送數(shù)量；2）權(quán)值確定階段，利用權(quán)值函數(shù)判定權(quán)值大小，保證拓?fù)浣Y(jié)構(gòu)的唯一性；3）拓?fù)錁?gòu)建階段，網(wǎng)絡(luò)首先分布式確定覆蓋冗余節(jié)點(diǎn)，將其調(diào)節(jié)為休眠狀態(tài)，在保證網(wǎng)絡(luò)監(jiān)測區(qū)域完全覆蓋的條件下，通過減少活動(dòng)節(jié)點(diǎn)數(shù)量，降低網(wǎng)絡(luò)能耗.然后通過構(gòu)建基于Delaunay三角剖分圖的最小剛性拓?fù)浣Y(jié)構(gòu)，提高網(wǎng)絡(luò)容錯(cuò)性，并可限制平均節(jié)點(diǎn)度數(shù)；4）功率調(diào)節(jié)階段，為了進(jìn)一步地降低網(wǎng)絡(luò)能耗，將每個(gè)節(jié)點(diǎn)的功率調(diào)節(jié)為網(wǎng)絡(luò)所需要的最小功率.
3.1信息收集
首先，MRTc算法采用與文獻(xiàn)［5］相同的機(jī)制實(shí)現(xiàn)通信鄰居節(jié)點(diǎn)的收集.通過該機(jī)制，網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)均能獲得其通信鄰居節(jié)點(diǎn)的信息，該信息包含每個(gè)通信鄰居節(jié)點(diǎn)的ID、節(jié)點(diǎn)位置坐標(biāo)以及與其通信鄰居節(jié)點(diǎn)的歐氏距離.通過這些信息，可得知每個(gè)節(jié)點(diǎn)的通信鄰居和感應(yīng)鄰居，也可通過下節(jié)的權(quán)值函數(shù)計(jì)算該節(jié)點(diǎn)與其通信鄰居節(jié)點(diǎn)的鏈路權(quán)值.
3.2權(quán)值函數(shù)的確定
無線傳感器網(wǎng)絡(luò)中保證兩節(jié)點(diǎn)i，j通信所需要的最小傳輸功率［11］為其中，α和 δ為可調(diào)參數(shù)，并且與特定無線通信系統(tǒng)硬件和傳輸環(huán)境有關(guān)，通常有2≤α≤4.顯然，傳輸功率隨著兩節(jié)點(diǎn)間距離的增加而增大.因此，本文用兩點(diǎn)間的距離代表這兩點(diǎn)間鏈路的權(quán)值.然而，在無線傳感器網(wǎng)絡(luò)中，不同節(jié)點(diǎn)間的距離可能相同，這會(huì)導(dǎo)致鏈路不同，但卻擁有相同的權(quán)值，所生成的最終拓?fù)浣Y(jié)構(gòu)不唯一.
為了保證生成拓?fù)涞奈ㄒ恍?，本文采用了以下?quán)值函數(shù).當(dāng)節(jié)點(diǎn)間距離滿足如式（6）～式（8）所示的三個(gè)條件之一時(shí)，即可得鏈路與的權(quán)值函數(shù)滿足
式中，id（i），id（j），id（m），id（n）分別表示節(jié)點(diǎn)i，j，m，n的ID.由于每個(gè)節(jié)點(diǎn)的ID是唯一的，因此該權(quán)值函數(shù)w保證了擁有最小權(quán)值的鏈路具有唯一性，由此可知使用MRTc算法生成的拓?fù)浣Y(jié)構(gòu)也是唯一的.
3.3拓?fù)錁?gòu)建
1）冗余節(jié)點(diǎn)選擇與休眠調(diào)度
監(jiān)測區(qū)域的良好覆蓋性是傳感器網(wǎng)絡(luò)拓?fù)錁?gòu)建的基本要求之一.由于節(jié)點(diǎn)經(jīng)常采用隨機(jī)部署方式，導(dǎo)致部分監(jiān)測區(qū)域可被多個(gè)節(jié)點(diǎn)同時(shí)覆蓋，由此產(chǎn)生大量冗余感知信息.因此，在保證網(wǎng)絡(luò)全覆蓋的前提下，將覆蓋冗余節(jié)點(diǎn)調(diào)節(jié)為休眠狀態(tài)，對(duì)于降低網(wǎng)絡(luò)能耗是必要的.本文第2.2節(jié)中Voronoi覆蓋原理提供了判定覆蓋冗余節(jié)點(diǎn)的理論依據(jù)，它能夠保證在將選出的覆蓋冗余節(jié)點(diǎn)調(diào)節(jié)為休眠狀態(tài)后，活動(dòng)節(jié)點(diǎn)依然能夠保持對(duì)監(jiān)測區(qū)域的完全覆蓋.其具體過程如MRTc算法偽代碼中第4～10行偽代碼所示.
2）基于Delaunay三角剖分圖的最小剛性拓?fù)涞臉?gòu)建
為了提高網(wǎng)絡(luò)的魯棒性，同時(shí)限制網(wǎng)絡(luò)的平均節(jié)點(diǎn)度.本節(jié)基于定理2，將覆蓋冗余節(jié)點(diǎn)調(diào)節(jié)為休眠狀態(tài)后，在活動(dòng)節(jié)點(diǎn)間構(gòu)建了基于Delaunay三角剖分圖的最小剛性拓?fù)浣Y(jié)構(gòu).構(gòu)建該拓?fù)涞牟襟E如下：
步驟1.每個(gè)節(jié)點(diǎn)與其鄰居節(jié)點(diǎn)構(gòu)建Delaunay三角剖分圖；
步驟2.在Delaunay三角剖分圖的基礎(chǔ)上不損失剛性的前提下刪除較長鏈路構(gòu)建局部最小剛性拓?fù)洌?/p>
步驟3.刪除不屬于全局最小剛性拓?fù)涞逆溌?，可?gòu)建全局最小剛性拓?fù)?
3.4功率調(diào)節(jié)
算法的最終階段，為了進(jìn)一步降低網(wǎng)絡(luò)能耗，對(duì)網(wǎng)絡(luò)中活動(dòng)節(jié)點(diǎn)的功率進(jìn)行調(diào)節(jié).功率調(diào)節(jié)時(shí)，每個(gè)節(jié)點(diǎn)將自身功率設(shè)置為能夠覆蓋其全部邏輯鄰居節(jié)點(diǎn)（節(jié)點(diǎn)i的邏輯鄰居節(jié)點(diǎn)即為經(jīng)過MRTc算法優(yōu)化后，仍然與節(jié)點(diǎn)i有通信關(guān)系的節(jié)點(diǎn)）所需要的最小功率，即節(jié)點(diǎn)能與距離其最遠(yuǎn)的邏輯鄰居節(jié)點(diǎn)成功通信的功率.這意味著可將每個(gè)活動(dòng)節(jié)點(diǎn)的通信半徑設(shè)置為與其距離最遠(yuǎn)的邏輯鄰居節(jié)點(diǎn)的距離.節(jié)點(diǎn)通信半徑的公式如下所示.
其中，rc（i）為節(jié)點(diǎn)i的通信半徑，為節(jié)點(diǎn)i的邏輯鄰居節(jié)點(diǎn)的集合.
分布式構(gòu)建基于Voronoi覆蓋與Delaunay三角剖分圖的最小剛拓?fù)浣Y(jié)構(gòu)的MRTc算法的偽代碼如下所示.
首先，節(jié)點(diǎn)通過信息的收集得到節(jié)點(diǎn)的感應(yīng)鄰居集合和通信鄰居節(jié)點(diǎn)集合（行1～2）.接著第3行根據(jù)第3.2節(jié)權(quán)值函數(shù)確定節(jié)點(diǎn)與通信鄰居節(jié)點(diǎn)的權(quán)值.行4～32為拓?fù)涞臉?gòu)建階段，該階段節(jié)點(diǎn)首先根據(jù)覆蓋原理（見第2.2節(jié)Voronoi覆蓋原理）確定網(wǎng)絡(luò)中的覆蓋冗余節(jié)點(diǎn)，并將其調(diào)節(jié)為休眠狀態(tài)（行4～10）.然后，在活動(dòng)節(jié)點(diǎn)間構(gòu)建基于Delaunay三角剖分圖的最小剛性拓?fù)浣Y(jié)構(gòu)，改善網(wǎng)絡(luò)容錯(cuò)性，有效約束網(wǎng)絡(luò)的平均節(jié)點(diǎn)度（行11～32）.算法的最終階段（行33）每個(gè)節(jié)點(diǎn)通過調(diào)節(jié)其傳輸功率來降低網(wǎng)絡(luò)能耗，將功率調(diào)節(jié)為能夠覆蓋所有邏輯鄰居節(jié)點(diǎn)的最小功率，（即）.
4 MRTc算法性能分析
MRTc算法使得網(wǎng)絡(luò)中的覆蓋冗余節(jié)點(diǎn)調(diào)節(jié)為休眠狀態(tài)，并在活動(dòng)節(jié)點(diǎn)間構(gòu)建最小剛性拓?fù)浣Y(jié)構(gòu)，有效降低了網(wǎng)絡(luò)能耗，該算法還具有以下4個(gè)方面的性質(zhì).
性質(zhì)1.由n個(gè)傳感器節(jié)點(diǎn)形成的初始拓?fù)?初始拓?fù)?沒有經(jīng)過任何算法優(yōu)化的起始拓?fù)浣Y(jié)構(gòu)GC（VC，εC），在經(jīng)過MRTc算法優(yōu)化后得到的拓?fù)浣Y(jié)構(gòu)GD（VD，εD）是2-容錯(cuò)的.
證明.通過第2.3節(jié)，我們可知構(gòu)成最小剛性拓?fù)涞娜我庖粋€(gè)節(jié)點(diǎn)至少連有兩條鏈路，由于初始拓?fù)銰C（VC，εC）經(jīng)過MRTc算法優(yōu)化后，得到的拓?fù)涫亲钚傂酝負(fù)?因此，拓?fù)浣Y(jié)構(gòu)GD（VD，εD）中的任意一個(gè)節(jié)點(diǎn)至少連接有兩條鏈路，即拓?fù)渲械娜我夤?jié)點(diǎn)至少含有兩條鏈路，根據(jù)第2.1節(jié)k-容錯(cuò)的定義可知，最終生成的拓?fù)涫?-容錯(cuò)的.
性質(zhì)2.由n個(gè)傳感器節(jié)點(diǎn)形成的初始拓?fù)銰C（VC，εC），在經(jīng)過MRTc算法優(yōu)化后得到的拓?fù)浣Y(jié)構(gòu)GD（VD，εD）滿足區(qū)域完全覆蓋.
證明.根據(jù)第2.2節(jié)覆蓋冗余節(jié)點(diǎn)的定義可知，如果一個(gè)節(jié)點(diǎn)的覆蓋區(qū)域被其他節(jié)點(diǎn)完全覆蓋，則該節(jié)點(diǎn)為覆蓋冗余節(jié)點(diǎn).經(jīng)算法MRTc優(yōu)化后，這些覆蓋冗余節(jié)點(diǎn)被調(diào)節(jié)為休眠狀態(tài)后，它們的覆蓋區(qū)域仍然可以被其他節(jié)點(diǎn)所覆蓋.因此，由n個(gè)傳感器形成的初始拓?fù)銰C（VC，εC），在經(jīng)過MRTc算法優(yōu)化后得到的拓?fù)浣Y(jié)構(gòu)GD（VD，εD）滿足區(qū)域完全覆蓋.
性質(zhì)3.由n個(gè)傳感器節(jié)點(diǎn)形成的初始拓?fù)銰C（VC，εC），在經(jīng)過MRTc算法優(yōu)化后得到的拓?fù)浣Y(jié)構(gòu)GD（VD，εD）是稀疏的.
證明.根據(jù)第2.1節(jié)網(wǎng)絡(luò)稀疏性的定義，可知若拓?fù)錆M足網(wǎng)絡(luò)稀疏性要求，需要網(wǎng)絡(luò)中的鏈路數(shù)量與節(jié)點(diǎn)數(shù)量之間呈線性關(guān)系.又根據(jù)第2.3節(jié)引理3知，由任意n個(gè)節(jié)點(diǎn)構(gòu)成的最小剛性圖有2n-3條鏈路.由于GC（VC，εC）在經(jīng)過MRTc算法優(yōu)化后，得到的拓?fù)浣Y(jié)構(gòu)GD（VD，εD）是一個(gè)最小剛性拓?fù)?，即拓?fù)銰D（VD，εD）中的鏈路數(shù)量和節(jié)點(diǎn)數(shù)量呈線性關(guān)系.所以，經(jīng)過MRTc算法優(yōu)化后得到的拓?fù)浣Y(jié)構(gòu)GD（VD，εD）是稀疏的.
性質(zhì)4.經(jīng)過MRTc算法優(yōu)化后得到的拓?fù)浣Y(jié)構(gòu)GD（VD，εD），其平均節(jié)點(diǎn)度不大于4.
證明.由引理3和定理2可知，經(jīng)MRTc算法優(yōu)化后的拓?fù)浣Y(jié)構(gòu)GD（VD，εD）有2n-3條鏈路.根據(jù)握手定理［21］可知，對(duì)于任意拓?fù)銰（V，ε），網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)度之和為2|ε|，其中|ε|為該拓?fù)渲墟溌返臄?shù)目.因此，拓?fù)浣Y(jié)構(gòu)GD（VD，εD）中所有節(jié)點(diǎn)的節(jié)點(diǎn)度之和為故它的平均節(jié)點(diǎn)度為即拓?fù)浣Y(jié)構(gòu)GD（VD，εD）的平均網(wǎng)絡(luò)節(jié)點(diǎn)度不超過4.
5 MRTc算法性能評(píng)價(jià)
為了分析和評(píng)價(jià)MRTc算法的性能，本文在Matlab R2009a環(huán)境中，使用M語言設(shè)計(jì)了以下4組數(shù)值仿真實(shí)驗(yàn).實(shí)驗(yàn)1分別在均勻和隨機(jī)兩種網(wǎng)絡(luò)中驗(yàn)證睡眠調(diào)度方案的性能；實(shí)驗(yàn)2以52個(gè)節(jié)點(diǎn)為例詳細(xì)介紹了同構(gòu)網(wǎng)絡(luò)拓?fù)涞臉?gòu)建過程；實(shí)驗(yàn)3通過比較4種典型算法，驗(yàn)證了MRTc算法的性能；實(shí)驗(yàn)4對(duì)最小剛性拓?fù)浣Y(jié)構(gòu)下睡眠調(diào)度前后網(wǎng)絡(luò)的總能耗以及活動(dòng)節(jié)點(diǎn)的比例進(jìn)行了詳細(xì)比較.本文所有實(shí)驗(yàn)均假設(shè)監(jiān)測區(qū)域?yàn)?00×100的方形區(qū)域，傳感器節(jié)點(diǎn)的最大感知半徑設(shè)為20.監(jiān)測區(qū)域范圍與節(jié)點(diǎn)感知半徑的大小見文獻(xiàn)［22］.節(jié)點(diǎn)的最大通信半徑為40.在均勻網(wǎng)絡(luò)中，每個(gè)傳感器節(jié)點(diǎn)均位于網(wǎng)格的頂點(diǎn)，網(wǎng)格大小設(shè)置為式中n為監(jiān)測區(qū)域內(nèi)布置的節(jié)點(diǎn)數(shù)目，ra為每個(gè)網(wǎng)格的長度值，rb為每個(gè)網(wǎng)格的寬度值.
5.1實(shí)驗(yàn)1冗余節(jié)點(diǎn)選擇與休眠調(diào)度
降低網(wǎng)絡(luò)能耗是拓?fù)淇刂频闹饕O(shè)計(jì)目標(biāo)，為了實(shí)現(xiàn)該目標(biāo)，本文采用了睡眠調(diào)度方案在保證網(wǎng)絡(luò)監(jiān)測區(qū)域全覆蓋的前提下，將覆蓋冗余節(jié)點(diǎn)調(diào)節(jié)為休眠狀態(tài).為了驗(yàn)證睡眠調(diào)度方案的性能，本實(shí)驗(yàn)分別在均勻網(wǎng)絡(luò)和隨機(jī)網(wǎng)絡(luò)兩種網(wǎng)絡(luò)中進(jìn)行仿真實(shí)驗(yàn).圖5和圖6分別為在均勻網(wǎng)絡(luò)和隨機(jī)網(wǎng)絡(luò)中部署70個(gè)節(jié)點(diǎn)時(shí)，睡眠調(diào)度前后的監(jiān)測區(qū)域覆蓋情況.節(jié)點(diǎn)感知半徑均為20.由這4個(gè)子圖可以看出在經(jīng)過睡眠調(diào)度后，監(jiān)測區(qū)域仍然被活動(dòng)節(jié)點(diǎn)完全覆蓋滿足性質(zhì)2.
圖5 均勻網(wǎng)絡(luò)睡眠調(diào)度（（a）睡眠調(diào)度前；（b）睡眠調(diào)度后）Fig.5 The sleep scheduling in uniform networks（（a）Before the sleep scheduling；（b）After the sleep scheduling）
圖6 隨機(jī)網(wǎng)絡(luò)睡眠調(diào)度（（a）睡眠調(diào)度前；（b）睡眠調(diào)度后）Fig.6 The sleep scheduling in random networks（（a）Before the sleep scheduling；（b）After the sleep scheduling）
當(dāng)節(jié)點(diǎn)數(shù)量分別為49、56、63、70、77時(shí)，算法的覆蓋性能如圖7所示，子圖7（a）、7（b）分別為實(shí)驗(yàn)中冗余節(jié)點(diǎn)的數(shù)目和冗余節(jié)點(diǎn)比例.由圖7（a）、7（b）可知，無論在均勻網(wǎng)絡(luò)中還是冗余網(wǎng)絡(luò)中，冗余節(jié)點(diǎn)的數(shù)目隨著網(wǎng)絡(luò)節(jié)點(diǎn)密度的增大而增加，并且冗余節(jié)點(diǎn)的占比也隨之增大.該結(jié)果表明對(duì)于節(jié)點(diǎn)密度不同的網(wǎng)絡(luò)，該算法均可以起到較好的睡眠調(diào)度效果.
5.2實(shí)驗(yàn)2網(wǎng)絡(luò)拓?fù)涞臉?gòu)建過程
在實(shí)驗(yàn)1的基礎(chǔ)上，我們以52個(gè)節(jié)點(diǎn)為例詳細(xì)介紹網(wǎng)絡(luò)拓?fù)涞臉?gòu)建過程.首先，將52個(gè)感知半徑為20的節(jié)點(diǎn)隨機(jī)部署在100×100的監(jiān)測區(qū)域內(nèi)，節(jié)點(diǎn)的分布情況與監(jiān)測區(qū)域的覆蓋情況如圖8（a）所示.根據(jù)Voronoi覆蓋原理選擇覆蓋冗余節(jié)點(diǎn)，并將覆蓋冗余節(jié)點(diǎn)調(diào)節(jié)為休眠狀態(tài).活動(dòng)節(jié)點(diǎn)對(duì)監(jiān)測區(qū)域的覆蓋情況如圖8（b）所示.由圖8（b）可以看出，在將部分節(jié)點(diǎn)調(diào)節(jié)為休眠節(jié)點(diǎn)后，監(jiān)測區(qū)域內(nèi)的任意一點(diǎn)仍至少被一個(gè)活動(dòng)節(jié)點(diǎn)覆蓋.可見，經(jīng)過睡眠調(diào)度后，網(wǎng)絡(luò)滿足完全覆蓋.在此基礎(chǔ)上，每個(gè)活動(dòng)節(jié)點(diǎn)與其鄰居節(jié)點(diǎn)生成局部的Delaunay三角剖分圖，構(gòu)建局部最小剛性拓?fù)浣Y(jié)構(gòu)如圖9（a）所示，圖中實(shí)線表示兩點(diǎn)間的實(shí)際鏈路，虛線表示可以被刪除的鏈路.每個(gè)節(jié)點(diǎn)在維持剛性的前提下刪除權(quán)重較大的鏈路，與其鄰居節(jié)點(diǎn)構(gòu)建權(quán)重和最小的局部最小剛性拓?fù)淙鐖D9（b）所示.最后根據(jù)定理2，刪除不屬于全局最小剛性拓?fù)涞逆溌罚瑯?gòu)建起全局最小剛性拓?fù)浣Y(jié)構(gòu)，如圖9（c）所示.
由該實(shí)驗(yàn)容易看出，經(jīng)MRTc算法優(yōu)化后的拓?fù)?，即圖9（c）中的任意一個(gè)節(jié)點(diǎn)至少連有兩條鏈路.這意味著該拓?fù)浣Y(jié)構(gòu)是2-容錯(cuò)的，滿足性質(zhì)1.圖9（c）與圖9（a）和圖9（b）相比，圖9（c）中的鏈路數(shù)明顯減少，表明經(jīng)MRTc算法優(yōu)化后的拓?fù)浣Y(jié)構(gòu)，其網(wǎng)絡(luò)平均節(jié)點(diǎn)度明顯小于圖9（a）和圖9（b）拓?fù)涞钠骄?jié)點(diǎn)度，即由MRTc算法優(yōu)化后的拓?fù)浣Y(jié)構(gòu)能夠幫助降低網(wǎng)絡(luò)MAC層干擾.
5.3實(shí)驗(yàn)3重要性能指標(biāo)的橫向比較
為了驗(yàn)證MRTc算法的性能，本實(shí)驗(yàn)選取4種經(jīng)典的拓?fù)淇刂扑惴℅G（Gabriel graph）、RNG（Relative neighborhood graph）、LMST、Udel與本文提出的MRTc算法進(jìn)行比較.首先，實(shí)驗(yàn)對(duì)5種算法生成的拓?fù)浣Y(jié)構(gòu)進(jìn)行對(duì)比.在100×100的區(qū)域內(nèi)隨機(jī)生成30個(gè)節(jié)點(diǎn)，在相同的仿真環(huán)境下，使用上述5種算法來構(gòu)建拓?fù)浣Y(jié)構(gòu)，并對(duì)5種拓?fù)浣Y(jié)構(gòu)進(jìn)行比較.實(shí)驗(yàn)中節(jié)點(diǎn)的感知半徑設(shè)置為20.當(dāng)傳感器節(jié)點(diǎn)的感知半徑和通信半徑滿足rc≥2×rs時(shí)，如果網(wǎng)絡(luò)在給定凸區(qū)域滿足1-覆蓋，則能夠保證網(wǎng)絡(luò)的連通性［23］.因此，本文假設(shè)網(wǎng)絡(luò)節(jié)點(diǎn)的感知半徑和通信半徑滿足rc=2×rs.然后，在相同的仿真環(huán)境中，通過改變傳感器節(jié)點(diǎn)的個(gè)數(shù)，使其在30～100的范圍內(nèi)變動(dòng)，比較5種不同算法的平均節(jié)點(diǎn)度、平均鏈路長度以及網(wǎng)絡(luò)的最大與最小節(jié)點(diǎn)度.通過全面的性能比較，驗(yàn)證本文提出的MRTc算法的性能.
圖7 兩種網(wǎng)絡(luò)中冗余節(jié)點(diǎn)數(shù)目和所占節(jié)點(diǎn)比例的比較（（a）冗余節(jié)點(diǎn)個(gè)數(shù)的比較；（b）冗余節(jié)點(diǎn)比例的比較）Fig.7 The comparison of the number of redundant nodes and the proportion of redundant nodes in the two networks（（a）The comparison of the number of redundant nodes；（b）The comparison of the proportion of the redundant nodes）
圖8 睡眠調(diào)度前后區(qū)域覆蓋情況（（a）睡眠調(diào)度前區(qū)域覆蓋情況；（b）睡眠調(diào)度后區(qū)域覆蓋情況）Fig.8 The area coverage by using the sleep scheduling（（a）The area coverage before sleep scheduling；（b）The area coverage after sleep scheduling）
1）網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)對(duì)比
在相同的仿真環(huán)境下，比較5種不同的拓?fù)淇刂扑惴℅G、RNG、LMST、Udel與MRTc生成的拓?fù)浣Y(jié)構(gòu).圖10顯示了由圖9（c）中的30個(gè)活動(dòng)節(jié)點(diǎn)在100×100的區(qū)域內(nèi)分別使用上述5種方法生成的拓?fù)浣Y(jié)構(gòu).由圖10（d）可以看出算法Udel生成的拓?fù)浣Y(jié)構(gòu)中有67條鏈路，是這5種拓?fù)浣Y(jié)構(gòu)中鏈路數(shù)最多的.該拓?fù)浣Y(jié)構(gòu)的平均節(jié)點(diǎn)度也是最大的.此外，Udel算法是一個(gè)集中式方法，它需要預(yù)先獲知網(wǎng)絡(luò)中所有節(jié)點(diǎn)的信息.相比之下，RNG算法（見圖10（b））和LMST算法（圖10（c））是分布式算法，它們的構(gòu)建過程只需依賴鄰居節(jié)點(diǎn)的信息.由這兩種算法所生成的拓?fù)渲?，鏈路?shù)分別為34和38，平均節(jié)點(diǎn)度過低.過低的節(jié)點(diǎn)度會(huì)導(dǎo)致節(jié)點(diǎn)間的通信鏈路過長，網(wǎng)絡(luò)能耗隨之增大.而本文算法（圖10（e））和GG算法（圖10（a））的鏈路數(shù)分別為57和52，兩者相差不大.然而，由這兩個(gè)子圖容易看出，GG算法擁有的長鏈路數(shù)量較多，這意味著該算法的能耗較大.
圖9 MRTc拓?fù)浣Y(jié)構(gòu)的構(gòu)建過程（（a）構(gòu)建局部Delaunay三角剖分圖；（b）構(gòu)建局部最小剛性拓?fù)?；（c）構(gòu)建全局最小剛性拓?fù)洌〧ig.9 The construction process of MRTc topology（（a）The construction of local Delaunay triangulation；（b）The construction of local minimum rigid topology；（c）The construction of global minimum rigid topology）
圖10 不同算法生成的拓?fù)浣Y(jié)構(gòu)（（a）GG；（b）RNG；（c）LMST；（d）Udel；（e）MRTc）Fig.10 The topological structures of different algorithms（（a）GG；（b）RNG；（c）LMST；（d）Udel；（e）MRTc）
2）其他重要性能指標(biāo)比較
在100×100的監(jiān)測區(qū)域內(nèi)，當(dāng)節(jié)點(diǎn)數(shù)量由30逐漸遞增時(shí)，上述5種算法的平均節(jié)點(diǎn)度、平均傳輸半徑、最大節(jié)點(diǎn)度以及最小節(jié)點(diǎn)度4種性能指標(biāo)如圖11所示.
網(wǎng)絡(luò)的平均節(jié)點(diǎn)度定義為網(wǎng)絡(luò)中所有節(jié)點(diǎn)的節(jié)點(diǎn)度之和與節(jié)點(diǎn)數(shù)量的比值.在無線傳感器網(wǎng)絡(luò)中，高的平均節(jié)點(diǎn)度需要在MAC層特別設(shè)計(jì)接入訪問機(jī)制，嚴(yán)重時(shí)還可引發(fā)訪問干擾和數(shù)據(jù)碰撞，造成非必要的網(wǎng)絡(luò)能耗.反過來，網(wǎng)絡(luò)的平均節(jié)點(diǎn)度過低則會(huì)導(dǎo)致節(jié)點(diǎn)間的鏈路過長，通信能耗值也相應(yīng)地增加.文獻(xiàn)［16］提出網(wǎng)絡(luò)的最優(yōu)平均節(jié)點(diǎn)度為6.根據(jù)實(shí)驗(yàn)2網(wǎng)絡(luò)拓?fù)錁?gòu)建過程可知，經(jīng)過MRTc算法優(yōu)化后減少了網(wǎng)絡(luò)拓?fù)涞逆溌窋?shù).由引理4可知，經(jīng)MRTc算法優(yōu)化后每個(gè)節(jié)點(diǎn)的節(jié)點(diǎn)度也會(huì)相應(yīng)地降低.圖11（a）為GG、RNG、LMST、Udel以及MRTc這5種算法在網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)目在30～100間變化時(shí)，網(wǎng)絡(luò)的平均節(jié)點(diǎn)的比較.由性質(zhì)4知算法MRTc的平均節(jié)點(diǎn)度因此，隨著節(jié)點(diǎn)數(shù)目n的增加，MRTc算法的平均節(jié)點(diǎn)度逐漸增加，且其值接近于4.由圖11（a）知該算法的平均節(jié)點(diǎn)度變化緩慢，說明該算法較穩(wěn)定.相比之下，算法RNG和算法LMST的平均節(jié)點(diǎn)度在3以下，這意味著由這兩種算法生成的拓?fù)浣Y(jié)構(gòu)過于稀疏.而Udel算法的平均節(jié)點(diǎn)度接近于最優(yōu)值6，這與文獻(xiàn)［12］相符合.
傳輸半徑定義為節(jié)點(diǎn)與其最遠(yuǎn)鄰居之間的距離.平均傳輸半徑為網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)的傳輸半徑之和與節(jié)點(diǎn)數(shù)量的比值.網(wǎng)絡(luò)中節(jié)點(diǎn)的平均傳輸半徑越大，網(wǎng)絡(luò)通信能耗也越大.上述5種算法平均傳輸半徑的比較結(jié)果如圖11（b）所示.由第2.3節(jié)2）基于Delaunay三角剖分圖的最小剛性拓?fù)涞臉?gòu)建可知MRTc算法是由刪除Delaunay三角剖分圖的部分較長鏈路得到的.因此，MRTc算法生成的拓?fù)浣Y(jié)構(gòu)具有較小的平均傳輸半徑.由圖11（b）可知，Udel算法和GG算法的平均傳輸半徑均高于MRTc算法.而LMST算法與RNG算法具有更小的平均傳輸半徑.
圖11（c）和（d）分別為5種算法最大節(jié)點(diǎn)度與最小節(jié)點(diǎn)度的比較.網(wǎng)絡(luò)的最大節(jié)點(diǎn)度定義為網(wǎng)絡(luò)中邏輯鏈路［5］最多的節(jié)點(diǎn)的度數(shù).與之類似，網(wǎng)絡(luò)的最小節(jié)點(diǎn)度定義為網(wǎng)絡(luò)中邏輯鏈路最少的節(jié)點(diǎn)的度數(shù).由第2.3節(jié)知最小剛性拓?fù)渲泄?jié)點(diǎn)至少包含兩條鏈路，因此，由MRTc算法生成的拓?fù)浣Y(jié)構(gòu)的最小節(jié)點(diǎn)度不低于2.這意味著由該算法生成的拓?fù)浣Y(jié)構(gòu)是2-容錯(cuò)的，具有較高的魯棒性.由圖11（c）和（d）知算法LMST和RNG的最大節(jié)點(diǎn)度均在最優(yōu)值6以下，進(jìn)一步說明這兩種算法的節(jié)點(diǎn)度過低.且算法LMST、GG和RNG的最小節(jié)點(diǎn)度均可以取值為1，表明這三種算法均是1-容錯(cuò)的.當(dāng)算法中的某條鏈路斷裂時(shí)，其他節(jié)點(diǎn)不能繼續(xù)維持網(wǎng)絡(luò)的連通性，因此網(wǎng)絡(luò)的容錯(cuò)性較差.
圖11 不同算法的性能比較（（a）平均節(jié)點(diǎn)度的比較；（b）平均傳輸半徑的比較；（c）最大節(jié)點(diǎn)度的比較；（d）最小節(jié)點(diǎn)度的比較）Fig.11 The performance comparison of different algorithms（（a）The comparison of average node degree；（b）The comparison of average transmission radius；（c）The comparison of maximum node degree；（d）The comparison of minimum node degree）
綜上所述，MRTc算法在保證網(wǎng)絡(luò)覆蓋性與連通性的同時(shí)，能夠限制網(wǎng)絡(luò)平均節(jié)點(diǎn)度從而降低了網(wǎng)絡(luò)MAC層干擾，并有效地增強(qiáng)了網(wǎng)絡(luò)的魯棒性能，降低了網(wǎng)絡(luò)能耗.另外，該算法具有較強(qiáng)的穩(wěn)定性.然而，此算法也存在不足之處，即當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)密度相同時(shí)，與LMST算法和RNG算法相比，MRTc算法的平均傳輸半徑較大，這表示由MRTc算法優(yōu)化得到的拓?fù)浣Y(jié)構(gòu)中存在部分較長鏈路.
針對(duì)該問題，我們提出下一步的研究方向即為尋找合適的方法，在保證網(wǎng)絡(luò)2-容錯(cuò)性能的前提下，刪除拓?fù)渲休^長鏈路.
5.4實(shí)驗(yàn)4睡眠調(diào)度前后能耗比較
節(jié)約能耗是網(wǎng)絡(luò)拓?fù)淇刂频氖滓繕?biāo)，網(wǎng)絡(luò)中節(jié)點(diǎn)存在休眠和活動(dòng)兩種狀態(tài).本實(shí)驗(yàn)使用最小剛性拓?fù)洌⒁钥偰芎暮痛婊罟?jié)點(diǎn)比例為指標(biāo)，全面深入地比較了網(wǎng)絡(luò)睡眠調(diào)度前、后的能量消耗情況.
計(jì)算睡眠調(diào)度前、后總能耗與活動(dòng)節(jié)點(diǎn)比例實(shí)驗(yàn)的設(shè)置場景如下：假設(shè)70個(gè)傳感器節(jié)點(diǎn)隨機(jī)部署于100×100的方形監(jiān)測區(qū)域內(nèi).每個(gè)節(jié)點(diǎn)擁有相同的初始能量E0=1kJ，且能量無法得到補(bǔ)充.假設(shè)數(shù)據(jù)包的長度為50Bytes，發(fā)射電路和接收電路的能量消耗Eelec=50nJ/bit，自由空間傳輸模型系數(shù)εfs=10pJ/bit/m2.實(shí)驗(yàn)中采用洪泛式路由，當(dāng)數(shù)據(jù)包個(gè)數(shù)變化時(shí)，睡眠調(diào)度前、后最小剛性拓?fù)涞目偰芎囊约盎顒?dòng)節(jié)點(diǎn)比例如圖12（a）和（b）所示.
由圖12（a）和（b）可知，最小剛性拓?fù)湓诮?jīng)由睡眠調(diào)度后，均能降低網(wǎng)絡(luò)的總能耗，提高網(wǎng)絡(luò)中存活節(jié)點(diǎn)的比例.因此，使用基于Voronoi覆蓋的睡眠調(diào)度算法后可有效降低網(wǎng)絡(luò)能耗.
圖12 睡眠調(diào)度前后最小剛性拓?fù)湫阅埽ǎ╝）睡眠調(diào)度前后最小剛性拓?fù)淇偰芎模唬╞）睡眠調(diào)度前后最小剛性拓?fù)浯婊罟?jié)點(diǎn)）Fig.12 The performances of minimum rigid topology before and after sleep scheduling（（a）Total energy consumption of the minimum rigid topology before and after sleep scheduling；（b）The proportion of survival nodes before and after sleep scheduling in minimum rigid topology）
6 結(jié)論
本文提出了一個(gè)基于Voronoi覆蓋與Delaunay三角剖分圖的最小剛性拓?fù)淇刂扑惴?，該算法采用睡眠調(diào)度與功率控制相結(jié)合的方案來降低網(wǎng)絡(luò)能耗.算法中，無線傳感器網(wǎng)絡(luò)通過睡眠調(diào)度在保證監(jiān)測區(qū)域全覆蓋的同時(shí)，可將覆蓋冗余節(jié)點(diǎn)調(diào)整為休眠狀態(tài).進(jìn)一步地，算法在剩余活動(dòng)節(jié)點(diǎn)之間，構(gòu)建基于Delaunay三角剖分圖的最小剛性拓?fù)浣Y(jié)構(gòu).這一方法有效限制了平均節(jié)點(diǎn)度，即網(wǎng)絡(luò)平均節(jié)點(diǎn)度不大于4，且所生成的鏈路數(shù)量滿足稀疏性要求.經(jīng)過MRTc算法優(yōu)化后的網(wǎng)絡(luò)拓?fù)涫?-容錯(cuò)的，提高了網(wǎng)絡(luò)的容錯(cuò)性.
未來工作可進(jìn)一步研究Delaunay三角剖分圖的性能對(duì)算法的影響，進(jìn)而研究該拓?fù)湓诋悩?gòu)網(wǎng)絡(luò)中的構(gòu)建問題；另外，尋找合適的方法，在保證網(wǎng)絡(luò)2-容錯(cuò)性能的前提下，刪除拓?fù)渲休^長鏈路.
References
1 Gui J S，Liu A F.A new distributed topology control algorithm based on optimization of delay and energy in wireless networks.Journal of Parallel and Distributed Computing，2012，72（8）:1032-1044
2 Hong Zhen，Yu Li，Zhang Gui-Jun，Chen You-Rong.Topology construction based on minimum connected dominating set for wireless sensor networks.Journal of Electronics& Information Technology，2012，34（8）:2000-2006（洪榛，俞立，張貴軍，陳友榮.基于最小連通支配集的無線傳感網(wǎng)拓?fù)錁?gòu)建研究.電子與信息學(xué)報(bào)，2012，34（8）:2000-2006）
3 Zhang Y M，He S，Chen J.Data gathering optimization by dynamic sensing and routing in rechargeable sensor networks.In:Proceedings of the 10th Annual IEEE Communications Society Conference on Sensor，Mesh and Ad Hoc Communications and Networks（SECON）.New Orleans，LA:IEEE，2013.273-281
4 Kang Yi-Mei，Li Zhi-Jun，Hu Jiang，Dong Ji-Chang.A lowpower hierarchical wireless sensor network topology control algorithm.Acta Automatica Sinica，2010，36（4）:543-549（康一梅，李志軍，胡江，董吉昌.一種低能耗層次型無線傳感器網(wǎng)絡(luò)拓?fù)淇刂扑惴?自動(dòng)化學(xué)報(bào)，2010，36（4）:543-549）
5 Luo Xiao-Yuan，Yan Yan-Lin，Hao Li-Juan，Li Shao-Bao，Guan Xin-Ping.Based on optimally rigid graph energy efficient distributed topology control algorithm.Journal on Communications，2013，34（12）:1-10（羅小元，閆彥霖，郝麗娟，李紹寶，關(guān)新平.基于最優(yōu)剛性圖的能量有效分布式拓?fù)淇刂扑惴?通信學(xué)報(bào)，2013，34（12）:1-10）
6 Yu C S，Lee B，Youn H Y.Energy efficient routing protocols for mobile ad hoc networks.Wireless Communications and Mobile Computing，2003，3（8）:959-973
7 Li L，Halpern J Y，Bahl P，Wang Y M，Wattenhofer R.A cone-based distributed topology-control algorithm for wireless multi-hop networks.IEEE/ACM Transactions on Networking，2005，13（1）:147-159
8 Chen B J，Jamieson K，Balakrishnan H，Morris R.Span:an energy-efficient coordination algorithm for topology maintenance in ad hoc wireless networks.Wireless Networks，2002，8（5）:481-494
9 Berman P，Calinescu G，Shah C，Zelikovsky A A.Efficient energy management in sensor networks.Ad Hoc and Sensor Networks，Wireless Networks and Mobile Computing.New York:Nova Science Publishers，2005.71-90
10 Li N，Hou J C，Sha L.Design and analysis of an MST-based topology control algorithm.IEEE Transactions on Wireless Communications，2005，4（3）:1195-1206
11 Shang D，Zhang B，Yao Z，Li C.An energy efficient localized topology control algorithm for wireless multihop networks.Journal of Communications and Networks，2014，16（4）:371-377
12 Wang Y，Li X Y.Localized construction of bounded degree and planar spanner for wireless ad hoc networks.Mobile Networks and Applications，2006，11（2）:161-175
13 Xu Y，Heidemann J，Estrin D.Geography-informed energy conservation for ad hoc routing.In:Proceedings of the 7th Annual International Conference on Mobile Computing and Networking.Rome，Italy:ACM，2001.70-84
14 Su Jin-Shu，Guo Wen-Zhong，Yu Zhao-Long，Chen Guo-Long.Fault-toleranceclusteringalgorithmwithloadbalance aware in wireless sensor network.Chinese Journal of Computers，2014，37（2）:445-456（蘇金樹，郭文忠，余朝龍，陳國龍.負(fù)載均衡感知的無線傳感器網(wǎng)絡(luò)容錯(cuò)分簇算法.計(jì)算機(jī)學(xué)報(bào)，2014，37（2）:445-456）
15 Li N，Hou J C.Localized fault-tolerant topology control in wireless ad hoc networks.IEEE Transactions on Parallel and Distributed Systems，2006，17（4）:307-320
16 Luo X Y，Yan Y L，Li S B，Guan X P.Topology control based on optimally rigid graph in wireless sensor networks. Computer Networks，2013，57（4）:1037-1047
18 Luo Xiao-Yuan，Shao Shi-Kai，Guan Xin-Ping，Zhao Yuan-Jie.Dynamic generation and control of optimally persistent formation for multi-agent systems.Acta Automatica Sinica，2013，39（9）:1431-1438（羅小元，邵士凱，關(guān)新平，趙淵潔.多智能體最優(yōu)持久編隊(duì)動(dòng)態(tài)生成與控制.自動(dòng)化學(xué)報(bào)，2013，39（9）:1431-1438）
19 Luo Xiao-Yuan，Yang Fan，Li Shao-Bao，Guan Xin-Ping. Generation of optimally persistent formation for multi-agent systems.Acta Automatica Sinica，2014，40（7）:1311-1319（羅小元，楊帆，李紹寶，關(guān)新平.多智能體系統(tǒng)的最優(yōu)持久編隊(duì)生成策略.自動(dòng)化學(xué)報(bào)，2014，40（7）:1311-1319）
20 Dong Jian，Peng Ren-Can，Zheng Yi-Dong.An improved algorithm of point-by-point interpolation by using local dynamic optimal Delaunay triangulation network.Geomatics and Information Science of Wuhan University，2013，38（5）: 613-617（董箭，彭認(rèn)燦，鄭義東.利用局部動(dòng)態(tài)最優(yōu)Delaunay三角網(wǎng)改進(jìn)逐點(diǎn)內(nèi)插算法.武漢大學(xué)學(xué)報(bào):信息科學(xué)版，2013，38（5）:613-617）
21 Wang Chao-Rui.Graph Theory（3rd Edition）.Beijing:Beijing Institute of Technology Press，2005.15（王朝瑞.圖論（第3版）.北京:北京理工大學(xué)出版社，2005.15）
22 Tian D，Georganas N D.A coverage-preserving node scheduling scheme for large wireless sensor networks.In: Proceedings of the 1st ACM International Workshop on Wireless Sensor Networks and Applications.Atlanta，Georgia，USA:ACM，2002.32-41
23 Xing G L，Wang X R，Zhang Y F，Lu C Y，Pless R，Gill C. Integrated coverage and connectivity configuration for energy conservation in sensor networks.ACM Transactions on Sensor Networks，2005，1（1）:36-72
薛 亮河北工程大學(xué)信息與電氣工程學(xué)院副教授.主要研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)，認(rèn)知無線網(wǎng)絡(luò)技術(shù).
E-mail:lxue@ysu.edu.cn
（XUE LiangAssociate professor at the School of Information and Electrical Engineering，Hebei University of Engineering.His research interest covers wireless sensor networks and cognitive radio networks.）
陳晰河北工程大學(xué)碩士研究生.主要研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)技術(shù).本文通信作者.
E-mail:cx3768255@hotmail.com
（CHEN XiMaster student at Hebei University of Engineering.Her research interest covers wireless sensor networks. Corresponding author of this paper.）
趙繼軍河北工程大學(xué)信息與電氣工程學(xué)院教授.主要研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)，寬帶通信網(wǎng).
E-mail:zjijun@hebeu.edu.cn
（ZHAOJi-JunProfessor at the School of Information and Electrical Engineering，Hebei University of Engineering.His research interest covers wireless sensor networks and broadband communication network.）
黎作鵬河北工程大學(xué)信息與電氣工程學(xué)院講師.主要研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)，物聯(lián)網(wǎng)技術(shù)，納米網(wǎng)絡(luò).
E-mail:lizuopeng@hebeu.edu.cn
（LIZuo-PengLectureratthe School of Information and electrical Engineering，Hebei University of Engineering.His research interest covers wireless sensor networks，internet of things，and nanonetworks.）
關(guān)新平上海交通大學(xué)電子信息與電氣工程學(xué)院教授.主要研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)，認(rèn)知無線電等通信網(wǎng)絡(luò)的控制，復(fù)雜網(wǎng)絡(luò)動(dòng)態(tài)系統(tǒng)的性能分析與控制，非線性時(shí)滯系統(tǒng)的拓?fù)淇刂?，網(wǎng)絡(luò)化控制系統(tǒng)設(shè)計(jì).
E-mail:xpguan@sjtu.edu.cn
（GUAN Xin-PingProfessor at the School of Electronic Information and Electrical Engineering，Shanghai Jiao Tong University.His research interest covers wireless sensor networks，cognitive radio communication network in the control，analysis and control of complex dynamic network system，topology control of nonlinear time-delay systems，and networked control system design.）
A Minimal Rigid Topology Control Algorithm Based on Voronoi Coverage and Delaunay Triangulation in Wireless Sensor Networks
XUE Liang1，2CHEN Xi1ZHAO Ji-Jun1，2LI Zuo-Peng1GUAN Xin-Ping3
This paper proposes a minimal rigid network topology control algorithm called minimal rigid topology control（MRTc），which is based on Voronoi coverage and Delaunay triangulation，to meet application needs of good coverage and for energy saving.MRTc can accurately control node operative modes by which the target sensing area can be completely covered only with active nodes.On the basis of complete coverage，MRTc constructs a topology that is applicable to wireless sensor networks by exploiting the characteristics of Delaunay triangulation.The topology structure can effectively restrict the average node degree，and the structure is characterized by its fault-tolerance，spread ability，and sparsity.Furthermore，MRTc also introduces a power control strategy to minimize the energy consumption of sensor nodes without losing complete coverage in the sensing area.Simulation results are provided to validate this proposal.
Wireless sensor networks（WSNs），topology control，minimal rigid，Voronoi coverage，Delaunay triangulation CitationXue Liang，Chen Xi，Zhao Ji-Jun，Li Zuo-Peng，Guan Xin-Ping.A minimal rigid topology control algorithm based on Voronoi coverage and Delaunay triangulation in wireless sensor networks，2016，42（10）:1570-1584
Manuscript October 26，2015；accepted March 3，2016
10.16383/j.aas.2016.c150702
2015-10-26錄用日期2016-03-03
國家自然科學(xué)基金（61304131，61402147），河北省自然科學(xué)基金（F2016402054，F(xiàn)2014402075），河北省教育廳科學(xué)研究計(jì)劃（BJ2014019，ZD2015087，QN2015046）資助
Supported by National Natural Science Foundation of China（61304131，61402147），Natural Science Foundation of Hebei Province（F2016402054，F(xiàn)2014402075），andtheScientific ResearchPlanProjectsofHebeiEducationDepartment（BJ2014019，ZD2015087，QN2015046）
本文責(zé)任編委趙千川
Recommended by Associate Editor ZHAO Qian-Chuan
1.河北工程大學(xué)信息與電氣工程學(xué)院邯鄲0560382.邯鄲市光纖通信與寬帶接入技術(shù)重點(diǎn)實(shí)驗(yàn)室邯鄲0560383.上海交通大學(xué)系統(tǒng)控制與信息處理教育部重點(diǎn)實(shí)驗(yàn)室上海200240
1.School of Information and Electrical Engineering，Hebei University of Engineering，Handan 0560382.Handan Key Laboratory of Optical Fiber Communication and Broadband Access Technologies，Handan 0560383.System Control and Information Processing Key Laboratory of Ministry of Education，Shanghai Jiao Tong University，Shanghai 200240
猜你喜歡
紡織科學(xué)研究(2023年9期)2023-10-23 11:18:10
昆鋼科技(2022年2期)2022-07-08 06:36:14
當(dāng)代陜西(2022年5期)2022-04-19 12:10:46
當(dāng)代水產(chǎn)(2021年10期)2022-01-12 06:20:28
移動(dòng)通信(2021年5期)2021-10-25 11:41:48
建材發(fā)展導(dǎo)向(2021年23期)2021-03-08 01:05:38
河南科學(xué)(2020年3期)2020-06-02 08:30:10
金融法苑(2018年2期)2018-12-07 00:59:52
華人時(shí)刊(2018年15期)2018-11-10 03:25:26
中國交通信息化(2014年3期)2014-06-05 03:07:09
