王 蒙 蒙

(濱州學(xué)院信息工程學(xué)院 山東 濱州 256603) (南京航空航天大學(xué)計算機科學(xué)技術(shù)學(xué)院 江蘇 南京 210000)

0 引 言

隨著5G應(yīng)用的普及，移動設(shè)備和數(shù)據(jù)流量將呈現(xiàn)指數(shù)增長。為了應(yīng)對海量接入以及大容量傳輸，最直接高效的方法是密集地部署基站(包括宏基站、微基站、中繼站等)，形成密集無線網(wǎng)絡(luò)[1-4]。在密集無線網(wǎng)絡(luò)中，有限的回程帶寬一定程度上限制了網(wǎng)絡(luò)性能。文獻[5]指出，在極端密集的無線網(wǎng)絡(luò)中，回程的功耗可以占到總功耗的30%。移動邊緣網(wǎng)絡(luò)緩存技術(shù)通過利用數(shù)據(jù)和用戶的空間、時間特性將存儲資源推送到移動網(wǎng)絡(luò)邊緣，可以有效減輕回程負載、降低網(wǎng)絡(luò)延遲和提高用戶體驗[6]。

在數(shù)據(jù)資源緩存決策研究中，主要包含非協(xié)作策略和協(xié)作策略，文獻[7]提出一種基于用戶移動感知的數(shù)據(jù)緩存策略，通過感知用戶移動將數(shù)據(jù)緩存到靠近用戶目的位置的區(qū)域。Psaras等[8]提出一種基于概率的數(shù)據(jù)資源緩存策略，通過與服務(wù)器的距離概率進行緩存決策。Wang等[9]提出一種確定性緩存策略，通過構(gòu)建啟發(fā)式算法解決緩存決策問題。Gu等[10]在啟發(fā)式策略構(gòu)建過程中進一步考慮了迭代過程與初始分配方案，優(yōu)化了算法性能。Gharaibeh等[11]提出一種在線緩存算法，通過多基站合作減少內(nèi)容提供總成本。非協(xié)作的數(shù)據(jù)緩存策略沒有考慮其他緩存主體的影響，在協(xié)作緩存策略中考慮了更多影響因素。Zhao等[12]提出了一種集中式和分布式相結(jié)合的緩存方式，以此提高緩存效率。文獻[13]提出一種區(qū)域協(xié)作緩存策略，以提高緩存收益。文獻[14]提出一種分層協(xié)作緩存策略，通過優(yōu)化算法減少用戶訪問代價。Sun等[15]提出一種輔助緩存布局方案，聯(lián)合優(yōu)化異構(gòu)網(wǎng)絡(luò)中的數(shù)據(jù)緩存和帶寬分配策略，降低用戶訪問中斷概率。

現(xiàn)有算法主要針對單個基站或是綜合考慮帶寬、實驗等因素判斷是否緩存，缺乏對邊緣緩存網(wǎng)絡(luò)協(xié)作問題的研究。另外這些討論都是針對固定網(wǎng)絡(luò)拓撲進行的，在邊緣緩存網(wǎng)絡(luò)中接入時刻、訪問時間、訪問內(nèi)容等都是隨機的，并且由于基站節(jié)點接入限制，一個用戶只能接入一個基站，那么緩存在該基站的內(nèi)容將無法為其他基站用戶服務(wù)。

為解決流行內(nèi)容緩存位置的決策問題，本文提出基于訪問均衡性核度中心的邊緣緩存決策方法(Cncv)，以一個分布式無線邊緣緩存網(wǎng)絡(luò)簇為研究對象，利用核度中心評估方法結(jié)合訪問信息熵共同決策內(nèi)容的緩存位置，該方法既考慮了基站節(jié)點自身的連接特點，同時也考慮了訪問均衡性對節(jié)點緩存價值的影響，能夠針對不同訪問內(nèi)容確定最快滿足用戶響應(yīng)的緩存節(jié)點，計算簡便。

1 邊緣緩存網(wǎng)絡(luò)模型

邊緣緩存網(wǎng)絡(luò)主要由基站、基站服務(wù)器、RAN控制器組成，如圖1所示?；鹃g通過無線連接，所有基站通過特定基站(簇首)經(jīng)過核心網(wǎng)與云中心連接，服務(wù)器具備緩存功能為用戶提供服務(wù)；RAN控制器與簇內(nèi)所有邊緣服務(wù)器相連，收集所有服務(wù)器信息。

