陳正勇,楊崇旭,姚 振,楊 堅

(中國科學技術(shù)大學 未來網(wǎng)絡(luò)實驗室, 合肥 230022)

1 引 言

思科預(yù)測全球移動數(shù)據(jù)流量將在2016年和2021年之間增長七倍,并且到2021年每月全球移動數(shù)據(jù)流量將達到49艾字節(jié)[1].為了滿足移動無線網(wǎng)絡(luò)用戶不斷增長的需求,網(wǎng)絡(luò)運營商引入了由密集部署的小基站組成的小基站網(wǎng)絡(luò)[2].在網(wǎng)絡(luò)中利用好緩存能力一般能夠較大地提升網(wǎng)絡(luò)性能[3,4].因此本文考慮使用具有存儲能力的小基站使內(nèi)容更接近終端用戶.與從遠程服務(wù)器獲取內(nèi)容相比,用戶從小基站的本地緩存中獲取內(nèi)容將體驗到更低的延遲和更快的下載速度.小基站網(wǎng)絡(luò)和有線網(wǎng)絡(luò)之間最重要的區(qū)別在于前者的用戶是移動的,一個用戶在下載一個文件的期間可能會經(jīng)過多個小基站.為了有效利用小基站的緩存能力,必須考慮到用戶的移動性.

考慮到一些流行的內(nèi)容通常被不同的用戶多次請求,許多相關(guān)工作以最大化復(fù)用緩存的內(nèi)容為目標來利用基站的存儲資源.文獻[5]在已知用戶對內(nèi)容的偏好以及移動模式的前提下,提出了一個最大化緩存效用的緩存策略.文獻[6]將用戶的移動建模為一個馬爾科夫鏈,以盡可能降低宏基站負載為目的提出了針對小基站內(nèi)容緩存的優(yōu)化策略.文獻[7]在用戶逗留時間服從指數(shù)分布的假設(shè)下,提出了文件在小基站上的分布策略.當小基站中存有部分流行內(nèi)容時,請求這些文件的用戶會獲得更高的QoE.但是請求其他文件的用戶并不能獲得任何QoE上的提高.

為了提高所有用戶的QoE,本文考慮在用戶從當前基站下載所請求的文件時,在用戶接下來有可能接入的基站中預(yù)先緩存部分請求文件.所以當用戶真的接入到某個預(yù)先緩存有部分文件的基站時就能體驗到更低的時延以及更快的下載速度.文獻[8]首次提出了一個稱為數(shù)據(jù)預(yù)取的概念用以將流量從移動網(wǎng)絡(luò)分流到WiFi熱點.文獻[9]在假設(shè)用戶移動信息已知的前提下介紹了一個分布式的主動緩存方案來支持用戶的無縫移動.盡管很多相關(guān)工作注意到在小基站網(wǎng)絡(luò)中用戶移動模式的重要性,但是它們要么假設(shè)用戶移動模式已知[5,9],要么用過于簡單的模型例如馬爾科夫鏈[6,10]預(yù)測用戶的移動.然而,在真實的環(huán)境中,用戶不會提供諸如將在一個基站停留多久以及將會接入哪個基站這樣的信息.顯然對用戶移動預(yù)測的準確性會極大地影響到緩存策略的性能.在本文的實驗中,馬爾科夫鏈模型只能達到21.4%的準確率.所以選擇一個合適的模型從歷史軌跡中學習到用戶移動模式是至關(guān)重要的.

深度學習在圖像處理領(lǐng)域取得的巨大成功使其在近些年得到進一步的發(fā)展.本文采用變分自動編碼器[11]的一個變式來進行軌跡預(yù)測.變分自動編碼器是一個應(yīng)用在潛在變量模型上的生成模型,目前已經(jīng)成為無監(jiān)督學習復(fù)雜分布的最流行的方法之一.用戶的移動取決于他的習慣和環(huán)境,這些因素是一條軌跡的潛在變量.因此,可以認為用戶移動模式是一個潛在變量模型,本文實際上使用條件變分自動編碼器[12],基于用戶已經(jīng)過的N1個基站來估計即將到達的下一個基站的概率分布.根據(jù)調(diào)研,本文是第一個使用生成模型來預(yù)測用戶軌跡的.在真實的GPS軌跡數(shù)據(jù)上,本文所提方案的預(yù)測準確率能達到79.7%.

