寧兆龍，張凱源，王小潔，郭磊

（1.重慶郵電大學(xué)通信與信息工程學(xué)院，重慶 400065；2.大連理工大學(xué)軟件學(xué)院，遼寧 大連 116620）

1 引言

隨著5G 時(shí)代的到來和互聯(lián)網(wǎng)設(shè)備的普及，萬(wàn)物互聯(lián)的概念逐漸走進(jìn)人們的生活，這推動(dòng)了大量時(shí)延敏感型的移動(dòng)應(yīng)用，如增強(qiáng)現(xiàn)實(shí)、實(shí)時(shí)導(dǎo)航以及自動(dòng)駕駛等[1-2]。雖然云技術(shù)逐漸成熟，但是隨著移動(dòng)設(shè)備的指數(shù)性增長(zhǎng)，單純依靠中央云服務(wù)器來控制廣域網(wǎng)存在時(shí)延難以保證的瓶頸[3]，從而難以保證時(shí)延敏感型應(yīng)用的服務(wù)質(zhì)量。因此，移動(dòng)邊緣計(jì)算應(yīng)運(yùn)而生，成為目前解決上述問題的一種可靠方案。移動(dòng)邊緣計(jì)算將計(jì)算資源和存儲(chǔ)資源以分布式的方式部署在距離用戶層更近的邊緣節(jié)點(diǎn)上，使這些邊緣節(jié)點(diǎn)就近處理其覆蓋區(qū)域內(nèi)的相關(guān)業(yè)務(wù)，從而減輕回程鏈路的傳輸壓力，并節(jié)約相應(yīng)的服務(wù)響應(yīng)時(shí)間。相對(duì)于中央云服務(wù)器的可擴(kuò)展性，輕量化的邊緣服務(wù)器存在資源容量受限和資源利用不均等問題[4-5]。尤其是隨著移動(dòng)應(yīng)用的多樣性增強(qiáng)，其所需的資源也具有很強(qiáng)的異質(zhì)性，這導(dǎo)致資源利用率低的問題日益凸顯。

人工智能和機(jī)器學(xué)習(xí)技術(shù)的不斷發(fā)展，以及其在多個(gè)領(lǐng)域的成功應(yīng)用，使其正成為解決移動(dòng)邊緣計(jì)算瓶頸問題的關(guān)鍵技術(shù)[6-7]。和傳統(tǒng)技術(shù)相比，人工智能技術(shù)對(duì)于環(huán)境的動(dòng)態(tài)變化擁有更強(qiáng)大的感知能力。作為其重要分支，深度強(qiáng)化學(xué)習(xí)在資源分配方面已經(jīng)得到一定的應(yīng)用，文獻(xiàn)[8-12]都表明基于強(qiáng)化學(xué)習(xí)的車聯(lián)網(wǎng)資源分配解決方案具有較好的準(zhǔn)確性和穩(wěn)健性。隨著用戶需求的動(dòng)態(tài)變化以及多方主體（設(shè)備節(jié)點(diǎn)、邊緣節(jié)點(diǎn)和云服務(wù)器）的參與，車聯(lián)網(wǎng)系統(tǒng)需要一種效率高、均衡性強(qiáng)的任務(wù)調(diào)度和資源分配方法。同時(shí)，由于邊緣節(jié)點(diǎn)的資源有限，需要輕量化、分布式的機(jī)器學(xué)習(xí)技術(shù)與其進(jìn)行適配，從而完成高效的學(xué)習(xí)過程。

車聯(lián)網(wǎng)作為萬(wàn)物互聯(lián)時(shí)代的重要一環(huán)，由于車輛的高移動(dòng)特性和車輛應(yīng)用需求的時(shí)變性，車輛應(yīng)用的處理存在著更突出的難度[13]。為了更好地服務(wù)車輛用戶和建設(shè)智慧城市，需要部署大量裝配邊緣服務(wù)器的路側(cè)單元（RSU,road side unit）來更好地處理其覆蓋區(qū)域內(nèi)的車輛應(yīng)用。因此，車輛、RSU和云服務(wù)器構(gòu)成了常見的三層車聯(lián)網(wǎng)框架[14]。然而實(shí)際情況下城市中車流分布通常是不均勻的，這導(dǎo)致一些RSU 沒有足夠的資源緩存車輛應(yīng)用所需的服務(wù)，從而需要將計(jì)算任務(wù)卸載到云服務(wù)器；另一些RSU 還有很多剩余的緩存空間沒有得到利用，這就導(dǎo)致車聯(lián)網(wǎng)系統(tǒng)的整體時(shí)延增加[15]。因此，為了充分利用車聯(lián)網(wǎng)中的緩存和計(jì)算資源，需要網(wǎng)絡(luò)運(yùn)營(yíng)商挖掘RSU 之間的合作能力，從而提升車聯(lián)網(wǎng)的服務(wù)效率。

