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

謝珊珊，白光偉，，曹 磊

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

0 引 言

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

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

1 相關(guān)工作

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

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

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

無(wú)論 MPR［12］還是 EMRP［13］，支配節(jié)點(diǎn)的選取都是以節(jié)點(diǎn)ID作為評(píng)判標(biāo)準(zhǔn)，降低協(xié)議復(fù)雜度。但單純依據(jù)節(jié)點(diǎn)的ID來(lái)選擇中繼節(jié)點(diǎn)，對(duì)于形成虛擬骨干網(wǎng)并不必要。同時(shí)MPR協(xié)議沒(méi)有充分利用拓?fù)湫畔?，部分支配?jié)點(diǎn)更接近拓?fù)溥吔纾采w鄰居個(gè)數(shù)比拓?fù)渲虚g支配節(jié)點(diǎn)相對(duì)減少，不利于形成更小規(guī)模的虛擬骨干網(wǎng)。

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

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

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

2.1 相關(guān)定義

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

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

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

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

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

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

2.2 基于拓?fù)湫畔⒌姆謪^(qū)策略

2.2.1 分區(qū)策略

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

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

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

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

若X1（X∈ ｛A，B，C｝）區(qū)域非空，X2（X∈ ｛A，B，C｝）區(qū)域?yàn)榭?，此時(shí)設(shè)置X2＝N（X1），X2中節(jié)點(diǎn)稱(chēng)為虛擬節(jié)點(diǎn)，虛擬節(jié)點(diǎn)至少隸屬于兩個(gè)分區(qū)。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（8）結(jié)束。

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

3 協(xié)議性能分析與評(píng)價(jià)

3.1 實(shí)驗(yàn)設(shè)計(jì)

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

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

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

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

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

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

（3）健壯性：虛擬骨干網(wǎng)中移除支配節(jié)點(diǎn)導(dǎo)致網(wǎng)絡(luò)必須重新構(gòu)建虛擬骨干網(wǎng)的支配節(jié)點(diǎn)數(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é)點(diǎn)數(shù)減小14.5%。MPR協(xié)議采用節(jié)點(diǎn)ID作為連通支配節(jié)點(diǎn)選擇的依據(jù)，不考慮節(jié)點(diǎn)通信范圍內(nèi)鄰居節(jié)點(diǎn)個(gè)數(shù)及其拓?fù)湮恢?。選中的支配節(jié)點(diǎn)鄰居個(gè)數(shù)少，則需要更多支配節(jié)點(diǎn)來(lái)覆蓋整個(gè)網(wǎng)絡(luò)，不利于形成更小規(guī)模的CDS，如節(jié)點(diǎn)ID為0的節(jié)點(diǎn)在任何情況下都被選中；RPMPR協(xié)議采用節(jié)點(diǎn)的度作為選擇依據(jù)，支配節(jié)點(diǎn)連接的鄰居個(gè)數(shù)增多，支配節(jié)點(diǎn)數(shù)目必然減少。Rulek（D，3）較Rulek形成的CDS規(guī)模也明顯降低，但仍然比RPMPR協(xié)議多出7%。這表明RPMPR協(xié)議采用分區(qū)選擇中繼轉(zhuǎn)發(fā)節(jié)點(diǎn)，支配節(jié)點(diǎn)分布更加均勻，較少數(shù)目的支配節(jié)點(diǎn)即可覆蓋全網(wǎng)。

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

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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

［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é)報(bào)，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ú)線傳感器網(wǎng)絡(luò)中一種能量感知的分布式分簇算法 ［J］.計(jì)算機(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ú)線傳感器網(wǎng)絡(luò)分簇路由協(xié)議 ［J］.軟件學(xué)報(bào)，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］.計(jì)算機(jī)學(xué)報(bào)，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］.小型微型計(jì)算機(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.