面向5G-ICN切片的分層緩存策略*

戈麗平，周金和

(北京信息科技大學(xué) 信息與通信工程學(xué)院，北京 100101)

0 引 言

5G網(wǎng)絡(luò)具有控制平面和用戶平面徹底分離，靈活轉(zhuǎn)發(fā)等功能，并且能夠?qū)崿F(xiàn)網(wǎng)絡(luò)服務(wù)協(xié)調(diào)和控制功能的靈活部署[1]，為部署網(wǎng)絡(luò)切片提供了保障。網(wǎng)絡(luò)切片可以支持不同服務(wù)需求的業(yè)務(wù)場(chǎng)景[2]，能夠顯著降低移動(dòng)虛擬網(wǎng)絡(luò)運(yùn)營(yíng)商(Mobile Virtual Network Operator,MVNO)運(yùn)營(yíng)過程中的資本支出和運(yùn)營(yíng)成本[3]。文獻(xiàn)[4]結(jié)合5G網(wǎng)絡(luò)和網(wǎng)絡(luò)切片技術(shù)，制定了緩存策略和資源分配策略，最大化了5GC-RAN的系統(tǒng)收益。文獻(xiàn)[5]提出了5G核心網(wǎng)切片，為增加網(wǎng)絡(luò)運(yùn)營(yíng)商的收入，綜合慮了延時(shí)約束，確定了聯(lián)合緩存分配和延時(shí)控制的資源分配方案(Joint Cache Allocation and Delay Control,JCADC)。雖然上述研究考慮了不同網(wǎng)絡(luò)需求條件下的緩存資源分配方案，降低了延時(shí)，但缺少對(duì)緩存成本的研究。為降低緩存的成本，文獻(xiàn)[6]在5G網(wǎng)絡(luò)中部署端到端網(wǎng)絡(luò)切片，考慮了核心網(wǎng)和無線接入網(wǎng)的不同成本需求，依據(jù)請(qǐng)求數(shù)量定義了緩存成本函數(shù)，并利用排序算法解決分層緩存資源共享問題。文獻(xiàn)[7]為降低端到端延時(shí)，結(jié)合緩存資源和帶寬資源需求，探討了基站間的協(xié)作緩存問題。雖然上述研究考慮了在網(wǎng)絡(luò)節(jié)點(diǎn)中加入緩存功能，但缺乏對(duì)傳輸能耗的考慮。

多接入邊緣計(jì)算(Multiple-Access Edge Computing,MEC)具有網(wǎng)絡(luò)緩存功能，能夠?qū)崿F(xiàn)和核心云之間的靈活調(diào)度，促進(jìn)了信息中心網(wǎng)絡(luò)(Information-Centric Network,ICN)服務(wù)與5G網(wǎng)絡(luò)切片的結(jié)合。文獻(xiàn)[8]為降低用戶和遠(yuǎn)程云之間的傳輸能耗，提出了協(xié)作式的MEC緩存分配和計(jì)算分載方案。文獻(xiàn)[9]提出了一種基于ICN的分層主動(dòng)緩存方法，根據(jù)用戶未來需求和移動(dòng)性確定緩存的位置。ICN不再以主機(jī)為中心，而是以內(nèi)容為中心，并提供網(wǎng)絡(luò)內(nèi)置緩存功能[10]。文獻(xiàn)[11]基于名稱在域內(nèi)部署ICN切片，使用戶可以在最近的地方獲得緩存內(nèi)容，降低了傳輸能耗。文獻(xiàn)[12]從ICN組網(wǎng)和服務(wù)提供的角度提出了一個(gè)ICN切片框架，優(yōu)化了虛擬內(nèi)容放置的問題，節(jié)省了傳輸能耗。上述研究提高了運(yùn)營(yíng)商收益，但缺少對(duì)緩存成本和傳輸能耗的綜合考慮。

