基于馬爾可夫修正模型的視頻預(yù)測(cè)策略

桂易琪,鞠爽爽

(揚(yáng)州大學(xué)信息工程學(xué)院,江蘇 揚(yáng)州 225100)

0 引 言

隨著互聯(lián)網(wǎng)的發(fā)展，人們對(duì)P2P流媒體的關(guān)注越來(lái)越密切。在這樣的背景下，以熱點(diǎn)視頻預(yù)測(cè)為切入點(diǎn)的研究引起了高度的重視，并成為未來(lái)的發(fā)展趨勢(shì)。對(duì)熱點(diǎn)視頻的預(yù)測(cè)是一種多模式的問(wèn)題，因?yàn)檎_的預(yù)測(cè)需要挖掘出很多視頻中未給出的潛在信息[1]。對(duì)于預(yù)測(cè)來(lái)說(shuō)，通過(guò)用戶的行為感知用戶的興趣愛(ài)好，起著非常關(guān)鍵的作用。但是，由于用戶操作的交互性及網(wǎng)絡(luò)狀態(tài)變化的隨機(jī)性，視頻預(yù)測(cè)的準(zhǔn)確性和有效性是一個(gè)緊要問(wèn)題。本文提出一種基于馬爾可夫修正模型的視頻預(yù)測(cè)策略。該策略能夠在用戶和網(wǎng)絡(luò)隨機(jī)變化的情況下，自適應(yīng)地對(duì)熱點(diǎn)視頻進(jìn)行預(yù)測(cè)，具有更高的可行性和準(zhǔn)確性。相比于使用神經(jīng)網(wǎng)絡(luò)，本文算法可避免復(fù)雜的訓(xùn)練過(guò)程，顯著提高視頻的播放質(zhì)量。

1 相關(guān)工作

最近幾年，為了提升視頻軟件的播放效率和質(zhì)量，國(guó)內(nèi)大量的學(xué)者對(duì)此進(jìn)行了廣泛研究。對(duì)熱點(diǎn)視頻段的選擇是P2P流媒體中一個(gè)具有挑戰(zhàn)性的領(lǐng)域，準(zhǔn)確地識(shí)別出熱門視頻至關(guān)重要[2]。

由于P2P流媒體中各節(jié)點(diǎn)可在服務(wù)節(jié)點(diǎn)和請(qǐng)求節(jié)點(diǎn)之間相互切換，所以用戶量的增多也會(huì)帶來(lái)服務(wù)節(jié)點(diǎn)跟請(qǐng)求節(jié)點(diǎn)的增多，這會(huì)導(dǎo)致網(wǎng)絡(luò)流量的增多。因此需要P2P流媒體中的緩存策略選擇合適的節(jié)點(diǎn)并合理地替換掉該節(jié)點(diǎn)中的視頻段，通過(guò)提高視頻段命中率的方式減少請(qǐng)求節(jié)點(diǎn)的搜尋時(shí)間，進(jìn)而減少網(wǎng)絡(luò)壓力。文獻(xiàn)[3]提出了一種基于訪問(wèn)集中的緩存替換策略。該策略根據(jù)視頻段的訪問(wèn)次數(shù)等指標(biāo)進(jìn)行緩存，這種方式類似于選擇流行度較高的視頻段進(jìn)行緩存；該策略通過(guò)一段時(shí)間積累用戶訪問(wèn)記錄，再運(yùn)行緩存替換策略，周期性地對(duì)節(jié)點(diǎn)中的數(shù)據(jù)進(jìn)行更新。文獻(xiàn)[4]提出了基于預(yù)測(cè)的網(wǎng)絡(luò)制造資源訪問(wèn)策略，對(duì)用戶查找頻率實(shí)現(xiàn)實(shí)時(shí)監(jiān)控，通過(guò)多項(xiàng)式回歸預(yù)測(cè)技術(shù)進(jìn)行動(dòng)態(tài)預(yù)測(cè)，以避免因用戶興趣改變而引起預(yù)測(cè)的不確定性。文獻(xiàn)[5]針對(duì)邊緣節(jié)點(diǎn)緩存空間有限的問(wèn)題，提出了一種基于猴群算法的優(yōu)化策略。該策略通過(guò)在猴群算法的猴群爬過(guò)程中引入文件流行度等引導(dǎo)因子和在望過(guò)程中改進(jìn)猴群視野范圍等方法找到最優(yōu)解，并合理地對(duì)邊緣節(jié)點(diǎn)的緩存內(nèi)容進(jìn)行替換，有效提高邊緣節(jié)點(diǎn)的請(qǐng)求命中率。文獻(xiàn)[6]提出了熱節(jié)點(diǎn)緩存優(yōu)化方案，提出了基于數(shù)據(jù)頻率的緩存算法。實(shí)驗(yàn)結(jié)果表明使用數(shù)據(jù)頻率緩存算法來(lái)緩存數(shù)據(jù)比傳統(tǒng)置換算法更趨近理論值，數(shù)據(jù)的請(qǐng)求延時(shí)相對(duì)較低。

