基于負載自適應的Ad Hoc網視頻傳輸隊列調度算法

李 悅，陳衛衛，單 勝，丁良輝

(1.海軍裝備研究院，北京 100616；2.中國電子系統工程公司，北京 100141；3.國家電網公司信息通信分公司，北京 100761；4.上海交通大學 電子工程系，上海 200240)

?

基于負載自適應的Ad Hoc網視頻傳輸隊列調度算法

李 悅1，陳衛衛2，單 勝3，丁良輝4

(1.海軍裝備研究院，北京 100616；2.中國電子系統工程公司，北京 100141；3.國家電網公司信息通信分公司，北京 100761；4.上海交通大學 電子工程系，上海 200240)

移動終端多媒體業務的發展目前已經成為終端發展的必然趨勢。如何在移動終端構成Ad hoc網絡時有效地進行視頻傳輸是無線網絡研究的熱點之一。提出了一種基于負載狀況的跨層優化方案，其基本思想是結合應用層視頻編碼的特點和接入層的網絡負載和資源的情況聯合進行優化。在特定的資源下通過概率接入的方法對重要性更高的數據包進行更優先的接入。仿真結果顯示，在網絡處于高負載、多跳傳輸等場景下，提出的方案視頻傳輸質量PSNR值提升3 dB以上。相對于傳統調度算法，系統時延也可以大幅度降低。

負載自適應；無線自組網；視頻傳輸

1 背景介紹

Ad Hoc網絡可以在任何時刻、任何地點，不需要硬件基礎網絡設施的支持，快速構建起一個移動通信網絡。它的建立不依賴于現有的網絡通信設施，具有一定的獨立性；Ad Hoc網絡沒有嚴格的控制中心；所有節點的地位平等，節點可以隨時加入和離開網絡；任何節點的故障不會影響整個網絡的運行，具有很強的抗毀性。Ad Hoc 網絡的這些特點使得它能滿足許多應用領域的特殊需求，如軍事通信網絡、應急救災等。

移動終端多媒體業務的發展目前已經成為終端發展的必然趨勢，目前無線視頻會議、無線視頻監控以及無線視頻對話等多媒體應用已經越來越多地出現在人們的生活和工作中，同時這些應用的需求也在飛速增長[1]。但是視頻數據在無線網絡中傳輸與有線傳輸有很大的不同[2-3]。首先，由于節點的移動以及無線信道的變化效應，無線鏈路傳輸不夠穩定，對于網絡的抖動有較大影響。其次，由于無線信道具有較高的誤碼率，對于通信質量有一定影響。再次，無線信道在一定的傳輸環境下信道共享，容易造成網絡擁塞，使得網絡延時較大。

而視頻數據傳輸的特點決定了其對于網絡通信質量的要求較高，視頻數據在傳輸時具有如下特征。首先是數據流海量性，視頻文件的數據量一般較大，因此視頻數據傳輸需要的帶寬較大；其次是流量不規則性，當今視頻壓縮技術采用預測編碼方式，對于不同視頻數據源的壓縮率有一定改變，使得視頻數據量隨著壓縮率改變；最后是傳輸需要實時性，視頻數據往往對于時延有一定的要求，這對網絡傳輸的時延和抖動都有較高的要求。由于上述特點，視頻數據對無線網絡傳輸性能的要求往往較高，這些性能主要包括在數據丟包率、網絡吞吐量、傳輸延時和抖動等。雖然視頻數據對于突發的傳輸錯誤能夠承受，但其對帶寬的要求仍然比較高。因此，無線網絡傳輸的一系列問題加上視頻數據的較高要求，使得無線網絡很難為多媒體通信提供比較可靠的服務質量(Quality of Service，QoS)。

