無(wú)線傳感器網(wǎng)絡(luò)中d-Hop 2-連通容錯(cuò)支配集的分布式構(gòu)造算法*

鄭 嬋，尹 令，孫世新

(1.電子科技大學(xué)計(jì)算機(jī)學(xué)院，成都610054;2.華南農(nóng)業(yè)大學(xué)信息學(xué)院，廣州510642)

無(wú)線傳感器網(wǎng)絡(luò)是由大量具有感知、數(shù)據(jù)處理和通信能力的傳感器節(jié)點(diǎn)組成的網(wǎng)絡(luò)，具有低功耗、低成本、智能化、分布式、自組織等特點(diǎn)，在軍事、環(huán)保、醫(yī)療、商業(yè)、農(nóng)業(yè)、災(zāi)害預(yù)測(cè)及救援等領(lǐng)域都有著廣闊的應(yīng)用前景。由于沒(méi)有類似蜂窩通信中基站的骨干基礎(chǔ)，且受到傳感器無(wú)線收發(fā)裝置傳輸半徑和節(jié)點(diǎn)能量的限制，多數(shù)的節(jié)點(diǎn)之間都不能直接進(jìn)行通信，只能通過(guò)若干中間節(jié)點(diǎn)形成的虛擬骨干網(wǎng)進(jìn)行多跳交換數(shù)據(jù)和通信。在無(wú)線傳感器網(wǎng)絡(luò)中構(gòu)造虛擬骨干網(wǎng)是優(yōu)化網(wǎng)絡(luò)結(jié)構(gòu)的一個(gè)重要手段，而構(gòu)建虛擬骨干網(wǎng)最常用的技術(shù)就是計(jì)算網(wǎng)絡(luò)的連通支配集CDS(Connected Dominating Set)。CDS中的支配節(jié)點(diǎn)構(gòu)成高一級(jí)的骨干節(jié)點(diǎn)控制著全網(wǎng)的路由、維護(hù)和管理。在單位圓盤圖UDG(Unit Disk Graph)的網(wǎng)絡(luò)模型中構(gòu)造最小連通支配集MCDS(Minimum CDS)早已被證明是NP完全問(wèn)題［1］，在節(jié)點(diǎn)具有中等規(guī)模以上(一般節(jié)點(diǎn)數(shù)量大于40)時(shí)，只能構(gòu)造近似的最小連通支配集。近十年來(lái)，關(guān)于構(gòu)造最小連通支配集已經(jīng)有較為深入而成熟的研究，研究學(xué)者們提出了各種算法來(lái)構(gòu)造近似的最小連通支配集［2］。

隨著無(wú)線傳感器網(wǎng)絡(luò)規(guī)模的增大和密集程度的增加，采用近似的最小連通支配集算法獲得的支配集節(jié)點(diǎn)數(shù)目依然較大。為了解決這一問(wèn)題，很多學(xué)者［3-8］提出d-hop連通支配集(d-hop CDS)來(lái)大大減少支配集節(jié)點(diǎn)數(shù)量。d-hop CDS指的是受支配節(jié)點(diǎn)和支配節(jié)點(diǎn)之間的跳數(shù)最多可達(dá)d跳。當(dāng)d≥2時(shí)，d-hop CDS具有比CDS少得多的支配節(jié)點(diǎn)數(shù)，可提高網(wǎng)絡(luò)容量和網(wǎng)絡(luò)性能，因?yàn)閐-hop CDS將無(wú)線傳感器網(wǎng)絡(luò)劃分為更大的簇(Cluster)，整個(gè)網(wǎng)絡(luò)收縮為以d-hop簇頭(Clusterhead)為超級(jí)節(jié)點(diǎn)的多層次網(wǎng)絡(luò)，簇內(nèi)其余節(jié)點(diǎn)都通過(guò)d-hop簇頭和別的節(jié)點(diǎn)通信。Nguyen等［9］證明了在 UDG中尋找最小 dhop CDS依然是NP完全問(wèn)題。

另一方面，由于傳感器節(jié)點(diǎn)存在能量、存儲(chǔ)和計(jì)算等資源約束，節(jié)點(diǎn)的失效、鏈路的斷裂會(huì)導(dǎo)致網(wǎng)絡(luò)失敗，因此構(gòu)造容錯(cuò)性好、可靠性高的虛擬骨干網(wǎng)是一個(gè)非常有意義的課題。構(gòu)造具有一定冗余度的k-連通支配集來(lái)充當(dāng)虛擬骨干網(wǎng)可提高網(wǎng)絡(luò)的容錯(cuò)性和可靠性。k-連通指虛擬骨干網(wǎng)中任意k-1個(gè)骨干節(jié)點(diǎn)出錯(cuò)，虛擬骨干網(wǎng)仍然是連通的。當(dāng)k較小(k=2，3等)，k-連通骨干網(wǎng)相對(duì)簡(jiǎn)單并且具有容錯(cuò)能力，可在少量節(jié)點(diǎn)失效的情況下依然能夠保持骨干網(wǎng)的拓?fù)溥B通。

