基于拉格朗日松弛法的受限低代價組播路由算法.pdf

1、目前Internet中現有的傳輸模式仍為單一的盡力而為(best-effort)型服務，無法滿足飛速發(fā)展的多媒體應用和用戶對網絡傳輸質量的更高要求。在這種情況下，以提高網絡資源的利用率、為用戶提供更高服務質量為目標的QoS控制技術應運而生，QoS組播路由技術則是網絡多媒體信息傳輸的關鍵技術之一。 組播是將單一的數據拷貝從源節(jié)點傳送到多個目的節(jié)點的網絡通信方式。實現組播通信的方法一般是建立網絡的組播樹，而QoS組播路由算法就是建立

2、一棵性能良好的滿足服務質量要求的組播樹。因此，建立性能良好的組播樹的QoS組播路由算法就成了本文研究的重點。 本文首先分析了組播技術的基礎理論，隨后介紹了拉格朗日松弛算法的基本原理。通過對現有的幾種典型的受QoS限制的組播路由算法分析后，指出了它們存在的不足，并提出了一種基于拉格朗日松弛法的受限低代價組播路由算法LR-DLMR。該算法具有以下主要特點： (1)算法并未對原網絡拓撲圖創(chuàng)建封閉圖，從而有效利用了鏈路中間節(jié)點信

3、息，也避免了封閉圖對原圖的多播不可達的問題； (2)算法具有比較強的擴展性，為了便于和其它延遲受限的組播路由算法進行性能對比，算法僅將延遲限制條件吸收到線性函數中進行拉格朗日松弛，同樣對于帶寬，丟包率等限制條件也可以吸收到線性函數中進行求解； (3)算法的效率取決于所采用的最小代價組播樹生成算法，這點保證了該算法具有長遠的生命力，只要有新的更優(yōu)的最小代價組播樹生成算法的誕生，就可以套用到該算法中進一步求解滿足延遲限制條件

4、的組播樹； (4)算法具有可調節(jié)性，可以根據用戶需求給算法設定松弛次數，要求在限定的次數內返回一棵組播樹；也可以設定一個大于零的誤差參數ε，要求在前后求得組播樹代價差值只要小于該參數，算法就返回一棵組播樹。 通過嚴格的理論分析，對LR-DLMR算法的正確性進行了證明，并且推理出算法的最壞時間復雜度僅為O(P(M+3/2)n<'2>-pm<'2>n)，n為網絡的節(jié)點數，m為目的節(jié)點數，p為松弛次數。最后，本文通過仿真實驗的