陳瑞昭， 劉永廣

(廣東輕工職業(yè)技術(shù)學(xué)院管理工程系,廣東廣州 510300)

基于分簇結(jié)構(gòu)的P2P流媒體混合分發(fā)算法

陳瑞昭， 劉永廣

(廣東輕工職業(yè)技術(shù)學(xué)院管理工程系,廣東廣州 510300)

提出了一種基于分簇結(jié)構(gòu)的混合分發(fā)算法，算法采用分簇的方法將流媒體中的節(jié)點(diǎn)資源進(jìn)行簇劃分, 形成由簇頭、簇內(nèi)節(jié)點(diǎn)構(gòu)成的分簇網(wǎng)絡(luò)結(jié)構(gòu)，簇頭與簇內(nèi)節(jié)點(diǎn)通過(guò)拉拽算法來(lái)獲得數(shù)據(jù)，而簇頭間采用推送分發(fā)算法. 仿真結(jié)果表明, 該算法能提高數(shù)據(jù)塊復(fù)制速度，減少數(shù)據(jù)傳播時(shí)延，有效降低系統(tǒng)的控制開(kāi)銷，提高了播放連續(xù)度.

對(duì)等網(wǎng)絡(luò)； 流媒體； P2P覆蓋網(wǎng)； 簇； 推送算法

隨著網(wǎng)絡(luò)技術(shù)的發(fā)展，以高質(zhì)量、富媒體、互動(dòng)性為特征的流媒體應(yīng)用是互聯(lián)網(wǎng)業(yè)務(wù)的趨勢(shì). 在致力于提高端到端的流媒體傳輸性能的同時(shí)，業(yè)界的研究人員引入了P2P(Peer-to-Peer)網(wǎng)絡(luò)來(lái)解決大規(guī)模流媒體傳輸時(shí)服務(wù)器資源瓶頸的難題，對(duì)P2P中流媒體的分發(fā)算法進(jìn)行了較多的研究[1]，研究熱點(diǎn)集中在成員管理和樹(shù)狀拓?fù)涞臉?gòu)造算法上. P2P流媒體直播協(xié)議劃分為3類[2]：源驅(qū)動(dòng)，接收端驅(qū)動(dòng)和數(shù)據(jù)驅(qū)動(dòng). 源驅(qū)動(dòng)協(xié)議需要為新加入的節(jié)點(diǎn)指派父節(jié)點(diǎn)，數(shù)據(jù)從源節(jié)點(diǎn)開(kāi)始，以接力的方式向下層的節(jié)點(diǎn)推送. 接收端驅(qū)動(dòng)協(xié)議在接收者一側(cè)建立樹(shù)狀拓?fù)?，由接收端整合和管理?jié)點(diǎn)以獲取流數(shù)據(jù). 數(shù)據(jù)驅(qū)動(dòng)的協(xié)議一般與網(wǎng)狀拓?fù)涞母采w網(wǎng)結(jié)合，節(jié)點(diǎn)發(fā)現(xiàn)自己需要的數(shù)據(jù)并從鄰居節(jié)點(diǎn)獲取這些數(shù)據(jù).

