基于MEC的無人物流車任務卸載策略

郜文燦 齊 平 束 紅 蔣劍軍

（銅陵學院，安徽 銅陵 244061）

一、引言

隨著電商的崛起，物流行業(yè)得到了迅猛發(fā)展。僅2019年我國快遞業(yè)務量就已達到635.2億件，相比2012年驟增732%。如此巨大的配送需求給物流配送行業(yè)帶來了前所未有的壓力[1]。無人駕駛技術(shù)承擔著革新交通運輸業(yè)的重要使命，而無人化的物流配送業(yè)務則有可能成為無人駕駛技術(shù)最先落地的應用場景[2]。無人駕駛物流車運用人工智能技術(shù)，提高了物品的配送效率、準確性和安全性，并且能夠有效的降低運營成本[3]，但龐大的數(shù)據(jù)傳輸制約著無人物流車的發(fā)展。據(jù)統(tǒng)計，一輛無人車運行一天產(chǎn)生的數(shù)據(jù)量約為4TB[4]，如果將數(shù)據(jù)均上傳到云數(shù)據(jù)中心處理，必然會產(chǎn)生較高的時延和帶寬浪費。

移動邊緣計算(Mobile Edge Computing，MEC)[5]作為云計算向用戶終端擴展，能夠在網(wǎng)絡(luò)邊緣側(cè)部署計算資源和服務，從而極大的降低帶寬消耗與網(wǎng)絡(luò)延遲。計算卸載技術(shù)作為MEC的關(guān)鍵技術(shù)，是指移動終端將部分或全部計算任務交給邊緣服務器或云服務器處理的技術(shù)[6]，主要研究移動終端是否需要卸載，卸載哪些任務，卸載至何處計算等問題[7-8]。從卸載決策優(yōu)化目標進行劃分，當前研究主要集中在以下3個方面：1.時延優(yōu)化，以獲得更快的卸載響應時間和任務完成時間為目標[9-10]；2.能耗優(yōu)化，以降低移動終端或整個MEC系統(tǒng)總體能耗為目標[11-12]；3.綜合考慮能耗和時延，根據(jù)具體任務特性，兼顧優(yōu)化能耗和時延為目標[13-14]。

在終端移動條件下，綜合考慮時延、能耗優(yōu)化問題，是當前智慧物流場景下的計算卸載技術(shù)急需解決的問題。因此，文獻[15]在MEC車聯(lián)網(wǎng)場景下，對于任務卸載過程中的能效與性能可靠性問題，提出了一種能耗最優(yōu)化的卸載方案，有效地提升了系統(tǒng)性能。文獻[16]采用層次分析法對車輛產(chǎn)生的安全消息進行優(yōu)先級劃分，再針對時延和能耗構(gòu)建任務卸載模型。然而在上述研究中，一般設(shè)定車輛與路邊單元(RoadSide Unit，RSU)之間的數(shù)據(jù)上傳、下載速率為定值，或設(shè)為車輛行駛期間的平均數(shù)據(jù)傳輸速率。然而，對于在邊緣服務器無線信號覆蓋范圍較小的小區(qū)內(nèi)行駛的無人車而言，無法忽略數(shù)據(jù)傳輸速率的瞬時變化以及物流車位置改變對計算卸載性能的影響。

針對上述問題，本文在MEC環(huán)境下，結(jié)合工作流任務、小區(qū)無人車配送場景地圖、邊緣服務器無線信號覆蓋范圍，構(gòu)建了考慮終端移動性的無人車任務卸載時間與能耗模型。在此基礎(chǔ)上，提出了無人車移動路徑規(guī)劃算法、任務卸載決策與調(diào)度算法和最優(yōu)配送路線算法。仿真實驗結(jié)果說明通過預先規(guī)劃最優(yōu)配送路徑和配送順序，合理地分配計算資源，能夠在用戶響應時間約束下有效降低終端能耗和違約率。

二、MEC環(huán)境下小區(qū)無人車物流配送場景建模

