柳 興，楊 震，王新軍，朱 恒

（1.北京郵電大學(xué)計(jì)算機(jī)學(xué)院，北京100876； 2.中國(guó)聯(lián)合網(wǎng)絡(luò)通信集團(tuán)有限公司聯(lián)通（湖南）產(chǎn)業(yè)互聯(lián)網(wǎng)研究院，長(zhǎng)沙410014）（?通信作者電子郵箱liuxing_bupt@qq.com）

0 引言

隨著5G的商用，流量數(shù)據(jù)應(yīng)用（如人人視頻、愛(ài)奇藝、快手等）必然愈發(fā)普及［1］。邊緣計(jì)算將以更快的網(wǎng)絡(luò)服務(wù)響應(yīng)能力，受到各類移動(dòng)用戶的青睞［2］。有研究表明，未來(lái)流量數(shù)據(jù)將是以視頻流量為主［3］，因此，如何合理設(shè)計(jì)移動(dòng)邊緣計(jì)算（Mobile Edge Computing，MEC）的緩存策略是值得研究的課題。

目前，已經(jīng)有多個(gè)文獻(xiàn)對(duì)MEC中的緩存策略進(jìn)行了研究：文獻(xiàn)［4］基于智能域名解析設(shè)計(jì)了一種基站和核心網(wǎng)聯(lián)合部署的MEC架構(gòu)，實(shí)現(xiàn)了信息技術(shù)與通信技術(shù)的融合，將上層功能下沉到網(wǎng)絡(luò)邊緣；文獻(xiàn)［5］考慮用戶訪問(wèn)資源的整體代價(jià)，提出了一種基于效用的啟發(fā)式分層協(xié)作緩存策略，根據(jù)資源的效用值進(jìn)行決策，可最小化用戶資源訪問(wèn)代價(jià)；文獻(xiàn)［6］考慮MEC服務(wù)器之間的協(xié)作，提出了一種協(xié)作式緩存管理算法，可在最大化緩存命中率的同時(shí)最小化帶寬開(kāi)銷(xiāo)。然而，上述方法都是從MEC協(xié)議或架構(gòu)的角度進(jìn)行設(shè)計(jì)，并沒(méi)有考慮MEC的隨機(jī)環(huán)境，僅從架構(gòu)上來(lái)設(shè)計(jì)難以有效提升MEC的性能。

為了適應(yīng)MEC的隨機(jī)環(huán)境，進(jìn)一步提升邊緣計(jì)算的服務(wù)質(zhì)量，文獻(xiàn)［7］利用用戶間的社交關(guān)系建立內(nèi)容傳播模型，采用傳播動(dòng)力學(xué)方法預(yù)測(cè)小用戶數(shù)據(jù)下的內(nèi)容流行度，從個(gè)體角度出發(fā)預(yù)測(cè)內(nèi)容被訪問(wèn)的概率；文獻(xiàn)［8］為了提升時(shí)延容忍任務(wù)的用戶體驗(yàn)，通過(guò)獲取移動(dòng)用戶的運(yùn)動(dòng)軌跡及個(gè)人偏好信息，設(shè)計(jì)了移動(dòng)感知的服務(wù)調(diào)度算法；文獻(xiàn)［9］基于移動(dòng)用戶位置信息提出一種區(qū)域人群流量預(yù)測(cè)的時(shí)空網(wǎng)絡(luò)模型，通過(guò)融合各類外部特征信息，以短時(shí)局部流量降低對(duì)全局信息傳輸?shù)囊?；文獻(xiàn)［10］針對(duì)視頻應(yīng)用場(chǎng)景，通過(guò)在邊緣計(jì)算平臺(tái)上執(zhí)行視頻分析服務(wù)操作，通過(guò)視頻內(nèi)容貼近用戶放置來(lái)減少響應(yīng)時(shí)間。雖然上述研究在很大程度上提升了移動(dòng)邊緣計(jì)算的性能，但是這些研究并沒(méi)有關(guān)注MEC服務(wù)器存儲(chǔ)空間的價(jià)值，因此還有一定的性能提升空間。

