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

張 雷 李 琳 陳鴻龍 Daniel Bovensiepen

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

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

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

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

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

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

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

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

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

1 相關(guān)工作

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

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

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

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

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

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

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

2 系統(tǒng)模型

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

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

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

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

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

2.2 問(wèn)題模型

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

(1)

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

(2)

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

maxH，

(3)

minD.

(4)

3 用戶請(qǐng)求流行度預(yù)測(cè)

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

3.1 用戶請(qǐng)求模型

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

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

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

(5)

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

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

3.2 用戶請(qǐng)求的流行度變化預(yù)測(cè)

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

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

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

(6)

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

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

(7)

4 PPPS緩存算法

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

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

(8)

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

(9)

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

算法1.PPPS算法.

輸出：緩存命中率H.

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

② fork=1,2,…,Kdo

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

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

⑤j++；

⑦ else

⑧ while(緩存空閑大小

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

⑩ end while

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

5 算法性能評(píng)估

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

5.1 實(shí)驗(yàn)參數(shù)設(shè)置

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

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

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

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

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

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

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

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

5.2 實(shí)驗(yàn)結(jié)果分析

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

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

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

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

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

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

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

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

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

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

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

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

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

6 總 結(jié)

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