蔣雁翔，夏騁宇,2

（1.東南大學(xué)移動通信國家重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 210096；2.香港科技大學(xué)電子與計(jì)算機(jī)工程系，香港 999077）

1 引言

近年來，移動網(wǎng)絡(luò)中對于多媒體業(yè)務(wù)的需求呈現(xiàn)爆炸式增長，由此帶來的傳輸鏈路負(fù)載，尤其是無線接入網(wǎng)絡(luò)和后傳鏈路中的負(fù)載成為移動運(yùn)營商們亟待解決的問題[1-2]。為了解決這些問題，研究者們提出了許多適用于未來新一代移動通信系統(tǒng)的新型網(wǎng)絡(luò)架構(gòu)及創(chuàng)新的文件傳輸方式[3-7]，其中一種比較流行的方法就是將流行文件緩存在離用戶較近的地方，這種方法主要包括以下2 種方案。

1)在基站部署緩存，以有效降低用戶對于流行內(nèi)容的重復(fù)下載而帶來的后傳鏈路負(fù)擔(dān)，同時(shí)還可以提高移動網(wǎng)絡(luò)的服務(wù)質(zhì)量，如降低時(shí)延等[2-7]。

2)采用新型網(wǎng)絡(luò)的架構(gòu)，將基站小型化，使整個通信網(wǎng)絡(luò)都更加靠近用戶。在霧無線接入網(wǎng)中，有較為分散部署的云節(jié)點(diǎn)（CU,cloud unit）、大量密集部署的小型霧接入點(diǎn)（F-AP,fog access point）等，形成了一種多層的拓?fù)浣Y(jié)構(gòu)。由于減小了接入節(jié)點(diǎn)和用戶的距離，霧無線接入網(wǎng)架構(gòu)可以很有效地提高無線網(wǎng)絡(luò)的區(qū)域頻譜效率及網(wǎng)絡(luò)容量[4-6]。

然而，在對霧網(wǎng)緩存布置的研究中，始終有2 個很重要的問題[4-6]，一是底層的F-AP 緩存容量都較小，無法緩存大量的流行文件；二是F-AP 覆蓋的用戶很少，導(dǎo)致他們產(chǎn)生的文件請求無法反映文件的聚集效應(yīng)，因此無法準(zhǔn)確估計(jì)出在本地流行的文件?？紤]到上述2 個問題，本文基于F-AP 成簇的場景，提出了一種多層協(xié)作緩存方法。單個F-AP覆蓋用戶很少，但是一個F-AP 簇可以覆蓋擁有相似文件喜好的一群用戶（例如一幢寫字樓中的員工、一個體育場中的觀眾等），將F-AP 適當(dāng)成簇，可以通過更多的文件請求更準(zhǔn)確地估計(jì)出文件的本地流行度；而多層的協(xié)作緩存則可以提高系統(tǒng)的協(xié)作度，彌補(bǔ)F-AP 緩存容量小的問題。

本文考慮了在F-AP 成簇的霧無線接入網(wǎng)中的多層協(xié)作緩存，提出了一種有效的緩存布置策略和層間、層內(nèi)的協(xié)作策略。本文的貢獻(xiàn)如下。

1)相對于其他文獻(xiàn)考慮每個F-AP 單獨(dú)緩存，本文考慮F-AP 成簇場景下的多層緩存布置，優(yōu)化問題更為復(fù)雜，但更加具有實(shí)際意義。

2)綜合考慮了傳輸信道容量及多層緩存的協(xié)作機(jī)制，提出了高效的緩存布置及協(xié)作算法，降低整個網(wǎng)絡(luò)尤其是后傳鏈路的負(fù)載。

3)將緩存布置優(yōu)化問題分解為每層內(nèi)的緩存布置子問題，從而簡化了問題求解的復(fù)雜度，并將每層的優(yōu)化問題都轉(zhuǎn)化成背包問題，進(jìn)而采用貪心算法求解。

4)仿真結(jié)果表明，本文提出的多層協(xié)作緩存算法可以顯著降低霧無線接入網(wǎng)中的后傳鏈路負(fù)載及提高緩存命中率。

2 系統(tǒng)建模

