多云協同輔助車輛計算的資源管理策略

張文萍，陳桂芬

(長春理工大學 電子信息工程學院，吉林 長春 130022)

0 引 言

近些年如何對云計算資源進行管理以及由于云計算資源的多樣性所涉及到的卸載節點的選擇，成為車聯網領域的研究熱點[1,2]。文獻[3]提出了邊緣云(MEC)和遠程云(RC)的協同調度方案，最大限度地增加了MEC服務的任務量。文獻[4]考慮了一個路邊cloudlet系統，該系統將公共車輛作為霧節點來完成cloudlet卸載的任務。文獻[5]提出中心云和微云協同解決卸載選擇和資源分配問題的架構，采用實數-遺傳算法(IM-GA)有效降低了系統時延。文獻[6]將集中式云、cloudlet和車載云(VC)融合在一起，采用遺傳算法與自適應粒子群算法相結合的算法對資源分配和任務調度問題進行了優化研究。文獻[7]通過聯合優化卸載決策和計算資源分配問題，提出了云和邊緣計算協同解決的辦法，有效降低了任務執行時間。

以上文獻在使用云計算資源時沒有同時將VC中的個別云節點考慮在內，這些云節點不僅可以提供低延時服務，而且資源使用成本低。本文基于時延和計算資源的使用成本建立目標函數，采用改進的遺傳算法有效解決了卸載選擇和資源分配問題。

1 系統模型和問題公式化

1.1 場景描述

如圖1所示，定義一種多云協同輔助車輛計算(MCAVC)范式。MCAVC包括3部分：MEC、RC和VC，由這3部分共同為車輛用戶執行應用程序中的眾多任務，系統為其選擇任務卸載節點以及分配計算資源，目標是最小化任務完成時間和使用計算資源貨幣成本的加權和，該范式更適合城市道路。

圖1 MCAVC

MCAVC可以啟用VC中不同數量的“移動志愿云節點”(mobile voluntary cloud nodes，MVCN)，增強了MCAVC的計算可伸縮性。MVCN多為公交車。

1.2 計算節點和任務模型

Γ={1,2,3,…,M}表示卸載節點的集合，xji∈Γ，其中xji=1為車輛本身，xji=2為MEC，xji=3為RC，xji∈={4,5,…,M}為第xji-3個MVCN。∈Γ，為一個周期內與用戶車輛通信的MVCNs。

1.3 本地計算

任務Ti在本地執行時的處理時間為

(1)

fi,1為分配到的計算資源(以每秒CPU周期為單位)，本地執行不計算金錢成本。

1.4 卸載到MEC

任務Ti卸載到MEC時，任務完成時間由傳輸時間和執行時間組成。由于計算結果大小遠小于輸入數據大小，因此省略了傳回時間[8]。fi,2和R2分別為MEC分配給任務Ti的計算資源和車輛到MEC的有線鏈路上行數據速率。任務Ti的完成時間為

(2)

(3)

1.5 卸載到RC

fi,3和R3分別為RC分配給任務Ti的計算資源和車輛到RC的有線鏈路上行數據速率。任務Ti的完成時間為

(4)

(5)

1.6 卸載到MVCN

(6)

tq時刻處的傳輸速率為

(7)

式中：Wm為信道帶寬，Pr為車輛發射功率，α為路徑損耗指數，σ2為加性高斯噪聲，I為小區間干擾(假設無)。tp時刻二者結束通信，平均數據傳輸速率為

(8)

fi,m為MVCNm的計算能力，任務Ti的完成時間為

(9)

應滿足ti,m≤Δtm,?m∈。

(10)

1.7 問題公式化

將任務完成時間和使用云計算資源貨幣成本的加權和定義為系統總計算開銷。節點選擇事件定義為Z={αi,xji|i∈,xji∈Γ}，其中αi,xji=1表示任務i位于節點xji上，否則αi,xji=0。資源分配事件定義為F={fi,xji|i∈,xji∈Γ}，將總計算開銷作為目標函數，表示為

(11)

(12)

s.t.αi,xji∈{0,1},?i∈,xji∈Γ

(13)

(14)

(15)

(16)

fi,xji>0,?i∈xji,xji∈Γ

(17)

(18)

式(13)表示Z是二進制向量。式(14)確保每個計算任務只在一個計算節點上執行。式(15)和式(16)規定每個MVCN在給定的時間內最多可以接收一個任務，MVCN在與車輛用戶連接期間完成任務。式(17)規定計算節點必須給任務分配正計算資源，xji={i∈|αi,xji=1}表示分配給計算節點的任務集。式(18)確保計算節點上任務的總計算資源不超過其總容量Fxji。

2 遺傳算法求解

節點選擇是二進制變量，資源分配是連續變量，此問題為NP-hard問題，求解最優解時復雜度高，這里使用改進遺傳算法求解，可在較短時間內獲得局部最優解。

2.1 編 碼

傳統遺傳算法編碼時，基因串長度等于決策變量個數[9]，導致基因串過長，從而延緩進化速度，長時間無法收斂到最優解。現采用改進浮點編碼遺傳算法IFGA，讓浮點數整數和小數部分分別映射為卸載節點和計算資源。種群表示為

(19)

S為種群中的個體數量，Cj為個體，即一條染色體。每條染色體表示為

(20)

N為任務總數。xji為任務i的卸載位置，yji為任務i所分配到的計算資源量。計算資源的基因值為0-1之間的隨機小數，為了滿足式(17)、式(18)，將計算資源歸一化處理

(21)

2.2 適應度函數和選擇

(22)

2.3 交 叉

