楊崇旭，陳正勇，楊 堅(jiān)

(中國科學(xué)技術(shù)大學(xué) 未來網(wǎng)絡(luò)實(shí)驗(yàn)室，合肥 230022)

1 引 言

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

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

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

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

圖1 離散分布的移動(dòng)感知策略流程圖

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

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

2 建立軌跡特征預(yù)測模型

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

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

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

(1)

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

(2)

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

Z1∪Z2∪…∪ZK=Z

(3)

Zk∩Zk′=φ

(4)

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

第三步，將每一個(gè)類別的轉(zhuǎn)移概率矩陣表示成：

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

(5)

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

(6)

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

(7)

(8)

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

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

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

(9)

Ψ1≤∑ρi≤1

(10)

3 逗留特征擬合模型

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

G(t)=a×tb+c

(11)

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

(tend-t0)×V=M

(12)

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

(13)

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

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

(14)

4 分布式緩存緩存

4.1 RaptorQ編碼文件

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

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

表1 RaptorQ編解碼恢復(fù)概率表

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

圖2 RaptorQ編碼示意圖

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

(15)

圖3 文件編碼流程圖

4.2 依概率分布式緩存

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

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

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

(16)

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

(17)

Ni=「ρi×N′?

(18)

(19)

4.3 緩存部署命中率

(20)

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

(21)

(22)

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

(23)

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

R=1

(24)

5 實(shí)驗(yàn)驗(yàn)證與分析

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

5.1 實(shí)驗(yàn)數(shù)據(jù)集

實(shí)驗(yàn)中采用的原始數(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°均分成多個(gè)方形小網(wǎng)格，除去所有軌跡都未經(jīng)過的網(wǎng)格，共獲得106個(gè)小網(wǎng)格區(qū)域，而這里將每一個(gè)小網(wǎng)格抽象為一個(gè)基站的覆蓋范圍.

5.2 訓(xùn)練軌跡特征預(yù)測模型

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

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

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

5.3 擬合逗留規(guī)律

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

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

(25)

和方差為4.178，標(biāo)準(zhǔn)差為0.032.

5.4 緩存部署與性能分析

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

圖4 逗留特征擬合模型

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

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

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

5.4.1 命中率分析

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

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

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

5.4.2 資源開銷分析

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

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

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

6 結(jié) 論

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

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