基于區域劃分的連通支配集協議

謝珊珊，白光偉，，曹 磊

（1.南京工業大學 計算機科學與技術系，江蘇 南京210009；2.南京大學 軟件新技術國家重點實驗室，江蘇 南京210093）

0 引 言

無線傳感器網絡是由大量自治節點通過多跳通信方式構建形成的自組織網絡。由于通信范圍受限、電池供電能量有限和較高的容錯性能要求，傳感器節點大多依賴于中間節點轉發和接收消息。中間轉發節點數目過多時，容易加重網絡擁塞，容易導致類似廣播風暴的問題［1－2］。分簇技術是一種能夠優化能耗的拓撲控制技術，能減少冗余數據量，延長網絡壽命，有效進行網內數據融合，減少數據報告延遲和增強網絡的可擴展性［3－5］。作為一種特殊的分簇形式，虛擬骨干網在傳感器網絡中可獲得良好的節能效果和路由執行效率［1，6－8］。虛擬骨干網的一種構造方法是通過構造整個網絡的連通支配集 （connected domination set，CDS）。通常希望在保證網絡功能、可靠性和效率的同時獲得盡可能小的CDS。

現有的求解連通支配集的協議較多考慮CDS的規模大?。?－11］，并不著重考慮支配節點在網絡拓撲中的分布情況，從而產生支配節點分布過于集中導致加快節點死亡等問題。本文在深入研究求解連通支配集的典型協議基礎上，提出基于局域劃分的連通支配集協議，保證CDS規模降低的同時，使得支配節點分布更加均勻。

1 相關工作

現有的構建CDS算法可分為集中型和分布式兩類。集中CDS需要網絡的全局信息，不適用于擁有大量節點的大規模網絡，基于分布式的局部化算法只需要對于周圍鄰居內的n跳相鄰信息，可以滿足協議低消耗、快收斂的要求。

原始MPR機制提供了一種局部化且有效的方式，圖1（a）和圖1（b）分別表示傳統洪泛廣播和多點中繼轉發（MPR）廣播方式，可看出MPR機制中節點轉發的數據包較傳統廣播方式明顯減少。文獻 ［12］提出獨立于源節點的創新方法來構造節點轉發集合，并提出兩條基于ID限制的簡單規則構建 CDS。EMPR［13］對 MPR［12］的兩條限制規則進行了改進，增加節點有兩個不直接相連鄰居的限制條件，并提出自由節點的概念。

圖1 節點廣播策略

無論 MPR［12］還是 EMRP［13］，支配節點的選取都是以節點ID作為評判標準，降低協議復雜度。但單純依據節點的ID來選擇中繼節點，對于形成虛擬骨干網并不必要。同時MPR協議沒有充分利用拓撲信息，部分支配節點更接近拓撲邊界，覆蓋鄰居個數比拓撲中間支配節點相對減少，不利于形成更小規模的虛擬骨干網。

鑒于此，本文提出基于區域劃分的連通支配集協議，根據網絡的拓撲信息，分區域選擇中繼轉發節點求解網絡的CDS，均勻分布所有支配節點。

2 基于區域劃分的連通支配集協議 （RPMPR）

本節提出一種基于區域劃分的連通支配集協議RPMPR。我們詳細介紹協議的具體機制，包括鄰居節點分區策略、分區選擇中繼節點以及支配節點的選舉策略。

2.1 相關定義

傳感器網絡研究中，一般采用用單位圓盤圖 （unit disk graph，UDG）模型，即利用無向圖G＝ （V，E）描述傳感器網絡的拓撲結構。V是節點集合，E為所有邊的集合。為方便描述，給出以下相關定義。

定義1（1跳鄰居集合N1（v）） 無向圖G＝ （V，E）中，對于節點v∈V，節點v的1跳鄰居集合N1（v）＝ ｛u∈V｜ （u，v）∈E｝。

定義2（節點集V’覆蓋的鄰居節點集合N（V’））無向圖G＝ （V，E）中，對于節點集合V’，節點集合中所有節點的一跳鄰居集合為N（V’）＝∪iN1（vi），vi∈V’。

