一種新的基于推薦的流媒體代理緩存替換機制

胡玉琦，李曉娜（.燕山大學信息科學與工程學院，河北秦皇島066004；2.河北省計算機虛擬技術與系統集成重點實驗室，河北秦皇島066004）

一種新的基于推薦的流媒體代理緩存替換機制

胡玉琦1，2，?，李曉娜1
（1.燕山大學信息科學與工程學院，河北秦皇島066004；
2.河北省計算機虛擬技術與系統集成重點實驗室，河北秦皇島066004）

摘 要：流媒體代理服務器緩存是有效緩解服務器負載、減少主干網傳輸的關鍵技術，而推薦算法是根據用戶歷史點播行為預測將被點播的可能性?，F有的緩存算法沒有考慮用戶推薦對點播的影響，為此本文首先提出一種融合相異度的協同過濾推薦算法CFCD。其次，針對CFCD算法的推薦結果，定義反映流媒體文件被用戶推薦程度的推薦度，并依此定義緩存價值函數，提出基于CFCD的流媒體代理緩存替換算法CRA＿CFCD。仿真實驗表明，CFCD算法能夠提高流媒體對象的推薦精度，而提出的CRA＿CFCD算法在緩存命中率和啟動延遲方面改善了點播系統的性能。

關鍵詞：代理緩存；緩存替換算法；協同過濾推薦算法；相異度；推薦度

0　引言

流媒體技術被廣泛應用于許多網絡服務中，如視頻點播、視頻會議和遠程教育等。其中，視頻點播系統能夠允許用戶點播觀看自己喜愛的視頻節目，因此迅速成為最為流行的網絡應用之一，僅YouTube每天就吸引了數以千萬計的網絡用戶，產生2 000 TB的流量［1］。然而，網絡視頻用戶規模的迅速擴張和視頻資源的不斷增多，都給流媒體服務器和傳輸網絡帶來巨大的挑戰。由于服務器過載和傳輸網絡阻塞等問題，傳統的C/S架構很難滿足大量用戶的點播請求，尤其是在用戶訪問高峰期。

流媒體代理服務器是部署在網絡邊緣，配置了一定緩存空間的一種特殊類型的服務器，緩存部分流媒體內容。用戶的視頻數據請求被定向給代理服務器，如果代理服務器緩存了用戶所需數據，代理直接將數據提供給用戶。否則，代理服務器首先向流媒體服務器請求該數據，然后再將數據發送給用戶。因此，代理服務器承擔了部分用戶請求，節省了流媒體服務器和主干網絡的帶寬資源，緩解了服務器過載和傳輸網絡阻塞等問題。由于代理緩存空間有限，緩存替換算法成為流媒體領域的研究熱點。

傳統的緩存替換算法包括LRU算法、LFU算法和LRU?K算法［2］。基于訪問最近性的LRU算法將上次訪問時間作為影響緩存價值的唯一因素。但是LRU算法容易出現對象剛被替換出緩存又被請求使用的情況。與LRU算法，LFU算法根據對象的訪問頻率來計算緩存價值，傾向于緩存訪問頻率較高的數據塊。但LFU算法存在緩存污染問題，即訪問頻率較高的數據對象即使不會再被訪問，依然占據緩存空間。LRU?K算法將LRU算法和LFU算法相結合，根據上次訪問時間和訪問頻率共同定義數據對象的緩存價值。該算法能夠提高代理服務器的性能，同時也避免LRU算法和LFU算法的缺陷。

除了以上介紹的經典緩存替換算法，許多研究者集中到流行度上，因為流行度越高的文件越熱門，近期被訪問的可能性越大。文獻［3］提出的PSU代理緩存策略，首先根據訪問頻率分別計算整個視頻文件和各個視頻段的流行度，然后，根據流行度將視頻文件劃分為不同的等級；最后，綜合考慮視頻文件的等級和視頻段的流行度來進行緩存替換操作。由于視頻段的數量過大，該算法中對各個視頻段的流行度的統計使系統開銷過大。文獻［4］提出基于最小代價的緩存替換算法，綜合考慮了數據塊的流行度和替換該數據塊所需的系統開銷。