博弈論與其他方法相比，能夠考慮一個(gè)或多個(gè)實(shí)體在特定約束條件下對(duì)局中利益相關(guān)方的優(yōu)化策略，能夠綜合考慮多個(gè)制約因素，如文獻(xiàn)[13]利用博弈論研究了內(nèi)容提供商和不同ICN實(shí)體間緩存和定價(jià)的相互作用。文獻(xiàn)[14]為激勵(lì)內(nèi)容提供商主動(dòng)緩存，提出了一種基于博弈的激勵(lì)性主動(dòng)緩存機(jī)制。文獻(xiàn)[15]通過使用納什討價(jià)還價(jià)博弈來關(guān)注延遲和能耗的聯(lián)合優(yōu)化，保證了良好的公平性。因此，博弈論可以用來研究切片中內(nèi)容提供者和網(wǎng)絡(luò)運(yùn)營(yíng)商之間的資源分配問題。

然而，博弈中的緩存分配問題需要進(jìn)一步優(yōu)化。為實(shí)現(xiàn)資源的有效分配，文獻(xiàn)[16]利用基于灰狼算法的群體智能算法實(shí)現(xiàn)功率的優(yōu)化分配，為解決資源分配提供了方向。為提高問題的準(zhǔn)確性，文獻(xiàn)[17]利用遺傳放置算法(Genetic Placement,GP) 解決了緩存資源的分層放置問題,有效降低了用戶請(qǐng)求的時(shí)延，提高了緩存放置的準(zhǔn)確性，但需要耗費(fèi)較長(zhǎng)的計(jì)算時(shí)間。

目前對(duì)于緩存問題有以下難點(diǎn)：首先，運(yùn)營(yíng)商收益問題不容忽視；其次，忽略了MVNO的部署成本和傳輸成本的聯(lián)合問題；最后，緩存分配的位置問題有待解決。因此，本文提出了一種基于改進(jìn)遺傳算法的聯(lián)合緩存成本和傳輸能耗的緩存策略。

1 網(wǎng)絡(luò)架構(gòu)和系統(tǒng)模型

1.1 網(wǎng)絡(luò)架構(gòu)

ICN網(wǎng)絡(luò)切片系統(tǒng)架構(gòu)如圖1所示，其中，MVNO為ICN切片提供者，內(nèi)容提供商(Content Provider,CP)為網(wǎng)絡(luò)切片資源消耗者。網(wǎng)絡(luò)切片中ICN用戶設(shè)備(ICN User Equipment,ICN-UE)通過gNB接入網(wǎng)絡(luò)，由MEC或ICN網(wǎng)關(guān)(ICN Gateway,ICN-GW) 提供緩存資源。ICN-GW離用戶較遠(yuǎn)，MEC更靠近用戶。由核心控制器執(zhí)行本文算法，選擇最優(yōu)緩存位置和緩存數(shù)量。用戶平面功能(User Plane Function,UPF)提供分流功能[18]，如果MEC緩存了內(nèi)容，則直接由MEC提供，否則由原路徑返回。

圖1 ICN切片系統(tǒng)架構(gòu)

1.2 系統(tǒng)模型

對(duì)于任一CP，排名為k的內(nèi)容出現(xiàn)的概率服從Zipf分布，表示為p(k)=z/kβ，z為常數(shù)，β為Zipf指數(shù)。若CP放置kn個(gè)流行內(nèi)容表示為

(1)

ICN-MVNO的支出綜合考慮了內(nèi)容傳輸所花費(fèi)的能耗和內(nèi)容緩存花費(fèi)的成本：

cost=λ1a+λ2w。

(2)

式中:cost為ICN-MVNO的總支出；w為傳輸能耗花費(fèi)；a為緩存成本花費(fèi)；λ1為緩存成本所占的權(quán)重；λ2為傳輸能耗所占的權(quán)重。

1.3 一主多從的Stackelberg博弈

博弈主要分為博弈方、策略、利潤(rùn)函數(shù)三個(gè)要素。Stackelberg博弈能夠?qū)崿F(xiàn)不同參與者利潤(rùn)的最大化，主導(dǎo)者是ICN-MVNO，策略是為每單位緩存資源制定價(jià)格p。博弈跟隨者是CP，策略是請(qǐng)求緩存資源的數(shù)量kn。

