遺傳組播路由算法

　　引言

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

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

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

　　組播路由問題描述

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

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

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