D2D集成霧無線接入網(wǎng)中的雙層分布式緩存

夏騁宇，蔣雁翔

（東南大學(xué)，江蘇 南京211189）

1 引言

近年來，高質(zhì)量的無線視頻、社交網(wǎng)絡(luò)等業(yè)務(wù)和智能應(yīng)用呈現(xiàn)爆炸式增長。可以預(yù)見，未來的 5G/B5G網(wǎng)絡(luò)中這些業(yè)務(wù)還將繼續(xù)增長，如何在指數(shù)增長的業(yè)務(wù)中為用戶提供低時延的體驗，是 5G/B5G移動通信的重要問題。霧無線接入網(wǎng)（fog-radio access network，F(xiàn)-RAN）作為新型的無線傳輸架構(gòu)，已經(jīng)引起了學(xué)術(shù)界和產(chǎn)業(yè)界的關(guān)注。雖然F-RAN能夠?qū)⒕彺婧陀嬎愎δ芟路诺竭吘壒?jié)點（F-AP）[1]，但由大量用戶下載少數(shù)流行文件時產(chǎn)生的通信負擔(dān)以及隨之而來的時延依然是其亟待解決的問題[2]。此外，F(xiàn)-AP本身緩存容量較小也帶來緩存命中率不高的問題[1]。因此，霧無線接入網(wǎng)需要一種有效的緩存布置算法來緩解用戶時延和提高命中率。同時，D2D通信近來已經(jīng)受到學(xué)術(shù)界和產(chǎn)業(yè)界的關(guān)注，但是已有的研究大都關(guān)注D2D通信如何有效實現(xiàn)及避免干擾[3-6]。將D2D通信和霧無線接入網(wǎng)結(jié)合，提出一種在F-AP層和用戶設(shè)備層中的分布式緩存布置。由此帶來兩個主要的問題：和傳統(tǒng)蜂窩基站（cellular base station）相比，F(xiàn)-AP和用戶設(shè)備的緩存容量都要小得多，因此決定某一個文件應(yīng)不應(yīng)該被緩存變得越發(fā)重要；如何在用戶設(shè)備層實現(xiàn)D2D通信也至關(guān)重要。

在本文中，希望用分布式算法來解決上面的問題，對于用戶設(shè)備層的緩存分布，將其轉(zhuǎn)化為背包問題，采用貪心算法求解。文件權(quán)重就是它的流行度，而一個用戶設(shè)備可以通過搜集周圍的信息計算出流行度，從而讓所有用戶設(shè)備分布式地做出緩存決定。將F-AP的緩存分布轉(zhuǎn)化為因子圖問題，使用置信度傳播算法（belief propagation algorithm）求解。對于如何實現(xiàn)UE間D2D傳輸，也通過分布式的方式求解。為了降低算法復(fù)雜度，在本文的研究中，UE和 F-AP都不會預(yù)先緩存（proactively cache）任何文件來提高命中率，并且整個網(wǎng)絡(luò)中UE間的文件交換全部都是單跳通信，不依賴任何多跳通信。這樣分布式的解決方案將更簡單，更有利于在現(xiàn)實霧無線接入網(wǎng)中的應(yīng)用。

圖1 霧無線接入網(wǎng)中的二維緩存

2 系統(tǒng)模型

如圖1所示，考慮一個集成了D2D通信的霧無線接入網(wǎng)，并且假設(shè)一個 F-AP覆蓋范圍內(nèi)的UE不會被其他F-AP覆蓋的UE影響[7]。在這種情況下，一個UE既可以從F-AP下載文件，也可以向其周圍的 UE獲取文件。同時，假設(shè)只有同一個F-AP覆蓋區(qū)域內(nèi)的UE之間可以進行D2D傳輸[7]。參考文獻[8]已經(jīng)研究了無線資源分配機制，因此可以假設(shè)F-AP和D2D通信不會互相干涉。正交頻分多址（OFDMA）技術(shù)以及參考文獻[8,9]研究的其他技術(shù)可以避免D2D通信的互相干擾。參考文獻[10]對于全雙工通信的研究使得可以假設(shè)每個UE可以在向一個UE發(fā)送文件的同時從另一個 UE接收文件。此外，為了降低算法復(fù)雜度，假設(shè)F-AP和UE都不會預(yù)先緩存某些文件，也就是每個 UE只會緩存它自己申請過的文件，并將這些文件傳輸給相鄰UE。每個F-AP的緩存一開始也為空，并通過自己收集的本地信息決定緩存。

3 方程建立

基于圖1所示的模型，先考慮緩存在用戶層內(nèi)的分布。假設(shè)每一個用戶也有一個緩存容量Qu。再定義znk表示文件fn是否緩存在uk的相鄰UE中。這樣，F(xiàn)-AP中的UE向F-AP申請文件fn的概率為式（1）：

