異質(zhì)無線傳感器網(wǎng)絡(luò)虛擬骨干重構(gòu)

何 峰，梁家榮，3，黎昌珍

（1.廣西大學(xué) 計算機(jī)與電子信息學(xué)院，南寧 530004；2.廣西大學(xué) 公共管理學(xué)院，南寧 530004；3.廣西多媒體通信與網(wǎng)絡(luò)技術(shù)重點實驗室，南寧 530004）

0 概述

無線傳感器網(wǎng)絡(luò)（Wireless Sensor Network，WSN）由許多無線結(jié)點組成，這些結(jié)點通常由數(shù)據(jù)處理單元、通信模塊和有限的能源設(shè)備等組成。隨著大規(guī)模集成電路、嵌入傳感器及無線通信技術(shù)的發(fā)展，無線結(jié)點的成本將不斷下降而其性能變得越來越好。同時，無線傳感器結(jié)點一旦有機(jī)地分布在應(yīng)用區(qū)域，它們不需要任何的基礎(chǔ)設(shè)施支撐就能自發(fā)地連接成一個通信網(wǎng)絡(luò)。因此，人們認(rèn)為無線傳感器網(wǎng)絡(luò)將會在下一代互聯(lián)網(wǎng)中起到極為關(guān)鍵的作用，目前已被廣泛地應(yīng)用于災(zāi)難 救援［1］、自動駕駛［2］、環(huán)境監(jiān)測［3］、智能家居［4］等諸多領(lǐng)域。

無線傳感器網(wǎng)絡(luò)的結(jié)點通常是電池供能的，是一個有限的能源供能。這意味著能耗效率是無線傳感器網(wǎng)絡(luò)中一個非常重要的問題。在無線通信中任意兩個傳感器間傳輸數(shù)據(jù)所消耗的能量與它們之間的距離呈超線性增加。為了節(jié)約電池能量，多數(shù)無線傳感器網(wǎng)絡(luò)采用多跳通信而非長距離直接通信模式。然而，多跳通信往往會導(dǎo)致網(wǎng)絡(luò)中增加大量的冗余信息及巨量的無線信號沖突和干擾，進(jìn)而使得結(jié)點消耗能量來轉(zhuǎn)發(fā)這些信息而造成不必要的巨量能耗。此外，網(wǎng)絡(luò)中大量的冗余信息及巨量的無線信號沖突和干擾也容易導(dǎo)致廣播風(fēng)暴問題。針對這個問題，一個有效的辦法是在無線傳感器網(wǎng)絡(luò)中選擇部分結(jié)點來承擔(dān)網(wǎng)絡(luò)的路由通信任務(wù)［5］，這些承擔(dān)路由任務(wù)的結(jié)點稱為虛擬骨干（Virtual Backbone，VB）。

在無線傳感器網(wǎng)絡(luò)中采用較小虛擬骨干承擔(dān)路由任務(wù)，可以產(chǎn)生較少的路由開銷，延長網(wǎng)絡(luò)的壽命。理論上，無線傳感器網(wǎng)絡(luò)的虛擬骨干可以建模為單位圓盤圖的一個連通控制集（Connected Dominating Set，CDS）。傳感器網(wǎng)絡(luò)中的最小虛擬骨干問題就轉(zhuǎn)化成單位圓盤圖的最小連通控制集（Minimal Connected Dominating Set，MCDS）問題。然而，單位圓盤圖的MCDS 問題已被證明是一個NP-hard 問題［6］。研究者們更多的是關(guān)注設(shè)計近似算法求解單位圓盤圖的MCDS 問題以獲得這個問題的次優(yōu)解，通?？刹捎孟率龇椒?gòu)造一個連通控制集：1）構(gòu)造一個極大獨立集；2）在極大獨立集中添加結(jié)點使得它是一個連通控制集。因此，為了獲得更小的連通控制集，一部分研究者考慮如何構(gòu)造更小的極大獨立集［7-9］，也有一部分研究者考慮如何在方法2）中添加更少的點［10-12］。

