史庭俊，方旭明，楊云

(揚(yáng)州大學(xué) 信息工程學(xué)院，江蘇 揚(yáng)州 225009)

1 引言

無(wú)線傳感器網(wǎng)絡(luò)(WSN, wireless sensor networks)是大量微型傳感器節(jié)點(diǎn)自組形成的多跳通信網(wǎng)絡(luò)。目前，無(wú)線傳感器網(wǎng)絡(luò)已被廣泛應(yīng)用于軍事、安全監(jiān)視、生態(tài)環(huán)境監(jiān)測(cè)、醫(yī)療健康等領(lǐng)域[1]。因?yàn)閼?yīng)用于不同領(lǐng)域的傳感器節(jié)點(diǎn)在感測(cè)能力、計(jì)算能力、通信能力和能量存儲(chǔ)等方面存在著差異，所以由不同類型傳感器節(jié)點(diǎn)組成的網(wǎng)絡(luò)稱為異構(gòu)傳感器網(wǎng)絡(luò)(heterogeneous sensor networks)[2]。相對(duì)于由相同類型傳感器節(jié)點(diǎn)組成的同構(gòu)傳感器網(wǎng)絡(luò)(homogeneous sensor networks)，異構(gòu)傳感器網(wǎng)絡(luò)是一種更加實(shí)際的網(wǎng)絡(luò)模型[3]。

設(shè)計(jì)無(wú)線傳感器網(wǎng)絡(luò)算法的重要目標(biāo)之一是降低網(wǎng)絡(luò)運(yùn)行時(shí)的能量消耗從而延長(zhǎng)網(wǎng)絡(luò)的生命周期[4]。拓?fù)淇刂?TC, topology control)算法是一種減少無(wú)線傳感器網(wǎng)絡(luò)能量消耗的常用方法。拓?fù)淇刂剖侵冈诒ＷC網(wǎng)絡(luò)連通和覆蓋所有節(jié)點(diǎn)的前提下，使大量的節(jié)點(diǎn)進(jìn)入休眠狀態(tài)以節(jié)省能量，只使用少量節(jié)點(diǎn)來(lái)轉(zhuǎn)發(fā)數(shù)據(jù)。目前，在無(wú)線傳感器網(wǎng)絡(luò)的研究中通常使用連通支配集(CDS, connected dominating sets)理論來(lái)實(shí)現(xiàn)這種拓?fù)淇刂芠5]。然而，無(wú)論是在同構(gòu)傳感器網(wǎng)絡(luò)中求解極小連通支配集[6]，還是在異構(gòu)傳感器網(wǎng)絡(luò)中求解極小連通支配集都被證明是一個(gè)NP-hard問(wèn)題[7]。

由于傳感器節(jié)點(diǎn)電池的能量總是有限的且不易被補(bǔ)充，因此節(jié)點(diǎn)失效后會(huì)導(dǎo)致無(wú)線傳感器網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)發(fā)生改變。為了使網(wǎng)絡(luò)保持連通和覆蓋所有節(jié)點(diǎn)的特性，本文提出了一種基于連通支配樹(shù)的異構(gòu)傳感器網(wǎng)絡(luò)拓?fù)湫迯?fù)(HSNTR, heterogeneous sensor network topology restoration)算法。該算法的主要優(yōu)點(diǎn)如下。

1) 與集中式執(zhí)行的算法相比，HSNTR算法采用分布式方式執(zhí)行，只需使用一跳鄰節(jié)點(diǎn)列表而無(wú)需知道節(jié)點(diǎn)的位置信息，因此它具有更好的擴(kuò)展性。

2) 與分布式執(zhí)行的算法相比，HSNTR算法使用更小的消息和時(shí)間復(fù)雜度，因此它具有更好的能效性。

3) 與使用同構(gòu)傳感器網(wǎng)絡(luò)模型的算法相比，HSNTR算法使用異構(gòu)傳感器網(wǎng)絡(luò)模型，因此它具有更好的實(shí)用性。

與使用靜態(tài)全局修復(fù)方式的算法相比，HSNTR算法使用動(dòng)態(tài)局部修復(fù)方式使連通支配樹(shù)恢復(fù)連通和覆蓋所有節(jié)點(diǎn)，因此它具有更好的可靠性。

2 相關(guān)工作

在同構(gòu)傳感器網(wǎng)絡(luò)環(huán)境下構(gòu)造連通支配集的算法主要分成2類。第一類算法分為2個(gè)階段執(zhí)行。算法首先在第一個(gè)階段構(gòu)造一個(gè)極大獨(dú)立集，然后在第二個(gè)階段選擇連接節(jié)點(diǎn)將極大獨(dú)立集連成一個(gè)連通支配集。其中代表性的算法主要有文獻(xiàn)[8]提出的一種基于準(zhǔn)全局信息的生成樹(shù)算法、文獻(xiàn)[9]提出的一種基于節(jié)點(diǎn)度的分布式算法和文獻(xiàn)[10]提出的一種能量高效的 EECDS(energy efficient connected dominating set)算法。第二類算法也分為2個(gè)階段執(zhí)行。算法首先在第一個(gè)階段生成一個(gè)未經(jīng)優(yōu)化的連通支配集，然后在第二個(gè)階段使用修剪規(guī)則去掉冗余的節(jié)點(diǎn)以使連通支配集變得更小。其中代表性的算法主要有文獻(xiàn)[11]提出的一種基于多點(diǎn)中繼的分布式算法、文獻(xiàn)[12]提出的一種基于遞歸的極小連通支配集算法和文獻(xiàn)[13]提出的一種基于修剪規(guī)則的 CDS-Rule-K(connected dominating set under rule k)算法。

