一種面向工業(yè)邊緣計算應(yīng)用的緩存替換算法

張 雷 李 琳 陳鴻龍 Daniel Bovensiepen

1(南京郵電大學(xué)物聯(lián)網(wǎng)學(xué)院 南京 210009)

2(中國石油大學(xué)(華東)控制科學(xué)與工程學(xué)院 山東青島 266580)

3(西門子中國研究院 北京 100102)

隨著物聯(lián)網(wǎng)技術(shù)的快速發(fā)展，越來越多的具有計算能力的智能傳感器和執(zhí)行器被應(yīng)用在工業(yè)自動化系統(tǒng)中，產(chǎn)生了海量的物聯(lián)網(wǎng)數(shù)據(jù)[1].這些數(shù)據(jù)可以用于改進控制工藝，優(yōu)化生產(chǎn)流程，進而提高生產(chǎn)效率.例如傳統(tǒng)工廠中控制策略通常通過離線下載到可編程邏輯控制器(programmable logic controller, PLC)，在封閉的控制網(wǎng)絡(luò)中運行，很難做到靈活更新.現(xiàn)在新型的PLC支持配備AI模塊，使得利用機器學(xué)習(xí)等算法實現(xiàn)生產(chǎn)任務(wù)的柔性自組織成為可能[2-3].

機器學(xué)習(xí)算法的樣本數(shù)據(jù)來自于傳感器、控制器和執(zhí)行器等現(xiàn)場設(shè)備在歷史生產(chǎn)過程中產(chǎn)生的控制和狀態(tài)參數(shù).工廠底層現(xiàn)場的設(shè)備數(shù)量眾多，加上單個設(shè)備產(chǎn)生的數(shù)據(jù)幀很短，但是由于生成周期小，因此每天產(chǎn)生的數(shù)據(jù)規(guī)模巨大.這些海量數(shù)據(jù)存儲在云服務(wù)器，如果采用基于云的數(shù)據(jù)服務(wù)，數(shù)據(jù)傳輸?shù)难舆t將會非常大[4].而工業(yè)應(yīng)用通常對數(shù)據(jù)傳輸?shù)臅r延往往有嚴格要求，因此，將邊緣計算應(yīng)用于工業(yè)物聯(lián)網(wǎng)有很大的優(yōu)勢[5].邊緣計算在靠近用戶的邊緣部署服務(wù)器設(shè)備，利用其自身的存儲和計算資源，對用戶請求提供低延遲的數(shù)據(jù)傳輸服務(wù)，為實時性任務(wù)處理提供保障.

但是，邊緣節(jié)點的存儲容量通常非常有限，在邊緣節(jié)點緩存所有內(nèi)容是不可能的.因此，通過合理的緩存策略確定緩存內(nèi)容集，最大化緩存利用率，減少向云服務(wù)器請求內(nèi)容次數(shù)，對于邊緣網(wǎng)絡(luò)的服務(wù)性能保障至關(guān)重要.

盡管已經(jīng)有很多邊緣緩存的研究工作，據(jù)我們所知，目前還沒有針對工業(yè)邊緣計算應(yīng)用的緩存策略.本文的主要貢獻有2個方面：

1) 在分析典型工業(yè)應(yīng)用場景的基礎(chǔ)上，建立工業(yè)邊緣網(wǎng)絡(luò)模型.基于散粒噪聲模型(shot noise model, SNM)對工業(yè)用戶請求進行建模，進而建立用戶請求的流行度變化模型；

2) 提出一種新的緩存替換算法，綜合考慮時效性、內(nèi)容大小優(yōu)先性和流行度預(yù)測確定內(nèi)容價值.通過與5種經(jīng)典緩存算法的對比實驗驗證了所提出算法的有效性.

1 相關(guān)工作

一個邊緣緩存策略是否成功主要取決于它對緩存內(nèi)容價值估計的準確性.內(nèi)容流行度是做出緩存決策的有效措施.經(jīng)典的最近最久未使用(least recently used, LRU)算法[6]將用戶訪問時間作為流行度指標，離當前時刻最近的訪問內(nèi)容流行度最高，容易受到一些偶然訪問內(nèi)容的干擾.最近最少訪問頻次(least frequently used, LFU)算法[7]將不同內(nèi)容的訪問頻次作為流行度指標，訪問次數(shù)最多的內(nèi)容流行度最高，容易導(dǎo)致緩存污染問題.Size算法[8]將內(nèi)容大小作為流行度指標，最小內(nèi)容流行度最高，可能會引起頻繁請求流行度高的大內(nèi)容，造成帶寬的浪費.針對單個特征指標存在的問題，很多研究提出基于訪問時間、訪問頻率、內(nèi)容大小等多個特征的混合緩存策略，以提高流行度評估的準確性，代表性工作如貪婪雙尺寸(greedy dual size, GDS)算法[9].

