一種節(jié)點高穩(wěn)定狀態(tài)的應(yīng)用層組播方案

崔建群 ,馬 媛, 常亞楠, 吳黎兵

1(華中師范大學(xué) 計算機學(xué)院, 武漢 430079 )2(武漢大學(xué) 計算機學(xué)院, 武漢 430072)

1 引 言

近年來，由于IPTV直播，視頻點播等應(yīng)用的需求，使得多媒體傳輸?shù)慕M播技術(shù)研究日益發(fā)展.組播(Multicast)是滿足一點對多點通信需求的一種全新高效的技術(shù)，將源節(jié)點數(shù)據(jù)流的副本以多路復(fù)用的方式通過網(wǎng)絡(luò)發(fā)送到一組接受者[1]，而源節(jié)點只需產(chǎn)生并發(fā)送一份數(shù)據(jù)流，經(jīng)過組播樹中路由器的復(fù)制與轉(zhuǎn)發(fā)，將數(shù)據(jù)流傳送到一組目的節(jié)點.

IP組播是網(wǎng)絡(luò)層組播[2]，在通訊時保證在網(wǎng)絡(luò)鏈路中只存在一份數(shù)據(jù)報文，因此可大量節(jié)省服務(wù)器成本與網(wǎng)絡(luò)帶寬，通過路由器來進(jìn)行組播數(shù)據(jù)的復(fù)制和轉(zhuǎn)發(fā)，減輕了服務(wù)器的負(fù)擔(dān)和視頻傳輸時延等問題.但是IP組播仍然存在較多并未解決的缺陷.例如組成員管理，組播擁塞控制以及難以部署等問題，圖1(a)是IP組播.取而代之的是逐漸興起的應(yīng)用層組播(application layer multicast，ALM)[3,4]，應(yīng)用層組播將組播功能由網(wǎng)絡(luò)層轉(zhuǎn)移到終端，由終端主機進(jìn)行數(shù)據(jù)分發(fā)，而節(jié)點

DataPackageLinkrouterserverrouterrouterrouter(a) 網(wǎng)絡(luò)層組播DataPackageLinkserverrouterrouterrouterrouter(b) 應(yīng)用層組播

圖1 組播類型
Fig.1 Multicast classification

間的數(shù)據(jù)傳輸則通過傳統(tǒng)的單播技術(shù)來實現(xiàn)，如此便解決了IP組播部署困難的問題，實現(xiàn)了組播的靈活性與擴展性，圖1(b)是應(yīng)用層組播.

對于應(yīng)用層組播，端系統(tǒng)的穩(wěn)定性與性能不如路由器，這就造成了應(yīng)用層組播在穩(wěn)定性與效率上不如網(wǎng)絡(luò)層組播.由于組播樹的性能會影響轉(zhuǎn)發(fā)數(shù)據(jù)的效率，所以端節(jié)點的穩(wěn)定狀態(tài)與其在組播樹中的位置直接關(guān)系到組播樹的整體表現(xiàn)，本文針對以上問題設(shè)計了一種基于節(jié)點穩(wěn)定狀態(tài)的應(yīng)用層組播方案.

2 相關(guān)工作

在已有的組播樹構(gòu)造算法中，組播協(xié)議分為集中式算法與分布式算法，分布式算法又分為網(wǎng)優(yōu)先算法、樹優(yōu)先算法與隱含式算法.

集中式算法由集中控制點RP(Rendezvous Point)負(fù)責(zé)收集成員節(jié)點的網(wǎng)絡(luò)信息，并周期性計算應(yīng)用層組播樹.RP負(fù)責(zé)數(shù)據(jù)分發(fā)，易于維持組播樹的一致性，但容易單節(jié)點負(fù)載過重并且擴展性差，適用于小規(guī)模、多數(shù)據(jù)源情況，典型協(xié)議有ALMI[5]與HBM[6].

