面向5G車聯(lián)網(wǎng)場(chǎng)景的移動(dòng)任務(wù)動(dòng)態(tài)卸載策略研究

摘 要：由于車輛自身的高速移動(dòng)性和資源有限性等特征，使得采用傳統(tǒng)通信和計(jì)算手段的車聯(lián)網(wǎng)場(chǎng)景無(wú)法滿足用戶日益增長(zhǎng)的數(shù)據(jù)計(jì)算需求和體驗(yàn)質(zhì)量需求。采用5G和邊緣計(jì)算技術(shù)構(gòu)建的新型車聯(lián)網(wǎng)架構(gòu)可以滿足以上需求，但由于網(wǎng)絡(luò)結(jié)構(gòu)的變化，需設(shè)計(jì)適合新場(chǎng)景下的車輛任務(wù)通信和計(jì)算策略。針對(duì)5G車聯(lián)網(wǎng)場(chǎng)景下的移動(dòng)車輛任務(wù)動(dòng)態(tài)卸載問(wèn)題進(jìn)行研究，提出了對(duì)應(yīng)的動(dòng)態(tài)任務(wù)分配策略和卸載調(diào)度低時(shí)延算法。車輛會(huì)根據(jù)提出的策略和算法將未完成的計(jì)算任務(wù)卸載到相應(yīng)的 MEC 服務(wù)器或車輛上，并且計(jì)算結(jié)果將通過(guò)邊緣服務(wù)器之間的聯(lián)合通信或直接從被選擇接受卸載任務(wù)的附近空閑車輛上直接返回給車主。仿真結(jié)果表明，所提出的策略和算法在優(yōu)化卸載延遲方面具有良好的性能，并提高了用戶體驗(yàn)質(zhì)量。

關(guān)鍵詞：聯(lián)合任務(wù)卸載；動(dòng)態(tài)調(diào)度；車聯(lián)網(wǎng)；移動(dòng)邊緣計(jì)算；5G

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695（2022）11-036-3427-05

doi：10.19734/j.issn.1001-3695.2022.03.0152

Research on dynamic offloading strategy of mobile task for 5G vehicle networks

Zhou Wenwen1，2，Lu Yang1，2，Shi Lei1，2

（1.Intelligent Interconnected Systems Laboratory of Anhui Province，Hefei University of Technology，Hefei 230009，China；2.Engineering Research Center of Safety Critical Industrial Measurement amp; Control Technology for Ministry of Education，Hefei 230009，China）

Abstract：Due to the characteristics of high-speed mobility and limited resources of the vehicle itself，the vehicle networks scenarios using traditional communication and computing methods cannot meet the increasing data computing needs and the quality of experience（QoE） required by users.New vehicle networks scenarios built with 5G and mobile edge computing（MEC） technologies can meet the above requirements，but due to changes in network structure，it is necessary to design vehicle task communication and computing strategies suitable for the new scenarios.This paper studied the dynamic offloading of mobile vehicle tasks in the 5G vehicle networks scenario，and proposed a corresponding dynamic task allocation strategy and a low-latency algorithm for offloading scheduling.The vehicle would offload the unfinished computing tasks to the corresponding MEC server or vehicle according to the proposed strategy and algorithm.And the calculation result would be directly returned to the vehicle owner through the joint communication between the edge servers or directly from the nearby idle vehicle selected to accept the offloading task.Simulation results show that the proposed strategy and algorithm have good performance in optimizing offload latency and improve the quality of user experience.

Key words：joint task offloading；dynamic scheduling；vehicle network；mobile edge computing；5G

基金項(xiàng)目：安徽省科技重大專項(xiàng)資助項(xiàng)目（202003a05020009）

作者簡(jiǎn)介：周雯雯（1997-），女，碩士研究生，主要研究方向?yàn)檫吘売?jì)算、車聯(lián)網(wǎng)任務(wù)卸載；陸陽(yáng)（1967-），男，安徽合肥人，教授，博導(dǎo)，博士，主要研究方向?yàn)槲锫?lián)網(wǎng)、分布式控制技術(shù)和無(wú)線通信網(wǎng)絡(luò)；石雷（1980-），男（通信作者），安徽合肥人，副教授，碩導(dǎo)，博士，主要研究方向?yàn)闊o(wú)線通信網(wǎng)絡(luò)和邊緣計(jì)算（shilei@hfut.edu.cn）.

0 引言

隨著技術(shù)的發(fā)展，車聯(lián)網(wǎng)中的數(shù)據(jù)需求也在日益增加［1，2］。例如，在自動(dòng)駕駛場(chǎng)景中，無(wú)人駕駛車輛可以與其他車輛共享視覺(jué)信息，那么這些車輛對(duì)于道路信息等可能會(huì)作出更好的決策和判斷［3］。很明顯，這個(gè)共享應(yīng)用場(chǎng)景需要大量的數(shù)據(jù)計(jì)算和數(shù)據(jù)通信。然而，車輛本身的計(jì)算資源是有限的，要確保所需的用戶體驗(yàn)質(zhì)量（quality of experience ，QoE）對(duì)它們來(lái)說(shuō)是一個(gè)很嚴(yán)峻的挑戰(zhàn)［4～6］。

