異構(gòu)環(huán)境下的P2P流媒體節(jié)點(diǎn)選擇算法

唐朝偉，肖俊，王恒，胡佩，劉倩男，宋俊平，李曉輝

?

異構(gòu)環(huán)境下的P2P流媒體節(jié)點(diǎn)選擇算法

唐朝偉1，肖俊1，王恒1，胡佩1，劉倩男1，宋俊平2，李曉輝3

(1. 重慶大學(xué)通信工程學(xué)院，重慶，400044；2. 中國(guó)科學(xué)院軟件研究所天基綜合信息系統(tǒng)技術(shù)重點(diǎn)實(shí)驗(yàn)室，北京，100190；3. 中國(guó)人民解放軍94270部隊(duì)，山東濟(jì)南，250117)

針對(duì)異構(gòu)環(huán)境的復(fù)雜性和不穩(wěn)定性，提出一種異構(gòu)環(huán)境下的點(diǎn)對(duì)點(diǎn)(P2P)流媒體節(jié)點(diǎn)選擇算法。利用模糊認(rèn)知圖理論研究異構(gòu)環(huán)境下影響節(jié)點(diǎn)性能的多方面因素之間的關(guān)系，計(jì)算節(jié)點(diǎn)的綜合服務(wù)能力，并選擇服務(wù)能力強(qiáng)的節(jié)點(diǎn)作為鄰居節(jié)點(diǎn)；為保證鄰居節(jié)點(diǎn)具有較強(qiáng)的實(shí)時(shí)服務(wù)能力，利用馬爾科夫蒙特卡洛方法進(jìn)行隨機(jī)行走，周期性地更新鄰居節(jié)點(diǎn)列表，采用Metropolis-Hastings算法計(jì)算轉(zhuǎn)移矩陣以滿(mǎn)足隨機(jī)行走的期望靜止概率分布。研究結(jié)果表明：該算法能在選擇優(yōu)質(zhì)鄰居節(jié)點(diǎn)，提高視頻服務(wù)質(zhì)量的同時(shí)，保證節(jié)點(diǎn)的負(fù)載均衡，降低系統(tǒng)消耗，顯著提高了系統(tǒng)性能。

異構(gòu)環(huán)境；P2P流媒體；節(jié)點(diǎn)選擇；綜合服務(wù)能力；隨機(jī)行走

節(jié)點(diǎn)選擇算法是P2P流媒體系統(tǒng)中的關(guān)鍵技術(shù)之一，它為每個(gè)節(jié)點(diǎn)選擇適合的鄰居節(jié)點(diǎn)提供數(shù)據(jù)上傳，保證用戶(hù)能夠高效、及時(shí)的下載數(shù)據(jù)。不同的節(jié)點(diǎn)選擇策略既會(huì)影響系統(tǒng)的整體服務(wù)性能，又會(huì)影響單個(gè)用戶(hù)的視頻體驗(yàn)。近年來(lái)，隨著P2P流媒體技術(shù)的推廣和網(wǎng)絡(luò)用戶(hù)數(shù)目的增多，針對(duì)P2P流媒體節(jié)點(diǎn)選擇算法的研究越來(lái)越重要。伴隨著網(wǎng)絡(luò)接入和終端類(lèi)型的多樣化，如何在異構(gòu)環(huán)境下進(jìn)行節(jié)點(diǎn)選擇，實(shí)現(xiàn)高效的數(shù)據(jù)傳輸是P2P流媒體系統(tǒng)面臨的重要挑戰(zhàn)之一[1]。一般來(lái)講，異構(gòu)環(huán)境的“異構(gòu)”主要包含終端異構(gòu)和接入方式異構(gòu)。其中終端異構(gòu)，也稱(chēng)為節(jié)點(diǎn)異構(gòu)，指多種終端(例如智能手機(jī)、iPad、筆記本、臺(tái)式機(jī)以及高清電視等)在網(wǎng)絡(luò)中共存。而接入方式異構(gòu)即以太網(wǎng)、WLAN和3G網(wǎng)絡(luò)等多種網(wǎng)絡(luò)共存。以上2個(gè)方面異構(gòu)導(dǎo)致節(jié)點(diǎn)的帶寬、鏈路狀態(tài)、電量、處理能力、逗留時(shí)間等不同，因此異構(gòu)節(jié)點(diǎn)能為鄰居節(jié)點(diǎn)提供上傳的能力也不相同。在設(shè)計(jì)異構(gòu)環(huán)境下的節(jié)點(diǎn)選擇算法時(shí)，需要解決3個(gè)方面的問(wèn)題：首先是節(jié)點(diǎn)服務(wù)能力的度量，即如何根據(jù)多種因素確定節(jié)點(diǎn)的綜合服務(wù)能力；其次是負(fù)載均衡問(wèn)題，即如何讓服務(wù)能力強(qiáng)的節(jié)點(diǎn)為更多鄰居節(jié)點(diǎn)提供服務(wù)，而服務(wù)能力弱的節(jié)點(diǎn)則為較少鄰居節(jié)點(diǎn)提供上傳；最后是動(dòng)態(tài)適應(yīng)性，即如何根據(jù)節(jié)點(diǎn)的加入、退出和服務(wù)能力的實(shí)時(shí)變化動(dòng)態(tài)更新節(jié)點(diǎn)列表。然而目前的節(jié)點(diǎn)選擇算法均不能同時(shí)滿(mǎn)足以上3個(gè)方面要求。Zhang等[2]提出一種小區(qū)優(yōu)先的節(jié)點(diǎn)選擇算法，它考慮了影響節(jié)點(diǎn)服務(wù)能力的多方面因素，但該算法針對(duì)于3G網(wǎng)絡(luò)模型；馮偵探等[3]提出的自適應(yīng)鄰居節(jié)點(diǎn)選擇算法動(dòng)態(tài)描述節(jié)點(diǎn)的服務(wù)能力，顯著提高了系統(tǒng)的服務(wù)性能，但是在服務(wù)能力方面僅以節(jié)點(diǎn)的上行帶寬作為指標(biāo)；Mushtaq等[4?5]基于可分級(jí)視頻編碼(SVC)[6]的P2P系統(tǒng)進(jìn)行了節(jié)點(diǎn)選擇研究，文獻(xiàn)[5]考慮SVC對(duì)視頻分層后的影響，選擇往返時(shí)延(RTT)最小的節(jié)點(diǎn)下載重要性最高的基礎(chǔ)層；Shen等[7]提出的基于節(jié)點(diǎn)間信任關(guān)系的P2P網(wǎng)絡(luò)，沒(méi)有考慮節(jié)點(diǎn)的服務(wù)能力。針對(duì)上述問(wèn)題，本文作者提出一種異構(gòu)環(huán)境下的節(jié)點(diǎn)選擇算法(PSAH)，該算法研究異構(gòu)環(huán)境下影響節(jié)點(diǎn)服務(wù)能力的各個(gè)因素之間的復(fù)雜關(guān)系，既考慮環(huán)境的異構(gòu)性又滿(mǎn)足系統(tǒng)的高服務(wù)質(zhì)量(QoS)需求；同時(shí)算法避免復(fù)雜的計(jì)算，每個(gè)節(jié)點(diǎn)只需維護(hù)其鄰居節(jié)點(diǎn)信息就能選擇整個(gè)網(wǎng)絡(luò)中實(shí)時(shí)服務(wù)能力較高的節(jié)點(diǎn)，并根據(jù)實(shí)時(shí)服務(wù)能力的變化來(lái)更新鄰居節(jié)點(diǎn)列表，這樣在保證節(jié)點(diǎn)負(fù)載均衡的同時(shí)考慮系統(tǒng)的動(dòng)態(tài)性。仿真結(jié)果表明，該算法能提高系統(tǒng)QoS，降低傳輸時(shí)延，提供系統(tǒng)的服務(wù)性能。

