基于進(jìn)化算法的下一代網(wǎng)絡(luò)QoS組播路由算法

浩慶波，徐巖

（曲阜師范大學(xué)網(wǎng)絡(luò)信息中心，山東濟(jì)寧，273100）

1 網(wǎng)絡(luò)模型

組播路由是將發(fā)送者和多個(gè)接收者之間實(shí)現(xiàn)點(diǎn)對多點(diǎn)的信息傳輸技術(shù)。組播路由技術(shù)的使用，能夠降低網(wǎng)絡(luò)出現(xiàn)擁塞的可能性，從而提高數(shù)據(jù)在網(wǎng)絡(luò)中的傳輸效率。組播路由技術(shù)是以數(shù)據(jù)源節(jié)點(diǎn)為根節(jié)點(diǎn)，依據(jù)網(wǎng)絡(luò)結(jié)構(gòu)和數(shù)據(jù)傳輸約束在多個(gè)目的節(jié)點(diǎn)之間構(gòu)建組播路由樹，以完成組播數(shù)據(jù)的傳輸。通常我們借助于斯泰納(Steiner)問題對組播路由問題進(jìn)行研究。在Steiner問題中，求解其最小樹MST(Minimum Steiner Tree,MST)的過程即是求解最小的組播樹的過程。

為更為直觀的描述組播路由問題，我們使用有向賦權(quán)圖G = ( V,E) 描述計(jì)算機(jī)網(wǎng)絡(luò)，其中V表示網(wǎng)絡(luò)節(jié)點(diǎn)集，E表示通信鏈路集。在通信網(wǎng)絡(luò)中，我們對每一條通信鏈路 Vi都定義三個(gè)加權(quán)值進(jìn)行描述，其中均為正實(shí)數(shù)。Bij表示節(jié)點(diǎn)i與節(jié)點(diǎn) j之間鏈路的帶寬，Cij則表示節(jié)點(diǎn)i與節(jié)點(diǎn) j之間鏈路傳輸數(shù)據(jù)的代價(jià)，Cij值的大小也反映出該鏈路資源的使用情況；Dij表示節(jié)點(diǎn)i與節(jié)點(diǎn) j之間鏈路的傳輸延時(shí)。為簡化網(wǎng)絡(luò)模型，假設(shè)網(wǎng)絡(luò)中每兩個(gè)節(jié)點(diǎn)的雙向鏈路權(quán)值相等，即。且網(wǎng)絡(luò)中每兩個(gè)節(jié)點(diǎn)最多存在一條連通鏈路。

組播問題即為花費(fèi)最小代價(jià)將數(shù)據(jù)從源節(jié)點(diǎn)s∈V發(fā)送到一組多個(gè)目的節(jié)點(diǎn) D ?V-{s}。組播樹為,其中。可知組播路由樹滿足如下幾個(gè)條件：

從源節(jié)點(diǎn)s到所有目的節(jié)點(diǎn)d∈D的所有路徑中，最小帶寬為組播樹T的帶寬

從源節(jié)點(diǎn)s到目的節(jié)點(diǎn)d∈D的所有路徑中，最大延時(shí)為組播樹T的延時(shí)

帶寬和延時(shí)是網(wǎng)絡(luò)中最為主要的評價(jià)參數(shù)。……