朱琛剛　程　光　胡一非　王玉祥

(東南大學計算機科學與工程學院　南京　211189)(教育部計算機網(wǎng)絡和信息集成重點實驗室(東南大學)　南京　211189)(gcheng@njnet.edu.cn)

基于流行度預測的互聯(lián)網(wǎng)+電視節(jié)目緩存調(diào)度算法

朱琛剛程光胡一非王玉祥

(東南大學計算機科學與工程學院南京211189)(教育部計算機網(wǎng)絡和信息集成重點實驗室(東南大學)南京211189)(gcheng@njnet.edu.cn)

摘要針對互聯(lián)網(wǎng)+電視平臺為提高熱點節(jié)目命中率而過渡消耗存儲空間的問題，提出一種基于流行度預測的節(jié)目緩存調(diào)度算法PPRA(popularity prediction replication algorithm).首先，在對實際測量數(shù)據(jù)進行統(tǒng)計與分析的基礎上，使用隨機森林(random forests, RF)算法構(gòu)建節(jié)目流行度預測模型.同時，針對所選特征存在的“維數(shù)災難”問題，利用主成分分析法(principal component analysis, PCA)實施特征降維處理，以實現(xiàn)視頻流行度預測值的快速計算.然后基于節(jié)目流行度預測數(shù)據(jù)調(diào)度緩存中的節(jié)目.最后以某廣電運營商130萬用戶120 d的收視數(shù)據(jù)為例，對PPRA算法進行實驗.實驗結(jié)果表明，在保證一定緩存命中率前提下，與LRU,LFU算法相比，PPRA算法僅需30%的存儲空間，可有效降低互聯(lián)網(wǎng)+電視平臺的建設成本.

關鍵詞互聯(lián)網(wǎng)+電視；流行度預測；隨機森林；緩存策略；維數(shù)災難

為克服傳統(tǒng)廣播電視要求用戶在固定時間及地點收看特定電視臺播出的特定節(jié)目，無法滿足當今用戶空間移動化、時間碎片化和內(nèi)容個性化需求的缺點，互聯(lián)網(wǎng)+電視網(wǎng)絡通過大數(shù)據(jù)分析技術(shù)，從海量用戶行為數(shù)據(jù)中分析當前用戶的收視興趣，有的放矢地向用戶提供符合用戶興趣的節(jié)目內(nèi)容，為用戶提供個性化的電視節(jié)目，給用戶帶來更加人性化的體驗.為此，互聯(lián)網(wǎng)+電視網(wǎng)絡系統(tǒng)通過將熱點節(jié)目緩存在邊緣服務器上，有效降低網(wǎng)絡訪問流量和播放時延.但為保證一定的節(jié)目緩存命中率，現(xiàn)有節(jié)目緩存調(diào)度算法需要消耗大量存儲空間，增加了緩存建設成本，阻礙了互聯(lián)網(wǎng)+電視的進一步推廣.

針對此問題，本文通過對實際互聯(lián)網(wǎng)+電視平臺數(shù)據(jù)分析，發(fā)現(xiàn)節(jié)目流行度與用戶點播量、播出時間、節(jié)目內(nèi)容、制作方等因素密切相關，在定性分析這些關系的基礎上，提出一種基于流行度預測的緩存調(diào)度算法PPRA(popularity prediction replication algorithm).該算法首先使用隨機森林(random forests, RF)算法建立了節(jié)目流行度的預測模型，采 用主成分分析法(principal component analysis, PCA)對模型輸入實施特征降維處理，實現(xiàn)流行度預測值的快速計算;然后通過比較各節(jié)目的預測流行度決定調(diào)入緩存的節(jié)目內(nèi)容;最后，以某廣電運營商的130萬云媒體電視用戶行為數(shù)據(jù)為例，對所提出的算法進行測試.實驗結(jié)果表明，在保證一定緩存命中率的前提下，與近期最少使用(least recently used, LRU)[1]算法、最近最不常用置換算法(least frequently used，LFU)[2]算法相比，PPRA算法僅需30%的存儲空間，可有效降低互聯(lián)網(wǎng)+電視平臺建設成本.

1相關工作

1.1流行度預測

節(jié)目流行度是節(jié)目收視量的表現(xiàn)，收視量越大流行度越高.節(jié)目流行度作為反映節(jié)目熱度的重要指標，不僅能夠幫助運營商在購買節(jié)目版權(quán)時做出決策，指導廣告商合理分配廣告投入，而且能夠作為邊緣內(nèi)容分發(fā)網(wǎng)絡(CDN)緩存調(diào)度的重要依據(jù).目前針對在線視頻、圖像、音樂、微博、話題的流行度分析和預測是當前研究的熱點和難點.近期的研究工作大多通過在具體情境下引入更多的分析特征，以提高預測的準確率和覆蓋率.

