基於模擬退火的動態分布式多播路由方法

2023-05-27 02:46:21

專利名稱：基於模擬退火的動態分布式多播路由方法
技術領域：
本發明屬於網際網路路具有多個服務質量參數的多播路由技術，特別是一種基於模擬退火的動態分布式多播路由方法。
二
背景技術：
作為多播通信的一個重要組成部分，基於服務質量(Quality-of-Service，QoS)約束的多播路由技術已經成為網絡研究領域的重要內容和熱點問題。近年來，隨著實時多媒體業務的出現，具有QoS約束的Steiner(斯坦利)樹問題已成為多播路由問題研究的焦點，該問題已被證明為NP(Nondeterministic Polynomial，非確定多項式)完全問題。
多播路由最初的研究主要集中在無約束的最小代價多播路由問題以及時延約束最小代價多播路由問題。但隨著網絡應用的發展，一些交換式實時通信應用除了要求源節點到目的節點的時延要受到約束以外，還要求時延抖動受到約束。時延抖動約束是為了保證不同的接收者在接收信息時保持同步，不讓某些接收者特別落在後面或特別提前。例如，在遠程電信會議中，講話者被所有與會者同時聽到是很重要的，否則，缺少交互式面對面交談的感覺。
時延及時延抖動約束的多播路由問題目前主要有兩方面的研究一類是不考慮代價優化的問題，稱為DVBMT問題(Delay and Delay Variation Bounded Multicast TreeProblem)；另一類是考慮代價優化的問題，稱為DVBST問題(Delay and Delay VariationBounded Steiner Tree Problem)。
Rouskas在1997年首次提出滿足端到端時延及時延抖動約束的多播路由問題，並給出了一種有效的方法DVMA(Delay Variation Multicast Algorithm)。該方法取得了良好的預期效果，即方法返回的多播樹時延抖動很小，但計算複雜度很高，為O(klmn4)，難以有效地進行多播路由。由於DVMA方法本身結構已經非常煩瑣複雜，Rouskas沒能進一步提出最小化網絡代價的問題並加以解決，因此方法的代價性能不是很好(Rouskas GN，Baldine I. Multicast Routing with End-to-End Delay and Delay Variation Constraints.IEEE Journal on Selected Areas in Communications，1997，15(3)346-356.)。
針對DVMA方法的高複雜度，Sheu等人提出一種快速有效的啟發式方法DDVCA(Delay and Delay Variation Constraint Algorithm)。該方法主要思想基於有核樹(CBT)中核心路由器的概念和最短代價路徑方法，能快速有效地找到滿足時延約束和最小時延抖動的多播樹，方法的時間複雜度為O(mn2)(Sheu P R，Chen S T. A Fast and EfficientHeuristic Algorithm for the Delay-and Delay Variation-bounded Multicast Tree Problem，Computer Communications，2002，25(8)825-833.)。
Low和Lee等人提出的DDVBM(Distributed Delay and Delay Variation BoundedMulticast Algorithm)方法是第一個解決DVBST問題的分布式方法，其計算複雜度為O(n3)。該方法主要分為兩個階段。第一階段主要尋找滿足時延約束的最小代價多播樹，如果該樹違反時延抖動限制，則進入第二階段，即通過調用路徑搜索過程來尋找同時滿足時延及時延抖動約束的最小代價樹。但DDVBM方法忽略了多播組中的目的節點也可以作為中間節點轉發分組，因此在計算輔助的Steiner Node Tree時，有可能無法建立連接源節點與所有Steiner節點的多播樹，導致方法無法繼續執行(Low C P，Lee Y J.Distributed Multicast Routing，with End-to-End Delay and Delay Variation Constrains.Computer Communications，2000，23(9)848-862.)。
王明中等人在研究DVBST問題的過程中，發現當前眾多方法所普遍使用的兩個最佳鏈路選擇函數並不能完全體現路由的動態過程，而且在某種特定的情況下可能無法實現「多播可達」，即由其生成的結果多播樹中可能不包含所有的目的節點。為此，他提出一個關於「多播可達」的限定性條件和一個新的最佳鏈路選擇函數，並在此基礎上設計了一個新的啟發式方法DDVBMRA(Delay and Delay Variation Bounded Multicast RoutingAlgorithm)，方法的時間複雜度為O(mn2)。但該方法在運行中會出現所有的網絡節點都已被訪問過，而此時Sub(M)仍然不等於目的節點集的情況，從而導致DDVBMRA方法無法獲得可行的多播樹(王明中，謝劍英，張敬轅.時延及時延抖動限制的最小代價多播路由策略.計算機學報，2002，25(5)534-541.)。
餘燕平在其博士論文中提出了另一種啟發式方法LCDVMA(Low-cost DelayVariation-constrained Multicast Algorithm)，構建滿足時延和時延抖動約束的網絡代價優化的多播樹。該方法主要思想是每次通過最短代價路徑或最短時延路徑連到樹上的任一節點，再通過比較找出最理想的路徑並添加到樹上，方法複雜度為O(mkn3)。由於該方法增加了可選路徑的範圍，從而導致多播樹的時延抖動增大(餘燕平.多播路由算法研究.浙江大學博士論文，2002.)。
郭偉等人把時延及時延抖動約束的多播路由問題提到優化的層次上，證明了DVBST問題是NP完全問題，繼而提出一種基於動態罰函數法的啟發式遺傳方法以求解該問題。該方法使用遺傳算法選擇Steiner點，並對選定的Steiner點，使用類似最小生成樹啟發式方法的方法求解Steiner樹。由於該方法採用罰函數法將不可行解可行化，從而擴大了搜索區域，增加了計算時間(郭偉，席裕庚.有時延及時延差別約束的最小代價組播路由問題.通信學報，2001，22(6)13-20.)。
現有的這些QoS約束的多播路由方法在應用到實時通信網絡中存在以下四個問題(1)大多數現有方法都是集中式的，集中式方法需要中心節點(或每個節點)負責計算整個路由樹，該節點必須掌握整個網絡結構的詳細信息。在大規模網絡中，會存在容錯性差、中心節點的計算負荷過重、以及路由信息不準確等問題。
(2)現有的分布式方法仍然需要每個節點維護整個網絡的部分狀態信息，或多或少會存在集中式方法的問題。而且，這些分布式方法具有通信代價高、連接建立時間過長、路由樹的質量差等缺點。
(3)只有少數方法考慮了多播成員的動態改變問題。由於在許多多播應用中，多播成員會自由地動態加入或離開多播會話。因此，確保多播成員的動態改變而不影響當前連接的正常通信、使多播樹的破壞程度最小是非常重要的。
(4)在時延和時延抖動雙重約束下尋找一棵最優多播樹是相當困難的。在多播路由中，最小化網絡代價往往會和時延或時延抖動限制相衝突。因此，對研究人員來說，設計同時滿足時延和時延抖動約束的Steiner樹方法，特別是分布式方法，就非常困難。
三

