薛亮　陳晰　趙繼軍　黎作鵬　關新平

無線傳感器網(wǎng)絡中基于Voronoi覆蓋及Delaunay三角剖分圖的最小剛性拓撲控制算法

薛亮1，2陳晰1趙繼軍1，2黎作鵬1關新平3

為同時滿足覆蓋與節(jié)能應用需求，本文提出了無線傳感器網(wǎng)絡中一種最小剛性拓撲控制算法MRTc（Minimal rigid topology control algorithm based on Voronoi coverage and Delaunay triangulation）.該算法基于Voronoi覆蓋機制，準確控制節(jié)點工作狀態(tài)，實現(xiàn)活動節(jié)點對目標區(qū)域的完全覆蓋.在此基礎上，MRTc利用Delaunay三角剖分圖的特點，構建出適用于無線傳感器網(wǎng)絡的最小剛性拓撲結構.該結構有效約束了網(wǎng)絡平均節(jié)點度，且同時具有容錯性、覆蓋性和稀疏性.此外，MRTc引入節(jié)點功率控制策略，在維持網(wǎng)絡完全覆蓋的基礎上最小化節(jié)點能耗.仿真結果進一步驗證了本文提出的MRTc算法的有效性.

無線傳感器網(wǎng)絡，拓撲控制，最小剛性，Voronoi覆蓋，Delaunay三角剖分圖

引用格式薛亮，陳晰，趙繼軍，黎作鵬，關新平.無線傳感器網(wǎng)絡中基于Voronoi覆蓋及Delaunay三角剖分圖的最小剛性拓撲控制算法.自動化學報，2016，42（10）:1570-1584

降低網(wǎng)絡能耗、限制網(wǎng)絡平均節(jié)點度以及提高網(wǎng)絡容錯性是無線傳感器網(wǎng)絡（Wireless sensor networks，WSNs）中的重要問題，而拓撲控制算法的主要任務是在滿足網(wǎng)絡連通性和覆蓋性的前提下，使得網(wǎng)絡中各個節(jié)點依據(jù)給定的規(guī)則從它的物理鄰居節(jié)點間選取合適的邏輯鄰居節(jié)點，形成一個優(yōu)化的網(wǎng)絡結構，以達到降低網(wǎng)絡能耗［1-4］，限制平均節(jié)點度，提高網(wǎng)絡容錯性的目的.

降低網(wǎng)絡能耗是能量受限網(wǎng)絡協(xié)議設計的首要目標.由于傳感器節(jié)點的體積限制，其可用能量必然有限［5］，因此，對于能量受限的無線傳感器網(wǎng)絡來說降低網(wǎng)絡能耗是構建拓撲結構需要考慮的首要因素.目前，拓撲控制技術中主要有兩種節(jié)能策略：1）通過調節(jié)網(wǎng)絡中各節(jié)點的傳輸功率實現(xiàn)降低網(wǎng)絡能耗的目的；2）是將網(wǎng)絡中部分節(jié)點調節(jié)為休眠狀態(tài)以達到降低網(wǎng)絡能耗的目標.本文為進一步降低網(wǎng)絡能耗，采用睡眠調度與功率控制方案，以更好地實現(xiàn)節(jié)能降耗目標.

有效限制平均節(jié)點度是拓撲控制技術中的另一個重要設計指標.網(wǎng)絡節(jié)點度是指與該節(jié)點存在直接通信鏈路的一跳鄰居節(jié)點的數(shù)目.在無線傳感器網(wǎng)絡中，高的網(wǎng)絡平均節(jié)點度需要在MAC（Media access control）層設計相應的接入訪問控制機制，節(jié)點度過高時還可能引發(fā)訪問沖突和數(shù)據(jù)碰撞，浪費節(jié)點有限的能量.因此，密集部署的無線傳感器網(wǎng)絡中，限制網(wǎng)絡的平均節(jié)點度是十分必要的.

網(wǎng)絡的容錯性能是拓撲構建過程中需要考慮的另一個重要指標.無線傳感器網(wǎng)絡經(jīng)常部署于惡劣的環(huán)境中，一旦網(wǎng)絡中某個節(jié)點遭到破壞或能量耗盡，將可能導致整個網(wǎng)絡癱瘓以致其不能正常運行.因此，在拓撲控制算法的設計中需要考慮網(wǎng)絡的容錯性.

基于上述設計目標，本文提出了一個基于Voronoi覆蓋及 Delaunay三角剖分圖的無線傳感器網(wǎng)絡最小剛性拓撲控制算法（Minimal rigid topology control algorithm based on Voronoi coverage and Delaunay triangulation，MRTc），該算法基于Voronoi原理調節(jié)節(jié)點的活動狀態(tài)，實現(xiàn)了目標區(qū)域的全覆蓋，在此基礎上基于Delaunay三角剖分圖構建了最小剛性拓撲結構.本文的主要貢獻為：1）采用睡眠調度與功率控制相結合的方法，在保持網(wǎng)絡連通的情況下進一步降低網(wǎng)絡能耗；2）提出定理，為構建基于Delaunay三角剖分圖的最小剛性拓撲提供了理論依據(jù)；3）充分利用最小剛性拓撲的特性，即2-容錯、稀疏性以及平均節(jié)點度有限等特點，實現(xiàn)了提高網(wǎng)絡魯棒性、簡化路由計算、降低節(jié)點間干擾的目標.

1　相關工作

作為無線傳感器網(wǎng)絡的基礎技術，拓撲控制技術已引起學者的廣泛關注［6-15］.通過拓撲控制，可以有效降低網(wǎng)絡能耗、限制節(jié)點度以及提高網(wǎng)絡的容錯性.

降低網(wǎng)絡能耗是拓撲控制算法需要首先考慮的設計目標.近幾年來，研究人員提出了多種面向節(jié)能應用的拓撲控制算法［6-9］，其節(jié)能方案主要有功率控制和睡眠調度兩種.對于功率控制而言，其主要思想為通過調節(jié)網(wǎng)絡中所有節(jié)點的功率來降低網(wǎng)絡能耗.例如文獻［6］中的COMPOW（Smallest common power）算法和文獻［7］中的CBTC（Conebased distributed topology-control）算法.COMPOW算法中所有節(jié)點采用能夠保持整個網(wǎng)絡連通的最小功率，統(tǒng)一的功率設置確保了網(wǎng)絡中鏈路的雙向連通性，且功率的最小化達到了降低網(wǎng)路能耗的目的.CBTC算法中每個節(jié)點則通過調整各自的傳輸功率，使得以該節(jié)點為中心，當在任意角度α（α≤5π/6）的扇形區(qū)域內至少存在一個鄰居節(jié)點時，能夠保持網(wǎng)絡的連通性，降低網(wǎng)絡能耗.在睡眠調度方面，Chen等［8］提出的Span算法其基本思想是：在維持網(wǎng)絡連通性的前提下，網(wǎng)絡中每個節(jié)點根據(jù)其剩余能量、鄰居節(jié)點個數(shù)以及節(jié)點效用等多種因素，自適應地判定該節(jié)點成為骨干節(jié)點或休眠節(jié)點.對于MSNL（Maximization of sensor network life）算法［9］而言，節(jié)點狀態(tài)可細分為活動、休眠以及過渡狀態(tài).處于過渡狀態(tài)的節(jié)點將進行實時監(jiān)測，且當其發(fā)現(xiàn)自身的監(jiān)測區(qū)域不能被其余處于活動狀態(tài)或過渡狀態(tài)的節(jié)點覆蓋時，此過渡狀態(tài)節(jié)點轉化為活動狀態(tài).上述4種算法均采用睡眠調度或功率控制中的一種方案面向節(jié)能設計而缺乏對多種方法的結合的運用.本文針對上述弊端，提出了基于Voronoi覆蓋的睡眠調度與功率控制相結合的方案，進一步降低網(wǎng)絡能耗.

