關(guān)麗華

(山西經(jīng)貿(mào)職業(yè)學(xué)院，山西 太原 030024)

基于霧計(jì)算邊緣數(shù)據(jù)存儲(chǔ)的緩存置換技術(shù)研究

關(guān)麗華

(山西經(jīng)貿(mào)職業(yè)學(xué)院，山西 太原 030024)

圍繞霧計(jì)算的邊緣數(shù)據(jù)緩存置換技術(shù)的相關(guān)概念、實(shí)現(xiàn)原理，以及所涉及的主要算法進(jìn)行了調(diào)查研究，并在此基礎(chǔ)上針對(duì)邊緣數(shù)據(jù)緩存置換技術(shù)中蟻群算法的優(yōu)化與改進(jìn)提出了一些新的思路和方法，以期為相關(guān)領(lǐng)域的研究提供一些參考依據(jù)。

霧計(jì)算；邊緣數(shù)據(jù)；緩存置換；蟻群算法

霧計(jì)算是從云計(jì)算技術(shù)延伸發(fā)展出來(lái)的，專用于云平臺(tái)靠近用戶終端層面的邊緣數(shù)據(jù)優(yōu)化存儲(chǔ)和調(diào)度的一項(xiàng)技術(shù)。主要是針對(duì)云端平臺(tái)上邊緣數(shù)據(jù)的動(dòng)態(tài)存儲(chǔ)、響應(yīng)效率等問(wèn)題提出的一種數(shù)據(jù)存儲(chǔ)優(yōu)化解決方案。由于云端數(shù)據(jù)存儲(chǔ)采用的是集中式的處理方式，對(duì)于移動(dòng)接入端所產(chǎn)生的大量時(shí)延性要求較高的數(shù)據(jù)的處理效果并不理想。因此這類邊緣數(shù)據(jù)的運(yùn)算存儲(chǔ)需要通過(guò)新的計(jì)算模型—霧計(jì)算來(lái)提高數(shù)據(jù)處理效率，而霧計(jì)算中最為核心的技術(shù)就是邊緣數(shù)據(jù)存儲(chǔ)緩沖置換技術(shù)。

1 邊緣數(shù)據(jù)存儲(chǔ)緩沖置換技術(shù)

1.1 緩沖置換技術(shù)概述

緩沖技術(shù)最初是被應(yīng)用于計(jì)算機(jī)內(nèi)部的，用于緩解CPU與輸入輸出設(shè)備之間的數(shù)據(jù)處理速度不匹配問(wèn)題的一項(xiàng)技術(shù)。其原理是通過(guò)某種調(diào)度算法預(yù)先計(jì)算出CPU可能要訪問(wèn)到的數(shù)據(jù)，并將其提前從輸入設(shè)備調(diào)度到可快速讀寫的數(shù)據(jù)存儲(chǔ)區(qū)中，當(dāng)CPU訪問(wèn)到這類數(shù)據(jù)時(shí)，就可以從高速數(shù)據(jù)緩存區(qū)中快速讀取到；當(dāng)CPU需要輸出數(shù)據(jù)時(shí)，也可以將數(shù)據(jù)預(yù)先寫入到數(shù)據(jù)緩沖區(qū)中，再由輸出設(shè)備依次輸出，CPU在這個(gè)過(guò)程中不必被輸出設(shè)備一直占用，可同時(shí)并行處理其他內(nèi)部任務(wù)。

將緩沖技術(shù)應(yīng)用到霧計(jì)算的邊緣數(shù)據(jù)處理中，就是要通過(guò)合理的調(diào)度算法將移動(dòng)終端用戶可能將要訪問(wèn)到數(shù)據(jù)預(yù)先存儲(chǔ)到“霧”的邊緣存儲(chǔ)節(jié)點(diǎn)上，當(dāng)用戶訪問(wèn)該數(shù)據(jù)時(shí)，可以快速通過(guò)邊緣節(jié)點(diǎn)獲取到數(shù)據(jù)。如此既能夠提高用戶響應(yīng)速度，又能降低數(shù)據(jù)在云端傳輸所占用的內(nèi)部帶寬，減少云端中心服務(wù)器的運(yùn)算負(fù)載。