1 系統(tǒng)模型和工作原理

在異構(gòu)網(wǎng)絡(luò)環(huán)境中，Mesh型[8]P2P流媒體系統(tǒng)具有易維護(hù)、網(wǎng)絡(luò)健壯性強(qiáng)、資源利用率高等特點(diǎn)，得到了廣泛的關(guān)注。異構(gòu)網(wǎng)絡(luò)環(huán)境下的Mesh系統(tǒng)主要由內(nèi)容服務(wù)器、Tracker服務(wù)器和Peer客戶(hù)端(固定節(jié)點(diǎn)和移動(dòng)節(jié)點(diǎn))組成。其中，內(nèi)容服務(wù)器存儲(chǔ)并提供原始數(shù)據(jù)；Tracker服務(wù)器負(fù)責(zé)節(jié)點(diǎn)信息的獲取和維護(hù)，以及初始鄰居節(jié)點(diǎn)列表下發(fā)；網(wǎng)絡(luò)中的固定節(jié)點(diǎn)(臺(tái)式機(jī)等)和移動(dòng)節(jié)點(diǎn)(智能終端，筆記本等)既可以是資源提供者，又可以是資源請(qǐng)求者。

異構(gòu)網(wǎng)絡(luò)環(huán)境下的數(shù)據(jù)傳輸原理示意圖如圖1所示。由圖1可見(jiàn)：當(dāng)節(jié)點(diǎn)加入系統(tǒng)時(shí)，節(jié)點(diǎn)將自身的節(jié)點(diǎn)信息(例如上行帶寬、時(shí)延、電量)上報(bào)給Tracker服務(wù)器；Tracker服務(wù)器獲取并存儲(chǔ)網(wǎng)絡(luò)中所有節(jié)點(diǎn)的節(jié)點(diǎn)信息，同時(shí)，根據(jù)獲取的節(jié)點(diǎn)信息計(jì)算各節(jié)點(diǎn)性能；當(dāng)系統(tǒng)網(wǎng)絡(luò)中的某一節(jié)點(diǎn)請(qǐng)求資源時(shí)，即出現(xiàn)請(qǐng)求節(jié)點(diǎn)，Tracker服務(wù)器搜索具備該請(qǐng)求資源內(nèi)容的節(jié)點(diǎn)，即資源節(jié)點(diǎn)，Tracker選擇部分資源節(jié)點(diǎn)并根據(jù)節(jié)點(diǎn)性能強(qiáng)弱進(jìn)行排序，形成鄰居節(jié)點(diǎn)列表下發(fā)給請(qǐng)求節(jié)點(diǎn)，對(duì)請(qǐng)求節(jié)點(diǎn)進(jìn)行資源傳輸；在資源傳輸過(guò)程中，由于節(jié)點(diǎn)的動(dòng)態(tài)變化會(huì)導(dǎo)致網(wǎng)絡(luò)性能、甚至是網(wǎng)絡(luò)構(gòu)成的改變，因此，節(jié)點(diǎn)通過(guò)實(shí)時(shí)更新鄰居節(jié)點(diǎn)列表，從而提高系統(tǒng)的服務(wù)質(zhì)量，降低資源的傳輸時(shí)延。

圖1 異構(gòu)網(wǎng)絡(luò)下的數(shù)據(jù)傳輸原理圖

2 節(jié)點(diǎn)選擇算法

基于前面對(duì)異構(gòu)網(wǎng)絡(luò)環(huán)境中Mesh型P2P流媒體系統(tǒng)工作原理的分析發(fā)現(xiàn)：鄰居節(jié)點(diǎn)列表是保障系統(tǒng)服務(wù)質(zhì)量、網(wǎng)絡(luò)系統(tǒng)運(yùn)行穩(wěn)定的關(guān)鍵。而本文的節(jié)點(diǎn)選擇算法發(fā)生在Tracker服務(wù)器和Peer客戶(hù)端2個(gè)部分，其中Tracker端向用戶(hù)節(jié)點(diǎn)下發(fā)初始鄰居節(jié)點(diǎn)列表，而Peer端則實(shí)現(xiàn)鄰居節(jié)點(diǎn)列表的實(shí)時(shí)更新。

