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

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

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

0 引言

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

在交通運(yùn)輸領(lǐng)域，智慧交通系統(tǒng)作為基于物聯(lián)網(wǎng)提出的一個(gè)重要的應(yīng)用方向，通過(guò)與大數(shù)據(jù)、人工智能、云計(jì)算、自動(dòng)控制等技術(shù)的有效結(jié)合，集成應(yīng)用于交通管理體系，使得人、車、路之間緊密配合，實(shí)現(xiàn)交通運(yùn)輸?shù)母咝省⒔煌ǔ鲂械陌踩院徒煌ü芾淼谋憬菪?，從而為人們提供更好的出行服?wù)[2]。

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

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

1 邊緣計(jì)算概述

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

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

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

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

1.2 邊緣計(jì)算的特點(diǎn)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1 匹配過(guò)程

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

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

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

3.2 仿真實(shí)驗(yàn)結(jié)果分析

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

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

4 結(jié)論

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

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