包沙如拉，孫 鵬，韓 銳，郭志川

(1.中國(guó)科學(xué)院聲學(xué)研究所國(guó)家網(wǎng)絡(luò)新媒體工程技術(shù)研究中心，北京 100190; 2.中國(guó)科學(xué)院大學(xué)，北京 100049)

0 引 言

隨著互聯(lián)網(wǎng)、移動(dòng)互聯(lián)網(wǎng)、物聯(lián)網(wǎng)[1]的普及和應(yīng)用，終端設(shè)備信息的獲取量大到足以使傳輸成為瓶頸。為了減小海量數(shù)據(jù)傳輸處理帶來的壓力，結(jié)合終端設(shè)備智能化的趨勢(shì)，中科院提出了以“海計(jì)算”模式為核心的海云協(xié)同服務(wù)技術(shù)架構(gòu)。在應(yīng)用方式上，云計(jì)算和海計(jì)算具有一定的相似性，都是將硬件資源和軟件資源以服務(wù)的形式提供給用戶，并按照用戶需求進(jìn)行可靠而高效的彈性供給。與此同時(shí)，2種計(jì)算模式具有一定的差異性[2]。其中海服務(wù)[3]是將服務(wù)請(qǐng)求通過靠近請(qǐng)求端的設(shè)備進(jìn)行快速處理，適合于局部快速計(jì)算和響應(yīng)，即圍繞前端智能化的趨勢(shì)和互聯(lián)網(wǎng)服務(wù)特點(diǎn)，不同于霧計(jì)算[4]的邊緣服務(wù)設(shè)備為主的服務(wù)模式，充分利用端設(shè)備，構(gòu)建以服務(wù)請(qǐng)求為中心，可提供現(xiàn)場(chǎng)、彈性、自治的，即時(shí)響應(yīng)的網(wǎng)絡(luò)系統(tǒng)；而云計(jì)算[5-6]則是基于虛擬化技術(shù)匯聚處理資源，對(duì)服務(wù)請(qǐng)求實(shí)現(xiàn)時(shí)空弱約束的承載，2類計(jì)算模式各有側(cè)重。因此海云協(xié)同服務(wù)系統(tǒng)通過海服務(wù)增強(qiáng)云計(jì)算的現(xiàn)場(chǎng)實(shí)時(shí)處理能力，使網(wǎng)絡(luò)服務(wù)既有云計(jì)算的服務(wù)資源自動(dòng)化指派能力，又有現(xiàn)場(chǎng)即時(shí)處理響應(yīng)的功能。而近年來，視頻類業(yè)務(wù)成為主要的互聯(lián)網(wǎng)業(yè)務(wù)形式之一，大規(guī)模海量視頻數(shù)據(jù)的服務(wù)提供與傳輸處理給當(dāng)前的服務(wù)系統(tǒng)與服務(wù)網(wǎng)絡(luò)帶來了巨大挑戰(zhàn)。副本放置是CDN+P2P等系統(tǒng)中有效解決存儲(chǔ)、傳輸和保證QoS等問題的途徑之一，常用于視頻類業(yè)務(wù)應(yīng)用中解決海量數(shù)據(jù)的存儲(chǔ)、傳輸?shù)葐栴}。對(duì)于副本放置，在不同系統(tǒng)中，根據(jù)不同的限制條件和優(yōu)化目標(biāo)，研究者提出了多種副本放置算法。為解決CDN數(shù)據(jù)傳輸開銷過大的問題，文獻(xiàn)[7]從代理服務(wù)器反饋的用戶動(dòng)態(tài)需求信息出發(fā)，建立基于內(nèi)容流行度的認(rèn)知預(yù)測(cè)模型，并依據(jù)此模型啟發(fā)式地完成內(nèi)容的分發(fā)和放置。該方法在降低內(nèi)容分發(fā)網(wǎng)絡(luò)傳輸開銷的同時(shí)，滿足了用戶的動(dòng)態(tài)需求，以提高用戶服務(wù)質(zhì)量，降低網(wǎng)絡(luò)成本為目標(biāo)。文獻(xiàn)[8]提出了最遠(yuǎn)優(yōu)先放置算法，此算法最大使用了每個(gè)副本的處理能力，并且也降低了網(wǎng)絡(luò)運(yùn)行成本。P2P系統(tǒng)中現(xiàn)有復(fù)制方法大多只考慮副本數(shù)量，副本數(shù)量越多就越能提高資源訪問效率，但采用這樣的數(shù)據(jù)復(fù)制方法將會(huì)帶來高昂的副本一致性維護(hù)代價(jià)的問題。為平衡副本一致性維護(hù)的開銷和多副本帶來的訪問性能提升之間的關(guān)系，文獻(xiàn)[9]提出了動(dòng)態(tài)副本分布方法。針對(duì)云存儲(chǔ)環(huán)境，為了保證在放置應(yīng)用數(shù)據(jù)副本時(shí)，數(shù)據(jù)副本都能滿足應(yīng)用的QoS要求，需要考慮云計(jì)算環(huán)境下QoS約束的應(yīng)用數(shù)據(jù)副本放置問題，文獻(xiàn)[10]提出一種QoS感知的副本放置算法。該算法首先對(duì)QoS約束集的屬性進(jìn)行量化，然后構(gòu)建目標(biāo)優(yōu)化模型，最后在副本放置優(yōu)化算法中引入粒子群優(yōu)化來決定副本放置位置。在CDN+P2P系統(tǒng)中，為了減少副本放置總代價(jià)，即存儲(chǔ)代價(jià)和傳輸代價(jià)，文獻(xiàn)[11]提出了HCPA算法。文獻(xiàn)[12]提出了用戶興趣度感知的內(nèi)容副本優(yōu)化放置算法，以最小化平均響應(yīng)時(shí)間為目標(biāo)，優(yōu)先放置群體興趣度較大的副本，以實(shí)現(xiàn)被放置副本與用戶內(nèi)容興趣主題的最大匹配。文獻(xiàn)[13]針對(duì)CDN+P2P系統(tǒng)，提出了一種算法，最小化代理服務(wù)器的總體部署成本，并增加網(wǎng)絡(luò)QoS的保證。該算法通過對(duì)具有環(huán)拓?fù)浣Y(jié)構(gòu)的網(wǎng)絡(luò)中進(jìn)行副本放置，去獲得最大增益。