2.1 鄰居節(jié)點(diǎn)列表下發(fā)

節(jié)點(diǎn)加入系統(tǒng)并請(qǐng)求數(shù)據(jù)時(shí)，首先向Tracker服務(wù)器上報(bào)自身信息以便Tracker服務(wù)器實(shí)時(shí)更新資源節(jié)點(diǎn)列表，同時(shí)Tracker服務(wù)器計(jì)算節(jié)點(diǎn)的綜合服務(wù)能力，并根據(jù)節(jié)點(diǎn)的綜合服務(wù)能力從資源節(jié)點(diǎn)列表中選擇一定數(shù)量的節(jié)點(diǎn)下發(fā)給請(qǐng)求節(jié)點(diǎn)作為初始鄰居節(jié)點(diǎn)列表。

綜合服務(wù)能力是節(jié)點(diǎn)的計(jì)算性能、傳輸速度和穩(wěn)定性等指標(biāo)的綜合，影響節(jié)點(diǎn)綜合服務(wù)能力的因素很多，例如節(jié)點(diǎn)帶寬越大，綜合服務(wù)能力越高，而傳輸時(shí)延越大則表示綜合服務(wù)能力越弱。另一方面，異構(gòu)環(huán)境的復(fù)雜性使得對(duì)綜合服務(wù)能力的評(píng)估更加復(fù)雜，移動(dòng)終端的電量、處理能力等都會(huì)對(duì)節(jié)點(diǎn)綜合服務(wù)能力產(chǎn)生影響。本文考慮實(shí)際P2P系統(tǒng)中影響節(jié)點(diǎn)性能的幾個(gè)主要因素包括上行帶寬、時(shí)延、電量、逗留時(shí)間、終端處理能力[1]，并定義節(jié)點(diǎn)的綜合服務(wù)能力為

其中：C0為節(jié)點(diǎn)v的綜合服務(wù)能力；C1，C2，C3，C4和C5分別為節(jié)點(diǎn)v的上行帶寬、時(shí)延、電量、逗留時(shí)間、終端處理能力的歸一化值，節(jié)點(diǎn)的服務(wù)能力會(huì)隨著這些因素的改變而有較大變化。

同時(shí)這些因素之間存在相互制約關(guān)系，上行帶寬越大、終端處理能力越強(qiáng)，所帶來(lái)的傳輸時(shí)延就會(huì)越小；傳輸時(shí)延增大，終端電量就會(huì)減小，相應(yīng)的逗留時(shí)間將會(huì)減小，從而導(dǎo)致節(jié)點(diǎn)失效風(fēng)險(xiǎn)增大。然而，由于缺少有力的分析工具，因此對(duì)于節(jié)點(diǎn)綜合服務(wù)能力的評(píng)估顯得比較困難。本文基于模糊認(rèn)知圖理論(FCM)[9]分析各因素之間的作用關(guān)系，以及各因素對(duì)綜合服務(wù)能力的影響，從而得到

式中：r為各個(gè)因素對(duì)節(jié)點(diǎn)性能的影響程度。

圖2 異構(gòu)環(huán)境下的P2P系統(tǒng)模糊認(rèn)知圖

根據(jù)各個(gè)因素之間的關(guān)系，將這些因素表示成FCM中的節(jié)點(diǎn)，基于FCM的理論和方法構(gòu)造1個(gè)有向圖，如圖2所示，其中C6為節(jié)點(diǎn)的失效風(fēng)險(xiǎn)。節(jié)點(diǎn)之間有向箭頭表示概念因素之間的有向影響關(guān)系，前向節(jié)點(diǎn)對(duì)后向節(jié)點(diǎn)的影響程度可以描述為{較大，一般，較小}，影響有正負(fù)之分，前向節(jié)點(diǎn)的增大引起后向節(jié)點(diǎn)增大的為正影響，前向節(jié)點(diǎn)的增大引起后向節(jié)點(diǎn)減小的為負(fù)影響。根據(jù)前面的分析與理論經(jīng)驗(yàn)[2]，本文使用{3,2,1}來(lái)量化節(jié)點(diǎn)間的影響程度進(jìn)而得到鄰接矩陣，其中，，，，，正值為正影響，負(fù)值為負(fù)影響。利用模糊認(rèn)知圖推理的數(shù)學(xué)模型式[9]，將前一個(gè)輸出狀態(tài)作為下一個(gè)輸入狀態(tài)進(jìn)行推理，通過(guò)多次迭代得到穩(wěn)定狀態(tài)時(shí)的鄰接矩陣，描述了穩(wěn)定狀態(tài)下各個(gè)因素之間的影響程度

由式(3)得到各個(gè)因素對(duì)目標(biāo)概念C0(即節(jié)點(diǎn)綜合服務(wù)能力)的影響程度的量化總和。其中概念因素C6不是異構(gòu)環(huán)境下影響節(jié)點(diǎn)服務(wù)能力的直接因素，本文考慮的5個(gè)因素對(duì)節(jié)點(diǎn)服務(wù)能力的影響程度量化值為

根據(jù)式(2)和式(4)得到節(jié)點(diǎn)服務(wù)能力的綜合評(píng)估值