定義3（2跳鄰居集合N2（v）） 無向圖G＝ （V，E）中，節點v的2跳鄰居集合N2（v）＝N1（N1（v））－（N1（v）∪ ｛v｝）。

定義4（中繼轉發節點集） 無向圖G＝ （V，E）中，對于節點v∈V，存在一個N1（v）的子集V’，滿足N2（v）N（V’），N（V’）N2（v）。

定義5（連通支配集） 無向圖G （V，E）中，若存在一個節點集合V’（V’V）滿足：①由節點集合V’導出的子圖是連通圖；②圖G中任意節點v∈V，滿足v∈N（V’）∪V’。則稱該節點集合V’為CDS。

2.2 基于拓撲信息的分區策略

2.2.1 分區策略

節點根據鄰居節點信息，對所有鄰居節點進行區域劃分。分區過程中節點直接對鄰居節點進行標記，不需要額外代價。分區情況如圖2所示，具體步驟如下：

（1）節點u獲取所有鄰居節點信息，根據各個鄰居節點的位置信息將一跳鄰居節點分為3個區域；

（2）每個區域間隔120°，A1、B1、C1分別為三區域中節點集合；

（3）根據2跳鄰居位置信息，將2跳鄰居節點也相應A2、B2、C2區。

若X1（X∈ ｛A，B，C｝）區域非空，X2（X∈ ｛A，B，C｝）區域為空，此時設置X2＝N（X1），X2中節點稱為虛擬節點，虛擬節點至少隸屬于兩個分區。

圖2 鄰居節點分區

2.2.2 中繼節點選舉策略

將節點的ID作為選擇中繼節點依據，容易導致部分節點單純因ID較大 （較?。┍贿x中，因此考慮節點的度作為選擇支配節點的依據。鄰居范圍內度最大的節點一般相距2跳或3跳距離。

對于每一對區域X1、X2（X∈ ｛A，B，C｝），選擇X1中1跳鄰居節點覆蓋X2中2跳鄰居節點。從X1區域選擇支配節點，若X1區域中已有節點p被選作支配節點，則節點u也選擇節點p作為支配節點；否則，節點u從X1區域內選擇支配節點，支配節點q∈X1，并且滿足

節點的度相同則選擇ID最小的節點作為支配節點。理想情況下鄰居節點分區如圖3所示。

圖3 理想情況下分區選擇中繼節點

2.3 構造連通支配集

連通支配集構造算法步驟如下：

（1）初始化，所有節點默認成為非支配節點；

（2）鄰居節點間進行消息交換，節點獲得2跳內的所有鄰居節點度信息和位置信息；節點u依據已知的鄰居節點信息，按照2.1節中分區方法進行區域劃分；

（3）按2.2節中繼節點選舉策略，A1區域進行中繼節點選擇；

（4）同時A2區域去除被覆蓋節點，涉及到其他B2、C2區也去掉相關覆蓋節點；

（5）同A1區域選擇支配節點的算法，B1／C1／D1區域執行支配節點的選擇；

（6）檢查X2（X∈ ｛A，B，C｝）區，若有未被覆蓋2跳節點集合非空，跳到步驟 （3）；

（7）以度為依據，選擇合適的支配節點；

（8）結束。

圖4是MPR［12］和RPMPR協議算法流程對比，不同之處用點劃線框出。MPR采用的是貪心算法構建中繼轉發節點集，RPMPR則通過對鄰居節點進行劃分，分區域選擇中繼轉發節點。RPMPR協議以節點的度作為選擇支配節點的依據。

3 協議性能分析與評價

3.1 實驗設計

本節采用網絡仿真器ns2對第2節提出的RPMPR協議進行仿真分析。仿真實驗基于IEEE 802.11協議MAC協層的DCF機制；300個節點隨機分布在200＊200的矩形空間內；節點通信半徑均為30m。仿真實驗所有分析數據均為多次重復實驗取平均值。

圖4 協議算法對比

這里將RPMPR協議與幾種代表性協議進行對比分析，包括 MPR［12］、WULI［14］、Rulek［15］（記為 Rulek （k）），以及采用節點的度作為選擇依據的Rulek（記為Rulek（D，k））。本次實驗考慮k＝3的情況。

仿真實驗考慮的性能分析標準包括以下方面：