中科院基于海服務(wù)，以新媒體服務(wù)領(lǐng)域?yàn)閼?yīng)用場(chǎng)景，研發(fā)了基于海云協(xié)同架構(gòu)的網(wǎng)絡(luò)新媒體服務(wù)系統(tǒng)方案，實(shí)現(xiàn)基于用戶側(cè)海端節(jié)點(diǎn)資源聚合的媒體內(nèi)容存儲(chǔ)分發(fā)服務(wù)能力。在此系統(tǒng)中，鄰域分組的海端節(jié)點(diǎn)上預(yù)部署視頻內(nèi)容是實(shí)現(xiàn)視頻類應(yīng)用服務(wù)快速、及時(shí)響應(yīng)的關(guān)鍵，需要一個(gè)適用于該網(wǎng)絡(luò)特性的副本放置策略。而前述已有的副本放置算法都是基于CDN或者P2P系統(tǒng)應(yīng)用進(jìn)行的研究，直接應(yīng)用于海服務(wù)系統(tǒng)不能充分利用海服務(wù)的及時(shí)響應(yīng)的現(xiàn)場(chǎng)特性，因此，提出一種適用于海服務(wù)系統(tǒng)的副本放置策略算法是本文研究重點(diǎn)。

1 系統(tǒng)結(jié)構(gòu)及優(yōu)化目標(biāo)

