基于改進(jìn)的混合遺傳算法的車聯(lián)網(wǎng)任務(wù)卸載策略研究

叢玉良，孫聞晞，薛科，錢志鴻，陳綿書

（1.吉林大學(xué)通信工程學(xué)院，吉林 長(zhǎng)春 130012；2.中國(guó)科學(xué)院長(zhǎng)春光學(xué)精密機(jī)械與物理研究所，吉林 長(zhǎng)春 130012）

0 引言

隨著智能汽車和無(wú)線通信的快速發(fā)展，車聯(lián)網(wǎng)中出現(xiàn)了許多先進(jìn)應(yīng)用，如自動(dòng)駕駛和視頻輔助實(shí)時(shí)導(dǎo)航等。這些應(yīng)用程序的實(shí)現(xiàn)需要強(qiáng)大的計(jì)算能力來(lái)管理各種計(jì)算密集且對(duì)時(shí)延敏感的任務(wù)[1-2]。為了解決車輛終端計(jì)算能力等問(wèn)題，移動(dòng)邊緣計(jì)算（MEC,mobile edge computing）被認(rèn)為是一種很有前途的范例[3]。有了MEC，車輛的計(jì)算任務(wù)通過(guò)無(wú)線鏈路上傳到MEC 服務(wù)器上計(jì)算[4]，可以減少本地計(jì)算時(shí)延。然而，隨著越來(lái)越多的任務(wù)被轉(zhuǎn)發(fā)到MEC 服務(wù)器，由于無(wú)線和計(jì)算資源有限，MEC 服務(wù)器將承受巨大壓力，這將導(dǎo)致車輛的高時(shí)延和低可靠性。面對(duì)多車多服務(wù)器的場(chǎng)景，合理的任務(wù)卸載決策和計(jì)算資源分配值得研究。

車聯(lián)網(wǎng)任務(wù)卸載決策主要解決的是終端是否將任務(wù)卸載至服務(wù)器，以及卸載多少的問(wèn)題，是一個(gè)典型的0-1 整數(shù)規(guī)劃問(wèn)題。近年來(lái)，遺傳算法因其具有全局優(yōu)化性、簡(jiǎn)單性及穩(wěn)健性等特點(diǎn)，得到了許多學(xué)者的青睞。余翔等[5]面對(duì)移動(dòng)邊緣計(jì)算的車聯(lián)網(wǎng)場(chǎng)景，考慮并發(fā)多個(gè)優(yōu)先級(jí)不同的計(jì)算任務(wù)，提出了一種基于遺傳算法的任務(wù)卸載策略。鄧添等[6]提出了一種在多信道環(huán)繞下的任務(wù)卸載模型，并采用遺傳算法來(lái)求解。高基旭等[7]考慮了本地、邊緣服務(wù)器和云端協(xié)同計(jì)算的任務(wù)卸載模型，提出了一種基于遺傳算法的求解方案，從而得到同時(shí)考慮時(shí)延和能耗的最小系統(tǒng)代價(jià)。但是上述文獻(xiàn)均沒(méi)有對(duì)基本的遺傳算法進(jìn)行改進(jìn)，傳統(tǒng)的遺傳算法后期易出現(xiàn)早熟現(xiàn)象且尋優(yōu)能力無(wú)法達(dá)到理想效果。并且上述文獻(xiàn)只考慮了任務(wù)卸載決策這一個(gè)問(wèn)題，未對(duì)MEC 的計(jì)算資源進(jìn)行優(yōu)化。

Zhao 等[8]在云輔助的情況下，通過(guò)聯(lián)合優(yōu)化任務(wù)卸載決策和計(jì)算資源分配，建立了以系統(tǒng)效用最大化的優(yōu)化問(wèn)題，提出了一種分布式計(jì)算卸載和資源分配算法。Yang 等[9]研究了車載邊緣計(jì)算網(wǎng)絡(luò)中高效的任務(wù)卸載策略。車輛以最佳方式執(zhí)行卸載時(shí)間選擇、通信和計(jì)算資源分配，并考慮車輛的移動(dòng)性和任務(wù)的最大時(shí)延。梁穎杰等[10]提出了一種基于MEC 和任務(wù)優(yōu)先級(jí)的智能卸載策略以降低由時(shí)延所組成的系統(tǒng)總成本，并根據(jù)任務(wù)優(yōu)先級(jí)對(duì)任務(wù)卸載位置進(jìn)行選擇。