基于上述兩個(gè)目的需構(gòu)建一個(gè)既精簡(jiǎn)又具有容錯(cuò)能力的連通支配集作為虛擬骨干網(wǎng)，可結(jié)合連通支配集的多跳性質(zhì)和k-連通性質(zhì)。

近十年來(lái)，關(guān)于1-hop的MCDS的構(gòu)造研究已經(jīng)較為成熟而深入，提出了多種分布式算法來(lái)構(gòu)造近似的最小連通支配集，其中以基于貪心［10］、Steiner tree［11］、剪枝［12］、最大獨(dú)立集［13］、多點(diǎn)中繼集［14］和簇構(gòu)造［15］等一系列方法的研究為最多。而后從單跳MCDS向d-hop CDS擴(kuò)展，比較有代表性的是基于簇構(gòu)造［3-4］、基于貪心［16］、基于剪枝［5-6］的d-hop CDS構(gòu)造法，以及能量均衡的 CDS構(gòu)造［17］。Gao等人［7］提出在 UDG 或 UBG(Unit Ball Graph)圖中構(gòu)造d-hop CDS的多項(xiàng)式近似算法并給出了詳盡的證明。在文獻(xiàn)［3］和文獻(xiàn)［4］中，采用基于Cluster構(gòu)造來(lái)構(gòu)造d-hop CDS，通信代價(jià)和算法時(shí)間都依賴于跳數(shù)d和節(jié)點(diǎn)平均度。Yang等［5］提出了不同一般做法的剪枝策略，初始i=0時(shí)所有節(jié)點(diǎn)都是ihop CDS，而后對(duì) i=0，1，…d-1 需經(jīng)過(guò) d次刪減，每次刪減i-hop CDS被剪枝成為(i+1)-hop CDS。文獻(xiàn)［8］更有新意的從青蟲產(chǎn)卵中得到啟示，模擬生物行為構(gòu)建d-hop CDS，使算法性能能獨(dú)立于跳數(shù)d和節(jié)點(diǎn)平均度，此法適合大規(guī)模和超大規(guī)模的傳感器網(wǎng)絡(luò)的d-hop CDS的構(gòu)建。

在提高連通支配集的容錯(cuò)性可靠性方面，學(xué)者們也做了許多研究［18-24］，這其中大部分都結(jié)合了 k-Vertex連通性和m-支配性。Dai等［18］采用基于概率的、確定的和混合的3種方法構(gòu)造k-連通k-支配集，文獻(xiàn)［19］也提出k-連通m-支配集的構(gòu)造法。關(guān)于2-連通多支配集也有特定研究［20-21］，Wang等［22］專門研究了2-連通的骨干網(wǎng)構(gòu)造方法，同時(shí)Li等［23］提出兩種中心式的構(gòu)造2-連通d-hop支配集的方法。據(jù)筆者所知，目前研究2-連通d-hop支配集的分布式構(gòu)造方法鮮少，本文基于單位圓盤圖網(wǎng)絡(luò)模型提出d-hop 2-連通支配集的分布式構(gòu)造算法，d-hop 2-CDS算法(d-hop 2-Connected Domination Set Construction)，主要策略分多步構(gòu)造，先分簇構(gòu)造d-hop獨(dú)立支配集，后添加路徑節(jié)點(diǎn)形成2-連通支配集。

1 問(wèn)題定義

1.1 定義1 單位圓盤圖UDG(Unit Disk Graph)

一般地，無(wú)線傳感器網(wǎng)絡(luò)可以抽象為無(wú)向單位圓盤圖，網(wǎng)絡(luò)中每個(gè)傳感器節(jié)點(diǎn)在圖中可用單位圓盤中的頂點(diǎn)來(lái)表示，如果兩個(gè)傳感器節(jié)點(diǎn)能相互直接通信則在圖中對(duì)應(yīng)為一條邊。為便于描述，以下將單位圓盤圖簡(jiǎn)稱為G=(V，E)。V和E分別表示節(jié)點(diǎn)集和邊集。這里只考慮連通的單位圓盤圖G。

1.2 定義2 連通支配集CDS(Connected Dominating Set)