（一）小區(qū)無人車物流配送場景

對小區(qū)無人車物流配送場景進行建模描述，圖1中已標注邊緣服務器、無人車出發(fā)地和目的地位置，同時使用藍色和橙色虛線標出從出發(fā)地到目的地的兩條可選路徑(實際情況中可能存在多條可選路徑)，移動路徑定義如下：

圖1 無人物流車配送場景及移動路徑平面圖

定義1將小區(qū)按照其地理位置劃分為若干網(wǎng)格，移動路徑由ngrid個具有偏序關(guān)系的網(wǎng)格位置構(gòu)成，定義移動路徑Path={ci|ci=(xi，yi)，i∈ngrid}。其中，ci為移動路徑上第i個網(wǎng)格的位置坐標，由二元組(xi，yi)表示，分別其橫坐標和縱坐標，且滿足相鄰位置坐標(xi，yi)和(xi+1，yi+1)在地理位置上相鄰并可達。

定義2小區(qū)無人車物流配送場景地圖可表示為二維數(shù)組。如圖2所示，數(shù)組元素用于表示地圖中網(wǎng)格點的通行狀態(tài)。數(shù)值0表示該網(wǎng)格存在永久性建筑或障礙物(如樓房、綠化帶等)，無法通過，數(shù)值1表示該網(wǎng)格可以正常通行。

圖2 小區(qū)無人車物流配送場景地圖構(gòu)建方法

（二）工作流任務模型

本文通過加權(quán)有向無環(huán)圖 （DirectedAcyclic Graph，DAG）對MEC環(huán)境下無人車物流配送工作流中任務執(zhí)行的先后依賴關(guān)系進行描述。其中，無人車物流配送工作流、云服務器、邊緣服務器、移動終端和無線信號覆蓋模型分別定義如下：

定義3工作流任務可采用一個加權(quán)有向無環(huán)圖（W，E）表示，W為任務集合，E為工作流任務間的依賴關(guān)系。其中W={wi|wi=(INi，OUTi，li)}，wi為工作流任務中第i個任務，INi為任務wi的輸入數(shù)據(jù)量，OUTi為任務wi的輸出數(shù)據(jù)量，li為任務負載；E={(wpre，wsucc)|wpre，wsucc∈W}， 其中wpre為前驅(qū)任務，wsucc為后繼任務。

定義4移動設(shè)備（MobileDevice，MD）可表示為一個五元組，MD=(fmd，Pmd，Locmd，nload，v)，其中fmd和Pmd分別表示MD的計算能力和能耗；Pmd=(pidle，pexec，ptra，prec)，分別表示MD的空閑功率、任務執(zhí)行功率、數(shù)據(jù)發(fā)送功率和接收功率；Locmd表示MD的位置坐標，v表示其速度（米/秒）；nload表示MD的最大承載能力，即MD每次回到小區(qū)物流配送服務站最多可以裝載nload件貨物。

定義5云服務器（CloudServer，CS）可表示為一個二元組，CS= (fcs，Rcs)，其中fcs表示CS的計算能力，Rcc表示CS的數(shù)據(jù)發(fā)送和接收速率。

定義6邊緣服務器（EdgeServer，ES）可表示為一個四元組，ES=(fes，Res，BWes，Loces)，其中fes表示ES的計算能力，Res表示數(shù)據(jù)發(fā)送和接收速率，BWes，為傳輸帶寬，Loces為位置坐標。

定義7MD與ES之間的瞬時數(shù)據(jù)傳輸速率為：

其 中fSNR(dES，MD)為 傳 輸 信 噪 比[11]，dES，MD為MD和ES之間的距離，dmax為兩者之間的最大通信距離。受信噪比的影響，對于不同ES，應通過dES，MD計算MD與各ES之間的瞬時數(shù)據(jù)傳輸速率。為簡化模型，本文假定MD在同一網(wǎng)格內(nèi)移動時，與同一ES進行通信的數(shù)據(jù)瞬時傳輸速率不變。