在實際應(yīng)用中，并非所有的無線傳感器網(wǎng)絡(luò)都是同質(zhì)網(wǎng)絡(luò)，也就是并非每一個傳感器結(jié)點的傳輸半徑都是相同的。在更多的情況下，不同的傳感器結(jié)點有不同的傳輸范圍，如果仍把這樣的無線傳感器網(wǎng)絡(luò)建模成單位圓盤圖，明顯是不合適的。對于這種具有不同傳輸范圍的結(jié)點組成的傳感器網(wǎng)絡(luò)（稱為異質(zhì)傳感器網(wǎng)絡(luò)），使用圓盤圖來抽象更為合適［13］。注意到單位圓盤圖的MCDS 問題是圓盤圖的MCDS 問題的特例，這就意味圓盤圖的MCDS 問題也是一個NP-hard 問題［14］。

在無線傳感器網(wǎng)絡(luò)通信中，由于電池剩余容量減少和自然環(huán)境變化等因素的影響，傳感器結(jié)點之間的直接通信可能會失效，這可能會導(dǎo)致整個網(wǎng)絡(luò)的路由通信不暢甚至癱瘓。因此，在無線傳感器網(wǎng)絡(luò)中如何設(shè)計一個虛擬骨干來承擔(dān)網(wǎng)絡(luò)的路由任務(wù)以應(yīng)對無線結(jié)點故障的影響顯得非常重要。

目前，基于容錯的要求，一些研究者研究了無線傳感器網(wǎng)絡(luò)的容錯虛擬骨干［被建模為(k,m)-CDS，能夠容納至多(k-1)個故障結(jié)點，其中，m≥k≥1］的構(gòu)建問題并取得了一些研究成果。例如：文獻(xiàn)［15］提出一個在圓盤圖中構(gòu)建(3,m)-CDS 的常數(shù)近似算法，其中，m≥3；文獻(xiàn)［16］研究了圓盤圖中最小(4,m)-CDS的構(gòu)建問題，其中，m≥4；文獻(xiàn)［17］研究了圓盤圖中最小(k,m)-CDS 的構(gòu)建問題，其中，m≥k≥1。

然而，在一個給定的無線傳感器網(wǎng)絡(luò)中，盡管構(gòu)建一個(k,m)-CDS 能實現(xiàn)容錯功能，但往往這樣的連通控制集的基數(shù)較大，并且隨著k值的增加而增加［18-19］。為了降低連通控制集的基數(shù)，文獻(xiàn)［20］提出一種稱為連通控制集重構(gòu)的策略，并基于這一策略，對于給定的具有故障結(jié)點的同質(zhì)無線傳感器網(wǎng)絡(luò)，設(shè)計了集中式的近似算法重構(gòu)連通控制集，并獲得了較為理想的效果。然而，文獻(xiàn)［20］策略有兩個不足：一是重構(gòu)的連通控制集只具有結(jié)點容錯性，不具有鏈路容錯性；二是考慮的無線傳感器網(wǎng)絡(luò)是同質(zhì)網(wǎng)絡(luò)。為了進(jìn)一步拓展無線傳感器網(wǎng)絡(luò)虛擬骨干的構(gòu)建理論，需要研究如何在異質(zhì)無線傳感器網(wǎng)絡(luò)中構(gòu)建具有鏈路容錯性的連通控制集，但目前還鮮見這方面的研究成果。

針對文獻(xiàn)［20］策略的兩個不足，本文研究具有鏈路失效的異質(zhì)無線傳感器網(wǎng)絡(luò)的連通控制集重構(gòu)問題，設(shè)計虛擬骨干重構(gòu)近似算法（ZREA22），由該算法重構(gòu)的連通控制集可實現(xiàn)在鏈路失效情況下網(wǎng)絡(luò)路由通信不但不受影響，而且路由通信的開銷不會過多增加。

1 預(yù)備知識

1.1 網(wǎng)絡(luò)模型