作為拓撲控制技術的重要設計目標之一，節(jié)點度的限制問題已成為國內外學者的研究熱點.文獻［10］中，Li等提出了LMST（Local minimum spanning tree）算法，算法中節(jié)點相互獨立地構建局部最小生成樹，并根據(jù)鄰近圖中與之距離最遠的邏輯鄰居節(jié)點確定自身功率.此外，文獻中證明了LMST算法中每個節(jié)點的節(jié)點度均不大于6，網(wǎng)絡的平均節(jié)點度接近于最小生成樹算法，略高于2，可見該算法限制了網(wǎng)絡的平均節(jié)點度.在LMST算法基礎上，文獻［11］通過定義每條鏈路的臨界能耗，提出一種基于LMST的改進算法X-LMST.它旨在以鏈路的能量有效性為指標，構建局部最小生成樹，網(wǎng)絡中節(jié)點的度數(shù)不多于6.LMST算法和X-LMST算法雖然限制了網(wǎng)絡平均節(jié)點度，但是這兩個算法均是1-容錯的，如果網(wǎng)絡中的某條鏈路因節(jié)點能量耗盡或環(huán)境干擾而意外中斷，將會導致網(wǎng)絡失效.Delaunay三角剖分圖和UDG（Unit disk graph）圖相結合，刪除Delaunay三角剖分圖中不能相互通信的鏈路，構建出Udel拓撲結構［12］，該拓撲是t-支撐的，并且經(jīng)Udel算法優(yōu)化后得到的拓撲結構的平均節(jié)點度不高于6.然而，該拓撲結構是集中式拓撲，需要已知網(wǎng)絡的全局信息.

容錯性是拓撲控制技術的另一重要設計目標.目前，已有較多文獻關注網(wǎng)絡容錯性能的研究.文獻［13］中Xu等提出了一個典型的睡眠調度算法GAF（Geographical adaptive fidelity），它以劃分網(wǎng)格的方式將節(jié)點分組，通過睡眠調度的方法使每個網(wǎng)格中僅保留一個活動節(jié)點，網(wǎng)格內其余節(jié)點則調節(jié)為休眠狀態(tài)，以降低網(wǎng)絡能量消耗.理論上，GAF算法是4-容錯的，有著良好的容錯性能.但是，GAF算法中節(jié)點的平均度數(shù)較大.過高的節(jié)點度會在節(jié)點間引發(fā)較嚴重的干擾和沖突，嚴重時引起數(shù)據(jù)包重傳，造成不必要的能量浪費.蘇金樹等［14］提出了一種容錯算法，該算法在局部最小生成樹（LMST）的基礎上，通過增添鏈路的方式減少網(wǎng)絡拓撲結構中的割邊和割點的數(shù)目，構建了一個2-容錯的拓撲結構.實驗證明，該拓撲具有一定的網(wǎng)絡容錯性能.然而，該算法在刪除拓撲的割邊和割點時，需要已知網(wǎng)絡的全局信息，增加了算法的計算復雜度.文獻［15］中提出的FGSSk（Fault-tolerant global spanning subgraph）算法是Kruskal最小生成樹算法在k-容錯的網(wǎng)絡中的推廣，它是一個集中式的拓撲控制算法.此算法通過插入較短鏈路的方式構建了一個k-容錯的拓撲結構，由于該算法是集中式算法，網(wǎng)絡中所有節(jié)點均需了解全局信息，因此，該算法的計算量較大.

針對上述算法的局限性，本文綜合考慮了網(wǎng)絡能耗、平均節(jié)點度以及容錯性三方面內容，提出了基于Voronoi覆蓋及Delaunay三角剖分圖的無線傳感器網(wǎng)絡最小剛性拓撲控制算法.該算法首先依據(jù)Voronoi覆蓋原理，判斷網(wǎng)絡中的覆蓋冗余節(jié)點，在保證網(wǎng)絡區(qū)域全覆蓋的條件下，將其調節(jié)為休眠狀態(tài).然后，在活動節(jié)點間，構建基于Delaunay三角剖分圖的無線傳感器網(wǎng)絡最小剛性拓撲結構.算法中睡眠調度與功率控制相結合，在保持網(wǎng)絡連通性的情況下，進一步降低網(wǎng)絡能耗.文中所提出的定理對于構建具有2-容錯、稀疏性的網(wǎng)絡拓撲結構，提高網(wǎng)絡魯棒性，有效約束平均節(jié)點度，提供了理論依據(jù)和基礎.文中第4節(jié)分析證明了MRTc算法的性能；算法性能評估與結果分析在第5節(jié)給出.

2　網(wǎng)絡模型與定義

2.1網(wǎng)絡模型

在二維空間中，無線傳感器網(wǎng)絡可用一個無向圖（Undirected graph）Gu（Vu，εu）來表示.其中，Vu=｛1，2，···，n｝表示無線傳感器網(wǎng)絡中節(jié)點的集合；εu=｛（lu）ji，i∈Vu，j∈Vu｝為網(wǎng)絡中節(jié)點間可相互通信的鏈路集.在同構網(wǎng)絡中，如果兩個節(jié)點i和j的歐氏距離滿足（其中，rc為節(jié)點的通信半徑），則稱節(jié)點i與j互為通信鄰居［16］.若兩節(jié)點可相互通信，鏈路本文中，Ni為節(jié)點i的通信鄰居的集合，集合Ni中的元素個數(shù)（集合Ni的勢）定義為節(jié)點i的度Di（Di=|Ni|，也可簡稱為i的節(jié)點度）.網(wǎng)絡中所有節(jié)點的度的平均值Dev稱為網(wǎng)絡平均節(jié)點度

為了方便后文分析，給出以下常用定義.

定義2（稀疏性）［5］.網(wǎng)絡拓撲生成后，若拓撲中的鏈路數(shù)目與節(jié)點數(shù)目滿足線性關系，則稱該網(wǎng)絡拓撲具有稀疏性.

定義3（區(qū)域完全覆蓋）.如果監(jiān)測區(qū)域內的任意一點均能夠被至少一個活動節(jié)點成功感知，則稱該監(jiān)測區(qū)域被完全覆蓋.

本文假設無線傳感器網(wǎng)絡是同構網(wǎng)絡，即網(wǎng)絡中所有節(jié)點的屬性相同，且節(jié)點的位置信息已知.節(jié)點的通信范圍和覆蓋范圍（也稱感知區(qū)域）可以看作以節(jié)點為中心，分別以通信半徑rc和感知半徑rs為半徑的圓盤，并且網(wǎng)絡中每個節(jié)點具有唯一的身份標識ID.

此外，我們引入一種常用于無線傳感器網(wǎng)絡中的無線傳輸能量消耗模型［16］.在該模型中，節(jié)點的工作能耗由發(fā)送器能耗和放大器能耗兩部分構成，接收能耗為接收器能耗.網(wǎng)絡節(jié)點的發(fā)射消耗與傳輸距離d有關.因此，節(jié)點傳輸k bits的信息所需的發(fā)射能耗為

接收k bits信息的接收能耗為

其中，Eelec為發(fā)射電路和接收電路的能量消耗，k為傳輸數(shù)據(jù)比特數(shù)，εfs為自由空間傳輸模型系數(shù).

2.2Voronoi覆蓋原理

