基于用戶偏好與副本閾值的端到端緩存算法

文凱 譚笑

摘 要：在端到端（D2D）緩存網絡中存在大量多媒體內容，而移動終端中緩存空間卻相對有限。為了實現移動終端中緩存空間的高效利用，提出了一種基于用戶偏好與副本閾值的D2D緩存部署算法。首先，基于用戶偏好，設計緩存收益函數，用于判斷各文件的緩存價值;然后，以系統緩存命中率最大化為目標，利用凸規劃理論設計緩存副本閾值，用于部署系統中文件的副本數量;最后，聯合緩存收益函數與副本閾值，提出一種啟發式算法實現了文件的緩存部署。與現有緩存部署算法相比，該算法可顯著提升緩存命中率及卸載增益，降低服務時延。

關鍵詞：端到端;內容緩存;用戶偏好;副本;凸規劃

Abstract： In the Device-to-Device （D2D） cache network， the cache space in the mobile terminal is relatively small with many multimedia contents. In order to realize the efficient use of cache space in mobile terminals， a D2D cache deployment algorithm based on user preference and replica threshold was proposed. Firstly， based on the user preference， a cache revenue function to determine the cache value of caching each file was designed. Then， with the goal of maximizing the cache hit ratio of system， the cache replica threshold was designed based on convex programming theory to deploy replica number of the files in the system. Finally， combining the cache revenue function with the replica threshold， a heuristic algorithm was proposed to implement file cache deployment. Compared with the existing cache deployment algorithm， the proposed algorithm can significantly improve the cache hit rate and the offload gain with the reduction of service delay.

Key words： Device-to-Device （D2D）; content caching; user preference; replica; convex programming

0 引言

隨著無線網絡數據流量指數式增長[1]，為了滿足下一代網絡高傳輸速率與低用戶側時延的通信需求，端到端 （Device-to-Device， D2D）通信技術獲得了極大的關注。D2D即終端直傳技術，可以使兩方設備在不經基站的情景下直接通信，利用分散在網絡中的D2D終端設備緩存資源，可以減輕基站流量壓力，降低用戶側傳輸時延，提高系統吞吐量及用戶體驗[2]。許多的學者考慮到D2D用戶之間的移動性、空間隨機性、社交關系等特點，利用隨機幾何理論來建立動態的終端動態拓撲模型，在此基礎上優化緩存網絡結構、更新緩存管理策略，以提升網絡緩存成功率和系統效能。

目前一些文獻基于信道信息、資源分配、流行度預測以及用戶分布模型研究了緩存部署問題。文獻[3]通過分配靜態緩存和按需中繼之間的最佳存儲分配權衡，提出了一種緩存分配方案來提升D2D網絡的緩存利用率。文獻[4]首先對高移動性網絡中終端緩存的流量卸載性能進行了研究，將流量卸載最大化問題建模為NP難題，提出了一個分布式流量卸載算法。文獻[5]考慮到用戶在D2D網絡中的地理位置來優化內容緩存分布，以提高緩存命中概率。

一些研究基于用戶興趣偏好與社交關系設計了緩存部署方案。文獻[6]分析了社交網絡和通信網絡的關系，并指出每個數據對象最終都會傳遞給感興趣的用戶，該文獻的研究為社交網絡與通信網絡的結合提供了依據。文獻[7]結合了用戶偏好和自私性，提出了一種緩存激勵方案，促進設備間合作，降低用戶自私性造成的影響。文獻[8]在以內容為中心的多跳無線網絡中，提出了基于用戶興趣的緩存部署策略。在內容中心網絡（Content Centric Network， CCN）中，文獻[9]中提出了一種合作緩存策略，它在作出緩存決策時考慮了用戶偏好、節點重要性和緩存替換率。然而，CCN更多地關注了路徑選擇問題，沒有考慮網絡性能的整體優化。

與機會網絡[10]類似，在D2D緩存網絡中，流行的資源往往會被多個終端緩存產生多個副本，由于D2D用戶終端緩存能力有限、移動性高，這有利于保證其緩存命中率與傳輸成功率，但過多的副本也會造成系統總體緩存空間的浪費，使其他流行文件無法得到充分的緩存而導致系統緩存命中率以及網絡性能下降。為了保證文件緩存成功率與緩存空間利用效率，提高緩存效率與系統性能，本文提出了一種基于用戶偏好與文件副本閾值集合的啟發式算法PRC（Preference Replicas Caching），旨在提升系統緩存命中率及卸載增益，降低服務時延。