EECDS算法在第一個(gè)階段使用染色法構(gòu)造一個(gè)極大獨(dú)立集。初始時(shí)，所有的節(jié)點(diǎn)均為白色節(jié)點(diǎn)。算法選擇一個(gè)白色節(jié)點(diǎn)染成黑色并且廣播黑色消息。當(dāng)白色鄰節(jié)點(diǎn)收到黑色消息時(shí)，它被染成灰色并且廣播灰色消息。當(dāng)白色鄰節(jié)點(diǎn)收到灰色消息時(shí)，它廣播查詢消息以獲取鄰節(jié)點(diǎn)的狀態(tài)與優(yōu)先級(jí)，同時(shí)它還設(shè)置一個(gè)定時(shí)器。如果在定時(shí)器超時(shí)前沒(méi)有收到任何鄰節(jié)點(diǎn)的黑色消息，那么它將染成黑色并且廣播黑色消息，否則它將保持白色。當(dāng)所有的白色節(jié)點(diǎn)都被染成灰色或黑色時(shí)，第一個(gè)階段執(zhí)行結(jié)束，其中所有的黑色節(jié)點(diǎn)構(gòu)成一個(gè)極大獨(dú)立集。算法在第二個(gè)階段使用貪婪方式選擇連接節(jié)點(diǎn)將極大獨(dú)立集連成一個(gè)連通支配集。算法選擇一個(gè)非獨(dú)立節(jié)點(diǎn)染成藍(lán)色并且廣播藍(lán)色消息。當(dāng)獨(dú)立節(jié)點(diǎn)收到藍(lán)色消息時(shí)，它被染成藍(lán)色并且廣播邀請(qǐng)消息。當(dāng)非獨(dú)立節(jié)點(diǎn)收到邀請(qǐng)消息時(shí)，它將計(jì)算優(yōu)先級(jí)并且廣播更新消息。算法選擇優(yōu)先級(jí)最大的非獨(dú)立節(jié)點(diǎn)染成藍(lán)色并且廣播藍(lán)色消息。當(dāng)所有的黑色節(jié)點(diǎn)都被染成藍(lán)色時(shí)，第二個(gè)階段執(zhí)行結(jié)束，其中所有的藍(lán)色節(jié)點(diǎn)構(gòu)成一個(gè)連通支配集。

CDS-Rule-K算法在第一個(gè)階段使用標(biāo)記法來(lái)構(gòu)造一棵沒(méi)有優(yōu)化的連通支配樹(shù)。初始時(shí)，所有的節(jié)點(diǎn)廣播 Hello消息以形成鄰節(jié)點(diǎn)列表并且相互交換列表。如果一個(gè)節(jié)點(diǎn)的鄰節(jié)點(diǎn)沒(méi)有被其他節(jié)點(diǎn)所覆蓋，那么它將被標(biāo)記成連通支配樹(shù)的一個(gè)節(jié)點(diǎn)。算法在第二個(gè)階段使用修剪規(guī)則去掉樹(shù)中冗余的葉子節(jié)點(diǎn)。直到所有冗余的葉子節(jié)點(diǎn)都被去掉之后，算法才會(huì)得到一棵優(yōu)化的連通支配樹(shù)。

DLEDSR(dynamic local energy and DSR based repair)算法是一種基于同構(gòu)傳感器網(wǎng)絡(luò)模型的拓?fù)湫迯?fù)算法[14]。當(dāng)一個(gè)節(jié)點(diǎn)的能量低于算法規(guī)定的最小能量閾值時(shí)，它將向所有休眠的鄰節(jié)點(diǎn)廣播喚醒消息，以使它們進(jìn)入復(fù)蘇狀態(tài)，同時(shí)這些復(fù)蘇節(jié)點(diǎn)也會(huì)向鄰節(jié)點(diǎn)廣播喚醒消息。當(dāng)失效節(jié)點(diǎn)復(fù)蘇鄰節(jié)點(diǎn)的子節(jié)點(diǎn)收到喚醒消息時(shí)，它們會(huì)向其子節(jié)點(diǎn)廣播喚醒消息，以使它們進(jìn)入復(fù)蘇狀態(tài)。當(dāng)失效節(jié)點(diǎn)復(fù)蘇鄰節(jié)點(diǎn)的父節(jié)點(diǎn)收到喚醒消息時(shí)，它們會(huì)向其子節(jié)點(diǎn)和父節(jié)點(diǎn)廣播喚醒消息，以使它們進(jìn)入復(fù)蘇狀態(tài)。當(dāng)失效節(jié)點(diǎn)復(fù)蘇鄰節(jié)點(diǎn)的祖父節(jié)點(diǎn)收到喚醒消息時(shí)，它們會(huì)向其子節(jié)點(diǎn)廣播喚醒消息，以使它們進(jìn)入復(fù)蘇狀態(tài)。當(dāng)算法的廣播周期結(jié)束時(shí)，所有距離失效節(jié)點(diǎn)的兩跳子節(jié)點(diǎn)和三跳父節(jié)點(diǎn)都已處于復(fù)蘇狀態(tài)。由于該算法在修復(fù)網(wǎng)絡(luò)拓?fù)涞倪^(guò)程中發(fā)送大量消息會(huì)產(chǎn)生通信擁塞和能量浪費(fèi)，因此它不適合運(yùn)行于規(guī)模很大、能量有限的無(wú)線傳感器網(wǎng)絡(luò)環(huán)境。