文獻(xiàn)[7]提出了一個(gè)基于集群的合作緩存機(jī)制，即集群內(nèi)成員節(jié)點(diǎn)進(jìn)行內(nèi)存共享，在集群中的節(jié)點(diǎn)會(huì)有重復(fù)緩存的內(nèi)容，為了減少這些重復(fù)的內(nèi)容，所有集群成員的一部分緩存空間相互共享，該機(jī)制可以節(jié)約節(jié)點(diǎn)存儲(chǔ)空間，擴(kuò)大有效緩存。文獻(xiàn)[8]提出了一種基于SVC(可擴(kuò)展視頻編碼)的分割方法。該策略通過(guò)將視頻編碼分割再傳輸，可以有效降低數(shù)據(jù)在P2P流媒體中傳輸時(shí)遇到的復(fù)雜情況，減少數(shù)據(jù)丟失、數(shù)據(jù)錯(cuò)位等現(xiàn)象，提高了P2P網(wǎng)絡(luò)中數(shù)據(jù)傳輸?shù)姆€(wěn)定性。文獻(xiàn)[9]提出了一種基于ABR的激勵(lì)方案，目的是保證用戶的視頻播放質(zhì)量，同時(shí)減少云的帶寬消耗。文獻(xiàn)[10]提出了一種在P2P-VoD流系統(tǒng)中面向QoE的新穎塊調(diào)度，其中包含基于請(qǐng)求隊(duì)列的負(fù)載平衡(RQLB)策略和基于消除索引的緩存替換(EICR)策略。在提出的RQLB策略中，定義塊請(qǐng)求的優(yōu)先級(jí)，使高優(yōu)先級(jí)的請(qǐng)求得到及時(shí)處理。在設(shè)計(jì)EICR策略時(shí)，考慮到視頻中的塊可能具有不同的流行度，因此選擇緩存值最低的塊進(jìn)行替換，有效解決P2P-VoD流媒體系統(tǒng)中的塊調(diào)度問(wèn)題，保證了觀眾的QoE。為了使緩存結(jié)構(gòu)的共享性能最大化，文獻(xiàn)[11]提出了一種核心感知的重新引用間隔預(yù)測(cè)替換算法(CA-RRIP)。該算法對(duì)部分共享的緩存執(zhí)行動(dòng)態(tài)虛擬分區(qū)，保證了緩存的排他性，并可以減輕使用不同訪問(wèn)模式的內(nèi)核之間的交互。文獻(xiàn)[12]提出了一種P2P-TV流媒體節(jié)點(diǎn)上行速率控制算法，該算法對(duì)于網(wǎng)絡(luò)模型的不確定性、網(wǎng)絡(luò)參數(shù)的時(shí)變性以及網(wǎng)絡(luò)抖動(dòng)具有較強(qiáng)的魯棒性。文獻(xiàn)[13]針對(duì)如何使混合型架構(gòu)流媒體內(nèi)容分發(fā)系統(tǒng)服務(wù)容量最大的問(wèn)題，按照多文件分發(fā)的服務(wù)容量模型將帶寬分配問(wèn)題映射為背包問(wèn)題，提出了利用遺傳算法進(jìn)行服務(wù)器帶寬分配的方法，提高了系統(tǒng)服務(wù)容量。