Wang等人[3]通過分析用戶在騰訊微博中轉(zhuǎn)發(fā)優(yōu)酷視頻鏈接的行為，采用神經(jīng)網(wǎng)絡算法構(gòu)建視頻流行度模型，在不依賴歷史收視數(shù)據(jù)的情況下取得了良好的預測精度.Vallet等人[4]綜合社交網(wǎng)絡和視頻發(fā)布平臺的數(shù)據(jù)，提出基于傳染病傳播的流行度預測模型，實現(xiàn)了對YouTube上點播量瞬間爆發(fā)視頻的預測.孔慶超等人[5]研究了影響網(wǎng)絡討論帖流行度的動態(tài)因素，并提出一種基于動態(tài)演化的討論帖流行度預測模型.Ding等人[6]通過分析社交網(wǎng)絡中流行圖片和非流行圖片的特征，提出一種用于預測圖片流行度的模型.Figueiredo[7]研究了YouTube視頻流行趨勢，給出了UGC視頻特征和節(jié)目流行度的關系.Pinto等人[8]利用節(jié)目上線初期的點播數(shù)據(jù)，提出了一種適用于YouTube平臺的內(nèi)容流行度預測算法，有效地降低了預測偏差.Ahmed等人[9]使用內(nèi)容自身流行度的比例變化與用戶關注其他內(nèi)容流行度的比例變化之間的相似程度，得出內(nèi)容在不同時間段聚類組的轉(zhuǎn)換關系.Sanner等人[10-11]利用Twitter數(shù)據(jù)對YouTube平臺內(nèi)容流行度進行分析，采用轉(zhuǎn)移學習算法有效預測出視頻流行度發(fā)生突變的情況.Chang等人[12]采用自動回歸模型捕獲用戶行為變化的特征，實現(xiàn)了對網(wǎng)絡連續(xù)劇內(nèi)容的質(zhì)量分析和流行度預測.McParlane等人[13]為解決預測內(nèi)容缺乏標簽、評論等交互數(shù)據(jù)導致的冷啟動問題，使用圖片、用戶上下文信息以及視覺感受預測Flickr圖片的流行度，取得了良好的效果.

1.2緩存調(diào)度

CDN網(wǎng)絡中如何高效地管理邊緣服務器的緩存空間是當前國內(nèi)外研究的熱點問題.緩存策略主要由緩存替換算法和緩存決策算法2部分構(gòu)成.緩存替換算法負責在有限的緩存空間下尋找出最合適的內(nèi)容數(shù)據(jù)進行緩存；緩存決策算法為需要緩存的數(shù)據(jù)尋找合適的存儲節(jié)點.因此，如何在有限的緩存空間下設計高效的緩存策略，從而提高緩存命中率、降低網(wǎng)絡帶寬消耗，是緩存管理的關鍵.

Abrahamsson等人[14]通過分析一個在線時移系統(tǒng)的用戶點播記錄，發(fā)現(xiàn)20%的節(jié)目產(chǎn)生了80%的點播請求.如果能夠合理地緩存熱點節(jié)目，可以很好地降低系統(tǒng)的帶寬消耗.Balachandran等人[15]分析了3 000萬的視頻會話數(shù)據(jù)，發(fā)現(xiàn)用戶在使用VOD服務時存在同步收視的特征，采用混合P2P-CDN的方式能有效降低CDN的建設成本.Zhou等人[16]研究了VOD系統(tǒng)中不同類型節(jié)目流行度的變化規(guī)律，并提出一種FIFO和LFU混合緩存策略，取得了較好的效果.Gouta等人[17]提出了一種ICN網(wǎng)絡中動態(tài)自適應流行度變化的流緩存策略.Abrahamsson等人[18]研究了影響緩存效果的諸多因素，包括節(jié)目流行度、節(jié)目大小、緩存策略等.Nencioni等人[19]通過在機頂盒硬盤上提前錄制用戶可能收視節(jié)目，有效降低高峰時段的網(wǎng)絡流量.Agrawal等人[20]通過緩存不定長的影片片段取得了相比LRU算法更好的命中率.Akhtar等人[21]提出了一種用于緩存在線影片的分層過濾算法，該算法復雜性類似于LRU，但在命中率、替換率和緩存吞吐量上均有明顯提升.Park等人[22]提出了一種自適應流行度分布的二元緩存算法，在緩存較小時取得了良好的效果.王永功等人[23]提出了一種基于預過濾的改進算法，通過對原始內(nèi)容的整形使得內(nèi)容更容易被后續(xù)緩存命中.

以上有關緩存策略的研究中，各邊緣節(jié)點在進行決策時均未綜合考慮內(nèi)容的流行度和緩存容量等因素.一些算法片面追求緩存命中率，沒有考慮緩存空間和內(nèi)容總量的關系，造成整個系統(tǒng)建設與運營成本高昂，性價比較低.

2互聯(lián)網(wǎng)+電視節(jié)目的流行度特征

目前流行度的研究對象主要集中于視頻、圖像、微博、分享鏈接等.流行度的定義與具體的應用相關.本文研究對象是互聯(lián)網(wǎng)+電視平臺中的節(jié)目，因此將節(jié)目在某段時間窗口內(nèi)的點播量以及節(jié)目點播量在總片庫中的排名數(shù)據(jù)作為節(jié)目流行度的度量.

2.1數(shù)據(jù)描述

本文數(shù)據(jù)采集是某廣電運營商互聯(lián)網(wǎng)+電視平臺2015-01-01—2015-04-30共計120 d的用戶時移回看記錄和電子節(jié)目指南數(shù)據(jù).本文主要關注基于IP技術(shù)的互聯(lián)網(wǎng)+電視，采集數(shù)據(jù)不包括傳統(tǒng)直播業(yè)務的收視記錄.通過對服務器RTSP日志的清洗，用戶回看記錄、電子節(jié)目指南都作為一條記錄存儲在ORACLE數(shù)據(jù)庫中.表1總結(jié)了數(shù)據(jù)集的具體情況.本文共收集了130.9萬個用戶2.01億次回看記錄，節(jié)目數(shù)量總計42.3萬個.每條回看記錄包含機頂盒序列號、回看時間、節(jié)目名稱、頻道名稱；每條電子節(jié)目指南包括頻道名稱、節(jié)目名稱、節(jié)目類型、節(jié)目時長、播出日期、拍攝日期、導演、演員信息.