3 相關(guān)概念與網(wǎng)絡(luò)模型

定義1 若圖G為簡(jiǎn)單連通圖，當(dāng)且僅當(dāng)圖G同時(shí)滿足以下條件：1) 任意1個(gè)節(jié)點(diǎn)沒(méi)有環(huán)；2) 任意2個(gè)節(jié)點(diǎn)之間至少存在1條通路。

定義2 設(shè)圖G為簡(jiǎn)單連通圖，所有節(jié)點(diǎn)的通信半徑r∈[rmin, rmax]，如果兩個(gè)節(jié)點(diǎn)u,v之間的距離不大于min(ru, rv)時(shí)，那么節(jié)點(diǎn)u和節(jié)點(diǎn)v之間就存在一條邊，稱圖G為雙向圓圖。其中，rmin是所有節(jié)點(diǎn)中最小的通信半徑，rmax是所有節(jié)點(diǎn)中最大的通信半徑，min( )是求解最小值的函數(shù)。

定義 3 設(shè)圖 G=(V,E)為雙向圓圖，如果節(jié)點(diǎn)u, v∈V且(u, v)∈E，即節(jié)點(diǎn)u和節(jié)點(diǎn)v在圖G中存在一條邊，那么稱節(jié)點(diǎn)u和節(jié)點(diǎn)v是相鄰節(jié)點(diǎn)。其中，V表示頂點(diǎn)集，E表示邊集。

定義4 設(shè)圖G=(V,E)為雙向圓圖，如果節(jié)點(diǎn)集U?V且?u, v∈U?(u, v)?E，即U中的任意2個(gè)節(jié)點(diǎn)互不相鄰，那么稱節(jié)點(diǎn)集U為圖G的獨(dú)立集，稱節(jié)點(diǎn)集U中的節(jié)點(diǎn)為獨(dú)立節(jié)點(diǎn)。如果?u∈(VU) ?U∪{u}不再是一個(gè)獨(dú)立集，那么稱節(jié)點(diǎn)集U為圖G的極大獨(dú)立集。其中，V表示頂點(diǎn)集，E表示邊集。

定義5 設(shè)圖G=(V,E)為雙向圓圖，如果節(jié)點(diǎn)集 D?V 且?u∈(V－D)?(?v∈D∧(u,v)∈E)，即不在D中的任一節(jié)點(diǎn)至少與D中一個(gè)節(jié)點(diǎn)相鄰，那么稱節(jié)點(diǎn)集D為圖G的支配集。如果圖G能由節(jié)點(diǎn)集D導(dǎo)出一個(gè)連通子圖，那么稱節(jié)點(diǎn)集D為圖G的連通支配集。其中，V表示頂點(diǎn)集，E表示邊集。

定義 6 設(shè)圖 G=(V,E)為雙向圓圖，VT?V，ET?E，如果 T=(VT,ET)是圖 G由節(jié)點(diǎn)集 VT導(dǎo)出的一棵生成樹(shù)，并且節(jié)點(diǎn)集VT是圖G的連通支配集，那么稱T為圖G的連通支配樹(shù)。其中，V表示頂點(diǎn)集，E表示邊集。

在異構(gòu)傳感器網(wǎng)絡(luò)模型中，網(wǎng)絡(luò)拓?fù)涫褂秒p向圓圖來(lái)表示，其中實(shí)線表示節(jié)點(diǎn)之間的通信鏈路，虛線表示節(jié)點(diǎn)的通信半徑，如圖1所示。

圖1 異構(gòu)傳感器網(wǎng)絡(luò)模型

異構(gòu)傳感器網(wǎng)絡(luò)模型具有如下性質(zhì)。

1) 網(wǎng)絡(luò)在完成部署以后所有的節(jié)點(diǎn)會(huì)自組地形成一個(gè)多跳通信網(wǎng)絡(luò)。

2) 網(wǎng)絡(luò)中的節(jié)點(diǎn)可以具有不同的通信半徑和初始能量。

3) 網(wǎng)絡(luò)中的所有節(jié)點(diǎn)都有一個(gè)全向天線以使它們的通信區(qū)域呈現(xiàn)圓形。

4) 網(wǎng)絡(luò)中能通信的節(jié)點(diǎn)之間的距離必定不超過(guò)它們的通信半徑。

4 HSNTR算法

4.1 選擇標(biāo)準(zhǔn)

算法優(yōu)先選擇剩余能量多、通信半徑大的節(jié)點(diǎn)成為骨干節(jié)點(diǎn)。每個(gè)節(jié)點(diǎn)的優(yōu)先級(jí)不是通過(guò)排序運(yùn)算得到的，而是通過(guò)在每個(gè)節(jié)點(diǎn)設(shè)置一個(gè)定時(shí)器來(lái)實(shí)現(xiàn)的。算法將節(jié)點(diǎn)的優(yōu)先級(jí)設(shè)置成定時(shí)器的倒數(shù)，這樣定時(shí)器的值越小就代表節(jié)點(diǎn)的優(yōu)先級(jí)越大，如式(1)所示。

