張 涵,胡宏林
(1.中國科學院 上海高等研究院,上海 201210;2.中國科學院大學,北京 100049;3.上海科技大學 信息科學與技術學院,上海 201210)
隨著網(wǎng)絡和移動通信應用技術的發(fā)展,數(shù)據(jù)流量的劇增帶來的大量移動數(shù)據(jù)處理需求成為第五代移動通信技術(5G)迫切需要解決的問題[1],通過在邊緣節(jié)點緩存文件給用戶提供訪問支持是解決該問題的主要方法?,F(xiàn)有的以端到端連接為基礎的傳輸控制協(xié)議/網(wǎng)際協(xié)議(TCP/IP)架構在處理大量數(shù)據(jù)時顯得低效,尤其是當傳輸重復的數(shù)據(jù)時,每次傳輸都需要進行重新建立連接。因此,新的信息中心網(wǎng)絡(information centric networking,ICN)架構被提出[2]。ICN被認為是下一代第六代移動通信技術(6G)系統(tǒng)中解決TCP/IP架構已有問題的有效解決方法,通過與TCP/IP協(xié)議中端到端連接不同的發(fā)布/訂閱(Publish/Subscribe)范式、使用命名取代IP、采用新的命名路由、在節(jié)點中加入緩存等方式解決現(xiàn)有架構的不足,避免重復建立新的連接從而高效傳輸數(shù)據(jù)。
另外,緩存也是ICN區(qū)別于TCP/IP架構的主要方面,邊緣緩存節(jié)點直接由本地緩存向用戶提供服務,不需要從基站(base station,BS)下載新內(nèi)容,這樣減少了BS到核心網(wǎng)的回程負載,但同時也出現(xiàn)了緩存冗余問題,如果緩存的冗余過多,就會導致緩存效率低下,還會造成資源浪費。為了減少硬件開銷成本并減少緩存的冗余,Zipf分布被廣泛用于現(xiàn)有的緩存策略中[3],但是Zipf分布需要預先知道總體文件的流行度情況,文件流行度指某一個文件在一個系統(tǒng)中的受歡迎程度,使用Zipf分布的前提是系統(tǒng)內(nèi)文件的流行度平穩(wěn)不變,并且需要知道系統(tǒng)中所有文件的全局流行度情況。而現(xiàn)階段一方面系統(tǒng)內(nèi)的文件的流行度情況是動態(tài)的,另一方面又難以完美把握總體流行度,因此Zipf分布不適用于分析實際的用戶請求模型[4]。需要采用新的分布來描述緩存文件的動態(tài)流行度情況。
以往對緩存的研究主要是聚類算法的應用或者將端到端(device to device,D2D)緩存設備引入到整個系統(tǒng)中。文獻[5]研究了在支持緩存的云無線電接入網(wǎng)絡(radio access network,RAN)中以內(nèi)容為中心的BS分簇和多播波束形成的聯(lián)合設計,最終將問題歸結為一個混合整數(shù)的非線性規(guī)劃問題(mixed-integer non-linear programming,MINLP)。作者考慮了以內(nèi)容為中心的傳輸在Zipf分布請求模型下如何降低網(wǎng)絡總成本的問題,與傳統(tǒng)的以用戶為中心的設計相比可以顯著降低網(wǎng)絡的總成本。Khan等[6]提出了一種使用D2D進行輔助緩存通信網(wǎng)絡的集聚層次聚類算法,通過優(yōu)化每個集群內(nèi)的緩存命中概率,以實現(xiàn)總體的高緩存命中概率。Qi等[7]使用了一種聯(lián)合學習方法來預測文件的流行程度以解決隱私問題,即每個用戶對每個文件的請求數(shù)據(jù)僅用于每個用戶的本地訓練。Jiang等[8]采用了一種更實際的方法,使用多智能體強化學習來設計移動D2D網(wǎng)絡中的內(nèi)容緩存策略,這樣做就無需考慮先驗的內(nèi)容流行度分布情況。為了緩解回程鏈路的壓力,Rim等[9]首次提出了一個通過助手節(jié)點(Helper)來實現(xiàn)的具有低速的上行回程速率但是具有高速下行速率系統(tǒng),其中Helper節(jié)點是一種具有高速下行速率但是具有低回程速率的設備,Helper節(jié)點用于緩存流行的視頻文件。
然而上述的研究對流行文件的分布都是采用Zipf分布,但是Zipf分布不能反映文件的流行度變化情況。Leconte等[4]提出了一種基于文件年齡閾值的方案,可以利用年齡閾值來估計流行度,在一定程度上反映了流行度的變化情況,但是該模型只適用于文件數(shù)量有限的系統(tǒng)內(nèi)。Zipf分布可以反映流行度特征,但是有如下缺陷:①不能及時估計不同內(nèi)容的受歡迎程度;②不能從小樣本中判斷文件的受歡迎程度。Zipf分布模型又被稱作獨立參考(independent reference model,IRM)模型,在IRM模型中,緩存文件的數(shù)目是固定的,實際中的文件數(shù)目是很大的并且時刻變化,因此該模型不適用于描述實際的視頻流的到達過程[10-12]。
上述的工作沒有解決IRM模型的這些缺陷,IRM模型忽略了局部熱點,并且IRM需要全局流行度的先驗知識。本文考慮了這些缺陷,使用新的散粒噪聲模型(shot noise model,SNM)模型,通過在D2D設備中進行被動緩存,可以解決局部熱點問題,此外,被動緩存還可以兼顧5G通信系統(tǒng)中要求的低能量消耗需求。實際中用戶的請求模型與SNM模型更一致,SNM模型是IRM模型在文件數(shù)量N趨于無窮時候的近似。文獻[13]中使用校園網(wǎng)中視頻流的實際數(shù)據(jù),證明了實際的文件流的到達情況符合SNM模型。
本文最終設計了一個基于SNM模型,并且依賴設備間協(xié)作的新緩存放置方案,模型最大化了緩存的成功卸載概率,滿足D2D節(jié)點以及Helper節(jié)點的緩存空間約束、D2D節(jié)點的能耗約束。SNM模型解決了Zipf分布模型的缺陷,不需要完美的流行度知識,提出的方案可以在提高網(wǎng)絡傳輸速率、減少系統(tǒng)總體能耗、縮短BS端排隊時延并提升用戶體驗上,對基于SNM模型的通信網(wǎng)絡進行緩存分配算法的研究具有非常重要的理論意義和現(xiàn)實價值。在仿真中比較了3種緩存策略:①提出的緩存策略;②流行度緩存策略;③隨機緩存策略。仿真結果表明,本文提出的新緩存放置方案在成功卸載概率方面具有更好的性能,通過與其它的兩種主流算法相比,驗證了算法的有效性。
系統(tǒng)模型圖如圖1所示,在一個BS下,包含Helper節(jié)點以及D2D節(jié)點。其中,Helper節(jié)點和D2D節(jié)點按照兩個獨立的均勻泊松點過程(poisson point process,PPP)在空間分布,其中,Helper節(jié)點和D2D節(jié)點的分布密度分別為λH和λD2D。
圖1 系統(tǒng)模型和傳輸協(xié)議
在IRM模型中,文件庫中包含有F={f1,f2,…fN} 不同的N個內(nèi)容。Zipf定律模擬的流行文件分布表示為q={q1,…qN},第i個流行內(nèi)容的概率為
(1)
其中,γ表示流行度的偏差。γ值越大意味著用戶的請求更集中于某些特定的文件,流行度會更加不平衡,即當γ值較高時,就更容易預測哪種類型的文件在用戶中流行,也更容易決定緩存哪種文件。
SNM模型在保留IRM模型的冪律特征的同時引入了動態(tài)流行度。因此,與IRM模型相比,SNM模型更適合于描述實際的請求到達過程。第m個熱點文件的到達強度由以下特征塑造:①文件生存時間;②文件到達的分布;③文件到達時候的強度;④文件到達時間。文件到達時間是以λ為參數(shù)的泊松過程,令Tm為SNM過程中一個文件的生命周期,tm為第m個SNM過程的到達時間。整個過程的生存時間為Am(t)={(m,t)|tm≤t≤tm+Tm}。一般來說,SNM分布的形狀對結果的影響很小[8],文件到達時候的強度是由冪律分布決定的。我們以下列方式構造第m個SNM內(nèi)容
(2)
如圖1所示,系統(tǒng)中包含一個基站以及若干個Helper節(jié)點和D2D節(jié)點,Helper節(jié)點A從BS獲取IRM列表并主動緩存IRM內(nèi)容,而D2D節(jié)點緩存不屬于IRM列表里面的SNM內(nèi)容,系統(tǒng)中的用戶可以從Helper節(jié)點或D2D節(jié)點直接獲取已經(jīng)緩存的內(nèi)容,也可以直接從BS獲取內(nèi)容。在系統(tǒng)初始化的時候,系統(tǒng)中所有的節(jié)點,包括BS,都不知道每個文件的流行度情況。此時所有請求內(nèi)容都使用最近最少使用(least recently used,LRU)策略緩存,直到Helper節(jié)點和D2D節(jié)點的緩存容量達到一個閾值。LRU策略是一種根據(jù)緩存文件的歷史訪問次數(shù)來淘汰數(shù)據(jù)的算法,其核心思想是“如果數(shù)據(jù)最近被用戶訪問,那么將來被訪問的幾率也更高”,而最近沒有被訪問的文件的緩存優(yōu)先級將會降低,當緩存容量不夠時,LRU策略會刪除低優(yōu)先級的文件。我們提出的協(xié)作緩存策略表述如下:在系統(tǒng)中經(jīng)過一定的時間之后,Helper節(jié)點和D2D節(jié)點需要向BS上報文件的流行度信息,他們向BS提交每個文件的請求次數(shù)列表。上傳的列表將告知BS他們所服務的所有用戶對每個內(nèi)容的受歡迎程度,BS將處理他們上傳的列表,通過在流行度中截取閾值,分類出IRM內(nèi)容和SNM內(nèi)容,并且會生成IRM表和SNM表,IRM表中將會記錄流行度高的IRM內(nèi)容,而SNM表中將會記錄流行度低的SNM內(nèi)容。BS將IRM列表分發(fā)給Helper節(jié)點,SNM列表分發(fā)給D2D節(jié)點。當Helper節(jié)點獲取到IRM列表時,Helper節(jié)點將主動緩存IRM表中的內(nèi)容,并與在通信范圍內(nèi)的其它Helper節(jié)點共享此列表。D2D節(jié)點將接收SNM表,D2D設備采用LRU策略來緩存,這是考慮到D2D設備電池容量一般情況下是有限的,而被動LRU策略可以延長D2D設備的使用時長以提高用戶體驗。這樣,通過Helper節(jié)點和D2D節(jié)點的協(xié)作,可以盡量將所有的文件在系統(tǒng)中緩存。
當用戶需要請求內(nèi)容時,執(zhí)行下面的流程:首先,如果附近的D2D節(jié)點有用戶需要的內(nèi)容,那么用戶先直接從附近的D2D節(jié)點請求。如果附近的D2D節(jié)點沒有內(nèi)容,那么用戶向附近的Helper節(jié)點請求內(nèi)容。如果D2D節(jié)點和Helper節(jié)點都沒有用戶需要的內(nèi)容,則最后BS將響應用戶的請求并進行傳輸。假設BS最終能滿足用戶的所有需求,則通過節(jié)點緩存可以減少BS端的服務負擔。
從BS端卸載流量有如下幾種方式:①自卸:考慮系統(tǒng)中的一些用戶是具有緩存能力的。如果用戶需求的內(nèi)容在本地緩存中,用戶將首先從本地緩存滿足需求。用α表示擁有緩存的用戶占所有用戶的比例 (0≤α≤1),對于用戶來說的泊松點過程的密度為αλD2D。當用戶的請求被本地緩存來滿足時,這種卸載方法稱為自卸載;②D2D節(jié)點卸載:當用戶的本地緩存中沒有用戶需要的內(nèi)容時,并且在用戶范圍內(nèi)有D2D設備并具有緩存能力,這時D2D設備可以通過D2D連接為用戶提供服務。當D2D設備的緩存內(nèi)容中有用戶需求的內(nèi)容,則這個D2D設備為用戶提供服務。這種卸載方法稱為D2D卸載;③Helper節(jié)點卸載:在請求了本地緩存和D2D節(jié)點的緩存后,如果兩者都沒有用戶請求的內(nèi)容,則用戶向Helper節(jié)點尋求內(nèi)容。如果在用戶的通信范圍內(nèi)至少有一個 Helper節(jié)點有用戶所需的內(nèi)容,則Helper節(jié)點將建立用戶與Helper之間的通信。這種卸載流量的方式稱為Helper節(jié)點卸載;④蜂窩傳輸:如果本地緩存、D2D節(jié)點和Helper節(jié)點都無法滿足用戶請求,則最終由蜂窩BS提供傳輸服務。BS通過回程鏈路從核心網(wǎng)的數(shù)據(jù)庫中獲取內(nèi)容。這里假設用戶請求的所有內(nèi)容最后肯定都能被核心網(wǎng)滿足,但是如果所有的請求都通過回程鏈路回傳,將給BS帶來巨大的負擔。通過Helper節(jié)點和D2D節(jié)點緩存內(nèi)容,并給用戶提供服務可以給BS卸載流量,減少擁塞。
D2D節(jié)點和Helper節(jié)點都具有各自的傳輸范圍RD2D和RH,與D2D節(jié)點相比,Helper節(jié)點具有更高的存儲容量和下行速率來給用戶提供服務。
考慮一個覆蓋有若干Helper節(jié)點和D2D節(jié)點的BS。BS可以通過其有限的回程訪問核心網(wǎng)。Helper節(jié)點可以在RH范圍內(nèi)為用戶服務,D2D節(jié)點可以在RD2D范圍內(nèi)為用戶服務。兩種類型的節(jié)點只能在其本地緩存包含用戶需要的內(nèi)容時才響應請求。為簡單起見,每個內(nèi)容設置成相同的大小。每個設備,包括Helper節(jié)點和D2D節(jié)點的容量都是有限的。在本文中,我們沒有考慮到內(nèi)容的細致劃分,每個被請求的文件被視作為一個整體。
(3)
式中:CH為Helper節(jié)點的容量,每個Helper都有相同的規(guī)格。同樣,CD2D是D2D節(jié)點的容量。
所有的文件分為兩類:IRM文件和SNM文件。流行度文件經(jīng)過排序之后,流行度高的文件劃分為IRM文件,剩下的文件稱為SNM文件。最終的目標是通過優(yōu)化緩存放置策略來最大化總體的卸載概率。緩存IRM文件和SNM文件的策略有所區(qū)別。若用M表示整個目錄的文件數(shù)量,那么IRM的文件數(shù)量為N,而SNM的內(nèi)容為N+1到M。Helper節(jié)點和D2D節(jié)點通過協(xié)作緩存策略來分別存儲IRM和SNM內(nèi)容,另外,為了延長D2D設備的使用時間,D2D節(jié)點使用LRU策略,而Helper節(jié)點使用主動策略來緩存IRM內(nèi)容。這樣,Helper節(jié)點能盡量覆蓋到大部分用戶的文件請求,而D2D節(jié)點可以滿足小區(qū)域內(nèi)突發(fā)的用戶熱點文件的請求。
在本部分中,假設所有的D2D節(jié)點不是都具有緩存能力,將具有緩存能力的用戶的比例設為α。
從文獻[6]可得,一個用戶在他的通信范圍內(nèi)向一個D2D設備的本地緩存請求文件,該D2D設備的本地緩存沒有用戶請求的這個文件的概率
(4)
式中:r為PPP過程的半徑,λ為PPP過程的密度,n為在半徑r內(nèi)的設備數(shù)量。這個概率表示在密度λ的PPP分布下,有n個設備在用戶的通信范圍內(nèi)的概率。
因此,第i個內(nèi)容被至少一個Helper節(jié)點緩存的概率由下式表示
(5)
式中:RH為Helper節(jié)點的覆蓋范圍,λH表示Helper節(jié)點在PPP過程下的分布密度。
同理,用戶至少被一個D2D節(jié)點緩存內(nèi)容服務的概率由下式表示
(6)
對于IRM內(nèi)容,用戶首先從本地緩存查看內(nèi)容,如果沒有,就會向Helper節(jié)點請求。有緩存能力的用戶對第i個IRM內(nèi)容的卸載概率為
(7)
式中:第一項表示用戶在本地緩存第i個內(nèi)容的概率,第二項表示,用戶沒有本地緩存,向Helper節(jié)點請求并在Helper節(jié)點成功卸載的概率。
總體的緩存第i個IRM內(nèi)容的概率,即第i個IRM內(nèi)容被卸載的概率為
(8)
式中:第一項表示有緩存能力的用戶對第i個內(nèi)容的總體卸載概率,第二項表示沒有緩存額能力的用戶對第i個內(nèi)容的總體卸載概率,如果用戶沒有緩存能力就需要向Helper節(jié)點請求內(nèi)容。
對于SNM內(nèi)容,沒有緩存能力的用戶向其它D2D節(jié)點尋求幫助。因此,有緩存能力的用戶緩存第j個SNM文件的概率為
(9)
式中:第一項表示用戶在本地緩存第j個SNM內(nèi)容的概率,第二項表示,用戶沒有本地緩存,向其它D2D節(jié)點請求并在D2D節(jié)點成功卸載內(nèi)容的概率。
與式(8)同理,最終第j個SNM內(nèi)容被卸載的概率為
(10)
總體的IRM內(nèi)容被卸載的概率為
(11)
總體的SNM內(nèi)容被卸載的概率為
(12)
式中:q是經(jīng)過排序之后的SNM過程生成的每個文件的流行度。最終,系統(tǒng)的總的成功卸載概率為
(13)
本文中的優(yōu)化變量是 Helper節(jié)點和D2D節(jié)點的緩存位置。目標是最大化卸載概率,式(13)的優(yōu)化條件可以寫成
maxPPoff
(14)
式(14)的優(yōu)化問題是非凸的。接下來,我們將證明目標函數(shù)(13)對于優(yōu)化變量P=[PH,PD2D]是一個凸差問題[14]。
化簡式(13)得
(15)
P1的Hessian矩陣為
因此,-Hi是正定的,因此-P1對P是凸的。
(16)
(17)
一般的凸差函數(shù)具有以下形式
α=inf{f(x)=g(x)-h(x),x∈}
(18)
其中,g和h為實數(shù)域上的半連續(xù)凸函數(shù)。
g的共軛函數(shù)定義如下
(19)
上式的對偶問題是
αD=inf{h*(y)-g*(y),y∈n}
(20)
inf{g(x)-h(xk)-
inf{h*(y)-g*(yk)-
(21)
基于凸分析和對偶理論,凸差算法通過探討原問題與對偶問題的關系,對原問題進行了優(yōu)化。
算法1:最優(yōu)化Helper節(jié)點以及D2D節(jié)點緩存放置的凸差算法
(1)min{g(x)-h(xk)
(2)min{h*(y)-g*(yk)
(3)當|xk+1-xk|≤ε或者g(xk)-h(xk)≤g(xk+1)-h(xk+1)+ε時
計算yk∈?h(xk) 以及xk+1∈?g*(yk);
令k=k+1
(4)重復步驟(3),直到算法滿足終止條件。
為了比較本文算法與其它緩存方法的優(yōu)劣,通過仿真分析針對不同的緩存節(jié)點密度、不同的SNM參數(shù),與按照流行度緩存的分配方法和隨機緩存分配方法的成功卸載概率進行對比。假設系統(tǒng)中D2D通信的初始范圍為RD2D=15 m,Helper節(jié)點的通信范圍為RH=100 m,有緩存能力的用戶占比α為0.5,IRM和SNM文件的數(shù)量N=M=30,D2D用戶的密度λD2D=5000/π5002個/平方米,Helper節(jié)點的密度為λH=50/π5002個/平方米,為了簡化模型,所有D2D設備和Helper節(jié)點的緩存容量被設置成相同大小,D2D設備的緩存容量CD2D為2個文件,Helper節(jié)點的緩存容量CH為8個文件。初始的SNM模型的參數(shù)γ為0.8。我們通過比較現(xiàn)有的緩存策略來評估所提出的混合方案。在按照流行度緩存的分配方法中,用戶的請求采用的是IRM模型,該模型只對流行的文件進行緩存,隨機緩存分配方法中,對所有內(nèi)容的緩存概率都是相同的。為了簡化模型,假設一個單一的單元場景,其中每個D2D節(jié)點和Helper節(jié)點都配備了一個單一的天線。它們一次只能為一個用戶提供內(nèi)容服務,而BS在用戶請求D2D節(jié)點和Hel-per節(jié)點之后,沒有得到節(jié)點服務的情況下給用戶提供服務。
圖2給出了IRM模型和SNM模型在不同的強度和符合泊松分布瞬時到達時間下的一次實現(xiàn),其中文件序號已經(jīng)根據(jù)流行度的大小進行了排序,請求頻率高的文件的序號排名靠前,而且SNM模型中,所有文件的流行時間以及到達的形狀都是固定的。從圖中可以看出,SNM模型曲線的輪廓比IRM模型曲線的輪廓在整體上更加平滑,這是因為SNM模型是IRM模型當文件數(shù)N趨于無窮時候的近似。
圖2 IRM模型和SNM模型
圖3給出了成功卸載概率與Helper節(jié)點密度λH之間的關系。3個算法中的SNM模型的流行度偏差γ相同??梢钥闯?,隨著Helper節(jié)點密度λH的增加,提出的算法以及按照流行度緩存的分配方法和隨機緩存分配方法的成功卸載概率都得到了不同程度的提升。這是因為密度的提高相當于增加了系統(tǒng)總體的緩存容量,系統(tǒng)中能緩存更多的文件,而用戶首先訪問IRM內(nèi)容或者是SNM內(nèi)容時被Helper節(jié)點和D2D節(jié)點服務的概率就會上升,同時,這也驗證了所提出的算法在λH變大的時候,提高的成功卸載概率更加明顯。
圖3 λH和成功卸載概率
圖4給出了成功卸載概率與D2D節(jié)點密度λD2D之間的關系。結果表明,提出的算法和隨機緩存分配方法的成功卸載概率隨著λD2D的增大而變大。達到相同成功卸載概率所需要的D2D節(jié)點的密度更低。按照流行度緩存的分配方法使用Zipf分布,只緩存流行度高的內(nèi)容,無法處理局部熱點的情況,因此,該方法的成功卸載概率與緩存SNM內(nèi)容的D2D節(jié)點密度λD2D無關。
圖4 λD2D和成功卸載概率
圖5中給出了SNM模型的流行度偏差與γ成功卸載概率的關系。可以看出,成功卸載概率隨著γ的增大而變大,即區(qū)域中的用戶請求集中在更少的文件上時,會提升成功卸載概率。按照流行度緩存的分配方法的成功卸載概率隨著γ增長的增長率最大,因為完美的流行度預測對使用Zipf分布的流行度緩存方案影響很大。但是,當γ很低時,提出的算法得到的成功卸載概率優(yōu)于其它兩種方案,說明當系統(tǒng)的流行度預測不完美或者是系統(tǒng)中的流行文件很分散時,這個情況與實際中的文件請求情況相同,這時所提出的算法具有最大的成功卸載概率。
圖5 SNM參數(shù)γ與成功卸載概率
為了提升D2D和Helper節(jié)點輔助的無線通信系統(tǒng)中的總體卸載概率,本文通過新的基于SNM模型并且依賴設備間協(xié)作的緩存放置算法,最優(yōu)化放置區(qū)域內(nèi)的流行文件。分析了D2D節(jié)點密度,Helper節(jié)點密度以及流行文件的偏差度給系統(tǒng)帶來的影響。本文提出的算法與以固定文件數(shù)目的Zipf模型為基礎的其它算法比較,在相同的D2D節(jié)點密度、Helper節(jié)點密度或者是流行度偏差因子下具有更高的卸載增益。3種算法中,隨機緩存分配方法都具有最低的復雜度以及次優(yōu)的卸載增益。通過最優(yōu)化分配緩存文件放置,可以減少網(wǎng)絡中用戶的總體時延,同時避免緩存不需要的文件,可以減少總體的能源消耗。