基于邊緣計算的任務(wù)卸載研究

潘煜 吳九天 孫宇筠 斯方超 俞鑫

關(guān)鍵詞：邊緣計算；車輛霧計算；任務(wù)卸載；響應(yīng)時間

0 引言

在現(xiàn)代計算機技術(shù)背景下，互聯(lián)網(wǎng)實現(xiàn)了人與人之間的連接，物聯(lián)網(wǎng)則以互聯(lián)網(wǎng)為基礎(chǔ)進行延伸，通過微波雷達傳感器、熱敏傳感器等各類傳感設(shè)備實現(xiàn)了人-物、物-物之間的連接[1]。

在交通運輸領(lǐng)域，智慧交通系統(tǒng)作為基于物聯(lián)網(wǎng)提出的一個重要的應(yīng)用方向，通過與大數(shù)據(jù)、人工智能、云計算、自動控制等技術(shù)的有效結(jié)合，集成應(yīng)用于交通管理體系，使得人、車、路之間緊密配合，實現(xiàn)交通運輸?shù)母咝?、交通出行的安全性和交通管理的便捷性，從而為人們提供更好的出行服?wù)[2]。

隨著智能路網(wǎng)、智慧出行、智慧停車等項目的推進與實現(xiàn)，智慧交通系統(tǒng)正處于快速發(fā)展的時代，與之相對的許多挑戰(zhàn)亟需攻克[3]。一方面，隨著日常生活中車輛使用的普及，車-路、車-人，以及車-車之間通信會產(chǎn)生巨量的信息，控制傳遞這些海量數(shù)據(jù)信息則需要同時滿足高帶寬和低延時的性能要求，而傳統(tǒng)的云計算在處理大量數(shù)據(jù)時往往會出現(xiàn)帶寬負載大和延遲高的問題，造成了成本的極大提升。另一方面，將數(shù)據(jù)傳送到云計算中心往往有很長的傳輸距離，長距離的信息傳輸會增大用戶個人隱私信息泄露的風(fēng)險，此外，大量未經(jīng)處理信息的判斷也會對云中心造成很大的負擔(dān)[4]。

為解決上述問題，降低云計算中心信息處理的負荷，人們提出了邊緣計算的概念。邊緣服務(wù)器相當(dāng)于一個小型的云計算中心，與移動設(shè)備相比有較高的計算能力。這些移動邊緣服務(wù)器處于網(wǎng)絡(luò)中心的邊緣，與用戶設(shè)備之間的距離大幅降低，能有效降低因傳輸造成的延遲以及隱私泄露的風(fēng)險[1]。另外，隨著技術(shù)進步，車載設(shè)備的性能提升，也使其足以作為一個霧服務(wù)器來提供服務(wù)，分擔(dān)邊緣服務(wù)器的壓力。

1 邊緣計算概述

智慧交通系統(tǒng)中云計算是至關(guān)重要的一部分，它一方面能提供超強的計算能力，另一方面能方便快捷的進行資源調(diào)度、信息共享，使得海量的數(shù)據(jù)得到集成化管理，能更好的幫助交通部門的日常管理以及為社會公眾提供服務(wù)。智慧交通系統(tǒng)主要通過傳感器、攝像頭等前端物理設(shè)備獲取數(shù)據(jù)并上傳給云中心，云中心完成計算任務(wù)再進行數(shù)據(jù)傳輸來完成信息交互。隨著交通量的增長和人們對高質(zhì)量網(wǎng)絡(luò)服務(wù)的需求，僅依靠云中心的計算已經(jīng)難以適應(yīng)智慧交通發(fā)展的需要，因此提出邊緣計算的概念。

邊緣計算是云計算的一種延伸，是設(shè)置在道路周邊的一些小型服務(wù)器，能處理云中心的部分或全部任務(wù)。云中心雖然擁有強大的計算處理能力，但其與移動設(shè)備之間在空間上長遠的傳輸距離導(dǎo)致的問題依舊無法解決，始終無法滿足低延遲的服務(wù)要求。而邊緣計算分布在網(wǎng)絡(luò)的邊緣地帶，拉近與用戶終端的傳輸距離，有效地解決了數(shù)據(jù)傳輸延遲高的問題。

