（計算機(jī)應(yīng)用技術(shù)專業(yè)論文）遺傳算法在qos組播路由優(yōu)化中的應(yīng)用研究.pdf

遺傳算法在q o s 組播路由優(yōu)化中的應(yīng)用研究 摘要 隨著i n t e r n e t 的發(fā)展 多媒體通信和分布式環(huán)境下的協(xié)同工作等應(yīng)用促使了組播通 信的發(fā)展 組播問題的關(guān)鍵在于組播路由的確定 即尋找簡單 高效 健壯的組播路由 算法 組播路由算法主要是用來建立一棵性能良好的組播樹 并使它能夠滿足各種業(yè)務(wù) 的服務(wù)質(zhì)量 q u a l i t yo f s e r v i c e q o s 需求 由于q o s 組播路由帶有多個q o s 約柬參 數(shù) 而這種多約束條件f 的q o s 組播路由問題屬于n p 完全問題 這使得它與傳統(tǒng)的路 由過程不同 難以用經(jīng)典的最短路徑優(yōu)先算法 如b e l l m a n f o r d 和d i j k s t r a 算法 求解 對于o o s 組播路由問題的研究大多都集中在采用啟發(fā)式算法求解無約束組播路由問題 和時延受限組播路由優(yōu)化問題 然而由于這些算法都具有較高的時間復(fù)雜度而不能滿足 實際應(yīng)用的需要 本文利用遺傳算法作為求解q o s 組播路由優(yōu)化的算法 主要研究了四 類典型的q o s 組播路由問題 首先 根據(jù)組播路由問題的特點 建立了候選路由表 采用了等長節(jié)點序列串的編 碼方式 針對標(biāo)準(zhǔn)遺傳算法的缺點 引入模擬退火思想 該算法既提高了算法的全局收 斂能力也提高了收斂速度 其次 針對目前的單約束 或無約束 組播路由問題的局限 性 用遺傳算法實現(xiàn)了一種通用的多約束q o s 組播路由問題 采用基于路徑的樹結(jié)構(gòu)編 碼方式 遺傳算子操作過程簡單 算法體現(xiàn)了遺傳算法較強(qiáng)的搜索能力 再次 通過分 析遺傳算法和組播路由問題的特點 提出一種雙種群遺傳算法 通過嫁接種群來指導(dǎo)種 群的進(jìn)化方向 大大提高了算法的收斂速度 最后提出一種雙染色體遺傳算法來求解時 延 帶寬約束組播路由問題 同時在產(chǎn)生初始群體時 引入了求解組播路由問題的經(jīng) 典啟發(fā)式算法思想 設(shè)計遺傳算子時 采用了雙變異率算子 而交叉算子是在兩種染色 體之間進(jìn)行的 通過仿真結(jié)果驗證了該算法的有效性 關(guān)鍵詞 遺傳算法 組播路由 模擬退火算法 s t e i n e r 樹 d i j k s t r a 算法 中北大學(xué)學(xué)位淪文 s t u d yo nq o s m u l t i c a s t r o u t i n go p t i m i z a t i o n b a s e do n g e n e t i c a l g o r i t h m p o s t g r a d u a t e l im e i l i a n t u t o r p r o f e s s o r z e a gj i a o e h a o p r o f e s s o rc h e nl i e h a o a b s t r a c t w i t ht h ed e v e l o p m e n to f i n t e m e t t h er e c e n te m e r g e n c eo f m u l t i m e d i ac o m m u n i c a t i o n s a n dc o o p e r a t i v ew o r k si nd i s t r i b u t e de n v i r o n m e n t sp r o v i d e sa r ti n c e n t i v et os y s t e md e s i g n e r s t oi n c l u d em u l t i c a s tc o m m u n i c a t i o ns u p p o r tf o rt h e s ea p p l i c a t i o n s af u n d a m e n t a li s s u ei n m u l t i c a s tc o m m u n i c a t i o ni sh o wt od e t e r m i n ea ne f f i c i e n tm u l t i c a s tr o u t i n g n a m e l yi ns e a r c h o fs i m p l e e f f e c t i v ea n dr o b u s tm n l t i c a s tr o u t i n ga l g o r i t h m s m u l t i c a s tr o u t i n ga l g o r i t h m sa r e u s e dt oc o m p u t em u l t i c a s tt r e e st h a ts a t i s f yq u a l i t yo fs e r v i c er e q u i r e m e n t t h ep r o b l e mi n s e a r c ho fm u l t i c a s tr o u t i n gw i t hq o sc o n s t r a i n e di san p c o m p l e t ep r o b l e m s ot h ep r o b l e m c a nn o tb es o l v e du s i n gt h ec l a s s i c a ls h o r t e s tp a t hf i r s ta l g o r i t h m ss u c ha sb e l l m a n f o r da n d d o k s t r a t h u s m o s tp r e v i o u sr e s e a r c h e r sh a v ef o c u s e do nd e v e l o p i n gh e u r i s t i ca l g o r i t h m st o s o l v eu n c o n s t r a i n e da n d d e l a y c o n s t r a i n e d m u l t i c a s t m u t i n gp r o b l e m h o w e v e r t h e s e h e u r i s t i ca l g o r i t l u n sh a v eh i 曲c o m p u t a t i o nc o m p l e x i t ys ot h e ya r en o tf i ti np r a c t i c a l i t y 1 1 1 t h ep a p e r g e n e t i ca l g o r i t h mi su s e dt ot h eq o sm u l t i c a s tm u t i n gp r o b l e ma n df o u rt y p i c a l r e s p e c t so f r e s e a r c hh a v eb e e np u tf o r w a r d f i r s to fa l l c a n d i d a t er o u t i n gt a b l e sa r e d e s i g n e db a s e d o nt h ec h a r a c t e r i s t i co fm u l t i c a s t r o u t i n gp r o b l e ma n dt h ee n c o d i n gm e t h o do fn o d e ss t r i n gw i t he q u a ll e n g t hi su s e d d u et o t h ed i s a d v a n t a g eo fs t a n d a r dg e n e t i ca l g o r i t h m s i m u l a t e da n n e a l i n gi si n t r o d u c e dt og e n e t i c o p e r a t o r s t h ep r o p o s e da l g o r i t h m e n h a n c e sn o t o n l yg l o b a l s e a r c h a b i l i t y b u ta l s o c o n v e r g e n c es p e e d s e c o n d l n i n a l l u s i o nt ot h e t i m i t a t i o no f s i n g l e c o n s t r a i n to r u n c o n s t r n n e dm u l t i c a s tr o u t i n g p r o b l e m ac o m m o n m u l f i c o n s t r a i n e dm u l t i c a s tr o u t i n gb a s e d o ng e n e t i ca l g o r i t h mi sr e a l i z e d t h e r o u t i n ge n c o d i n gm e t h o di su s e d s ot h eg e n e t i c i i 中北火學(xué)學(xué)位論文 o p e r a t o r sc a nb eo p e r a t e dc o m p a r a t i v e l ye a s i l y t h ea l g o r i t h r n m a n i f e s t sb e t t e rs e a r c ha b i l i t y o f g e n e t i ca l g o r i t h m m o r e o v e r a n a l y z i n gt h ec h a r a c t e r i s t i co fm u l t i c a s tr o u t i n ga n dg e n e t i c a l g o r i t h m ad u a l p o p u l a t i o n sg e n e t i ca l g o r i t h mi sd e s i g n e d i nt h ep r o c e s so f e v o l u t i o n t h e g r a f t e dp o p u l a t i o ni n s t r u c t st h ee v o l u t i o nd i r e c t i o n o ft h ee v o l u t i v ep o p u l a t i o n t oag r e a t e x t e n t t h ec o n v e r g e n c es p e e do ft h ea l g o r i t h mi si m p r o v e df i n a l l y t h eg e n e t i ca l g o r i t h m b a s e do nt w oc h r o m o s o m e ss o l v e sb a n d w i d t h d e l a y c o n s t r a i n e dl e a s t c o s tm u l t i c a s tr o u t i n g p r o b l e m w h e n t h ei n i t i a l p o p u l a t i o n i s p r o d u c e d t h e t r a d i t i o n a lh e u r i s t i c a l g o r i t h m i s i n t r o d u c e dt ot h ei m p r o v e dg e n e t i ca l g o r i t h m d u a lm u t a t i o no p e r a t o ri su s e d a n dc r o s s o v e r o p e r a t o r i s o p e r a t e db e t w e e nt w oc h r o m o s o m e s s i m u l a t i o nr e s u l t s s h o wt h i s a l g o r i t h mi s e f f e c t i v e k e y w o r d s g e n e t i ca l g o r i t h m m u l t i c a s tr o u t i n g s i m u l a t e d a n n e a l i n g s t e i n e r t r e e d i j k s t r a i i i 中北大學(xué)學(xué)位論文 本人聲明 我聲明 本論文及其研究工作是由本人在導(dǎo)師指導(dǎo)下獨立完成的 在完 成論文時所利用的一切資料已在參考文獻(xiàn)中列出 作者 簽字 幸關(guān)龜 日期 中北大學(xué)學(xué)位論文 1 緒論 現(xiàn)代計算機(jī)網(wǎng)絡(luò)包括i n t e r n e t 都是分組交換網(wǎng) 在進(jìn)行分組交換阿設(shè)計時 網(wǎng)絡(luò)的 路由選擇是需要考慮的重要因素 一個好的路由選擇可以使網(wǎng)絡(luò)的平均時延較低 提高 網(wǎng)絡(luò)的吞吐量 同列 路由選擇是 個非常復(fù)雜的問題 這是因為 路由選擇是網(wǎng)絡(luò)中 的所有節(jié)點共同協(xié)調(diào)工作的結(jié)果 其次 路由選擇的環(huán)境往往是在變化的 而這種變化 有時無法事先知道 此外 當(dāng)網(wǎng)絡(luò)發(fā)生擁塞時 就特別需要有能緩解這種擁塞的路由選 擇策略 但恰好在這種條件下 很難從網(wǎng)絡(luò)中的各節(jié)點獲得所需的路由選擇信息 可見 路由選擇在當(dāng)前乃至于在可預(yù)見的未來 都是分組交換網(wǎng)的重要組成部分 其性能的好 壞將直接影響到網(wǎng)絡(luò)整體性能的好壞 近代科學(xué)技術(shù)發(fā)展的特點之 是生命科學(xué)與工程科學(xué)的相互交叉 相互滲透和相互 促進(jìn) 遺傳算法的發(fā)展正體現(xiàn)了科學(xué)發(fā)展的這一特征和趨勢 由于遺傳算法的整體搜索 策略和優(yōu)化計算是不依賴于梯度信息 所以它的應(yīng)用范圍非常廣泛 尤其適合于處理傳 統(tǒng)搜索方法難以解決的高度復(fù)雜的非線性問題 遺傳算法是2 l 世紀(jì)智能計算的關(guān)鍵技 術(shù)之一 j 路由選擇實際上是一個優(yōu)化問題 傳統(tǒng)的啟發(fā)式算法難以求解并且計算復(fù)雜 度高 特別適合使用遺傳算法來求解 近年來 隨著網(wǎng)絡(luò)通訊技術(shù)的快速發(fā)展以及i n t e r n e t 的普及 出現(xiàn)了許多新的網(wǎng) 絡(luò)應(yīng)用系統(tǒng) 如視頻點播 遠(yuǎn)程教學(xué) 遠(yuǎn)程醫(yī)療及網(wǎng)上拍賣等 而這些系統(tǒng)對網(wǎng)絡(luò)服務(wù) 質(zhì)量的要求較高 組播是從一個發(fā)送者同時向特定多個接收者傳送數(shù)據(jù)的通信過程 由 于組播通信是建立樹狀路由 數(shù)據(jù)只在樹的分枝處復(fù)制 能夠節(jié)約帶寬 降低服務(wù)器負(fù) 載 降低網(wǎng)絡(luò)負(fù)載和減少擁塞 在國外 組播得到了很廣泛的應(yīng)用 微軟公司每個月都 要用組播技術(shù)傳播多媒體數(shù)據(jù)流 c i s c o 公司已經(jīng)用i p 廠r v 來進(jìn)行實時視頻流組播 用 于公司內(nèi)部的會議和培訓(xùn) 美國田納西州的p r o m u s 飯店已經(jīng)使用s t a r b u r s t 通信公司 的軟件 通過衛(wèi)星鏈路向所屬分店分發(fā)軟件升級和數(shù)據(jù)更新信息 m c i 公司以及b b n p l a n e t 公司等一些i n t e m e t 服務(wù)提供商 h a t e m e ts e r v i c ep r o v i d e r i s p 正在有限的基礎(chǔ) 中北大學(xué)學(xué)位論文 上進(jìn)行組播試驗 包括u l 州e t t e c h n o l o g i e s 在內(nèi)的供應(yīng)商已經(jīng)開始向客戶提供組播服 務(wù) d i g i t a lx p r e s s 公百j 通過衛(wèi)旱經(jīng)銷組播眼務(wù) 2 1 組播是一項非常實用的技術(shù) 為了推動它的發(fā)展 由全球主要的網(wǎng)絡(luò)設(shè)備廠商 電 信運營公司和i s p s 成立了 個 滄壇型的組織 i p 組播倡議組織 i p m i 許多大公 司 包括a t t i b m a l c a t e l c i s c o m i c r o s o f t 和3c o r n 等都支持i p 組播技術(shù) 并且成為了i p m i 的成員 i p m i 的目的是與網(wǎng)絡(luò)工程部i e t f i n t e r n e t e n g i n e e r i n gt a s k f o r c e 中的組播工作組一起制定i p 組播標(biāo)準(zhǔn) 并加速這些標(biāo)準(zhǔn)的采用 隨著組播技術(shù) 的進(jìn) 步完善 以及更多高效 實用的組播應(yīng)用程序被開發(fā)出來 組播將獲得更加廣泛 的應(yīng)用 組播通信的關(guān)鍵是組播路由的選擇 也就是如何構(gòu)建一棵組播分布樹 用以在 轉(zhuǎn)發(fā)數(shù)據(jù)時能保證用戶服務(wù)質(zhì)量的需求 因此 找出既能滿足應(yīng)用服務(wù)質(zhì)量需求 又具 有最小代價的組播路由對保證組播應(yīng)用系統(tǒng)的正常高效運行具有很重要的意義 1 2 網(wǎng)絡(luò)路由選擇問題 1 2 1 路由技術(shù) 路由是在最宏觀的層次上對網(wǎng)絡(luò)資源進(jìn)行管理的手段 它是交換機(jī)或者路由器不可 缺少的基本配置之 路由技術(shù)也是因特網(wǎng)中最復(fù)雜和要求最嚴(yán)格的內(nèi)容之一 路由有 兩方面的基本內(nèi)容 收集網(wǎng)絡(luò)狀態(tài)信息并不斷更新信息 根據(jù)已有信息來為新的連接請 求選擇 條合適的路由 一個路由算法的好壞極大地取決于信息收集的好壞 比如信息 更新的頻度 最終信息的準(zhǔn)確度 這些問題和實際協(xié)議實現(xiàn)方法關(guān)聯(lián)程度更大 通信網(wǎng) 絡(luò)路由功能可以分為兩個方面 一是在連接建立階段為通信會話選擇一個路由 二是確 保該會話的分組沿指定的路由轉(zhuǎn)發(fā) 面向連接的通信進(jìn)程執(zhí)行完整的路由功能 而面向 無連接的通信進(jìn)程并不是這么嚴(yán)格地執(zhí)行路由功能 有時候是收到分組后再為它計算路 由 有時候是用軟狀態(tài)來設(shè)置路由通道 1 2 2 基本分類 根據(jù)應(yīng)用范圍 路由選擇問題一般可分為兩大類 單播路由選擇和組播路由選擇 具體定義如下 2 中北大學(xué)學(xué)位論文 可行路徑 可行樹 可行路徑 可行樹 是網(wǎng)絡(luò)中從源節(jié)點到 所有 目的節(jié)點 的一條路徑 組播杠j 并且該路徑 樹 具有足夠的尚未分配的資源 能夠滿足特定 的q o s 需求 單播路由選擇問題可定義如下 給定一源節(jié)點s 一目的節(jié)點t 組服務(wù)質(zhì)量約 束c 以及可能的最佳化目標(biāo) 尋找從s 到t 滿足c 的最可行路徑 組播路由選擇問題定義如下 給定一源節(jié)點s 一組目的節(jié)點集r 一組約束c 以 及可能的鼴佳化目標(biāo) 尋找從s 出發(fā)覆蓋r 中所有節(jié)點日標(biāo)滿足c 的最可行的樹 1 3q o s 組播路由選擇方法 1 3 1 組播通信概述 f 1 組播的 作原理 組播是一種從一個發(fā)送者同時向多個接收者或者多個發(fā)送者向多個接收者傳送數(shù) 據(jù)包的通信過程 組播源把數(shù)據(jù)包發(fā)送到特定組播組 而只有屬于該組播組的地址才能 接收到此數(shù)據(jù)包 組播以最佳的方式將數(shù)據(jù)傳輸給所有的主機(jī) 組的成員可以是動態(tài)的 即成員可阱在任何時間加入一個組或離開一個組 組的大小和位置沒有限制 一個主機(jī) 可以是多個組的成員 組播可以大大的節(jié)省網(wǎng)絡(luò)帶寬 提高數(shù)據(jù)傳送效率 減少主干網(wǎng) 出現(xiàn)擁塞的刈 能性 因為無論有多少個1 7 i 標(biāo)地址 在整個網(wǎng)絡(luò)的任何一條鏈路上只傳送 單一的數(shù)據(jù)包 組播組中的主機(jī)可以是在同一物理網(wǎng)絡(luò) 也可以來自不同的物理網(wǎng)絡(luò) 如 果有組播路由器的支持 為了滿足多媒體實時應(yīng)用等的需求 很有必要尋求網(wǎng)絡(luò)層對組播通信的支持 使組 播技術(shù)滿足此類應(yīng)用的要求 為此就有了實現(xiàn)組播的方式 也就是建立組播樹 m u l t i c a s t i n gt r e e 組播樹是覆蓋源節(jié)點和所有目的節(jié)點的一棵生成樹 建立組播樹有 以下優(yōu)點 信息可以沿著樹的分支并行的傳到各個目的節(jié)點 這可以降低信息傳遞的 時延 信息只在樹的分支處進(jìn)行復(fù)制 從而使復(fù)制的份數(shù)盡量少 這樣做可以節(jié)省大 量的帶寬資源 提高資源的利用率 并且能減少擁塞的發(fā)生 除了組播通信方式 計算機(jī)網(wǎng)絡(luò)中常用的通信方式還有單播通信方式和廣播通信方 式 從圖1 1 可以看出組播通信和單播通信的區(qū)別 3 中北大學(xué)學(xué)位論文 單播t u n i c a s t 傳輸 在發(fā)送者和每一接收者之間需要單獨的數(shù)據(jù)信道 如果一臺 主機(jī)同時給很少量的接收者傳輸數(shù)據(jù) 一般沒有什么問題 但如果有大量主機(jī)希望獲得 數(shù)據(jù)包的同一份拷貝時卻很難實現(xiàn) 因為這犒導(dǎo)致發(fā)送者負(fù)擔(dān)沉重 時延增加以及造成 網(wǎng)絡(luò)擁塞 而且為了保證一定的服務(wù)質(zhì)量還需要增加硬件和帶寬 廣播 b r o a d c a s t 傳輸 是指在整個i p 子網(wǎng)內(nèi)廣播數(shù)據(jù)包 所有在子網(wǎng)內(nèi)部的主 機(jī)都將收到這些數(shù)據(jù)包 廣播意味著網(wǎng)絡(luò)向子網(wǎng)主機(jī)都投遞一份數(shù)據(jù)包 不論這些主機(jī) 是否樂于接收該數(shù)據(jù)包 然而廣播的使用范圍非常小 只在本地子網(wǎng)內(nèi)有效 因為路由 器會封鎖 播通信 同時廣播傳輸增加非接收者的開銷 a 牲艟j 煎倍方式 接收釋3 廬耘蹴 弋尹嘎 滴鬈鷲 組播傳輸可在數(shù)據(jù)鏈路層 第二層 和網(wǎng)絡(luò)層 第三層 實現(xiàn) 支持的媒體類型包 括以太網(wǎng) f d d i 和a t m 大多數(shù)路由器提供商支持i p 組播 不支持i p 組播的網(wǎng)絡(luò)通 過組播隧道技術(shù)傳輸組播信息包 2 組播通信的實現(xiàn)方案 在單播模型中 數(shù)據(jù)包通過網(wǎng)絡(luò)沿著單一路徑從源主機(jī)向目標(biāo)主機(jī)傳遞 但在組播 4 中北大學(xué)學(xué)位論文 模型中 紺播源向某一組地址傳遞數(shù)據(jù)包 而這一地址卻代表一個主機(jī)組 為了向所有 接收者傳遞數(shù)據(jù) 一般采用組播分布樹描述i p 組播在網(wǎng)絡(luò)罩經(jīng)過的路徑 組播分布樹有三種基本類型 洪泛法 有源樹 共享樹 有核樹和s t e i n e r 樹 洪泛法 這是最簡單的向前傳送組播路由算法 并不構(gòu)造所謂的分布樹 其基本原理如下 當(dāng)組播路由器收到發(fā)往某個組播地址的數(shù)據(jù)包后 首先判斷是否是首次收到該數(shù)據(jù)包 如果是首次收到 那么將其轉(zhuǎn)發(fā)到所有接口上 以確保其最終能到達(dá)所有接收者 如果 不是首次收到 則拋棄該數(shù)據(jù)包 洪泛法的實現(xiàn)關(guān)鍵是 首次收到 的檢測 這需要維護(hù)一個最近通過的數(shù)據(jù)包列 表 但無需維護(hù)路由表 它適合于對組播需求比較高的場合 并且能做到即使傳輸出現(xiàn) 錯誤 只要還存在一條到接收者的鏈路 則所有接收者都能接收到組播數(shù)據(jù)包 然而 洪泛法不適合用于i n t e r n e t 因為它不考慮鏈路狀態(tài) 并產(chǎn)生大量的拷貝數(shù)據(jù)包 此外 對于高速網(wǎng)絡(luò)而言 首次收到 列表將會很長 占用相當(dāng)大的內(nèi)存 盡管它能保證不 對相同的數(shù)據(jù)包進(jìn)行二次轉(zhuǎn)發(fā) 但不能保證對相同數(shù)據(jù)包只接收一次 有源樹 有源樹也稱為基于信源的樹或最短路徑樹 s h o r t e s tp a t ht r e e s p t 它是以組播 源為根構(gòu)造的從根到所有接收者路徑部最短的分布樹 如果組中有多個組播源 則必須 為每個組播源構(gòu)造一棵組播樹 由于不同組播源發(fā)出的數(shù)據(jù)包被分散到各自分離的組播 樹上 因此采用s p t 有利于網(wǎng)絡(luò)中數(shù)據(jù)流量的均衡 同時 因為從組播源到每個接收者 的路徑最短 所以端到端 e n d t o e n d 的時延性能較好 有利于流量大 時延性能要 求較高的實時媒體應(yīng)用 s p t 的缺點是 要為每個組播源構(gòu)造各自的分布樹 當(dāng)數(shù)據(jù)流 4 孱 7 i i x j 構(gòu)造s p t 的開銷相對較大 共享樹 共享樹也稱r p 樹 r p t 是指為每個組播組選定一個共用根 匯合點r p 或核心 以r p 為根建立的組播樹 同一組播組的組播源將所要組播的數(shù)據(jù)單播到r i p 再由r p 向其它成員轉(zhuǎn)發(fā) 目前 討論最多同時也是最具代表性的兩種共享樹是s t e i n e r 樹和有 核樹 c b t s t e i n e r 樹是總代價最小的分布樹 它使連接特定圖 g r a p h 中的特定組成員所需 5 中北大學(xué)學(xué)位淪文 的鏈路數(shù)最少 若考慮資源總量被大量的組使用的情況 那么使用資源較少最終就會減 少產(chǎn)牛搠塞的風(fēng)臉 s t e j n e r 樹相當(dāng)不穩(wěn)定 樹的形狀隨組中成員關(guān)系的改變而改變 且 對大型網(wǎng)絡(luò)缺少通用的解決方案 所以s t e i n e r 樹只是一種理論模型 而非實用工具 目前 出現(xiàn)了許多s t e i n e r 樹的次優(yōu)啟發(fā)式生成算法 有核樹 c b t 是由根到所有組成員的最短路徑合并兩成的樹 c b t 以選定中心為 根 其他組成員按照最短路的原則與中心建立連接 構(gòu)造成為一棵由所有發(fā)送節(jié)點共享 的樹 a b a l l a r d i e 在1 9 9 7 年9 月的 基于核的組播路由體系結(jié)構(gòu) c o f eb a s e dt r e e s c b t m u l f i c a s t r o u t i n g a r c h i t e c t u r e 中介紹了有核樹 共享樹在路由器所需存儲的狀態(tài)信息的數(shù)量和路由樹的總代價兩個方面具有較好 的性能 當(dāng)組的規(guī)模較大 而每個成員的數(shù)據(jù)發(fā)送率較低時 使用共享樹比較適合 但 當(dāng)通信量大時 使用共享樹將導(dǎo)致流量集中及根 r p 附近的瓶頸 3 組播的應(yīng)用 自從1 9 9 2 年3 月第一次建立組播主干網(wǎng) m b o n e m u l t i c a s tb o n e 且i e t f i m e m e t e n g i n e e r i n gt a s kf o r c e i n t e m e t 工程任務(wù)組 利用它成功地舉行第一次網(wǎng)絡(luò)會議以來f 3 1 組播引起了更為廣泛的重視 并取得很大的發(fā)展 許多專家學(xué)者對其各個方面進(jìn)行了深 入的研究 4 6 組播應(yīng)用大致可以分為三類 點對多點應(yīng)用 多點對多點應(yīng)用和多點對 點應(yīng)用 點對多點的應(yīng)用 點對多點應(yīng)用是指一個發(fā)送者 多個接收者的應(yīng)用形式 這是最常見的組播應(yīng)用形 式 典型的應(yīng)用包括 媒體廣播 媒體推送 信息緩存 事件通知和狀態(tài)監(jiān)視等 多點對多點的應(yīng)用 多點對多點應(yīng)用是指多個發(fā)送者和多個接收者的應(yīng)用形式 通常 每個接收者可以 接收多個發(fā)送者發(fā)送的數(shù)據(jù) 同時 每個發(fā)送者可以把數(shù)據(jù)發(fā)送給多個接收者 典型應(yīng) 用包括 多點會議 資源同步 并行處理 協(xié)同處理 遠(yuǎn)程學(xué)習(xí)和討論組等 多點對點的應(yīng)用 多點對點應(yīng)用是指多個發(fā)送者 一個接收者的應(yīng)用形式 通常是雙向請求響應(yīng)應(yīng)用 任何 端 多點或點 都有可能發(fā)起請求 典型應(yīng)用包括 資源查找 數(shù)據(jù)收集 網(wǎng)絡(luò)競 拍 信息詢問和j u k e b o x 等 6 中北大學(xué)學(xué)位淪文 1 3 2 服務(wù)質(zhì)量要求 服務(wù)質(zhì)量 q u a l i t yo f s e r v i c e 簡稱q o s 指發(fā)送和接收信息的用戶之間以及用戶 與傳輸信息的服務(wù)網(wǎng)絡(luò)之間關(guān)于信息傳輸?shù)馁|(zhì)量約定 q o s 包括用戶要求和網(wǎng)絡(luò)服務(wù)提 供者的行為兩個方面 用戶要求指用戶在i r t t e r n e t 網(wǎng)絡(luò)上進(jìn)行多媒體通信時所要求的服 務(wù)類型以及相應(yīng)的傳輸性能和質(zhì)量 所以多媒體應(yīng)用對i p 網(wǎng)q o s 的要求同時體現(xiàn) 丟 包率 傳輸時延 時延抖動 網(wǎng)絡(luò)帶寬等參數(shù)描述的分組傳輸特性 網(wǎng)絡(luò)要滿足用戶的 質(zhì)量要求 就必須滿足用戶要求的q o s 參數(shù) 1 q o s 主要參數(shù) 帶寬 b a n d w i d t h 單位時問內(nèi)傳送的i p 包數(shù)量 多媒體業(yè)務(wù)的數(shù)據(jù)傳輸量往往較 大 因此需要網(wǎng)絡(luò)為其分配最小帶寬 延時 d e l a y 指i p 包從發(fā)送到接收之間的時間間隔 它包括終端設(shè)備的編碼 解 碼時間 i p 包在傳播介質(zhì)的傳播時間 i p 包在交換機(jī)或路由器中被處理的時間 以及 i p 包在交換機(jī)或路由器的等待隊列中的排隊時間 延時抖動 j i t t e r 即延時變j l p d e l a yv a r i a t i o n 當(dāng)i p 包到達(dá)交換設(shè)備時 如果等 待隊列中沒有別的i p 包 則它將以固定延時被轉(zhuǎn)發(fā)出去 但是 如果等待隊列中還有 別的包 則它可能就需要等待 這時i p 包被交換的延時就等于固定延時加上在隊列中 等待的時間 以上兩種情況下延時的變化程度就是延時抖動 包丟失率 p a c k e tl o s sr a t e 是指特定的時間段丟失的包占傳輸包的總數(shù)的比例 丟包主要是由于網(wǎng)絡(luò)擁塞引起的 2 q o s 度量 對于路徑p a b c f g 用d a b 表示對應(yīng)鏈路 a 山 的度量 則q o s 度量可以按性 質(zhì)分為以下三類 a 凸性q o s 度量 如果d a g m i n d a b d b c d g g 那么度量由傳輸通道中瓶頸決定 即此度量 僅與路徑上的某個瓶頸鏈路的q o s 度量有關(guān) 如剩余帶寬 剩余緩存空間 鏈路速度等 b 加性q o s 度量 如果d a g d a b d b e d c g 那么度量由傳輸通道中所有鏈路的特性共同決 7 中北大學(xué)學(xué)位論文 定 如時延 時延抖動 費用等 c 乘性q o s 度量 如果d a g 2 d a b d b e d f g 即度量為所有鏈路對應(yīng)度量的乘積 如可靠性等 如耿d a b l n d a b 則乘性度量就轉(zhuǎn)化為加性度量 因此 按度量的性質(zhì)q o s 路由可歸結(jié)為基本的兩大類 路徑優(yōu)化問題 對應(yīng)加性 q o s 度量 鏈路優(yōu)化問題 對應(yīng)凸性q o s 度量 1 3 3q o s 組播路由 因為目前廣泛發(fā)展的多媒體通信業(yè)務(wù)的需要 多媒體服務(wù)往往在采用組播的同時帶 有q o s 要求 越來越多的研究人員關(guān)注研究滿足多媒體通信的需求及其發(fā)展方向 其中 q o s 組播路由問題主要是研究在滿足服務(wù)質(zhì)量需求的情況下怎樣更好地實現(xiàn)組播功能 q o s 路由問題又稱為受限路由問題 其約束條件包含了兩個或兩個以上的加法型度量 如延遲 代價等 或者包含加法型度量和乘法型度量 如丟失率 的組合 是n p 完全 問題 1 組播路由問題的闡述 組播路由選擇問題定義如下 給定一源節(jié)點s 一組目的節(jié)點集r 一組約束c 以 及可能的最佳化目標(biāo) 尋找從s 出發(fā)覆蓋r 中所有節(jié)點目標(biāo)滿足c 的最可行的樹 為簡單起見 分析多點路由問題時 將網(wǎng)絡(luò)看成無向帶權(quán)連通圖g v e 其中v 是網(wǎng)絡(luò)中所有交換節(jié)點組成的集合 e 是圖g 中所有邊的集合 每一條邊表示兩節(jié)點間 的一條通信鏈路 源節(jié)點s 目的節(jié)點集d 每一條邊e e 的代價函數(shù)c e e r r o 其中財表示代價的值域范圍為包括0 在內(nèi)的正整數(shù) 典型的代價函數(shù)包括 鏈路上的延 遲 可用資源 帶寬和價格 圖1 2 為帶q o s 參數(shù)的網(wǎng)絡(luò)拓?fù)鋱D 在組播應(yīng)用中 給定頂點集合d v 尋找g 中一棵覆蓋d 的子樹t v t e t 信 息從源節(jié)點出發(fā) 經(jīng)組播樹t v t e t 到達(dá)各目的節(jié)點 其中v t c v e t c e 并使t 的代價最小 即使 e e t c e 最小 組播樹的費用是指樹中所有鏈路費用的總和 這里 鏈路的費用是一個廣義的費用 它可以指鏈路上的延遲 可用資源 帶寬和價格等 在 實際應(yīng)用中 一般要求確定的路由要有效利用網(wǎng)絡(luò)資源 為此要求組播樹的費用最小 8 中北大學(xué)學(xué)位論文 圖1 2 帶q o s 參數(shù)的網(wǎng)絡(luò)拓?fù)鋱D 2 q o s 組播路由算法的研究現(xiàn)狀及發(fā)展趨勢 f 1 研究現(xiàn)狀 求解帶q o s 約束的組播生成樹問題稱為帶約束的s t e i n e r 樹問題 該問題同樣是一 個n p 完全問題 迄今為止 樹建立實際上還使用一些基本的啟發(fā)式算法 其中針對最 短路徑問題提出d i j k s t r a 算法 b e l l m a n f o r d 算法 f l o y d 算法 動態(tài)規(guī)劃方法 它們 是尋找節(jié)點陽j 最短路徑的基本算法 貪心算法 p r i m 算法 破圈法 k r u s k a l 算法是基 本的最小生成樹算法 p m s t 算法 k m b 算法是基于最小生成樹算法 經(jīng)剪枝生成 s t e i n e r 樹的啟發(fā)式算法 n a i v e 算法 s p h 算法 s p h z 算法 k s p h 算法 a d h 算 法 7 1 是利用最短路徑算法生成s t e i n e r 樹的啟發(fā)式算法 然而采用啟發(fā)式算法 隨著網(wǎng) 絡(luò)節(jié)點和鏈路數(shù)量的增加 其計算時間代價會急劇的增加 目前q o s 組播路由問題中研 究最多的就是延時受限組播樹 即只包含1 個約束條件 對于多個約束條件的情況 國 內(nèi)外現(xiàn)在主要用的方法有遺傳算法 8 1 1 1 螞蟻算法 模擬退火算法 t a b u 算法等 分別 提出了基于這些智能算法的組播路由算法 另外還提出人工神經(jīng)網(wǎng)絡(luò)技術(shù) 幢 1 3 群集智 能技術(shù) 免疫算法等智能算法來解決該問題 目前q o s 組播路由問題是國內(nèi)外研究 的熱點 近年來 隨著對遺傳算法的研究不斷深入 發(fā)現(xiàn)采用該算法來求解n p 難問題能取 9 中北大學(xué)學(xué)位論文 得較好的效果 i 復(fù)方式同樣適合于求解q o s 組播路由問題 因此人們的注意力越來越集 中在基于g a 的q o s 組播路由算法的研究上 2 組播路由選擇算法正在向以下趨勢發(fā)展 通用性 多媒體應(yīng)用具有各種q o s 需求 如帶寬 時延 時延抖動 代價等 從 組播路由發(fā)展來看 應(yīng)該開發(fā) 種通用的路由算法 來取代對不同類型的q o s 需求開 發(fā)的不同路由算法 因此 應(yīng)對多種q o s 參數(shù)需求下的組播路由問題進(jìn)行研究 簡單性 在邏輯上簡單的組播路由算法 有助于提高運行效率 減少調(diào)試和改進(jìn) 的時間 也將使得算法易于理解 實現(xiàn) 維護(hù)和升級 開發(fā)簡單而有效的組播路由算法 具有重要的現(xiàn)實意義 外延性 隨著網(wǎng)絡(luò)體系結(jié)構(gòu)的改變以及容量的增加 將會出現(xiàn)各種各樣新的組播 應(yīng)用 因此需要路由算法具有自適應(yīng)性 柬滿足各種新出現(xiàn)的服務(wù)類型 層次型路由 隨著網(wǎng)絡(luò)和組播組的增大 就會帶來可擴(kuò)展性問題 解決可擴(kuò)展性 問題的方式就是采用層次型路由 層次型路由較難用于q o s 路由 a 狀態(tài)信息不精確 b 對于一個節(jié)點而言 其網(wǎng)絡(luò)拓?fù)湫畔⒑玩溌窢顟B(tài)信息都是局部的 因此很難確定q o s 路由 還有待于進(jìn)一步進(jìn)行層次型路由的理論研究 不精確狀態(tài)信息下的路由 大多數(shù)現(xiàn)存組播路由算法都假定能得到精確的網(wǎng)絡(luò)狀 態(tài)信息 然而在層次型路由環(huán)境中 精確的狀態(tài)信息通常難以得到 因此 在大型網(wǎng)絡(luò) 中應(yīng)設(shè)計狀態(tài)信息不精確時的路由算法 目前該問題尚處在理論研究階段 1 4 組播路由選擇算法 q o s 組播路由的q o s 約束包括帶寬 或者成本 跳數(shù) 吞吐量 延遲 抖動和丟 失率等等 組播路由算法即是選擇優(yōu)化一個或多個q o s 約束的組播路由 1 4 1 組播路由算法分類 從不同的角度 組播路由算法可以有多種分類的方法 i 集中式與分布式 集中式算法要求計算節(jié)點知道所有的網(wǎng)絡(luò)狀態(tài)信息 而分布 式算法則只要求計算節(jié)點知道部分信息 可以看出 在廣域網(wǎng)上布署一個集中式算法是 1 0 中北大學(xué)學(xué)位論文 有困難的 因此 尋求分布式的求解算法是非常重要的 2 靜態(tài)型與動態(tài)型 所謂的靜忿型是指在組插樹生成以后就不再發(fā)生變化了 顯 然這對于大部分應(yīng)用來說是不適合的 而動態(tài)型則與此相反 在會話階段 它允許節(jié)點 動態(tài)地加入或者離開 這符合實際的需求 但同時也給算法帶來了新的問題 3 源基樹與共享樹型 解決組撩路由問題的算法大致可分兩類 類算法稱為源 基樹算法 該算法為組中每一個發(fā)送者建立一棵以發(fā)送者所在子網(wǎng)為根的組播樹 源基 樹算法只適用于廣播業(yè)務(wù) 另一類算法則為組內(nèi)所有發(fā)送者與接收者建立一棵共享樹 這類算法適用于會議型業(yè)務(wù) 如計算機(jī)會議 會議型業(yè)務(wù)具有以下特征 既有1 一t o n 型傳輸 也有m t o n 型傳輸 對信息傳送的時延有嚴(yán)格要求 數(shù)據(jù)量大 且媒體 多樣要求不同的處理 在改變發(fā)言者時要求進(jìn)行快速的路由切換 1 4 2 組播路由算法 1 基f 最短路徑樹的算法 最短路徑樹算法求解從組播源點到組播終點各成員的路徑并使路徑總權(quán)值之和最 小 如果使用單位樅值 則得到的組播樹就是最小跳 h o p 樹 即從源點到終點所經(jīng) 過的節(jié)點最少的組播樹 如果權(quán)值表示鏈路時延 則所得到的組播樹就是最小時延樹 b e l l m a n f o r d 算法 和d i j k s t r a 算法 1 6 1 是最有名的兩個最短路徑算法 兩個算法都是多 項式時間復(fù)雜度 最短路徑算法可以用來解決時延受限問題 2 基于最小生成樹的算法 一棵最小生成樹是包含了組播源點和所有組播終點且權(quán)值最小的一棵樹 最有名的 集中式最小生成樹算法是普里姆 p r i m 算法 g a l l a g e r 等提出了一種分布式算法 1 7 普里姆算法的基本思想是 在網(wǎng)絡(luò)中任選一個節(jié)點v o 作為樹根 從v o 開始 連接與v o 相連的 邊權(quán)值最小的節(jié)點v l 得到子樹t l 再以上述規(guī)則連接t 1 與網(wǎng)絡(luò)中不在t l 中的節(jié)點 如此繼續(xù)下去 直到所有節(jié)點都用到為止 最小生成樹算法可以用來解決樹 優(yōu)化問題 3 基于最大帶寬樹的算法 s h a c h a m 墉1 提出了一個用于處理分布式層次型編碼數(shù)據(jù)的最大帶寬樹 首先使用迪 杰斯特拉算法得到從組播源點到每個組播終點的最大帶寬路徑 然后將這些最短路徑進(jìn) 中北大學(xué)學(xué)位論文 行合并 消除環(huán)路等處理 最終得到最大帶寬樹 最大帶寬樹可以解決鏈路優(yōu)化問題 4 基于斯坦利樹的算法 所謂s t e i n e r 樹 是指給定某個度量空閫中的一個點集 求解將這些點互聯(lián)的最短 網(wǎng)絡(luò) 斯坦利 s t e i n e r 樹問題以最小化組播樹的總代價為目標(biāo) 是n p 完全問題 1 9 2 0 l 如果組播組包含了網(wǎng)絡(luò)中的所有節(jié)點 則斯坦利樹問題就簡化為最小生成樹問題 不受 限斯坦利樹算法可以用來解決樹優(yōu)化問題 但不能用來解決有q o s 約束的樹受限問題 w i n t e r 1 9 和h w a n g 2 0 對啟發(fā)式斯坦利樹算法進(jìn)行了總結(jié) k o u m a r k o w s k i 和b e r m a n 提出了一種求解斯坦利樹的啟發(fā)式算法1 2 i k m b 算 法先定義個距離完全圖 所謂距離完全圖是包含了網(wǎng)絡(luò)中所有節(jié)點的完全圖 且用每 對節(jié)點之間的邊表示它們之間的最短路徑 設(shè)從最初的網(wǎng)絡(luò)拓?fù)鋱Dg 創(chuàng)建出的距離完 全圖為h 首先用普里姆最小生成樹算法得到h 圖的最小生成樹u 再把u 中的每條 邊用相應(yīng)的最短路徑替換 從而得到連通子圖v 然后對v 運用最小生成樹算法得到 一個生成樹t 最后 反復(fù)修剪t 中的非組播葉子節(jié)點 從而得到一棵組播樹 此外 t a k a h a s h i 提出了 種啟發(fā)式算法f 2 2 1 b a u e r 和v e r m a 2 剮提出了一種分布式 算法來求解斯坦利樹問題 f 5 1 基于受限斯坦利樹的算法 對斯坦利樹問題加上其它附加條件 如時延 時延抖動等 就成為受限斯坦利樹問 題 該類問題也是n p 完全的 目前已有一些啟發(fā)式算法被提出 z h u p a r s a 和g a r c i a l u n a a c e v e s 提出了一種稱為有界最短組播算法 b o u n d e d s h o r t e s tm u l t i c a s ta l g o r i t h m b s m a 用來解決時延受限樹優(yōu)化問題 該算法定義鏈路 代價作為鏈路使用函數(shù) 同時定義樹的超邊 s u p e r e d g e 所謂超邊就是一個最長簡單 路徑 它的節(jié)點 包括端點 都是非組播點 稱為中繼點 r e l a yn o d e 算法先以組播 終點集為葉子節(jié)點 以時延為權(quán)值生成一棵最小生成樹 然后在不違反時延約束時 以 時延更小的超邊來取代最小時延樹中的超邊 直到樹的代價不能更低 超邊由第k 最 短路徑算法生成 由于b s m a 算法以最小時延生成樹開始 因此 只要時延受限組播 樹存在 就一定能夠找到它 k o m p e l l a p a s q u a l e 和p o l y z o p 9 1 提出了一個稱為k p p 的啟發(fā)式算法 他們假定鏈 路 u v 的時延為d u v 時延約束d 是一個整數(shù) 而代價c u v 是任一正實數(shù) 定義 1 2 l j 北大學(xué)學(xué)位論文 了受限最小代價路徑和節(jié)點集n 的封閉圖g 受限最小代價路徑為u 和v 之間的最小 代價路徑 從u 到v 的時延小于d 而節(jié)點集n 的封閉圖g 為節(jié)點集n 的完全 圖 且節(jié)點v 到w 的邊的權(quán)值與從v 到w 的受限最小代價路徑的權(quán)值相同 同時還給 出了兩個選擇函數(shù) 一個是鏈路代價函數(shù) 另一個是平衡代價和時延的函數(shù) 首先構(gòu)建 一個基于組播源點和組播終點集的封閉圖g 然后從組播源點s 開始 用普早姆算法 構(gòu)造一個最小生成樹 構(gòu)造最小生成樹時每條邊按以下規(guī)則選取 連接樹節(jié)點與非樹 節(jié)點 不違反時延約束條件 使選擇函數(shù)的值最小 最后用受限最小代價路徑代替 最小生成樹中的相應(yīng)邊 同時消除可能存在的環(huán)路 從而得到一棵組播榭 浚算法存在 時間復(fù)雜度大 準(zhǔn)確度低等問題 h a b e r m a n 等 25 提出了 種求解時延和時延抖動約束的斯坦利樹問題的算法 首先 構(gòu)造 棵參考樹t r 它的路徑是從組播源點s 到所有終點的最小代價路徑 對每一個組 播終點d 都構(gòu)造一棵樹t i 這棵樹初始化為t r 中從s 到d i 的路徑 通過添加樹中 節(jié)點到非樹組播終點的滿足時延和時延抖動約束的路徑來擴(kuò)展樹t 直到所有組播終點 都被包括進(jìn)去 如果最后得到的樹不止一棵 剛選取代價最小的那棵作為最終的組播樹 k o m p e l l a 2 6 提出了一個構(gòu)建時延約束斯坦利樹的分布式算法 該算法要求每個節(jié)點 維持 個到網(wǎng)絡(luò)中其它節(jié)點的最小時延距離向量 首先初始化為包含組播源點的一棵 樹 然后每次向樹中添加一個組播終點 直到所有的組播終點都添加完為止 所要添加 的組播終點按如下方法選擇 組播源點發(fā)出一個f i n d 報文 當(dāng)某點收到此報史后 就確定一個連接非樹組播終點的路徑 該路徑滿足時延約束 并且代價函數(shù)最小 該 點發(fā)送一個包含候選路徑標(biāo)識的r e s p o n s e 報文給組播源點 當(dāng)組播源點收到所有的 響應(yīng)報文后 就從候選路徑中選取一條最佳路徑 添加到樹中 多次重復(fù)上述過程直 至建立起一棵組播樹 w i d y o n o 2 7 1 采用受限b e l l m a n f o r d c b f 算法求解受限斯坦利樹 性能較優(yōu) 但計 算時間隨著網(wǎng)絡(luò)規(guī)模的增大而里指數(shù)增長 般用作評價解決同類問題的參考模型 f 6 智能化算法 隨著近年來遺傳算法 人工神經(jīng)網(wǎng)絡(luò)算法等的興起 科學(xué)工作者對這些算法的模型 理論和應(yīng)用技術(shù)等一系列問題進(jìn)行了深入的研究 這些算法被稱為現(xiàn)代優(yōu)化算法 其主 要應(yīng)用對象是優(yōu)化問題中的n p 問題 由于s t e i n e r 樹問題是n p 完全問題 為此近年 1 3 巾北大學(xué)學(xué)位論文 來許多學(xué)者崩這些算法來解決這個問題 文獻(xiàn) 2 8 和 2 9 提出了基于神經(jīng)網(wǎng)絡(luò)的路由選 擇方案 研究了基于s t e i n c r 樹或受限于部分q o s 參數(shù)的s t c i n e r 樹的路由選擇問題 但未考慮受限于多個q o s 參數(shù)的路由選擇問題 而在基于遺傳算法的組播路由算法中 目盼采用標(biāo)準(zhǔn)遺傳算法 而標(biāo)準(zhǔn)遺傳算法存在過早收斂和進(jìn)化后期搜索效率低的不足 1 5 本文的主要研究內(nèi)容 本文根據(jù)q o s 組播路由選擇問題的特點 結(jié)合遺傳算法的尋優(yōu)特征 從不同角度對 遺傳算法進(jìn)行改進(jìn) 旨