本文采用編碼緩存來更好地利用緩存資源.Raptor碼[13]能夠?qū)⒁粋€由k個符號組成的文件編碼不斷產(chǎn)生新的符號,用戶只要獲得略大于k個新的符號就能夠還原出原始文件.使用編碼緩存能夠保證緩存下來的內(nèi)容對于用戶總是有效的.本文將緩存效用定義為預(yù)先緩存內(nèi)容中被用戶消費的部分帶來的收益減去預(yù)先緩存內(nèi)容中被浪費的部分帶來的懲罰,并設(shè)計了一個緩存策略來最大化緩存效用.

2 系統(tǒng)模型及問題定義

本文考慮由密集部署的小基站組成的小基站網(wǎng)絡(luò).圖1給出了一個網(wǎng)絡(luò)布局和用戶軌跡的例子,每個正六邊形表示相應(yīng)小基站的覆蓋范圍.本文通過從歷史軌跡數(shù)據(jù)中學習到的用戶移動模型,預(yù)測用戶即將到達的小基站.在用戶從當前基站下載文件的同時,預(yù)測的小基站緩存部分用戶所請求的文件.當用戶接入預(yù)測到的基站時,能以快得多的速度下載文件,從而提高用戶的QoE.當用戶從基站的本地存儲中下載內(nèi)容時產(chǎn)生收益,當用戶錯過了預(yù)測到的基站或者基站緩存了過多內(nèi)容導致用戶在逗留期間沒有下載完時產(chǎn)生懲罰.在這部分中,本文首先做出一些假設(shè),然后描述系統(tǒng)結(jié)構(gòu),最后給出問題定義.軌跡預(yù)測方法將在下一部分介紹.

圖1 網(wǎng)絡(luò)布局和用戶軌跡示例Fig.1 An Example of network layout and user trajectory

2.1 假設(shè)

1)為了更好地利用小基站的緩存容量,本文使用raptor碼編碼被請求的文件.當用戶下載的編碼數(shù)據(jù)略大于原文件大小時就能夠恢復(fù)出原文件.

2)所有被請求的文件大小一樣,表示為fMb.用戶從基站本地緩存下載速度表示為RMbps,從原服務(wù)器下載速度表示為rMbps.因為小基站比原服務(wù)器離用戶更近,所以有R>r.小基站預(yù)緩存文件的速度為rMbps.

3)當用戶下載完預(yù)緩存的內(nèi)容或者錯過了緩存文件的基站時,這些緩存內(nèi)容都可以從基站刪除.并且每個基站只為相鄰基站里的用戶緩存一小部分文件.所以本文認為基站的緩存空間足夠.

2.2 系統(tǒng)結(jié)構(gòu)

為了使本文的系統(tǒng)正常運行,需要一個控制器來收集用戶的軌跡信息和請求信息,同時對預(yù)測到的小基站下達預(yù)緩存指令.每個用戶需要進行注冊,并且配有獨一無二的UID.系統(tǒng)結(jié)構(gòu)如圖2所示.控制器與小基站之間有三種類型的信息交互.

圖2 系統(tǒng)結(jié)構(gòu)Fig.2 System architecture

1)軌跡記錄:控制器使用哈希表記錄系統(tǒng)中所有用戶的近期軌跡.當一個用戶接入一個新的小基站時,小基站將UID和接入的時間戳發(fā)送給控制器.然后控制器將小基站的id和時間戳接入UID所對應(yīng)的表項,如果表項長度達到設(shè)置的閾值,就刪除最早的記錄.

2)請求處理:當用戶需要一個文件時,他向當前接入的小基站發(fā)送一個請求,并且在他下載的過程中,每接入一個新的小基站就發(fā)送一次請求.當一個小基站接到一個請求時,首先向控制器發(fā)送UID和請求的文件名以及時間戳,然后檢查本地緩存,看是否為該用戶緩存部分內(nèi)容.如果有,小基站就從本地緩存向用戶發(fā)送內(nèi)容,否則經(jīng)過骨干網(wǎng)從原服務(wù)器下載內(nèi)容.當控制器接收到請求信息時,根據(jù)該用戶的近期軌跡預(yù)測用戶可能進入的下一個基站.然后控制器對預(yù)測可能性較大的基站下達預(yù)緩存指令.

