滿足時延及時延差別約束的組播路由問題研究.pdf

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

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