霧無(wú)線接入網(wǎng)中的多層協(xié)作緩存方法

蔣雁翔，夏騁宇,2

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

1 引言

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

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

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

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

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

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

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

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

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

2 系統(tǒng)建模

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

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

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

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

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

2.2 系統(tǒng)模型

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

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

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

3 優(yōu)化問(wèn)題

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

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

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

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

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

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

證明如附錄所示。

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

算法1解決子問(wèn)題1 的貪心算法

算法2解決子問(wèn)題2 的貪心算法

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

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

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

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

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

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

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

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

算法3解決子問(wèn)題3 的貪心算法

算法4解決子問(wèn)題4 的貪心算法

3.3 CU 層緩存分布

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

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

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

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

首先，假設(shè)有500 個(gè)文件，網(wǎng)絡(luò)中有一個(gè)CU，它通過(guò)前傳鏈路連接到2 個(gè)簇的簇頭，每個(gè)簇中有5 個(gè)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è)每個(gè)簇中有50 個(gè)用戶，共100 個(gè)用戶。在每個(gè)簇中，簇頭覆蓋了30 個(gè)用戶，5 個(gè)F-AP 中的每一個(gè)覆蓋5 個(gè)用戶，并且其覆蓋區(qū)域互不重疊。文件of的流行度可以通過(guò)機(jī)器學(xué)習(xí)的辦法獲得，為了便于仿真，假設(shè)和服從Zipf 分布。

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

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

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

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

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

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

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

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

本文主要研究了霧無(wú)線接入網(wǎng)中的緩存布置問(wèn)題。為了降低網(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 能分布式地做出緩存決定，并提出了緩存布置策略。特別地，為了簡(jiǎn)化問(wèn)題，在考慮了層內(nèi)協(xié)作、層間協(xié)作、鏈路容量的基礎(chǔ)上，本文將優(yōu)化問(wèn)題分解為三層內(nèi)的緩存布置問(wèn)題，并分別轉(zhuǎn)化為背包問(wèn)題，采用貪心算法求解。仿真結(jié)果顯示，所提出的多層協(xié)作緩存方法可以顯著降低后傳鏈路負(fù)載。

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

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