移動邊緣網絡中的多目標緩存優化方法

吳 越,薛釗煜,郭婉婉,崔志華

(太原科技大學 計算機科學與技術學院,太原 030024)

0 引 言

隨著信息技術的快速發展,各種社交媒體、視頻網站的發展十分迅速,用戶量快速增長,大量的網絡通信流量對基站造成了巨大的壓力.基于移動邊緣計算(MEC)的緩存方法利用邊緣網絡靠近用戶的特點和感知與存儲能力,將數據放置于靠近用戶的邊緣節點上,能夠有效降低網絡負載、提升服務質量.但是在邊緣網絡環境中,每個邊緣節點的可用緩存空間十分有限,因此如何合理的利用有限的緩存空間將流行度更高的內容放置于合適的位置成為了關鍵問題.

為了提高MEC緩存的性能,研究人員做出了許多工作.文獻[1,2]使用基于貝葉斯的流行內容預測來制定緩存預取方案;文獻[3]將存儲資源和計算資源推到網絡邊緣,基于長短期記憶(LSTM)神經網絡預測內容流行度,將預測結果應用于緩存方案的制定;文獻[4]基于博弈論的思想將邊緣網絡中的節點看做博弈者,決定自身的緩存策略來達到最大緩存收益,在博弈中達到納什均衡并據此設計了一種分布式均衡算法;文獻[5]基于多臂強盜方法設計的解決如何估計未知用戶偏好,并提出了一種基于多智能體擴展單抗的解決方案,實現了分散的緩存放置策略;文獻[6]使用神經網絡模型預測未來可能的用戶請求,并通過聯合優化延遲和能耗來制定緩存方案;文獻[7]使用Zipf定律估計用戶偏好,將目標建模為延遲最優,提出了基于改進KM(Kuhn-Munkres)的內容放置方法;文獻[8]從服務運營商的角度將數據緩存問題表述為一個約束優化問題,優化目標位延遲最低,用整數規劃的方法來解決優化問題;文獻[9]結合了基于長短期記憶(LSTM)的局部學習和基于集成的元學習來提高預測性能繼而提高緩存命中率.以上研究主要針對估計用戶偏好,根據估計的用戶偏好進行緩存決策,雖然能夠提高緩存性能,但考慮緩存問題的角度單一,不能滿足多樣化的緩存需求.

針對復雜的緩存需求,文獻[10]將RAN建模為一個區域,通過劃分區域的方式簡化問題,將緩存問題表述為一個混合整數線性規劃模型,文獻[11]同樣使用區域劃分的方式建模,提出基于博弈論的緩存放置策略;文獻[12,13]從服務提供商的角度考慮,在滿足訪問延遲約束的前提下最大化服務提供商的利益;文獻[14-16]使用數據訪問計數、數據訪問頻率和數據大小作為優化目標的多目標優化數據緩存模型,結合了蟻群算法和遺傳算法進行求解;文獻[17]為了克服緩存污染問題,提出了LRU-GENACO,該方法結合了LRU、ACO和GA算法,其中LRU算法被分配用于解決緩存污染問題,而混合ACO-GA在緩存數據被消除之前優化緩存數據選擇;[18]使用評估的緩存值、數據對象獲取和替換成本將緩存放置問題建模,使用禁忌搜索算法求解模型;文獻[19]提出了一種基于貪心算法的云邊緣協同緩存模型和相應算法,以降低負載提高緩存命中率;文獻[20]提出了歸一化布谷鳥搜索算法聯合優化延遲、功耗、連接成功率;文獻[21]基于博弈論的思想研究了聯合優化中如何公平的處理具有競爭關系的優化目標,將QoE和能量效率作為博弈對象,置于納什均衡模型中,并提出了一個公平的多回合博弈算法;文獻[22]提出了一種基于多臂強化學習的實用感知協作服務緩(UACSC)方案,以協調多個邊緣服務器以做出動態聯合緩存決策,在最小化緩存成本的同時優化服務延遲.文獻[23]將STP和平均傳輸延遲建模為一個多目標優化問題,以最大化STP或最小化延遲為目標,并建立了多目標緩存布局優化問題.提出了一種新的投影多目標杜鵑搜索算法(PMOCSA),以獲得最優緩存布局的解決方案.上述研究考慮了多樣化的緩存需求,大部分通過將多目標轉化為單目標的方式聯合優化,然而多個目標之間的關系難以區分、不易比較,不同目標的權重參數確定方式十分主觀,尤其是目標之間互相沖突時會使加權目標函數的結構十分復雜,權重參數需要在優化開始前確定,在迭代過程中無法干預,這使得優化結果難以使人滿意.