假設(shè)一個異質(zhì)無線傳感器網(wǎng)絡(luò)傳輸半徑為r?[rmin,rmax]，其中，rmin、rmax分別表示傳輸范圍最小、最大的結(jié)點的傳輸半徑。對于這樣的一個異質(zhì)無線傳感器網(wǎng)絡(luò)，可以使用一個圓盤圖G=(V,E)來抽象，其中，V表示網(wǎng)絡(luò)中所有傳感器結(jié)點組成的集合，E表示網(wǎng)絡(luò)中所有鏈路組成的集合。對于任意的一對結(jié) 點t和w?V，當(dāng)dist(t,w)≤rt，那 么G=(V,E)中有一條從t指向w的有向邊（dist(t,w)表示rt和rw的歐氏距離）；特別地，當(dāng)dist(t,w)≤min{rt,rw}時，rt和rw之間就有一條雙向邊，記為(t,w)?E。為了討論方便，僅考慮抽象圓盤圖G=(V,E)的邊都是雙向邊的異質(zhì)無線傳感器網(wǎng)絡(luò)的虛擬骨干的重構(gòu)問題，這種抽象圓盤圖G=(V,E)事實上是雙向鏈路圓盤圖（Disk Graph with Bidirectional links，DGB）。一個雙向鏈路圓盤圖示例如圖1 所示。

圖1 雙向鏈路圓盤圖示例Fig.1 Example of a disk graph with bidirectional links

1.2 符號和定義

假設(shè)G=(V,E)表示一個雙向鏈路圓盤圖，S?V，t和w?V。文中用到的一些符號具體如下：

1）G[S]，集合S中的點所產(chǎn)生的誘導(dǎo)子圖。

2）N(w)，頂點w的所有鄰居結(jié)點組成的集合。

3）N[w]，N(w)∪{w}。

4）N[S]，

5）Sopt，圖G的一個最小連通控制集。

6）Iw,d，頂點w的Id。

7）A(S)，N[S]-S。

8）dh(t,w)，頂點t和w之間的最短路徑長度。

9）rmax(rmin)，最大（最小）傳輸半徑。

10）ρ，傳輸半徑比率

文中用到的相關(guān)定義具體如下：

定義1假設(shè)集合S?V，對于任意的頂點u?V-S，均有w?S使得(u,w)?E，那么稱集合S是圖G的一個控制集。

定義2假設(shè)集合S?V，S中任意一對頂點u和w均有(u,w)?E，那么集合S是圖G的一個獨立集。

定義3假設(shè)集合S?V是圖G的一個獨立集，若對于任意的頂點w?V-S均有S∪{w}不是一個獨立集，則稱集合S是圖G的一個極大獨立集。

定義4假設(shè)集合S是圖G的一個極大獨立集，若子圖G[S]是連通的，則稱集合S是圖G的一個連通控制集。

定 義5若對于 任意的(x1,y1),(x2,y2)??2，W(x1,y1)>W(x2,y2)，當(dāng)且僅當(dāng)下述條件之一成立，則函數(shù)W：?2→? 稱為權(quán)函數(shù)，其中，? 表示實數(shù)集，?2表示二維實向量空間：

1）x1>x2。

2）x1=x2且y1>y2。

在本文中，圖G的頂點r的權(quán)函數(shù)定義為W(N(r),Ir,d)。

定義6假設(shè)一個連通圖G=(V,E)中的所有結(jié)點已被染成了白色、紅色、藍(lán)色或者灰色，S?V。若下述任意一個條件成立，則稱G[S]是圖G的一個紅藍(lán)連通分支：

1）集合S中僅包含紅色結(jié)點且G[S]是連通的，同時對于任意的不屬于S的紅色結(jié)點w，G[S∪{w}]是不連通的。

2）集合S中僅包含紅色結(jié)點和藍(lán)色結(jié)點且G[S]是連通的。對于任意的不屬于S的紅色或藍(lán)色結(jié)點w，G[S∪{w}]是不連通的。

為了方便起見，用Cblock表示紅藍(lán)連通分支。

定義7假設(shè)一個連通圖G=(V,E)中的所有結(jié)點已被染成了白色、紅色、藍(lán)色或者灰色，共有k個Cblock：B1,B2,…,Bk，k≥1。若圖G的一條路徑P滿足下述條 件，則 稱P是圖G的一條Ln路徑，其中，n是一個非負(fù)整數(shù)：

1）P的兩個端點屬于集合A，其他結(jié)點不屬于集合A，并且P的不屬于集合A的結(jié)點數(shù)不超過n，其中，

2）P的兩個端點不屬于同一個Cblock。