PEERCAST[3]和COOLSTREAMING[4]是P2P流媒體直播領(lǐng)域代表性的原型系統(tǒng)，PeerCast使用了樹(shù)狀的拓?fù)洌梢詽M足低流量的流媒體應(yīng)用，而在高流量的流媒體應(yīng)用方面其表現(xiàn)不能令人滿意，當(dāng)并發(fā)數(shù)目在數(shù)百的數(shù)量級(jí)時(shí)，節(jié)點(diǎn)的異構(gòu)性引發(fā)拓?fù)鋭?dòng)蕩現(xiàn)象十分嚴(yán)重，高層節(jié)點(diǎn)的離開(kāi)和崩潰導(dǎo)致嚴(yán)重的回放斷續(xù). CoolStreming構(gòu)造了一個(gè)網(wǎng)狀的網(wǎng)絡(luò)，對(duì)網(wǎng)絡(luò)動(dòng)態(tài)變化具有更好的魯棒性，更適合于P2P流媒體直播. CoolStreaming中的節(jié)點(diǎn)采用了主動(dòng)發(fā)送拉拽數(shù)據(jù)請(qǐng)求來(lái)獲得數(shù)據(jù)的拉拽算法[5]，由于重復(fù)的數(shù)據(jù)塊傳輸浪費(fèi)帶寬，使得本來(lái)稀缺的上傳帶寬資源更稀缺，節(jié)點(diǎn)扮演下載服務(wù)的角色，拉拽算法無(wú)法利用處于不能映射的內(nèi)外節(jié)點(diǎn)上傳帶寬，隨著網(wǎng)絡(luò)規(guī)模的增大，拉拽算法引入越來(lái)越多的傳輸時(shí)延[6]. 文獻(xiàn)[7]提出了節(jié)點(diǎn)主動(dòng)發(fā)送推送數(shù)據(jù)請(qǐng)求來(lái)獲得數(shù)據(jù)的推送算法(Push-to-Pull Algorithm,PTPA)，但在實(shí)際運(yùn)行中還是存在數(shù)據(jù)復(fù)制速度不足、回放時(shí)延較大的問(wèn)題. 針對(duì)以上問(wèn)題，提出了一種混合式分發(fā)數(shù)據(jù)的方法，該方法通過(guò)對(duì)流媒體中的節(jié)點(diǎn)資源進(jìn)行分簇處理，由性能較高(處理、存儲(chǔ)、帶寬等方面性能)的節(jié)點(diǎn)擔(dān)任簇頭，在簇頭間采用推送算法，而簇頭與簇內(nèi)節(jié)點(diǎn)采用拉拽算法來(lái)獲得數(shù)據(jù)，獲得較好的性能.

1 算法描述

基于分簇結(jié)構(gòu)的混合分發(fā)算法(A Hybrid Scheduling Algorithm for P2P Stream Based on Clustering，HSAC)采用P2P網(wǎng)絡(luò)，它是一個(gè)自組織的層次式結(jié)構(gòu)網(wǎng)絡(luò)，由一個(gè)索引數(shù)據(jù)服務(wù)器負(fù)責(zé)簇頭節(jié)點(diǎn)的管理，記錄共享信息，響應(yīng)信息的查詢. 網(wǎng)絡(luò)中的節(jié)點(diǎn)向索引數(shù)據(jù)服務(wù)器提供自己的共享信息，并負(fù)責(zé)分發(fā)共享文件的通信，也會(huì)根據(jù)需要下載自己所需要的其他節(jié)點(diǎn)上的信息. 簇頭之間構(gòu)成一個(gè)高速轉(zhuǎn)發(fā)層，采取主動(dòng)發(fā)送數(shù)據(jù)的推送算法，簇頭負(fù)責(zé)簇的管理和簇之間信息的交互，然后分別把附近性能較差的節(jié)點(diǎn)聚集成簇， 簇內(nèi)節(jié)點(diǎn)與簇頭節(jié)點(diǎn)之間采用請(qǐng)求數(shù)據(jù)的拉拽算法，形成HSAC的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖，如圖1所示.

圖1 HSAC網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖Fig.1 Topology of HSAC network

1.1基于分簇結(jié)構(gòu)的覆蓋網(wǎng)絡(luò)構(gòu)建方法