車聯(lián)網(wǎng)中的計(jì)算卸載和服務(wù)緩存得到學(xué)術(shù)界和工業(yè)界的廣泛關(guān)注，因?yàn)橥ㄟ^制定相應(yīng)策略可以更好地提升網(wǎng)絡(luò)性能并減少能耗[16-17]。文獻(xiàn)[16]提出一種多時(shí)間尺度的強(qiáng)化學(xué)習(xí)框架來進(jìn)行緩存和計(jì)算資源的分配來最小化車輛應(yīng)用的服務(wù)時(shí)延。文獻(xiàn)[18]考慮了用戶的移動(dòng)性和網(wǎng)絡(luò)連通性來進(jìn)行內(nèi)容緩存，從而能夠縮短用戶對(duì)內(nèi)容的獲取時(shí)間。文獻(xiàn)[13]在能耗限制的情況下，通過計(jì)算卸載的方式滿足了所有基站的能耗約束。很多研究關(guān)注車聯(lián)網(wǎng)中的合作機(jī)制，文獻(xiàn)[19]中，當(dāng)車聯(lián)網(wǎng)需要處理計(jì)算密集型任務(wù)時(shí)，多個(gè)邊緣服務(wù)器會(huì)共同合作處理相關(guān)應(yīng)用。文獻(xiàn)[20]研究多接入車聯(lián)網(wǎng)，將資源豐富的車輛與云服務(wù)器相結(jié)合，構(gòu)建協(xié)同計(jì)算架構(gòu)。也有很多相關(guān)研究利用車輛用戶的屬性，比如社會(huì)信任、位置區(qū)域等構(gòu)建相應(yīng)的車輛應(yīng)用處理集群[5,14]。然而，這些研究大多集中在用戶與服務(wù)器、用戶與用戶間的合作，缺少對(duì)于邊緣節(jié)點(diǎn)之間合作的研究來提升車聯(lián)網(wǎng)的整體服務(wù)性能。

本文考慮了車聯(lián)網(wǎng)中RSU 之間的合作來解決車輛應(yīng)用處理過程中的服務(wù)緩存和任務(wù)調(diào)度問題。解決這一問題存在如下幾個(gè)挑戰(zhàn)：1) 車輛服務(wù)緩存和任務(wù)調(diào)度具有耦合性，車輛服務(wù)緩存決定任務(wù)調(diào)度的決策空間，任務(wù)調(diào)度的結(jié)果反映服務(wù)緩存的表現(xiàn)；2) 任務(wù)計(jì)算和傳輸?shù)臋?quán)衡，RSU 間合作會(huì)減少任務(wù)的計(jì)算時(shí)間，從而增加系統(tǒng)內(nèi)的傳輸時(shí)間，如何在兩者之間進(jìn)行權(quán)衡得到最優(yōu)解也是一個(gè)挑戰(zhàn)；3) RSU 行為平衡，即RSU 間合作能夠降低系統(tǒng)時(shí)延，但求解過程中需避免陷入每個(gè)RSU 的局部最優(yōu)，而是求解全局最優(yōu)策略。

本文主要的研究工作如下。

1) 本文構(gòu)建了多邊合作的車聯(lián)網(wǎng)服務(wù)模型，它聯(lián)合了任務(wù)緩存和邊緣任務(wù)調(diào)度問題，在可用資源約束的情況下，最小化系統(tǒng)時(shí)延。本文將車聯(lián)網(wǎng)服務(wù)問題建模成一個(gè)混合整數(shù)非線性規(guī)劃問題，并證明求解該問題需要非多項(xiàng)式的計(jì)算復(fù)雜度。

2) 本文提出了一種雙層的多RSU 協(xié)同緩存框架求解上述問題，它采用多智能體元強(qiáng)化學(xué)習(xí)框架為RSU 緩存車輛應(yīng)用提供所需服務(wù)。每一個(gè)RSU作為一個(gè)本地智能體計(jì)算其對(duì)應(yīng)狀態(tài)下的緩存決策，云服務(wù)器作為元智能體，采用長(zhǎng)短期記憶（LSTM,long short-term memory）結(jié)構(gòu)的神經(jīng)網(wǎng)絡(luò)來平衡本地智能體的決策，并維護(hù)自己的狀態(tài)信息來進(jìn)行更快的策略學(xué)習(xí)。

3) 在緩存策略確定的情況下，本文提出一種自適應(yīng)的RSU 協(xié)同卸載算法，它采用拉格朗日乘子法來求解最佳協(xié)同卸載策略。本文通過二分迭代搜索的思想搜索最優(yōu)拉格朗日乘子，從而調(diào)度系統(tǒng)中每一個(gè)RSU 的計(jì)算任務(wù)，實(shí)現(xiàn)系統(tǒng)中所有RSU 的工作量負(fù)載均衡。

4) 本文采用杭州交通流數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，結(jié)果表明本文提出的算法具有良好的效能和實(shí)用性。與其他3 種基準(zhǔn)算法相比，本文提出的算法能夠獲得更低的系統(tǒng)時(shí)延，并且能在大規(guī)模任務(wù)流下?lián)碛邢鄬?duì)穩(wěn)定的表現(xiàn)。