Table 1　Internet Plus TV Data Set in Figures

通過對120 d的點播行為數(shù)據(jù)(如圖1所示)進行分析，發(fā)現(xiàn)在線用戶數(shù)(clients)和節(jié)目數(shù)(programs)基本穩(wěn)定在相對固定的范圍，而收視次數(shù)(requests)隨時間呈現(xiàn)周期性震蕩.點播次數(shù)在每周六通常會出現(xiàn)一個高峰.數(shù)據(jù)采集周期內(nèi)，平均每天點播次數(shù)達167.5萬次.

Fig. 1　Number of requests, active clients, and distinct programs requested over 120 days.圖1　點播量用戶節(jié)目在采集周期內(nèi)的總體情況

Fig. 2　Number of requests of top10, top500 and all programs for an hour in a week.圖2　一周內(nèi)每小時top10,top50和所有節(jié)目的點播量

2.2流行度與時間關系

在觀測周期內(nèi)，點播量以周為單位存在明顯的周期變化.周末的點播量明顯高于工作日的點播量.圖2展示了一周之內(nèi)每小時的點播量數(shù)據(jù).通過圖2可以發(fā)現(xiàn)，一周內(nèi)的所有節(jié)目點播次數(shù)呈現(xiàn)出明顯的周期性，其中周六和周日在一周中的點播量最大，而在每天晚間20:00—21:00是收視高峰期;此外在每天中午的12:00—13:00會出現(xiàn)一個小高峰，而在下午會有所回落，直到傍晚16:00之后，點播量開始逐漸上升.總體看來，Top10和Top500的節(jié)目也呈現(xiàn)出同樣的特征.

2.3流行度與內(nèi)容關系

Fig. 4　Requests and rank for movies, TV show, news and children’s programs for seven days.圖4　電影、綜藝、新聞和卡通7日點播量和收視排名變化

觀測周期內(nèi)，平均每天有4.5萬個節(jié)目被點播.排名最高的節(jié)目累計點播量接近20萬次，大部分節(jié)目的累計點播量不足1 000次.圖3是收視次數(shù)與節(jié)目排名的累積分布，可以看出排名前10%的節(jié)目占據(jù)了75%的點播量，排名前20%的節(jié)目占據(jù)了90%的點播量，呈現(xiàn)出明顯的長尾效應.

Fig. 3　Cumulative distribution of requests to programs.圖3　收視次數(shù)隨節(jié)目排名的累積分布

本文將節(jié)目分為電影、電視劇、新聞、少兒和綜藝.由于收視人群的不同以及各期節(jié)目之間的關聯(lián)性，造成不同類型節(jié)目的流行度呈現(xiàn)不同的變化趨勢.

圖4(a)為一部熱播電影上線以來的點播量以及每天的點播排名變化情況.可以發(fā)現(xiàn)，電影節(jié)目在上線初期點播量很大且排名很高，隨上線時間變長，其點播量和排名均會同步下降;在周末，點播量會出現(xiàn)一個明顯的回升.

圖4(b)為綜藝節(jié)目點播量以及點播排名變化情況.可以看出節(jié)目在上線初期的點播量較高;而后出現(xiàn)下降的情況;與其他類型節(jié)目不同，真人秀節(jié)目會周期性出現(xiàn)一些點播的高點，而這一周期正好與真人秀節(jié)目的播放周期一致.

圖4(c)為單條新聞發(fā)布48 h內(nèi)的點播量以及點播排名變化情況.可以發(fā)現(xiàn)，新聞剛發(fā)布，即帶來較高的點播量，其排名也較高，但點播量和排名在48 h內(nèi)都會快速下降.

圖4(d)為兒童動漫節(jié)目點播量以及點播排名變化情況.可以發(fā)現(xiàn)，動漫節(jié)目在上線初期的點播量特別大，然后會下降;與其他類型節(jié)目不同的是，動漫節(jié)目在上線一段時間后仍會保持比較穩(wěn)定的點播量和點播排名;此外，動漫節(jié)目在周六和周日的點播量會明顯高于一般工作日.

2.4流行度與節(jié)目制作方關系

同樣內(nèi)容和類型的節(jié)目，由于導演、演員、制片公司、宣發(fā)頻道和首播時間的不同，點播量和排名變化也呈現(xiàn)出不同的趨勢.

節(jié)目是否符合當前觀眾的興趣口味，節(jié)目本身的制作水平是關鍵的影響因素，與導演風格、演員的當紅程度、制作公司能力息息相關.在觀測的120 d內(nèi)，本文整理了445位導演和2 008位演員的節(jié)目數(shù)據(jù)，發(fā)現(xiàn)16%的導演制作的節(jié)目產(chǎn)生了80%的點播量，15%的演員參演的節(jié)目產(chǎn)生了80%的點播量.圖5(a)為在相同宣發(fā)頻道、相同內(nèi)容主題的前提下，不同制作方拍攝節(jié)目的流行度隨時間的變化.可以看出，不同演員和導演制作的節(jié)目會產(chǎn)生截然不同的流行度.

