基于競價模式和智能迭代模式的邊緣協作緩存算法研究

摘" 要： 為了讓用戶更快地獲取內容，提出一種基于競價模式和智能迭代模式的綜合式邊緣協作緩存算法。在競價算法部分，采用熵權法計算中間值、訪問熱度、緩存空間和內容熱度的權重，并綜合計算節點上內容的緩存分數，根據緩存分數進行緩存替換。在迭代算法部分，將網絡空間劃分為多個子域，每個子域通過混合遺傳算法進行周期性計算，并得出子域內內容緩存方案。實驗結果表明，所提算法在降低云服務器負載、減少請求平均跳數方面具有明顯的優勢。

關鍵詞： 邊緣計算； 協作緩存； 競價模式； 智能迭代模式； 熵權法； 網絡空間； 混合遺傳算法

中圖分類號： TN919?34； TP311" " " " " " " " " "文獻標識碼： A" " " " " " " " " " " 文章編號： 1004?373X（2024）12?0165?05

Research on edge collaborative caching algorithm based on bidding mode

and intelligent iteration mode

LI Changminchen1， LU Feipeng2， WANG Yanling2

（1. Hangzhou Dianzi University， Hangzhou 310018， China; 2. Hangzhou Newgrand Technology Co.， Ltd.， Hangzhou 310000， China）

Abstract： In order to enable users to obtain content faster， a comprehensive edge collaborative caching algorithm based on bidding mode and intelligent iteration mode is proposed. In the bidding algorithm section， the entropy weight method is used to calculate the weights of intermediary value， access heat， cache space， and content heat. The cache score of the content on the node is calculated comprehensively， and cache replacement is performed based on the cache score. In the iterative algorithm section， the network space is divided into multiple subdomains， each of which is periodically computed by means of the hybrid genetic algorithm， and a content caching scheme within the subdomains is obtained. The experimental results show that the proposed algorithm has significant advantages in reducing cloud server load and average hop count of requests.

Keywords： edge computing; collaborative caching; bidding mode; intelligent iteration mode; entropy weight method; cyberspace; hybrid genetic algorithm

0" 引" 言

隨著各行業數字化改造的持續推進，越來越多的終端設備接入網絡，導致網絡中的數據流量呈現井噴式增長[1]。然而，龐大的數據流量極易引發網絡擁塞甚至堵塞，從而增加用戶接入時延，并嚴重降低用戶服務體驗。因此，在智能交通、智能醫療和智能工業等物聯網環境下對設備終端的數據緩存研究尤為關鍵[2]。傳統云計算架構一般遠離大部分用戶地理位置，因此會影響服務質量和用戶體驗[3]。針對上述問題，邊緣計算應運而生。邊緣計算緩存是指將數據、應用或計算結果存儲在邊緣計算節點上，以提高數據訪問速度并降低網絡延時和帶寬消耗[4]。通過將數據緩存到離用戶更近的地方，從而減少數據在網絡上傳輸的距離，并提升數據訪問速度和響應時間。邊緣計算緩存通常適用于處理具有實時性要求的網絡資源，如直播視頻[5]、移動應用[6]、物聯網[7]和人工智能等[8]。

在邊緣計算環境下[9?12]，為了更好地降低設備終端訪問時延，本文提出了一種競價緩存算法。該算法充分考慮了節點中間值、節點訪問熱度、節點緩存空間和內容流行度對緩存性能的影響，并采用熵權法，根據歷史數據確定各影響因素的權重，以使內容在響應分組下行過程中被緩存在競價得分最高的節點上。此外，本文周期性地運行智能迭代緩存算法，并在其執行間隔內運行競價緩存算法。這樣做不僅可以提高緩存方案的準確性，還可以使其對流量的時空變化更具適應性。

1" 問題建模

在邊緣計算環境中，網絡節點可分為三種類型：云端節點（內容提供者）、邊緣節點（緩存提供者和計算服務提供者）以及設備終端。在本文實驗的樹狀網絡中，僅存在一個云端節點，其余均為邊緣節點和設備終端節點。實驗旨在將適當的內容緩存至相應的節點上，以使系統總體平均請求成本最小化。