這些傳統(tǒng)的緩存算法易于實現(xiàn)、算法復(fù)雜度低，已經(jīng)取得廣泛應(yīng)用.然而隨著因特網(wǎng)數(shù)據(jù)的爆發(fā)式增長，邊緣計算、內(nèi)容中心網(wǎng)絡(luò)和5G網(wǎng)絡(luò)等新型網(wǎng)絡(luò)的出現(xiàn)對緩存策略提出了更高的要求，因此近年來的研究工作主要面向新型網(wǎng)絡(luò)場景提出相應(yīng)的緩存優(yōu)化算法.

根據(jù)緩存內(nèi)容集合與用戶請求內(nèi)容集合的關(guān)系，這些緩存策略可分為2類：1)假設(shè)網(wǎng)絡(luò)節(jié)點緩存所有用戶請求的內(nèi)容，此類緩存研究將主要關(guān)注點放在請求內(nèi)容如何在不同節(jié)點上進行緩存部署.一般做法是基于成本、延遲等網(wǎng)絡(luò)性能指標將緩存部署問題轉(zhuǎn)化線性優(yōu)化問題[10-11]，接著通過進化算法或啟發(fā)式算法找到優(yōu)化的全局緩存部署方案.這類策略需要收集全局網(wǎng)絡(luò)信息，求解開銷昂貴.因此文獻[12-13]利用節(jié)點間合作關(guān)系，提出分布式緩存策略，得到節(jié)點的最佳緩存內(nèi)容集.2)緩存研究假設(shè)緩存容量有限，網(wǎng)絡(luò)節(jié)點只緩存部分內(nèi)容.經(jīng)典的基于流行度的緩存算法MPC(most-popular content)[14]認為緩存熱點內(nèi)容相比緩存不是熱點的內(nèi)容所帶來的緩存效益更高，因此通過流行度表記錄每個內(nèi)容的流行度值，只有足夠流行的內(nèi)容才可能請求緩存.文獻[15]綜合比較了MPC及其改進算法的性能，并面向命名數(shù)據(jù)網(wǎng)絡(luò)提出改進算法.Sun等人[16]針對D2D網(wǎng)絡(luò)提出一種基于移動感知的MPC改進算法.Deng等人[17]針對車聯(lián)網(wǎng)中車輛的需求和偏好，以及收發(fā)節(jié)點的相對位置，提出分布式概率緩存策略.

目前大多數(shù)緩存策略研究都采用了靜態(tài)的內(nèi)容流行度模型，通常假設(shè)服從Zipf分布.但是靜態(tài)模型忽略了真實場景下用戶對不同內(nèi)容的請求偏好隨時間變化的動態(tài)性.當內(nèi)容請求發(fā)生變化，緩存算法會出現(xiàn)性能退化.因此，最近的研究已經(jīng)轉(zhuǎn)向分析和預(yù)測流行度的動態(tài)變化，并設(shè)計動態(tài)緩存策略.這些緩存策略主要從內(nèi)容本身特征或用戶請求特征刻畫流行度模型.

一部分研究者通過分析視頻、社交內(nèi)容的更多相關(guān)特征，用于流行度預(yù)測.有數(shù)據(jù)表明，視頻流量數(shù)據(jù)已經(jīng)成為互聯(lián)網(wǎng)的主要流量[18].Zhang等人[19]將視頻文件序列化為具有名稱前綴和順序索引的塊，通過分析用戶的請求行為發(fā)現(xiàn)視頻塊之間的關(guān)聯(lián)特征從而預(yù)測未來視頻塊的流行度.朱琛剛等人[20]分析了電視節(jié)目與上線日期、播出時間和節(jié)目類型等特征的關(guān)聯(lián)性，從中提取影響節(jié)目流行度的關(guān)鍵特征構(gòu)建節(jié)目流行度隨時間變化的模型，使用隨機森林算法構(gòu)建電視節(jié)目流行度預(yù)測模型，并提出了一種節(jié)目緩存調(diào)度算法.社交流量數(shù)據(jù)是另外一類活躍因特網(wǎng)流量，可利用社交媒體的傳播特性進行內(nèi)容流行度分析.朱海龍等人[21]基于傳播加速度和用戶活躍性提出微博消息的在線流行度預(yù)測方法.Li等人[22]提出面向社交網(wǎng)絡(luò)的popCaching緩存策略，算法沒有預(yù)測每個內(nèi)容單獨的流行度，而是假設(shè)上下文特征相似時內(nèi)容流行度相似，采用4段歷史訪問量作為當前上下文特征.