優秀的緩存替換算法需要知道數據塊將來的訪問情況，以便在緩存替換時保留那些將來被訪問的可能性較大的數據。用戶的訪問行為決定了視頻對象的流行程度，間接地決定了數據塊將被訪問的可能性。因此，用戶行為預測成為緩存替換算法研究的重要部分。協同過濾推薦算法是目前應用最為成功的推薦技術，它能夠根據用戶的歷史評分記錄，預測出用戶的興趣愛好。因此，本文將協同過濾推薦算法引入到緩存替換算法中。

1　融合相異度的協同過濾推薦算法

目前，協同過濾推薦是所有推薦技術中應用最多的算法之一?；谟脩舻膮f同過濾推薦的核心是根據用戶評分矩陣計算用戶相似度，找到目標用戶的最近鄰居用戶；然后，通過最近鄰居用戶的興趣愛好預測目標用戶的興趣愛好。協同過濾推薦技術以其科學性和對社會情境的充分考慮，自從出現后便取得了巨大的成就，尤其是在電影和音樂等非結構化對象的推薦領域。

計算用戶相似度來尋找目標用戶的最近鄰居，是基于用戶的協同過濾推薦的關鍵步驟。然而，傳統的相似度計算方法更加重視用戶共同評分項目，或多或少地忽視了隱藏在用戶非共同評分項目中的、能夠反映用戶相似或相異關系的潛在信息。大多數情況下，相異度和相似度之間能夠相互轉化［5］。為了更加準確地計算用戶相似度，本文考慮了用戶相異度信息，在傳統相似度計算的基礎上結合相異度，提出結合相異度的協同過濾推薦算法CFCD（Collaborative Filtering Recom?mendation Algorithm Combined with Dissimilarity）。

目前，主要有4種相異度計算方法：城市?街區距離，歐幾里得距離，切比雪夫距離和閔可夫斯基距離。前3種方法均是第4種計算方法的一種特殊形式。為了降低CFCD算法的復雜性，以最簡單的城市?街區距離（又名為L1范式）為基礎，依據不同用戶對相同項目的評分差值來定義相異度。

定義1 U代表用戶集合，V代表視頻集合，u1∈U，u2∈U，v1∈V，用戶u1和u2的評分項目集合分別為Iu1和Iu2，且Uu1u2＝Iu1∪Iu2，Ru1，v1和Ru2，v1分別表示用戶u1和u2對視頻v1的評分值，用戶u1和u2的相異度為

由相異度定義，相似度計算公式為Rl（u1，u2）＝Sim（u1，u2）－Dis（u1，u2）·R，（2）其中，R代表相異度Dis（u1，u2）的權重系數，當R＝0時，CFCD退化為傳統的協同過濾推薦算法。根據大量實驗可知，使用余弦相似度、修正余弦相似度和皮爾遜相似度方法計算用戶間相似度時，余弦相似度能夠獲得更好的效果。因此，選用余弦相似度作為相似度Sim（u1，u2）。那么，

因此，用戶u1對視頻v2∈V的預測評分計算公式為

為了驗證提出的結合相異度的協同過濾推薦算法CFCD算法的性能，選取MovieLens數據集，以平均絕對誤差MAE（Mean Absolute Error）作為推薦算法的評價指標。MAE計算方法如下：

其中，n代表預測評分的個數，Pu1，v2表示用戶u1對視頻項目v2的預測評分值，Ru1，v2表示用戶u1對視頻項目v2的真實評分值。MAE代表了推薦算法預測評分和真實評分之間差值的平均值，反映了推薦算法預測評分的準確性。MAE值越小，說明推薦算法越精確。

選取R值分別為0，－20，－40，－60時，最近鄰居個數分別為5，10，15，20，25，30，35，40，45，50，55，60，65時，實驗結果如圖1所示。

圖1　CFCD與傳統算法的平均絕對誤差Fig.1　Mean absolute errors of CFCD and traditional algorithm