其中，Tu表示節(jié)點(diǎn)u定時(shí)器的值，Tcon表示一個(gè)的時(shí)間常量。a和b分別表示剩余能量和通信半徑的權(quán)重因子。根據(jù)不同網(wǎng)絡(luò)的應(yīng)用需求，可以通過(guò)改變權(quán)重因子來(lái)配置網(wǎng)絡(luò)。如果a大于b，那么骨干節(jié)點(diǎn)的剩余能量會(huì)更多，否則骨干節(jié)點(diǎn)的通信半徑會(huì)更大。Eu表示節(jié)點(diǎn)u的剩余能量，Einit表示節(jié)點(diǎn)的初始能量。Ru表示節(jié)點(diǎn)u當(dāng)前使用的通信半徑，Rmax表示節(jié)點(diǎn)可以使用的最大通信半徑。

4.2 執(zhí)行流程

算法首先在第一個(gè)階段使用染色法、標(biāo)記法和生成樹(shù)技術(shù)構(gòu)造一棵連通支配樹(shù)，同時(shí)使用修剪規(guī)則去掉樹(shù)中冗余的葉子節(jié)點(diǎn)，然后在第二個(gè)階段修復(fù)因節(jié)點(diǎn)失效而拓?fù)涓淖兊倪B通支配樹(shù)。修剪規(guī)則的定義是如果一個(gè)節(jié)點(diǎn)的所有鄰節(jié)點(diǎn)已被它的所有兄弟節(jié)點(diǎn)覆蓋，那么該節(jié)點(diǎn)就是一個(gè)冗余的葉子節(jié)點(diǎn)。算法規(guī)定，如果未標(biāo)記的白色節(jié)點(diǎn)第一次收到應(yīng)答消息，那么它將被標(biāo)記為應(yīng)答節(jié)點(diǎn)的子節(jié)點(diǎn)。

階段1（構(gòu)造連通支配樹(shù)）

步驟 1 算法初始化時(shí)，網(wǎng)絡(luò)中所有的節(jié)點(diǎn)都是未標(biāo)記的白色節(jié)點(diǎn)，如圖2所示。

圖2 步驟1執(zhí)行后的示例

步驟 2 算法首先選擇一個(gè)白色節(jié)點(diǎn)作為連通支配樹(shù)的根節(jié)點(diǎn)，然后這個(gè)節(jié)點(diǎn)被標(biāo)記為黑色節(jié)點(diǎn)，并且廣播黑色消息，如圖3所示。

圖3 步驟2執(zhí)行后的示例

步驟 3 當(dāng)未標(biāo)記的白色節(jié)點(diǎn)收到黑色應(yīng)答消息時(shí)，它將被標(biāo)記為灰色節(jié)點(diǎn)，并且廣播灰色消息，如圖4所示。

圖4 步驟3執(zhí)行后的示例

步驟 4 當(dāng)未標(biāo)記的白色節(jié)點(diǎn)收到灰色應(yīng)答消息時(shí)，它將根據(jù)優(yōu)先級(jí)的計(jì)算公式設(shè)置定時(shí)器的值。如果它在定時(shí)結(jié)束前收到來(lái)自兄弟節(jié)點(diǎn)的黑色消息，那么它將被標(biāo)記為灰色節(jié)點(diǎn)，并且廣播灰色消息，否則它將被標(biāo)記為黑色節(jié)點(diǎn)，并且廣播黑色消息，如圖5所示。

圖5 步驟4執(zhí)行后的示例

步驟 5 當(dāng)灰色節(jié)點(diǎn)收到來(lái)自子節(jié)點(diǎn)的黑色消息時(shí)，它將被標(biāo)記為黑色節(jié)點(diǎn)，并且廣播黑色消息，如圖6所示。

圖6 步驟5執(zhí)行后的示例

步驟 6 當(dāng)黑色節(jié)點(diǎn)沒(méi)有任何一個(gè)子節(jié)點(diǎn)時(shí)，它將被標(biāo)記為灰色節(jié)點(diǎn)，并且廣播灰色消息，如圖7所示。

圖7 步驟6執(zhí)行后的示例

步驟 7 當(dāng)所有的白色節(jié)點(diǎn)都被標(biāo)記為灰色或黑色節(jié)點(diǎn)時(shí)，算法的階段1執(zhí)行結(jié)束。其中，所有的黑色節(jié)點(diǎn)構(gòu)成一棵連通支配樹(shù)，如圖8所示。

圖8 步驟7執(zhí)行后的示例

階段2（修復(fù)連通支配樹(shù)）

步驟 1 當(dāng)黑色節(jié)點(diǎn)失效時(shí)，它將廣播喚醒消息。所有的灰色鄰節(jié)點(diǎn)被標(biāo)記為深灰色節(jié)點(diǎn)，并且廣播深灰色消息，如圖9所示。

圖9 步驟1執(zhí)行后的示例

