移動邊緣網絡中基于內容信息年齡和流行度的緩存機制

邱婭，蔡岳平，譚兵

（重慶大學微電子與通信工程學院, 重慶 400044）

1 引言

隨著信息技術和電信技術的進步，移動蜂窩網絡在過去20年里經歷了1G到4G的演進，用戶的偏好逐步從傳統的手機到智能手機，從筆記本電腦到平板電腦。因此，隨著智能設備和新移動應用程序的爆炸式增長[1]，用戶對移動網絡的需求也越來越嚴格，如超高的數據速率和極低的延時，然而傳統的以基站中心的網絡結構已經不能滿足用戶日益增長的需求。在下一代5G系統中，移動蜂窩網絡的架構將以基站為中心向以用戶為中心和以內容為中心的網絡演進，即將網絡的重心從核心向邊緣轉移。

對于此，學術界和產業界相繼提出了Cloudlet[2～4]、霧計算[5～7]、邊緣計算[8]，旨在移動網絡邊緣提供IT服務環境和云計算能力，使其更加靠近終端處理業。在滿足計算要求的同時有效地降低業務延時，其中邊緣計算[9]作為第五代移動通信技術的關鍵技術之一，將通信、存儲與計算資源放置于互聯網邊緣接近用戶或設備，按需提供應用與服務。移動邊緣計算[10](Mobile Edge Computing，MEC)則是將邊緣計算技術應用至移動互聯網，在無線移動網絡邊緣靠近移動用戶或設備的地方，提供按需訪問共享可配置虛擬計算池或提供與之交互服務的一種新型移動計算模式。通過這種新型的計算模式將服務遷移到距離用戶較近的位置，能有效降低服務的通信延時[11]。由于邊緣設備本身具有一定的計算能力和存儲能力，因此能夠直接在邊緣設備上進行一部分的數據處理和分析。在移動通信網絡結構中將直接進行數據處理和分析的網絡結構稱為移動邊緣網絡。如圖1所示，主要包括移動前傳網絡(RU至DU間)和移動中傳網絡(DU至CU間)兩部分，用戶設備和物聯網物體通過遠端射頻端RRH或WiFi接入點方式接入移動網絡，移動邊緣計算功能可根據需求部署在移動邊緣網絡內的任何位置。因此，將部分用戶經常訪問的數據內容提前存儲在移動邊緣網路上，用戶就能更加方便、快捷地獲取所需內容，即移動邊緣緩存。

移動邊緣緩存的重點是解決節點選取和內容選取的問題，以最大化內容緩存命中率及最小化用戶獲取內容時延。針對上述問題，本文提出一種基于內容信息年齡和內容流行度的移動邊緣網絡緩存機制AoIPC，用于提高緩存命中率，降低核心網流量，從而提高移動邊緣網絡性能。

2 研究現狀

對于移動邊緣網絡緩存機制的設計，主要解決的問題可歸納為三點：

（1）如何挑選緩存的節點；

（2）如何確定需要緩存的內容；

（3）采用何種方式獲取所需內容。

其中，緩存決策策略很大程度上影響著用戶獲取所需內容的速率，是移動邊緣緩存的重要研究方向。

圖1 移動通信網絡總體架構圖

在緩存地點的選擇研究上，文獻[12]提出一種DPC(Distributed Probabilistic Caching )策略，選擇位于關鍵位置的節點作為緩存節點，以平衡數據的可訪問性和緩存開銷，在DPC中每個節點獨立做出緩存決策，節點通過挖掘用戶需求，接收者和發送者的相對運動及自身的度中心性和介數中心性決定出需要緩存的內容，從而做出緩存決策。DPC算法雖然考慮到了緩存節點移動性的問題，卻忽略了緩存節點的容量有限的問題。文獻[13]提出的PCBCS(Popularity and Centrality Based Caching Scheme)緩存策略根據內容的流行度和節點的中心度匹配來進行緩存決策，在考慮內容流行度的基礎上加入了節點中心性考量，將內容與節點進行排名匹配后再決定是否要對其進行緩存，從而實現更合理的資源分配。PCBCS沒有考慮節點的位置信息，不能保證內容緩存在靠近用戶的節點上，可能會導致流行度高的內容只緩存在中心度高且離用戶較遠的節點上，使得用戶獲取內容的時延增大。文獻[14]提出的基于內容流行度和節點重要性的CCN(Content Centric Network)緩存策略解決了這一問題，將節點中心度與內容流行度相結合，節點的中心度反應了節點在網絡中的重要性。中心度等于路由器節點的度，即與該路由器相關聯的鏈路的條數，節點的中心度越高表示該節點在緩存位置的選取中越重要。在節點重性高的節點內生成內容流行度排名之后，將新到達的大于最大流行度的內容放在此重要節點的下一級節點，將小于最小流行度的內容放在此重要節點的上一級節點，從而減緩重要節點的緩存替換率和負荷，讓流行的內容逐漸靠近用戶，減少內容冗余。

