一種離散分布的移動感知緩存策略

楊崇旭，陳正勇，楊 堅

(中國科學技術大學 未來網(wǎng)絡實驗室，合肥 230022)

1 引 言

近年來，隨著各種網(wǎng)絡應用的迅猛發(fā)展，業(yè)務模式向移動端傾斜，移動設備與通訊正在逐漸取代自互聯(lián)網(wǎng)誕生以來主導互聯(lián)網(wǎng)的fixed-host/server通訊模型，根據(jù)《2016年愛立信移動市場報告》[1]，移動數(shù)據(jù)流量從2016年到2021年間將以47%的復合年增長率(CAGR)增長.便攜式移動終端的日益普及和物聯(lián)網(wǎng)終端數(shù)量的爆炸式增長對網(wǎng)絡的移動性提出了更高要求，用戶終端移動性導致數(shù)據(jù)傳輸路徑頻繁變換，嚴重破壞了上層應用服務的連續(xù)性，影響了IP網(wǎng)絡用戶的服務質量，亟需在新型智慧網(wǎng)絡中對移動數(shù)據(jù)進行優(yōu)化.

本文核心思路是在新型智慧網(wǎng)絡中搭建用戶感知層，通過用戶集體行為與個體移動特征相結合，分析用戶移動行為，從而有針對性地對用戶請求的文件進行分布式部署.結合當前已有的新型網(wǎng)絡架構方案，選擇在小基站網(wǎng)絡[2]中進行移動感知的分布式緩存策略研究，因為小基站網(wǎng)絡是一種新型3G/4G宏蜂窩性能補充的網(wǎng)絡架構，特點是體積小、能耗低，是目前網(wǎng)絡研究領域的一個主流方向，且對移動數(shù)據(jù)處理的需求極高.本文策略是通過感知用戶的移動規(guī)律，將其需求的內容提前部署在合適基站上，從而大幅度提高緩存部署的命中率，降低對骨干網(wǎng)的回程壓力，減少用戶下載文件的時延.

在目前已有的緩存部署策略中，如Femto caching[3]，雖然做了很多關于緩存部署策略的研究，但是都沒有考慮用戶的移動特征；在Sprinkler中[4]，考慮了移動特征進行緩存部署，提出了不少啟發(fā)性的想法，比如沿著用戶軌跡將文件分割部署在多個基站上，但是其也忽略了很多問題，比如它假設了軌跡已知，也忽視了在每個基站中逗留時間的問題；在Mobicacher中[5]，它的思路是假設已知用戶請求的文件或網(wǎng)絡須向其主動推送的文件，然后對多個用戶的軌跡進行預測，考慮文件的重復使用，對文件進行部署，但其缺點是過多地依賴馬爾可夫位置預測算法的準確性，而事實上這個準確性并不可靠，并且Mobicacher試圖一次預測之后多個時刻的位置，其誤差會變得更大，因此在其基礎上做出的緩存部署策略并不可靠，另外，Mobicacher存在一個很大的弊端，其部署策略是非在線不能更新，僅僅能部署一次，無法根據(jù)用戶軌跡的變化及時更新部署方式.

針對以上問題，本文針對性提出了一種離散分布的移動感知緩存策略(Distributed Mobility-Aware Cacher，DMACacher)，策略流程如、所示，主要思路是結合集體的移動軌跡特征，分析用戶下一步可能到達的位置集，用集合的概念代替單一位置保證基于馬爾科夫預測的準確性，另一方面分析用戶在當前基站的逗留時間，盡可能地按逗留時間將文件分布在多個基站上.

圖1 離散分布的移動感知策略流程圖