針對(duì)該問(wèn)題，本文在考慮MEC服務(wù)器存儲(chǔ)空間受限的基礎(chǔ)上，利用移動(dòng)用戶群對(duì)不同對(duì)象的興趣差異，提出了一種基于興趣的內(nèi)容分發(fā)加速策略（Interest-based Content Distribution Acceleration Strategy，ICDAS）。該策略根據(jù)MEC服務(wù)器存儲(chǔ)空間、移動(dòng)用戶群對(duì)不同對(duì)象的興趣以及對(duì)象的文件大小，選擇性地在MEC服務(wù)器上緩存對(duì)象，最大限度地滿足移動(dòng)用戶群的內(nèi)容需求。仿真驗(yàn)證了所提策略的有效性。

1 系統(tǒng)模型

圖1給出了MEC的網(wǎng)絡(luò)架構(gòu)。如圖1所示，MEC服務(wù)器位于基站附近，可直接響應(yīng)移動(dòng)用戶請(qǐng)求，也可將請(qǐng)求轉(zhuǎn)發(fā)至后端的云數(shù)據(jù)中心。本文研究的內(nèi)容分發(fā)加速問(wèn)題，考慮MEC服務(wù)器存儲(chǔ)空間受限、移動(dòng)用戶群對(duì)不同對(duì)象的興趣差異，選擇性地緩存對(duì)象數(shù)據(jù)。

圖1 MEC網(wǎng)絡(luò)架構(gòu)［11］Fig.1 Network framework of MEC［11］

假設(shè)MEC中的所有移動(dòng)用戶群的對(duì)象需求集合為A={a1，a2，…，aN}，MEC服務(wù)器緩存任意對(duì)象ai∈A占用的存儲(chǔ)空間為p(ai)。假設(shè)MEC服務(wù)器的存儲(chǔ)空間為P，且至少能夠存儲(chǔ)任意一個(gè)對(duì)象，則有

考慮移動(dòng)用戶群對(duì)內(nèi)容分發(fā)加速的訴求是盡可能快地獲取對(duì)象數(shù)據(jù)，同一對(duì)象數(shù)據(jù)被用戶群體獲取次數(shù)越多，則認(rèn)為用戶群對(duì)該對(duì)象的興趣越高?？紤]到MEC服務(wù)器存儲(chǔ)空間受限，為了衡量用戶群對(duì)單位存儲(chǔ)空間內(nèi)存儲(chǔ)的對(duì)象內(nèi)容的興趣，引入興趣度的概念。

定義1 在[tj，tj+1)時(shí)段內(nèi)，任意對(duì)象ai∈A占用服務(wù)器的存儲(chǔ)空間為p(ai)，被用戶群訪問(wèn)的次數(shù)為ei，則稱該對(duì)象在[tj，tj+1)時(shí)段內(nèi)的興趣度為ei p(ai)。

本文的目標(biāo)是根據(jù)不同時(shí)期移動(dòng)用戶群對(duì)不同對(duì)象的興趣，設(shè)計(jì)一種緩存策略，提高M(jìn)EC服務(wù)器的緩存命中率，提升用戶感知。

2 方案設(shè)計(jì)

為了減少M(fèi)EC中的移動(dòng)用戶獲取對(duì)象的延時(shí)，則MEC服務(wù)器緩存的對(duì)象必須具備一定的興趣度。本文引入一個(gè)興趣度排序的概念，利用這一概念能使MEC服務(wù)器盡量緩存興趣度大的對(duì)象，提高M(jìn)EC服務(wù)器的緩存命中率。相應(yīng)的緩存特性用定理給出如下：

定理1 假設(shè)MEC服務(wù)器存儲(chǔ)空間為P，MEC中的所有移動(dòng)用戶在[tj，tj+1)時(shí)段對(duì)集合A的對(duì)象按興趣度遞減排序?yàn)閧a1'，a2'，…，aN'}，存在M＜N滿足：

證明 假設(shè)MEC服務(wù)器存儲(chǔ)空間為P，MEC中的所有移動(dòng)用戶的對(duì)象需求集合為A={a1，a2，…，aN}，則有：