綜上所述，在Tracker服務(wù)器首先根據(jù)FCM計(jì)算新加入Peer客戶(hù)端的綜合服務(wù)能力，并存儲(chǔ)此Peer客戶(hù)端的信息，同時(shí)在已加入系統(tǒng)的節(jié)點(diǎn)中選擇一部分資源節(jié)點(diǎn)返回給該P(yáng)eer客戶(hù)端。考慮到Tracker服務(wù)器的負(fù)擔(dān)以及整個(gè)網(wǎng)絡(luò)的負(fù)載問(wèn)題，Tracker服務(wù)器根據(jù)節(jié)點(diǎn)的綜合服務(wù)能力隨機(jī)的選擇個(gè)節(jié)點(diǎn)。為盡快獲取數(shù)據(jù)以及保證視頻的服務(wù)質(zhì)量，再?gòu)膫€(gè)節(jié)點(diǎn)中選擇綜合服務(wù)能力最大的個(gè)節(jié)點(diǎn)作為鄰居節(jié)點(diǎn)列表返回給Peer客戶(hù)端。

2.2 鄰居節(jié)點(diǎn)列表實(shí)時(shí)更新

Peer客戶(hù)端首先根據(jù)Tracker服務(wù)器返回的鄰居節(jié)點(diǎn)列表進(jìn)行數(shù)據(jù)下載，然后周期性地利用馬爾科夫蒙特卡洛方法進(jìn)行隨機(jī)行走，動(dòng)態(tài)更新Peer客戶(hù)端的鄰居節(jié)點(diǎn)列表。

Tracker服務(wù)器主要根據(jù)綜合服務(wù)能力選擇鄰居節(jié)點(diǎn)，綜合服務(wù)能力越高的節(jié)點(diǎn)被選擇的次數(shù)和概率越大，當(dāng)請(qǐng)求節(jié)點(diǎn)規(guī)模增大時(shí)，綜合服務(wù)能力強(qiáng)的節(jié)點(diǎn)會(huì)因?yàn)榉?wù)節(jié)點(diǎn)數(shù)的增大而出現(xiàn)過(guò)載，并且提供服務(wù)的節(jié)點(diǎn)的綜合服務(wù)能力會(huì)隨著所服務(wù)節(jié)點(diǎn)數(shù)目的增多而降低，為了保證節(jié)點(diǎn)負(fù)載均衡以及確保流的服務(wù)質(zhì)量，需要更新鄰居節(jié)點(diǎn)列表，選擇實(shí)時(shí)服務(wù)能力高的節(jié)點(diǎn)，為此定義服務(wù)能力級(jí)別為

其中：C0為v-的綜合服務(wù)能力；為常量，，本文采用0.5；為時(shí)刻節(jié)點(diǎn)v-所服務(wù)的鄰居節(jié)點(diǎn)數(shù)，節(jié)點(diǎn)的服務(wù)能力級(jí)別為節(jié)點(diǎn)的實(shí)時(shí)服務(wù)能力。

節(jié)點(diǎn)v-被選作鄰居節(jié)點(diǎn)的概率為

節(jié)點(diǎn)v-的服務(wù)能力級(jí)別越高，被選為鄰居節(jié)點(diǎn)的概率就越大，當(dāng)v-被選為鄰居節(jié)點(diǎn)時(shí)，增加，服務(wù)能力級(jí)別降低，期望概率也降低，這樣既考慮了節(jié)點(diǎn)的動(dòng)態(tài)加入過(guò)程也避免了級(jí)別較高的節(jié)點(diǎn)過(guò)載問(wèn)題，充分利用節(jié)點(diǎn)的服務(wù)能力，主動(dòng)找到并選擇出服務(wù)能力級(jí)別高的節(jié)點(diǎn)。

由式(7)的分母計(jì)算期望概率M，需要知道全局節(jié)點(diǎn)的級(jí)別信息?？梢酝ㄟ^(guò)Tracker服務(wù)器定期統(tǒng)計(jì)節(jié)點(diǎn)服務(wù)能力級(jí)別，新節(jié)點(diǎn)加入系統(tǒng)時(shí)，Tracker服務(wù)器按照式(7)計(jì)算概率返回給節(jié)點(diǎn)，但如果系統(tǒng)節(jié)點(diǎn)數(shù)目增大，會(huì)造成Tracker服務(wù)器負(fù)載過(guò)重，引起單點(diǎn)故障。針對(duì)此問(wèn)題，本文借助馬爾科夫蒙特卡洛方法，進(jìn)行隨機(jī)行走[10]，通過(guò)Metropolis-Hastings[11?12]算法構(gòu)造轉(zhuǎn)移矩陣，使得隨機(jī)行走的靜止概率與式(7)描述的期望概率相同。具體如下：對(duì)于網(wǎng)絡(luò)中不同的節(jié)點(diǎn)v-，作為馬爾科夫鏈中不同的狀態(tài)X，從系統(tǒng)中任意1個(gè)節(jié)點(diǎn)開(kāi)始進(jìn)行隨機(jī)行走，在時(shí)刻停留在節(jié)點(diǎn)v-，即狀態(tài)X；在+1時(shí)刻，會(huì)以一定的概率停留在節(jié)點(diǎn)v-的鄰居v-+1上，達(dá)到狀態(tài)X+1；經(jīng)過(guò)步后，會(huì)以一定的概率M停留節(jié)點(diǎn)v-上，停留在節(jié)點(diǎn)v-的概率為隨機(jī)行走的靜止概率。

根據(jù)Metropolis-Hastings定義，為了構(gòu)造1個(gè)以目標(biāo)分布的馬爾科夫鏈，借助于1個(gè)輔助的概率謎底函數(shù)，Chib等[11]提出從狀態(tài)轉(zhuǎn)移到狀態(tài)的轉(zhuǎn)移概率為，其中為狀態(tài)到狀態(tài)的接受概率，。選擇，計(jì)算轉(zhuǎn)移概率P。

