基于強化學習的DASH自適應碼率決策算法研究

馮蘇柳，姜秀華

(中國傳媒大學信息與通信工程學院，北京100024)

1 引言

隨著無線通信技術的飛速發(fā)展和智能手機、平板電腦、移動電視等視頻觀看設備的多樣化，內(nèi)容提供商和用戶對可變網(wǎng)絡環(huán)境下提供高QoE(用戶體驗質(zhì)量)視頻流服務的需求不斷增加。在這樣的背景下，能夠根據(jù)網(wǎng)絡環(huán)境動態(tài)調(diào)節(jié)請求碼率以最大化QoE的自適應流媒體傳輸應運而生。目前基于HTTP的動態(tài)自適應流媒體傳輸(MPEG-DASH)標準具有覆蓋廣泛、兼容性良好、部署較簡便等特性，成為自適應流媒體傳輸?shù)难芯恐攸c。在DASH中，一個視頻流被切割成固定時長的分片，每個分片存儲有多種碼率，客戶端的播放器根據(jù)當前網(wǎng)絡狀況以及播放信息，采用碼率自適應(ABR)決策算法，選擇下個分片請求的最優(yōu)碼率。DASH標準中并沒有指定ABR算法，所以存在很大的研究空間。ABR算法的總體目標是：1)避免由緩沖區(qū)下溢引起的播放中斷，即重緩沖；2)最大化視頻質(zhì)量；3)最小化視頻質(zhì)量切換次數(shù)及幅度以保證視頻播放平滑度。而實現(xiàn)最優(yōu)的ABR算法存在著以下挑戰(zhàn)：1)動態(tài)網(wǎng)絡環(huán)境下實現(xiàn)精確的吞吐量預測難度較大；2)ABR算法必須平衡各種QoE指標，但這些指標存在著內(nèi)在沖突，例如高碼率和重緩沖；3)當前的碼率決策會對后續(xù)的決策產(chǎn)生級聯(lián)效應；4)ABR算法可用的決策碼率是粗粒度的，僅限于給定視頻的可用碼率。所以對ABR算法的研究一直在不斷提升中。

目前基于客戶端的ABR算法主要有基于吞吐量、基于緩沖和基于混合/控制理論這三類，但這些算法都存在局限性，即它們都使用基于特定環(huán)境的低準確性的建模來實現(xiàn)固定的控制算法，這使它們很難捕獲和反映真實網(wǎng)絡環(huán)境中動態(tài)網(wǎng)絡的變化情況，并且很難在不同的網(wǎng)絡環(huán)境下和不同的QoE目標上實現(xiàn)最佳決策。強化學習(RL)作為新興的機器學習方法，通過學習環(huán)境的動態(tài)特性，反復試驗并通過反饋的回報不斷調(diào)整執(zhí)行策略，逐漸收斂到最優(yōu)策略，目前已廣泛應用于無人駕駛、智能控制機器人等領域。近幾年開始有研究將強化學習應用于ABR算法并取得了比啟發(fā)式算法更好的效果。所以，采用強化學習來研究自適應流媒體傳輸中的ABR算法，為用戶提供更加智能化的視頻流服務，對提升用戶體驗質(zhì)量，具有重大的意義。

本文采用了強化學習和深度神經(jīng)網(wǎng)絡相結合的深度強化學習算法，對動態(tài)網(wǎng)絡環(huán)境下的DASH客戶端碼率決策算法進行優(yōu)化。

本文第二章介紹目前的基于客戶端的碼率自適應算法研究現(xiàn)狀，第三章介紹本文所采用的的基于深度強化學習的碼率決策算法，第四章為實驗部分，新算法和現(xiàn)有算法進行比較并分析，最后一章為結論。

2 研究現(xiàn)狀

目前基于客戶端的ABR算法主要有基于吞吐量、基于緩沖和基于混合/控制理論這三類。