假設(shè)所有移動(dòng)用戶在[tj，tj+1)時(shí)段對(duì)集合A的對(duì)象按興趣度遞減排序?yàn)椋鸻1'，a2'，…，a N'｝。MEC服務(wù)器至少能緩存任意一個(gè)對(duì)象，則有：

根據(jù)式（3）和（4），可推得存在M，滿足M＜N，使得式（1）成立。 證畢。

由定理1可知，MEC服務(wù)器根據(jù)對(duì)象興趣度排序便能極大地提升緩存命中率。由于MEC服務(wù)器是分布式架構(gòu)，服務(wù)器會(huì)根據(jù)用戶的需求做出響應(yīng)，同時(shí)根據(jù)對(duì)象的興趣度進(jìn)行緩存。本文主要考慮被動(dòng)拉的方式在MEC服務(wù)器上緩存用戶感興趣的對(duì)象，緩存控制策略的具體過(guò)程如下：

步驟1 MEC服務(wù)器接收用戶發(fā)起的對(duì)象ai的請(qǐng)求，并判斷是否存儲(chǔ)對(duì)象ai：若MEC服務(wù)器緩存了對(duì)象ai，則跳至步驟2；否則跳至步驟3。

步驟2 判斷MEC服務(wù)器緩存的對(duì)象ai是否為最新：若對(duì)象ai為最新，則跳至步驟5；否則跳至步驟3。

步驟3 判斷MEC服務(wù)器是否有緩存空間存儲(chǔ)對(duì)象ai最新版本，即P(tj)+P(ai(tj))≤P是否成立：若成立，則跳至步驟5；否則跳至步驟4。

步驟4 判斷MEC服務(wù)器用對(duì)象ai替換其他對(duì)象，是否可減少云數(shù)據(jù)中心的訪問(wèn)量，即P(aj')＜P(ai)≤P(aj')&&ej P(aj')＜ei P(ai)：若成立則跳至步驟 5；否則跳至步驟6。

步驟5 MEC服務(wù)器刪除對(duì)象{aj'|y＜j＜M}，緩存并交付對(duì)象ai，跳至步驟7。

步驟6 云數(shù)據(jù)中心交付對(duì)象ai，跳至步驟7。

步驟7 控制策略結(jié)束。

該策略中，P(tj)表示MEC服務(wù)器在tj時(shí)刻緩存的數(shù)據(jù)量，P(ai(tj))表示對(duì)象ai在tj時(shí)刻版本需要占用的緩存空間。由于策略采用用戶拉的方式來(lái)緩存并更新MEC服務(wù)器的對(duì)象，因此在系統(tǒng)啟動(dòng)時(shí)，MEC服務(wù)器不會(huì)緩存任何對(duì)象的數(shù)據(jù)。

3 仿真實(shí)驗(yàn)

仿真中，考慮移動(dòng)用戶向最近的MEC服務(wù)器發(fā)起申請(qǐng)，MEC服務(wù)器與后端云數(shù)據(jù)中心同步數(shù)據(jù)的場(chǎng)景。假設(shè)總共有1億個(gè)對(duì)象，所有對(duì)象的大小固定為p(ai)=10 MB，蜂窩小區(qū)為1 000臺(tái)移動(dòng)終端在線，MEC服務(wù)器存儲(chǔ)空間P=100 TB。本文從緩存命中率［12］和延時(shí)兩方面對(duì)所提策略的性能進(jìn)行分析，并將所提策略與主動(dòng)推送策略和周期同步策略進(jìn)行比較。

圖2給出了三種策略在緩存命中率方面的比較。從圖中可以看出：1）周期同步策略的緩存命中率會(huì)周期性地達(dá)到最大值，然后隨著時(shí)間的推移遞減；2）主動(dòng)推送策略的緩存命中率圍繞某一值波動(dòng)，驗(yàn)證了主動(dòng)推送策略是將最新的對(duì)象推送給MEC服務(wù)器緩存，但是最新的對(duì)象不一定是用戶最感興趣的對(duì)象；3）所提策略的緩存命中率隨著仿真時(shí)間的推移而增加并逐漸趨于一個(gè)穩(wěn)定值，這是因?yàn)樗岵呗允遣捎帽粍?dòng)拉的方式進(jìn)行緩存；4）當(dāng)所提策略的緩存命中率達(dá)到穩(wěn)定后，所提策略要優(yōu)于主動(dòng)推送策略和周期同步策略，驗(yàn)證了采用移動(dòng)用戶對(duì)對(duì)象的興趣度進(jìn)行緩存的方式可有效提升緩存命中率。

