無線多跳網絡中SVC 視頻流傳輸的分布式優化方法

由 磊，雷建軍，王丕超

(天津大學電子信息工程學院，天津 300072)

經過可伸縮編碼(scalable video coding，SVC)的視頻流包含1 個基本層和多個增強層，可以在一定程度上根據所處的傳輸環境實現靈活的速率和視頻質量的自適應調整[1-2]．近年來，SVC 視頻在無線網絡中的傳輸問題得到廣泛關注．但目前的研究主要集中在單跳無線網絡[3-6]，如蜂窩網中基站可以集中式地控制整個小區的資源調度和為多個用戶選擇SVC 視頻流傳輸的內容．無線多跳網絡(如無線網格網和無線傳感器網絡[7-8])具有成本低、部署快、可靠性高以及可覆蓋邊緣或環境惡劣的區域等優點，是實現未來無處不在的接入網和物聯網的潛在技術之一．然而，由于節點功率受限、上層可用網絡傳輸容量(能力域)與底層資源分配的緊耦合性，以及要求傳輸協議具有可擴展性和服務質量保證等特點[9]，SVC 視頻在無線多跳網絡中傳輸面臨著更多挑戰．本文研究無線多跳網絡SVC 視頻流傳輸中2 個重要性能參數(網絡功率消耗和傳輸視頻質量)的最優權衡(trade-off)及其分布式優化的實現問題．通過對原問題進行對偶分解和采用次梯度算法求解，實現了底層資源分配(帶寬和功率)與上層SVC 視頻流傳輸內容選擇的最佳匹配，同時得到了一個可分布式執行的跨層傳輸優化算法．

1 系統模型和問題描述

1.1 系統模型和假設

一個無線多跳網絡的拓撲可以用有向圖G =(V,E)來表示，其中V 表示節點集合，而E 表示無線鏈路集合．用S 表示發送SVC 視頻的源節點集合．所有的SVC 視頻都需要發送到某個已知的匯聚(sink)節點上．集合V、E 和S 的元素分別用n、l 和m表示，其元素數分別為N、L 和M．另外，節點i 和節點j 之間的鏈路用(i，j)表示．

由于無線信道的干擾，同時發送信息的鄰近鏈路必須分配不同的頻帶以避免干擾，而在相鄰較遠的鏈路上可以進行頻率重利用．本文在相同的頻帶上采用節點獨占干擾模型(node exclusive interference model)[10]，該模型只允許節點的一條鏈路在某段頻帶上發送或接收信息．定義網絡中不能在同一頻帶上傳輸的鏈路組成一個互干擾鏈路集．對于節點獨占干擾模型來說，網絡中共有N 個互干擾鏈路集．本文的優化方法很容易應用到其他的干擾模型中．

定義一個N × L鏈路互干擾矩陣Χ ．如果鏈路l屬于互干擾鏈路集n，則xnl= 1，否則 xnl= 0．假設網絡的可用頻帶帶寬為b，定義 W =[ w1,…,wL]T為各無線鏈路的帶寬分配矢量，則W 必須滿足

其中 B =[b,…,b]T．

定義 P =[ p1,…,pL]T為各無線鏈路上功率分配矢量，hl為鏈路l 的無線信道增益．本文假設在整個優化過程中無線鏈路的信道增益不發生變化．鏈路l 的傳輸速率 fl由分配給它的功率和帶寬決定，可以根據香農公式計算為

式中Θ為鏈路速率與香農公式間的差距(由于采用一定的信道編碼)；N0為接收端噪聲功率譜密度．用Γ表示網絡資源分配和鏈路速率矢量 F=[ f1,…,fL]T的可行取值域，則有

SVC 是一種可伸縮的分層視頻編碼，可以通過丟棄低優先級的增強層數據來適應可變的傳輸環境，達到最優率失真性能[1-2]．SVC 標準允許空間、時序和質量上的編碼可伸縮性．本文采用質量可伸縮編碼中的“ 中等粒度可伸縮(medium grain scalable ，MGS)編碼”．關于MGS 視頻編碼讀者可參考文獻[1-2]．假設SVC 源節點m 需要發送的視頻包含 Im個幀，每個幀被編碼成1 個基本層和T 個MGS 層．定義為節點m 的SVC 視頻幀傳輸策略矢量，其中= 0表示幀 z 只發送基本層，而= t (t ≤T)表示幀z 發送基本層和前t 個MGS 層．用峰值信噪比(peak signal-to-noise ratio，PSNR)作為視頻質量指標．SVC 視頻源m 的PSNR(qm)是Πm的函數，即

