基于邊選擇的時延抖動受限組播路由算法

摘要：組播技術在多媒體通信的實際應用中十分重要，對各種交互式實時組播業務如視頻會議等來說，不僅要考慮時延約束，而且要考慮時延抖動約束。對基于邊選擇的時延抖動受限的啟發式算法進行了研究，仿真結果表明算法復雜度較低，性能也較好。

關鍵詞：組播路由；邊選擇；時延抖動

中圖分類號：TP311文獻標識碼：A文章編號：1009-3044(2008)19-30170-02

A Delay Variation Constrained Multicast Routing Algorithm based on Alternative Routing

ZENG Hua-pu， SA Li

(Computer Science Engineering College， Jimei University， Xiamen 361021， China)

Abstract: Multicast routing is more and more important in multimedia applications.Delay and delay variation constraints must be taken into account for interactive real-time application such as video-conferences. We present a new heuristic of multicast routing with delay and delay variation constraints in this paper which is based on alternative routing(ARMA). The computer simulations show that the heuristic achieves both low complexity and good performance.

Key words: multicast routing; alternative routing; delay variation

1 引言

隨著通信網絡業務的發展，組播業務正日益增多，不僅對信息傳送的時延有嚴格要求，而且要求組成員之間的同步接收必須滿足目標節點間的時延抖動界限。為此，文獻[1]引入了時延抖動限制，即從源節點到各目的節點的時延之差不能大于某一界限，提出了一種 DVMA(delay variation multicast algorithm)算法。

此算法可以產生很好的結果，返回的組播樹時延抖動很小，但是其算法復雜度O(klmn4)相當高。文獻[2]提出了一種新的算法，通過擴大中間節點的范圍使得路徑選擇的范圍加大，降低復雜度。

但是，非樹節點的中間節點的引入會產生兩種情況：可能導致等待加入的目標節點到源點的路徑本身產生回路；也可能使原來的樹加入路徑后產生回路。因此，我們提出一種基于邊選擇的時延抖動受限的組播路由啟發式算法(ARMA)來解決這個問題，并對文獻[1-2]的算法進行一些改進，使之能以較低的算法復雜度得到較好的性能。

前一種情況可檢查在等待加入路徑中節點的序列是否有重復出現的節點來排除；對于后一種情況，則回溯并找到會產生環路的兩個環節點，找到與第一個(即在待加入路徑節點序列中靠近目標點的環節點)環節點相連的兩條可選環邊，選擇兩條環邊中的一條，使得抖動可能減小，并使生成樹無環。

2 時延抖動受限的啟發式算法

2.1 網絡模型

通信網絡可以用無向圖G=(V，A)表示，其中V是網絡中所有節點組成的集合，節點數為n=|V|；A是圖G中所有邊的集合，邊數為l=|A|，每一條邊表示兩節點間的一條通信鏈路，相鄰兩節點間最多僅有一條邊。每一條邊都對應一個非負時延值，鏈路時延函數為D:A→R+ 。

在組播應用中，信息從源節點s∈V出發，經組播樹T=(VT，AT)到達各目標節點。組播樹T是一棵以s為源節點到達所有目標節點的樹，它是圖G的子圖。目標節點表示為M?哿V-{s}，令m表示目標節點的個數， m=|M|。P(s，v)表示從樹上源節點到目標組播節點v(v∈M)的路徑。

2.2時延抖動受限的問題描述

時延抖動受限的組播路由問題， 其約束條件可以用式(1)和(2)描述.

其中，Δ為時延上限邊界值，δ為任意兩條到達組播節點路徑時延之差，即時延抖動上限邊界值。式(1)和式(2)兩個約束是沖突的，式(1)要求源節點經過短路徑到目標節點，式(2)常放棄最短而選時延更長的路徑，使得時延抖動滿足限制。

2.3 基于邊選擇的啟發式算法(ARMA)

本文借鑒文[1，2]的基本思想，在形成組播樹時，先求源節點到各個目標節點的最短時延路徑，若這些最短時延路徑中最大的路徑時延大于Δ，則需與目標節點重新協商約束邊界；若此時路徑間時延抖動小于δ，即為所求結果，算法結束；否則啟動基于邊選擇的啟發式算法，通過計算可以得到一棵滿足約束(1)、(2)的符合要求的組播樹或是得到一棵滿足約束(1)并且抖動最小的組播樹。