2 系統(tǒng)模型

本文構(gòu)建的多邊車聯(lián)網(wǎng)服務(wù)系統(tǒng)由N個(gè)RSU和一個(gè)提供服務(wù)的云服務(wù)器組成，如圖1 所示。

圖1 多邊車聯(lián)網(wǎng)服務(wù)系統(tǒng)模型

RSU 分布在城市中的不同區(qū)域，并配置邊緣服務(wù)器為其相應(yīng)區(qū)域內(nèi)的車輛提供計(jì)算服務(wù)，不同的RSU 之間通過局域網(wǎng)連接，且具有計(jì)算功能和服務(wù)緩存功能。車輛用戶會(huì)和其鄰近RSU 通過無線通信的方式，將計(jì)算任務(wù)上傳到對(duì)應(yīng)的邊緣服務(wù)器上，考慮它們之間的連接采用正交頻分復(fù)用技術(shù)，因此多個(gè)車輛可以在不考慮干擾的情況下和同一個(gè)RSU 通信。為了完成不同類別的車輛應(yīng)用，系統(tǒng)需要從服務(wù)商處下載不同的服務(wù)，例如視頻轉(zhuǎn)碼服務(wù)和障礙物識(shí)別服務(wù)等，設(shè) S={1,2,…,S}表示系統(tǒng)提供的服務(wù)集合，且緩存服務(wù)所需的存儲(chǔ)空間為ps，F(xiàn)n和Cn分別表示RSUn擁有的計(jì)算能力和緩存能力，M={1,2,…,M}和 N={1,2,…,N}分別表示車輛用戶和RSU的集合。假設(shè)RSUn接收車輛應(yīng)用任務(wù)是一個(gè)泊松過程[20]，且任務(wù)接收速率為，處理一個(gè)任務(wù)所需的計(jì)算資源（CPU 周期數(shù)）服從期望為h的指數(shù)分布。本文主要變量及其含義如表1所示。

表1 主要變量及其含義

2.1 服務(wù)緩存模型

由于車輛資源有限，并且車輛應(yīng)用對(duì)于處理時(shí)延具有嚴(yán)格要求，因此需要通過計(jì)算卸載的方式上傳到RSU 進(jìn)行實(shí)時(shí)處理。此外，為了處理車輛任務(wù)，RSU 需要從中央云服務(wù)器上緩存任務(wù)所需的服務(wù)；否則，RSU 需要將任務(wù)上傳到云服務(wù)器上進(jìn)行處理。中央云服務(wù)器擁有充足的計(jì)算能力和緩存能力，因此，如果在云服務(wù)器上處理任務(wù)，時(shí)延主要由從RSU 上傳到云端的傳輸時(shí)延Tcloud造成。設(shè)表示服務(wù)的緩存策略，表示RSUn的緩存策略。由于RSU 的緩存能力有限，因此對(duì)于每一個(gè)RSU，不等式成立。同時(shí)，由于同一個(gè)服務(wù)可能緩存在多個(gè)RSU 上，不同的RSU 處理應(yīng)用所需的服務(wù)可能緩存在其他RSU 上，因此，系統(tǒng)需要根據(jù)服務(wù)緩存情況進(jìn)行協(xié)同卸載，從而更好地利用系統(tǒng)中的空閑資源。

2.2 任務(wù)計(jì)算模型

在協(xié)同卸載過程中，本文假設(shè)計(jì)算任務(wù)在服務(wù)器間只能卸載一次，即如果計(jì)算任務(wù)從RSUi卸載到RSUj，那么任務(wù)將在RSUj上的服務(wù)器上執(zhí)行，而不會(huì)再卸載到其他RSU。設(shè)表示系統(tǒng)的協(xié)同卸載策略，其中表示t時(shí)刻由RSUi卸載到RSUj的計(jì)算任務(wù)數(shù)量，表示RSUi自身處理的任務(wù)數(shù)量，則RSUi在t時(shí)刻處理的任務(wù)數(shù)量可以表示為。RSU 接收任務(wù)的過程是一個(gè)泊松過程，本文采用M/M/1 排隊(duì)系統(tǒng)來為任務(wù)處理建模[21]，車聯(lián)網(wǎng)系統(tǒng)的計(jì)算時(shí)延可以表示為

其中，μi=Fi/h。為了滿足任務(wù)隊(duì)列處理的穩(wěn)定性，≤μi需要得到滿足以確保每一個(gè)RSU 的服務(wù)性能。

由于網(wǎng)絡(luò)帶寬有限，協(xié)同卸載會(huì)導(dǎo)致額外的擁塞時(shí)延。系統(tǒng)的擁塞時(shí)延由網(wǎng)絡(luò)中的全部任務(wù)數(shù)量決定，系統(tǒng)中的總?cè)蝿?wù)數(shù)量為，其中=表示RSUi卸載到其他RSU 的任務(wù)數(shù)量。根據(jù)M/M/1 排隊(duì)模型相關(guān)理論[18]，系統(tǒng)的擁塞時(shí)延為