本算法是一個(gè)動(dòng)態(tài)、分布執(zhí)行的算法，節(jié)點(diǎn)首先將消息發(fā)送給周圍的一組節(jié)點(diǎn)，周圍節(jié)點(diǎn)在接收到消息后根據(jù)需要對(duì)消息進(jìn)行轉(zhuǎn)發(fā). 這樣，消息就可以通過(guò)節(jié)點(diǎn)之間接力的方式進(jìn)行傳遞. 每個(gè)節(jié)點(diǎn)用一個(gè)二元組(IP，id)來(lái)標(biāo)識(shí)，IP表示該節(jié)點(diǎn)的編號(hào)，id為節(jié)點(diǎn)的標(biāo)識(shí)值，對(duì)簇頭的集合C的所有節(jié)點(diǎn)標(biāo)識(shí)值id為1，其余簇成員節(jié)點(diǎn)集合標(biāo)識(shí)為0. 節(jié)點(diǎn)緩沖中的各個(gè)分段的可用性信息被表示為一個(gè)緩沖映射，稱為緩沖映射信息(Buffer_Map，BM)，每個(gè)節(jié)點(diǎn)會(huì)和它的鄰居節(jié)點(diǎn)不斷交換各自的BM，收到的節(jié)點(diǎn)可能會(huì)轉(zhuǎn)發(fā)該節(jié)點(diǎn)的消息. 算法通過(guò)BM信息建立和維持與相鄰節(jié)點(diǎn)的鏈路，并承載一些控制信息，算法同時(shí)設(shè)置另外4個(gè)控制消息. 節(jié)點(diǎn)Vi用CH(Vi)宣布自己為簇頭節(jié)點(diǎn)，用JOIN(Vj,Vi)請(qǐng)求加入以Vj為簇頭的簇，成為其成員節(jié)點(diǎn). 若Vj為簇頭節(jié)點(diǎn)，則用ACCEPT(Vi,Vj)消息接受節(jié)點(diǎn)Vi的加入請(qǐng)求，或者用REJECT(Vi,Vj)消息拒絕節(jié)點(diǎn)Vi的加入請(qǐng)求. 網(wǎng)絡(luò)拓?fù)鋱D中的每一節(jié)點(diǎn)中，存在一張拓?fù)浣Y(jié)構(gòu)表，用來(lái)記錄與節(jié)點(diǎn)相關(guān)的拓?fù)浣Y(jié)構(gòu). 通過(guò)讓每個(gè)節(jié)點(diǎn)定期向相鄰節(jié)點(diǎn)發(fā)送和接收BM消息，以獲取相鄰節(jié)點(diǎn)的信息，不斷更新自身的相鄰節(jié)點(diǎn)集NList，以適應(yīng)節(jié)點(diǎn)的動(dòng)態(tài)性. 如果節(jié)點(diǎn)離開(kāi)，它就會(huì)向鄰居節(jié)點(diǎn)發(fā)出“離開(kāi)”信息，收到信息的節(jié)點(diǎn)應(yīng)會(huì)在其相鄰節(jié)點(diǎn)集刪去此節(jié)點(diǎn). 因此，通過(guò)定期監(jiān)測(cè)鄰居信息，獲得鄰居的相關(guān)信息，也就能找到自己所需要的數(shù)據(jù).

1.1.2 節(jié)點(diǎn)的退出及更換簇頭節(jié)點(diǎn) 在簇的初始化完成以后，隨著節(jié)點(diǎn)的頻繁變動(dòng)，網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)會(huì)發(fā)生變化，節(jié)點(diǎn)的退出包括簇內(nèi)節(jié)點(diǎn)的退出與簇頭節(jié)點(diǎn)的退出，在HSAC系統(tǒng)中的節(jié)點(diǎn)通過(guò)周期性地與鄰居節(jié)點(diǎn)發(fā)送在線消息以保持聯(lián)系.

(1)簇內(nèi)節(jié)點(diǎn)的退出.如果簇內(nèi)節(jié)點(diǎn)由于節(jié)點(diǎn)失效而被動(dòng)離開(kāi)時(shí)，簇頭節(jié)點(diǎn)不會(huì)收到該節(jié)點(diǎn)發(fā)來(lái)的在線消息，那么幾個(gè)在線周期后簇頭節(jié)點(diǎn)將把該節(jié)點(diǎn)的狀態(tài)視為離開(kāi)，并將其從成員列表中刪除，其它非簇頭鄰居節(jié)點(diǎn)更新自己的鄰居表.

(2)簇頭節(jié)點(diǎn)的退出.若節(jié)點(diǎn)Vi是簇頭節(jié)點(diǎn)Vk的成員節(jié)點(diǎn)，當(dāng)Vk脫離網(wǎng)絡(luò)，則Vk發(fā)出JOIN(-1,Vi)消息. 因?yàn)闊o(wú)ID為-1的節(jié)點(diǎn)，節(jié)點(diǎn)Vk以此消息辭去簇頭角色，重新執(zhí)行初始化過(guò)程.

