基于隨機森林的帶寬預測算法研究與實現

王 烽，李澤平，林 川，王忠德，黃初華

(貴州大學 計算機科學與技術學院，貴州 貴陽 550025)

0 引 言

動態自適應流媒體技術(dynamic adaptive streaming technology)是一種結合了實時流式傳輸和順序流式傳輸的分發傳輸技術，可以動態調節傳輸不同碼率的視頻。隨著4G網絡以及即將來臨的5G網絡的發展，大批移動智能終端的普及，大量移動應用的涌現，為移動互聯網視頻服務提供了良好的基礎，流媒體技術在移動互聯網中的應用也越加廣泛。然而移動流媒體服務仍然面臨著諸多挑戰，例如在移動的網絡環境下，用戶在體驗視頻服務時往往伴隨著畫面卡頓、畫質模糊、切換時間過長等問題。傳統的解決方案是將低碼率的視頻分發給用戶，降低了視頻的服務質量(quality of service，QoS)，導致用戶體驗質量(qua-lity of experience，QoE)較差，而且容易造成可用帶寬的浪費。因此，如何更好地提升用戶QoE成為目前流媒體服務迫切需要解決的關鍵問題之一。本文提出的算法可以預測移動客戶端可用帶寬大小，檢測其網絡狀況，并根據用戶的可用帶寬分發最優碼率的視頻，提高用戶視頻觀看體驗，降低服務器壓力。

1 相關工作

Ragil等[1]提出了一種基于參考信號接收功率(RSRP)和參考信號接收質量(RSRQ)來估計LTE網絡負載的算法。Teerapat等[2]提出了LTE-A網絡中基于多方位的手機底層參數驗證具有更好的性能評估。GideonKutz等[3]提出了一種低復雜度的，能抵消來自相鄰基站干擾的LTE測量算法。DuHaipeng等[4]基于HTTP自適應流(HAS)提出了差異化速率自適應算法，降低了比特率切換頻率。Tsung-Han Lei等[5]提出了一種使用隨機森林回歸方法來預測虛擬化網絡功能(VNF)的延遲分布的算法。Rana等[6]通過使用多機學習算法測量視頻流來比較性能。結合文獻[7]提出的LinkForecast預測框架，本文采集Android端的參考信號參數，使用隨機森林處理數據預測帶寬，并將其應用于流媒體分發系統中，實現自適應流媒體分發系統。

目前流媒體系統解決方案有很多種，其中Apple公司的HLS(HTTP live streaming)比較出色，HLS是一種基于HTTP的自適應流媒體協議，具備良好的兼容性，尤其適用于移動終端觀看視頻。HLS移動流媒體系統由3部分組成：服務器端、視頻分發存儲端和客戶端。服務器端由編碼器和流分割器組成。對源視頻首先進行存儲、編碼和流處理，然后服務器端的切片器將媒體流分割為一串簡短的流媒體文件和索引文件，通常，給定的URL(uniform resource locator)用于標識關于視頻流的信息。視頻文件需要使用FFmpeg轉碼為H.264格式，然后存儲到服務器中等待用戶的請求。視頻文件被切片生成相應的M3U8索引文件，然后將其編碼為具有多個不同碼率的視頻流，用以響應不同的需求服務，然而，如何準確地獲得可用帶寬則是一個有待解決的問題。本文提出的基于隨機森林的MABP算法，可在動態網絡環境下實時采集客戶端的LTE參數并預測客戶端可用帶寬，使用該預測算法，實現了流媒體自適應技術，提高了用戶QoE。

2 帶寬預測算法

隨機森林(random forest，RF)是由多棵決策樹分類器 {T(x,θn)} 組成的一種集成機器學習策略，其中 {θn} 是獨立同分布的隨機向量，n為決策樹分類器的數量，RF通過重采樣法，從原始樣本數據集x中有放回地重復隨機抽取n個樣本，生成一個新的訓練樣本集，之后按照訓練樣本集生成n個分類決策樹，組成隨機森林。根據決策樹投票原則，將多個分類預測結果統一為最終結果，從而構成結果預測，預測架構如圖1所示。RF對噪聲數據和具有缺失值的數據具有良好的適應性[8]。