文獻[1]提出了一種基于TCP的AIMD算法，使用平滑的吞吐量測量來探測空閑網(wǎng)絡容量并檢測擁塞，漸進向上切換碼率，檢測到網(wǎng)絡擁塞時乘性減小碼率。文獻[2]提出了一種多個商業(yè)DASH播放器共享瓶頸鏈路，基于公平性、效率和穩(wěn)定性三個評估指標的碼率自適應算法，采用歷史吞吐量的調(diào)和均值估計當前帶寬，并且采用有狀態(tài)和延遲的碼率更新以及隨機下載塊調(diào)度。文獻[3]提出了一種基于緩沖區(qū)的碼率自適應算法，構建了基于重緩沖、分片質(zhì)量和質(zhì)量切換的QoE模型，并表示為非線性隨機最優(yōu)控制問題，設計了基于動態(tài)緩沖區(qū)的PID控制器，該控制器可以確定每個分片的比特率并穩(wěn)定緩沖區(qū)級別。文獻[4]提出了基于緩沖區(qū)的Lyapunov 算法(BOLA)，將碼率自適應表示為效用最大化問題，并使用Lyapunov優(yōu)化技術來求解最優(yōu)策略。BOLA現(xiàn)在是dash.js中實驗算法的一部分。文獻[5]提出了一種基于模型預測控制(MPC)的算法，該算法結合吞吐量和緩沖區(qū)占用反饋信號，使用過去5個塊的吞吐量調(diào)和均值進行吞吐量預測，并采用CPLEX等現(xiàn)有技術來解決QoE優(yōu)化問題。他們還提出了robust-MPC[6]，其控制器等效于吞吐量取下限估計值輸入的MPC。

近年來開始出現(xiàn)了基于馬爾可夫決策過程(MDP)的碼率自適應算法，將碼率決策模型化為有限狀態(tài)的MDP，在波動的網(wǎng)絡環(huán)境下做出決策。文獻[7]提出了基于Q-learning算法的控制算法，客戶端通過學習網(wǎng)絡環(huán)境的動態(tài)特性，根據(jù)每個狀態(tài)下不同動作的Q值選擇當前的最佳動作，并更新狀態(tài)-動作值Q表。與現(xiàn)有的啟發(fā)式算法相比，QoE增加了9.7%。文獻[8]將狀態(tài)空間減少為兩個變量：緩沖區(qū)級別和可用帶寬，并簡化了回報函數(shù)。文獻[9][10]也提出了一種基于Q-learning的控制模型，改進之處主要在于對回報函數(shù)的調(diào)整。但由于Q-learing算法要求狀態(tài)空間必須是離散的以及維度災難問題，因此出現(xiàn)了使用神經(jīng)網(wǎng)絡來逼近價值函數(shù)的深度Q-learning算法(DQN)。文獻[11]采用double-DQN，其主網(wǎng)絡輸出不同動作的近似Q值，目標網(wǎng)絡輸出目標Q值。D-DASH[12]根據(jù)分片大小來估計SSIM代替碼率來作為分片質(zhì)量度量標準[13]，還使用混合神經(jīng)網(wǎng)絡框架，包括前饋神經(jīng)網(wǎng)絡和循環(huán)神經(jīng)網(wǎng)絡。Pensieve[14]采用A3C算法，該算法結合了策略梯度和基于值函數(shù)的方法，用值函數(shù)來指導策略更新，取得了更高的QoE值。

本文同樣采用了深度強化學習的方法，通過學習環(huán)境的動態(tài)特性做出決策，并根據(jù)回報來調(diào)整策略，強化學習算法本文采用了OpenAI推出的將值迭代和策略梯度算法相結合的近似策略優(yōu)化算法(PPO)[15]。

3 基于并行PPO的ABR算法研究

3.1 PPO算法簡介

強化學習采用近端策略優(yōu)化算法(PPO)，PPO是2017年OpenAI推出的一種新的基于Actor-Critic算法。本文選用該算法的原因是PPO結合了策略梯度算法和值函數(shù)的優(yōu)勢，但是之前的策略梯度算法存在著學習步長難以確定的問題，在訓練過程中新舊策略的的變化差異如果過大，相當于用了一個較大的學習率，不利于學習。而PPO提出了新的目標函數(shù)，經(jīng)過理論推導得出只要策略參數(shù)朝著增大目標函數(shù)的方向更新，就可以保證策略的期望回報是單調(diào)遞增的，解決了策略梯度算法中步長難以確定的問題。

原始的AC算法的策略網(wǎng)絡的損失函數(shù)如式(1)所示。

(1)

其中pθ(st，at)為狀態(tài)s下采取動作a的概率，優(yōu)勢函數(shù)Aθ(st，at)的含義是在狀態(tài)s下采取動作a所獲得的價值相比于平均價值有多好，損失函數(shù)的含義是增大獲得較大回報價值的動作發(fā)生的概率。

(2)