幸運(yùn)的是5G和移動(dòng)邊緣計(jì)算（mobile edge computing，MEC）等新興技術(shù)為解決這一難題提供了機(jī)會(huì)［7］。眾所周知，5G擁有著高速度、泛在網(wǎng)和低延遲等鮮明特點(diǎn)［8～10］。但它也有著不容忽視的缺點(diǎn)，即與4G基站相比，5G基站的覆蓋范圍更小（通常只有250 m左右）且布置成本更高［11］。而與邊緣智能相關(guān)的計(jì)算任務(wù)大部分都是計(jì)算密集型的，所以僅僅依靠5G基站完成數(shù)據(jù)通信會(huì)造成車聯(lián)網(wǎng)系統(tǒng)中巨大的成本。這里便要引入MEC技術(shù)，MEC技術(shù)可以使車輛和車輛（vehicle to vehicle，V2V）之間以及車輛和基站（base station，BS）之間進(jìn)行更多的協(xié)調(diào)配合，以便更好地完成計(jì)算任務(wù)［12，13］，并且具有強(qiáng)大計(jì)算和存儲(chǔ)能力的MEC服務(wù)器安裝在車輛網(wǎng)絡(luò)的邊緣，通常與RSU（road side unit）并置［14～16］，這不僅可以大大緩解車輛繁重的計(jì)算需求來(lái)縮減任務(wù)的計(jì)算時(shí)延［17］ ，同樣也能極大地降低成本。

近年來(lái)，有大量的研究工作集中在計(jì)算卸載上，并且在基于MEC的車聯(lián)網(wǎng)絡(luò)中有許多研究成果。文獻(xiàn)［18］提出了一種聯(lián)合優(yōu)化無(wú)線資源分配和計(jì)算資源管理的方案。具體而言，其使用封閉形式推導(dǎo)移動(dòng)設(shè)備和MEC服務(wù)器的最佳CPU周期頻率，并使用高斯賽德?tīng)柕姆椒ǐ@得最佳發(fā)射功率和帶寬分配。文獻(xiàn)［19］研究了具有多用戶和多服務(wù)器的車聯(lián)網(wǎng)絡(luò)架構(gòu)中的任務(wù)卸載問(wèn)題，并將其表述為一個(gè)混合的非線性規(guī)劃問(wèn)題。為了解決該問(wèn)題，將其分為兩個(gè)子問(wèn)題，并提出了一種優(yōu)化算法，該算法聯(lián)合優(yōu)化了MEC服務(wù)器的選擇和任務(wù)的卸載決策。文獻(xiàn)［20］提出了一種動(dòng)態(tài)網(wǎng)絡(luò)條件下的自適應(yīng)卸載算法。對(duì)于文章中討論的卸載中斷問(wèn)題，研究人員提出了各種方法。綜上所述可以看到，已經(jīng)有很多研究車輛網(wǎng)絡(luò)下的任務(wù)卸載的工作，一部分是通過(guò)優(yōu)化資源管理來(lái)控制延遲，另一部分是通過(guò)控制服務(wù)器的選擇來(lái)節(jié)省延遲。然而，在5G網(wǎng)絡(luò)中，很少有考慮在有多種卸載方式可選擇的條件下，通過(guò)研究邊緣服務(wù)器端的任務(wù)分配策略以及車輛與邊緣服務(wù)器之間的聯(lián)合調(diào)度和分配任務(wù)來(lái)縮短延遲。

本文為了向車輛用戶提供低延遲和高可靠性的計(jì)算服務(wù)，一個(gè)主要問(wèn)題是決定何時(shí)何地卸載他們的計(jì)算任務(wù)。在提出的模型中，考慮到車輛的移動(dòng)性、RSU覆蓋范圍的局限性和車輛的本地計(jì)算資源的有限性，另外MEC服務(wù)器上存在任務(wù)等待隊(duì)列，附近可選擇卸載小車上不存在任務(wù)等待隊(duì)列，所以本文共考慮了兩種可卸載方式。根據(jù)這些可變約束，本文提出了兩種有效的車聯(lián)網(wǎng)中的卸載調(diào)度算法。算法1確定何時(shí)將車輛的計(jì)算任務(wù)卸載到MEC服務(wù)器，算法2實(shí)現(xiàn)如何調(diào)度和分配邊緣服務(wù)器，以最大程度地節(jié)省延遲。仿真結(jié)果表明，所提出的算法在節(jié)省卸載時(shí)延和提高QoE上具有良好的性能。

1 系統(tǒng)模型

首先，考慮一條長(zhǎng)度為L(zhǎng)的筆直道路，并且道路的邊緣會(huì)放置RSU，如圖1所示。每個(gè)RSU均配備相對(duì)應(yīng)的MEC服務(wù)器。

