翟 月

(安徽電子信息職業(yè)技術(shù)學(xué)院軟件學(xué)院，安徽 蚌埠 233000)

0 引 言

諸如智能電話等移動設(shè)備的爆炸性增長產(chǎn)生了巨大的網(wǎng)絡(luò)流量，據(jù)估計，到2022年，全球的移動數(shù)據(jù)流量將增長到每月77 EB，其中智能設(shè)備和連接的份額將增加到73%[1]。5G無線網(wǎng)絡(luò)能為移動用戶更好的服務(wù)質(zhì)量，并具有更高的帶寬、更大的天線規(guī)模以及更高效的頻率復(fù)用等特點。預(yù)計其傳輸速度將比4G快20倍左右，并且延遲可能下降到個位數(shù)毫秒，幾乎無法檢測到滯后時間[2]。緩存技術(shù)是5G的關(guān)鍵技術(shù)之一，將數(shù)據(jù)內(nèi)容緩存到距離用戶更近的基站能夠有效降低網(wǎng)絡(luò)延遲。因此，為了提高5G網(wǎng)絡(luò)的性能，本研究結(jié)合考慮路由算法，設(shè)計分布式緩存優(yōu)化算法。

1 問題建模

1.1 系統(tǒng)模型

考慮一個由N個小型基站和M套移動用戶組成的5G無線網(wǎng)絡(luò)。在每個時間間隔t∈{1,2,…,T}，緩存策略和路由策略可以更新。令N={1,…,N}和M={1,…,M}分別表示小型基站集和用戶集。用戶集合m與小型基站n之間的連通性被表示為knm，knm= 1說明則用戶集m在小型基站n的服務(wù)范圍內(nèi)；否則，knm= 0。用集合F={1,...,F}表示內(nèi)容集合，每個內(nèi)容的大小都是相同的。

顯然，每個小型基站n不能緩存超出其容量的數(shù)據(jù)，即，

(1)

其中，Cn是小型基站n存儲容量。

同樣，從小型基站到用戶的總流量受帶寬容量Bn的限制，即，

(2)

緩存策略和路由策略緊密結(jié)合在一起：只有在小型基站已經(jīng)緩存了所請求的內(nèi)容，否則小型基站無法提供請求的內(nèi)容。緩存策略和路由策略之間的這種相互依賴關(guān)系由以下約束描述：

(3)

1.2 網(wǎng)絡(luò)成本函數(shù)

目標(biāo)是通過確定每個小型基站的緩存和路由策略，最大程度地降低服務(wù)用戶的總運營成本。為了捕獲位置多樣性和服務(wù)成本隨時間的變化，讓gt(·)表示小型基站的服務(wù)成本。對于每個小型基站n，服務(wù)成本由用戶的位置、請求的數(shù)量以及所請求內(nèi)容的服務(wù)部分來確定。

覆蓋用戶集合m的大型基站和小型基站接收從用戶集合m發(fā)送的關(guān)于內(nèi)容f的請求。大型基站以集中的方式收集網(wǎng)絡(luò)的全局信息，確定每個小型基站緩存和路由策略，以最大程度地降低網(wǎng)絡(luò)的總運營成本。如果內(nèi)容f被緩存在某些小型基站中，則小型基站可以將內(nèi)容直接發(fā)送到用戶。不同的小型基站所傳輸內(nèi)容的比例由大型基站控制。如果內(nèi)容未在小型基站中緩存或小型基站帶寬資源有限，則請求將由大型基站服務(wù)。

成本函數(shù)gt(·)的表達式如下所示

(4)

ft(Yt)的表達式如下所示：

(5)

緩存替換成本捕獲了小型基站中內(nèi)容替換所產(chǎn)生的能耗和金錢成本。在時隙t，從用戶接收到請求后，小型基站更新緩存策略，從大型基站獲取新內(nèi)容，并刪除需要替換的內(nèi)容。從時隙t-1 到t的小型基站的緩存替換成本為

(6)

其中βn是在緩存替換期間產(chǎn)生的成本。

1.3 聯(lián)合優(yōu)化問題

通過確定時間范圍T內(nèi)每個小型基站的緩存策略和路由策略來最大程度地降低網(wǎng)絡(luò)的總運營成本，該問題具有如下所示的表達式：

(7)

2 分布式算法設(shè)計

(8)

原問題(7)的對偶問題如下所示：

s.t.μ≥0

(9)

將原始問題分解為以下兩個子問題：

(10)

(11)

通過引入拉格朗日乘子對問題進行分解后，提出了一種對偶算法來解決該問題。對于每次迭代l，子問題P1(x)和P2(y)可以并行地進行。

3 實驗評估

首先探討網(wǎng)絡(luò)拓?fù)鋵λ惴ㄐ阅艿挠绊?。通過改變用戶的數(shù)量來改變網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，實驗結(jié)果如圖1所示。當(dāng)用戶的數(shù)量增加時，網(wǎng)絡(luò)的成本會增加。這是由于用戶越多，服務(wù)用戶的網(wǎng)絡(luò)運營商就會越多。由結(jié)果可知，提出的算法的性能仍然明顯優(yōu)于LRU。

圖1 用戶數(shù)量對成本的影響

接下來，探討小型基站的緩存容量和帶寬對算法性能的影響。在圖2中，當(dāng)小型基站的存儲容量增加時，網(wǎng)絡(luò)的總運營成本會稍微下降一點。圖3展示了帶寬的影響，當(dāng)帶寬容量從500增加到2000時，總運營成本最多可節(jié)省約60%。

圖2 小型基站緩存容量對成本的影響

圖3 帶寬對成本的影響

4 結(jié) 論

研究首先建立了緩存和路由的聯(lián)合優(yōu)化模型，然后通過求解該模型設(shè)計分布式的緩存算法。最后采用對比實驗對算法的性能進行評估，結(jié)果表明本算法具有一定的有效性。為了適應(yīng)網(wǎng)絡(luò)環(huán)境的動態(tài)變化，在未來的工作中，將設(shè)計動態(tài)的實時緩存算法，進一步降低網(wǎng)絡(luò)的成本。