文獻(xiàn)[8-10]雖同時(shí)考慮了任務(wù)卸載決策和資源分配2 個(gè)因素，但均只考慮了時(shí)延這一個(gè)指標(biāo)。近幾年來(lái)，能源短缺正成為限制車聯(lián)網(wǎng)發(fā)展的一個(gè)關(guān)鍵障礙。根據(jù)統(tǒng)計(jì)數(shù)據(jù)[11]，在不斷增長(zhǎng)的能源需求中，電力占16.5%，傳統(tǒng)可再生能源占11.9%，煤炭占6.4%，而化石燃料占49.4%，主要包括現(xiàn)有車輛消耗。因此，考慮車輛應(yīng)用的能耗意義重大。特別是，電動(dòng)汽車或混合動(dòng)力電動(dòng)汽車將在不久的將來(lái)主導(dǎo)市場(chǎng)，這促使人們考慮車聯(lián)網(wǎng)中的能源消耗。

在現(xiàn)實(shí)生活中，每輛車由于計(jì)算任務(wù)大小的不同通常會(huì)需要不同計(jì)算資源。在計(jì)算任務(wù)卸載過(guò)程中，有限的計(jì)算資源在車輛之間共享，每輛車需要確定是否進(jìn)行卸載，每臺(tái)MEC 服務(wù)器也應(yīng)在多車之間進(jìn)行合理的資源分配?？紤]到上述問(wèn)題，本文的主要研究工作如下。

1) 構(gòu)建了基于MEC 的車聯(lián)網(wǎng)任務(wù)卸載模型，在任務(wù)卸載決策和資源分配的約束下，通過(guò)聯(lián)合優(yōu)化任務(wù)卸載決策和邊緣服務(wù)器的資源分配來(lái)最小化系統(tǒng)內(nèi)的平均成本。成本是基于任務(wù)時(shí)延、能耗和權(quán)重因子這3 個(gè)指標(biāo)定義的。

2) 將任務(wù)卸載決策和資源分配建模為一個(gè)混合整數(shù)非線性規(guī)劃問(wèn)題，針對(duì)這個(gè)問(wèn)題，提出了一種基于改進(jìn)的混合遺傳算法的兩階段啟發(fā)式方案。通過(guò)將優(yōu)化問(wèn)題分成2 個(gè)子問(wèn)題，利用改進(jìn)的混合遺傳算法（IGHA,improved hybrid genetic algorithm）求解任務(wù)卸載決策問(wèn)題，利用改進(jìn)的人工魚群算法（AFSA,artificial fish-swarm algorithm）求解資源分配問(wèn)題，再將二者不斷迭代求解，直至達(dá)到終止條件。

3) 對(duì)基本的遺傳算法進(jìn)行了改進(jìn)。充分考慮了MEC 服務(wù)器出現(xiàn)過(guò)載或者對(duì)計(jì)算資源利用不足的2 種情況，具體為通過(guò)對(duì)經(jīng)過(guò)交叉、變異后得到的不滿足約束條件的染色體和滿足約束條件但對(duì)MEC 的計(jì)算資源并未充分利用的染色體使用了貪婪修正法進(jìn)行修正，使其轉(zhuǎn)換為對(duì)MEC 的計(jì)算資源充分利用的染色體，從而提高算法的收斂速度和尋優(yōu)能力。

4) 仿真結(jié)果表明，相比于基準(zhǔn)方案，IHGA-AFSA方案降低了系統(tǒng)內(nèi)的平均開(kāi)銷、時(shí)延及能耗。

1 系統(tǒng)模型

1.1 網(wǎng)絡(luò)模型

如圖1 所示，本文所研究的基于MEC 的車聯(lián)網(wǎng)包括N輛單向行駛在道路上的汽車，道路沿線有M個(gè)路邊單元（RSU,road side unit），每個(gè)RSU 都配備一個(gè)MEC 服務(wù)器，二者通過(guò)光纖有線鏈路連接。RSU 的集合定義為 M=｛1,2,…,M｝。車輛的集合定義為 N=｛1,2,…,N｝，每輛車有且僅有一個(gè)計(jì)算任務(wù)。其中，Dn是輸入數(shù)據(jù)的大小，Cn是完成任務(wù)Qn所需的CPU 周期數(shù)，是任務(wù)完成可容忍的最大時(shí)延。任務(wù)可以在本地處理，或者卸載到MEC 服務(wù)器處理，定義an表示任務(wù)卸載決策變量，an=1表示車輛將任務(wù)卸載至邊緣服務(wù)器計(jì)算，an=0表示任務(wù)在車輛本地計(jì)算。