由圖1可知，當R值為－20，－40，－60時，CFCD算法的MAE值雖然幾乎一致，但均小于傳統的協同過濾推薦算法（即R＝0時），可見改進的CFCD算法的推薦是相對準確的，大約平均絕對誤差減小10%以上。

2　推薦度

推薦算法能夠預測用戶的訪問行為，通過對用戶訪問行為的預測，能夠判斷流媒體對象的熱門程度，因此，本文基于推薦算法來改進緩存替換算法。

2.1流媒體文件的推薦度

協同推薦算法中，預測評分值的高低在一定程度上代表了視頻項目被推薦給用戶的程度。對于同一個用戶來說，不同的預測評分值代表用戶不同的喜歡程度。預測評分值越高，喜歡的程度越高，被推薦的程度越高。但是，對不同用戶，由于用戶的評分尺度不同，不能完全根據預測評分值的大小判斷用戶對項目的喜歡程度或者項目被推薦的程度。因此，怎樣消除用戶評分尺度的影響，客觀地量化項目被推薦的程度是一個需要解決的問題。本文定義推薦度的概念，表示項目被推薦給用戶的程度。

定義2 U代表用戶集合，V代表視頻集合，u1∈U，v2∈V，Pu1，v2代表用戶u1對視頻v2的預測評分值，代表用戶u1對所有項目的評分平均值，Nu1表示用戶u1的最近鄰居集合，設u2∈Nu1，則視頻v2被推薦給用戶u1的程度DoRu1，v2定義為

那么，視頻v2被所有用戶推薦的程度為

當用戶登錄到代理服務器時，基于用戶的協同過濾推薦算法會將預測評分值較高的視頻項目推薦給用戶。然后，推薦結果中的預測評分值被轉化為用戶對各推薦視頻的推薦度。最后，本次推薦行為產生的所有推薦度會根據式（8）更新到各視頻項目的推薦度中，實現各視頻文件推薦度的動態更新。如果視頻文件的推薦度越大，說明該視頻被推薦的次數越多或者是某幾次被推薦的程度越大，那么該視頻文件將來被用戶訪問的可行性越大，被代理服務器緩存的價值越高。

2.2數據塊的推薦度

由于流媒體文件數據量大，如果將整個流媒體文件作為代理服務器的緩存單元，緩存空間很快會被耗盡。同時，同一視頻文件的不同部分具有不同的流行度，為了提高緩存空間的利用率，將流媒體文件各個分塊作為訪問的基本單位，根據整個視頻文件的推薦度計算各個視頻數據塊的推薦度。

定理1 V代表視頻集合，v2∈V，DoRv2代表視頻v2被推薦的程度，視頻v2的文件時間長度為L（單位：min），均等分長度為B，視頻v2的數據塊編號為n（n＝0，1，…）。假設視頻播放結束位置均勻分布且不考慮VCR操作影響［5］，那么視頻v2的數據塊n的推薦度DoRv2（n）為

DoRv2（n）＝DoRv2·（1－n·B/L）。（9）

由分析可知，推薦度越大，說明被觀看的概率越大，所以數據塊之間的推薦度和被觀看的概率成正比關系。因此，

Pv2（n）/Pv2（0）＝DoRv2（n）/DoRv2（0），（12）根據式（10）和（11），式（12）擴展為：

取視頻文件的第一個數據塊的推薦度為整個視頻文件的推薦度，即

因此，由式（13）得由于α服從0到1之間的均勻分布，則P（L·α/B≥n）＝P（α≥n·B/L）＝1－n·B/L，（16）因此，視頻文件v2的數據塊n的推薦度可以根據式（9）計算。并且，數據塊的推薦度是決定該數據塊是否被緩存的關鍵。

3　基于CFCD的緩存替換算法CRA＿CFCD

3.1緩存價值函數（Caching Value Function）

推薦算法能夠預測用戶的興趣愛好，獲知流媒體數據塊被用戶訪問的可能性。根據從CFCD算法中得出的數據塊的推薦度，定義基于數據塊推薦度的緩存價值函數：

