ＤＶＢＭＴ問題的一種改進(jìn)算法

（重慶郵電大學(xué) a.數(shù)理學(xué)院； b.計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院， 重慶 400065）



摘要：

研究多播端到端時(shí)延受限條件下的最優(yōu)時(shí)延抖動(dòng)問題，目前已經(jīng)出現(xiàn)了許多啟發(fā)式算法，如DVMA(delay variation multicast algorithm)、DDVCA(delay and delay variation constraint algorithm)。DDVCA的時(shí)延抖動(dòng)小于DVMA。Cheng等人也提出了一種算法，它的時(shí)延抖動(dòng)小于DDVCA。在此基礎(chǔ)上提出了一種有效的多播路由算法。仿真結(jié)果表明，該算法的平均時(shí)延抖動(dòng)小于Cheng等人的平均時(shí)延抖動(dòng)。

關(guān)鍵詞：時(shí)延； 時(shí)延抖動(dòng)； 多播樹； 時(shí)延和時(shí)延有界的多播樹； 弗洛伊德算法

中圖分類號(hào)：TP393文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：10013695(2009)03105904



Improved algorithm of DVBMT problem



YANG Chundea， YANG Xiaotianb



（a.School of Mathematics Physics， b.School of Computer Science Technology， Chongqing University of Posts Communications， Chongqing 400065， China）



Abstract:

This research was concerned with the problem of minimization of multicast delay variation under the multicast endtoend delay constraints. At present， this paper proposed several heuristic algorithms， such as DVMA( delay variation multicast algorithm)， DDVCA( delay and delay variation constraint algorithm). In the third reference， presented an algorithm which outperforms the bestknown DDVCA. On the basis of the third literature， presented an efficient multicast routing algorithm. It is shown that， in terms of delay variation， the heuristic algorithm is better than the algorithm in the third literature on average.

Key words：delay; delay variation(delay and delay variation bounded multicast tree); multicast tree; DVBMT; Floyd algorithm



0引言

隨著網(wǎng)絡(luò)技術(shù)的飛速進(jìn)步，許多多播通信應(yīng)用（如視頻會(huì)議、分布式交互仿真、在線購(gòu)物、股市交易、在線游戲等）需要網(wǎng)絡(luò)支持多播且能夠保證QoS（服務(wù)質(zhì)量）。在實(shí)時(shí)通信中，消息必須在一定的時(shí)間范圍內(nèi)發(fā)送到目的節(jié)點(diǎn)，否則消息就會(huì)變得無(wú)效。例如視頻會(huì)議和在線游戲必須接收最新的圖像和聲音。如果接收延時(shí)十幾秒，用戶就會(huì)很不耐煩。

為了支持實(shí)時(shí)多播通信，通信網(wǎng)絡(luò)必須保證從源節(jié)點(diǎn)到每個(gè)目的節(jié)點(diǎn)的時(shí)延小于一個(gè)給定的上界，這就是多播端到端的時(shí)延問題。端到端的時(shí)延是一個(gè)重要的QoS參數(shù)，它能保證從源節(jié)點(diǎn)發(fā)送的信息在一定的時(shí)間范圍內(nèi)到達(dá)目的節(jié)點(diǎn)。

另一方面，如果同樣的消息不能同時(shí)到達(dá)每個(gè)目的節(jié)點(diǎn)，用戶之間就會(huì)產(chǎn)生不一致性或不公平性。例如，在一個(gè)分布式數(shù)據(jù)庫(kù)系統(tǒng)中，如果不同的工作站在不同的時(shí)刻接收同一條消息，計(jì)算結(jié)果就會(huì)不準(zhǔn)確。又如在線游戲中，幾個(gè)玩家連接到同一臺(tái)服務(wù)器上，毫無(wú)疑問，所有的玩家必須同時(shí)接收?qǐng)D像和聲音才能公平競(jìng)爭(zhēng)。在會(huì)議電視中，特別強(qiáng)調(diào)講話者的話音被其他與會(huì)者同時(shí)聽到，否則這種通信就顯得缺乏面對(duì)面實(shí)時(shí)交互對(duì)話的特性。這些應(yīng)用都與時(shí)延抖動(dòng)問題有關(guān)。時(shí)延抖動(dòng)約束是為了保證不同的接收者在接收信息時(shí)保持同步，不讓某些接收者特別落后或特別提前。

