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

?

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

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

(1. 重慶大學通信工程學院，重慶，400044；2. 中國科學院軟件研究所天基綜合信息系統(tǒng)技術重點實驗室，北京，100190；3. 中國人民解放軍94270部隊，山東濟南，250117)

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

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

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

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

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

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

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

2 節(jié)點選擇算法

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

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

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

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

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

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

式中：r為各個因素對節(jié)點性能的影響程度。

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

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

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

根據(jù)式(2)和式(4)得到節(jié)點服務能力的綜合評估值

綜上所述，在Tracker服務器首先根據(jù)FCM計算新加入Peer客戶端的綜合服務能力，并存儲此Peer客戶端的信息，同時在已加入系統(tǒng)的節(jié)點中選擇一部分資源節(jié)點返回給該Peer客戶端?？紤]到Tracker服務器的負擔以及整個網(wǎng)絡的負載問題，Tracker服務器根據(jù)節(jié)點的綜合服務能力隨機的選擇個節(jié)點。為盡快獲取數(shù)據(jù)以及保證視頻的服務質(zhì)量，再從個節(jié)點中選擇綜合服務能力最大的個節(jié)點作為鄰居節(jié)點列表返回給Peer客戶端。

2.2 鄰居節(jié)點列表實時更新

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

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

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

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

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

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

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

根據(jù)隨機過程理論，若轉(zhuǎn)移矩陣是不可約且非周期的，則存在靜止概率分布，使得。為保證靜態(tài)概率的存在性，需要確定轉(zhuǎn)移矩陣不可約且非周期的條件。不可約就是馬爾科夫的互達特性，對任意狀態(tài)X和X，存在滿足，系統(tǒng)中的所有節(jié)點組成一個覆蓋網(wǎng)[13?14]，網(wǎng)狀結(jié)構(gòu)流媒體系統(tǒng)主要特點是覆蓋網(wǎng)拓撲在很大程度上避免了“孤島”，節(jié)點之間可以互達，因此滿足不可約的條件。為滿足非周期特性，根據(jù)文獻[15]所述，通過引入惰性因子來構(gòu)造非周期轉(zhuǎn)移矩陣，其中。結(jié)合式(6)，得轉(zhuǎn)移概率為

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

3 仿真實驗與性能分析

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

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

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

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

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

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

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

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

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

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

3.2 接收視頻層數(shù)

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

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

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

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

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

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

圖6 視頻傳輸時間概率直方圖分布圖

圖7 節(jié)點視頻傳輸時間平均值

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

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

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

4 結(jié)論

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

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

[1] 宋俊平, 張棪, 周旭, 等. 基于SVC的P2P流媒體系統(tǒng)研究綜述[J]. 計算機應用研究, 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)自適應鄰居節(jié)點選擇算法[J]. 西安電子科技大學學報(自然科學版), 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é)點選擇機制研究[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

國家科技重大專項(2011ZX03005-004-02)；國家青年科學基金資助項目(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)

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