內(nèi)容中心網(wǎng)絡(luò)(CCN)是面向未來(lái)Internet的新體系結(jié)構(gòu)[14]。CCN依賴于網(wǎng)絡(luò)內(nèi)緩存，并且數(shù)據(jù)的多個(gè)副本存儲(chǔ)在網(wǎng)絡(luò)中。任何具有數(shù)據(jù)的節(jié)點(diǎn)都可以滿足將來(lái)的請(qǐng)求，并有助于減少服務(wù)器的負(fù)載和網(wǎng)絡(luò)的擁塞。CCN[15-19]是一種新的客戶端/服務(wù)器網(wǎng)絡(luò)體系結(jié)構(gòu)，可通過(guò)使用多個(gè)服務(wù)器提高網(wǎng)絡(luò)傳輸效率并增加用戶數(shù)量。在內(nèi)容中心網(wǎng)絡(luò)體系結(jié)構(gòu)中，網(wǎng)絡(luò)中的每個(gè)路由節(jié)點(diǎn)都具有緩存功能。通過(guò)網(wǎng)絡(luò)內(nèi)緩存，CCN避免了當(dāng)前TCP/IP網(wǎng)絡(luò)中相同內(nèi)容的重復(fù)傳輸，因此CCN減少了網(wǎng)絡(luò)帶寬資源消耗，并加快了網(wǎng)絡(luò)對(duì)請(qǐng)求的響應(yīng)速度。所以，人們提出了一些以內(nèi)容為中心的網(wǎng)絡(luò)架構(gòu)(ICN)。這些架構(gòu)與傳統(tǒng)的服務(wù)器緩存不同，其主要利用網(wǎng)絡(luò)中的節(jié)點(diǎn)來(lái)緩存，這種無(wú)處不在的緩存可以提高內(nèi)容的分發(fā)效率以及避免過(guò)于集中的訪問(wèn)，而且緩存對(duì)應(yīng)用透明。這些卓越的功能給ICN緩存技術(shù)提出了新的挑戰(zhàn)，也是未來(lái)需要研究的切入點(diǎn)。

2 系統(tǒng)模型

新視頻剛上映時(shí)，由于沒(méi)有大量的用戶訪問(wèn)記錄，無(wú)法通過(guò)統(tǒng)計(jì)來(lái)獲得準(zhǔn)確的用戶觀看趨向和視頻段的流行度。馬爾可夫模型可以通過(guò)用戶訪問(wèn)記錄獲得用戶初始狀態(tài)和狀態(tài)轉(zhuǎn)移矩陣，在不受用戶訪問(wèn)記錄數(shù)量的約束下，獲得相比于統(tǒng)計(jì)學(xué)更為準(zhǔn)確的用戶趨向，再通過(guò)后續(xù)到達(dá)的用戶訪問(wèn)記錄不斷修正狀態(tài)轉(zhuǎn)移矩陣，可獲得較高的視頻段預(yù)測(cè)命中率。以下介紹本文所提策略。

為了提升用戶的觀影體驗(yàn)，使用戶在觀看視頻時(shí)隨意跳轉(zhuǎn)都不需要等待緩沖，本文通過(guò)分析用戶的歷史操作，建立馬爾科夫修正模型對(duì)用戶將要訪問(wèn)的段進(jìn)行預(yù)測(cè)，有選擇地解決預(yù)取問(wèn)題。由于用戶訪問(wèn)段不是隨機(jī)訪問(wèn)，都具有一定的規(guī)律，隨著用戶訪問(wèn)次數(shù)的增加，這種規(guī)律越發(fā)明顯。本文將馬爾科夫模型和指數(shù)加權(quán)平均模型進(jìn)行融合，在系統(tǒng)迭代過(guò)程中，使用指數(shù)加權(quán)平均模型修正狀態(tài)轉(zhuǎn)移矩陣。準(zhǔn)確緩存用戶即將要看的視頻段，提高段緩存的命中率。

在馬爾科夫預(yù)測(cè)模型中，根據(jù)用戶訪問(wèn)記錄即先驗(yàn)數(shù)據(jù)，提取出用戶訪問(wèn)規(guī)律，得出初始狀態(tài)轉(zhuǎn)移矩陣以及用戶訪問(wèn)初始概率。為便于表達(dá)，以下假設(shè)用6條數(shù)據(jù)產(chǎn)生狀態(tài)轉(zhuǎn)移矩陣。

表1 用戶訪問(wèn)記錄1

在表1用戶訪問(wèn)記錄中，用戶初始訪問(wèn)第1段的概率為2/15，訪問(wèn)第2段的概率為4/75，則用戶初始訪問(wèn)概率矩陣為：

(1)