Fig. 5　Influence of film production and distribution corporation on programs popularity.圖5　不同制作方和宣發(fā)頻道對節(jié)目流行度的影響

宣發(fā)頻道的實力和定位也影響著節(jié)目的點播量和排名變化.宣發(fā)頻道是否有足夠?qū)嵙υ诠?jié)目播出前在觀眾群中為節(jié)目預熱、宣發(fā)頻道本身帶來的收視慣性，以及該宣發(fā)頻道的定位是否與節(jié)目風格符合都直接影響節(jié)目上線后的流行度.圖5(b)為相同節(jié)目在不同宣發(fā)頻道上的流行度變化，可以看出，宣發(fā)頻道對節(jié)目流行度有直接的影響.

3PPRA算法

從第2節(jié)分析可看出,可通過選取多個不同特征來描述一個節(jié)目,如上線日期、播出時間、節(jié)目類型等,而節(jié)目流行度與所選取的節(jié)目特征之間有很強的關聯(lián)性,因此本文選用一系列有監(jiān)督學習的方法來對節(jié)目的歷史數(shù)據(jù)進行分析和學習,從而提取影響節(jié)目流行度的關鍵特征，并構(gòu)建節(jié)目流行度隨時間變化的模型,根據(jù)某個節(jié)目的特征和該節(jié)目上線以來的歷史數(shù)據(jù)預測該節(jié)目未來7 d的流行度,為節(jié)目的緩存調(diào)度提供合理的理論依據(jù).

3.1數(shù)據(jù)預處理及輸入特征選取

在本文第2節(jié)中,已經(jīng)描述了若干對節(jié)目流行度有顯著影響的特征,但是由于這些特征并不能夠直接作為機器學習算法模型的輸入,所以需要對其進行預處理.

1) 上線時間.圖4為電影、綜藝、新聞和卡通4類電視節(jié)目7 d的點播量和收視變化，可以看出，隨著節(jié)目上線時間的增長，節(jié)目的點播量和收視排名均會出現(xiàn)下降.因此，新上線節(jié)目往往會比老節(jié)目更加受歡迎,本文用“距離首次上線的天數(shù)”這一指標衡量上線時間帶來的影響，如式(1)所示:

(1)

其中，T為觀測日期,T0為節(jié)目首次上線時間.

2) 頻道、節(jié)目類型.圖5為不同制作方和宣發(fā)頻道對節(jié)目流行度的影響，可以看出宣發(fā)頻道和節(jié)目類型對節(jié)目的流行度有直接的影響.同時，此類特征屬于類型特征,每一個特征都有m個不同的取值,但同時只有一個是有效的.本文將其轉(zhuǎn)換成采用One-Of-K編碼模式的特征,即如果一個特征有m個不同的取值,則用一組長度為m且只有一位為1的二進制數(shù)來表示.

3) 節(jié)目標簽、導演、演員.本文的觀測數(shù)據(jù)集中，包含445位導演和2 008位演員，通過分析發(fā)現(xiàn)80%的點播量由16%的導演制作的節(jié)目產(chǎn)生，15%的演員參演的節(jié)目產(chǎn)生了80%的點播量.此類特征和節(jié)目類型有相似之處,都會有m個不同的取值,但不同的是有效取值可以同時存在多個.對其采用類似的處理方法,轉(zhuǎn)換為長度為m的二進制位后,將每一個有效的位用1來表示,其余則為0.需要指出的是,導演和演員的數(shù)量眾多,如果不加處理直接使用會導致樣本屬性維度過大、訓練結(jié)果過擬合.因此在訓練前，篩選貢獻80%流行度的導演和演員,將導演和演員的數(shù)量分別從445位和2 008位減少到223位和1 202位.

4) 播放時間.從圖2可以看出，不同時間段的點播量存在較大差異.本文將一天按24 h劃分為24個時間段,根據(jù)節(jié)目播放的時間，為其標記1—24當中對應的值,然后再根據(jù)類型特征的預處理方法進行處理.

3.2流行度預測模型的訓練

Biau[24]對RF算法的適用場景和計算模型進行了分析和改進，改進后的RF可以用來做分類、聚類、回歸和生存分析.本文選用RF模型的原因有3點：

1) 經(jīng)過預處理后的特征維度會達到2 000的數(shù)量級，即使經(jīng)過一系列的降維處理，仍會有100.而RF算法得益于算法中雙重抽樣的環(huán)節(jié)，在面對高維特征時仍有較好的性能和較高的準確性.

2) RF算法在學習完成后可以給出特征的重要性，這對于分析特征對點播率的影響有很大的作用.

3) 本文的目標是根據(jù)節(jié)目的特征預測出未來7 d的流行度，屬于回歸問題，RF算法相比于傳統(tǒng)線性回歸算法更為簡潔高效.

使用隨機森林算法進行流行度預測的過程如下：

設X為R×M的矩陣,Xi j表示第i個樣本的第j個特征；Y為R×1的向量，Yi表示第i個樣本的輸出值.

Step2. 采樣完成后對數(shù)據(jù)使用完全分裂的方式建立決策樹.決策樹的訓練DecisionTreeTrain(X,Y)過程如下：