2 ZREA22 算法

2.1 算法原理

為了更好地理解算法執(zhí)行過程，對其做一個簡短的介紹。在算法準(zhǔn)備階段，對于任意輸入的連通的雙向鏈路圓盤圖G=(V,E)、故障邊集M以及圖G的一個連通控制集C（可通過現(xiàn)有最新且性能最好的算法［21］得到），計算得到圖Gf=(V,Ef)，其中，Ef=E-M。該算法主要分為以下3 個步驟：

1）在圖G中，將集合C和A(C)中的點分別染成紅色和灰色。接著，在圖Gf中計算集合W，一個由圖中所有非C及其鄰居結(jié)點組成的集合，并將W中的點染成白色。選擇一個根結(jié)點，并計算出圖Gf中每個點到根結(jié)點的跳數(shù)，將圖中每個點分層。

2）通過逐層遍歷的方式，在圖GGf[W]中構(gòu)造一個極大獨立集K。將K中所有點染成紅色、K的所有位于子圖GGf[W]中的白色鄰居染成灰色。

3）對于每一層中的點Vi，迭代地選擇一條Ln（1 ≤i≤2）路徑以連接圖中2 個不同的Cblock，同時將Ln路徑的所有中間結(jié)點染成藍(lán)色。重復(fù)執(zhí)行上述操作，直到圖中僅有一個Cblock，它的所有結(jié)點形成圖中重構(gòu)的連通控制集Cr。

2.2 算法流程

為了直觀地展現(xiàn)算法執(zhí)行過程，給出ZREA22算法流程，如圖2 所示。

圖2 ZREA22 算法流程Fig.2 Procedure of the ZREA22 algorithm

2.3 算法偽代碼

算法1ZREA22 算法

3 算法正確性分析

下面證明算法1 的正確性，即通過算法1 可以輸出一個重構(gòu)的連通控制集Cr。

引理1集合K是子圖GGF[W]的一個極大獨立集。

證明為了證明K是子圖GGF[W]的一個極大獨立集，首先證明集合W是一個由圖Gf中所有未被控制的點組成的集合，即集合W中的點均不是集合C中點的鄰居，需要注意的是集合C和M分別是圖G的一個連通控制集和故障邊集，由算法1 的第1 和2 行可知，集合W中的點均不是集合C中任何一個點的鄰居；接著證明集合K是子圖GGF[W]的一個極大獨立集，當(dāng)W=?時討論是沒有意義的，因此考慮當(dāng)W≠?時的情況，根據(jù)算法1 的第7～12 行的循環(huán)可知，任何新加入集合K的點均不是K中其他點的鄰居。因此，K是圖GGF[W]的一個極大獨立集。

定理1集合C∪K是圖Gf的一個控制集。

證明由于C是圖G的一個連通控制集，考慮如下2 種情況：

1）u?W-K，根據(jù)引理1，集合K是圖GGF[W]的一個極大獨立集，一定存在一個頂點v?W使得(u,v)?Ef。

2）u?V-W∪C，由算法1 的第1 和2 行可知，一定存在一個頂點v?C使得(u,v)?Ef。

因此，對于任意的頂點u?C∪K，一定存在一個頂點v?V-C∪K使得(u,v)?Ef，進(jìn)而得到集合C∪K是圖G的一個控制集。

引理2在算法1 的第14～23 行的每次循環(huán)中，對于任意的i?[0,kmax]，子 圖中僅有一個Cblock。

證明由推斷法可得：當(dāng)i=0 時，根據(jù)算法1 的第3 行，根結(jié)點r即為該Cblock，因此該結(jié)論是正確的；當(dāng)i=1 時，如果存在一個由紅色結(jié)點集合S?V1，則S∪{r}是子圖中唯一的Cblock，否則{r}為子圖中唯一的Cblock，因此該結(jié)論也是正確的；假設(shè)當(dāng)i=k時，該結(jié)論是正確的；當(dāng)i=k+1 時，對于該結(jié)論的證明類似于i=1 的情況，因此該結(jié)論也是正確的。

定理2算法1 執(zhí)行結(jié)束后，Cr是圖Gf的一個重構(gòu)的連通控制集。

