車聯(lián)網(wǎng)云邊協(xié)同計(jì)算場(chǎng)景下的多目標(biāo)優(yōu)化卸載決策

朱思峰，蔡江昊，柴爭(zhēng)義，孫恩林

（1.天津城建大學(xué)計(jì)算機(jī)與信息工程學(xué)院，天津 300384；2.天津工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，天津 300387）

0 引言

隨著萬(wàn)物互聯(lián)時(shí)代的到來(lái)，各類能夠提升人們生活質(zhì)量的物聯(lián)網(wǎng)服務(wù)不斷涌現(xiàn)，增強(qiáng)現(xiàn)實(shí)、自動(dòng)駕駛和多維數(shù)字媒體等應(yīng)用開(kāi)始全面向移動(dòng)終端遷移[1-3]。這些具有高資源需求性的任務(wù)對(duì)移動(dòng)終端有限的計(jì)算和存儲(chǔ)資源帶來(lái)了極大的挑戰(zhàn)。云計(jì)算允許用戶將任務(wù)卸載到云端以使用其豐富的計(jì)算和存儲(chǔ)資源。但車聯(lián)網(wǎng)場(chǎng)景下的任務(wù)常常具有高時(shí)延敏感性的特點(diǎn)，上傳到云端會(huì)帶來(lái)不可避免的高額傳輸時(shí)延，這使常規(guī)的云計(jì)算模型在車聯(lián)網(wǎng)場(chǎng)景下無(wú)法適用。邊緣計(jì)算通過(guò)將任務(wù)卸載到網(wǎng)絡(luò)邊緣的服務(wù)設(shè)備上以提供就近的服務(wù)，實(shí)現(xiàn)了云計(jì)算資源的下沉，為云計(jì)算提供了良好的補(bǔ)充。雖然邊緣計(jì)算可以顯著降低任務(wù)的傳輸時(shí)延和傳輸過(guò)程中受到的干擾，但是與云計(jì)算相比，邊緣計(jì)算所能提供的計(jì)算和存儲(chǔ)資源是有限的，因此協(xié)同云計(jì)算和邊緣計(jì)算可以提供更優(yōu)質(zhì)的服務(wù)[4]。此外，隨著技術(shù)發(fā)展，車載終端所具有的資源也不應(yīng)當(dāng)被忽視，通過(guò)整合車輛空閑資源作為資源池可為車載任務(wù)提供服務(wù)。

目前，對(duì)于車聯(lián)網(wǎng)場(chǎng)景下的云邊協(xié)同計(jì)算卸載決策已經(jīng)有了一定的研究基礎(chǔ)。文獻(xiàn)[5]在車聯(lián)網(wǎng)場(chǎng)景下構(gòu)建了單向公路模型并設(shè)計(jì)了邊緣服務(wù)器和車載服務(wù)器協(xié)同工作的安全協(xié)商機(jī)制，提出了一種在車輛移動(dòng)時(shí)的安全切換交互協(xié)議，完成了對(duì)卸載能耗和時(shí)延的優(yōu)化；文獻(xiàn)[6]在云邊協(xié)同策略下，提出了一種協(xié)同優(yōu)化計(jì)算卸載資源分配優(yōu)化方案，在邊緣服務(wù)器計(jì)算資源不足的情況下有效提高系統(tǒng)效用和計(jì)算時(shí)間。

此外，對(duì)于計(jì)算卸載策略的研究也已經(jīng)較成熟，常用的方法主要有深度學(xué)習(xí)、強(qiáng)化學(xué)習(xí)和啟發(fā)式算法等。文獻(xiàn)[7]結(jié)合每個(gè)移動(dòng)設(shè)備的系統(tǒng)效益和帶寬分配建立了一個(gè)混合卸載模型，提出了一種分布式深度學(xué)習(xí)驅(qū)動(dòng)任務(wù)卸載（DDTO,distributed deep learning-driven task offloading）算法，實(shí)現(xiàn)了對(duì)移動(dòng)設(shè)備、邊緣服務(wù)器和中心云服務(wù)器的共同優(yōu)化；文獻(xiàn)[8]設(shè)計(jì)了一種車輛輔助卸載的計(jì)算卸載網(wǎng)絡(luò)架構(gòu)，結(jié)合Q-learning 方法和深度強(qiáng)化學(xué)習(xí)（DRL,deep reinforcement learning）方法獲得計(jì)算卸載和資源分配的最佳策略；文獻(xiàn)[9]結(jié)合云計(jì)算和霧計(jì)算設(shè)計(jì)了優(yōu)化模型，采用基于非支配排序的遺傳算法（NSGA-II,nondominated sorting genetic algorithm II）對(duì)多目標(biāo)問(wèn)題進(jìn)行了優(yōu)化求解，結(jié)果表明該模型可以有效地對(duì)系統(tǒng)的能量消耗和卸載時(shí)延進(jìn)行優(yōu)化；文獻(xiàn)[10]在車聯(lián)網(wǎng)場(chǎng)景下提出了一種基于時(shí)效性的數(shù)據(jù)傳輸模型，通過(guò)結(jié)合車對(duì)車（V2V,vehicle to vehicle）通信和車對(duì)基礎(chǔ)設(shè)備（V2I,vehicle to infrastructure）通信，使用演化算法對(duì)數(shù)據(jù)質(zhì)量和交付比2 個(gè)相互沖突的目標(biāo)同時(shí)優(yōu)化。

