面向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ù)場景[2]，能夠顯著降低移動虛擬網(wǎng)絡(luò)運營商(Mobile Virtual Network Operator,MVNO)運營過程中的資本支出和運營成本[3]。文獻[4]結(jié)合5G網(wǎng)絡(luò)和網(wǎng)絡(luò)切片技術(shù)，制定了緩存策略和資源分配策略，最大化了5GC-RAN的系統(tǒng)收益。文獻[5]提出了5G核心網(wǎng)切片，為增加網(wǎng)絡(luò)運營商的收入，綜合慮了延時約束，確定了聯(lián)合緩存分配和延時控制的資源分配方案(Joint Cache Allocation and Delay Control,JCADC)。雖然上述研究考慮了不同網(wǎng)絡(luò)需求條件下的緩存資源分配方案，降低了延時，但缺少對緩存成本的研究。為降低緩存的成本，文獻[6]在5G網(wǎng)絡(luò)中部署端到端網(wǎng)絡(luò)切片，考慮了核心網(wǎng)和無線接入網(wǎng)的不同成本需求，依據(jù)請求數(shù)量定義了緩存成本函數(shù)，并利用排序算法解決分層緩存資源共享問題。文獻[7]為降低端到端延時，結(jié)合緩存資源和帶寬資源需求，探討了基站間的協(xié)作緩存問題。雖然上述研究考慮了在網(wǎng)絡(luò)節(jié)點中加入緩存功能，但缺乏對傳輸能耗的考慮。

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

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

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

目前對于緩存問題有以下難點：首先，運營商收益問題不容忽視；其次，忽略了MVNO的部署成本和傳輸成本的聯(liá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離用戶較遠，MEC更靠近用戶。由核心控制器執(zhí)行本文算法，選擇最優(yōu)緩存位置和緩存數(shù)量。用戶平面功能(User Plane Function,UPF)提供分流功能[18]，如果MEC緩存了內(nèi)容，則直接由MEC提供，否則由原路徑返回。

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

1.2 系統(tǒng)模型

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

(1)

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

cost=λ1a+λ2w。

(2)

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

1.3 一主多從的Stackelberg博弈

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

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

(3)

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

(4)

(5)

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

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

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

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

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

(6)

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

(7)

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

(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ù)在其策略空間上連續(xù)且公式(3)和公式(4)關(guān)于kn和p的函數(shù)是準凹的，所以博弈存在納什均衡解。

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

(10)

(11)

(12)

(13)

2 資源分配算法

2.1 分層緩存位置求解

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

圖2 遺傳算法基本步驟

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

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

(14)

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

(15)

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

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

(16)

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

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

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

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

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

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

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

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

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

7X=X+Xi-1

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

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

10 根據(jù)Pm突變

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

13 end if

14 it=it+1

15 end for

2.2 博弈求解過程

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

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

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

2 whilet≤Tdo

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

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

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

7 else

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

9 end if

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

12p←p′

13t=t+1

14 CP評估是否更改放置緩存資源的數(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算法考慮了交叉特性，計算復(fù)雜度略高于貪婪算法復(fù)雜度以及灰狼算法的復(fù)雜度，但在犧牲復(fù)雜度的同時提高了最優(yōu)解的精度，并且ECGA算法復(fù)雜度低于GP算法的復(fù)雜度T×O(G×K3×I4)。博弈策略X和p不斷更新，直到達到納什均衡解，因此算法2的復(fù)雜度為O(t)。

3 仿真與分析

3.1 仿真設(shè)置

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

3.2 可行性分析

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

圖3 優(yōu)化過程

3.3 收益變化情況

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

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

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

圖5 λ1和β對ICN-MVNO的收益的影響

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

圖6 不同算法的ICN-MVNO收入對比

3.4 能量節(jié)省率

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

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

3.5 博弈迭代解

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

圖8 納什均衡解

4 結(jié)束語

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