一種基于合作緩存的D2D通信緩存策略?

虞新穎 譚 沖 劉 洪 鄭 敏 卜智勇

（1.中國科學院上海微系統與信息技術研究所 上海 200050）（2.中國科學院大學 北京 100049）

1 引言

全球移動數據流量在2016年至2021年間將以47%的年復合率增長，在2021年達到每月49艾字節［1］。移動數據流量如此爆炸性增長主要是超高清晰度流媒體視頻、基于云的應用逐漸爆發以及智能終端的海量接入［2］。在傳統的蜂窩網絡中，移動終端之間的數據通信必須通過基站的中繼轉發。因此，在無線通信數據業務日益增長、用戶對移動通信網絡服務質量的要求不斷提高的情況下，基站承載壓力越來越大。終端直通（Device-to-Device，D2D）技術作為5G通信關鍵技術之一，允許臨近終端在基站的控制下，互相之間直接進行數據共享，形成數據共享網絡，復用蜂窩網絡的信道資源以達到減輕基站負載、提升頻譜利用率、提高系統吞吐量的目的［3］。

在D2D無線緩存網絡中，借助于網絡中大量分散的終端存儲資源，數據可以在非高峰通信期提前被緩存到終端。在通信高峰期，用戶便可以從自身緩存或者通過D2D通信從臨近節點的緩存中得到所需數據，使流量本地化，大大減輕基站負載。大量學者已針對D2D通信中的緩存技術展開了研究，主要集中在緩存策略的優化上。文獻［4］以最小化數據服務提供商所需付出的代價為目標進行系統建模，將終端緩存空間分為Duplicate和Unique兩部分，前者緩存部分最流行的數據，后者只存儲剩余的從未被緩存過的數據。該策略從數據服務提供商的角度出發，并未完全利用終端有限的內存空間，易產生數據冗余。文獻［5］從博弈論的角度出發將D2D數據共享描述為一種交易行為，數據請求用戶是買方，數據提供用戶是賣方，已緩存數據是待售物品，以最大化所有用戶收益為目標對緩存網絡進行建模求解。仿真表明該緩存策略具有較好的魯棒性，但是緩存命中率不高。文獻［6］通過分析終端與數據之前的請求關系提出了基于終端偏好（Interest-based）的緩存策略，該策略只考慮終端本身有潛在需求的數據。文獻［7］針對數據請求用戶以最大化平均緩存命中概率為目標建立緩存模型，提出兩種次優緩存策略。這兩種策略的前提是將一部分較不流行的數據從緩存數據庫中撤除，比較受限于特定場景。因此，如何設計有利于基站卸載、能充分利用終端內存而不受限于特定場景的緩存策略仍亟待研究。

針對D2D緩存策略的優化，多數文獻基于用戶角度出發進行研究，從基站角度出發的研究還比較少。本文針對D2D無線緩存網絡中的緩存問題，以最大化蜂窩網絡流量卸載為優化目標，結合臨近節點緩存情況，提出一種基于合作緩存的緩存策略，根據數據單位價值的大小從高到低進行緩存。最大化蜂窩網絡流量卸載的同時保證終端有限的內存資源得到高效利用。

2 系統模型和問題描述

首先描述D2D無線緩存網絡中終端與數據分布的情況以及一些假設條件，然后討論具體的問題描述。

2.1 系統模型

考慮LTE網絡下一個單蜂窩小區，小區內存在一個中心基站、n個具備D2D通信能力的智能終端，終端集合為，所有終端均勻分布在小區內。假設D2D通信距離最大為R，則用戶 Di的臨近節點集合為。每個終端的數據請求都是相互獨立的。假設所有請求數據來自一個數據集合，包含m個數據。數據大小不完全相同，符合正態分布，可被分塊緩存。

D2D無線緩存網絡如圖1所示，網絡中存在兩種通信:傳統蜂窩通信與D2D通信，后者以Underlay模式存在于蜂窩網絡中［8］。D2D用戶復用蜂窩用戶的頻譜資源，中心基站負責D2D通信與蜂窩通信之間的無線資源分配與干擾管理［9］。為了保證多址接入，蜂窩網絡采用正交頻分復用（Orthogonal Frequency Division Access，OFDM）系統以提升頻譜利用效率［10］。

圖1 D2D無線緩存網絡

用戶獲取數據時，首先采用文獻［11］提出的一種軟件定義無線電的設備間信號機制詢問臨近節點是否已緩存該數據，若已緩存，則選擇一個空閑節點配對，兩者匹配成功后進行D2D通信，否則用戶進行蜂窩通信，即通過基站獲取數據。假設用戶可以同時發送和接受數據，但是建立的發送鏈路最多一條，接收鏈路也最多一條。

