路由約束下的高效可靠虛擬骨干網構建算法

羅錦暉，劉春顏，王越濤，李洋，趙蘊龍

南京航空航天大學，計算機科學與技術學院，江蘇 南京 211106

無線傳感器網絡(wireless sensor network,WSN)因為其成本低、易部署、使用方便等特性被廣泛應用于環境監測、健康應用、災難救援、戰場監控、交通控制、移動計算以及軍事行動等各場景中。在大規模無線傳感器部署過程中，特別是野外環境監測場景，無線傳感器常被大量且隨機地投擲在覆蓋區域內，由此構建的無線傳感器網絡在信息收集與傳輸過程中極易造成擁塞、骨干節點過度消耗、網絡拓撲不穩定、網絡生命周期短等問題。為解決以上問題，常采取分層分簇路由和虛擬骨干路由等策略來引導信息定向傳輸。其中虛擬骨干網技術由Ephremides 等[1]于1987 年提出，并得到學術界廣泛支持和采用。在虛擬骨干網中，每個節點將消息發送到臨近虛擬骨干網中的骨干節點，信息沿這些骨干節點組成的虛擬路由網轉發至其目的節點。因此，當路由路徑搜索空間被限制在虛擬骨干網中，可以得到更短的路由路徑搜索時間、更小的路由表以及更便捷的路由維護，從而大大提高無線傳感器網絡轉發效率，延長網絡生命周期。

在虛擬骨干網絡中，通常以平均骨干路徑長度(the average backbone path length，ABPL)[2]來衡量網絡中節點間傳輸路徑的長度，間接反映網絡中信息傳輸的成本或能耗。無線傳感器網絡中虛擬骨干網構建問題已轉化為圖論中的連通控制集(connected dominating set，CDS)問題，學者們針對路由約束、最小權重、錯誤容忍等特性的虛擬骨干網開展研究，設計了一系列可推導、可驗證的近似算法，為通過連通控制集構建特定約束下的極小虛擬骨干網提供了理論方法。

在一些特定無線傳感器網絡中，因為節點的移動、失效等原因導致網絡的拓撲結構不穩定，因此需要構建具有容錯性的虛擬骨干網。在圖論中此問題可通過以k-連通m-控制集算法構建連通控制集的方法來解決，即要求虛擬骨干網C以外的任一點都至少被C中m個點所控制，而C導出的子圖的連通度至少為k。采用(k,m)-CDS 作為虛擬骨干，即使min{k-1，m-1}個節點發生故障，虛擬骨干仍能正常工作。

本文提出同時考慮網絡容錯性和平均路由長度的虛擬骨干網構建問題，并將該問題轉化為（1，m）-α路由約束的最小連通控制集(minimum connected dominating set, MCDS)問題，同時給出時間復雜度為O(n3)的構建算法，最后通過仿真實驗驗證其有效性。

1 國內外研究現狀

1.1 考慮路徑長度的連通控制集

在虛擬骨干網絡中，骨干節點越少，整個網絡的架設成本也越低，同時也能保證較高的通信效率。因此學者們從大量節點中選擇MCDS 組成骨干網絡，構造MCDS 是一個非確定性多項式(non-deterministic polynomial， NP)完全問題[3]。2005 年Mohammed 等[4]首次提出了以直徑和為附加因子生成控制集的算法，實驗結果表明，該算法在不增加解的規模的情況下，可以生成直徑較小的控制集。2007 年Li 等[5]開始研究無線網絡中直徑有界的虛擬骨干網構造問題，并提出了一種啟發式算法，該算法的時間復雜度為O(n2)。Kim 等[6]改進自己的原有算法，提出一個分布式CDS 構造算法，使近似比減少到6.906。