發明內容
本發明的目的在於提供一種基於模擬退火的動態分布式多播路由方法，本方法不僅可以以一種分布式方式構造出滿足時延和時延抖動約束的最小代價多播路由樹，而且當多播成員的動態變化時，進行多播樹的動態重組，並保證多播會話的破壞程度最小。
實現本發明目的的技術解決方案為一種基於模擬退火的動態分布式多播路由方法，包括初始解構造過程和最優解構造過程，即1.1所述的初始解構造過程的步驟如下1.1.1使用分布式k-Bellman-Ford第k條最短路徑方法計算從源節點s到每個目的節點m∈M的前k條最短時延路徑，作為備選路徑集，其中M為目的節點集，又稱多播組；1.1.2隨機選擇一個目的節點，並將備選路徑集中源節點s到該目的節點的最短時延路徑添加到初始多播樹T0中，其中T0的初始狀態為一棵空樹；1.1.3在備選路徑集中選擇從源節點s到樹外目的節點m滿足式max{0，maxd-δ}≤d(p(s，m))≤min{mind+δ，Δ}的第一條備選路徑，該m∈M，mT0，並將其添加到T0中，其中d(p(s，m))表示從源節點s到目的節點m的路徑時延；maxd和mind分別表示從源節點s到T0中包括的目的節點的路徑中路徑的最大時延和最小時延，Δ和δ分別為多播會話的時延上限和時延抖動上限；1.1.4重複步驟1.1.3，直到M中的所有目的節點都包括在T0中，至此初始解構造過程結束，該過程構造的初始多播樹T0將作為最優解構造過程的初始解；1.2所述的最優解構造過程的步驟如下1.2.1設置Tbest＝Tnow＝T0，其中Tbest表示到目前為止代價最小的多播樹，即最優解，Tnow表示當前多播樹，即當前解；1.2.2設定初始溫度t＝t0；1.2.3若在該溫度達到內循環終止準則，則進入步驟1.2.8；否則進入下一步驟1.2.4；1.2.4用鄰域解構造過程產生當前解Tnow的鄰域解集N(Tnow)，並從中隨機選擇一棵多播樹Tnext，計算Δc＝cost(Tnext)-cost(Tnow)，其中cost(Tnext)和cost(Tnow)分別表示多播樹Tnext和當前解Tnow的代價；1.2.5如果Δc≤0或者exp(-Δc/t)＞random(0，1)，Tnow＝Tnext；1.2.6如果cost(Tnow)＜cost(Tbest)，其中cost(Tbest)表示最優解的代價，Tbest＝Tnow；
1.2.7重複步驟1.2.3～步驟1.2.6；1.2.8退溫，t＝λ·t，其中λ為退溫速率；若滿足終止規則，終止計算，否則回到步驟1.2.3；至此最優解構造過程結束，該過程的輸出就是最終滿足時延和時延抖動約束的一棵最小代價多播樹。
本發明基於模擬退火的動態分布式多播路由方法的鄰域解構造過程通過交換路徑在可行解範圍內構造鄰域解集，其步驟如下步驟1在當前多播樹Tnow中隨機選擇一個葉子目的節點m；步驟2從目的節點m起，刪除當前多播樹Tnow中通向源節點s的鏈路，直到遇到另一個目的節點或者源節點，形成一棵子樹Tsub；步驟3計算當前子樹Tsub中從源節點s到每個目的節點路徑的最大時延maxd和最小時延mind；步驟4在備選路徑集中，將時延在[max{0，maxd-δ}，min{mind+δ，Δ}]之間、且從源節點s到目的節點m的備選路徑加入到當前子樹Tsub中；如果形成的新樹無環，則成為當前多播樹Tnow的一個鄰域解；步驟5重複步驟4，直到所有k條備選路徑都檢查過。
本發明基於模擬退火的動態分布式多播路由方法在構造滿足時延和時延抖動約束的一棵最小代價多播樹後，會出現多播成員動態地加入或離開多播會話的情況，這時需要動態重組多播樹目的節點，並確保重組後的多播樹仍然滿足時延和時延抖動約束，所述的動態重組方法如下當目的節點成員m∈M請求「離開」多播組，分兩種情況(1)如果目的節點m不是一個葉子節點，這種情況不對多播樹做任何改變，只要讓該節點停止向自己的用戶轉發分組數據即可；(2)如果目的節點m是一個葉子節點，那麼它向多播樹的源節點方向發送leave request消息，一個節點接一個節點，直到該消息到達源節點或另一個目的節點；消息所經過的鏈路將被刪除；當新節點vM請求「加入」多播組，那麼它向源節點發送join request消息，分三種情況(1)如果v不是樹中的節點，則獲得從源節點到節點v的前k條最短時延路徑，並選擇第一條時延在[max{0，maxd-δ}，min{mind+δ，Δ}]之間路徑加入到當前多播樹中；如果無法找到這樣的路徑，則拋棄節點v的加入請求；(2)如果v是樹中的節點，且新的多播組M∪{v}滿足時延抖動上限δ，則該多播樹本身就是一棵可行樹；(3)如果v是樹節點，且新的多播組M∪{v}不滿足時延抖動上限δ，說明節點v必定是源節點到一個或多個目的節點路徑上的中間節點；這種情況下，刪除這條包含v和這些目的節點的路徑，再將節點v和這些目的節點依次加入到路由樹中。
本發明與現有技術相比，其顯著優點為(1)以完全分布式的方式構造滿足時延和時延抖動最小代價的多播樹；(2)根據目的節點的改變，能動態重組多播樹，並確保對多播樹的破壞程度最小；(3)通過交換路徑進行的鄰域解構造過程克服了搜索區域擴大、計算時間增加等現有方法的缺點，並確保最優樹滿足時延和時延抖動約束；(4)具有收斂速度快、編解碼簡單以及實時性好的特點；(5)代價小，而且時延、時延抖動和路由成功率的性能也相當好。
四