首先，利用數(shù)據(jù)挖掘分析人類的行為模式，從大規(guī)模的移動軌跡數(shù)據(jù)庫中挖掘出用戶移動趨勢和逗留時間特征分別建立軌跡特征預測模型(Predictive Trajectory Feature Model，PTF-Model)和逗留特征擬合模型(Sojourn Time Fitting Model，STF-Model).其中，利用PTF模型分析用戶的移動軌跡特征，計算出一系列可能到達的位置，按照概率大小排列組成可達位置集；根據(jù)STF模型，預測出發(fā)生移動的具體時間，用于決策推送到當前基站的文件大小.當在任意時刻，服務器收到用戶文件下載的請求(或根據(jù)流行度等決定向用戶主動推送文件)，遠端服務器用RaptorQ碼編碼該文件，將編碼符號集并依概率部署在多個小基站上，用戶從基站群中接收并解碼文件，通過網(wǎng)絡編碼保證用可達位置集代替單一位置緩存的可行性.在用戶到達新的位置后，將其添加到軌跡信息中，迭代更新預測下一個可達位置集，并等待用戶下一次的文件請求.這里一次部署的文件尺寸限定在經(jīng)過兩個基站可下載完畢的約束下，如文件過大，將其分割，剩余部分在用戶到達下一個位置后，調用DMACacher重新對其進行部署.

在下文中，將具體介紹討論DMACacher的每一步實現(xiàn)方式，并對其進行理論上的性能分析，最后進行仿真實驗與Mobicacher等方法比較.

2 建立軌跡特征預測模型

隨著移動終端規(guī)模地日益增大，建立具有移動感知功能的新型智慧網(wǎng)絡愈顯重要，而本文的第一項工作就是建立PTF模型.關于位置預測，目前已有一些基于離散時間馬爾科夫鏈的成果，比如馬爾科夫模型(Markov Model)[6]，隱馬爾科夫模型(Hidden Markov Model)[7,8]，混合馬爾科夫模型(Mixed Markov Model)[9,10].結合本文場景，分析三種方法可以發(fā)現(xiàn)，MM僅僅簡單地將所有移動用戶考慮為一類人，未考慮不同人群間的移動差異性；HMM將用戶所在位置設為可觀狀態(tài)，將用戶的目標位置設為不可觀狀態(tài)，而在不可觀狀態(tài)的轉移過程中無法滿足不同位置在地理上的連續(xù)性約束；MMM則是在MM的基礎上，考慮到了不同人群間的差異性，為每一類人群單獨建立一個馬爾科夫鏈，而對每個個體考慮了其歸屬于不同人群的可能性.綜上考慮，選擇用MMM建立PTF模型.

第一步，考慮所有可以接入的無線基站組成基站集S={S1，…，Sssum}，將移動用戶z所接入的無線基站s∈S當做可觀狀態(tài)，用戶在不同基站間的移動過程描述為一階馬爾科夫鏈的狀態(tài)轉移過程.令矢量tracez表示用戶的的移動軌跡，trz，x表示軌跡tracez中經(jīng)過的第x個基站，則有

tracez=trz，1→…→trz，|tracez|

(1)

trz，x∈S，x=2，…，|tracez|

(2)

第二步，將所有移動用戶組成的集合Z={1，2，…，Zz-sum}依據(jù)人群間的移動特征相似性進行分類，令類別總數(shù)為K，即有

Z1∪Z2∪…∪ZK=Z

(3)

Zk∩Zk′=φ

(4)

值得注意的是，對于每一類人群都有一個特定的轉移概率矩陣進行描述，在模型初建之時，并不需要指定某一個用戶歸屬于某一類別，也不需要指定每個類別的段尺寸P(Zk)，其中段尺寸的定義是隨機挑選的某個移動用戶恰好歸屬于類別Zk的概率.

第三步，將每一個類別的轉移概率矩陣表示成：

i，j∈{1，…，ssum}，k∈{1，…，K}

(5)

第四步，針對含未知參數(shù)的轉移概率矩陣求解問題，選擇用最大期望算法(Expectation-maximization algorithm，EM)[11]進行計算.

(6)

③用②求得的最大似然估計值更新參數(shù)：

(7)

(8)

其中用Sij表示從狀態(tài)Si轉移到狀態(tài)Sj的次數(shù).

④將③中更新的參數(shù)代入②中重復計算，不斷迭代直至收斂.

1≥ρ1≥ρ2≥ρ3≥…

(9)

Ψ1≤∑ρi≤1

(10)

3 逗留特征擬合模型