1 系統模型

本文考慮一個單一小區無線D2D網絡，網絡由一個基站BS和N個D2D終端設備（D2D User Equipment， DUE）組成，系統模型如圖1所示。網絡中所有用戶的位置服從密度為λ 的齊次泊松點過程（Homogeneous Poisson Point Process， HPPP），DUE之間的通信與有效緩存傳輸距離均為R，網絡中緩存文件具有相同大小，且所有的DUE具有相同的緩存功能和存儲空間[11]。

在該系統模型中D2D通信采用正交頻率，且在傳輸時不會產生因同頻干擾發生的鏈路沖突，用戶n在其通信范圍內的其他鄰居用戶n′構成的集合記為Θn[12]。假設整個緩存網絡的文件總數為N，單個DUE不會重復緩存已有文件，那么緩存網絡中緩存文件fi的個數也即是已緩存文件fi的用戶終端數，均為Ni。

在此模型中，每個文件按照文件被請求概率，也就是文件流行度進行排名，描述文件的集合為F={f1， f2，…， fN}，文件的被訪問概率服從zipf分布[13]，則對于排名為i的文件fi的被請求概率為：

其中：γ為流行度分布的偏移指數，γ越大表示流行文件請求越集中。

當用戶在請求文件時，考慮以下兩種緩存命中事件：

事件一 自卸載。當用戶請求文件已在本地緩存時，則直接獲取本地緩存文件。

事件二 D2D卸載。當用戶請求文件在本地并沒有緩存時，用戶可在緩存傳輸距離R內找尋一個空閑的已緩存請求文件的DUE獲取該文件。

若用戶在本地緩存網絡中沒有成功請求的需求文件，則通過回程鏈路將請求文件從核心網絡下載到最近的基站，然后再通過基站發送給請求該文件的用戶，本文僅考慮事件一和事件二構成的緩存命中事件集。本文緩存算法設計基于被動緩存策略，即緩存動作發生在DUE獲得請求文件之后，由于D2D網絡中用戶具有較強的移動性，被動緩存比主動緩存可以降低系統能耗[14]。

2 PRC算法設計

2.1 基于用戶興趣偏好的緩存收益函數設計

在本節中，首先構建興趣相關度量，再利用其定義緩存收益函數。根據系統模型，在D2D緩存網中共存在N個文件，包含不同類型的G個主題集合為L={l1，l2，…，lk，…，lG}，則對于文件fi中包含的主題集合為Li={la，lb，…}，LiL，那么用戶n對于主題lk的偏好函數可表示為：

其中：X（lk） 表示用戶選擇lk主題的事件集;Vn 表示用戶n選擇主題的歷史事件;P（X（lk）│Vn）表示用戶n選擇主題lk的歷史概率，P（X（lk））表示全網用戶選擇主題lk的歷史概率。對于文件fi中是否存在主題lk，利用Pi（lk） 來表示：

用戶n對文件fi的偏好程度則可以用向量余弦距離[15]來表示：

由于緩存部署與內容分發時間間隔很短，本文考慮在設計緩存收益函數時，利用用戶間的物理距離d（n，n′）此處語句不通順，請作相應調整代替路徑損耗，則用戶n緩存文件fi的收益函數可表示為：

2.2 基于系統緩存命中率的副本布設方案

系統緩存命中率可以表示為本地緩存命中與D2D緩存命中兩個事件發生的概率和：

其中：pselfhit為自卸載緩存命中率;pd2dhit為D2D緩存命中率。

本文首先考慮本地緩存命中事件，用戶請求文件fi在本地已緩存的概率為：

則系統的自卸載概率可以表示為每個文件流行度與已緩存概率乘積的累加和：

因為在緩存網絡中的DUE滿足概率密度為λ的HPPP分布，則在半徑為R的方圓范圍內有m個DUE的概率表達式為：

根據HPPP稀釋理論，已緩存文件qiλ的DUE服從概率密度為qiλ的HPPP，那么對于文件fi的D2D卸載緩存命中率可以表示為：

整理可得，系統總的緩存命中率為：

設文件副本數布設集合為J={N1，N2，…，NN}，則優化問題可表示為：

其中Md為DUE的緩存存儲容量空間大小。

下面證明目標優化問題為凸規劃問題，首先對phit關于Ni進行二階偏導數運算，可得到：

