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

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

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

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

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

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

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

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

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

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

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