Ad hoc網絡中基于MCDS構建延遲定界組播轉發結構

摘 要:根據無線信號傳播方式的特殊性，重新定義了無線組播路由中的代價和時延函數，基于圖論中最小連通支配集(MCDS)理論，提出的基于圖論中點著色思想的時延定界組播轉發結構的構建方法，通過求解MCDS來實現構建最小代價組播路由結構的目的，提出了組播路由時延定界的概念，并在該約束下構建MCDS。理論推導證明了該算法的正確性，與同類算法相比，較低的近似比證明了該算法的有效性，同時具有O(n)的時間復雜度和O(n)的消息復雜度，進一步證明了其高效性，具有適應于靈活多變的Ad hoc網絡的優勢。

關鍵詞:Ad hoc網絡; 組播; 時延; 最小連通支配集

中圖分類號:TP393

文獻標志碼:A

文章編號:1001-3695(2010)02-0632-04

doi:10.3969/j.issn.1001-3695.2010.02.063

Construction of delay definition multicast forwarding backbone forAd hoc network based on MCDS

PENG Lai， WANG Chao， AN Jian-wei， WU Hua-yi

(Dept. of Communication Engineering， School of Information Engineering， University of Science Technology Beijing， Beijing 100083， China)

Abstract:On the basis of particularity of the propagation method of wireless signal， this paper redefined the cost and delay function in wireless multicast routing. Proposed a vertex-coloring algorithm based method of construction of delay definition multicast forwarding backbone based on minimum connected dominating set (MCDS) theory in graph theory. By solving the MCDS problem， realized the construction of minimum cost multicast routing. And proposed the concept of delay definition in multicast routing. Theoretic analyzed the accuracy of this algorithm of construction and the low approximation ratio prove the algorithm to be more efficient than other conventional algorithm. It is further proven that this algorithm has high efficiency with O(n) time complexity and O(n) message complexity， which make it has more advantages when applied in Ad hoc network with characteristics of flexibility and variability.

Key words:Ad hoc network; multicast; delay; minimum connected dominating set

0 引言

Ad hoc網絡是一種沒有固定網絡基礎設施的自組織網絡。它由一些移動節點組成，通過這些節點間的無線鏈路或中間節點的多跳鏈路相連保持網絡連接和實現數據傳遞，因而具有分布式、自組織、多跳路由、動態拓撲、有限的安全保證等特點。近年來，研究人員對Ad hoc網絡組播已有了較深入的研究，按常用分類標準，Ad hoc網絡組播路由結構分為樹結構、mesh結構和混合結構三種類型。在對組播樹結構的研究中，普遍認為Steiner樹是最小代價組播樹。但是，這一結論在無線組播通信中并不成立，P. M. Ruiz等人[1]指出，無線媒介的廣播本質，即只發送一個消息來轉發組播報文給所有的下一跳節點，而不是復制報文給下游鄰居節點，組播通信的能量主要由節點轉發消耗，總體取決于組播樹中的報文轉發次數，也即承擔轉發任務的節點個數。因此，最小化Ad hoc網絡資源消耗的目標就是要建立一棵轉發節點數最少的組播樹，此問題歸結為圖論中尋找最小連通支配集(MCDS)問題。Ephremides等人[2]提出了用CDS構建一個用于消息和控制報文傳輸的虛擬骨干網絡的想法。S. Guha等人[3]提出了MCDS。B. Das等人[4]用分布式架構Ad hoc虛擬骨干網絡，將虛擬骨干網絡思想擴展到Ad hoc網絡。分布式Ad hoc網絡連通支配集算法可以概括為基于獨立集[5，6]、自裁減(self-pruning)[7～10]和多點中繼(如A.Qayyum算法、TDP、PDP算法)三個思路。也有基于圖論中點著色算法的連通支配集的構造[11]。

大多數MCDS求解算法只基于對減小MCDS的勢的考慮，很少考慮在實際的組播通信環境下，將MCDS看成組播轉發結構，能減少組播通信代價。并有基于連通支配集的最小化時延廣播策略的相關工作[12，13]，還沒有相關文獻將求解MCDS的方法用于組播通信并考慮時延約束問題。本文提出的基于圖論中順序點著色的時延定界組播路由算法，通過求解MCDS來實現構建最小代價組播路由結構的目的，并且在求解最大獨立集MIS階段就考慮組播時延約束，基于組播目的節點的最小時延性能下限，對組播路由時延定界。

1 相關模型及定義