本文研究時(shí)延受限條件下的最優(yōu)時(shí)延抖動(dòng)問題。具體來(lái)說(shuō)，給定一個(gè)網(wǎng)絡(luò)，一個(gè)源節(jié)點(diǎn)，一個(gè)目的節(jié)點(diǎn)集合，本文所要做的就是構(gòu)建一棵多播樹，它以源節(jié)點(diǎn)為根，以目的節(jié)點(diǎn)為葉子節(jié)點(diǎn)，使得從源節(jié)點(diǎn)到每個(gè)目的節(jié)點(diǎn)的時(shí)延小于一個(gè)給定的上界，而且目的節(jié)點(diǎn)間的多播時(shí)延抖動(dòng)最小。

1相關(guān)工作

時(shí)延和時(shí)延差受限多播問題目前主要研究的有兩個(gè)方面，即不考慮費(fèi)用優(yōu)化和考慮費(fèi)用優(yōu)化的問題。文獻(xiàn)[1~3]研究不考慮費(fèi)用優(yōu)化的問題，文獻(xiàn)[4，5]研究考慮費(fèi)用優(yōu)化的問題。本文研究前一種問題，即不考慮費(fèi)用優(yōu)化的問題，又被稱之為DVBMT[1] (delay and delay variation bounded multicast tree) 問題，并且被證明是一個(gè)NP完全問題。DVBMT是由G. N.Rouskas等人提出來(lái)的，同時(shí)他們提出了一種解決辦法，即DVMA[1] (delay variation multicast algorithm) 算法。該算法首先找到SPT(shortest path tree) 中一個(gè)距離源節(jié)點(diǎn)s最遠(yuǎn)的目標(biāo)節(jié)點(diǎn)w，并以s到達(dá)w的k條最短路徑中的一條路徑作為初始多播樹，然后再逐漸向初始多播樹中加入剩余的目標(biāo)節(jié)點(diǎn)。這一算法得到了良好的預(yù)期結(jié)果，即算法返回的多播樹時(shí)延差很小，其算法的時(shí)間復(fù)雜度為O(klmn4)，m為多播節(jié)點(diǎn)的數(shù)目，n為網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)。

為了進(jìn)一步減少時(shí)延抖動(dòng)，又出現(xiàn)了DDVCA[2] (delay and delay variation constraint algorithm) 算法。DDVCA性能優(yōu)于DVMA。DDVCA是基于CBT(core based tree)和SP(shortest path) 啟發(fā)式算法，即CBT+SP。首先通過(guò)連接源節(jié)點(diǎn)到中心節(jié)點(diǎn)，再連接中心節(jié)點(diǎn)和各個(gè)目的節(jié)點(diǎn)來(lái)構(gòu)建多播樹。