圖1 邊緣緩存網(wǎng)絡(luò)模型

用戶可以隨機接入任何一個基站節(jié)點請求任何內(nèi)容，假設(shè)簇內(nèi)任意節(jié)點間的傳輸時間都小于簇首節(jié)點到核心云的傳輸時間，則用戶獲得響應(yīng)的方式如下：

1) 如果接入基站服務(wù)器緩存了用戶請求的內(nèi)容，則服務(wù)器直接響應(yīng)用戶請求。否則執(zhí)行2)。

2) 如果接入基站服務(wù)器的一跳鄰居服務(wù)器緩存了用戶請求內(nèi)容，則一跳鄰居服務(wù)器將內(nèi)容發(fā)送給接入服務(wù)器并響應(yīng)用戶請求，否則執(zhí)行3)。

3) 如果其他節(jié)點緩存用戶請求的內(nèi)容，則該服務(wù)器負責(zé)傳給接入基站服務(wù)器并響應(yīng)用戶請求，否則，繼續(xù)查找其他基站服務(wù)器是否緩存該內(nèi)容，直到簇內(nèi)所有基站節(jié)點查找完畢。如果簇內(nèi)所有節(jié)點都未緩存該內(nèi)容，則執(zhí)行4)。

4) 假設(shè)在核心云中用戶請求得到響應(yīng)，核心云將請求內(nèi)容發(fā)送給簇首服務(wù)器，然后再由簇首服務(wù)器發(fā)送給接入服務(wù)器，最后發(fā)送給用戶。在核心云中獲得響應(yīng)將不得不付出更大的代價。

顯然，請求的內(nèi)容離訪問接入基站越近，付出的代價越??；邊緣緩存網(wǎng)絡(luò)簇內(nèi)緩存的內(nèi)容越多，用戶請求響應(yīng)平均代價越小。然而邊緣服務(wù)器緩存空間有限，用戶訪問請求分布不均勻，高效的緩存策略有利于服務(wù)質(zhì)量的提高。

2 邊緣緩存網(wǎng)絡(luò)緩存決策策略

2.1 訪問核度中心率

核度中心率既考慮了網(wǎng)絡(luò)的拓撲結(jié)構(gòu)，也考慮了鄰居節(jié)點的連接情況，通過考察節(jié)點的連接度就可以獲得節(jié)點的核度中心率。但是在邊緣緩存網(wǎng)絡(luò)中用戶的接入位置是不確定的，因此哪個節(jié)點處在網(wǎng)絡(luò)的中心位置需要考慮當前的訪問情況，因此本文通過引入節(jié)點自身訪問頻率構(gòu)成訪問核度中心率Cvc(v)，以此作為緩存決策標準，確定網(wǎng)內(nèi)緩存策略，綜合考慮節(jié)點位置和接入確定放置位置。

節(jié)點的訪問核度中心率是所有鄰居節(jié)點的訪問核度與本節(jié)點的訪問數(shù)之和，Cvc(v)節(jié)點v的訪問核度中心率由式(1)給出：

(1)

式中：N(v)為節(jié)點v的鄰居集合；kvj是節(jié)點j的訪問核度；λv為節(jié)點v的訪問數(shù)，節(jié)點訪問數(shù)是在統(tǒng)計時間內(nèi)用戶接入該節(jié)點發(fā)起訪問請求的次數(shù)。

訪問核度的確定是通過按連接度從小到大的順序依次刪除節(jié)點和其連接的邊，確定其所在核層，并記錄節(jié)點自身訪問數(shù)，節(jié)點的訪問核度就是節(jié)點的訪問數(shù)與其所在核層的和。

如圖2所示，其中節(jié)點旁邊的數(shù)字代表訪問數(shù)。按照公式1計算，節(jié)點a的訪問核度中心率為18，節(jié)點b的訪問核度中心率為21，同理可以計算其他節(jié)點的訪問核度中心率，從計算結(jié)果可以看出節(jié)點b具有最大的訪問核度中心率，因此將內(nèi)容緩存在b節(jié)點上具有更高的響應(yīng)效率。下面按傳輸能耗(假設(shè)每一跳能耗均為1)比較內(nèi)容緩存在節(jié)點a和b上時的不同：