其中，τ表示在帶寬充足情況下通過局域網(wǎng)傳輸一單位計(jì)算任務(wù)的時(shí)延。

2.3 問題描述

綜上所述，系統(tǒng)時(shí)延主要由3 個(gè)部分組成，分別是計(jì)算時(shí)延、擁塞時(shí)延和（從RSU 上傳到中央云服務(wù)器的）傳輸時(shí)延。系統(tǒng)時(shí)延sT為

其中，wos≥0表示系統(tǒng)中需要服務(wù)s且需要上傳到云服務(wù)器上處理的任務(wù)數(shù)量。

本文聯(lián)合考慮服務(wù)緩存策略和服務(wù)器間的協(xié)同卸載策略，目標(biāo)是最小化車輛任務(wù)的處理時(shí)延，得到如下優(yōu)化問題。

其中，約束C1 保證每個(gè)RSU 緩存的服務(wù)不能超過其緩存能力；約束C2 保證每個(gè)RSU 協(xié)同卸載的任務(wù)數(shù)量不能超過其接受的車輛任務(wù)數(shù)量；約束C3保證每個(gè)RSU 處理的任務(wù)數(shù)量不超過其計(jì)算能力。

定理1優(yōu)化問題P1是一個(gè)混合整數(shù)非線性規(guī)劃，求解其需要非多項(xiàng)式的計(jì)算復(fù)雜度。

證明效用函數(shù)凸凹性

通過2 種簡(jiǎn)化情況來分析優(yōu)化問題P1 的計(jì)算復(fù)雜度。

1) RSU 不進(jìn)行協(xié)同卸載。當(dāng)RSU 不進(jìn)行協(xié)同卸載時(shí)，不同服務(wù)所對(duì)應(yīng)的計(jì)算任務(wù)只能由接收任務(wù)的RSU 進(jìn)行本地計(jì)算或者上傳到云服務(wù)器上。因此，系統(tǒng)時(shí)延不僅由RSU 的計(jì)算能力決定，也高度依賴于RSU 的服務(wù)緩存能力。這時(shí)，優(yōu)化問題P1 可以轉(zhuǎn)化為服務(wù)緩存問題和任務(wù)流輸出問題，類似于文獻(xiàn)[13]。文獻(xiàn)[13]已經(jīng)證明這個(gè)問題是一個(gè)混合整數(shù)非線性規(guī)劃問題，并且擁有非多項(xiàng)式的計(jì)算復(fù)雜度。

2) 所有計(jì)算任務(wù)需要同一種服務(wù)。當(dāng)所有計(jì)算任務(wù)需要同一種服務(wù)時(shí)，在計(jì)算資源充足的情況下，服務(wù)會(huì)被緩存在任一個(gè)緩存空間充足的RSU。因此，該種情況可以被看作一個(gè)協(xié)同卸載問題，即在計(jì)算資源約束的情況下，進(jìn)行計(jì)算任務(wù)的分配，類似于文獻(xiàn)[18]。文獻(xiàn)[18]已經(jīng)證明求解這一問題擁有非多項(xiàng)式的計(jì)算復(fù)雜度。

通過上述分析，2 種簡(jiǎn)化情況都具有非多項(xiàng)式的計(jì)算復(fù)雜度。因此，求解本文的優(yōu)化問題P1 也具有非多項(xiàng)式的計(jì)算復(fù)雜度。證畢。

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

由于求解優(yōu)化問題P1 具有非多項(xiàng)式的計(jì)算復(fù)雜度，本文提出一種雙層的多RSU 協(xié)同緩存算法（MPO,mutli-RSU service caching and peer offloading algorithm），外層采用多智能體元強(qiáng)化學(xué)習(xí)框架來為RSU 緩存車輛應(yīng)用所需的服務(wù)；內(nèi)層在緩存策略確定的情況下，在緩存同一種服務(wù)的RSU 間進(jìn)行協(xié)同卸載，本文提出一種自動(dòng)任務(wù)適應(yīng)算法來求解系統(tǒng)的協(xié)同卸載策略。算法流程如圖2 所示。

圖2 算法流程

3.1 基于多智能體學(xué)習(xí)的緩存分配策略

本文提出一種多智能體元策略的強(qiáng)化學(xué)習(xí)（MAMRL,multi-agent meta reinforcement learning）框架進(jìn)行RSU 的緩存分配，算法架構(gòu)如圖3 所示。

圖3 多智能體元策略的強(qiáng)化學(xué)習(xí)框架

和傳統(tǒng)的強(qiáng)化學(xué)習(xí)相比，MAMRL 框架包含2 種智能體：一種是本地智能體，它配置在每一個(gè)RSU上，根據(jù)任務(wù)量和RSU 上的可用資源并利用強(qiáng)化學(xué)習(xí)算法進(jìn)行自身緩存資源的分配；另一種是元智能體，它配置在云服務(wù)器上，根據(jù)每一個(gè)本地智能體學(xué)習(xí)到的信息和任務(wù)量的信息，利用LSTM 進(jìn)行全局緩存資源分配。MAMRL 減輕了因任務(wù)產(chǎn)生和資源需求帶來的維度災(zāi)難，同時(shí)減少了RSU 和云服務(wù)器之間的消息傳遞（本地智能體只需向元智能體上傳其處理過的信息而不是全部信息），從而提供一個(gè)計(jì)算和通信復(fù)雜度更低的緩存分配方案。