圖2 基于網(wǎng)狀的應(yīng)用層組播樹結(jié)構(gòu)Fig.2 Data structure of mesh-basedoverlay multicast

分布式算法組播樹構(gòu)造與維護依賴于各個節(jié)點維護的局部信息，因此具有良好的擴展性.網(wǎng)優(yōu)先算法將節(jié)點分布式自組織成Mesh，Mesh中各個節(jié)點都要維護全部或者部分成員狀態(tài)信息，來迅速恢復(fù)網(wǎng)絡(luò)分割，并運行組播路由協(xié)議.其優(yōu)點是組成員管理、負(fù)載均衡與數(shù)據(jù)傳輸效率高，缺點是復(fù)雜度較高，維護代價比較大與有限的擴展性.典型協(xié)議有Narada[7]、PRO[8]和Prime[9]等.基于網(wǎng)狀的應(yīng)用層組播數(shù)據(jù)結(jié)構(gòu)如圖2所示，其中節(jié)點A是組播源節(jié)點.

圖3 基于樹狀的應(yīng)用層組播樹結(jié)構(gòu)Fig.3 Data structure of tree-based overlay multicast

樹優(yōu)先算法是成員節(jié)點直接在組內(nèi)選擇父節(jié)點構(gòu)建組播樹，與非鄰居節(jié)點建立并維護控制鏈接，其優(yōu)點是用戶節(jié)點便于直接控制，缺點是進(jìn)行單獨的檢測與回路避免處理.典型協(xié)議有TBCP[10]、Overcast[11]、PROMISE[12]等，基于樹狀的應(yīng)用層組播數(shù)據(jù)結(jié)構(gòu)如圖3所示，其中節(jié)點A是組播源節(jié)點.隱含式算法在構(gòu)造控制拓?fù)渑c數(shù)據(jù)拓?fù)浞矫鏇]有先后次序之分，節(jié)點之間也沒有其余交互信息，控制拓?fù)渲须[含著數(shù)據(jù)拓?fù)?其優(yōu)點是大幅度降低組播成員的處理開銷，具有良好的擴展性.典型協(xié)議有NICE[13]、ZIGZAG[14]、Scribe[15]等.

文獻(xiàn)[20]提出一種基于gossip的應(yīng)用層組播方案，將數(shù)據(jù)分發(fā)過程分為上層分發(fā)以及底層簇內(nèi)分發(fā)兩個階段.該方案具有較高的數(shù)據(jù)分發(fā)成功率，但增加了控制開銷.已有的研究協(xié)議大多針對某一特定應(yīng)用，在特定的前提下以生成最小延時組播樹為目標(biāo)，由于網(wǎng)絡(luò)的易構(gòu)性以及終端節(jié)點用戶的不穩(wěn)定性，必須綜合考慮節(jié)點性能以及所在位置對組播樹的影響.已有的研究協(xié)議大多針對某一特定應(yīng)用，在特定的前提下以生成最小延時組播樹為目標(biāo)，由于網(wǎng)絡(luò)的易構(gòu)性以及終端節(jié)點用戶的不穩(wěn)定性，必須綜合考慮節(jié)點性能以及所在位置對組播樹的影響.

針對節(jié)點穩(wěn)定狀態(tài)與延時的問題，我們抽象出一種合理的問題模型-T-DTD (Spanning tree based on degree-constrained, max on-session time and depth bound for ALM) 模型.在應(yīng)用層組播樹生成過程中，該模型綜合考慮了終端節(jié)點的轉(zhuǎn)發(fā)能力與在線時長，以及節(jié)點所在組播樹中位置這三個因素，構(gòu)造高穩(wěn)定性、低延時應(yīng)用層組播樹.

3 T-DTD模型及相應(yīng)的概念

3.1 組播樹穩(wěn)定性