圖1是本發明基於模擬退火的動態分布式多播路由方法的流程圖。
圖2是本發明基於模擬退火的動態分布式多播路由方法的鄰域解構造過程的流程圖。
圖3是本發明基於模擬退火的動態分布式多播路由方法運用實例的網絡拓撲圖。
圖4是本發明運用實例的初始解構造過程示意圖。
圖5是本發明運用實例的鄰域解構造過程示意圖。
圖6是本發明的實驗模擬結果-網絡節點數和多播樹代價的關係。
圖7是本發明的實驗模擬結果-目的節點數和多播樹代價的關係。
五
具體實施例方式
下面結合附圖對本發明作進一步詳細描述。
結合圖1，為尋找滿足時延和時延抖動約束的最小代價多播路由樹，本發明基於模擬退火的動態分布式多播路由方法包括初始解構造過程和最優解構造過程，即1.1所述的初始解構造過程是在不考慮代價前提下，構造一棵滿足端到端時延和時延抖動約束的多播樹，將其作為最優解構造過程的初始可行解，其步驟如下1.1.1使用分布式k-Bellman-Ford第k條最短路徑方法計算從源節點s到每個目的節點m∈M的前k條最短時延路徑，作為備選路徑集，其中M為目的節點集，又稱多播組；1.1.2隨機選擇一個目的節點，並將備選路徑集中源節點s到該目的節點的最短時延路徑添加到初始多播樹T0中，其中T0的初始狀態為一棵空樹；1.1.3在備選路徑集中選擇從源節點s到樹外目的節點m滿足式max{0，maxd-δ}≤d(p(s，m))≤min{mind+δ，Δ}的第一條備選路徑，該m∈M，mT0，並將其添加到T0中，其中d(p(s，m))表示從源節點s到目的節點m的路徑時延；maxd和mind分別表示從源節點s到T0中包括的目的節點的路徑中路徑的最大時延和最小時延，Δ和δ分別為多播會話的時延上限和時延抖動上限；1.1.4重複步驟1.1.3，直到M中的所有目的節點都包括在T0中，至此初始解構造過程結束，該過程構造的初始多播樹T0將作為最優解構造過程的初始解；1.2所述的最優解構造過程是通過模擬退火不斷迭代降低初始多播樹的代價，但不違反時延和時延抖動的限制，最終獲得最小代價的多播樹，其步驟如下1.2.1設置Tbest＝Tnow＝T0，其中Tbest表示到目前為止代價最小的多播樹，即最優解，Tnow表示當前多播樹，即當前解；1.2.2設定初始溫度t＝t0；1.2.3若在該溫度達到內循環終止準則，則進入步驟1.2.8；否則進入下一步驟1.2.4；1.2.4用鄰域解構造過程產生當前解Tnow的鄰域解集N(Tnow)，並從中隨機選擇一棵多播樹Tnext，計算Δc＝cost(Tnext)-cost(Tnow)，其中cost(Tnext)和cost(Tnow)分別表示多播樹Tnext和當前解Tnow的代價；
1.2.5 如果Δc≤0或者exp(-Δc/t)＞random(0，1)，Tnow＝Tnext；1.2.6 如果cost(Tnow)＜cost(Tbest)，其中cost(Tbest)表示最優解的代價，Tbest＝Tnow；1.2.7 重複步驟1.2.3～步驟1.2.61.2.8 退溫，t＝λ·t，其中λ為退溫速率；若滿足終止規則，終止計算，否則回到步驟1.2.3；至此最優解構造過程結束，該過程的輸出就是最終滿足時延和時延抖動約束的一棵最小代價多播樹。
上述方法的詳細說明如下。
假定以帶權簡單無向圖G＝(V，E)表示一個網絡。其中，V，E分別是網絡節點和鏈路集合。對於每條鏈路e∈E，定義兩個正實數函數代價函數cost(e)E→R+和時延函數delay(e)E→R+，其中R+表示正實數集。給定多播會話的源節點s∈V，一組目的節點MV-{s}，m表示目的節點集M中的一個目的節點，多播樹T(TG)是根為s，並包含目的節點集合M的一棵樹。
定義時延和時延抖動約束最小代價多播樹時延和時延抖動約束最小代價多播樹是一棵從源節點s出發，連接所有目的節點M的多播路由樹T(VT，ET)，且滿足●時延約束T==max(ep(s,m)d(e))---(1)]]>●時延抖動約束T=maxu,vM{|ep(s,u)d(e)-ep(s,v)d(e)|}]]>●代價約束在滿足條件(1)、(2)的所有多播樹中，cost(T)=eTcost(e)]]>最小。
其中，ΔT，δT，cost(T)分別表示多播樹T的時延、時延抖動和代價。
假設每個節點具有到每個目的節點的k條最短時延路徑和其路徑時延。這些信息存儲在每個節點的本地路由表中，用Route表示，並通過運行分布式kBF方法計算時延度量值獲得。在Route中，每個節點v∈V含有k×|M|個條目，每個條目對應一個目的節點的第k條最短路徑。條目Route[i][m]有兩個欄位Route[i][m].n和Route[i][m].d，分別表示v到m的第i條最短時延路徑上的下一個鄰接節點以及這條路徑的時延大小。另外，對於最優解構造過程中的每棵多播樹Tnow，假設每個節點存儲其前一個鄰接節點(沿源節點方向)到每個目的節點的逆向路由信息，用RevRoute來表示此路由信息。每個節點v有|M|個條目，其中，條目RevRoute[m]有一個欄位RevRoute[m].p表示Tnow中s到目的節點m路徑中v的前一個鄰接節點。
控制消息的數據結構用一個三元組type，kth，dest表示，其中type表示消息類型、kth表示備選路徑集中第k條最短時延路徑、dest表示當前選擇的目的節點。本發明用到了9種主要消息類型，如表1所示表1本發明的消息類型