2010 年，Ding 等[7]發現在之前的研究中只是意識到路由路徑長度的重要性，沒有考慮最小路由約束(minimum routing cost，MOC)，不能保證通過其CDS 的路由路徑是原始網絡的最短路徑。在文獻[7]中提出了MOC-CDS，MOC-CDS 路由可以保證任意一對節點之間的每一條路由路徑也是網絡中的最短路徑，所以可以大大降低能耗和延遲，該算法的近似比為(1-ln2)+2lnδ，δ為網絡中的最大節點度。數值實驗顯示MOC-CDS 的尺寸非常大，為了平衡虛擬骨干的尺寸和路由成本，Du 等[8-10]又提出了α倍路由約束問題(αMOCCDS)。對于α≥5，他們給出了單位圓盤圖中αMOC-CDS 的常數近似算法。該算法首先以貪婪的方式構造圖G（V，E）的極大獨立集I，然后把集合I中的元素都放入集合D。對于每一對屬于I的節點u,v，若它們滿足其經過D的路徑長度dD(u,v)≤4，那么找到它們之間的一條最短路徑，并把該路徑上的所有點放入D中，最終得到|D|≤121|I|。Liu 等[11]針對各節點傳輸半徑不同的異構網絡提出了α-MOC-強聯通雙向控制集（ strongly connected bidirectional dominating set，

SCBDS）問題，并給出了近似比為(3(8ρ+1)2(2ρ+1)2/2)Mopt（1,m）的近似算法，其中ρ為最大與最小傳輸半徑之比，Mopt（1,m）為二維空間下最小m重連通控制集問題的最優解。Putwattana 等[12]改進了Liu 的算法，驗證了對于任意在I中并且d(u,v)≤3 的一對點u,v，計算出連通u,v的最短路徑，并把最短路徑的中間節點全部放入C集合中，α倍路由約束連通控制集D=C∪I，D的導出子圖是連通的，同時滿足dD(u，v)≤5d(u，v)。改進過后的α-MOCSCBDS 近似比為2(6ρ+1)2(2ρ+1)2。

1.2 考慮容錯性的連通控制集

Dai 等[13]最先提出將k-連通m-控制集問題引入容錯性虛擬骨干網的研究中。他們提出了最小(k，m)-CDS 的3 種啟發式算法。但是生成的連通控制集的大小沒有給出上限。Wu 等[14]提出了一個構造k-連通m-控制集的分布式算法，這個算法的優點就在于它的信息開銷很低。THAI 等[15]研究了k-連通m-控制集并且首次提出了1-連通m-控制集和k-連通k-控制集的近似算法?；谶@2 個算法，提出了對于k-連通m-控制集的一般算法。Wang 等[16]提出了增強連通控制集(connecting dominating set augmentation，CDSA)，構造一個能夠克服無線節點故障的2-連通CDS。其主要思想是首先構造一個連通控制集，然后通過在主干中添加新的節點將其擴充為2-連通，通過證明CDSA 具有72 的恒定近似比， 從而保證了CDSA 的質量。Shang 等[17]指出考慮容錯的虛擬骨干網中，利用單位圓盤圖和一個較小的m(m≤2)，迭代地選取m個極大獨立集，它們的并集構成一個m-控制集，同時也給出了(1，m)-CDS 的常數近似比，并討論了如何設計具有任意大m問題的近似算法。Kim 等[18]得到了單位圓盤圖中最小(3，m)-CDS 問題的常數近似算法，但該算法非常復雜，近似比也很大，如(3，3)-CDS 的近似比為280。Wang 等[19]擴展了文獻[17]中容錯虛擬骨干網的研究，運用2-連通但非3-連通圖的Tutte-分解簡化了該算法，并改進了近似比到5α，特別當k=m=3 時，近似比可以降到62.3，其中α為(2,m)-CDS 的近似比。Shi 等[20]提出基于單位圓盤圖上最小節點加權Steiner 網絡問題的常數近似算法，這個算法是k-連通m-控制集的虛擬骨干網，其中k和m為m≥k的2 個固定常數，得到(k，m)-CDS 問題常數近似比。當k≥3 時，該近似比為(α+5ρ)；當k=2 時，該近似比為(α+2.5ρ)，其中α為最小m控制-CDS 的近似比，ρ為最小k-連通CDS 的近似比。Zhou 等[21]把容錯性和異構網絡結構同時考慮進去，提出了異構無線傳感器網絡(3，m)-CDS 的近似算法。文中性能比最大為γ，其中α≥4 時，γ=α+8+2ln(2α-6)；α＜4 時，γ=3α+2ln2，α是極小(2，m)-CDS 問題的近似比。如果將算法應用到單位圓盤圖上，則近似比將小于27。