基于海云協(xié)同架構(gòu)的網(wǎng)絡(luò)新媒體服務(wù)系統(tǒng)如圖1所示。中心管理服務(wù)器記錄海端節(jié)點(diǎn)拓?fù)湫畔?，?dāng)節(jié)點(diǎn)的狀態(tài)發(fā)生變化時(shí)(離線、退出)，中心管理服務(wù)器會(huì)進(jìn)行相應(yīng)調(diào)整，以免影響集群的整體運(yùn)行情況，并且中心管理服務(wù)器存儲(chǔ)著系統(tǒng)全部的視頻內(nèi)容。海端節(jié)點(diǎn)是具有動(dòng)態(tài)特性(即隨時(shí)可能上線、離線)的，并且存儲(chǔ)著部分視頻內(nèi)容。在線的海端節(jié)點(diǎn)為用戶提供流媒體服務(wù)，當(dāng)用戶所請(qǐng)求的內(nèi)容自己沒有存儲(chǔ)時(shí)，從其他存儲(chǔ)該內(nèi)容的海端節(jié)點(diǎn)獲取內(nèi)容到本地再進(jìn)行服務(wù)。

圖1 海云協(xié)同架構(gòu)的網(wǎng)絡(luò)新媒體服務(wù)系統(tǒng)結(jié)構(gòu)

在海云協(xié)同架構(gòu)的網(wǎng)絡(luò)新媒體服務(wù)系統(tǒng)中，為了保證海服務(wù)的現(xiàn)場(chǎng)特性，提高用戶的QoS，需要在海端節(jié)點(diǎn)上放置視頻副本內(nèi)容。但是在視頻內(nèi)容占用存儲(chǔ)多的情況下，節(jié)點(diǎn)不可能也沒有必要把全部視頻內(nèi)容存儲(chǔ)在本地，當(dāng)節(jié)點(diǎn)沒有所求內(nèi)容時(shí)，可以從鄰域分組海端節(jié)點(diǎn)獲取所請(qǐng)求內(nèi)容來為用戶提供服務(wù)。本文結(jié)合海端節(jié)點(diǎn)動(dòng)態(tài)特性，在鄰域分組海端節(jié)點(diǎn)協(xié)作服務(wù)時(shí)，以最小化節(jié)點(diǎn)之間傳輸數(shù)據(jù)的代價(jià)為目標(biāo)，提出基于時(shí)間匹配度的副本放置算法RPTM (Replica Placement based on Time Matching algorithm)。

2 問題描述

2.1 視頻內(nèi)容的獲取

在部署視頻片段時(shí)，視頻內(nèi)容按用戶點(diǎn)播熱度進(jìn)行排序，可發(fā)現(xiàn)影片分布大致服從帕累托法則[14]，即排名靠前的少數(shù)影片貢獻(xiàn)了大部分點(diǎn)擊量，選取前m個(gè)視頻內(nèi)容作為熱點(diǎn)視頻。

2.2 副本放置

鄰域分組海端節(jié)點(diǎn)副本放置問題：已知n個(gè)節(jié)點(diǎn)及它們組成的拓?fù)銰，節(jié)點(diǎn)i的存儲(chǔ)容量為si，在邊k上傳輸單位數(shù)據(jù)量付出的代價(jià)為ck，有m個(gè)視頻內(nèi)容，視頻內(nèi)容j的大小為bj，被訪問概率為pj，每個(gè)節(jié)點(diǎn)所服務(wù)用戶的請(qǐng)求到達(dá)率為ωi。求m個(gè)視頻內(nèi)容在n個(gè)鄰域分組海端節(jié)點(diǎn)上的放置策略，使節(jié)點(diǎn)間因彼此傳輸視頻內(nèi)容而產(chǎn)生的代價(jià)C最小。

由于海端節(jié)點(diǎn)具有動(dòng)態(tài)特性(隨時(shí)上線或者離線)，中心管理服務(wù)器根據(jù)歷史記錄預(yù)測(cè)出每個(gè)海端節(jié)點(diǎn)一天內(nèi)在線時(shí)間，節(jié)點(diǎn)i和節(jié)點(diǎn)k的在線時(shí)間段分別為Ti、Tk。本文引入一個(gè)參數(shù)時(shí)間匹配度Dik，表示一天時(shí)間內(nèi)節(jié)點(diǎn)i在線時(shí)間段里，節(jié)點(diǎn)k也在線時(shí)間段的比例。數(shù)學(xué)表達(dá)式如下：

Dik=|Ti∩Tk|/|Ti|

(1)

其中0≤Dik≤1。