現設定[S0]代表網絡中的云端節點；S=[s1，s2，…，sα]代表網絡中的邊緣節點集合；H=[h1，h2，…，hα]代表網絡中每個邊緣節點上緩存空間大小的集合；M[=m1，m2，…，mβ]代表網絡中的設備終端集合；L=[l1，l2，…，lβ]代表網絡中的設備終端訪問云端節點的最短距離；C=[c1，c2，…，cγ]代表流通于網絡中的內容類目種類集合；矩陣sD[=d1，1…d1，α???dβ，1…dβ，α]代表網絡中的設備終端到達各個邊緣節點的最短距離，[Di，j]代表設備終端[mi]到邊緣節點[sj]的最短距離；矩陣P[=p1，1…p1，γ???pβ，1…pβ，γ]代表網絡中設備終端發出的各類內容數量，[Pi，j]代表設備終端[mi]請求內容[cj]的數量。現設緩存決策矩陣Z[=z1，1…z1，α???zγ，1…zγ，α]，[zi，j]代表內容[ci]是否在邊緣節點[sj]上緩存。其中，[zi，j]應當滿足的約束條件為：

[zi，j=0，" 內容ci未緩存在節點j上zi，j=1，" 內容ci緩存在節點j上i=1，j∈Sγzi，j ≤hj]

以設備終端平均訪問跳數作為系統訪問代價，系統訪問代價計算公式如下所示：

[Rm，c，s=lm1-zc，s+dm，szc，s]" （1）

[Costz=m=1βc=1γminRm，c，1，Rm，c，2，…，Rm，c，α·pm，cm=1βc=1γpm，c]" （2）

式中：[Rm，c，s]表示設備終端[m]在節點[s]上訪問內容[c]的跳數；[lm]表示設備終端[m]到達云端節點的最短距離；[dm，s]表示設備終端[m]到達邊緣節點[s]的最短距離；[zc，s]表示內容[c]是否緩存在邊緣節點[s]上；[Costz]表示在當前緩存策略矩陣Z下的系統訪問代價；[pm，c]表示設備終端[m]發出內容[c]請求的數量。

2" 算法描述

2.1" H2BC競價算法

在H2BC算法中，將節點的中間值、節點熱度值、節點剩余緩存值和節點內容熱度值這4個指標作為緩存競價因素，并通過熵權法[13]確定各競價因素對價格的影響權重；再通過數據分發鏈路進行競價。算法具體過程如下。

定期計算本節點的熱度值和內容熱度值。節點熱度值的計算公式如下所示：

[Hots，t=0.2Hots，t-1+0.8Nums，t]" （3）

式中：[Hots，t]表示[t]周期節點[s]的節點熱度值；[Nums，t]表示[t]周期節點[s]的被訪問量。

節點內容熱度值計算公式如下所示：

[HCs，c，t=max（Counts，c，t-max（νs，c，0）·emax（νs，c，0），0）]" （4）

式中：[HCs，c，t]表示[t]周期內容[c]在節點[s]上的熱度值；[Counts，c，t]表示[t]周期時，內容[c]在節點[s]上的累積請求量；[νs，c]表示內容[c]在節點[s]上的熱度衰減速度，當到達節點[s]的請求為內容[c]時，[νs，c=νs，c-1]，反之[νs，c=νs，c+1]。

請求到達節點時，節點會進行以下操作。

1） 保存請求數據包中的[Mb]、[Mh]、[Mc]標簽到節點本地。

2） 將自身中間值、節點熱度值以及請求內容的節點熱度值與數據包中三個標簽做比較，將較大者更新到數據包上。

3） 計算節點緩存內容得分。

4） 若本地緩存內容得分高于請求數據包中的[O]標簽，則更新請求數據中的O標簽，同時將請求數據包中的N標簽更新為本地節點序號。

本地緩存內容得分計算公式如下所示：