2.1 多層緩存架構(gòu)

圖1 展示了一種霧無線接入網(wǎng)中的多層緩存的網(wǎng)絡(luò)模型，其中，CU 為云節(jié)點(diǎn)，ue 為用戶設(shè)備。最頂端為云端，存儲整個系統(tǒng)中的文件庫。CU 有一定容量的緩存，并通過后傳鏈路和云端相連，通過前傳鏈路與網(wǎng)絡(luò)邊緣的F-AP 相連。網(wǎng)絡(luò)邊緣的F-AP 也帶有一定大小的緩存，且形成了很多簇。由于CU 的覆蓋范圍較廣，同一個CU 可以覆蓋多個F-AP 簇。本文將同一個簇中的F-AP 定義為相鄰的，相鄰F-AP 之間可以通過簇頭實(shí)現(xiàn)協(xié)作緩存。而同一個CU 覆蓋下的F-AP 簇間可以通過CU 實(shí)現(xiàn)協(xié)作緩存。如前文所述，網(wǎng)絡(luò)中的CU 和F-AP 都能緩存一些文件，以此來降低用戶下載文件的時(shí)延及重復(fù)從云端下載流行文件所帶來的鏈路負(fù)載。由于CU 和F-AP 的緩存，以及F-AP 簇的存在，整個網(wǎng)絡(luò)形成了一種三層的緩存拓?fù)浣Y(jié)構(gòu)，Tire 0 為CU 層，Tire 1 為F-AP 簇間（通過CU 控制協(xié)作），Tire 2 為F-AP 簇內(nèi)（通過簇頭控制協(xié)作）。

網(wǎng)絡(luò)中每個簇頭都存有一個本簇內(nèi)其他F-AP的緩存文件表，每個CU 都存有一個它所覆蓋的所有簇的緩存文件表，根據(jù)相關(guān)研究，由此帶來的負(fù)載可以忽略不計(jì)。這樣，簇頭就能為簇內(nèi)的其他F-AP 做出緩存決定。CU 則可以為每個簇做出緩存決定，并控制簇間的協(xié)作。用戶向F-AP 申請文件時(shí)，F(xiàn)-AP 首先檢查本地緩存，如果文件在本地緩存中，則直接發(fā)送給用戶；如果本地沒有緩存，F(xiàn)-AP 則會將申請發(fā)送到簇頭，如果簇頭仍沒有緩存，簇頭會控制簇內(nèi)其他F-AP 協(xié)作；若整個簇內(nèi)都沒有緩存此文件，則簇頭會將申請發(fā)送到CU，如果在CU 仍沒有命中，則CU 會控制其他簇的協(xié)作；如果CU 覆蓋的所有簇內(nèi)都沒有緩存這個文件，則從云端下載。

圖1 霧無線接入網(wǎng)中的多層緩存網(wǎng)絡(luò)模型

本文假設(shè)文件的流行度變化很慢，系統(tǒng)可以在負(fù)載較低的時(shí)候（例如深夜）緩存那些流行文件。由于一段時(shí)間內(nèi)文件的流行度可以看成是固定不變的，本文不考慮更新文件所帶來的負(fù)載。文件的流行度可以通過機(jī)器學(xué)習(xí)及分析用戶的行為或偏好等得到[4]，因此本文假設(shè)文件流行度是已知的。

2.2 系統(tǒng)模型

本文在建模中考慮只有一個CU 的系統(tǒng)，包括一個CU、M個簇，第m個簇中有Nm個F-AP。Q0表示CU 的緩存容量，{Q1,Q2,Q3,…,Qm,…,QM}表示M個簇的緩存容量，{Qm1,Qm2,Qm3,…,}表示第m個簇中的F-AP 的緩存容量。表示第m個簇中的第n個F-AP，和簇頭之間的鏈路容量，Cm為第m個簇和CU 之間的鏈路容量。