2 問題描述

利用圖G=(V，E)描述網絡拓撲結構，V為網絡中所有節點，E為網絡中的所有邊。假設C為V的一個子集，如果含有V/C中的每個頂點都在C中有鄰點，則子集C稱為控制集。如果由C導出的子圖GC是連通的，則稱C為連通控制集。為了進一步解決傳感器網絡中由于網絡節點失效等原因導致的網絡拓撲不穩定問題，使用圖論中k-連通m-控制集解決網絡的容錯性問題；同時通常使用α倍路由約束來體現虛擬骨干網的高效。為此本文給出以下定義。

定義1k-連通m-控制集：給定圖G=(V,E)中的1 個連通控制集D是k-連通m-控制的，當且僅當任意大小不超過k-1 的子集D′?D使得GD-D′仍然是連通的，同時存在1 個連通控制集D是G的m控制集，當且僅當對于任意的節點u∈VD，則u在D中至少存在m個鄰居。

定義2最小路由約束連通控制集：MOCCDS 是尋找一個最小的點集合D?V，這個集合D有以下特性：

1)?u∈VD，?v∈D，使(u, v)∈E。

2) 導出子圖GD是連通的。

3) ?u,v∈V， 若Dist(u, v)＞1， 那么?pi(u,v)∈Pi(u,-v),pi(u,v){u,v}?D。其中pi(u, v)={u,w1,w2,···,wk,v}，表示點u, v之間第i條最短路徑；Dist(u,v)表示點u, v間的最短路徑跳數；Pi(u, v)表示u,v間所有的最短路徑。

定義3α倍路由約束連通控制集：αMOCCDS 為點集合D?V，這個集合D有以下特性：

1) ?u∈VD，?v∈D，使(u, v)∈E。

2) 導出子圖GD是連通的。

3) ?u,v∈V，若Dist(u, v)＞1，那么pD(u, v)上的所有中間節點都屬于D并且dD(u, v)≤αd(u,v)。其中pD(u, v)表示u, v間在D上的最短路徑；P(u,v)表示u, v間的最短路徑；dD(u, v)和d(u, v)分別表示pD(u, v)和P(u, v)上中間節點的數量。

定義4考慮容錯性的α倍路由約束問題(1,m)-αMOC-CDS：給定1 個單位圓盤圖G=(V,E)，子集S被稱為G的1 個考慮容錯性α-路由約束的連通控制集，則S必須滿足以下4 個個條件：

1）S是G的1 個控制集。

2）由S導出的子圖GS是連通的，即GS中的任意2 點之間都至少存在1 條路徑，使得2 點之間可以相互傳輸信息。

3）對于給定的常數α≥1，任意u, v點都滿足dD(u, v)≤αd(u, v)。

4）G中所有非骨干節點都至少被m個骨干節點所支配。

3 算法與理論分析

3.1 理論分析

尋找最小路由約束連通控制集的問題已經被證明是NP 難問題，部分文獻提出了通過尋找MOC-CDS 的近似算法來解決這個問題。這些近似算法一般分為2 個階段：第1 階段構造一個極大獨立集；在第2 階段，添加其他節點作為連接節點連通極大獨立集來構成一個完整的最小路由約束連通控制集。引理1～3 將為算法第2 階段提供理論支撐。

引理1G為一個連通的圖，D為G的一個連通控制集。d(u, v)為圖G中u, v這2 點的最短路長度，dD(u, v)為連接u, v這2 點的中間節點全在D中的最短路長度。假設任意滿足d(u, v)=2 的一對節點u, v都有dD(u, v)-1≤α，那么dD(u, v)-1≤α(d(u, v)-1)。