1) 如果X中的所有樣本值都相同或R<2,則跳轉(zhuǎn)Step2，否則跳轉(zhuǎn)Step3.

2) 產(chǎn)生一個葉節(jié)點，該節(jié)點的值為X中任意樣本的值.

3) 搜索分裂變量和分裂點.將空間劃分為2個節(jié)點R1,R2.假設分裂變量和分裂點分別為j和s,定義一對半平面如式(2)所示.

(2)

4) 搜索分裂變量j和分裂點s的目標函數(shù)為

(3)

其中：

(4)

5) 對分裂出的2個節(jié)點R1和R2再次調(diào)用算法

DecisionTreeTrain(R1,Y1)，

DecisionTreeTrain(R2,Y2).

Step3. 決策樹訓練完成后,輸入需要預測的數(shù)據(jù),每一棵樹會給出一個預測值pi,計算最終結(jié)果

(5)

3.3模型準確性評估

用來訓練的數(shù)據(jù)集是2015-03-04—2015-04-15之間某廣電運營商互聯(lián)網(wǎng)+電視平臺共103 721條各類節(jié)目的節(jié)目特征，130萬用戶在節(jié)目上線7 d的點播量及節(jié)目的點播排名.

在模型訓練的過程中,原有的103 721條樣本經(jīng)過清洗,去掉異常值和空值后剩余91 636條,從中隨機打亂抽取15%的樣本作為模型訓練的交叉驗證集，防止在樣本空間中出現(xiàn)過擬合的現(xiàn)象，影響預測的準確率.在多次嘗試和調(diào)整之后,發(fā)現(xiàn)將RF算法中每次抽樣的樹個數(shù)設定為100棵,通過PCA將特征降維至50維時，模型可以取得最佳的輸出結(jié)果.

通過總樣本抽取的15%的交叉驗證集(共13 746條)來驗證上述模型的準確性.采用R2值和均方誤差(mean square error， MSE)來衡量預測結(jié)果的準確性.將本文的RF模型與線性回歸模型(linear regression， LR)以及梯度提升決策樹(gradient boost decision tree， GBDT)模型進行對比.

圖6顯示了RF與上述2個模型比較的結(jié)果,無論是R2或是MSE,本文提出的RF模型在結(jié)果上都要優(yōu)于GBDT和LR兩個模型.

Fig. 6　Comparison of precision between RF, LR and GBDT.圖6　RF，LR與GBDT模型準確度比較

RF模型可以計算出特征對預測結(jié)果的影響力.在模型學習之后,每個特征都會被賦予一個影響因子.從圖7可以看出，上線時長的影響因子最大，節(jié)目越新，流行度越高；導演和演員對節(jié)目的流行度也存在較大影響；其余特征按影響力大小依次為節(jié)目類型、節(jié)目時長以及節(jié)目內(nèi)容.

Fig. 7　Weight of features in RF model.圖7　RF模型中各影響因子權(quán)重

3.4基于流行度的緩存策略

在互聯(lián)網(wǎng)+電視平臺中，用戶對某個節(jié)目的首次收視請求將被提交給中心服務器處理，隨后由緩存替換算法決定該節(jié)目是否調(diào)度到邊緣服務器緩存中，以降低后續(xù)收視對網(wǎng)絡帶寬的消耗，同時也可以縮短服務的請求響應時間.相對互聯(lián)網(wǎng)+電視整個片庫的容量，邊緣服務器的緩存容量十分有限.因此，系統(tǒng)需要從片庫中選擇最合適的節(jié)目存儲到緩存中，同時需要將用戶不感興趣的節(jié)目從緩存中刪除以釋放緩存空間.

掌握節(jié)目流行度的變化，可以有效地提升緩存命中率，對提升服務質(zhì)量有重要作用.本節(jié)利用節(jié)目流行度預測模型的輸出結(jié)果，作為節(jié)目緩存調(diào)度的依據(jù)，設計了一種緩存調(diào)度算法.

好的緩存策略應在有限的空間里盡可能多地緩存最近用戶可能收看的節(jié)目.常見的算法包括LRU算法和LFU算法.LFU算法記錄了最近一個時間窗口內(nèi)某個節(jié)目被播放的次數(shù)，時間窗口的長度作為一個可調(diào)參數(shù).每次當新節(jié)目上線后，CDN服務器會將上一個時間窗口內(nèi)訪問最少的節(jié)目丟棄.如果節(jié)目流行度是靜態(tài)，且時間窗口選擇的足夠大，LFU算法在理論上是能夠選擇出最流行的影片進行緩存的.與LFU算法類似，LRU算法保存了最近用戶收看的節(jié)目.LRU算法記錄了緩存中每個節(jié)目最近一次的訪問時間，并用最新播放的非緩存節(jié)目代替長時間無人訪問的節(jié)目.

互聯(lián)網(wǎng)+電視平臺的節(jié)目流行度是高度動態(tài)變化的，這點在新聞類節(jié)目流行度的變化上尤其明顯.LRU算法和LFU算法無法預測新上線的節(jié)目流行度，也無法適應節(jié)目流行度的劇烈變化.根據(jù)之前的觀測數(shù)據(jù)，部分節(jié)目的流行度在上線后迅速爬升，無法被LFU算法捕捉到.因此，互聯(lián)網(wǎng)+電視的緩存策略一方面要能偵測到流行度相對穩(wěn)定的老節(jié)目，另一方面也要在歷史收視數(shù)據(jù)很少的情況下捕捉到用戶感興趣的新節(jié)目.為實現(xiàn)上述目標，采用了節(jié)目流行度預測數(shù)據(jù)，作為緩存調(diào)度的依據(jù).

