用戶興趣感知的內容副本優化放置算法

陽小龍，王欣欣，張敏，隆克平，黃瓊

(1. 北京科技大學 計算機與通信工程學院，北京100083；2. 重慶郵電大學 移動通信技術重點實驗室，重慶400065)

1 引言

內容分發網絡(CDN， content delivery network)針對用戶對大量相同信息訪問頻繁的現象，通過在網絡邊緣設置副本服務器放置用戶頻繁訪問內容的副本，以此分擔中心源服務器的流量壓力，減輕大規模用戶同時訪問產生的瓶頸效應，同時提高用戶訪問體驗的質量。副本放置策略通過將內容的多個副本合理分配在不同邊緣服務器上，為內容分發網絡的大規模運行提供了強有力的支持。特別是隨著分發服務覆蓋區域的增加以及用戶群體規模的擴大，副本放置算法成為內容有效分發和網絡高效運行的關鍵。但副本放置需解決 2個問題：一是CDN網絡中應放置哪些內容副本，二是如何為這些副本選擇合適的放置位置。通過將內容副本合理地分布在網絡中，副本放置算法降低了通信開銷和響應延遲，從而提高了網絡分發性能并保證運營商利益得到滿足。

現有的副本放置主要采用貪婪算法、隨機算法或其他改進啟發式算法，以響應延遲[1]、負載均衡[2，3]、通信代價和存儲開銷[4～6]等為優化指標，在存儲容量或最少副本等約束條件下，確定副本放置方案。貪婪算法初始將所有內容集中在源服務器上，此時系統代價最大。在非線性模型約束下，采用貪婪的方式逐一在各副本服務器上放置副本，使代價減小量最大。因隨機等其他放置算法在某些約束條件下難以體現用戶的內容需求，比較而言，貪婪算法效果較好，故本文在貪婪算法的基礎上進行改進?，F有算法通常只關注網絡運營商利益，通過優化系統的平均性能指標來保證網絡正常運轉，但沒有從用戶需求出發進行副本放置，提供個性化的網絡服務。為滿足不同用戶請求的QoS（如響應時間），文獻[7]提出QoS感知的副本放置算法，其主要目標在于通過最小化成本開銷提升用戶的服務體驗質量。該算法根據用戶請求所需QoS不同而區別對待，保證滿足所有用戶的QoS需求，實現從用戶需求出發來提高網絡可靠性。針對用戶對不同服務QoS（即可靠性、時間性和安全性）需求的差異性，文獻[8]從QoS敏感的用戶需求出發，提出基于層次分析法的QoS偏好感知副本選擇策略，為QoS敏感用戶按需提供數據服務，進一步提高了網絡資源可用性。為解決CDN數據傳輸開銷過大的問題，文獻[9]從代理服務器反饋的用戶動態需求信息出發，建立基于內容流行度的認知預測模型，并依據此模型啟發式地完成內容的分發和放置。該方法在降低內容分發網絡傳輸開銷的同時，滿足了用戶的動態需求。

文獻[7～9]雖從用戶需求出發進行副本放置，在一定程度上提高了用戶需求滿意度。但因副本服務器容量和主干網帶寬限制，不可能將用戶需求的所有副本都放置在副本服務器。所以，只有充分了解用戶對內容的興趣，才能有針對性地將滿足用戶興趣及特定需求的副本放置到網絡中，滿足用戶對內容的個性化需求，同時提高網絡存儲空間的利用率。獲取用戶興趣是個性化服務的關鍵環節，因此，本文從 CDN個性化服務角度出發，提出一種用戶興趣感知的內容副本優化放置算法(UIARP， user interest-aware content replica optimized placement algorithm)，采用聚類算法[10]獲得各用戶的群體內容興趣主題，然后在非線性優化模型下，優先放置群體興趣度[11]較大的副本，以實現被放置副本與用戶內容需求的最大匹配。該算法不僅可提高CDN網絡的服務能力和分發效率，而且可滿足用戶對內容的個性化需求，實現用戶和網絡運營商的互利共贏。

2 副本優化放置算法

本算法從副本服務器日志中提取被訪內容的信息特征，運用聚類算法獲得該副本服務器所轄用戶的內容興趣主題，并計算其群體興趣度（即副本服務器所轄用戶對不同內容主題的感興趣程度）；在非線性優化模型下，優先放置各副本服務器下群體興趣度較大的副本，以此實現被放置副本關鍵詞與內容主題相匹配的優化，滿足用戶對內容的個性化需求。