系統中的每個節點執行相同的路由方法，初始為空狀態等待連接建立請求。在初始解構造過程中，當節點收到打開多播連接的請求(open消息)，該請求帶有如下參數目的節點集M，時延上限Δ和時延抖動上限δ。該節點利用分布式kBF方法計算s到每個目的節點m∈M的前k條最短時延路徑。設Pm表示目的節點m的前k條最短時延路徑，即Pm＝{p1(s，m)，p2(s，m)，...，pk(s，m)}，其中，d(p1(s，m))≤d(p2(s，m))≤...≤d(pk(s，m))。
當源節點s收到ini_start請求後，初始多播樹T0被初始化為一棵空樹，並隨機選擇一個目的節點m。設maxd和mind分別表示從源節點s到當前T0中包括的目的節點的路徑中路徑的最大時延和最小時延，初始值均為d(p1(s，m))(即Route[1][m].d)。ini_add連接消息ini_add，1，m被發送到沿路徑p1(s，m)的下一個鄰接節點v，並且鏈路(s，v)被加到多播樹T0上。
當ini_add消息在傳遞到指定目的節點m的過程中到達一個中間節點u後，節點u又將ini_add消息ini_add，kth，m傳遞給它的下一個鄰接節點u′(u′＝Route[kth][m].n)，隨後鏈路(u，u′)被加到多播樹T0上。
當ini_add消息到達指定的目的節點後，ini_notify消息被送往源節點s，告知一個目的節點已被加入到多播樹上。收到ini_notify消息後，選擇一個樹外的目的節點，例如m′。然後，從備選路徑集中選出時延在[max{0，maxd-δ}，min{mind+δ，Δ}]之間的第一條備選路徑。假設這條備選路徑是第i條最短時延路徑，那麼ini_add，i，m′消息被送往沿該路逕到m′方向的下一個鄰接節點v′。在更新maxd和mind的值後，鏈路(s，v′)被加到多播樹T0上。
上述幾個步驟在目的節點之間重複進行，直到M中的所有目的節點都包括在多播樹T0中。當ini_add請求消息到達M中的最後一個目的節點，該節點向源節點s發送ini_finish消息。這樣，構造滿足時延和時延抖動的初始多播樹過程完成，方法進入最優解構造過程，並將多播樹T0作為模擬退火的初始解。
最優解構造過程調用模擬退火方法不斷迭代降低初始多播樹的代價，而不違反時延和時延抖動約束，最終獲得最小代價的多播路由樹。其中，模擬退火參數設置如下●多播樹的編解碼T=p(s,m1)p(s,m2)...p(s,m|M|)=i=1|M|p(s,mi),]]>其中mi∈M，1≤i≤|M|，p(s，mi)表示多播樹T中源節點s到目的節點mi∈M的路徑。
●初始溫度t0＝100；●評價函數f(x)＝cost(x)；
●退溫策略ti+1＝λ·ti，其中i≥0，λ＝0.9，λ稱為退溫速率；●狀態接受函數Aij(t)=1,cost(Ti)cost(Tj)exp(-cij/t),cost(Ti),cost(Tj)]]>其中，Aij(t)表示從當前解Ti的鄰域N(Ti)中隨機選取解Tj後，接受Tj的概率；t為當前溫度；Δcij是狀態Ti與Tj的目標差，即Δcij＝cost(Ti)-cost(Tj)。
●內循環終止準則只要最優解連續20次迭代沒有改善，則進行退溫；●終止規則設置最大迭代次數為100。
最優解構造過程的關鍵問題是鄰域解集的產生，本發明通過交換路徑在可行解範圍內構造鄰域解集，即通過交換路徑在可行解範圍內構造鄰域解集，從而克服了現有方法採用罰函數策略中存在的搜索區域擴大、計算時間增加等缺點，並確保最終的最優樹滿足時延和時延抖動約束。
結合圖2，所述的鄰域解構造過程的步驟如下在構造當前樹Tnow的鄰域解過程中，一個被選擇的葉子目的節點m收到gn_start消息後，會將gn_delete，/，m消息沿s到m的路徑向源節點s方向逐節點傳遞，直到該消息被傳送到源節點或其它目的節點。消息傳遞所通過的每條鏈路都被刪除，Tnow刪除這些鏈路後所形成的子樹用Tsub表示，其中Tsub被初始化為Tnow。假設Tnow中路徑p(s，m)上目的節點m的前一個鄰接節點為v，v可通過逆向路由表RevRoute得到(v＝RevRoute[m].p)。接著gn_delete，/，m消息被送往節點v，並且鏈路(m，v)從Tsub中刪除。
當一個中間節點收到gn_delete消息後，立即將該消息傳遞到它的下一個鄰接節點上。否則，如果源節點或另一個目的節點收到gn_delete消息，意味著刪除路徑的操作結束。接下來，選擇備選路徑集中其它到目的節點m的備選路徑來代替被刪除的路徑，形成Tnow的新鄰域解。在源節點或另一個目的節點上，首先計算通向Tsub子樹中包含的所有目的節點的路徑的最大和最小時延(分別用maxd和mind表示)，隨後向源節點發送gn_add消息gn_add，1，m開始進行添加操作。
設T代表Tnow的一棵新的鄰域多播樹，初始時包含Tsub的所有鏈路。當一個中間節點v收到gn_add消息，它將該消息傳遞到下一個節點v′，其中，v′是在通向目的節點m的第k條備選路徑上v的鄰接節點。隨後，鏈路(v，v′)加入到多播樹T中。
當源節點s收到gn_add消息後，指定的目的節點m以及kth的值從消息中提取出來並記錄在源節點中。源節點反覆選擇一條s到m的備選路徑，直到該路徑的時延在[max{0，maxd-δ}，min{mind+δ，Δ}]之間。如果所有k條備選路徑都被訪問過，則發送gn_finish消息到源節點s，告知鄰域解構造結束。否則，向源節點s的下一個鄰接節點u發送gn_add，kth，m消息，並且將(s，u)鏈路加入到多播樹T中。
當gn_add消息到達指定目的節點，表明成功生成了一棵新的鄰域多播樹T。如果T無環，則將其插入鄰域解集N(Tnow)中作為Tnow的一個鄰域解。隨後檢查kth的值，如果kth值大於k，則向源節點s發送gn_finish消息。否則，kth值加1，並將gn_add，kth，m消息送往源節點s以檢查下一條備選路徑。
添加操作將每條通向指定的葉子目的節點的備選路徑添加到子樹Tsub上，直到所有k條最短時延路徑都被訪問過。當gn_finish消息被發送到源節點後，即完成了鄰域解的構造。
當通過本發明的初始解構造過程和最優解構造過程完成一棵滿足時延和時延抖動約束的最小代價多播樹後，會出現多播成員動態地加入或離開多播會話的情況，這時需要動態重組多播樹目的節點。目前，在網際網路上已經出現了標準的多播組管理協議(Internet Group Management Protocol，IGMP)用於處理多播組動態改變的問題。但由於網際網路本身的特性，在多播組成員之間不存在邏輯連接，所以IGMP沒有考慮網絡代價，從而直接將IGMP應用於多媒體多播會話中是不合適的。同時，為了支持多播組的動態重組，如果按照新的目的節點集來重新構造多播樹的話，將會阻斷正在進行的多播會話，而這一會話只能在新的多播樹建立完畢之後才可以重新開始。因此這種動態重組的方法也是不可取的。為此，本發明提供如下的多播樹的動態重組方法當目的節點成員m∈M請求「離開」多播組，分兩種情況(1)如果目的節點m不是一個葉子節點，這種情況不對多播樹做任何改變，只要讓該節點停止向自己的用戶轉發分組數據即可；(2)如果目的節點m是一個葉子節點，那麼它向多播樹的源節點方向發送leave request消息，一個節點接一個節點，直到該消息到達源節點或另一個目的節點；消息所經過的鏈路將被刪除；當新節點vM請求「加入」多播組，那麼它向源節點發送join request消息，分三種情況(1)如果v不是樹中的節點，則獲得從源節點到節點v的前k條最短時延路徑，並選擇第一條時延在[max{0，maxd-δ}，min{mind+δ，Δ}]之間路徑加入到當前多播樹中；如果無法找到這樣的路徑，則拋棄節點v的加入請求；(2)如果v是樹中的節點，且新的多播組M∪{v}滿足時延抖動上限δ，則該多播樹本身就是一棵可行樹；(3)如果v是樹節點，且新的多播組M∪{v}不滿足時延抖動上限δ，說明節點v必定是源節點到一個或多個目的節點路徑上的中間節點；這種情況下，刪除這條包含v和這些目的節點的路徑，再將節點v和這些目的節點依次加入到路由樹中。
下面通過一個實施例來說明本發明工作的過程。
網絡拓撲結構如圖3所示，其中s＝{F}，M＝{B，D，E，H}，圖中實心圓圈表示源節點，粗線圓圈表示目的節點，每條鏈路的括號內標註的是該鏈路的代價和時延值，給定時延約束Δ和時延抖動約束δ分別為10、3。通過分布式kBF方法得到的備選路徑集如表2所示，其中k＝5。
表2實例網絡的備選路徑集

