桂易琪,鞠爽爽

(揚州大學信息工程學院,江蘇 揚州 225100)

0 引 言

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

1 相關工作

最近幾年，為了提升視頻軟件的播放效率和質量，國內大量的學者對此進行了廣泛研究。對熱點視頻段的選擇是P2P流媒體中一個具有挑戰(zhàn)性的領域，準確地識別出熱門視頻至關重要[2]。

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

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

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

2 系統(tǒng)模型

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

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

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

表1 用戶訪問記錄1

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

(1)

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

(2)

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

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

圖1 滑動窗口示意圖

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

則當前時刻的狀態(tài)轉移矩陣估計Sn_now為：

(3)

表2為新的用戶訪問后的用戶訪問記錄表，其中用戶編號為7、8、9的記錄是新加入的用戶訪問記錄。

表2 用戶訪問記錄2

根據滑動窗口的讀取方式，在t1時刻，從第4條～第9條訪問記錄中提取狀態(tài)轉移矩陣。

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

(4)

可得t1時刻的狀態(tài)轉移矩陣估計為：

(5)

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

(6)

由此，可以計算每個時間點的視頻段被訪問概率，下面給出前3個時間點的視頻段被訪問概率：

P1=P0×S0

(7)

(8)

(9)

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

基于馬爾可夫修正模型的視頻預測策略如表3所示。

表3 馬爾科夫修正預測模型(MMPM)

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

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

3 仿真實驗

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

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

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

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

表5 參數(shù)列表

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

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

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

圖3 CRA-MMPM命中率1

圖4 CRA-MMPM命中率2

圖5 FIFO-MMPM命中率1

圖6 FIFO-MMPM命中率2

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

4 結束語

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