在無線網絡中，各節點共享無線帶寬，共同接入無線信道。因此如何有效分配信道則對網絡的整個吞吐量和傳輸性能有著重要影響。因此在無線網絡中，媒體接入控制協議(MAC)起著至關重要的作用。于無線自組網來說，由于沒有中心節點，因此不能采用點協調功能的方式實現媒體接入調度。因此在無線自組網中，一般采用基于競爭的接入方式，因此分布式控制(Distributed Coordination Function, DCF)在無線自組網協議設計中得到廣泛應用[4]。為了提升網絡吞吐量，提高業務的傳輸質量，IEEE802.11協議組在IEEE802.11e標準中提出了增強分布式控制EDCA(Enhanced Distributed Channel Access)，利用不同優先級和接入參數的定義和調整提升傳輸效率[5]。EDCA協議對業務進行了區分，提供了8種用戶優先級UP(User Priority)和4種接入類別(Access Category，AC)。4個接入類別分別對應4種類別的業務類型數據，其優先級別從高到低排列分別是：語音業務(AC_VO)、視頻業務(AC_VI)、盡力而為業務(AC_BE)和背景業務(AC_BK)。對于不同優先級的業務給予不同的接入機會，使得網絡資源要求更高的業務更有機會接入信道，從而在一定信道資源的情況下能夠擁有更高的服務質量。IEEE802.11e的調度模型如圖1所示。

隨著視頻編碼技術的飛速發展，分層編碼技術，又稱為可伸縮性編碼技術，在諸如MPEG-4以及H.264、H.264/SVC編碼標準中廣泛應用[6-7]。這種編碼技術通過幀內幀間預測技術的方法去除大量的冗余信息以得到較高的壓縮率。原始視頻可以被編碼成一個基本層和一個或者幾個增強層。只需對基本層的解碼即可恢復一個質量可以接受的視頻。通過對更多增強層的數據進行解碼便對視頻的質量進一步提高。因此這樣的編碼方式對于無線視頻傳輸而言，大大提高了無線視頻傳輸的質量[8]。

結合視頻編碼中的分層編碼技術與IEEE802.11的ED

圖1 典型的自組網跨層資源調度框圖

CA技術，研究人員提出了很多跨層優化傳輸方法[9-14]。文獻[13]中提出了靜態映射算法，利用編碼的分層特點，將不同重要性的數據幀映射到不同的隊列中去，將視頻編解碼過程和物理層傳輸過程聯合優化；文獻[14]中，作者提出了基于MPEG-4的一種動態映射算法。其目的是利用分層編碼結構中不同類型數據的情況，并根據隊列實時被占用的情況，動態地分配不同數據幀到不同的隊列中去。

但是，上述研究都沒有考慮到網絡負載的動態變化情況，不能根據網絡負載自適應地調整調度算法，充分利用網絡資源，提高視頻質量。針對此問題，本文提出了一種基于負載自適應的動態調度算法，結合應用層視頻編碼的特點和接入層網絡負載和資源的情況聯合進行優化。在特定的資源下通過概率接入的方法對重要性高的數據包進行優先接入。

2 相關研究進展

2.1 分層視頻編解碼技術

目前，關于可伸縮性的要求大致有3種：時間可伸縮性、空間可伸縮性以及信噪比可伸縮性。對于空間可伸縮性的實現，是將輸入的原始視頻序列進行下采樣，得到低分辨率的序列，然后再對此序列變換后的系數進行量化編碼，即可得到基本層碼流。將基本層重構信息與原始視頻信息的誤差進行編碼即可得到增強層碼流。對于時間可伸縮性的實現，是將視頻序列幀分為兩組，對一個組的序列進行編碼得到基本層，對于另一個序列進行編碼得到增強層。基本層的碼率相對較低，而增強層的碼率相對較高。對于信噪比可伸縮性則是在變換系數量化過程中實現的，基本層采用量化步長相對較大，得到的碼率也相對較低。而增強層則是對基本層殘差數據采用更小的步長進行量化，從而得到更加精細的系數量化結果。本文的研究中，采用H.264/SVC的編碼方法，并僅采用了時間可伸縮性，但是所提出的方法對于其他的編碼方式仍然可行。數據幀通過時間可伸縮性區分的視頻包數據類型包括T0，T1，T2。其關系如圖2所示。

圖2 H.264/SVC數據流結構

2.2 動態映射算法