可是由于霧計(jì)算中的高速緩存節(jié)點(diǎn)存儲(chǔ)容量是極其有限的，因此不可能一次性將運(yùn)算得出的所有結(jié)果數(shù)據(jù)都調(diào)度存儲(chǔ)起來(lái)，還需要有合理的置換算法將可能被最近訪問(wèn)到的數(shù)據(jù)與不太可能馬上將被訪問(wèn)到的數(shù)據(jù)進(jìn)行置換。置換算法是否合理，其中一個(gè)最重要的衡量指標(biāo)就是數(shù)據(jù)命中率。

1.2 緩沖置換算法

常用的緩沖置換算法主要有先進(jìn)先出堆棧式算法、近期最少訪問(wèn)算法、蜂群算法、蟻群算法等。其中前兩者屬于傳統(tǒng)置換算法，思路簡(jiǎn)單，易于實(shí)現(xiàn)。

顧名思義，先進(jìn)先出就是將緩存時(shí)間最長(zhǎng)的數(shù)據(jù)先置換出去，是最基礎(chǔ)的一種調(diào)度算法；而近期最少訪問(wèn)算法更優(yōu)化一些，在先進(jìn)先出思路上，又綜合考慮了數(shù)據(jù)的訪問(wèn)頻率因素，將近期一段時(shí)間內(nèi)最少被訪問(wèn)到的數(shù)據(jù)置換出緩沖存儲(chǔ)區(qū)。

隨著數(shù)據(jù)處理需求的日益復(fù)雜化，這些傳統(tǒng)的調(diào)度算法已經(jīng)很難滿足海量數(shù)據(jù)的訪問(wèn)需求，因此逐漸出現(xiàn)了更加優(yōu)化、也更加復(fù)雜的一類算法。例如蜂群算法和蟻群算法，這類算法主要是通過(guò)對(duì)蜂群和蟻群的各種行為分析所推演出的優(yōu)化算法，在智能集群調(diào)度、多變量函數(shù)優(yōu)化計(jì)算、分布式組合優(yōu)化計(jì)算等方面都得到了廣泛的應(yīng)用。以蟻群算法為例，從螞蟻尋食的行為中推演得出的最優(yōu)路徑算法，其思路就取決于螞蟻在尋食過(guò)程中，會(huì)不斷選擇若干節(jié)點(diǎn)釋放激素，為后來(lái)經(jīng)過(guò)的螞蟻提供一個(gè)路徑判斷的條件，后來(lái)的螞蟻再做出判斷的同時(shí)會(huì)在當(dāng)前節(jié)點(diǎn)上再次釋放激素。反映到群體行為結(jié)果中，就會(huì)發(fā)現(xiàn)某些路徑節(jié)點(diǎn)上的激素氣味越大，哪條路徑被選擇的概率就越大。應(yīng)用到算法設(shè)計(jì)當(dāng)中，就可以根據(jù)對(duì)網(wǎng)絡(luò)路徑的節(jié)點(diǎn)上的信息量判斷繪制出最優(yōu)的傳輸路徑。再將其應(yīng)用到霧計(jì)算的邊緣數(shù)據(jù)調(diào)度中，就可以通過(guò)判斷某些數(shù)據(jù)上的調(diào)度頻率，來(lái)動(dòng)態(tài)實(shí)現(xiàn)優(yōu)化置換。

類似蟻群算法的這類復(fù)雜算法，最大的特點(diǎn)就是支持分布式的并發(fā)執(zhí)行運(yùn)算。每個(gè)螞蟻都可以看作是一個(gè)獨(dú)立的數(shù)據(jù)運(yùn)算任務(wù)，彼此之間的交互主要通過(guò)負(fù)載在數(shù)據(jù)之上的信息元素量。在分布式運(yùn)算空間，每個(gè)運(yùn)算任務(wù)都可以獨(dú)立解決一個(gè)問(wèn)題，再通過(guò)信息素的交互實(shí)現(xiàn)復(fù)雜組合優(yōu)化計(jì)算，增加了算法的可靠性和全局運(yùn)算能力。

2 邊緣數(shù)據(jù)存儲(chǔ)的緩沖優(yōu)化策略

2.1 邊緣數(shù)據(jù)存儲(chǔ)的緩沖置換效能評(píng)價(jià)指標(biāo)