本文討論的無線Ad hoc網絡中的節點分布在平面二維區域中，具有相同單位無線電波發射半徑，每一節點用惟一的ID標志。用圖論中的 unit-disk graph (UDG)來建模，網絡拓撲用UDG G(t)=(V，E)表示(V代表網絡中的所有主機，E代表它們之間的無線鏈路)。兩節點之間的距離在給定的電波發射距離R=1之內有邊相連。若U為頂點集V的子集，由U引出的圖G的子圖表示為G[U]。對任意正整數k，Gk表示在圖G中的頂點集V中的任意頂點之間的距離小于或等于k則有邊相連的圖。本文將在無線Ad hoc網絡中構建組播路由結構歸結為在UDG中求解MCDS問題，已被證明是NP完備的[14]。

定義1 對圖G進行頂點著色劃分。用有序自然數標志的顏色對圖G頂點著色，對頂點集V中的任意相鄰頂點不能著相同的顏色，對某一頂點序列v1，v2，…，vn按i從小到大的順序對vi盡可能著序號最小的顏色，劃分Vi(1≤i≤k)表示著顏色序號i的所有頂點集合，稱Vi(1≤i≤k)是圖G的著色劃分。

引理1[15] 對圖G進行著色劃分。其中任意劃分Vi(1≤i≤k)是圖G的一個獨立集(i表示著色序號)。

定義2 組播路由的時延上界。將所有目的節點的最小延遲路徑Pmin-delay中的最長路徑定義為時延上界路徑，L(Pmin-delay=Δ)，則Δ為組播路由的時延上界。

定義3 定界組播路由。時延Δ是組播節點在網絡拓撲結構上不能超越的界限，以此作為組播通信的時延上界約束，即建立的組播路由結構中的所有目的節點都要滿足時延Δ約束。

本文基于連通支配集理論構建一棵時延定界最小化代價的組播樹結構，該樹的非葉節點即近似MCDS。如前所述，由于無線媒介傳播方式的特殊性，將組播樹邊的總代價作為無線組播通信代價的衡量指標是不合理的，時延也不能用路徑上邊的延遲代價的疊加來定義，無線通信中最小代價組播樹應該是一棵覆蓋源和目的節點的非葉節點數目最少的樹。在用最小連通支配集構造虛擬骨干網絡的研究中，對網絡代價優化的目標是精簡覆蓋全網節點的連通支配集的勢，而基于連通支配集的組播路由的研究卻不常見。本文在時延定界的約束下優化無線組播通信的能量代價，重新定義了網絡模型和代價函數。

代價cost(u)=1:節點一跳轉發能量消耗。

時延delay(u)=1:節點接收和發送消息的延時消耗。

對于給定的連通網絡圖G(V，E)，組播源節點s，Δ為組播路由的時延上界，若一棵覆蓋s∪VM的樹T(VT，ET)滿足如下條件和約束:

cost(T)=min∑v∈Vm ∑u∈P(s，v)/vcost(u)=∑u∈VMCDScost(u)

s.t. delay(P(s，v))≤Δ

delay(P(s，v))=∑u∈P(s，v)/vdelay(u)

v∈Vm，P(s，v)∈T

則稱樹T為覆蓋s∪Vm的時延定界最小代價組播樹。

文中出現的符號和變量如下:

Vm表示組播目的節點集;VMCDS表示最小連通支配集(MCDS)的節點集合;Pmin-delay表示組播目的節點的最小延遲路徑;L(P)表示路徑長;TTL表示消息的最大轉發跳數。

2 DCDTC算法描述

2.1 基于圖著色的MIS選舉

源s知道到所有組播目的節點的最小時延路徑Pmin-delay，找出所有目的節點中到源s的Pmin-delay中的最長路徑目的節點，從該路徑上與目的節點相鄰的節點開始，每相隔兩跳確定一個獨立集節點，最長路徑如有k條，則執行k次直到找到所有獨立集節點。這些獨立集節點的確定過程中可能會遇見如下兩種情況:

a)后確定的獨立集節點與之前確定的獨立集節點相鄰如圖1所示，u為已確定的目的節點di的最小時延路徑上的獨立集節點，v為另一目的節點dj的最小時延等長路徑上想要加入獨立集的節點，因為L(P(s，di))=L(P(s，dj))，獨立集節點之間相隔兩跳，所以路徑P(s，v)和路徑P(s，u)長相差2 的整數倍，即|L(P(s，v))-L(P(s，u))|=2k，k=0，1，2，…。如L(P(s，u))-L(P(s，v))≥2，則節點u可以通過路徑P(s，v)到達源節點s，L(P((s，v)，(v，u)))=L(P(s，v))+1

