遺傳組播路由算法

　　引言

　　隨著多媒體技術的高速發(fā)展導致大量多媒體業(yè)務出現(xiàn)，如視頻點播、視頻/音頻會議、遠程教學、多人游戲等，這些都要求網(wǎng)絡必需具備點到多點(組播)通信的能力。原來的點對點通信就難以適應以視聽多媒體業(yè)務為核心的業(yè)務發(fā)展。因此組播路由問題成為網(wǎng)絡資源優(yōu)化問題研究的熱點之一。

　　所謂組播，指的是一個源節(jié)點向多個目的節(jié)點發(fā)送信息的通信方式，參與組播的多個目的端點組成了一個組播組，每個端節(jié)點稱為組播組成員。算法要尋找連接源節(jié)點和一組目的節(jié)點的一棵樹，不僅要使網(wǎng)絡進行通信的費用最小，還要求源節(jié)點與各目的節(jié)點間的通信時延滿足約束條件，它是網(wǎng)絡中的一個NP完全問題[1]，這類問題不能求出其最優(yōu)解，只能求出其近似最優(yōu)解或滿意解[2~3]。

　　為此，本文探討了遺傳組播路由算法，該算法有效地克服了早熟現(xiàn)象;而且通過引入交叉和變異算子，加快了收斂速度。仿真表明，該算法是有效可行的。

　　組播路由問題描述

　　通常，通信網(wǎng)絡可以被表示為一個連通圖),(EVG，V表示節(jié)點(路由器)的集合，E為任意兩相鄰節(jié)點x和y間通信鏈路(x,y)的集合。對于Eyx∈∀),(，均有兩個正實數(shù) ，分別表示鏈路(x,y)的時延和費用。對于Vba∈∀,，則a和b間路徑P(a,b)的時延函數(shù)和費用函數(shù)為:

　　在多媒體實時業(yè)務的QoS傳輸中，基于時延受限的組播路由優(yōu)化問題可表述為：給定源節(jié)點s和目的節(jié)點集合D∈V-{s}，以及尋找從源節(jié)點s到所有目的節(jié)點v(D∈v)的組播樹并且滿足條件：

　　其中Δ為實時業(yè)務允許時延的上限值，),(vsPT為GA中從源節(jié)點s經組播樹到目的節(jié)點v的路徑。