在復(fù)雜的車載網(wǎng)絡(luò)環(huán)境下，為了滿足大量用戶多樣化的服務(wù)需求，用戶可以將任務(wù)卸載到具有豐富資源的邊緣服務(wù)器或云服務(wù)器執(zhí)行，高效的計(jì)算卸載機(jī)制可以提供更優(yōu)質(zhì)的服務(wù)。然而服務(wù)端在處理任務(wù)時(shí)不僅需要具有充足的計(jì)算資源，也需要緩存相應(yīng)的服務(wù)應(yīng)用，現(xiàn)有工作通常只對(duì)服務(wù)端的計(jì)算資源進(jìn)行管理，忽視了任務(wù)對(duì)服務(wù)緩存的需求。同時(shí)，邊緣服務(wù)端有限的計(jì)算和存儲(chǔ)資源也使計(jì)算卸載策略和邊緣緩存策略呈相互耦合的關(guān)系。如何將邊緣緩存策略引入車聯(lián)網(wǎng)場(chǎng)景已經(jīng)成為一個(gè)關(guān)鍵且具有挑戰(zhàn)性的問(wèn)題。文獻(xiàn)[11]使用分層緩存策略對(duì)小基站（SBS,small base station）和宏基站（MBS,macro base station）進(jìn)行了聯(lián)合優(yōu)化，在滿足文件傳輸速率要求和緩存資源的前提下最大限度地提高網(wǎng)絡(luò)容量；文獻(xiàn)[12]通過(guò)異步分布式強(qiáng)化學(xué)習(xí)算法對(duì)車聯(lián)網(wǎng)場(chǎng)景下的任務(wù)卸載和服務(wù)緩存問(wèn)題進(jìn)行了聯(lián)合優(yōu)化，對(duì)網(wǎng)絡(luò)資源進(jìn)行全面協(xié)同和管理。

上述文獻(xiàn)分別從云邊協(xié)同策略、計(jì)算卸載常用優(yōu)化方法和邊緣緩存策略多個(gè)角度對(duì)現(xiàn)有工作進(jìn)行了介紹，可以看到，目前對(duì)于邊緣計(jì)算卸載決策的研究較成熟，但對(duì)于車聯(lián)網(wǎng)等特殊場(chǎng)景的計(jì)算卸載模式和邊緣緩存策略在車聯(lián)網(wǎng)領(lǐng)域的應(yīng)用仍然存在盲點(diǎn)。針對(duì)該問(wèn)題，本文將主要考慮在車聯(lián)網(wǎng)場(chǎng)景下結(jié)合中心云、邊緣云和車輛云三層架構(gòu)模型，通過(guò)將卸載策略與信道狀態(tài)結(jié)合，以突出計(jì)算卸載策略與邊緣緩存策略之間的耦合關(guān)系，并采用多目標(biāo)智能優(yōu)化算法對(duì)模型進(jìn)行求解。本文的主要貢獻(xiàn)如下。

1) 設(shè)計(jì)了一種基于多目標(biāo)免疫算法（MOIA,multi-objective immune algorithm）來(lái)實(shí)現(xiàn)對(duì)卸載時(shí)延、車載終端能耗和服務(wù)質(zhì)量的多目標(biāo)優(yōu)化。

2) 提出了一種基于云邊協(xié)同的計(jì)算卸載網(wǎng)絡(luò)模型，使用基于車對(duì)車通信的無(wú)線傳輸來(lái)緩解車輛在跨區(qū)域傳輸任務(wù)時(shí)所帶來(lái)的帶寬壓力。

3) 通過(guò)對(duì)服務(wù)應(yīng)用進(jìn)行分類，設(shè)計(jì)了一種自適應(yīng)的邊緣緩存策略并應(yīng)用于車聯(lián)網(wǎng)場(chǎng)景。

1 系統(tǒng)模型

本文主要考慮云邊協(xié)同三層架構(gòu)下的雙向直線型公路場(chǎng)景，在路邊均勻分布多個(gè)路側(cè)感知單元并分別配備邊緣服務(wù)器，并設(shè)有一個(gè)中心服務(wù)器。車輛與路側(cè)感知單元采用無(wú)線通信，相鄰的邊緣服務(wù)器和所轄的各路側(cè)感知單元之間采用有線連接，本文設(shè)計(jì)的系統(tǒng)架構(gòu)如圖1 所示。圖1 展示了車載任務(wù)處理的4 種方式：本地執(zhí)行、原屬邊緣服務(wù)器執(zhí)行、中心云服務(wù)器執(zhí)行和跨區(qū)域邊緣服務(wù)器執(zhí)行。系統(tǒng)架構(gòu)主要分為三層：中心云、邊緣云、車輛云，該架構(gòu)的主要優(yōu)勢(shì)介紹如下[12]。

圖1 系統(tǒng)架構(gòu)

縱向協(xié)作。在該模型中，有多種可為車載終端提供服務(wù)的設(shè)備（遠(yuǎn)點(diǎn)的中心集群云服務(wù)器、近點(diǎn)的邊緣服務(wù)器、車輛本身的服務(wù)設(shè)備），通過(guò)對(duì)任務(wù)的智能調(diào)度，可以為處在網(wǎng)絡(luò)底層的車輛設(shè)備提供更高質(zhì)量的服務(wù)。

橫向協(xié)作。當(dāng)大量任務(wù)從車輛終端卸載到邊緣服務(wù)器時(shí)，會(huì)不可避免地使各個(gè)服務(wù)器的負(fù)載不均衡，輕負(fù)載的服務(wù)器具有大量的閑置資源，重負(fù)載的服務(wù)器將使服務(wù)質(zhì)量下降甚至使部分任務(wù)無(wú)法完成。通過(guò)對(duì)邊緣服務(wù)器的任務(wù)調(diào)度遷移，可以提高系統(tǒng)資源使用率。