1.1 邊緣計算基本架構(gòu)

如圖1 所示，邊緣計算主要包含云中心、邊緣云、移動設(shè)備這三個基本組件[5]。移動設(shè)備是指用戶使用的各種終端設(shè)備，包含智能手機、筆記本電腦、智能汽車等，是向邊緣計算服務(wù)器發(fā)送任務(wù)請求的主體；邊緣云則由多種移動計算服務(wù)器組成，能對移動設(shè)備的卸載任務(wù)進行本地化計算處理，減少因超遠距離傳輸或移動設(shè)備計算緩慢產(chǎn)生的延遲；云中心是布置在網(wǎng)絡(luò)核心區(qū)域的高性能服務(wù)器，負責(zé)儲存和共享大量的數(shù)據(jù)信息，解決超出邊緣云計算能力的任務(wù)，對整個網(wǎng)絡(luò)系統(tǒng)進行控制。

1.2 邊緣計算的特點

⑴ 能耗低，性能強。移動設(shè)備容易受到電池容量和性能的限制，在執(zhí)行大型應(yīng)用任務(wù)時，不僅會占用大量的資源空間，還容易導(dǎo)致能耗迅速上升。通過將這些復(fù)雜的任務(wù)卸載到邊緣計算服務(wù)器上進行計算，不僅能提高信息處理效率，也能減少移動設(shè)備的能源消耗，提升用戶的服務(wù)體驗。

⑵ 時延低。相比于將大量數(shù)據(jù)傳送到云端計算中心進行處理再進行回傳處理，邊緣計算服務(wù)器能發(fā)揮在空間中與移動設(shè)備更近的距離優(yōu)勢，有效地減少網(wǎng)絡(luò)帶寬占用的同時，還能更快地完成計算任務(wù)及反饋，實現(xiàn)網(wǎng)絡(luò)時延降低，進一步提升用戶體驗。

⑶ 感知性強。由于邊緣計算服務(wù)器的分布距離移動設(shè)備更近，能夠迅速準(zhǔn)確地捕捉用戶的地理位置等實時信息，并以此來為用戶提供更加準(zhǔn)確、優(yōu)質(zhì)的服務(wù)。

⑷ 安全性高。邊緣計算可以避免大容量數(shù)據(jù)在網(wǎng)絡(luò)上進行傳輸時存在的隱私數(shù)據(jù)容易泄露的問題，對一些必要的數(shù)據(jù)進行匿名、加密等預(yù)處理，提升了數(shù)據(jù)傳輸?shù)陌踩浴?/p>

1.3 邊緣計算任務(wù)卸載

越來越多的用戶選擇在終端設(shè)備上處理各種業(yè)務(wù)，但移動設(shè)備往往受到體積、質(zhì)量的限制，其計算能力和存儲空間總是有限的。任務(wù)卸載的基本思想是將移動設(shè)備無法獨立完成的任務(wù)轉(zhuǎn)移到距離相近的邊緣服務(wù)器或其他設(shè)備上執(zhí)行，從而提升移動設(shè)備的性能。按照任務(wù)類型分類有兩種：①數(shù)據(jù)任務(wù)卸載，在自身網(wǎng)絡(luò)堵塞時，暫時使用其他閑置的網(wǎng)絡(luò)，從而提升數(shù)據(jù)傳輸?shù)乃俣龋虎谟嬎闳蝿?wù)卸載，在自身設(shè)備硬件實力或剩余資源不足以支持復(fù)雜的計算時，將任務(wù)遷移到其他服務(wù)器中完成并接收傳回的結(jié)果。