無線傳感器網(wǎng)絡中，由于大量節(jié)點部署于監(jiān)測區(qū)域內，部分區(qū)域可被多個節(jié)點同時覆蓋，同一監(jiān)測信息也可被多個節(jié)點重復感知，導致大量的冗余感知數(shù)據(jù).針對該問題，本文采用Voronoi覆蓋方案，將網(wǎng)絡中的覆蓋冗余節(jié)點調整為休眠狀態(tài)，在保證網(wǎng)絡區(qū)域完全覆蓋的前提下降低網(wǎng)絡能耗.為了清楚地闡述Voronoi覆蓋原理，給出以下定義4～定義7.

定義4（感應鄰居）.在網(wǎng)絡中，如果一個節(jié)點i的感知區(qū)域和另外一個節(jié)點j的感知區(qū)域相交（i/=j），則稱這兩個節(jié)點i，j互為感應鄰居.

定義5（Voronoi鄰居）.在二維無線傳感器網(wǎng)絡中，如果節(jié)點i所形成的Voronoi多邊形與節(jié)點j所形成的Voronoi多邊形共邊，則稱節(jié)點i和節(jié)點j互為Voronoi鄰居.

定義6（2-Voronoi圖）.在網(wǎng)絡拓撲中，如果去掉節(jié)點i后，由i的Voronoi鄰居構成的Voronoi圖稱為節(jié)點i的2-Voronoi圖.節(jié)點i的2-Voronoi圖的頂點稱為2-Voronoi頂點，記為節(jié)點i的 2-Voronoi圖的邊與節(jié)點i自身覆蓋圓盤邊界的交點，稱為2-Voronoi交點，記為

舉例而言，圖1為節(jié)點i的2-Voronoi圖.其中，節(jié)點j，k，m，n均為節(jié)點i的Voronoi鄰居節(jié)點.由圖1可知，節(jié)點i的2-Voronoi頂點有兩個，分別為和節(jié)點i的2-Voronoi交點有4個，它們分別為和

圖1　節(jié)點i的2-Voronoi圖Fig.1　The 2-Voronoi diagram of node i

定義7（冗余節(jié)點）.如果一個節(jié)點的感知區(qū)域被其他節(jié)點完全覆蓋，我們就稱該節(jié)點為冗余節(jié)點.

為了簡化計算，我們使用引理1僅根據(jù)節(jié)點感應鄰居的信息分布式地判斷節(jié)點的冗余性.文獻［17］證明了引理1的復雜度僅為O（NlogN），其中，N為單個節(jié)點的Voronoi鄰居的個數(shù).

引理1［17］.節(jié)點i是一個冗余節(jié)點的充分必要條件是節(jié)點i的2-Voronoi頂點和的2-Voronoi交點均被其Voronoi鄰居覆蓋.

然而，在使用引理1判斷冗余節(jié)點時，如果兩個冗余節(jié)點互為Voronoi鄰居節(jié)點，同時將它們調節(jié)為休眠狀態(tài)后，它們感知區(qū)域的交叉區(qū)域可能不會被完全覆蓋.為了解決該問題，本文將所有冗余節(jié)點看做一個新的無向圖其中，為所有冗余節(jié)點的集合，為互為Voronoi鄰居的冗余節(jié)點間的鏈路集.然后計算圖的最大獨立集1最大獨立集:假設存在一個無向圖Gu（Vu，Eu），如果集合S?Vu且S/=?，若S中任意頂點在圖Gu中邏輯不相鄰則稱集合S為圖Gu的獨立集，如果不存在|S′|＞|S|，則稱集合S為圖Gu的最大獨立集.，最大獨立集中的節(jié)點即為覆蓋區(qū)域的盲節(jié)點.為了保證監(jiān)測區(qū)域的完全覆蓋，將這部分盲節(jié)點調節(jié)為活動狀態(tài)，其余冗余節(jié)點（即覆蓋冗余節(jié)點）進入休眠狀態(tài).

綜上所述，Voronoi覆蓋原理可概括為：每個節(jié)點分布式的收集其感應鄰居的信息后構建局部的Voronoi圖，然后由其Voronoi鄰居構建2-Voronoi圖，并找出所有的2-Voronoi頂點和所有的2-Voronoi交點，并根據(jù)引理1判斷其是否為冗余節(jié)點.最后通過計算圖的最大獨立集找出網(wǎng)絡的盲節(jié)點，將其調節(jié)為活動狀態(tài)，其余冗余節(jié)點維持休眠狀態(tài).此方法可保證在監(jiān)測區(qū)域完全覆蓋的基礎上，減少活動節(jié)點數(shù)量，因此可以進一步降低能耗.

2.3最小剛性拓撲

最小剛性拓撲中每個頂點至少連有兩條鏈路，并且它的鏈路數(shù)與節(jié)點數(shù)滿足線性關系，它滿足無線傳感器網(wǎng)絡2-容錯的特性以及稀疏性.為了構建容錯且稀疏的拓撲結構，本文在活動節(jié)點間構建最小剛性拓撲.如果對網(wǎng)絡拓撲中部分鏈路的長度加以限制，就可以維持整個拓撲構型不變，那么就稱該網(wǎng)絡拓撲是一個剛性拓撲［5］.如果一個拓撲不是剛性的，則稱該拓撲為可變形拓撲.圖2（a）和圖2（b）分別為由4個節(jié)點構成的剛性拓撲與可變形拓撲.由圖2易知，組成剛性拓撲的任意一個節(jié)點至少連有兩條鏈路.

圖2　剛性拓撲和可變形拓撲（（a）剛性拓撲；（b）可變形拓撲；（c）最小剛性拓撲）Fig.2　The rigid topology and flexible topology（（a）Rigid topology；（b）Flexible topology；（c）Minimal rigid topology）

如果刪除一個剛性拓撲中的任意一條鏈路則會影響該拓撲的剛性，我們稱這樣的拓撲為最小剛性拓撲.顯然地，最小剛性拓撲是鏈路數(shù)最少的剛性拓撲［18］.圖2（c）為二維空間中由4個節(jié)點構成的最小剛性拓撲.在二維空間中，給定一個含有n個節(jié)點的拓撲結構G（V，ε（t）），節(jié)點i位置的時變函數(shù)為qi（t）=f（xi（t），yi（t））（其中，i=1，2，···，n）.本文假設每個節(jié)點的位置函數(shù)qi（t）是可微的.如果拓撲中的任意一條鏈路滿足||qi（t）-qj（t）||=c（其中，c為正實數(shù)），則稱該鏈路的移動為剛性移動.在此基礎上，如果該鏈路同時滿足則稱為該拓撲結構的無窮小變形.如果一個拓撲結構的無窮小變形均是由剛性移動引起的，那么則稱該拓撲結構為無窮小剛性拓撲.顯然，無窮小剛性拓撲也是一個剛性拓撲.

本文引入剛性矩陣檢測某個拓撲是否具有剛性，并輔助生成剛性拓撲結構.鏈路集ε中的每一條鏈路，均可用于轉化并對應生成剛性矩陣中的一個行向量.設鏈路集ε中的所有鏈路均可隨機排序，當構建一個剛性矩陣為網(wǎng)絡拓撲中的鏈路數(shù)）時，ε中第k條鏈路對應于剛性矩陣M中第k行元素構成的行向量（如式（4）所示）.

以下引理2和引理3分別描述了剛性矩陣與無窮小剛性拓撲、無窮小剛性拓撲與最小剛性拓撲之間的內在聯(lián)系.

引理2［19］.在二維空間中，假設矩陣M為n個傳感器節(jié)點所構成拓撲的剛性矩陣，該拓撲是無窮小剛性的當且僅當Rank（M）=2n-3.

