基于連通支配樹的異構(gòu)傳感器網(wǎng)絡(luò)拓撲修復(fù)算法

史庭俊，方旭明，楊云

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

1 引言

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

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

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

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

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

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

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

2 相關(guān)工作

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

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

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

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

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

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

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

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

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

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

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

在異構(gòu)傳感器網(wǎng)絡(luò)模型中，網(wǎng)絡(luò)拓撲使用雙向圓圖來表示，其中實線表示節(jié)點之間的通信鏈路，虛線表示節(jié)點的通信半徑，如圖1所示。

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

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

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

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

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

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

4 HSNTR算法

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

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

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

4.2 執(zhí)行流程

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.3 實現(xiàn)代價

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

5 理論分析

5.1 相關(guān)定理

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

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

定理2 在雙向圓圖中，任一節(jié)點至多相鄰 N個獨立節(jié)點。

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

圖14 k=1時的相鄰節(jié)點分布

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

圖15 k=1時的獨立節(jié)點分布

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

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

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

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

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

5.2 階段1分析

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

證明 設(shè)I是算法中由白色直接染成黑色的節(jié)點集，即不包括由灰色染成黑色的連接節(jié)點。因為算法中的白色節(jié)點都是按照灰色與黑色交替的方式染色的，所以黑色節(jié)點都是不相鄰節(jié)點，即I是獨立集。又因為任一灰色節(jié)點至少有一個黑色相鄰節(jié)點，所以如果任一灰色節(jié)點被染成黑色，那么 I將不再是獨立集，即I是極大獨立集。

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

證明 算法從根節(jié)點開始廣播消息，讓所有的節(jié)點構(gòu)成一棵生成樹。由性質(zhì)1可知，算法構(gòu)造了一個極大獨立集。因為在雙向圓圖中，極大獨立集也是支配集[1]，所以算法構(gòu)造了一個支配集。又因為樹是連通的，所以算法構(gòu)造了一棵連通支配樹。

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

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

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

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

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

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

5.3 階段2分析

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

證明 算法首先喚醒失效節(jié)點的所有休眠的鄰節(jié)點，然后利用它們將所有無法連通的節(jié)點重新連通，并且重新指派它們的父節(jié)點和子節(jié)點。因為所有喚醒的黑色節(jié)點恢復(fù)了樹的連通性，同時確保每個休眠的灰色節(jié)點至少與一個黑色節(jié)點相鄰，所以由算法修復(fù)的樹仍然是一棵連通支配樹。

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

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

圖17 k=1時的連接節(jié)點分布

因為在同一個扇形區(qū)域內(nèi)的所有節(jié)點都相鄰，所以每個扇形區(qū)域內(nèi)至多使用2個節(jié)點就能連通其他區(qū)域。又因為所有增加的連接節(jié)點可以形成一個環(huán)，所以最后2個扇形區(qū)域分別只需使用一個節(jié)點就能與其他的區(qū)域連通。由此可見，當(dāng)k=1時，算法至多使用10個節(jié)點就能修復(fù)連通支配樹。

因為在同一個弧形區(qū)域內(nèi)的所有節(jié)點都相鄰，所以每個弧形區(qū)域內(nèi)至多使用2個節(jié)點就能連通其他區(qū)域。又因為所有增加的連接節(jié)點可以形成一個環(huán)，所以10個半徑為rmin的扇形區(qū)域分別只需使用一個節(jié)點就能與其他的區(qū)域連通。由此可見，當(dāng)k＞1時，算法至多使用個節(jié)點就能修復(fù)連通支配樹。

圖18 k＞1時的連接節(jié)點分布

6 仿真分析

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

1) 能效性分析

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

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

2) 擴展性分析

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

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

3) 可靠性分析

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

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

7 結(jié)束語

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

[1] 孫利民, 李建中, 陳渝. 無線傳感器網(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] 解文斌, 李佳, 鮮明等. 基于拓撲特性的分布式虛擬骨干網(wǎng)算法[J].軟件學(xué)報, 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.