1.2 跨層傳輸優化問題表達

所有SVC 視頻需要從源節點經過多跳無線鏈路傳送到sink 節點上．分配給各個鏈路的傳輸速率必須能夠承載(即大于或等于)經過它們的視頻流的速率．本文采用多徑路由，即允許視頻流在所有可能的端到端路徑上傳輸．定義一個N × L的節點-鏈路矩陣H，hnl= 1表示節點n 是鏈路l 的發射節點，而 hnl= ?1表示節點n 是鏈路l 的接收節點，否則 hnl= 0．定義=[ r1,…,rN]T為所有節點的源速率矢量，其中rn= 0,n ? S．在多徑路由的網絡中，流出某個節點的數據速率與流入的數據速率之差必須大于該節點的源速率[10]，即網絡流必須滿足如下條件：

在無線多跳網絡中傳輸視頻信息，總是希望用最小的傳輸功率獲得盡可能好的視頻質量．然而，這2個指標不可能同時滿足，二者之間需要權衡考慮．為了在優化中體現這種權衡，本文采用如下的優化目標：γTQ - ηTP，其中，γ 和η 分別是sink 節點接收到的SVC 視頻質量和無線鏈路功率消耗的加權系數矢量，它們的值代表2 個優化參數的重要程度．可以把η 看作是功率的 “成本”，而γ 為接收相應SVC 視頻質量所獲得的“收益”，因此，SVC 視頻在無線多跳網絡中傳輸的跨層權衡優化問題可以表述為

由于SVC 視頻的率失真函數和鏈路速率函數都是凸函數，因此問題(5)是凸優化問題，可以采用經典的非線性優化算法(如內點法)來求解[11]．然而，這些集中式的算法要求網絡配置計算性能強大的計算節點，并在優化之前需要所有節點把各自SVC 視頻信息、所有鏈路的信道狀態以及功率配置發送到該節點，而優化結果也需要向全網分發，這種機制會產生大量的控制消息，大大降低了無線多跳網絡的運行效率和可擴展性．分布式算法是無線多跳網絡多媒體承載邁向實際應用的關鍵．

2 問題求解和分布式算法

通過對約束條件(1)和(4)引入拉格朗日乘子μ= [μ1, …,μN]T和λ= [λ1, …,λN]T，可以獲得問題(5)的拉格朗日函數為

記

則問題(5)的對偶問題可以表示為

這里，λ和μ變成了對偶問題的優化變量．由于問題(5)是凸優化問題，因此可以通過求解其對偶問題(7)獲得原問題的最優解(即對偶間隔為0)[12]．然而，雖然問題(7)是一個凸優化問題，但其目標函數卻不是嚴格可微分的函數．這時可以通過次梯度(subgradient)法來搜尋其最優解[12]．假設在第i 步循環中對偶變量為λ(i)和μ(i)，求解式(6)中的最大化問題，獲得最優的原變量 F?、和W?，則第i＋1 步的對偶變量按照如下方式更新，即

式中ΗF??和B ?ΧW?分別是函數 D(λ ,μ)在λ(i)和μ(i)處的次梯度．

在每一步更新對偶變量時，需要首先對對偶目標函數(6)中的最大化問題求解．對于給定的對偶變量λ(i)和μ(i)，該最大化問題可以分解為如下2 個獨立的子問題：

問題(10)是SVC 視頻流傳輸策略選擇問題．對于給定的γ 和λ ，各個SVC 視頻源傳輸策略選擇相互獨立．因此，問題(10)可以進一步分解為M 個獨立的子問題，即