(3)更換簇頭節(jié)點(diǎn).由于P2P網(wǎng)絡(luò)的動(dòng)態(tài)性，簇頭節(jié)點(diǎn)在任何時(shí)候都有可能更換. 若Vj是簇頭節(jié)點(diǎn)而Vi是以Vk為簇頭的成員節(jié)點(diǎn)，則Vi將比較Vj與Vk的負(fù)載情況. 若節(jié)點(diǎn)Vk的負(fù)載小于節(jié)點(diǎn)Vj的負(fù)載，則Vi還是以Vk作為自己的簇頭節(jié)點(diǎn)，只是刷新自己的鄰居表. 若節(jié)點(diǎn)Vk的負(fù)載大于節(jié)點(diǎn)Vj的負(fù)載，則Vi脫離原簇，發(fā)出JOIN(Vj,Vi)消息請(qǐng)求成為Vj的成員節(jié)點(diǎn). 而Vk節(jié)點(diǎn)收到JOIN(Vj,Vi)消息后將Vi從成員表中刪除.

1.2數(shù)據(jù)傳送算法

數(shù)據(jù)傳送是指如何在所構(gòu)建的應(yīng)用層覆蓋網(wǎng)絡(luò)上傳輸實(shí)時(shí)流媒體數(shù)據(jù). P2P中每個(gè)節(jié)點(diǎn)和其鄰居周期性地交換數(shù)據(jù)可用性信息，通過(guò)分析數(shù)據(jù)可用性信息有選擇地從其鄰居獲取數(shù)據(jù)，節(jié)點(diǎn)Buffer_Map變化或者鄰居Buffer_Map的變化都會(huì)觸發(fā)數(shù)據(jù)傳送，接收到完整的數(shù)據(jù)塊、添加新鄰居、鄰居Buffer_Map更新都會(huì)導(dǎo)致Buffer_Map的變化.

1.2.1 推送算法 簇頭之間采取簇頭節(jié)點(diǎn)主動(dòng)發(fā)送推送數(shù)據(jù)的請(qǐng)求，向它的伙伴節(jié)點(diǎn)發(fā)送自己的緩存信息，擁有數(shù)據(jù)塊的簇頭節(jié)點(diǎn)主動(dòng)連接有較多子節(jié)點(diǎn)的伙伴節(jié)點(diǎn)之后就成為上傳服務(wù)器，如算法1所示.

算法1推送算法

for each packet j

計(jì)算每個(gè)數(shù)據(jù)塊的時(shí)間戳time-stamp[j];

for each packet j

n←時(shí)間戳最大的數(shù)據(jù)塊個(gè)數(shù);

if n=1

推送該數(shù)據(jù)塊;

else

在時(shí)間戳相同的數(shù)據(jù)塊中找發(fā)送次數(shù)最小的數(shù)據(jù)塊p;

推送該數(shù)據(jù)塊p;

end if

end for

end for

for 每個(gè)連接的簇頭節(jié)點(diǎn)

通過(guò)輪盤賭算法，找子節(jié)點(diǎn)層數(shù)越多的簇頭節(jié)點(diǎn)作為目標(biāo)節(jié)點(diǎn);

向選擇的目標(biāo)節(jié)點(diǎn)發(fā)起請(qǐng)求;

end for

if 推送該數(shù)據(jù)塊的請(qǐng)求時(shí)間遲于該數(shù)據(jù)塊的播放時(shí)間

then

拒絕接收;

else if 本節(jié)點(diǎn)正在從別的伙伴處接收該數(shù)據(jù)塊

then

拒絕接收;

else if 本節(jié)點(diǎn)的緩存中已經(jīng)擁有該數(shù)據(jù)塊

then

拒絕接收;

else

接收該數(shù)據(jù)塊;

end if

1.2.2 拉拽算法 簇頭與簇內(nèi)節(jié)點(diǎn)、簇內(nèi)節(jié)點(diǎn)間主動(dòng)發(fā)送拉拽數(shù)據(jù)請(qǐng)求來(lái)獲得數(shù)據(jù)，這種模式與DONet(Data-driven Overlay network)[4]中的純拉策略相同，數(shù)據(jù)提供者首選有足夠帶寬而且所擁有的數(shù)據(jù)塊有充分處理時(shí)間的節(jié)點(diǎn)，如算法2所示.

算法2拉拽算法

if 潛在數(shù)據(jù)提供者個(gè)數(shù)=1

該節(jié)點(diǎn)為數(shù)據(jù)提供者;

else

把有足夠帶寬而且所擁有的數(shù)據(jù)塊有充分處理時(shí)間的節(jié)點(diǎn)作為數(shù)據(jù)提供者;

end if