當(dāng)ICN-MVNO緩存一定的資源后，由于CP購買緩存資源需要一定的成本，CPn的收入會(huì)隨著緩存能力的增加而放緩，αn為每個(gè)CPn的成本系數(shù)，CPn的收入可以表示為

(3)

ICN-MVNO的收入為CP所花費(fèi)的成本，支出是緩存kn數(shù)量的資源時(shí)的緩存成本以及傳輸成本：

(4)

(5)

式(5)中：an為緩存到MEC所需花費(fèi)的成本；xn,j∈{0,1}；xn,CN∈{0,1}代表的是CPn是否會(huì)選擇mj節(jié)點(diǎn)和CN節(jié)點(diǎn)。

在這個(gè)過程中，綜合考慮了內(nèi)容緩存和能量消耗，目的是選擇一個(gè)能夠滿足CP需求并且綜合費(fèi)用低的節(jié)點(diǎn)。

1.4 納什均衡解存在性及唯一性

Stackelberg博弈可以通過找出其完美的納什均衡來獲得。本文在給定ICN-MVNO的定價(jià)后，CP間屬于非合作博弈，每一個(gè)理性的參與者都不會(huì)有單獨(dú)改變策略的沖動(dòng)[19]時(shí)，即存在納什均衡解。

證明：給定緩存資源的價(jià)格下，博弈參與者數(shù)量有限，式(3)中函數(shù)的一階偏導(dǎo)數(shù)為

(6)

根據(jù)公式(12)和公式(13)的一階導(dǎo)數(shù)定理，公式(6)得到的極大值點(diǎn)為

(7)

公式(3)的二階偏導(dǎo)數(shù)可計(jì)算為

(8)

(9)

公式(4)得到最優(yōu)緩存數(shù)量下關(guān)于p的一階偏導(dǎo)函數(shù)見公式(10)，二階偏導(dǎo)函數(shù)見公式(11)。αn>0,λ1,λ2≥0,an,aCN>0,kn>0,0<β<1,p>0時(shí)每個(gè)參與者的策略空間的集合都是歐氏空間有界閉集合，且利潤(rùn)函數(shù)在其策略空間上連續(xù)且公式(3)和公式(4)關(guān)于kn和p的函數(shù)是準(zhǔn)凹的，所以博弈存在納什均衡解。

xn,CNkn(λ1aCN+λ2wb))=

(10)

(11)

(12)

(13)

2 資源分配算法

2.1 分層緩存位置求解

遺傳算法(Genetic Algorithm,GA)可以用來解決博弈問題以及0-1背包問題[20]，直接對(duì)結(jié)構(gòu)對(duì)象操作，具有更好的全局尋優(yōu)能力，相較于其他的啟發(fā)式算法得到的解集更加趨近于全局最優(yōu)。圖2展示了GA算法的流程圖。為了防止丟失個(gè)體，本文使用“精英選擇”策略將在進(jìn)化過程中最好的個(gè)體直接復(fù)制到下一代和“相似性交叉方法”使相似性較低的染色體交叉作用。

圖2 遺傳算法基本步驟

CP內(nèi)容緩存的位置無法確定，是NP問題，其中costs和costt分別為成本和能耗的聯(lián)合成本函數(shù)：

cost(kn)=xn,jcosts+xn,CNcostt。

(14)