圖1 車聯(lián)網(wǎng)場(chǎng)景

車輛與RSU 之間的通信是通過(guò)直連的無(wú)線鏈路進(jìn)行的，車輛到RSU 的上傳鏈路設(shè)定為頻率平坦型快衰落瑞利信道。根據(jù)香農(nóng)公式，可以計(jì)算出上傳鏈路的傳輸速率為

其中，Bn表示MEC 服務(wù)器與車輛之間的帶寬大小，Pn表示車載設(shè)備的發(fā)射功率，Gn表示車輛與RSU之間的信道增益，σ2表示無(wú)線信道的傳輸噪聲。

1.2 計(jì)算模型

1) 本地計(jì)算

當(dāng)車輛在本地處理其計(jì)算任務(wù)時(shí)，計(jì)算時(shí)延取決于其自身的計(jì)算能力，設(shè)是車輛n的計(jì)算能力，由放置在車輛上的車載單元（OBU,on-board unit）確定[12]。故本地計(jì)算時(shí)延為

同時(shí)可以獲得車輛用戶進(jìn)行任務(wù)卸載的能耗為

2) 邊緣服務(wù)器計(jì)算

與其他研究[12-13]一樣，在語(yǔ)音識(shí)別等許多應(yīng)用中，其計(jì)算結(jié)果的大小遠(yuǎn)小于輸入數(shù)據(jù)的大小，接收計(jì)算結(jié)果的時(shí)延可以忽略不計(jì)。在這種情況下，總時(shí)延具體包括上行鏈路傳輸時(shí)延及計(jì)算任務(wù)執(zhí)行時(shí)延。車輛n的總時(shí)延為

其中，fn表示MEC 服務(wù)器分配給車輛n的計(jì)算資源，定義為服務(wù)器m的總計(jì)算資源，有表示計(jì)算任務(wù)所屬車輛與服務(wù)器之間的無(wú)線傳輸速率。

車輛任務(wù)卸載時(shí)的能耗主要來(lái)自卸載數(shù)據(jù)到邊緣服務(wù)器的過(guò)程中的能耗，即

1.3 問(wèn)題表述

由于每個(gè)任務(wù)可以在本地或者M(jìn)EC 服務(wù)器上執(zhí)行，因此車輛n的總時(shí)延為

車輛n的能耗包括本地能耗和上傳能耗，表示為

將時(shí)延能耗開(kāi)銷（LEC,latency-energy cost）即車輛開(kāi)銷，定義為任務(wù)執(zhí)行的時(shí)延和能耗的加權(quán)和。因此，車輛n的LEC 表達(dá)式為

本節(jié)將聯(lián)合任務(wù)卸載決策和資源分配作為優(yōu)化問(wèn)題，目標(biāo)是最小化系統(tǒng)內(nèi)平均開(kāi)銷。定義a=｛a1,a2,…,an｝為MEC 服務(wù)器任務(wù)卸載決策變量，f=｛f1,f2,…,fn｝為計(jì)算資源變量，將優(yōu)化問(wèn)題表示為

其中，C1和C2 表示一個(gè)計(jì)算任務(wù)只能卸載至某一個(gè)MEC 服務(wù)器，不能同時(shí)卸載至2 個(gè)服務(wù)器；C3表示MEC 服務(wù)器分配給車輛n的計(jì)算資源不能為負(fù)數(shù)；C4 表示MEC 服務(wù)器總計(jì)算資源的約束。

2 算法設(shè)計(jì)

解決P1的關(guān)鍵挑戰(zhàn)是求解整數(shù)變量an∈ ｛0,1｝，an使P1是一個(gè)混合整數(shù)非線性規(guī)劃問(wèn)題，這類問(wèn)題通常都是非凸的NP-hard[14]，求解起來(lái)具有一定的難度，對(duì)此本文提出了一種基于改進(jìn)的混合遺傳算法的求解方案，具體將P1劃分為2 個(gè)子問(wèn)題。

1) 任務(wù)卸載決策問(wèn)題。假設(shè)資源分配已給定，即f=f(0)，那么原優(yōu)化問(wèn)題就變成了只關(guān)于變量a的0-1 整數(shù)規(guī)劃問(wèn)題，本文采用IHGA 求解。

2) 資源分配問(wèn)題。在該子問(wèn)題的基礎(chǔ)上，確定a=a*后，問(wèn)題P1轉(zhuǎn)化為關(guān)于f的連續(xù)問(wèn)題，本文采用改進(jìn)的AFSA 求解。

2.1 任務(wù)卸載決策

