基于訪問均衡性核度中心的分布式密集無線網(wǎng)絡(luò)邊緣緩存決策策略

王 蒙 蒙

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

0 引 言

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

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

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

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

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ò)模型

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

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

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

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

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

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

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

2.1 訪問核度中心率

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

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

(1)

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

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

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

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é)點(diǎn)b作為緩存節(jié)點(diǎn)更有利于響應(yīng)訪問請(qǐng)求。

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

2.2 訪問均衡率

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

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

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

(2)

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

對(duì)訪問均衡熵進(jìn)行標(biāo)準(zhǔn)化處理，本文中標(biāo)準(zhǔn)化訪問均衡熵我們稱為訪問均衡率，其公式為：

(3)

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

2.3 訪問均衡核度中心評(píng)估方法

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

(4)

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

3 節(jié)點(diǎn)緩存價(jià)值理論分析

3.1 節(jié)點(diǎn)緩存價(jià)值比較

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

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

表2 不同方法下核心節(jié)點(diǎn)的計(jì)算值

3.2 訪問均衡熵對(duì)節(jié)點(diǎn)滿足訪問請(qǐng)求能力的意義

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

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

3.3 節(jié)點(diǎn)滿足訪問請(qǐng)求的能力

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

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

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

4 實(shí) 驗(yàn)

4.1 實(shí)驗(yàn)網(wǎng)絡(luò)拓?fù)鋽?shù)據(jù)

為了更準(zhǔn)確地驗(yàn)證本文方法的有效性，實(shí)驗(yàn)過程中使用了真實(shí)的Jazz網(wǎng)絡(luò)，拓?fù)涮匦匀绫?所示，其中每個(gè)節(jié)點(diǎn)的訪問頻率設(shè)置為[0,10]隨機(jī)數(shù)，并且實(shí)驗(yàn)參數(shù)β=0.8，φ=0.8。

表4 Jazz網(wǎng)絡(luò)拓?fù)鋽?shù)據(jù)

4.2 實(shí)驗(yàn)結(jié)果分析

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

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

(a)

(b)

(c)

(d)圖4 前15名節(jié)點(diǎn)滿足訪問請(qǐng)求效率差異圖

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

5 結(jié) 語

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