時延和能耗均衡的強連通支配集構造算法

孫彥景，錢建生，馬姍姍，任鵬

（1. 中國礦業大學 信息與電氣工程學院，江蘇 徐州 221116；2. 中國礦業大學 煤炭資源與安全開采國家重點實驗室，江蘇 徐州 221116）

1 引言

與傳統計算機網絡不同，無線傳感器網絡(WSN, wireless sensor networks)沒有固定的基礎結構。依據圖論的獨立集、支配集、連通支配集、獨立支配集、團簇及染色等基本理論[1]，研究人員提出了很多構造層次網絡的方法，作為無線傳感器網絡的虛擬骨干[2]。在單位圓圖（UDG, unit disk graph）網絡模型的基礎上，學者對使用最小連通支配集構造虛擬骨干的方法進行了大量的研究[3]，提出了很多最小連通支配集（MCDS, minimum connected dominating set）的構造算法。

文獻[4～6]主要研究高效的分布式MCDS算法，或者在一定程度維護虛擬骨干的冗余以保證容錯性和路由的靈活性。文獻[7]針對最小連通支配集問題提出了具有較高能量效率的啟發式算法。該算法把網絡中所有的節點作為最小連通支配集的一個初始解，然后利用啟發式修剪策略剔除冗余節點從而減小最小連通支配集的規模。文獻[8]使用圖著色算法求得的極大獨立集等價于簇劃分后的簇頭集合，然后搜索網關節點使得簇頭連通，由此生成極小連通支配集，形成虛擬主干網。文獻[9]提出一種基于能量代價的最小權和連通支配集拓撲控制算法，解決無線傳感器網絡中最小連通支配集拓撲并非網絡耗能最小拓撲的問題，最小化網絡整體能耗。文獻[10]為了提高無線傳感器網絡的能量利用效率、延長網絡的生存時間，提出了用馬爾科夫模型優化分布式最小連通支配集算法。文獻[11]在串行最大獨立集構造算法的基礎上，提出了基于權重和時序的觸發式連通支配集構造算法。

隨著傳感器網絡應用范圍的迅速擴大，不僅要考慮節能特性，同時也對傳輸時延提出了要求。文獻[12]提出采用一種新型動態樹來組織網絡拓撲的能效與時延平衡的數據收集機制。文獻[13]提出了一種基于虛擬點優先級的移動sink路徑優化選擇方法，以滿足時延要求和最小化網絡整體能耗。就無線傳感器網絡而言，在單位長度下，路徑長度等相關因素決定了網絡數據在節點之間的傳輸時延。在網絡圖上，路徑長度轉化為最短路徑樹(SPT,shortest path tree)問題，等效于傳輸時延。數據傳輸帶來的能量功耗則可以看作求解最小支撐樹(MST,minimum spanning tree)問題。文獻[14]的研究結果表明不可能滿足路徑和費用同時最小的要求。在文獻[15]的基礎上，文獻[16]提出了理想情況下基于無向圖的有界傳輸時延連通支配樹問題，并給出了構建CDT(connected dominating tree)的有效算法，構建連通支配樹來平衡連通支配集中功耗和傳輸時延。

考慮到無線網絡中通信鏈路的非對稱性，本文使用加權有向連通圖建模無線網絡，在文獻[16]的基礎上提出對應無線傳感器網絡有界傳輸時延強連通支配樹聯合約束問題，并給出基于有向加權圖的時延和能耗均衡的強連通支配集算法，驗證了算法的有效性。

2 SDTT問題

在無線網絡中，相鄰節點間的邊權重并不是對稱的，例如，節點u和v在不同噪聲環境下，有不同的信號檢測閾值，這樣從u到v和從v到u的路徑上發送的功率也就不同，依圖論理論，本文使用有向圖進行網絡建模。

文獻[14]研究表明不可能同時滿足最小化權重和距離的目標。為平衡MST和SPT的目標要求，本文分別以MST和SPT的費用（權重）表示發送時消耗的能量和從發送方到接收方的路徑長度，構造具有雙重權值的生成樹。同時，為簡化分析，以路徑長度代替傳輸時延。這樣，對強連通支配集的生成樹而言，目的是在能量消耗(α)和傳輸時延(β)要求之間進行折中。設加權有向圖G=(V, E)，要找到支撐G滿足(α,β)約束要求的強連通生成樹C，相關符號沿用文獻[16]中的定義：

Puv：從節點u到v發送成功所需要的功率

d(u, v) 或d(e)：在單位長度下，從節點u到節點v沿邊e的歐氏距離；