引理3［5］.由n個傳感器節(jié)點構成的鏈路數(shù)為2n-3的無窮小剛性拓撲是最小剛性拓撲.

以下引理4表明可以分布式地生成最小剛性拓撲.

引理4［16］.一個剛性拓撲G的一個子拓撲G′被其他剛性拓撲G′′替代后，得到一個新拓撲那么新拓撲是剛性的.

2.4Delaunay三角剖分圖

Delaunay三角剖分圖是由Voronoi鄰居節(jié)點相互連接而成的三角形，其外接圓圓心是與該三角形相關的Voronoi圖的一個頂點.圖3為由傳感器節(jié)點構成Voronoi圖與Delaunay三角剖分圖，其中，虛線表示由節(jié)點構成的Voronoi圖，實線表示由這些節(jié)點構成的Delaunay三角剖分圖.以Delaunay三角剖分圖中任意兩個三角形（如圖3中所示的矩形虛線框內的三角形）為例，以下定理1使用數(shù)學歸納法證明由n（n≥3）個節(jié)點構成的Delaunay三角剖分圖至少含有2n-3條鏈路，并且它是剛性的.

圖3　節(jié)點的Voronoi圖以及Delaunay三角剖分圖Fig.3　The Voronoi graph and Delaunay triangulation of nodes

定理1.在無線傳感器網(wǎng)絡中，每個節(jié)點與其n-1（n≥3）個通信鄰居節(jié)點構成的Delaunay三角剖分圖的鏈路數(shù)不小于2n-3，且其是剛性的.

證明.采用數(shù)學歸納法證明由n（n≥3）個傳感器節(jié)點構成的Delaunay三角剖分圖至少含有2n-3條鏈路.假設由n個傳感器節(jié)點構成的Delaunay三角剖分圖的鏈路數(shù)為m.

1）當n=3時，Delaunay三角剖分圖的鏈路數(shù)m=3，滿足鏈路數(shù)不小于2n-3；

2）假設當n=k時，Delaunay三角剖分圖的鏈路數(shù)m≥2k-3；

3）當n=k+1時，根據(jù)生成Delaunay三角剖分圖逐點插入法［20］的原理可知在原來的Delaunay三角剖分圖中任意插入一點Q時，共包含有兩種情況：

a）插入點Q在三角形的內部：如圖4（a）所示，△IJN和△JNM為Delaunay三角剖分圖中相鄰的兩個三角形，如圖4（a）所示，當插入點Q在△IJN的內部時，連接IQ，JQ和NQ，然后逐個對它們進行外接圓檢測.通過交換對角線的方法，保證所形成的圖形（如圖4（a）所示）為Delaunay三角剖分圖.因此，在這種情況下增加一點Q后，形成的Delaunay三角剖分圖增加了三條鏈路，即當n=k+1時，Delaunay三角剖分圖的鏈路數(shù)m′=m+3≥2k-3+3=2k≥2（k+1）-3.

圖4　Delaunay三角剖分圖逐點插入法（（a）插入點Q在△IJN的內部；（b）插入點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）插入點Q在三角形的邊上：如圖4（b）所示，當插入點Q在公共邊JN上時，連接IQ和MQ，并且JN被分成了兩條鏈路JQ和NQ，然后逐個對它們進行外接圓檢測，通過交換對角線的方法來保證所形成的圖形為Delaunay三角剖分圖.因此，在這種情況下增加一點Q后形成的Delaunay三角剖分圖，同樣增加了三條鏈路，即當n=k+1時，Delaunay三角剖分圖的鏈路數(shù)m′=m+3≥2k-3+3=2k≥2（k+1）-3.因此，當n=k+1時，Delaunay三角剖分圖的鏈路數(shù)不小于2n-3.

因此，每個傳感器節(jié)點與其n-1（n≥3）個鄰居節(jié)點構成的Delaunay三角剖分圖的鏈路數(shù)m滿足m≥2n-3.

以上我們證明了每個傳感器節(jié)點與其n-1（n≥3）個鄰居節(jié)點構成的Delaunay三角剖分圖的鏈路數(shù)m滿足m≥2n-3.實際上，Delaunay三角剖分圖是由若干個三角形構成的，根據(jù)引理4可知剛性拓撲G的一個子拓撲G′被其他剛性拓撲G′′替代后，得到一個新拓撲是剛性的，而三角形是一個最簡單的剛性圖，因此由n（n≥3）個傳感器節(jié)點構成的Delaunay剖分圖是剛性的.

綜上所述，由n（n≥3）個傳感器節(jié)點構成的Delaunay剖分圖至少含有2n-3條鏈路，且其是剛性的.

基于定理1，我們給出了以下定理2，為分布式的生成基于Delaunay三角剖分圖的最小剛性拓撲提供了理論依據(jù).

定理2.如果網(wǎng)絡中任意節(jié)點i與其通信鄰居節(jié)點構成基于Delaunay三角剖分圖的最小剛性拓撲記為Gi（i=1，···，n），Gm（Vm，εm）為網(wǎng)絡節(jié)點生成的全局最小剛性拓撲，則有以下結論：

1）若Gi與Gj（i/=j）有公共節(jié)點e和f，如果存在鏈路且那么

2）若Gi與Gj（i/=j）有n個公共節(jié)點，且Gi或Gj中存在由該n個節(jié)點構成的圈2圈:節(jié)點間鏈路首尾相連構成的封閉回路.，如果拓撲Gj中存在m（2m≤n）條鏈路（鏈路的頂點均為公共點）滿足但拓撲Gi中同樣存在m條鏈路（鏈路的頂點均為公共點）與中任意鏈路均不相同）滿足且m條鏈路的權值和大于另外m條鏈路那么，將權值和較小的鏈路代替權值和較大的鏈路后，再刪除滿足條件1）的鏈路，得到的拓撲是最小剛性拓撲.

證明.1）假設Gi與Gj（i/=j）有公共節(jié)點e和f，如果存在且由于最小剛性拓撲是鏈路數(shù)最少的剛性拓撲.因此，連接最小剛性拓撲中任意兩個不存在鏈路的點，得到的拓撲同樣是剛性的，故存在是剛性的.根據(jù)引理4一個剛性拓撲的子拓撲由另外一個剛性拓撲代替得到的拓撲仍然是剛性的.因此，可用Gi替換來保持最終拓撲仍然是剛性的，因此，去掉該鏈路不改變拓撲的剛性特性，即得證.

2）假設Gi與Gj（i/=j）有n個公共節(jié)點，且Gi或Gj中存在由該n個節(jié)點構成的圈，如果拓撲Gj中存在m條鏈路（鏈路的頂點均為公共點）滿足但拓撲Gi中存在m 條鏈路（鏈路的頂點均為公共點）（q=1，···，m）與中任意鏈路均不相同）滿足但由于生成Delaunay三角剖分圖時，在同一個圈內生成三角形的連接鏈路不同，如果直接刪除滿足條件1）的鏈路，即同時刪除和則圈內的剛性不能保證，全局拓撲的剛性也不能保證，因此，則將權值和較小的鏈路代替權值和較大的鏈路后，根據(jù)引理4一個剛性拓撲的子拓撲由另外一個剛性拓撲代替生成的新拓撲是剛性的，由于新拓撲與原拓撲Gi有相同的鏈路，因此拓撲是最小剛性拓撲，然后刪除滿足條件1）的鏈路.用Gij（Vij，εij）表示由拓撲和拓撲Gj（Vj，εj）的公共節(jié)點組成的拓撲，其中，Vij=Vi∩Vj，εij表示兩個頂點均在Vij中的鏈路，因此有令εij=as∪bs1∪bs2，其中，as表示拓撲與Gj的公共鏈路，bs1和bs2分別表示εij中僅存在于和Gj中的鏈路.同時刪除bs1和bs2后，每個子拓撲滿足否則，至少存在一條鏈路使或Gj的鏈路數(shù)超過這與條件或Gj均為最小剛性拓撲相矛盾.假設刪除bs1和bs2后得到的拓撲有超過2|Vi∪Vj|-3的鏈路，則Gij有|εij|＞2|Vij|-3，這將導致在刪除bs1和bs2之前，或Gj的鏈路數(shù)超過2|Vi|-3或2|Vj|-3，這與條件或Gj均為最小剛性拓撲相矛盾，因此，得到的拓撲滿足-3.由上述1）可知刪除bs1和bs2后不改變拓撲的剛性，因此，有因此，刪除bs1和 bs2后有，生成的最終拓撲為最小剛性拓撲.