節(jié)點的穩(wěn)定狀態(tài)對組播樹的穩(wěn)定性有至關(guān)重要的作用.從節(jié)點的行為屬性來看，在線時間越長的節(jié)點、位于組播樹中越高層位置的節(jié)點，組播樹越穩(wěn)定；從節(jié)點度的角度看，組播樹中間節(jié)點轉(zhuǎn)發(fā)能力越強組播樹越穩(wěn)定.文獻(xiàn)[16]用穩(wěn)定度來衡量組播系統(tǒng)的穩(wěn)定性，應(yīng)用層組播穩(wěn)定度定義為公式(1).

(1)

并由此推出公式(2).

(2)

1)直接將帶寬與節(jié)點已在線時間乘積值作為節(jié)點所在的位置，而沒有考慮在實際問題中帶寬與已在線時間對組播樹穩(wěn)定性影響權(quán)重比例問題；

圖4 完全無向圖Fig.4 Complete undirected graph

2)Tan默認(rèn)高度低的組播樹延遲小，但是對應(yīng)用層組播樹而言可能不正確.因此，要提高應(yīng)用層組播樹穩(wěn)定性，既要綜合考慮節(jié)點度與在線時間，還要考慮它們對組播樹穩(wěn)定性影響的權(quán)重問題.

3.2 組播路由問題描述

T-DTD問題模型：在組播路由問題中，通訊網(wǎng)絡(luò)通常用完全無向圖G(V,E)表示，如圖4，其中V是待加入節(jié)點集合，E是路徑集合，算法過程是由圖G生成樹T，將G中的節(jié)點及相關(guān)邊加入到T中.

定義1.節(jié)點度是衡量一個節(jié)點轉(zhuǎn)發(fā)能力的指標(biāo).B(vi)為節(jié)點vi的上行帶寬，R為流媒體播放速度，節(jié)點在加入組播樹時帶有自己的出度，根據(jù)數(shù)據(jù)流的狀態(tài)可以計算節(jié)點出度.節(jié)點vi的出度定義為節(jié)點上行帶寬與流媒體傳輸速率的比值，可用公式(3)表示.

Deg(vi)=B(vi)/R

(3)

定義2.節(jié)點深度表示節(jié)點所在組播樹中的層次，根節(jié)點層次為1.若根節(jié)點不空時深度記為1；若根節(jié)點為空時則深度記為0，在此模型中都假設(shè)根節(jié)點不空.節(jié)點的深度可表示為公式(4).

(4)

定義3. 在應(yīng)用層組播樹中，所有節(jié)點組成集合V，V(T)={v1,v2,…,vn-1,vn}，n為組播樹中節(jié)點個數(shù)，則組播樹T的平均深度按公式(5)所示.

(5)

定義4.節(jié)點在線時間表示從節(jié)點成功加入到組播樹的時間到當(dāng)前時刻的時間段，在線時間越長，表示節(jié)點繼續(xù)停留平均時間也越大，節(jié)點退出概率越小.節(jié)點的在線時間可用公式(6)表示，其中Tjoin(vi)表示節(jié)點vi的請求加入時間，t表示當(dāng)前時間.

Ton-session(vi)=t-Tjoin(vi)

(6)

定義5.節(jié)點穩(wěn)定度因子(Nodedegreeofstability,NSD)是表示節(jié)點穩(wěn)定狀態(tài)的指標(biāo)，NSD越大，表示節(jié)點越穩(wěn)定，節(jié)點越穩(wěn)定，組播樹性能越好.節(jié)點vi(1≤i≤n)的出度Deg(vi)，節(jié)點在線時間Ton-session(vi)，則公式(7)可表示節(jié)點的穩(wěn)定度因子.

(7)