（1）連通支配集規模：即連通支配集中節點個數。

（2）平均最短路徑：虛擬骨干網中的平均最短路徑。

（3）健壯性：虛擬骨干網中移除支配節點導致網絡必須重新構建虛擬骨干網的支配節點數上限。

3.2 結果分析

本文分析了RPMPR協議生成的連通支配集規模，分析了由連通支配集導出的虛擬骨干網分布情況，最后分析生成的虛擬骨干網的平均最短路徑和健壯性。

圖5是協議生成的連通支配集規模的比較，RPMPR協議產生的CDS較 MPR協議產生的節點數減小14.5%。MPR協議采用節點ID作為連通支配節點選擇的依據，不考慮節點通信范圍內鄰居節點個數及其拓撲位置。選中的支配節點鄰居個數少，則需要更多支配節點來覆蓋整個網絡，不利于形成更小規模的CDS，如節點ID為0的節點在任何情況下都被選中；RPMPR協議采用節點的度作為選擇依據，支配節點連接的鄰居個數增多，支配節點數目必然減少。Rulek（D，3）較Rulek形成的CDS規模也明顯降低，但仍然比RPMPR協議多出7%。這表明RPMPR協議采用分區選擇中繼轉發節點，支配節點分布更加均勻，較少數目的支配節點即可覆蓋全網。

圖5 連通支配集規模

圖6描述的是各協議所形成的虛擬骨干網分布情況。MPR協議生成的虛擬骨干網，例如圖6（a）中支配節點a就是這樣的 “冗余”節點，圖6（a）中還有其它類似因為ID較小而被選中的支配節點。圖6（b）中Rulek（3）形成的虛擬骨干網中，支配節點分布相較圖6（a）和圖6（c）均勻，但支配節點數目較多，且部分支配節點分布靠近拓撲邊界。圖6（c）中Rulek（D，3）生成的虛擬骨干網，局部區域支配節點分布過于集中，如圖6（c）中A、B、C這3個標記區域；支配節點較多，各支配節點覆蓋的通信范圍也相互重疊，降低控制冗余數據包和信號干擾的效果。從圖6（d）可以看出，相較MPR和Rulek（D，3）所形成的虛擬骨干網，基于分區策略的RPMPR協議所形成的虛擬骨干網更集中于拓撲中間，支配節點分布更均勻。

圖6 在200＊200m的矩形空間內形成的虛擬骨干網

圖7 是各協議關于虛擬骨干網中平均最短路徑參數的對比。RPMPR協議產生的CDS的支配節點個數比MPR協議的要少，而RPMPR協議生成的虛擬骨干網的平均最短路徑卻優于MPR。這是因為MPR協議中部分支配節點間距離較遠，如圖6（a）中支配節點A到節點B必須通過節點C，導致平均最短路徑較長。Rulek（D，3）中局部支配節點分布更為密集，因而平均最短路徑略端些。平均最短路徑變長也是虛擬骨干網中骨干節點稀疏并且均勻分布所要犧牲的代價之一。

圖7 骨干網平均最短路徑

圖8 描述了各協議關于虛擬骨干網健壯性的性能對比。可以看出，WULI產生的CDS規模較大，健壯性必然較好。相較于MPR和Rulek（3），RPMPR協議在維持更小規模的CDS的同時，健壯性更好。RPMPR的CDS規模比Rulek（D，3）協議減小了7%，健壯性比Rulek（D，3）略微降低。RPMPR協議產生的支配節點分布均勻，不僅有利于生成更小規模的虛擬骨干網，同時保障生成的虛擬骨干網仍具有良好的健壯性。

圖8 骨干網健壯性

4 結束語

無線傳感器網絡中，利用連通支配集導出的虛擬骨干網可以有效應對傳感器路由、節能等要求。如何求解網絡中最小連通支配集合是其中的關鍵問題。本文提出一種基于區域劃分的連通支配集求解協議 （RPMPR），充分考慮節點能獲取到的拓撲信息，采取分區策略構建中繼轉發節點集，并以節點的度作為支配節點選擇依據。仿真實驗證明RPMPR形成的連通支配集規模更小，提高了支配節點分布的均勻性，能夠較好地適應于節點密集型無線傳感器網絡。下一步的工作是進一步降低連通支配集規模，同時考慮全網節點能耗均衡，研究構建節點分布更加均勻的連通支配集算法。