另一部分研究者挖掘新型網(wǎng)絡(luò)場景下的用戶偏好和請求特性用于動態(tài)流行度預(yù)測.如無線網(wǎng)絡(luò)區(qū)別于有線網(wǎng)絡(luò)一個重要特征是用戶的移動性，不同用戶移動時體現(xiàn)為不同的時空特征.因此很多研究者面向移動邊緣計算應(yīng)用，結(jié)合實際場景下用戶的時空移動特性，為邊緣節(jié)點提出流行度預(yù)測算法和緩存策略.如Yang等人[23]和Yan等人[24]利用邊緣節(jié)點的位置特征代表該位置的用戶偏好，并提出在線預(yù)測算法，提高內(nèi)容命中率.Gao等人[25]通過基站感知用戶的移動模式，以此來計算本地內(nèi)容的流行度，并將不同移動速度用戶請求的文件分別緩存在不同的基站.Li等人[26]針對移動網(wǎng)絡(luò)用戶的移動歷史數(shù)據(jù)，建立Markov模型預(yù)測用戶在移動和請求方面的行為，根據(jù)計算的內(nèi)容流行度進行預(yù)緩存.Bharath等人[27]針對時變且未知的內(nèi)容流行度，分別以Bernoulli模型和Poisson模型作為內(nèi)容請求模型，面向異構(gòu)無線網(wǎng)絡(luò)的小基站節(jié)點，提出根據(jù)預(yù)估的內(nèi)容流行度和最優(yōu)值的誤差決定緩存更新，仿真結(jié)果表明比定期的緩存更新性能更優(yōu).

可以發(fā)現(xiàn)，對于基于流行度動態(tài)變化的緩存策略研究方法主要面向在線音視頻、社交網(wǎng)絡(luò)等互聯(lián)網(wǎng)內(nèi)容，在某個具體網(wǎng)絡(luò)情境下引入更多的分析特征提高流行度預(yù)測準確性，進而提高緩存命中率.而工業(yè)應(yīng)用與在線音視頻、社交網(wǎng)絡(luò)等互聯(lián)網(wǎng)應(yīng)用有著截然不同的流量和用戶請求特征.音視頻數(shù)據(jù)流具有數(shù)據(jù)幀長、流量大、占用帶寬高的特點，而工業(yè)生產(chǎn)過程生成的數(shù)據(jù)量巨大，數(shù)據(jù)幀短且時效性高.互聯(lián)網(wǎng)中的內(nèi)容有可能被任意一個用戶請求，而工業(yè)邊緣緩存節(jié)點往往服務(wù)于特定的工業(yè)控制設(shè)備，設(shè)備的內(nèi)容請求與生產(chǎn)任務(wù)相關(guān)，沒有復(fù)雜的社會關(guān)系交互的干擾，不會發(fā)生內(nèi)容在大部分設(shè)備上廣泛傳播.因此，已有的緩存算法很難直接應(yīng)用于工業(yè)應(yīng)用場景下的邊緣緩存.

2 系統(tǒng)模型

本節(jié)面向典型的工廠應(yīng)用需求建立網(wǎng)絡(luò)模型和緩存問題模型.

2.1 網(wǎng)絡(luò)模型

一個典型工業(yè)應(yīng)用場景中的邊緣網(wǎng)絡(luò)體系結(jié)構(gòu)如圖1所示.最上層為云服務(wù)器中心.中間層為邊緣節(jié)點層，每個邊緣節(jié)點都有有限大小的緩存資源.底層為現(xiàn)場智能設(shè)備，如智能傳感器、PLC、工控機、工程師站等.

Fig. 1 A typical industrial edge network structure圖1 一個典型的工業(yè)邊緣網(wǎng)絡(luò)結(jié)構(gòu)

假設(shè)底層傳感器、控制器和執(zhí)行器等現(xiàn)場設(shè)備產(chǎn)生的歷史生產(chǎn)控制和狀態(tài)參數(shù)等內(nèi)容集合記為Ω.現(xiàn)場設(shè)備進行學(xué)習(xí)任務(wù)時將請求其中部分內(nèi)容集合M，大小為|M|，每塊內(nèi)容m的大小為Sm.為了減小數(shù)據(jù)傳輸延遲，N個邊緣節(jié)點將提供緩存服務(wù)，每個邊緣節(jié)點n緩存容量為L(單位為MB).

2.2 問題模型

假設(shè)工業(yè)用戶總共發(fā)出了K次內(nèi)容請求，Cmk表示第k次請求的內(nèi)容是否為第m個內(nèi)容，是則Cmk=1，否則Cmk=0.Ank表示請求內(nèi)容是否被緩存到邊緣節(jié)點n，是則Ank=1，否則Ank=0.緩存命中率表示為

(1)