為了保證策略的回報期望是單調(diào)遞增，PPO限制新舊策略不能相差過大。PPO有兩種算法，第一種是PPO-penalty，目標函數(shù)如式(3)所示，增加了兩個策略的KL散度懲罰項。

KL散度的系數(shù)β隨KL散度而變化，若大于設定目標值，則增大懲罰系數(shù)使得參數(shù)朝著減小KL散度的方向更新，反之亦然。

(3)

第二種是PPO-clip，它不在損失函數(shù)中加KL散度懲罰項，而是直接對式(3)的第一部分進行裁剪，限制在預設范圍(1-ε，1+ε)內(nèi)，損失函數(shù)如式(4)所示。

(4)

為了增加模型探索性，在目標函數(shù)中加入了概率熵，熵權值隨著訓練次數(shù)增加而減小。

本文將實現(xiàn)PPO-penalty和PPO-clip這兩種算法。

3.2 算法實現(xiàn)

3.2.1 強化學習元素

狀態(tài)選用六種特征，包括過去k個視頻塊的吞吐量測量矢量；過去k個視頻塊的下載時間矢量，代表了吞吐量測量的時間間隔；下一個視頻塊的可下載大小的矢量，矢量長度為可選碼率數(shù)量；當前緩沖水平；視頻還存留的塊數(shù)；上一個塊下載的碼率。

回報函數(shù)選用了ABR算法中常用的線性Qoe模型，包括三個部分：媒體分片質(zhì)量、重緩沖事件、碼率切換事件，如式(5)所示。碼率切換部分需要先判斷當前緩沖是否小于預設最低閾值，若小于預設閾值，則獎勵減小決策碼率的行為，懲罰增大碼率的行為；若大于預設閾值，則懲罰減小決策碼率的行為，獎勵增大碼率的行為。

(5)

3.2.2 網(wǎng)絡框架

本文采用PPO結合神經(jīng)網(wǎng)絡的算法，包括actor策略網(wǎng)絡和critic值網(wǎng)絡，網(wǎng)絡框架圖如圖1所示。

圖1 PPO算法框架

Actor網(wǎng)絡和Critic網(wǎng)絡的輸入層和隱藏層設置相同。輸入層為6個狀態(tài)特征，輸入的狀態(tài)中的三個序列，包括吞吐量、分片下載完成時間、當前分片大小列表，經(jīng)過一個一維卷積層，卷積層的size為4，濾波器個數(shù)設置為128。輸入狀態(tài)的其他單值特征則輸入一層全連接層，節(jié)點數(shù)設為128，然后第一層隱藏層的所有輸出合在一起輸入一層全連接層，最后接輸出層。

Actor網(wǎng)絡的輸出層為softmax層，輸出節(jié)點數(shù)為動作數(shù)量，對應輸入狀態(tài)s下不同動作a對應的概率分布p(a|s)，Critic網(wǎng)絡的輸出層為全連接層，輸出節(jié)點為1，對應為輸入狀態(tài)s的狀態(tài)價值V(s)。

3.2.3 算法訓練

本文采用并行訓練的方法訓練PPO算法，即采用多個不同訓練環(huán)境采集樣本，可以提升訓練速度，并且樣本分布更加均勻，更利于網(wǎng)絡的訓練。相比于值函數(shù)方法中用經(jīng)驗池來存儲歷史樣本，再隨機抽取樣本訓練，并行訓練可以大大地節(jié)省存儲空間。并行訓練的框架如圖2所示。

圖2 并行訓練框架

各個agent在各自的環(huán)境下進行不斷決策，獲取到?jīng)Q策軌跡(s，a，r，s_next)，然后積累到一定樣本時送到central_agent，對網(wǎng)絡參數(shù)進行更新，更新完之后把參數(shù)復制給agent網(wǎng)絡。

本文采用了兩種并行訓練的方式，一種是同步并行，即等所有agent采集完足夠的樣本，把所有agent的(s，a，r，s_next)送入到central_agent，計算梯度然后更新網(wǎng)絡參數(shù)，更新完后把參數(shù)分發(fā)給各個agent。另一種是異步并行，即只要有一個agent采集完足夠的樣本，就把該agent的(s，a，r，s_next)送入到central_agent，計算梯度然后更新網(wǎng)絡參數(shù)，更新完后把參數(shù)分發(fā)給該agent。本文將同時采用這兩種訓練方式。

4 實驗結果

4.1 實驗準備