Cv：信號偵測閾值常量，與具體環境條件相關。無線信號傳輸消耗的能量正比于dγ，γ的取值是從2到4，本文設為2；

p(u)：從節點u到節點v的最大發送功率為p(u)=max{puv:(u,v)∈G}；

w(e)：從節點u到節點v的邊e的權重為

w(C)：強連通樹C的權重w(C) = Σe∈Tw(e)；

p(C)：強連通樹C的能量消耗p(C) = Σu∈Vp(u)；

d(G)：圖G的路徑長度（傳輸時延）d(G)=Σe∈Ed(e)。

定義1 無線傳感器網絡有界傳輸時延強連通支配樹約束(SDTT)問題：給定無線傳感器網絡子集，構建一個 SCDT-tree，使得d(SCDT)不大于用戶設定的閾值，并且p(SCDT)有界。

通過構建一個強連通SCDT，同時滿足能量均衡和傳輸時延約束的要求。據文獻[16]SCDT-tree定義如下：

定義2 如果圖G的強連通支配樹C在α≥1且β≥1時，滿足下面的要求，則稱C為圖G的SCDT-tree：

1) 距離：對每一個頂點u，根節點r與u之間的距離至多是從r到u的最短路徑的α倍；

2) 能耗：C的能量消耗最多是SDTT問題最優解的β倍。

針對鏈路的不對稱性，本文使用加權有向連通圖建模無線網絡，提出對應SDTT問題在有向加權圖中的SCDT算法。

3 SCDT算法

在加權有向連通圖上，該圖的最小費用樹把節點對間的發送功率作為權值，最短路徑樹以路徑長度為權值，任選根節點r，SCDT算法構建能耗和時延均衡的強連通支配樹。

算法構造以r為根的MSTT和以r為匯聚點的T′，通過二者的疊加得到強連通圖。依據網絡的連通信息構建H，H包含從根r至每個頂點的最短路徑；使用文獻[17]提出的MWIA-TC算法構建T和T′。

SCDT算法按深度優先(DFS, depth first search)的方式遍歷最小生成樹T，當訪問節點u時，如果在T中從r到u的路徑長度大于α倍H中的最短路徑，則用H中從r到u的路徑取代T中的路徑。對于T′執行同樣的過程。這樣，在遍歷所有節點后，SDTT問題得以解決。算法輸入α，r, MSTT，MSTT′和SPTH，最后返回SCDT-treeC。

算法1 SCDT算法

4 分布式強連通支配集算法

分布式強連通支配集算法過程分為2個階段，首先在單位圓圖構建極大獨立集，然后基于有向圖使用分布式SCDT算法構造時延和能耗均衡的強連通支配集。

4.1 分布式MIS構建

采用文獻[18]的方法讓所有的節點知道自己的排序和鄰居后，根節點啟動染色標記過程構建極大獨立集。使用分布式簇頭選擇算法構建有根生成樹進行等級排序的機制，以保證生成的極大獨立集滿足兩跳的標準。在生成的有根生成樹中每個節點把與根節點之間的跳數看作自身的級別，節點的排序按照級別和ID標識的有序數對進行，遵循詞典次序排列，具體過程如文獻[16]所述。當所有的節點標記為灰色或黑色，根節點就開始執行下一階段的算法。

4.2 分布式SCDT算法

下面介紹在有向圖模型下的分布式 SCDT算法。算法運行在生成的極大獨立集中的每個節點，分為2個階段：①采用單源分布式dMST, dSPT和dDFS算法分別獲取SPT，MST和DFS的遍歷次序，在無向圖模型中生成連通支配集；②通過改變與節點關聯的邊的方向反轉每個節點所有的邊，重復步驟①的過程。通過反轉得到的SCDTD邊的方向，生成反轉的SCDTD′，聯合2個階段生成的SCDT，就得到強連通支配樹。在構建過程中，節點之間使用消息WAKEUP、ADD、ADD_ FINISH、UPDATE、REVERSE實現信息交換。WAKEUP、ADD、ADD_FINISH 和 UPDATE消息如文獻[16]所述，REVERSE消息如下。

REVERSE：如果節點收到該消息，反轉關聯的該節點的所有邊的方向，把出邊變為入邊，把入邊變為出邊。

為構建SCDT樹，分布式算法dSPT、dMST和dDFS在每個節點執行，發起和終止由根r控制，以串行方式運行，網絡內的所有節點同步。按照dDFS過程中得到的順序，首先在MSTT上執行算法，每個節點u使用p[u]記錄上一級的父節點，d[u]記錄距離。每個節點在初始時將d[u]設定為dT(r,u)，根r依照dDFS所得次序，發布WAKEUP消息到后續的節點，發起遍歷過程。

