時延受限組播路由算法的研究.pdf

1、隨著互聯(lián)網(wǎng)技術(shù)的迅速發(fā)展,視頻點播、遠(yuǎn)程會議、在線教育和網(wǎng)絡(luò)游戲等實時多媒體服務(wù)運用的越來越廣泛,人們對網(wǎng)絡(luò)應(yīng)用的服務(wù)質(zhì)量(Quality of Services,QoS)要求也隨之增高。為了滿足實時多媒體服務(wù)的需要,組播技術(shù)得到廣泛應(yīng)用。組播技術(shù)將數(shù)據(jù)從一個或多個節(jié)點同時向多個目的節(jié)點發(fā)送,該技術(shù)在一定程度上解決了實時多媒體業(yè)務(wù)對網(wǎng)絡(luò)通信中時延、代價、帶寬等QoS服務(wù)質(zhì)量要求造成的瓶頸問題。
　　受限的組播路由問題是組播路由中一

2、個關(guān)鍵問題,而時延受限組播路由問題又是受限組播路由問題中一個重要課題,時延受限組播路由問題就是在時延限制的前提下找到一個總代價最小的組播路由,該問題是NP-Complete問題,一般用啟發(fā)式算法解決。針對單源的時延受限組播路由問題,提出了一種動態(tài)時延受限組播路由啟發(fā)式算法。該算法分為靜態(tài)和動態(tài)兩部分,將時延受限組播路由算法中初始狀態(tài)組播樹的構(gòu)建和節(jié)點動態(tài)變化后組播樹更新兩階段綜合考慮,減少了構(gòu)建組播樹的總時間。該算法不僅能解決靜態(tài)時延受

3、限組播路由問題,還能解決動態(tài)的時延受限組播路由問題。
　　本文的主要工作包括:
　?、俳M播的研究背景、國內(nèi)外現(xiàn)狀、原理、相關(guān)協(xié)議和算法分類的介紹;
　?、诮榻B無約束組播路由問題中重要解決方法之一的Steiner樹問題和對幾種典型啟發(fā)式算法分析比較;
　?、劢榻B時延受限組播路由問題數(shù)學(xué)模型、常見定義,對常見靜態(tài)時延受限組播路由算法和動態(tài)時延受限組播路由算法進(jìn)行分析比較,闡述兩類算法之間關(guān)系;
　　④由靜態(tài)時延

4、受限組播路由算法和動態(tài)時延受限組播路由算法的關(guān)系,提出一種時延受限組播路由啟發(fā)式算法 KNDMR。該算法包括靜態(tài)和動態(tài)兩部分,靜態(tài)部分實質(zhì)上是一種新的靜態(tài)時延受限組播路由算法,用于在初始階段構(gòu)建符合時延限制的組播樹,該部分改進(jìn)已有鏈路選擇優(yōu)化函數(shù),并首次提出關(guān)鍵次數(shù)概念;動態(tài)部分在靜態(tài)部分組播樹基礎(chǔ)上,處理組播成員動態(tài)變化時組播樹更新問題,動態(tài)部分重點提出對組播樹轉(zhuǎn)發(fā)節(jié)點退出情況的處理,通過共用關(guān)鍵節(jié)點的關(guān)鍵次數(shù)減少構(gòu)建組播樹的時間。仿