if 拉拽該數(shù)據(jù)塊的請(qǐng)求時(shí)間遲于該數(shù)據(jù)塊的播放時(shí)間then

拒絕接收;

else if 本節(jié)點(diǎn)正在從別的伙伴處接收該數(shù)據(jù)塊

then

拒絕接收;

else if 本節(jié)點(diǎn)的緩存中已經(jīng)擁有該數(shù)據(jù)塊

then

拒絕接收;

else

接收該數(shù)據(jù)塊;

end if

Do更新緩沖映射信息Buffer Map

2 實(shí)驗(yàn)仿真與分析

為了驗(yàn)證HSAC的性能，使用了GT-ITM網(wǎng)絡(luò)拓?fù)渖善鱗8]及NS-2 網(wǎng)絡(luò)仿真器對(duì)HSAC進(jìn)行測(cè)試. 仿真參數(shù)為：視頻長(zhǎng)度為120 min(電影的標(biāo)準(zhǔn)長(zhǎng)度)，視頻流碼流為390 Kbps， 數(shù)據(jù)塊劃分時(shí)間間隔為1 s，緩沖時(shí)間為60 s，節(jié)點(diǎn)的鄰居節(jié)點(diǎn)數(shù)量限制為5個(gè)，參與網(wǎng)絡(luò)的節(jié)點(diǎn)個(gè)數(shù)1 000，接入平均上傳帶寬為500 Kbps，其中20%的節(jié)點(diǎn)上傳帶寬為1 000 Kbps，40%的節(jié)點(diǎn)上傳帶寬為500 Kbps，40%的節(jié)點(diǎn)上傳帶寬為250 Kbps，上傳帶寬約為流碼率的1.3倍.

仿真主要測(cè)試了數(shù)據(jù)塊復(fù)制速度、播放緩沖延遲、控制開(kāi)銷等3個(gè)指標(biāo)，并與DONet算法和文獻(xiàn)[7]中的PTPA算法進(jìn)行比較, 其中，DONet算法采用數(shù)據(jù)驅(qū)動(dòng)方式,流媒體數(shù)據(jù)的傳輸是基于接收節(jié)點(diǎn)的主動(dòng)請(qǐng)求的拉拽算法,也就是純拉策略，而PTPA算法則采用每個(gè)節(jié)點(diǎn)都主動(dòng)盡力將自己擁有的數(shù)據(jù)傳輸給它的鄰居節(jié)點(diǎn)的推送策略.

2.1數(shù)據(jù)塊復(fù)制速度

數(shù)據(jù)塊復(fù)制速度是數(shù)據(jù)塊從產(chǎn)生至分發(fā)到節(jié)點(diǎn)的時(shí)間關(guān)系，影響P2P直播系統(tǒng)源端到接收端的回放延時(shí). 如圖2所示，由于HSAC算法采用分簇的覆蓋網(wǎng)絡(luò)構(gòu)建方法及數(shù)據(jù)傳輸推拉結(jié)合策略，把處理、存儲(chǔ)、帶寬等方面性能較佳節(jié)點(diǎn)作為簇頭節(jié)點(diǎn)，更能發(fā)掘快速傳輸數(shù)據(jù)的潛力，覆蓋所有節(jié)點(diǎn)的時(shí)間為14 s，采用推送策略的PTPA算法覆蓋所有節(jié)點(diǎn)的時(shí)間為20 s,而DONet的純拉策略由于需要多次交互才能找到合適的下載節(jié)點(diǎn)，不能有效地發(fā)掘節(jié)點(diǎn)的上傳帶寬，覆蓋所有節(jié)點(diǎn)的時(shí)間需要60 s. HSAC中的節(jié)點(diǎn)根據(jù)自己的BM信息和鄰居的BM信息來(lái)調(diào)度數(shù)據(jù)塊的復(fù)制傳輸，簇頭節(jié)點(diǎn)在收到數(shù)據(jù)塊時(shí)進(jìn)行數(shù)據(jù)調(diào)度，節(jié)省了數(shù)據(jù)調(diào)度的延遲，并且可以最大限度利用節(jié)點(diǎn)的上傳帶寬. PTPA算法雖然能主動(dòng)傳輸數(shù)據(jù)，但由于沒(méi)有充分發(fā)揮性能較佳的節(jié)點(diǎn)性能，使得數(shù)據(jù)傳輸速度略遲于HSAC，而DONet算法在BM信息更新時(shí)才能觸發(fā)新一輪的數(shù)據(jù)調(diào)度，BM信息廣播的頻率會(huì)影響數(shù)據(jù)塊復(fù)制的速度，不能有效利用節(jié)點(diǎn)的上傳帶寬. 在相同BM信息廣播頻率的情況下，DONet算法表現(xiàn)不如HSAC及PTPA算法.