其中，γ∈(0,1)為折扣因子。在狀態(tài)sti下采取動(dòng)作定義為一個(gè)策略πθi，它是由參數(shù)θi決定的。策略πθi決定了狀態(tài)轉(zhuǎn)移函數(shù)Γ:S ti×Ati?St′i，以及相應(yīng)的獎(jiǎng)勵(lì)值函數(shù)ri(s ti,a ti):S ti×Ati?R。因此，在給定狀態(tài)sti下，策略的狀態(tài)值函數(shù)可以表示為

狀態(tài)值函數(shù)可作為評(píng)論家的角色來評(píng)判每一個(gè)動(dòng)作在該狀態(tài)下的表現(xiàn)。因此，對(duì)于狀態(tài)sti下的最佳策略(ati|sti)，可以由該狀態(tài)的值函數(shù)最大值確定，即最大的狀態(tài)值函數(shù)可以獲得其對(duì)應(yīng)的最佳策略，最優(yōu)值函數(shù)為

通過式(7)可以選擇出每一個(gè)決策智能體i的最佳策略。采用時(shí)序差分（TD,temporal difference）法求解最優(yōu)值函數(shù)和最優(yōu)策略，采取策略iθπ的優(yōu)勢(shì)函數(shù)（TD 誤差）定義為

其策略梯度為

通過式(9)可以將網(wǎng)絡(luò)中每一個(gè)RSU 的緩存決策離散化求解。在所有狀態(tài)信息已知的情況下，本文可以采用集中式的解決策略，它的時(shí)間復(fù)雜度為O(Si Ai|N|2T)，這需要消耗大量的計(jì)算資源。同時(shí)，由于集中式的解決策略忽略了其他智能體的決策，導(dǎo)致強(qiáng)化學(xué)習(xí)過程中的探索和開發(fā)出現(xiàn)不平衡的現(xiàn)象，因此本文提出一種元策略的強(qiáng)化學(xué)習(xí)框架來解決上述困難。

2) 元策略強(qiáng)化學(xué)習(xí)模型

元智能體由LSTM 結(jié)構(gòu)的神經(jīng)網(wǎng)絡(luò)組成，設(shè)它的網(wǎng)絡(luò)參數(shù)為φ，且由4 個(gè)門層來計(jì)算出下一個(gè)狀態(tài)st'i的最優(yōu)決策和其對(duì)應(yīng)的優(yōu)勢(shì)函數(shù)，4 個(gè)門層分別為遺忘門Ft'、輸入門It'、單元狀態(tài)層和輸出層Zt'。元智能體的具體實(shí)現(xiàn)為

其中，遺忘門Ft'負(fù)責(zé)確定哪些信息需要拋除；輸入門It'負(fù)責(zé)確定哪些信息需要更新；單元狀態(tài)層使用tanh(·) 函數(shù)產(chǎn)生新的候選值向量，并通過公式更新單元狀態(tài)層；輸出層Zt'決定哪些信息輸出，通過公式計(jì)算單元輸出，并將最終的輸出利用softmax 函數(shù)輸出最佳策略。因此，元智能體的損失函數(shù)是由本地智能體的分布所決定的，其損失函數(shù)的期望可以表示為

因此，MAMRL 框架將元智能體的學(xué)習(xí)參數(shù)傳遞給本地智能體，以便每個(gè)本地智能體更新自身的學(xué)習(xí)參數(shù)來計(jì)算出最優(yōu)的緩存分配策略。其參數(shù)更新式為

MAMRL 框架可以理解成一個(gè)多參與人（N-player）的馬爾可夫博弈模型。根據(jù)當(dāng)前對(duì)多人馬爾可夫博弈模型的研究[22]，MAMRL 模型至少存在一個(gè)納什均衡點(diǎn)來保證最佳的緩存分配策略。因此，對(duì)于MAMRL 模型求解的最優(yōu)性，有命題1 成立。

命題1對(duì)于RSUi，其最佳的緩存分配策略是一個(gè)納什均衡點(diǎn)，且其納什均衡值為。

證明對(duì)于RSUi而言，是綜合考慮所有RSU 動(dòng)作后產(chǎn)生的納什均衡的最優(yōu)策略。因此，BSi無法采取更優(yōu)的策略來提升，則對(duì)于式(10)，有如下不等式成立

通過上述不等式可知，MAMRL 模型中的元智能體Mt'(Ot';φ)能夠在RSUi采取策略時(shí)達(dá)到納什均衡，且RSUi的最優(yōu)值為

因此，最優(yōu)策略是緩存分配問題的一個(gè)納什均衡點(diǎn)。證畢。

對(duì)于MAMRL 模型的收斂性，有命題2 成立。