邊緣網(wǎng)絡(luò)中的數(shù)據(jù)傳輸延遲由2部分組成，如用戶請求內(nèi)容被緩存，延遲為內(nèi)容從邊緣節(jié)點傳輸?shù)接脩舻臅r間，即延遲為緩存讀取時間d.如用戶請求的內(nèi)容沒有在緩存中時，邊緣緩存設(shè)備需要向工廠私有云請求緩存該內(nèi)容，數(shù)據(jù)的傳輸會受到回傳鏈路容量的限制，令B表示工廠云服務(wù)器向邊緣緩存節(jié)點的傳輸鏈路帶寬，γ表示該鏈路的傳輸因子，即網(wǎng)絡(luò)不穩(wěn)定或擁塞時引起的延遲.則平均傳輸延遲D可以表示為

(2)

本文的優(yōu)化目標是最大化邊緣節(jié)點的緩存命中率，最小化用戶請求內(nèi)容的傳輸延遲，優(yōu)先保障控制數(shù)據(jù).優(yōu)化問題可以表述為

maxH，

(3)

minD.

(4)

3 用戶請求流行度預(yù)測

本節(jié)首先結(jié)合工業(yè)應(yīng)用中用戶請求特點，建立用戶請求模型，然后梳理了工業(yè)用戶請求內(nèi)容的特征屬性，并給出用戶請求流行度變化的預(yù)測方法.

3.1 用戶請求模型

目前用戶請求模型使用比較廣泛的是獨立參考模型(independent reference model, IRM)[28].IRM模型作為一種靜態(tài)模型，假設(shè)內(nèi)容請求的流行度不隨時間改變，用戶請求遵循Zipf分布.該模型簡化了緩存問題復(fù)雜度，但是無法反映內(nèi)容流行度的時間局部性特征.而工業(yè)應(yīng)用中，設(shè)備請求的內(nèi)容隨著生產(chǎn)任務(wù)的變化而變化，請求內(nèi)容的生命周期與生產(chǎn)節(jié)拍密切相關(guān)，因此IRM模型不適用于工業(yè)場景.本文采用Traverso等人[29]提出的SNM作為用戶請求模型.與IRM模型相比，SNM模型描述了內(nèi)容請求的過程，可以更好地表現(xiàn)不同內(nèi)容熱度隨時間變化的動態(tài)趨勢.

SNM模型下，內(nèi)容請求產(chǎn)生過程被假定為Poisson過程，對每個內(nèi)容的請求過程是獨立的齊次Poisson過程.整個請求過程表示為許多獨立過程的疊加，每個內(nèi)容的請求過程對應(yīng)一個獨立過程.具體地，對于內(nèi)容m，將時間u處的請求到達率表示為

Ym(u)=Vmλm(u-τm)，

(5)

其中，m代表內(nèi)容m進入系統(tǒng)的時間點，λm(u)代表對內(nèi)容m的請求到達率隨時間u變化的規(guī)律，即“流行度輪廓”.文獻[30]提到常用的3種流行度輪廓為指數(shù)輪廓、均勻輪廓和隨機輪廓.為簡化應(yīng)用，本文采用均勻流行度輪廓，即內(nèi)容m遵循在生命周期T內(nèi)，平均到達率為λ的齊次Poisson過程.在整個評估時間E期間所請求的內(nèi)容的平均數(shù)量為λE.Vm表示內(nèi)容m在活躍時間內(nèi)被請求的總次數(shù).通過以上特征來描述內(nèi)容m隨時間變化的請求過程.

Fig. 2 Examples of requests generated by two different contents圖2 不同的2個內(nèi)容生成的請求示例

3.2 用戶請求的流行度變化預(yù)測

工業(yè)應(yīng)用中設(shè)備請求的動態(tài)性與當前進行的生產(chǎn)任務(wù)更新調(diào)整具有高度的相關(guān)性.工廠一天內(nèi)可能有多個不同生產(chǎn)優(yōu)化任務(wù)發(fā)生.以生產(chǎn)的自組織調(diào)度為例，生產(chǎn)線可能包含多個不同種類的設(shè)備，控制器請求的內(nèi)容盡管來源于同生產(chǎn)線的不同設(shè)備，但是都具有相同的位置屬性.又例如控制器基于機器學(xué)習(xí)算法優(yōu)化設(shè)備故障預(yù)測策略，需要請求設(shè)備對象自帶的相關(guān)傳感器歷史數(shù)據(jù)、歷史診斷數(shù)據(jù)以及類似設(shè)備的歷史數(shù)據(jù).這些請求的內(nèi)容都來自同類型的對象設(shè)備.通過這2個實際應(yīng)用案例對比，可以發(fā)現(xiàn)：不同任務(wù)發(fā)生時，控制器運行學(xué)習(xí)算法需要請求的內(nèi)容完全不同.但是每個設(shè)備請求的內(nèi)容有一定的共性特征，這些特征反映了當前進行的不同生產(chǎn)任務(wù).

