戈麗平,周金和
(北京信息科技大學(xué) 信息與通信工程學(xué)院,北京 100101)
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)合緩存成本和傳輸能耗的緩存策略。
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)
對于任一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)重。
博弈主要分為博弈方、策略、利潤函數(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é)點。
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)
遺傳算法(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 博弈首先評估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 假設(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)。 本文使用的計算機配置為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]。 為了驗證算法的可行性,將ECGA算法與GP算法進行對比,如圖3所示。由于個體需要相關(guān)性交叉操作,本文算法在開始時的收斂速率低于GP算法。由圖可知,本文算法遺傳代數(shù)收斂于第300代,與收斂于400代的GP算法相比收斂性較好,具有較快的計算時間,復(fù)雜度較低。 圖3 優(yōu)化過程 圖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收入對比 圖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é)省率對比 圖8說明了ITOG求得的納什均衡解。ICN-MVNO制定一個較高緩存價格p,CP根據(jù)資源價格p調(diào)整購買緩存資源的數(shù)量,兩個參與者不斷更新策略,最終得到穩(wěn)定解(4.7,69),即CP和ICN-MVNO之間達到納什均衡。 圖8 納什均衡解 本文考慮了具有ICN-GW和多個MEC的5G-ICN切片分層緩存架構(gòu),通過博弈方法最大化ICN-MVNO和CP的利潤函數(shù),并根據(jù)ITOG算法得到最佳緩存數(shù)量和價格。在解決分層問題時,本文利用ECGA算法確定分層緩存分配方案。該算法具有較高的有效性以及較好的緩存資源分配能力,能夠降低傳輸能耗和緩存成本,提高運營商的收益。未來為綜合考慮運營商收益和延時需求,我們將對MEC節(jié)點的部署和動態(tài)重配置作進一步研究。2.2 博弈求解過程
2.3 復(fù)雜度分析
3 仿真與分析
3.1 仿真設(shè)置
3.2 可行性分析
3.3 收益變化情況
3.4 能量節(jié)省率
3.5 博弈迭代解
4 結(jié)束語