命題2對(duì)于式(10)的梯度估計(jì)，可以建立估計(jì)值θiL(θi)和真實(shí)值?θiL(θi)之間的關(guān)系為

證明對(duì)于RSUi在時(shí)刻t采取動(dòng)作ati的概率可以表示為

考慮單個(gè)狀態(tài)的情況下，策略梯度的估計(jì)量可表示為

因此，RSUi的期望獎(jiǎng)勵(lì)可以表示為

上式說明，在求解過程中，梯度步長(zhǎng)朝著正確的方向移動(dòng)，且隨著RSU 數(shù)量的增加而呈指數(shù)級(jí)下降。證畢。

MAMRL算法的偽代碼如算法1和算法2所示，其中算法1 為本地智能體訓(xùn)練過程，算法2 為元智能體訓(xùn)練過程。

算法1本地智能體訓(xùn)練

算法2元智能體訓(xùn)練

3.2 RSU 協(xié)同計(jì)算卸載算法

當(dāng)所有RSU 的緩存策略確定后，優(yōu)化問題P1將轉(zhuǎn)換為車輛任務(wù)在緩存同一服務(wù)的RSU 之間進(jìn)行協(xié)同計(jì)算卸載的子問題P2

將式(1)～式(3)代入優(yōu)化問題的目標(biāo)函數(shù)中，可以得到

變量和 是2 個(gè)獨(dú)立變量，根據(jù)上文定義可知，它們都是由RSU 協(xié)同計(jì)算卸載策略β決定的，其定義和關(guān)系見2.2 節(jié)，因此可以通過求解式(14)來確定最優(yōu)協(xié)同計(jì)算卸載策略。對(duì)于每一個(gè)緩存服務(wù)s，它與其他的緩存服務(wù)之間是獨(dú)立的。因此，在問題求解過程中，下文以服務(wù)s為例，對(duì)于子問題P2，本文采用一種迭代的思路搜尋解空間中滿足KKT 條件的結(jié)果作為優(yōu)化問題的解。在RSU 協(xié)同計(jì)算卸載過程中，對(duì)于每一個(gè)RSU 都有工作量負(fù)載均衡等式成立，其中，Ii表示RSUi的接收任務(wù)量，Oi表示RSUi的輸出任務(wù)量。根據(jù)定義，有成立。將上述等式代入優(yōu)化問題，可將優(yōu)化問題P2 轉(zhuǎn)化為關(guān)于變量I和O的優(yōu)化問題P3

為了求解上述優(yōu)化問題，本文首先將RSU 處理計(jì)算任務(wù)分為3 種模式：接收模式、平衡模式、卸載模式。接收模式表示RSU 接收來自其他RSU的計(jì)算任務(wù)；平衡模式表示RSU 不接收其他RSU的任務(wù)也不發(fā)送計(jì)算任務(wù)給其他RSU；卸載模式表示RSU 發(fā)送自身的計(jì)算任務(wù)給其他RSU。RSU 在處理計(jì)算任務(wù)時(shí)，只能選擇一種模式。同時(shí)，本文定義2 個(gè)輔助函數(shù)來進(jìn)行優(yōu)化問題求解，一是邊界計(jì)算時(shí)延函數(shù)

它表示當(dāng)RSU 處理任務(wù)的計(jì)算時(shí)延的邊界值；二是邊界網(wǎng)絡(luò)擁塞時(shí)延

定理2RSU 在t時(shí)刻的任務(wù)處理模式和最優(yōu)協(xié)同計(jì)算卸載策略如下所示。

其中，λt*和α是式(17)的解，λt*表示最優(yōu)網(wǎng)絡(luò)擁塞時(shí)延，α表示拉格朗日乘子，R和 F 分別表示網(wǎng)絡(luò)中處于接收模式和卸載模式的RSU 集合。

由于直接通過求導(dǎo)來求解α存在較大困難，因此本文采用一種二分迭代搜索的思路來通過工作量負(fù)載等式尋找最優(yōu)解。在每一次迭代中，首先通過初始參數(shù)α確定處于接收模式的RSU 以及其接收的任務(wù)量λR。然后，令λ=λR來確定網(wǎng)絡(luò)中處于平衡模式和卸載模式的RSU，并計(jì)算卸載的任務(wù)量λF。如果λ R=λF，此時(shí)的α為最優(yōu)解；否則，算法更新參數(shù)α并進(jìn)入下一輪迭代。求解算法流程如算法3 所示。

算法3二分迭代協(xié)同計(jì)算卸載算法

輸入RSU 接受任務(wù)量,i∈N,t∈T，RSU服務(wù)速率μi,i∈N，網(wǎng)絡(luò)通信時(shí)間τ

輸出

4 實(shí)驗(yàn)結(jié)果和分析