本算法的一個特點是：在加入組播目標節點時，可以使用圖G中的任意節點作為中間節點，中間節點以最短時延路徑來分別連接源節點和待加入目標節點。對于待加入的目標節點，算法在多條含不同中間節點的可選路徑中選擇一條路徑，使得加入路徑后樹的時延抖動最小。

但是，非樹節點的中間節點的引入會產生兩種情況，可能導致待加入目標節點到源點的路徑本身產生回路；也可能使原來的樹加入路徑后產生回路。

對于前一種情況，源節點到待加入目標節點的路徑被中間節點分為兩段，對比源節點到中間節點以及中間節點到待加入目標節點這兩條路徑便可以發現從源節點到待加入目標節點的路徑上是否有環路，并排除掉。只要其中一段路徑中包含有另一段路徑中的節點，則整條路徑中有環路，該路徑不可選。

對于后一種情況，在待選路徑中，算法沿著待加入目標節點到源節點方向回溯，若找到環中的第一條環邊，便找到此環邊的兩個環節點，分別為：第一個環節點同時處在原有樹和待選路徑上，是二者的交點；第二個環節點一定處在待選路徑上，不一定在原有樹上。因此靠近目標節點的環節點便連接有兩條可選邊(其中一條在原有樹上，另外一條在待選路徑上)，算法只選擇其中一條，使得時延抖動可能減小，又能破壞此環路，之后并刪除此環路中非必要的節點。在無環的樹中加入一條路徑后可能產生多個環，因此在最壞情況下，去環過程的重復次數為待選路徑上的節點個數減一。

為了便于比較兩條可選邊的選取對于待加入目標節點的時延抖動和樹中其它目標節點的時延的影響，我們在樹中的每個節點都記錄了每條包含經過此節點的源節點到目標節點路徑的時延值。因此可以判斷出，當打破環路而選擇兩條可選邊中的一條時，得到的結果是否能依然滿足約束條件(1)、(2)。在原有樹中，以第一個環節點為祖先節點的其它目標節點在邊選擇后，它們的時延可能會改變，也要求這些節點必須滿足約束條件(1)、(2)。

2.4 算法描述

算法的步驟如下：

第一步：用Dijkstra最短路徑算法求源節點s和各目標節點v ∈M分別到圖G中各點的最短時延路徑；

第二步：找出s到v ∈M的最短時延路徑中時延最長的路徑的目標節點Vm，求s到Vm的前k條最短時延路徑P1，P2，…，Pk， 以最短路徑P1為起始路徑建立初始樹；

第三步： 設置加入樹中的目標節點數Count＝1。檢查初始樹上是否有不符合約束條件(2)的目標節點，若有不滿足約束(2)的目標節點，則選擇s到Vm的下一條最短路徑建立初始樹，當k條最短路都已試過，轉到第七步；若有滿足約束(2)的目標節點，則標記目標節點為已訪問，計數Count相應增加， 轉到下一步；若路徑中沒有其它目標節點，也轉下一步；

第四步：當組播組M非空時，任選一待加入目標節點v∈M，標記v為已訪問。以圖G中除v之外的每個點為中間節點，共有(n-1)條可選路。每個中間節點都在一條可選路徑P上，中間節點以最短時延路徑分別連接源節點s(產生路徑Ps)和待加入目標節點v(產生路徑Pv)；

第五步： 對于每條可選路徑P，檢查路徑P自身是否會產生環路，對比子路徑Ps和Pv中的節點序列，如果其中一段包含有另一段中的節點， 則路徑P中有環路，該路徑不可選，并選擇下一條中間節點的可選路徑，重復第五步，直到中間節點遍歷節點集{V－v}; 如果路徑P本身無環， 檢查加入P后，原來樹是否會因此產生環路(環路檢查的方法如上文2.3所述，如果有環路，則同時進行邊選擇，以期降低時延抖動)。當加入P后生成的樹中的所有目標節點能滿足約束條件(1)、(2)時，則記錄此路徑P為可行路徑之一。選擇下一條中間節點的待選路徑，重復第五步，直到中間節點遍歷節點集{V－v}之后轉下一步；