每個子問題可以在對應的SVC 視頻源節點獨立求解．每個源節點根據幀之間的預測關系和增強層的重要程度為每一幀選擇相應的MGS 層，即Πm，使式(12)取得最大值．本文采用基于MGS-temporal 層的選擇策略[2]．這種策略同時考慮幀所在的時序增強層和每幀中MGS 層的重要程度．由于幀所在的時序增強層越高對視頻質量貢獻越低，而每幀中MGS 層越高也對視頻質量貢獻越低，因此基于MGS-temporal層的選擇策略在確定 Πm時，按照如下順序選擇SVC視頻的傳輸內容：較低時序層的低MGS 層、較低時序層的高MGS 層、較高時序層的低MGS 層、較高時序層的高MGS 層，直到γmqm(Πm) ?λmrm(Πm)取得最大值．采用這種選擇策略，式(12)的目標函數是Πm的凸函數，因此對于確定的λm和γm總能找到最大值.

問題(11)是網絡層資源分配問題，可以進一步分解為每個鏈路上的資源分配子問題，即

由于問題(13)不是變量 lw 和 lp 的嚴格凸函數，為了容易求解，本文采用文獻[13]的方法在式(13)的目標函數中減去一個很小的正則化項(regularization term)ε，即

如果0ε→，則正則化后的最大化問題(14)的最優解趨近于問題(13)的最優解．正則化后很容易求得每個鏈路子問題(14)的解為

由上述求解過程可以得到無線多跳網絡SVC 視頻流傳輸的分布式跨層優化算法．

初始化根據網絡應用要求和運營策略等確定權值γ 和η；設置對偶矢量λ(0)和 μ (0)各個分量的初值，并保存在相應的節點中；設置常量ε、固定步長θ和δ；告知各節點網絡可用頻帶帶寬b；發射節點測量并保存鏈路的信道增益 hl．

算法循環在第i 步執行下述操作：

(1) 每個節點n 向鄰居節點廣播對偶變量λn(i)和μn(i)；計算鏈路l 的發射節點的αl和βl值；

(2) 每個SVC 視頻源節點m 采用基于MGStemporal層的選擇策略確定 Πm，使式(12) 中

(3) 每個鏈路的發射節點根據式(15)和式(16)為該鏈路分配功率和帶寬；

(4) 每個節點根據式(8)和式(9)更新其對應的對偶變量．

上述過程循環執行，直到收斂．

網絡各節點和鏈路根據上述計算結果傳輸SVC視頻信息．

可以看出，上述算法是通過網絡中所有節點協同工作，以達到問題(5)的最優解．算法只需要在相鄰節點間交換對偶變量，而各節點根據各自SVC 視頻特點或鏈路狀態獨立地對相應子問題進行求解．分布式算法避免了集中式算法在全網傳播控制信息和狀態信息的問題．同時，該分布式優化算法實際上是對偶問題(7)的次梯度算法的應用．由于原問題(5)是凸優化問題，在得到問題(7)最優解的同時，也獲得了原問題優化變量的最優值．另外，該算法同時分配底層資源、確定無線鏈路上的流速率和上層SVC 視頻的傳輸內容，使之達到最優匹配．因此，所提出的無線多跳網絡SVC 視頻傳輸算法是一個分布式的、能夠獲得最優目標值的、跨層協同的SCV 視頻流傳輸算法．

對于一個集中式算法來說，所有網絡節點必須把所有算法相關信息發送到執行集中式計算的節點(如sink 節點)上并且這些信息可能需要多次轉發．越接近sink 節點的轉發節點所承載的控制信息越多．假設某個與sink 節點相鄰的節點x 需要轉發τM個SVC 源節點的信息和ζN個網絡節點的信息(0 ≤τ,ζ≤1)．SVC 源節點的信息包括SVC 視頻每個圖像組(group of pictures)包含不同時間增強層和MGS 層的PSNR 值和數據量，假設這些參數總個數為A．可見如果SVC 視頻較長，A 是非常大的．假設每個節點需要發送的信息的參數個數為B(這主要包括節點可用功率值、所有鏈路的發射距離、鏈路的連接和相互干擾情況)，則節點x 需要承載τMA +ζNB 個控制信息參數的轉發．一方面這個值非常大，另一方面隨著網絡規模的增大、SVC 源節點數以及SVC 視頻長度的增加，這個值也會快速增大．另外，集中式算法還要把最終計算結果進行全網分發，因而，集中式算法控制信息較高且可擴展性差．而本文所提出的分布式算法中，控制信息只在相鄰節點之間傳遞，而且每個循環中，節點n 只有需向其所有鄰節點一次性廣播2 個參數λn和μn．假設算法循環次數為I ，每個節點需要廣播2I 個信息．一方面該算法能夠快速收斂，因而每個節點需要發送的參數個數遠小于上述集中式算法．另一方面，該值與網絡規模和拓撲、SVC源節點數、SVC 視頻長度、數據流發送路徑等均無關，因而具有很好的可擴展性．