其中?為穩(wěn)定度因子權(quán)重系數(shù)，根據(jù)不同的應(yīng)用環(huán)境權(quán)重系數(shù)取不同的值.Bishop和Rao等人研究異構(gòu)環(huán)境中組播樹穩(wěn)定性問題[19]，實驗結(jié)果顯示，基于節(jié)點度的策略優(yōu)勢明顯優(yōu)勝于基于節(jié)點已在線時間的策略，基于節(jié)點在線時間的策略中，節(jié)點頻繁的更改自己的位置，其優(yōu)勢不明顯.因此在綜合計算節(jié)點穩(wěn)定度因子時，這里設(shè)置度所占權(quán)重?為大于0.5小于等于1的實數(shù).

4 基于節(jié)點穩(wěn)定狀態(tài)的組播方案

為了更好地對算法進(jìn)行說明，本文將組播樹中已有節(jié)點用三元組N(T,Deg,C)信息來表示，如圖5所示.其中T表示節(jié)點在線時間，Deg表示節(jié)點的轉(zhuǎn)發(fā)能力，C為候選父節(jié)點集合.實線部分表示已構(gòu)建的組播樹，虛線部分表示待加入節(jié)點有可能的位置.在構(gòu)建組播樹的過程中，節(jié)點候選位置集合為ST={E,F,G,H}.

4.1 組播樹的建立

本文將解決T-DTD(Spanning tree based on degree-constrained, maxon-session time and depth bound for ALM)問題模型的算法定義為DTD-H(DTD-heuristic)算法.DTD-H基本數(shù)據(jù)結(jié)構(gòu)與具體算法可以描述如下：

m為組播樹中小于平均節(jié)點深度的節(jié)點數(shù)目.

圖5 組播樹
Fig.5 Multicast tree

臨時集合(Templeset,TS)：記錄組播樹中深度小于等于平均樹深度并且具有度剩余的節(jié)點集合，TS={v1,v2,…,vm-1,vm}.

候選父節(jié)點優(yōu)先級集合(priority set of candidate parents,CPPS)：記錄可以納入新孩子節(jié)點的節(jié)點集合，并按照節(jié)點穩(wěn)定度因子降序排序.

輸入：G(V,E)，圖中每個節(jié)點帶有出度Deg(Vi)，深度Dep(Vi) ，以及節(jié)點在線時間.

輸出：樹T.

初始化待求樹T=φ，將源節(jié)點s納入到樹T中.

1) 計算組播樹平均深度Depavg(T)，圖5中Depavg(T)=(1+2+2+2+3)/5=2.

2) 取V′中深度不大于?Depavg(T)」 且有剩余出度的節(jié)點位置得到集合TS，如果所有候選位置深度都大于?Depavg(T)」，則取深度最小的候選位置得TS.

3) 計算TS中的候選父節(jié)點的節(jié)點穩(wěn)定度因子NSD，并按照節(jié)點穩(wěn)定度因子大小降序排序得CPPS.

4) 取CPPS中穩(wěn)定度因子最大的節(jié)點作為待加入節(jié)點N的最佳候選父節(jié)點.每成功加入一個節(jié)點，候選父節(jié)點度減少1.

5) 實時更新修改集合TS、CPPS.

算法偽代碼如下：

DTD-H Algorithm

Input：G(V,E),for anyv∈V

Output：T(V,E′)

Procedure:

1)T=φ;TS=φ.

2)V(T)←s;

3)TS←{s};

5)FOR each node in V′

6)IF node′s out-degree is not full and node′s depth≤?Depavg(T)」

7)TS←v.

8) END IF

9) END FOR

10) FOR each node inTS

11) calculateNSDof each node and sort the nodes ofCPPS

12) father←select the first node ofCPPS

13) out-degree[father]= out-degree[father]-1.

14) updateTSandCPPS

15) END FOR

16) END WHILE

4.2 組播樹的維護

4.2.1 組播樹調(diào)整