假設(shè)整條路可以分成許多緊密相連的部分，道路每個(gè)部分由一個(gè)RSU覆蓋。假設(shè)每輛車都有自己的計(jì)算任務(wù)，如這些任務(wù)可能是一些實(shí)時(shí)監(jiān)控信息的任務(wù)等。假設(shè)每個(gè)任務(wù)可以分為兩部分：第一部分將會(huì)直接在車輛上進(jìn)行處理，第二部分將會(huì)有兩種選擇方式進(jìn)行卸載處理且這兩部分處理過(guò)程是并行的。第一種方式是選擇卸載到RSU上（vehicle to RSU，V2R）進(jìn)行處理。由于假設(shè)在任何時(shí)候，每輛車都將由一個(gè)RSU覆蓋，所以很明顯當(dāng)一輛車有計(jì)算任務(wù)時(shí)，它將首先選擇此RSU來(lái)處理剩余計(jì)算任務(wù)。然而，由于這些車輛不斷移動(dòng)，當(dāng)車輛離開(kāi)RSU的覆蓋范圍時(shí)，可能計(jì)算任務(wù)無(wú)法全部完成，對(duì)于這種情況，通過(guò)RSU之間的配合來(lái)完成此任務(wù)，并通過(guò)下一個(gè)RSU將計(jì)算結(jié)果返回給小車。第二種方式是選擇卸載到附近車輛。對(duì)于被選擇接受卸載任務(wù)的車輛有一定的性能規(guī)定，如果小車選擇第二種卸載方式，便可認(rèn)定為被選擇接受卸載任務(wù)的車輛符合性能要求且自身不存在任務(wù)等待隊(duì)列，即小車剩余計(jì)算任務(wù)將會(huì)直接在這輛被選擇接受卸載任務(wù)的車輛上進(jìn)行計(jì)算，等計(jì)算完畢后結(jié)果直接返回先前車輛。

通過(guò)用si（si∈S，i=1，…，u）來(lái)標(biāo)記整條道路上的每個(gè)RSU，用ci（ci∈C，i=1，…，u）來(lái)標(biāo)記小車以及每輛小車的車速用vi（vi∈V，i=1，…，v）來(lái)標(biāo)記。假設(shè)所有RSU的計(jì)算能力都是相同的，記做frsu，由于不同小車的計(jì)算能力可能不同，所以用fil來(lái)表示不同小車ci的計(jì)算能力，并且被選擇接受卸載任務(wù)的小車計(jì)算能力用fiv2v表示。同時(shí)假定每個(gè)RSU的覆蓋范圍是相同的，記做r。用di（t）表示在時(shí)間t小車ci與RSU之間的距離，所以可以得到小車剩余的行駛距離記做Si，Si可以由式（1）表示。

用tirest表示車輛完成剩余距離所需的時(shí)間，tirest可以表示為

根據(jù)作出的決定，系統(tǒng)中存在兩種場(chǎng)景：

a）場(chǎng)景1：如果tilocal≤tirest，這個(gè)RSU就會(huì)在當(dāng)前RSU范圍內(nèi)返回結(jié)果，如圖2所示。

b）場(chǎng)景2：如果tilocalgt;tirest，這個(gè)RSU會(huì)將計(jì)算結(jié)果傳遞給下一個(gè)RSU，并由下一個(gè)RSU將計(jì)算結(jié)果返回給小車，如圖3所示。

2 問(wèn)題描述

假設(shè)將整個(gè)調(diào)度時(shí)間T等分成n個(gè)時(shí)間片，記做τi（τi∈T，1=1，…，h），在時(shí)間片τk中的每個(gè)任務(wù)用mi，k表示。在整個(gè)調(diào)度時(shí)間里，一個(gè)小車會(huì)產(chǎn)生多個(gè)任務(wù)，但在一個(gè)確定的時(shí)間片τ中，一輛小車最多只能產(chǎn)生一個(gè)任務(wù)。用二維變量x（i，j，k）表示為

x（i，j，k）=1小車j在時(shí)間片k產(chǎn)生了任務(wù)i

0其他情況

任務(wù)mi，k需要計(jì)算的總的數(shù)據(jù)量大小記做Bi。具體來(lái)說(shuō)，用λi表示在本地處理的數(shù)據(jù)量占mi，k的總數(shù)據(jù)量的比例，因此在本地處理的數(shù)據(jù)量為λiBi，需要卸載的數(shù)據(jù)量為（1-λi）Bi。由于本地計(jì)算的過(guò)程與卸載過(guò)程是并行的，且存在兩種卸載選擇方式，所以通過(guò)比較選擇一種更加縮減時(shí)延的方式，即完成任務(wù)mi，k的總時(shí)間可以表示為