消息的傳遞觸發以下處理規則。

1) 從節點v收到WAKEUP消息，節點u成為當前被訪問的節點，u更新d[u]和p[u]。接著，u檢查是否d[u]>αdSPT(r,u)，若是，添加從r到u的路徑PSPT(r,u)到T；否則，維持不變。為添加該路徑，u發送給其在SPT中的父親w消息ADD，這里，u是 ADD消息的發起者。接著，u等待發起者為u的ADD消息的回復。

2) 當節點w而不是根節點收到來自節點u的發起者i的ADD消息，w發送一個發起者為i的ADD消息給SPT中的父親x，同時，w記錄u作為新的子節點。

3) 當根節點r收到發起者為i的ADD消息，r記錄u為新的子節點，并返回ADD_FINISH消息至u，與ADD消息一樣，ADD_FINISH也需要包含發起者。

4) 當節點u收到w的發起者i的ADD_FINISH消息，節點u更新d[u]和p[u]。若u不同于i，u發送發起者為i的ADD_FINISH消息給向u發送發起者i的ADD消息的節點；否則，u向由dDFS獲得的下一個節點發送WAKEUP消息，若p[u]由x變為y，u發送一個發起者為u的UPDATE消息到x。

5) 當節點x從u收到UPDATE消息，節點x更新d[x]和p[x]。若p[x]由v變為w，x發送一個發起者為x的UPDATE消息到v。

6) 若在dDFS所得序列中的最后一個節點u收到發起者為u的ADD_FINISH消息，就反轉與自己關聯的邊的方向，并發送REVERSE消息給其父親。

7) 每個節點在收到REVERSE消息時，反轉所關聯的邊的方向，并發送REVERSE消息給自己的父親節點。

在收到發起者為u的REVERSE和UPDATE消息，u被標記為dDFS隊列中的最后一個節點。根r反轉與其關聯的邊，結束第一階段。然后r發送WAKEUP消息發起第二階段。在根r收到一個發起者為u的UPDATE消息，而且u在dDFS次序中標記為最后一個節點時，算法終止。

5 理論分析及算例

把SCDT算法運用到圖G，構造強連通樹C，設γ=2且Cv=1，p(opt)為SDTT問題的最優解opt的總能耗。

引理1 在有向圖G中，圖G的支配樹C總功率消耗p(C)≤w(G)。

證明

引理2 對于圖G的SPTH和MSTT和T′，H的功耗至多倍MST功耗。

證明 由文獻[5]證明知，

顯然

由此得證。

引理3w(Topt)≤Δp(opt)，w(T′opt)≤p(opt)Δ是G中最大節點度。

證明 由文獻[16]可知，w(Topt)≤Δp(opt)。

對于T′，每個非根節點有且僅有一條出邊，因此，w(T′opt) ≤p(opt)，由此得證。

定理1 設C為由SCDT構建的SCDT-tree，那么

證明 設圖G的SPTH，MSTT和T′，由引理1和2，可得

由此得證。

下面分析分布式算法 SCDT的時間和消息復雜度。

定理2 分布式SCDT算法的時間復雜度O(n2)，消息復雜度O(n2)。

證明 由前面過程可知，在每個節點同時執行SCDT算法。ROUTE-ADD決定了算法的執行時間，而ROUTE-ADD的最大執行時間正比于RELEXed邊數，而RELEX的執行時間是O(1)的。因此，考慮最壞的情況下，需要添加長度為O(n)的路徑，這樣ROUTE-ADD的執行時間為O(n)，由于dSPT、dMST和dDFS等算法的時間復雜度最大為O(n2)，顯然算法SCDT的時間復雜度也為O(n2)。

在運行過程中，每個節點發送 REVERSE和WAKEUP消息 2次。ADD、ADD_FINISH和UPDATE至多O(n)次，因此算法總的消息復雜度應為O(n2)。由此得證。

下面給出SCDT算法執行過程示例。

在圖1中，設圖1(a)是執行MIS構建過程后形成的網絡虛擬骨干節點的無向圖，數字表示節點之間的通信距離；圖1(b)是在考慮每個節點為實現有效的傳輸所需要的發送功率后，形成的一個強連通雙向加權信息圖，每邊上的數字表示該方向上節點對間的通信所需的傳輸功率；圖1(c)是邊反轉后的加權圖；圖 1(d)是最短路徑樹H，圖 1(e)和 1(f)是最小支撐樹T和T'；設節點1為根節點，且α=2，對T按照DFS次序進行遍歷，當訪問4時，T中的路徑(1,2,3,4)dT(1,4)=23，此時在H中，dH(1,4)=11，也就是dT(1, 4)大于2dH(1, 4)=22，于是把邊(1,4)添加到H，同時p[u]從3更新為1。注意到邊（3,4）沒有刪除，這是因為需要從此邊回溯。在遍歷T之后得到D如圖1(g)，同樣的在遍歷T'后得到D'，如圖 1(h)，括號內的數字表示路徑長度(即時延)，外面的為該邊的功耗，最后聯合D和D'得到最終的SCDT樹C，如圖1(i)所示。