根據(jù)上文所述，已經(jīng)獲得了可達位置集和對應的轉移概率集，然而據(jù)此作緩存部署還需解決逗留時間問題，因為PTF模型得到的結果是時間離散的，它只能預測出可能到達的位置，而無法同時估測出發(fā)生移動轉移的時間點.逗留時間所帶來的誤差也是目前大部分移動緩存部署策略所忽視的問題.目前已有一些工作針對用戶逗留特征進行了研究，文章[12]通過大量實驗發(fā)現(xiàn)用戶的逗留特征符合冪次定律，文章[13]則進一步地從理論上論證了該規(guī)律.結合本文緩存部署的場景，考慮使用冪次定律來擬合逗留特征，按逗留特征將文件大致分割成兩部分部署在當前基站和可達位置集中.定義函數(shù)G(t)表示用戶在t時刻依然逗留在該基站的概率，其中t=0表示用戶接入基站的時刻，則STF模型可以表示為：

G(t)=a×tb+c

(11)

用t0表示用戶向遠端服務器請求文件M的時刻，當然也可以理解為由主動推送服務器決策向用戶推送文件M的時刻，至于具體請求/推送內容的不是本文重點分析的對象，不在此處贅述.假設用戶的文件下載速率為常數(shù)V MB/S，則理論上用戶如果不離開該基站所需的下載完成時間tend滿足.

(tend-t0)×V=M

(12)

設用戶真實離開時間為tl，理論離開時間為tl′.用事件A和事件B分別表示用戶離開基站發(fā)生在時間點tl′前和時間點t0前，則用戶在時間t0到tl′之間離開的概率ρ0的計算公式為：

(13)

其中Ψ2是判定離開是否發(fā)生的閾值，借此可以計算出用戶理論離開時間tl′：

tl′=G-1[G(t0)×(1-Ψ2)]

(14)

4 分布式緩存緩存

4.1 RaptorQ編碼文件

考慮到要將文件分割部署在多個基站上，并可以使用戶從多個基站中恢復源文件，因此選擇用網(wǎng)絡編碼的方式對文件進行分割.而在編碼理論中，噴泉碼是最高效的編解碼算法，其可以從任意N′個編碼符號中恢復原始的N個源符號從而提供可靠傳輸[14].而目前的噴泉碼中性能最好的是Raptor碼，它的編解碼過程僅需要很少的常數(shù)量級的XOR操作，即在線性時間內即可完成[15]，其中RaptoQ碼是Raptor碼中目前性能設計最好的一個版本[16]，它有諸多優(yōu)點比如：

①只要用戶接收到任意足夠多的編碼符號，即可恢復出源文件，并且恢復概率極高如表1所示.

表1 RaptorQ編解碼恢復概率表

②RaptorQ屬于系統(tǒng)碼，它的源符號是包含在編碼符號中的，而恢復概率和接收到的編碼符號具體歸屬于哪一部分無關.

圖2 RaptorQ編碼示意圖

結合本文所需編碼的文件M來分析，如圖3所示，首先計算單次DMACacher所能處理的文件尺寸閾值M′，

(15)

圖3 文件編碼流程圖

4.2 依概率分布式緩存

如果tend≤tl′，則認為文件可以在用戶離開基站之前完成傳輸，即將全部的N個編碼符號部署在基站tracez，x中.

如果tend≥tl′，則認為文件無法在用戶離開基站之前完成傳輸，需要將全部編碼符號分別部署在多個基站上.其中，先產(chǎn)生的N0個編碼符號部署在基站tracez，x上，

N0?[(tl′-t0)×ν]

(16)

N′=N-N0=N1+N2+N3+…Nζ

(17)

Ni=「ρi×N′?

(18)

(19)

4.3 緩存部署命中率

(20)

②當t0≤tl≤tend≤tl′時，N個編碼符號全部部署在tracez，x中，且離開基站發(fā)生在完成傳輸之前，此時命中率為

(21)

(22)

④當t0≤tl′≤tend≤tl時，部署在trz，x中的編碼符號個數(shù)為N0，且傳輸完成發(fā)生在真實離開之前，此時命中率為