交叉過程如圖2所示。基因的兩個組成部分分別根據交叉概率隨機產生一個由0和1組成的N位交叉因子序列，如交叉概率為0.9，則出現1的概率為0.9。先交叉節點部分，再交叉資源部分，若交叉因子為1，則互換父代染色體相應值。若交叉因子為0，則相應值保持不變。

圖2 交叉過程

為了自適應調節，依據文獻[10]，交叉概率公式為

(23)

favg和fmax分別代表當代種群中個體適應度值的平均值和最大值，f′代表交叉個體中的較大適應度值，k1為交叉概率常數，k2為交叉概率調節系數。當f′≥favg時，為防止優秀的基因結構被破壞采用較小交叉概率。

算法1：交叉操作

(1) for a= Q：P //P為種群大小，Q為初始種群大小

(2) 選擇Xm.Ym，Xn.Yn;

(3) iffm>favg∥fn>favg

(5) else

(6)Pc=k1;

(7) end

(8) 交叉因子序列1

(9)xmo?xno//卸載位置，第o個基因值互換

(10) 交叉因子序列2

(11)ymt?ynt//計算資源，第t個基因值互換

(12) end

2.4 變 異

變異過程如圖3所示。同上，根據變異概率隨機給出N位變異因子序列。若變異因子為0，則相應值保持不變。若變異因子為1，對于節點選擇部分，變異值為隨機節點對應值，對于資源分配部分，變異值為0-1之間的隨機值。

圖3 變異過程

變異概率公式為

(24)

k3為變異概率常數，k4為變異概率調節系數。當f≥favg時，小變異概率可以更好地保留住優秀的基因結構。

算法2：變異操作

(1) for a= Q∶P

(2)T=[1 2 … M]; //卸載節點集合

(3)選擇Xj.Yj;

(4) iffj≥favg

(6) else

(7)Pm=k3;

(8) end

(9) 變異因子序列1

(10)xji=T(ceil(rand(1,>1)>*length(T))); //卸載位置變異值

(11) 變異因子序列2

(12)yji=vpa(rand(1,>1),>2); //計算資源變異值

(13) end

2.5 算法流程

圖4為遺傳算法流程。

3 仿真結果與分析

3.1 仿真參數設置

參照文獻[11]和文獻[12]，仿真參數設置見表1、表2。

表1 遺傳算法的仿真參數

表2 其它仿真參數

N(μ,σ2)表示均值為μ，標準差為σ2的從正態分布導出的截斷正態分布。

由于用戶車輛與云服務器之間的距離及傳輸鏈路帶寬是時變的，假設車輛用戶與MVCNs的連接時長Δtm在10 s到100 s之間隨機分配，車輛用戶到云服務器的數據傳輸速率在1 Mbps到12 Mbps之間隨機分配，使用MEC、RC和MVCNs資源的單位計算成本分別為0.7 MYM/千兆周、0.9 MYM/千兆周和0.5 MYM/千兆周[11]。無特殊說明默認N=40和M=15。

3.2 仿真結果分析

(1)多種方案之間的性能比較

①僅本地處理(OL)；②本地+MEC+RC(LER)；③本地+MEC+RC+MVCNs的隨機處理(R-LERM)。

圖5展示了不同任務數下MCAVC和其它3種方案在總計算開銷上的性能差異。可以看出OL方案由于本地資源有限，性能最差。LER方案盡管使用云資源存在貨幣成本，但MEC和RC可以幫助過載車輛執行更多任務，從而減少任務完成時間。因此當任務數量變大時，LER方案比OL方案性能更好。R-LERM方案等概率將任務隨機分配給計算節點，提供的解決方案不穩定。而MCAVC總能實現最佳的總計算開銷。

圖5 不同任務數下各方案的性能評估

圖6展示了不同任務數下本地、MEC、RC和MVCNs的任務分配百分比。當任務數量較少時，MVCNs的任務百分比接近0，這也解釋了在N=10時，圖5方案MCAVC與LER性能相近的原因。當任務數量從10增加到30時，MVCNs的任務百分比逐漸增加，直到MVCNs的最大數量被用完，任務百分比將慢慢減少。RC的任務百分比從N=20開始逐漸增大，這是因為沒有更多的MVCNs去接收任務，任務只能卸載到RC或MEC。圖7展示的是MVCN數量對方案MCAVC的總計算開銷的影響。

圖6 不同任務數下各節點任務分配百分比

圖7 移動志愿云節點(MVCNs)數量對 總計算開銷的影響

(2)3種算法之間的性能比較

將IFGA與傳統遺傳算法(T-GA)和實數-遺傳算法[5](IM-GA)進行比較。圖8展示的是3種算法在總計算開銷方面的收斂曲線。可以看出，IFGA收斂值最低，IM-GA次之，T-GA最高。圖中IFGA和IM-GA收斂迭代次數較大，在17代左右可以收斂到局部最優值，而T-GA在14代左右收斂到局部最優值。明顯看出T-GA的不足，相比IM-GA的實數編碼方式，IFGA獲得的結果更優，算法性能更好。

圖8 3種GA算法的收斂性能

4 結束語

在MCAVC范式中，選用公交車這類公共設施作為移動志愿云節點，為車輛用戶提供了低延時低消費服務。此外，為了解決MCAVC范式中節點選擇和資源分配這一NP-hard問題，提出使用對編碼、交叉和變異操作做出改進的遺傳算法，結果表明，與現有方案相比，所提方案得到的總計算開銷更小，算法性能更好。事實上，很多復雜應用劃分的多個任務之間存在一定的依賴關系，因此接下來將會基于任務依賴關系進一步研究任務的節點選擇和資源分配問題。