圖1 SCDT-算法示例

接下來，驗證算法的約束能力，分別單獨計算圖1所示MST、SDT和SPT的功耗：

以路徑長度代替時延計算如下：

根據上面的計算結果可得：

結果表明SCDT算法執行正確，具有聯合約束能力，符合預期效果。

6 仿真實驗

采用與文獻[16]相同的參數設置，在網絡規模從20到300個節點的情況下進行仿真，所有的網絡場景在1 000×1 000的單位區域內生成，對每個網絡場景運行20此取統計平均值。對每條邊e設置其權重為Cvdruv，dru為圖G單位長度下的歐氏距離，r取值2。Cv為隨機常量，由網絡場景參數為每條鏈路設定。

圖2的仿真結果表明，由于算法SCDT僅添加在最小支撐樹中從u到r的權重2倍以上最短路徑樹中權重的路徑，算法SCDT能量消耗低于SPT，有效限制了總能耗。另外，在固定區域范圍內，當網絡規模不斷變大，節點數增多時，鄰居節點之間的距離在逐漸變小，因此總能量消耗并沒有快速增加。由圖2(b)可知，就能量消耗而言，SCDT/MST要比 SPT/MST低，而且在固定的區域內，隨著節點數增加，網絡密度增加，此時節點彼此之間更加接近，分布更均勻，所以比值呈下降趨勢，都更接近MST，也就是總能耗最小。

本文通過統計路徑長度來簡化傳輸時延特性分析。由圖3可以看出，對路徑長度而言，算法SPT總是最短也就是說傳輸時延最小，符合最短路徑的特性。由圖3(b)可知，就時延而言，SCDT與SPT的比值要比 MST低，而且在固定的區域內，隨著節點數增加，網絡密度增加，此時節點彼此之間更加接近，分布更均勻，所以比值呈下降趨勢，都更接近SPT，也就是總路徑長度最小，傳輸時延更小。

圖2 能量消耗對比

圖3 傳輸時延對比

綜合圖2和圖3的結果可知，SCDT具有在最小費用MST和最短路徑SPT之間的折中能力。

為分析α參數的選擇對算法時延和能耗約束關系的影響，分別對不同α取值時SCDT、MST和SPT算法總能耗和路徑時延進行仿真，結果如圖4所示。為分析能耗關系，如圖4(a)所示，分別把SCDT和SPT能耗與最小能耗MST進行比較。當α=1時，SCDT算法構建SPT，因此，2條曲線在1處相交，隨著α得增加，SPT/MST保持在5左右；SCDT/MST逐漸降低，當α足夠大時，此時對SCDT而言，只考慮能耗而不考慮時延問題，SCDT成為MST，符合的關系。

為分析傳輸時延關系，如圖4(b)所示，分別把SCDT和MST總路徑長度與最短路徑SPT進行比較。當α=1時，SCDT構建 SPT，隨著α的增加，MST/SPT維持在5；然而，SCDT/SPT逐漸增長，最后與MST相交。這是因為當α足夠大時，基本不考慮時延約束，SCDT等同于構建MST。

圖4α對約束關系的影響

7 結束語

為了解決無線傳感器網絡虛擬骨干構造時能耗和時延聯合約束的問題，考慮到無線鏈路的不對稱性，借鑒平衡MST和SPT樹的(α,β)約束機制，本文提出基于有向圖構造時延和能耗均衡的強連通支配集的分布式算法，解決了能耗和時延均衡的問題。理論分析、算例和仿真實驗都證明了提出的算法對解決該問題的有效性。在實際應用中，可以結合具體應用要求確定參數α、β調節約束關系。

[1] KIM D, WU Y, LI Y,et al. Constructing minimum connected dominating sets with bounded diameters in wireless networks[J]. IEEE Trans Parallel and Distributed Systems, 2009, 20(2): 147-157.

[2] MISRA R, MANDAL C. Minimum connected dominating set using a collaborative cover heuristic for ad hoc sensor networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2010, 21(3): 292-302.

[3] ZHENG C, SUN S X, HUANG T Y. Constructing distributed connected dominating sets in wireless ad hoc and sensor networks[J].Journal of Software, 2011,22(5):1053-1066.