其中：tilocal表示任務(wù)在本地需要的計(jì)算時(shí)間；tioffload表示任務(wù)卸載過(guò)程的時(shí)間；tiwait表示任務(wù)在邊緣RSU上的等待時(shí)間；tiV2Rex表示選擇卸載到RSU上的計(jì)算時(shí)間；tiV2Vex表示選擇卸載到小車上的計(jì)算時(shí)間。由于考慮到兩種卸載方式且車輛自身的移動(dòng)性、無(wú)線傳輸能力和計(jì)算能力，一個(gè)完整的計(jì)算任務(wù)的處理時(shí)延包括以上幾個(gè)部分，下面將具體討論它們。

2.1 本地計(jì)算時(shí)延

在本地計(jì)算的數(shù)據(jù)量可以表示為λiBi，所以本地計(jì)算時(shí)延的公式可以表示為

其中：α是由任務(wù)的計(jì)算復(fù)雜度決定的一個(gè)常數(shù)。

2.2 任務(wù)卸載時(shí)延

假設(shè)從車輛到 RSU 的上行鏈路信道是頻率平坦塊衰落瑞利信道。小車ci與RSU之間的路徑損耗建模為d-γi（t），其中γ是一個(gè)常數(shù)，表示為路徑損耗指數(shù)，將N0表示為白高斯噪聲功率，那么上行速率Ri（t）可以表示為

其中：W是上傳信道帶寬；Pi是ci的發(fā)射功率；h為常數(shù)，表示上行信道衰落系數(shù)。由于會(huì)有（1-λi）Bi卸載到RSU，所以卸載時(shí)延可以表示為

其中：β是上行傳輸開(kāi)銷系數(shù)的常數(shù)。

2.3 任務(wù)等待時(shí)延

等待時(shí)延tiwait對(duì)于此次研究來(lái)說(shuō)是一個(gè)比較復(fù)雜的變量。而剩余的卸載任務(wù)可能需要多個(gè)邊緣服務(wù)器，因此通過(guò)表示一個(gè)二進(jìn)制調(diào)度變量yl（i）來(lái)表示任務(wù)mi，k是否在服務(wù)器sl上執(zhí)行，即

yl（i）=1x（i，j，k）=1并且任務(wù)mi，k分配到服務(wù)器sl上執(zhí)行

0其他情況

很顯然可以得到∑ul=1yl（i）=1。對(duì)于等待時(shí)間，首先表示任務(wù)mi，k的到達(dá)時(shí)間tiarrive，可以得到

當(dāng)任務(wù)mi，k在服務(wù)器上執(zhí)行時(shí)，所有在tiarrive之前到達(dá)的任務(wù)mi′，k必須全部完成。這里將用到二維變量zij（mi，k）來(lái)判定任務(wù)的到達(dá)時(shí)間，當(dāng)z1tiarrive（mi′，k）=1表示任務(wù)mi′，k到達(dá)邊緣服務(wù)器的時(shí)間比任務(wù)mi，k要早。另外，對(duì)于在同一時(shí)刻到達(dá)邊緣服務(wù)器的任務(wù)，又引入了另外一個(gè)二維變量z2j（mi，k）來(lái)表示。當(dāng)z2tiarrive（mi′，k）=1表示任務(wù)mi′，k和mi，k在相同時(shí)間片到達(dá)邊緣服務(wù)器。需要注意的是，為了解決滿足z2j（mi，k）任務(wù)的執(zhí)行順序，對(duì)這些任務(wù)采用第一代先服務(wù)（first-generation-first-serving，F(xiàn)GFS）策略。這兩個(gè)二進(jìn)制變量可以表示為

式（8）中主要包含三個(gè)部分：a）所有和任務(wù)mi，k分配到同一個(gè)服務(wù)器的任務(wù)，并且在任務(wù)mi，k之前到達(dá)服務(wù)器的所有任務(wù)在服務(wù)器上的時(shí)間消耗；b）所有和任務(wù)mi，k分配到同一個(gè)服務(wù)器的任務(wù)，和任務(wù)mi，k在同一個(gè)時(shí)間片到達(dá)服務(wù)器的但是比任務(wù)mi，k先產(chǎn)生的所有任務(wù)在服務(wù)器上的時(shí)間消耗；c）系統(tǒng)在任務(wù)mi，k到達(dá)服務(wù)器之前的服務(wù)器運(yùn)行時(shí)間。值得注意的是，tiwait的值需要大于0，tiwait′在服務(wù)器上無(wú)隊(duì)列或者任務(wù)很少的情況會(huì)出現(xiàn)小于0的情況，所以tiwait的表達(dá)應(yīng)該修正為

2.4 邊緣服務(wù)器計(jì)算時(shí)延

本文考慮到兩種卸載方式可以選擇，所以對(duì)于車輛在邊緣服務(wù)器端的任務(wù)處理時(shí)延可分為以下兩種情況討論：

a）選擇卸載到RSU上，則計(jì)算時(shí)延tiV2Rex可以表示為

b）選擇卸載到附近車輛上，則計(jì)算時(shí)延tiV2Vex可以表示為