從以上僅有的6條用戶訪問(wèn)記錄中可知，當(dāng)用戶訪問(wèn)第1段后，再次訪問(wèn)第1段的概率為0，訪問(wèn)第2段的概率為5/6，訪問(wèn)第3段的概率為1/6，訪問(wèn)其余段的概率為0；用戶訪問(wèn)第2段后，訪問(wèn)第1段的概率為1/7，訪問(wèn)第3段的概率為5/7，訪問(wèn)第4段的概率為1/7。以此類推，可得這6條數(shù)據(jù)的初始狀態(tài)轉(zhuǎn)移矩陣S0：

(2)

由于用戶具有較強(qiáng)的主觀意識(shí)，在系統(tǒng)迭代過(guò)程中，固定不變的狀態(tài)轉(zhuǎn)移矩陣無(wú)法準(zhǔn)確描述視頻段被訪問(wèn)概率的變化過(guò)程。先驗(yàn)概率在系統(tǒng)執(zhí)行初期能有不錯(cuò)的表現(xiàn)，但隨著系統(tǒng)的持續(xù)迭代，需要對(duì)狀態(tài)轉(zhuǎn)移矩陣進(jìn)行修正，使其能更準(zhǔn)確預(yù)測(cè)段的被訪問(wèn)概率。

本文使用指數(shù)加權(quán)平均模型對(duì)狀態(tài)轉(zhuǎn)移矩陣進(jìn)行修正，將舊的狀態(tài)轉(zhuǎn)移矩陣通過(guò)加權(quán)求和的方式加入到新的狀態(tài)轉(zhuǎn)移矩陣中。當(dāng)系統(tǒng)持續(xù)迭代時(shí)，新的用戶訪問(wèn)記錄加入到舊的訪問(wèn)記錄中，由于會(huì)有大量的用戶訪問(wèn)記錄，使用累加計(jì)算的方式求狀態(tài)轉(zhuǎn)移矩陣的計(jì)算量會(huì)逐步增大。考慮到用戶訪問(wèn)記錄之間的時(shí)序關(guān)系，本文使用滑動(dòng)窗口的方式，讀取用戶訪問(wèn)記錄，獲取“影子狀態(tài)轉(zhuǎn)移矩陣”。如圖1所示。

圖1 滑動(dòng)窗口示意圖

再使用指數(shù)加權(quán)平均模型對(duì)模型進(jìn)行修正，從t0時(shí)刻的用戶訪問(wèn)記錄中獲取t0時(shí)刻的狀態(tài)轉(zhuǎn)移矩陣S0；從t1時(shí)刻的用戶訪問(wèn)記錄中獲取t1時(shí)刻的狀態(tài)轉(zhuǎn)移矩陣S1；從t2時(shí)刻的用戶訪問(wèn)記錄中獲取t2時(shí)刻的狀態(tài)轉(zhuǎn)移矩陣S2。

則當(dāng)前時(shí)刻的狀態(tài)轉(zhuǎn)移矩陣估計(jì)Sn_now為：

(3)

表2為新的用戶訪問(wèn)后的用戶訪問(wèn)記錄表，其中用戶編號(hào)為7、8、9的記錄是新加入的用戶訪問(wèn)記錄。

表2 用戶訪問(wèn)記錄2

根據(jù)滑動(dòng)窗口的讀取方式，在t1時(shí)刻，從第4條～第9條訪問(wèn)記錄中提取狀態(tài)轉(zhuǎn)移矩陣。

則t1時(shí)刻的“影子狀態(tài)轉(zhuǎn)移矩陣”為：

(4)

可得t1時(shí)刻的狀態(tài)轉(zhuǎn)移矩陣估計(jì)為：

(5)

為便于本文所提狀態(tài)轉(zhuǎn)移矩陣的表述，此處設(shè)a=0.5，則：

(6)

由此，可以計(jì)算每個(gè)時(shí)間點(diǎn)的視頻段被訪問(wèn)概率，下面給出前3個(gè)時(shí)間點(diǎn)的視頻段被訪問(wèn)概率：

P1=P0×S0

(7)

(8)

(9)

本文提出的基于修正馬爾科夫預(yù)測(cè)模型的視頻段預(yù)測(cè)策略中，首先根據(jù)修正馬爾可夫模型預(yù)測(cè)出視頻段被訪問(wèn)概率， 再選擇訪問(wèn)概率較大的段進(jìn)行緩存。

基于馬爾可夫修正模型的視頻預(yù)測(cè)策略如表3所示。