常見的任務(wù)卸載主要分為以下兩種：①0-1 卸載，對于一些不能或者不需要分割的任務(wù)，將其從用戶設(shè)備完整的轉(zhuǎn)移到另一個設(shè)備上；②部分卸載，對任務(wù)進行分解處理，將需要卸載的任務(wù)轉(zhuǎn)移到另一設(shè)備處理，剩下的進行本地處理[6]。分解的方式可分為兩種：①開發(fā)人員在編寫代碼時提前完成分割，把需要卸載的部分代碼塊進行標(biāo)識，在實施遷移策略時就可以把標(biāo)記部分放在更高的優(yōu)先級，這種方式由于在代碼層面就進行了分解，因此擁有較高的細粒度和靈活性；②通過策略執(zhí)行者對任務(wù)進行分解，無法實現(xiàn)特別精密的控制，但對底層開發(fā)而言則比較輕松[7]。在滿足上述卸載條件后，還需要從任務(wù)類型、卸載時間、用戶的具體位置、用戶的偏好習(xí)慣等多個方面進行考慮。

2 系統(tǒng)模型搭建及參數(shù)定義

2.1 系統(tǒng)模型搭建

在依靠邊緣計算實現(xiàn)智慧交通管理的實際應(yīng)用中，真實的路況和車輛形式情況是非常復(fù)雜的，因此完全基于實際情況建模十分困難，為簡化實驗，選用單向兩車道的路面，保持車輛勻速行駛，路側(cè)RSU（邊緣服務(wù)器）均勻沿道路均勻分布，每個RSU的信號強度、接收范圍等性能都相同。RSU 和車輛之間可以進行通信，RSU 與RSU 之間通過有線連接實現(xiàn)通信。每個RSU都作為一個服務(wù)器對卸載任務(wù)完成處理并將結(jié)果返回。試驗車輛本身具有一定計算能力，可以在本地對一些簡單任務(wù)進行處理，而當(dāng)車輛有剩余的空閑資源時就能作為一個霧服務(wù)器來幫助其他車輛完成任務(wù)。

表1 為模型中各參數(shù)及其定義，R 表示路側(cè)的所有RSU，R={R1 ，R2 ，...，Rs}，其中每個RSU 包含三個屬性，Rs（RSU 編號，位置橫坐標(biāo)，位置縱坐標(biāo)）；C 表示所有道路上的車輛，C={C1 ，C2 ，...，Ci}，其中每輛車都包含四個屬性，Ci （車輛編號，位置橫坐標(biāo)，位置縱坐標(biāo)）；CT 表示發(fā)起任務(wù)的車輛，且每輛車只能發(fā)起一個任務(wù)，CT={CT1 ，CT2 ，...，CTj}；CS 表示車輛霧服務(wù)器，CS={CS1 ，CS2 ，...，CSk}，CSk為資源空閑的車輛。

2.2 任務(wù)卸載響應(yīng)時間

任務(wù)卸載性能的評估通過平均響應(yīng)時間的長短來判斷，主要包括計算時間和通信時間。響應(yīng)時間計算所需參數(shù)如表2 所示。

表2 中，A 表示需要卸載的任務(wù)的集合，A={A1，A2，...，An}，An包含任務(wù)的三個屬性，用An（xn ，yn ，zn）來表示，其中xn為上行鏈路要傳輸?shù)臄?shù)據(jù)大?。ㄐ枰M行卸載的任務(wù)），yn為下行鏈路要傳輸?shù)臄?shù)據(jù)大?。ㄍ瓿扇蝿?wù)后要傳回的計算結(jié)果），zn是計算單位比特任務(wù)的能力，即完成任務(wù)An需要xn·zn個CPU 周期的時間。

3 基于KM 算法的最優(yōu)匹配

KM 算法是基于匈牙利算法而產(chǎn)生的求最大權(quán)值匹配的算法，常用于解決與二分圖匹配有關(guān)的問題[8]。二分圖是一種特殊的圖，其分為兩個部分，各自部分的點互相獨立，匹配就是將兩部分的點兩兩連接形成的邊的集合，且任意兩條邊不能有公共點。匈牙利算法的目的就是得到最大的匹配邊數(shù)，這種方法得到的匹配并不是惟一的。KM 算法則是基于此為兩部分的點都加上權(quán)值，最優(yōu)匹配就是權(quán)值綜合最大的匹配。KM 算法流程如下：