證明由定理1 可知，C∪K是圖Gf的一個控制集，那么Cr=C∪K∪H也是圖G的一個控制集，因此只須證明Cr是連通的。由引理2 可知，在算法1 的第14～23 行的每次循環(huán)中，對于任意的i?[0,kmax]，子圖中僅有一個CblockT。對于Vi中的每個紅色結(jié)點t，如果T∪{t}不是一個新的Cblock，則圖中一定會存在一條Ln路徑連接t和w?T使得T∪X∪{t}是一個新的Cblock。因此，在第14～23 行的while 循環(huán)結(jié)束后，T∪H一定會是一個新的Cblock，進(jìn)而得到集合T∪H=C∪K∪H是圖Gf的一個重構(gòu)的連通控制集。

4 算法性能分析

本節(jié)給出算法1 的性能分析，包括以下2 個部分：1）算法1 所產(chǎn)生的連通控制集的大小的上界；2）算法1 的時間復(fù)雜度。由算法1 可知，在第12 行執(zhí)行完成后集合包含了圖Gf中所有的紅色結(jié)點。由引理2可知，算法1的第14～23行的每次循環(huán)中子圖中僅有一個CblockT，進(jìn)而得到對于任意的t?Vi∩(C∪K)(2 ≤i≤kmax)，圖Gf中一定會存在一條Ln路徑連接t和v?T。因此，當(dāng)算法的第14～23 行執(zhí)行完成后有|H|≤n|C∪K|≤n(|C|+|K|)。

引理3在算法1 中路徑Ln的中間結(jié)點數(shù)量為n≤2。

證明該結(jié)論的證明與文獻(xiàn)［22］中的引理2.3類似，則該結(jié)論也是正確的。

因此，當(dāng)算法1 的第14～23 行執(zhí)行完成后有|H|≤n(|C|+|K|)≤2(|C|+|K|)。

假 設(shè)M1={(t,w)?M|t,w?C}、M2={(t,w)?Ef|t?C,w?(V-C)}、M3={(t,w)?Ef|t,w?(V-C)}、mi=|Mi| 和m=m1+m2（1 ≤i≤2）。由引理1 可知，集合W是一個由非連通控制集C及其鄰居結(jié)點組成的集合，集合K是由W產(chǎn)生的誘導(dǎo)子圖的極大獨立集。根據(jù)圖論知識可得，|K|≤|W|≤m2。

假設(shè)算法1 中輸入的連通控制集C的大小不超過αSopt+γ，其中，α>0 是原連通控制集的近似比，γ是一個常數(shù)，那么算法1 產(chǎn)生的連通控制集的大小如下：

定理3算法1 能夠輸出一個大小上界為3αSopt+3(γ+m)的連通控制集，其中，α>0 是原虛擬骨干的近似比，γ是一個常數(shù)，m是故障鏈路的數(shù)量，Sopt是最小虛擬骨干的大小。

定理4算法1 的時間復(fù)雜度為O(n3)，其中，n表示算法輸入圖的頂點總數(shù)。

證明在算法1 的第1～5 行中，挑選根結(jié)點、計算集合W和Vk所需的時間為O(n)。在算法1的第7～12行中，在集合W形成的子圖中構(gòu)造一個極大獨立集K需要的時間為O(n2)。在算法第14～23 行的while 循環(huán)中，迭代地尋找唯一的一個CblockT、選擇一條Ln路徑所需的時間花費都是O(n2)。因此，在第14～23 行的循環(huán)中，迭代地選擇Ln路徑連接圖Gf中所有的Cblock以形成一個重構(gòu)的連通控制集所需花費的時間是O(n3)，進(jìn)而得到算法1 的時間復(fù)雜度為O(n3)。

5 仿真實驗