算法1. 基于流行度的緩存替換算法.

輸入：置換窗口大小W、緩存節(jié)目集CT、節(jié)目集S、置換節(jié)目集RT；

輸出：置出節(jié)目集OT、置入節(jié)目集IT.

初始化：根據(jù)流行度將CT中的節(jié)目進行升序排序.

① forpinsorted(CT)

② if ((size ofRT)

③RT=RT+p;

④ else:

⑤ break;

⑥ end if

⑦ end for

⑧ fortin (S-CT)

⑨ forqinRT

⑩ if (Pt>Pq)

基于流行度預測的緩存算法1所示，該算法設置大小為W的緩存窗口，緩存窗口內(nèi)的節(jié)目是緩存中流行度排名靠后的W個節(jié)目.在緩存置換時，僅將主存內(nèi)的節(jié)目與緩存窗口內(nèi)的節(jié)目進行流行度的比較，將比置換窗口中節(jié)目流行度高的節(jié)目調(diào)入緩存，并將相應的低流行度節(jié)目調(diào)出緩存，這樣可以有效地減少比較次數(shù)，提高緩存替換算法的響應速率.

4性能評估

采用某廣電運營商互聯(lián)網(wǎng)+電視平臺的用戶行為記錄作為性能評估的原始數(shù)據(jù).以天為單位計算節(jié)目收視次數(shù)和調(diào)度緩存內(nèi)容的時間間隔，比較LRU，LFU，PPRA三種緩存調(diào)度策略命中率隨緩存數(shù)目的變化.其中，命中率是指節(jié)目請求的命中率，命中率的計算周期為7 d，實驗結(jié)果如圖8所示.從圖8可以看出，緩存算法的命中率與緩存大小之間正相關，而且，當緩存較小時緩存的增大對于命中率的提高幅度較大，但隨著命中率的提高，緩存大小對于命中率的提升效果減弱.從2.1節(jié)的數(shù)據(jù)集介紹中可以得出,每天的平均電視節(jié)目請求數(shù)為19 098，為了比較不同緩存策略的差異，取日均節(jié)目請求數(shù)的5%(955個)作為觀測點.從圖8可以看出，當緩存總請求量5%的電視節(jié)目時，LRU算法的緩存命中率為57%，LFU算法的緩存命中率為59%，PPRA的緩存命中率為79%,而且，在緩存節(jié)目大小相同時，PPRA算法的緩存命中率明顯優(yōu)于LRU算法和LFU算法的緩存命中率；同時，為了達到一定的緩存命中率，PPRA策略所需的緩存空間要遠小于LFU算法和LRU算法，例如要達到80%的緩存命中率，LRU和LFU需要緩存2 987個節(jié)目，而PPRA算法僅需緩存1 021個，從而可以有效地節(jié)省緩存空間、降低系統(tǒng)建設成本.

Fig. 8　Cache hit ratio vs cache size for three algorithms.圖8　不同算法緩存命中率和緩存容量的對比

同時，選取日均節(jié)目的5%作為緩存的容量，使用120 d的用戶收視數(shù)據(jù)檢驗PPRA緩存算法緩存命中率,并將PPRA算法的緩存命中率與LRU算法和LFU算法的緩存命中率進行比較.

基于17周的觀測數(shù)據(jù)，我們對PPRA算法、LRU算法和LFU算法的緩存命中率進行了對比，發(fā)現(xiàn)3種算法的緩存命中率均隨時間發(fā)生一定的波動.圖9展現(xiàn)了17周中3種算法緩存命中率最高一周的波動情況.在整個17周中，PPRA算法最大緩存命中率是隨時間發(fā)生周期變化的，且大部分時間高于LRU算法和LFU算法，在系統(tǒng)負載最大時達到最高值，在黃金時間(每天20:00—21:00)命中率超過80%；而LRU算法和LFU算法的緩存命中率穩(wěn)定在50%～60%.實驗結(jié)果表明，PPRA算法能夠有效地提高最大緩存命中率.

Fig. 9　Comparison of max cache hit ratio.圖9　最大緩存命中率的比較

圖10展現(xiàn)了17周中3種算法緩存命中率取得中間值時一周的波動情況.在整個17周中，PPRA算法緩存命中率是隨時間發(fā)生周期變化的，且大部分時間高于LRU算法和LFU算法，在系統(tǒng)負載最大時達到最高值，在黃金時間(每天20:00—21:00)命中率超過70%；而LRU算法和LFU算法的緩存命中率穩(wěn)定在45%～55%.實驗結(jié)果表明，PPRA算法相比LRU算法和LFU算法，對緩存命中率中值有很好的提升.

Fig. 10　Comparison of median cache hit ratio.圖10　緩存命中率中值的比較

圖11展現(xiàn)了17周中3種算法緩存命中率最低一周的波動情況.在整個17周中，PPRA算法最大緩存命中率是隨時間發(fā)生周期變化的，在系統(tǒng)負載最大時達到最高值，在黃金時間(每天20:00—21:00)命中率超過80%，遠高于同期的LRU算法和LFU算法最小緩存命中率；而LRU算法和LFU算法的緩存命中率穩(wěn)定在40%～50%.實驗結(jié)果表明，PPRA算法的最大緩存命中率優(yōu)于LRU算法和LFU算法.

Fig. 11　Comparison of min cache hit ratio.圖11　最小緩存命中率的比較

綜上所述，可以得出以下結(jié)論：

1) PPRA算法采用日均節(jié)目的5%作為緩存空間,可以達到平均70%的緩存命中率.