也就是說，如果某個 UE的周圍已經(jīng)緩存有文件fn，則它不需要向 F-AP請求文件；若周圍沒有此文件，則它仍然要向F-AP請求文件。這樣就得到了用戶向F-AP申請文件的概率。同時，用戶向相鄰用戶申請文件fn的概率為

這樣，通過D2D下載的總的時延就可以寫為：

其中，dD2D為D2D通信的平均時延。

從而F-AP層下載的總時延為：

其中，dnk為設(shè)備uk從F-APam下載文件的時延，且其中h為 UE與 F-AP間的信道增益，mγ為F-APam的等效傳輸信噪比（equivalent transmit SNR）。

這樣，就得到總時延的閉式解，為：

類似地，可以得到雙層緩存對單純的 F-AP層緩存的時延增益的閉式解為：

3.1 UE層緩存分布

3.1.1 文件流行度

首先研究 UE層。假設(shè)不同 F-AP覆蓋下的UE不會互相干擾[7]，因此只需要研究一個 F-AP覆蓋下的UE。UE層的緩存問題可以看作一個典型的背包問題：每個文件的流行度可以看作背包問題中每個物品的權(quán)重；背包容量就是 UE的緩存容量Qu。為了讓UE可以分布式地估計每個文件的流行度，設(shè)備uk要記住相鄰設(shè)備向自己請求文件fn的次數(shù)，記為tnk，這樣，就能定義某個文件 fn的本地流行度，為：

考慮到突發(fā)新聞等因素，用戶的興趣可能會在短時間內(nèi)突變，為了提高D2D傳輸利用率，讓F-AP也能通過上述類似的方法計算某個文件的全局流行度，并使UE從F-AP下載文件的同時也獲得該文件的全局流行度。而全局流行度會在相鄰UE間快速傳播，這樣每個UE都能了解到最新的流行文件，并緩存它。

總之，對本地流行度可以這樣估計：每次一個相鄰 UE向ui請求文件 fn，ui就會將自己的tni加 1。ui從相鄰的uj那里獲取一個文件 fn的同時，tnj也會一起傳送給ui。這樣，ui就能更新自己的tni：

當(dāng)ui從F-AP下載1個文件時，這個文件的全局流行度nP也會一并傳送給ui。ui將nP折算成申請次數(shù)，并更新自己的tni：

3.1.2 優(yōu)化緩存利用率

然而隨之而來的問題是：經(jīng)過一段時間后，每個UE都會保存最流行的文件，導(dǎo)致每個UE緩存內(nèi)容相同，浪費了緩存資源。為了解決這個問題，UE不能簡單地緩存流行度大的文件。規(guī)定UE將流行度和緩存率的差作為判斷是否緩存的標(biāo)準，優(yōu)先緩存差值大的文件。為了做到這一點，ui每次緩存fn之前都要向相鄰 UE發(fā)送廣播信號，詢問周圍有多少UE已經(jīng)緩存了fn，然后計算 fn的緩存率P'ni和，最后緩存Gni最大的文件。這樣，ui每次就能緩存周圍 UE較少緩存的但流行度又較高的文件。

其中，緩存率P'ni定義為ui周圍已緩存 fn的UE個數(shù)與UE總數(shù)的比值，即：

3.1.3 UE層分布式緩存算法

擁有了Gni，就能求解緩存分布的背包問題。前面已經(jīng)提到，每個UE的緩存容量為Qu。當(dāng)緩存未滿時，UE總是保存接收到的文件；如果緩存已滿，則根據(jù)Gni的大小，替換緩存中Gni最小的文件。假設(shè)ui已經(jīng)緩存了Qu個文件，這時它從別處（F-AP或別的UE）獲得了第個文件，記為在收集所有必要信息之后，ui可以計算出所有個文件的G，進而可以替換緩存中的文件。

用貪心算法來解決這個背包問題，算法的復(fù)雜度由將每個文件的G降序排列的過程決定，為

算法1 UE層分布式算法

將Hk降序排列

3.2 D2D通信的實現(xiàn)

前文已經(jīng)提到，在D2D網(wǎng)絡(luò)中，每個UE每次最多只能向一個 UE發(fā)送或接收文件，因此定義狀態(tài)變量Sk表示uk是否正在發(fā)送文件表示 uk正在發(fā)送文件，反之表示沒有發(fā)送。定義表示uk是否正在接收文件，顯然只有當(dāng)時，uk才能發(fā)送文件請求。ui向uj發(fā)出文件申請的同時會查詢Rj的值，只有時，ui和uj才能進行D2D通信。

