邱婭，蔡岳平，譚兵

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

1 引言

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

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

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

2 研究現(xiàn)狀

對于移動邊緣網(wǎng)絡(luò)緩存機制的設(shè)計，主要解決的問題可歸納為三點：

（1）如何挑選緩存的節(jié)點；

（2）如何確定需要緩存的內(nèi)容；

（3）采用何種方式獲取所需內(nèi)容。

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

圖1 移動通信網(wǎng)絡(luò)總體架構(gòu)圖

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

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

3 AoIPC機制

3.1 邊緣節(jié)點屬性分析

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

（1）通信能力

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

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

（2）計算能力

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

（3）緩存能力

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

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

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

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

3.2 緩存替換機制

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

（1）內(nèi)容的信息年齡

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

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

（2）內(nèi)容流行度

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

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

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

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

3.3 AoIPC算法實現(xiàn)

圖2 AoPC算法流程圖

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

4 仿真與分析

4.1 實驗設(shè)置

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

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

（1）拓撲設(shè)置

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

（2）實驗參數(shù)設(shè)置

圖3 固定節(jié)點拓撲連接示意圖

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

4.2 仿真結(jié)果

表2 仿真參數(shù)設(shè)置

（1）緩存命中率

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

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

其中，Ctotal為節(jié)點緩存能力總量，U為總內(nèi)容數(shù)大小。

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

（2）內(nèi)容源節(jié)點平均接收請求次數(shù)

圖4 邊緣節(jié)點緩存命中率分析

邊緣節(jié)點的緩存命中率越高，表明內(nèi)容源節(jié)點接收到的請求次數(shù)降低，源節(jié)點的請求負載也就越低，從而流向核心網(wǎng)絡(luò)的流量減少，相應(yīng)的網(wǎng)絡(luò)內(nèi)緩存性能就越好。

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

（3）平均請求時延

圖5 內(nèi)容源節(jié)點平均接受請求次數(shù)分析

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

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

5 結(jié)束語

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

圖6 平均請求時延分析

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