CBT+SP啟發(fā)式算法的思想是：對(duì)每一個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)，算法首先構(gòu)建從該網(wǎng)絡(luò)節(jié)點(diǎn)到各個(gè)目的節(jié)點(diǎn)的最短時(shí)延路徑，求出從該網(wǎng)絡(luò)節(jié)點(diǎn)到各個(gè)目的節(jié)點(diǎn)的時(shí)延抖動(dòng)。選擇時(shí)延抖動(dòng)最小的網(wǎng)絡(luò)節(jié)點(diǎn)作為中心節(jié)點(diǎn)；然后檢查從源節(jié)點(diǎn)到中心節(jié)點(diǎn)的最短時(shí)延與從中心節(jié)點(diǎn)到各個(gè)目的節(jié)點(diǎn)的最大時(shí)延之和是否滿足多播端到端的時(shí)延限制。如果超出時(shí)延限制，該中心節(jié)點(diǎn)將被拋棄，算法繼續(xù)選擇下一個(gè)時(shí)延抖動(dòng)最小的節(jié)點(diǎn)作為中心節(jié)點(diǎn)，并重復(fù)上述步驟直到找到滿足時(shí)延限制的中心節(jié)點(diǎn)。CBT+SP啟發(fā)式算法所構(gòu)建的多播樹的時(shí)延抖動(dòng)就是中心節(jié)點(diǎn)到各個(gè)目的節(jié)點(diǎn)的時(shí)延抖動(dòng)。

文獻(xiàn)[3]指出了CBT+SP算法存在的兩個(gè)缺陷：a）目的節(jié)點(diǎn)位于源節(jié)點(diǎn)到中心節(jié)點(diǎn)的最短時(shí)延路徑上；b）存在某個(gè)目的節(jié)點(diǎn)，從源節(jié)點(diǎn)到中心節(jié)點(diǎn)的最短時(shí)延路徑與從中心節(jié)點(diǎn)到該目的節(jié)點(diǎn)的最短時(shí)延路徑有重疊。文獻(xiàn)[3]提出了一個(gè)有效的QoS多播路由算法，時(shí)延抖動(dòng)小于DDVCA。文獻(xiàn)[3]中提到，該算法是第一個(gè)性能優(yōu)于DDVCA的算法，是目前為止時(shí)延抖動(dòng)性能最優(yōu)的算法。

本文在文獻(xiàn)[3]的基礎(chǔ)上也提出了一種算法，仿真結(jié)果表明本文的算法能夠在此基礎(chǔ)上進(jìn)一步減小時(shí)延抖動(dòng)。

2時(shí)延和時(shí)延抖動(dòng)受約束的多播網(wǎng)絡(luò)模型

用賦權(quán)無(wú)向圖G=(V，E)表示一個(gè)網(wǎng)絡(luò)，V代表工作站或路由器的集合，E代表節(jié)點(diǎn)之間的鏈路集合。n=|V|代表網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)目。對(duì)每條鏈路l∈E，定義一個(gè)鏈路時(shí)延函數(shù)D:l→R+。用一個(gè)非負(fù)值D(l)代表消息沿著鏈路l的傳輸時(shí)延。

源節(jié)點(diǎn)用vs表示，vs∈V；目的節(jié)點(diǎn)集用M表示，MV-{vs}，m=|M|表示目的節(jié)點(diǎn)的個(gè)數(shù)。從源節(jié)點(diǎn)vs發(fā)送一個(gè)消息，經(jīng)過(guò)一些其他節(jié)點(diǎn)，最后到達(dá)目的節(jié)點(diǎn)集合M。

消息沿著一棵樹T=(VT，ET)到達(dá)M中每一個(gè)節(jié)點(diǎn)。T可能包含其他節(jié)點(diǎn)，這些節(jié)點(diǎn)不屬于M∪vs，它們只是用來(lái)作為中轉(zhuǎn)節(jié)點(diǎn)。定義PT(vs，vw)為從源節(jié)點(diǎn)vs到樹T上一個(gè)目的節(jié)點(diǎn)vw∈M的路徑。從vs到vw的傳輸時(shí)延定義為∑l∈PT(vs，vw)D（l）。

