邊緣節(jié)點(diǎn)緩存替換策略研究

崔炳輝 李孜 薛吉 李佳偉

摘要：緩存替換機(jī)制是內(nèi)容中心網(wǎng)絡(luò)研究的重點(diǎn)，在解決網(wǎng)絡(luò)時(shí)延與網(wǎng)絡(luò)帶寬擁堵等問題中發(fā)揮著重要作用。針對(duì)目前邊緣側(cè)量節(jié)點(diǎn)設(shè)備緩存空間的有限性，提出一種基于猴群算法的優(yōu)化方案。該方案可合理地對(duì)邊緣設(shè)備緩存內(nèi)容進(jìn)行置換，有效提高邊緣量設(shè)備請(qǐng)求命中率。通過在猴群算法的猴群爬過程中引入文件流行度等引導(dǎo)因子、在望過程中改進(jìn)猴群視野范圍等方法找到最優(yōu)解。仿真實(shí)驗(yàn)結(jié)果顯示了不同大小的邊緣設(shè)備緩存空間請(qǐng)求命中率。與傳統(tǒng)算法相比，該方案可有效提高請(qǐng)求命中率。

關(guān)鍵詞：緩存替換;邊緣設(shè)備;猴群算法;請(qǐng)求命中率

DOI： 10. 11907/rjdk.191 825

開放科學(xué)（資源服務(wù)）標(biāo)識(shí)碼（OSID）：

中圖分類號(hào)：TP301

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1672-7800（2020）004-0131-04

Research on Cache Replacement Strategy for Edge Nodes

CUI Bing-hui，LI Zj，XUE Jj2 . LI Jja-wejl

（1.School of Mechanic.s Engirzeering ， University of .Sh.anghaifor .Science and Technology ， Sh.anghai 200093 ， China ;

2.Sh anghai Electrical Apparatus Re.search Institute（Cro up） Co. . Ltd. ， Sh.anghai 200063 . China ）Abstract： Cache replacement mechanisru is an iruportant part of content-centric network research. It is ，videly used to solve network de-lay and network bandwidth congestion. Aiming at the limitation of the buffer space of' edge detection devices， we propose an optimiza-tion scheme based on iuonkey swarm algorithm "-hich can replace the content of edge detection devices' cache reasonably and effective-ly to improve the hit rate of edge detection devices' requests. In order to find the optimal solution， this paper introduces some guidingfactors such as file popularity into the monkey group cra"-ling process and improves the horizon of the monkey group in the looking pro-cess. Then the simulation experiments are carried out. The experimental results shou-， the hit rate of' each request in different size ofedge device cache space. rinally ， by coruparing with the traditional algorithm， it is proved that this scheme can eff'ectively improve thehit rate of requests.Key Words ： Cache replacement ; edge device ; monkey algorithm ; requ est hit ratio

O 引言

隨著網(wǎng)絡(luò)的不斷發(fā)展，嵌入式產(chǎn)品數(shù)量逐年增加，感應(yīng)層海量數(shù)據(jù)隨之產(chǎn)生，傳統(tǒng)云計(jì)算模式處理能力已不能滿足數(shù)據(jù)實(shí)時(shí)傳輸、計(jì)算及快速?zèng)Q策需求。因此需要一種新的邊緣計(jì)算模型，輔助云中心處理海量數(shù)據(jù)[1-3]。邊緣計(jì)算利用更靠近數(shù)據(jù)源的邊緣節(jié)點(diǎn)設(shè)備計(jì)算與存儲(chǔ)能力，快速處理部分請(qǐng)求，可以有效減少帶寬壓力與網(wǎng)絡(luò)延時(shí)。

但是，每個(gè)邊緣節(jié)點(diǎn)設(shè)備的存儲(chǔ)空間有限[4]，只能存儲(chǔ)一些具有高訪問頻率的文件，隨著時(shí)間變化，各文件請(qǐng)求頻率也會(huì)發(fā)生相應(yīng)變化，而具有高訪問頻率的文件不能保持一成不變。因此，當(dāng)邊緣測(cè)量設(shè)備的緩存空間已滿時(shí)，需清除價(jià)值較小的文件，并根據(jù)某種替換策略存儲(chǔ)新的、更有價(jià)值的數(shù)據(jù)，以提高緩存空間請(qǐng)求命中率[5]。因此，提升網(wǎng)絡(luò)整體性能的關(guān)鍵是如何合理地管理和替換緩存內(nèi)容[6]。