當(dāng)f=f(0)給定時(shí)，P1轉(zhuǎn)化為P2

此時(shí)，P1轉(zhuǎn)化為關(guān)于a的優(yōu)化問(wèn)題P2，a為0-1 整數(shù)變量，采用遺傳算法進(jìn)行求解。遺傳算法不要求求解的問(wèn)題是連續(xù)的或可微的，也不需要控制算法的執(zhí)行方向，具體步驟如下。

步驟1染色體。遺傳算法借鑒了自然選擇的思想[15]，引入了染色體的概念，即可能的解。本文中的任務(wù)卸載決策構(gòu)成了個(gè)體的染色體信息，對(duì)于第n條染色體，其染色體信息可表示為

編碼及種群初始化。根據(jù)任務(wù)的卸載模型，共有N個(gè)任務(wù)要經(jīng)過(guò)卸載決策之后決定是否卸載。因此在遺傳算法中，每個(gè)染色體都應(yīng)該由N個(gè)基因組成，每個(gè)任務(wù)都可以選擇在本地計(jì)算還是卸載至MEC 服務(wù)器計(jì)算，故每個(gè)基因都有2 個(gè)可能的值（本地計(jì)算則基因?yàn)?，MEC 服務(wù)器計(jì)算則基因?yàn)?），并得到初始的染色體種群I(0)。

步驟2染色體修正。對(duì)初始化染色體進(jìn)行修正，修正主要分為以下兩步。

1) 對(duì)不符合約束條件的染色體進(jìn)行修正。對(duì)于該部分染色體，基于文獻(xiàn)[16]中混合遺傳算法的思想使其轉(zhuǎn)換為符合約束條件的染色體，如果轉(zhuǎn)換后的染色體充分利用了資源，則修正結(jié)束；否則轉(zhuǎn)至2)。具體為，當(dāng)時(shí)，將an=1的車輛按照從大到小的順序進(jìn)行排序，然后根據(jù)排序?qū)⑦x擇卸載的車輛進(jìn)行任務(wù)卸載，直至接近但不超過(guò)服務(wù)器的計(jì)算總資源，將剩余選擇卸載的車輛由狀態(tài)an=1改變?yōu)閍n=0。

2) 對(duì)滿足約束條件但對(duì)MEC 的計(jì)算資源利用不足的染色體，運(yùn)用貪婪修正法進(jìn)行修正。設(shè)是一個(gè)對(duì)MEC 的計(jì)算資源利用不足的染色體，該染色體有r個(gè)車輛an=0，MEC的剩余計(jì)算資源為Fm0，通過(guò)貪婪修正法將其修正為充分利用計(jì)算資源的染色體將染色體Xi中an=0的車輛按照從大到小的順序進(jìn)行排序，形成長(zhǎng)度為r的序列｛b1,b2,…,br｝（其中，b1為最大的序號(hào)，br為最小的序號(hào)），然后按排序?qū)n=0的車輛轉(zhuǎn)變?yōu)閍n=1，直至接近服務(wù)器的計(jì)算總資源，但不能超過(guò)其計(jì)算資源。

步驟3遺傳算法中個(gè)體（解決方案）的質(zhì)量由適應(yīng)度值來(lái)評(píng)估。由于本文研究了最小化問(wèn)題，因此將適應(yīng)度函數(shù)設(shè)置為

適應(yīng)度值越高，目標(biāo)函數(shù)的成本就會(huì)越小，表明該卸載策略越優(yōu)。

步驟4選擇。采用輪盤賭算法篩選個(gè)體，即隨機(jī)旋轉(zhuǎn)輪盤進(jìn)行選擇，每個(gè)個(gè)體都可能被反復(fù)挑選。其基本思想是每個(gè)個(gè)體被選中的概率與其適應(yīng)度成正比。設(shè)P(di)為下一代選擇染色體di被選中的概率，即

步驟5交叉。如圖2 所示，采用單點(diǎn)交叉的方式，在染色體串中隨機(jī)設(shè)置一個(gè)交叉點(diǎn)，然后進(jìn)行基因交換，生成2 個(gè)新個(gè)體。其意義在于通過(guò)為下一代群體保留具有更好親本的基因來(lái)改善新群體的適應(yīng)性。

圖2 交叉

步驟6變異。防止種群中的所有解落入局部最優(yōu)解。對(duì)于二進(jìn)制編碼，隨機(jī)選擇幾個(gè)位置從1變成0 或從0 變成1，如圖3 所示。

圖3 變異

2.2 資源分配