三、無人車任務卸載模型

設(shè)定無人車的初始位置為小區(qū)物流配送服務站，當用戶發(fā)出配送服務請求時，如圖3(a)所示，無人車應盡可能多的裝載貨物(設(shè)nload為4)，再將貨物分別送至各用戶指定位置，若此時配送任務沒有完成，還需返回小區(qū)物流配送服務站繼續(xù)裝載、配送貨物，直至任務完成。

配送過程中存在兩方面問題：（1）如圖3(b)所示，當無人車的出發(fā)地和目的地確定時，應結(jié)合當前可選移動路徑以及無人車的移動速度，計算各可選路徑在任務響應時間約束下的最少終端能耗，進而選擇終端能耗最小的最優(yōu)路徑行駛；（2）如圖3(c)所示，當存在多個用戶的配送請求時，應結(jié)合最優(yōu)路徑選擇算法，確定服務的先后順序，得到最優(yōu)配送路線。本節(jié)針對確定起止點的路徑構(gòu)建任務卸載能耗模型，該模型由云服務器能耗模型、移動設(shè)備能耗模型和邊緣服務器能耗模型三部分構(gòu)成。

圖3 無人物流車配送路徑規(guī)劃

（一）云服務器能耗模型

當計算任務卸載至云服務器時，MD能耗由三部分組成：1）數(shù)據(jù)發(fā)送能耗；2）數(shù)據(jù)回傳接收能耗；3）整個過程中空閑等待能耗。設(shè)卸載至云端執(zhí)行的任務數(shù)量為ncs，則將任務卸載至云端時，終端的總執(zhí)行時間和總能耗可由式(2)計算：

在移動路徑預先規(guī)劃的情況下，設(shè)（Startx，Starty）為MD初始網(wǎng)格的位置坐標，網(wǎng)格邊長為len米，則在Tcs時間內(nèi)MD通過的網(wǎng)格數(shù)gridcs為[(V×Tcs)/len]。因而，任務執(zhí)行完畢后MD位置(Endx，Endy)可更新為(Startx，Starty)之后第gridcs個鄰接網(wǎng)格位置(若任務執(zhí)行過程中，已到達目的地則MD位置不再改變)。

（二）移動終端能耗模型

當任務在MD執(zhí)行時，其終端能耗為任務在MD的執(zhí)行能耗。設(shè)在MD上執(zhí)行的任務數(shù)量為nmd，則終端的總執(zhí)行時間和總能耗可由式(3)計算：

（三）邊緣服務器能耗模型

如圖4所示，當任務卸載至邊緣服務器時，MD能耗由任務所需數(shù)據(jù)的發(fā)送能耗、回傳數(shù)據(jù)的接收能耗以及在發(fā)送、接收、執(zhí)行期間MD的空閑等待能耗組成。數(shù)據(jù)發(fā)送階段，MD的位置由坐標(TraXstart，TraYstart)移動至坐標(TraXend，TraYend)；在回傳數(shù)據(jù)接收階段，MD的位置從坐標(RecXstart，RecYstart)移動到坐標(RecXend，RecYend)。然而，如圖4(b)所示，由于MD和ES之間的瞬時數(shù)據(jù)傳輸速率與距離相關(guān)，在數(shù)據(jù)發(fā)送或回傳階段，當MD離開當前ES的無線信號覆蓋范圍時(d|ES，MD|＞dmax)，任務將無法卸載至ES，需在本地或卸載至云端執(zhí)行。

圖4 邊緣服務器計算卸載模型

設(shè)卸載至邊緣側(cè)執(zhí)行的任務數(shù)量為nes，則將任務卸載至邊緣側(cè)時，終端的總執(zhí)行時間Tes和總能耗Ees分別為：

四、工作流卸載決策及其調(diào)度算法