假設(shè)在鄰域分組海端節(jié)點(diǎn)之間，當(dāng)其中某個(gè)節(jié)點(diǎn)向其他節(jié)點(diǎn)請(qǐng)求內(nèi)容時(shí)，總是去請(qǐng)求有內(nèi)容、滿足時(shí)間匹配度要求且到它的傳輸代價(jià)最小的節(jié)點(diǎn)進(jìn)行傳輸，而不考慮其他節(jié)點(diǎn)的當(dāng)前服務(wù)負(fù)載和帶寬。

用xij表示媒體內(nèi)容j在節(jié)點(diǎn)i上是否已存儲(chǔ)：

(2)

用一個(gè)m×n的矩陣X來表示每個(gè)節(jié)點(diǎn)上每個(gè)視頻內(nèi)容的存儲(chǔ)狀態(tài)：

(3)

當(dāng)用戶從節(jié)點(diǎn)i請(qǐng)求視頻內(nèi)容j時(shí)，為滿足其用戶請(qǐng)求，產(chǎn)生的代價(jià)為：

Cij(X)=PjbjHij(X)

(4)

在單位時(shí)間內(nèi)，請(qǐng)求到達(dá)率為ωi情況下的總代價(jià)為：

(5)

系統(tǒng)的總代價(jià)期望為：

(6)

所以，需求解決的是如下的優(yōu)化問題：

(7)

由于海端節(jié)點(diǎn)存儲(chǔ)空間有限，所以限制條件是指每個(gè)節(jié)點(diǎn)上放置的視頻內(nèi)容的總大小等于其存儲(chǔ)容量。這是個(gè)NP完全問題，在文獻(xiàn)[15]中提出了全局貪婪放置算法RPGG。

2.3 基于時(shí)間匹配度的算法

本文提出的RPTM算法，從代價(jià)為0的狀態(tài)(X的元素全部為1)出發(fā)，采用貪婪的方式來逐漸變換放置矩陣，每次刪除一個(gè)節(jié)點(diǎn)上的一個(gè)內(nèi)容，使代價(jià)的增量最小，最后達(dá)到滿存儲(chǔ)容量的限制。本算法在文獻(xiàn)[15]的啟發(fā)式貪婪算法中引入時(shí)間匹配度因子，在計(jì)算系統(tǒng)代價(jià)時(shí)，充分考慮海端節(jié)點(diǎn)的動(dòng)態(tài)性。下面詳細(xì)介紹本文算法。

若把某個(gè)節(jié)點(diǎn)上的某個(gè)視頻內(nèi)容刪除，會(huì)增加用戶訪問此內(nèi)容的代價(jià)，式(6)改寫如下：

(8)

則用戶訪問視頻內(nèi)容j產(chǎn)生的代價(jià)是：

(9)

所以總代價(jià)如下：

(10)

算法詳細(xì)步驟：

初始化放置矩陣X，使其每個(gè)元素為1，即每個(gè)節(jié)點(diǎn)上存儲(chǔ)有每個(gè)視頻內(nèi)容，當(dāng)用戶請(qǐng)求視頻內(nèi)容時(shí)本地都有，無需從其他節(jié)點(diǎn)獲取，所以不產(chǎn)生傳輸代價(jià)，即此時(shí)的總代價(jià)為0。

1)首先對(duì)每一個(gè)視頻內(nèi)容j，計(jì)算用戶訪問內(nèi)容j而產(chǎn)生的代價(jià)，這是針對(duì)內(nèi)容j (j=1,2,…,m)的當(dāng)前總代價(jià)：

(11)

其中，Hij(X)的含義同2.2節(jié)。

3)對(duì)內(nèi)容j，重復(fù)執(zhí)行步驟2，可得到aj個(gè)ΔCj。

6)轉(zhuǎn)步驟1，在新的X狀態(tài)下重復(fù)上述過程，直到所有的節(jié)點(diǎn)都滿足存儲(chǔ)容量限制。

3 仿 真

為了驗(yàn)證本文所提出的RPTM算法的有效性，搭建了有效的仿真環(huán)境進(jìn)行仿真。為確保算法的性能，選取有參考性的隨機(jī)算法(Random Replica Placement algorithm, RRP)和文獻(xiàn)[15]算法RPGG與本文算法RPTM進(jìn)行比較。