(23)

⑤當t0≤tend≤tl′≤tl或t0≤tend≤tl≤tl′時，N個編碼符號全部部署在trz，x中，且在離開基站前完成了傳輸，此時命中率為

R=1

(24)

5 實驗驗證與分析

實驗中，首先挑選合適的用戶移動軌跡數(shù)據(jù)庫，根據(jù)軌跡數(shù)據(jù)訓練軌跡特征預測模型，然后根據(jù)軌跡提取出時間信息并擬合逗留特征模型，通過Matlab仿真對本文提出的策略進行性能驗證，并與其它多種算法進行性能比較.

5.1 實驗數(shù)據(jù)集

實驗中采用的原始數(shù)據(jù)是微軟亞洲研究院從2007年到2012年間采集的182位用戶的GPS軌跡信息，共17621條原始數(shù)據(jù).該數(shù)據(jù)集的軌跡是遍布在中國、美國和歐洲，其中大部分集中在北京市區(qū)，為了更好建立模型，選取東經(jīng)116.25°到116.5°，北緯39.85°到40.05°區(qū)域之間(大致范圍屬于北京市區(qū))的8181條軌跡數(shù)據(jù)，每條軌跡長度不大于10.將選取出的區(qū)域按照經(jīng)度間隔0.01°，緯度間隔0.01°均分成多個方形小網(wǎng)格，除去所有軌跡都未經(jīng)過的網(wǎng)格，共獲得106個小網(wǎng)格區(qū)域，而這里將每一個小網(wǎng)格抽象為一個基站的覆蓋范圍.

5.2 訓練軌跡特征預測模型

從采集到的8181條軌跡中，隨機挑選4000條用來訓練軌跡特征預測模型.綜合考慮實驗效果和計算性能，將訓練中需要預先設計好的用戶類別總數(shù)K設為100.

表2 可達位置集的命中數(shù)和命中率

訓練好模型后，另外隨機挑選500條軌跡對模型預測能力進行驗證.對每條軌跡，輸入前3個基站，預測第4個基站，并與真實的到達第4個基站比較；再輸入前4個基站，繼續(xù)預測下去直至軌跡結束.其中每一次預測獲得一個大小為5的可達位置集.統(tǒng)計全部可達位置集的命中率如表2所示，可以發(fā)現(xiàn)，可達位置集總命中率可以達到88.8%，一號預測的命中率達69.6%.而五號預測的命中率為0，表示MMM的方法在本實驗中已經(jīng)達到了其預測能力的上限.

5.3 擬合逗留規(guī)律

計算并統(tǒng)計出8181條軌跡所包含的每個基站的逗留時間，按照公式(11)擬合.擬合結果如圖4所示，擬合函數(shù)為

G(t)=1.742×t-0.3091-0.1206

(25)

和方差為4.178，標準差為0.032.

5.4 緩存部署與性能分析

這里采用Matlab進行仿真實驗，設定網(wǎng)絡傳輸速率固定為1M/S，而1M大小文件可以用RaptorQ編碼為1000個編碼符號，考慮用戶在任意時刻請求不同大小的文件，文件尺寸小于單次部署的尺寸限額，采用離散分布的移動感知緩存策略進行編碼符號的部署，分析其部署的命中率，并與其他幾種部署方法比較命中率和開銷.選擇的對比算法包括：

圖4 逗留特征擬合模型

①Mobicacher，即將請求的文件全部推送在按馬爾科夫方法計算出的最大概率的下一個基站上.由于此處比較的是部署性能的優(yōu)缺，故實驗中用本文的軌跡特征預測模型獲得的最大概率預測位置替代了Mobicacher中的馬爾科夫方法，而事實上本文模型所基于的混合馬爾科夫的準確率遠高于馬爾科夫方法.

②Sprinkler，即將文件分割部署在沿途的基站上.但Sprinkler方法是假設已知固定軌跡并且沒有考慮逗留時間，因此在實驗中簡化為將文件前一半部署在當前基站，后一半部署在下一個預測位置上.