定義多播通信中兩個(gè)重要的服務(wù)質(zhì)量參數(shù)，即Δ和δ。Δ為多播端到端的時(shí)延限制，它表示從源節(jié)點(diǎn)到所有目的節(jié)點(diǎn)時(shí)延的上界。設(shè)置Δ的目的就是限制消息在網(wǎng)絡(luò)中傳輸?shù)臅r(shí)間。如果端到端的時(shí)延超出時(shí)延上界，消息就失效了。δ為多播時(shí)延抖動(dòng)，它表示從源節(jié)點(diǎn)到所有目的節(jié)點(diǎn)的最大時(shí)延與最小時(shí)延之差應(yīng)小于δ。設(shè)置δ的目的是為了使得所有的目的節(jié)點(diǎn)盡可能同時(shí)接收到同樣的數(shù)據(jù)。為了保證多播通信的QoS，從源節(jié)點(diǎn)到各目的節(jié)點(diǎn)的端到端時(shí)延不應(yīng)超過(guò)端到端的時(shí)延約束Δ，而且各目的節(jié)點(diǎn)間的時(shí)延抖動(dòng)應(yīng)該最小。

本文用ΔT表示多播樹T中端到端的時(shí)延，用δT表示多播時(shí)延抖動(dòng)。

在上述符號(hào)的基礎(chǔ)上，本文描述DVBMT問題如下：

給定一個(gè)賦權(quán)無(wú)向圖G=（V，E），源節(jié)點(diǎn)vs∈V，目的節(jié)點(diǎn)集MV-{vs}，鏈路時(shí)延函數(shù)D:l→R+（l∈E），時(shí)延約束Δ，尋找一棵最優(yōu)的多播樹T*=(VT*，ET*)，{vs}∪MVT*，ET*E，滿足：

a)ΔT*=maxvw∈M{∑l∈PT*(vs，vw)D(l)}≤Δ

b）δT*=minT{maxvu，vw∈M{∑l∈PT(vs，vu)D(l)-∑l∈PT(vs，vw)D(l)}}

其中：T定義為圖G（V，E）中包含vs和M的任何一棵多播樹。

DVBMT問題被證明是NP完全問題，只能定義各種啟發(fā)式算法，并通過(guò)理論分析和實(shí)驗(yàn)?zāi)M來(lái)評(píng)估算法的性能。

3基于時(shí)延有界的最小時(shí)延抖動(dòng)算法

3.1算法描述

本文研究時(shí)延受限條件下的最優(yōu)時(shí)延抖動(dòng)問題，屬于DVBMT問題。對(duì)于DVBMT問題而言，最短路徑就是最短時(shí)延路徑。

文獻(xiàn)[3]算法思路是：

a)設(shè)dvmin為最小時(shí)延抖動(dòng)，vc為中心節(jié)點(diǎn)。

dvmin=∞，vc=

b)對(duì)每一個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)vi，執(zhí)行以下操作：計(jì)算源節(jié)點(diǎn)vs到vi的最短路徑P。對(duì)每個(gè)目的節(jié)點(diǎn)vw∈M，計(jì)算vi到vw的最短路徑Pw，選擇P上與目的節(jié)點(diǎn)vw最近的節(jié)點(diǎn)記為pk，vs到vw的時(shí)延就是路徑P上vs到pk的時(shí)延與路徑pw上pk到vw的時(shí)延之和。如果所得時(shí)延大于端到端的時(shí)延限制，則拋棄此節(jié)點(diǎn)，轉(zhuǎn)而考慮下一個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)。計(jì)算vs到各個(gè)目的節(jié)點(diǎn)的時(shí)延抖動(dòng)dv(vi)。如果dv(vi)＜dvmin，則令vc=vi，dvmin=dv(vi)。

c)如果vc=，則表示所求的多播樹不存在；否則，將源節(jié)點(diǎn)vs與中心節(jié)點(diǎn)vc通過(guò)最短路徑連接起來(lái)，將vc與各個(gè)目的節(jié)點(diǎn)通過(guò)最短路徑連接起來(lái)，就得到了最后的多播樹。