2.2 問題描述

首先，終端通常基于自身意愿緩存最新接收的數據信息（比如最新的視頻、音樂文件等），如果恰好也有臨近節點所請求的數據，那么當臨近節點發起請求后，經過會話建立等一系列過程，兩者之間可通過D2D通信進行數據共享。小區內成功進行D2D數據共享的終端越多，蜂窩網絡流量卸載越多［12］。因此，終端緩存的數據應盡可能滿足臨近節點的需求，使流量本地化。然而，由于本身內存的限制，終端不可能對全部數據進行緩存，只能選擇性緩存。

其次，當出現某一熱點消息（比如爆炸性新聞等）時，大多數終端將請求并緩存該消息，導致短時間內基站負荷過大，同時造成終端內存數據冗余，浪費了有限的終端存儲資源［13］。

解決上述問題，既要保證臨近節點的數據需求，又要兼顧終端內存高效的利用率。為此本文以最大化蜂窩網絡流量卸載為目標，提出一種基于合作緩存的D2D通信緩存策略，具體如下:

定義1定義一個n×m的緩存矩陣H=[hij]n×m，表示用戶緩存數據的情況。其中0≤hij≤1，當 hij=1時，表示用戶 Di對數據 Mj全部緩存；當hij=0時，表示不緩存，介于兩者之間表示部分緩存。

定義2定義數據請求概率Pij，表示Di的臨近節點集合Ni請求數據Mj的概率。

Pij可反映出臨近節點的數據需求，Pij越大，表示臨近節點對該數據需求越大。若終端緩存數據的請求概率越大、體積越大，則越有利于蜂窩網絡流量卸載。因此，將緩存問題轉化為以下最優化問題:

進一步觀察式（1）可知，反映臨近節點需求的Pij是時刻改變、無法確定的，上述優化問題是NP-hard問題。

3 緩存策略

對于式（1），目標是最大化蜂窩網絡流量卸載，即終端所緩存的數據力求最大化滿足臨近節點的共享請求以進行D2D通信。為了求解緩存矩陣H，需確定數據請求概率Pij。為解決這個問題，可對Pij進行預測。考慮到用戶Di可記錄其臨近節點的共享請求，包括請求數據的種類和次數，因此，根據Zipf定律——事物請求概率與其出現頻次相關［14］，對 Pij進行預測如下:

其中:tij表示過去某段時間臨近節點集合Ni向Di請求數據Mj的次數。

事物流行趨勢一般不會出現突變，式（2）實質上是根據歷史請求情況預測數據未來被請求的概率。但是，對于突然出現的某一熱點消息，其請求概率非常大，而終端并未來得及緩存，導致短時間內蜂窩通信次數劇增，造成網絡負擔。由于終端都選擇緩存，也會造成數據冗余。針對該現象，考慮引入合作緩存，不僅考慮數據請求概率，也考慮其他用戶的緩存情況。合作緩存具體如下:

定義3定義緩存比例為Bij，表示數據Mj相對于終端Di的緩存比例，其值等于緩存Mj的臨近節點數占已進行緩存的臨近節點數的百分比。

在合作緩存中，用戶將結合緩存比例，重新預測數據請求概率，如式（3）所示:

即更新后的請求概率等于原請求概率與緩存比例之差。

以圖2為例說明如何進行合作緩存:假設D2D無線緩存網絡中有4個具有相同內存的終端，2個具有單位大小的數據M1和M2，對于4個終端的請求概率分別是0.6和0.4。若終端獨立緩存，則都會選擇請求概率較高的M1進行緩存，易造成基站負擔和數據冗余。若終端合作緩存:

1）D1緩存前，詢問臨近節點緩存情況，此時另外三個節點緩存全為空，顯然M1和M2緩存比例都為0，則請求概率不變，D1選擇M1進行緩存；

2）D2緩存前，同樣詢問臨近節點緩存情況，發現一個已緩存的節點，且其緩存數據為M1，則M1的緩存比例為100%，M2的緩存比例為0，根據式（3）更新 M1和 M2請求概率，變為（0.6-1）和（0.4-0），因此D2選擇M2進行緩存；

3）D3緩存前，發現兩個已緩存的節點，且分別緩存了M1和M2，則M1和M2的緩存比例都為50%，因此更新請求概率為（0.6-0.5）和（0.4-0.5），選擇緩存M1；