根據(jù)工作流任務的執(zhí)行先后依賴關(guān)系對其優(yōu)先等級進行劃分，相同優(yōu)先級任務可并行處理。設(shè)任務最大優(yōu)先級為N，優(yōu)先級序列為LV={lv1，lv2，…，lvN}，對于其中第i級可并行任務lvi(設(shè)第i級可并行任務的任務總數(shù)為mi)，使用任務執(zhí)行矩陣對其進行描述，如式(5)所示：

（一）基于最優(yōu)路徑的卸載決策及調(diào)度算法

最優(yōu)路徑是指在滿足任務時間約束的條件下，終端能耗最低的路徑。在小區(qū)無人車物流配送場景下，當無人車出發(fā)地和目的地確定時，需要在兩地之間的多條路徑中找出最優(yōu)路徑，并依此得到卸載決策和任務調(diào)度方案。本文使用遺傳算法設(shè)計基于最優(yōu)路徑的無人車任務調(diào)度算法(TaskSchedulingAlgorithmBasedontheOptimalPath，TSABOP)。TSABOP算法首先對染色體進行解碼，再結(jié)合無人車的移動路徑得到各任務調(diào)度序列(如將任務卸載至邊緣服務器則根據(jù)各邊緣服務器位置及其無線信號覆蓋范圍，找出邊緣側(cè)無線信號最優(yōu)的候選邊緣服務器進行卸載)，最后通過適應度函數(shù)對各任務調(diào)度序列進行評價。

（二）無人車最優(yōu)配送路線算法

本節(jié)基于遺傳算法設(shè)計了無人車最優(yōu)配送路線算法（OptimalServiceSequenceofDriverlessLogistics DistributionVehicle，OSS-DV)。

設(shè)請求配送貨物的用戶數(shù)量為ndist，按時間排列的配送請求位置序列為由于無人車最多能夠裝載nload個貨物，因此以序號1，2，...，nload表示nload個用戶，Eij表示無人車從用戶i到用戶j的最優(yōu)能耗(由算法1計算，當無人車早于用戶指定時間到達配送位置時，應加上無人車等待期間的終端空閑能耗)；tij表示無人車從用戶i到用戶j所花費的時間；xij∈{0，1}為決策變量；Ti表示無人車到達用戶i的時刻，應落在時間范圍[Tui-ε，Tui+ε]內(nèi)，Tui為用戶i指定的服務時間，Eear和Elate分別表示無人車提前到達和延后到達的懲罰值，因而該問題的目標函數(shù)f為：

式(7)右側(cè)第一項為不考慮時間約束下的能耗；第二項為無人車到達時間早于Tui-ε時，等待時間的懲罰值；第三項為無人車晚于Tui+ε時，遲到時間的懲罰值。

五、仿真實驗與分析

本文通過在MatlabR2017b環(huán)境下進行仿真實驗以檢驗算法性能，所有實驗結(jié)果均采用10次實驗的平均值。

實驗參數(shù)設(shè)置如下：無人車的最大承載能力為6，計算能力為1GHz，執(zhí)行功率為0.5W，數(shù)據(jù)發(fā)送時功率為0.5W，數(shù)據(jù)接收時功率為0.05W，空閑功率為0.02W，Eear和Elate分別取0.1和0.15，移動速度為1m/s[2]，無人車與云端的數(shù)據(jù)傳輸速率為5Mb/s，與邊緣側(cè)的數(shù)據(jù)瞬時傳輸速率由兩者之間的通信距離決定[11][12]。邊緣服務器數(shù)量為10，其位置在小區(qū)內(nèi)呈均勻分布，計算能力介于[2GHz～5GHz]之間，云服務器的計算能力為8GHz[12]。設(shè)定小區(qū)無人車物流配送場景為800m*600m的長方形區(qū)域，小區(qū)路徑預先給定，網(wǎng)格大小設(shè)定為1m*1m。設(shè)定用戶位置隨機生成，用戶配送請求時間間隔服從指數(shù)分布[17]；無人車工作流任務DAG圖隨機生成，任務計算量介于1～5GHz之間，發(fā)送和回傳數(shù)據(jù)量介于1～15Mb之間[18]，用戶響應時間約束為該任務在1.4GHz虛擬機上平均執(zhí)行時間的2倍[19]。