在文獻(xiàn)[17]中，對視頻日志進(jìn)行統(tǒng)計分析，驗證了用戶在線時間符合對數(shù)正態(tài)分布，并指出用戶剩余在線時間隨著用戶在線時間增大而增大.本文對文獻(xiàn)[17]中統(tǒng)計數(shù)據(jù)進(jìn)行分析，將節(jié)點分為以下三類：當(dāng)節(jié)點在線時間小于200秒時，有超過70%的節(jié)點會在連接后的200秒內(nèi)選擇退出，為保證組播樹的穩(wěn)定狀態(tài)，應(yīng)當(dāng)使該節(jié)點遠(yuǎn)離根節(jié)點；在線時間在200秒到2000秒之間的節(jié)點，對降低節(jié)點的退出概率相比第一類節(jié)點已有較大提升；而在線時間超過2000秒的節(jié)點，其剩余在線時間在10的三次方數(shù)量級以上，節(jié)點已處于相對穩(wěn)定的狀態(tài)，所以為保證組播樹的穩(wěn)定狀態(tài)，應(yīng)當(dāng)使該節(jié)點靠近根節(jié)點.

節(jié)點不僅要維護自己的信息，還要保存孩子節(jié)點的信息.當(dāng)新節(jié)點加入組播樹后，分別計算父節(jié)點與子節(jié)點的NSD值，當(dāng)父節(jié)點的穩(wěn)定度因子小于子節(jié)點的穩(wěn)定度因子時，則將父節(jié)點與子節(jié)點進(jìn)行交換.本文將節(jié)點交換的周期設(shè)置為200秒，即每隔200秒對組播樹內(nèi)的節(jié)點進(jìn)行動態(tài)維護.

4.2.2 節(jié)點離開

節(jié)點離開組播樹有兩種方式：友好離開方式，將離開消息通知給父節(jié)點與子節(jié)點；意外離開方式，由于外在故障原因未能將離開消息告知父節(jié)點與子節(jié)點.

當(dāng)節(jié)點離開時，非葉子節(jié)點的離開會導(dǎo)致其子孫節(jié)點離開組播樹從而中斷數(shù)據(jù)傳輸，最簡單的一種解決方法是使中斷連接的節(jié)點重新申請加入到組播樹中，但是這樣會花費較多時間，降低組播樹的服務(wù)質(zhì)量，因此針對以上兩種節(jié)點離開方式，本文分別給出兩種快速恢復(fù)組播樹機制.設(shè)F(A)為A的父節(jié)點，C(A)為A的孩子節(jié)點集.

1)友好離開

當(dāng)節(jié)點A離開時，告知父節(jié)點F(A)與子節(jié)點C(A)自己將要離開的消息，F(xiàn)(A)收到離開消息后將A的有關(guān)信息刪除，C(A)收到A的離開消息后則將C(A)中節(jié)點按照NSD值排序.因為A節(jié)點的離開，F(xiàn)(A)一定有空余出度，然后將C(A)中排序后的節(jié)點依次作為F(A)的子節(jié)點.若C(A)中還存在子孫節(jié)點，則剩余節(jié)點以集合中NSD值最大的節(jié)點作為父節(jié)點加入組播樹.

2)意外離開

這種情況下A離開時，并未告知父節(jié)點F(A)與子節(jié)點C(A).子節(jié)點在一段時間未收到A節(jié)點發(fā)送的數(shù)據(jù)，則向A節(jié)點發(fā)送心跳探測消息.若A節(jié)點回應(yīng)則說明節(jié)點仍然在組播樹上，無需進(jìn)行任何操作；若A一段時間未回應(yīng)則說明A節(jié)點已失效，C(A)將A失效已離開的消息告知F(A)，后續(xù)操作和節(jié)點友好離開組播樹的處理方式相同.

5 仿真實驗