3.1 仿真環(huán)境搭建

本文采用GT-ITM生成Transit-Stub拓?fù)洌總€(gè)節(jié)點(diǎn)都作為一個(gè)海端節(jié)點(diǎn)。每個(gè)節(jié)點(diǎn)有各個(gè)節(jié)點(diǎn)之間的距離、時(shí)間匹配度等拓?fù)湫畔?。仿真中?duì)每個(gè)節(jié)點(diǎn)數(shù)，都產(chǎn)生10個(gè)不同的拓?fù)?，所給出的結(jié)果是10個(gè)拓?fù)渖线\(yùn)行結(jié)果的均值。

3.2 仿真參數(shù)配置

3.3 仿真結(jié)果

1)取Zipf分布參數(shù)a=0.6、時(shí)間匹配度閾值d=0.5、視頻內(nèi)容數(shù)目m=1000、節(jié)點(diǎn)數(shù)目n=100時(shí)，本文RPTM算法分別與隨機(jī)算法RRP、貪婪算法RPGG進(jìn)行比較。仿真中時(shí)間匹配度閾值d的取值根據(jù)仿真實(shí)驗(yàn)數(shù)據(jù)，選擇了當(dāng)本文中提出的算法效率最高，即算法平均代價(jià)減少最多時(shí)的值d=0.5，結(jié)果如表1、圖2與表2所示。

表1 n=100、 m=1000時(shí)3種算法下的代價(jià)

rCost(RPGG)Cost(RRP)Cost(RPTM)0.05441.239513.235334.450.10297.100358.922220.0560.15241.220263.157189.7120.20153.971190.728128.3430.30107.779118.79197.510

圖2 n=100、 m=1000時(shí)相對(duì)代價(jià)

表2 n=100、 m=1000時(shí)RPTM算法代價(jià)減少比例

r減少比例/%0.0523.50.1024.50.1521.20.2016.60.309.5

2)取Zipf分布參數(shù)a=0.6、時(shí)間匹配度閾值d=0.5、視頻內(nèi)容數(shù)目m=5000、節(jié)點(diǎn)數(shù)目n=200時(shí)，本文RPTM算法分別與RRP算法、RPGG算法進(jìn)行比較的結(jié)果如表3、圖3與表4所示。仿真中時(shí)間匹配度閾值d的取值根據(jù)仿真實(shí)驗(yàn)數(shù)據(jù)，選擇了當(dāng)本文中提出的算法效率最高，即算法平均代價(jià)減少最多時(shí)的值d=0.5。

表3 n=200、 m=5000時(shí)3種算法下的代價(jià)

rCost(RPGG)Cost(RRP)Cost(RPTM)0.05634.488849.635506.6740.10356.846507.226246.3940.15254.890342.761212.4090.20212.408257.547178.4230.30161.430173.624135.942

圖3 n=200、 m=5000時(shí)相對(duì)代價(jià)

表4 n=200、 m=5000時(shí)RPTM算法代價(jià)減少比例

r減少比例/%0.0520.20.1030.90.1516.60.2016.00.3015.7

從表1和表3數(shù)據(jù)可以得出：在節(jié)點(diǎn)數(shù)和副本數(shù)相同的情況下，本文提出的RPTM算法總代價(jià)最小。這是因?yàn)椋罕疚乃惴ㄖ幸肓朔虾６斯?jié)點(diǎn)動(dòng)態(tài)特性的時(shí)間匹配度因子，即計(jì)算節(jié)點(diǎn)為滿足用戶請(qǐng)求從其他節(jié)點(diǎn)獲取內(nèi)容而產(chǎn)生的代價(jià)時(shí)，首先考慮存儲(chǔ)有內(nèi)容的節(jié)點(diǎn)是否在線問題，然后選擇放置副本的節(jié)點(diǎn)。3種算法下，系統(tǒng)總代價(jià)隨著節(jié)點(diǎn)存儲(chǔ)容量占所有媒體內(nèi)容總大小的比例r的增加，其產(chǎn)生的代價(jià)都在減少，這是因?yàn)殡S著r的增加，在節(jié)點(diǎn)數(shù)和副本數(shù)一定的情況下，每個(gè)節(jié)點(diǎn)存儲(chǔ)的內(nèi)容更多，減少了節(jié)點(diǎn)為用戶提供服務(wù)從其他節(jié)點(diǎn)獲取內(nèi)容而產(chǎn)生的傳輸代價(jià)。表2和表4分別給出了n=100, m=1000和n=200, m=5000時(shí)RPTM算法比RPGG算法的代價(jià)減少情況,即比RPGG算法代價(jià)降低了10%～31%。