為了總結(jié)其特點，我們定義來自工業(yè)現(xiàn)場的內(nèi)容的多維特征屬性：時間屬性、位置屬性、來源設(shè)備屬性、對象設(shè)備屬性等.時間屬性為數(shù)據(jù)采集的發(fā)生時間；位置屬性為數(shù)據(jù)采集的發(fā)生地點；來源設(shè)備屬性為數(shù)據(jù)源；對象設(shè)備屬性為數(shù)據(jù)的監(jiān)測對象.對于任意的內(nèi)容m，都有W個特征屬性，用集合{fm1,fm2,…,fmW}表示.

由于內(nèi)容只在有限生命周期內(nèi)活躍，流行度分析只統(tǒng)計最近的時間窗口的請求內(nèi)容的特征屬性變化.假設(shè)T為周期時間窗口大小，F(xiàn)(t)為第t個時間窗口內(nèi)所有請求內(nèi)容的特征集合.利用Jaccard相似度系數(shù)定義第t個和第t-1個時間窗口內(nèi)請求內(nèi)容集合的相似性函數(shù)為

(6)

在第t個時間窗口內(nèi)，當相似度系數(shù)Sim(t)值大于閾值θ時，認為前后2個時間窗內(nèi)進行的生產(chǎn)優(yōu)化任務(wù)沒有發(fā)生變化.當相似度系數(shù)值小于閾值θ時，認為當前活躍的生產(chǎn)優(yōu)化任務(wù)已經(jīng)發(fā)生變化.

在實驗過程中發(fā)現(xiàn)，生產(chǎn)優(yōu)化任務(wù)變化時，往往會有一個主導(dǎo)內(nèi)容屬性特征隨之發(fā)生變化.因此本文沒有統(tǒng)計所有特征屬性，而是利用最近周期窗口內(nèi)的出現(xiàn)次數(shù)最多的熱點特征屬性來表征當下實時進行的任務(wù).這種單一特征屬性指征的優(yōu)勢在于簡化了計算，降低緩存算法復(fù)雜度.定義Mo(F(t))為熱點特征屬性，F(xiàn)(t)集合中Mo(F(t))的元素序數(shù)為w*，即fw*(t)=Mo(F(t)) ，則相似度函數(shù)的計算可簡化為

(7)

4 PPPS緩存算法

基于3.2小節(jié)對用戶請求的流行度變化預(yù)測方法，提出基于屬性特征流行度預(yù)測的緩存算法(combing periodic popularity prediction and size caching strategy, PPPS).PPPS算法一方面考慮流行度和內(nèi)容尺寸的影響，為每個內(nèi)容設(shè)置緩存內(nèi)容價值；一方面，將熱度較高的特征屬性內(nèi)容提前存儲到邊緣緩存的空閑空間，提升邊緣緩存的命中率，提高緩存利用效率.

PPPS算法為每個內(nèi)容定義了緩存價值Q，通過緩存價值函數(shù)作為緩存替換的依據(jù).緩存價值函數(shù)首先考慮時間局部性的影響，設(shè)置緩存更新時間.其次根據(jù)最近的歷史請求內(nèi)容，預(yù)測各緩存內(nèi)容流行度概率.再則，在工業(yè)應(yīng)用下，控制和狀態(tài)信息內(nèi)容的尺寸小、頻率高，音視頻內(nèi)容大但出現(xiàn)頻率小，將尺寸納入價值函數(shù)的意義在于優(yōu)先保障緩存那些具有更重要的文件.對于任意內(nèi)容m，得到其價值函數(shù)Qm：

(8)

該函數(shù)值的大小與緩存內(nèi)容被替換的概率呈負相關(guān).其中，pm(t)表示單個內(nèi)容m在第t個時間窗內(nèi)的流行度概率.第t個時間窗口內(nèi)用戶請求內(nèi)容的熱點屬性特征集合為{fxw*,f(x+1)w*,…,f(x+T)w*}，內(nèi)容m的流行度概率可表征為其特征屬性在第t個時間窗口的發(fā)生概率為

(9)

算法實現(xiàn)流程為：每次當新的用戶請求內(nèi)容到達，判斷緩存中是否已經(jīng)存在當前請求的內(nèi)容.若命中，則更新該內(nèi)容的價值；若未命中，則判斷緩存剩余空間是否足以存儲該內(nèi)容，是則直接存入緩存隊列，否則替換掉緩存價值最小的內(nèi)容，直到空間大小足夠容納新內(nèi)容.然后判斷累計用戶請求次數(shù)是否到達T，是則更新t值，t=t+1.同時計算t和t-1周期時間窗口請求內(nèi)容的相似度系數(shù)Sim(t)，當其小于閾值θ時，則刪除緩存隊列里非熱點特征屬性內(nèi)容，并隨機選擇熱點特征屬性的內(nèi)容放入緩存，但緩存內(nèi)容價值Q=0.PPPS算法實現(xiàn)的偽代碼如算法1所示：

算法1.PPPS算法.