圖2 不同算法下數(shù)據(jù)塊的復(fù)制速度

2.2播放緩沖延遲

播放緩沖延遲是節(jié)點(diǎn)從加入網(wǎng)絡(luò)至回放開(kāi)始的延遲時(shí)間. 仿真中節(jié)點(diǎn)緩沖時(shí)間為60 s，緩沖比97%時(shí)節(jié)點(diǎn)開(kāi)始回放流媒體數(shù)據(jù)，如圖3所示，HSAC均優(yōu)于PTPA算法及DONet算法. 在節(jié)點(diǎn)數(shù)量較少時(shí)(節(jié)點(diǎn)數(shù)目少于300)，新加入的節(jié)點(diǎn)需要更多的時(shí)間來(lái)緩沖數(shù)據(jù)，隨著網(wǎng)絡(luò)規(guī)模的增大，緩沖時(shí)間減少，HSAC比PTPA算法需要的緩沖時(shí)間大約少10 s，比DONet算法需要的緩沖時(shí)間大約少40 s. 而在節(jié)點(diǎn)數(shù)量較大的情況下(節(jié)點(diǎn)數(shù)目大于400)，節(jié)點(diǎn)緩沖的時(shí)間并不會(huì)隨著網(wǎng)絡(luò)規(guī)模的增大而減少. 這是因?yàn)槊總€(gè)節(jié)點(diǎn)的伙伴個(gè)數(shù)是有限的，擁有剩余帶寬的節(jié)點(diǎn)并不都能發(fā)現(xiàn)新加入的節(jié)點(diǎn). 緩沖時(shí)間與節(jié)點(diǎn)的上傳帶寬相關(guān)，在節(jié)點(diǎn)的平均上傳帶寬僅為碼率的1.3 倍時(shí)，HSAC的緩沖時(shí)間大概為40 s，PTPA算法的緩沖時(shí)間為50 s，而DONet算法需要多出大概20 s的緩沖時(shí)間.

圖3 不同算法下的回放緩沖延遲Fig.3 Buffer-to-play delay of different algorithms

2.3控制開(kāi)銷

控制開(kāi)銷(overhead)是衡量算法效率的一個(gè)重要指標(biāo)，在流媒體分發(fā)系統(tǒng)，大量的開(kāi)銷用于數(shù)據(jù)塊的傳輸和交換，它是指節(jié)點(diǎn)的控制流量和視頻流量的比率，通信開(kāi)銷的大小是系統(tǒng)可擴(kuò)展性的重要表現(xiàn)，取每個(gè)節(jié)點(diǎn)上控制開(kāi)銷的平均值. 在實(shí)驗(yàn)開(kāi)始階段，各個(gè)節(jié)點(diǎn)加入有一個(gè)大約為 1 min的初始化時(shí)間，自加入開(kāi)始每個(gè)節(jié)點(diǎn)在線時(shí)長(zhǎng)都至少為120 min，默認(rèn)的流率為500 kbps. 圖4給出了不同節(jié)點(diǎn)數(shù)下，HSAC和PTPA算法及DONet算法在鄰居節(jié)點(diǎn)數(shù)n=3和n=5的控制開(kāi)銷，可以看出3種算法的控制開(kāi)銷不隨著網(wǎng)絡(luò)規(guī)模的增大而增大，這說(shuō)明它們都具有很好的可擴(kuò)展性，HSAC由于利用簇頭節(jié)點(diǎn)的性能，數(shù)據(jù)傳輸算法又減少了節(jié)點(diǎn)之間BM和請(qǐng)求的交換，其控制開(kāi)銷明顯低于DONet算法，而PTPA算法跟HSAC一樣，由于減少了交換的開(kāi)銷，控制開(kāi)銷僅次于HSAC.

圖4 不同算法下的控制開(kāi)銷

