時(shí)延受限組播路由算法的研究.pdf

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

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

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

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