聚合組優(yōu)化模型與算法研究.pdf

1、近年來Internet發(fā)展迅速，網(wǎng)絡(luò)上需要組通信支持的各種分布式應(yīng)用不斷增多。作為支持組通信的主要技術(shù)，傳統(tǒng)的IP(Internet protocol)組播技術(shù)要求網(wǎng)絡(luò)為每一個組播組(甚至組播組的每一個源)建立和維護(hù)一棵組播轉(zhuǎn)發(fā)樹，樹上的每臺路由器都需要保存這個組播組(源)的轉(zhuǎn)發(fā)狀態(tài)。當(dāng)網(wǎng)絡(luò)上并發(fā)的組播組不斷增加時，路由器上為這些組播組維護(hù)的組播轉(zhuǎn)發(fā)狀態(tài)也會不斷增加。不斷增長的組播轉(zhuǎn)發(fā)狀態(tài)一方面需要路由器更多的內(nèi)存來存儲，另一方面轉(zhuǎn)發(fā)組

2、播分組時查表的時間更長。同時，一個組播組的轉(zhuǎn)發(fā)狀態(tài)需要組播組的樹上路由器之間周期性的交換信息來建立和維護(hù)。當(dāng)并發(fā)的組播組增加時，用于建立和維護(hù)這些轉(zhuǎn)發(fā)狀態(tài)的控制信息也會不斷增加，這會消耗網(wǎng)絡(luò)更多的帶寬。轉(zhuǎn)發(fā)狀態(tài)和控制信息的增多會減慢網(wǎng)絡(luò)的轉(zhuǎn)發(fā)速度，導(dǎo)致整個網(wǎng)絡(luò)的性能不斷下降。當(dāng)網(wǎng)絡(luò)上組播組的數(shù)量增加到一定程度，整個網(wǎng)絡(luò)就會由于性能下降的厲害而變得不可用。這就是傳統(tǒng)IP組播技術(shù)面臨的組播狀態(tài)擴展性問題。尤其是，這個問題當(dāng)組播支持服務(wù)質(zhì)量(

3、Quality ofService，QoS)時變得更加嚴(yán)重，這時不僅需要額外的內(nèi)存來存儲各種服務(wù)質(zhì)量的參數(shù)，同時，由于組播組成員服務(wù)質(zhì)量的要求不同，可能一個組播組需要幾棵組播樹才能夠完成滿足不同服務(wù)質(zhì)量要求的數(shù)據(jù)的傳遞。所以，真正大規(guī)模部署IP組播時，面臨著組播狀態(tài)擴展性問題的挑戰(zhàn)，只有解決了這個問題，大規(guī)模的組播的部署才會變得可能。
　　 由于Internet網(wǎng)絡(luò)是一個層次網(wǎng)絡(luò)，多個用戶網(wǎng)絡(luò)連接到一個區(qū)域網(wǎng)絡(luò)，多個區(qū)域網(wǎng)絡(luò)連接

4、到一個骨干網(wǎng)絡(luò)。多個用戶網(wǎng)絡(luò)之間的數(shù)據(jù)傳輸都需要經(jīng)過共同的骨干網(wǎng)絡(luò)，傳統(tǒng)IP組播技術(shù)中骨干網(wǎng)絡(luò)需要為每個經(jīng)過它的組播組維護(hù)組播狀態(tài)，組播狀態(tài)擴展性問題在骨干網(wǎng)絡(luò)中尤為突出。所以，研究組播狀態(tài)擴展性問題，尤其是骨干網(wǎng)絡(luò)上的組播狀態(tài)擴展性問題，具有重要的理論和現(xiàn)實意義。
　　 聚合組播作為近年提出的一種非常有前途的解決骨干網(wǎng)絡(luò)中組播狀態(tài)擴展性問題的思想，使多個組播組共享一棵組播樹(聚合樹)。組播樹數(shù)量的減少，不但減少了整個網(wǎng)絡(luò)中組播