2.1 用戶訪問特征獲取

為最小化 CDN中用戶的平均響應時間，提高用戶滿意度，本算法從用戶個性化內容需求出發放置副本。為獲得用戶的內容興趣主題，首先需提取被訪副本的特征，以此獲得用戶訪問特征；然后對其進行聚類，以此獲得用戶感興趣的內容主題。因本算法放置對象為 CDN中廣泛分發的視頻內容副本，故提取的副本特征包括副本關鍵詞（即視頻類型如動作、喜劇等）、被訪次數和被訪時長。本文采用空間向量模型(VSM， vector space model)[12]表示用戶訪問特征，其基本思想是將單個用戶訪問特征用N維向量表示，其每一維由關鍵詞及其權重組成，如式(1)所示

其中，(k1…ki…kN) (1≤i≤N)為VSM空間向量模型坐標系，ki表示動作、喜劇、愛情、動畫、戰爭和教育等副本關鍵詞；(w1…wi…wN)則為相應坐標值，其中，wi為關鍵詞ki的權重。其權重wi計算[13]如下

其中，0 ＜α＜ 0 .1，f(ki)表示某用戶訪問副本ki的頻次，ni表示此副本服務器下所有用戶訪問ki的頻次，nall表示此用戶所在服務器下被訪副本的總頻次。取對數是為防止nall/ni占主導作用，α是為避免當nall=ni時對數為0。因此，網絡中每個用戶的訪問特征便可映射到VSM向量空間，從而將用戶訪問特征的獲得轉化為VSM空間向量的運算。

VSM模型將用戶訪問特征轉化為空間向量，該向量僅能體現單個用戶對哪些副本感興趣，但不能體現用戶間的興趣差異。因此，本文通過日志中的相關信息跟蹤各用戶行為，以區分用戶間的興趣差異。文獻[14，15]指出用戶的瀏覽、上傳或下載等行為可通過用戶對內容的訪問次數和訪問時長來表示，故用戶的平均訪問時長可反映用戶間的興趣差異；平均訪問時長越長，則個體興趣度越大。因此，可用式(13)計算用戶j對副本ki的興趣度IRji。

其中，Tji表示用戶j訪問副本ki的時長，Vji表示此用戶訪問ki的次數。因此，各用戶對不同內容的興趣度(IRji)即可體現不同用戶的興趣差異。因個體興趣度隨時間變化，為準確表示用戶個體興趣度，利用滑動平均法以相鄰時段的滑動平均值來表示其當前值。故時段t（以周為單位）IRji的計算如下

其中，α表示當前t時段用戶個體興趣度的權重系數；IRji(t)為t時段用戶j對ki的個體興趣度，IRji(t-1)為其在相鄰(t-1)時段的個體興趣度；由式(4)可得個體興趣度IRji的滑動平均值，它是獲取群體用戶對不同主題感興趣程度的基礎。

2.2 群體興趣度表示

為進一步獲得群體的內容興趣主題及其興趣度，可對副本服務器所轄用戶的訪問特征向量聚類。因單個用戶訪問特征用VSM中的向量表示，故副本服務器所轄群體的訪問特征用矩陣表示。其中矩陣行數為副本服務器所轄用戶的數目，列數則為副本類型的數目。將矩陣中所有行向量作為聚類對象，根據用戶對所訪副本的興趣偏好是否相似，采用改進K-Means算法[16]對其向量進行聚類，可得到K類興趣主題(即S1…Si…SK)。通過聚類得到群體的興趣主題之后，需引入群體興趣度來區分不同主題的受歡迎程度。一般地，主題的群體興趣度越大，表明此主題越受歡迎，故對其降序排列可獲得群體偏好進而實現用戶興趣感知的副本放置。群體興趣度的獲取，需考慮主題內所有用戶對此主題的個體興趣度，并以用戶訪問特征向量與主題向量的相似度作為加權因子。因而，主題Si的群體興趣度計算如下

其中，collective_IRi(1≤i≤K)為主題Si的群體興趣度；Li表示Si主題內所含用戶數，IRji表示用戶j對主題Si的興趣度；Sim(uj，uci)為Si內用戶j的訪問特征向量uj和主題向量uci的相似度[17]，可通過VSM空間的向量夾角余弦得到，其計算如下。

