多云協(xié)同輔助車輛計(jì)算的資源管理策略

張文萍，陳桂芬

(長(zhǎng)春理工大學(xué) 電子信息工程學(xué)院，吉林 長(zhǎng)春 130022)

0 引 言

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

以上文獻(xiàn)在使用云計(jì)算資源時(shí)沒有同時(shí)將VC中的個(gè)別云節(jié)點(diǎn)考慮在內(nèi)，這些云節(jié)點(diǎn)不僅可以提供低延時(shí)服務(wù)，而且資源使用成本低。本文基于時(shí)延和計(jì)算資源的使用成本建立目標(biāo)函數(shù)，采用改進(jìn)的遺傳算法有效解決了卸載選擇和資源分配問題。

1 系統(tǒng)模型和問題公式化

1.1 場(chǎng)景描述

如圖1所示，定義一種多云協(xié)同輔助車輛計(jì)算(MCAVC)范式。MCAVC包括3部分：MEC、RC和VC，由這3部分共同為車輛用戶執(zhí)行應(yīng)用程序中的眾多任務(wù)，系統(tǒng)為其選擇任務(wù)卸載節(jié)點(diǎn)以及分配計(jì)算資源，目標(biāo)是最小化任務(wù)完成時(shí)間和使用計(jì)算資源貨幣成本的加權(quán)和，該范式更適合城市道路。

圖1 MCAVC

MCAVC可以啟用VC中不同數(shù)量的“移動(dòng)志愿云節(jié)點(diǎn)”(mobile voluntary cloud nodes，MVCN)，增強(qiáng)了MCAVC的計(jì)算可伸縮性。MVCN多為公交車。

1.2 計(jì)算節(jié)點(diǎn)和任務(wù)模型

Γ={1,2,3,…,M}表示卸載節(jié)點(diǎn)的集合，xji∈Γ，其中xji=1為車輛本身，xji=2為MEC，xji=3為RC，xji∈={4,5,…,M}為第xji-3個(gè)MVCN?！师?，為一個(gè)周期內(nèi)與用戶車輛通信的MVCNs。

1.3 本地計(jì)算

任務(wù)Ti在本地執(zhí)行時(shí)的處理時(shí)間為

(1)

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

1.4 卸載到MEC

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

(2)

(3)

1.5 卸載到RC

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

(4)

(5)

1.6 卸載到MVCN

(6)

tq時(shí)刻處的傳輸速率為

(7)

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

(8)

fi,m為MVCNm的計(jì)算能力，任務(wù)Ti的完成時(shí)間為

(9)

應(yīng)滿足ti,m≤Δtm,?m∈。

(10)

1.7 問題公式化

將任務(wù)完成時(shí)間和使用云計(jì)算資源貨幣成本的加權(quán)和定義為系統(tǒng)總計(jì)算開銷。節(jié)點(diǎn)選擇事件定義為Z={αi,xji|i∈,xji∈Γ}，其中αi,xji=1表示任務(wù)i位于節(jié)點(diǎn)xji上，否則αi,xji=0。資源分配事件定義為F={fi,xji|i∈,xji∈Γ}，將總計(jì)算開銷作為目標(biāo)函數(shù)，表示為

(11)

(12)

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

(13)

(14)

(15)

(16)

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

(17)

(18)

式(13)表示Z是二進(jìn)制向量。式(14)確保每個(gè)計(jì)算任務(wù)只在一個(gè)計(jì)算節(jié)點(diǎn)上執(zhí)行。式(15)和式(16)規(guī)定每個(gè)MVCN在給定的時(shí)間內(nèi)最多可以接收一個(gè)任務(wù)，MVCN在與車輛用戶連接期間完成任務(wù)。式(17)規(guī)定計(jì)算節(jié)點(diǎn)必須給任務(wù)分配正計(jì)算資源，xji={i∈|αi,xji=1}表示分配給計(jì)算節(jié)點(diǎn)的任務(wù)集。式(18)確保計(jì)算節(jié)點(diǎn)上任務(wù)的總計(jì)算資源不超過其總?cè)萘縁xji。

2 遺傳算法求解

節(jié)點(diǎn)選擇是二進(jìn)制變量，資源分配是連續(xù)變量，此問題為NP-hard問題，求解最優(yōu)解時(shí)復(fù)雜度高，這里使用改進(jìn)遺傳算法求解，可在較短時(shí)間內(nèi)獲得局部最優(yōu)解。

2.1 編 碼

傳統(tǒng)遺傳算法編碼時(shí)，基因串長(zhǎng)度等于決策變量個(gè)數(shù)[9]，導(dǎo)致基因串過長(zhǎng)，從而延緩進(jìn)化速度，長(zhǎng)時(shí)間無法收斂到最優(yōu)解?，F(xiàn)采用改進(jìn)浮點(diǎn)編碼遺傳算法IFGA，讓浮點(diǎn)數(shù)整數(shù)和小數(shù)部分分別映射為卸載節(jié)點(diǎn)和計(jì)算資源。種群表示為