5、狀態(tài)，同時也減少了網(wǎng)絡(luò)建立和維護(hù)樹的控制開銷。共享的組播樹一定要能夠完全覆蓋其所服務(wù)的組播組才能夠完成數(shù)據(jù)的正確傳輸，由于共享組播樹的組播組不一定有共同的成員集合，通常情況下聚合樹的葉子節(jié)點要多于每個組播組的成員。這就會帶來額外的帶寬浪費。因此，聚合組播是組播樹數(shù)量減少和額外帶寬浪費的一種折中。這是一個多目標(biāo)優(yōu)化問題，對應(yīng)著兩個優(yōu)化方向：給定帶寬浪費率，最小化組播樹數(shù)量的聚合樹優(yōu)化問題(帶寬浪費率受限的聚合組播問題)；和給定聚合樹數(shù)量，

6、最小化帶寬浪費率的帶寬優(yōu)化問題(聚合樹數(shù)目受限的聚合組播問題)。
　　 能否有效的解決這兩個優(yōu)化問題，得到相應(yīng)優(yōu)化問題較好的解，關(guān)系到聚合組播在網(wǎng)絡(luò)中實際的部署效果。同時，這兩個問題又都是NPC問題。為這兩個問題設(shè)計有效的解決算法，提高算法的優(yōu)化能力，是本文研究的重點。
　　 首先，論文給出了聚合樹優(yōu)化問題(ATOP，Aggregated Tree OptimizationProblem)的最小分組描述和最小分組模型。最

7、小分組問題是一類問題的統(tǒng)稱，許多具體的問題，如裝箱問題、圖分色問題和最小團覆蓋問題等，都屬于最小分組問題。使用啟發(fā)式算法解決這些問題時，通常由于陷入局部最優(yōu)而不能得到滿足需求的比較優(yōu)化的解。為了得到更高質(zhì)量的解，近年來提出許多種類的元啟發(fā)式算法。由于蟻群優(yōu)化(Ant Colony Optimization，ACO)算法在解決許多最小分組問題的具體問題時能夠取得一流的或有競爭力的解，所以重點是設(shè)計高效的聚合樹優(yōu)化問題的蟻群優(yōu)化算法。在設(shè)計

8、具體的蟻群優(yōu)化算法時，使用了分層的設(shè)計思路：首先根據(jù)問題的最小分組特征，尤其是在一次迭代過程結(jié)束時，經(jīng)常有多個迭代最優(yōu)解的情況，為了有效的從這些解中得到有利于尋找最優(yōu)解的知識，提出了兩個組播組之間的適應(yīng)度函數(shù)的設(shè)計原則，并在此之上，設(shè)計了新的多級信息素的分配原則。同時，根據(jù)算法的隨機特性，提出了算法的新的終止條件。然后，在這些原則的基礎(chǔ)上，分別使用裝箱模型和最小團覆蓋模型來解析聚合樹優(yōu)化問題中的聚合條件，提出了基于裝箱模型和基于最小團覆

9、蓋模型的啟發(fā)式信息，以及具體的組播組之間的適應(yīng)度函數(shù)的定義和信息素的更新規(guī)則。這兩個模型分別從不同的角度刻畫和描述了聚合樹優(yōu)化問題，反應(yīng)了聚合樹優(yōu)化問題的不同的特征。仿真結(jié)果顯示，本文提出的組播組之間的適應(yīng)度函數(shù)定義原則和與之關(guān)聯(lián)的多級信息素分配原則能夠顯著的提高算法的尋優(yōu)能力。與已有算法比較，不再需要事先計算候選樹集合，更加適用于帶寬浪費率比較大或網(wǎng)絡(luò)規(guī)模比較大的場景。
　　 其次，論文使用分組模型定義了帶寬優(yōu)化問題，并提出了

10、基于組播樹的相似性的蟻群優(yōu)化算法。通過分析帶寬優(yōu)化問題的特征，將帶寬優(yōu)化問題分解為初始樹選擇和樹聚合兩個階段。定義了組播樹(組播組)的相似性，分析了相似性的不對稱特征，提出使用相似度和相似性排名的組合來確定初始樹選擇階段和樹聚合階段的啟發(fā)式信息。同時，在這兩個階段中，根據(jù)信息素的含義，在不同的階段使用信息素的兩種形式(信息素本身和它的反)和相似性的兩種形式。根據(jù)問題的特征設(shè)計了新的信息素的更新規(guī)則。仿真結(jié)果表明，本文提出的算法取得了比啟