表3 馬爾科夫修正預(yù)測(cè)模型(MMPM)

將基于馬爾可夫的視頻段預(yù)測(cè)策略搭載在基于流行度的緩存替換策略中，得出基于馬爾可夫鏈的緩存替換策略(CRA-MMPM)算法如表4所示。

表4 基于馬爾科夫修正模型的緩存替換算法(CRA-MMPM)

3 仿真實(shí)驗(yàn)

本文生成100,000個(gè)數(shù)據(jù)段，使其滿足正態(tài)分布，再將這100,000個(gè)數(shù)據(jù)段按圖2的分組方式分成10,000條數(shù)據(jù)，構(gòu)成用戶訪問(wèn)記錄數(shù)據(jù)集。

假設(shè)以1000條數(shù)據(jù)提取視頻段被訪問(wèn)概率和初始狀態(tài)轉(zhuǎn)移矩陣，9000條數(shù)據(jù)作為后續(xù)訪問(wèn)記錄，分9批進(jìn)入系統(tǒng)迭代。

圖2 仿真數(shù)據(jù)排列

具體仿真條件如表5所示。

表5 參數(shù)列表

本次實(shí)驗(yàn)用戶以10個(gè)為一組進(jìn)入系統(tǒng)，直到用戶數(shù)達(dá)到100，觀察其命中率變化，并設(shè)置計(jì)數(shù)器，每命中一次，該段計(jì)數(shù)器加1。

將策略MMPM分別基于緩存替換(CRA)和先進(jìn)先出(FIFO)算法運(yùn)行，并與CFCD[20]和PCN[21]進(jìn)行比較，具體仿真結(jié)果如圖3～圖6所示。

圖3和圖4分別表示CRA-MMPM和FIFO-MMPM在迭代過(guò)程中的命中率變化趨勢(shì)，并且加入基于流行度的先進(jìn)先出策略(FIFO-P)和基于流行度的關(guān)聯(lián)規(guī)則策略(VOVO-P)進(jìn)行比較。從圖中可看出，隨著迭代次數(shù)的增加，命中率越來(lái)越高，并且一直高于PCN和CFCD算法。由于沒(méi)有使用高級(jí)的流行度評(píng)估方式，在70次迭代之前，使用MMPM策略的算法命中率上升較快，隨著迭代次數(shù)的增加上升趨于緩慢，甚至保持不變。相比于FIFO，CRA具有較為科學(xué)的緩存替換方式，所以CRA-MMPM比FIFO-MMPM具有較高的命中率，且一直如此。

圖3 CRA-MMPM命中率1

圖4 CRA-MMPM命中率2

圖5 FIFO-MMPM命中率1

圖6 FIFO-MMPM命中率2

圖5和圖6對(duì)使用MMPM模型的算法與未使用MMPM的算法進(jìn)行比較。FIFO-MMPM相比其他的算法皆具有較高的命中率。由于在MMPM中融入了滑動(dòng)加權(quán)平均的方式將以前的狀態(tài)轉(zhuǎn)移矩陣進(jìn)行疊加，使得狀態(tài)轉(zhuǎn)移矩陣可以包含更多的信息，可以更有效地做出預(yù)測(cè)，相比于未使用預(yù)測(cè)策略的模型會(huì)取得更好的效果。

4 結(jié)束語(yǔ)

本文針對(duì)用戶的興趣愛(ài)好展開研究，對(duì)熱點(diǎn)視頻進(jìn)行預(yù)測(cè)。所謂預(yù)測(cè)，就是在服務(wù)器處理用戶請(qǐng)求的同時(shí)，利用預(yù)測(cè)算法對(duì)用戶下一步可能訪問(wèn)的視頻內(nèi)容進(jìn)行感知挖掘，將預(yù)測(cè)內(nèi)容存放在服務(wù)節(jié)點(diǎn)中。本文通過(guò)構(gòu)建用戶的歷史播放記錄，進(jìn)行實(shí)時(shí)監(jiān)測(cè)，提出了基于馬爾可夫修正模型的視頻預(yù)測(cè)算法，實(shí)現(xiàn)動(dòng)態(tài)預(yù)測(cè)，避免了因用戶興趣漂移引起的預(yù)取不確定性，提高了命中率及響應(yīng)速度，驗(yàn)證了算法的有效性、準(zhǔn)確性及快速性。