3 結(jié)論

提出的HSAC采用分簇的方法將流媒體中的節(jié)點(diǎn)資源進(jìn)行簇劃分，簇頭與簇內(nèi)節(jié)點(diǎn)通過(guò)拉拽算法來(lái)獲得數(shù)據(jù)，充分發(fā)揮了高能力節(jié)點(diǎn)的性能優(yōu)勢(shì)，而簇頭間采用推送分發(fā)算法，能減少數(shù)據(jù)傳播時(shí)延，提高了流媒體的傳輸質(zhì)量，適合大規(guī)模的流媒體服務(wù)的應(yīng)用. 但HSAC也面臨著過(guò)分依賴超級(jí)簇頭節(jié)點(diǎn)等問(wèn)題，是HSAC今后研究改進(jìn)的重點(diǎn).

[1] DESHPANDE H,BAWA M, GARCIA-MONINA H.Streaming live media over a peer-to-peer network[C]∥Technical Report CS-2001-31, Stanford, CA, USA: CS Dept, Stanford University, 2001.

[2] SILVERSTON T, FOURMAUX O. Source vs data-driven approach for Live P2P streaming networking[C]∥International Conference on Systems and International Conference on Mobile Communications and Learning Technologies. Mauritius: IEEE, 2006:99.

[3] BAWA M, DESHPANDE H, GARCIA-MONINA H. Transience of peers amp; streaming media[J]. ACM SIGCOMM Comput Commun Rev, 2003,33(1):107-112.

[4] ZHANG X, LIU J, LI B, et al. Coolstreaming/donet: A data-driven overlay network for peer-to-peer live media streaming[C]∥24th Annual Joint Conference of the IEEE Computer and Communications Societies. Miami, FL, USA: IEEE, 2005:2102-2111.

[5] LI B, XIE S, KEUNG G Y, et al. An empirical study of the coolstreaming system[J]. IEEE Journal on Selected Areas in Communications, 2007, 12(25):1627-1639.

[6] 鄭凱．一種P2P VOD系統(tǒng)的緩存部署及調(diào)度機(jī)制[J]．華南師范大學(xué)學(xué)報(bào):自然科學(xué)版，2009(2):34-37．

ZHENG Kai. A mechanism of cache deploymenting and scheduling of P2P VOD system[J]. Journal of South China Normal University: Natural Science Edition, 2009(2):34-37．

[7] 周衛(wèi),葉梧.推送模式的P2P流媒體分發(fā)算法[J]. 科學(xué)技術(shù)與工程,2008,8(4):946-952.

ZHOU Wei,YE Wu.Push Based Scheduling for P2P Streaming[J].Science Technology and Engineering, 2008,8(4):946-952.

[8] CALVERT K，DOAR M,ZEGURA E.Modeling internet topology [J]．IEEE Communications Magazine,1997(6):160-163．

Keywords： peer-to-peer;stream media; P2P overlay network; clustering; push algorithm

【責(zé)任編輯 莊曉瓊】

AHYBRIDSCHEDULINGALGORITHMFORP2PSTREAMBASEDONCLUSTERING

CHEN Ruizhao, LIU Yongguang)

(Department of Management, Guangdong Industry Technical College, Guangzhou 510300, China)

A hybrid scheduling algorithm based on clustering is presented. In the algorithm, node resources are divided into cluster head and cluster nodes by clustering method and form a clustering network structure. For the network, data is obtained by push algorithm between cluster heads and heads, while pull algorithm between cluster heads and inter-cluster nodes. Simulations show that the algorithm can increase the speed of data block duplication, reduce the data propagation delay and the control overhead of streaming system efficiently, and improve the degree of continuous playback.

2009-09-14

廣東省計(jì)算機(jī)網(wǎng)絡(luò)重點(diǎn)實(shí)驗(yàn)室開(kāi)放基金資助項(xiàng)目(cn200407)；廣東輕工職業(yè)技術(shù)學(xué)院自然科學(xué)基金資助項(xiàng)目(KX010405)

陳瑞昭(1970—)，男，廣東潮州人，廣東輕工職業(yè)技術(shù)學(xué)院講師，主要研究方向：信息網(wǎng)絡(luò)理論與技術(shù)，Email:chen_rz@163.com.

1000-5463(2010)01-0037-05

TP393

A