假設(shè)系統(tǒng)中共有F個文件，用{o1,o2,o3,…,of,…,oF}表示。考慮到實(shí)際情況，所有文件的大小都是不相同的，用{s1,s2,s3,…,sf,…,sF}表示文件的大小。第m個簇中的F-AP 的緩存布置由一系列二值數(shù)表示，例如=1表示文件of緩存在沒有緩存。類似地，表示M個簇頭中的緩存布置。一旦F-AP 層的緩存布置確定后，F(xiàn)-AP 簇內(nèi)的緩存布置也就確定了。定義λmn、λm、λ0分別為文件請求到達(dá)、第m個簇頭及CU 的平均到達(dá)率。需要注意的是，到達(dá)第m個簇頭的文件請求可能來自簇頭本身覆蓋的用戶或者簇內(nèi)的F-AP。因此，本文定義mβ為簇頭m的用戶發(fā)送的文件請求的平均到達(dá)率。對文件of的請求在及簇頭m的到達(dá)率分別為。考慮到簇頭m處對文件of的請求可能來自直接相連的用戶，也可能來自簇內(nèi)的F-AP，因此定義為簇頭m的用戶對文件of的請求的到達(dá)率。定義文件of在處的流行度和歸一化流行度分別為，類似地，簇頭m的用戶申請文件of的流行度定義為。因此，可以得到

本文假設(shè)文件的全局流行度{P1,P2,P3,…,Pf,…,PF}滿足Zipf 分布，顯然有。

3 優(yōu)化問題

本節(jié)研究文件的最優(yōu)緩存策略，從而減小網(wǎng)絡(luò)后傳鏈路的負(fù)載。由于整個系統(tǒng)涉及文件在三層緩存中的縱向分布及每層內(nèi)的橫向分布，較為復(fù)雜，因此，考慮將優(yōu)化問題分解為三層內(nèi)的緩存分布問題，并分別求解。

3.1 F-AP 簇內(nèi)協(xié)作緩存

對于用戶發(fā)出的文件請求，如果本地的F-AP正好緩存了被請求的文件，則請求可以被立即滿足；如果簇內(nèi)其他F-AP 緩存了這個文件，則文件請求會被發(fā)送到簇頭，再由簇頭控制簇內(nèi)協(xié)作，實(shí)現(xiàn)用戶的下載。

在不同F(xiàn)-AP 簇中的協(xié)作是可以同時(shí)進(jìn)行、互不干擾的，因此，得到如式(6)所示的優(yōu)化問題來表示第m個簇中的協(xié)作。

式(7)限制了每個F-AP 中緩存的文件大?。皇?8)和式(9)限制了F-AP 和簇頭之間的信道容量；式(10)限制了若本地F-AP 緩存了被請求文件，則協(xié)作不會發(fā)生；式(11)限制了每次最多只會有一個F-AP 與請求文件的F-AP 協(xié)作，而不會出現(xiàn)多個F-AP 同時(shí)向請求文件的F-AP 傳輸，避免了重復(fù)傳輸帶來的資源浪費(fèi)。

式(10)和式(11)可以分別通過放縮轉(zhuǎn)化為線性不等條件，而且可以證明，這種轉(zhuǎn)化是等價(jià)的，即式(10)和式(11)分別等價(jià)于式(12)和式(13)。

證明如附錄所示。

這樣，優(yōu)化問題就變成了一個整數(shù)線性規(guī)劃問題，這是一個NP-hard 問題，考慮到其指數(shù)式的復(fù)雜度不可能求得它的最優(yōu)解。因此，本文參考主元的思想，提出一種較為簡單的算法，希望求得該優(yōu)化問題的次優(yōu)解。首先，將優(yōu)化問題分成2 個子問題，具體如下。

算法1解決子問題1 的貪心算法

算法2解決子問題2 的貪心算法

3.2 F-AP 簇間協(xié)作緩存

簇頭處的文件請求包含了簇頭用戶發(fā)送的文件請求及簇內(nèi)F-AP 發(fā)送的文件請求。

因此，定義增益函數(shù)的表達(dá)式為

其中，η（0≤η≤1 ）是本文引入的一個系數(shù)，用于表征CU 所控制協(xié)作的成功率，η越小，則越大，表示協(xié)作的成功率越高。例如，當(dāng)η=0時(shí)，有，這時(shí)簇頭m能與所有請求此文件的簇協(xié)作；而當(dāng)η=1 時(shí)，，簇間沒有協(xié)作發(fā)生。由此可得簇間協(xié)作的優(yōu)化問題為

