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

郜文燦 齊 平 束 紅 蔣劍軍

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

一、引言

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

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

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

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

二、MEC環境下小區無人車物流配送場景建模

（一）小區無人車物流配送場景

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

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

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

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

圖2 小區無人車物流配送場景地圖構建方法

（二）工作流任務模型

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

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

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

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

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

定義7MD與ES之間的瞬時數據傳輸速率為：

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

三、無人車任務卸載模型

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

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

圖3 無人物流車配送路徑規劃

（一）云服務器能耗模型

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

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

（二）移動終端能耗模型

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

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

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

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

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

四、工作流卸載決策及其調度算法

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

（一）基于最優路徑的卸載決策及調度算法

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

（二）無人車最優配送路線算法

本節基于遺傳算法設計了無人車最優配送路線算法（OptimalServiceSequenceofDriverlessLogistics DistributionVehicle，OSS-DV)。

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

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

五、仿真實驗與分析

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

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

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

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

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

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

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

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

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

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

由圖可見，Timesequence策略相比OptimalSequence策略的終端能耗提高了17.6%，違約率提高38.9%，說明不同配送順序對算法性能具有較大影響，而本文提出的OSS-DV算法結合移動路徑，即考慮了用戶配送時間要求，又考慮了任務在云端、邊緣服務器以及移動設備上的執行效益，能夠在響應執行時間約束下有效降低終端能耗和違約率。

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

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

圖7 不同任務數下算法的比較

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

六、結語

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