3　MRTc算法

本節(jié)我們詳細介紹基于Voronoi覆蓋及Delaun -ay三角剖分圖的最小剛性拓撲控制算法MRTc.算法執(zhí)行過程可分為以下4個階段：1）信息收集階段，網(wǎng)絡中各節(jié)點僅根據(jù)其感知鄰居節(jié)點和通信鄰居節(jié)點的信息構建拓撲，可降低網(wǎng)絡中消息傳送數(shù)量；2）權值確定階段，利用權值函數(shù)判定權值大小，保證拓撲結構的唯一性；3）拓撲構建階段，網(wǎng)絡首先分布式確定覆蓋冗余節(jié)點，將其調節(jié)為休眠狀態(tài)，在保證網(wǎng)絡監(jiān)測區(qū)域完全覆蓋的條件下，通過減少活動節(jié)點數(shù)量，降低網(wǎng)絡能耗.然后通過構建基于Delaunay三角剖分圖的最小剛性拓撲結構，提高網(wǎng)絡容錯性，并可限制平均節(jié)點度數(shù)；4）功率調節(jié)階段，為了進一步地降低網(wǎng)絡能耗，將每個節(jié)點的功率調節(jié)為網(wǎng)絡所需要的最小功率.

3.1信息收集

首先，MRTc算法采用與文獻［5］相同的機制實現(xiàn)通信鄰居節(jié)點的收集.通過該機制，網(wǎng)絡中的每個節(jié)點均能獲得其通信鄰居節(jié)點的信息，該信息包含每個通信鄰居節(jié)點的ID、節(jié)點位置坐標以及與其通信鄰居節(jié)點的歐氏距離.通過這些信息，可得知每個節(jié)點的通信鄰居和感應鄰居，也可通過下節(jié)的權值函數(shù)計算該節(jié)點與其通信鄰居節(jié)點的鏈路權值.

3.2權值函數(shù)的確定

無線傳感器網(wǎng)絡中保證兩節(jié)點i，j通信所需要的最小傳輸功率［11］為其中，α和 δ為可調參數(shù)，并且與特定無線通信系統(tǒng)硬件和傳輸環(huán)境有關，通常有2≤α≤4.顯然，傳輸功率隨著兩節(jié)點間距離的增加而增大.因此，本文用兩點間的距離代表這兩點間鏈路的權值.然而，在無線傳感器網(wǎng)絡中，不同節(jié)點間的距離可能相同，這會導致鏈路不同，但卻擁有相同的權值，所生成的最終拓撲結構不唯一.

為了保證生成拓撲的唯一性，本文采用了以下權值函數(shù).當節(jié)點間距離滿足如式（6）～式（8）所示的三個條件之一時，即可得鏈路與的權值函數(shù)滿足

式中，id（i），id（j），id（m），id（n）分別表示節(jié)點i，j，m，n的ID.由于每個節(jié)點的ID是唯一的，因此該權值函數(shù)w保證了擁有最小權值的鏈路具有唯一性，由此可知使用MRTc算法生成的拓撲結構也是唯一的.

3.3拓撲構建

1）冗余節(jié)點選擇與休眠調度

監(jiān)測區(qū)域的良好覆蓋性是傳感器網(wǎng)絡拓撲構建的基本要求之一.由于節(jié)點經(jīng)常采用隨機部署方式，導致部分監(jiān)測區(qū)域可被多個節(jié)點同時覆蓋，由此產生大量冗余感知信息.因此，在保證網(wǎng)絡全覆蓋的前提下，將覆蓋冗余節(jié)點調節(jié)為休眠狀態(tài)，對于降低網(wǎng)絡能耗是必要的.本文第2.2節(jié)中Voronoi覆蓋原理提供了判定覆蓋冗余節(jié)點的理論依據(jù)，它能夠保證在將選出的覆蓋冗余節(jié)點調節(jié)為休眠狀態(tài)后，活動節(jié)點依然能夠保持對監(jiān)測區(qū)域的完全覆蓋.其具體過程如MRTc算法偽代碼中第4～10行偽代碼所示.

2）基于Delaunay三角剖分圖的最小剛性拓撲的構建

為了提高網(wǎng)絡的魯棒性，同時限制網(wǎng)絡的平均節(jié)點度.本節(jié)基于定理2，將覆蓋冗余節(jié)點調節(jié)為休眠狀態(tài)后，在活動節(jié)點間構建了基于Delaunay三角剖分圖的最小剛性拓撲結構.構建該拓撲的步驟如下：

步驟1.每個節(jié)點與其鄰居節(jié)點構建Delaunay三角剖分圖；

步驟2.在Delaunay三角剖分圖的基礎上不損失剛性的前提下刪除較長鏈路構建局部最小剛性拓撲；

步驟3.刪除不屬于全局最小剛性拓撲的鏈路，可構建全局最小剛性拓撲.

3.4功率調節(jié)

算法的最終階段，為了進一步降低網(wǎng)絡能耗，對網(wǎng)絡中活動節(jié)點的功率進行調節(jié).功率調節(jié)時，每個節(jié)點將自身功率設置為能夠覆蓋其全部邏輯鄰居節(jié)點（節(jié)點i的邏輯鄰居節(jié)點即為經(jīng)過MRTc算法優(yōu)化后，仍然與節(jié)點i有通信關系的節(jié)點）所需要的最小功率，即節(jié)點能與距離其最遠的邏輯鄰居節(jié)點成功通信的功率.這意味著可將每個活動節(jié)點的通信半徑設置為與其距離最遠的邏輯鄰居節(jié)點的距離.節(jié)點通信半徑的公式如下所示.

其中，rc（i）為節(jié)點i的通信半徑，為節(jié)點i的邏輯鄰居節(jié)點的集合.

分布式構建基于Voronoi覆蓋與Delaunay三角剖分圖的最小剛拓撲結構的MRTc算法的偽代碼如下所示.

首先，節(jié)點通過信息的收集得到節(jié)點的感應鄰居集合和通信鄰居節(jié)點集合（行1～2）.接著第3行根據(jù)第3.2節(jié)權值函數(shù)確定節(jié)點與通信鄰居節(jié)點的權值.行4～32為拓撲的構建階段，該階段節(jié)點首先根據(jù)覆蓋原理（見第2.2節(jié)Voronoi覆蓋原理）確定網(wǎng)絡中的覆蓋冗余節(jié)點，并將其調節(jié)為休眠狀態(tài)（行4～10）.然后，在活動節(jié)點間構建基于Delaunay三角剖分圖的最小剛性拓撲結構，改善網(wǎng)絡容錯性，有效約束網(wǎng)絡的平均節(jié)點度（行11～32）.算法的最終階段（行33）每個節(jié)點通過調節(jié)其傳輸功率來降低網(wǎng)絡能耗，將功率調節(jié)為能夠覆蓋所有邏輯鄰居節(jié)點的最小功率，（即）.