輸出：緩存命中率H.

① 初始化j=0，t=0；

② fork=1,2,…,Kdo

③ 用戶請求內(nèi)容m；

④ if內(nèi)容m已被緩存

⑤j++；

⑦ else

⑧ while(緩存空閑大小

⑨ 刪除最小價值Qmin的內(nèi)容；

⑩ end while

PPPS算法時間復(fù)雜度的計算可分為緩存更新和內(nèi)容流行度計算2部分，緩存更新流程與LRU算法類似，算法復(fù)雜度為O(1)；流行度的計算主要取決于熱點特征屬性w*的更新，可以歸結(jié)為F(t)集合的眾數(shù)求解問題，因此算法復(fù)雜度為O(TlogT).結(jié)合這2部分，PPPS算法時間復(fù)雜度為O(TlogT).

5 算法性能評估

本節(jié)首先介紹了實驗參數(shù)設(shè)置，然后通過3組實驗場景分析和比較算法性能.

5.1 實驗參數(shù)設(shè)置

算法的運行環(huán)境為Matlab R2016b，操作系統(tǒng)為Windows10，計算機處理器為Intel i7-8565U 8核，主頻為1.80 GHz，內(nèi)存為8 GB.

工業(yè)邊緣網(wǎng)絡(luò)采用圖1的網(wǎng)絡(luò)結(jié)構(gòu).最上層的云存儲了所有內(nèi)容.在網(wǎng)絡(luò)邊緣部署了邊緣節(jié)點，每個節(jié)點都有有限大小的緩存空間.每個緩存設(shè)備的容量在20～180 MB.從云服務(wù)器到邊緣節(jié)點的鏈路傳輸帶寬為100 MBps.緩存?zhèn)鬏旀溌返难舆t因子設(shè)為15 ms.

因為沒有工業(yè)環(huán)境下的真實數(shù)據(jù)，我們通過仿真產(chǎn)生內(nèi)容和用戶請求序列.云服務(wù)器存儲了M種內(nèi)容.產(chǎn)生的內(nèi)容大小是服從Zipf分布的隨機數(shù).基于SNM模型隨機產(chǎn)生內(nèi)容請求數(shù)據(jù).隨機生成各內(nèi)容的生命周期和各內(nèi)容活躍的起始時間，并根據(jù)起始時間來劃分內(nèi)容的位置屬性.

PPPS算法參數(shù)：閾值θ=0.1，時間窗口周期T=100.值得注意的是，時間窗口周期T設(shè)置與生產(chǎn)任務(wù)的更新頻率有關(guān).T值太小會導(dǎo)致緩存價值頻繁更新，影響算法性能.緩存性能的影響因素很多，如用戶請求序列、內(nèi)容大小分布、內(nèi)容種類、緩存容量等.通過3個實驗分別分析主要因素對算法性能的影響.

實驗1.對比了分別在IRM模型和SNM模型產(chǎn)生的數(shù)據(jù)流量下，各算法隨緩存容量的性能變化.該實驗旨在探究緩存算法分別在不同用戶請求模型產(chǎn)生的數(shù)據(jù)流量下的性能表現(xiàn).實驗參數(shù)設(shè)置為：內(nèi)容大小設(shè)置服從Zipf分布，參數(shù)α=0.7，范圍為1～5 MB，內(nèi)容種類M=200，總共請求次數(shù)為19 562次，緩存空間為20～180 MB.

實驗2.研究內(nèi)容大小相同時緩存算法的性能，并對比實驗1探究內(nèi)容尺寸對緩存算法的影響.實驗1的內(nèi)容尺寸是考慮工業(yè)網(wǎng)絡(luò)混合了控制數(shù)據(jù)、視頻數(shù)據(jù)、圖像數(shù)據(jù)等多種類型內(nèi)容.實驗2的內(nèi)容尺寸設(shè)置實際上也有現(xiàn)實的應(yīng)用背景.在很多傳統(tǒng)的工廠內(nèi)，工業(yè)網(wǎng)絡(luò)中的數(shù)據(jù)類型單一，現(xiàn)場設(shè)備產(chǎn)生很短的控制數(shù)據(jù)幀，經(jīng)過網(wǎng)關(guān)緩存上傳給云服務(wù)器，表現(xiàn)為單一的內(nèi)容尺寸.實驗參數(shù)設(shè)置為：所有內(nèi)容大小設(shè)為1 MB，內(nèi)容種類M=200，總共請求次數(shù)為19 562次，緩存空間為20～180 MB.

實驗3.固定緩存容量，主要研究內(nèi)容種類對緩存算法性能的影響.實驗參數(shù)設(shè)置為：固定緩存為300 MB，內(nèi)容種類M為100～500，各內(nèi)容種類分別對應(yīng)的請求次數(shù)為8 810，19 562，29 076，38 875，49 356，內(nèi)容大小隨機生成，服從Zipf分布，參數(shù)α=0.7，范圍為1～5 MB.

