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

夏騁宇，蔣雁翔

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

1 引言

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

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

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

2 系統(tǒng)模型

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

3 方程建立

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

也就是說(shuō)，如果某個(gè) UE的周?chē)呀?jīng)緩存有文件fn，則它不需要向 F-AP請(qǐng)求文件；若周?chē)鷽](méi)有此文件，則它仍然要向F-AP請(qǐng)求文件。這樣就得到了用戶(hù)向F-AP申請(qǐng)文件的概率。同時(shí)，用戶(hù)向相鄰用戶(hù)申請(qǐng)文件fn的概率為

這樣，通過(guò)D2D下載的總的時(shí)延就可以寫(xiě)為：

其中，dD2D為D2D通信的平均時(shí)延。

從而F-AP層下載的總時(shí)延為：

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

這樣，就得到總時(shí)延的閉式解，為：

類(lèi)似地，可以得到雙層緩存對(duì)單純的 F-AP層緩存的時(shí)延增益的閉式解為：

3.1 UE層緩存分布

3.1.1 文件流行度

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

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

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

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

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

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

其中，緩存率P'ni定義為ui周?chē)丫彺?fn的UE個(gè)數(shù)與UE總數(shù)的比值，即：

3.1.3 UE層分布式緩存算法

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

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

算法1 UE層分布式算法

將Hk降序排列

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

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

3.3 F-AP層緩存分布

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

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

3.3.1 緩存分布的因子圖

為了應(yīng)用BP算法，必須先將上面帶邊界條件的優(yōu)化問(wèn)題轉(zhuǎn)化為下面的無(wú)邊界優(yōu)化問(wèn)題?？梢宰C明，原問(wèn)題等價(jià)于求解：

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

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

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

圖2 F-AP層因子圖模型

3.3.2 因子圖中的置信度傳播

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

因?yàn)槭剑?7）均為連乘，因此為了便于計(jì)算，將其化為對(duì)數(shù)域：

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

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

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

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

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

設(shè)tmax為足夠大

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

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

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

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

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

圖3 3種緩存方式的時(shí)延性能曲線(xiàn)

4.2 算法復(fù)雜度

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

圖4 不同Qm的平均時(shí)延曲線(xiàn)

4.3 UE緩存容限Qu和時(shí)延性能

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

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

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

5 結(jié)束語(yǔ)

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

參考文獻(xiàn)：

[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.