遺傳算法選擇最優(yōu)的個(gè)體，或者達(dá)到最大迭代次數(shù)，稱之為一代[21]。本文將公式(4)作為適應(yīng)度函數(shù)。xn,j表示為染色體的基因，表示的是第n個(gè)CP是否將內(nèi)容緩存在第j個(gè)節(jié)點(diǎn)，最大迭代次數(shù)為It，種群數(shù)目為I。染色體表示為Xi=(xn,1,xn,2,…,xn,M+1)，種群X=(X1,X2,…,XI)。如果對(duì)應(yīng)個(gè)體沒有節(jié)點(diǎn)響應(yīng)CP的請(qǐng)求，則應(yīng)該重新初始化個(gè)體，直到滿足條件。如果一個(gè)CP與多個(gè)存儲(chǔ)點(diǎn)配對(duì)，則應(yīng)選擇利潤(rùn)最大且滿足約束條件的節(jié)點(diǎn)緩存；否則，應(yīng)重新初始化該個(gè)體。算法對(duì)于Xi被選擇用于繁育后代的概率為

(15)

輪盤每圈的概率隨機(jī)生成的，ξw∈U(0,1)，當(dāng)滿足PPw-1<ξw

根據(jù)相關(guān)性矩陣區(qū)分染色體，將相似性較低的染色體進(jìn)行交叉操作，防止產(chǎn)生不必要的染色體[24]：

(16)

突變概率Pm的典型值在0.005%～0.05%的范圍內(nèi)。在此之后進(jìn)行修訂操作，移除不符合要求的染色體，如果CP尚未向ICN-MVNO發(fā)送與新個(gè)體中一種或多種個(gè)體相對(duì)應(yīng)的請(qǐng)求，則該個(gè)體將被上一代種群中的相應(yīng)個(gè)體替換。

改進(jìn)的遺傳算法(Elite Correlative Genetic Algorithm,ECGA) 綜合考慮了內(nèi)容傳輸能耗和緩存成本，并將ICN-MVNO的利潤(rùn)函數(shù)作為該算法的適應(yīng)度函數(shù)，通過對(duì)個(gè)體進(jìn)行精英選擇、相關(guān)性交叉、突變、修訂操作，獲得最佳的緩存分配位置X。ECGA算法(算法1)偽代碼如下所示：

Input:初始種群X,種群數(shù)量I，緩存節(jié)點(diǎn)集合w+1，CP集合S,ICN-MVNO的價(jià)格p,緩存容量集合S,最大種群迭代次數(shù)It。

1 根據(jù)公式(7)和初始價(jià)格p,獲得緩存數(shù)量請(qǐng)求列表kn；

2 for it=1,2,3,…,It do

3 通過公式(4)和公式(5)獲得Xi-1的適應(yīng)度確定適應(yīng)函數(shù)R和可行的解決方案。

4 根據(jù)公式(15)計(jì)算個(gè)體選擇概率PX

5 根據(jù)概率PX選擇個(gè)體

6 ifRIM(Xi-1)>RIM(Xi) then

7X=X+Xi-1

8 根據(jù)公式(16)，計(jì)算相關(guān)性矩陣

9 根據(jù)相關(guān)性矩陣交叉操作

10 根據(jù)Pm突變

11 修訂并消除重復(fù)個(gè)體

13 end if

14 it=it+1

15 end for

2.2 博弈求解過程

博弈首先評(píng)估CP的緩存情況，輸入初始價(jià)格p。初始化后，CP間競(jìng)爭(zhēng)緩存資源，ICN-MVNO尋找最優(yōu)價(jià)格。算法1根據(jù)ICN-MVNO的收益尋找收益值最大的點(diǎn)，并將每個(gè)節(jié)點(diǎn)對(duì)應(yīng)的收益值放入存儲(chǔ)庫中，以便下一步計(jì)算使用。當(dāng)價(jià)格不隨緩存數(shù)量和位置的變化而變化或達(dá)到最大迭代次數(shù)時(shí)，博弈迭代(Iteration of Game,IToG)算法(算法2)停止并輸出最優(yōu)的價(jià)格和緩存數(shù)量。算法2的偽代碼如下：

Input:CP集合N，緩存節(jié)點(diǎn)集合M+1，緩存資源請(qǐng)球數(shù)量kn,緩存容量集合S,最大迭代次數(shù)T。

1 根據(jù)博弈跟隨者CP請(qǐng)求的資源數(shù)量確定博弈領(lǐng)導(dǎo)者ICN-MVNO的初始價(jià)格p；