跨區(qū)傳輸。為解決任務(wù)跨區(qū)域傳輸問(wèn)題，在該架構(gòu)中引入基于車對(duì)車通信的無(wú)線傳輸，為車載任務(wù)傳輸提供更多的選擇，以緩解服務(wù)器之間進(jìn)行大量任務(wù)調(diào)度所帶來(lái)的帶寬壓力。

在該模型中，車載服務(wù)單元、邊緣服務(wù)器和云服務(wù)器均可為任務(wù)提供服務(wù)，每個(gè)服務(wù)單元具有獨(dú)立的存儲(chǔ)資源Zj和計(jì)算資源Cj，將服務(wù)器ECj的特征信息表示為{Z j,Cj},1≤j≤n+1，車輛在公路上勻速行駛且有一個(gè)特定類型的計(jì)算密集型任務(wù)可向服務(wù)器申請(qǐng)卸載，該任務(wù)需要存儲(chǔ)資源zi和計(jì)算資源ci。使用二進(jìn)制變量air表示所有任務(wù)的任務(wù)類型，當(dāng)air=1時(shí)，表示任務(wù)i的任務(wù)類型為r，將taski的特征信息表示為{z i,ci,r},1≤i≤m,1≤r≤k。每個(gè)時(shí)隙邊緣服務(wù)器都可預(yù)先緩存多個(gè)不同類型的服務(wù)應(yīng)用，每個(gè)類型應(yīng)用都會(huì)占用額外的存儲(chǔ)資源zr，使用bjr（1≤j≤n+1）表示服務(wù)器的緩存情況，當(dāng)bjr=1時(shí)，表示ECj緩存了類型為r的服務(wù)應(yīng)用。

本文采用集中式?jīng)Q策。每個(gè)時(shí)隙開(kāi)始時(shí)，車載終端和邊緣服務(wù)器分別將任務(wù)特征信息{z i,ci,r} 和服務(wù)器特征信息{Zj,Cj}上傳至云服務(wù)器，云服務(wù)器將任務(wù)所需資源類型和各服務(wù)器所具有的資源進(jìn)行匯總，結(jié)合卸載時(shí)延、車載能量消耗和服務(wù)質(zhì)量成功率高效地為用戶分配卸載目標(biāo)服務(wù)器xi（云服務(wù)器、邊緣服務(wù)器、車載終端）、對(duì)應(yīng)的傳輸方式hi和該時(shí)隙中邊緣服務(wù)器的緩存策略bjr。特別地，當(dāng)出現(xiàn)車輛任務(wù)卸載目標(biāo)服務(wù)器不在該車輛所在區(qū)域時(shí)，車輛可以通過(guò)基于V2V 技術(shù)的無(wú)線傳輸或通過(guò)服務(wù)器傳輸來(lái)完成車輛的跨區(qū)域傳輸。當(dāng)使用V2V 技術(shù)傳輸時(shí)，任務(wù)會(huì)先傳給下一區(qū)域（為得出更有效的結(jié)論，本文將單個(gè)區(qū)域的長(zhǎng)度定義為V2V 技術(shù)的可靠傳輸范圍）內(nèi)的車輛，并由該車輛進(jìn)行傳遞。

1.1 緩存模型

邊緣緩存策略的優(yōu)勢(shì)在于通過(guò)提前在服務(wù)器端緩存相應(yīng)的服務(wù)應(yīng)用來(lái)更快地為指定類型任務(wù)提供更高效的服務(wù)，但邊緣服務(wù)器有限的計(jì)算和存儲(chǔ)資源無(wú)法緩存所有類型任務(wù)的服務(wù)應(yīng)用，當(dāng)邊緣服務(wù)器使用未緩存類型服務(wù)應(yīng)用時(shí)，需要從云服務(wù)器端下載該服務(wù)應(yīng)用，該應(yīng)用會(huì)在使用完成后被放棄，再次使用時(shí)需要重新下載，并帶來(lái)額外的時(shí)延。而車載單元執(zhí)行任務(wù)時(shí)，向邊緣服務(wù)器請(qǐng)求服務(wù)應(yīng)用，若邊緣服務(wù)器未緩存該類型任務(wù)，則需要邊緣服務(wù)器額外從云服務(wù)器下載并傳遞。設(shè)g為中心云服務(wù)器需要提供服務(wù)應(yīng)用總次數(shù)，則云服務(wù)器吞吐率為

其中，二進(jìn)制變量uij表示車載任務(wù)的卸載目標(biāo)，uij=1表示taski在ECj上執(zhí)行，uij=0表示taski在車載終端本地執(zhí)行；B表示服務(wù)器之間分配的帶寬，S表示信道損失，P表示服務(wù)器的傳輸功率，σ2表示噪聲功率[13-14]。則在一個(gè)時(shí)隙內(nèi)，下載taski所需的服務(wù)應(yīng)用所帶來(lái)的緩存時(shí)延為

其中，θV2E為車輛到邊緣服務(wù)器（V2E,vehicle to edge computing server）的字節(jié)傳輸速率。wi為二進(jìn)制變量，wi=1表示taski的所屬服務(wù)器已緩存所需的應(yīng)用程序。

1.2 時(shí)延模型

任務(wù)的執(zhí)行時(shí)延分為處理時(shí)延和排隊(duì)時(shí)延兩部分[15]，其中處理時(shí)延只與服務(wù)器性能和任務(wù)所需的計(jì)算資源相關(guān)，則taski的執(zhí)行時(shí)延為