[Scores，c，t=αBetwsMb+βHots，tMh+γHCs，c，tMc+0.05Rs] （5）

式中：[Scores，c，t]表示當前內容[c]在節點[s]上的緩存得分；[Betws]表示節點[s]的中間值；[Hots，t]表示當前節點[s]的節點訪問熱度；[HCs，c，t]表示當前內容[c]在節點[s]上的熱度值；[Rs]表示當前節點剩余緩存空間比例；[α]、[β]、[γ]為權重值。[α]、[β]、[γ]通過熵權法來計算，計算過程如下。

在系統初始化時，網絡中尚未有數據流通，此時每個節點的[Mb]、[Mh]、[Mc]初始值都為0。當數據開始在網絡中流通，積累了一定量的數據之后，進行指標標準化。[Xi]表示指標i的原始值集合，[Xi={Mi1，Mi2，…}]；[Yi]表示指標i的標準值集合：

[Yi=Mi1-min（Xi）max（Xi）-min（Xi），Mi2-min（Xi）max（Xi）-min（Xi），…]

標準化后，[α]、[β]、[γ]權重值計算公式如下：

[Pi=Yi1j=1nYij，Yi2j=1nYij，…] （6）

[Ei=-（lnn）-1j=1npijlnpij] （7）

[Wi=1-Ei3-j∈{α，β，γ}Ej] （8）

最后經過云端節點的判斷，請求數據包中N標簽所對應的節點被確定為最終競價獲勝者，并將N值復制到下行內容數據包中。當本地節點接收到下行內容數據包時，若其為獲勝者，則會緩存該數據包中的內容；如果本地H2BC可分配緩存空間不足，則會淘汰當前周期內在本地H2BC緩存空間中且流行度低于待緩存內容的其他內容。

2.2" CPMGA迭代算法

遺傳算法是一種基于基因和染色體作為基本單元，模擬生物進化過程（包括遺傳、變異、選擇和交叉操作），以尋求最優解的優化方法[14]，具體過程如下。

核節點設置初始種群規模k、迭代次數t。隨機生成初代種群個體，同時計算對應的適應值。對初代種群中個體按照適應值大小進行降序排序。個體適應值計算公式如下所示：

[Rm，c，s=lm1-zc，s+dm，szc，s] （9）

[Fitz=m=1βc=1γpm，cm=1βc=1γminRm，c，1，Rm，c，2，…，Rm，c，α·pm，c] （10）

式中：[Rm，c，s]表示設備終端[m]在節點[s]上訪問內容[c]的跳數；[lm]表示設備終端[m]到達云端節點的最短距離；[dm，s]表示設備終端[m]到達邊緣節點[s]的最短距離；[zc，s]表示內容[c]是否緩存在邊緣節點[s]上；[Fitz]表示當前個體的適應值；[pm，c]表示設備終端m發出內容c請求的數量。

個體被選擇進入下一代的概率滿足指數為內容傾斜度的冪函數模型，計算公式如下所示：

[Pz=1rskewzi=1k1rskewi] （11）

式中：[Pz]代表個體[z]被選中進入下一代的概率；[rz]表示個體[z]的適應性排名值；[skew]為內容傾斜度。式（11）確保了適應值較高的個體在下一代中被選入的概率更大，同時也為適應值較低的個體提供了進入下一代的機會，避免陷入局部最優解。

在新一代種群中，概率選擇個體進行隨機基因長度交叉。個體選擇交叉概率公式如下所示：

[Pz=e-rz-0.8+0.15] （12）

式中：[Pz]代表個體[z]進行交叉的概率；[rz]表示個體[z]的適應性排名值。式（12）確保了適應值較高的個體在交叉過程中參與染色體交換的概率更大，同時也給予適應值較低的個體染色體交換的機會，避免陷入局部最優解。

在新一代種群中，對所有個體進行隨機1～3個基因變異操作。個體的突變概率如下所示：

[Pz=0.95（1-e-（rz-1））+0.05e-（rz-1）] （13）