圖 G=(V，E)中，設(shè)D?V，?u∈V，u∈D 或 u 與 D中某一節(jié)點(diǎn)相鄰，稱D為圖G的支配集(Dominating Set，DS)，DS中的節(jié)點(diǎn)稱為支配節(jié)點(diǎn)，不在該集中的節(jié)點(diǎn)則被稱為受支配節(jié)點(diǎn)。若由D導(dǎo)出的子圖為連通圖，則稱D為CDS。若?u∈D，D-{u}不是一個(gè)連通支配集，則稱D為圖G的極小連通支配集(MCDS)。

1.3 定義3 極大獨(dú)立集MIS(Maximal Independent Set)

圖 G=(V，E)中，設(shè) U?V，若對(duì)?u，v∈U，(u，v)?E，即點(diǎn)集中任意2個(gè)節(jié)點(diǎn)不相鄰，則稱U為圖G的獨(dú)立集。若對(duì)?u∈V-U，U∪{u}不是一個(gè)獨(dú)立集，則稱U為圖G的極大獨(dú)立集(MIS)。

1.4 定義 4 d-hop CDS［9］

圖 G=(V，E)中，頂點(diǎn)子集 D?V，對(duì)?u∈D，v?D，可以找到一條從u到v跳數(shù)為d的一條通路(或者說(shuō)節(jié)點(diǎn)u和v之間有d-1個(gè)中間節(jié)點(diǎn))，而且由子集D導(dǎo)出的子圖是連通的，則稱頂點(diǎn)子集D為d-hop CDS。特別地，當(dāng)d=1時(shí)，1-hop CDS就是一般意義的CDS。

1.5 定義 5 d-hop 2-連通支配集［22-23］

圖G=(V，E)中，頂點(diǎn)子集D?V，若滿足①D為d-hop CDS;②由子集D導(dǎo)出的子圖是2-連通的，即子集D任意一對(duì)頂點(diǎn)間都存在至少2條點(diǎn)不相同的路徑，則稱頂點(diǎn)子集D為d-hop 2-CDS。

1.6 定義6 割點(diǎn)、塊、葉子塊和塊-割點(diǎn)圖

連通圖G中，若移去某個(gè)頂點(diǎn)u導(dǎo)致圖G不連通，則u稱為割點(diǎn)(Cut-Vertices)。圖G的不含割點(diǎn)的最大連通子圖稱為塊(block)。圖G的僅含一個(gè)割點(diǎn)的連通子圖稱為葉子塊(Leaf Block)。割點(diǎn)示例如圖1所示。明顯地，至少含有3個(gè)頂點(diǎn)的塊是2-連通圖。

圖1 割點(diǎn)的示例圖

塊-割點(diǎn)圖是個(gè)二部圖H，其中一個(gè)部集由G的割點(diǎn)構(gòu)成，另一部集每個(gè)點(diǎn)bi對(duì)應(yīng)于G的一個(gè)塊Bi，vbi作為H的一條邊當(dāng)且僅當(dāng)v∈bi。

2 算法描述

本文總體上分3個(gè)步驟分布式構(gòu)造d-hop 2-CDS:

第1步 每個(gè)節(jié)點(diǎn)給周圍d-hop鄰居泛洪Hello消息，建立d-hop鄰居發(fā)現(xiàn)，收集d-hop范圍的鄰居節(jié)點(diǎn)狀態(tài)信息。根據(jù)收集的信息確定自己著色狀態(tài)，所有節(jié)點(diǎn)確認(rèn)完畢即建立d-hop支配集，即d-hop DS。

第2步 從一個(gè)支配節(jié)點(diǎn)出發(fā)，在(d+1)跳范圍內(nèi)和另一個(gè)支配節(jié)點(diǎn)之間尋找最短路徑，路徑上的節(jié)點(diǎn)作為支配節(jié)點(diǎn)的連接點(diǎn)。每個(gè)支配節(jié)點(diǎn)重復(fù)這一過(guò)程，直至整個(gè)支配集連通。

第3步 對(duì)連通支配集導(dǎo)出的塊-割點(diǎn)圖，若存在葉子塊，在葉子塊和其余塊之間尋找最短路徑，并將路徑節(jié)點(diǎn)擴(kuò)充入連通支配集中。重復(fù)這一過(guò)程，直至塊的個(gè)數(shù)為1。

2.1 d-hop 鄰居發(fā)現(xiàn)

每個(gè)節(jié)點(diǎn)要發(fā)現(xiàn)周圍d-hop鄰居信息，就要先向周圍d-hop范圍的鄰居節(jié)點(diǎn)發(fā)送泛洪的Hello消息。泛洪的過(guò)程如下:

(1)每個(gè)節(jié)點(diǎn)在首輪信息交換時(shí)，向所有一跳鄰居發(fā)送Hello消息。收到消息的節(jié)點(diǎn)將一跳鄰居保存在本節(jié)點(diǎn)的鄰居列表NList中，直至該節(jié)點(diǎn)從所有一跳鄰居處都收到Hello消息。

(2)在第 i∈［2，d］輪的信息交換時(shí)，每個(gè)節(jié)點(diǎn)在廣播Hello消息捎帶(i-1)hop鄰居列表信息。

(3)經(jīng)過(guò)(1)和(2)共d輪的消息交換每個(gè)節(jié)點(diǎn)都可以匯集周圍d-hop范圍的鄰居節(jié)點(diǎn)狀態(tài)信息(包括鄰居的ID和著色狀態(tài)等信息)，這些鄰居信息都保存在該節(jié)點(diǎn)的鄰居列表NList中。

2.2 第1步 構(gòu)造d-hop MIS

節(jié)點(diǎn)用3種顏色(黑色、灰色和白色)來(lái)分別代表3種狀態(tài)。

(1)支配節(jié)點(diǎn)(黑色):支配集的成員

(2)受支配節(jié)點(diǎn)(灰色):被支配節(jié)點(diǎn)支配的節(jié)點(diǎn)

(3)未定狀態(tài)(白色):指空閑或初始的狀態(tài)

節(jié)點(diǎn)的狀態(tài)變化基于以下原則:

原則1 未定狀態(tài)(白色)→受支配節(jié)點(diǎn)狀態(tài)(灰色):如果一個(gè)白色節(jié)點(diǎn)收到一條來(lái)自于黑色節(jié)點(diǎn)v的消息，該白色節(jié)點(diǎn)將自己變?yōu)榛疑?，并成為支配?jié)點(diǎn)v的受支配節(jié)點(diǎn)。

原則2 未定狀態(tài)(白色)→支配節(jié)點(diǎn)狀態(tài)(黑色):如果一個(gè)白色節(jié)點(diǎn)發(fā)現(xiàn)在它及它周圍d-hop的所有白色節(jié)點(diǎn)中，自己擁有最大ID，且這一結(jié)果狀態(tài)維持一個(gè)時(shí)間Iτ。該白色節(jié)點(diǎn)將自己變?yōu)楹谏?/p>

將d-hop 2-CDS算法的第1步具體過(guò)程歸納如下:

算法1:構(gòu)造d-hop簇，所有簇頭構(gòu)成d-hop MIS

(1)計(jì)算并發(fā)現(xiàn)所有節(jié)點(diǎn)的d-hop鄰居，每個(gè)節(jié)點(diǎn)將鄰居信息(包括鄰居ID和著色狀態(tài)等)保存在本節(jié)點(diǎn)鄰居列表中;

(2)初始時(shí)所有節(jié)點(diǎn)都為白色。選擇所有d-hop白色鄰居中有最大ID的白色節(jié)點(diǎn)，將它變?yōu)楹谏?，和該黑色?jié)點(diǎn)相鄰的所有d-hop白色鄰居們皆標(biāo)為灰色。將此黑色節(jié)點(diǎn)加入支配節(jié)點(diǎn)集合D。在這一輪著色中，黑色和灰色構(gòu)成了d-hop Cluster，簇節(jié)點(diǎn)加入集合C，黑色節(jié)點(diǎn)為Clusterhead;

(3)考慮點(diǎn)集合C的所有一跳鄰域中，計(jì)算并發(fā)現(xiàn)擁有最大ID的白色節(jié)點(diǎn)，將之著黑色，同時(shí)將被黑色節(jié)點(diǎn)支配的節(jié)點(diǎn)都著灰色。黑色節(jié)點(diǎn)繼續(xù)加入支配節(jié)點(diǎn)集合D，黑色和灰色也加入集合C。如此不斷擴(kuò)充支配節(jié)點(diǎn)D和簇節(jié)點(diǎn)集合C，直至C為全頂點(diǎn)集合V或者說(shuō)找不到白色節(jié)點(diǎn)為止;

(4)返回獨(dú)立的支配節(jié)點(diǎn)集合D作為d-hop Dominating Set。算法1完畢。

2.3 第2步 構(gòu)造d-hop連通支配集

構(gòu)造d-hop連通支配集的過(guò)程就是將算法1得到的d-hop DS中的支配節(jié)點(diǎn)尋找連接節(jié)點(diǎn)(Connector)連接起來(lái)。支配節(jié)點(diǎn)和連接節(jié)點(diǎn)共同構(gòu)成了 d-hop的 CDS。