b)當P(s，dr)和P(s，dt)兩路徑在節點w處重疊時，由于L(P(s，dr))=L(P(s，dt))，L(P(w，dr))=L(P(w，dt))，兩條路徑在確定獨立集節點時不會在節點w處發生沖突，如圖2所示。

給這些獨立集節點賦予最大優先級，其他節點按照權重大小賦予優先級，以分布式異步方式進行的著色過程將首先由這些已確定的MIS節點發起，節點基于鄰居節點的信息確定自己的顏色:a)最大優先級節點首先確定顏色;b)相鄰節點的著色過程不能同時執行，優先級大的鄰居節點具有優先著色權。初始化時，每個節點中有如下變量:

Color表示節點顏色序號(初始化為0);P表示優先級;T表示節點種類(M獨立集節點;C連接節點);C表示優先級高的鄰居節點的顏色序號集合;MN.P表示鄰居MIS節點的優先級;MN.N表示鄰居MIS節點的個數;NF表示優先級高的鄰居節點的個數;S表示{D，ND}節點狀態(D已確定;ND未確定)。

節點收到鄰居節點發來的D消息，執行如下算法:

1 if(S=ND)

2 {

3 if(D.color=1)

4 {

5MN.P=D.P;

6MN.N++;

7if(MN.N≥2)

T=C;

8 }

9 else C←D.color;

10 if(NF--=0)

11 {

12if(MN.N=0)

13

color=1;

14

T=M;

15else

16

for(i=2，color=0，i++)

17

{

18

if(iC)

19

color=i;

20

}

21廣播D消息給所有鄰居節點 (D.P=P， D.color=color);

22}

23 else

24

發送probe消息給優先級大的鄰居節點;

25If(優先級大的節點的著色程序執行中)

26

等待直到收到該鄰居D消息，跳轉到程序開始執行;

27else

28

跳轉到程序的12行;

29 }

引理2 由同一MIS節點發起的著色過程著色的color=1節點集的任意互補子集最少跳數為兩跳。

證明 由同一MIS節點發起的獨立集確定的過程可用圖3表示。不失一般性，假設著色過程從a到b再到c，節點c確定color=1是由優先級比自己大的鄰居節點b確定自己color≠1的過程引起，而c的鄰居中沒有color=1的節點。節點b至少與一個之前確定的color=1的節點a相鄰，否則它可以確定自己的color為1，所以節點c與a兩跳相隔。

引理3 圖G中V1的任意互補子集間相隔兩跳或三跳。

證明 由引理2可知，由同源發起的著色過程著色的獨立集節點之間有兩跳間隔，不同源的著色過程從兩個方向進行，如圖4所示，u和v為兩個定界路徑上的著色發起節點，可能在兩互補子集間產生三跳間隔。

定理1 以上算法過程得到的color=1節點集合，即V1集合是圖G的一個最大獨立集。

證明 由引理3可知，圖G中V1的任意互補子集之間相隔兩跳或三跳，所以V1集合是圖G的一個獨立集(IS)，并且圖G的連通性保證了算法對所有節點的著色，獨立集節點覆蓋圖G中所有節點，V1集合是圖G的一個最大獨立集(MIS)。

用U表示著色劃分得到的V1，兩跳相隔的獨立集節點有邊相連，圖G2[U]可以清楚地表示獨立集節點間的相鄰關系。

引理4 圖G2[U]中任意頂點與源s都是連通的。

證明 在圖G2[U]中，在獨立集節點選舉階段，首先確定的由優先級最高的獨立集節點與源s相連的k條路徑記為p1，p2，…，pk，它們是以s為根的樹上的k條樹枝，著色過程由樹枝上的節點發起，由引理2可知，由同源發起的著色過程著色的獨立集節點之間有兩跳間隔，所以在圖G2[U]中有邊相連，同理在圖3中節點a必與先于它確定的某獨立集節點相連，由此可得節點c與著色發起節點連通，著色過程是一個尋找獨立集節點之間在圖G2[U]中的連通關系的過程。不失一般性，所有獨立集節點均與樹枝上的某著色發起節點連通，而樹枝節點又與源s連通，因此所有獨立集節點與源s在圖G2[U]中是連通的。

2.2 分布式組播樹構建

目的節點按到源節點的最小時延路徑的長短順序依次尋路，接入組播樹。將k條時延上界路徑作為初始組播樹T。