2) PPRA算法消耗的緩存空間明顯低于相比傳統(tǒng)算法(LRU,LFU)，達到80%緩存命中率時只消耗相當于傳統(tǒng)算法30%的空間.

3) 在互聯(lián)網(wǎng)+電視系統(tǒng)負載最高時，PPRA算法的命中率達到最高，較好地契合了互聯(lián)網(wǎng)+電視節(jié)目流行度隨時間的變化規(guī)律.

5結(jié)論

為了解決互聯(lián)網(wǎng)+電視平臺以提高熱點節(jié)目命中率而過渡消耗存儲空間的問題，本文首先從互聯(lián)網(wǎng)+電視平臺真實數(shù)據(jù)中揭示了與節(jié)目流行度關系緊密的若干因素，定性分析了相應的關系，并根據(jù)這些關系選取節(jié)目上線時間、類型、標簽、播放時間作為特征，基于RF算法和PCA算法，構(gòu)建了節(jié)目流行度預測模型，并提出一種基于節(jié)目流行度的緩存調(diào)度算法——PPRA.該算法在保證緩存命中率的同時能有效節(jié)省存儲空間.實驗結(jié)果表明，在相同節(jié)目緩存命中率下，PPRA算法的空間開銷最多可縮減至LRU算法的30%，降低了互聯(lián)網(wǎng)+電視平臺的建設成本.

作為后續(xù)研究工作：擬分析用戶其他行為(如使用社交網(wǎng)絡、移動終端)對節(jié)目流行度的影響，進一步挖掘用戶收視興趣，精細化該預測模型，提高預測準確度，并部署在真實的互聯(lián)網(wǎng)+電視平臺上進行驗證和應用.

參考文獻

[1]Fricker C, Robert P, Roberts J. A versatile and accurate approximation for LRU cache performance[C] //Proc of the 24th Int Teletraffic Congress. Krakow, Poland; International Teletraffic Congress, 2012: 1-8

[2]Hendrantoro G, Affandi A. Early result from adaptive combination of LRU, LFU and FIFO to improve cache server performance in telecommunication network[C] //Proc of Int Seminar on Intelligent Technology and Its Applications (ISITIA). Piscataway, NJ: IEEE, 2015: 429-432

[3]Wang Z, Sun L, Wu C, et al. Guiding Internet-scale video service deployment using microblog-based prediction[C] //Proc of IEEE INFOCOM 2012. Piscataway, NJ: IEEE, 2012: 2901-2905

[4]Vallet D, Berkovsky S, Ardon S, et al. Characterizing and predicting viral-and-popular video content[C] //Proc of the 24th ACM Int Conf on Information and Knowledge Management. New York: ACM, 2015: 1591-1600[5]Kong Qingchao, Mao Wenji. Predicting popularity of forum threads based on dynamic evolution [J]. Journal of Software, 2014, 25(12): 2767-2776 (in Chinese)(孔慶超, 毛文吉. 基于動態(tài)演化的討論帖流行度預測. 軟件學報, 2014, 25(12): 2767-2776)

[6]Ding W, Shang Y, Guo L, et al. Video popularity prediction by sentiment propagation via implicit network[C] //Proc of the 24th ACM Int Conf on Information and Knowledge Management. New York: ACM, 2015: 1621-1630

[7]Figueiredo F. On the prediction of popularity of trends and hits for user generated videos[C] //Proc of the 6th ACM Int Conf on Web Search and Data Mining. New York: ACM, 2013: 741-746

[8]Pinto H, Almeida J M, Gon?alves M A. Using early view patterns to predict the popularity of YouTube videos[C] //Proc of the 6th ACM Int Conf on Web Search and Data Mining. New York: ACM, 2013: 365-374

[9]Ahmed M, Spagna S, Huici F, et al. A peek into the future: Predicting the evolution of popularity in user generated content[C] //Proc of the 6th ACM Int Conf on Web Search and Data Mining. New York: ACM, 2013: 607-616

[10]Roy S D, Mei T, Zeng W, et al. Towards cross-domain learning for social video popularity prediction [J]. IEEE Trans on Multimedia,2013, 15(6): 1255-1267

[11]Yu H, Xie L, Sanner S. Twitter-driven YouTube views: Beyond individual influencers[C] //Proc of the ACM Int Conf on Multimedia. New York: ACM, 2014: 869-872

[12]Chang B, Zhu H, Ge Y, et al. Predicting the popularity of online serials with autoregressive models[C] //Proc of the 23rd ACM Int Conf on Information and Knowledge Management. New York: ACM, 2014: 1339-1348

[13]McParlane P J, Moshfeghi Y, Jose J M. Nobody comes here anymore, it’s too crowded; predicting image popularity on Flickr[C] //Proc of Int Conf on Multimedia Retrieval. New York: ACM, 2014: 385-397

[14]Abrahamsson H, Nordmark M. Program popularity and viewer behaviour in a large TV-on-demand system[C] //Proc of the 2012 ACM Conf on Internet Measurement. New York: ACM, 2012: 199-210

