謝珊珊，白光偉，，曹 磊

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

0 引 言

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

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

1 相關(guān)工作

現(xiàn)有的構(gòu)建CDS算法可分為集中型和分布式兩類。集中CDS需要網(wǎng)絡(luò)的全局信息，不適用于擁有大量節(jié)點的大規(guī)模網(wǎng)絡(luò)，基于分布式的局部化算法只需要對于周圍鄰居內(nèi)的n跳相鄰信息，可以滿足協(xié)議低消耗、快收斂的要求。

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

圖1 節(jié)點廣播策略

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

鑒于此，本文提出基于區(qū)域劃分的連通支配集協(xié)議，根據(jù)網(wǎng)絡(luò)的拓撲信息，分區(qū)域選擇中繼轉(zhuǎn)發(fā)節(jié)點求解網(wǎng)絡(luò)的CDS，均勻分布所有支配節(jié)點。

2 基于區(qū)域劃分的連通支配集協(xié)議 （RPMPR）

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

2.1 相關(guān)定義

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

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

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

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

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

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

2.2 基于拓撲信息的分區(qū)策略

2.2.1 分區(qū)策略

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

（1）節(jié)點u獲取所有鄰居節(jié)點信息，根據(jù)各個鄰居節(jié)點的位置信息將一跳鄰居節(jié)點分為3個區(qū)域；

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

（3）根據(jù)2跳鄰居位置信息，將2跳鄰居節(jié)點也相應(yīng)A2、B2、C2區(qū)。

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

圖2 鄰居節(jié)點分區(qū)

2.2.2 中繼節(jié)點選舉策略

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

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

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

圖3 理想情況下分區(qū)選擇中繼節(jié)點

2.3 構(gòu)造連通支配集

連通支配集構(gòu)造算法步驟如下：

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

（2）鄰居節(jié)點間進行消息交換，節(jié)點獲得2跳內(nèi)的所有鄰居節(jié)點度信息和位置信息；節(jié)點u依據(jù)已知的鄰居節(jié)點信息，按照2.1節(jié)中分區(qū)方法進行區(qū)域劃分；

（3）按2.2節(jié)中繼節(jié)點選舉策略，A1區(qū)域進行中繼節(jié)點選擇；

（4）同時A2區(qū)域去除被覆蓋節(jié)點，涉及到其他B2、C2區(qū)也去掉相關(guān)覆蓋節(jié)點；

（5）同A1區(qū)域選擇支配節(jié)點的算法，B1／C1／D1區(qū)域執(zhí)行支配節(jié)點的選擇；

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

（7）以度為依據(jù)，選擇合適的支配節(jié)點；

（8）結(jié)束。

圖4是MPR［12］和RPMPR協(xié)議算法流程對比，不同之處用點劃線框出。MPR采用的是貪心算法構(gòu)建中繼轉(zhuǎn)發(fā)節(jié)點集，RPMPR則通過對鄰居節(jié)點進行劃分，分區(qū)域選擇中繼轉(zhuǎn)發(fā)節(jié)點。RPMPR協(xié)議以節(jié)點的度作為選擇支配節(jié)點的依據(jù)。

3 協(xié)議性能分析與評價

3.1 實驗設(shè)計

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

圖4 協(xié)議算法對比

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

仿真實驗考慮的性能分析標(biāo)準(zhǔn)包括以下方面：

（1）連通支配集規(guī)模：即連通支配集中節(jié)點個數(shù)。

（2）平均最短路徑：虛擬骨干網(wǎng)中的平均最短路徑。

（3）健壯性：虛擬骨干網(wǎng)中移除支配節(jié)點導(dǎo)致網(wǎng)絡(luò)必須重新構(gòu)建虛擬骨干網(wǎng)的支配節(jié)點數(shù)上限。

3.2 結(jié)果分析

本文分析了RPMPR協(xié)議生成的連通支配集規(guī)模，分析了由連通支配集導(dǎo)出的虛擬骨干網(wǎng)分布情況，最后分析生成的虛擬骨干網(wǎng)的平均最短路徑和健壯性。

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

圖5 連通支配集規(guī)模

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

圖6 在200＊200m的矩形空間內(nèi)形成的虛擬骨干網(wǎng)

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

圖7 骨干網(wǎng)平均最短路徑

圖8 描述了各協(xié)議關(guān)于虛擬骨干網(wǎng)健壯性的性能對比?？梢钥闯?，WULI產(chǎn)生的CDS規(guī)模較大，健壯性必然較好。相較于MPR和Rulek（3），RPMPR協(xié)議在維持更小規(guī)模的CDS的同時，健壯性更好。RPMPR的CDS規(guī)模比Rulek（D，3）協(xié)議減小了7%，健壯性比Rulek（D，3）略微降低。RPMPR協(xié)議產(chǎn)生的支配節(jié)點分布均勻，不僅有利于生成更小規(guī)模的虛擬骨干網(wǎng)，同時保障生成的虛擬骨干網(wǎng)仍具有良好的健壯性。

圖8 骨干網(wǎng)健壯性

4 結(jié)束語

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

［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）.［解文斌，李佳明，陳永光.基于區(qū)域劃分的分布式虛擬骨干網(wǎng)算法 ［J］.軟件學(xué)報，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：無線傳感器網(wǎng)絡(luò)中一種能量感知的分布式分簇算法 ［J］.計算機研究與發(fā)展，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）.［沈波，張世永，鐘亦平.無線傳感器網(wǎng)絡(luò)分簇路由協(xié)議 ［J］.軟件學(xué)報，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］.計算機學(xué)報，2010，33 （6）：1073－1087.］

［10］LIAO Feixiong，MA Liang，F(xiàn)AN Bingquan.Efficient approximation algorithm for minimum connected dominating set［J］.Journal of Chinese Computer Systems，2008，29 （5）：875－878（in Chinese）.［廖飛雄，馬良，范炳全.一種求解最小連通支配集的高效近似算法 ［J］.小型微型計算機系統(tǒng)，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.