1)樹根s選擇還未接入樹T目的節點的Pmin-delay中最長路徑，該目的節點為將要加入的節點，并通過該路徑發消息S給它，激起該節點的尋路過程，該節點廣播消息P。當獨立集節點轉發消息P時，只有鄰居節點中的連接節點(T=C)接收該消息參與轉發，消息的來源節點不接收該消息。當連接節點轉發該P消息時，只有鄰居節點中的獨立集節點(T=M)接收該消息參與轉發，消息的來源獨立集節點或其他節點不接收該消息。P消息中包括如下信息:TTL=LPmin-delay(該節點到源的最小時延路徑長)，PID記錄該消息經過路徑上的節點ID。

2)原樹T上的MIS節點若收到消息P，將自己到樹根的跳數加上PID中記錄的節點個數，得到此條路徑長的值L。發送消息I，將L值和P消息中的PID信息遞交給樹根s。

3)a)樹根s比較所有消息I中L和時延上界的大小，找出L值小于時延上界的I消息，選出攜帶的PID信息記錄的路徑跳數最小的I消息，發送消息C，攜帶目的節點ID，首先按原樹路徑返回給選出的I消息的發送節點，然后根據PID中記錄的節點經過這些節點到達要接入樹T的目的節點，消息C經過的節點確定上一跳節點為父節點，下一跳節點為子節點，通過這種路徑確認，將該路徑接入到樹T上。b) 若樹根s沒有收到I消息或沒有L值小于時延上界的I消息，通過目的節點的最小時延路徑發送消息C，確認該條路徑為目的節點的組播樹接入路徑。如果發生MIS節點沖突，按照MIS選舉中步驟2)中的方法將新路徑接入到老路徑上，最多增加一跳時延。

4)如有多個最小時延路徑長相等的目的節點，按任意順序重復執行以上步驟。

5)基于已建樹T循環執行步驟1)～4)直到所有目的節點都接入樹T。

推論1 每個目的節點一定能找到一條滿足時延要求的路徑。

證明 由引理4可知，目的節點的支配節點到源節點一定有路徑可達，如果這些路徑都不滿足時延約束，步驟3)用目的節點的時延最小路徑接入源節點。

3 性能分析

算法最終得到一個連通頂點集V′，它是被樹T上所有MIS節點覆蓋的節點集，G(V′)是G(V)的一個連通子圖，Vm∈V′，在G(V′)中Vm和源s是連通的，以Sopt表示圖G(V′)的最小連通支配集(MCDS)的最優解，Vm和源s的MCDS的近似最優解，opt代表MCDS節點個數，得到如下結論:

定理2[16] 在unit-disk graph G=(V，E)中，任何獨立集的大小不超過4opt+1。

定理3 算法得到的近似MCDS最大為8opt+1。

證明 圖G(V′)中的獨立集頂點數|V′MIS|≤4opt+1，在圖G2[U]中，算法最后得到一棵覆蓋所有獨立集節點的樹結構，任意相鄰獨立集節點之間的邊代表一個連接節點，算法得到的MCDS節點個數最多為2|V′MIS|-1=8opt+1。

定理4 算法的時間復雜度為O(n)，消息復雜度為O(n)。

證明 確定時延定界路徑中的MIS節點的時間復雜度小于O(n);在MIS節點選舉階段中每個節點的著色過程需要查詢鄰居節點的顏色信息，著色過程以分布式異步方式進行，所以時間復雜度不超過O(Δn);分布式組播樹構建階段的時間復雜度最大的是步驟1)的P消息的轉發，每個節點都參與轉發的最壞情況下不超過O(Δn)，算法循環執行m次，該階段的時間復雜度為O(mΔn)，所以DCDTC算法的時間復雜度為O(n+Δn+mΔn)=O(n)。

確定時延定界路徑中的MIS節點的消息復雜度小于O(n);在MIS節點選舉階段每個節點除了廣播D消息外，可能發送probe消息，最多發送Δ個，最壞情況下的消息復雜度為O((1+Δ)n);分布式組播樹構建階段的消息復雜度主要決定于步驟1)，每個節點都參與轉發的最壞情況下不超過O(Δn)，算法循環執行m次，消息復雜度為O(mΔn)，所以DCDTC算法的消息復雜度為O(n+(1+Δ)n+mΔn)=O(n)。