(19)

S為種群中的個(gè)體數(shù)量，Cj為個(gè)體，即一條染色體。每條染色體表示為

(20)

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

(21)

2.2 適應(yīng)度函數(shù)和選擇

(22)

2.3 交 叉

交叉過程如圖2所示。基因的兩個(gè)組成部分分別根據(jù)交叉概率隨機(jī)產(chǎn)生一個(gè)由0和1組成的N位交叉因子序列，如交叉概率為0.9，則出現(xiàn)1的概率為0.9。先交叉節(jié)點(diǎn)部分，再交叉資源部分，若交叉因子為1，則互換父代染色體相應(yīng)值。若交叉因子為0，則相應(yīng)值保持不變。

圖2 交叉過程

為了自適應(yīng)調(diào)節(jié)，依據(jù)文獻(xiàn)[10]，交叉概率公式為

(23)

favg和fmax分別代表當(dāng)代種群中個(gè)體適應(yīng)度值的平均值和最大值，f′代表交叉?zhèn)€體中的較大適應(yīng)度值，k1為交叉概率常數(shù)，k2為交叉概率調(diào)節(jié)系數(shù)。當(dāng)f′≥favg時(shí)，為防止優(yōu)秀的基因結(jié)構(gòu)被破壞采用較小交叉概率。

算法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個(gè)基因值互換

(10) 交叉因子序列2

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

(12) end

2.4 變 異

變異過程如圖3所示。同上，根據(jù)變異概率隨機(jī)給出N位變異因子序列。若變異因子為0，則相應(yīng)值保持不變。若變異因子為1，對(duì)于節(jié)點(diǎn)選擇部分，變異值為隨機(jī)節(jié)點(diǎn)對(duì)應(yīng)值，對(duì)于資源分配部分，變異值為0-1之間的隨機(jī)值。

圖3 變異過程

變異概率公式為

(24)

k3為變異概率常數(shù)，k4為變異概率調(diào)節(jié)系數(shù)。當(dāng)f≥favg時(shí)，小變異概率可以更好地保留住優(yōu)秀的基因結(jié)構(gòu)。

算法2：變異操作

(1) for a= Q∶P

(2)T=[1 2 … M]; //卸載節(jié)點(diǎn)集合

(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); //計(jì)算資源變異值

(13) end

2.5 算法流程

圖4為遺傳算法流程。

3 仿真結(jié)果與分析

3.1 仿真參數(shù)設(shè)置

參照文獻(xiàn)[11]和文獻(xiàn)[12]，仿真參數(shù)設(shè)置見表1、表2。

表1 遺傳算法的仿真參數(shù)

表2 其它仿真參數(shù)

N(μ,σ2)表示均值為μ，標(biāo)準(zhǔn)差為σ2的從正態(tài)分布導(dǎo)出的截?cái)嗾龖B(tài)分布。

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

3.2 仿真結(jié)果分析

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

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

圖5展示了不同任務(wù)數(shù)下MCAVC和其它3種方案在總計(jì)算開銷上的性能差異?？梢钥闯鯫L方案由于本地資源有限，性能最差。LER方案盡管使用云資源存在貨幣成本，但MEC和RC可以幫助過載車輛執(zhí)行更多任務(wù)，從而減少任務(wù)完成時(shí)間。因此當(dāng)任務(wù)數(shù)量變大時(shí)，LER方案比OL方案性能更好。R-LERM方案等概率將任務(wù)隨機(jī)分配給計(jì)算節(jié)點(diǎn)，提供的解決方案不穩(wěn)定。而MCAVC總能實(shí)現(xiàn)最佳的總計(jì)算開銷。

圖5 不同任務(wù)數(shù)下各方案的性能評(píng)估

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

圖6 不同任務(wù)數(shù)下各節(jié)點(diǎn)任務(wù)分配百分比

圖7 移動(dòng)志愿云節(jié)點(diǎn)(MVCNs)數(shù)量對(duì) 總計(jì)算開銷的影響

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

將IFGA與傳統(tǒng)遺傳算法(T-GA)和實(shí)數(shù)-遺傳算法[5](IM-GA)進(jìn)行比較。圖8展示的是3種算法在總計(jì)算開銷方面的收斂曲線?？梢钥闯觯琁FGA收斂值最低，IM-GA次之，T-GA最高。圖中IFGA和IM-GA收斂迭代次數(shù)較大，在17代左右可以收斂到局部最優(yōu)值，而T-GA在14代左右收斂到局部最優(yōu)值。明顯看出T-GA的不足，相比IM-GA的實(shí)數(shù)編碼方式，IFGA獲得的結(jié)果更優(yōu)，算法性能更好。

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

4 結(jié)束語(yǔ)

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