任務(wù)的排隊(duì)時(shí)延與該服務(wù)器當(dāng)前狀態(tài)的負(fù)載情況相關(guān)，設(shè)Kj為ECj上已卸載未完成的任務(wù)集合，則taski的排隊(duì)時(shí)延為

任務(wù)的傳輸時(shí)延分為車輛上傳時(shí)延、邊緣服務(wù)器之間的傳輸時(shí)延、車對(duì)車傳輸時(shí)延和邊緣服務(wù)器上傳到中心云服務(wù)器的上傳時(shí)延（E2C,edge computing server to cloud computing server）4 個(gè)部分，由于本文考慮計(jì)算密集型任務(wù)，計(jì)算結(jié)果回傳時(shí)延忽略不計(jì)。車輛上傳時(shí)延與任務(wù)所占的存儲(chǔ)資源和車載終端的發(fā)射功率相關(guān)，則taski的上傳時(shí)延為

任務(wù)在邊緣服務(wù)器之間的傳輸時(shí)延與任務(wù)所占的存儲(chǔ)資源和分配到的帶寬相關(guān)，在設(shè)計(jì)的公路模型中，只有相鄰的服務(wù)器采用有線連接，當(dāng)二進(jìn)制變量yij=1時(shí)，taski將會(huì)使用ECj和ECj+1之間的信道。結(jié)合香農(nóng)公式，得到協(xié)同服務(wù)器完成卸載決策后ECj和ECj+1之間通信的單位傳輸速率為

則taski在邊緣服務(wù)器之間的傳輸時(shí)延為

當(dāng)任務(wù)需要跨區(qū)域傳輸時(shí)，除通過(guò)服務(wù)器之間傳輸外，還可以通過(guò)基于車對(duì)車通信技術(shù)的無(wú)線傳輸，則車對(duì)車傳輸時(shí)延除了與任務(wù)所需存儲(chǔ)資源和車輛傳輸功率相關(guān)外，還與所跨區(qū)域數(shù)量相關(guān)[16]，則基于車對(duì)車通信的傳輸時(shí)延為

其中，二進(jìn)制變量hi表示需要跨區(qū)域傳輸時(shí)任務(wù)的傳輸方式，hi=0表示taski會(huì)通過(guò)車對(duì)車通信的無(wú)線傳輸，hi=1表示taski會(huì)由服務(wù)器進(jìn)行轉(zhuǎn)遞；ρ表示通過(guò)車輛跨區(qū)域傳輸次數(shù)，θV2V表示車對(duì)車的字節(jié)傳輸速率。則taski在通過(guò)邊緣服務(wù)器上傳到中心云服務(wù)器的傳輸時(shí)延為

車載終端的可卸載服務(wù)單元有車載終端、邊緣服務(wù)器和云服務(wù)器3 種，則taski的卸載總時(shí)延為

該系統(tǒng)的卸載總時(shí)延為

1.3 能耗模型

本節(jié)設(shè)計(jì)的系統(tǒng)模型中的能耗主要考慮車載終端的使用能耗，分為本地執(zhí)行能耗和任務(wù)卸載能耗兩大部分。本地執(zhí)行能耗與任務(wù)大小和車載服務(wù)器功率相關(guān)，則taski在本地執(zhí)行時(shí)的能耗為

其中，α表示車載服務(wù)器的功率。則taski由車載終端卸載到服務(wù)器的能耗為

其中，θV2V表示車載終端的傳輸速率，β表示車載終端的傳輸功率，則taski的總能耗Ei為

則系統(tǒng)總能耗E為

1.4 服務(wù)質(zhì)量模型

隨著計(jì)算卸載和邊緣緩存模型的建立，將任務(wù)從有限的計(jì)算和存儲(chǔ)資源的車載終端卸載到性能更高的邊緣服務(wù)器來(lái)降低任務(wù)計(jì)算時(shí)延和終端設(shè)備能耗成為所有車載終端的傾向，但呈正相關(guān)的時(shí)延和能耗關(guān)系并不符合實(shí)際場(chǎng)景和設(shè)計(jì)需求。隨著車載終端數(shù)量的增加，任務(wù)在服務(wù)器端的排隊(duì)時(shí)延和各服務(wù)器之間的信道質(zhì)量會(huì)有所下降。而一定程度上增加的排隊(duì)時(shí)延和下降的信道質(zhì)量是可以接受的，為了將卸載決策與任務(wù)排隊(duì)時(shí)延和信道質(zhì)量?jī)?yōu)化結(jié)合，本節(jié)假設(shè)車載終端的任務(wù)具有最大響應(yīng)時(shí)延tmax[15]，設(shè)二進(jìn)制變量qi表示taski是否卸載成功，即

則系統(tǒng)的服務(wù)質(zhì)量Q為

1.5 問(wèn)題模型

本文在車聯(lián)網(wǎng)場(chǎng)景下設(shè)計(jì)的模型將最小化時(shí)延作為主要目標(biāo)，并保證各個(gè)服務(wù)器負(fù)載均衡的同時(shí)降低服務(wù)器總能耗。因此將本文要解決的問(wèn)題定義為

其中，式(19)表示在卸載過(guò)程中服務(wù)器的存儲(chǔ)資源不會(huì)過(guò)載（任務(wù)所需的存儲(chǔ)資源、緩存資源和臨時(shí)緩存資源）；式(20)表示在卸載過(guò)程中服務(wù)器的計(jì)算資源不會(huì)過(guò)載；式(21)表示云服務(wù)器會(huì)緩存所有類型的任務(wù)；式(22)表示每個(gè)任務(wù)僅在一個(gè)服務(wù)器或者本地執(zhí)行。