為了更好地分析和比較所提出的PPPS算法，本文實現(xiàn)了5種經(jīng)典的緩存策略FIFO，LRU，LFU，GDS，MPC算法作為對比算法.其中MPC算法本身并未考慮緩存容量有限的情況，因此許多研究工作在MPC算法實現(xiàn)時與LRU相結(jié)合，實現(xiàn)緩存內(nèi)容的替換[31].本文采用同樣的策略，MPC算法的流行度閾值設(shè)為3.采用緩存命中率和平均延遲作為算法的性能評估指標.

5.2 實驗結(jié)果分析

1) IRM模型和SNM模型的用戶請求影響分析用SNM模型和IRM模型分別產(chǎn)生用戶請求序列，假設(shè)請求時間總長為S，按時間順序分為4等份，圖3對比了2種模型下內(nèi)容請求過程中不同時間段的請求頻率.IRM模型產(chǎn)生的內(nèi)容序列遵循Zipf分布，內(nèi)容流行度始終不變.而SNM模型產(chǎn)生的內(nèi)容序列則更好地體現(xiàn)了內(nèi)容流行度在生命周期內(nèi)的動態(tài)變化.隨不同內(nèi)容熱度的逐漸上升，熱點內(nèi)容都在某一時間段內(nèi)出現(xiàn)請求高峰值，符合工業(yè)應(yīng)用場景.

Fig. 3 Frequency of requested contents under different content request models圖3 不同內(nèi)容請求模型下內(nèi)容請求頻率分布

實驗1結(jié)果對應(yīng)圖4和圖5.首先，圖4描述了PPPS算法和5種對比算法在基于SNM模型的用戶請求序列下，隨緩存容量變化命中率和平均延遲的性能表現(xiàn).從圖4(a)可以看出，LFU算法的命中率表現(xiàn)最差，是由于過氣的熱點內(nèi)容長期滯留緩存的“緩存污染”問題造成.FIFO算法和LRU算法的命中率次之，反映了2種算法對動態(tài)模型下的內(nèi)容請求分布適應(yīng)性也較差.MPC算法只緩存超過閾值的流行內(nèi)容，因此緩存容量較小時MPC在LRU基礎(chǔ)上性能有一定改進，但隨著緩存容量變大MPC的命中率出現(xiàn)收斂趨勢.GDS算法中權(quán)衡了內(nèi)容尺寸和訪問時間，因此更適應(yīng)存在很多小尺寸的控制流量的工業(yè)應(yīng)用.GDS算法在緩存容量較小時與MPC表現(xiàn)接近，但隨緩存容量增大，GDS可以達到比MPC更好的命中率.本文提出的PPPS算法命中率始終保持最高.緩存容量為120 MB時，PPPS算法的命中率比MPC提高12.3%，比GDS提高15.7%，比LRU提高21.3%，比LFU提高24%，比FIFO提高29.6%.

Fig. 4 Algorithm performance comparison under the SNM圖4 SNM模型下算法性能對比

圖4(b)描述了6種緩存算法隨緩存容量的變化引起的平均延遲變化.可以看出，平均延遲的變化與命中率變化的趨勢相反，隨著緩存容量的增大，6種算法的延遲都逐漸減小，PPPS算法的平均延遲一直低于其他5種緩存算法，與命中率的表現(xiàn)具有一致性.緩存容量為120 MB時，PPPS算法的平均延遲比MPC降低12.3%，比GDS降低15.7%，比LRU降低21.3%，比LFU降低24%，比FIFO降低29.6%.因此可以說PPPS算法平衡了內(nèi)容尺寸、時間和流行度等影響因素，在數(shù)據(jù)請求為動態(tài)分布時有最優(yōu)的性能表現(xiàn).

圖5展示了內(nèi)容請求序列遵循Zipf分布時，6種緩存算法隨緩存容量變化的命中率和平均延遲的比較.可以看到LFU算法命中率較高，這是因為Zipf分布遵循二八定律，有少數(shù)的內(nèi)容被多次請求，這對于按照請求頻次作為流行度指標的LFU算法十分有利. PPPS算法隨緩存容量的增大，其命中率始終高于其他5種算法.緩存容量為120 MB時，PPPS算法的命中率比MPC提高9.8%，比GDS提高5.6%，比LFU提高2.2%，比LRU提高11.5%，比FIFO提高15.6%. 在算法的平均延遲表現(xiàn)上.PPPS算法也具有較低的延遲.因此，PPPS算法在數(shù)據(jù)請求為Zipf分布時也有較穩(wěn)定的性能.

Fig. 5 Algorithm performance comparison under the IRM圖5 IRM模型下算法性能對比

2) 內(nèi)容大小相同時緩存算法的性能分析