3.3 F-AP層緩存分布

上文已經(jīng)得到了uk向 F-AP申請文件fn的概率以 及 F-AP層 的 下 載 總 時 延那么F-AP層內(nèi)緩存優(yōu)化問題可以表示為：

上文已經(jīng)提到，這也是一個 NP難問題。為了分布式地解決這個問題，根據(jù) BP（belief propagation）理論提出一種分布式算法。參考文獻[11]闡述了BP算法中的信息傳遞理論和因子圖理論。

3.3.1 緩存分布的因子圖

為了應(yīng)用BP算法，必須先將上面帶邊界條件的優(yōu)化問題轉(zhuǎn)化為下面的無邊界優(yōu)化問題。可以證明，原問題等價于求解：

其中，ηnk和gm是緩存策略X的兩個函數(shù)，分別等價于uk下載 fn的時延以及 F-AP緩存容量的限制。

這樣就能把圖2所示的因子圖應(yīng)用于求解式（10）。因為要求解X，所以將變量節(jié)點iμ設(shè)為xnm，而和為X的函數(shù)，因此將它們設(shè)為函數(shù)節(jié)點Fj：

其中，F(xiàn)k是用戶uk所請求的文件的集合，是集合Fk中的元素數(shù)量，ζ (n,k)指的是集合Fk中文件fn的下標(biāo)。因子圖中每個變量節(jié)點iμ都和函數(shù)節(jié)點Fj相連，因此共有NM個變量節(jié)點、個函數(shù)節(jié)點。

圖2 F-AP層因子圖模型

3.3.2 因子圖中的置信度傳播

在因子圖中，每個變量節(jié)點將一個更新后的信息送到一個與它相鄰的函數(shù)節(jié)點中，并收到一個更新后的、發(fā)送自該函數(shù)節(jié)點的信息，在多次迭代之后，就可以計算出尋找優(yōu)化問題的最優(yōu)解。而要做的就是設(shè)計一個信息傳遞算法。用表示從變量節(jié)點發(fā)送到函數(shù)節(jié)點的信息，用表示從函數(shù)節(jié)點發(fā)送到變量節(jié)點的信息。根據(jù)BP算法，信息可以根據(jù)式（16）更新為：

因為式（17）均為連乘，因此為了便于計算，將其化為對數(shù)域：

當(dāng)Fj=ηnk時，信息由式（20）獲得：

當(dāng)Fj=gm時，信息可按式（21）更新：

然后，就能得出指數(shù)域中的置信度比率：

至此，已經(jīng)得到了置信度，只需根據(jù)式（23），就能得出變量節(jié)點的值，為：

算法2 F-AP層分布式算法

設(shè)tmax為足夠大

4 仿真結(jié)果及分析

假設(shè)場景中有M個F-AP，M=10，有K=50個 UE，它們均勻分布在 10個 F-AP范圍內(nèi)。總共有 N個文件，N=100。如前文所述，假設(shè)每個F-AP能夠緩存Qm個文件，每個用戶能夠緩存Qu個文件。

取F-AP到UE的通信鏈路帶寬為30 MHz[12]，每個時隙長度為20 ms，文件平均大小為1 GB。F-AP到UE信道增益在每個時隙上符合標(biāo)準指數(shù)分布。F-AP和用戶層間傳輸平均信噪比為SNR=10 dB，D2D通信平均信噪比SNR=20 dB，從云端下載時延D*=40 s[12]。使用MATLAB軟件進行仿真，結(jié)果如下。

4.1 下載平均時延和F-AP緩存容限Qm

取Qm=10,20,…,90，并保持Qu=10不變，得到圖3。圖3中選擇了基于貪心算法的單層集中式緩存[13]、基于 BP算法的單層分布式緩存（即本文的雙層緩存去掉UE層，將UE層緩存容量加入F-AP層）與本文的雙層緩存對比，設(shè)定3種緩存分布的總?cè)萘慷枷嗤龀隽藭r延性能曲線。雙層緩存對于F-AP的容量要求并不是很高，在Qm較小時也能獲得較大的時延增益。效果明顯優(yōu)于單層緩存布置。同時可以看出，基于BP算法的分布式緩存時延特性基本上與集中式算法相當(dāng)，這得益于BP算法優(yōu)異的性能。

圖3 3種緩存方式的時延性能曲線

4.2 算法復(fù)雜度

為了研究算法的收斂特性，設(shè)Qu=5不變，得到不同Qm的平均時延曲線如圖4所示。從圖4中可以看出，平均時延一開始有一個初始值，接著在迭代過程中不斷改變，最終收斂。算法迭代次數(shù)與Qm取值沒有明顯關(guān)系，在Qu不變時，對于所有的Qm，算法都能在10次左右完成收斂。考慮到UE網(wǎng)絡(luò)的貪心算法復(fù)雜度為，n為UE緩存的文件個數(shù)，通常UE緩存不會太大，因而總的復(fù)雜度依然不高。