本文利用杭州真實(shí)的交通流數(shù)據(jù)模擬任務(wù)的產(chǎn)生，驗(yàn)證本文提出的車聯(lián)網(wǎng)系統(tǒng)的有效性。系統(tǒng)中由一個(gè)云服務(wù)器和9 個(gè)RSU 組成（如圖4 所示），每一個(gè)RSU 的覆蓋區(qū)域?yàn)?00 m×200 m，且為車輛提供8 種類型不同的服務(wù)。為了適應(yīng)不同規(guī)模的任務(wù)量，RSU 布置在杭州市中心如圖4 所示的9 個(gè)十字路口，且每一個(gè)車輛產(chǎn)生任務(wù)服從速率為[0,4]任務(wù)/2 分鐘的泊松分布。其他參數(shù)設(shè)定如表2 所示。

圖4 車聯(lián)網(wǎng)系統(tǒng)布置說明

表2 參數(shù)設(shè)定

本文與3 種基準(zhǔn)算法進(jìn)行比較。1) 非協(xié)作卸載算法：RSU 完成緩存分配后，只有RSU 本地處理或上傳到云服務(wù)器處理2 種情況。2) 單智能體緩存算法：采用單智能體強(qiáng)化學(xué)習(xí)進(jìn)行緩存分配，然后采用協(xié)同計(jì)算卸載進(jìn)行計(jì)算任務(wù)分配。3) 貪婪緩存策略：每個(gè)RSU 緩存最流行的服務(wù)，然后計(jì)算任務(wù)將在本地處理或上傳到云服務(wù)器進(jìn)行處理。

4.1 系統(tǒng)表現(xiàn)

圖5 為不同智能體（9 個(gè)本地智能體和一個(gè)元智能體）獲得的獎(jiǎng)勵(lì)值，本文計(jì)算每50 次迭代的平均獎(jiǎng)勵(lì)值。在MAMRL 框架中，所有的智能體經(jīng)過1 000 輪迭代都會(huì)得到一個(gè)收斂的獎(jiǎng)勵(lì)值，其中，元智能體擁有最高的獎(jiǎng)勵(lì)值（大約為90），所有的本地智能體（RSU）在收斂時(shí)大約為80 到85，只有一個(gè)RSU 6 收斂時(shí)獎(jiǎng)勵(lì)值在70 左右。不同RSU 上的獎(jiǎng)勵(lì)值變化是由RSU 上處理任務(wù)的不同和分配資源的不同所導(dǎo)致的，同時(shí)也由強(qiáng)化學(xué)習(xí)中各個(gè)本地智能體求解資源分配方案過程中的探索和利用權(quán)衡所決定。

圖5 多智能體元強(qiáng)化學(xué)習(xí)中不同智能體的獎(jiǎng)勵(lì)值

圖6為本文提出的緩存分配策略在不同探索衰減下的系統(tǒng)表現(xiàn)。探索率表示強(qiáng)化學(xué)習(xí)過程中對(duì)于動(dòng)作空間的探索概率，從而在探索和利用之間進(jìn)行權(quán)衡搜索到最優(yōu)的緩存策略。初始情況下，探索率大可以快速探索動(dòng)作空間中的優(yōu)秀策略，探索率逐漸衰減可以平衡動(dòng)作選擇過程中的探索利用效率，從而使智能體逐漸搜索到最佳策略（動(dòng)作）。較大的探索衰減強(qiáng)調(diào)動(dòng)作選取中的探索過程，可以獲得更快的收斂速度，但是可能導(dǎo)致智能體對(duì)于動(dòng)作空間探索不夠完全；較小的探索衰減則強(qiáng)調(diào)動(dòng)作選取中的利用過程，可能會(huì)獲得更好的收斂結(jié)果，但是不斷減小該值可能會(huì)影響收斂速度。因此在仿真實(shí)驗(yàn)中，本文將探索衰減設(shè)置成不同值來觀察收斂效果，可以看出，當(dāng)探索衰減大于1 0?4時(shí)，1 000 輪迭代內(nèi)可以收斂；當(dāng)探索衰減為0.1 時(shí)，收斂時(shí)的獎(jiǎng)勵(lì)值較低。

圖6 不同探索衰減的收斂結(jié)果

4.2 性能對(duì)比

和其他3 種基準(zhǔn)算法（非合作卸載、單智能體緩存、貪婪緩存）相比，本文提出的多RSU 協(xié)同緩存算法表現(xiàn)最優(yōu)，能夠得到最低的系統(tǒng)時(shí)延。圖7 給出了不同緩存大小下不同算法的網(wǎng)絡(luò)時(shí)延。緩存大小對(duì)于RSU 緩存內(nèi)容的選擇具有重要的影響，緩存大小為0 則表明所有處理任務(wù)的服務(wù)需要從云服器上下載，因此所有的緩存策略失去意義；如果緩存大小超過任務(wù)所需的服務(wù)個(gè)數(shù)，服務(wù)器可以緩存所有的服務(wù)，緩存策略也失去意義。因此，本文只討論緩存大小在區(qū)間內(nèi)不同算法的表現(xiàn)情況。從圖7 中可以看出，隨著緩存大小的增加，所有算法的系統(tǒng)時(shí)延都會(huì)有所下降，但是本文提出的算法相比較其他3 種算法表現(xiàn)更加優(yōu)異；在緩存空間明顯不足時(shí)，本文提出的算法相較其他3 種算法提升更明顯，這說明本文提出的算法能夠更好地應(yīng)對(duì)資源有限情況下的緩存分配問題，即能夠在有限的資源情況下，最小化系統(tǒng)時(shí)延。