圖1 隨機森林架構

RF具備分析分類特征的能力，并且具備較快的學習速度，如今已被普遍應用于各種分類、預測、特征選擇等問題。本文使用隨機森林這種機器學習方法預測視頻帶寬，并通過HLS協議實現自適應流媒體技術。

以下步驟是對MABP算法的描述：

步驟1 手機端通過編寫的LTEinfo程序采集底層參數，每隔2 min采集一次，每次采集20 s～30 s，將采集數據導出為.csv記錄文件。

步驟2 加載數據樣本，樣本進行有放回隨機(Bagging)采樣，產生獨立同分布子集，特征屬性采樣(每個節點采一次)。

步驟3 當訓練集中存在缺失值，按C4.5權重分配。當測試集中有缺失值時，將節點分為兩個分支tk，fk并根據tk，fk樣本占比，對返回到該節點的結果進行重新計算。

步驟4 計算每個特征屬性的Gini值，對節點進行排序并分配節點權重。

步驟5 按照決策樹建立算法建立多棵決策樹，為了防止決策樹過擬合，采用控制Gini值變化大小以及結點樣本數等方法。隨機森林預測性能采用調參(如max_depth)進行控制。

步驟6 綜合多棵樹的預測結果，采用投票原則構成最終預測結果。

步驟7 通過TCP通信，將客戶端預測數據打包發送給服務器。

步驟8 服務器解析數據，流媒體分發服務器根據HLS協議向客戶端分發適宜碼率視頻，實現自適應流。

對于決策樹，我們所獲取的結果是訓練樣本數據集在該區間內最常見的分類類別。為了達到預測目的，很多情況下我們并不會只預測一個類別，而是預測一組類別及其出現的概率。因此我們在決策樹中定義葉節點的不純度來作為二元分割的標準，即一種可以在子集區域R1,R2,…,Rj度量目標特征同質性的方法。在結點m中，通過Nk個樣本數據值表示一個區間內Rk類別出現的概率，第n個類別在第k區間下所出現的概率可表示為式(1)

(1)

其中， I(yi=n) 為指示函數，即如果yi=n， 則取1，否則為0。分裂節點處的特征屬性使用Gini指數[9]來度量節點的誤差率，定義為式(2)

(2)

根據節點誤差率對樣本進行分割，最后將樣本分成不同的子節點，每個葉節點對應一個預測結果。由此提出算法1決策樹的建立。

算法1： 決策樹建立算法

輸入： 原始樣本X， 樣本數量N， 特征屬性數量M

輸出： Decision Trees

(1) X→forbagging

(2) //采用bagging抽樣循環處理X

(3)endfor

(4)whileextracting ntry(ntry=N)→Xtraindo

