遺傳組播路由算法

　　仿真實(shí)驗(yàn)

　　仿真網(wǎng)絡(luò)的生成采用了改進(jìn)的Waxman隨機(jī)網(wǎng)絡(luò)模型[6]，它保證了生成網(wǎng)絡(luò)的連通性，并保證每個節(jié)點(diǎn)的度數(shù)大于等于2。在該模型中，任意兩個節(jié)點(diǎn)u，v間存在鏈路的概率為

　　其中，d(u,v)為節(jié)點(diǎn)u到節(jié)點(diǎn)v的歐氏距離，L為任意節(jié)點(diǎn)間最大距離同，參數(shù)α和β控制產(chǎn)生網(wǎng)絡(luò)的特征，其值在(0,1)之間，參數(shù)α控制網(wǎng)絡(luò)中短邊與長邊之比，β用來調(diào)節(jié)網(wǎng)絡(luò)節(jié)點(diǎn)的平均度數(shù),采用的網(wǎng)絡(luò)的坐標(biāo)空間為4000×4000Rm2，α為0.26， β為0.4，節(jié)點(diǎn)的平均度數(shù)為4，時延上限Δ為100。

　　我們以最短路徑組播樹算法(STP)為比較基礎(chǔ)，采用如下的性能指標(biāo):

　　其中M表示實(shí)驗(yàn)次數(shù)，R值小于1表示遺傳算法(GA)的平均性能優(yōu)于STP，R值變大，則說明GA的平均性能變差。實(shí)驗(yàn)中，遺傳算法的參數(shù)設(shè)置如下:種群規(guī)模N=100, pm=0.2, pc=0.6，進(jìn)化代數(shù)為100。

　　算法隨網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)增長的性能比較

　　在本節(jié)實(shí)驗(yàn)中，我們將GA和STP的性能比較。固定目的節(jié)點(diǎn)占網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)比例記為r，分別為5%，10%，20%，考察算法在不同網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)下的性能比較。網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)從20到100,每隔10采樣，在每個采樣點(diǎn)上GA和STP各獨(dú)立運(yùn)行10次。圖1給出了GA和STP比較的結(jié)果。從實(shí)驗(yàn)來看，R小于1且比較穩(wěn)定，這充分表明GA較STP更優(yōu)的性能和良好的擴(kuò)展性。

　　GA的收斂性結(jié)果

　　利用Waxman網(wǎng)絡(luò)模型，生成一個具有100節(jié)點(diǎn)的隨機(jī)網(wǎng)絡(luò)，仿真目的節(jié)點(diǎn)占網(wǎng)絡(luò)總節(jié)點(diǎn)不同比例時GA的收斂情況，實(shí)驗(yàn)結(jié)果如圖2。

　　從圖2，可以明顯發(fā)現(xiàn)：與SPT相比，GA對組播樹費(fèi)用的改善比較明顯，收斂速度也比較快。

　　結(jié)論

　　針對傳統(tǒng)算法求解時延受限組播路由問題出現(xiàn)的搜索空間過小而無法獲得滿意解的缺點(diǎn)，本文探討了一種遺傳組播路由算法。該算法設(shè)計(jì)了交叉和變異算子以實(shí)現(xiàn)全局優(yōu)化的目的，并通過前K-shortest方法克服搜索空間過大的缺點(diǎn)。在實(shí)驗(yàn)中，給出了該算法與傳統(tǒng)最短路徑法(STP)隨目的節(jié)點(diǎn)和網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)增長的性能比較。結(jié)果表明，該算法比STP具有更強(qiáng)的搜索能力和更快的收斂速度，同時具有良好的擴(kuò)展性。