通過式(5)獲得每類主題的群體興趣度之后，對其降序排列即可確定群體對不同主題的偏好程度，故將其排序作為副本服務器放置副本的標準。因群體興趣度隨時間變化，故利用滑動平均法以相鄰時段群體興趣度的滑動平均值來表示其當前值。t時段collective_IRi計算如下

其中，α為t時段群體興趣度的權重系數；collective_IRi(t)為t時段主題Si的群體興趣度，而collective_IRi(t-1)則為其(t-1)時段的群體興趣度；由式(7)可得群體興趣度的平均值，便于準確獲取群體偏好放置相應副本。

本文將時間分段看作一個個時間窗口，上述部分只是在一個窗口中提取了用戶興趣主題并計算其主題興趣度。從一個窗口到下一個窗口的過程中，根據用戶訪問內容的變化，用戶感興趣內容主題相應發生變化，由于個體用戶對內容訪問興趣的變化與大腦記憶的遺忘規律類似，于是本文用戶興趣更新中的衰減規律符合艾賓浩斯遺忘曲線的變化。通過對個體用戶的訪問內容進行增強或減弱，達到群體用戶興趣更新的目的。以上解決了副本放置的第一個問題，即 CDN中應放置哪些副本，然后在非線性優化模型下為被放置副本選擇合適的放置位置。

2.3 副本優化放置

鑒于傳統貪婪放置算法難以滿足用戶的個性化內容需求，為提高用戶滿意度，本文從用戶的興趣偏好出發，在貪婪算法的基礎上對放置方案進行改進。在非線性優化模型下，依據群體興趣度的降序排列，優先放置群體興趣度較大的副本，以此實現被放置副本與用戶內容需求的相匹配的優化。因貪婪放置只保證局部最優選擇而不具有全局優化效果，故在貪婪放置的基礎上進行服務器間副本的交換操作(即群體興趣度排序相似的服務器間交換副本)，以平均響應時間最小為目標確定副本的最終放置位置。故副本放置的非線性優化模型如下所示。

其中，v表示副本服務器數目，K表示興趣主題數目，ResponseTimeij和freqij分別表示副本服務器i訪問副本ki的響應時間和頻次；Tthreshold表示請求響應容忍極限，若ResponseTimeij超過Tthreshold，服務器i上用戶將不會向此副本服務器請求副本，即不在此副本服務器放置該類副本；xij表示副本服務器i是否存在副本kj，若存在則xij=1，否則xij=0；|cj|表示副本kj的大小，|Ci|表示副本服務器i的容量。其中，目標函數式(8)要求平均響應時間最小，約束條件式(9)、式(10)則分別表示請求響應容忍極限及副本服務器存儲容量限制。因此，UIARP算法流程如下所示。

算法1UIARP算法流程

輸入：各副本服務器日志logs和被放置副本(數目為r)

輸出：被放置副本的位置矩陣L[v][r]

fori=1 tov

提取logs中用戶訪問特征并聚類，計算各主題的群體興趣度及其降序Rank_IR(i)；

end for；

forj=1 toK//K為興趣主題數

依據各服務器的Rank_IR(i)，得到各服務器對主題Si偏好的降序排列Sort(Sj)；

依據Sort(Sj)放置副本；

3 仿真結果分析

3.1 仿真環境

本文仿真主要采用Matlab仿真軟件，利用隨機過程模擬用戶訪問行為，來實現 CDN網絡的內容副本放置。內容分發網絡拓撲G=(V，E)隨機生成，其中節點集合V由源服務器和副本服務器組成。為簡化仿真環境僅設網絡架構為2級：第一級為源服務器，第二級為副本服務器(v=5)及其所轄用戶(m=15)，且副本服務器節點之間全連接；假設CDN中存在6種副本類型(N=6)。假設用戶對內容的請求到達服從泊松(Poisson)分布，用戶對內容的訪問服從Zipf分布；因本算法針對中小規模CDN網絡進行副本放置，故副本服務器容量和副本大小分別在GB和MB數量級內隨機產生。為帶給用戶更好的訪問體驗，副本服務器拒絕超過響應容忍極限的用戶請求。仿真參數設置如表1所示。

表1 仿真參數設置