圖3給出了平均延時(shí)與用戶數(shù)之間的關(guān)系。從圖中可以看出：1）隨著用戶數(shù)的增加，三種策略的延時(shí)都有所增加，這是因?yàn)镸EC服務(wù)器的存儲(chǔ)空間有限，用戶數(shù)越大則對(duì)對(duì)象的種類需求大，必然導(dǎo)致部分用戶到后端云數(shù)據(jù)中心取數(shù)據(jù)；2）主動(dòng)推策略優(yōu)于周期同步策略，這主要是主動(dòng)推策略能將最新的對(duì)象及時(shí)緩存至MEC服務(wù)器；3）所提策略優(yōu)于主動(dòng)推策略，這是因?yàn)樗岵呗阅芨鶕?jù)小區(qū)用戶興趣在MEC服務(wù)器緩存對(duì)象。

圖2 三種策略的緩存命中率比較Fig.2 Comparison of cache hit ratioof three strategies

圖3 三種策略的平均延時(shí)與用戶數(shù)的關(guān)系Fig.3 Relationship between averagedelay and user number of three strategies

圖4給出了平均延時(shí)與小區(qū)數(shù)之間的關(guān)系。從圖中可以看出：1）三種策略的平均延時(shí)隨小區(qū)數(shù)的增加而增加，驗(yàn)證了不同小區(qū)用戶感興趣的對(duì)象不同，導(dǎo)致緩存命中率下降造成的結(jié)果；2）所提策略的平均延時(shí)相對(duì)較平穩(wěn)，且明顯低于另外兩種策略，這主要是因?yàn)樗岵呗猿浞挚紤]了不同小區(qū)用戶需求的差異，能根據(jù)不同小區(qū)用戶的需求，盡量緩存興趣度高的對(duì)象；3）結(jié)合圖3和圖4的仿真比較可得出結(jié)論，當(dāng)系統(tǒng)運(yùn)行達(dá)到穩(wěn)定后，所提策略較另外兩種策略，用戶獲取對(duì)象數(shù)據(jù)的時(shí)延可減少20%。

圖4 三種策略的平均延時(shí)與小區(qū)數(shù)的關(guān)系Fig.4 Relationship between averagedelay and cell number of three strategies

4 結(jié)語(yǔ)

本文對(duì)MEC中的內(nèi)容分發(fā)加速問(wèn)題進(jìn)行了研究，提出了一種ICDAS策略，該策略可根據(jù)不同小區(qū)用戶對(duì)不同對(duì)象的興趣的不同進(jìn)行差異化緩存，能夠較好地適應(yīng)MEC服務(wù)器存儲(chǔ)受限的場(chǎng)景。仿真結(jié)果表明，所提策略在緩存命中率和延時(shí)方面均優(yōu)于現(xiàn)有策略，在復(fù)雜的MEC環(huán)境中具有較好的應(yīng)用前景。文中所考慮的應(yīng)用場(chǎng)景具有一定的合理性和有效性，在某種程度上可以提升移動(dòng)邊緣計(jì)算的性能。然而，在實(shí)際應(yīng)用中，移動(dòng)用戶通常在一個(gè)區(qū)域內(nèi)活動(dòng)，相鄰MEC服務(wù)器上緩存的對(duì)象存在一定的關(guān)系。下一步研究工作的重點(diǎn)是，針對(duì)這種相鄰MEC服務(wù)器緩存的對(duì)象存在一定關(guān)系的情況設(shè)計(jì)聯(lián)合緩存，以提高策略的實(shí)用性。