(5) M→mtry(mtry<

(6) //隨機選取mtry個屬性

(7) mtry→the best node

(9)endwhile

(10)for(itree=0； 1

(11) //按照最優屬性進行節點分裂，生成決策樹

(12)endfor

endProcedure

為保證RF隨機性，采用自匯聚法(Bagging)和自抽樣法(Bootstrap)，Bagging每次從原始數據集中有放回的隨機抽樣構成自助訓練集，這個過程獨立重復B次，之后，每一個新的test(測試集)都被獨立用于訓練一棵決策樹。Bootstrap是從大小為N的原始數據集中隨機選擇n個樣本組成一個新的test集，該過程獨立重復B次，統計量的估計值定義為θ，如式(3)所示

(3)

RF由若干個單決策樹組合而成，從而能對測試樣本進行分類，比單個分類器具備更好的分類能力和泛化效果。通過對不同決策樹進行的多個獨立預測進行投票，得到最終預測結果。用于訓練單顆樹的樣本是從訓練數據集Xtrain中隨機選擇的，一些元組可能被選擇多次，而有些元組可能永遠不會被使用，這反映了隨機森林的隨機性。本文帶寬預測算法如下。

算法2： 帶寬預測算法

輸入： 樣本sample， 訓練集Xtrain， 測試集Xtest

輸出： K棵樹和預測結果L

(1)foralli = 1 to Kdo

(2)whilej ≤ Ndo

(3) rowsample= rowsample+ Select(Xtrain)

(4) j + +

(5)endwhile

(6)whilestop condition not truedo

(7) colsample= Select(rowsample)

(8) split_Attribute = min{Gini(colsample)}

(9) //分裂屬性由最小Gini值確定

(10) tree = AddNode(split_Attribute)

(11)endwhile

(12) leaf_node ← node

(13)endfor

(14)foralli = 1 to Kdo

(15) li= Ti_Predict(Dtest)

(16) L = MostCommon(li)

(17)endfor

endProcedure

3 數據采集

在文獻[7]的基礎上研究帶寬實時預測算法，并編寫程序完成對移動端所需參數(分別為RSRP、RSRQ、CQI、BLER和Handover Events)的調用，使用隨機森林算法實現實時帶寬的檢測。參考信號接收功率(reference signal receiving power，RSRP)，是在單個資源塊(resource block，RB)中測量的功率，它不包含任何來自相鄰單元的噪聲或干擾，其單位為dBm。參考信號接收質量(refe-rence signal receiving quality，RSRQ)是評價接收信號質量的一個重要參數，其定義如式(4)所示，接收信號強度指示(received signal strength indication，RSSI)定義為在資源塊(RB)中接收的總功率。使用RSRP和RSSI計算RSRQ，在移動網絡中作為參考信號進行切換決策。N用于計量RB的數量

(4)

頻道質量指標(channel quality indicator，CQI)是一個載有質量信息的指標參數，是網絡中用戶終端傳輸的反饋信息。CQI可以反映UE(user equipment)的通道質量，無線信道越好，UE報告的CQI越高。CQI用于確定調制格式、數據包類型、預編碼矩陣類型等重要參數的值，這些參數直接影響向用戶傳輸的吞吐量。阻塞錯誤率(block error rate，BLER)定義為目標用戶接收到的錯誤塊除以塊的總數，一般BLER不大于10%，否則鏈路必須切換到較低的速度。交接事件(Handover Events)發生在用戶移動過程中，從一個服務區域切換到另一個服務區域時會使帶寬下降。

所需參數信息由Android API調用得到，首先將事件接收器注冊到操作系統，當一個信號發生變化事件，Android核心模塊會向app中的事件接收器發送一個事件，它將捕獲事件并將該信號的當前值基于時間戳記錄下來，之后建樹組成隨機森林進行訓練預測。表1為參數不同值對應的帶寬區間。

表1 預測數值對應

由表1可知，當采集的數據處于不同區間時，對結果預測將會產生不同影響。這里我們把BandWidth劃分3個區間定義為3個等級：poor(0～1*104kbps)、mid(1*104～2*104kbps)、good(2*104～4*104kbps)。建樹過程中，每一次節點切分都涉及到計算切分后的均方誤差(mean-square error，MSE)，通過計算最小均方誤差(MMSE)確定進行建樹時所需的特征屬性(Attributes)，計算公式如式(5)，式(6)所示

MMSE=minf,v{mine1∑xi∈R1(yi-e1)2+
mine2∑xi∈R2(yi-e2)2}

(5)

(6)

其中，f和v表示特征和特征值，xi和yi是樣本數據的輸入和輸出，R1和R2是該節點切分后的左右子樹集，e1和e2表示切分后左子樹和右子樹的平均值。誤差越小，表示切分的效果越好，最終提取為12個特征屬性[10]，見表2。

表2 特征屬性

因為交接事件(Handover Events)發生越多，產生的帶寬減少事件就會越多，所以當交接事件越少時，鏈路可用帶寬越大，所以AT12無具體參考區間，其值越小越好。圖2 為采集的一個原始樣本集下各個特征屬性的比例分布圖，圖3為運動和靜止場景下的部分數據具體值采集結果。

圖2 特征分布

樣本數據每隔一段時間采集一次，為了確定最佳間隔時間T，以保證樣本與手機真實性能具有匹配性，我們使用均方根誤差(root mean square error，RMSE)與相關系ρ進行驗證[11]，定義如式(7)所示

(7)

(8)

(9)

表3列出了計算后的結果對比，從多組數據結果比較來看，樣本Y2(T=2min)具有更好的匹配性，因為它的相關系數ρ更高，均方根誤差(RMSE)更低，所以綜合下來將測量間隔時間T定為2 min，即2 min作為一個測量周期。

4 實 驗

構建一個基于HLS協議的流媒體系統，視頻數據的輸入在服務器端完成，然后使用編碼器壓縮和編碼原始數據，之后，視頻被切片并分發到內容服務器。流分割器(stream segmenter)負責將編碼文件轉碼為不同的碼率或分辨率，并將它們分成連續且相等的ts片段，并靜態生成索引文件存儲在服務器上。例如用編譯好的FFmpeg軟件切

圖3 采集數據

表3 結果對比

片生成m3u8索引文件，然后部署到基于Nginx搭建的WEB服務器上進行分發。客戶端通信方式采用基于TCP通信模型的Socket通信，通信時序如圖4所示。Socket在建立連接時可以直接進行數據傳輸，可以實現主動推送信息，而不是每次都由客戶端向服務器發送請求[12]。系統架構如圖5所示。

圖4 通信時序

實驗環境為Intel CoreTMi5 3.2 GHz CPU,16 GB RAM，Windows7 OS，Oracle VM VirtualBox5.2.18，Android Studio3.4，PyCharm2018.2.4，Android手機一部。使用Speedtest.net的測試值作為對比參照，驗證本算法的有效性。Speedtest.net是ookla公司提供的業界知名的網速測試方案，具有獨立性和準確性特點。

實驗設置不同的max_depth(樹的最大深度)和n_estimators(森林里的樹木數量)參數值來控制隨機森林的預測性能[13]，分別為方案a～方案f，見表4。

本文算法預測值為Bp，對照值為Br，預測值與對照值之間的誤差記為Et，絕對誤差計算如式(10)所示

(10)

圖5 系統架構

表4 參數控制方案

如圖6所示，x軸為時間序列，按照T=2min為一個測試節點，y軸為預測值與對照值的絕對誤差率。通過使用同一組樣本在a，b，c，d，e，f這6種方案中的預測表現進行對比，由圖可知，方案e在所有比較方案中表現最佳，具有最低誤差率。當n_estimators較小時，隨機森林的分類誤差較大，性能也較差。當增加決策樹數量時也會增大隨機森林的構建時間，增大開銷，導致預測結果有所偏差。

圖6 對比

5 結束語

本文在Chao等[7]的LinkForecast框架基礎上，提出了基于隨機森林的MABP算法。該算法通過采集LTE參數，計算最小均方誤差，將LTE參數分為12個特征屬性；然后結合RF算法預測客戶端手機的可用帶寬，最后使用均方根誤差與相關系數計算樣本的相關性，確定了算法的預測周期。最終實驗結果表明，該預測算法能充分利用采集的LTE參數實現實時帶寬預測，為搭建的HLS流媒體系統提供自適應流依據，優化視頻分發，提升用戶視頻觀看體驗。并且本文的預測算法不會增大網絡負載，使我們的預測結果具有匹配性。優化算法，減小系統開銷將會是我們下一步將要研究解決的問題。