滿足時(shí)延及時(shí)延差別約束的組播路由問(wèn)題研究.pdf

1、組播是一種點(diǎn)到多點(diǎn)的網(wǎng)絡(luò)數(shù)據(jù)傳播技術(shù)，在視頻點(diǎn)播、電視會(huì)議、網(wǎng)絡(luò)游戲等方面具有很好的應(yīng)用價(jià)值。組播路由算法的目標(biāo)是尋找一棵連接源節(jié)點(diǎn)和多個(gè)目的節(jié)點(diǎn)的組播樹(shù)，同時(shí)滿足各種服務(wù)質(zhì)量需求。在實(shí)時(shí)交互性組播應(yīng)用中，時(shí)延和時(shí)延差別等服務(wù)質(zhì)量因素顯得尤為重要。為此，本文研究受時(shí)延和時(shí)延差別約束的組播路由問(wèn)題。 本文首先研究時(shí)延約束下的組播路由問(wèn)題。該問(wèn)題的目標(biāo)是創(chuàng)建一棵覆蓋源節(jié)點(diǎn)和目的節(jié)點(diǎn)的代價(jià)最小樹(shù)，且滿足端到端時(shí)延要求。這個(gè)問(wèn)題被證明是

2、NP完全問(wèn)題。我們?cè)谘芯恳延兴惴ǖ幕A(chǔ)上，提出一個(gè)新的啟發(fā)式算法，稱為STBMR算法。該算法在構(gòu)造滿足時(shí)延約束的組播樹(shù)過(guò)程中，先構(gòu)造最小生成樹(shù)作為初始樹(shù)，然后以時(shí)延最小路徑代替樹(shù)中的時(shí)延越界路徑，直至樹(shù)的根節(jié)點(diǎn)到所有目的節(jié)點(diǎn)的路徑滿足時(shí)延要求。該算法簡(jiǎn)單、易實(shí)現(xiàn)，與經(jīng)典的KPP算法相比，有較小的算法復(fù)雜性，但性能稍差。實(shí)驗(yàn)表明，STBMR算法構(gòu)造的組播樹(shù)費(fèi)用比KPP算法構(gòu)造的約大4％，算法執(zhí)行時(shí)間比KPP算法約少54％。 然后，