2 基于MOIA 的卸載決策方案

傳統(tǒng)的優(yōu)化算法由于具有較高的時(shí)間復(fù)雜度導(dǎo)致其在車聯(lián)網(wǎng)場(chǎng)景下的效果不太理想，而演化算法在近年來(lái)得到了極大的發(fā)展，并能夠較好地滿足車聯(lián)網(wǎng)場(chǎng)景下高時(shí)延敏感性的特點(diǎn)。免疫算法是一種新興的主流演化算法，近年來(lái)得到了極大的發(fā)展和完善。在免疫算法中，抗原代表待優(yōu)化的問(wèn)題，抗體代表問(wèn)題的候選解，抗體中一個(gè)基因位代表一個(gè)任務(wù)的卸載決策，采用親和度函數(shù)來(lái)評(píng)估抗體對(duì)抗原的適應(yīng)能力。

2.1 編碼

通過(guò)對(duì)問(wèn)題固有特征分析并選擇合適的編碼方式是演化類算法的第一步，本文提出的問(wèn)題主要是對(duì)3 個(gè)相互耦合內(nèi)容進(jìn)行組合優(yōu)化。第一部分是對(duì)任務(wù)的卸載目標(biāo)服務(wù)器進(jìn)行決策，跨區(qū)域數(shù)量會(huì)通過(guò)影響服務(wù)器直接的信道質(zhì)量而對(duì)時(shí)延造成直接影響，二進(jìn)制編碼容易丟失問(wèn)題的固有信息，因此本節(jié)將二進(jìn)制變量uij轉(zhuǎn)化為十進(jìn)制變量xi，轉(zhuǎn)化式為

當(dāng)xi=j時(shí)，表示taski在ECj上執(zhí)行；xi=0時(shí)，表示taski在車輛本地執(zhí)行。第二部分對(duì)需要跨區(qū)域任務(wù)的上傳方式進(jìn)行決策，使用二進(jìn)制變量hi表示，當(dāng)hi=1時(shí)，taski會(huì)通過(guò)基于車對(duì)車通信的無(wú)線鏈路進(jìn)行傳輸；當(dāng)hi=0時(shí)，taski會(huì)通過(guò)服務(wù)器進(jìn)行傳遞。第三部分對(duì)各個(gè)服務(wù)器的服務(wù)應(yīng)用緩存情況進(jìn)行決策，使用二進(jìn)制變量bjr（1≤j≤n+1）表示，當(dāng)bjr=1時(shí)，表示ECj緩存了類型為r的服務(wù)應(yīng)用；當(dāng)bjr=0時(shí)，表示ECj未緩存該類型服務(wù)應(yīng)用。

2.2 抗體種群初始化

在本文設(shè)計(jì)的模型中，任務(wù)跨區(qū)域傳輸次數(shù)將直接導(dǎo)致任務(wù)傳輸時(shí)延的增加。因此在初始化過(guò)程中，xij將根據(jù)每個(gè)任務(wù)所屬服務(wù)器的初始狀態(tài)生成而不是隨機(jī)生成，將hi和bjr全部設(shè)置為0，默認(rèn)初始狀態(tài)所有任務(wù)通過(guò)服務(wù)器傳輸且邊緣服務(wù)器不會(huì)緩存服務(wù)應(yīng)用。最后依概率進(jìn)行變異生成初始種群，并采用約束式(19)～式(22)對(duì)抗體種群進(jìn)行修正。

2.3 親和度評(píng)價(jià)函數(shù)

在免疫算法中，親和度函數(shù)用來(lái)評(píng)價(jià)抗體和抗原的結(jié)合情況，即該抗體對(duì)應(yīng)解與問(wèn)題結(jié)合強(qiáng)度，對(duì)應(yīng)遺傳算法中的適應(yīng)度函數(shù)。本文從卸載時(shí)延、能量消耗和服務(wù)質(zhì)量3 個(gè)方面進(jìn)行評(píng)價(jià)，則抗體的親和度評(píng)價(jià)函數(shù)分別如式(11)、式(15)和式(17)所示。

2.4 變異算子

免疫算法通過(guò)變異算子對(duì)得到的抗體群進(jìn)行局部搜索，算法中所有變異操作均采用單點(diǎn)變異，通過(guò)將抗體的某一位依概率進(jìn)行隨機(jī)變異或按位取反。由于xij表征的任務(wù)只能有一個(gè)卸載目標(biāo)，而任務(wù)從初始服務(wù)器傳遞到其他服務(wù)器的跨度將降低服務(wù)器之間的信道使用程度并直接影響時(shí)延，因此本節(jié)設(shè)計(jì)了一種基于距離的自適應(yīng)變異方法，如式(24)所示。

圖2 變異操作

2.5 MOIA 框架

本節(jié)提出了一種改進(jìn)的MOIA。首先根據(jù)分配的初始狀態(tài)就近隨機(jī)生成初始抗體種群；在對(duì)當(dāng)前種群進(jìn)行標(biāo)準(zhǔn)化和關(guān)聯(lián)之后，根據(jù)非支配層選擇前個(gè)抗體進(jìn)行免疫操作（選擇、克隆、克隆抑制）；在進(jìn)行免疫操作時(shí)，為了保證生成解的多樣性，MOIA 借鑒了NSGA-III 算法中參考線為核心的理念，使用支配原則和基于參考點(diǎn)的選擇來(lái)對(duì)抗體種群進(jìn)行更新；最后刷新種群大小至NP。與常規(guī)的NSGA-III 算法相比，改進(jìn)的MOIA 具有更好的多峰值搜索能力。算法1 給出了MOIA 的偽代碼。MOIA 的計(jì)算復(fù)雜度為O((nD+nC)2)，其中nD為決策種群規(guī)模，nC為克隆種群規(guī)模[17]。