3)預(yù)緩存:當一個小基站接收到預(yù)緩存指令時,記錄相應(yīng)的UID和文件名,然后從原服務(wù)器下載部分內(nèi)容.

2.3 問題定義

(1)

(2)

(3)

(4)

3 緩存策略

(5)

(6)

(7)

(8)

(9)

公式(9)說明為了最大化E[Ui,s],應(yīng)該在使其偏導大于0的基站j上緩存內(nèi)容,即基站j應(yīng)滿足:

(10)

3.1 軌跡預(yù)測

本文用l1,l2,…,lN表示一個用戶依次經(jīng)過的N個連續(xù)的基站,需要在給定前N-1個基站的條件下預(yù)測第N個基站的位置,即估計概率分布P(lN|l1,l2,…,lN-1).數(shù)據(jù)集中的每一個數(shù)據(jù)都表示為一個向量:

(11)

這些向量是由用戶的習慣和環(huán)境所產(chǎn)生的,因此可以將用戶習慣和環(huán)境看作隱藏變量.將X的前N-1個基站也表示為一個向量:

(12)

本文的目的是估計P(X|Y).使用條件變分自動編碼器,能找到一個分布P(X|Y,z;θ)來逼近一個未知分布P(X|Y),其中z通常是從高斯分布采樣的隱藏變量,θ是學習到的神經(jīng)網(wǎng)絡(luò)的參數(shù).可以將P(X|Y)表示為:

(13)

通過最大化(13)式,在給定Y的情況下神經(jīng)網(wǎng)絡(luò)就能輸出準確的結(jié)果.為了計算(13)式,需要對z進行采樣.但是大部分的z值并不能產(chǎn)生有效的X,所以應(yīng)該尋找z的分布Q(z|X,Y),使服從該分布的z有很大概率會產(chǎn)生相應(yīng)的X.這里,Q(z|X,Y)是P(z|X,Y)的一個估計,將輸入的X編碼為隱變量z,即編碼器;相應(yīng)的P(X|Y,z)為譯碼器.Q(z|X,Y)和P(z|X,Y)的KL散度為:

D[Q(z|X,Y)‖P(z|X,Y)]=Ez～Q(·|X,Y)

[logQ(z|X,Y)-logP(z|X,Y)]

(14)

logP(X|Y)-D[Q(z|X,Y)‖P(z|X,Y)]=Ez～Q(·|X,Y)[logP(X|Y,z)]-D[Q(z|X,Y)‖P(z|Y)]

(15)

如果Q的復(fù)雜度足夠高,那么(15)式左邊第二項會趨近于0.同時假設(shè)P(z|Y)為標準正態(tài)分布,因為只要給出合適的系數(shù)和偏移,可以由標準正態(tài)分布得到任何復(fù)雜的分布,具體參數(shù)由神經(jīng)網(wǎng)絡(luò)和相應(yīng)Y決定.為了最大化P(X|Y),只需要最大化(15)式的右邊.通常將Q(z|X,Y)取為:

(16)

并且限制∑為一個對角矩陣,這樣就能很容易地計算出(15)式右邊第二項.編碼器Q(z|X,Y)和譯碼器P(X|Y,z)都由神經(jīng)網(wǎng)絡(luò)表示,可以利用從Q(z|X,Y)采樣得到的z估計(15)式右邊第一項.為了避免網(wǎng)絡(luò)中出現(xiàn)采樣層以使反向傳播算法能夠起作用,這里采用了再參數(shù)化的技巧采樣.即首先采樣ε～N(0,I),然后計算:

(17)

圖3 CVAE的訓練結(jié)構(gòu)(虛線框內(nèi)為損失函數(shù))Fig.3 Training architecture of CVAE(dotted boxes show loss functions)

圖3和圖4分別畫出條件變分編碼器(CVAE)的訓練和應(yīng)用過程.給定Y和從標準正態(tài)分布采樣的z,本文訓練好的譯碼器能夠產(chǎn)生近似于從P(X|Y)采樣得到的X.當已知用戶當前所在基站和此前經(jīng)過的(N-2)個基站時,能夠通過對z進行足夠多的采樣然后通過譯碼器得到用戶下一到達基站的概率分布.

圖4 訓練好的CVAE的應(yīng)用Fig.4 Application of a trained CVAE

3.2 緩存策略

