基于隨機森林的帶寬預(yù)測算法研究與實現(xiàn)

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

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

0 引 言

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

1 相關(guān)工作

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

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

2 帶寬預(yù)測算法

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

圖1 隨機森林架構(gòu)

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

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

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

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

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

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

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

步驟6 綜合多棵樹的預(yù)測結(jié)果，采用投票原則構(gòu)成最終預(yù)測結(jié)果。

步驟7 通過TCP通信，將客戶端預(yù)測數(shù)據(jù)打包發(fā)送給服務(wù)器。

步驟8 服務(wù)器解析數(shù)據(jù)，流媒體分發(fā)服務(wù)器根據(jù)HLS協(xié)議向客戶端分發(fā)適宜碼率視頻，實現(xiàn)自適應(yīng)流。

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

(1)

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

(2)

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

算法1： 決策樹建立算法

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

輸出： Decision Trees

(1) X→forbagging

(2) //采用bagging抽樣循環(huán)處理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) //按照最優(yōu)屬性進行節(jié)點分裂，生成決策樹

(12)endfor

endProcedure

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

(3)

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

算法2： 帶寬預(yù)測算法

輸入： 樣本sample， 訓(xùn)練集Xtrain， 測試集Xtest

輸出： K棵樹和預(yù)測結(jié)果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 數(shù)據(jù)采集

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

(4)

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

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

表1 預(yù)測數(shù)值對應(yīng)

由表1可知，當(dāng)采集的數(shù)據(jù)處于不同區(qū)間時，對結(jié)果預(yù)測將會產(chǎn)生不同影響。這里我們把BandWidth劃分3個區(qū)間定義為3個等級：poor(0～1*104kbps)、mid(1*104～2*104kbps)、good(2*104～4*104kbps)。建樹過程中，每一次節(jié)點切分都涉及到計算切分后的均方誤差(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是樣本數(shù)據(jù)的輸入和輸出，R1和R2是該節(jié)點切分后的左右子樹集，e1和e2表示切分后左子樹和右子樹的平均值。誤差越小，表示切分的效果越好，最終提取為12個特征屬性[10]，見表2。

表2 特征屬性

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

圖2 特征分布

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

(7)

(8)

(9)

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

4 實 驗

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

圖3 采集數(shù)據(jù)

表3 結(jié)果對比

片生成m3u8索引文件，然后部署到基于Nginx搭建的WEB服務(wù)器上進行分發(fā)?？蛻舳送ㄐ欧绞讲捎没赥CP通信模型的Socket通信，通信時序如圖4所示。Socket在建立連接時可以直接進行數(shù)據(jù)傳輸，可以實現(xiàn)主動推送信息，而不是每次都由客戶端向服務(wù)器發(fā)送請求[12]。系統(tǒng)架構(gòu)如圖5所示。

圖4 通信時序

實驗環(huán)境為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公司提供的業(yè)界知名的網(wǎng)速測試方案，具有獨立性和準確性特點。

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

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

(10)

圖5 系統(tǒng)架構(gòu)

表4 參數(shù)控制方案

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

圖6 對比

5 結(jié)束語

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