步驟2 當(dāng)深灰色節(jié)點(diǎn)收到2個(gè)不能連通的黑色節(jié)點(diǎn)廣播的消息時(shí)，它將代替失效節(jié)點(diǎn)成為這 2個(gè)黑色節(jié)點(diǎn)的父節(jié)點(diǎn)和子節(jié)點(diǎn)，同時(shí)它被標(biāo)記為黑色節(jié)點(diǎn)，并且廣播黑色消息，如圖10所示。

圖10 步驟2執(zhí)行后的示例

步驟3 當(dāng)深灰色節(jié)點(diǎn)收到2個(gè)不能連通的黑色和深灰色節(jié)點(diǎn)廣播的消息時(shí)，它將成為黑色節(jié)點(diǎn)的子節(jié)點(diǎn)和深灰色節(jié)點(diǎn)的父節(jié)點(diǎn)，同時(shí)它被標(biāo)記為黑色節(jié)點(diǎn)，并且廣播黑色消息，如圖11所示。

圖11 步驟3執(zhí)行后的示例

步驟4 當(dāng)深灰色節(jié)點(diǎn)收到2個(gè)不能連通的深灰色節(jié)點(diǎn)廣播的消息時(shí)，它將成為已經(jīng)有父節(jié)點(diǎn)的節(jié)點(diǎn)的子節(jié)點(diǎn)和還沒(méi)有父節(jié)點(diǎn)的節(jié)點(diǎn)的父節(jié)點(diǎn)，同時(shí)它被標(biāo)記為黑色節(jié)點(diǎn)，并且廣播黑色消息，如圖12所示。

圖12 步驟4執(zhí)行后的示例

步驟5 當(dāng)深灰色節(jié)點(diǎn)沒(méi)有任何一個(gè)子節(jié)點(diǎn)時(shí)，它將被標(biāo)記為灰色節(jié)點(diǎn)，并且廣播灰色消息，如圖13所示。

圖13 步驟5執(zhí)行后的示例

步驟 6 當(dāng)所有的深灰色節(jié)點(diǎn)都被標(biāo)記為灰色或黑色節(jié)點(diǎn)時(shí)，算法的階段2執(zhí)行結(jié)束。其中，所有的黑色節(jié)點(diǎn)構(gòu)成一棵新的連通支配樹(shù)。

4.3 實(shí)現(xiàn)代價(jià)

由于網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)在執(zhí)行HSNTR算法時(shí)至多廣播6條消息，因此，有n個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)至多廣播 6n條消息，即 HSNTR算法的消息復(fù)雜度為O(n)。又由于 HSNTR算法在每個(gè)節(jié)點(diǎn)運(yùn)行的時(shí)間復(fù)雜度為O(1)，因此，HSNTR算法在有n個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)中運(yùn)行的時(shí)間復(fù)雜度為O(n)。

5 理論分析

5.1 相關(guān)定理

定理1 節(jié)點(diǎn)v1和節(jié)點(diǎn)v2是節(jié)點(diǎn)u在雙向圓圖中的2個(gè)相鄰節(jié)點(diǎn)，如果d(u,v1)≤d(u,v2)且d(v1,v2)≤d(u,v1)，那么節(jié)點(diǎn)v1和節(jié)點(diǎn)v2也是相鄰節(jié)點(diǎn)。其中，d( )是求解2個(gè)節(jié)點(diǎn)之間距離的函數(shù)。

證明 因?yàn)楣?jié)點(diǎn)v1是節(jié)點(diǎn)u在雙向圓圖中的相鄰節(jié)點(diǎn)，所以節(jié)點(diǎn)v1的通信半徑rv1≥d(u,v1)。同理，節(jié)點(diǎn)v2的通信半徑rv2≥d(u,v2)。又因?yàn)閐(v1,v2)≤d(u,v1)且 d(u,v1)≤d(u,v2)，所以 d(v1,v2)≤rv1且 d(v1,v2)≤rv2，即節(jié)點(diǎn)v1和節(jié)點(diǎn)v2在雙向圓圖中是相鄰節(jié)點(diǎn)。

定理2 在雙向圓圖中，任一節(jié)點(diǎn)至多相鄰 N個(gè)獨(dú)立節(jié)點(diǎn)。

證明 設(shè)任一節(jié)點(diǎn)u至多相鄰N個(gè)獨(dú)立節(jié)點(diǎn)，當(dāng)節(jié)點(diǎn)u所有的獨(dú)立節(jié)點(diǎn)都趨向于兩兩相鄰時(shí)，N將接近于最大極限。

圖14 k=1時(shí)的相鄰節(jié)點(diǎn)分布

當(dāng)k=1時(shí)，假設(shè)v1,…,v6分別是與節(jié)點(diǎn)u相鄰的獨(dú)立節(jié)點(diǎn)，如圖 1所示。因?yàn)槿切?v1uv2是等邊三角形，所以 d(u,v1)=d(u,v2)=d(v1,v2)。由定理 1可知，節(jié)點(diǎn)v1和節(jié)點(diǎn)v2是相鄰節(jié)點(diǎn)，與它們是獨(dú)立節(jié)點(diǎn)相矛盾，所以節(jié)點(diǎn)u至多相鄰5個(gè)獨(dú)立節(jié)點(diǎn)，如圖15所示。

圖15 k=1時(shí)的獨(dú)立節(jié)點(diǎn)分布

當(dāng)k＞1時(shí)，假設(shè)v1,…,vj分別是與節(jié)點(diǎn)u相鄰的獨(dú)立節(jié)點(diǎn)，如圖16所示。