根據互聯網用戶對所請求內容的等待時間進行大量統計分析，本文將響應容忍極限設為500 ms[18]。為驗證用戶滿意度的提高，選取平均響應時間和請求響應匹配度作為仿真指標；為證明網絡性能的提升，選擇負載均衡和鄰近副本利用率作為仿真指標；故從以上4方面來分析UIARP算法的可行性及有效性，并以Greedy和1-Greedy-Insert[7]算法作對比。

3.2 性能仿真分析

1) 平均響應時間

平均響應時間反映了 CDN中各副本服務器所轄用戶的平均訪問效率，故利用式(11)來計算平均響應時間。從圖1可看出，不同副本放置算法下的平均響應時間隨副本個數的增加都逐漸減少。當副本個數較少(1～3)時，UIARP的平均響應時間與l-Greedy-Insert相比沒有明顯降低，但比Greedy的平均響應時間要短；隨著副本個數的增加，UIARP與l-Greedy-Insert相比，平均響應時間降低幅度約為44%，與Greedy相比，平均降低約60%；由此得出，本算法在降低平均響應時間方面具有一定優勢。因副本服務器存儲容量限制，平均響應時間在副本服務器所放副本接近其容量之后，下降趨勢逐漸趨于平穩。

圖1 平均響應時間隨副本個數的變化

2) 請求響應匹配度

請求響應匹配度是指副本服務器所轄用戶請求的副本正好被放置到此副本服務器的個數占整個網絡請求副本總數的比率。由圖2可看出，不同副本放置算法下的請求響應匹配度都隨副本個數的增加呈上升趨勢。本算法與l-Greedy-Insert算法相比，請求響應匹配度平均約提高72.4%，與Greedy相比，提高幅度近 100%。因本算法針對用戶興趣偏好進行副本放置，故與其他算法相比，大大提高了請求響應匹配度。因副本服務器存儲容量及請求響應容忍極限的約束，請求響應匹配度上升趨勢最終趨于穩定。

圖2 請求響應匹配度隨副本個數的變化

3) 負載均衡

由圖3可得不同算法下各副本服務器的負載情況，當采用Greedy和l-Greedy-Insert時，節點的最高負載量和最低負載量之比均為 7.0，相差幅度較大，而在UIARP中其比值降低到1.3，服務器之間負載差距較小。這是因為 UIARP考慮了副本服務器所轄用戶的興趣主題分布，能夠依據用戶興趣偏好來均勻放置副本，故副本服務器負載比較均衡；而對比算法分別以最小傳輸開銷和最大歸一化利益(即單位傳輸代價滿足用戶請求數最多)為優化目標進行副本放置，故副本服務器間副本分布極不均勻，負載均衡性較差。

圖3 負載均衡性對比

4) 鄰近副本利用率

假設 CDN中用戶請求的總數不變，鄰近副本利用率表示隨副本個數的增加，用戶在鄰近副本服務器被滿足的請求數占請求總數的比率。鄰近副本服務器是間接為用戶提供副本服務的其他副本服務器。一般認為，從本地服務器請求副本的帶寬遠大于服務器之間的帶寬。所以，如果鄰近副本利用率較小表明副本放置算法能充分利用本地副本資源，節省網絡帶寬。從圖4可看出，隨著副本個數的增加，鄰近副本利用率逐漸降低，表示本地副本可用性越來越高；UIARP與 Greedy和 1-Greedy-Insert相比，鄰近副本利用率平均降低約 29.1%～37.5%。表明該算法能有效提高用戶訪問效率，降低網絡運行負載。因副本服務器容量及響應容忍極限的限制，鄰近副本利用率降低趨勢逐漸趨于穩定。

圖4 鄰近副本利用率隨副本個數的變化

5) 算法復雜度

4 結束語

為滿足用戶對內容的個性化需求，本文提出用戶興趣感知的內容副本優化放置算法。通過對用戶訪問特征聚類，獲得群體的內容興趣主題，然后依據其群體興趣度降序排列放置副本，以此實現被放置副本與用戶內容需求相匹配的優化。仿真結果表明該算法可降低平均響應時間，提高請求響應匹配度，均衡網絡負載和內容副本可用性。與現有副本放置算法相比，該算法在提高內容分發網絡服務能力和分發效率的同時，大大提升了用戶對內容的需求滿意度。因運營商利益和用戶滿意度之間沒有統一的衡量標準，故無法對兩者進行博弈進而選取最優折中。