綜上本文站在不同的角度觀察MEC緩存方案得到了不同的需求[24]:用戶希望能在更短的時間內得到響應獲得所訪問的內容;網絡提供商希望使得邊緣節點的負載盡可能地低,緩存效率更高;服務提供商則希望降低緩存成本的支出.為了使多個利益相關方均能收益,提升系統整體性能,本文構建了一個考慮3個目標的邊緣緩存模型,并設計了一種基于最遠交配和淘汰策略的多目標進化算法(MOEA-FMES).

本文的重要貢獻總結如下:

1)構建了一個考慮用戶時延、緩存存儲成本和邊緣節點傳輸能耗的多目標緩存模型,以提高系統的整體性能,使得不同的利益相關方均能從中收益.

2)為了求解所提出的緩存模型,設計了MOEA-FMES,采用基于參考向量的最遠距離選擇來選擇父代個體;采用一種基于BDE和歐式距離的動態適應度值算子;在環境選擇中循環淘汰機制選出下一代種群.

3)為了驗證所提方法的有效性、評估提出算法,設計了模擬仿真試驗,通過對比AGEII、IBEA、SPEA/R、NSGAII、VaEA和MOEA-FMES說明了本文提出方法的有效性.

1 模型設計

1.1 網絡模型

邊緣云計算環境是多層網絡架構,包括云計算層、邊緣計算層和終端層.為了能夠更為高效的利用邊緣網絡資源來提升服務效率,需要將高流行度的緩存內容放置在合適的邊緣節點.不同的放置方案會產生不同的影響、收益,如前文所述,MEC緩存中的利益相關方之間互相沖突.

本文考慮如圖1所示的網絡架構,包含一個宏基站(MBS)和M個小基站(SBS),宏基站通過光纖鏈路與云網絡連接,通過BS鏈路與SBS連接;每個SBS與不等數量的用戶設備(UE)連接,MBS中存儲整個內容庫,考慮到實際情況中的內容大小不同,本文假設內容庫包含N個大小不等的內容,記為D={d1,d2,…,dN},內容大小服從參數為α的正態分布.使用E={e1,e2,…,eM}表示SBS集合,SBS的存儲容量有限,容量大小記為C.將用戶連接的SBS稱為本地SBS,當UE所請求的內容不在本地SBS中時,可以向一跳友鄰SBS請求內容,若一跳友鄰SBS也沒有緩存內容時,向MBS請求內容,SBS之間的關聯情況由Z={zm1,zm2,…,zMM}表示,zmm=1表示互相連接,否則表示不連接,Y={y1,y2,…,yN}表示SBS連接的用戶的數量的集合,本文假設在時隙t內Y服從參數為δ的泊松分布.X={xm1,xm2,…,xmn}表示緩存方案,xmn表示基站em是否緩存內容dn,1表示緩存該內容,0則表示不緩存該內容.

圖1 MEC結構Fig.1 MEC structure

1.2 緩存模型

本文考慮在時隙t內的緩存內容放置方案,假設在時隙t內內容的流行度基本穩定不變.齊普夫(Zipf)定律被用于估計內容的流行度已經被證明了其有效性,許多的研究也基于假設滿足該定律展開,如文獻[25]證明YouTube上的內容流行度服從Zipf分布.因此本文假設內容流行度服從Zipf分布.內容庫中包含N個內容,并按照訪問次數進行降序排序P={p1,p2,…,pN},表示內容的請求概率分布,pi表示第i個內容被請求概率,概率值由公式(1)按照Zipf計算:

(1)

式中γ為參數控制分布的密集程度.

SBS、MBS向所連接的設備發送數據的速率V由公式(2)得出:

(2)

式中y表示所連接的設備數量,B為帶寬,Q為平均發射功率,μ為噪聲功率.SBS的緩存空間大小記為C.

1.3 優化目標

本文針對MEC緩存中不同利益方的需求,提出了3個優化目標,分別為延遲、緩存成本、基站傳輸功耗.當用戶請求的內容不在本地SBS時,僅向一跳友鄰SBS或MBS發起請求.因此本文中所計算的延遲、傳輸功耗需要綜合考慮不同的情況進行計算,即a)請求的內容緩存于本地SBS時,直接向用戶返回內容;b)請求的內容未緩存與本地SBS但緩存于友鄰SBS時,首先將請求的內容發送至本地SBS,再由本地SBS發送給用戶;c)當請求的內容本地SBS與友鄰SBS均未緩存時,先由MBS發送至本地SBS,再由本地SBS發送給用戶.delay(m)表示某個SBS所連接用戶的延遲,計算方式由公式(3)給出.cost(m)表示某個SBS所緩存的內容大小,用于衡量緩存成本計算方式由公式(4)給出,用于衡量存儲成本,power(m)表示某個SBS提供服務時的傳輸功耗,計算方式由公式(5)給出.

delay(m)=t1+t2+t3

(3)

(4)

power(m)=Qst1+Qst2+QMt3

(5)

其中t1為情況a下的延遲;t2為情況b下的延遲;t3為情況c下的延遲.

(6)

(7)

(8)

式中BS,BM分別表示SBS和MBS的帶寬,QM,QS分別表示SBS和MBS的平均發射功率.

那么可以得到3個互相沖突的目標,分別是:用戶平均延遲f1,SBS平均緩存成本f2,平均傳輸功耗f3.由于本文考慮的SBS的緩存空間大小有限且一致,故每個SBS所緩存的內容大小必須不大于C.

因此MEC緩存多目標優化問題可以表述為:

(9)

顯然的,延遲與緩存是否命中相關,節點緩存的內容越多緩存命中的可能性越高將會使得平均延遲越低,而這將導致緩存成本變高,所以f1與f2互相是沖突的.另外當緩存命中時本地SBS直接向服務的用戶發送數據,而未命中時則需要友鄰SBS或MBS先向本地SBS發送數據再由本地SBS發送給服務的用戶,所以節點緩存內容增加將使得平均傳輸功耗降低,故而f2與f3互相沖突.由于MBS發射功率高于SBS,因此當友鄰節點緩存了本地所請求的內容時本地SBS無需向MBS請求數據從而降低了功耗但相應的提高了延遲,因此f1與f3也是互相沖突的.圖2(a)～圖2(c)展示了求解本文時模型不同目標值之間的關系,通過觀察圖中解的分布也能得出相同的結論.

圖2 目標值關系圖Fig.2 Objective value relation diagram

2 算法改進

上述問題是一個非凸優化問題,進化算法是解決大規模非凸優化問題的一種有效方法.再過去的十數年中,研究者們提出了多種高性能多目標進化算法.這些算法的基本一般過程是:1)隨機生成初始種群并計算目標函數的值;2)通過交配選擇算子從種群中選擇個體,以雜交和突變產生后代種群;3)父代和子代種群被合并,下一代種群從環境選擇算子中選擇;4)重復上述操作,直到滿足終止條件.其中,匹配選擇算子和環境選擇算子極大地影響了算法的求解性能.為了更好地平衡分集和收斂,本文提出了MOEA-FMES算法,在匹配選擇時采取最遠鄰居結合的策略來增加多樣性,設計了結合SDE[23]和歐式距離的適應度值計算方式用于環境選擇算子,以平衡進化過程中的收斂性和多樣性,并且環境選擇還采用了循環淘汰的方式為下一代種群選擇優秀的個體.