引理2G為一個連通的圖，D為G的一個連通控制集。假設任意滿足d(u, v)=2 的一對節點u,v都有dD(u, v)-1≤α，那么dD(u,v)≤αd(u,v)。

證明：根據引理1，

引理3[8]I為圖G的一個極大獨立集，D為包含I的一個連通控制集。假設對任意滿足d(u,v)≤4 且u,v都在I中的一對節點u,v，都有dD(u,v)≤4，那么dD(u,v)≤5d(u,v)。

Du 等[8]證明了引理1～3。根據這3 個引理，可以得知在無向圖G中，求出G的控制集C后，將C中的所有節點放入D中。若任意一對節點u,v∈D并且d(u,v)＜4，把u和v之間最短路徑的所有節點都加到D上，可以得到dD(u,v)≤5d(u,v)。Putwattana 等[12]對異構網絡中的路由約束提出了改進。受此改進的啟發，我們可以考慮無向圖G和G的控制集C，如果任意一對節點u, v∈D和d(u,v)＜3，把u和v之間最短路徑的所有節點都加到D上，同樣可以得到dD(u,v)≤5d(u,v)，理論分析過程如引理4。

引理 4I為由第1 階段構造的極大獨立集，D為包含I的1 個連通控制集，如果對于每一對屬于I的節點u,v，若滿足dD(u,v)≤3，那么找到它們之間的一條最短路徑，并把該路徑上的所有點放入S中，它們的誘導子圖GS是連通的，并且對于圖中任意一對節點u,v，都滿足dD(u,v)≤5d(u,v)。

證明：考慮V中一對節點u,v，它們在圖G中的最短路徑為k，假設這條路徑為(u=w0,w1,· ··,wk-1,v=wk)(如圖1 所示)，已知GS是連通的，對該路徑中每一對相鄰的wi和wi+1：

圖1 連接u, v 的最短路徑

1）若wi和wi+1其中一個是I中的節點，不失一般性假設wi不是I中的節點，那么在原圖G中Ddom(wi)domD(wi)和wi之間必有1 條只經過D中的點同時小于等于3 的路徑。（Ddom(wi)為I中支配wi的節點）。

2）若wi和wi+1都不是I中的節點，那么存在Ddom(wi)和Ddom(wi+1)分別支配w1和w2。 無論Ddom(wi)和Ddom(wi+1)是否為同一個點，均有圖G中Ddom(wi)和Ddom(wi+1)之間必有1 條只經過D中的點同時小于等于3 的路徑。又因為由已知條件可得原圖G中存在1 條長度為3 的路徑(Ddom(wi),wi,wi+1,Ddom(wi+1))。那么可以得出：

式中：k≥1，Ddom(u)為集合C中控制u的的點。

3.2 算法設計與分析

本節設計一個3 階段算法(1,m)-αMOCCDS 構建基于最小權重連通控制集的α倍路由約束虛擬骨干網，該算法是一種基于極大獨立集的連通控制集構建方法，算法過程簡述如下。

第1 階段：構建極大獨立集I1作為骨干節點。

第2 階段：以動態規劃思想連接I1中的節點構建連通控制集。

第3 階段：通過一個迭代算法構建m-控制集。不斷求解普通節點集中的極大獨立集Im，并加入第2 階段所求的連通控制集中，通過m-1 次迭代，確保網絡中任意一個普通節點都被至少m個骨干節點所控制。

算法1構建αMOC-CDS。引用文獻[8]中的Algorithm 2 作為第1 階段構造極大獨立集（maximum independent set, MIS）的算法1，該算法貪婪地尋找節點間度最小的節點作為骨干節點，最終構成一個極大獨立集。

算法2構建連通集合C。 對控制集(dominating set, DS)中任意一對滿足d(u,v)≤3的節點u, v，求出u, v間在圖G中的最短路徑，并把路徑中的點都加入集合C中，算法如下。

輸入：一個連通單位圓盤圖G= (V,E)，求出圖G的極大獨立集I

輸出：連通集合C