本文算法思路是：首先利用文獻(xiàn)[3]算法構(gòu)建多播樹T，求出源節(jié)點(diǎn)到各個(gè)目的節(jié)點(diǎn)的時(shí)延，求出平均時(shí)延和最大時(shí)延。找出大于平均時(shí)延的目的節(jié)點(diǎn)，找出多播樹中源節(jié)點(diǎn)到這些節(jié)點(diǎn)的路徑，構(gòu)成多播樹T1。對(duì)時(shí)延小于平均值的每個(gè)目的節(jié)點(diǎn)vw，尋找T1中的某個(gè)點(diǎn)w*，使得將vw到w*的最短路徑連接到樹T1上時(shí)，所得的新時(shí)延滿足：（a）大于原有時(shí)延；（b)小于等于最大時(shí)延；（c)與最大時(shí)延最為接近；（d)vw到w*的最短路徑上沒有樹T1上的點(diǎn)（w*除外）。如果沒有找到這樣的點(diǎn)，就將T中vs到vw的路徑添加到T1中。因?yàn)樾聲r(shí)延大于等于原有時(shí)延，同時(shí)又小于最大時(shí)延，所以就達(dá)到了減小時(shí)延抖動(dòng)的目的。

算法具體步驟如下：

a）設(shè)T1為最后所求的多播樹，T1= ，集合U=。

b）利用Floyd最短時(shí)延路徑算法計(jì)算出所有節(jié)點(diǎn)之間的最短路徑，d[i][j]表示根據(jù)Floyd算法求出的節(jié)點(diǎn)i與j之間的最小時(shí)延。

c）用文獻(xiàn)[3]的算法構(gòu)建一棵多播樹T，計(jì)算出源點(diǎn)到每個(gè)目的節(jié)點(diǎn)v的時(shí)延值D[v]，求出所有時(shí)延的平均值aver，并求出最大時(shí)延max。

d）建立兩個(gè)表：list1和list2，將目的節(jié)點(diǎn)中時(shí)延大于aver的節(jié)點(diǎn)加入表list1中，將目的節(jié)點(diǎn)中時(shí)延小于aver的節(jié)點(diǎn)加入表list2中。

e）對(duì)表list1中的每個(gè)目的節(jié)點(diǎn)，找出T中從vs到該目的節(jié)點(diǎn)的路徑P，將P加入到樹T1中，并記下vs到路徑P上每個(gè)點(diǎn)w的時(shí)延delay[w]。

f）對(duì)表list2中的每個(gè)目的節(jié)點(diǎn)v1，執(zhí)行以下操作：如果v1已經(jīng)在樹T1中，則不做任何操作；否則，令U=，v1到樹T1中每個(gè)點(diǎn)w的最小時(shí)延為d[v1][w]（已經(jīng)由b）求出）。如果v1到w的最短路徑P1（已經(jīng)由b）求出）上的點(diǎn)（不含w）都不在樹T1中，并且D[v1]＜delay[w]+d[v1][w]≤max(D[v1]為樹T中從vs到v1的時(shí)延)，就將節(jié)點(diǎn)w作為候選節(jié)點(diǎn)加入集合U中。在考查完樹T1中的所有節(jié)點(diǎn)后，對(duì)U中的每個(gè)點(diǎn)w1，計(jì)算max-(delay[w1]+d[v1][w1])，選擇對(duì)應(yīng)值最小的點(diǎn)為w*，將v1到w*的最短時(shí)延路徑添加到樹T1中。如果集合U=，則表示沒有符合要求的節(jié)點(diǎn)。此時(shí)，令T1=T，轉(zhuǎn)g)。

g）最后所得的多播樹T1就是所求。

3.2算法性能分析

定理1本算法的時(shí)延抖動(dòng)小于等于文獻(xiàn)[3]算法的時(shí)延抖動(dòng)，并且不會(huì)產(chǎn)生環(huán)路。