圖4顯示了運用實例的初始解構造過程。首先選擇目的節點D，並且F到D的最小時延路徑(F，D)被加入到空樹上，如圖4(a)所示。接著，E成為下一個加入的目的節點。由於maxd和mind都為2，因此選擇通向E的第一條時延在
的備選路徑。結果時延為3的路徑(F，D，E)加入T0中，如圖4(b)所示。隨後，通過相同方式加入路徑(F，D，C，G，B)，目的節點B也包含在T0中，如圖4(c)所示。此時，maxd和mind分別更新為5和2。考慮最後一個目的節點H，第一條從F到H且時延分布在[max{0，5-3}，min{2+3，10}](i.e.[2，5])的備選路徑是{F，H}，因此路徑{F，H}被加入到T0中，如圖4(d)所示。至此，初始解構造過程結束。
對於鄰域解的構造過程，假設當前解為圖4(d)所示的T0。隨機選擇目的節點E，且路徑{F，D，E}從樹T0中刪除。注意，由於D是一個目的節點，所以只有鏈路(D，E)被刪除，刪除後的子樹如圖5(a)所示。此時，maxd和mind分別為5和2。從表2可知，除了被刪除的路徑{F，D，E}外，只有兩條路徑的時延分布在[2，5]之間，即(F，H，E)和(F，A，E)。因此，將這兩條路徑分別加入子樹中，就形成了T0的兩個鄰域解，如圖5(b)和(c)所示。圖5(d)給出了運用本發明得到的實例網絡的最優多播樹。初始解T0、T0的兩個鄰域解以及最優解的編碼如表3所示。
表3解的編碼情況