本文將通過仿真實驗對比DTD-H算法與NICE算法和度優(yōu)先算法以及隨機算法在平均加入時延、最大加入時延和鏈路伸展度這三方面性能.NICE[13]協(xié)議是一種典型的分層分簇的應(yīng)用層組播協(xié)議，它可以支持大量不同的數(shù)據(jù)轉(zhuǎn)發(fā)樹，有較強的可擴展性.度優(yōu)先算法[19]是優(yōu)先考慮有最大度的節(jié)點并且以最大度節(jié)點為父節(jié)點加入新節(jié)點的過程.隨機算法是隨機選擇組播樹中仍有剩余出度的節(jié)點將新節(jié)點加入組播樹的過程.

5.1 仿真實驗的環(huán)境

為了驗證DTD-H算法的性能，本節(jié)對算法進(jìn)行實驗.這里使用OMNet++作為模擬環(huán)境，以O(shè)verSim[21]為基礎(chǔ)進(jìn)行代碼編寫和模擬實驗.

OMNet++是Objective Modular Network Testbed in C++的縮寫，是一個免費且開源的網(wǎng)絡(luò)環(huán)境模擬軟件，其通過對基礎(chǔ)底層網(wǎng)絡(luò)事件的模擬可以精確的復(fù)現(xiàn)出近似實際網(wǎng)絡(luò)的結(jié)果.而OverSim則是基于OMNet++實驗環(huán)境的一套覆蓋網(wǎng)絡(luò)模擬框架，該框架包含了基本的組播覆蓋網(wǎng)絡(luò)實現(xiàn)算法，為實現(xiàn)自定義的各種覆蓋網(wǎng)絡(luò)算法提供了較為便利的開發(fā)環(huán)境.通過復(fù)用OverSim的部分代碼，可以很容易的開發(fā)并設(shè)計出自己想要的覆蓋網(wǎng)絡(luò)模型.該仿真器可以運行于 Linux和Windows 等多個平臺.圖6是節(jié)點數(shù)目為150時，DTD-H算法的模擬仿真架構(gòu)圖.

圖6 模擬仿真架構(gòu)圖Fig.6 Simulation framework diagram

5.2 實驗參數(shù)設(shè)置

下列是對實驗中相關(guān)參數(shù)的設(shè)置情況：

1)節(jié)點的出度代表著節(jié)點的轉(zhuǎn)發(fā)能力，節(jié)點的最大出度表現(xiàn)為該節(jié)點能夠容納孩子節(jié)點的最大數(shù)目.根據(jù)文獻(xiàn)[22,23]中采用的實驗參數(shù)，本文在仿真實驗中采用節(jié)點的最大出度degmax(vi)服從整數(shù)區(qū)間[2,6]之間的均勻分布；

2)在文獻(xiàn)[17]中，對視頻日志進(jìn)行統(tǒng)計分析時，當(dāng)節(jié)點在線時間小于200秒時，有超過70%的節(jié)點會在連接后的200秒內(nèi)選擇退出，為保證組播樹的穩(wěn)定狀態(tài)，因此在實驗中設(shè)置組播樹更新調(diào)整維護周期為200s.

5.3 性能指標(biāo)

平均加入時延：當(dāng)新的節(jié)點要加入組播樹中時，在組播樹中找到最合適的父節(jié)點，并且向父節(jié)點發(fā)送加入請求，父節(jié)點發(fā)出回應(yīng)后才能順利加入.從開始找父節(jié)點到最后順利加入到組播樹中所花費的時間的平均值.加入時延越小，新節(jié)點就能越迅速加入到組播樹中，也就能更快接收到數(shù)據(jù).假設(shè)vi節(jié)點發(fā)送加入請求時刻為t0，父節(jié)點發(fā)送回應(yīng)消息的時刻為t(vi)，組播樹中節(jié)點總數(shù)為n，則平均加入時延tave的計算如公式(8)所示.

(8)

最大加入時延：新節(jié)點在加入組播樹的過程中，在組播樹中找到最合適的父節(jié)點，向父節(jié)點發(fā)送加入請求后才能順利加入.假設(shè)vi節(jié)點發(fā)送加入請求時刻為t1，父節(jié)點發(fā)送回應(yīng)消息的時刻為tmax，則最大加入時延的計算如公式(9)所示.