為了能夠客觀衡量和判斷霧計(jì)算中數(shù)據(jù)緩存存儲(chǔ)算法的效率如何，設(shè)定合理的數(shù)據(jù)存儲(chǔ)效能評(píng)價(jià)指標(biāo)體系是非常必要的。在這個(gè)體系中最為核心的評(píng)價(jià)指標(biāo)主要有兩個(gè)，一個(gè)是前面就提到過(guò)的被訪問(wèn)數(shù)據(jù)對(duì)象的命中率，另一個(gè)是用戶從提出請(qǐng)求到數(shù)據(jù)節(jié)點(diǎn)響應(yīng)的平均時(shí)間間隔長(zhǎng)短，也就是平均時(shí)延。第一個(gè)指標(biāo)主要反映了預(yù)先緩沖置換到的霧計(jì)算節(jié)點(diǎn)中的數(shù)據(jù)對(duì)象能夠被用戶訪問(wèn)到命中率有多高，命中率越高，就說(shuō)明預(yù)先緩存的數(shù)據(jù)對(duì)象越符合用戶的訪問(wèn)需求；第二個(gè)指標(biāo)用于計(jì)算通常情況下，用戶從發(fā)出請(qǐng)求到獲取數(shù)據(jù)需要等待的時(shí)間長(zhǎng)短，平均時(shí)延的值越小，就說(shuō)明數(shù)據(jù)響應(yīng)越快，這可以表明數(shù)據(jù)是被緩存在霧計(jì)算節(jié)點(diǎn)中，還是存儲(chǔ)在云端。

2.2 邊緣數(shù)據(jù)存儲(chǔ)的緩沖置換算法改進(jìn)

傳統(tǒng)的蟻群算法通常是應(yīng)用在路徑的選擇問(wèn)題中，通過(guò)將螞蟻信息素釋放到各個(gè)路徑節(jié)點(diǎn)上，通過(guò)遍歷進(jìn)行路徑的判斷。在霧計(jì)算的邊緣數(shù)據(jù)緩存置換技術(shù)中蟻群算法是要實(shí)現(xiàn)最優(yōu)的數(shù)據(jù)對(duì)象選擇和置換，通過(guò)對(duì)數(shù)據(jù)對(duì)象上承載的信息量多少與占用存儲(chǔ)空間大小兩個(gè)因素的綜合判斷來(lái)得出結(jié)果，因此信息素是加載在被選擇的數(shù)據(jù)對(duì)象上的。在遍歷數(shù)據(jù)對(duì)象的螞蟻總數(shù)給定的情況下，固定時(shí)間間隔內(nèi)單個(gè)數(shù)據(jù)對(duì)象上螞蟻所釋放信息量越大，表示該數(shù)據(jù)對(duì)象被選擇的重要程度也就越大；同時(shí)該數(shù)據(jù)對(duì)象所占用的存儲(chǔ)空間越小，其被螞蟻選擇的期望程度也就越高。通過(guò)對(duì)這兩個(gè)因素的運(yùn)算比對(duì)，即可得出最佳的選擇結(jié)果。

由于移動(dòng)端用戶的位置不確定性，每個(gè)數(shù)據(jù)對(duì)象被訪問(wèn)請(qǐng)求的到達(dá)時(shí)間隨機(jī)性非常大，很難保持同步，這就使得數(shù)據(jù)對(duì)象的置換時(shí)間也是隨時(shí)在發(fā)生變化的。為了不影響緩存空間的充分利用，置換算法還增加了定期對(duì)數(shù)據(jù)對(duì)象所承載的信息素進(jìn)行更新的運(yùn)算操作。運(yùn)算思路主要是依據(jù)訪問(wèn)量減少的數(shù)據(jù)對(duì)象上的信息素會(huì)逐漸減少規(guī)律。首先定期更新時(shí)，只會(huì)對(duì)這段時(shí)間間隔內(nèi)被訪問(wèn)到數(shù)據(jù)對(duì)象上的信息素，這段時(shí)間沒(méi)有被選擇到的數(shù)據(jù)對(duì)象上的信息素就會(huì)自然減少，最后就會(huì)被選中置換出邊緣數(shù)據(jù)緩存區(qū)。

2.3 邊緣數(shù)據(jù)存儲(chǔ)的緩沖置換優(yōu)化策略的實(shí)現(xiàn)