用戶在需要某文件時發(fā)出請求,然后每次移動到新的基站時發(fā)送一次請求直到下載完成.用戶的每次請求都會觸發(fā)一次預(yù)緩存調(diào)度.本文算法1描述了對第i個請求的第s次預(yù)緩存調(diào)度的過程.前4行的信息很容易通過查詢控制器記錄的信息得到,其中mSojourn是一個數(shù)組,mSojourn[k]表示第k個基站地平均逗留時間.第5行得到用戶在當前基站的平均逗留時間.第6行通過軌跡預(yù)測模型計算出用戶下一個連接基站的概率分布,第7到10行根據(jù)此概率分布選擇進行預(yù)緩存的基站.第11到15行估計用戶能夠在當前基站下載的內(nèi)容大小.第16到18行計算選中的基站應(yīng)該緩存多少內(nèi)容.

算法1.對第i個請求的第s次預(yù)緩存調(diào)度1:計算還需要下載的文件大小fleft2:當前基站緩存內(nèi)容大小為cachedSize3:用戶軌跡Y=[l1l2…lN-1]4:在每個基站統(tǒng)計的平均逗留時間mSojourn5:Ti,scur←mSojourn[lN-1]6:Psi←cvaeTrajectoryPrediction(Y)7:Sf←?8:for allj such that psi,j>βα+βdo9: Sf←Sf∪{j}10:end for11:if cachedSize>R·Ti,scurthen12: f si←R·Ti,scur13:else14: fsi←cachedSize+(Ti,scur-cachedSizeR)·r15:end if 16:for all j such that j∈sfdo17: csi,j←min {fleft-fsi,mSojourn[j]·R}18:end for

4 性能評估

4.1 用戶移動模型

本文使用Geolife[14]項目從182位用戶收集的總共17621條軌跡的GPS軌跡數(shù)據(jù)集.這些軌跡大部分是在中國北京產(chǎn)生的,本文選取其中軌跡最密集的區(qū)域為研究區(qū)域,即經(jīng)度116.3到116.35和緯度39.97到40.02.研究區(qū)域如圖1分為85個正六邊形,每個正六邊形表示一個基站的覆蓋范圍.移除幾乎沒有用戶經(jīng)過的范圍后,得到77個有效基站.一方面,用戶可能到達家里或工作地點,所以有些軌跡中包含逗留時間相當長的點;另一方面,用戶可能在相鄰基站的邊界徘徊,造成軌跡中出現(xiàn)抖動現(xiàn)象.這兩種異常點會對實驗造成影響,所以在這些點處將原軌跡一分為二.得到的數(shù)據(jù)就可以做模型訓練了.

在進行軌跡預(yù)測時,本文將N設(shè)置為5,即在已知軌跡中前4個點的條件下預(yù)測第5個點.每個基站位置表示為一個獨熱向量.隱藏變量z的維度設(shè)置為60.訓練集和測試集分別有15634和3181條長度為5的GPS軌跡.對于測試期間的每個Y(即已知的用戶經(jīng)過的前四個基站位置),本文將z從正態(tài)分布中采樣200次以獲得下一基站的概率分布.

表1是本文所用軌跡預(yù)測模型的準確率.第一列表示概率范圍,第二列表示預(yù)測出的最大概率落于相應(yīng)范圍的預(yù)測數(shù),第三列表示最大概率落在相應(yīng)范圍的預(yù)測的準確率.總體預(yù)測準確率為79.7%,有58%的預(yù)測其最大概率在0.98到1.0之間,這部分的預(yù)測準確率可以達到91.3%.

4.2 實驗

本文緩存策略的核心部分是軌跡預(yù)測模型.很多相關(guān)工作使用馬爾可夫鏈[10]或隨機運動模型[15]建模用戶移動模型.因此本文對比以下三種策略的性能:

表1 CVAE的軌跡預(yù)測準確率
Table 1 Trace prediction accuracy of CVAE

概率范圍次數(shù)準確率0.98～1.0183491.3%0.96～0.9827983.9%0.94～0.9622180.1%0.92～0.949269.6%0.0～1.0318179.7%

1)基于條件變分編碼器的緩存策略(CBS):如算法1所示.

2)基于馬爾可夫鏈的緩存策略(MBS):整體緩存策略如算法1所示,差別是先用訓練集算出概率轉(zhuǎn)移矩陣,然后用該矩陣估計用戶下一接入基站的概率分布,從而部署預(yù)緩存.