當(dāng)邊緣服務(wù)器完成計(jì)算后，將計(jì)算結(jié)果發(fā)送回任務(wù)啟動(dòng)車輛。由于計(jì)算結(jié)果數(shù)據(jù)通常很小，從MEC服務(wù)器到車輛的傳輸時(shí)間往往被忽略，所以可以得到系統(tǒng)中小車任務(wù)的總計(jì)算時(shí)延。時(shí)延最小化的問(wèn)題可以表示為

其中：約束條件c1表示問(wèn)題P1受限于上述所有公式；c2和c3表示λi和vi的定義域；c4表示這三個(gè)變量分別是二維變量。通過(guò)求解問(wèn)題P1，可以推導(dǎo)出最優(yōu)卸載率λi。通過(guò)提出的調(diào)度方案獲得的參數(shù)λi決定了小車上的任務(wù)該如何卸載。如果能保證車輛在每個(gè)服務(wù)器中用最短的時(shí)間完成任務(wù)，就可以達(dá)到提升用戶整體體驗(yàn)質(zhì)量的目的。

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

本章首先提出最優(yōu)卸載率選擇（optimal-offloading-ratio-selection，OORS）算法，該算法將會(huì)確定每輛小車的最優(yōu)卸載率是多少，即有多少數(shù)據(jù)量會(huì)在本地執(zhí)行，多少會(huì)被卸載到邊緣服務(wù)器執(zhí)行；接著又提出任務(wù)分配策略（task-allocation-strategy，TTAS）算法，TTAS算法是為了解決邊緣服務(wù)器如何調(diào)度和處理等待任務(wù)。

3.1 最優(yōu)卸載率選擇算法（OORS）

很顯然，問(wèn)題P1不可以被直接求解，所以本節(jié)針對(duì)這個(gè)問(wèn)題將會(huì)提出解決方案。在本文的數(shù)學(xué)模型中，通過(guò)式（5）（6）可以知道d-γi（t）和λi是變量。同時(shí)可以看出di（t）與Ri（t）成反比例關(guān)系，即隨著di（t）的不斷增大，Ri（t）的值在不斷縮小。λ的取值設(shè)置為［0，1］，通過(guò)設(shè)置隨機(jī)函數(shù)對(duì)λ進(jìn)行隨機(jī)取值。當(dāng)λ隨機(jī)等于一個(gè)值時(shí)，便可得到一組數(shù)據(jù)tiV2R和tiV2V，tiV2R表示選擇卸載到邊緣RSU上，tiV2R=tioffload+tiwait+tiV2Rex，tiV2V表示選擇卸載到附近車輛上，tiV2V=tioffload+tiV2Vex。通過(guò)計(jì)算比較，若tiV2Rgt;tiV2V，則選擇卸載到附近車輛上，反之則選擇卸載到邊緣RSU上，再與tilocal比較選擇較大值作為該任務(wù)的完成時(shí)延，具體步驟如算法1所示。

算法1 OORS算法

輸入：λ為車輛的卸載率集合；C為車輛集合；tilocal為本地計(jì)算時(shí)延；tiV2R為邊緣服務(wù)器卸載時(shí)延；tiV2V為選擇卸載到附近車輛上卸載時(shí)延；M為任務(wù)棧。

輸出：系統(tǒng)中每輛小車的最優(yōu)卸載率λi。

過(guò)程：

1 for ci in C do

2 for λi=［0，1］隨機(jī)取值 do

3 計(jì)算tiV2R，tiV2V；

4 if tiV2Rgt;tiV2V

5 選擇卸載到附近車輛，放進(jìn)任務(wù)棧N中；

6 else

7 選擇卸載到邊緣RSU，放進(jìn)任務(wù)棧N中；

8 end if

9 并計(jì)算λ對(duì)應(yīng)的tilocal，由于兩部分任務(wù)并行處理，較大值作為該任務(wù)的計(jì)算時(shí)延；

10 λ隨機(jī)生成20組數(shù)據(jù)，選擇最小的一組數(shù)據(jù)所對(duì)應(yīng)的卸載率λ便是本文要求的相對(duì)最優(yōu)卸載率；

11 end for

12 通過(guò)此類運(yùn)算本文可以得到每輛小車的最優(yōu)卸載率λi，放入集合λ中；

13 end for

3.2 任務(wù)分配策略算法（TTAS）

通過(guò)以上關(guān)于OORS算法的討論可以得到每輛小車的最優(yōu)卸載率，因此本節(jié)便主要討論邊緣服務(wù)器端的任務(wù)分配策略問(wèn)題。數(shù)學(xué)模型中有很多的二維變量，如x（i，j，k）、yl（i）等。所以基于貪心思想，提出了一種求解該問(wèn)題的啟發(fā)式算法，稱之為T(mén)TAS算法。接下來(lái)闡述TTAS算法的主要思想。