目前，我們已經通過實驗模擬驗證了本發明具有良好的性能。在評價過程中，採用隨機網絡拓撲方法產生節點度數為4的拓撲網絡圖，網絡節點隨機分布的矩形區域大小設定為4000km×2400km，每條鏈路的容量為155Mbps。任意兩個節點u和v之間是否存在鏈路概率函數P(u，v)＝βexp(-l(u，v)/α·L)確定，其中l(u，v)是u，v之間的歐拉距離，L是任意兩節點間的最大距離，較小的α將增大短鏈路的密度，較大的β將導致較高的鏈路密度，我們取α＝0.15，β＝2.2。網絡的鏈路時延定義為鏈路的傳輸時延，忽略排隊時延和發送時延，傳輸速度為光速的2/3，鏈路代價在[10，120]Mbps之間隨機分布。每個模擬點的實驗次數為200，每次隨機產生網絡拓撲和源/目的節點，然後統計平均值。
我們選取現有的DVMA、SPT(分布式Bellman-Ford最短路徑樹方法，Bellman RE，Dynamic programming，Princeton University，Princeton，NJ，1957.)、DDVBM和DDVMBRA方法和本發明所述方法進行比較。首先比較了這幾種方法所獲得多播樹的代價性能，其中，圖6是固定目的節點數為5，Δ＝35ms，δ＝20ms情況下，網絡節點數和代價的關係。圖7是固定網絡節點數為50，Δ＝35ms，δ＝20ms情況下，目的節點數和代價的關係。圖6和圖7兩幅圖表明，和DVMA、SPT、DDVBM、DDVMBRA方法相比，本方法所獲得的多播樹代價最低，代價性能最好。從圖6可以看出，所有方法求得的多播樹的代價隨著網絡節點數的增加而增加。這是由於隨著網絡規模的增大，源節點到達各個目的節點的路徑長度隨之增加，從而使得樹的代價增加。從圖7可以看出，所有方法求得的多播樹的代價隨著目的節點數的增加而增加。這是因為，隨著目的節點數的增加，多播樹的規模就會變大，因而佔用更多的資源，導致相應的代價增加。
類似上述實驗方法，我們還模擬驗證了這些多播路由方法所獲得多播樹的時延、時延抖動、路由成功率、以及收斂性等性能，所有實驗表明，本方法在時延、時延抖動以及路由成功率等方面都表現出了良好的性能，並且本方法具有較快的收斂速度，滿足實時通信的要求。
權利要求
1.一種基於模擬退火的動態分布式多播路由方法，其特徵在於包括初始解構造過程和最優解構造過程，即1.1所述的初始解構造過程的步驟如下1.1.1使用分布式k-Bellman-Ford第k條最短路徑方法計算從源節點s到每個目的節點m∈M的前k條最短時延路徑，作為備選路徑集，其中M為目的節點集，又稱多播組；1.1.2隨機選擇一個目的節點，並將備選路徑集中源節點s到該目的節點的最短時延路徑添加到初始多播樹T0中，其中T0的初始狀態為一棵空樹；1.1.3在備選路徑集中選擇從源節點s到樹外目的節點m滿足式max{0，maxd-δ}≤d(p(s，m))≤min{mind+δ，Δ}的第一條備選路徑，該m∈M，mT0，並將其添加到T0中，其中d(p(s，m))表示從源節點s到目的節點m的路徑時延；maxd和mind分別表示從源節點s到T0中包括的目的節點的路徑中路徑的最大時延和最小時延，Δ和δ分別為多播會話的時延上限和時延抖動上限；1.1.4重複步驟1.1.3，直到M中的所有目的節點都包括在T0中，至此初始解構造過程結束，該過程構造的初始多播樹T0將作為最優解構造過程的初始解；1.2所述的最優解構造過程的步驟如下1.2.1設置Tbest＝Tnow＝T0，其中Tbest表示到目前為止代價最小的多播樹，即最優解，Tnow表示當前多播樹，即當前解；1.2.2設定初始溫度t＝t0；1.2.3若在該溫度達到內循環終止準則，則進入步驟1.2.8；否則進入下一步驟1.2.4；1.2.4用鄰域解構造過程產生當前解Tnow的鄰域解集N(Tnow)，並從中隨機選擇一棵多播樹Tnext，計算Δc＝cost(Tnext)-cost(Tnow)，其中cost(Tnext)和cost(Tnow)分別表示多播樹Tnext和當前解Tnow的代價；1.2.5如果Δc≤0或者exp(-Δc/t)＞random(0，1)，Tnow＝Tnext；1.2.6如果cost(Tnow)＜cost(Tbest)，其中cost(Tbest)表示最優解的代價，Tbest＝Tnow；1.2.7重複步驟1.2.3～步驟1.2.6；1.2.8退溫，t＝λ·t，其中λ為退溫速率；若滿足終止規則，終止計算，否則回到步驟1.2.3；至此最優解構造過程結束，該過程的輸出就是最終滿足時延和時延抖動約束的一棵最小代價多播樹。
2.根據權利要求1所述的基於模擬退火的動態分布式多播路由方法，其特徵是鄰域解構造過程通過交換路徑在可行解範圍內構造鄰域解集，其步驟如下步驟1在當前多播樹Tnow中隨機選擇一個葉子目的節點m；步驟2從目的節點m起，刪除當前多播樹Tnow中通向源節點s的鏈路，直到遇到另一個目的節點或者源節點，形成一棵子樹Tsub；步驟3計算當前子樹Tsub中從源節點s到每個目的節點路徑的最大時延maxd和最小時延mind；步驟4在備選路徑集中，將時延在[max{0，maxd-δ}，min{mind+δ，Δ}]之間、且從源節點s到目的節點m的備選路徑加入到當前子樹Tsub中；如果形成的新樹無環，則成為當前多播樹Tnow的一個鄰域解；步驟5重複步驟4，直到所有k條備選路徑都檢查過。
3.根據權利要求1所述的基於模擬退火的動態分布式多播路由方法，其特徵在於在構造滿足時延和時延抖動約束的一棵最小代價多播樹後，會出現多播成員動態地加入或離開多播會話的情況，這時需要動態重組多播樹目的節點，並確保重組後的多播樹仍然滿足時延和時延抖動約束，所述的動態重組方法如下當目的節點成員m∈M請求「離開」多播組，分兩種情況(1)如果目的節點m不是一個葉子節點，這種情況不對多播樹做任何改變，只要讓該節點停止向自己的用戶轉發分組數據即可；(2)如果目的節點m是一個葉子節點，那麼它向多播樹的源節點方向發送leave request消息，一個節點接一個節點，直到該消息到達源節點或另一個目的節點；消息所經過的鏈路將被刪除；當新節點vM請求「加入」多播組，那麼它向源節點發送join request消息，分三種情況(1)如果v不是樹中的節點，則獲得從源節點到節點v的前k條最短時延路徑，並選擇第一條時延在[max{0，maxd-δ}，min{mind+δ，Δ}]之間路徑加入到當前多播樹中；如果無法找到這樣的路徑，則拋棄節點v的加入請求；(2)如果v是樹中的節點，且新的多播組M∪{v}滿足時延抖動上限δ，則該多播樹本身就是一棵可行樹；(3)如果v是樹節點，且新的多播組M∪{v}不滿足時延抖動上限δ，說明節點v必定是源節點到一個或多個目的節點路徑上的中間節點；這種情況下，刪除這條包含v和這些目的節點的路徑，再將節點v和這些目的節點依次加入到路由樹中。
全文摘要
本發明公開了一種基於模擬退火的動態分布式多播路由方法。它是以一種分布式方式構造出滿足時延和時延抖動約束的最小代價多播路由樹，並支持多播樹的動態重組。本發明由初始解構造過程和最優解構造過程組成。其中，初始解構造過程是在不考慮代價前提下，構造一棵滿足端到端時延和時延抖動約束的初始多播樹；最優解構造過程是通過模擬退火不斷迭代降低初始多播樹的代價，通過交換路徑在可行解範圍內構造鄰域解解，最終獲得滿足條件的多播樹。採用本發明的方法可支持多播樹的動態重組，構造代價很小、網絡性能較好的多播樹，解決現有方法中搜索區域大、計算時間長等問題，並具有收斂速度快、實時性好的特點。
文檔編號H04L12/56GK1968122SQ20061008614
公開日2007年5月23日 申請日期2006年9月4日 優先權日2006年9月4日
發明者張琨, 王珩, 張宏, 劉鳳玉, 嚴悍 申請人:南京理工大學