證明本算法對(duì)時(shí)延較小的目的節(jié)點(diǎn)的處理原則是：如果計(jì)算得到的新時(shí)延大于原來(lái)的時(shí)延，同時(shí)小于最大時(shí)延，并且目的節(jié)點(diǎn)v1與樹上節(jié)點(diǎn)w的最短時(shí)延路徑上沒有樹T1上的節(jié)點(diǎn)（w除外），則將w作為候選節(jié)點(diǎn)加入集合U中。從U中選擇與最大時(shí)延最接近的路徑添加到多播樹T1中。否則仍然采用文獻(xiàn)[3]求出的路徑。由于新的時(shí)延大于等于原有時(shí)延，時(shí)延抖動(dòng)小于等于文獻(xiàn)[3]算法的時(shí)延抖動(dòng)，而且由于挑選的路徑都不包含樹T1上的點(diǎn)，不會(huì)產(chǎn)生環(huán)路。

3.3算法復(fù)雜度分析

文獻(xiàn)[3]算法時(shí)間復(fù)雜度是O(mn)2(m代表目的節(jié)點(diǎn)數(shù)目，n代表網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)目)。3.1節(jié)中步驟b）Floyd算法的時(shí)間復(fù)雜度為O(n3)；對(duì)c）而言，構(gòu)建多播樹T時(shí)間復(fù)雜度是O(mn2)，計(jì)算平均時(shí)延和最大時(shí)延復(fù)雜度為O(m)，所以c）的復(fù)雜度是O(mn2)+O(m)=O(mn2)；對(duì)d）選擇小于平均時(shí)延的目的節(jié)點(diǎn)復(fù)雜度是O(m)；對(duì)e）構(gòu)建T1復(fù)雜度是O(mn)；對(duì)f）復(fù)雜度為O(mn)。所以，總的時(shí)間復(fù)雜度為O(n3)+O(mn2)+O(m)+O(mn)=O(n3)，略高于文獻(xiàn)[3]算法時(shí)間復(fù)雜度，但是小于DVMA[1]算法的時(shí)間復(fù)雜度O(klmn4)。

4算法舉例分析

如圖1所示，源節(jié)點(diǎn)vs=1，目的節(jié)點(diǎn)集合為M={3，4，8，9，10}，即邊框較粗的節(jié)點(diǎn)，Δ=58.5。連線上的數(shù)字代表時(shí)延值。

按照文獻(xiàn)[3]的方法，所生成的多播樹T如圖2所示，中心節(jié)點(diǎn)為1。

源節(jié)點(diǎn)到目的節(jié)點(diǎn)的路徑分別為

1→4時(shí)延：29

1→9時(shí)延：9

1→9→10時(shí)延：19

1→8時(shí)延：17

1→8→3時(shí)延：39

由文獻(xiàn)[3]算法所得的多播樹的時(shí)延抖動(dòng)是39-9=30。

本文利用文獻(xiàn)[3]算法求出源節(jié)點(diǎn)到各個(gè)目的節(jié)點(diǎn)的時(shí)延，并求出平均時(shí)延為22.6，最大時(shí)延39。小于平均時(shí)延的目的節(jié)點(diǎn)是8、9、10。構(gòu)建T中由源節(jié)點(diǎn)和大于平均時(shí)延的目的節(jié)點(diǎn)（即3和4）組成的多播樹T1，如圖3所示。

由于目的節(jié)點(diǎn)8在T1中，不做任何操作。轉(zhuǎn)而考查目的節(jié)點(diǎn)9，計(jì)算9到T1中每個(gè)節(jié)點(diǎn)的最短時(shí)延，選擇T1中合適的節(jié)點(diǎn)w*，使得T1中源節(jié)點(diǎn)到w*的時(shí)延與w*到9最小時(shí)延之和小于最大時(shí)延39，同時(shí)大于原有時(shí)延9，并且與最大時(shí)延之差的絕對(duì)值最小。對(duì)目的節(jié)點(diǎn)9而言，T1中符合要求的節(jié)點(diǎn)w*就是8，新路徑為1→8→9，對(duì)應(yīng)時(shí)延為26，將目的節(jié)點(diǎn)9到T1中節(jié)點(diǎn)8的最短路徑添加到T1中。對(duì)目的節(jié)點(diǎn)10，當(dāng)它通過(guò)節(jié)點(diǎn)8連接到樹上時(shí)，即1→8→10，對(duì)應(yīng)時(shí)延為27，而當(dāng)它通過(guò)節(jié)點(diǎn)9連接到樹上時(shí)，即1→8→9→10，對(duì)應(yīng)時(shí)延為36，更加接近最大時(shí)延，所以選擇通過(guò)節(jié)點(diǎn)9連接到T1中。