假如，在第一個(gè)時(shí)間片第一輛小車產(chǎn)生的第一個(gè)任務(wù)，它可以選擇任何一個(gè)邊緣服務(wù)器進(jìn)行任務(wù)卸載，因?yàn)闊o(wú)論它選擇哪個(gè)服務(wù)器邊緣端的等待時(shí)間都是tiwait=0。類似地，可以計(jì)算后面時(shí)間片的任務(wù)計(jì)算時(shí)間。值得注意的是，后產(chǎn)生的任務(wù)可能比早產(chǎn)生的任務(wù)更早到達(dá)服務(wù)器。但是，如果只是使用先來(lái)先服務(wù)算法思想的話，那么后面生成的任務(wù)應(yīng)該在服務(wù)器上等待，直到前面生成的任務(wù)完成，這對(duì)后產(chǎn)生的任務(wù)是不公平且不合理的。因此，在遇到這種情況時(shí)對(duì)任務(wù)的決策進(jìn)行調(diào)整。

如圖4所示，任務(wù)m6，6在任務(wù)m3，4和m4，5被分配給第一個(gè)服務(wù)器之后，也被分配到了第一個(gè)服務(wù)器上，但由于每個(gè)任務(wù)數(shù)據(jù)量大小不同，即Bi不同，所以存在它比任務(wù)m3，4和m4，5先到達(dá)服務(wù)器的情況。明顯地，任務(wù)m3，4和m4，5的決策是可以被提升的，因?yàn)楫?dāng)這兩個(gè)任務(wù)在確定卸載率和被分配到的服務(wù)器時(shí)，任務(wù)m6，6是沒(méi)有被考慮到的。對(duì)于這種情況，TTAS算法會(huì)為那些有待提升的任務(wù)重新制定它們的策略，以此來(lái)提升整個(gè)系統(tǒng)的表現(xiàn)。任務(wù)m3，4和m4，5會(huì)被從第一個(gè)服務(wù)器的任務(wù)隊(duì)列中移除，然后重新做決策。基于以上想法，可以得到算法2。

算法2 TTAS算法

輸入：Q為邊緣服務(wù)器的任務(wù)隊(duì)列；M為任務(wù)棧。

過(guò)程：

1 while M！=empty do

2 M′←M.pop（）

3 while M′！=1 do

4 for mi，k∈M′ do

5 根據(jù)min Ttotal公式獲取任務(wù)分配的服務(wù)器

6 將任務(wù)放入Q；更新任務(wù)隊(duì)列

7 end for

8 end while

9 for mi，k in Q do

10 if任務(wù)的策略是可改進(jìn)的 then

11 將任務(wù)mi，k加入到Q′中

12 end if

13 end for

14 for mi，k in Q′ do

15 為任務(wù)mi，k重新做決策

16 end for

17 更新隊(duì)列Q

18 end while

返回：M中所有任務(wù)的分割點(diǎn)和分配策略。

根據(jù)TTAS算法，可以總結(jié)為以下三步：

a）初始化。將所有任務(wù)以生成時(shí)間為單位放入任務(wù)棧M。第一個(gè)生成的任務(wù)在棧頂，最后一個(gè)生成的任務(wù)在棧底。

b）獲取任務(wù)策略。取出棧頂M的所有任務(wù)，并計(jì)算它們的最優(yōu)策略。

c）一個(gè)棧中的所有任務(wù)的策略完成后，需要檢查是否有策略可改進(jìn)的任務(wù)，例如如圖所示任務(wù)m3，4和m4，5，并且重復(fù)步驟b）c）直至棧M為空。

4 實(shí)驗(yàn)仿真與結(jié)果

4.1 實(shí)驗(yàn)仿真卸載過(guò)程

在仿真部分，通過(guò)設(shè)置一條筆直的道路，上面有四輛車，路邊有六個(gè)RSU放置在道路邊。小車剩余計(jì)算任務(wù)可以選擇卸載到RSU或者附近車輛上，由于邊緣服務(wù)器端考慮等待時(shí)間，若卸載到小車上則表示直接進(jìn)行計(jì)算處理，不存在等待時(shí)間，所以通過(guò)計(jì)算比較這兩種方式時(shí)延長(zhǎng)短，哪種方式耗時(shí)短則選擇哪種方式。具體卸載選擇過(guò)程如圖5所示。

如圖5所示，在時(shí)間片τ=0時(shí)，通過(guò)計(jì)算比較，小車剩余計(jì)算任務(wù)選擇卸載到RSU上計(jì)算時(shí)延更短，另外tiV2R與t1local計(jì)算并行進(jìn)行，小車1整個(gè)任務(wù)完成時(shí)間為耗時(shí)長(zhǎng)一點(diǎn)的t1V2R。類似地，在時(shí)間片τ=2時(shí)，小車剩余計(jì)算任務(wù)選擇卸載到附近車輛上計(jì)算時(shí)延更短，小車2整個(gè)任務(wù)完成時(shí)間通過(guò)比較t2V2V與t2local，選擇耗時(shí)較長(zhǎng)的t2local；在時(shí)間片τ=4時(shí)，小車3與4同時(shí)產(chǎn)生卸載任務(wù)，通過(guò)計(jì)算比較，小車3選擇將剩余計(jì)算任務(wù)卸載到附近車輛上計(jì)算，小車4選擇將剩余計(jì)算任務(wù)卸載到邊緣RSU上計(jì)算，以上四個(gè)任務(wù)的總完成時(shí)延則表示為最后時(shí)延片小車上面任務(wù)完成時(shí)間，表示為T(mén)total。

