可伸縮視頻流在多覆蓋網絡中基於拍賣的帶寬分配方法

2023-06-03 07:44:46 1

專利名稱：可伸縮視頻流在多覆蓋網絡中基於拍賣的帶寬分配方法
技術領域：
本發明涉及一種可伸縮視頻流在多覆蓋網絡中基於拍賣的帶寬分配方法，包括多 覆蓋網絡的構建，節點之間帶寬拍賣模型的建立，以及帶寬資源的分配策略。
背景技術：
可伸縮視頻編碼(SVC，Scalable Video Coding)是由JVT/MPEG組織制定的，以 H. 264/AVC為基礎的視頻編碼標準。一般的視頻編碼技術在輸出碼流中只包含單層碼流，在 視頻傳輸過程中必須全部傳輸，否則接收端無法正確解碼。可伸縮視頻編碼通過一次編碼 可生成一層或多層子碼流，這些子碼流通過一定依賴關係的組合可以提供不同視頻質量和 解析度的碼流集合。可伸縮視頻編碼技術可適應不同用戶節點的需求以及時變的環境，滿 足異構網絡中視頻內容分發的需要。P2P(Peer-to-Peer)流媒體系統融合了 P2P技術和流媒體技術，它的出現使得在 現有網絡基礎上實現大規模流媒體共享成為可能。在P2P流媒體系統中，用戶節點在接收 和播放流媒體數據的同時，利用上行帶寬和硬體資源，把緩存的流媒體數據轉發給其他節 點，充當起伺服器的角色。通過這樣的流數據共享，用戶節點不必直接從伺服器請求數據， 通過合理的節點組織、緩存管理等技術，可以使大量的用戶節點共享源自伺服器的一條數 據流。目前的P2P流媒體系統僅適用於單速率碼流的傳輸，即同一內容(頻道)的視頻 流僅由一個覆蓋網傳輸，用戶節點可加入不同的覆蓋網，獲得不同內容的視頻資源。相應的 帶寬分配方法只考慮了傳輸不同內容的多覆蓋網中，節點之間的帶寬分配策略。例如C. Wu 等於 2008 年 6 月在 IEEE Transactions on Parallel and Distributed Systems (國際電 子電氣工程師協會並行和分布式系統學報)發表的文獻「Dynamic Bandwidth Auctions in Multi-overlay P2Pstreaming with Network Coding(基於網絡編碼的多重覆蓋對等網絡 流媒體中的動態帶寬拍賣)」。該文用一種拍賣方法詮釋了網絡節點間的帶寬分配過程，即 每個節點組織一場拍賣，拍賣品即該節點的上行帶寬，參與者則是向該點請求帶寬的其他 節點。其中每層覆蓋網傳輸的內容都是不相關的。使用P2P流媒體技術傳輸可伸縮視頻流時，視頻流的各層子碼流都單獨由一個覆 蓋網傳輸，即同一內容的視頻流由多個覆蓋網傳輸。用戶節點可以根據自己的接收和解碼 能力，加入一定數量的覆蓋網，從而得到同一內容在不同尺度組合下的視頻圖像。由於子 碼流間的依賴性，這些覆蓋網也存在著不同的優先級，若使用上述的帶寬分配方法，將造成 帶寬資源的浪費。本發明提出了一種可伸縮視頻流在多覆蓋網絡中基於拍賣的帶寬分配 方法，以解決傳輸相關內容的多覆蓋網絡間的帶寬衝突，從而改善網絡性能，提高用戶滿意 度。