最后得到的多播樹如圖4所示。

源節(jié)點(diǎn)到目的節(jié)點(diǎn)的路徑分別為

1→4時(shí)延：29

1→8時(shí)延：17

1→8→3時(shí)延：39

1→8→9時(shí)延：26

1→8→9→10時(shí)延：36

修改后的時(shí)延抖動(dòng)是：39-17=22。

可以看到，由于修改了目的節(jié)點(diǎn)中時(shí)延較小的節(jié)點(diǎn)到源節(jié)點(diǎn)的路徑，使得在不改變最大時(shí)延的情況下將時(shí)延較小的目的節(jié)點(diǎn)加入到T1中，使新的時(shí)延值大于等于原有的時(shí)延值，達(dá)到了減小時(shí)延抖動(dòng)的目的。

5計(jì)算機(jī)仿真模型和結(jié)果

5.1隨機(jī)網(wǎng)絡(luò)模型

仿真實(shí)驗(yàn)中采用文獻(xiàn)[6]的方法產(chǎn)生隨機(jī)網(wǎng)絡(luò)。該模型首先產(chǎn)生一棵遍歷所有節(jié)點(diǎn)的生成樹以保證網(wǎng)絡(luò)的連通性，即使得節(jié)點(diǎn)的度數(shù)大于等于1；然后為確保每個(gè)節(jié)點(diǎn)都是雙連接的，將度數(shù)為1的節(jié)點(diǎn)與另一個(gè)隨機(jī)選擇的節(jié)點(diǎn)產(chǎn)生連接；最后以Waxman[7]提出的隨機(jī)網(wǎng)絡(luò)模型為基礎(chǔ)，產(chǎn)生隨機(jī)鏈路，當(dāng)網(wǎng)絡(luò)的平均節(jié)點(diǎn)度數(shù)達(dá)到給定值時(shí)，便得到了所需的網(wǎng)絡(luò)。任意兩個(gè)節(jié)點(diǎn)u與v之間是否存在鏈路由概率函數(shù)p(u，v)=β exp(-d(u，v))/αL確定。其中：p(u，v)節(jié)點(diǎn)u與v之間存在連接的概率，它與u和v之間的距離d(u，v)有關(guān)；L是任意兩點(diǎn)間的最大距離；α和β是兩個(gè)在0與1之間的參數(shù)。α影響長(zhǎng)鏈路和短鏈路所占的比重，α越大，長(zhǎng)鏈路的比重就越大。參數(shù)β控制網(wǎng)絡(luò)的平均節(jié)點(diǎn)度數(shù)，β越大，網(wǎng)絡(luò)平均節(jié)點(diǎn)度數(shù)越大。α取值為0.4，β取值為0.2。網(wǎng)絡(luò)的鏈路時(shí)延等于1~10的一個(gè)整數(shù)值，該值與鏈路距離成正比。時(shí)延約束Δ設(shè)定為從源點(diǎn)到目的節(jié)點(diǎn)的最大時(shí)延值的1.5倍，網(wǎng)絡(luò)節(jié)點(diǎn)平均度數(shù)為6。

5.2實(shí)驗(yàn)結(jié)果比較和說(shuō)明

