遺傳組播路由算法

　　仿真實驗

　　仿真網絡的生成采用了改進的Waxman隨機網絡模型[6]，它保證了生成網絡的連通性，并保證每個節點的度數大于等于2。在該模型中，任意兩個節點u，v間存在鏈路的概率為

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

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

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

　　算法隨網絡節點數增長的性能比較

　　在本節實驗中，我們將GA和STP的性能比較。固定目的節點占網絡節點數比例記為r，分別為5%，10%，20%，考察算法在不同網絡節點數下的性能比較。網絡節點數從20到100,每隔10采樣，在每個采樣點上GA和STP各獨立運行10次。圖1給出了GA和STP比較的結果。從實驗來看，R小于1且比較穩定，這充分表明GA較STP更優的性能和良好的擴展性。

　　GA的收斂性結果

　　利用Waxman網絡模型，生成一個具有100節點的隨機網絡，仿真目的節點占網絡總節點不同比例時GA的收斂情況，實驗結果如圖2。

　　從圖2，可以明顯發現：與SPT相比，GA對組播樹費用的改善比較明顯，收斂速度也比較快。

　　結論

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