霧計(jì)算的邊緣節(jié)點(diǎn)接收到數(shù)據(jù)請(qǐng)求后，首先要查詢節(jié)點(diǎn)上的數(shù)據(jù)緩存列表，如列表中包含被請(qǐng)求的數(shù)據(jù)對(duì)象，則在該對(duì)象的請(qǐng)求次數(shù)的記錄上累加一次，并將數(shù)據(jù)響應(yīng)給請(qǐng)求用戶；如列表中沒(méi)有包含被請(qǐng)求的對(duì)象，則向云計(jì)算中心請(qǐng)求獲取數(shù)據(jù)對(duì)象，并通過(guò)置換算法將數(shù)據(jù)對(duì)象存儲(chǔ)至邊緣節(jié)點(diǎn)。

將數(shù)據(jù)對(duì)象置換存儲(chǔ)至邊緣節(jié)點(diǎn)時(shí)，首先要計(jì)算當(dāng)前節(jié)點(diǎn)的空余空間能否滿足數(shù)據(jù)的存儲(chǔ)需求。如能滿足，則不需進(jìn)行置換，直接建立存儲(chǔ)記錄即可；如不能滿足，則需調(diào)用置換算法，對(duì)計(jì)算參數(shù)進(jìn)行初始化，更新數(shù)據(jù)緩存列表與數(shù)據(jù)對(duì)象的信息素記錄。

數(shù)據(jù)置換初始化工作完成之后，遍歷數(shù)據(jù)緩存列表中的所有數(shù)據(jù)對(duì)象，先對(duì)數(shù)據(jù)對(duì)象的信息素進(jìn)行比對(duì)分析，選擇出被選擇概率較大的數(shù)據(jù)對(duì)象，再將其所占的存儲(chǔ)空間的大小與要置換入緩存區(qū)的數(shù)據(jù)對(duì)象容量大小進(jìn)行比對(duì)分析，選擇存儲(chǔ)容量相當(dāng)?shù)臄?shù)據(jù)對(duì)象與其置換。

置換工作完成之后，對(duì)存儲(chǔ)在邊緣節(jié)點(diǎn)的新的數(shù)據(jù)對(duì)象進(jìn)行初始化，并為其創(chuàng)建相應(yīng)的信息記錄，用于記錄該數(shù)據(jù)對(duì)象的被訪問(wèn)次數(shù)與初始時(shí)間。

3 結(jié)論

本文針對(duì)云計(jì)算在移動(dòng)端實(shí)時(shí)數(shù)據(jù)處理性能不足等問(wèn)題，在霧計(jì)算中邊緣數(shù)據(jù)存儲(chǔ)的優(yōu)化思路與策略上進(jìn)行了深入研究。其中主要涉及到的核心技術(shù)—數(shù)據(jù)緩存置換技術(shù)，主要是為了緩解用戶數(shù)據(jù)需求與霧計(jì)算邊緣節(jié)點(diǎn)存儲(chǔ)容量不匹配的問(wèn)題，本文重點(diǎn)就此問(wèn)題提出了基于蟻群置換算法的改進(jìn)思路和優(yōu)化策略，以期為之后的相關(guān)技術(shù)完善和發(fā)展提供一定的研究參考價(jià)值。

[1] Li P,Xu Q, Wang N.Evolution Course and Analysis of Things[J].2014(219):132-137.

[2] 張德孚.霧計(jì)算中的數(shù)據(jù)邊緣存儲(chǔ)優(yōu)化技術(shù)研究[D].杭州：浙江工商大學(xué).2016.

Research on Cache Replacement Technology Based on Fog Computing Edge Data Storage

Guan Lihua

(ShanxiEconomicandTradeVocationalCollege,TaiyuanShanxi030024，China)

In this paper, the related concepts, implementation principles and the main algorithms involved in fog computing are discussed. Based on this, some new ideas and methods are put forward for the optimization and improvement of ant colony algorithm in the edge data cache replacement technology in order to provide some reference for the research in related fields.

fog computing；edge data； cache replacement；ant colony algorithm

2017-07-16

關(guān)麗華(1973- ),女，山西清徐人，本科，研究方向：計(jì)算機(jī)應(yīng)用。

1674- 4578(2017)04- 0090- 02

TP333；TP311.13

A