圖7 不同緩存空間下系統(tǒng)時(shí)延對(duì)比

圖8 說明了不同緩存大小下不同方法中從RSU輸出到云服務(wù)器處理的任務(wù)大小。當(dāng)RSU 之間無法通過協(xié)同卸載來處理用戶任務(wù)時(shí)需要將任務(wù)傳輸?shù)皆品?wù)器來處理，這一過程需要相對(duì)高的傳輸時(shí)延。因此，輸出到云服務(wù)器的任務(wù)量可以表明不同方法的協(xié)同卸載處理情況。從圖8 中曲線可以看出，隨著RSU 緩存空間的增加，更多的任務(wù)可以在RSU 集群內(nèi)進(jìn)行處理，因此傳輸?shù)皆品?wù)器的任務(wù)數(shù)會(huì)越來越小，相比其他3 種算法，本文提出的算法因?yàn)榫哂袇f(xié)同計(jì)算卸載機(jī)制會(huì)在RSU 之間進(jìn)行處理任務(wù)，而不是直接上傳到云處理器，因此會(huì)大幅減少輸出任務(wù)量；相比單智能體緩存算法，多智能體算法在緩存空間相對(duì)不足的情況下，表現(xiàn)更佳，這說明本文提出的算法在受限資源情況下表現(xiàn)更佳。

圖8 不同緩存空間下輸出任務(wù)情況對(duì)比

圖9 和圖10 分別表明了在用戶產(chǎn)生不同數(shù)量任務(wù)的情況下不同方法的系統(tǒng)時(shí)延和輸出到云服務(wù)器的任務(wù)數(shù)量分布。當(dāng)用戶產(chǎn)生的任務(wù)數(shù)量增加時(shí)，系統(tǒng)的計(jì)算壓力會(huì)增大，導(dǎo)致系統(tǒng)時(shí)延增加，同時(shí)也需要將更多的任務(wù)上傳到云服務(wù)器上進(jìn)行處理。如圖9 所示，用戶產(chǎn)生的任務(wù)越多，所有算法的系統(tǒng)時(shí)延都呈上升趨勢(shì)，其中貪婪算法和非協(xié)作卸載算法上升趨勢(shì)明顯，因?yàn)樵诰彺尜Y源有限的情況下，依靠單獨(dú)RSU 來處理對(duì)應(yīng)任務(wù)效率低，只有通過多RSU 合作來處理相應(yīng)任務(wù)才能獲得更低的系統(tǒng)時(shí)延，相對(duì)于單智能體緩存算法，多智能體算法同時(shí)考慮每一個(gè)RSU 的任務(wù)情況，因此能夠獲得更低的系統(tǒng)時(shí)延。圖10 表明用戶產(chǎn)生任務(wù)的增加導(dǎo)致更多任務(wù)需要上傳到云服務(wù)器處理。從圖10 可以看出，用戶任務(wù)在3 到6 時(shí)增長(zhǎng)趨勢(shì)較緩慢，而當(dāng)用戶任務(wù)繼續(xù)增加后，由于RSU緩存空間有限，所有算法都需要將大量的任務(wù)上傳到云服務(wù)器，因此輸出任務(wù)數(shù)量增長(zhǎng)趨勢(shì)會(huì)更加明顯。

圖9 不同任務(wù)數(shù)下系統(tǒng)時(shí)延對(duì)比

圖10 不同任務(wù)數(shù)下輸出任務(wù)情況對(duì)比

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

本文在車聯(lián)網(wǎng)邊緣計(jì)算系統(tǒng)中聯(lián)合考慮了用戶任務(wù)緩存和邊緣任務(wù)調(diào)度問題，并將其建模成一個(gè)混合整數(shù)非線性規(guī)劃問題，從而最小化系統(tǒng)時(shí)延。為了降低問題求解的計(jì)算復(fù)雜度，本文提出一種雙層的多RSU 協(xié)同緩存框架將問題進(jìn)行解耦，其中外層采用多智能體元強(qiáng)化學(xué)習(xí)方法，在每個(gè)本地智能體進(jìn)行決策學(xué)習(xí)的同時(shí)，采用LSTM 作為元智能體來平衡本地決策并加速學(xué)習(xí)，從而得到最優(yōu)的RSU 緩存策略；在緩存策略確定后，內(nèi)層采用拉格朗日乘子法求解最佳協(xié)同卸載策略，實(shí)現(xiàn)RSU 間的任務(wù)分配?；诤贾菡鎸?shí)交通數(shù)據(jù)的實(shí)驗(yàn)表明，本文提出的算法具有很好的能效性能，并且能夠在大規(guī)模任務(wù)流下保持網(wǎng)絡(luò)穩(wěn)健性。