在基于EDCA的視頻傳輸系統中，視頻數據是接入到第2個接入類別AC_VI中，其接入優先級僅次于對于傳輸性能要求更高的音頻服務數據AC_VO隊列，而高于最大努力型的業務數據AC_BE、背景業務數據AC_BK。與DCF相比，EDCA從一定程度上提高了視頻數據的傳輸質量。但是這種機制將所有類型的視頻數據統一處理，在網絡資源緊缺的情況下將會面臨數據量過大，從而導致網絡擁塞丟包和不必要的時延。同時由于很多基本層幀丟失，造成接收到的增強層數據包即使正確接收也無法正確解碼，使得視頻的傳輸質量嚴重下降。

靜態映射算法[13]，利用編碼的分層特點，將不同重要性的數據幀映射到不同的隊列中去。將重要性高的基本層數據幀映射到AC[2]，將重要性低的視頻數據幀映射到低優先級的隊列。靜態映射方法在網絡負載較重的時候對于視頻的傳輸質量有一定的提升作用，但其固定的映射方式顯然不夠靈活，不能對網絡負載的變化做出適時的反應。另外在網絡負載較輕時，其表現并不如傳統的EDCA機制，尤其是延時相對較長。

無線自組網受到無線傳播環境的影響，信道狀況一般有較大的波動，每個節點的出站速率會隨之變化。同時由于網絡中沒有中心協調節點，無法做到實時的資源協調和分配，從而造成每個節點的負載和隊列情況也是動態變化的。針對自組織網絡的特征，動態映射算法[14]在一定程度上解決了靜態映射方法存在的問題。動態映射算法利用分層編碼輸出數據的重要性信息，并結合隊列實時被占用的情況，動態地將數據幀分配到不同的隊列中去。一個典型的動態映射算法如下所述：

Step1：在包頭添加了服務類型信息(Type of Service，TOS)用來記錄視頻數據幀的類型，應用層將這個信息傳遞到網絡層和媒體接入層。

Step2：所有類型的視頻數據包都按照EDCA的方式默認映射到AC[2]中。

Step3：媒體接入層對網絡負載情況進行檢測，當AC[2]被占用長度增大的情況下，視頻數據包將以一定的概率被降至低優先級級的隊列中去。對于視頻編碼來說，降隊列概率與數據包重要性直接相關。

Step4：為了防止隊列長度進一步增大，降隊列概率在隊列長度的特定范圍內隨著隊列長度的增加而線性地增加，即

(1)

(2)

算法框圖如圖3所示，動態映射算法通過引入利用分層編碼結構中的不同類型數據的情況，并根據隊列實時被占用的情況，動態地將不同數據幀分配到不同的隊列中去，可以較好地解決自組織網絡中的視頻傳輸問題。

圖3 動態映射算法程序流程圖

3 基于負載自適應的隊列調度算法

動態映射算法雖然從某種程度上提高了接收視頻的傳輸質量，但是仍然有許多缺點。首先僅僅采用AC[2]的隊列占用長度顯然對于網絡負載情況和外部環境情況不能很好地體現。其次，采用降隊列概率的方法雖然能夠從一定程度上緩解負載過重的情況，但當網絡持續負載較重的情況下，這種方式只能暫時緩解問題，當負載過重的情況下，AC[2]或者其他隊列仍然會產生溢出，從而將重要性較高的數據包丟掉，對視頻傳輸質量造成較大的影響。再次，降隊列概率的最終值即分配概率為固定值，網絡負載很重的情況下并不能得到最優的結果，而且當網絡環境變化的情況下也不能及時地調節，從而對于性能會產生不良的影響。

3.1 算法描述

針對上述問題，提出了基于負載自適應的動態映射算法(Load Adaptive Dynamic Mapping，LADM)，算法框圖如圖4所示。

圖4 負載自適應動態映射算法程序流程圖

算法基本描述如下：

步驟2:所有類型的視頻數據包都按照EDCA的方式默認映射到AC[2]中。

步驟3：媒體接入層對網絡負載情況進行檢測，當AC[2]被占用長度增大的情況下，視頻數據包將以一定的概率被降至低優先級級的隊列中去。對于視頻編碼來說，B幀應該具有最大的降隊列概率，而I幀則應該有最小的降隊列概率。

