聚合組播算法研究.pdf

1、近年來，隨著在Internet上流媒體、視頻點播等業(yè)務的相繼開展，IP組播技術得到了快速的發(fā)展。組播是一種有效的支持多點通信的機制，它采用樹轉發(fā)結構，每一個數(shù)據(jù)包只在節(jié)點處被復制，在每一條鏈路上只發(fā)送一次。這種方法使IP組播能有效的同時向組成員發(fā)送數(shù)據(jù)，并支持大量的組播組。IP組播是Internet上流媒體、視頻會議等高帶寬、共享型應用的重要基礎。 然而，一棵組播分布樹要求所有樹節(jié)點保持每一個組的轉發(fā)狀態(tài)，因此，當多個組播組并存

2、于網(wǎng)絡當中的時候，IP組播遇到一系列問題：隨著組播組個數(shù)的增加，組播轉發(fā)狀態(tài)增多，組播樹上路由器的內(nèi)存需求隨之增大；同時，由于每個數(shù)據(jù)包的轉發(fā)需要進行地址查找，進行組播轉發(fā)查詢的CPU開銷也隨之增大，轉發(fā)過程也會變慢。當網(wǎng)絡中的組播會話數(shù)很大時，需要大量的資源和控制開銷來管理組播組。組播轉發(fā)狀態(tài)數(shù)是制約網(wǎng)絡中大規(guī)模組播應用可擴展性的瓶頸。 聚合組播技術就是針對大規(guī)模組播可擴展性問題、結合真實網(wǎng)絡拓撲結構特點提出來的。其主要思想是

3、適當放寬對節(jié)約帶寬的要求，使能夠復合的組播組共享一棵組播分發(fā)樹。樹節(jié)點上保持的是這棵樹的狀態(tài)，而不是每一個組播組的狀態(tài)，這樣大大減少了組播轉發(fā)的狀態(tài)數(shù)，提高了網(wǎng)絡性能。聚合組播問題的關鍵在于如何找到數(shù)目最小的組播樹，使之覆蓋所有的組播組。它的數(shù)學本質(zhì)是最小集合覆蓋問題，是一個NP-C問題。傳統(tǒng)的解決聚合組播的方法是貪婪算法。貪婪算法有一定的局限性，它每一次都選擇當前情況下的最優(yōu)解，很容易陷入局部最優(yōu)解，所以得到全局最優(yōu)解的可能性很小，最

4、終的聚合效果并不理想。 針對于這個問題，本文提出了拉格朗日松弛算法、遺傳算法和免疫算法來選擇聚合組播樹。 拉格朗日松弛的基本思想是，把造成問題難的約束條件吸收到目標函數(shù)中，并使得目標函數(shù)仍保持線性，使得問題容易求解。在傳統(tǒng)的拉格朗日松弛算法的基礎上，算法能夠動態(tài)調(diào)整拉格朗日乘子，使找到的解盡量接近于全局最優(yōu)解。 遺傳算法是一類借鑒生物界“自然選擇、適者生存”機制的智能搜索算法。在生物進化過程中，適應性好的個體生存