3)基于隨機運動模型的緩存策略(RBS):整體緩存策略如算法1所示.這種模型假設(shè)用戶是自由隨機地移動的,所以每次隨機選擇與用戶當前所在基站相鄰的基站進行預(yù)緩存.

本文假設(shè)在所考慮時間段內(nèi),系統(tǒng)一共服務(wù)了300條請求(K=300),每一條請求對應(yīng)于測試集里一條完整軌跡.用戶從基站緩存中下載速度為2MB/s,即R=2MB/s;用戶從原服務(wù)器下載速度為1MB/s,即r=1MB/s.在接下來的實驗中,本文將被用戶消費的單位預(yù)緩存內(nèi)容的效用設(shè)置為1,即令α=1.

圖5 文件大小的影響Fig.5 Influence of file size

在第一組實驗中,本文將浪費的單位預(yù)緩存內(nèi)容的懲罰設(shè)置為1,即令β=1,然后將所請求文件大小由50MB變化到350MB.圖5(a)是三種策略的平均下載速度.當文件較小時,用戶很可能在一個基站就能完成下載,因此預(yù)緩存不能帶來明顯的提升.三種策略的平均下載速度都隨著文件大小增大而提升,這是因為用戶在下載過程中經(jīng)過更多基站,從而獲得更多的預(yù)緩存內(nèi)容,并且本文提出的策略總是具有最高的平均下載速度.本文將緩存命中率定義為被用戶消費的預(yù)緩存內(nèi)容占總的預(yù)緩存內(nèi)容的比值.圖5(b)是三種策略的緩存命中率.RBS的緩存命中率一直比較低,因為不能準確預(yù)測用戶軌跡.CBS和MBS的緩存命中率隨著文件增大而降低,因為隨著用戶經(jīng)歷更多基站,浪費的預(yù)緩存內(nèi)容也一直在累加.本文用call表示所有的緩存內(nèi)容,用cused表示所有被用戶消費的緩存內(nèi)容,那么效用可表示為[α·cused-β·(call-cused)]/(K·f).圖5(c)是三種策略的緩存效用.CBS由于可以準確預(yù)測用戶軌跡,因此比RBS和MBS有高得多的效用.

圖6 β的影響Fig.6 Influence of β

在第二組實驗中,本文將文件大小f設(shè)置為250MB,將β從0.4變化到1.4.根據(jù)算法1,是否在一個基站進行預(yù)緩存取決于用戶接入該基站的概率是否大于p=β/(α+β).該閾值隨β增大而上升.圖6(a)、(b)和(c)分別表示三種緩存策略的平均下載速度、緩存命中率和緩存效用.如表1所示,在大部分情況下CBS預(yù)測的結(jié)果中只有一個基站具有很大的接入概率.所以改變β的值幾乎不影響CBS的平均下載速度和緩存命中率.MBS的平均下載速度隨β增大而減小,這是因為隨著閾值升高,MBS滿足預(yù)緩存要求的基站越少,從而用戶從緩存中獲取的內(nèi)容越少.對于RBS,平均下載速度和緩存命中率都很低,這是因為其預(yù)測準確率過低.因為β增大意味著對于浪費了的緩存內(nèi)容的懲罰加大,所以所有策略的緩存效用都隨著β增大而減小,但是CBS一直具有最高的緩存效用.

5 結(jié) 論

本文提出了一個基于深度學習的具有移動感知能力的預(yù)緩存策略,通過在預(yù)測出的小基站上預(yù)緩存用戶請求的部分文件來提高用戶體驗.首先根據(jù)用戶消費緩存內(nèi)容所產(chǎn)生的收益及浪費掉的緩存內(nèi)容所產(chǎn)生的懲罰,給出了緩存效用的概念.然后本文將所考慮的問題公式化為一個最大化緩存效用的最優(yōu)化問題.接下來本文第一個提出了使用條件變分自動編碼器進行軌跡預(yù)測,并給出了具體緩存策略.本文使用了真實的GPS軌跡數(shù)據(jù)評估所提出的緩存策略的性能,結(jié)果顯示所提出的緩存策略比其他基于現(xiàn)有移動模型預(yù)測軌跡的緩存策略具有更高的平均下載速度和緩存效用.