根據(jù)隨機(jī)過(guò)程理論，若轉(zhuǎn)移矩陣是不可約且非周期的，則存在靜止概率分布，使得。為保證靜態(tài)概率的存在性，需要確定轉(zhuǎn)移矩陣不可約且非周期的條件。不可約就是馬爾科夫的互達(dá)特性，對(duì)任意狀態(tài)X和X，存在滿(mǎn)足，系統(tǒng)中的所有節(jié)點(diǎn)組成一個(gè)覆蓋網(wǎng)[13?14]，網(wǎng)狀結(jié)構(gòu)流媒體系統(tǒng)主要特點(diǎn)是覆蓋網(wǎng)拓?fù)湓诤艽蟪潭壬媳苊饬恕肮聧u”，節(jié)點(diǎn)之間可以互達(dá)，因此滿(mǎn)足不可約的條件。為滿(mǎn)足非周期特性，根據(jù)文獻(xiàn)[15]所述，通過(guò)引入惰性因子來(lái)構(gòu)造非周期轉(zhuǎn)移矩陣，其中。結(jié)合式(6)，得轉(zhuǎn)移概率為

在Peer客戶(hù)端，請(qǐng)求節(jié)點(diǎn)首先根據(jù)Tracker服務(wù)器返回的鄰居節(jié)點(diǎn)列表進(jìn)行下載數(shù)據(jù)；為保證鄰居節(jié)點(diǎn)的實(shí)時(shí)服務(wù)能力，每隔周期進(jìn)行1次隨機(jī)行走，隨機(jī)行走步長(zhǎng)為，行走結(jié)束時(shí)的節(jié)點(diǎn)是v。若請(qǐng)求節(jié)點(diǎn)的鄰居節(jié)點(diǎn)已經(jīng)達(dá)到上限，則將自身鄰居節(jié)點(diǎn)中服務(wù)能力級(jí)別最低的節(jié)點(diǎn)刪除，將v作為鄰居節(jié)點(diǎn)，否則直接添加為鄰居，同時(shí)更新請(qǐng)求節(jié)點(diǎn)和v的服務(wù)能力級(jí)別。

3 仿真實(shí)驗(yàn)與性能分析

本文基于Oversim模擬器[16?17]進(jìn)行仿真，針對(duì)異構(gòu)環(huán)境使用SVC可擴(kuò)展視頻編碼技術(shù)將視頻分為基礎(chǔ)層和17個(gè)增強(qiáng)層，每個(gè)終端節(jié)點(diǎn)根據(jù)接入網(wǎng)類(lèi)型的不同申請(qǐng)下載不同層數(shù)的視頻，固網(wǎng)、WLAN和3G網(wǎng)絡(luò)的申請(qǐng)層數(shù)分別為18，12和6，實(shí)際解碼接收層數(shù)越多則獲得的視頻質(zhì)量越高。實(shí)驗(yàn)環(huán)境中，起始種子節(jié)點(diǎn)數(shù)為5，仿真節(jié)點(diǎn)數(shù)目為150，節(jié)點(diǎn)在加入系統(tǒng)時(shí)會(huì)隨機(jī)生成仿真所需要的參數(shù)，取值范圍如表1所示，節(jié)點(diǎn)每隔20 s行走1次，隨機(jī)行走的步長(zhǎng)設(shè)為3。

表1 仿真參數(shù)初始取值范圍

仿真實(shí)驗(yàn)主要從3個(gè)方面驗(yàn)證算法的有效性。首先，從鄰居節(jié)點(diǎn)的綜合服務(wù)能力和服務(wù)能力級(jí)別的分布情況分析算法選擇鄰居節(jié)點(diǎn)的有效性；其次統(tǒng)計(jì)客戶(hù)節(jié)點(diǎn)接收的實(shí)際視頻層數(shù)，驗(yàn)證算法對(duì)系統(tǒng)服務(wù)質(zhì)量的影響；最后通過(guò)視頻傳輸時(shí)間、電量消耗等參數(shù)來(lái)分析算法對(duì)系統(tǒng)性能的改進(jìn)。

為了驗(yàn)證算法的性能，將PSAH算法與另外2種算法進(jìn)行對(duì)比，一種是針對(duì)綜合服務(wù)能力隨機(jī)選擇的方式，隨機(jī)選擇R-S(random select)是P2P系統(tǒng)采用的一種典型節(jié)點(diǎn)選擇機(jī)制，另外一種是文獻(xiàn)[3]中提到的ASDC算法，它使用隨機(jī)行走來(lái)更新鄰居節(jié)點(diǎn)列表但僅以帶寬作為節(jié)點(diǎn)的服務(wù)能力。

3.1 鄰居節(jié)點(diǎn)的性能分析

本文從鄰居節(jié)點(diǎn)的平均綜合服務(wù)能力和平均服務(wù)能力級(jí)別2個(gè)方面分析PSAH算法所選擇到的鄰居節(jié)點(diǎn)的性能，如圖3和圖4所示。

首先計(jì)算每個(gè)客戶(hù)端的鄰居節(jié)點(diǎn)綜合服務(wù)能力的平均值，該值越大代表鄰居節(jié)點(diǎn)列表所能提供的服務(wù)性能越強(qiáng)，計(jì)算結(jié)果如圖3所示。從圖3可以看出：使用PSAH和ASDC算法時(shí)，鄰居節(jié)點(diǎn)平均綜合服務(wù)能力明顯高于使用R-S算法時(shí)，平均綜合服務(wù)能力，例如使用PSAH算法時(shí)，90%的節(jié)點(diǎn)的平均綜合服務(wù)能力大于40，而使用R-S算法時(shí)平均綜合服務(wù)能力大于40的只有40%。這是由于ASDC算法能動(dòng)態(tài)更新鄰居節(jié)點(diǎn)的服務(wù)能力級(jí)別，同樣在PSAH算法中周期性更新鄰居節(jié)點(diǎn)列表，將實(shí)時(shí)服務(wù)能力高的節(jié)點(diǎn)替換實(shí)時(shí)服務(wù)能力低的節(jié)點(diǎn)，因此所選的鄰居節(jié)點(diǎn)的綜合服務(wù)能力會(huì)整體偏高；而相對(duì)于ASDC算法使用帶寬作為指標(biāo)，PSAH算法計(jì)算綜合服務(wù)能力，因此PSAH算法得到的結(jié)果與ASDC算法得到的結(jié)果略有不同。