2 whilet≤Tdo

當(dāng)前，人工智能正處于高速發(fā)展階段，其發(fā)展方向、發(fā)展邊界尚不清晰，導(dǎo)致規(guī)范什么和怎么規(guī)范并無統(tǒng)一認(rèn)識(shí)。盡管爭(zhēng)論不斷，但人工智能在很多方面開始受到監(jiān)管，相關(guān)法律法規(guī)正在孕育。這些努力不一定是制定規(guī)范人工智能發(fā)展的普遍原則，更多的是對(duì)涉及人工智能技術(shù)應(yīng)用的具體領(lǐng)域的規(guī)范，如隱私保護(hù)、網(wǎng)絡(luò)安全、反商業(yè)和金融欺詐行為，以及交通、健康、就業(yè)等領(lǐng)域的安全保障等。大多數(shù)規(guī)范并不特別適合人工智能，隨著人工智能的發(fā)展還在不斷引發(fā)新的問題?？梢哉J(rèn)為，人工智能應(yīng)用到哪里，人工智能引發(fā)的問題出現(xiàn)到哪里，人工智能的立法領(lǐng)域就應(yīng)延伸到哪里。目前討論來看，人工智能涉及的法律問題主要有以下幾個(gè)。

3 ICN-MVNO確定需要緩存CP的資源數(shù)量為kn

4 ICN-MVNO根據(jù)算法1確定緩存節(jié)點(diǎn)位置Xi

7 else

8 根據(jù)算法1重新定義緩存節(jié)點(diǎn)

9 end if

10 ICN-MVNO通過緩存位置和數(shù)據(jù)重新定義緩存價(jià)格

12p←p′

13t=t+1

14 CP評(píng)估是否更改放置緩存資源的數(shù)量

17 end while

18 end if

19 end while

2.3 復(fù)雜度分析

假設(shè)算法1收斂于itst，復(fù)雜度為O(I3)，因此，ECGA算法的復(fù)雜度為itst×O(I3)。ECGA算法考慮了交叉特性，計(jì)算復(fù)雜度略高于貪婪算法復(fù)雜度以及灰狼算法的復(fù)雜度，但在犧牲復(fù)雜度的同時(shí)提高了最優(yōu)解的精度，并且ECGA算法復(fù)雜度低于GP算法的復(fù)雜度T×O(G×K3×I4)。博弈策略X和p不斷更新，直到達(dá)到納什均衡解，因此算法2的復(fù)雜度為O(t)。

3 仿真與分析

3.1 仿真設(shè)置

本文使用的計(jì)算機(jī)配置為Intel(R) Core(TM) i5-6300HQ CPU @2.30 GHz和16RAM，并對(duì)Matlab R2018b的仿真結(jié)果進(jìn)行了分析。網(wǎng)絡(luò)環(huán)境由3個(gè)CP、3個(gè)MEC和1個(gè)ICN-GW組成，sj=100，ICN-GW的容量設(shè)置為MEC的2倍。與貪婪搜索(Iteration Greedy Search,IGS)算法[25]、JCADC算法和隨機(jī)的選擇節(jié)點(diǎn)分配緩存(Random Cache Allocation,RCA)算法[26]進(jìn)行了對(duì)比。最初將λ1、λ2設(shè)置為等值，再根據(jù)試錯(cuò)機(jī)制進(jìn)行調(diào)整[27]。仿真參數(shù)設(shè)置為aCN=3,ε=0.001,β=0.8,an設(shè)置為定價(jià)p的一半,ωa=10-8J/b,ωb=2.7×10-8J/b[28]。

3.2 可行性分析

為了驗(yàn)證算法的可行性，將ECGA算法與GP算法進(jìn)行對(duì)比，如圖3所示。由于個(gè)體需要相關(guān)性交叉操作，本文算法在開始時(shí)的收斂速率低于GP算法。由圖可知，本文算法遺傳代數(shù)收斂于第300代，與收斂于400代的GP算法相比收斂性較好，具有較快的計(jì)算時(shí)間，復(fù)雜度較低。