每個(gè)黑色簇頭管理和維護(hù)著一個(gè)本地表T，表T用來(lái)記錄到達(dá)另一個(gè)黑色簇頭的路徑。如果一個(gè)黑色簇頭v收到另一個(gè)簇頭w發(fā)來(lái)的INVITE消息，若w沒(méi)有在表T中，這時(shí)將w和INVITE。PathList加入表T中。否則，若表T中已經(jīng)含有w，但是由消息IN-VITE。PathList獲知的v和w之間的新路徑比表T中的老路徑更短，則用更短的新路徑替換老路徑。消息的PathList中的節(jié)點(diǎn)是連接節(jié)點(diǎn)Connector。

算法2:將d-hop獨(dú)立支配集連通起來(lái)

(1)每個(gè)黑色簇頭節(jié)點(diǎn)向周圍(d+1)-hop廣播INVITE消息，消息中包含路徑列表PathList;

(2)從某個(gè)指定簇頭根節(jié)點(diǎn)開始，根據(jù)簇頭本地表T來(lái)構(gòu)建局部最小生成樹，僅向其具有最大 ID的兒子廣播DISTANCE消息(消息中包含父親簇頭生成的局部最小生成樹節(jié)點(diǎn))，當(dāng)兒子簇頭節(jié)點(diǎn)收到DISTANCE消息，繼續(xù)擴(kuò)充最小生成樹(須避免和父親節(jié)點(diǎn)形成環(huán)路)，向具有最大ID的孫子廣播，這一過(guò)程直至DISTANCE消息傳遍全網(wǎng)的簇頭節(jié)點(diǎn)并已無(wú)法擴(kuò)充最小生成樹為止。此時(shí)所有簇頭節(jié)點(diǎn)位于最小生成樹頂點(diǎn)，而連接點(diǎn)位于最小生成樹路徑上;

(3)獲得的連接點(diǎn)加入d-hop CDS集合D中，返回集合D。算法2完畢。

2.4 第3步 擴(kuò)充d-hop 2-連通支配集

由算法的前兩步獲得的d-hop連通支配集為D。第3步對(duì)D導(dǎo)出的塊-割點(diǎn)圖G［D］只要存在葉子塊L，尋找將L和D-L連接的路徑P，P須滿足:(1)該路徑兩端點(diǎn)是L和D-L中，路徑的中間節(jié)點(diǎn)必須是原始網(wǎng)路圖G中非D集合的節(jié)點(diǎn);(2)該路徑是最短的，即中間節(jié)點(diǎn)個(gè)數(shù)最少的路徑。

這里假設(shè)前3步獲得的d-hop連通支配集D導(dǎo)出塊-割點(diǎn)圖為G［D］，對(duì)G［D］塊的個(gè)數(shù)記為B［D］，路徑P的中間節(jié)點(diǎn)集合為I。

算法3 繼續(xù)擴(kuò)充路徑，將d-hop支配集2-連通

(1)采用Depth First Search(DFS)法對(duì) G［D］計(jì)算塊個(gè)數(shù) B［D］;

(2)若B［D］＞1，計(jì)算葉子塊和G［D］中其余部分的最短路徑P，P的中間節(jié)點(diǎn)不屬于D，將P中間節(jié)點(diǎn)集合I擴(kuò)充入D，即 D=D∪I;

(3)重新計(jì)算 B［D］，重復(fù)執(zhí)行上述2)過(guò)程，直至 B［D］=1。返回集合D。算法3完畢。

2.5 d-hop 2-CDS算法實(shí)例展示

在100×100的矩形區(qū)域內(nèi)，隨機(jī)放置100個(gè)傳感器節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)通信半徑為15。對(duì)d=2，3和4，本文算法前兩步獲得2-hop，3-hop和4-hop CDS分別如圖2(a)、2(b)和2(c)所示。這里d-hop CDS被連通為樹狀。

圖2 生成的d-hop CDS示例圖

初始UDG網(wǎng)絡(luò)圖如圖3(a)所示。以d=3為例，運(yùn)行算法的第1和第2步驟可生成3-hop CDS，如圖3(b)和3(c)所示。運(yùn)行第3步可生成3-hop 2-CDS，如圖3(d)所示。

圖3 d-hop 2-CDS算法在各階段后實(shí)例場(chǎng)景圖(以d=3為例)

3 性能評(píng)價(jià)

3.1 算法理論分析