圖5和6分別為以上仿真條件下的Floyd最短時(shí)延路徑算法、文獻(xiàn)[3]算法、本文算法產(chǎn)生的多播樹的時(shí)延抖動(dòng)和網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)的關(guān)系，網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)目n從20~100，目的節(jié)點(diǎn)數(shù)目分別為0.1*n和0.3*n，實(shí)驗(yàn)在每個(gè)數(shù)據(jù)點(diǎn)仿真100次并求平均值。所得時(shí)延抖動(dòng)數(shù)據(jù)如表1和2所示。

從表1和2可以看出，本文算法的時(shí)延抖動(dòng)略小于文獻(xiàn)[3]算法的時(shí)延抖動(dòng)。

由圖5和6均可以看出，本文算法比文獻(xiàn)[3]算法能夠獲得更小的時(shí)延抖動(dòng)，兩種算法的時(shí)延抖動(dòng)明顯小于Floyd最短時(shí)延路徑算法的時(shí)延抖動(dòng)。對(duì)比表1和2可以看出，當(dāng)網(wǎng)絡(luò)中的目的節(jié)點(diǎn)數(shù)目增加時(shí)，三種算法的時(shí)延抖動(dòng)均增加。這是因?yàn)榉嵌嗖ス?jié)點(diǎn)減少了，作為合適中轉(zhuǎn)的節(jié)點(diǎn)數(shù)相應(yīng)減少，可選路徑數(shù)少了。

6結(jié)束語(yǔ)

本文對(duì)DVBMT問題進(jìn)行了研究。在文獻(xiàn)[1]中首先給出DVBMT的定義，并提出了一種算法，即DVMA。DVMA擁有較小的時(shí)延抖動(dòng)性能，但是時(shí)間復(fù)雜度很高，為O(klmn4)。針對(duì)此問題，文獻(xiàn)[2]給出了一種算法，即DDVCA。DDVCA的時(shí)延抖動(dòng)小于DVMA，并且擁有較小的時(shí)間復(fù)雜度，為O(mn2)。文獻(xiàn)[3]指出了DDVCA的兩個(gè)缺陷，并加以改進(jìn)，進(jìn)一步減小了時(shí)延抖動(dòng)。本文在由文獻(xiàn)[3]算法構(gòu)建的多播樹的基礎(chǔ)上，通過(guò)盡可能地提高目的節(jié)點(diǎn)中時(shí)延較小的節(jié)點(diǎn)到源節(jié)點(diǎn)的時(shí)延，使其時(shí)延增大的同時(shí)又不超出最大時(shí)延，達(dá)到了減小時(shí)延抖動(dòng)的目的。實(shí)驗(yàn)表明，本算法的時(shí)延抖動(dòng)小于等于文獻(xiàn)[3]的時(shí)延抖動(dòng)。

參考文獻(xiàn)：

[1]ROUSKAS G N， BALDINE I. Multicast routing with endtoend delay and delay variation constraints[J]. IEEE Journal on Selected Areas in Communications，1997，15(3):346356.

[2] SHEU P R， CHEN Shantai. A fast and efficient heuristic algorithm for the delay and delay variation bounded multicast tree problem[J].Computer Communications，2002，25(8):611618.

[3]CHENG Hui，CAO Jiannong， WANG Xingwei. Constructing delaybounded multicast tree with optimal delay variation[C]//Proc of IEEE International Conference on Communications. 2006:800805.

[4]王明中，謝劍英，張敬轅.時(shí)延及時(shí)延抖動(dòng)限制的最小代價(jià)多播路由策略[J].計(jì)算機(jī)學(xué)報(bào)，2002， 25(5):534541.

[5]余燕平，仇佩亮.時(shí)延和時(shí)延抖動(dòng)約束的低費(fèi)用多播路由算法[J].電路與系統(tǒng)學(xué)報(bào)，2001，6(4):6568.

[6]余燕平.多播路由算法的研究[D].杭州：浙江大學(xué)，2002.

[7]WAXMAN B. Routing of multipoint connections[J]. IEEE Journal on Selected Areas in Communications，1988，6(9):16171622.