算法：1—PSAH；2—ASDC；3—R-S

算法：1—PSAH；2—ASDC；3—R-S

然后計(jì)算每個(gè)客戶(hù)端的鄰居節(jié)點(diǎn)平均服務(wù)能力級(jí)別，得到鄰居節(jié)點(diǎn)平均服務(wù)能力級(jí)別的累積概率分布如圖4所示。從圖4可以看出：PSAH和ASDC算法得到的平均服務(wù)能力分布比較均衡，主要分布于區(qū)間[10, 20]，而R-S算法得到的平均服務(wù)能力級(jí)別具有隨機(jī)性。這主要是因?yàn)镻SAH算法和ASDC算法都根據(jù)節(jié)點(diǎn)服務(wù)能力的變化動(dòng)態(tài)選擇鄰居節(jié)點(diǎn)，根據(jù)式(6)和式(7)可以得到：服務(wù)能力強(qiáng)的節(jié)點(diǎn)被選擇作為鄰居節(jié)點(diǎn)的概率會(huì)隨著所服務(wù)節(jié)點(diǎn)數(shù)的增大而下降，同時(shí)服務(wù)能力弱的節(jié)點(diǎn)被選擇鄰居節(jié)點(diǎn)的概率小，服務(wù)能力級(jí)別相對(duì)有所上升，這樣保證了服務(wù)能力強(qiáng)的節(jié)點(diǎn)不會(huì)因?yàn)榉?wù)節(jié)點(diǎn)數(shù)的增大而出現(xiàn)過(guò)載，從而保證負(fù)載均衡。

3.2 接收視頻層數(shù)

通過(guò)比較3種算法得到的實(shí)際接收視頻層數(shù)，評(píng)估系統(tǒng)的服務(wù)性能。性能越好，接收層數(shù)越多視頻播放越清晰。

圖5 客戶(hù)節(jié)點(diǎn)接收視頻層數(shù)

由于異構(gòu)環(huán)境中不同接入網(wǎng)類(lèi)型的節(jié)點(diǎn)的下行帶寬、分辨率、電量等因素有較大差異，因此，不同接入網(wǎng)類(lèi)型的客戶(hù)節(jié)點(diǎn)申請(qǐng)下載不同層數(shù)的視頻，分別為18層(wired)，12層(WLAN)和6層(3G)，計(jì)算并統(tǒng)計(jì)3種接入網(wǎng)的客戶(hù)終端實(shí)際接收到的視頻層數(shù)的平均值，如圖5所示。從圖5可知：3種接入網(wǎng)下客戶(hù)節(jié)點(diǎn)接收到的視頻層數(shù)有類(lèi)似結(jié)果，使用R-S算法客戶(hù)節(jié)點(diǎn)接收的視頻層數(shù)都非常低；使用PSAH算法客戶(hù)節(jié)點(diǎn)接收的視頻層數(shù)與ASDC算法得到的結(jié)果相似，并且明顯高于R-S算法得到的結(jié)果。這是由于R-S算法采用隨機(jī)方式選擇鄰居節(jié)點(diǎn)，不能確保鄰居節(jié)點(diǎn)列表的服務(wù)性能，并且鄰居節(jié)點(diǎn)的實(shí)時(shí)服務(wù)能力會(huì)發(fā)生改變從而影響視頻數(shù)據(jù)的有效下載；ASDC算法自適應(yīng)地調(diào)整鄰居節(jié)點(diǎn)以確保鄰居節(jié)點(diǎn)列表的服務(wù)性能并且僅以節(jié)點(diǎn)的上行帶寬作為指標(biāo)進(jìn)行節(jié)點(diǎn)選擇，上行帶寬是影響節(jié)點(diǎn)數(shù)據(jù)傳輸?shù)淖钪匾囊蛩?，因此能夠很好地保證系統(tǒng)的服務(wù)質(zhì)量，而本文提出的PSAH算法雖然不是以上行帶寬作為唯一指標(biāo)，但是綜合考慮了包括節(jié)點(diǎn)上行帶寬、時(shí)延在內(nèi)的多個(gè)因素的影響，并且周期性更新鄰居節(jié)點(diǎn)列表以確保鄰居節(jié)點(diǎn)列表的服務(wù)性能，同樣獲得了較好的服務(wù)質(zhì)量，實(shí)際視頻接收層數(shù)與ASDC的結(jié)果相似。

3.3 系統(tǒng)性能分析

本文主要從視頻傳輸時(shí)間和剩余電量2個(gè)方面進(jìn)行分析算法對(duì)系統(tǒng)服務(wù)性能的改進(jìn)。視頻傳輸時(shí)間指客戶(hù)節(jié)點(diǎn)從資源節(jié)點(diǎn)處接收完視頻資源所需要的時(shí)間，傳輸時(shí)間越短，說(shuō)明系統(tǒng)中節(jié)點(diǎn)能夠更快地獲取數(shù)據(jù)。電量損耗是指客戶(hù)節(jié)點(diǎn)從資源節(jié)點(diǎn)處接收完視頻資源所消耗的電量，電量損耗越少說(shuō)明系統(tǒng)消耗越少，系統(tǒng)性能越好。