4.2 實(shí)驗(yàn)仿真結(jié)果

實(shí)驗(yàn)中設(shè)置帶寬W=5 MB，RSU的計(jì)算能力設(shè)置為fRSU=8×108 cycles/s，附近小車的計(jì)算能力設(shè)置為fiV2V=8×103 cycles/s。其余參數(shù)取值如下：每輛車的數(shù)據(jù)量大小為Bi=（35，45，22，44）Mbit，計(jì)算復(fù)雜度α=40，小車ci到RSU的距離di（t）=4，車輛的計(jì)算能力設(shè)置為fil=（4×107，5×107，7×107，3×107）cycles/s，小車ci的發(fā)射功率Pi=（1.31，1.33，1.32，1.37）W，路徑損耗指數(shù)γ=2，上行信道衰落系數(shù)h=4，白高斯噪聲功率N0=3×10-13，上行傳輸開(kāi)銷系數(shù)的常數(shù)β=1.05。

如圖6和7所示，λ隨機(jī)取值，不同的λ都對(duì)應(yīng)一組任務(wù)計(jì)算數(shù)據(jù)。由圖可知，小車在不同的卸載率下任務(wù)計(jì)算時(shí)延不同，在同一卸載率下小車選擇卸載方式不同對(duì)應(yīng)的任務(wù)計(jì)算完成時(shí)延也是不同的。并且可以看出小車1在λ=0.92時(shí)計(jì)算時(shí)延最短，并且選擇卸載到邊緣服務(wù)器上，小車2在λ=0.11時(shí)計(jì)算時(shí)延最短，選擇卸載到小車上。

圖8和9主要比較多輛小車在不同卸載率下OORS算法與隨機(jī)（random offloading，RO）算法的任務(wù)計(jì)算時(shí)延。由圖可知，四輛小車選擇OORS算法進(jìn)行卸載的計(jì)算時(shí)延對(duì)比選擇RO算法的計(jì)算時(shí)延都要小。可見(jiàn)本文算法在節(jié)省任務(wù)計(jì)算時(shí)延和提高系統(tǒng)資源利用率方面有著一定的效果。

圖10和11主要實(shí)現(xiàn)的是比較在不同帶寬下，通過(guò)only-server、only-vehicle和OORS-algorithm三種卸載方式的計(jì)算時(shí)延來(lái)比較帶寬對(duì)小車任務(wù)計(jì)算時(shí)延的影響。由于不同小車上的任務(wù)量一定，且小車自身計(jì)算能力一定，所以當(dāng)小車將任務(wù)全部在本地執(zhí)行時(shí)，得到的是一個(gè)定值，如圖所示，得到的是一條橫線。同時(shí)，隨著帶寬的不斷增大，可以看出only-server和OORS-algorithm兩種方式的計(jì)算時(shí)延也在不斷降低，但又可注意到兩條折線愈發(fā)靠近，可見(jiàn)上傳信道分配的帶寬越大，邊緣服務(wù)端的任務(wù)等待時(shí)間越短。在實(shí)際生活中，上行信道帶寬的分配都是有限的，當(dāng)帶寬分配并不是很大時(shí)，OORS-algorithm方式下的計(jì)算時(shí)延都要比only-vehicle和only-server兩種方式的計(jì)算時(shí)延低，可見(jiàn)，本文算法和任務(wù)分配策略在減小任務(wù)計(jì)算時(shí)延方面有著顯著效果。

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

本文研究了車聯(lián)網(wǎng)中多輛車在多種方式可選擇卸載下的任務(wù)卸載和計(jì)算問(wèn)題。由于車輛的移動(dòng)性和資源有限性，文章引入了MEC和5G技術(shù)。車輛通過(guò)提出的算法和任務(wù)分配策略將剩余計(jì)算任務(wù)卸載到邊緣RSU或者附近空閑車輛上。當(dāng)小車駛出RSU范圍時(shí)，計(jì)算結(jié)果將通過(guò)RSU范圍內(nèi)對(duì)應(yīng)邊緣服務(wù)器之間的聯(lián)合通信或者附近空閑車輛直接返回給車主。通過(guò)聯(lián)合優(yōu)化選擇決策、卸載率和計(jì)算資源，筆者開(kāi)發(fā)了OORS和TTAS 兩種低復(fù)雜度的算法。仿真結(jié)果表明，系統(tǒng)性能在總卸載時(shí)延和QoE方面得到了顯著提高。對(duì)于未來(lái)的工作，更全面地考慮如何動(dòng)態(tài)卸載任務(wù)或考慮更復(fù)雜的路況進(jìn)行進(jìn)一步的研究。

參考文獻(xiàn)：