NodeNumber←|V|

D←I←Construct-MIS(G,V,NodeNumber)

W[v] ←0 for allv∈I

W[v] ←1 for allv∈VI

for allu∈I

w[u][L] ←∞, for allu∈Vand 0 ≤L≤2

w[u][0] ←0

p[u][0] ←?

Used←{u}

forL= 0 to 2 do

newUsed←?

for allv∈ Used do

for allx∈ Neighbor[v] do

ifw[v][L]+W[x] ＜w[x][L+1]

w[v][L+1]←w[v][L]+W[x]

p[x][L+1] ←v

newUsed←newUs∪{x}

end if

end for

end for

Used←newUsed

end for

for allv∈Isuch thatd(u,v) ≤ 3 do

ifw[v][l] is minimum inw[v][L] then

Path←Path ∪p[v][l]

end if

end for

C←C∪ Path

W[v]←0 for allv∈C

end for

引理5[13]無向圖G=(V，E)是一個單位圓盤圖，m是一個自然數并且δ(G)≥m-1，使Dm*為圖G的最?。?，m）-CDS，S為圖G的一個MIS，那么可以得到

具體證明過程在文獻[17]中給出。

算法3構建基于(1,m)-連通控制集的α倍路由約束虛擬骨干網構建算法。該算法的基本思想是首先使用算法1 和算法2 中提出的方法生成αMOC-CDS，然后依次使用算法1 產生一個(m-1)個MIS，使得每個非骨干節點都由m個以上骨干節點中的頂點控制，算法如下。

輸入：一個連通單位圓盤圖G=(V,E)

輸出：基于(1,m)-連通控制集的α倍路由約束虛擬骨干網D

NodeNumber←|V|

I1←Construct-MIS(G,V,NodeNumber)

C←Construct Connected Set (G,I1)

S1←VI1

D←I1∪C

fori=2 tomdo

Ii← Construct-MIS(G,Si-1, NodeNumber)

Si←Si-1Ii

D←D∪Ii

end for

returnD

3.3 算法近似比分析

引理6若I為極大獨立集，那么對于任意u∈I，|{v∈I|0 ＜d(u,v)≤3}|≤48。

證明：對于每個節點v∈I，且d(u,v)≤3，構建中心為v、半徑為0.5 的圓盤，再構建一個中心為u、半徑為3.5 的大圓盤，在這個大圓盤中能容納的互不相交的半徑為0.5 的圓盤數量，即為

因為u點也在其中，所以

引理7由第2 階段構成連通集合具有以下性質|C|≤48|I|，其中I是第1 階段構建的極大獨立集。

證明：構造一個圖G，它的節點集為I，邊集為{(u, v)|u, v∈I，0＜d(u, v)≤3}。根據引理5 可知，G中節點最大的度為48，所以G包含最多24 |I|條邊。第2 階段中，因為d(u, v)≤3，每對極大獨立集節點對之間最多加2 個點，所以|C′|≤2×24|I|=48|I|。

引理8通過算法3 構成的（1，m）-αMOCCDS 中， 當m≤5時，當m＞5時其中為1 個圖G的最小(1,m)-CDS。

繼而可以推出

引理9算法3 中構造的(1，m)-αMOCCDS 構建的連通控制集D的上界大小如下：當m≤5時，為(240/m+5)Mopt（1,m），其中Mopt（1,m）指極小(1，m)-CDS 的最優解；m＞5時，為54Mopt（1,m）。同時對于任意一對節點u,v，都有dD(u,v)≤5d(u,v)。

證明：根據引理7、引理8 可知：當m≤5時，當m＞5時，

根據引理4 可知，在D中，任意一對節點u,v都有dD(u,v)≤5d(u,v)，同時每個非骨干節點都被m個以上的骨干節點支配。

4 仿真結果與分析

本節主要介紹了(1，m)-αMOC-CDS 的仿真實驗結果以及與相關算法的對比分析。

4.1 實驗環境

4.1.1 計算機平臺性能