為了驗證所提ZREA22 算法的性能，通過仿真實驗將其與文獻(xiàn)［23-24］中構(gòu)建(2,1)-CDS 和(2,2)-CDS 的算法進(jìn)行對比。為了對比方便，兩個對比算法分別被記為WFSK09 和SHLO14。對于WFSK09算法，首先運行文獻(xiàn)［21］中的算法構(gòu)造一個連通控制集C，然后將C作為WFSK09 的輸入以獲得一個(2,1)-CDS。對于SHLO14 算法，使用上述相同的C作為文獻(xiàn)［25］中算法的輸入以獲得一個(1,2)-CDS，然后將獲得的(1,2)-CDS 作為SHLO14 算法的輸入以獲得一個(2,2)-CDS。對于ZREA22 算法，隨機(jī)產(chǎn)生一個故障邊集M。如果在網(wǎng)絡(luò)中移除M中的邊后剩余網(wǎng)絡(luò)仍然是連通的，但原來的連通控制集C不再是剩余圖的一個連通控制集，那么將M作為候選故障邊集，否則舍棄它并重復(fù)上述操作直到產(chǎn)生一個候選的M。隨后，使用上述相同的連通控制集C和故障邊集M作為該算法的輸入以得到一個重構(gòu)的連通控制集。仿真實驗主要包括連通控制集的大小和算法的運行時間兩個部分的性能比較。

5.1 參數(shù)設(shè)置

在實驗準(zhǔn)備階段，假設(shè)n個傳感器被隨機(jī)地分布在一個大小為100 m×100 m 的虛擬空間中，其中，n從10 變化到100，增量為10。設(shè)置每個傳感器的傳輸半徑為r?[rmin,rmax]，其中，最小傳輸半徑rmin固定為20 m，最大傳輸半徑rmax為30 m、35 m 和40 m。在相同仿真參數(shù)設(shè)置下，隨機(jī)產(chǎn)生具有不同網(wǎng)絡(luò)設(shè)置的候選網(wǎng)絡(luò)，即傳輸半徑比率分別為1.5、1.75 和2 的2 連通的雙向鏈路圓盤圖。一旦隨機(jī)產(chǎn)生一個網(wǎng)絡(luò)，判斷它是否為2 連通的雙向鏈路磁盤圖，如果它是一個2 連通的雙向鏈路磁盤圖，則將其作為實驗的候選網(wǎng)絡(luò)，否則舍棄它。重復(fù)執(zhí)行上述操作，直到產(chǎn)生100 個候選網(wǎng)絡(luò)。在每個候選網(wǎng)絡(luò)中分別運行3 個算法并取100 次結(jié)果的平均值作為最終的仿真實驗結(jié)果。

5.2 連通控制集的大小比較

圖3 給出了在結(jié)點傳輸半徑比率為1.5、1.75 和2時，網(wǎng)絡(luò)規(guī)模變化對連通控制集的大小的影響。由圖3 可以看出，對于任意的傳輸半徑比率，隨著網(wǎng)絡(luò)規(guī)模的增加，ZREA22、WFSK09 和SHLO14 算法所產(chǎn)生的連通控制集的大小也會相應(yīng)增加，這是因為在一個固定大小的區(qū)域中，隨著網(wǎng)絡(luò)規(guī)模的增加，相應(yīng)會需要更多的點來控制其他的結(jié)點，因此將產(chǎn)生一個更大的連通控制集。此外，在網(wǎng)絡(luò)規(guī)模相同時，隨著結(jié)點傳輸半徑比率的增加，3 個算法所產(chǎn)生的連通控制集的大小也會相應(yīng)減小，這是因為結(jié)點的半徑越大，它的鄰居結(jié)點的數(shù)量越多，需要更少的點來控制其他的結(jié)點，連通控制集也會更小。此外，ZREA22 算法在應(yīng)對結(jié)點失效且減小連通控制集方面具有較好的效果。具體地，對于每個傳輸半徑比率，ZREA22 算法所產(chǎn)生的連通控制集的大小均會小于WFSK09 和SHLO14 算法所產(chǎn)生的連通控制集的大小。需要注意的是，由圖3 可得，相比于WFSK09 和SHLO14算法，ZREA22 算法產(chǎn) 生的連 通控制集的大小分別至少減少了9%和31%。這是因為ZREA22 算法是基于原連通控制集添加結(jié)點進(jìn)行重構(gòu)，WFSK09 和SHLO14 算法需要在原連通控制集的基礎(chǔ)上添加結(jié)點使得它是2 連通的。正如上文所述，(k,m)-CDS 往往比較大并且隨著k值的增加而增加，這意味著它需要添加大量的結(jié)點，然而ZREA22 算法僅是重新構(gòu)造一個新的連通控制集，所需添加的結(jié)點數(shù)量會比較少。因此，ZREA22算法所產(chǎn)生的連通控制集的大小遠(yuǎn)小于另外兩種算法。