圖4 不同Qm的平均時延曲線

4.3 UE緩存容限Qu和時延性能

本文取Qm=40，Qu=1,5,10,15,20，作出了雙層緩存對于基于BP算法的F-AP單層分布式緩存的時延增益，如圖5所示。

圖5 雙層緩存對于基于BP算法的F-AP單層分布式緩存的時延增益

從圖5中可以看出，在Qu很小的情況下，時延增益也能提高 25%～50%，這主要得益于 D2D傳輸?shù)牡蜁r延以及D2D層中的分布式背包算法以及對于權(quán)重的優(yōu)化提高了命中率。

5 結(jié)束語

本文主要研究了集成了D2D通信的霧無線接入網(wǎng)中的緩存分布問題，提出雙層緩存布置的分布式算法，仿真結(jié)果顯示該雙層分布式緩存布置可以顯著降低用戶的下載時延。在將來的研究中，可以考慮實際信道條件或針對鏈路負載、信令開銷等進行優(yōu)化，最終提出可以工程應(yīng)用的緩存分布算法。

參考文獻：

[1] PENG M, YAN S, ZHANG K, et al.Fog Computing based radio access networks：issues and challenges[J].IEEE Network,2016, 30(4)： 46-53.

[2] LIU J, BAI B, ZHANG J, et al.Cache placement in fog-RANs：from centralized to distributed algorithms[J].IEEE Transactions on Wireless Communications, 2017, PP(99)： 1.

[3] DOPPLERK, RINNEM, WIJTINGC, et al.Device-to-device communication as an underlay to LTE-advanced networks[J].Modern Science & Technology of Telecommunications, 2010,47(12)： 42-49.

[4] DOPPLER K, YU C H, RIBEIRO C B, et al.Mode selection for device-to-device communication underlaying an LTE-advanced network[C]//2010 IEEE Wireless Communications and Networking Conference (WCNC), April 18-21, 2010, Sydney,NSW, Australia.Piscataway： IEEE Press, 2010： 1-6.

[5] YU C H, TIRKKONEN O, DOPPLER K, et al.Power optimization of device-to-device communication underlaying cellular communication[C]//2009 IEEE International Conference onCommunications, June 14-18, 2009, Dresden, Germany.Piscataway： IEEE Press, 2009： 1-5.

[6] JANIS P.Interference-aware resource allocation for device-to-device radio underlaying cellular networks[C]//2009 IEEE Vehicular Technology Conference (VTC), April 26-28,2009, Barcelona, Spain.Piscataway： IEEE Press, 2009： 1-5.

[7] GOLREZAEI N, MOLISCH AF, DIMAKISAG.Base-station assisted device-to-device communications for high-throughput wireless video networks[C]//IEEE International Conference on Communications, June 10-15, 2012, Ottawa, ON, Canada.Piscataway： IEEE Press, 2012.

[8] ZHU H, WANG J.Chunk-based resource allocation in OFDMA systems-part I： chunk allocation[J].IEEE Transactions on Wireless Communications, 2009, 57(9)： 2734-2744.

[9] ZHU H, WANG J.Chunk-based resource allocation in OFDMA systems-part II： joint chunk, power and bit allocation[J].IEEE Transactions on Wireless Communications, 2012, 60(2)： 499-509.

[10] CHOI J, JAIN M, SRINIVASAN K, et al.Achieving single channel, full duplex wireless communication[C]//2010 IEEE International Conference on Mobile Computing and Networking (MobiCom), September 20-24, 2010, Chicago, Illinois,USA.Piscataway： IEEE Press, 2010： 1-12.

[11] YIN C, YANG D, ZHAO X, et al.State estimation of active distribution system based on the factor graph analysis and belief propagation algorithm[C]//2017 IEEE International Conference on Environment and Electrical Engineering and IEEE Industrial and Commercial Power Systems Europe (IEEE/I&CPS Europe),June 6-9, 2017, Milan, Italy.Piscataway： IEEE Press, 2017： 1-6.

[12] BAS E, BENNIS M, DEBBAH M, et al.Living on the edge： the role of proactive caching in 5G wireless networks[J].IEEE Communications Magazine, 2015, 52(8)： 82-89.

[13] BASTUG E, BENNIS M, KOUNTOURIS M, et al.Cache-enabled small cell networks： modeling and tradeoffs[J].EURASIP Journal on Wireless Communications and Networking, 2015(1)： 41.