［1］XIE Wenbin，LI Jiaming，CHEN Yongguang.Distributed virtue backbone network algorithm based on topology characteristic［J］.Journal of Software，2010，21 （6）：1416－1425 （in Chinese）.［解文斌，李佳明，陳永光.基于區域劃分的分布式虛擬骨干網算法 ［J］.軟件學報，2010，21 （6）：1416－1425.］

［2］QU L，Ahmet S，Nallasamy M.A low－cost flooding algorithm for wireless sensor networks ［C］.HK：Proceedings of IEEE WCNC，2007：3498－3503.

［3］Cantoni V，Lombardi L，Lombardi P.Future scenarios of parallel computing：Distributed sensor networks ［J］.Journal of Visual Languages ＆Computing，2007，18 （8）：484－491.

［4］ZHOU Xinlian，WU Min，XU Jianbo.BPEC－an energy－aware distributed clustering algorithm in WSNs ［J］.Journal of Computer Research and Development，2009，46 （5）：723－730 （in Chinese）.［周新蓮，吳敏，徐建波.BPEC：無線傳感器網絡中一種能量感知的分布式分簇算法 ［J］.計算機研究與發展，2009，46 （5）：723－730.］

［5］SHEN Bo，ZHANG Shiyong，ZHONG Yiping.Cluster－based routing protocols for wireless sensor networks ［J］.Journal of Software，2006，17 （7）：1588－1600 （in Chinese）.［沈波，張世永，鐘亦平.無線傳感器網絡分簇路由協議 ［J］.軟件學報，2006，17 （7）：1588－1600.］

［6］Basagni S，Mastrogiovanni M，Panconesi A，et al.Localized protocols for Ad Hoc clustering and backbone formation：A performance comparison ［J］.IEEE Transactions on Parallel and Distributed Systems，2006，17 （4）：292－306.

［7］Teymoori P，Yazdani N.Local reconstruction of virtual backbone to support mobility in wireless ad hoc networks［C］.Proceedings of the Int’l Symp on Telecommunications，2008：382－387.

［8］WANG L，XIAO Y.A survey of energy－efficient scheduling mechanisms in sensor networks ［J］.Mobile Networks and Applications，2006，11 （5）：723－740.

［9］LU Gang，ZHOU Mingtian，TANG Yong，et al.A survey on exact algorithms for dominating set related problems in arbitrary graphs［J］.Chinese Journal of Computers，2010，33 （6）：1073－1087（in Chinese）.［路綱，周明天，唐勇，等.任意圖支配集精確算法回顧 ［J］.計算機學報，2010，33 （6）：1073－1087.］

［10］LIAO Feixiong，MA Liang，FAN Bingquan.Efficient approximation algorithm for minimum connected dominating set［J］.Journal of Chinese Computer Systems，2008，29 （5）：875－878（in Chinese）.［廖飛雄，馬良，范炳全.一種求解最小連通支配集的高效近似算法 ［J］.小型微型計算機系統，2008，29 （5）：875－878.］

［11］Rai M，Verma S，Tapaswi S.A heuristic for minimum connected dominating set with local repair for wireless sensor networks ［C］.Gosier，Guadeloupe：Proceedings of ICN，2009：106－111.

［12］Adjih C，Jacquet P，Viennot L.Computing connected dominated sets with multi－point relays ［J］.Ad Hoc ＆ Sensor Wireless Networks，2005 （1）：27－39.

［13］WU J，LOU W，DAI F.Extended multipoint relays to determine connected dominating sets in MANETs ［J］.IEEE Transactions on Computers，2006，55 （3）：334－347.

［14］WU J，LI H.On calculating connected dominating sets for efficient routing in Ad Hoc wireless networks［C］.Seattle，WA：Proceedings of ACM Int’l Workshop Discrete Algorithms and Methods for Mobile Computing and Communications，1999：7－14.

［15］DAI F，WU J.An extended localized algorithm for connected dominating set formation in Ad Hoc wireless networks ［J］.IEEE Transactions on Parallel and Distributed Systems，2004，15 （10）：908－920.