P(a)=6×2×1+3×2×1+7×3×1+

(7+1+1)×2=57

P(b)=6×3×1+3×2×2+7×2+

(7+1+1)×1=53

顯然節(jié)點b作為緩存節(jié)點更有利于響應(yīng)訪問請求。

圖2 訪問核度中心率示意圖1

2.2 訪問均衡率

在圖2中因為a、b鄰居節(jié)點的總訪問數(shù)不一樣，影響了a、b節(jié)點的重要性，進而影響了兩者的緩存價值，我們通過訪問核度中心率可以很好地解決這個問題。如果a、b鄰居節(jié)點的訪問數(shù)一樣，那a、b節(jié)點的緩存價值如何確定呢？

圖3 訪問核度中心率示意圖2

如圖3所示，此時a、b鄰居節(jié)點的總的訪問數(shù)是一樣的，經(jīng)過計算可以發(fā)現(xiàn)Cvc(a)=Cvc(b)=18，僅通過訪問核度中心率顯然無法判斷a、b誰更具緩存價值。由于兩者訪問核度中心率相同，節(jié)點a和b會被認為具有相同的緩存價值。然而觀察可以發(fā)現(xiàn)，雖然節(jié)點a和節(jié)點b的鄰居節(jié)點的總訪問數(shù)都是6，但分布不一樣，因此如果節(jié)點b和節(jié)點h之間路徑崩潰則直接影響4個訪問，而對于節(jié)點a，若與相鄰的節(jié)點e、f、g之間的1條路徑的崩潰，則只影響2個訪問，即在同等通信環(huán)境下，節(jié)點a比節(jié)點b對網(wǎng)絡(luò)的影響更大，因此該節(jié)點a具有更大的緩存價值。為了衡量鄰居節(jié)點訪問數(shù)對節(jié)點自身緩存價值的影響，本文基于香農(nóng)熵定義節(jié)點的訪問均衡熵ei為：

(2)

式中：j為i鄰居節(jié)點中的任一節(jié)點(j∈N(i))；kvj為節(jié)點j的訪問核度；ei值越大表明節(jié)點i的訪問越均衡，越容易滿足用戶的訪問請求，其緩存價值也越大。

對訪問均衡熵進行標準化處理，本文中標準化訪問均衡熵我們稱為訪問均衡率，其公式為：

(3)

式中：mi=N(i)集合中節(jié)點的個數(shù)，并且mi≥2。因為小于2時均衡性討論沒有意義，所以本文中當某一節(jié)點的鄰居節(jié)點數(shù)小于2時，其均衡性為1。均衡性實際指的是節(jié)點各分支節(jié)點的訪問分布是否均勻，與節(jié)點其他因素沒有關(guān)系。

2.3 訪問均衡核度中心評估方法

通過以上分析，在邊緣緩存網(wǎng)絡(luò)中節(jié)點的緩存價值是與其訪問均衡率以及訪問核度中心率有關(guān)，結(jié)合鄰居節(jié)點訪問核度中心率，提出一種訪問均衡核度中心評估方法Cncv(v)，其公式為：

(4)

邊緣緩存網(wǎng)絡(luò)簇中的基站節(jié)點可以獨立地計算自身的訪問均衡核度中心值Cncv(v)，然后通過RAN進行排序并確定最佳緩存節(jié)點。

3 節(jié)點緩存價值理論分析

3.1 節(jié)點緩存價值比較

下面以圖3的小規(guī)模樣本網(wǎng)絡(luò)為例，分別利用各種核心節(jié)點確認方法(CD、CB、Ckc、Cnc、Cncd及Cncv)對節(jié)點價值進行評估及排序。表1顯示了不同核心節(jié)點確認方法的排序結(jié)果(φ=0.8)，結(jié)果顯示有些方法無法區(qū)分節(jié)點排序，因此采用更為精確的方法就顯得非常重要；如節(jié)點a和b在Cncv中進行了更細粒度的排序。表2顯示了核心節(jié)點在不同方法下的計算值。

表1 不同方法下核心節(jié)點的排序

表2 不同方法下核心節(jié)點的計算值

3.2 訪問均衡熵對節(jié)點滿足訪問請求能力的意義

