基于最小時延差的多播路由中心點選擇算法

李　萍

[摘要]研究分析各種中心點選擇方案對中心樹的時延和時延差的影響。首先證明尋找時延和時延差受約束的中心樹問題是NP完全問題,然后提出一種可以使時延差較小的中心點選擇算法。

[關鍵詞]計算機網(wǎng)絡 多播路由 動態(tài)多播路由算法 多播路由協(xié)議 中心點選擇

中圖分類號:TP3文獻標識碼:A文章編號:1671-7597(2009)0920092-01

隨著網(wǎng)絡技術的發(fā)展,應用于多媒體會議、遠程教育、數(shù)據(jù)分發(fā)等實時業(yè)務的多播通信成為當前研究最多,和應用最廣泛的網(wǎng)絡連接方式。目前,單目標和多目標多播路由問題仍是路由問題研究的一個熱點。

一、分布式中心點選擇研究

在分布式網(wǎng)絡(例如互聯(lián)網(wǎng))中,網(wǎng)絡的拓撲結構也是由網(wǎng)絡中所有節(jié)點分布式掌握,因此沒有一個節(jié)點掌握全部拓撲結構。為此,一個理想的中心點選擇算法應該在每一個節(jié)點只需要一部分信息,并且與鄰節(jié)點的交互也應該盡量少。HILLCLIMB協(xié)議步驟如下:(l)初始時,多播組只有一個成員,因此它就成為中心點,然后周期性地運算以下步驟;(2)啟動計時器Tl,Tl計時到就開始搜索;(3)發(fā)起搜索的節(jié)點向鄰節(jié)點發(fā)送組成員和源節(jié)點列表,詢問它們的權值,重新啟動計時器TI,以便在以下步驟中有消息丟失時算法會重新從步驟(3)開始;(4)每個鄰節(jié)點根據(jù)選擇函數(shù)計算權值應答;(5)發(fā)起搜索的點根據(jù)最新消息更新n個最佳中心點;(6)若搜索點的權值小于鄰節(jié)點的最小權值,則轉移到步驟(11);(7)若所有最佳鄰節(jié)點已在路徑列表中,則轉移到(11);(8)搜索點將自己加到已訪問節(jié)點列表中;(9)搜索點從未訪問的最佳鄰節(jié)點中選取最佳的一個節(jié)點作為下一個發(fā)起搜索的節(jié)點;(10)上一個搜索節(jié)點將路徑列表、組成員和源節(jié)點列表發(fā)給新的搜索節(jié)點,然后轉到(3);(11)最后的搜索點向中心點發(fā)回一個消息報告它的權值,中心點是路徑列表中的第一個節(jié)點;(12)最后的中心點成為新的中心點,然后轉到(2)。

二、一種優(yōu)化時延差的方案設計

對于時延受約束的中心樹問題,最小最大直徑方案(MinMaxDiameter)

應該是最合適的,因為此時的目標是限制最大時延,使之小于約束值。而最小平均距離方案并不合適,因為我們并不關心平均時延,只要最大時延約束值小于約束值即可。分析最小最大直徑方案,可以發(fā)現(xiàn)可能會出現(xiàn)有些成員的時延較小,從而導致時延差比較大。最小平均化方案也不能解決這個問題。為此這里首先提出一種方案,該方案的基本思想如下:

步驟1:首先以任一節(jié)點為中心點,求多播樹最大時延,若最大時延小于約束值,則求出時延差,然后加入中心點集合;

步驟2:將中心點集合中時延差最小的節(jié)點作為中心點。方案稱為優(yōu)化時延差方案,將該方案稱為OVET(nelayvariation Based CenteredTree)。

通過該方案選擇的中心點成員以最短路徑連到中心點即可使時延差較小。當然優(yōu)化時延差方案并沒有使得時延差受到約束,這個問題可以使用以下方法解決,即欲加入的成員不是通過最佳路徑連到中心樹,而是求到中心樹各節(jié)點的最短路徑,選取一個最佳的作為中間連接節(jié)點,但這樣做會帶來一個問題,即失去了中心點選擇的意義。因此上述方案不是一個時延差約束問題DVBCT的解決方案,而是盡可能減少了時延差。以上方案基于網(wǎng)絡組成員節(jié)點來選擇中心點。本章主要關注中心點選擇,因此對路由選擇采用了固定的算法——最短路徑算法,從而來比較

不同中心點選擇算法的性能。

三、仿真模型和仿真結果

對一定大小的網(wǎng)絡規(guī)模產生200個網(wǎng)絡,在每個網(wǎng)絡上進行20次試驗,每次試驗隨機選擇m個成員多播組進行仿真,m為0.1n-0.6n之間變化,因此每一個仿真數(shù)據(jù)對應4000個實驗數(shù)據(jù)。仿真數(shù)據(jù)的置信度為95%,置信區(qū)間不超過5%。時延根據(jù)節(jié)點間的距離和信號在光纖中的傳播速度為2/3光速算得。這里仿真的網(wǎng)絡大小分別為n=20,50,網(wǎng)絡平均節(jié)點度數(shù)為4。這里將比較最小化時延差方案DVCT、最小最大直徑方案DCT和最大中心樹方案MCT的時延、平均跳數(shù)、時延差和計算時間。圖1～4是網(wǎng)絡節(jié)點數(shù)為20,平均節(jié)點度數(shù)為4時各算法的最大時延、平均跳數(shù)、時延差和計算時間的比較。圖5～6是網(wǎng)絡節(jié)點數(shù)為50,平均節(jié)點度數(shù)為4時各算法的最大時延、平均跳數(shù)、時延差和計算時間的比較。

由圖1～6可見,DCT的最大時延最小,DVCT的最大時延最大,MCT的最大時延略大于DCT的最大時延。這是因為在這里只考慮時延,DCT使最大直徑最小也就是使時延最小,MCT的最大距離也是與時延緊密相關,因此其時延較小,而DVCT由于只考慮使時延小于約束值,并沒有使之最小化,因此它的時延最大并不為奇。綜上所述,DVCT是時延約束的、時延差較小、且執(zhí)行時間與DCT、MCT算法相當?shù)乃惴?可適用于時延約束且時延差較小的場合。

四、結論

本文著重討論了中心樹和中心點的選擇。綜述了現(xiàn)在學術界對中心樹和中心點選擇的研究進展,然后分析了現(xiàn)有的中心點選擇方案,提出了尚未有研究的時延和時延差受約束的中心樹問題,并證明它是一個NP完全問題,最后針對這一問題,提出了一種優(yōu)化時延差的方案,即DVCT方案。對DvCT的仿真結果表明它是一種時延受到約束的、時延差較小、計算復雜度與MCT、DCT相當?shù)囊环N算法,可適用于對時延差有要求的場合。

參考文獻:

[1]曹佳、魯士文,應用層組播的最小延遲生成樹算法,軟件學報,2005,16(10):1766-1773.

[2]李幫義、姚恩瑜,最短路網(wǎng)絡及應用,系統(tǒng)工程理論與實踐,2000,6:104-107.