當(dāng)求出較優(yōu)的任務(wù)卸載決策a*后，代入P1，得到問(wèn)題P3

特別是，AFSA 有一種機(jī)制，可以使搜索行為跳出局部極值點(diǎn)并獲得全局優(yōu)化解。因此，采用AFSA 求解資源分配問(wèn)題[17]。通常，AFSA 有4 個(gè)關(guān)鍵行為，具體如下。

1) 覓食行為：人工魚趨向于食物的一種行為。人工魚通過(guò)視覺(jué)或味覺(jué)來(lái)感知水中食物量或食物濃度來(lái)選擇行動(dòng)的方向。覓食行為是算法收斂的基礎(chǔ)。假設(shè)第i條人工魚的當(dāng)前位置和適應(yīng)度值分別為Xi和Yi，人工魚視野內(nèi)的另一個(gè)位置為Xj和適應(yīng)度值為Yj，若Yj＞Yi，則按式(15)向新選擇的位置靠近一步；否則，重新獲取新位置，判斷是否滿足條件，若還不滿足條件，則按式(16)隨機(jī)移動(dòng)一步，人工魚Xi在其視野內(nèi)隨機(jī)選擇一個(gè)位置Xj，其表達(dá)式為

2) 聚群行為：促使人工魚自發(fā)地聚集在一起以避免傷害。如果魚群中心有許多“營(yíng)養(yǎng)食物”，并且它們不是太擁擠，即人工魚Xi搜索當(dāng)前視野內(nèi)(dij＜ Visual)的伙伴數(shù)目nf和中心位置Xc，若，則Xi朝伙伴的中心位置移動(dòng)一步

3) 追尾行為：當(dāng)一個(gè)人工魚找到一個(gè)食物充足且不太擁擠的最佳區(qū)域時(shí)，附近的人工魚將跟隨它并快速到達(dá)其附近的位置。人工魚Xi搜索當(dāng)前視野內(nèi)(dij＜ Visual)的伙伴中函數(shù)Yj最優(yōu)伙伴Xj，若，則Xi朝此伙伴移動(dòng)一步

4) 隨機(jī)行為：為了使人工魚在更大范圍內(nèi)尋找食物或同伴，會(huì)按式(19)在水中隨機(jī)地游來(lái)游去。當(dāng)發(fā)現(xiàn)食物時(shí)，會(huì)向食物逐漸增多的方向快速移動(dòng)。

基本的AFSA 步長(zhǎng)和視野一般是固定值，這樣前期的搜索易陷入盲目搜索，故本文引入自適應(yīng)因子使視野和步長(zhǎng)能根據(jù)外界環(huán)境信息的變化而動(dòng)態(tài)地調(diào)整，這樣算法在前期具有更好的全局搜索能力，還可以避免算法在后期容易發(fā)生振蕩現(xiàn)象。二者的變化滿足

其中，k為迭代次數(shù)，a∈（0,1）為自適應(yīng)因子。

基于改進(jìn)的AFSA 求解資源分配的具體步驟如下。

步驟1初始化設(shè)置，包括種群規(guī)模N，每條人工魚的初始位置、視野Visual、步長(zhǎng)Step、擁擠度因子δ、重復(fù)次數(shù)k；

步驟2根據(jù)P3 計(jì)算初始個(gè)體的適應(yīng)值；

步驟3對(duì)每個(gè)個(gè)體進(jìn)行評(píng)價(jià)，從覓食、聚群、追尾和隨機(jī)中選擇一個(gè)行為；

步驟4執(zhí)行行為，更新自己，生成新魚群；

步驟5評(píng)價(jià)所有個(gè)體；

步驟6達(dá)到迭代次數(shù)上限時(shí)算法結(jié)束，否則轉(zhuǎn)到步驟3。

2.3 全局算法

綜上，本文將任務(wù)卸載決策和資源分配建模為混合整數(shù)非線性規(guī)劃問(wèn)題，對(duì)此提出了一個(gè)基于改進(jìn)的混合遺傳算法的兩階段啟發(fā)式算法的方案。將問(wèn)題分成2 個(gè)子問(wèn)題，通過(guò)將初始化資源分配代入P1，得到只關(guān)于任務(wù)卸載決策的P2，通過(guò)IHGA 進(jìn)行求解。將得到的任務(wù)卸載決策解代入P1，得到只關(guān)于資源分配問(wèn)題的P3。利用改進(jìn)的AFSA 進(jìn)行求解，基于二者的耦合關(guān)系，不斷迭代求解，具體步驟如下。