鑒于實際情況中節(jié)點接入及無線通信并不都是穩(wěn)定可靠的，假設(shè)接入的穩(wěn)定性(每個訪問結(jié)束前鏈路保持連通的概率)為β，節(jié)點間無線通信的成功率為α，當接入節(jié)點i的訪問請求數(shù)為di時，該節(jié)點成功接受的有效訪問請求數(shù)為Ii=di·βdi。

假設(shè)圖3中a、b節(jié)點為t=0時刻的信源節(jié)點，則在t=1時刻，具有較大訪問均衡熵的節(jié)點a可以滿足的平均訪問數(shù)是6β2α，而具有較小訪問均衡熵的b節(jié)點可以滿足的平均訪問數(shù)是4β4α+2βα。由此可見相對于其他方法，基于訪問均衡熵的方法能夠更細致地對節(jié)點滿足訪問請求能力進行有效區(qū)分和排序。

3.3 節(jié)點滿足訪問請求的能力

對于每個節(jié)點發(fā)起的訪問，無非有兩種狀態(tài)：滿足和未滿足。當請求的內(nèi)容緩存或傳輸?shù)皆摴?jié)點時，該節(jié)點的所有訪問請求將被滿足，否則就是未滿足。

表3 不同核心節(jié)點訪問能耗比較

通過比較計算可以看出訪問能耗的排序與Cncv方法中節(jié)點緩存價值排序是一致的，也就是說訪問能耗更小的節(jié)點具有更大的緩存價值，能更有效地滿足請求。

4 實 驗

4.1 實驗網(wǎng)絡(luò)拓撲數(shù)據(jù)

為了更準確地驗證本文方法的有效性，實驗過程中使用了真實的Jazz網(wǎng)絡(luò)，拓撲特性如表4所示，其中每個節(jié)點的訪問頻率設(shè)置為[0,10]隨機數(shù)，并且實驗參數(shù)β=0.8，φ=0.8。

表4 Jazz網(wǎng)絡(luò)拓撲數(shù)據(jù)

4.2 實驗結(jié)果分析

使用獨立級聯(lián)模型IC比較不同方法選取差異節(jié)點的滿足訪問效果；實驗平臺為Intel(R)Core(TM) i7- 6200CPU，8 GB內(nèi)存，使用的操作系統(tǒng)軟件為ubuntu-14.04.4-desktop-i386.

為了分析本文提出的訪問均衡性核度中心方法與其他評估方法在節(jié)點滿足訪問能力方面的差異，實驗分別將Cncv與CD、CB、Cnc及Cncd四種方法兩兩比較，選取排名前15且與比較方法不完全一致的節(jié)點作為源節(jié)點(當節(jié)點排序無法區(qū)分時，實驗節(jié)點隨機選擇，實驗中Cncv與CB和CD各有5個不同節(jié)點、Cncv與Cnc和Cncd各有3個不同節(jié)點)，因為相同節(jié)點在同一輪次內(nèi)滿足的訪問請求數(shù)是一樣的。

(a)

(b)

(c)

(d)圖4 前15名節(jié)點滿足訪問請求效率差異圖

從圖4(a)-圖4(d)中可以觀察到，與其他四種方法相比，Cncv方法在滿足訪問請求效率方面優(yōu)于其他方法，在同樣的傳播輪次下可以滿足更多的訪問請求。分析可知，Cncv方法引入了訪問核度的概念，對于節(jié)點的連接度、訪問頻率、訪問多樣性進行了全面考慮，因此可以更好地滿足訪問請求。

5 結(jié) 語

為了解決邊緣緩存網(wǎng)絡(luò)中緩存基站節(jié)點的選擇問題，結(jié)合訪問頻率和網(wǎng)絡(luò)結(jié)構(gòu)對于緩存效率的影響，提出一種基于訪問均衡性的基站節(jié)點緩存決策方法，即基于訪問均衡性核度中心(Cncv)方法，該方法創(chuàng)新性地將滿足用戶請求作為直接研究對象，因此相對其他緩存決策方法可以更高效地滿足用戶請求。與當前其他研究工作類似，本文主要研究如何緩存內(nèi)容可以更好地滿足訪問請求，沒有深入細致地討論信道及緩存資源分配，而在邊緣網(wǎng)絡(luò)中，這些問題是無法忽略的。未來將進一步考慮這些因素，從而實現(xiàn)更高的訪問效率。