2.1 算法總體描述

為了同時優化本文所提出的3個目標函數,本文提出了MOEA-FMES.如前文所述X表示一個緩存方案矩陣,表示某個SBS是否緩存某個內容,因此本文的多目標進化算法采用二進制編碼方式,種群數量記為L.

多目標進化算法總體流程如算法1中偽代碼所示.首先進行初始化設置,包括初始化種群,產生L個個體;通過混合均勻設計方法在單位超平面上精確返回L個具有M個目標的均勻分布點;對目標值進行歸一化處理,并將每個個體關聯到余弦距離最近的參考向量上,從而完成初始種群劃分.然后開始進化過程,直到達到最大迭代次數:計算參數θ;根據匹配選擇算子選擇父代種群;進行交叉變異操作產生子代種群;將父代與子代合并,并進行歸一化處理;根據環境選擇算子選擇最優的前L個個體作為下一代種群.

算法1.多目標進化算法框架

輸入：種群數量L

輸出：最終解集

1.Create an initial parent populationP

2.Generate L reference vectors W according to the MUD method

3.W=MUD()

4.Normalize objectives of members inP

5.P′:= Objective_Normalization (P)

6.Associated reference vector:

7.E(i)=Associate(P′, W)

8.while t

9. θ is calculated by Eq.8

10.P=FarthestSelection (W,E(i)) //Select the P by Matching Selection Operator

11. O=GA(P)//The Offspring population O was generated by GA

12.G=P∪O

13.G′=Objective_Normalization(P)

14.P=Environment_Selection(G′,W,θ);

15.end while

2.2 匹配選擇

匹配選擇的目的是通過高質量的父代個體進行交叉、變異,從而產生優秀的子代,是進化算法的重要組成部分.本文的匹配選擇通過選擇兩個最遠子種群中的個體即余弦距離最遠的參考向量所關聯的個體來組成父代種群.偽代碼如算法2所示.首先通過使用公式(11)計算所有參考向量之間的余弦距離:

θ=(FE/maxFE)2

(11)

然后開始選擇:從參考向量集中選擇一個w,隨機選擇一個w關聯的個體添加到Parent1中并從當前種群中刪去該個體,選擇w余弦距離最遠的參考向量w′,之后隨機選擇一個w′關聯的個體添加到Parent2中并從當前種群中刪去該個體.循環結束后合并Parent1,Parent2.

算法2.匹配選擇

輸入：參考向量W,個體關聯的參考向量集合E(i)

輸出：用于交叉變異的父代種群P

1.Wdis=cosθ(W)//by Eq.(12)

2.while length/(Parent1)

3. for w=W

4. p1=random(E(i)==w)

5. Parent1=[Parent1,p1]

6.w′=max(Wdis(w))

7. p2=random(E(i)==w)

8. Parent2=[Parent2,p2]

9. end for

10.P=[Parent1, Parent2]

11.end while

2.3 適應度計算

σ=(FE/maxFE)2

(12)

(13)

2.4 環境選擇

環境選擇的目的是從合并后的種群中選擇優秀的個體組成新的種群,新的種群應當確保個體之間保持收斂性和多樣性的平衡,從而不斷優化種群.在本文的設計中,環境選擇參考了SPEA/R[27].與SPEA/R不同的是:本文替換了適應度的計算方式,且不同于SPEA/R的適應度以多樣性優先、收斂性第二,本文根據迭代次數動態的調整多樣性與收斂性的關系;SPEA/R在一個選擇循環完成后進行下一輪循環,而本文在一個選擇循環完成后會刪去被選擇的個體并重新評估剩余個體再開始下一輪循環.