處理器：AMD Ryzen 5 3500X 6-Core Processor，4.00 GHz；RAM，16.0 GB；系統類型：64 位操作系統，基于x64 的處理器；編程IDE：MATLAB。

4.1.2 無線傳感器網絡參數

在仿真中，具有不同傳輸范圍的無線傳感器網絡的參數設置如下。傳感器由一組隨機部署在以100×100 為邊界的歐幾里得平面上的節點來模擬，節點總數分別為100、200、300、400 個，傳輸半徑分別為15、20 和25，針對每組參數構造100個隨機圖，每個隨機圖進行100 次實驗取平均值。

4.2 對比算法

目前只有分別考慮容錯性的(k,m)-連通控制集問題和α倍路由約束連通控制集問題的解決方案，沒有同時考慮容錯性和α倍路由約束問題解決方案。仿真實驗在參數m=1、2、3 時，分別用(1,m)-MOC-CDS 算法在隨機網絡圖中構建虛擬骨干網，并進行多次試驗分別統計MOC-CDS、(1,2)-αMOC-CDS 和(1, 3)-MOC-CDS的規模大小。其中當m=1 時，(1, 1)-MOC-CDS 就是一個普通的αMOC-CDS。

4.3 仿真結果

最后利用不同傳輸半徑CDS 的大小比較仿真結果。傳輸半徑為15 情況下的仿真結果如圖2 所示，傳輸半徑為20 情況下的仿真結果的描述如圖3 所示，傳輸半徑為25 情況下的仿真結果如圖4 所示。

圖2 傳輸距離為15 時3 種算法CDS 大小

圖3 傳輸距離為20 時3 種算法CDS 的大小

圖4 傳輸距離為25 時3 種算法CDS 大小

4.4 仿真結果比較分析

圖2～圖4 給出了MOC-CDS、(1,2)-MOC-CDS和(1,3)-MOC-CDS 算法生成的CDS 大小的仿真結果，由這3 個圖中可以看到，隨著傳感器節點的總數量從100 個增加到400 個，每個算法生成的CDS 的平均大小略有增加，這是合理的。因為所有的算法都需要在最短路徑上有更多的中間節點連接更多的控制節點來構建CDS。同時隨著傳感器節點的總數量從100 個增加到400 個，3 種算法骨干節點增長速度在降低，這也是合理的。因為畫布總大小不變的情況下，隨著節點個數的增加，整個傳感器網絡變得十分稠密，執行算法1 和算法2 所需要增加的節點變少，骨干網節點數隨著網絡變得稠密逐漸趨于飽和。此外，我們還可以看到由算法MOC-CDS 生成的CDS 的平均大小受到引理8 近似比的限制。通過對比實驗可以得出，在傳輸半徑為15、20 和25 時，構建(1,2)-MOC-CDS和(1,3)-MOC-CDS 所需要增加的CDS 大小不超過15%和30%，這是一個可以接受的范圍，驗證了(1,m)-MOC-CDS 算法的可行性。

綜上所述，(1,m)-MOC-CDS 算法有效地解決了考慮容錯性的α倍路由約束問題，在滿足了α倍路由約束(α≥5)的情況下，充分考慮了整個網路的容錯性問題。通過實驗可以驗證(1,m)-αMOC-CDS 的有效性，同時由引理3 證明可得，對于任意一對節點u,v都有dD(u, v)≤5d(u, v)。

5 結束語

本文研究了無線傳感器網絡中具有容錯的虛擬骨干網構建算法，該算法同時考慮容錯性和路由約束兩方面約束。

關于如何有效延長網絡生命周期問題，還有一種方法是動態更新骨干節點，形成輪換來實現網絡中節點的負載均衡，從而延長網絡生命周期。這種動態更新虛擬骨干節點方法的正確性和有效性有待進一步研究和驗證。關于網絡魯棒性問題，可使用基于k-連通m-控制集和α 倍路由約束的方法構建虛擬骨干網，通過雙重約束來保證虛擬骨干網的魯棒性，其近似比和虛擬骨干網性能有待進一步研究和論證。