[1] WANG W F， WEI W H. A dynamic replica placement mechanism based on response time measure[A]. 2010 International Conference on Communications and Mobile Computing (CMC)[C]. Shenzhen， China，2010.169-173.

[2] AYYASAMY S， SIVANANDAM S N. A cluster based replication architecture for load balancing in peer-to-peer content distribution[J].International Journal of Computer Networks & Communications(IJCNC)， 2010， 2(5)： 158-172.

[3] GABER S M A， SUMARI P. Predictive and content-aware load balancing algorithm for peer-service area based IPTV networks[J]. Multimedia Tools and Applications， 2012.1-24.

[4] SUN J， GAO S X， YANG W G，et al. Heuristic replica placement algorithms in content distribution networks[J]. Journal of Networks，2011， 6(3)：416-423.

[5] LI T Y， WANG J L， WANG L F. Replica placement algorithm in distributed media service system[J]. Computer Engineering， 2010， 36(2)：9-12.

[6] 衛星， 楊堅， 奚宏生. 同構流媒體集群系統優化內容部署[J]. 電子與信息學報， 2009， 31(9)：2232-2236.WEI X， YANG J， XI H S. Optimal content distribution on clustered streaming media system consisting of homogeneous configuration[J].Journal of Electronics & Information Technology， 2009， 31(9)：2232-2236.

[7] TANG X Y， XU J L. QoS-aware replica placement for content distribution[J]. IEEE Transactions on Parallel and Distributed Systems，2005， 16(10)： 921-932.

[8] XIONG R Q， LUO J Z， SONG A B，et al. QoS preference-aware replica selection strategy in cloud computing[J]. Journal on Communications， 2011， 32(7)： 93-102.

[9] 韓國棟， 朱一戈， 張帆. 一種基于認知的動態副本放置方法[J]. 計算機應用與軟件， 2013， 30(1)： 83-87.HAN G D， ZHU Y G， ZHANG F. A dynamic replica placement approach based on cognition[J]. Computer Applications and Software，2013， 30(1)： 83-87.

[10] 周濤， 陸惠玲. 數據挖掘中聚類算法研究進展[J]. 計算機工程與應用， 2012， 48(12)： 100-111.ZHOU T， LU H L. Clustering algorithm research advances on data mining[J]. Computer Engineering and Applications， 2012， 48(12)：100-111.

[11] YAN D M， LU C H. Optimized collaborative filtering recommendation based on users' interest degree and feature[J]. Application Research of Computers， 2012， 29(2)：497-500.

[12] 李連，朱愛紅，蘇濤. 一種改進的基于向量空間文本相似度算法的研究與實現[J].計算機應用與軟件， 2012， 29(2)： 282-284.LI L， ZHU A H， SU T. Research and implementation of an improved VSM-based text similarity algorithm[J]. Computer Application and Software， 2012， 29(2)： 282-284.

[13] WANG N， WANG P Y， ZHANG B W. An improved TF-IDF weights function based on information theory[A]. 2010 International Conference on Computer and Communication Technologies in Agriculture Engineering (CCTAE)[C]. Chengdu， China， 2010.439-441

[14] ZHANG Z Y， LIU P Y， ZHU Z F，et al. Improved visit statistical method and calculation in user's interest degree[J]. Computer Engineering and Design， 2011， 32(002)： 424-426.

[15] 王微微，夏秀峰，李曉明.一種基于用戶行為的興趣度模型[J]. 計算機工程與應用， 2012， 48(8)： 128-152.WANG W W， XIA X F， LI X M. Personal interest degree model based on consumer behavior[J].Computer Engineering and Applications，2012， 48(8)：128-152.

[16] YEDLA M， PATHAKOTA S R， SRINIVASA T M. EnhancingK-means clustering algorithm with improved initial center[J]. International Journal of Computer Science and Information Technologies，2010， 1(2)： 121-125.

[17] 徐風苓，孟祥武，王立才. 基于移動用戶上下文相似度的協同過濾推薦算法[J]. 電子與信息學報，2011， 33(11)： 2785-2789.XU F L， MENG X W， WANG L C. A collaborative filtering recommendation algorithm based on context similarity for mobile users[J].Journal of Electronics & Information Technology， 2011， 33(11)：2785-2789.

[18] CHEN Y， KATZ R H， KUBIATOWICZ J D. Dynamic Replica Placement for Scalable Content Delivery[M]. Springer Berlin Heidelberg，2002.306-318.