圖6所示為視頻傳輸時(shí)間概率直方圖分布圖。從圖6可以看出：與R-S算法、ASDC算法相比，本文提出的PSAH算法得到的傳輸時(shí)間相對(duì)均勻，大部分節(jié)點(diǎn)的傳輸時(shí)間低于500 s，而R-S算法和ASDC算法得到的傳輸時(shí)間跨度比較大且傳輸時(shí)間在500~ 600 s之間的節(jié)點(diǎn)比較多；計(jì)算所有節(jié)點(diǎn)傳輸時(shí)間的平均值如圖7所示。從圖7可知：PSAH算法得到的 441 s低于R-S算法得到的475 s和ASDC算法得到的469 s。這是因?yàn)椴捎秒S機(jī)選擇方式選擇的鄰居節(jié)點(diǎn)的服務(wù)能力具有不確定性，會(huì)造成服務(wù)能力較高的節(jié)點(diǎn)過(guò)載從而使得傳輸時(shí)間變長(zhǎng)，并且隨機(jī)選擇的鄰居節(jié)點(diǎn)的鏈路時(shí)延具有隨機(jī)性；ASDC算法自適應(yīng)的更新服務(wù)能力級(jí)別，確保鄰居節(jié)點(diǎn)的服務(wù)能力，并且傳輸時(shí)間有所減小，而本文提出的PSAH算法通過(guò)更新鄰居節(jié)點(diǎn)服務(wù)能力級(jí)別減少傳輸時(shí)間的同時(shí)，使用FCM計(jì)算綜合服務(wù)能力，考慮了節(jié)點(diǎn)的鏈路時(shí)延，選擇的鄰居節(jié)點(diǎn)的時(shí)延小，從而保證了較短的視頻傳輸時(shí)間。

圖6 視頻傳輸時(shí)間概率直方圖分布圖

圖7 節(jié)點(diǎn)視頻傳輸時(shí)間平均值

圖8所示為節(jié)點(diǎn)電量消耗累積概率分布。從圖8可以看出：使用PSAH算法時(shí)系統(tǒng)中節(jié)點(diǎn)所消耗的電量明顯小于使用ASDC算法和R-S算法時(shí)的電量。例如：使用R-S算法有將近80%的節(jié)點(diǎn)的電量損耗超過(guò)1.5 A?h，使用ASDC算法有將近60%的節(jié)點(diǎn)的電量損耗超過(guò)1.5 A?h，而使用PSAH算法，電量損耗超過(guò) 1.5 A?h的節(jié)點(diǎn)只有30%。這是由于使用R-S算法時(shí)的視頻傳輸時(shí)間長(zhǎng)，所消耗的電量增加，另外采用隨機(jī)選擇容易引起節(jié)點(diǎn)的過(guò)載，電量少的節(jié)點(diǎn)有可能被多次選作鄰居節(jié)點(diǎn)而電量多的節(jié)點(diǎn)被選為鄰居節(jié)點(diǎn)的次數(shù)少，從而引起系統(tǒng)損耗的增加；ASDC算法自適應(yīng)更新鄰居節(jié)點(diǎn)從而保證鄰居節(jié)點(diǎn)列表的服務(wù)能力，縮短視頻傳輸時(shí)間降低電量損耗，但是ASDC算法僅以帶寬作為指標(biāo)，所選節(jié)點(diǎn)的電量具有隨機(jī)性，電量少的節(jié)點(diǎn)被多次選作鄰居節(jié)點(diǎn)會(huì)使得電量消耗加劇，節(jié)點(diǎn)會(huì)因電量消耗完而過(guò)早的離開(kāi)系統(tǒng)從而引起系統(tǒng)的損耗增加；PSAH算法不僅通過(guò)縮短視頻傳輸時(shí)間來(lái)降低電量的損耗，而且以FCM計(jì)算的綜合服務(wù)能力為標(biāo)準(zhǔn)，考慮到了電量的影響，從而使得系統(tǒng)節(jié)點(diǎn)電量消耗降低。

算法：1—PSAH；2—ASDC；3—R-S

通過(guò)前面的分析可知，相對(duì)于R-S算法和ASDC算法，本文提出的PSAH算法在選擇優(yōu)質(zhì)鄰居節(jié)點(diǎn)的同時(shí)，保證了節(jié)點(diǎn)的負(fù)載均衡，相對(duì)于ASDC算法同樣取得了較好的服務(wù)質(zhì)量，并在系統(tǒng)服務(wù)性能上明顯優(yōu)于ASDC算法。

4 結(jié)論

1) 研究了異構(gòu)環(huán)境下的P2P流媒體系統(tǒng)中節(jié)點(diǎn)選擇問(wèn)題，提出一種新的節(jié)點(diǎn)選擇算法。該算法的主要優(yōu)勢(shì)在于：利用模糊認(rèn)知理論計(jì)算節(jié)點(diǎn)的綜合服務(wù)能力，并為每個(gè)新加入的節(jié)點(diǎn)選擇綜合服務(wù)能力強(qiáng)的節(jié)點(diǎn)；使用馬爾科夫蒙特卡洛方法進(jìn)行隨機(jī)行走，避免了全局信息的維護(hù)以及復(fù)雜的計(jì)算，充分利用系統(tǒng)中服務(wù)能力較強(qiáng)的節(jié)點(diǎn)。

2) 該算法充分考慮異構(gòu)環(huán)境對(duì)節(jié)點(diǎn)服務(wù)能力的影響，保證良好的節(jié)點(diǎn)性能，同時(shí)大幅提高系統(tǒng)的服務(wù)質(zhì)量。

[1] 宋俊平, 張棪, 周旭, 等. 基于SVC的P2P流媒體系統(tǒng)研究綜述[J]. 計(jì)算機(jī)應(yīng)用研究, 2013, 30(4): 965?970. SONG Junping, ZHANG Yan, ZHOU Xu, et al.A survey of the research on SVC-based P2P streaming systems[J]. Application Research of Computers, 2013, 30(4): 965?970.

[2] Zhang Y, Zhou X, Tang H, et al. Peer selection in mobile P2P systems over 3G cellular networks[C]// 2011 IEEE International Conference on Pervasive Computing and Communications Workshops (PERCOM Workshops). Seattle, WA, USA: IEEE, 2011: 467?470.

