李　萍

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

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

中圖分類號:TP3文獻(xiàn)標(biāo)識碼:A文章編號:1671-7597(2009)0920092-01

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

一、分布式中心點(diǎn)選擇研究

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

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

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

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

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

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

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

不同中心點(diǎn)選擇算法的性能。

三、仿真模型和仿真結(jié)果

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

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

四、結(jié)論

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

參考文獻(xiàn):

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

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