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

（1.廣西大學 計算機與電子信息學院，南寧 530004；2.廣西大學 公共管理學院，南寧 530004；3.廣西多媒體通信與網絡技術重點實驗室，南寧 530004）

0 概述

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

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

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

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

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

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

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

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

1 預備知識

1.1 網絡模型

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

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

1.2 符號和定義

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

1）G[S]，集合S中的點所產生的誘導子圖。

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

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)，最大（最?。﹤鬏敯霃健?/p>

10）ρ，傳輸半徑比率

文中用到的相關定義具體如下：

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

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

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

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

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

1）x1>x2。

2）x1=x2且y1>y2。

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

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

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

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

為了方便起見，用Cblock表示紅藍連通分支。

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

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

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

2 ZREA22 算法

2.1 算法原理

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

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

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

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

2.2 算法流程

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

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

2.3 算法偽代碼

算法1ZREA22 算法

3 算法正確性分析

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

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

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

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

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

1）u?W-K，根據引理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，進而得到集合C∪K是圖G的一個控制集。

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

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

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

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

4 算法性能分析

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

引理3在算法1 中路徑Ln的中間結點數量為n≤2。

證明該結論的證明與文獻［22］中的引理2.3類似，則該結論也是正確的。

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

假 設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及其鄰居結點組成的集合，集合K是由W產生的誘導子圖的極大獨立集。根據圖論知識可得，|K|≤|W|≤m2。

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

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

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

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

5 仿真實驗

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

5.1 參數設置

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

5.2 連通控制集的大小比較

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

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

5.3 算法運行時間比較

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

表1 不同傳輸半徑比率下的算法運行時間結果 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 結束語

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