發明內容
本發明的目的在於提供一種可伸縮視頻流在多覆蓋網絡中基於拍賣的帶寬分配方法。該方法不僅能解決多覆蓋網絡間的帶寬衝突，提高節點接收視頻的質量，還能自適應 匹配可伸縮視頻編碼的層間依賴性，提高帶寬利用率。根據上述發明構思，本發明採用下述技術方案可伸縮視頻流在多覆蓋網絡中基 於拍賣的帶寬分配方法，其特徵在於第一，將P2P多覆蓋網絡的帶寬分配優化問題轉化為 一系列單層覆蓋網絡的帶寬分配優化問題，降低了計算複雜度，便於用分布式算法實現。第 二，節點間以雙向拍賣的形式，一方面出售自己的上行帶寬給其他節點，另一方面向其他節 點購買帶寬，從而解決多覆蓋網中節點的帶寬衝突問題。第三，提出一種自適應的「層加入 /退出」算法，使節點在進行帶寬出售和競拍的同時，可以根據網絡實時狀況選擇所要參加 的覆蓋網層數量，避免帶寬的浪費。下面給出原理說明1、P2P多覆蓋網的帶寬分配優化問題(1)網絡模型及相關參數原始視頻流通過編碼生成M層子碼流IL1, L2, ... , LM}，優先級從高到低排列，每 層子碼流Lm由一層覆蓋網m以速率Rm進行傳輸。每層覆蓋網m可抽象為有向圖Gm= (Vffl, Effl)，其中Vm代表所有參與該網絡的節點集合，Effl代表節點之間的鏈路集合。節點按序參加 不同數量覆蓋網，可在終端解碼出不同質量的視頻，用Ki表示節點i參加的覆蓋網層數，Uffl 表示每層覆蓋網中的效用函數。節點組織的每輪拍賣分為兩個子周期在分配周期內，拍賣組織節點i(上遊節 點)接收到所有其他請求帶寬節點(下遊節點)的報價後，使用一種分配策略出售其上行 帶寬Ci ；在競拍周期內，下遊節點根據分配到的帶寬，使用一種競拍策略調整自己在下一輪 拍賣中的報價。在覆蓋網m中，下遊節點j向上遊節點i提交的一個報價用= (PThrV) 表示，其中『^代表請求帶寬，表示其願意支付的帶寬單價，從上遊節點i接收到的分配 帶寬用表示。當網絡中所有下遊節點的帶寬請求得到滿足，即對任意下遊節點j，有
，則稱系統達到均衡狀態，此時網絡帶寬達到最優分配。
系統達到均衡狀態所經歷的拍賣輪數稱為收斂速度。(2)優化目標首先對於下遊節點j，其多層覆蓋網優化問題為 優化目標下遊節點總效用最大化，即效用函數減去競拍代價最大化。約束條件在每個覆蓋網中，下遊節點向所有上遊節點請求的總帶寬小於該覆蓋 網的傳輸速率。上述優化問題可分解Kj個單層覆蓋網優化問題 這樣節點在每個覆蓋網中單獨解決該問題即可。而上遊節點i的優化問題則為 優化目標上遊節點拍賣帶寬所得收入最大化。約束條件1)上遊節點可出售的帶寬總量受其上傳帶寬限制。2)上遊節點分配給下遊節點的帶寬量小於等於下遊節點請求的帶寬量。2、雙向拍賣過程(1)分配周期上遊節點i接收到來自所有下遊節點的報價後，以價高者得的原則分配自己擁有 的上傳帶寬Ci,直到所有帶寬分完或者所有下遊節點的需求均已滿足為止。偽代碼如下 選擇B中對應最高的報價咭；分配帶寬巧=min(C*,々)給節點j用於在覆蓋網m中下載數據； 從集合B中刪除報價0》}(2)競拍周期下遊節點j接收到來自所有上遊節點的分配帶寬後，首先執行「層加入/退出」算 法來決定在下一輪拍賣中參與的覆蓋網層數Kj,然後在每層覆蓋網中，解決單層覆蓋網優 化問題。具體步驟在每層覆蓋網中，節點對所有上遊節點的報價進行調整。首先根據上一 輪拍賣分配到的帶寬調整價格，若所得的帶寬小於請求的帶寬，則加價，反之減價。然後根 據新定的價格決定所要請求的帶寬，這裡使用一種注水算法，向邊際效用最大的上遊節點 請求帶寬。最後判斷新調整的報價是否可以得到滿足，若可以滿足則發送新報價，否則重複 以上價格和請求帶寬調整過程。在第m層覆蓋網中，報價調整的偽代碼如下
I= u，i:(i:j) eEj /*第m層覆蓋網中上遊節點集合*/fi = I,Mi ￡ //*報價滿足標誌位*/


