用戶興趣感知的內(nèi)容副本優(yōu)化放置算法

陽(yáng)小龍，王欣欣，張敏，隆克平，黃瓊

(1. 北京科技大學(xué) 計(jì)算機(jī)與通信工程學(xué)院，北京100083；2. 重慶郵電大學(xué) 移動(dòng)通信技術(shù)重點(diǎn)實(shí)驗(yàn)室，重慶400065)

1 引言

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

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

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

2 副本優(yōu)化放置算法

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

2.1 用戶訪問(wèn)特征獲取

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

其中，(k1…ki…kN) (1≤i≤N)為VSM空間向量模型坐標(biāo)系，ki表示動(dòng)作、喜劇、愛(ài)情、動(dòng)畫(huà)、戰(zhàn)爭(zhēng)和教育等副本關(guān)鍵詞；(w1…wi…wN)則為相應(yīng)坐標(biāo)值，其中，wi為關(guān)鍵詞ki的權(quán)重。其權(quán)重wi計(jì)算[13]如下

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

VSM模型將用戶訪問(wèn)特征轉(zhuǎn)化為空間向量，該向量?jī)H能體現(xiàn)單個(gè)用戶對(duì)哪些副本感興趣，但不能體現(xiàn)用戶間的興趣差異。因此，本文通過(guò)日志中的相關(guān)信息跟蹤各用戶行為，以區(qū)分用戶間的興趣差異。文獻(xiàn)[14，15]指出用戶的瀏覽、上傳或下載等行為可通過(guò)用戶對(duì)內(nèi)容的訪問(wèn)次數(shù)和訪問(wèn)時(shí)長(zhǎng)來(lái)表示，故用戶的平均訪問(wèn)時(shí)長(zhǎng)可反映用戶間的興趣差異；平均訪問(wèn)時(shí)長(zhǎng)越長(zhǎng)，則個(gè)體興趣度越大。因此，可用式(13)計(jì)算用戶j對(duì)副本ki的興趣度IRji。

其中，Tji表示用戶j訪問(wèn)副本ki的時(shí)長(zhǎng)，Vji表示此用戶訪問(wèn)ki的次數(shù)。因此，各用戶對(duì)不同內(nèi)容的興趣度(IRji)即可體現(xiàn)不同用戶的興趣差異。因個(gè)體興趣度隨時(shí)間變化，為準(zhǔn)確表示用戶個(gè)體興趣度，利用滑動(dòng)平均法以相鄰時(shí)段的滑動(dòng)平均值來(lái)表示其當(dāng)前值。故時(shí)段t（以周為單位）IRji的計(jì)算如下

其中，α表示當(dāng)前t時(shí)段用戶個(gè)體興趣度的權(quán)重系數(shù)；IRji(t)為t時(shí)段用戶j對(duì)ki的個(gè)體興趣度，IRji(t-1)為其在相鄰(t-1)時(shí)段的個(gè)體興趣度；由式(4)可得個(gè)體興趣度IRji的滑動(dòng)平均值，它是獲取群體用戶對(duì)不同主題感興趣程度的基礎(chǔ)。

2.2 群體興趣度表示

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

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

通過(guò)式(5)獲得每類(lèi)主題的群體興趣度之后，對(duì)其降序排列即可確定群體對(duì)不同主題的偏好程度，故將其排序作為副本服務(wù)器放置副本的標(biāo)準(zhǔn)。因群體興趣度隨時(shí)間變化，故利用滑動(dòng)平均法以相鄰時(shí)段群體興趣度的滑動(dòng)平均值來(lái)表示其當(dāng)前值。t時(shí)段collective_IRi計(jì)算如下

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

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

2.3 副本優(yōu)化放置

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

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

算法1UIARP算法流程

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

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

fori=1 tov

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

end for；

forj=1 toK//K為興趣主題數(shù)

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

依據(jù)Sort(Sj)放置副本；

3 仿真結(jié)果分析

3.1 仿真環(huán)境