步驟1初始化資源分配為f(0)，代入P1，設(shè)置當(dāng)前迭代次數(shù)為r=0；

步驟2將資源分配f(r)代入P2，通過(guò)IHGA得到較優(yōu)的任務(wù)卸載決策a(r+1)；

步驟3通過(guò)IHGA 得到的任務(wù)卸載決策a(r+1)代入P1，得到P3，通過(guò)改進(jìn)的AFSA 求解得到資源分配方案f（r+1）；

步驟4判別相鄰兩次目標(biāo)函數(shù)的增長(zhǎng)值是否小于閾值τ，若大于或等于則r=r+1，并同時(shí)繼續(xù)步驟2；否則輸出當(dāng)前最優(yōu)的任務(wù)卸載決策和資源分配方案f*。

全局算法流程如圖4 所示。

圖4 全局算法流程

3 仿真實(shí)驗(yàn)及數(shù)據(jù)分析

為了驗(yàn)證本文針對(duì)任務(wù)卸載決策和資源分配所提的算法，在MATLAB 平臺(tái)進(jìn)行仿真實(shí)驗(yàn)。參考文獻(xiàn)[7-9,12]，以及本文的實(shí)際仿真環(huán)境，有如下參數(shù)設(shè)置?？紤]一條長(zhǎng)為2 000 m 的單向道路，放置5 個(gè)RSU，每個(gè)RSU 的通信覆蓋范圍的半徑為500 m，RSU 分配給每輛車的子信道帶寬為2 MHz，每輛車的發(fā)射功率為46 dBm，高斯白噪聲為σ2=-1 47dBm，車輛用戶的信道衰減模型為u=127+30logd，其中d是每輛車與RSU 中心的距離，RSU 與車輛i之間的信道增益為。IHGA 中的交叉概率為0.4，變異概率為0.02，種群數(shù)量為50，迭代次數(shù)為50。改進(jìn)的AFSA 中[18]的人工魚數(shù)量為50 只，感知距離為1，步長(zhǎng)為1，擁擠度因子為0.618，最多迭代次數(shù)為50，最多試探次數(shù)為100，自適應(yīng)因子為0.6。設(shè)置時(shí)延因子，能耗因子。IHGAAFSA 方案的閾值τ=0.1。

為了驗(yàn)證本文提出的IHGA-AFSA 方案的性能，對(duì)比了以下3 種基準(zhǔn)方案。

1) 本地計(jì)算方案：計(jì)算任務(wù)不卸載到MEC 服務(wù)器上計(jì)算，而是全部留在車輛本地計(jì)算。

2) 隨機(jī)卸載策略：車輛隨機(jī)選擇是否進(jìn)行卸載，若卸載則利用改進(jìn)的AFSA 求解資源分配問(wèn)題。

3) IHGA-平均方案：IHGA 求解任務(wù)卸載決策，將MEC 的計(jì)算資源平均分配給車輛。

3.1 任務(wù)所需CPU 周期數(shù)性能分析

本節(jié)實(shí)驗(yàn)中一共有100 輛車，每輛車均有一個(gè)計(jì)算任務(wù)，故共有100 個(gè)計(jì)算任務(wù)。每個(gè)RSU 配備一臺(tái)MEC 服務(wù)器，每臺(tái)MEC 服務(wù)器的最大計(jì)算資源為400 GHz，每輛車的計(jì)算頻率在1.8～2.0 GHz隨機(jī)分布。計(jì)算任務(wù)的輸入數(shù)據(jù)量大小為1.5 MB，圖5～圖7 分別展示了完成任務(wù)所需計(jì)算量（用CPU周期數(shù)表示）為1 300～2 000 Megacycles 時(shí)系統(tǒng)內(nèi)開(kāi)銷、時(shí)延及能耗的變化。為了消除隨機(jī)性，一共進(jìn)行100 次實(shí)驗(yàn)，最后結(jié)果取平均。

圖5 分析了任務(wù)所需計(jì)算量與系統(tǒng)內(nèi)開(kāi)銷的關(guān)系。從圖5 可以看出，當(dāng)任務(wù)所需計(jì)算量增加時(shí)，系統(tǒng)內(nèi)開(kāi)銷不斷增加。其中，本地計(jì)算方案的開(kāi)銷最大，IHGA-AFSA 方案與隨機(jī)卸載策略相比，資源分配均采用改進(jìn)的AFSA，而IHGA-AFSA 方案所產(chǎn)生的開(kāi)銷更小，說(shuō)明本文提出的IHGA對(duì)任務(wù)卸載決策起到了優(yōu)化作用。IHGA-AFSA 方案與IHGA-平均方案相比，卸載決策均采用IHGA，而IHGA-AFSA 方案所產(chǎn)生的開(kāi)銷也是更小，說(shuō)明本文提出的改進(jìn)的AFSA 對(duì)資源分配起到了優(yōu)化效果。因此本文提出的IHGA-AFSA 方案在優(yōu)化系統(tǒng)開(kāi)銷方面性能優(yōu)于本地計(jì)算、隨機(jī)卸載和IGHA-平均方案。

