一種有效的時(shí)延約束組播路由算法

《一種有效的時(shí)延約束組播路由算法》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、一種有效的時(shí)延約束組播路由算法黃勇(國(guó)防科大人文與管理學(xué)院，湖南長(zhǎng)沙410073)摘要:在多媒休通信網(wǎng)絡(luò)中，組播問(wèn)題提出了新的要求，除了最小化組播通信的代價(jià)，同時(shí)要求保證每一個(gè)目的的節(jié)點(diǎn)在固定的延時(shí)之內(nèi)接收信息。在這篇論文中，我們提出了一個(gè)鏈路選擇函數(shù)用于解決時(shí)延約束組播問(wèn)題。我們的實(shí)驗(yàn)結(jié)果揭示了該函數(shù)能提供滿足時(shí)延約束且代價(jià)較小的組播路由問(wèn)題近似解。關(guān)鍵詞:組播路由;時(shí)延約束;鏈路選擇函數(shù)Abstract:Inmultimediacommunicationnetworks，theproblemofmulticastingassumesanewdimension.Apartfrommin

2、imizingthecostofmulticastcommunication，itisalsonecessarytoensurethateachofthedestinationnodesreceivesthemessagewithinaboundeddelay.Inthispaper，wepresentanedgeselectionfunctionforsolvingthedelay一boundedmulticastproblem.Ourexperimentalresultsrevelalthatthealgorithmprovidesfastandsuperiorqualitysolu

3、tionstothedelay一boundedmulticastproblem.Keywords:MulticastRouting;Delay一bounded;edgeselectionfunctionQoS組播路由技術(shù)。0引言1網(wǎng)絡(luò)模型及問(wèn)題的描述隨著視頻會(huì)議/點(diǎn)播、多媒體播放以及遠(yuǎn)程教學(xué)等應(yīng)用的興起，對(duì)成員是的交互通信在多媒體實(shí)時(shí)業(yè)務(wù)的QoS傳輸中，基于提出了高的服務(wù)質(zhì)量QoS的要求。在網(wǎng)絡(luò)各時(shí)延約束的代價(jià)優(yōu)化路由模型可表示為無(wú)向中繼系統(tǒng)中實(shí)現(xiàn)對(duì)QoS需求的流進(jìn)行帶賦權(quán)圖G=(V,E)，其中V是網(wǎng)絡(luò)中所有交QoS需求約束的路由選擇機(jī)制，被稱為QoS換節(jié)點(diǎn)組成的集合，E是圖G中任意兩相

4、鄰路由選擇問(wèn)題(QoSrouting)，所用算法的路節(jié)點(diǎn)i,j的邊(i,j)的集合。對(duì)于G中的每一由計(jì)算約束條件包括各種QoS需求，如時(shí)條邊(G,j)EE，均對(duì)應(yīng)兩個(gè)正實(shí)數(shù)加權(quán)值延、時(shí)延抖動(dòng)、帶寬等約束。QoS路由實(shí)現(xiàn)的cost(i,j).delay(i,j)ecost(i,j)定義了邊(i,j)困難是路徑計(jì)算的復(fù)雜性，選擇有單一QoS的代價(jià)，其值與該邊的資源使用情況有關(guān)。約束的可行路徑可由任何最短路徑算法實(shí)delay(i,j)定義了邊(i,j)的信息傳送延時(shí)，該現(xiàn)，但是許多服務(wù)類別需要多個(gè)QoS約束，延時(shí)包括排隊(duì)延時(shí)、傳輸延時(shí)和交換延時(shí)等。這通常是一個(gè)NP完全問(wèn)題[l]。組播路由問(wèn)題可

5、描述為在圖G中尋找一棵本文將通過(guò)對(duì)這一課題的研究，提出一包含發(fā)送源及所有接收節(jié)點(diǎn)的樹T=(VT,種基于鏈路選擇函數(shù)的性能較優(yōu)的網(wǎng)絡(luò)ET)，(TgG)，收稿日期:2002一03一27;修改B期:2002一11一26作者簡(jiǎn)介:黃勇(1975-)，男，湖南長(zhǎng)沙人，碩士研究生，主要方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)，智能計(jì)算。·16。《電腦與信息技術(shù)》2002年第6期并滿足:min藝cost(i,j))(1)行其他的選擇，這大大豐富了f的行為，具體U.j)EE,的規(guī)律如下:當(dāng)k較小時(shí)，分母的比重較小，f約束條件:藝delay(i,j)<,A,U.j)任P"(x.v)更加偏重于代價(jià)的優(yōu)化，當(dāng)k較大時(shí)，分母的VVEM

6、(2)比重較大，f更加偏重于延遲的優(yōu)化，事實(shí)其中△為時(shí)延上限(或稱時(shí)延約束)，該上，當(dāng)k足夠大時(shí)(一般為20以上)，可以得參量定義了實(shí)時(shí)業(yè)務(wù)的傳送延時(shí)要求。PT(s,到與Dijkstra最短路徑算法同樣的延遲限，v)為樹T中從發(fā)送源s到接收點(diǎn)v的路徑，而且同時(shí)所得到的總代價(jià)一般較小。但當(dāng)kM為接收點(diǎn)的集合。比較大時(shí)，不但增加運(yùn)算的時(shí)間，同時(shí)也有可能會(huì)溢出，于是對(duì)鏈路函數(shù)f進(jìn)行了一些小2鏈路選擇函數(shù)的變化，使之成為:本文中的鏈路選擇函數(shù)是在需要滿足f(v,w)=logc(v,w)一k‘log(A一QoS請(qǐng)求的多播路由中，用于平衡代價(jià)與延P(v)一D(v,w))遲的一種路由選擇策略。當(dāng)前的鏈

7、路選擇函P(v)+D(v,w)<,6數(shù)多采用文獻(xiàn)[z7中提出的以下兩種:否則，f(v,w)二0f(v,w)=c(v,w)同時(shí)鏈路函數(shù)的搜索過(guò)程直接在網(wǎng)絡(luò)上P(v)+D(v,w)