tdelay=tmax-t1

(9)

平均鏈路伸展長度：對于組播樹中的每個成員節(jié)點，數(shù)據(jù)從數(shù)據(jù)源經(jīng)過其他節(jié)點轉(zhuǎn)發(fā)到達(dá)該節(jié)點所走過的路徑長度，是衡量組播數(shù)據(jù)路徑質(zhì)量的主要標(biāo)準(zhǔn).設(shè)數(shù)據(jù)從數(shù)據(jù)源經(jīng)過其他節(jié)點轉(zhuǎn)發(fā)到節(jié)點vi所走過的路徑長度為Leg,則平均鏈路伸展長度的計算公式如公式(10)所示.

(10)

5.4 仿真結(jié)果分析

將DTD-H算法與Nice算法、度優(yōu)先算法、隨機算法在平均加入時延、最大加入延時與平均鏈路伸展長度方面對比.

圖7統(tǒng)計了當(dāng)節(jié)點數(shù)目為10～150時，節(jié)點加入到組播樹中所需要的平均時間，當(dāng)節(jié)點數(shù)目為10的時候，度優(yōu)先算法在比較少的節(jié)點里可以快速找到有最大度的父節(jié)點，度優(yōu)先算法加入時延比DTD-H算法快0.02s，比NICE協(xié)議快0.05s，加入時延會優(yōu)先于其余三個算法.但是在節(jié)點數(shù)目逐漸增多時，NICE算法在由上至下每次尋找最近的成員會需要較多時間，而隨機算法在組播樹中隨機加入有剩余度的節(jié)點.當(dāng)節(jié)點數(shù)目為100時，DTD-H算法的平均加入時延為0.15s，明顯小于NICE協(xié)議的0.43s和隨機算法的0.42s，因此DTD-H算法的平均加入時延會優(yōu)于隨機算法與NICE算法；度優(yōu)先算法在所有節(jié)點中選出最大度的節(jié)點的過程，而DTD-H算法只在滿足穩(wěn)定狀態(tài)的節(jié)點集合中選擇父節(jié)點，DTD-H算法的平均加入時延小于度優(yōu)先算法0.02s，隨著節(jié)點個數(shù)越來越多，DTD-H算法在減少節(jié)點加入時延方面相對于度優(yōu)先算法的優(yōu)勢也越來越大.

圖7 平均加入延時與節(jié)點數(shù)目的關(guān)系圖Fig.7 Relation graph of average delay of the spanning tree and the number of nodes

圖8統(tǒng)計了當(dāng)節(jié)點數(shù)目為10～150時，節(jié)點加入到組播樹中所需要的最大時延.當(dāng)節(jié)點數(shù)目為10～20之間時，四種算法在最大加入時延方面均呈現(xiàn)遞增趨勢，隨機算法與NICE協(xié)議的最大加入時延分別分布在0.32s到0.4s之間以及0.41s到0.8s之間，度優(yōu)先算法在比較少的節(jié)點里可以快速找到有最大度的父節(jié)點，最大加入時延分布在0.16s到0.53s之間，而本文提出的DTD-H算法的最大加入時延分布在0.22s到0.40s之間，所以節(jié)點數(shù)目略小時，度優(yōu)先算法最大時延會優(yōu)先于其他三個算法.但節(jié)點數(shù)目逐漸增多時，NICE算法在由上至下每次尋找最近的成員時所需要的時間也越來越長，最大加入時延分布在0.8s到1.73s之間，所以NICE算法最大加入延時最大；隨機算法在所有具有度剩余的節(jié)點中隨機選出父節(jié)點，最大加入延時低于NICE算法，分布在0.45s到1.18s之間；度優(yōu)先算法會在眾多節(jié)點中選出最大度的節(jié)點，最大加入延時分布在0.53s到0.57s之間；DTD-H算法的最大加入時延分布在0.44s到0.52s之間.因此節(jié)點數(shù)目多于20個時，DTD-H算法的最大加入時延會略優(yōu)于度優(yōu)先算法，而明顯優(yōu)于NICE算法以及隨機算法.