3 仿真結果與分析

3.1 仿真場景與參數

本文采用如圖1 所示的無線多跳網絡拓撲驗證所提出的算法性能．該拓撲包含16 個無線節點，均勻分布在150,m×150,m 的區域內．設置節點1、4 和13 為SVC 視頻源節點，而右上角的節點16 為匯聚(sink) 節點．本文采用典型視頻“silence of the lambs”、“NBC news” 和“sony demo” 分別作為3 個源節點所需發送的視頻．這3 個視頻的SVC-MGS 編碼的trace 文件可以從網站[14]下載．設網絡可用帶寬為b＝200,kHz，設 hl/ΘN0=K，其中常數 K = 2 ×1 010，dl為鏈路l 發射和接收節點的距離(單位為m) ．

圖1 仿真拓撲Fig.1 Topology for the simulations

為了在數值仿真中減少式(14)中正則化項的影響，需要對帶寬和速率進行歸一化處理，即b′=b/(2×105)，W′=W/(2 ×105)，R′= R/(2 ×105)和=/(2 ×105)，而常數變為K=105，但功率和PSNR 值不變．設ε=0.05．對偶變量的初值設置為1．步長θ=0.01，δ=0.005．

3.2 算法的收斂性

為了方便仿真結果顯示，設加權矢量γ和η的各自分量相等，且γm/ηl=φ．在每次優化中比值φ是一個給定的常數．圖2 顯示了φ=3時SVC 視頻的平均PSNR、網絡總功率消耗以及鏈路(7，11)所分配的帶寬隨著循環次數的變化情況．可見，采用所提出的分布式算法，上述優化變量可以在300 多次循環后逐步收斂到穩定值，即平均PSNR 為37.018,dB，總功率消耗為2.253,W，鏈路(7，11)所分配帶寬為63.46,,kHz．這說明所提出的分布式算法能夠快速收斂，而由第2節分析可知收斂所達到的穩定值即是問題(5)的最優值．快速收斂的分布式協議能夠減少無線多跳網絡的控制信息交換開銷和流傳輸的啟動延遲．

圖2 算法收斂性Fig.2 Convergence of the algorithm

3.3 不同加權比值下的優化結果

所提出算法在不同加權值比值φ的優化結果如圖3 所示．本文的SVC 視頻傳輸算法是“內容感知(content-aware)”的，即根據SVC 視頻內容的重要程度確定是否發送．這可以與非內容感知(contentblind)的機制比較[15]，該機制以源速率效用函數(本文采用lnmr)最大化為優化目標，其優化結果如圖3中的 “基于速率的優化”(注意基于速率的優化其底層資源分配仍然采用第2 節的方法) ．

圖3 優化結果與比較Fig.3 Optimization results and comparison

圖3中每一點對應一個確定φ值的平均PSNR和功率消耗最佳權衡值(trade-off)．增大φ值相當于提高了式(5)中SVC 視頻質量的權值或降低了功率的“成本”，因此優化算法可以分配更多的功率以提高傳輸視頻的質量．相反，降低φ值相當于提高了功率成本，算法相應地降低SVC 視頻的傳輸質量以節省無線多跳網絡的功率和提高網絡有效運行時間．實際φ值(或加權矢量γ和η)的設置依賴于具體的應用和網絡管理策略．另一方面，采用本文的優化框架和底層資源分配機制，基于速率的優化結果與基于內容感知的優化具有相似的趨勢．但由于不考慮SVC視頻內容對PSNR 影響的差異，而直接對其速率效用函數進行優化，其優化性能明顯低于內容感知的機制．從圖3 可以看出，基于速率的優化在相同的功率消耗下，所獲得的平均視頻質量要低于基于內容感知的機制，或者說要得到相同的平均視頻質量，需要消耗更多的網絡功率．