使用注水算法計算G 估計下一輪拍賣可獲得帶寬z^r (v^ e
其中，注水算法的目的在於下遊節點j對各上遊節點(Vi G /)出價—定的情況 下，確定向每個節點i請求的帶寬、7。原則上是向可獲得邊際效用越大的節點請求更多的
帶寬，直到請求的總帶寬達到覆蓋網的傳輸速率，即Σ^^ ^ 具體過程的偽代碼如下
i&I
邊際效用函數=d[Um{rY；)/drT3 while C^rf3 < Rm)if (j第一次加入網絡){ Kj = M ；/*加入所有覆蓋層*//*計數器初始化*/Caj = 0 ；/* 加層計數 */for (m = 1 to Kj){ cdf = 0; } 退層計數 */

}if (Caj ^ Ta)
IKj = Kj+1 ；/* 加入新層 */ cdfj = 0, Caj = 0;/*計數器初始化*/
本方法與現有帶寬分配方法比較具有以下優點本方法提出了一種適用於傳輸可 伸縮視頻流的多覆蓋網的帶寬分配方法，解決了傳輸相關內容覆蓋網間的帶寬衝突問題， 不僅為接收節點提供了更高的視頻質量，還提高了網絡帶寬的利用率。


圖1本方法與現有帶寬分配方法比較的視頻質量示意圖；圖2本方法與現有帶寬分配方法比較的基本層接收帶寬示意圖；圖3本方法與現有帶寬分配方法比較的增強層接收帶寬示意圖4分配周期流程圖；圖5競拍周期流程圖
具體實施例方式下面結合附圖詳細描述本發明方法的應用實例1、網絡拓撲設定本方法通過隨機生成的覆蓋網絡進行性能仿真，其中70%的節點擁有IOO(Kbps) IlJ 300 (Kbps)的上傳帶寬，30%的節點(包括伺服器)擁有I(Mbps)到2(Mbps)的上傳帶 寬。本方法採用30幀/秒(fps)、解析度為CIF(352*288)的標準測試視頻序列「Foreman」 進行測試，GOP大小取32幀。對於每個序列，使用基於H. 264/AVC推廣標準的JSVM9_10參 考編碼器，將序列編碼成速率為256kbps的基本質量層，然後在基本層之上通過res編碼 達到384kbps碼率點。本方法使用U(X) = log(l+x)作為效用函數，並用平均峰值信噪比 (PSNR)衡量節點的接收視頻質量。2、建立基於上述拓撲的算法模型每個節點i同時充當上遊節點和下遊節點的角色，在每輪拍賣的兩個周期內分別 執行下列步驟1)分配周期步驟1.收集來自所有下遊節點的報價，令報價集合為B 二 {竭Hj)eEmym&Ki}·』步驟2.選擇集合B中出價椏最高的報價，分配對應帶寬邛= min(c;，唄)，並將 該報價從集合B中刪除；步驟3.重複步驟2直到上傳帶寬分配完或集合B為空集。2)競拍周期步驟1.收集來自所有上遊節點的分配帶寬，X = Vj (ij) e Emym e Ki)步驟2.執行「層加入/退出算法」，決定下一輪拍賣要參加的覆蓋網層數Ki ；步驟3.在覆蓋網m= 1，2，...，Ki中，根據上一輪拍賣結果分別調整報價。3、在上述網絡拓撲中進行性能分析1)靜態網絡收斂速度考慮一個靜態網絡，即沒有節點加入或退出網絡。令退出層門限Td = 5，不考慮加 入層。表1給出了在不同規模網絡中，每個節點可擁有的最大上遊節點數對網絡收斂速度 的影響，顯然上遊節點數量越多，網絡收斂速度越快。
表1.靜態網絡收斂速度2)門限值的確定首先不考慮加入層，僅改變退出層門限Td的大小，表2給出了在不同規模網絡中， 節點的平均接收視頻質量。隨著Td的增加，接收視頻質量先升後降，在Td = 5達到最高值。 表2.平均接收視頻質量在Td = 5的條件下，改變加入層門限Ta的大小，表3給出了在不同規模網絡中，節 點的平均接收視頻質量。隨著Ta的增加，接收視頻質量同樣經歷了先升後降的過程，在Ta =10達到最高值。 表3.平均接收視頻質量4、與現有帶寬分配方法的比較考慮一個包含100個節點的網絡，將本發明方法(Ml)與文獻「Dynamic BandwidthAuctions in Multi-overlay P2P streaming with Network Coding(基於網絡 編碼的多重覆蓋對等網絡流媒體中的動態帶寬拍賣)」中的分配方法(M2)進行比較，其中 Td = 5，Ta = 10。圖1-3分別比較了兩種分配方法在30輪拍賣內，節點平均的接收視頻質 量以及在各覆蓋層的分配帶寬。由於加入了「層加入/退出」算法，使用Ml可達到的接收 視頻質量明顯優於M2。使用M2雖然可以在增強層獲得較多分配帶寬，卻因為基本層接收帶 寬不足而造成帶寬浪費。
權利要求
一種可伸縮視頻流在多覆蓋網絡中基於拍賣的帶寬分配方法，其特徵在於採用下述步驟解決多覆蓋網絡間的帶寬衝突，提高節點接收視頻的質量，自適應匹配可伸縮視頻編碼的層間依賴性第一，將P2P多覆蓋網絡的帶寬分配優化問題轉化為一系列單層覆蓋網絡的帶寬分配優化問題；第二，節點間以雙向拍賣的形式，一方面出售自己的上行帶寬給其他節點，另一方面向其他節點購買帶寬，從而解決多覆蓋網中節點的帶寬衝突問題；第三，提出一種自適應的「層加入/退出」算法，使節點在進行帶寬出售和競拍的同時，可以根據網絡實時狀況選擇所要參加的覆蓋網層數量，避免帶寬的浪費。
2.根據權利要求1所述的可伸縮視頻流在多覆蓋網絡中基於拍賣的帶寬分配方法，其 特徵在於P2P多覆蓋網的帶寬分配優化問題為(1)網絡模型及相關參數原始視頻流通過編碼生成M層子碼流ILpL2,...，LM}，優先級從高到低排列，每層子碼 流Lm由一層覆蓋網m以速率Rm進行傳輸；每層覆蓋網m可抽象為有向圖Gm = (Vffl, Effl)，其 中Vm代表所有參與該網絡的節點集合，Em代表節點之間的鏈路集合；節點按序參加不同數 量覆蓋網，可在終端解碼出不同質量的視頻，用Ki表示節點i參加的覆蓋網層數，Um表示每 層覆蓋網中的效用函數；節點組織的每輪拍賣分為兩個子周期在分配周期內，拍賣組織節點i，即上遊節點 接收到所有其他請求帶寬節點，即下遊節點的報價後，使用一種分配策略出售其上行帶 寬(；；在競拍周期內，下遊節點根據分配到的帶寬，使用一種競拍策略調整自己在下一輪 拍賣中的報價；在覆蓋網m中，下遊節點j向上遊節點i提交的一個報價用巧=(PH) 表示，其中『^代表請求帶寬，？^表示其願意支付的帶寬單價，從上遊節點i接收到的分 配帶寬用表示；當網絡中所有下遊節點的帶寬請求得到滿足，即對任意下遊節點j，有 ，則稱系統達到均衡狀態，此時網絡帶寬達到最優分配； 系統達到均衡狀態所經歷的拍賣輪數稱為收斂速度；(2)優化目標首先對於下遊節點j，其多層覆蓋網優化問題為 Ki 優化目標下遊節點總效用最大化，即效用函數減去競拍代價最大化； 約束條件在每個覆蓋網中，下遊節點向所有上遊節點請求的總帶寬小於該覆蓋網的 傳輸速率；上述優化問題可分解Kj個單層覆蓋網優化問題 max Um(τΤ3)~ J]這樣節點在每個覆蓋網中單獨解決該問題即可；而上遊節點i的優化問題則為 優化目標上遊節點拍賣帶寬所得收入最大化；約束條件1)上遊節點可出售的帶寬總量受其上傳帶寬限制；2)上遊節點分配給下遊節點的帶寬量小於等於下遊節點請求的帶寬量。
3.根據權利要求1所述的可伸縮視頻流在多覆蓋網絡中基於拍賣的帶寬分配方法，其 特徵在於雙向拍賣過程為(1)分配周期上遊節點i接收到來自所有下遊節點的報價後，以價高者得的原則分配自己擁有的上 傳帶寬Ci,直到所有帶寬分完或者所有下遊節點的需求均已滿足為止；(2)競拍周期下遊節點j接收到來自所有上遊節點的分配帶寬後，首先執行「層加入/退出」算法來 決定在下一輪拍賣中參與的覆蓋網層數Kj，然後在每層覆蓋網中，解決單層覆蓋網優化問 題；具體步驟在每層覆蓋網中，節點對所有上遊節點的報價進行調整；首先根據上一輪 拍賣分配到的帶寬調整價格，若所得的帶寬小於請求的帶寬，則加價，反之減價；然後根據 新定的價格決定所要請求的帶寬，這裡使用一種注水算法，向邊際效用最大的上遊節點請 求帶寬；最後判斷新調整的報價是否可以得到滿足，若可以滿足則發送新報價，否則重複以 上價格和請求帶寬調整過程；其中，注水算法的目的在於下遊節點j對各上遊節點(W G /)出價PG—定的情況下，確 定向每個節點i請求的帶寬原則上是向可獲得邊際效用越大的節點請求更多的帶寬，直到請求的總帶寬達到覆蓋網的傳輸速率，即
4.根據權利要求1所述的可伸縮視頻流在多覆蓋網絡中基於拍賣的帶寬分配方法，其 特徵在於「層加入/退出」算法為節點剛加入網絡時，參與所有的覆蓋網絡，即Kj = M ；每一輪拍賣結束，節點根據上一輪 拍賣帶寬的分配情況，決定下一輪拍賣所要參與的覆蓋網層數；如果節點在一個覆蓋網中， 連續數輪拍賣，無法獲得足夠的帶寬，它就退出該層以及優先級比該層更低的覆蓋網；反之， 如果節點連續數輪拍賣，在所有參與覆蓋網中均獲得足夠帶寬，它將新加入一層覆蓋網。
全文摘要
本發明涉及一種可伸縮視頻流在多覆蓋網絡中基於拍賣的帶寬分配方法。本發明採用下述步驟實現多覆蓋網帶寬分配最優化1.將多覆蓋網絡的帶寬分配優化問題轉化為一系列單層覆蓋網絡的帶寬分配優化問題，降低了計算複雜度，便於用分布式算法實現。2.節點間以雙向拍賣的形式，一方面出售自己的上行帶寬給其他節點，另一方面向其他節點購買帶寬，從而解決多覆蓋網中節點的帶寬衝突問題。3.提出一種自適應的「層加入/退出」算法，使節點在進行帶寬出售和競拍的同時，可以根據網絡實時狀況選擇所要參加的覆蓋網層數量，避免帶寬的浪費。
文檔編號H04N7/26GK101895580SQ20101022759
公開日2010年11月24日 申請日期2010年7月15日 優先權日2010年7月15日
發明者熊燕婷, 鄒君妮 申請人:上海大學