傳統(tǒng)緩存替換算法有FIFO（First In First Out）算法、LFU[7] （Least Frequentlv Used）算法、LRU[8]（Least RecentlvUsed）算法、SIZE替換策略[9]。FIFO算法優(yōu)先替換掉最先進(jìn)入緩存區(qū)的對(duì)象，使最新文件替換到緩存區(qū)中，該算法比較容易實(shí)現(xiàn)，復(fù)雜度低，但請(qǐng)求命中率較低;LRU算法將離上一次被訪問時(shí)間間隔最長(zhǎng)的文件對(duì)象優(yōu)先替換掉，將最近訪問的文件替換進(jìn)來，認(rèn)為最近經(jīng)常被訪問的文件數(shù)據(jù)在之后一段時(shí)間內(nèi)被訪問的概率較高，該算法忽略了在一段時(shí)間內(nèi)客戶端訪問文件的偶然性對(duì)文件的影響，同時(shí)當(dāng)文件流行程度發(fā)生改變時(shí)也會(huì)導(dǎo)致該算法適應(yīng)度較差;基于對(duì)象大小的SIZE替換算法將緩存中所占空間較大的文件替換為較小的文件，認(rèn)為文件數(shù)量越多，被訪問概率越高，但沒有考慮緩存命中次數(shù)，反而將一些較小且價(jià)值不高的文件存儲(chǔ)在邊緣設(shè)備上;LFU替換策略認(rèn)為訪問頻率越高的資源，被訪問價(jià)值越大，因此當(dāng)緩存空間不足時(shí)，總是替換客戶端訪問頻率最低的內(nèi)容。但是有可能文件訪問程度越高，占用空間很大，存儲(chǔ)內(nèi)容卻太少。以上4種傳統(tǒng)緩存替代算法僅考慮單方面影響因素，存在一定缺陷。

猴群算法是Zhao &Tang[10]于2008年提出的新興智能優(yōu)化算法。該算法源于對(duì)白然界中猴群爬山過程的模擬，其主要思想是模仿猴群爬山的過程[11]。猴子通過爬、望、跳3個(gè)基本動(dòng)作方式向最高山峰前進(jìn)。它是一種簡(jiǎn)單有效、隨機(jī)改變的全局性優(yōu)化算法，具有尋優(yōu)能力強(qiáng)、參數(shù)少等優(yōu)點(diǎn)，可有效解決復(fù)雜問題，逐漸成為計(jì)算研究領(lǐng)域的一大熱點(diǎn)。本文結(jié)合猴群算法，針對(duì)傳統(tǒng)算法的不足，綜合考慮文件訪問次數(shù)、文件大小及文件流行度等因素，提出基于猴群算法的優(yōu)化策略。

1衡量指標(biāo)

當(dāng)產(chǎn)生感應(yīng)層數(shù)據(jù)請(qǐng)求時(shí)，對(duì)請(qǐng)求數(shù)據(jù)的回應(yīng)如圖1所示，如果邊緣節(jié)點(diǎn)設(shè)備的內(nèi)存空間存儲(chǔ)了該請(qǐng)求數(shù)據(jù)，則此時(shí)邊緣沒備作為一個(gè)臨時(shí)服務(wù)器，立即對(duì)請(qǐng)求的數(shù)據(jù)進(jìn)行回應(yīng);如果邊緣設(shè)備沒存儲(chǔ)該請(qǐng)求數(shù)據(jù)，只能上傳數(shù)據(jù)，選擇云服務(wù)器回應(yīng)數(shù)據(jù)請(qǐng)求。但是數(shù)據(jù)通過網(wǎng)絡(luò)上傳會(huì)導(dǎo)致數(shù)據(jù)決策時(shí)延。如何選擇合理的文件存入邊緣設(shè)備中進(jìn)行緩存替換是本文重點(diǎn)研究?jī)?nèi)容。 （2）計(jì)算廠（y1），如果f（yi）>f（x：），且y=（yl，y2，…，yn）在允許范圍內(nèi)，則更新xi為yi;否則xi保持不變，重復(fù)執(zhí)行上述步驟，直到找到滿足條件的y點(diǎn)。

（3）到達(dá)更好位置y后，猴子以y為起點(diǎn)重新執(zhí)行爬過程[19]。

2.3跳過程

跳過程主要是從空翻限制范圍[a.b]內(nèi)隨機(jī)生成一個(gè)空翻控制系數(shù) ，其中 ，為空翻支點(diǎn)。若y在可行范圍內(nèi)，則用y替換掉xi，否則繼續(xù)執(zhí)行步驟，直至找到合適的y值。