其中，式(21)限制了簇頭的緩存容量；式(22)和式(23)保證了當(dāng)本簇中已經(jīng)緩存了被請求文件時(shí)，就不會再向其他簇請求文件。顯然式(20)也是一個整數(shù)線性規(guī)劃問題，同樣也是NP-hard 問題。與3.1 節(jié)類似，本文依然希望采用貪心算法求出次優(yōu)解。

首先，式(20)所示的問題可以展開為

式(20)可以進(jìn)一步被分解成2 個子問題，即子問題3 和子問題4。

與3.1 節(jié)類似，提出求解子問題3 和子問題4的貪心算法，如算法3 和算法4 所示。算法3 和算法4 的總體復(fù)雜度為O(FM2lb(FM2))。

算法3解決子問題3 的貪心算法

算法4解決子問題4 的貪心算法

3.3 CU 層緩存分布

通過上述的分析，得到了F-AP 簇內(nèi)的緩存分布、協(xié)作方式，以及簇頭的緩存分布和簇間協(xié)作方式。因此，可以得到從簇層到達(dá)CU 層的文件請求到達(dá)率，如式(28)所示。

類似地，對于CU 層的緩存分布同樣可以找到優(yōu)化問題來最大化鏈路容量，如式(29)所示。

其中，xf表示CU 層的緩存分布，xf=1表示文件of被緩存在CU 中，否則表示沒有被緩存在CU 中。CU 層的優(yōu)化問題是一個簡單的背包問題，本文用復(fù)雜度很低的背包算法[8]來解決。

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

首先，假設(shè)有500 個文件，網(wǎng)絡(luò)中有一個CU，它通過前傳鏈路連接到2 個簇的簇頭，每個簇中有5 個F-AP。同時(shí)，假設(shè)F-AP、簇頭、CU 的緩存大小關(guān)系為Qmn:Qm:Q0=1:4:10；假設(shè)每層之間的鏈路容量為=1Gbit/s，Cm=2 Gbit/s，系數(shù)η=0.9。

為了便于仿真，假設(shè)每個簇中有50 個用戶，共100 個用戶。在每個簇中，簇頭覆蓋了30 個用戶，5 個F-AP 中的每一個覆蓋5 個用戶，并且其覆蓋區(qū)域互不重疊。文件of的流行度可以通過機(jī)器學(xué)習(xí)的辦法獲得，為了便于仿真，假設(shè)和服從Zipf 分布。

為了便于橫向比較算法性能，本文選取了另外2 種緩存分布算法：部分協(xié)作的多層緩存算法[9]和基于BP（belief propagation）算法的分布式緩存算法[10]，具體如下。

1)部分協(xié)作的多層緩存算法。這種算法也是一種多層緩存布置算法，與本文所提算法的區(qū)別在于這種算法沒有考慮層內(nèi)的緩存協(xié)作，只有層間的協(xié)作。

2)基于BP 算法的分布式緩存算法。這種算法中只有最底層的F-AP 帶有緩存，采用了置信度傳播算法，使每個F-AP 可以獨(dú)自做出緩存決定。根據(jù)其主要思想，將這種算法應(yīng)用到本文的模型中，并進(jìn)行仿真，便于同本文算法進(jìn)行比較。

4.1 緩存總?cè)萘亢途彺婷新实年P(guān)系