測試視頻選用DASH-246 JavaScript參考客戶端的“Envivio-Dash3”序列，該視頻采用H.264/MPEG-4編碼，總時長為193秒，被分割成48個分片，每個分片的可用碼率包括{300，750，1200，1850，2850，4300}六種，分片時長為4秒。訓練和測試的網(wǎng)絡軌跡選用挪威收集的3G / HSDPA移動數(shù)據(jù)集，由傳輸過程中(如通過公交、火車等)流媒體視頻的移動設備生成。訓練集包含了127個軌跡文件，每個文件包括300-1500個時刻的吞吐量測量值；測試集包含了147個軌跡文件，每個文件只有50-250個時刻的吞吐量測量值。吞吐量范圍在0.2～6Mbps。本實驗是在ubuntu16.04的Pycharm中下進行仿真，模擬碼率決策和分片下載過程。

4.2 實驗結果

采用PPO-clip的算法，且同步并行訓練。輸出本課題算法及現(xiàn)有算法在測試軌跡集上的總回報均值，如表1所示。

表1 不同算法在各個測試軌跡的總回報均值

可以看出，本文的算法在相同的測試軌跡下獲得的總回報均值要高于現(xiàn)有算法。繪制不同算法在測試軌跡集上的總回報的累積分布曲線，如圖3所示。

圖3 不同算法在測試軌跡上的總回報累積分布曲線

可以看出，在橫軸相同的區(qū)間范圍內(nèi)，本文算法在縱軸的比例較大，說明PPO算法落在較高回報值區(qū)間的比例最大。

隨機選取一個軌跡，輸出各個算法在測試軌跡下的碼率選擇，緩存區(qū)余量，帶寬隨時間變化曲線，如圖4所示。

可以看出，PPO算法能夠保證選擇較高碼率并且較穩(wěn)定，碼率切換頻率較小，并且能夠充分利用緩沖，在吞吐量即使較小時，如果緩沖區(qū)較充足，仍然選擇較大碼率，同時在緩存區(qū)低于門限值時能夠立即減小碼率。

選用ppo-pen、ppo-clip和同步并行、異步并行組合訓練，輸出四種方法下在測試軌跡集上的總回報均值，如表2所示。

表2 ppo-pen、ppo-clip及同步并行、異步并行組合訓練在測試軌跡上的總回報均值

從ppo算法上看，ppo-clip總回報值要略高于ppo-pen，從并行訓練方式上看，同步并行總回報值較高于異步并行。

從ppo算法分析，從式(3)和式(4)可以看出，ppo-clip是直接對新舊策略的比值進行一定程度的裁剪，可以保證兩次更新之間的分布差距不大。從并行訓練方式分析，異步并行會導致過期梯度情況，即cenral_agent在更新當前網(wǎng)絡參數(shù)時使用的從agent傳來的梯度可能是多次更新之前的參數(shù)，這樣會導致梯度下降的過程變得不穩(wěn)定，而實驗中輸出agent使用的參數(shù)，小于當前central_agent的參數(shù)版本在10-16，充分說明過期梯度的問題。對于這個問題，目前有研究提出給梯度增加延時補償，利用梯度函數(shù)的泰勒展開來有效逼近損耗函數(shù)的Hessian矩陣。

輸入狀態(tài)的時間序列長度slen分別設置為1，4，8，16，采用ppo-clip及同步并行訓練，輸出這四種設置在測試軌跡上的總回報均值，如表3所示。

表3 四種不同的時間序列長度在測試軌跡上的總回報均值

可以看出，時間序列由1增大到4、由4增大到8時，總回報均值均有較大提升，但是由8增大到16時，總回報均值沒有增大，反而有略微減小。

結果說明一定程度的增大歷史吞吐量的數(shù)量可以提升碼率決策性能，因為一定的歷史吞吐量信息有利于較為準確地預測當前帶寬，但是歷史吞吐量數(shù)量增大到一定程度性能不再提升，因為當前動作對未來回報的影響是逐漸衰減的，越久之前的信息對當前影響越小。

5 結論

本文采用了強化學習和深度神經(jīng)網(wǎng)絡相結合的DRL算法，實現(xiàn)了DASH客戶端的自適應碼率決策算法。在真實網(wǎng)絡軌跡數(shù)據(jù)集上進行多種算法的測試，實驗結果表明：本文所采用的算法能夠獲得比現(xiàn)有算法更高質(zhì)量的用戶體驗，并且具有較少的重緩沖事件和質(zhì)量切換事件。