圖8 最大加入延時與節(jié)點數(shù)目的關(guān)系圖Fig.8 Relation graph of max delay of the spanning tree and the number of nodes

圖9所示統(tǒng)計了100～1000個節(jié)點數(shù)目時，DTD-H算法與對比算法的平均鏈路伸展長度.隨著節(jié)點數(shù)目逐漸增多時，四種算法的平均鏈路伸展度均呈現(xiàn)遞增趨勢.NICE協(xié)議采用的分層分簇結(jié)構(gòu)，大部分節(jié)點位于分層結(jié)構(gòu)的最底層，組播樹中成員節(jié)點加入的過程由上至下尋找最近的節(jié)點，一旦某一層出現(xiàn)誤差將會影響下層節(jié)點簇的選擇，在實現(xiàn)數(shù)據(jù)轉(zhuǎn)發(fā)的過程中路徑長度越來越大；而度優(yōu)先的算法不考慮其他因素，只選擇最大度的節(jié)點加入；隨機算法任意加入組播樹中，將存在出度剩余的節(jié)點作為父節(jié)點；而本文的算法在考慮路徑長度的前提下選擇穩(wěn)定度因子最大的節(jié)點作為父節(jié)點加入.仿真數(shù)據(jù)顯示，DTD-H算法降低了平均鏈路伸展長度.

圖9 平均鏈路伸展長度與節(jié)點數(shù)目的關(guān)系圖Fig.9 Relation graph of average link stretch length and the number of nodes

6 結(jié)束語

針對應(yīng)用層組播的終端節(jié)點隨機任意退出的問題，本文主要研究了如何構(gòu)造高穩(wěn)定性的應(yīng)用層組播樹.本文的主要貢獻(xiàn)為提出了一種合理的問題模型-T-DTD模型，在應(yīng)用層組播樹生成過程中，該模型綜合考慮了終端節(jié)點的轉(zhuǎn)發(fā)能力與在線時長，以及節(jié)點所在組播樹中位置這三個因素，并且對主要影響因素進(jìn)行比重控制構(gòu)造高穩(wěn)定性、低延時應(yīng)用層組播樹.最后通過仿真實驗，對比了本文DTD-H算法與NICE協(xié)議和度優(yōu)先算法以及隨機算法在平均加入延時、最大加入延時以及平均鏈路伸展度這三個方面的性能，仿真結(jié)果表明本文提出的算法能夠有效地降低組播樹的時延以及鏈路伸展度.

本文對應(yīng)用層組播的構(gòu)建算法進(jìn)行了研究，但還存在諸多不足和有待繼續(xù)完善的地方，在未來的研究中，我們將繼續(xù)深入研究T-DTD模型中調(diào)整組播樹的算法，以更加精確有效的提高組播樹服務(wù)質(zhì)量.我們也將進(jìn)一步探索求解T-DTD問題模型的算法，以獲得更優(yōu)的解法.另外，從分布式和組成員動態(tài)管理的方面對本文提出的算法進(jìn)行改進(jìn)，使之能適應(yīng)成員節(jié)點規(guī)模較大的應(yīng)用層組播場景，這也是我們下一步研究方向.同時，由于本文中對利用DTD-H算法構(gòu)建的應(yīng)用層組播樹性能的驗證，是通過OMNet++仿真實驗實現(xiàn)的，還沒有考慮到實際網(wǎng)絡(luò)中的環(huán)境，所以下一步工作也會將本算法投入到實際應(yīng)用中，以驗證算法的優(yōu)越性.