4）同理，對于D4，更新后的請求概率分別為（0.6-0.67）和（0.4-0.33），選擇緩存 M2。最終兩個終端緩存M1，兩個終端緩存M2。實際上，這和數據原先的請求概率（0.6和0.4）是比較對應的。

圖2 合作緩存圖

對Pij進行有效定義后，對于優化問題（1），可將其視為背包問題，用經典的貪心算法求解。緩存策略具體步驟如下:

1）初始化。對于終端Di，背包大小即終端內存Ci，物品大小即數據大小。

2）Di緩存前，收集 tij及 Bij，根據式（2）和式（3）求出數據請求概率Pij，則物品價值等于數據請求概率與數據大小的乘積。

3）排序。將數據的單位價值進行降序排列。

4）緩存。將單位價值最高的數據緩存進內存，若將該種數據全部緩存完畢后，未超過Ci，則選擇單位價值次高的數據并盡可能緩存。依此策略一直進行下去，直到Ci滿為止，即得到選擇矩陣。

4 仿真結果及分析

仿真實驗中，我們測試了一個單蜂窩小區中D2D無線緩存網絡的性能，簡單起見，不考慮終端的移動性，并且假設終端每秒提出請求的概率為0.5，數據大小符合正態分布，其他性能參數如表1所示。

表1 仿真參數設置

網絡性能由緩存命中率和卸載率表示:緩存命中率指臨近節點提出的數據請求正好是終端已緩存數據的比例，數值越高意味著緩存策略越有效；卸載率指D2D通信次數占通信總次數（D2D通信+蜂窩通信）的百分比，數值越高表明蜂窩網絡流量卸載越大。如無特別說明，終端內存大小為100KB，數據個數為100，大小均值為10KB。

圖3比較了有合作緩存和無合作緩存兩種情況下的網絡總體性能指標。開始時，終端還未緩存，內存為空，無法滿足臨近節點的數據共享請求，所有數據通過基站獲取，所以緩存命中率和卸載率為0。總體上看，不管有沒有合作緩存，隨著終端逐漸緩存數據，緩存命中率和卸載率都在緩慢提升。經過20s左右，引入合作緩存的網絡中，緩存命中率和卸載率開始大幅度上升，50s左右接近于60%，而未引入合作緩存的網絡中，性能指標穩定在40%，可以看出引入合作緩存帶來的好處。

圖3 網絡總體性能指標

為了更好分析本文所提策略的優點，仿真結合對比了現有最為普遍的等概率緩存策略（Equal Probability Caching，EPC）和最流行緩存策略（Most Popular Caching，MPC）的緩存命中率。在EPC策略中，所有數據被終端緩存的概率是相等的，并不考慮終端的偏好和數據的差異［15］。在MPC策略中，數據請求概率遵循齊普夫分布，終端優先考慮緩存熱點數據，易造成數據冗余［16］。由圖4可以看出，開始時由于終端并未緩存大量數據，MPC策略和本文所提緩存策略的差別并不明顯，到緩存后期，在MPC策略中大多數終端都擁有最流行數據，造成終端內存數據冗余，MPC策略的劣勢突顯，而本文所提緩存策略的緩存命中率穩定在55%左右，比MPC策略高30%左右，比EPC策略高13%左右。

最后，為了更好地分析D2D無線緩存網絡的性能細節，進一步分析了數據因素的影響。在圖5仿真結果中，網絡性能隨著數據個數的增多而下降。這是由于數據個數越多，意味著可供終端緩存的選擇越多，分散了用戶的喜好，導致緩存命中率和卸載率的下降。在圖6仿真結果中，網絡性能隨著數據平均大小的提高而下降，這是由于數據越大，在終端內存固定的前提下，意味著可緩存的數據種類變少，滿足臨近節點請求的概率降低。

圖4 不同緩存策略下的緩存命中率

圖5 數據個數對系統性能的影響

圖6 數據平均大小對系統性能的影響

5 結語

D2D通信作為未來通信網絡的重要支撐技術之一，可應用于本地終端數據共享，使流量本地化，有助于減輕蜂窩網絡流量負載、改善用戶體驗等。針對D2D無線緩存網絡，本文以最大化蜂窩網絡流量卸載為優化目標，提出一種基于合作緩存的D2D通信緩存策略。首先從終端本身及臨近節點需求出發，預測數據請求概率，再結合當前數據緩存比例，引入合作緩存。最后將緩存問題視為背包問題，用經典貪心算法求解。仿真結果表明該策略能最大化蜂窩網絡流量卸載，同時能高效利用終端有限內存。