環境選擇循環的從各個參考向量的關聯個體中進行選擇.在每一輪開始時首先計算當前種群中個體的適應度值,然后從每個參考向量周圍選擇適應度值最小的個體(求解最小化問題時),選擇完一輪之后將選擇的個體添加到下一代種群中并從當前種群中刪去,直到新種群的數量達到種群數量L.之所以每選擇一輪就重新計算剩余個體的適應度值,這是因為循環選擇的目的是均勻的選擇參考向量所劃分的子種群中的優秀個體,以選擇高質量的解并提高解的均勻性,而本文在適應度的計算中考慮了個體之間的密度信息,一輪選擇循環結束之后剩余個體之間的密度信息必然會發生變化,因此有必要對剩余個體進行重新評估.雖然重新計算適應度增加了計算量但能夠更好的評估剩余個體的優劣.環境選擇的偽代碼如算法3所示.

算法3.環境選擇

輸入：歸一化目標值P′,參考向量W,平衡參數

輸出：NextP,E

1.E=Associate(P′,W)//Associate reference vector

2.while length(NextP)

3. Fit=(P′,E,σ)

4. for each reference directioni∈W

5. if E(i)≠?

6. q=argminp∈E(i)Fit(p)

7. Save q to H

8. end if

9. end for

10. remove H from P and E

11.end while

3 實驗與總結

3.1 實驗設計

為了驗證本文提出的MEC緩存方法的有效性,本文基于MATLAB 2022a軟件使用PlatEMO v3.3平臺進行仿真模擬實驗,參數設置如表1所示,并與5種多目標優化算法進行對比:AGEII[28]、IBEA[29]、SPEA/R[30]、NSGAII[31]、VaEA[32]、MaOEAPCS[33].為了保證結果的可靠性,對比算法的參數設置保持默認設置.

表1 仿真參數表Table 1 Simulation parameter table

3.2 評價指標

本文使用Spacing[34]、IGD[35]來進行性能評價,這兩個指標被廣泛使用的評估多目標優化算法,分別用于評價算法的解的多樣性、綜合性能.

1)Spacing metric (SP):

(14)

2)Inverse generation distance (IGD):

(15)

P為解集,P′為從前沿面上采樣的一組均勻分布的參考點,d(i,j)為參考集中的點i與解集中的點j之間的歐氏距離.

3.3 結果分析

在多目標問題中,每個算法都會最終給出一組非支配解集,供決策者進行決策,解集中的每個解在不同目標上的各有優劣.

表2中給出了AGEII、IBEA、NSGAII、SPEAR、VaEA、MaOEAPCS和MOEA-FMES在本文提出的MEC緩存模型上計算得到的SP、IGD值.表中用黑體著重標出了最優值,并在每個數值的后面用‘+’、‘-’、‘=’標注了對比算法與MOEA-FMES的對比情況,分別表示優于MOEA-FMES、弱于MOEA-FMES和與MOEA-FMES持平.結果顯示在IGD上MOEA-FMES表現最好,說明MOEA-FMES覆蓋了真實的帕累托前沿面,能夠給出一組高質量的非支配解集,SPEA/R和NSGAII在IGD上較為接近MOEA-FMES,而其他算法表現較差.在SP上,MOEA-FMES表現最好,說明所提出算法的解集最為均勻,種群的多樣性最好,SPEA/R在SP上的表現較為接近MOEA-FMES,而AGEII性能最差,說明其給出的解集分布不均勻,多樣性較差.

表2 評價指標對照表Table 2 Comparison table of evaluation indicators

表3中給出了AGEII、IBEA、NSGAII、SPEAR、VaEA、MaOEAPCS和MOEA-FMES對本文模型上的影響情況.通過對比不同算法給出的最終解集的不同目標值上的最優、最差、平均值來評估算法的優劣.可以看出MOEA-FMES在3個目標值上的平均、最優和最差表現均優于其他算法,表現出了良好的整體性能.具體來說在延遲方面6種算法的表現相似,無論是最優、最差還是平均值MOEA-FMES的領先幅度都很小;在緩存成本上MOEA-FMES和SPEA/R在平均、最優和最差上對于其他算法都有明顯優勢,且MOEA-FMES均能取得最優結果,說明MOEA-FMES能夠有效的降低緩存成本;在傳輸功耗方面,雖然六種算法的最優值和平均值區別較小,但在最差值上VaEA與其他算法的差距很大,MOEA-FMES在最優、最差和平均值上都優于其他算法,說明MOEA-FMES能夠有效降低傳輸功耗.