算法1MOIA 的偽代碼

2.6 標(biāo)準(zhǔn)化與子代種群

由于求解的問(wèn)題需要同時(shí)對(duì)多個(gè)目標(biāo)進(jìn)行優(yōu)化，而其數(shù)量級(jí)通常不在一個(gè)數(shù)量級(jí)上，因此在得到更新后的抗體種群后需要對(duì)其進(jìn)行標(biāo)準(zhǔn)化以便進(jìn)行下一步的操作，本節(jié)采用的標(biāo)準(zhǔn)化方式為

其中，為抗體的單個(gè)優(yōu)化目標(biāo)取值，NP 為種群規(guī)模。標(biāo)準(zhǔn)化完成后，將參考點(diǎn)與理想點(diǎn)相連得到參考線，并將每個(gè)個(gè)體和與其最近的參考線關(guān)聯(lián)，根據(jù)關(guān)聯(lián)后的非支配關(guān)系得到下一代種群。特別地，本文提出的MOIA 的參考點(diǎn)設(shè)計(jì)使用Das 和Dennis[18]提出的方法，而理想點(diǎn)的取值為父代種群在每個(gè)目標(biāo)上的最小值。

2.7 免疫操作

算法2 給出了免疫操作的偽代碼。在對(duì)選出的抗體進(jìn)行克隆變異時(shí)，使用公式進(jìn)行鄰近變異以提升效率。同時(shí)，在改進(jìn)的MOIA 中深化了參考線的作用，在標(biāo)準(zhǔn)化完成后保留相關(guān)參數(shù)并在進(jìn)行免疫操作時(shí)也會(huì)采用同樣的參考標(biāo)準(zhǔn)，在克隆抑制操作時(shí)，當(dāng)個(gè)體滿足以下3 個(gè)條件之一時(shí)，該個(gè)體就會(huì)被保留：1) 該個(gè)體是本次克隆種群內(nèi)支配原個(gè)體程度最高的個(gè)體；2) 該個(gè)體使用新的參考線；3) 該個(gè)體的3 個(gè)目標(biāo)值小于原種群中的最小值，即不被理想點(diǎn)支配。特別地，條件3)被用于處理優(yōu)于理想點(diǎn)的個(gè)體，通過(guò)對(duì)條件3)進(jìn)行控制可以實(shí)現(xiàn)對(duì)優(yōu)化目標(biāo)的宏觀調(diào)控（3.2 節(jié)）。在完成迭代后，將會(huì)返回一個(gè)略大于的種群，通過(guò)種群刷新操作保持種群規(guī)模為NP。

算法2免疫操作的偽代碼

3 仿真實(shí)驗(yàn)及分析

為了驗(yàn)證本文提出的基于云邊協(xié)同方案和MOIA的有效性，本節(jié)使用MATLAB 軟件進(jìn)行仿真實(shí)驗(yàn)。在本節(jié)的仿真實(shí)驗(yàn)中，3.1 節(jié)將驗(yàn)證MOIA 的有效性，并將其與傳統(tǒng)的NSGA-III[19-20]、NSGA-II[21]、MOEA-D[22]和Pareto 前沿進(jìn)行對(duì)比；3.2 節(jié)對(duì)MOIA 的定向優(yōu)化性能進(jìn)行實(shí)驗(yàn)驗(yàn)證；3.3 節(jié)對(duì)不同最大時(shí)延約束下MOIA方案的優(yōu)化效果進(jìn)行了對(duì)比；3.4 節(jié)對(duì)設(shè)計(jì)的通信策略和緩存策略進(jìn)行了對(duì)比實(shí)驗(yàn)，并展示了4 種卸載方案的各部分優(yōu)化指標(biāo)。本文實(shí)驗(yàn)的算法參數(shù)為迭代次數(shù)Gen=100、種群規(guī)模NP=100、變異概率、克隆個(gè)數(shù)NCL=10、任務(wù)數(shù)量M=100、邊緣服務(wù)器數(shù)量N=5。本文實(shí)驗(yàn)中制定的詳細(xì)仿真參數(shù)如表1 所示。

表1 仿真參數(shù)

3.1 與不同卸載算法的優(yōu)化效果對(duì)比

本節(jié)將本文提出的 MOIA 算法與傳統(tǒng)的MOEA-D、NSGA-II、NSGA-III 算法及Pareto 前沿進(jìn)行對(duì)比。其中Pareto 是4 種算法分別運(yùn)行100 次得到的最優(yōu)前沿。圖3～圖5 分別展示了4 種算法及其Pareto 前沿的運(yùn)行效果。可以看出，MOIA 算法具有更好的全局搜索能力，同時(shí)在單個(gè)目標(biāo)的優(yōu)化上具有較好的效果。特別地，由于在模型設(shè)計(jì)中卸載總時(shí)延和服務(wù)質(zhì)量的評(píng)價(jià)沒(méi)有呈現(xiàn)出對(duì)立性，因此在圖4 中Pareto 前沿的設(shè)計(jì)中采用相同服務(wù)質(zhì)量情況下的最小時(shí)延情況，即Pareto 前沿為靠近服務(wù)質(zhì)量一側(cè)。