步驟4：降隊列概率在隊列長度的特定范圍內隨著隊列長度的增加而線性地增加，降隊列概率與分配概率的關系和動態映射算法相同，但分配概率隨負載情況而變化。

3.2 網絡負載狀況判斷算法

網絡是否過載的判斷通過利用所估計得到的網絡資源信息與網絡負載信息進行比較得出結果。即如果滿足

(3)

判斷此時的網絡資源足夠傳輸所用類型業務的數據，網絡處于非過載狀態。否則網絡處于過載狀態。

3.3 分配概率的計算

對于分配概率，即當隊列長度超過較大門限時的降隊列概率的最終值，需要采用針對負載和資源估計的值進行相應的調節。在本算法中，采用了根據負載和網絡資源估計，針對相關的數據包率進行線性調節的方法，其計算方法為

(4)

3.4 丟棄概率的計算

當網絡處于過載狀態時，需要將一部分業務的數據包主動丟棄，為重要性更高的數據包讓出信道資源，保證更加重要的數據包的傳輸。對于數據包的丟棄，仍然采用概率丟棄的方法。丟棄概率的值應該與網絡資源和負載情況相關，在本算法中仍然采用了基于數據包率的線性關系來計算。計算方法為

(5)

4 仿真分析

文章對于無線自組網中的基于跨層優化的視頻傳輸方案進行了仿真分析，網絡仿真工具為NS2，視頻編解碼工具為可伸縮視頻評估框架(ScalableVideoEvaluationFramework,SVEF)。SVEF是一款開源軟件，專門用于評價H.264/SVC視頻流的傳輸質量。在整個仿真過程中，首先要對原始視頻進行編碼，然后數據封裝，之后將數據輸入到NS2仿真過程之中進行仿真，將仿真結果記錄下來并存儲視頻數據接收端所接收到的數據，然后對其進行解碼后，將接收到的視頻與原視頻進行比較評估接收視頻質量，從而得出視頻數據傳輸質量的評估結果。仿真流程如圖5所示。

圖5 仿真流程圖

4.1 網絡負載對系統性能的影響

首先對在特定帶寬不同網絡負載情況下進行仿真，物理層傳輸的數據率設置為1Mbit/s。

在仿真過程中采用了3個節點，n0，n1和n2。n0發送H.264/SVC的視頻業務，并且利用業務源流量產生器CBR作為背景業務數據和音頻數據。其中n0向n1發送視頻業務，視頻碼率為0.2Mbit/s，原始視頻采用的是YUVCIF(352×288)格式的Foreman。n0向n2發送背景業務數據。

對于視頻傳輸而言，丟包并不能完全說明傳輸質量。因為不同數據包的丟失對于視頻質量影響不一樣。計算接收視頻的PSNR是對視頻傳輸質量綜合的體現，在上面的情況下對于不同網絡負載的情況下，對不同算法下接收視頻的PSNR進行了計算，算法包括EDCA、靜態映射、動態映射、LADM，其PSNR結果如圖6所示，傳輸時延的結果如圖7所示。

根據圖6可以看出，負載較輕的情況下，由于靜態映射算法將數據包放入低優先級隊列中造成丟包率相對更大。而動態映射算法通過隊列長度對網絡負載情況進行檢測，因此存在一定的自適應性，并不是完全將重要性低的數據包放入低優先級隊列進行調度。而自適應動態映射算法，采用了隊列

圖7 不同負載下延時仿真結果

發送速率和不同類型的數據包進隊列速率作為網絡情況的進一步衡量，在負載較輕時其表現與動態映射算法和EDCA基本差不多，但在負載情況較重時其表現優于其他算法，當負載到達物理層傳輸的極限時(5個視頻流同時發射)，提出的算法PSNR改善3dB以上，有效地提升視頻質量。

根據圖7可以看出，靜態算法的延時最大。動態算法和自適應算法的延時均比EDCA大，但比靜態算法要小。自適應算法在網絡負載較輕時，延時稍大于動態算法，但在網絡負載較重時，延時小于動態算法。