式中：[Pz]代表個體[z]進行變異的概率；[rz]表示個體[z]的適應性排名值。式（13）保證了適應值低的個體有更高概率變異，同時適應值高的個體也有機會進行變異，避免局部最優。

2.3" NEXC協作算法

NEXC算法將H2BC與CPMGA結合在一起，在初始化網絡階段，將每個邊緣節點的可用緩存空間劃分為兩部分：一部分用于緩存由H2BC算法決定的待緩存內容；另一部分則用于緩存由CPMGA算法決定的待緩存內容。每當節點收到網絡數據包時都會執行H2BC算法，而CPMGA則由子域核節點定期執行。每個節點定期按照式（14）的概率清理訪問記錄。

[r=Tc-TrT0+Tc-Tr] （14）

式中：[r]表示訪問記錄被清除的概率；[Tc]表示當前時間；[Tr]表示訪問時間；[T0]是清理算法的執行周期。

3" 實驗與分析

3.1" 仿真環境

仿真實驗基于自編程序進行場景模擬和數值仿真，通過對比其他算法的性能來驗證本文算法的可靠性。實驗運行在Windows 11 21H2 64 bit操作系統下，并使用AMD Ryzen 7 4800H @2.9 GHz*8處理器和16 GB內存。仿真網絡采用樹狀拓撲結構，如圖1所示。

實驗中模擬了1 500個節點的網絡拓撲，其中終端設備與服務器數量比約為6∶4。此外，在實驗中設置了4個偏好區間，每個設備終端都按照特定順序訪問偏好區間，概率比例為4∶3∶2∶1，總共4×2 500種內容類目；每個內容大小固定為單位1；設備終端發出的內容請求符合齊普夫定律在偏好區間中的分布。實驗結束條件是達到2 000 000個流通內容數量。

3.2" 實驗結果

本文選取了ICN網絡中的通用緩存算法，即LCE緩存算法、基于競價的BID緩存算法以及基于K?means的智能ANC緩存算法作為實驗的對比算法。

1） 不同節點緩存容量下的平均請求跳數

本文對比了不同節點緩存空間下，不同算法之間平均請求跳數的變化情況，實驗結果如圖2所示。在低緩存空間率時，BID算法表現不及ANC算法；然而，在高緩存空間率時，BID算法優于ANC算法。相較于其他算法，LCE算法始終具有較高的平均請求跳數，而NEXC算法則始終具有較低的平均請求跳數。

2） 不同內容傾斜度下的平均請求跳數

本文對比了不同內容傾斜度下，各種算法之間平均請求跳數變化情況，實驗結果如圖3所示。

由圖3可知：在低內容傾斜度條件下，LCE、BID和ANC算法的平均請求跳數差異不大，其中LCE略低于BID算法和ANC算法；隨著內容傾斜度增加，ANC算法的平均請求跳數逐漸落后于LCE算法和BID算法，而NEXC算法始終優于其他三種算法。

3） 不同節點緩存容量下的云端命中率

本文對比了不同節點緩存空間利用率下，各算法在云端命中率方面的變化情況，結果如圖4所示。

由圖4可知：在緩存空間較少時，NEXC算法在減輕云端負荷方面表現出顯著優勢，ANC算法優于BID算法，而BID算法則優于LCE算法；隨著緩存空間逐漸增大，NEXC算法的優勢更加明顯，ANC與BID之間的差異趨于平緩，并且LCE相較其他三者表現較為不理想。

4） 不同內容傾斜度下的云端命中率

本文對比了不同內容傾斜度下，各種算法之間云端命中率的變化情況，結果如圖5所示。

在內容傾斜度低于0.8時，BID與ANC算法表現相似，而LCE算法與其他三種算法存在明顯差距；當內容傾斜度高于0.8時，ANC算法源端命中率的下降趨勢變得平緩，并且內容傾斜度達到1.4后被LCE算法超過。相比其他三種算法，NEXC算法一直表現優異。

4" 結" 語