圖3 4 種算法及其Pareto 前沿的能量消耗與服務(wù)質(zhì)量對(duì)比

圖4 4 種算法及其Pareto 前沿的卸載總時(shí)延與服務(wù)質(zhì)量對(duì)比

圖5 4 種算法及其Pareto 前沿的卸載總時(shí)延與能量消耗對(duì)比

3.2 MOIA 定向優(yōu)化能力測(cè)試

本節(jié)就MOIA在優(yōu)化過(guò)程中對(duì)單個(gè)目標(biāo)的調(diào)控能力進(jìn)行實(shí)驗(yàn)，調(diào)控方法為在達(dá)到指定迭代次數(shù)前只對(duì)單個(gè)目標(biāo)進(jìn)行優(yōu)化。圖6～圖8 為達(dá)到最大迭代次數(shù)后整個(gè)種群的分布情況，分別展示了對(duì)優(yōu)化目標(biāo)T、E、Q 的對(duì)比優(yōu)化效果，可以看出，在每個(gè)優(yōu)化目標(biāo)上的種群分布都更集中，且該目標(biāo)上的最優(yōu)值有所突破。其中，MOIA-T、MOIA-E、MOIA-Q分別在前50%的迭代次數(shù)中僅對(duì)該目標(biāo)上滿足條件3)的個(gè)體（即在該目標(biāo)上優(yōu)于理想點(diǎn)的個(gè)體）進(jìn)行保留。結(jié)合圖6～圖8 的種群分布情況，本文認(rèn)為MOIA 可以通過(guò)對(duì)迭代次數(shù)的控制來(lái)達(dá)到對(duì)特定目標(biāo)的優(yōu)化效果。特別地，結(jié)合圖6～圖8 的種群分布和基于參考點(diǎn)的算法理論，本文認(rèn)為MOIA 是通過(guò)增加種群在單個(gè)目標(biāo)上的濃度以達(dá)到對(duì)更優(yōu)解搜索的效果。

圖7 對(duì)能量消耗優(yōu)化時(shí)的種群分布

圖8 對(duì)服務(wù)質(zhì)量?jī)?yōu)化時(shí)的種群分布

3.3 不同最大響應(yīng)時(shí)延下的優(yōu)化效果對(duì)比

圖9～圖11 分別展示了當(dāng)最大響應(yīng)時(shí)延tmax分別為1 s、2 s、3 s 時(shí)MOIA 的優(yōu)化效果對(duì)比。圖9 和圖10 分別為服務(wù)質(zhì)量與能量消耗和卸載總時(shí)延的關(guān)系，實(shí)驗(yàn)結(jié)果隨最大響應(yīng)時(shí)延變化呈梯次分布。圖11 為能量消耗和卸載總時(shí)延的關(guān)系，實(shí)驗(yàn)結(jié)果在同一梯度上，最大時(shí)延變化與能耗和任務(wù)卸載時(shí)延無(wú)直接關(guān)聯(lián)，實(shí)驗(yàn)結(jié)果和理論依據(jù)相符。本文認(rèn)為通過(guò)對(duì)最大時(shí)延的調(diào)整可以得到符合要求的實(shí)驗(yàn)數(shù)據(jù)。

圖9 不同最大響應(yīng)時(shí)延下能量消耗與服務(wù)質(zhì)量對(duì)比

圖10 不同最大響應(yīng)時(shí)延下卸載總時(shí)延與服務(wù)質(zhì)量對(duì)比

圖11 不同最大響應(yīng)時(shí)延下卸載總時(shí)延與能量消耗對(duì)比

3.4 對(duì)緩存策略和通信策略的測(cè)試

為了對(duì)本文模型設(shè)計(jì)中的通信策略和緩存策略效果進(jìn)行研究，本節(jié)選擇tmax=1s時(shí)MOIA 方案在服務(wù)質(zhì)量指標(biāo)最低條件下能耗最小的個(gè)體進(jìn)行展示。圖12 為各對(duì)比算法在服務(wù)質(zhì)量上的取值；圖13 為各對(duì)比算法在能量消耗的取值；圖14 為各對(duì)比算法在各部分時(shí)延上的取值。其中，基準(zhǔn)（Benchmark）方案為MOIA 對(duì)通信策略和緩存策略均隨機(jī)賦值優(yōu)化后得到的方案[16,23]。

圖12 不同算法的服務(wù)質(zhì)量對(duì)比

圖13 不同算法的各部分能量消耗對(duì)比

在本文設(shè)計(jì)的優(yōu)化模型中，當(dāng)任務(wù)需要卸載到其他邊緣服務(wù)器時(shí)，可以通過(guò)基于V2V 技術(shù)的無(wú)線傳輸或通過(guò)服務(wù)器進(jìn)行傳輸；MOIA-S 方案對(duì)通信策略進(jìn)行了測(cè)試，取消了基于V2V 技術(shù)的無(wú)線傳輸，只能通過(guò)服務(wù)器進(jìn)行傳輸。從圖14 中可以看出，MOIA-S 方案較MOIA 方案和基準(zhǔn)方案的卸載總時(shí)延分別增加了58.45%和28.67%；單獨(dú)通過(guò)服務(wù)器進(jìn)行任務(wù)傳輸會(huì)給帶寬帶來(lái)極大的壓力，MOIA-S 方案的傳輸時(shí)延較MOIA 方案和基準(zhǔn)方案別分增加了433.33%和279.45%。同時(shí)，隨著邊緣服務(wù)器之間傳輸任務(wù)數(shù)量的增加，信道質(zhì)量隨之下降，MOIA 傾向于將任務(wù)卸載到云端服務(wù)器執(zhí)行，因此圖14 中邊緣服務(wù)器上傳到云端的時(shí)延較MOIA 方案增加了62.58%，而緩存時(shí)延和執(zhí)行時(shí)延分別下降了35.29%和29.13%，排隊(duì)時(shí)延則上升了7.25%。此外，由于取消了基于V2V 技術(shù)的無(wú)線傳輸，車載任務(wù)只能通過(guò)服務(wù)器傳輸，因此圖13 中系統(tǒng)能耗大幅降低，且圖12 中服務(wù)質(zhì)量指標(biāo)也有所增加，表明多種傳輸方式會(huì)給用戶更好的體驗(yàn)。