圖5 任務(wù)所需計(jì)算量與系統(tǒng)內(nèi)開(kāi)銷的關(guān)系

圖6分析了任務(wù)所需計(jì)算量與系統(tǒng)內(nèi)時(shí)延的關(guān)系。從圖6 可以看出，當(dāng)任務(wù)所需計(jì)算量增加時(shí)，系統(tǒng)內(nèi)時(shí)延不斷增加。其中，本地計(jì)算方案的時(shí)延最大，其余3 種方案均小于本地時(shí)延，說(shuō)明車聯(lián)網(wǎng)與MEC 技術(shù)的結(jié)合更加符合時(shí)延敏感型任務(wù)對(duì)時(shí)延的苛刻要求。當(dāng)任務(wù)所需計(jì)算量為 1 700 Megacycles 時(shí)，IHGA-AFSA 方案與本地計(jì)算方案相比時(shí)延減少了約17.4%。在4 種方案中，本文所提方案時(shí)延最低，因此本文提出的IHGA-AFSA 方案在優(yōu)化系統(tǒng)時(shí)延方面性能強(qiáng)于本地計(jì)算、隨機(jī)卸載和IHGA-平均方案。

圖6 任務(wù)所需計(jì)算量與系統(tǒng)內(nèi)時(shí)延的關(guān)系

圖7 分析了任務(wù)所需計(jì)算量與系統(tǒng)內(nèi)能耗的關(guān)系。當(dāng)任務(wù)所需計(jì)算量增加時(shí)，系統(tǒng)內(nèi)能耗不斷增加。其中，本地計(jì)算方案的能耗最大，其次是隨機(jī)卸載策略，再次是IHGA-平均方案，本文提出的方案在優(yōu)化能耗方面性能是最優(yōu)的，產(chǎn)生的能耗是最低的。IHGA-AFSA 方案與隨機(jī)卸載策略相比，資源分配均采用改進(jìn)的AFSA，而IHGA-AFSA 方案所產(chǎn)生的能耗更小，說(shuō)明本文提出的IHGA 不僅對(duì)任務(wù)卸載決策起到了優(yōu)化作用，對(duì)能耗也有效果，在任務(wù)所需計(jì)算量為1 700 Megacycles 時(shí)，能耗減少約16.6%。

圖7 任務(wù)所需計(jì)算量與系統(tǒng)內(nèi)能耗的關(guān)系

3.2 任務(wù)數(shù)據(jù)量大小性能分析

本節(jié)實(shí)驗(yàn)中一共有70輛車，每輛車均有一個(gè)計(jì)算任務(wù)，故共有70 個(gè)計(jì)算任務(wù)。每個(gè)RSU 配備一臺(tái)MEC 服務(wù)器，每臺(tái)MEC 服務(wù)器的最大計(jì)算資源為400 GHz，每輛車的計(jì)算頻率在1.8～2.0 GHz 隨機(jī)分布。計(jì)算任務(wù)所需的CPU 周期數(shù)為2 000 Megacycles，圖8～圖10 分別展示了任務(wù)數(shù)據(jù)量大小為0.5～1.5 MB 時(shí)系統(tǒng)內(nèi)開(kāi)銷、時(shí)延及能耗的變化。為了消除隨機(jī)性，一共進(jìn)行100 次實(shí)驗(yàn)，最后結(jié)果取平均。

圖8 分析了任務(wù)數(shù)據(jù)量大小與系統(tǒng)內(nèi)開(kāi)銷的關(guān)系。當(dāng)任務(wù)數(shù)據(jù)量大小增加時(shí)，本地計(jì)算方案所產(chǎn)生的開(kāi)銷波動(dòng)較小，這是因?yàn)殚_(kāi)銷是時(shí)延和能耗的加權(quán)，時(shí)延和能耗波動(dòng)均比較小，故開(kāi)銷波動(dòng)也小。但本地計(jì)算方案產(chǎn)生的開(kāi)銷是最大的，其次是隨機(jī)卸載策略，本文提出的IHGA-AFSA 方案與IHGA-平均方案相比產(chǎn)生的開(kāi)銷更小。這說(shuō)明IHGA-AFSA 方案在優(yōu)化開(kāi)銷方面強(qiáng)于本地計(jì)算、隨機(jī)卸載、IHGA-平均方案。當(dāng)任務(wù)數(shù)據(jù)量大小為1 MB 時(shí)，本文方案相比于本地計(jì)算、隨機(jī)卸載、IHGA-平均方案所產(chǎn)生的開(kāi)銷降低了約29.1%、23.3%、14.4%。