[3] 馮偵探, 倪宏, 王勁林, 等. P2P流媒體直播系統(tǒng)自適應(yīng)鄰居節(jié)點(diǎn)選擇算法[J]. 西安電子科技大學(xué)學(xué)報(bào)(自然科學(xué)版), 2012, 39(3): 136?143. FENG Zhentan, NI Hong, WANG Jinlin,et alAdaptive neighbor selection method for the P2P media streaming system[J]. Journal of XiDian University, 2012, 39(3): 136?143.

[4] Mushtaq M, Ahmed T. Smooth video delivery for SVC based media streaming over P2P networks[C]// 2008 IEEE International Conference on Consumer Communications and Networking Conference, Las Vegas, NV, USA: IEEE, 2008: 447?451.

[5] ZHANG Gui, YUAN Chun. Self-adaptive peer-to-peer streaming for heterogeneous networks using scalable video coding[C]// 2010 IEEE International Conference on Communication Technology (ICCT). Beijing, China: IEEE, 2010: 1390?1393.

[6] Schwarz H, Marpe D, Wiegand T. Overview of the scalable video coding extension of the H. 264/AVC standard[J]. IEEE Transactions on Circuits and Systems for Video Technology, 2007, 17(9): 1103?1120.

[7] SHEN Haiying, LIU Guoxin, Gemmill J, et al. A P2P-based Infrastructure for adaptive trustworthy and efficient communication in wide-area distributed systems[J]. IEEE Transactions on Parallel and Distributed Systems, 2014, 25(9): 2222?2233.

[8] 鄭婕, 張松. 基于 Mesh 的P2P流媒體節(jié)點(diǎn)選擇機(jī)制研究[J]. 微電子學(xué)與計(jì)算機(jī), 2008, 24(12): 95?99. ZHENG Jie, ZHANG Song. A Study of peer selection strategy for mesh based P2P streaming[J]. Microelectronics and computer, 2008, 24(12): 95?99.

[9] Kosko B. Fuzzy cognitive maps[J]. International journal of man-machine studies, 1986, 24(1): 65?75.

[10] Lovász L. Random walks on graphs: A survey[J]. Combinatorics, Paul erdos is eighty, 1993, 2(1): 1?46.

[11] Chib S, Greenberg E. Understanding the metropolis-hastings algorithm[J]. The American Statistician, 1995, 49(4): 327?335.

[12] Johnson A A, Flegal J M. A modified conditional Metropolis- Hastings sampler[J]. Computational Statistics & Data Analysis, 2014, 78(5): 141?152.

[13] Jannotti J, Gifford D K, Johnson K L, et al. Overcast: reliable multicasting with on overlay network[C]// The 4th USENIX Symposium on Operating System Design & Implementation (OSDI).Colorado, USA: USENIX Association, 2000: 14?14.

[14] ZHANG Meng, ZHANG Qian, SUN Lifeng, et al. Understanding the power of pull-based streaming protocol: Can we do better?[J]. IEEE Journal on Selected Areas in Communications, 2007, 25(9): 1678?1694.

[15] ZHONG Ming, SHEN Kai, Seiferas J. The convergence- guaranteed random walk and its applications in peer-to-peer networks[J]. IEEE Transactions on Computers, 2008, 57(5): 619?633.

[16] Baumgart I, Heep B, Krause S. OverSim: A Flexible Overlay Network Simulation Framework[C]// IEEE Global Internet Symposium, New Jersey, USA: IEEE, 2007: 79?84.

[17] Muňoz-Gea J P, Malgosa-Sanahuja J, Manzanares-Lopez P, et al. Simulation of a P2P application using OverSim[C]// 2009 First International Conference on Advances in Future Internet. New Jersey, USA: IEEE, 2009: 53?60.

(編輯 羅金花)

Peer selection algorithm for P2P streaming media in heterogeneous environment

TANG Chaowei1, XIAO Jun1, WANG Heng1, HU Pei1, LIU Qiannan1, SONG Junping2, LI Xiaohui3

(1. College of Communication Engineering, Chongqing University, Chongqing 400044, China;2. Science and Technology on Integrated System Laboratory, Institute of Software, Chinese Academy of Science, Beijing 100190, China;3. 94270 Unit of People’s Liberation Army, Jinan 250117, China)

In view of the complexity and the instability of heterogeneous environment, a peer selection algorithm for P2P streaming media system was proposed. The relationship between the factors which affect the performance of joints under heterogeneous environment was studied, the comprehensive service ability of peers was calculated through the fuzzy cognitive maps theory, and the peers with high service ability were selected as the neighbors. In order to guarantee that the neighbors have a high real time ability, the random walk process was utilized to update the list of neighbors periodically by using Monte Carlo methods. In addition, transition probability matrix was calculated by the Metropolis- Hastings methods to satisfy the expected stationary distribution of random walk. The results show that the proposed algorithm can select excellent peers and ensure the load balance of peers, as well as reduce the consumption of the system andimprove the quality of video service and significantly improve system performance.

heterogeneous environment; P2P streaming media; peer selection; comprehensive service ability; random walk

10.11817/j.issn.1672-7207.2015.09.018

TP393

A

1672?7207(2015)09?3287?08

2014?12?18；

2015?02?20

國(guó)家科技重大專(zhuān)項(xiàng)(2011ZX03005-004-02)；國(guó)家青年科學(xué)基金資助項(xiàng)目(61102076) (Project(2011ZX03005-004-02) supported by the National Science and Technology Major Program of China; Project(61102076) supported by the National Natural Science Foundation for Young Scientists of China)

唐朝偉，博士(后)，研究員，從事于寬帶無(wú)線移動(dòng)多媒體和P2P流媒體技術(shù)研究；E-mail: cwtang@cqu.edu.cn