［1］Wang Feng，Xu Jie，Wang Xin，et al.Joint offloading and computing optimization in wireless powered mobile-edge computing systems［J］.IEEE Trans on Wireless Communications，2018，17（3）：1784-1797.

［2］Liu Yaqiong，Peng Mugen，Shou Guochu，et al.Towards edge intelligence：multi-access edge computing for 5G and Internet of Things［J］.IEEE Internet of Things Journal，2020，7（8）：6722-6747.

［3］施巍松，孫輝，曹杰，等.邊緣計(jì)算：萬(wàn)物互聯(lián)時(shí)代新型計(jì)算模型［J］.計(jì)算機(jī)研究與發(fā)展，2017，54（5）：907-924.（Shi Weisong，Sun Hui，Cao Jie，et al.Edge computing-an emerging computing model for the Internet of everything era［J］.Journal of Computer Research and Development，2017，54（5）：907-924.）

［4］Yang Lichao，Zhang Heli，Li Ming，et al.Mobile edge computing empowered energy efficient task offloading in 5G［J］.IEEE Trans on Vehicular Technology，2018，67（7）：6398-6409.

［5］Wang Chenmeng，Yu F R，Liang Chengchao，et al.Joint computation offloading and interference management in wireless cellular networks with mobile edge computing［J］.IEEE Trans on Vehicular Technology，2017，66（8）：7432-7445.

［6］Ji Luyue，Guo Songtao .Energy-efficient cooperative resource allocation in wireless powered mobile edge computing［J］.IEEE Internet of Things Journal，2019，6（3）：4744-4754.

［7］Huang Xinyu，He Lijun，Zhang Wanyue.Vehicle speed aware computing task offloading and resource allocation based on multi-agent reinforcement learning in a vehicular edge computing network［C］//Proc of IEEE International Conference on Edge Computing.Piscataway，NJ：IEEE Press，2020：1-8.

［8］Hou Xiangwang，Ren Zhiyuan，Wang Jingjing，et al.Reliable computation offloading for edge-computing-enabled software-defined IoV［J］.IEEE Internet of Things Journal，2020，7（8）：7097-7111.

［9］Wu Ducheng，Wu Qihui，Xu Yuhua，et al.QoE and energy aware resource allocation in small cell networks with power selection，load management，and channel allocation［J］.IEEE Trans on Vehicular Technology，2017，66（8）：7461-7473.

［10］Ansari S，Ahmad J，Shah S A，et al.Chaos-based privacy preserving vehicle safety protocol for 5G connected autonomous vehicle networks［J］.Trans on Emerging Telecommunications Technologies，2020，31（5）：e3966.

［11］Tran T X，Hajisami A，Pandey P，et al.Collaborative mobile edge computing in 5G networks：new paradigms，scenarios，and challenges［J］.IEEE Communications Magazine，2017，55（4）：54-61.

［12］謝人超，廉曉飛，賈慶民，等.移動(dòng)邊緣計(jì)算卸載技術(shù)綜述［J］.通信學(xué)報(bào)，2018，39（11）：138-155.（Xie Renchao，Lian Xiaofei，Jia Qingmin，et al.Survey on computation offloading in mobile edge computing［J］.Journal on Communications，2018，39（11）：138-155.）

［13］Zhang Jie，Guo Hongzhi，Liu Jiajia，et al.Task offloading in vehicular edge computing networks：a load-balancing solution［J］.IEEE Trans on Vehicular Technology，2020，69（2）：2092-2104.

［14］Mao Yuyi，Zhang Jun，Letaief K B.Joint task offloading scheduling and transmit power allocation for mobile-edge computing systems［C］//Proc of IEEE Wireless Communications and Networking Conference.Piscataway，NJ：IEEE Press，2017：1-6.

［15］Zhang Ke，Mao Yuming，Leng Supeng，et al.Energy-efficient offloa-ding for mobile edge computing in 5G heterogeneous networks［J］.IEEE Access，2016，4：5896-5907.

［16］Zhang Ke，Mao Yuming，Leng Supeng，et al.Mobile-edge computing for vehicular networks：a promising network paradigm with predictive off-loading［J］.IEEE Vehicular Technology Magazine，2017，12（2）：36-44.

［17］Kuang Zhufang，Li Linfeng，Gao Jie，et al.Partial offloading scheduling and power allocation for mobile edge computing systems［J］.IEEE Internet of Things Journal，2019，6（4）：6774-6785.

［18］Mao Yuyi，Zhang Jun，Song S H，et al.Stochastic joint radio and computational resource management for multi-user mobile-edge computing systems［J］.IEEE Trans on Wireless Communications，2017，16（9）：5994-6009.

［19］Dai Yueyue，Xu Du，Maharjan S，et al.Joint load balancing and offloading in vehicular edge computing and networks［J］.IEEE Internet of Things Journal，2019，6（3）：4377-4387.

［20］Ashok A，Steenkiste P，Bai Fan.Adaptive cloud offloading for vehicular applications［C］//Proc of IEEE Vehicular Networking Confe-rence.Piscataway，NJ：IEEE Press，2016：1-8.