其中，Cvalue（v2，n）代表視頻文件v2中數據塊n的緩存價值，它主要和視頻文件v2的推薦度和數據塊在文件中的位置有關，從而提出基于CFCD的緩存替換算法CRA＿CFCD（Cache Replacement Algorithm Based on CFCD），算法中的參數說明如表1所示。

表1　參數說明Tab.1　Notes of parameters

3.2算法描述

系統的基本工作流程如下：

1）任意用戶u∈U，當u登錄到代理服務器時，CFCD算法將預測評分值較高，即用戶將來觀看可能性較大的視頻項目推薦給用戶。

2）根據步驟（1）的推薦結果，生成用戶u的推薦集K（u）。K（u）包含了用戶u推薦的各個視頻項目v∈V及用戶u對視頻v的推薦度DoRu，v，構成序偶，集合K（u）的元素表示為k（u）＝（v，DoRu，v）。

3）步驟（2）中得到的用戶u的推薦視頻k（u）∈K（u），根據式（8），將用戶u對視頻v的推薦度更新到視頻v的推薦度DoRv中，以使所有視頻文件的推薦度隨著用戶的觀看行為而動態變化。

4）用戶開始視頻點播和觀看，代理服務器使用CRA＿CFCD算法進行緩存替換操作。CRA＿CFCD緩存替換算法描述如下：算法1 緩存替換算法CRA＿CFCD

4　實驗及性能分析

4.1仿真環境

為了真實地模擬代理服務器中緩存策略的性能，需要生成用戶的請求序列。一般有兩種方法：一種是概率模擬，即根據統計數據中呈現出的規律性來模擬事件發生的概率，另一種是軌跡驅動模擬，是根據現實服務器中記錄的訪問日志來進行的。這里選擇第2種方法，即軌跡驅動模擬，使用流行的數據集MovieLens，并將其以8∶2的比例分割成推薦模塊的訓練集和緩存替換模塊的用戶請求序列。Movielens數據集來源于Movielens網站真實的用戶訪問記錄，滿足Zipf規律。采用指數分布數據發生器產生前后兩個用戶訪問請求進入系統的時間間隔。設定用戶登錄到系統選擇影片時，接受推薦影片的概率為0.6，并假定被推薦的所有影片中被用戶選擇的概率相等，并且用戶訪問強度隨時間段而變化。

設緩存比例f為緩存空間大小和流媒體文件總大小的比值，取60%以下。其它的仿真參數如表2所示。

表2　仿真參數取值Tab.2 Values of simulation parameters

4.2結果分析

使用緩存命中率和用戶平均啟動延遲兩個指標來評價緩存替換算法的性能，并選用LRU算法、LFU算法作為對比算法。當緩存比例f分別為0.1，0.15，0.2，0.25，0.3，0.35，0.4，0.45，0.5，0.55時進行實驗。

1）緩存命中率（Cache hit ratio）

緩存命中率是代理緩存服務器滿足的用戶請求個數與用戶總的請求個數的比值，反映了代理服務器緩存空間的利用率，緩存命中率越高，緩存空間的利用率越高。

由圖2可知，隨著緩存比例的增加，代理服務器能夠緩存數據塊增多，所以緩存命中率提高。當緩存比例較小時，本文提出的CRA＿CFCD算法的命中率明顯高于LRU和LFU算法，例如，當25%的媒體數據被緩存時，傳統的LRU和LFU緩存替換算法的命中率大約是30%，而改進的CRA＿CFCD算法的命中率是45%。而隨著緩存比例的增大，這種差異有漸小的趨勢，因為流媒體文件的訪問頻率滿足Zipf規律，即小部分的流媒體文件被大部分的用戶訪問，所以當緩存比例較大時，緩存空間將滿足用戶所需的大部分數據，緩存替換算法的作用減弱。

圖2　緩存替換算法的命中率比較Fig.2　Comparisons of cache hit ratios of cache replacement algorithms

2）平均啟動延遲（Average Start?up latency）

啟動延遲是指從用戶發出請求到接收到請求的數據所需的時間間隔，它反映了用戶開始視頻觀看的等待時間。用戶啟動延遲越小，用戶體驗效果越好。

由圖3可知，本文提出的CRA＿CFCD算法比LRU和LFU算法能夠獲得較低的啟動延遲。