在緩存內容的選擇上，大多數學者將內容的流行度作為參考指標，但是用戶對內容的偏好程度在不同的上下文環境中可能有所不同，因此需要對內容的流行度進行預測。文獻[15]設計一種基于位置自定義的緩存方案，以最大限度地提高內容的命中率，針對零均值噪聲的情況，提出了一種基于脊回歸的正擾動在線算法，然而隨著時間增長，該算法的命中率與最優緩存策略的命中率逐步接近，無法體現出其優勢。文獻[16]提出了一種新的用于塊級的緩存替換方法PPC(Popularity Prediction Caching)，分析用戶行為獲得視頻塊之間的聯系，作為流行度預測的基礎，預測和緩存未來最流行的塊，并以線性復雜度驅逐那些未來最不受歡迎的塊。結果表明，研究所提出策略性能高于最近最少使用(LRU)，最不頻繁使用(LFU)和先進先出(FIFO)等緩存策略。但是，未考慮在存儲空間有限的節點中如何度量以替換出流行度較低的內容。文獻[17]使用深度學習來學習和預測未來內容的流行程度，以支持緩存決策。通過預測每個內容的未來類標簽，得出每個內容的流行度分數，最后緩存流行度分數高的內容，該方案能有效提高內容的緩存命中率，然而沒有考慮緩存節點選取的問題。

3 AoIPC機制

3.1 邊緣節點屬性分析

在AoIPC中，通常將移動邊緣網絡中的射頻單元和分布單元作為緩存節點，射頻單元節點將充當接入點（Access Point，AP）功能。與移動系統類似[18]，邊緣節點的核心屬性包括通信、計算和緩存，這三者將構成移動系統的主要資源，因此本文將重點討論節點的三種屬性。

（1）通信能力

移動系統的通信能力是由數據速率來衡量的，無線通信中電波在傳輸時接收功率強度與傳輸距離存在某種關系，因此在AoIPC中使用的用戶節點到邊緣節點的距離來表征通信能力。孫佩剛等人[19]采用混合定位法得出了功率與傳輸距離的變化關系，當傳輸距離較近時，采用最小二乘曲線擬合法計算出用戶節點到邊緣節點的距離；當傳輸距離較遠時，通過信號強度分布法，查詢接收到的接收信號強度顯示RSSI(Receive Signal Strength Indicator)值較大邊緣節點的采樣值數據庫，從而計算出用戶節點到邊緣節點的距離。計算公式[18]為：

其中，E表示接收到的信號功率，K為常數取值為15.4，ui表示某個用戶，vj表示某個節點，D(uivj)表示某個用戶用戶與某個節點間的傳輸距離。用戶距離邊緣節點越近，無線信道越穩定，支持的上下行速率就越高，從而節點的通信能力就越強。在無向圖中，將用戶到某個節點的距離除以用戶到所有節點的距離總和進行歸一化。

（2）計算能力

計算是邊緣節點的主要資源之一，節點的計算能力反映了其快速處理、轉發和路由數據流的能力，節點高效的計算能力能夠帶來高效的數據傳輸能力，從而實現節點對單個用戶的服務。節點的計算能力越強，在處理用戶請求內容的時間越短，則用戶從節點處獲取內容的平均時延就越短。文獻[18]提出節點的計算能力是由參與操作的節點數和信息流來度量的，將其稱之為“計算度”(Degree of Computing，DoC)，當需要計算單個節點的計算能力時，DoC=1；當計算兩個或兩個以上節點的計算能力時，DoC=2+，因此本文的DoC為參與到數據處理的邊緣節點數量。在無向圖中，將DoC除以邊緣節點總數n進行歸一化。

（3）緩存能力

節點的緩存能力主要是由緩存容量和空閑緩存容量決定的。緩存能力的上限是由緩存容量決定的，緩存容量越大則緩存的內容越多樣，從而緩存命中率越高，節點的緩存容量越小則導致無法完整的緩存文件，從而降低緩存命中率?？臻e緩存容量是指節點在不刷新就緩存的前提下進行緩存的能力，對于空閑緩存容量大的節點，優先考慮為緩存節點，從而能提高緩存利用率。由此，將緩存空閑率C(vi)表示為某個節點的綜合緩存能力，計算公式為：