4.2 節點競爭對系統性能的影響

為了評估自組織網絡間節點通信產生的碰撞對系統的影響，設計以下的場景：網絡中有3個節點，n0，n1和n2。n0和n1同時向n2發送數據，其中n0發送視頻流和64kbit/s音頻數據，n1同時也發送196kbit/s背景數據。視頻傳輸質量如圖8所示。

從圖8的結果可以看出，當存在節點競爭時系統視頻傳輸質量有較大變化。當網絡負載較輕的時候，性能下降最多的是靜態映射算法，其次是EDCA算法，然后是動態映射算法，自適應動態映射算法受到的影響最小。靜態映射算法將數據包固定映射到低優先級的隊列中之后，當出現節點競爭的時候，低優先級的隊列傳輸性能變差，導致視頻傳輸性能變差。然而自適應動態映射算法通過對網絡的負載情況進行了更加詳細的檢測，因此可以改善這一情況。

圖8 節點競爭下的仿真結果

4.3 多跳視頻傳輸場景下的系統性能

對于自組網來說，多跳傳輸是自組網的一種重要的傳輸方式。因此對于多跳傳輸，同樣通過設置一系列節點進行仿真。在NS2中設置了如圖9的拓撲結構。其中，節點node(i-1)向節點node(i)發送視頻數據，視頻流速率為0.2Mbit/s。同時，節點間存在背景業務數據流速率為192kbit/s。

圖9 多跳場景拓撲圖

研究不同跳數情況下的視頻傳輸質量PSNR和延時情況。其結果如圖10和圖11所示。

圖10 多跳環境下的視頻傳輸質量

圖11 多跳環境下的延時

從仿真結果可以看出，隨著跳數增加，視頻傳輸質量有一定的下降。對于此仿真場景中，當跳數增加時視頻質量有所下降，時延明顯上升。從結果上看，靜態映射算法的傳輸時延最長，多于其余幾個算法，其次是動態映射算法的時延，然后是EDCA和自適應動態映射算法。從傳輸質量上看，在跳數增加的情況下，自適應動態映射算法的傳輸質量相對不如靜態映射算法和動態映射算法，原因應該是對于每個節點都需要從傳輸過程中進行實時的參數監測，參數監測隨著節點增加而準確度降低，因此調度過程一定程度上出現不準確的計算結果。

5 結論

本文主要提出了一種負載自適應的動態調度算法，其基本思想是結合應用層視頻編碼的特點和接入層網絡負載和資源的情況聯合進行優化。在特定的資源下通過概率接入的方法對重要性更高的數據包進行更優先的接入。仿真結果顯示，在視頻傳輸質量方面，自適應算法在負載較輕的時候并沒有大幅度提升。但當網絡負載較重的情況下，自適應動態映射算法的優勢相對明顯，PSNR提升3dB以上。在延時方面，自適應動態映射算法的延時在網絡負載較重時稍好于動態映射算法，但都比EDCA本身延時大，但自適應算法在視頻傳輸質量上有較明顯的提升。

[1]CiscoSystems.Ciscovisualnetworkingindex:forecastandmethodology[R].[S.l.]：Cisco，2008.

[2]HALVORSENM,PLAGEMANNT,SIEKKINENM.Videostreamingovermanets:realityorfiction[C]//Proc.the4thInternationalMobileMultimediaCommunicationsConference.Oulu,Finland：[s.n.], 2008：153-162.

[3]TSENGYC,NISY,CHENYS,etal.Thebroadcaststormprobleminamobileadhocnetwork[J].Wirelessnetworks, 2002, 8(2/3)：153-167.

[4]BOUKERCHEA,TURGUTB,AYDINN,etal.Routingprotocolsinadhocnetworks:asurvey[J].ComputerNetworks, 2011, 55(13):3032-3080.

[5]RANIWALAA,CHIUEHT.ArchitectureandalgorithmsforanIEEE802.11-basedmulti-channelwirelessmeshnetwork[C]//Proc.the24thAnnualJointConferenceoftheIEEEComputerandCommunicationsSocieties.Miami,FLUSA：IEEEPress，2005：2223-2234.