4　MRTc算法性能分析

MRTc算法使得網(wǎng)絡中的覆蓋冗余節(jié)點調節(jié)為休眠狀態(tài)，并在活動節(jié)點間構建最小剛性拓撲結構，有效降低了網(wǎng)絡能耗，該算法還具有以下4個方面的性質.

性質1.由n個傳感器節(jié)點形成的初始拓撲3初始拓撲:沒有經(jīng)過任何算法優(yōu)化的起始拓撲結構GC（VC，εC），在經(jīng)過MRTc算法優(yōu)化后得到的拓撲結構GD（VD，εD）是2-容錯的.

證明.通過第2.3節(jié)，我們可知構成最小剛性拓撲的任意一個節(jié)點至少連有兩條鏈路，由于初始拓撲GC（VC，εC）經(jīng)過MRTc算法優(yōu)化后，得到的拓撲是最小剛性拓撲.因此，拓撲結構GD（VD，εD）中的任意一個節(jié)點至少連接有兩條鏈路，即拓撲中的任意節(jié)點至少含有兩條鏈路，根據(jù)第2.1節(jié)k-容錯的定義可知，最終生成的拓撲是2-容錯的.

性質2.由n個傳感器節(jié)點形成的初始拓撲GC（VC，εC），在經(jīng)過MRTc算法優(yōu)化后得到的拓撲結構GD（VD，εD）滿足區(qū)域完全覆蓋.

證明.根據(jù)第2.2節(jié)覆蓋冗余節(jié)點的定義可知，如果一個節(jié)點的覆蓋區(qū)域被其他節(jié)點完全覆蓋，則該節(jié)點為覆蓋冗余節(jié)點.經(jīng)算法MRTc優(yōu)化后，這些覆蓋冗余節(jié)點被調節(jié)為休眠狀態(tài)后，它們的覆蓋區(qū)域仍然可以被其他節(jié)點所覆蓋.因此，由n個傳感器形成的初始拓撲GC（VC，εC），在經(jīng)過MRTc算法優(yōu)化后得到的拓撲結構GD（VD，εD）滿足區(qū)域完全覆蓋.

性質3.由n個傳感器節(jié)點形成的初始拓撲GC（VC，εC），在經(jīng)過MRTc算法優(yōu)化后得到的拓撲結構GD（VD，εD）是稀疏的.

證明.根據(jù)第2.1節(jié)網(wǎng)絡稀疏性的定義，可知若拓撲滿足網(wǎng)絡稀疏性要求，需要網(wǎng)絡中的鏈路數(shù)量與節(jié)點數(shù)量之間呈線性關系.又根據(jù)第2.3節(jié)引理3知，由任意n個節(jié)點構成的最小剛性圖有2n-3條鏈路.由于GC（VC，εC）在經(jīng)過MRTc算法優(yōu)化后，得到的拓撲結構GD（VD，εD）是一個最小剛性拓撲，即拓撲GD（VD，εD）中的鏈路數(shù)量和節(jié)點數(shù)量呈線性關系.所以，經(jīng)過MRTc算法優(yōu)化后得到的拓撲結構GD（VD，εD）是稀疏的.

性質4.經(jīng)過MRTc算法優(yōu)化后得到的拓撲結構GD（VD，εD），其平均節(jié)點度不大于4.

證明.由引理3和定理2可知，經(jīng)MRTc算法優(yōu)化后的拓撲結構GD（VD，εD）有2n-3條鏈路.根據(jù)握手定理［21］可知，對于任意拓撲G（V，ε），網(wǎng)絡內節(jié)點度之和為2|ε|，其中|ε|為該拓撲中鏈路的數(shù)目.因此，拓撲結構GD（VD，εD）中所有節(jié)點的節(jié)點度之和為故它的平均節(jié)點度為即拓撲結構GD（VD，εD）的平均網(wǎng)絡節(jié)點度不超過4.

5　MRTc算法性能評價

為了分析和評價MRTc算法的性能，本文在Matlab R2009a環(huán)境中，使用M語言設計了以下4組數(shù)值仿真實驗.實驗1分別在均勻和隨機兩種網(wǎng)絡中驗證睡眠調度方案的性能；實驗2以52個節(jié)點為例詳細介紹了同構網(wǎng)絡拓撲的構建過程；實驗3通過比較4種典型算法，驗證了MRTc算法的性能；實驗4對最小剛性拓撲結構下睡眠調度前后網(wǎng)絡的總能耗以及活動節(jié)點的比例進行了詳細比較.本文所有實驗均假設監(jiān)測區(qū)域為100×100的方形區(qū)域，傳感器節(jié)點的最大感知半徑設為20.監(jiān)測區(qū)域范圍與節(jié)點感知半徑的大小見文獻［22］.節(jié)點的最大通信半徑為40.在均勻網(wǎng)絡中，每個傳感器節(jié)點均位于網(wǎng)格的頂點，網(wǎng)格大小設置為式中n為監(jiān)測區(qū)域內布置的節(jié)點數(shù)目，ra為每個網(wǎng)格的長度值，rb為每個網(wǎng)格的寬度值.

5.1實驗1冗余節(jié)點選擇與休眠調度

降低網(wǎng)絡能耗是拓撲控制的主要設計目標，為了實現(xiàn)該目標，本文采用了睡眠調度方案在保證網(wǎng)絡監(jiān)測區(qū)域全覆蓋的前提下，將覆蓋冗余節(jié)點調節(jié)為休眠狀態(tài).為了驗證睡眠調度方案的性能，本實驗分別在均勻網(wǎng)絡和隨機網(wǎng)絡兩種網(wǎng)絡中進行仿真實驗.圖5和圖6分別為在均勻網(wǎng)絡和隨機網(wǎng)絡中部署70個節(jié)點時，睡眠調度前后的監(jiān)測區(qū)域覆蓋情況.節(jié)點感知半徑均為20.由這4個子圖可以看出在經(jīng)過睡眠調度后，監(jiān)測區(qū)域仍然被活動節(jié)點完全覆蓋滿足性質2.

圖5　均勻網(wǎng)絡睡眠調度（（a）睡眠調度前；（b）睡眠調度后）Fig.5　The sleep scheduling in uniform networks（（a）Before the sleep scheduling；（b）After the sleep scheduling）

圖6　隨機網(wǎng)絡睡眠調度（（a）睡眠調度前；（b）睡眠調度后）Fig.6　The sleep scheduling in random networks（（a）Before the sleep scheduling；（b）After the sleep scheduling）

當節(jié)點數(shù)量分別為49、56、63、70、77時，算法的覆蓋性能如圖7所示，子圖7（a）、7（b）分別為實驗中冗余節(jié)點的數(shù)目和冗余節(jié)點比例.由圖7（a）、7（b）可知，無論在均勻網(wǎng)絡中還是冗余網(wǎng)絡中，冗余節(jié)點的數(shù)目隨著網(wǎng)絡節(jié)點密度的增大而增加，并且冗余節(jié)點的占比也隨之增大.該結果表明對于節(jié)點密度不同的網(wǎng)絡，該算法均可以起到較好的睡眠調度效果.

5.2實驗2網(wǎng)絡拓撲的構建過程