由此可知，phit的海森矩陣對角線元素均小于零且其他元素均為零，故函數phit是關于J的嚴格凹函數。又因為J的定義為凸閉集，可知目標優化問題是一個凸規劃問題。

利用次梯度投影的方法可求解該優化問題。首先記拉格朗日函數為：

其中μ≥0，則對偶函數表示為：

對偶問題表示為：

將式（17）整理后得到Ni關于μ的函數表達式為：

因為副本數應為大于等于零的整數，所以在實際副本布設中需取其最接近正整數N^i=[N*i]為文件fi最優副本數，則當系統緩存命中率最大時，最優系統副本數布設表示為：

2.3 緩存算法設計

本文提出了一種啟發式算法，其中心思想是在考慮系統緩存命中最優條件下，使用戶選擇緩存收益更大的文件，放棄緩存收益相對較小的文件，從而最大化系統緩存收益。達到提高回程鏈路業務卸載量和緩存命中率、降低內容獲取時延的目的。

當用戶請求文件在本地有緩存時，DUE完成自卸載，若自卸載不成功，用戶將從鄰居用戶和基站獲得請求內容。為了部署緩存文件fi，本文采用了聯合用戶偏好與緩存閾值的啟發式算法。具體步驟如下：

其中：Ni表示文件fi當前網絡中的緩存副本數量;Cn表示用戶n已使用緩存空間大小。偽代碼執行條件為用戶n請求文件γ，且用戶n自卸載未成功。其第一層判斷語句用于判斷文件γ副本是否已經達到閾值，在未飽和的情況下再進入第二層DUE緩存空間判斷;若存在剩余緩存空間則進行緩存動作，否則選擇用戶n已緩存文件中緩存收益最小的文件，將其緩存收益與文件γ的緩存收益進行比較，選擇緩存高的文件進行緩存。

需要說明的是，由于文件流行度的實時性，網絡中的文件副本數可能超過文件副本閾值，此時需先行刪除緩存收益低的多余副本，再執行算法。

首先對本文所提算法特性進行分析。設置PRC算法參數為表1數值，并利用Matlab仿真可以得出按照文件流行度排名文件的最優副本數的布設方案如圖2所示。通過計算得出該副本布設方案下系統緩存命中率為phit=0.668。可以觀察到，排名越高，被請求概率越大的文件緩存副本閾值越大，即系統容許其在網絡中擁有更多的副本數。

在不同緩存容量Md場景下，三種算法的緩存命中率隨緩存文件數量N的變化情況如圖3所示。由圖3可知，Md越大表示DUE用于緩存的空間越多，系統整體緩存空間隨之增大。可以觀察到，當緩存容量確定的情況下，緩存命中率隨緩存文件數的增加而降低，由于DUE緩存容量有限，無法完全滿足文件緩存需求，致使系統緩存命中率降低;而當緩存文件數量一定時，DUE緩存容量越大，能夠緩存的文件也就越多，系統緩存命中率也就越高。與其他兩種算法相比，本文所提算法有更優的緩存命中效果。

圖4（a）顯示了三種算法在不同用戶密度與緩存容量下的用戶時延變化情況，可以觀察到本文算法相比GC和RCC平均服務時延更低。結果還表明，考慮到用戶偏好的緩存算法，其平均服務時延會隨用戶密度的增加而增加，這是由于隨著用戶密度的增大，網絡中的用戶總數呈線性增長，然而基于偏好的緩存文件數量呈對數式增長，前者增速大于后者，故平均服務時延隨用戶密度的增大而增加，而隨機緩存算法由于沒有考慮用戶偏好表現基本穩定。

圖4（b）比較了不同算法的流量卸載能力，可以看出，本文所提算法相比其他兩種算法有更高的卸載增益，且隨著用戶密度的增大，各算法的流量卸載能力均有不同程度的下降，這是由于更多用戶的緩存請求無法被響應，值得一提的是，本文所提算法卸載增益下降程度也明顯低于其他兩種算法。

圖4（c）為系統緩存命中率隨用戶密度λ的變化情況，可以觀察到，本文所提算法與其他兩種算法在用戶密度逐漸增大的趨勢下，系統緩存命中率均隨之增長，這是由于隨著小區中的用戶密度增大，更多的DUE參與進緩存動作中，網絡總體緩存空間也隨之增多，緩存命中事件也將增長，導致系統緩存命中率增大。