3基于改進(jìn)猴群算法的緩存替換問題

用猴群算法解決緩存替換問題是在以公式（2）為目標(biāo)的基礎(chǔ)上尋求最優(yōu)解的過程。在求解過程中，可行解的集合相當(dāng)于猴群種群大小，每一只猴子的位置相當(dāng)于目標(biāo)函數(shù)的一個(gè)可行解，文件數(shù)量對(duì)應(yīng)維數(shù)[20]。在猴群算法設(shè)計(jì)過程中，由于猴群在爬過程和望過程中的前進(jìn)方向存在隨機(jī)性，導(dǎo)致算法復(fù)雜程度變大、目標(biāo)函數(shù)無法快速收斂，所以在設(shè)計(jì)過程中通過加入文件流行度與文件單位存儲(chǔ)大小等誘導(dǎo)因素，并改進(jìn)固定的視野距離，從而對(duì)整個(gè)算法進(jìn)行完善。

3.1誘導(dǎo)因子設(shè)計(jì)

誘導(dǎo)因子是猴群算法在猴子爬過程中給猴子一個(gè)前進(jìn)的方向，讓猴群朝著設(shè)計(jì)的目標(biāo)前進(jìn)。針對(duì)傳統(tǒng)緩存替代算法僅考慮單一因素的不足，綜合考慮文件大小與文件訪問頻率，以及一段時(shí)間內(nèi)文件流行度等綜合因素，設(shè)計(jì)誘導(dǎo)因子改進(jìn)傳統(tǒng)算法。

由于請(qǐng)求命中率只能在用戶進(jìn)行訪問時(shí)才可計(jì)算，并且替換算法需在訪問發(fā)生之前調(diào)整邊緣設(shè)備存儲(chǔ)的緩存內(nèi)容，因此該算法的目的是基于歷史數(shù)據(jù)預(yù)測(cè)下一個(gè)階段請(qǐng)求命中率。由于用戶對(duì)某一個(gè)文件數(shù)據(jù)的請(qǐng)求不是一成不變的，而是隨時(shí)間改變不斷變化，因此該文件的請(qǐng)求命中率也在不停變化。例如，緩存中的一些內(nèi)容在當(dāng)前時(shí)間段內(nèi)受到用戶高度關(guān)注，且請(qǐng)求命中率與文件流行度也非常高，但隨著客戶端對(duì)該文件請(qǐng)求次數(shù)的降低，該內(nèi)容很可能變成用戶很少訪問的對(duì)象，所以相應(yīng)的請(qǐng)求命中率也會(huì)下降，為了對(duì)文件進(jìn)行準(zhǔn)確預(yù)測(cè)，提出可利用文件流行度進(jìn)行文件性能分析。文件流行度根據(jù)上個(gè)周期內(nèi)容流行度及當(dāng)前周期內(nèi)該內(nèi)容命中率計(jì)算而來。

其中，pi（t）為當(dāng)前周期內(nèi)文件i的文件流行度;hi（t-1）代表文件i上個(gè)周期內(nèi)文件請(qǐng)求命中率; 為衰減因子，表示上個(gè)周期文件流行度在當(dāng)前周期所占比列; 表示文件i在當(dāng)前周期的請(qǐng)求命中率。

求出每個(gè)文件單位存儲(chǔ)空間的價(jià)值量，第i件物的價(jià)值量為：求出每個(gè)文件所占存儲(chǔ)空間的比列為：由此可設(shè)置誘導(dǎo)因子為：

3.2算法步驟

設(shè)置種群規(guī)模M=30、最大迭代次數(shù)Max=1000。算法流程如圖2所示。

隨機(jī)生成二進(jìn)制向量的一個(gè)解 作為猴子的初始位置。其中第x，維度只能為0或者l。當(dāng)其為1時(shí)，代表第i文件被選中;當(dāng)其為0時(shí)，代表第i文件未被選中。執(zhí)行爬過程計(jì)算 ，從而優(yōu)先選取物品中單位存儲(chǔ)空間訪問程度最高的文件并存人邊緣設(shè)備中，同時(shí)引入誘導(dǎo)因子。

選取可行解 、隨機(jī)選取的文件 及未被選取的文件 ，其中 和 屬于0到D，分別計(jì)算它們的誘導(dǎo)因子，如果 ，則更新猴子的位置， 為 為O;否則猴子的位置不變。計(jì)算 ，如果 ，則 更新為 ，否則xi保持不變。