在表1中將DCDTC算法與在無線Ad hoc網絡中的構建連通支配集的同類算法進行了比較，可以看出本文提出的算法在有定界時延約束的條件下比其他算法具有更優的時間復雜度和消息復雜度。

表1 DCDTC算法與已有算法的性能比較

算法ratiotimemessagedelay-constrained

文獻[4]Θ(log n)O(n2)O(n2)無

文獻[5]n/2，nΩ(n)O(n2)無

文獻[16]8opt-2O(n)O(n log n)無

文獻[11]8opt+1O(n2)O(nΔ)無

DCDTC8opt+1O(n)O(n)有

4 結束語

本文研究了無線Ad hoc網絡中的組播路由的代價和時延問題，提出了一種新的在UDG圖中以求解MCDS構建組播路由結構的新的分布式算法DCDTC，該算法將組播路由時延定界的概念加入到MCDS構建算法中。理論推導證明了該算法的正確性，近似比為8，證明了其有效性。DCDTC在近似比不低于同類算法的同時具有較已有算法更低的時間復雜度和消息復雜度，并滿足文中定義的組播時延約束。該算法只需要鄰居節點信息，特別是其圖著色階段的異步執行方式的時間復雜度小于一般分布式算法，組播樹構建階段以一種新的路徑添加方式在已定時延上界的約束下試圖減少參與組播通信的節點數目，也即構建的MCDS的勢的大小，分布式的執行方式同時具有較小的時間復雜度和消息復雜度。

參考文獻:

[1]RUIZ P M， GOMEZ-SKARMETA A F. Heuristic algorithms for minimum bandwidth consumption multicast routing in wireless mesh networks[C]//Proc of ADHOC-NOW.2005:258-270.

[2]EPHREMIDES A， WIESELTHIER J， BAKER D. A design concept for reliable mobile radio networks with frequency hopping signaling[J]. Proc of the IEEE，1987，75(1):56-73.

[3]GUHA S， KHULLER S. Approximation algorithms for connected dominating sets[J]. Algorithmica，1998，20(4):374-387.

[4]DAS B， BHARGHAVAN V. Routing in Ad hoc networks using minimum connected dominating set[C]//Proc of IEEE International Conference on Communications.1997.

[5]STOJMENOVIC I， SEDDIGH M， ZUNIC J. Dominating sets and neighbor elimination based broadcasting algorithms in wireless networks[J]. IEEE Trans on Parallel and Distributed Systems，2002，13(1): 14-25.

[6]WAN P J， ALZOUBI K M， FRIEDER O. Distributed construction of connected dominating sets in wireless Ad hoc networks[C]//Proc of IEEE INFCOM.2002.

[7]DAI Fei， WU Jie. Distributed dominant pruning in Ad hoc wireless networks[C]//Proc of International Conference on Communications.2003:353.

[8]SUCEC J， MARSIC I. An efficient distributed network-wide broadcast algorithm for mobile Ad hoc networks[R]. Proc of CAIP Technical Report 248.[S.l.]:Rutgers University，2000.

[9]PENG Wei， LU Xi-cheng. On the reduction of broadcast redundancy in mobile Ad hoc networks[C]//Proc of the 1st ACM International Symposium on Mobile Ad hoc Networking Computing. Boston， Massachusetts: IEEE Press， 2000:129-130.

[10]DAI Fei， WU Jie. Performance analysis of broadcast protocols in Ad hoc networks based on self-pruning[J]. IEEE Trans on Parallel and Distributed Systems，2004，15(11):1027-1040.

[11]許力，林志偉.基于圖著色的無線自組網極小連通支配集算法[J].通信學報，2007，28(3):108-144.

[12]BANIK S M， RADHAKRISHNAN S. Minimizing broadcast latency in Ad hoc wireless networks[C]//Proc of the 45th Annual Southeast Regional Conference. New York: ACM Press，2007:533-534.

[13]HUANG S C H， WAN P J， JIA X， et al. Minimum-latency broadcast scheduling in wireless Ad hoc networks[C]//Proc of the 26th Annual IEEE Conference on Computer Communications.2007:733-739.

[14]CLARK B N， COLBOURN C J， JOHNSON D S. Unit disk graphs[J]. Discrete Mathematics，1990，86(1-3):165-177.

[15]BUCKLEY F， LEWINTER M.圖論簡明教程[M].北京:清華大學出版社，2005.

[16]WAN P J， ALZOUBI K M， FRIEDER O. Distributed construction of connected dominating sets in wireless Ad hoc networks[C]//Proc of IEEE INFCOM.2002.