圖3　緩存替換算法的啟動延遲比較Fig.3　Comparisons of start?up latency of cache replacement algorithms

5　結論

流媒體代理服務器能夠緩存將來可能被訪問的數據塊，承擔部分用戶請求，減少流媒體服務器和主干網的負載。為了提高緩存空間的利用率，代理服務器刪除緩存價值最小的數據塊。推薦算法能夠預測用戶的訪問行為，本文基于推薦算法來設計緩存替換算法。首先，對協同過濾推薦算法中的相似度計算方法進行改進，提出了結合相異度的協同過濾推薦算法CFCD。然后，基于CFCD定義了緩存價值函數、提出了改進的緩存替換算法CRA＿CFCD，得出如下結論：

1）從CFCD推薦算法中得出：在傳統相似度的基礎上結合相異度計算用戶關系的方法是有效的，它能夠提高推薦算法的精度。

2）在改進的緩存替換算法CRA＿CFCD中，引入協同過濾推薦算法，能夠提高緩存替換算法的性能，開辟了改進緩存替換算法的新途徑。

3）基于推薦的緩存替換算法的性能和使用的推薦算法的性能是相關的（相關的實驗驗證由于篇幅限制，未能附上），今后我們將嘗試利用各種推薦算法改進緩存替換算法。

參考文獻

［1］Neves M Rodrigues M Azevêdo E et al.Selecting the most suited cache strategy for specific streaming media workloads C //2013 IFIP/IEEE International Symposium Ghent 2013 792?795.

［2］林子雨 賴明星 鄒權 等.基于替換概率的閃存數據庫緩沖區替換算法 J .計算機學報 2013 36 8 1568?1581.

［3］Ge Yang.A proxy caching algorithm based on popularity for stream?ing media C //9th International Conference on Natural Computa?tion Shenyang 2013 1520?1525.

［4］Keshavarzi M Dehghan M Mashinchi M.Applications of Classifica?tion Based on Similarities and Dissimilarities J .Fuzzy Information and Engineering 2012 4 1 75?91.

［5］Krishnamoorthi V Carlsson N Eager D et al.Proxy?Assisted HTTP?Based Adaptive Streaming Performance C //IEEE 21st International Symposium on Modeling Analysis＆Simulation of Computer and Telecommunication Systems San Francisco 2013 182?191.

A new proxy cache replacement mechanism of multimedia streams based on recommendation

HU Yu?qi1，2，LI Xiao?na1
（1.School of Information Science and Engineering，Yanshan University，Qinhuangdao，Hebei 066004，China；2.The Key Laboratory for Computer Virtual Technology and System Integration of Hebei Province，Qinhuangdao，Hebei 066004，China）

Abstract：Streaming media proxy cache is the key technology of reducing load of streaming media server and transmission network.Recommendation algorithm is based on the historical access behavior of users to predict which media data would be probably re?quested in the further.The traditional cache replacement mechanisms have not concluded user′s recommendation influences.Firstly，CFCD（Collaborative Filtering Recommendation Algorithm Combined with Dissimilarity）algorithm is proposed.Secondly，Recom?mended Degree of a media file is defined based on the analysis of the CFCD recommendation result.And then CRA＿CFCD（Cache Replacement Algorithm Based on CFCD）is proposed.Finally，Extensive simulations show that the CFCD algorithm can enhance the accuracy of the recommendations，CRA＿CFCD is more effective in cache hit ratio and start?up latency.

Key words：proxy cache；cache replacement algorithm；collaborative filtering recommendation；dissimilarity；recommended degree

作者簡介：?胡玉琦（1964?），女，黑龍江齊齊哈爾人，博士，副教授，主要研究方向為多媒體網絡、移動多媒體技術，Email：hu＿yuqi＠sina.com。

基金項目：教育部科技發展中心專項研究課題基金資助項目（2011109）

收稿日期：2014?09?02

文章編號：1007?791X（2015）02?0139?06

DOI：10.3969/j.issn.1007?791X.2015.02.007

文獻標識碼：A

中圖分類號：TP939.09