圖8 任務(wù)數(shù)據(jù)量大小與系統(tǒng)內(nèi)開(kāi)銷的關(guān)系

圖9 分析了任務(wù)數(shù)據(jù)量大小與系統(tǒng)內(nèi)的時(shí)延的關(guān)系。隨著任務(wù)數(shù)據(jù)量大小的增加，本地計(jì)算方案的時(shí)延波動(dòng)最小，這是因?yàn)槿蝿?wù)數(shù)據(jù)量大小與本地時(shí)延沒(méi)有直接的關(guān)系。其余3 種方案的時(shí)延隨著任務(wù)數(shù)據(jù)量大小的增加并沒(méi)有明顯的遞增性，這是因?yàn)槿蝿?wù)數(shù)據(jù)的大小只會(huì)對(duì)任務(wù)上傳的時(shí)延造成影響，而上傳鏈路的傳輸速率較快，故總體的時(shí)延不會(huì)有很明顯的遞增表現(xiàn)。但是在3 種方案中，本文提出的IGHA-AFSA 方案產(chǎn)生的時(shí)延最小，證實(shí)了其在優(yōu)化時(shí)延方面的優(yōu)越性。當(dāng)任務(wù)數(shù)據(jù)量大小為1 MB 時(shí)，本文方案相比于本地計(jì)算、隨機(jī)卸載、IHGA-平均方案所產(chǎn)生的時(shí)延降低了約23.4%、16.5%、15.5%。

圖9 任務(wù)數(shù)據(jù)量大小與系統(tǒng)內(nèi)時(shí)延的關(guān)系

圖10 分析了任務(wù)數(shù)據(jù)量大小與系統(tǒng)內(nèi)能耗的關(guān)系。隨著任務(wù)數(shù)據(jù)量大小的增加，本地計(jì)算方案的能耗波動(dòng)最小，這是因?yàn)槿蝿?wù)數(shù)據(jù)量大小與本地能耗沒(méi)有直接的關(guān)系。其余3 種方案的能耗隨著任務(wù)數(shù)據(jù)量大小的增加而增加，這是因?yàn)槿蝿?wù)數(shù)據(jù)量大小會(huì)對(duì)任務(wù)上傳的能耗造成影響，在這種情況下本文提出的IHGA-AFSA 方案在能耗優(yōu)化方面效果是最好的。隨機(jī)卸載策略中，卸載決策是隨機(jī)選擇的，并且本文時(shí)延因子設(shè)置的較大，更傾向于對(duì)時(shí)延的優(yōu)化，在圖10 中也證實(shí)了該方案對(duì)能耗優(yōu)化的有效性。當(dāng)任務(wù)數(shù)據(jù)量大小為1 MB 時(shí)，IGHA-AFSA 方案相比于本地計(jì)算、隨機(jī)卸載、IHGA-平均方案所產(chǎn)生的能耗降低了約32.1%、27.2%、13.6%。

圖10 任務(wù)數(shù)據(jù)量大小與系統(tǒng)內(nèi)能耗的關(guān)系

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

本文對(duì)基于MEC 車聯(lián)網(wǎng)中的任務(wù)卸載決策和資源分配進(jìn)行了研究?？紤]決策和資源的約束，建立了以最小化系統(tǒng)內(nèi)平均開(kāi)銷為目標(biāo)的計(jì)算模型。針對(duì)優(yōu)化問(wèn)題的NP-hard，將優(yōu)化問(wèn)題劃分成2 個(gè)子問(wèn)題，提出了一個(gè)基于改進(jìn)的混合遺傳算法的兩階段啟發(fā)式方案。利用IHGA求解任務(wù)卸載決策，AFSA求解資源分配，再將二者不斷迭代優(yōu)化求解，直至達(dá)到閾值條件。仿真結(jié)果表明，所提方案與基準(zhǔn)方案相比降低了系統(tǒng)內(nèi)的平均開(kāi)銷、時(shí)延及能耗。