4 結 語

本文提出了一種無線多跳網絡中SVC 視頻流的分布式傳輸優化算法．該算法是基于非線性優化中的對偶理論，用次梯度算法對傳輸質量和功率消耗的跨層權衡優化問題的對偶問題進行求解的過程中推導出來的．分布式算法把問題分解為可以在對應無線節點上獨立求解的帶寬和功率分配子問題以及SVC視頻內容選擇子問題，通過節點的本地信息交換和在網協同工作，獲得相關優化參數的最優值，避免了控制信息的集中式收集和全網分發．本文所提出的算法能夠為無線多跳網絡的設計和實際部署提供參考依據．

本文所提出的算法中傳輸質量和功率的加權系數比值決定了SVC 視頻流傳輸和網絡功率消耗的最優權衡點．今后將進一步研究這些參數與無線多跳網絡的能量管理策略、有效運行時間以及多媒體的服務質量保證等的相互關系和影響．

［1］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.

［2］Seeling P，Reisslein M. Video transport evaluation with H.264 video traces[J]. IEEE Communications Surveys and Tutorials，2011，14(4)：1142-1165.

［3］Pourmohammadi-Fallah Y，Mansour H，Khan S，et al.A link adaptation technique for efficient transmission of H.264 scalable video over multirate WLANs[J]. IEEE Transactions on Circuits and Systems for Video Technology，2008，18(7)：875-887.

［4］Mansour H，Fallah Y P，Nasiopoulos P，et al. Dynamic resource allocation for MGS H.264/AVC video transmission over link-adaptive networks[J]. IEEE Transactions on Multimedia ， 2009 ， 11(8)： 1478-1491.

［5］Zhang Honghai ， Zheng Yanyan ， Khojastepour Mohammad A，et al. Scalable video streaming over fading wireless channels[C]// IEEE Wireless Communications and Networking Conference. Budapest，Hungary，2009：1-6.

［6］孫剛友. 無線網絡中H.264/SVC 視頻傳輸的QoS 保障機制[J]. 電信快報：網絡與通信，2011，26(7)：41-44.Sun Gangyou. QoS guarantee mechanism for H.264/SVC video transmission[J]. Telecommunication Information：Network and Communication，2011，26(7)：41-44(in Chinese).

［7］Akyildiz I F，Wang Xudong，Wang Weilin. Wireless mesh networks：A survey [J]. Computer Networks，2005，47(4)：445-487.

［8］Yick J，Mukherjee B，Ghosal D. Wireless sensor network survey[J]. Computer Networks，2008，52(12)：2292-2330.

［9］由 磊. 無線多跳網絡跨層設計與優化的相關理論和算法研究[D]. 北京：北京郵電大學電子工程學院，2009.You Lei. Research on the Theory and Algorithms of Cross-Layer Design and Optimization for Wireless Multihop Network[D]. Beijing：School of Electronic Engineering，Beijing University of Posts and Telecommunications，2009(in Chinese).

［10］Lin Xiaojun，Shroff N B. The impact of imperfect scheduling on cross-layer rate control in multi-hop wireless networks [C]//IEEE International Conference on Computer Communications. Miami，Florida，USA，2005：1804-1814.

［11］Bertsekas D P. Nonlinear Programming[M]. Belmont，MA：Athena Scientific，1999.

［12］Boyd S，Xiao L，Mutapcic A. Subgradient Methods[EB/OL]. http ： //trace.eas.asu.edu/videotraces2/mgs/index.php，2012-01-06.

［13］Bertsekas D P，Tsitsiklis J N. Parallel and Distributed Computation ： Numerical Methods[M]. Belmont ，MA，USA：Athena Scientific，1997.

［14］Reisslein M，Karam L J，Seeling P，et al. Video Traces for Network Performance Evaluation[EB/OL]. http：//trace. eas. asu. edu/videotraces2/mgs/index. php，2012-01-06.

［15］Palomar D P，Chiang M. A tutorial on decomposition methods for network utility maximization[J]. IEEE Journal on Selected Areas in Communications，2006，24(8)：1439-1451.