從圖2和圖3可以看出：隨著r的逐漸增加，從RRP算法到RPGG算法再到RPTM算法，其改進(jìn)效果呈現(xiàn)出先增加后減少的趨勢(shì)。這是因?yàn)閞較小的時(shí)候，每個(gè)節(jié)點(diǎn)的存儲(chǔ)容量都很小，限制了內(nèi)容調(diào)度的空間，也就限制了不同算法的發(fā)揮空間。當(dāng)r增大時(shí)，節(jié)點(diǎn)存儲(chǔ)容量增大，3種算法起的作用差異就明顯增大。而當(dāng)r繼續(xù)增大，節(jié)點(diǎn)的存儲(chǔ)容量很大時(shí)，算法可以獲得的效果差異會(huì)越來越小，最終趨于沒有差異。

3)從前面內(nèi)容已知，時(shí)間匹配度閾值的取值范圍是0≤d≤1。表5與表6給出了當(dāng)時(shí)間匹配度閾值d取不同值時(shí)，RPTM算法代價(jià)減少比例的平均值。平均值是在r分別取0.05、0.10、0.15、0.20、0.30時(shí)的平均值。

表5 n=100、 m=1000、 a=0.6時(shí)RPTM算法代價(jià)減少比例的平均值

d平均減少比例/%0.15.670.317.330.519.060.83.98

表6 n=200、 m=5000、 a=0.6時(shí)RPTM算法代價(jià)減少比例的平均值

d平均減少比例/%0.13.440.315.400.519.880.85.61

從表5和表6數(shù)據(jù)可以得出：在節(jié)點(diǎn)數(shù)和副本數(shù)相同的情況下，當(dāng)時(shí)間匹配度閾值d取不同的值時(shí)，RPTM算法代價(jià)減少比例平均值也會(huì)隨之變化；當(dāng)d=0.5時(shí)RPTM算法代價(jià)減少比例平均最高，也就是RPTM算法起的作用最明顯；而當(dāng)d=0.1和d=0.8時(shí)，RPTM算法代價(jià)減少比例的平均值都明顯較小，這是因?yàn)楫?dāng)d=0.1時(shí)，對(duì)節(jié)點(diǎn)之間在線時(shí)間的相似性要求較小，限制了時(shí)間匹配度的影響，也就限制了RPTM算法的發(fā)揮空間；而當(dāng)d=0.8時(shí)，對(duì)節(jié)點(diǎn)之間在線時(shí)間的相似性要求過高，導(dǎo)致節(jié)點(diǎn)之間過于依賴時(shí)間的相似性，而忽略節(jié)點(diǎn)之間的代價(jià)，這就限制了RPTM算法代價(jià)達(dá)到一個(gè)較好的效果。

4 結(jié)束語

在海云協(xié)同架構(gòu)媒體服務(wù)系統(tǒng)中，結(jié)合海端節(jié)點(diǎn)的動(dòng)態(tài)特性，引入時(shí)間匹配度因子，以優(yōu)化協(xié)作海端節(jié)點(diǎn)之間協(xié)同傳輸代價(jià)為目標(biāo)，本文提出了一種靜態(tài)副本放置算法。這是一種符合海云協(xié)同媒體服務(wù)系統(tǒng)動(dòng)態(tài)、彈性、自治、現(xiàn)場(chǎng)化特點(diǎn)的，基于全局信息的啟發(fā)式算法。仿真結(jié)果表明此算法是有效的。