[4] 卞永釗,于海斌,曾鵬. 無線傳感器網絡中一種啟發式最小連通支配集算法[J]. 信息與控制，2009, 38 (3): 355-359 BIAN Y Z, YU H B, ZENG P. A heuristic minimum connected dominating set algorithm for wireless sensor network[J]. Information and Control, 2009, 38 (3): 355-359.

[5] 徐洪兵, 祝穎. 基于拓撲控制的異類無線傳感器網絡分簇算法研究[J]. 電子科技大學學報, 2006, 35(4): 674-677.XU H B, ZHU Y. A topology-based cluster algorithm of heterogeneous wireless sensor networks[J]. Journal of University of Electronic Science and Technology of China, 2006, 35(4): 674-677.

[6] THAI M T, WANG F. Connected dominating sets in wireless networks with different transmission ranges[J]. IEEE Transactions on Mobile Computing, 2007, 6(7): 1-10.

[7] WU W L, DU H W, JIA X H,et al. Minimum connected dominating sets and maximal independent sets in unit disk graphs[J]. Theoretical Computer Science, 2006, 352(1): 1-7.

[8] 許力，林志偉. 基于圖著色的無線自組網極小連通支配集算法[J].通信學報, 2007, 28(3):108-114.XU L, LIN Z W. Graph coloring based minimal connected dominating set algorithm in wireless ad hoc networks[J]. Journal on Communications, 2007, 28(3):108-114.

[9] 孫超, 尹榮榮, 郝曉辰. WSNs中基于能量代價的最小權和支配集拓撲控制算法[J]. 電子與信息學報, 2010, 32(4): 857-863 SUN C, YIN R R, HAO X C. Energy cost based topology control algorithm of minimum-total-weight connected dominating set in WSNs[J]. Journal of Electronics and Information Technology, 2010,32(4): 857-863.

[10] 汪文勇, 向渝, 董傳坤等. 用馬爾科夫模型優化分布式最小連通支配集算法[J].電子學報,2010, 38(10):2441-2446.WANG W Y, XIAGN Y, DONG C K,et al. Optimizing distributed algorithm for minimum connected dominating set with Markov model[J]. Acta Electronica Sinica, 2010, 38(10):2441-2446.

[11] 王玉明, 趙大勝. 基于串行最大獨立集的連通支配集構造及分析[J].華中科技大學學報(自然科學版),2011,39(3):61-65.WANG Y M, ZHAO D S. Construction and analysis of connecteddominating set based on serial maximum independent set[J]. Journal of Huazhong Science and Technology (Natuaral Science Edition),2011,39(3):61-65.

[12] 鄭杰, 郭淑杰, 屈玉貴等. 無線傳感器網絡能效時延平衡數據收集機制[J].中國科學技術大學學報,2008, 38(12):1414-1421.ZHENG J, GUO S J, QU Y G,et al.Energy efficiency and delay balancing data gathering for wireless sensor networks[J]. Journal of University of Science and Technology of China, 2008, 38(12):1414-1421.

[13] 郜帥, 張宏科. 時延受限傳感器網絡移動Sink路徑選擇方法研究[J]. 電子學報,2011, 39(4):742-747.GAO S, ZHANG H K. Optimal path selection for mobile sink in delay-guaranteed sensor networks[J]. Acta Electronica Sinica, 2011,39(4):742-747.

[14] SAMIR K, BALAJI R, NEAL E. Young balancing minimum spanning trees and shortest path trees[J]. Algorithm, 1994, 120(4):305-321.

[15] LI Y S, THAI M T, WU F. On the construction of a strongly connected broadcast arborescence with bounded transmission delay[J].IEEE Transactions on Mobile Computing, 2006, 5(10):1460-1470.

[16] 孫彥景, 錢建生, 顧相平等.聯合約束無線傳感器網絡連通支配集算法[J].電子科技大學學報，2009，38(2)：231-235.SUN Y J, QIAN J S, GU X P,et al. Distributed connected dominating set algorithm with combined constraints in wireless sensor network[J].Journal of University of Electronic Science and Technology of China,2009，38(2)：231-235.

[17] LI Y, CHENG M X, DU D Z. Optimal topology control for balanced energy consumption in wireless networks[J]. Journal Parallel and Distributed Computing, 2005, 65(2): 124-131.

[18] WAN P J, KHALED M A, OPHIR F. Distributed construction of connected dominating sets in wireless ad hoc networks[J]. ACM/Kluwer Mobile Networks and Applications, 2004, 9(2): 141- 149.