（一）任務卸載模型的有效性

1.路徑選擇對算法性能的影響

工作流任務數(shù)量為50，Path1～Path8分別表示兩點間隨機選擇的8條路徑，實驗結(jié)果如圖5所示。

圖5 不同移動路徑下的終端能耗比較

由圖可見，當選擇不同路徑時，終端能耗也不相同。對比最小能耗路徑Path3和最大能耗路徑Path7，Path7所需能耗增加了152.3%，可見TSABOP算法規(guī)劃最優(yōu)路徑的必要性。

2.配送路線對算法性能的影響

本實驗在不同任務數(shù)情況下，從終端能耗、違約率和任務完工時間三個方面考察不同配送路線對算法性能的影響。相關(guān)實驗參數(shù)設(shè)置如下：ε為30s，每條路徑的工作流任務數(shù)量變化范圍為[10，100]，任務完成后無人車才可進入下一條配送路徑。TimeSequence(兩點間最優(yōu)路徑由TSABOP算法計算，配送路線按照用戶請求時間)、ShortestPath(兩點間路徑選取最短路徑，配送路線按照用戶請求時間)和Optimal Sequence(OSS-DV算法得到的最優(yōu)配送路線)為3種無人車配送策略，實驗結(jié)果如圖6所示。

圖6 不同配送路線算法的性能比較

由圖可見，Timesequence策略相比OptimalSequence策略的終端能耗提高了17.6%，違約率提高38.9%，說明不同配送順序?qū)λ惴ㄐ阅芫哂休^大影響，而本文提出的OSS-DV算法結(jié)合移動路徑，即考慮了用戶配送時間要求，又考慮了任務在云端、邊緣服務器以及移動設(shè)備上的執(zhí)行效益，能夠在響應執(zhí)行時間約束下有效降低終端能耗和違約率。

（二）不同任務數(shù)情況下的算法性能比較

本實驗在不同任務數(shù)下，對OSS-DV算法和其它3種任務卸載策略進行比較。實驗參數(shù)設(shè)置為：每條路徑的工作流任務量為50，對比策略包括Only-Cloud、Only-Edge和LoPRTC[20](其中Only-Cloud、Only-Edge分別指工作流任務全部在云端或邊緣側(cè)執(zhí)行)，對比策略選取路徑為兩點間最短路徑，配送路線按照用戶請求時間，實驗結(jié)果如圖7所示。

圖7 不同任務數(shù)下算法的比較

由圖7(a)和圖7(c)可見，本文提出的OSS-DV算法的違約率比LoPRTC算法降低50.1%，任務完工時間減少25.3%，而終端能耗降低41.3%，說明OSSDV算法通過合理規(guī)劃移動路徑，優(yōu)化任務卸載決策，和其他3種算法相比能夠大幅降低終端能耗和違約率，有效提升無人車配送效率。

六、結(jié)語

本文在小區(qū)無人車物流配送場景下，將終端移動性納入計算卸載模型，根據(jù)移動終端的實時位置、移動速率、邊緣服務器位置、邊緣服務器無線信號覆蓋范圍以及小區(qū)地圖構(gòu)建了無人車任務卸載模型，設(shè)計了工作流任務優(yōu)先級劃分算法和邊緣側(cè)卸載優(yōu)化算法，并在此基礎(chǔ)上使用遺傳算法設(shè)計基于最優(yōu)路徑的無人車任務調(diào)度算法和無人車最優(yōu)配送路線算法以計算最優(yōu)路徑和配送路線。仿真實驗結(jié)果說明本文提出的TSABOP算法和OSS-DV算法能夠在響應時間約束下，有效降低終端能耗和配送違約率。由于本文只考慮了單個無人車的物流配送場景，下一步工作將研究多個無人車的協(xié)作問題。