爬過程之后每只猴子都達(dá)到了小范圍的局部最優(yōu)，為實(shí)現(xiàn)較大范圍的尋優(yōu)過程，可在望過程中進(jìn)行搜索。所以視野距離y決定望過程的范圍，但由于y值過小，此時(shí)望過程與爬過程的區(qū)別不大，y值過大的目標(biāo)函數(shù)收斂過慢，可能導(dǎo)致在最大迭代次數(shù)之后均無法找到最優(yōu)值。為了平衡這種情況，對(duì)y進(jìn)行一些改進(jìn)。

其中p代表當(dāng)前迭代次數(shù)， 代表當(dāng)前函數(shù)值與最近替換前的函數(shù)值。因此望過程的視野范圍 在視野允許的范圍內(nèi)，隨機(jī)生成一個(gè)向量 ，則 ，其中 為猴群可視距離。計(jì)算 ，如果 ， 在允許范圍內(nèi)，則更新 為 。隨著函數(shù)越來越接近最優(yōu)值，視野距離的值越來越大，從而可有效降低快速陷入局部最優(yōu)的可能性。與迭代次數(shù)同時(shí)進(jìn)行改變可有效維持函數(shù)平衡。

執(zhí)行跳過程，計(jì)算 ，生成一個(gè)新的二進(jìn)制向量 。若v在可行范圍中，則用v替換 ;否則繼續(xù)執(zhí)行以上步驟直到找到合適的y值。

重復(fù)上述步驟直到達(dá)到最大的迭代次數(shù)，結(jié)束算法，輸出最優(yōu)值與最優(yōu)個(gè)體。

4 實(shí)驗(yàn)與分析

4.1 實(shí)驗(yàn)數(shù)據(jù)選擇

在MATLAB軟件上進(jìn)行仿真實(shí)驗(yàn)，客戶端用戶請(qǐng)求習(xí)慣一般符合Zipf規(guī)律，為了驗(yàn)證實(shí)驗(yàn)合理性，對(duì)于實(shí)驗(yàn)數(shù)據(jù)的選擇也需符合Zipf正態(tài)分布規(guī)律。本文選取的基本測(cè)試實(shí)驗(yàn)數(shù)據(jù)如表l所示。

為了更契合客戶端請(qǐng)求習(xí)慣，隨機(jī)選取其中20個(gè)文件作為高頻文件并對(duì)其進(jìn)行1600次請(qǐng)求訪問，對(duì)剩下的80個(gè)文件進(jìn)行400次請(qǐng)求訪問。

在仿真中，將改進(jìn)猴群算法解決邊緣設(shè)備的緩存替換參數(shù)設(shè)置為：種群規(guī)模M=30，最大迭代次數(shù)Max=1000，爬步長(zhǎng)a=l，衰減因子^=0.4，視野距離y=0.5，跳區(qū)間[a，b]=[-1，1]，常數(shù)s=1.2。

4.2實(shí)驗(yàn)結(jié)果

本文實(shí)驗(yàn)基于表1的數(shù)據(jù)進(jìn)行仿真。圖3對(duì)比了改進(jìn)猴群算法與傳統(tǒng)算法在文件總大小為2000MB、邊緣設(shè)備存儲(chǔ)空間大小不同的情況下對(duì)應(yīng)的請(qǐng)求命中率。該圖總體反映了改進(jìn)猴群算法在邊緣設(shè)備中請(qǐng)求命中率有良好效果。尤其在邊緣設(shè)備存儲(chǔ)空間較小時(shí)，明顯優(yōu)于其它算法，但是在邊緣儲(chǔ)存空間較大時(shí)，請(qǐng)求命中率提高幅度不明顯。通過分析可知改進(jìn)的猴群算法可在一定程度上提高請(qǐng)求命中率，本文實(shí)驗(yàn)也驗(yàn)證了算法可行性。

5結(jié)語

本文主要在猴群算法中通過加入誘導(dǎo)因子，使得到的解朝著設(shè)計(jì)的方向前進(jìn)，解決了在邊緣設(shè)備存儲(chǔ)空間一定的情況下，如何選擇更合適文件的問題，從而提高了邊緣設(shè)備請(qǐng)求命中率。但是由于猴群算法是逐步尋優(yōu)，因此要求邊緣設(shè)備有一定的計(jì)算能力，不適用于邊緣沒備計(jì)算能力較弱的情況。同時(shí)，實(shí)驗(yàn)結(jié)果反映該算法在邊緣設(shè)備存儲(chǔ)空間較大時(shí)，得到的效果并不十分明顯，該算法更適用于邊緣設(shè)備存儲(chǔ)空間較小的情況。后續(xù)研究將進(jìn)一步優(yōu)化計(jì)算，擴(kuò)展算法應(yīng)用范圍。