[15]Balachandran A, Sekar V, Akella A, et al. Analyzing the potential benefits of CDN augmentation strategies for Internet video workloads[C] //Proc of the 2013 ACM Conf on Internet Measurement. New York: ACM, 2013: 43-56

[16]Zhou Y, Chen L, Yang C, et al. Video popularity dynamics and its implication for replication [J]. IEEE Trans on Multimedia, 2015, 17(8): 1273-1285

[17]Gouta A, Hong D K, Kermarrec A M, et al. HTTP adaptive streaming in mobile networks: Characteristics and caching opportunities[C] //Proc of the 21st IEEE Int Symp on Modeling, Analysis & Simulation of Computer and Telecommunication Systems (MASCOTS). Piscataway, NJ: IEEE, 2013: 90-100

[18]Abrahamsson H, Bjorkman M. Caching for IPTV distribution with time-shift[C] //Proc of 2013 Int Conf on Computing, Networking and Communications (ICNC). Piscataway, NJ: IEEE, 2013: 916-921

[19]Nencioni G, Sastry N, Chandaria J, et al. Understanding and decreasing the network footprint of catch-up TV[C] //Proc of the 22nd Int Conf on World Wide Web. New York: ACM, 2013: 965-976

[20]Agrawal K M, Venkatesh T, Medhi D. A dynamic popularity-based partial caching scheme for video on demand service in IPTV networks[C] //Proc of the 6th Int Conf on Communication Systems and Networks (COMSNETS). Piscataway, NJ: IEEE, 2014: 1-8

[21]Akhtar S, Beck A, Rimac I. HiFi: A hierarchical filtering algorithm for caching of online video[C] //Proc of the 23rd Annual ACM Conf on Multimedia. New York: ACM, 2015: 421-430

[22]Park J G, Choi H, Lee B C. Content caching with bi-level control for efficient IPTV content steaming service[C] //Proc of 2014 Int Conf on Information Networking (ICOIN). Piscataway, NJ: IEEE, 2014: 439-443

[23]Wang Yonggong, Li Zhenyu, Wu Qinghua, et al. Performance analysis and optimization for in-network caching replacement in information centric networking [J]. Journal of Computer Research and Development, 2015, 52(9): 2046-2055 (in Chinese)(王永功, 李振宇, 武慶華, 等. 信息中心網(wǎng)絡內(nèi)緩存替換算法性能分析與優(yōu)化[J]. 計算機研究與發(fā)展, 2015, 52(9): 2046-2055)

[24]Biau G. Analysis of a random forests model [J]. Journal of Machine Learning Research, 2012, 13(1): 1063-1095

[25]Candès E J, Li X, Ma Y, et al. Robust principal component analysis?[J]. Journal of the ACM, 2011, 58(3): 1-37

Zhu Chengang, born in 1982. PhD candidate. Member of China Computer Federation. His research interests include networking measurement and behavior analysis, future networks.

Cheng Guang, born in 1973. PhD, professor, PhD supervisor. Senior member of China Computer Federation. His main research interests include networking measurement and behavior analysis, future networks.

Hu Yifei, born in 1990. Master candidate. His main research interests include networking measurement and behavior analysis, future networks.

Wang Yuxiang, born in 1990. Master candidate. His main research interests include networking measurement and behavior analysis, future networks.

A Caching Strategy for Internet Plus TV Based on Popularity Prediction

Zhu Chengang, Cheng Guang, Hu Yifei, and Wang Yuxiang

(SchoolofComputerScienceandEngineering,SoutheastUniversity,Nanjing211189) (KeyLaboratoryofComputerNetworkandInformationIntegration(SoutheastUniversity),MinistryofEducation,Nanjing211189)

AbstractInternet plus TV tends to excessively consume storage space to achieve higher cache hit ratio. A novel cache schedule algorithm called PPRA(popularity prediction replication algorithm) is proposed in this paper based on programs popularity forecast. Firstly, according to statistical analysis from actual measurement, we apply random forests (RF) algorithm to construct a forecasting model of programs popularity. Subsequently, we use the principal component analysis (PCA) to overcome dimensionality curse and accelerate the forecasting process. Finally, we validate PPRA with authentic behavior data of a certain cable operator’s 1.3 million users in a period of 120 days. Our experimental results show that PPRA only consumes 30% storage space to achieve a fixed cache hit ratio compared with LRU and LFU algorithms, therefore the cost of Internet plus TV platform is saved.

Key wordsInternet plus TV; popularity prediction; random forests (RF); caching strategy; dimensionality curse

收稿日期：2015-12-21；修回日期：2016-02-16

基金項目：國家“八六三”高技術(shù)研究發(fā)展計劃基金項目(2015AA015603);江蘇省未來網(wǎng)絡創(chuàng)新研究院未來網(wǎng)絡前瞻性研究項目(BY2013095-5-03);江蘇省“六大人才高峰”高層次人才項目(2011-DZ024)

通信作者：程光(gcheng@njnet.edu.cn)

中圖法分類號TP393

This work was supported by the National High Technology Research and Development Program of China (863 Program) (2015AA015603), the Prospective Research Program on Future Networks of Jiangsu (BY2013095-5-03), and the Six Industries Talent Peaks Plan of Jiangsu (2011-DZ024).