基于最小時(shí)延差的多播路由中心點(diǎn)選擇算法

李　萍

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

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

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

隨著網(wǎng)絡(luò)技術(shù)的發(fā)展,應(yīng)用于多媒體會(huì)議、遠(yuǎn)程教育、數(shù)據(jù)分發(fā)等實(shí)時(shí)業(yè)務(wù)的多播通信成為當(dāng)前研究最多,和應(yīng)用最廣泛的網(wǎng)絡(luò)連接方式。目前,單目標(biāo)和多目標(biāo)多播路由問(wèn)題仍是路由問(wèn)題研究的一個(gè)熱點(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)分布式掌握,因此沒(méi)有一個(gè)節(jié)點(diǎn)掌握全部拓?fù)浣Y(jié)構(gòu)。為此,一個(gè)理想的中心點(diǎn)選擇算法應(yīng)該在每一個(gè)節(jié)點(diǎn)只需要一部分信息,并且與鄰節(jié)點(diǎn)的交互也應(yīng)該盡量少。HILLCLIMB協(xié)議步驟如下:(l)初始時(shí),多播組只有一個(gè)成員,因此它就成為中心點(diǎn),然后周期性地運(yùn)算以下步驟;(2)啟動(dòng)計(jì)時(shí)器Tl,Tl計(jì)時(shí)到就開(kāi)始搜索;(3)發(fā)起搜索的節(jié)點(diǎn)向鄰節(jié)點(diǎn)發(fā)送組成員和源節(jié)點(diǎn)列表,詢問(wèn)它們的權(quán)值,重新啟動(dòng)計(jì)時(shí)器TI,以便在以下步驟中有消息丟失時(shí)算法會(huì)重新從步驟(3)開(kāi)始;(4)每個(gè)鄰節(jié)點(diǎn)根據(jù)選擇函數(shù)計(jì)算權(quán)值應(yīng)答;(5)發(fā)起搜索的點(diǎn)根據(jù)最新消息更新n個(gè)最佳中心點(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)將自己加到已訪問(wèn)節(jié)點(diǎn)列表中;(9)搜索點(diǎn)從未訪問(wèn)的最佳鄰節(jié)點(diǎn)中選取最佳的一個(gè)節(jié)點(diǎn)作為下一個(gè)發(fā)起搜索的節(jié)點(diǎn);(10)上一個(gè)搜索節(jié)點(diǎn)將路徑列表、組成員和源節(jié)點(diǎn)列表發(fā)給新的搜索節(jié)點(diǎn),然后轉(zhuǎn)到(3);(11)最后的搜索點(diǎn)向中心點(diǎn)發(fā)回一個(gè)消息報(bào)告它的權(quán)值,中心點(diǎn)是路徑列表中的第一個(gè)節(jié)點(diǎn);(12)最后的中心點(diǎn)成為新的中心點(diǎn),然后轉(zhuǎn)到(2)。

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

對(duì)于時(shí)延受約束的中心樹(shù)問(wèn)題,最小最大直徑方案(MinMaxDiameter)

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

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

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

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

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

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

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

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

四、結(jié)論

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

參考文獻(xiàn):

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

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