圖16 k＞1時(shí)的相鄰區(qū)域分布

因?yàn)閐(u,v1)=d(v1,v2)且∠v1uv2=α，所以d(u,v2)=rmin×2×cosα。同理可得，第j個(gè)節(jié)點(diǎn)與節(jié)點(diǎn)u的距離d(u,vj)=rmin×(2×cosα)j。又因?yàn)閞min(2×cosα)j≤rmax，所以由定理1可知，節(jié)點(diǎn)u在以α為弧度的扇形區(qū)域中至多存在 j個(gè)獨(dú)立節(jié)點(diǎn)。又因?yàn)檎麄€(gè)圓形區(qū)域至多被劃分成個(gè)扇形區(qū)域，所以節(jié)點(diǎn)u在整個(gè)圓形區(qū)域內(nèi)至多存在個(gè)獨(dú)立節(jié)點(diǎn)。令，其中，k是一個(gè)大于 1的常數(shù)，。當(dāng)時(shí)，f(α)取得極值所以節(jié)點(diǎn) u至多相鄰個(gè)獨(dú)立節(jié)點(diǎn)。

定理 3 在雙向圓圖中，任何一個(gè)極大獨(dú)立集中的節(jié)點(diǎn)個(gè)數(shù)都不超過(guò)N×|MCDS|。

證明 設(shè)I是雙向圓圖的極大獨(dú)立集，MCDS是雙向圓圖的極小連通支配集。由定理2可知，在雙向圓圖中，任一節(jié)點(diǎn)至多相鄰N個(gè)獨(dú)立節(jié)點(diǎn)，因此極大獨(dú)立集中的節(jié)點(diǎn)個(gè)數(shù)至多是極小連通支配集中的節(jié)點(diǎn)個(gè)數(shù)的N倍，即|I|≤N×|MCDS|。

5.2 階段1分析

性質(zhì)1 在 HSNTR算法中，由白色直接染成黑色的節(jié)點(diǎn)集是極大獨(dú)立集。

證明 設(shè)I是算法中由白色直接染成黑色的節(jié)點(diǎn)集，即不包括由灰色染成黑色的連接節(jié)點(diǎn)。因?yàn)樗惴ㄖ械陌咨?jié)點(diǎn)都是按照灰色與黑色交替的方式染色的，所以黑色節(jié)點(diǎn)都是不相鄰節(jié)點(diǎn)，即I是獨(dú)立集。又因?yàn)槿我换疑?jié)點(diǎn)至少有一個(gè)黑色相鄰節(jié)點(diǎn)，所以如果任一灰色節(jié)點(diǎn)被染成黑色，那么 I將不再是獨(dú)立集，即I是極大獨(dú)立集。

性質(zhì)2 由HSNTR算法生成的樹(shù)是連通支配樹(shù)。

證明 算法從根節(jié)點(diǎn)開(kāi)始廣播消息，讓所有的節(jié)點(diǎn)構(gòu)成一棵生成樹(shù)。由性質(zhì)1可知，算法構(gòu)造了一個(gè)極大獨(dú)立集。因?yàn)樵陔p向圓圖中，極大獨(dú)立集也是支配集[1]，所以算法構(gòu)造了一個(gè)支配集。又因?yàn)闃?shù)是連通的，所以算法構(gòu)造了一棵連通支配樹(shù)。

性質(zhì)3 由 HSNTR算法選擇的連接節(jié)點(diǎn)至少相鄰2個(gè)獨(dú)立節(jié)點(diǎn)。

證明 在算法中，獨(dú)立節(jié)點(diǎn)的所有白色鄰節(jié)點(diǎn)都被標(biāo)記為灰色節(jié)點(diǎn)。當(dāng)灰色節(jié)點(diǎn)存在一個(gè)獨(dú)立的子節(jié)點(diǎn)時(shí)，它將被標(biāo)記為黑色節(jié)點(diǎn)，即它被選為連接節(jié)點(diǎn)。因此，由算法選擇的連接節(jié)點(diǎn)至少相鄰 2個(gè)獨(dú)立節(jié)點(diǎn)。

性質(zhì) 4 由 HSNTR算法選擇的連接節(jié)點(diǎn)不超過(guò)N×|MCDS|-1。

證明 設(shè)I是由算法構(gòu)造的極大獨(dú)立集，C是由算法選擇的連接節(jié)點(diǎn)集，T是由算法生成的連通支配樹(shù)。由性質(zhì)3可知，任一連接節(jié)點(diǎn)至少相鄰2個(gè)獨(dú)立節(jié)點(diǎn)，因此當(dāng)T中的所有節(jié)點(diǎn)排成一條直線時(shí)連接節(jié)點(diǎn)達(dá)到最多，即|C|=|I|-1。由定理3可知，|I|≤N×|MCDS|，因此|C|≤N×|MCDS|-1。

性質(zhì)5 由 HSNTR算法生成的連通支配樹(shù)中的節(jié)點(diǎn)不超過(guò)2N×|MCDS|-1。

證明 由性質(zhì)1和定理3可知，由算法構(gòu)造的極大獨(dú)立集中的節(jié)點(diǎn)不超過(guò) N×|MCDS|。由性質(zhì) 4可知，由算法選擇的連接節(jié)點(diǎn)不超過(guò)N×|MCDS|-1。由性質(zhì)2可知，由算法生成的樹(shù)是連通支配樹(shù)，因此由算法生成的連通支配樹(shù)中的節(jié)點(diǎn)不超過(guò)2×N×|MCDS|-1。

