關麗華

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

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

關麗華

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

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

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

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

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

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

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

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

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

1.2 緩沖置換算法

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

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

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

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

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

2.1 邊緣數(shù)據(jù)存儲的緩沖置換效能評價指標

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

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

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

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

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

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

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

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

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

3 結(jié)論

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

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

[2] 張德孚.霧計算中的數(shù)據(jù)邊緣存儲優(yōu)化技術(shù)研究[D].杭州：浙江工商大學.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

關麗華(1973- ),女，山西清徐人，本科，研究方向：計算機應用。

1674- 4578(2017)04- 0090- 02

TP333；TP311.13

A