參考文獻(xiàn)：

[l]王曉飛，韓溢文邊緣智能計(jì)算與智能邊緣計(jì)算[J].張江科技評(píng)論，2019（2）：10-12

[2]劉俊奇，范明翔，李瀟.大數(shù)據(jù)時(shí)代下的新型計(jì)算模型——邊緣計(jì)算[J].電腦知識(shí)與技術(shù)，2017，13（19）：182-183

[3]吳大鵬，張普寧，王汝言.“端邊云”協(xié)同的智慧物聯(lián)網(wǎng)[J]物聯(lián)網(wǎng)學(xué)報(bào)，2018，2（03）：21-28

[4]BEAVERS I.智能邊緣：邊緣節(jié)點(diǎn)[J].中國(guó)集成電路，2017，26（11）：53-57+81.

[5]黃丹，宋榮方.基于內(nèi)容價(jià)值的緩存替換策略[J].電信科學(xué)，2018，34（11）：59-66.

[6]翟聰聰，鄒君妮基于時(shí)延和效用的多速率視頻的緩存優(yōu)化[J].電子測(cè)量技術(shù)，2018，41（15）：66-71

[7]黃賢明.基于LRU改進(jìn)算法的實(shí)時(shí)數(shù)據(jù)庫緩存機(jī)制[J]工業(yè)控制計(jì)算機(jī)，2015，28（12）：63+77.

[8]CUO J，LIU C C， CHEN J L.et al. S-LRU：a Cache replacement algo-rithm of video sharing system for mobile devices[C].Changchun： Pro-ceedings of 2012 2nd International Conference on Computer Scienceand Network Technology， 2012.

[9]陳建，沈?yàn)t軍，姚一楊，等.基于密文策略屬性基加密系統(tǒng)訪問機(jī)制的緩存替換策略[J].計(jì)算機(jī)應(yīng)用，2017，37（10）：2964-2967

[10]ZHAO R Q，TANG WS. Monkey algorithm for glohal numerical opti-mization[Jl. Journal of Uncertain Svstems. 2008，2（3）： 164-176.

[11] 張東潔猴群算法的改進(jìn)及其應(yīng)用[D].西安：西安理工大學(xué)，2017.

[12] 黎慧源，易國(guó)洪，代瑜，等.貪婪雙尺寸頻率算法的優(yōu)化與改進(jìn)[J].武漢工程大學(xué)學(xué)報(bào)，2018，40（6）：685-690

[13] 肖敬偉.基于數(shù)據(jù)挖掘的緩存替換算法研究[D].北京：北京交通大學(xué)，2015

[14] 王博.同步電機(jī)遠(yuǎn)程數(shù)據(jù)采集與監(jiān)視控制系統(tǒng)[D].杭州：浙江大學(xué)，2018.

[15] 張?jiān)?NDN網(wǎng)絡(luò)中視頰數(shù)據(jù)緩存問題研究[D].合肥：中國(guó)科學(xué)技術(shù)大學(xué)，2017.

[16] 陳海濤.改進(jìn)的猴群算法在云計(jì)算資源分配中的研究[J].計(jì)算機(jī)系統(tǒng)應(yīng)用，2015，24（8）：191-196.

[17] 齊艷玉，蘭燕飛.一類基于動(dòng)態(tài)優(yōu)化問題的混沌猴群算法[J]武漢理工大學(xué)學(xué)報(bào)（信息與管理工程版），2013，35（2）：164-167.

[18]徐小平，張東潔.基于猴群算法求解旅行商問題[J].計(jì)算機(jī)工程與應(yīng)用，2018，54（2）：144-148.

[19] 杜國(guó)璋基于猴群算法的傳感器優(yōu)化布置方法研究[D].蘭州：蘭州交通大學(xué)，2016.

[20]徐小平，師喜婷，錢富才.基于猴群算法求解0-1背包問題[J].計(jì)算機(jī)系統(tǒng)應(yīng)用，2018，27（5）：133-138.

（責(zé)任編輯：江艷）

收稿日期：2019-06-17

作者簡(jiǎn)介：崔炳輝（1995-），男，上海理工大學(xué)機(jī)械工程學(xué)院碩士研究生，研究方向?yàn)殡娏﹄娮蛹夹g(shù)。