郜文燦 齊 平 束 紅 蔣劍軍

（銅陵學(xué)院，安徽 銅陵 244061）

一、引言

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

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

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

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

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

（一）小區(qū)無(wú)人車物流配送場(chǎng)景

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

圖1 無(wú)人物流車配送場(chǎng)景及移動(dòng)路徑平面圖

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

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

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

（二）工作流任務(wù)模型

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

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

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

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

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

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

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

三、無(wú)人車任務(wù)卸載模型

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

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

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

（一）云服務(wù)器能耗模型

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

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

（二）移動(dòng)終端能耗模型

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

（三）邊緣服務(wù)器能耗模型

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

圖4 邊緣服務(wù)器計(jì)算卸載模型

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

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

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

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

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

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

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

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

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

五、仿真實(shí)驗(yàn)與分析

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

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

（一）任務(wù)卸載模型的有效性

1.路徑選擇對(duì)算法性能的影響

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

圖5 不同移動(dòng)路徑下的終端能耗比較

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

2.配送路線對(duì)算法性能的影響

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

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

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

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

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

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

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

六、結(jié)語(yǔ)

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