實驗2結(jié)果對應(yīng)圖6，旨在探究內(nèi)容的尺寸對緩存算法的性能影響.在SNM模型生成的請求流量下，將所有內(nèi)容的大小設(shè)置為相同，圖6(a)為6種緩存替換算法在不同緩存容量下的命中率比較.MPC算法的表現(xiàn)最差，這是因為當內(nèi)容大小都設(shè)置為1 MB的小文件時，MPC由于設(shè)定了靜態(tài)的流行度閾值，導(dǎo)致即使緩存有充足的空間，相當部分的數(shù)據(jù)由于達不到流行度閾值不能進入緩存.LFU算法次之.LRU，GDS，F(xiàn)IFO三種算法的性能相近.PPPS算法的命中率仍然保持最高，且隨著緩存容量變大性能改進更加明顯.緩存容量為120 MB時，PPPS算法的命中率比GDS，LRU，F(xiàn)IFO這3種算法提高5.5%，比LFU提高16.8%，比MPC提高20.7%.圖6(b)為6種緩存算法平均延遲的比較，PPPS算法具有最小的平均延遲.可見將內(nèi)容尺寸的影響因素去除后，PPPS算法的表現(xiàn)仍然最佳，證實了基于屬性特征流行度預(yù)測方法的有效性.

Fig. 6 Algorithm performance comparison with unique content size setting圖6 內(nèi)容尺寸相同時算法性能對比

3) 內(nèi)容種類對算法性能的影響分析

實驗3結(jié)果對應(yīng)圖7，旨在探究緩存算法在不同內(nèi)容種類下的性能表現(xiàn).在SNM模型生成的請求流量下，令內(nèi)容種類范圍為100～500，圖7展示了6種緩存替換算法的性能對比.可以看到，隨內(nèi)容種類的增多，所有緩存算法的命中率都逐漸下降，平均延遲都逐漸增大.LFU算法因為緩存污染的問題在各內(nèi)容種類下性能都較低，LFU算法的平均延遲曲線出現(xiàn)小的波動，這是因為工業(yè)中小尺寸內(nèi)容較多，當請求頻率較低的大尺寸內(nèi)容發(fā)生頻繁替換時，容易導(dǎo)致延遲的增加.FIFO，LRU，GDS這3種算法性能曲線相近，在LFU的基礎(chǔ)上有不同程度的性能提升.MPC算法在緩存容量足夠大時，性能出現(xiàn)退化；隨著內(nèi)容流量增加，MPC算法表現(xiàn)逐漸優(yōu)于LRU算法.PPPS算法則始終保持最高的命中率，以及更低的延遲.內(nèi)容種類為350種時，PPPS算法的命中率比GDS提高15.3%，比MPC提高17.3%，比LRU提高20.1%，比FIFO提高22.3%，比LFU提高24.8%.并且，PPPS算法相對于其他算法的性能改進隨著內(nèi)容種類的增加而增加.在工業(yè)應(yīng)用中可能面臨內(nèi)容種類的多樣性，PPPS算法在不同的內(nèi)容種類測試中，均保持了最優(yōu)表現(xiàn).

Fig. 7 Algorithm performance comparison with different content types setting圖7 內(nèi)容種類變化時算法性能對比

從實驗結(jié)果可以看出，內(nèi)容大小、內(nèi)容種類、用戶請求模型都對緩存替換算法的性能產(chǎn)生影響，但是本文提出的PPPS算法與其他經(jīng)典緩存算法相比，始終具有最高的緩存命中率和較低的平均延遲.PPPS算法通過周期性預(yù)測特征屬性熱度，將內(nèi)容流行度預(yù)測納入緩存價值的計算，并判斷未來熱點內(nèi)容，在緩存空間空余時提前將熱點內(nèi)容存儲到邊緣緩存中，確實有效提升緩存利用率，提高緩存命中率，并有效減少傳輸延遲.

6 總 結(jié)

本文基于工業(yè)邊緣計算應(yīng)用場景，首先建立工業(yè)邊緣網(wǎng)絡(luò)模型和用戶請求模型，然后基于最近時間窗口的內(nèi)容請求序列的特征變化，建立單一維度的內(nèi)容流行度概率模型，結(jié)合內(nèi)容尺寸提出一種新的PPPS緩存替換算法.實驗結(jié)果表明：PPPS算法與MPC，GDS，LRU，LFU，F(xiàn)IFO 這5種經(jīng)典算法對比，在緩存命中率和平均延遲2種性能指標下，在不同內(nèi)容大小分布、內(nèi)容種類、用戶請求模型下均取得最佳性能，為實際工業(yè)場景里緩存算法的選擇提供了依據(jù).未來工作將考慮通過多維度特征表征內(nèi)容流行度，并使用機器學(xué)習(xí)算法預(yù)測流行度周期的變化.