其中，Cfree(vi)表示該節點的空閑緩存容量，Ctotal(vi)表示該節點的總緩存容量。

通過本文分析綜合節點的通信能力、計算能力和緩存能力選擇出合適的節點來緩存用戶所需內容：

得到節點重要性度量結果后控制器對各邊緣節點進行排序，從而得到節點的重要性排名。

3.2 緩存替換機制

邊緣節點緩存空間的容量是有限的，無法將用戶請求的所有內容緩存在節點中，在緩存空間不足時為了能緩存新到達的緩存資源，傳統的緩存替換算法最近最少使用（Least Recently Used，LRU）或使用頻率最少（Least Frequently Used，LFU）會導致文件下載時延較長，降低內容的緩存命中率。因此，本文將從內容信息年齡和內容流行度兩方面選擇出需要被替換的內容。

（1）內容的信息年齡

邊緣節點緩存內容的指標之一，是內容的熱度。為了提高移動邊緣網絡緩存的性能，緩存節點需要盡可能及時的獲取用戶感興趣的內容，即監測數據的實時更新狀態。數據的新鮮度量采用信息年齡標準，其定義[20]為在源端生成帶時間戳的狀態更新消息并通過通信系統傳輸到監視器，當監視器在時刻t收到時間戳為u(t)的狀態更新消息時，則狀態更新年齡為t-u(t)。在移動邊緣網絡中，由于用戶所需內容緩存在靠近用戶的節點，所以用戶或者設備在獲取實時信息更新的時延會有所減小。因此，在AIAPC中將內容的信息年齡引申為邊緣節點對用戶興趣偏好的監控，當用戶發出內容請求被命中時，此刻產生用戶信息更新且邊緣節點將接收到更新的狀態信息，邊緣節點上內容的信息年齡表示為：

其中，t表示邊緣節點接收用戶信息更新的時間，u(t)表示用戶發出內容請求的時間戳，T(k)越小表示該內容熱度越高以及邊緣節點獲取用戶信息更新的時延越小。

（2）內容流行度

邊緣節點緩存內容的指標之二，是內容的流行度，以提高用戶獲取內容的命中率，內容的流行度主要受過去一段時間內被請求的次數的影響。假設內容k在節點vi上在過去T時間內被用戶請求的次數為fi(k)，則內容k在節點vi上的流行度為：

綜上分析，記節點中緩存內容的度量為S(k)。

其中，α為控制因子，控制內容信息年齡和內容流行度的權重，出于公平考慮，取α=0.5，即不偏袒其中任意度量，但在實際應用中，根據實際網絡，α需要進行修改。得到節點中內容的度量后，對S(k)較小的內容進行緩存替換。

其算法流程圖如圖2所示。

3.3 AoIPC算法實現

圖2 AoPC算法流程圖

按照建議對AoIPC算法的復雜性進行適當分析。如表1所示，是對AoIPC緩存機制的算法描述。首先根據控制器的全局視角獲得全局網絡拓撲，然后分別計算各個節點的D(uivj)、DoC和C(vi)，并進行歸一化處理，依據不同的需求確定三個度量所占的權重分別為α、β和γ，并依據公式(3)計算得出各個節點的度量總分I(vi)，仔根據度量總分對節點的緩存優先級進行排序，并按順序依次選出k個節點并發出主動緩存指令。因此，在選擇最佳緩存節點時的時間復雜度為O(n3)，在緩存空間不足時，計算出節點中已緩存內容的Pi(k)和T(k)，并依據公式(6)計算出已緩存內容的度量總分S(k)，最后按排序選擇出需要替換的內容，因此在決定緩存替換的內容的時間復雜度時O(n)。綜上分析，此AIAPC算法可知時間復雜度為O(n3)+O(n)，當n足夠大時，該算法的復雜度為O(n3)。

4 仿真與分析

4.1 實驗設置

實驗硬件環境為Intel（R）Core（TM）i3-4170cpu@3.7.GHz，12GB內存；操作系統是Ubuntu14.04LTS 64 bit。將仿真數據導入Matlab軟件中處理，與處緩存機制LCE(Leave Copy Everywhere)、概率緩存機制Prob（Copy with Probability）進行比較，主要指標為緩存命中率、內容源節點平均請求次數和平均請求時延等三個評價指標上進行了定量的比較和分析。