在實驗1的基礎上，我們以52個節(jié)點為例詳細介紹網(wǎng)絡拓撲的構建過程.首先，將52個感知半徑為20的節(jié)點隨機部署在100×100的監(jiān)測區(qū)域內，節(jié)點的分布情況與監(jiān)測區(qū)域的覆蓋情況如圖8（a）所示.根據(jù)Voronoi覆蓋原理選擇覆蓋冗余節(jié)點，并將覆蓋冗余節(jié)點調節(jié)為休眠狀態(tài).活動節(jié)點對監(jiān)測區(qū)域的覆蓋情況如圖8（b）所示.由圖8（b）可以看出，在將部分節(jié)點調節(jié)為休眠節(jié)點后，監(jiān)測區(qū)域內的任意一點仍至少被一個活動節(jié)點覆蓋.可見，經(jīng)過睡眠調度后，網(wǎng)絡滿足完全覆蓋.在此基礎上，每個活動節(jié)點與其鄰居節(jié)點生成局部的Delaunay三角剖分圖，構建局部最小剛性拓撲結構如圖9（a）所示，圖中實線表示兩點間的實際鏈路，虛線表示可以被刪除的鏈路.每個節(jié)點在維持剛性的前提下刪除權重較大的鏈路，與其鄰居節(jié)點構建權重和最小的局部最小剛性拓撲如圖9（b）所示.最后根據(jù)定理2，刪除不屬于全局最小剛性拓撲的鏈路，構建起全局最小剛性拓撲結構，如圖9（c）所示.

由該實驗容易看出，經(jīng)MRTc算法優(yōu)化后的拓撲，即圖9（c）中的任意一個節(jié)點至少連有兩條鏈路.這意味著該拓撲結構是2-容錯的，滿足性質1.圖9（c）與圖9（a）和圖9（b）相比，圖9（c）中的鏈路數(shù)明顯減少，表明經(jīng)MRTc算法優(yōu)化后的拓撲結構，其網(wǎng)絡平均節(jié)點度明顯小于圖9（a）和圖9（b）拓撲的平均節(jié)點度，即由MRTc算法優(yōu)化后的拓撲結構能夠幫助降低網(wǎng)絡MAC層干擾.

5.3實驗3重要性能指標的橫向比較

為了驗證MRTc算法的性能，本實驗選取4種經(jīng)典的拓撲控制算法GG（Gabriel graph）、RNG（Relative neighborhood graph）、LMST、Udel與本文提出的MRTc算法進行比較.首先，實驗對5種算法生成的拓撲結構進行對比.在100×100的區(qū)域內隨機生成30個節(jié)點，在相同的仿真環(huán)境下，使用上述5種算法來構建拓撲結構，并對5種拓撲結構進行比較.實驗中節(jié)點的感知半徑設置為20.當傳感器節(jié)點的感知半徑和通信半徑滿足rc≥2×rs時，如果網(wǎng)絡在給定凸區(qū)域滿足1-覆蓋，則能夠保證網(wǎng)絡的連通性［23］.因此，本文假設網(wǎng)絡節(jié)點的感知半徑和通信半徑滿足rc=2×rs.然后，在相同的仿真環(huán)境中，通過改變傳感器節(jié)點的個數(shù)，使其在30～100的范圍內變動，比較5種不同算法的平均節(jié)點度、平均鏈路長度以及網(wǎng)絡的最大與最小節(jié)點度.通過全面的性能比較，驗證本文提出的MRTc算法的性能.

圖7　兩種網(wǎng)絡中冗余節(jié)點數(shù)目和所占節(jié)點比例的比較（（a）冗余節(jié)點個數(shù)的比較；（b）冗余節(jié)點比例的比較）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　睡眠調度前后區(qū)域覆蓋情況（（a）睡眠調度前區(qū)域覆蓋情況；（b）睡眠調度后區(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)絡拓撲結構對比

在相同的仿真環(huán)境下，比較5種不同的拓撲控制算法GG、RNG、LMST、Udel與MRTc生成的拓撲結構.圖10顯示了由圖9（c）中的30個活動節(jié)點在100×100的區(qū)域內分別使用上述5種方法生成的拓撲結構.由圖10（d）可以看出算法Udel生成的拓撲結構中有67條鏈路，是這5種拓撲結構中鏈路數(shù)最多的.該拓撲結構的平均節(jié)點度也是最大的.此外，Udel算法是一個集中式方法，它需要預先獲知網(wǎng)絡中所有節(jié)點的信息.相比之下，RNG算法（見圖10（b））和LMST算法（圖10（c））是分布式算法，它們的構建過程只需依賴鄰居節(jié)點的信息.由這兩種算法所生成的拓撲中，鏈路數(shù)分別為34和38，平均節(jié)點度過低.過低的節(jié)點度會導致節(jié)點間的通信鏈路過長，網(wǎng)絡能耗隨之增大.而本文算法（圖10（e））和GG算法（圖10（a））的鏈路數(shù)分別為57和52，兩者相差不大.然而，由這兩個子圖容易看出，GG算法擁有的長鏈路數(shù)量較多，這意味著該算法的能耗較大.

圖9　MRTc拓撲結構的構建過程（（a）構建局部Delaunay三角剖分圖；（b）構建局部最小剛性拓撲；（c）構建全局最小剛性拓撲）Fig.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　不同算法生成的拓撲結構（（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）其他重要性能指標比較

在100×100的監(jiān)測區(qū)域內，當節(jié)點數(shù)量由30逐漸遞增時，上述5種算法的平均節(jié)點度、平均傳輸半徑、最大節(jié)點度以及最小節(jié)點度4種性能指標如圖11所示.

網(wǎng)絡的平均節(jié)點度定義為網(wǎng)絡中所有節(jié)點的節(jié)點度之和與節(jié)點數(shù)量的比值.在無線傳感器網(wǎng)絡中，高的平均節(jié)點度需要在MAC層特別設計接入訪問機制，嚴重時還可引發(fā)訪問干擾和數(shù)據(jù)碰撞，造成非必要的網(wǎng)絡能耗.反過來，網(wǎng)絡的平均節(jié)點度過低則會導致節(jié)點間的鏈路過長，通信能耗值也相應地增加.文獻［16］提出網(wǎng)絡的最優(yōu)平均節(jié)點度為6.根據(jù)實驗2網(wǎng)絡拓撲構建過程可知，經(jīng)過MRTc算法優(yōu)化后減少了網(wǎng)絡拓撲的鏈路數(shù).由引理4可知，經(jīng)MRTc算法優(yōu)化后每個節(jié)點的節(jié)點度也會相應地降低.圖11（a）為GG、RNG、LMST、Udel以及MRTc這5種算法在網(wǎng)絡節(jié)點數(shù)目在30～100間變化時，網(wǎng)絡的平均節(jié)點的比較.由性質4知算法MRTc的平均節(jié)點度因此，隨著節(jié)點數(shù)目n的增加，MRTc算法的平均節(jié)點度逐漸增加，且其值接近于4.由圖11（a）知該算法的平均節(jié)點度變化緩慢，說明該算法較穩(wěn)定.相比之下，算法RNG和算法LMST的平均節(jié)點度在3以下，這意味著由這兩種算法生成的拓撲結構過于稀疏.而Udel算法的平均節(jié)點度接近于最優(yōu)值6，這與文獻［12］相符合.

傳輸半徑定義為節(jié)點與其最遠鄰居之間的距離.平均傳輸半徑為網(wǎng)絡中各個節(jié)點的傳輸半徑之和與節(jié)點數(shù)量的比值.網(wǎng)絡中節(jié)點的平均傳輸半徑越大，網(wǎng)絡通信能耗也越大.上述5種算法平均傳輸半徑的比較結果如圖11（b）所示.由第2.3節(jié)2）基于Delaunay三角剖分圖的最小剛性拓撲的構建可知MRTc算法是由刪除Delaunay三角剖分圖的部分較長鏈路得到的.因此，MRTc算法生成的拓撲結構具有較小的平均傳輸半徑.由圖11（b）可知，Udel算法和GG算法的平均傳輸半徑均高于MRTc算法.而LMST算法與RNG算法具有更小的平均傳輸半徑.