定理1 本文d-hop 2-CDS算法時(shí)間復(fù)雜度為O(d(mn+n2))，其中d為跳數(shù)，m為網(wǎng)絡(luò)圖邊數(shù)，n為網(wǎng)絡(luò)節(jié)點(diǎn)個(gè)數(shù);消息復(fù)雜度為O(d2Δ(mn+n2))，其中Δ為最大節(jié)點(diǎn)度。

證明 事實(shí)上此算法時(shí)間最大消耗在第3步。(1)先考慮算法的前2步構(gòu)造時(shí)間，含有 d-hop或(d+1)-hop的泛洪步驟，雖每個(gè)節(jié)點(diǎn)的泛洪消息是并行的，但由于消息跳數(shù)為d或(d+1)，因此發(fā)送消息的時(shí)間和d成正比。另外，構(gòu)造時(shí)間也和網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量n成正比，這由于在算法第1步(§3.2)每個(gè)節(jié)點(diǎn)須確定自己的著色狀態(tài)，算法第2步(§3.3)每個(gè)距離為(d+1)的支配節(jié)點(diǎn)互連，這兩個(gè)過(guò)程都類似:連續(xù)而非并行。最壞時(shí)間復(fù)雜度發(fā)生在當(dāng)所有節(jié)點(diǎn)以優(yōu)先級(jí)鏈狀遞增排列或遞減排列時(shí)，節(jié)點(diǎn)最大的節(jié)點(diǎn)度為2。此時(shí)，每個(gè)節(jié)點(diǎn)都必須在等所有具有較大優(yōu)先級(jí)的節(jié)點(diǎn)確定之后才能確認(rèn)自己。因此，算法的前兩步時(shí)間復(fù)雜度為O(dn)，其中d為跳數(shù)，n為網(wǎng)絡(luò)節(jié)點(diǎn)個(gè)數(shù)。

(2)在算法第3步，深度優(yōu)先搜索(DFS)塊個(gè)數(shù)的計(jì)算需O(m+n)，m為網(wǎng)絡(luò)圖邊數(shù)。每次循環(huán)中最短路徑計(jì)算需O((2d+1)×n)，因?yàn)樗鶖U(kuò)充的2-連通路徑長(zhǎng)度不超過(guò)(2d+1)。因此算法第3步需O((m+n)(2d+1)n)，可簡(jiǎn)化為 O(d(mn+n2))，綜合(1)(2)得證。

另外，關(guān)于算法的消息數(shù)量的分析，每個(gè)節(jié)點(diǎn)d-hop泛洪消息的數(shù)量是和跳數(shù)d的平方成比例關(guān)系;節(jié)點(diǎn)個(gè)數(shù)n和總泛洪消息數(shù)量成正比;不考慮丟包等通信損失，每個(gè)節(jié)點(diǎn)都的和周圍所有鄰接點(diǎn)交換消息，因此消息代價(jià)還和平均節(jié)點(diǎn)度成正比關(guān)系。綜上前述(1)(2)的循環(huán)次數(shù)分析，算法的消息復(fù)雜度為O(d2Δ(mn+n2))，其中Δ為最大節(jié)點(diǎn)度。

引理 1［24］UDG 圖 G=(V，E)中，定義 I為r-hop IS，對(duì)G中任意一頂點(diǎn) u，|Nr(u)∩I|≤β，其中:

引理2 算法第2步，連通節(jié)點(diǎn)使得所有獨(dú)立支配節(jié)點(diǎn)連通而形成生成樹的頂點(diǎn)，這樣插入的連接節(jié)點(diǎn)個(gè)數(shù)不超過(guò)d(|I|-1)，d為跳數(shù)，I同引理1定義。

證明 算法第2步，將第1步生成的|I|個(gè)節(jié)點(diǎn)組織成生成樹，樹的頂點(diǎn)就是支配節(jié)點(diǎn)，而樹的路徑就是連接節(jié)點(diǎn)。樹的路徑個(gè)數(shù)為|I|-1，由于是最短路徑每條路徑長(zhǎng)度不超過(guò)d，因此，插入的連接節(jié)點(diǎn)個(gè)數(shù)不超過(guò)d(|I|-1)。

引理3［23］算法第3步，插入連通節(jié)點(diǎn)使得算法第2步已連通的d-hop CDS能具有2-Connect性質(zhì)，每次循環(huán)計(jì)算塊個(gè)數(shù)后插入的路徑節(jié)點(diǎn)個(gè)數(shù)不超過(guò)2β+2d，d為跳數(shù)，β同引理1定義。

引理1和引理3證明略，參閱文獻(xiàn)［23-24］。

定理2 本文d-hop 2-CDS算法是一個(gè)(2β+2d+1)(d+1)β的近似算法，這里d為跳數(shù)，β同引理1定義。

