[發明專利]可伸縮視頻流多速率組播通信的最優速率分配方法

有效

• 申請號: 200910052029.3
• 申請日: 2009-05-26
• 公開（公告）號: CN101568026A
• 公開（公告）日: 2009-10-28
• 發明（設計）人: 鄒君妮;江璐;汪敏;譚沖
• 申請（專利權）人: 上海大學
• 主分類號: H04N7/24
• 分類號: H04N7/24;H04L12/18;H04L12/56;H04L29/06
• 代理公司: 上海上大專利事務所(普通合伙)
• 代理人: 何文欣

1.一種可伸縮視頻流多速率組播通信的最優速率分配方法，其特征在于采用下述步驟實現異構網絡環境中用戶效用的最大化：第一，將多速率多徑路由、中繼節點的網絡編碼和網絡化流量控制進行聯合優化；第二，在選擇最佳組播傳輸路徑和分配各層次視頻流傳輸速率時，兼顧視頻編碼層的碼流優先級問題，不僅為每個視頻編碼層尋求代價最小的傳輸網絡，也同時滿足可伸縮視頻編碼層間依賴性的需求；第三，采用完全分布式的速率分配算法，即采用拉格朗日對偶方法將原始凸優化問題分解為高階和低階兩個子優化問題，既實現資源的最優分配，又便于分布式求解；所述第一步驟中的聯合優化是：每個接收節點在編碼網絡中接收各層次視頻流時，同時選用多條路由路徑；基于這些路徑，將網絡編碼運用在不同接收節點的交叉路徑上，進一步提高網絡的吞吐量；所述第二步驟中的兼顧視頻編碼層的碼流優先級問題是：在選擇路由和進行流量分配時，使最低層的傳輸代價最小，同時保證從低層到高層的傳輸代價依次遞增，以滿足接收端的解碼要求；所述第三步驟中的完全分布式速率分配算法是：利用拉格朗日釋限和對偶方法，將原始凸優化問題分解為高階和低階兩個子優化問題，允許每個網絡節點和每條鏈路利用本地局部信息進行速率的動態調整和更新，以分布式方式實現鏈路傳輸速率的全局最優化分配；以所有用戶整體效用最大化為目標函數，兼顧可伸縮視頻流解碼的層間依賴關系，以信息流平衡條件、鏈路容量限制、網絡編碼條件為約束函數，建立多速率組播通信的資源分配凸優化數學模型；具體方法如下：

(1)網絡模型的建立：將網絡抽象為有向圖G(V，E)，其中V是節點的集合，分為源節點集合S、中間節點集合N和接收節點集合R，E是節點之間鏈路的集合；對于每條鏈路e∈E都對應有限的傳輸帶寬C_e；假定可伸縮視頻流在源節點編碼為M層{l₁，l₂，...l_M}，第m層數據以速率B_m通過組播組m向|R_m|個接收點分發；假設從源節點到每個接收節點r都有多條傳輸路徑P(r)，表示接收節點r在接收第m層數據時，第j條路徑上分配的流量大小；f_m，e表示第m層數據流在鏈路e上占有的帶寬；矩陣Z^r表示鏈路和接收節點r的傳輸路徑之間的關系，其中Z^r的元素表示鏈路e包含于接收節點r的第j條傳輸路徑中；采用普遍運用的代價函數ρ(·)，定義為

(2)建立凸優化數學模型

目標問題P1：maximizeΣr∈RΣm∈MUm(Σj∈P(r)xm,jr)]]>

約束條件：

1)Σj∈P(r)zj,er·xm,jr≤fm,e,∀e∈E,∀m∈M,∀r∈R;]]>

2)Σm∈Mfm,e≤Ce,∀e∈E;]]>

3)Σj∈P(r)ρ(xm,jr)≤Σj∈P(r)ρ(xm+1,jr),∀m=1,...,M-1,∀r∈R;]]>

4)bm≤Σj∈P(r)xm,jr≤Bm,∀m∈M;∀r∈R;]]>

5)xm,jr≥0,∀j∈P(r);∀m∈M,∀r∈R.]]>

優化目標：使異構網絡環境中的用戶效用總和最大化；

約束條件：

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

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

3)確保各層次視頻流的傳輸代價從低層到高層依次遞增；

4)對應于各個接收節點在每條路徑上的流量限制條件；

5)規定各個接收節點在每條路徑上的流量必須大于零；

(3)將原始凸優化問題分解為以下低階和高階兩個子優化問題：

目標問題P2a：maximizeX∈CΣr∈RΣm∈MUm(Σj∈Pxm,jr)]]>

約束條件：

1)Σj∈P(r)zj,er·xm,jr≤fm,e,∀e∈E,∀m∈M,∀r∈R;]]>

2)Σj∈P(r)ρ(xm,jr)≤Σj∈P(r)ρ(xm+1,jr),∀m=1,...,M-1,∀r∈R.]]>

目標問題P2b：maximizef≥0U^m(f)]]>

約束條件：Σm=Mfm,e≤Ce,∀e∈E.]]>

(4)兩個子優化問題的分布式求解算法：

①低階子優化問題——目標問題P2a的求解步驟如下：

步驟1：定義拉格朗日對偶：

L(X,p,q)=Σr∈RΣm∈MUm(Σj∈P(r)xm,jr)]]>

-Σr∈RΣm∈MΣe∈Epm,er(Σj∈P(r)zj,er·xm,jr-fm,e)-Σr∈RΣm=1M-1qmr[Σj∈P(r)ρ(xm,jr)-Σj∈P(r)ρ(xm+1,jr)]]]>

其中，和是拉格朗日乘子；

步驟2：定義拉格朗日對偶函數：g(p,q)=supxL(X,p,q);]]>

步驟3：定義對偶問題：minimizep≥0,q≥0g(p,q);]]>

步驟4：采用原始-對偶算法，同時更新原始變量和對偶變量，逐步逼近最優點，其中α(t)、β(t)和γ(t)是正的步長值，[·]⁺表示取正值的運算；

xm,jr(t+1)=[xm,jr(t)+x·m,jr]+=[xm,jr(t)+α(t)∂L(X,p,q)∂xm,jr(xm,jr(t))]+]]>

pm,er(t+1)=[pm,er(t)+p·m,er]+=[pm,er(t)-β(t)∂L(X,p,q)∂pm,er(pm,er(t))]+]]>

qmr(t+1)=[qmr(t)+q·mr]+=[qmr(t)-γ(t)∂L(X,p,q)∂qmr(qmr(t))]+]]>

其中，流量分配大小X以及拉格朗日乘子p和q的偏導數為：

p·m,er=β(pm,er)[Σj∈P(r)zj,er·xm,jr-fm,s]]]>

②高階子優化問題——目標問題P2b的求解過程

定義為滿足目標問題P2a中約束條件的最優化拉格朗日乘子，定義f_e＝[f_1，e，…，f_M，e]、f＝[f₁，…，f_E]^T以及

Fe={fe|fm,e≥0forallmandΣm∈Mfm,e≤Ce},e∈E,]]>

F表示F_e(e∈E)的笛卡爾乘積，于是目標問題P2b可由以下的次梯度方法進行求解：

fm,e(t′+1)=[fm,e(t′)+μ(t′)·p^m,e(fm,e(t′))]F.]]>