4 結語

針對D2D網絡中文件緩存與替換問題，本文提出了一種聯合了用戶偏好與緩存副本閾值的D2D緩存算法，利用用戶偏好判斷文件緩存價值，以副本閾值布設優化系統緩存命中率。通過仿真表明，本文所提算法對系統緩存命中率、平均服務時延、流量卸載增益方面較貪心算法與隨機算法均有更優性能表現，但在D2D通信網絡中，可能還存在鏈路沖突、信道衰落和干擾等復雜因素制約系統緩存能力，進一步研究可以結合信道模型考慮緩存問題。

參考文獻 （References）

[1] Cisco. Cisco visual networking index： global mobile data traffic forecast update， 2016—2021 white paper [EB/OL]. （2017-03-28） [2018-12-05]. https：//www.cisco.com/c/en/us/solutions/collateral/service-provider/visual-networking-index-vni/mobile-white-paper-c11-520862.html.

[2] 錢志鴻，王雪.面向5G通信網的D2D技術綜述[J].通信學報，2016，37（7）：1-14.（QIAN Z H， WANG X. Reviews of D2D technology for 5G communication networks [J]. Journal on Communications， 2016， 37（7）： 1-14.）

[3] WANG W， WU X， XIE L， et al. Joint storage assignment for D2D offloading systems [J]. Computer Communications， 2016， 83（C）： 45-55.

[4] 藍瑞寧.終端直通蜂窩系統中的邊緣緩存技術[D].杭州：浙江大學，2017：9-47.（LAN R L. Edge caching for cellular systems with device-to-device communications [D]. Hangzhou： Zhejiang University， 2017： 9-47.）

[5] MALAK D， AL-SHALASH M， ANDREWS G J. Optimizing the spatial content caching distribution for device-to-device communications [C]// Proceedings of the 2016 IEEE International Symposium on Information Theory. Piscataway， NJ： IEEE， 2016： 280-284.

[6] CHEN K， CHIANG M， POOR H V. From technological networks to social networks [J]. IEEE Journal on Selected Areas in Communications， 2013， 31（9） ：548-572.

[7] CHEN Z， LIU Y， ZHOU B， et al. Caching incentive design in wireless D2D networks： a stackelberg game approach [C]// Proceedings of the 2016 IEEE International Conference on Communications. Piscataway， NJ： IEEE， 2016： 1-6.

[8] IQBAL J， GIACCONE P. Interest-based cooperative caching in multi-hop wireless networks [C]// Proceedings of the 2013 IEEE Globecom Workshops. Piscataway， NJ： IEEE. 2013： 617-622.

[9] WU L， ZHANG T， XU X， et al. Grey relational analysis based cross-layer caching for content centric networking [C]// Proceedings of the 2015 IEEE/CIC International Conference on Communications in China. Piscataway， NJ： IEEE， 2015： 643-648.

[10] 熊永平，孫利民，牛建偉，等.機會網絡[J].軟件學報，2009，20（1）：124-137.（XIONG Y P， SUN L M， NIU J W， et al. Opportunistic networks [J]. Journal of Software， 2009， 20（1）： 124-137.）

[11] KANG H J， PARK K Y， CHO K， et al. Mobile caching policies for Device-to-Device （D2D） content delivery networking [C]// Proceedings of the 2014 IEEE Conference on Computer Communications Workshops. Piscataway， NJ： IEEE， 2014： 299-304.

[12] LIU A， LAU V K N， CAIRE G. Cache-induced hierarchical cooperation in wireless device-to-device caching networks [J]. IEEE Transactions on Information Theory， 2018， 64（6）： 4629-4652.

[13] CHA M， KWAK H， RODRIGUEZ P， et al. Analyzing the video popularity characteristics of large-scale user generated content systems [J]. IEEE/ACM Transactions on Networking， 2009， 17（5）： 1357-1370.

[14] SOURLAS V， PASCHOS G S， FLEGKAS P， et al. Mobility support through caching in content-based publish/subscribe networks [C]// Proceedings of the 10th IEEE/ACM International Conference on Cluster， Cloud and Grid Computing. Piscataway， NJ： IEEE， 2010： 715-720

[15] KHAN E A， SHEIKH Y A， KANADE T. Mode-seeking by medoidshifts [C]// Proceedings of the 11th IEEE International Conference on Computer Vision. Piscataway， NJ： IEEE， 2007： 1-8.