⑴ 初始化可行頂標(biāo)的值；

⑵ 用匈牙利算法尋找完備匹配；

⑶ 若未找到完備匹配則修改可行頂標(biāo)的值；

⑷ 重復(fù)⑵⑶直至找到相等子圖的完備匹配為止。

3.1 匹配過程

首先，在匹配前需要對必須的參數(shù)進行初始化設(shè)置，例如RSU 的集合R，車輛的集合C 等，以及在計算過程中產(chǎn)生的一些中間變量，如任務(wù)卸載位置的集合S，才能順利執(zhí)行后續(xù)的計算。

然后計算卸載任務(wù)的車輛CTj與車輛霧服務(wù)器之間的幾何距離dj，k，如果dj，k小于通信距離r 就將其存儲在集合S 中，如果S 為空集則計算CTj與RSU 之間的距離dj，s ，如果存在dj，s小于r 則可以將任務(wù)卸載到Rs上，否則只能在本地進行處理，如圖2為服務(wù)器篩選流程圖。

如果S 不為空集，則說明存在車輛霧服務(wù)器可以完成卸載任務(wù)，計算不同連接完成任務(wù)所需的響應(yīng)時間t，根據(jù)數(shù)值大小賦予相應(yīng)的權(quán)值，隨后就可以通過KM 算法得到最優(yōu)匹配，這即為完成所有車輛的卸載任務(wù)耗時最少的方案。

3.2 仿真實驗結(jié)果分析

通過仿真分析該方法對時延的影響，根據(jù)需求采用MATLAB r2018b 平臺進行仿真實驗。以下為實驗參數(shù)設(shè)置：RSU 的數(shù)量R=6；車輛數(shù)量C=40，其中發(fā)送任務(wù)的車輛與協(xié)助完成任務(wù)的車輛在每次計算實驗時隨機確定；任務(wù)的大小都是隨機生成的；傳輸速率為3～4Mbps；RSU 的計算速率為2～2.5Ghz，車輛霧服務(wù)器的計算速率為0.8～1Ghz。

圖3 所示為10 次仿真實驗的數(shù)據(jù)結(jié)果，每組數(shù)據(jù)的左側(cè)是車輛僅與RSU 進行任務(wù)卸載的響應(yīng)時間，右側(cè)是增加車輛霧服務(wù)器后的任務(wù)卸載響應(yīng)時間，與前者相比，后者所需的平均響應(yīng)時間明顯降低，減少了51%，最高者能到達70%，證明能有效降低數(shù)據(jù)傳輸時延。

4 結(jié)論

本文主要針對智慧交通管理領(lǐng)域的任務(wù)卸載問題進行了研究與分析，邊緣計算能夠為各種應(yīng)用提供低延遲服務(wù)，隨著車輛用戶終端設(shè)備的普及，過多的卸載任務(wù)會影響邊緣服務(wù)器的性能，引入車輛霧服務(wù)器來完成部分任務(wù)，并通過KM 算法實現(xiàn)一對一的最優(yōu)匹配，有效降低車輛、邊緣計算服務(wù)器、云計算中心間的傳輸時延，提升用戶的駕駛體驗。

本文的實驗環(huán)境為理想狀況，路面駕駛與傳感器等設(shè)備現(xiàn)場安裝情況等實際應(yīng)用場景更加復(fù)雜，對此問題仍有較大的研究空間：①本文采用直線道路作為研究環(huán)境，實際的道路場景存在交叉路口、紅綠燈等復(fù)雜因素，霧節(jié)點的連接可能會發(fā)生中斷；②本文默認(rèn)所有車輛愿意提供空閑的計算資源，實際可能會有較多不愿共享的情況，需要進一步完善共享機制以獲取信任。