第六步：對待加入目標節點，當存在可行路徑時，選擇一條可行路徑，使得結果滿足約束(1)、(2)，并使得時延抖動最小，Count相應增加；當不存在可行路徑時，選擇一條可選路徑，使得結果滿足約束(1)，并且時延抖動最小，Count不變；當組播組M非空時，轉到第四步了；否則組播組訪問結束，此時若count=|M|，則找到一棵滿足約束(1)、(2)的組播樹， 否則返回一棵滿足約束(1)且抖動最小的樹。當s到Vm還有最短路徑未搜索時，選s到Vm的下一條最短路徑建立初始樹，轉到第三步；

第七步：如果得到符合約束條件的組播樹，則輸出所求解中的最優可行解，算法結束；否則，需要與目標節點協商時延抖動約束邊界， 協商成功后轉第二步，若協商不成功，則輸出當前所求到的最優解，算法結束。

3 算法分析

可以證明上述算法最壞情況下的復雜度為O(kmn3)。

證明：上述算法中第一步的復雜度為求m次Dijkstra算法的復雜度，等于O(mn2)；第二步需要計算k條最短路徑，k條最短路徑采用文獻[3]的方法，其復雜度為O(kn3)；第三、四、五、六步在最壞情況下，是求k棵路由樹。求每棵樹時都要加入m個目標節點；每個目標節點都有(n-1)條待選路徑；判斷每條路徑自身是否有環需要O(n2/4)時間(∵|Ps|+|Pv|的值最大為n，則|Ps|*|Pv|最大為n2/4)；在原本無環的樹中，每加入一條路徑都可能產生數量為路徑上節點個數減一的可去掉的環路，而去掉每一個環路需要O(m)時間(∵每次邊選擇都要處理兩個節點上的經過本節點的時延值，而每個節點上的時延值最多為m)，因此，判斷一條可選路徑需要[O(n2/4)+O(m*n)]時間，每個目標節點共有(n-1)條可選路徑；同理，對于每一個目標節點， 要加入一條最優可行路徑樹中，需要O(m*n)時間。因此，求每棵樹的復雜度為m*{(n-1)*[O(n2/4)+O(m*n)]+O(m*n)}， 又m

4 數值實驗

在下面的實驗中，我們首先采用文獻[4]提出的生成網絡的方法隨機地產生網絡，即網絡的n個節點從一個L*L坐標平面中隨機選取，每對節點(u，v)間存在邊的概率為■，其中d(u，v)為歐氏距離。參數α，β從區間(0，1] 中選取。α越大，β距離遠的節點之間邊存在的概率就越大；越大，網絡就越稠密。仿真是在 200 個網絡上進行的，對于每個隨機網絡產生 20 個隨機組播組，因此每個數據點都是經過 4000 次仿真。對算法進行性能比較。組播組的規模分別設置為節點數目的5%和10%， n從40到140。

■■

圖1 組播節點數為5%n時的時延抖動比較圖2 組播節點數為10%n時的時延抖動比較

5 結束語

本文提出基于邊選擇的時延抖動受限組播路由啟發式算法(ARMA)，此算法的優點在于充分利用了中間節點到源節點和目標節點的最短路徑上的鏈路，實驗結果表明本算法在復雜度和性能之間達到很好的折中，時間復雜性較低，而性能良好。

參考文獻：

[1] George N.Rouskas， Baldine I. Multicast routing with end-to-end delay and delay variation constraints[J].IEEE Journal on Selected Areas in Comm，1997，15(3):346-356.

[2] 余燕平.一種時延和時延抖動受約束的啟發式多播路由算法[J].通信學報，2003，24(2).

[3] LAWER E.Combinational Optimization: Networks and Matroids[M].Holt， Rinehart and Winston，1976.

[4] Waxman B M. Routing of multipoint connections[J].IEEE J on Sel Areas in Commun，1988， 6(9):1617-1622.

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文