本文提出了一種既能保證高準確度又能保證高時效性的協作緩存算法。該算法可以并行運行經過優化的競價算法和迭代算法。競價算法綜合考慮中間值、節點熱度、節點緩存空間和內容流行度對最終緩存分數的影響，并采用熵權法確定各指標的權重。智能迭代算法通過劃分子域、有限迭代的方式縮小了求解規模，從而提高了緩存策略的時效性。實驗結果顯示，所提方法在降低平均跳數、降低云負載等方面具有明顯優勢。

參考文獻

[1] DHAMDHERE A， DOVROLIS C. Twelve years in the evolution of the internet ecosystem [J]. IEEE/ACM transactions on networking， 2011， 19（5）： 1420?1433.

[2] YU W， LIANG F， HE X， et al. a Survey on the edge computing for the Internet of Things [J]. IEEE access， 2017（6）： 6900?6919.

[3] KUMAR M， DUBEY K， PANDEY R. Evolution of emerging computing paradigm cloud to fog： applications， limitations and research challenges [C]// 2021 11th International Conference on Cloud Computing， Data Science amp; Engineering （Confluence）. Noida， India： IEEE， 2021： 257?261.

[4] SRIRAM G S. Edge computing vs. cloud computing： an overview of big data challenges and opportunities for large enterprises [J]. International research journal of modernization in engineering technology and science， 2022， 4（1）： 1331?1337.

[5] QIAN B， WEN Z， TANG J， et al. OsmoticGate： adaptive edge?based real?time video analytics for the Internet of Things [J]. IEEE transactions on computers， 2023（72）： 1178?1193.

[6] OSPANOVA A， MAHAM B. Delay?outage probability of capacity achieving?based task offloading for mobile edge computing [C]// 2022 IEEE International Conferences on Internet of Things （iThings） and IEEE Green Computing amp; Communications （GreenCom） and IEEE Cyber， Physical amp; Social Computing （CPSCom） and IEEE Smart Data （SmartData） and IEEE Congress on Cybermatics （Cybermatics）. Espoo， Finland： IEEE， 2022： 236?242.

[7] SOWMYA R， NANDHINI M， PRIYANGA M. Enhancing edge node resilience through SDN?driven proactive failure management [C]// 2024 IEEE International Conference for Women in Innovation， Technology amp; Entrepreneurship （ICWITE）. Sakon Nakhon， Thailand： IEEE， 2022： 198?201.

[8] TRAN?DANG H， KIM D S. Perspectives of digital twin?empowered distributed artificial intelligence for edge computing [C]// 2023 International Conference on Artificial Intelligence Innovation. Lefkosa， Cyprus： IEEE， 2022： 446?450.

[9] GUO Y， ZHOU G， HOU J， et al. Cooperative caching strategy based on dynamic cache value perception in edge networks [C]// 2022 IEEE 21st International Conference on Ubiquitous Computing and Communications. Chongqing： IEEE， 2022： 73?80.

[10] Lü X， DU H， YE Q. TBTOA： a DAG?based task offloading scheme for mobile edge computing [C]// IEEE International Conference on Communications. Seoul， South Korea： IEEE， 2022： 4607?4612.

[11] SAMPEDRO G A， MANAIG R， SALAZAR?MANAIG P， et al. An overview of opportunities and challenges of edge computing in smart manufacturing [C]// 2022 13th International Conference on Information and Communication Technology Convergence. Jeju Island， South Korea： IEEE， 2022： 2182?2186.

[12] SHARAN B， SAGAR A K， CHHABRA M. A review on edge?computing： challenges in security and privacy [C]// 2022 International Conference on Applied Artificial Intelligence and Computing. Salem， India： IEEE， 2022： 1280?1286.

[13] 劉瑋，周華任，黃春艷.基于灰色?熵權法的合成旅裝備戰斗力評估[J].計算機仿真，2023，40（4）：26?30.

[14] YANG F， TIAN Z. MRPGA： a genetic?algorithm?based in?network caching for information?centric networking [C]// 2021 IEEE 29th International Conference on Network Protocols （ICNP）. Dallas， TX， USA： IEEE， 2021： 1?6.