表1 AoIPC緩存機制的算法描述

（1）拓撲設置

設置一個深度為4，固定節點數為14，移動節點（即用戶設備）數為100的隨機樹狀拓撲，移動節點初始隨機放置于邊緣節點覆蓋范圍內，其中射頻單元和分布單元作為邊緣緩存節點，固定節點拓撲連接示意圖如圖3所示。

（2）實驗參數設置

圖3 固定節點拓撲連接示意圖

設置網絡提供的內容數量為10000個，用戶數量為100個，用戶的請求模式為Zipf分布，其參數設置為0.7，Zipf越大說明用戶的偏好越集中，用戶的請求過程服從泊松分布，即請求的間隔時間服從指數分布。假設每個節點的緩存容量相同均為C，仿真主要參數設置如表2所示。

4.2 仿真結果

表2 仿真參數設置

（1）緩存命中率

緩存命中率是評價緩存機制的性能指標之一，緩存命中率越大，緩存機制的效率越高。定義緩存命中率為：

其中，N為邊緣節點接收到的請求內容總數，Ki為邊緣節點vi接收到的請求命中數，Ch為邊節點的緩存命中率。橫軸變化量為相對緩存容量R，給出R的定義為：

其中，Ctotal為節點緩存能力總量，U為總內容數大小。

對各緩存機制的緩存命中率對比如圖4所示。從圖4中可以看出，隨著R的增加，三種緩存機制的緩存命中率也逐漸增加。LCE的緩存命中率最低，這是因為該緩存策略要求所有節點均緩存所需內容，就會導致出現大量緩存內容冗余，從而降低緩存內容多樣性；其次是Prob，該策略要求所有節點以固定的概率緩存所需內容對象，雖然能增加節點的空間利用率，但是仍然存在大量冗余緩存；緩存命中率最高的是AoIPC，該機制可以有效的減少緩存冗余，提高節點中緩存內容的多樣性，從而響應較多的內容請求，體改緩存命中率。

（2）內容源節點平均接收請求次數

圖4 邊緣節點緩存命中率分析

邊緣節點的緩存命中率越高，表明內容源節點接收到的請求次數降低，源節點的請求負載也就越低，從而流向核心網絡的流量減少，相應的網絡內緩存性能就越好。

對各緩存機制的內容源節點平均請求次數對比如圖5所示。從圖5中可以看出，隨著R的增加，三種緩存機制的內容源節點平均請求次數均逐漸減少，因為用戶將直接從邊緣節點處獲取所需內容，其中AoIPC減小的幅度最大，流向核心網的流量最少，Prob次之，LCE減少的最少。

（3）平均請求時延

圖5 內容源節點平均接受請求次數分析

平均請求時延是指用戶發出請求信息到返回內容所經歷的平均時延，反映了請求的反應速度。由于邊緣節點最靠近用戶，所以具有較快的反應速度。反應速度越快，說明緩存機制的緩存效率越高。定義Ti為內容fi的請求時延，Tmean為所有內容的平均請求時延，其計算方法為：

對各緩存機制的平均請求時延對比如圖6所示。從圖6中可以看出，隨著R的增加，三種緩存機制的平均請求時延逐漸減小。對比分析可以看出，三種緩存機制中，平均請求時延最大的是LCE，其次是Prob，而AoIPC的平均請求時延最小。因為，LCE的大多數請求需要在內容源節點處獲得響應；Prob通過增加緩存內容的多樣性，使得較多的請求在邊緣處獲得；而AoIPC可以有效的利用緩存的多樣性，提高緩存內容的多樣性，響應大量的內容請求，從而有效降低獲取內容的平均時延。

5 結束語

為了提高移動邊緣網絡的緩存性能，本文提出了一種基于內容信息年齡和流行度的移動邊緣網絡緩存機制AoIPC。該機制分析提取了邊緣節點的屬性，通過節點的通信能力、計算能力和緩存能力三個參數綜合計算出邊緣節點在內容緩存方面的重要性并加以降序排序，最后根據排名順序選擇重要節點進行主動緩存。同時，對節點中已緩存的內容做流行度和信息年齡表征，對節點中流行度和信息年齡較低的內容進行緩存替換。

圖6 平均請求時延分析

仿真實驗結果表明，AoIPC與LCE、Prob機制的對比中，有效地提高了節點的緩存命中率，在相對緩存容量較低的情況下有效提高邊緣節點緩存命中率，且減少網絡源節點平均請求次數即降低流向內容源節點的流量，同時該機制還降低了用戶獲取內容的平均時延。