圖3 優(yōu)化過程

3.3 收益變化情況

圖4表明隨著迭代次數(shù)的增大，ICN-MVNO和CP的利潤(rùn)函數(shù)收斂到定值。ICN-MVNO和CP的博弈是參與者策略交互的過程，經(jīng)過迭代后能夠使得緩存分配收斂到納什均衡。還對(duì)比了αn=30和αn=20的收益情況，ICN-MVNO和CP的收益值都隨著αn的升高而增大。

圖4 不同αn下的ICN-MVNO和CP收益變化情況

圖5分析了權(quán)重因子λ1和Zipf分布指數(shù)β對(duì)ICN-MVNO的收益的影響。在β相同時(shí)，可以看出λ1=0.3比λ1=0.5的收益高，表明運(yùn)營(yíng)商更加關(guān)注傳輸能耗花費(fèi)。當(dāng)λ1相同時(shí)，β=0.8時(shí)的收益高于β=0.3時(shí)的收益，表明內(nèi)容提供商放置的內(nèi)容越流行，ICN-MVNO的收益越高。

圖5 λ1和β對(duì)ICN-MVNO的收益的影響

圖6說明了不同算法下ICN-MVNO的收益變化情況。IGS算法考慮了傳輸能耗，但缺少對(duì)資源成本的研究，降低了運(yùn)營(yíng)商的收益，得到穩(wěn)定解(60,270.349)。JCADC算法綜合考慮了核心網(wǎng)節(jié)點(diǎn)緩存成本和延時(shí)需求，在一定程度上增加了內(nèi)容傳輸?shù)哪芎模玫椒€(wěn)定解(60,249.842)。本文算法穩(wěn)定解為(60,360.244)，與IGS、JCADC算法相比，運(yùn)營(yíng)商的收益分別提高了32%、44%，且收斂性最好。

圖6 不同算法的ICN-MVNO收入對(duì)比

3.4 能量節(jié)省率

圖7對(duì)比了本文算法和IGS、JCADC和RCA的能量節(jié)省率，可以看出IGS、JCADC、ITOG算法的節(jié)省率隨著CP數(shù)量的增多而上升，在CP等于4時(shí)達(dá)到最大。由圖中可以得出，本文算法與IGS、JCADC算法相比，傳輸能耗分別節(jié)省了5%、11%。由于算法在開始尋找最優(yōu)解時(shí)需要耗費(fèi)大部分能量，因此，IGS具有較高節(jié)省率。而JCADC算法考慮了延時(shí)的控制能力，能量節(jié)省率較低，并且下降速率較快。

圖7 不同算法的能量節(jié)省率對(duì)比

3.5 博弈迭代解

圖8說明了ITOG求得的納什均衡解。ICN-MVNO制定一個(gè)較高緩存價(jià)格p，CP根據(jù)資源價(jià)格p調(diào)整購買緩存資源的數(shù)量，兩個(gè)參與者不斷更新策略，最終得到穩(wěn)定解(4.7,69)，即CP和ICN-MVNO之間達(dá)到納什均衡。

圖8 納什均衡解

4 結(jié)束語

本文考慮了具有ICN-GW和多個(gè)MEC的5G-ICN切片分層緩存架構(gòu)，通過博弈方法最大化ICN-MVNO和CP的利潤(rùn)函數(shù)，并根據(jù)ITOG算法得到最佳緩存數(shù)量和價(jià)格。在解決分層問題時(shí)，本文利用ECGA算法確定分層緩存分配方案。該算法具有較高的有效性以及較好的緩存資源分配能力，能夠降低傳輸能耗和緩存成本，提高運(yùn)營(yíng)商的收益。未來為綜合考慮運(yùn)營(yíng)商收益和延時(shí)需求，我們將對(duì)MEC節(jié)點(diǎn)的部署和動(dòng)態(tài)重配置作進(jìn)一步研究。