[6]STOCKHAMMERT,HANNUKSELAMM,WIEGANDT.H.264/AVCinwirelessenvironments[J].IEEETrans.CircuitsandSystemsforVideoTechnology, 2003, 13(7):657-673.

[7]SOHNH,YOOH,LEEYB.MPEG-21-Basedscalablebitstreamadaptationusingmediumgrainscalability[C]//Proc.IEEERegion10Conference.[S.l.]：IEEEPress, 2008: 1-5.

[8]駱政屹，余松煜，宋利，等.H.264可分級擴展技術的介紹和分析[J].中國圖象圖形學報, 2006(11) :1578-1583.

[9]雷蕾, 林闖.無線數據網絡中機會調度理論模型的研究[J].電子學報, 2007, 35(8):1548-1557.

[10]周超, 張行功, 郭宗明.面向 MIMO 多跳無線網絡的多用戶視頻傳輸優化方法[J].軟件學報, 2013, 24(2):279-294.

[11]MANTZOURATOSS, GARDIKIS G, KOUMARAS H, et al.Survey of cross-layer proposals for video streaming over Mobile Ad hoc Networks(MANETs)[C]//Proc.2012 International Conference on Telecommunications and Multimedia(TEMU).[S.l.]：IEEE Press，2012:101-106.

[12]LINC H, SHIEH C K, KE,C H，et al.An adaptive cross-layer mapping algorithm for MPEG-4 video transmission over IEEE 802.11e WLAN[J].Telecommunication Systems, 2009, 42(3/4): 223-234.

[13]NEJATIN, YOUSEFIZADEH H, JAFARKHANI H.Wireless video transmission: a distortion-optimal approach[C]//Proc.Data Compression Conference.[S.l.]：IEEE Press ,2008: 202-211.

[14]KSENTINI A, NAIMI M, GUEROUI A.Toward an improvement of H.264 video transmission over IEEE 802.11e through a cross-layer architecture[J].IEEE Communications Magazine, 2006, 44(1):107-114.

李 悅(1977— )，女，工程師，主研衛星通信、自組織網絡；

陳衛衛(1976— )，高級工程師，主研無線自組織網絡、無線通信；

單 勝(1971— )，工程師，主研無線自組織網絡、視頻通信；

丁良輝(1981— )，助理研究員，主研無線通信、無線網絡。

責任編輯：薛 京

Load Adaptive Queue Scheduling for Video Transfer in Wireless Ad Hoc Networks

LI Yue1，CHEN Weiwei2，SHAN Sheng3, DING Lianghui4

(1.NavalArmamentResearchInstitute,Beijing100616,China; 2.ChinaElectronicSystemEngineeringCompany，Beijing100141,China;3.InformationandCommunicationBranch,NationalGrid,Beijing100761,China; 4.DepartmentofElectronicEngineering,ShanghaiJiaoTongUniversity,Shanghai200240,China)

Development of multimedia on mobile terminals has been the trend, and how to transfer video in wireless ad hoc networks has been a hot research topic in recent years.In this paper, the cross-layer optimization scheme for video transfer based on network load is proposed.The proposed scheme considers both video coding on application layer and network load status on MAC layer to optimize the video quality.Packets with higher priority are transmitted with high access probability when the network resource is limited.Simulation results show that the performance of the video, i.e.,PSNR, can be improved up to 3 dB in heavy-load and multi-hop scenario.Compared with traditional scheduling algorithm, system delay can also be reduced significantly.

load adaptive; wireless ad hoc networks; video transfer

國家自然科學基金項目(61301117；61102051；61221001；61420106008)；國家高技術研究發展“863”計劃項目(2012AA011701；2012AA121601)；上海交通大學“科技創新專項資金”(AF0300021)；上海市數字媒體處理與傳輸重點實驗室項目(12DZ2272600)

TN915

A

10.16280/j.videoe.2015.07.017

2014-10-20

【本文獻信息】李悅，陳衛衛，單勝，等.基于負載自適應的Ad Hoc網視頻傳輸隊列調度算法[J].電視技術,2015，39(7).