本文仿真主要采用Matlab仿真軟件，利用隨機(jī)過(guò)程模擬用戶訪問(wèn)行為，來(lái)實(shí)現(xiàn) CDN網(wǎng)絡(luò)的內(nèi)容副本放置。內(nèi)容分發(fā)網(wǎng)絡(luò)拓?fù)銰=(V，E)隨機(jī)生成，其中節(jié)點(diǎn)集合V由源服務(wù)器和副本服務(wù)器組成。為簡(jiǎn)化仿真環(huán)境僅設(shè)網(wǎng)絡(luò)架構(gòu)為2級(jí)：第一級(jí)為源服務(wù)器，第二級(jí)為副本服務(wù)器(v=5)及其所轄用戶(m=15)，且副本服務(wù)器節(jié)點(diǎn)之間全連接；假設(shè)CDN中存在6種副本類(lèi)型(N=6)。假設(shè)用戶對(duì)內(nèi)容的請(qǐng)求到達(dá)服從泊松(Poisson)分布，用戶對(duì)內(nèi)容的訪問(wèn)服從Zipf分布；因本算法針對(duì)中小規(guī)模CDN網(wǎng)絡(luò)進(jìn)行副本放置，故副本服務(wù)器容量和副本大小分別在GB和MB數(shù)量級(jí)內(nèi)隨機(jī)產(chǎn)生。為帶給用戶更好的訪問(wèn)體驗(yàn)，副本服務(wù)器拒絕超過(guò)響應(yīng)容忍極限的用戶請(qǐng)求。仿真參數(shù)設(shè)置如表1所示。

表1 仿真參數(shù)設(shè)置

根據(jù)互聯(lián)網(wǎng)用戶對(duì)所請(qǐng)求內(nèi)容的等待時(shí)間進(jìn)行大量統(tǒng)計(jì)分析，本文將響應(yīng)容忍極限設(shè)為500 ms[18]。為驗(yàn)證用戶滿意度的提高，選取平均響應(yīng)時(shí)間和請(qǐng)求響應(yīng)匹配度作為仿真指標(biāo)；為證明網(wǎng)絡(luò)性能的提升，選擇負(fù)載均衡和鄰近副本利用率作為仿真指標(biāo)；故從以上4方面來(lái)分析UIARP算法的可行性及有效性，并以Greedy和1-Greedy-Insert[7]算法作對(duì)比。

3.2 性能仿真分析

1) 平均響應(yīng)時(shí)間

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

圖1 平均響應(yīng)時(shí)間隨副本個(gè)數(shù)的變化

2) 請(qǐng)求響應(yīng)匹配度

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

圖2 請(qǐng)求響應(yīng)匹配度隨副本個(gè)數(shù)的變化

3) 負(fù)載均衡

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

圖3 負(fù)載均衡性對(duì)比

4) 鄰近副本利用率

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

圖4 鄰近副本利用率隨副本個(gè)數(shù)的變化

5) 算法復(fù)雜度

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

為滿足用戶對(duì)內(nèi)容的個(gè)性化需求，本文提出用戶興趣感知的內(nèi)容副本優(yōu)化放置算法。通過(guò)對(duì)用戶訪問(wèn)特征聚類(lèi)，獲得群體的內(nèi)容興趣主題，然后依據(jù)其群體興趣度降序排列放置副本，以此實(shí)現(xiàn)被放置副本與用戶內(nèi)容需求相匹配的優(yōu)化。仿真結(jié)果表明該算法可降低平均響應(yīng)時(shí)間，提高請(qǐng)求響應(yīng)匹配度，均衡網(wǎng)絡(luò)負(fù)載和內(nèi)容副本可用性。與現(xiàn)有副本放置算法相比，該算法在提高內(nèi)容分發(fā)網(wǎng)絡(luò)服務(wù)能力和分發(fā)效率的同時(shí)，大大提升了用戶對(duì)內(nèi)容的需求滿意度。因運(yùn)營(yíng)商利益和用戶滿意度之間沒(méi)有統(tǒng)一的衡量標(biāo)準(zhǔn)，故無(wú)法對(duì)兩者進(jìn)行博弈進(jìn)而選取最優(yōu)折中。

[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] 衛(wèi)星， 楊堅(jiān)， 奚宏生. 同構(gòu)流媒體集群系統(tǒng)優(yōu)化內(nèi)容部署[J]. 電子與信息學(xué)報(bào)， 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] 韓國(guó)棟， 朱一戈， 張帆. 一種基于認(rèn)知的動(dòng)態(tài)副本放置方法[J]. 計(jì)算機(jī)應(yīng)用與軟件， 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] 周濤， 陸惠玲. 數(shù)據(jù)挖掘中聚類(lèi)算法研究進(jìn)展[J]. 計(jì)算機(jī)工程與應(yīng)用， 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] 李連，朱愛(ài)紅，蘇濤. 一種改進(jìn)的基于向量空間文本相似度算法的研究與實(shí)現(xiàn)[J].計(jì)算機(jī)應(yīng)用與軟件， 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]. 計(jì)算機(jī)工程與應(yīng)用， 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] 徐風(fēng)苓，孟祥武，王立才. 基于移動(dòng)用戶上下文相似度的協(xié)同過(guò)濾推薦算法[J]. 電子與信息學(xué)報(bào)，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.