基于P2P的流媒體數據算法

摘要：近年來，基于P2P技術的流媒體應用已成為研究熱點。由于流媒體的數據傳輸率較高，若對于每個請求均采取傳統C/S模式，在服務器上為其單獨分配一條數據流，不僅無法滿足大規模流媒體應用部署的需求，而且很容易使中央服務器負載過重，導致局部網絡發生擁塞。P2P技術的發展，為解決流媒體服務器的瓶頸問題提供了新的途徑，其充分利用每個節點的空閑資源分擔服務器負載， 從而可極大地減少服務器上網絡帶寬資源的消耗和局部網絡的擁塞，并且具有良好的擴展性，能支持大數量級的用戶同時在線。

關鍵詞：P2P；流媒體；數據算法

中圖分類號：TN919.8文獻標識碼：A文章編號：1674-7712 (2014) 08-0000-01

一、相關研究

OTSp2p算法是一種最優的媒體數據分配算法，其主要思想是越晚用到的數據塊就越晚獲取它，優點是在其假設條件下延遲達到了最優，請求者維持數據傳輸的接收開銷相對較小。但是OTSp2p算法對服務節點的帶寬限制不符合實際，在應用時會造成帶寬的浪費。

Round-Robin算法按照比例分配所有請求的數據塊到一個伙伴。如果僅有一個伙伴持有該數據塊，那么就從該伙伴獲?。环駝t，從擁有最大可用帶寬的伙伴節點獲取。其活動是可預知的，每個節點被選擇的機會是1/N，因此很容易計算出節點的負載分布。該算法更適合用在靜態的，同構的環境中。

Random算法比較簡單，只是隨機從持有被請求數據塊的節點集中選擇一個節點請求數據。這種算法在異構的網絡環境中性能不穩定。

RF調度算法與BitTorrent的下載策略相似，是一種快速時間響應的啟發式算法。由于稀缺的數據塊不容易適應播放截止時間的約束，所以RF算法的主要思想是首先請求潛在提供者較少的數據塊。如果一個數據塊有多個潛在提供者，那么將選擇具有最多剩余帶寬和足夠可用時間的伙伴節點。對于RF算法的不足將在下面給出。

二、數據調度策略

（一）提出問題

實時流媒體的數據調度算法要受到兩個條件的約束，即每個數據塊的播放截止時間以及每個伙伴節點的帶寬的不一致性。其調度策略被歸結為并行機調度問題的一個變種，屬于NP難的問題，因此不容易找到其最佳解決辦法。

出于對要快速適應高動態的網絡環境變化的考慮，在CoolStreaming中提出了RF調度算法。該算法可以取得近似的最佳調度，但是由于其對數據的分發仍然存在一定的隨機性和不確定性，因此在實時性要求較高的情況下很難保證每個數據塊都會在播放截止時間之前分發到所有節點上。

在RF調度算法中，稀缺的數據塊具有優先調度的權利。我們做如下假設：當請求的一個數據塊很新時，其沒有被廣泛傳播，網絡中只有少數節點擁有該數據塊。按照RF的策略，先要請求該數據塊。若此時網絡帶寬不足以同時發送或接收多個數據塊，則可能會使序號較小的數據塊在其播放截止時間之前不能到達，導致媒體播放的不流暢。

對于請求節點而言，其期望得到可提供最小延遲的數據提供節點的服務。而對于一個數據塊，會有多個節點擁有它，因此最后選定的數據提供節點的服務延遲可能并不是最小的。同時由于一次調度請求的是多個數據塊，有可能多個數據塊在調度過程中選擇了同一個提供者。因此后到的請求必須等待先到的請求或者重新選擇提供者，這樣會增大數據請求的延遲時間。下面我們提出一種新算法來解決以上問題。

（二）改進的綜合調度算法

類似CoolStreaming，將視頻數據分割成大小相等的片段，用一個緩存映射BM（Buffer Map）來表示Peer節點中是否擁有某個片斷的數據。一個Peer節點會周期性的同與其連接的伙伴節點交換BM信息，同時可獲得其與伙伴節點間的傳輸延遲。在數據傳輸時，計算數據接收速率，并保存在Peer節點的伙伴節點信息表中。

在新算法中，通過對數據緊急度和稀缺度的綜合考慮來決定數據塊請求的先后順序，通過對請求節點接收速率的統計來計算數據的傳輸時間。

這樣在請求的數據塊序號較大且提供者較少時，其稀缺度也是不會是一個很大的值。

在獲得了這些參數以后，我們可以獲得數據塊的優先級。之后再將要請求的數據塊按照優先級的大小降序排列，然后順序對排列后的數據塊依次發出請求，就可以更好的協調數據調度問題。

對于前面提出的多個數據塊請求可能選擇同一個提供者的問題，我們用一個貪婪算法來盡可能快的獲取優先級高的數據塊既可以保證對緊急數據和稀缺數據的優先請求，又可以避免多個數據請求全都集中在一個服務節點上的情況，一定程度的縮短了節點接收數據的延遲，平衡了每個伙伴節點的負載。

三、性能評價

為了更好的分析算法的性能，在數據塊的傳輸延遲方面將其與RF調度算法進行了比較。在每個調度周期內，計算數據塊到達請求節點的延遲時間。測試中，每個節點都有6～8個伙伴節點，每個數據塊的大小為300K。假設媒體數據的正常播放速率為300Kbps，并將其作為接收節點數據塊的消耗速率。因為該算法可以縮短數據到達的延遲，所以在數據塊消耗過程中，在調度周期內請求不同數量的數據塊，對數據塊的傳輸延遲時間進行測試。

結果表明，新算法可以一定程度的縮短每個調度周期的數據到達延遲，進而使得播放效果更為流暢。在保證了更好的QoS的同時，可以在不知道伙伴節點帶寬和沒有負載平衡機制的情況下取得更好的性能。

四、結束語

本文介紹了一種基于P2P的流媒體數據調度策略，通過與傳統的策略進行比較，分析了目前的一些調度算法存在的問題。該策略的主要特點是提出了綜合數據塊的緊急度與稀缺度對數據塊進行調度的方法，克服了RF調度算法的缺點，同時對傳輸速率的動態監測也體現了該策略的自適應性，充分的利用了P2P網絡中節點的資源。測試分析表明，該數據調度算法可以有效的縮短數據緩沖的延遲。

[作者簡介]徐其江，男，碩士，山東信息職業技術學院，講師，研究方向：計算機應用、動漫游戲設計與開發；王建峰，男，碩士，山東信息職業技術學院，講師。