③Noon-strategy，不采用任何部署策略，即服務器收到用戶請求后將文件全部推送到用戶當前所在基站上.

5.4.1 命中率分析

比較四種部署方法在請求不同大小文件時的命中率如圖5所示，其中，Mobicacher在請求較小文件時命中率極低，因為它將文件全部部署在了下一個位置，而用戶逗留在當前基站所需的數(shù)據(jù)包全部未命中，隨著請求的文件變大，其部署在下一位置的命中比例也隨之升高，但由于馬爾科夫提供的下一個位置的準確度只有69.6%，所以基于馬爾科夫方式的Mobicacher的命中率無法超過69.6%，而在實驗限定了文件小于1000MB的場景下，最高只能達到60.6%的命中率.Sprinkler 本質上是一種折中的部署策略，在沒有分析逗留時間的情況下，將文件固定拆分成兩部分押注在兩個基站上，所以其命中率的峰值出現(xiàn)在文件大小恰好適合對半拆分的時候，而其中押注的一個基站還要受約于馬爾科夫的準確度限定，所以其命中率穩(wěn)定且較低，均值為49.3%.而僅將文件全部推送到用戶當前所在基站上的部署方式，會隨著文件尺寸變大而不斷減小，直至逼近于0，實驗中由于用戶請求文件的時刻是隨機的，所以始終保持著一定的命中率，最低為15.7%.

而本文的DMACacher算法是將文件按逗留特征擬合模型分割成兩部分，前一部分部署在當前基站上，后一部分借助RaptorQ編碼部署在可達位置集上，前一部分的誤差主要由于逗留特征擬合模型的誤差導致，當文件較小時，該部分誤差較小，文件大部分都部署在了當前基站，故其命中率較高，當文件變大時，擬合誤差隨之增大導致DMACacher算法整體命中率下降；而后一部分的誤差決定于馬爾科夫準確性，這里由于采用可達位置集替代單一的位置預測，因此，其馬爾科夫準確性約束為整個可達位置集的總命中率88.8%，在實驗中最低命中率為67%，遠大于其他幾種算法.通過命中率的比較，反映出DMACacher算法可以更加合理地部署緩存資源.

圖5 四種算法的緩存命中率比較

5.4.2 資源開銷分析

在這一部分，考慮轉發(fā)造成的資源損耗進一步地分析不同算法間的性能差異，這里的資源損耗主要代表對骨干網(wǎng)的回程壓力和用戶的下載時延.

圖6 四種算法的資源開銷比較

四種算法資源開銷如圖6所示，可見四種算法在實驗場景下隨著下載文件變大，開銷呈近線性增加，通過線性擬合可知DMACacher的斜率為288500，Mobicacher斜率為303600，Sprinkler斜率為429000，Non-strategy的斜率為622800，可見DMACacher的資源消耗量和消耗增長速率遠低于其他三種算法.分析其本質原因是，DMACacher通過RaptorQ使多端存儲轉發(fā)成為可能，在數(shù)據(jù)包未命中時無須向遠端服務器請求數(shù)據(jù)包從而大大降低了網(wǎng)絡資源的開銷.

6 結 論

本文針對當前移動數(shù)據(jù)流量爆炸式增長的現(xiàn)狀，在小基站網(wǎng)絡中，搭建對用戶移動行為的智能感知層，通過集體行為與個體移動特征相結合的方式建立軌跡特征預測模型，對用戶軌跡進行預測，并采用統(tǒng)計學的方式分析用戶在基站中的逗留特征，擬合逗留特征模型.然后通過RaptorQ的編碼，將文件智能化地分割部署在多個基站上.最終完整實現(xiàn)本文提出的離散分布的移動感知緩存策略.

通過理論分析部署策略的命中率，并結合實驗與多種典型緩存部署算法進行性能比較，可以得出結論：本文提出的離散分布的移動感知緩存策略可以通過分析用戶移動行為和逗留特征有針對性地進行智能化地緩存部署，大幅度地提高緩存部署的命中率，降低對骨干網(wǎng)的回程壓力，減少用戶的下載時延.