圖11（c）和（d）分別為5種算法最大節(jié)點度與最小節(jié)點度的比較.網(wǎng)絡的最大節(jié)點度定義為網(wǎng)絡中邏輯鏈路［5］最多的節(jié)點的度數(shù).與之類似，網(wǎng)絡的最小節(jié)點度定義為網(wǎng)絡中邏輯鏈路最少的節(jié)點的度數(shù).由第2.3節(jié)知最小剛性拓撲中節(jié)點至少包含兩條鏈路，因此，由MRTc算法生成的拓撲結構的最小節(jié)點度不低于2.這意味著由該算法生成的拓撲結構是2-容錯的，具有較高的魯棒性.由圖11（c）和（d）知算法LMST和RNG的最大節(jié)點度均在最優(yōu)值6以下，進一步說明這兩種算法的節(jié)點度過低.且算法LMST、GG和RNG的最小節(jié)點度均可以取值為1，表明這三種算法均是1-容錯的.當算法中的某條鏈路斷裂時，其他節(jié)點不能繼續(xù)維持網(wǎng)絡的連通性，因此網(wǎng)絡的容錯性較差.

圖11　不同算法的性能比較（（a）平均節(jié)點度的比較；（b）平均傳輸半徑的比較；（c）最大節(jié)點度的比較；（d）最小節(jié)點度的比較）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)絡覆蓋性與連通性的同時，能夠限制網(wǎng)絡平均節(jié)點度從而降低了網(wǎng)絡MAC層干擾，并有效地增強了網(wǎng)絡的魯棒性能，降低了網(wǎng)絡能耗.另外，該算法具有較強的穩(wěn)定性.然而，此算法也存在不足之處，即當網(wǎng)絡節(jié)點密度相同時，與LMST算法和RNG算法相比，MRTc算法的平均傳輸半徑較大，這表示由MRTc算法優(yōu)化得到的拓撲結構中存在部分較長鏈路.

針對該問題，我們提出下一步的研究方向即為尋找合適的方法，在保證網(wǎng)絡2-容錯性能的前提下，刪除拓撲中較長鏈路.

5.4實驗4睡眠調度前后能耗比較

節(jié)約能耗是網(wǎng)絡拓撲控制的首要目標，網(wǎng)絡中節(jié)點存在休眠和活動兩種狀態(tài).本實驗使用最小剛性拓撲，并以總能耗和存活節(jié)點比例為指標，全面深入地比較了網(wǎng)絡睡眠調度前、后的能量消耗情況.

計算睡眠調度前、后總能耗與活動節(jié)點比例實驗的設置場景如下：假設70個傳感器節(jié)點隨機部署于100×100的方形監(jiān)測區(qū)域內.每個節(jié)點擁有相同的初始能量E0=1kJ，且能量無法得到補充.假設數(shù)據(jù)包的長度為50Bytes，發(fā)射電路和接收電路的能量消耗Eelec=50nJ/bit，自由空間傳輸模型系數(shù)εfs=10pJ/bit/m2.實驗中采用洪泛式路由，當數(shù)據(jù)包個數(shù)變化時，睡眠調度前、后最小剛性拓撲的總能耗以及活動節(jié)點比例如圖12（a）和（b）所示.

由圖12（a）和（b）可知，最小剛性拓撲在經(jīng)由睡眠調度后，均能降低網(wǎng)絡的總能耗，提高網(wǎng)絡中存活節(jié)點的比例.因此，使用基于Voronoi覆蓋的睡眠調度算法后可有效降低網(wǎng)絡能耗.

圖12　睡眠調度前后最小剛性拓撲性能（（a）睡眠調度前后最小剛性拓撲總能耗；（b）睡眠調度前后最小剛性拓撲存活節(jié)點）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　結論

本文提出了一個基于Voronoi覆蓋與Delaunay三角剖分圖的最小剛性拓撲控制算法，該算法采用睡眠調度與功率控制相結合的方案來降低網(wǎng)絡能耗.算法中，無線傳感器網(wǎng)絡通過睡眠調度在保證監(jiān)測區(qū)域全覆蓋的同時，可將覆蓋冗余節(jié)點調整為休眠狀態(tài).進一步地，算法在剩余活動節(jié)點之間，構建基于Delaunay三角剖分圖的最小剛性拓撲結構.這一方法有效限制了平均節(jié)點度，即網(wǎng)絡平均節(jié)點度不大于4，且所生成的鏈路數(shù)量滿足稀疏性要求.經(jīng)過MRTc算法優(yōu)化后的網(wǎng)絡拓撲是2-容錯的，提高了網(wǎng)絡的容錯性.

未來工作可進一步研究Delaunay三角剖分圖的性能對算法的影響，進而研究該拓撲在異構網(wǎng)絡中的構建問題；另外，尋找合適的方法，在保證網(wǎng)絡2-容錯性能的前提下，刪除拓撲中較長鏈路.

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)拓撲構建研究.電子與信息學報，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)絡拓撲控制算法.自動化學報，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（羅小元，閆彥霖，郝麗娟，李紹寶，關新平.基于最優(yōu)剛性圖的能量有效分布式拓撲控制算法.通信學報，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（蘇金樹，郭文忠，余朝龍，陳國龍.負載均衡感知的無線傳感器網(wǎng)絡容錯分簇算法.計算機學報，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（羅小元，邵士凱，關新平，趙淵潔.多智能體最優(yōu)持久編隊動態(tài)生成與控制.自動化學報，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（羅小元，楊帆，李紹寶，關新平.多智能體系統(tǒng)的最優(yōu)持久編隊生成策略.自動化學報，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（董箭，彭認燦，鄭義東.利用局部動態(tài)最優(yōu)Delaunay三角網(wǎng)改進逐點內插算法.武漢大學學報:信息科學版，2013，38（5）:613-617）

21 Wang Chao-Rui.Graph Theory（3rd Edition）.Beijing:Beijing Institute of Technology Press，2005.15（王朝瑞.圖論（第3版）.北京:北京理工大學出版社，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

薛 亮河北工程大學信息與電氣工程學院副教授.主要研究方向為無線傳感器網(wǎng)絡，認知無線網(wǎng)絡技術.

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.）

陳晰河北工程大學碩士研究生.主要研究方向為無線傳感器網(wǎng)絡技術.本文通信作者.

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.）

趙繼軍河北工程大學信息與電氣工程學院教授.主要研究方向為無線傳感器網(wǎng)絡，寬帶通信網(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.）

黎作鵬河北工程大學信息與電氣工程學院講師.主要研究方向為無線傳感器網(wǎng)絡，物聯(lián)網(wǎng)技術，納米網(wǎng)絡.

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.）

關新平上海交通大學電子信息與電氣工程學院教授.主要研究方向為無線傳感器網(wǎng)絡，認知無線電等通信網(wǎng)絡的控制，復雜網(wǎng)絡動態(tài)系統(tǒng)的性能分析與控制，非線性時滯系統(tǒng)的拓撲控制，網(wǎng)絡化控制系統(tǒng)設計.

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

國家自然科學基金（61304131，61402147），河北省自然科學基金（F2016402054，F(xiàn)2014402075），河北省教育廳科學研究計劃（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）

本文責任編委趙千川

Recommended by Associate Editor ZHAO Qian-Chuan

1.河北工程大學信息與電氣工程學院邯鄲0560382.邯鄲市光纖通信與寬帶接入技術重點實驗室邯鄲0560383.上海交通大學系統(tǒng)控制與信息處理教育部重點實驗室上海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