5.3 階段2分析

性質(zhì) 6 由HSNTR算法修復(fù)的樹(shù)仍是連通支配樹(shù)。

證明 算法首先喚醒失效節(jié)點(diǎn)的所有休眠的鄰節(jié)點(diǎn)，然后利用它們將所有無(wú)法連通的節(jié)點(diǎn)重新連通，并且重新指派它們的父節(jié)點(diǎn)和子節(jié)點(diǎn)。因?yàn)樗袉拘训暮谏?jié)點(diǎn)恢復(fù)了樹(shù)的連通性，同時(shí)確保每個(gè)休眠的灰色節(jié)點(diǎn)至少與一個(gè)黑色節(jié)點(diǎn)相鄰，所以由算法修復(fù)的樹(shù)仍然是一棵連通支配樹(shù)。

性質(zhì) 7 由HSNTR算法修復(fù)的連通支配樹(shù)至多增加M個(gè)節(jié)點(diǎn)。

證明 當(dāng)k=1時(shí)，由定理2可知，失效節(jié)點(diǎn)u至多使用6個(gè)扇形區(qū)域中的節(jié)點(diǎn)就能連通所有鄰節(jié)點(diǎn)，如圖17所示。

圖17 k=1時(shí)的連接節(jié)點(diǎn)分布

因?yàn)樵谕粋€(gè)扇形區(qū)域內(nèi)的所有節(jié)點(diǎn)都相鄰，所以每個(gè)扇形區(qū)域內(nèi)至多使用2個(gè)節(jié)點(diǎn)就能連通其他區(qū)域。又因?yàn)樗性黾拥倪B接節(jié)點(diǎn)可以形成一個(gè)環(huán)，所以最后2個(gè)扇形區(qū)域分別只需使用一個(gè)節(jié)點(diǎn)就能與其他的區(qū)域連通。由此可見(jiàn)，當(dāng)k=1時(shí)，算法至多使用10個(gè)節(jié)點(diǎn)就能修復(fù)連通支配樹(shù)。

因?yàn)樵谕粋€(gè)弧形區(qū)域內(nèi)的所有節(jié)點(diǎn)都相鄰，所以每個(gè)弧形區(qū)域內(nèi)至多使用2個(gè)節(jié)點(diǎn)就能連通其他區(qū)域。又因?yàn)樗性黾拥倪B接節(jié)點(diǎn)可以形成一個(gè)環(huán)，所以10個(gè)半徑為rmin的扇形區(qū)域分別只需使用一個(gè)節(jié)點(diǎn)就能與其他的區(qū)域連通。由此可見(jiàn)，當(dāng)k＞1時(shí)，算法至多使用個(gè)節(jié)點(diǎn)就能修復(fù)連通支配樹(shù)。

圖18 k＞1時(shí)的連接節(jié)點(diǎn)分布

6 仿真分析

本文使用一種面向無(wú)線傳感器網(wǎng)絡(luò)的拓?fù)淇刂品抡婀ぞ逜tarraya對(duì)不同算法進(jìn)行了性能仿真。仿真假設(shè)無(wú)線傳感器網(wǎng)絡(luò)中所有的節(jié)點(diǎn)都被均勻地散布在一個(gè)200m×200m的正方形區(qū)域內(nèi)，并且每個(gè)節(jié)點(diǎn)的最大通信半徑為50m。為了觀察不同算法之間的性能差異，仿真中的節(jié)點(diǎn)總數(shù)分別取為20、40、60、80和 100。仿真首先在不同的節(jié)點(diǎn)總數(shù)處分別生成 50種網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，然后在每種網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)處重復(fù)執(zhí)行3次算法，最后將平均值作為仿真的最終結(jié)果。如果隨機(jī)生成的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)不是連通的，那么仿真將重新生成一個(gè)新的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，直到這個(gè)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)連通為止。對(duì)算法性能的仿真分析如下所述：

1) 能效性分析

如圖 19所示，雖然不同的算法在不同的節(jié)點(diǎn)總數(shù)處構(gòu)造骨干網(wǎng)時(shí)消耗的能量都在增大，但是HSNTR算法比其他算法消耗的能量要小得多，這表明HSNTR算法的能量使用效率要更加高效。

圖19 消耗能量隨節(jié)點(diǎn)總數(shù)變化的曲線

2) 擴(kuò)展性分析

如圖 20所示，雖然不同的算法在不同的節(jié)點(diǎn)總數(shù)處構(gòu)造骨干網(wǎng)時(shí)發(fā)送的消息總數(shù)都在增多，但是HSNTR算法比其他算法發(fā)送的消息總數(shù)要少得多，并且還呈現(xiàn)出了非常緩慢地線性增長(zhǎng)趨勢(shì)，這表明HSNTR算法更能滿足無(wú)線傳感器網(wǎng)絡(luò)規(guī)模不斷擴(kuò)大拓展的應(yīng)用需求。

圖20 發(fā)送消息隨節(jié)點(diǎn)總數(shù)變化的曲線

3) 可靠性分析