本文分別改變緩存布置算法中緩存總?cè)萘康拇笮?，對于本文算法、本文算法中只有某一層協(xié)作、部分協(xié)作式多層緩存、基于BP 算法的單層緩存分別繪制了緩存命中率和緩存總?cè)萘康年P(guān)系曲線，如圖2 所示。在本文算法中，當(dāng)緩存總?cè)萘恐徽嫉轿募偞笮〉?0%時(shí)，命中率就已經(jīng)達(dá)到了51.8%，此時(shí)，對于部分協(xié)作式多層緩存和基于BP 算法的單層緩存，本文提出的算法分別有16.5%和11.5%的提高，這是由于本文的緩存中同時(shí)存在垂直方向和水平方向的協(xié)作。而觀察本文算法中只有某一層協(xié)作時(shí)的性能曲線，可以發(fā)現(xiàn)，最底層F-AP 層（Tire 2）的協(xié)作對于系統(tǒng)命中率的增益最大，而簇間（Tire 1）協(xié)作的增益較小，但相對于部分協(xié)作式多層緩存，在緩存總?cè)萘繛?0%時(shí)都至少有12.4%的增益。仿真結(jié)果顯示，當(dāng)緩存容量在較小的范圍內(nèi)增長時(shí)，本文算法的命中率提高速率也是最快的，這是因?yàn)楸疚乃惴ㄍㄟ^整個簇內(nèi)用戶的申請來估算流行度，這樣得到的流行度要比另外2 種算法更為精確。

圖2 各算法緩存總?cè)萘颗c緩存命中率關(guān)系

4.2 緩存容量和后傳鏈路負(fù)載關(guān)系

本文分別改變3 種算法中緩存容量的大小，繪制了后傳鏈路負(fù)載與緩存容量的關(guān)系曲線，如圖3 所示。在本文算法中，當(dāng)緩存總?cè)萘繛榭偽募笮〉?15%時(shí)，后傳鏈路負(fù)載已經(jīng)降低為40.9%，增益明顯高于另外2 種算法，這主要是因?yàn)楸疚牡乃惴ㄒ肓烁叩膮f(xié)作度，因此，更充分地利用了CU 到簇的前傳鏈路，有效降低了后傳鏈路的負(fù)載。

圖3 緩存總?cè)萘亢秃髠麈溌坟?fù)載關(guān)系

4.3 鏈路使用率和申請次數(shù)的關(guān)系

本文將緩存總?cè)萘抗潭槲募偞笮〉?%，通過改變用戶的申請次數(shù)，繪制了不同申請次數(shù)下，不同層內(nèi)的鏈路占用率和申請次數(shù)的關(guān)系，如圖4 所示。從圖4 中可以看出，簇內(nèi)傳輸鏈路的占用率始終高于簇間傳輸鏈路占用率，這是因?yàn)榇貎?nèi)F-AP 層的水平協(xié)作、簇頭和F-AP 的垂直協(xié)作及簇間協(xié)作后傳輸?shù)紽-AP 都需要占用簇內(nèi)傳輸鏈路。在申請數(shù)量在1.0×104次以上時(shí)，兩層的鏈路使用率都在90%以上，這表示這種算法的協(xié)作機(jī)制十分有效；當(dāng)申請數(shù)量繼續(xù)增加時(shí)，兩層的鏈路占用率最終都達(dá)到了100%，協(xié)作度達(dá)到最大。但是由于緩存總?cè)萘恐挥形募偞笮〉?%，無法緩存所有流行文件，所以，此后后傳鏈路的負(fù)載將會快速增加。

圖4 鏈路使用率和申請次數(shù)關(guān)系

5 結(jié)束語

本文主要研究了霧無線接入網(wǎng)中的緩存布置問題。為了降低網(wǎng)絡(luò)的后傳鏈路負(fù)載以及提高鏈路利用率，本文提出了CU 層、F-AP 簇間、F-AP 簇內(nèi)的多層協(xié)作緩存方法，使F-AP 簇內(nèi)緩存可以在簇頭的指導(dǎo)下協(xié)作，F(xiàn)-AP 簇間可以在CU 的指導(dǎo)下協(xié)作，而CU 能分布式地做出緩存決定，并提出了緩存布置策略。特別地，為了簡化問題，在考慮了層內(nèi)協(xié)作、層間協(xié)作、鏈路容量的基礎(chǔ)上，本文將優(yōu)化問題分解為三層內(nèi)的緩存布置問題，并分別轉(zhuǎn)化為背包問題，采用貪心算法求解。仿真結(jié)果顯示，所提出的多層協(xié)作緩存方法可以顯著降低后傳鏈路負(fù)載。

附錄 式(10)、式(11)與式(12)、式(13)等價(jià)的證明

證明式(10)、式(11)到式(12)、式(13)的轉(zhuǎn)化是等價(jià)的。