圖14 不同方案的各部分時(shí)延指標(biāo)對(duì)比

為對(duì)緩存策略進(jìn)行測(cè)試，MOIA-C 方案取消了50%的可緩存任務(wù)類型，即邊緣服務(wù)器只會(huì)緩存一半的緩存任務(wù)類型。圖14 中MOIA-C 方案卸載總時(shí)延較基準(zhǔn)方案和MOIA 方案分別增加了10.35%和35.88%。為了盡可能地減少緩存策略所帶來(lái)的影響，算法傾向于更頻繁地將任務(wù)卸載到具有該類型服務(wù)應(yīng)用的邊緣服務(wù)器上，圖14 中任務(wù)的傳輸時(shí)延和緩存時(shí)延較MOIA 方案分別增加了153.89%和196.85%。同時(shí)，云服務(wù)器的高性能使算法傾向于將更多的任務(wù)卸載到云服務(wù)器，以降低額外下載服務(wù)應(yīng)用所帶來(lái)的時(shí)延，上傳到云服務(wù)器的時(shí)延較MOIA 方案增加了5.69%。由于上傳到高性能云服務(wù)器的任務(wù)增加，任務(wù)的執(zhí)行時(shí)延較MOIA 方案降低了41.37%，但排隊(duì)時(shí)延增加了47.87%。此外，部分邊緣服務(wù)器沒(méi)有相應(yīng)的服務(wù)應(yīng)用，MOIA-C 方案中任務(wù)會(huì)更多地向邊緣服務(wù)器卸載而不是在車輛終端本地執(zhí)行，而任務(wù)上傳所帶來(lái)的能量消耗遠(yuǎn)小于在本地執(zhí)行的能量消耗，因此圖13 中車載終端的執(zhí)行能耗大幅下降、上傳能耗有所提升，總能耗較MOIA 方案降低了29.94%。圖12 中MOIA-C 方案的服務(wù)質(zhì)量指標(biāo)較MOIA 方案增加了23.68%。本文認(rèn)為，高效的緩存策略可以對(duì)邊緣服務(wù)器的有限存儲(chǔ)空間進(jìn)行高效的利用，極大提升整體服務(wù)質(zhì)量。此外，計(jì)算卸載策略和邊緣緩存策略之間的耦合關(guān)系主要表現(xiàn)為邊緣服務(wù)器有限的存儲(chǔ)資源和車載終端多樣的任務(wù)類型需求之間的矛盾，高效的邊緣緩存決策可以極大降低從邊緣服務(wù)器或云服務(wù)器下載服務(wù)應(yīng)用的時(shí)間，實(shí)驗(yàn)結(jié)果與理論分析相吻合。

最后，結(jié)合圖12～圖14 中各優(yōu)化目標(biāo)的各部分指標(biāo)和對(duì)MOIA-S、MOIA-C 方案的對(duì)比實(shí)驗(yàn)可知，本文提出的緩存策略和通信策略是高效可行的。

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

本文基于車聯(lián)網(wǎng)中的車對(duì)車無(wú)線傳輸技術(shù)和邊緣緩存技術(shù)提出了一種自適應(yīng)的服務(wù)緩存和任務(wù)卸載策略，主要在一條雙向直線型公路上實(shí)現(xiàn)，在保證服務(wù)質(zhì)量的基礎(chǔ)上盡可能地降低車載任務(wù)的卸載總時(shí)延和車輛的能量消耗，通過(guò)建立卸載決策與傳輸時(shí)延的聯(lián)系以加深對(duì)緩存策略與信道狀態(tài)的聯(lián)系。本文采用基于支配關(guān)系的免疫算法完成多目標(biāo)優(yōu)化，并給出了該算法的偽代碼。仿真實(shí)驗(yàn)結(jié)果表明，本文提出的MOIA 較傳統(tǒng)的NSGA-III等多目標(biāo)算法具有相當(dāng)?shù)娜炙阉髂芰透玫膯文繕?biāo)上的搜索性能，且能夠?qū)υO(shè)計(jì)的緩存策略和通信策略進(jìn)行高效使用，達(dá)到了為車輛提供更優(yōu)質(zhì)服務(wù)的目的。

本文主要對(duì)服務(wù)器之間的信道質(zhì)量和緩存策略進(jìn)行使用，完成了對(duì)服務(wù)質(zhì)量、車輛能量消耗和任務(wù)卸載時(shí)延的優(yōu)化，但沒(méi)有考慮車輛在任務(wù)傳輸時(shí)出現(xiàn)跨區(qū)域的情況。之后的工作將會(huì)在更復(fù)雜的交通場(chǎng)景下對(duì)車輛跨區(qū)域移動(dòng)問(wèn)題設(shè)計(jì)相關(guān)策略，以期更符合實(shí)際情況。