[發明專利]可伸縮視頻流的覆蓋網絡分層組播資源最優分配方法

有效

• 申請號: 200910050366.9
• 申請日: 2009-04-30
• 公開（公告）號: CN101547347A
• 公開（公告）日: 2009-09-30
• 發明（設計）人: 鄒君妮;李樂揚;江璐
• 申請（專利權）人: 上海大學
• 主分類號: H04N7/24
• 分類號: H04N7/24;H04N7/26;H04L29/06
• 代理公司: 上海上大專利事務所(普通合伙)
• 代理人: 何文欣

1.一種可伸縮視頻流的覆蓋網絡分層組播資源最優分配方法，其特征在于：第一，采用了一種新的組播性能度量方法——“層伸展度”，測定各視頻層數據傳輸時的端到端時延大??；第二，以端到端的層伸展度最小化為總體目標，對中繼節點的網絡編碼、接收端驅動的流量控制，以及多路徑路由策略進行聯合優化，建立覆蓋網絡下的分層組播資源最優分配模型；第三，針對上述最優分配模型，采用線性規劃方法進行求解；第四，采用一種低復雜度、逼近全局最優解的分布式啟發式算法，構建可伸縮視頻流分發網絡；所述“層伸展度”定義為覆蓋網絡中從源點到各個組播組成員的傳輸路徑長度之和與對應的IP層單播傳輸路徑長度之和的比值；所述對中繼節點的網絡編碼技術和接收端驅動的流量控制的方法是：一方面自適應匹配了可伸縮視頻編碼的層間依賴性；另一方面允許接收節點自行決定所需要的視頻質量，從而使層伸展度總體最小化；所述分層組播資源最優分配模型中，接收節點可自適應地調整接收的視頻層數來避免覆蓋網絡的鏈路資源沖突和網絡擁塞；所述針對最優化分配模型，采用線性規劃方法求解是：以端到端的層伸展度最小化為目標函數，兼顧所有接收端的吞吐量以及可伸縮視頻流解碼的層間依賴關系，以信息流平衡條件、鏈路容量限制、網絡編碼條件為約束函數，建立覆蓋網絡分層組播資源分配的線性規劃優化模型；具體的線性規劃算法如下：

(1)覆蓋網絡模型：將覆蓋網絡抽象為有向圖G(V，E)，其中V是節點的集合，分為源節點集合S和接收節點集合R，E是節點之間鏈路的集合；對于每條鏈路(i，j)都有相應的權值：傳輸帶寬C(i，j)和時延D(i，j)；假定可伸縮視頻流在源節點編碼為M層{l_1，，l₂，...，l_M}，每層數據以速率B_m，通過組播組m進行分發；系數?表示接收節點r是否加入了組播組m，即是否接收第m層數據；?代表r申請加入組播組m，反之?f_m(i，j)代表第m層視頻分發網絡在各條鏈路上消耗的帶寬；假設從源節點到每個接收節點r都有多條傳輸路徑P(r)，矩陣Z^r表示鏈路和接收節點r的傳輸路徑之間的關系，其中Z^r的元素?表示鏈路(i，j)包含于接收節點r的第k條傳輸路徑中；?表示接收節點r接收第m層數據時，其第k條路徑在鏈路(i，j)上消耗的帶寬大小；?和?分別表示第m層視頻分發時，接收節點r在IP層單播網絡和覆蓋網絡上的傳輸時延，s_m表示覆蓋網絡上第m層數據的伸展度；

(2)線性規劃算法?

Subject?to：

優化目標：使總的端到端層伸展度最小化；p_m對應于每一層的權值，滿足：p₁+p₂+...+p_M＝1；考慮到可伸縮視頻編碼的層間依靠性，使p₁＞p₂＞...＞p_M；

約束條件：

1)對應于各個節點的流量平衡限制條件；

2)對應于每條路徑的流量平衡限制條件；

3)規定每條鏈路上的實際帶寬消耗量為所有接收節點在該鏈路上消耗帶寬的最大值；該條件表示在鏈路上采用網絡編碼的限制條件，實現不同節點在同一鏈路上的資源共享；

4)對應于鏈路上帶寬的限制條件；

5)指示鏈路是否被使用；如果?即接收節點r在接收第m層數據時，使用了第k條路徑在的鏈路(i，j)，那么?反之，?

6)規定?為節點r接收第m層數據時所使用的路徑中傳輸時延的最大值；?

所述分布式啟發式算法，它不需要了解整個網絡的全局信息，降低了算法的復雜度；該算法在傳輸低層視頻數據時使用時延小的鏈路，以保證重要信息優先到達接收端，同時增強了覆蓋網絡視頻分發的魯棒性；具體地，每個接收節點按照時延遞增的順序依次選擇傳輸路徑；設定節點r要求接收基本層，它首先選擇時延?最小的第k條路徑，當該路徑的帶寬容量無法滿足基本層的傳輸要求，剩余的流量將由時延次小的路徑來傳遞；基本層的速率分配結束后，更新覆蓋網絡的可用帶寬，繼續構建高層視頻流的分發網絡；第m層視頻分發時，為節點r進行速率分配的過程如下：

步驟1.檢測?的值，若?表示節點r無法接收第m層數據，即停止對第m層的數據分配；

步驟2.若?設定未分配流量R_un等于當前第m層的速率B_m；

步驟3.若R_un＞0，表示第m層的速率分配還未完成，繼續在P(r)中選擇時延最小的路徑k；

步驟4.若?表示路徑k上的帶寬容量能夠承受第m層的傳輸速率；首先，執行路徑k上的流量分配：?其次，更新網絡帶寬，去除已分配掉的容量：?

步驟5.若表示僅依靠路徑k的帶寬量不能完成第m層的數據傳輸；首先，執行路徑k上的流量分配：；其次，更新網絡帶寬：?從P(r)中去除路徑k；最后，更新未分配流量：；返回步驟3，執行至R_un＝0，即完成了第m層的流量分配。?