證明 令|MCDS|表示G中最小連通支配集內(nèi)頂點(diǎn)的個(gè)數(shù)，OPT(G)表示最優(yōu)d-hop 2-連通支配集中頂點(diǎn)的個(gè)數(shù)，顯然，d-hop 2-連通支配集也是CDS，D，I，D2和D3分別是本算法輸出的d-hop 2-連通支配集，本算法第1步產(chǎn)生的d-hop IS，第2步添加的連接點(diǎn)集合以及第3步再次添加的使2-連通的連接點(diǎn)集合。其中第3步循環(huán)次數(shù)(即塊的個(gè)數(shù))最多|I|+|D2|-1次，則由引理1至引理3，有:

所以，本算法的近似比為:

3.2 算法仿真分析

仿真環(huán)境1:100×100的矩形區(qū)域，傳感器節(jié)點(diǎn)隨機(jī)布置，通信半徑 r=15時(shí)，本文算法產(chǎn)生的 d-hop獨(dú)立支配集和2-連通支配集(d=1，2，3，4)隨節(jié)點(diǎn)個(gè)數(shù) n(n=80，100，150，200，250，300)的變化關(guān)系如圖4(a)和4(b)所示。從圖中可得:隨著d的增大，支配集或連通支配集的大小急劇縮小，即可選取更少的節(jié)點(diǎn)作為虛擬骨干網(wǎng)以支配其余節(jié)點(diǎn)，這驗(yàn)證了支配集的d-hop性質(zhì)可以大大減小支配集節(jié)點(diǎn)數(shù)目。另外，隨著節(jié)點(diǎn)個(gè)數(shù)n的增大，d-hop DS緩慢增加，這是由于節(jié)點(diǎn)密度雖增加，原本的支配節(jié)點(diǎn)依然可支配新增加的大多數(shù)節(jié)點(diǎn)。

圖4 當(dāng)通信半徑r=15時(shí)，隨n的變化關(guān)系

仿真環(huán)境2:100×100的矩形區(qū)域，傳感器節(jié)點(diǎn)隨機(jī)布置，節(jié)點(diǎn)個(gè)數(shù)n=100時(shí)，本文算法產(chǎn)生的d-hop支配集和2-連通支配集(d=1，2，3，4)隨通信半徑 r(r=12，14，15，16，18，20)的變化關(guān)系如圖5(a)、5(b)所示。半徑r增大，平均節(jié)點(diǎn)度增加，網(wǎng)絡(luò)圖也更加密集，支配節(jié)點(diǎn)數(shù)量下降。說(shuō)明在密集網(wǎng)絡(luò)圖中本算法具有較好性能。

圖5 當(dāng)n=100，通信半徑為r時(shí)，隨r的變化關(guān)系

4 結(jié)論

本文提出了基于UDG網(wǎng)絡(luò)模型的d-hop 2-連通支配集的分布式構(gòu)造算法。先構(gòu)造d-hop獨(dú)立支配集，然后連通形成 d-hop連通支配集(d-hop CDS)，最后再次擴(kuò)充路徑形成2-連通集。理論和實(shí)驗(yàn)都表明:d-hop CDS有著比單跳CDS少得多的連通支配節(jié)點(diǎn)個(gè)數(shù)，因而采用d-hop CDS作為虛擬骨干網(wǎng)也就可以大大減少骨干節(jié)點(diǎn)的個(gè)數(shù)，增加了網(wǎng)絡(luò)的可擴(kuò)展性和網(wǎng)絡(luò)容量。另外2-連通的性質(zhì)也可以增加虛擬骨干網(wǎng)容錯(cuò)性和可靠性。下一階段的研究將著重在節(jié)點(diǎn)自由運(yùn)動(dòng)模式下d-hop連通支配集的維護(hù)代價(jià)的探討。

［1］ Garey M R，Johnson D S.Computers and Intractability:A Guide to the Theory of NP-Completeness［M］.New York:W.H.Freeman and Company，1990:71-72.

［2］ Zheng C，Sun S X，Huang T Y.Constructing Distributed Connected Dominating Sets in Wireless Ad Hoc and Sensor Networks［J］.Journal of Software，2011，22(5):1053-1066.

［3］ Yang S H，Wu T，Cao J N.Connected k-Hop Clustering in Ad Hoc Networks［C］//Proceedings of ICPP:2005 International Conference on Parallel Processsing.Oslo，Norway，2005:373-380，649.

［4］ Theoleyre F，Valois F.A Self-Organization Structure for Hybrid Networks［J］.Ad Hoc Networks，2008，6(3):393-407.