如圖 21所示，不同的算法在不同的節(jié)點(diǎn)總數(shù)處保持網(wǎng)絡(luò)連通和覆蓋所有節(jié)點(diǎn)的時(shí)間都在變長(zhǎng)，但是HSNTR算法比其他算法保持網(wǎng)絡(luò)運(yùn)行的時(shí)間要長(zhǎng)，這表明HSNTR算法能夠在節(jié)點(diǎn)失效的情況下使得網(wǎng)絡(luò)更加可靠地運(yùn)行。

圖21 網(wǎng)絡(luò)壽命隨節(jié)點(diǎn)總數(shù)變化的曲線

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

本文在異構(gòu)傳感器網(wǎng)絡(luò)模型的基礎(chǔ)上提出了一種基于連通支配樹(shù)的拓?fù)湫迯?fù)算法。由于算法使用定時(shí)器對(duì)競(jìng)爭(zhēng)骨干的節(jié)點(diǎn)進(jìn)行排序，因此節(jié)點(diǎn)避免了排序算法從而減少了大量的計(jì)算能耗。又由于算法只要發(fā)送很少的消息就能構(gòu)造和修復(fù)虛擬骨干網(wǎng)，因此節(jié)點(diǎn)避免了網(wǎng)絡(luò)風(fēng)暴從而減少了大量的通信能耗。本文分析了算法在構(gòu)造和修復(fù)骨干網(wǎng)的過(guò)程中具有的一些性質(zhì)。最后，仿真顯示出算法在能效性、擴(kuò)展性和可靠性方面的優(yōu)越性。由于移動(dòng)的節(jié)點(diǎn)可能使得網(wǎng)絡(luò)不再連通，因此下一步的工作是利用圖論中的支配吸收集理論和有向圓圖對(duì)移動(dòng)傳感器網(wǎng)絡(luò)的拓?fù)淇刂扑惴ㄟM(jìn)行研究。

[1] 孫利民, 李建中, 陳渝. 無(wú)線傳感器網(wǎng)絡(luò)[M]. 北京: 清華大學(xué)出版社, 2005.SUN L M, LI J Z, CHUN Y. Wireless Sensor Networks[M]. Beijing:Tsinghua University Press, 2005.

[2] DUARTEMELO E J, LIU M Y. Analysis of energy consumption and lifetime of heterogeneous wireless sensor networks[A]. Proc of the GLOBECOM 2002[C]. New York, USA, 2002. 21-25.

[3] YARVIS M, KUSHALNAGAR N, SINGH H, et al. Exploiting heterogeneity in sensor networks[A]. 24th Annual Joint Conference of the IEEE Computer and Communications Societies(INFOCOM 2005)[C].2005. 878-890.

[4] CHANG J H, TASSIULAS L. Maximum lifetime routing in wireless sensor networks[J]. IEEE/ACM Transactions on Networking, 2004,12(4):609-619.

[5] 解文斌, 李佳, 鮮明等. 基于拓?fù)涮匦缘姆植际教摂M骨干網(wǎng)算法[J].軟件學(xué)報(bào), 2010, 21(6):1416-1425.XIE W B, LI J, XIAN M, et al. Distributed virtue backbone network algorithm based on topology characteristic[J]. Journal of Software,2010, 21(6):1416-1425.

[6] CLACK B N, COLBOURN C J, JOHNSON D S. Unit disk graphs[J].Discrete Mathematics, 1990, 86(13):165-177.

[7] GAREY M R, JOHNSON D S. Computers and Intractability: a guide to the Theory of NP-completeness[M]. New York: Freeman, 1979.

[8] WAN P L, ALZOUBI K M, FRIEDER O. Distributed construction of connected dominating set in wireless ad hoc networks[J]. ACM/ Kluwer Mobile Networks and Applications(MONET), 2004, 6(2): 141-149.

[9] CHENG X, DING M, DU D H, et al. Virtual backbone construction in multihop ad hoc wireless networks[J]. Wireless Communications and Mobile Computing, 2006, 6(2):183-190.

[10] YUAN Y Z, JIA X, YAN X H. Energy efficient distributed connected dominating sets construction in wireless sensor networks[A]. Proceedings of the 2006 ACM International Conference on Communica-tions and Mobile Computing[C]. New York, USA, 2006. 797-802.

[11] WU L, LOU W, DAI F. Extended multipoint relays to determine connected dominating sets in MANETs[J]. IEEE Transactions on Computers, 2006, 55(3):334-347.

[12] BUTENKO S, MURPHEY R, PARDALOS P M. Recent Developments in Cooperative Control and Optimization[M]. Berlin: Springer,2003.

[13] WU J, CARDEI M, DAI F, et al. Extended dominating set and its applications in ad hoc networks using cooperative communication[J].IEEE Transactions on Parallel and Distributed Systems, 2006, 17(8):851-864.

[14] LABRADOR M A, WIGHTMAN P M. Topology Control in Wireless Sensor Networks: with a Companion Simulation Tool for Teaching and Research[M]. Berlin:Springer, 2009.

[15] RAEI H, SARRAM M, ADIBNIYA F, et al. Optimal distributed algorithm for minimum connected dominating sets in wireless sensor networks[A]. Proceedings of the 5th IEEE Int’l Conf on Mobile Ad Hoc and Sensor Systems[C]. Atlanta, GA, 2008. 695-700.