圖3 不同傳輸半徑比率下連通控制集的大小比較Fig.3 Comparison of connected dominating set size under different transmission radius ratios

5.3 算法運行時間比較

圖4 給出了在結(jié)點傳輸半徑比率為1.5、1.75 和2的情況下，網(wǎng)絡(luò)規(guī)模變化對3 種算法運行時間的影響，表1 給出了具體數(shù)據(jù)。由圖4 和表1 可以看出，對于任意的傳輸半徑比率，隨著網(wǎng)絡(luò)規(guī)模的增加，3 種算法的運行時間也相應(yīng)增加，這是因為在一個固定的區(qū)域中，隨著網(wǎng)絡(luò)規(guī)模的增加，需要更多的時間來處理一個更大的數(shù)據(jù)集。另外，對于每一個傳輸半徑比率，在任意網(wǎng)絡(luò)規(guī)模下，ZREA22 算法的運行時間均小于WFSK09 和SHLO14 算法，這是因為ZREA22 算法基于原連通控制集重構(gòu)新的連通控制集，導(dǎo)致其在尋找極大獨立集時所需的搜尋空間變小，所以這一過程所需的時間也會減少。同時，根據(jù)算法1，在極大獨立集中添加結(jié)點以形成連通控制集時，只需迭代地選擇一條最短路徑，這意味著ZREA22 算法需要相對較少的時間實現(xiàn)連通。然而，WFSK09 算法不但需要構(gòu)造一個連通控制集，而且需要采用貪婪策略不斷地添加結(jié)點到所獲得的連通控制集中，使其成為2 連通，這就意味著它需要相對較多的時間開銷。與WFSK09 算法相比，SHLO14 算法通過勢函數(shù)計算所有結(jié)點的勢函數(shù)值，并將其中具有最大勢函數(shù)值的結(jié)點加入原連通控制集中，該過程被執(zhí)行多輪直到所得到的結(jié)果是一個(1,2)-CDS，隨后使用類似的方法把最大勢函數(shù)值的結(jié)點加入所獲得的(1,2)-CDS 中，直至擴(kuò)充成一個(2,2)-CDS。由于勢函數(shù)的計算是非常復(fù)雜的且每次迭代中均需要計算所有非連通控制集中結(jié)點的勢函數(shù)值，因此SHLO14 比WFSK09 算法需要更多的時間開銷。

表1 不同傳輸半徑比率下的算法運行時間結(jié)果 Table 1 Results of algorithm running time under different transmission radius ratios

圖4 不同傳輸半徑比率下算法運行時間比較Fig.4 Comparison of algorithm running time under different transmission radius ratios

6 結(jié)束語

本文主要研究存在故障通信鏈路的異質(zhì)無線傳感器網(wǎng)絡(luò)的虛擬骨干重構(gòu)問題，這一問題可以抽象為雙向鏈路圓盤圖G=(V,E)的連通控制集的重構(gòu)問題。針對給定的雙向鏈路圓盤圖G=(V,E)及其連通控制集和相應(yīng)的故障邊集，設(shè)計一個連通控制集重構(gòu)算法。首先計算沒有被原連通控制集控制的點組成的集合W，然后計算W的生成子圖的極大獨立集，最后對該極大獨立集中的每個頂點，尋找一條最短路徑將它與原連通控制集中的點連接起來，并將這些最短路徑中的點加入原連通控制集中形成一個新的連通控制集。該算法可以產(chǎn)生一個新的連通控制集，大小的上界為3α?Sopt+3(γ+m)。仿真實驗結(jié)果表明，相比于已有的容錯虛擬骨干構(gòu)建算法，所提算法在虛擬骨干的大小和運行時間上更具優(yōu)勢。下一步將研究存在結(jié)點和鏈路混合故障的異質(zhì)無線傳感器網(wǎng)絡(luò)虛擬骨干重構(gòu)問題。