［5］ Yang H Y，Lin C H，Tsai M J.Distributed Algorithm for Efficient Construction and Maintenance of Connected k-Hop Dominating Sets in Mobile Ad Hoc Networks［J］.Mobile Computing，2008，7(4):444-457.

［6］ Rieck M，Pai S，Dhar S.Distributed Routing Algorithms for Multi-Hop Ad Hoc Networks Using d-Hop Connected d-Dominating Sets［J］.Computer Networks，2005，47(6):785-799.

［7］ Gao X F，Wang W，Zhang Z，et al.A PTAS for Minimum d-Hop Connected Dominating Set in Growth-Bounded graphs［J］.Optimization Letters，2010，4(3):321-333.

［8］ Janacik P，Kujat A.Biologically-Inspired Construction of Connected k-Hop Dominating Sets in Wireless Sensor Networks［C］//Proceedings of SASO:2009 Third IEEE International Conference on Self-Adaptive and Self-Organizing Systems.San Francisco，California，USA，2009:103-114，294.

［9］ Nguyen T N，Huynh D T.Connected d-Hop Dominating Sets in Mobile Ad Hoc Networks［C］//Proceedings of 2006 4th International Symposium on Modeling and Optimization in Mobile，Ad Hoc and Wireless Networks.2006:138-145，734.

［10］ Das B，Bharghavan V.Routing in Ad-Hoc Networks Using Minimum Connected Dominating Sets［C］//Proceedings of ICC’97:1997 IEEE International Conference on Communications-Towards the Knowledge Millennium.Montreal，1997，1-3:376-380，1743.

［11］ Min M K，Du H W，Jia X H，et al.Improving Construction for Connected Dominating Set With Steiner Tree in Wireless Sensor Networks［J］.Journal of Global Optimization，2006，35(1):111-119.

［12］ 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.

［13］ Alzoubi K M，Wan P J，F(xiàn)rieder O.Message-Optimal Connected Dominating Sets in Mobile Ad Hoc Networks［C］//Proceedings of MOBIHOC.EPFL Lausanne，Switzerland，2002:157-164.

［14］ Adjih C，Jacquet P，Viennot L.Computing Connected Dominated Sets with Multipoint Relays［C］//Proceedings of Ad Hoc ＆ Sensor Wireless Networks(AHSWN)2005:27-39.

［15］ Gerla M，Tsai J T C.Multicluster，Mobile，Multimedia Radio Network［J］.Wireless Networks，1995，1(3):255-265.

［16］ Sausen P S，Spohn M A，Lima A M N，et al.Boundeddistance Multi-Coverage Backbones in Wireless Sensor Networks［C］//Proceedings of SAC:2007 ACM Symposium on Applied Computing.Seoul，Korea，2007:203-208.

［17］付永生，李善平，周波.無(wú)線傳感網(wǎng)絡(luò)中能量均衡的連通支配集算法［J］.傳感技術(shù)學(xué)報(bào)，2010，23(8):1142-1145.

［18］ Dai F，Wu J.On Constructing k-Connected k-Dominating Set in Wireless Networks［C］//Proceedings of Special Issue 19th International Parallel and Distributed Processing Symposium(IPDPS).2005.

［19］ Wu Y，Li Y.Construction Algorithms for k-Connected m-Dominating Sets in Wireless Sensor Networks［C］//Proceedings of MobiHoc’08 Proceedings of the 9th ACM international Symposium on Mobile Ad Hoc Networking and Computing.New York，2008:83-90.

［20］ Liu Z L，Tian F，Xu J M.Probabilistic Analysis of upper Bounds for 2-Connected Distance k-Dominating Sets in Graphs［J］.Theoretical Computer Science，2009，410(38-40):3804-3813.

［21］ Schleich J，Danoy G，Bouvry P，et al.Blackbone2，an Efficient Deterministic Algorithm for Creating 2-Connected m-Dominating Set-Based Backbones in Ad Hoc Networks［C］//Proceedings of the Seventh Acm International Symposium on Mobility Management and Wireless Access，Mobiwac09，2009:91-98.

［22］ Wang F，Thai M T，Du D Z.On the Construction of 2-Connected Virtual Backbone in Wireless Networks［J］.IEEE Transactions on Wireless Communications，2009，8(3):1230-1237.

［23］ Li X Y，Zhang Z.Two Algorithms for Minimum 2-Connected r-Hop Dominating set［J］.Information Processing Letters，2010，110(22):986-991.

［24］ Zahng Z，Liu Q，Li D.Two Algorithms for Connected r-Hop k-Dominating Set ［J］. Discrete Mathematics， Algorithms and Applications，2009，1(4):485-498.