表3 6種算法在3個目標上的目標值Table 3 Target values of six algorithms on three targets

圖3中的折線圖顯示了AGEII、IBEA、NSGAII、SPEAR、VaEA、MaOEAPCS和MOEA-FMES求解本文模型的3個目標的收斂情況.本文仿真實驗最大迭代次數設為1000,可以看出在前300代收斂速度較快,之后收斂速度不斷放緩,在約900代之后收斂程度基本沒有變化.MOEA-FMES能夠使得3個目標均有效收斂,且表現最好,SPEA/R雖然也能使3個目標共同收斂,但在傳輸功耗上的收斂程度較差,而其他算法則僅能使個別目標收斂,其余目標上幾乎不收斂,導致曲線重疊,最終的收斂折線圖直觀上不易觀察到每個圖像的收斂程度,且收斂程度較低,陷入了局部最優.

圖3 解集收斂圖Fig.3 Convergence plot of the solution set

圖4中的散點圖顯示了AGEII、IBEA、NSGAII、SPEAR、VaEA、MaOEAPCS和MOEA-FMES求解本文模型得到的解集分布情況,圖中每一個小球代表一個解.可以看出SPEA/R的解在空間中的分布呈長條狀,MaOEAPCS的解集雖然分散較為均勻但最終保留的解個數過少,AGEII的解主要分布在空間的上半部分,IBEA、NSGAII、和VaEA的分布范圍較為均勻、接近,MOEA-FMES解在空間中的分布最為均勻,表明解的多樣性較好,在3個目標上均進行了有效的探索.

圖4 解集分布圖(a～g分別為AGEII、IBEA、NSGAII、SPEAR、VaEA/MaOEAPCS和MOEA-FMES)Fig.4 Solution set distribution diagram (a～g is AGEII, IBEA, NSGAII, SPEAR, VaEA, MaOEAPCS and MOEA-FMES, respectively)

這是由于MOEA-FMES的環境選擇在循環選擇中不斷地重新評估剩余個體,動態地調整收斂性和多樣性的關系,從而使得選出的個體具有更好的代表性,在匹配選擇時從兩個最遠子種群中隨機選擇個體來組成父代種群,因此MOEA-FMES不僅能夠探索更多的解空間,解集的多樣性更好,還能避免解集陷入局部最優,使算法更快地收斂且3個目標均能收斂到最優.

以上分析說明本文提出的MEC緩存模型是合理的,并且本文提出的優化算法在求解所提出的緩存模型時能夠同時優化3個目標,最終給出一組收斂性好且分布均勻的非支配解集供決策者選擇.

4 總 結

針對MEC緩存資源緊張的問題,為了提升系統整體性能,使得各個利益相關方均能從MEC中獲益,本文提出了一種兼顧延遲、緩存成本、傳輸能耗的多目標緩存模型.為了更好的求解提出的模型,提出了一種基于最遠交配和淘汰策略的多目標進化算法(MOEA-FMES),通過從具有最遠余弦距離的參考向量周圍選擇個體的方式來選擇父代個體,通過循環淘汰機制從各個參考向量的關聯個體中進行環境選擇,由于淘汰個體后會導致剩余個體的密度信息發生改變,所以每一輪選擇開始前需要重新評估剩余個體.為了評估提出的MOEA-FMES,本文進行了模擬仿真實驗,在IGD、Spacing上均表現優秀,并分析了算法的性能.在未來的工作中,將進一步完善緩存模型、改進算法來提高系統整體性能,如考慮用戶偏好的動態變化;多個用戶之間的優先性;考慮用戶的移動對緩存性能的影響.