無人機(jī)配送系統(tǒng)中端邊協(xié)同的并行任務(wù)調(diào)度算法

周博文，黃海軍，徐 怡+，李學(xué)俊，高 寒，陳天翔，劉 曉，徐 佳

(1.安徽大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽 合肥 230601；2.中移在線服務(wù)有限公司 浙江分公司，浙江 杭州 310000；3.迪肯大學(xué) 信息技術(shù)學(xué)院，澳大利亞 吉朗 VIC 3126)

0 引言

近年來，在線購物逐漸增多，訂單量也隨之增加。2018年11月11日，淘寶平臺(tái)全天的物流訂單達(dá)到10億，這一數(shù)據(jù)在2019年超過了12.92億[1]。物流企業(yè)需要在規(guī)定時(shí)間內(nèi)完成全部訂單的配送工作。在整體配送流程中，最后一公里配送環(huán)節(jié)所占的運(yùn)輸時(shí)間和配送成本高達(dá)30%和50%。無人機(jī)因其靈活部署、成本低廉、高速飛行的特點(diǎn)，在最后一公里配送場(chǎng)景中具有得天獨(dú)厚的優(yōu)勢(shì)。目前，大型物流企業(yè)，如亞馬遜、京東等都已經(jīng)開始嘗試將無人機(jī)作為最后一公里配送的運(yùn)輸工具[2]。在無人機(jī)配送的整個(gè)過程中，需要不斷地對(duì)無人機(jī)上傳感器和攝像頭捕獲的數(shù)據(jù)進(jìn)行處理和計(jì)算，從而保障貨物安全送達(dá)。由于無人機(jī)終端的計(jì)算能力與電池容量均有限，無法高效執(zhí)行此類計(jì)算密集型應(yīng)用，而傳統(tǒng)云計(jì)算環(huán)境又存在距離終端設(shè)備較遠(yuǎn)、網(wǎng)絡(luò)帶寬有限等缺點(diǎn)，無法滿足無人機(jī)飛行過程中高實(shí)時(shí)性與數(shù)據(jù)傳輸需求[3]。

移動(dòng)邊緣計(jì)算環(huán)境通過將計(jì)算資源下沉至更靠近終端設(shè)備，使得其具有低延時(shí)、分布式、高效率等優(yōu)勢(shì)[4-6]，更加適用于在移動(dòng)設(shè)備上部署和執(zhí)行人工智能應(yīng)用。與云計(jì)算不同，移動(dòng)邊緣計(jì)算并不是將所有原始數(shù)據(jù)直接傳輸?shù)皆贫耍峭ㄟ^邊緣服務(wù)器對(duì)原始數(shù)據(jù)進(jìn)行預(yù)處理、過濾和分析，充分利用邊緣設(shè)備的空閑計(jì)算資源。在文獻(xiàn)[7]中，將部分無人機(jī)視頻分析任務(wù)卸載至邊緣節(jié)點(diǎn)，節(jié)省網(wǎng)絡(luò)帶寬從而提高可擴(kuò)展性。在文獻(xiàn)[8]中，無人機(jī)可以利用周圍城市范圍內(nèi)邊緣服務(wù)器的計(jì)算資源來優(yōu)化用戶體驗(yàn)，其中提出了一個(gè)決策框架來控制任務(wù)是否卸載到無人機(jī)系統(tǒng)的邊緣服務(wù)器中，利用馬爾可夫決策優(yōu)化執(zhí)行時(shí)延。上述工作將邊緣計(jì)算引入無人機(jī)視頻分析的場(chǎng)景中，但目前仍然存在的問題是，即使邊緣服務(wù)器的資源比終端設(shè)備豐富，相較于云服務(wù)器節(jié)點(diǎn)還是相對(duì)有限。當(dāng)最后一公里配送場(chǎng)景中收貨人較多，即終端設(shè)備請(qǐng)求較多時(shí)，單一的邊緣服務(wù)器可能會(huì)超過其本身的任務(wù)負(fù)載。一旦出現(xiàn)任務(wù)擁塞，則無法在滿足用戶時(shí)間約束的情況下得到處理結(jié)果。因此，需要部署多臺(tái)邊緣服務(wù)器，通過任務(wù)調(diào)度協(xié)作處理無人機(jī)所請(qǐng)求的大量計(jì)算任務(wù)。

在MEC環(huán)境中，任務(wù)調(diào)度是一項(xiàng)關(guān)鍵技術(shù)，通過將任務(wù)分配給不同的邊緣服務(wù)器進(jìn)行處理，可以減少任務(wù)的響應(yīng)時(shí)間，從而優(yōu)化用戶服務(wù)質(zhì)量(Quality of Service,QoS)。當(dāng)前存在很多MEC環(huán)境下任務(wù)調(diào)度的研究。文獻(xiàn)[9]提出一種用于車輛行駛過程中的邊緣計(jì)算框架，以提高車輛的計(jì)算能力，基于蟻群優(yōu)化的調(diào)度算法有效地進(jìn)行任務(wù)調(diào)度，優(yōu)化時(shí)間延遲。文獻(xiàn)[10]利用時(shí)分多址協(xié)議將全部或部分任務(wù)卸載到邊緣服務(wù)器，基于時(shí)間約束優(yōu)化終端設(shè)備能耗。文獻(xiàn)[11]在移動(dòng)邊緣環(huán)境下建立了最小化系統(tǒng)計(jì)算開銷的卸載與任務(wù)調(diào)度聯(lián)合優(yōu)化問題，提出了通過迭代求解兩個(gè)子問題的聯(lián)合優(yōu)化算法(algorithm of Joint Offloading decision, Bandwidth, and Computation resource Allocation ，JOBCA)。文獻(xiàn)[12]提出用戶移動(dòng)條件下的任務(wù)調(diào)度問題，并提出一種基于遺傳算法的分布式資源優(yōu)化算法。然而，大多數(shù)研究聚焦于在網(wǎng)絡(luò)環(huán)境穩(wěn)定的場(chǎng)景中進(jìn)行任務(wù)調(diào)度，忽視了現(xiàn)實(shí)場(chǎng)景中網(wǎng)絡(luò)環(huán)境往往存在波動(dòng)。此外，它們沒有考慮不同邊緣服務(wù)器的計(jì)算負(fù)載問題。由于邊緣服務(wù)器更貼近于終端用戶，呈現(xiàn)出分布式的特點(diǎn)，因此各個(gè)邊緣節(jié)點(diǎn)存在計(jì)算能力、容量、帶寬等差異，需要綜合考慮進(jìn)行任務(wù)調(diào)度。

針對(duì)上述問題，本文針對(duì)無人機(jī)物流場(chǎng)景構(gòu)建了漸進(jìn)式任務(wù)調(diào)度模型，并基于移動(dòng)邊緣計(jì)算環(huán)境設(shè)計(jì)了端邊協(xié)同的并行任務(wù)處理框架。同時(shí)，針對(duì)上述模型和框架對(duì)現(xiàn)有的移動(dòng)邊緣計(jì)算中的調(diào)度算法進(jìn)行優(yōu)化和改進(jìn)，改進(jìn)后的調(diào)度算法除了能夠在端邊協(xié)同的并行任務(wù)處理框架下充分降低任務(wù)的時(shí)延，還考慮了邊緣服務(wù)器和終端設(shè)備之間的網(wǎng)絡(luò)波動(dòng)情況，以及邊緣服務(wù)器自身的計(jì)算負(fù)載，相比傳統(tǒng)的調(diào)度算法具有良好的穩(wěn)定性。

1 端邊協(xié)同的并行任務(wù)調(diào)度模型

1.1 漸進(jìn)式任務(wù)調(diào)度模型

在傳統(tǒng)云計(jì)算環(huán)境中，無人機(jī)需要將拍攝的全部視頻流數(shù)據(jù)上傳到云服務(wù)器進(jìn)行處理，最后將結(jié)果反饋到終端設(shè)備上。但是由于傳輸時(shí)延較高，可能存在不可知的網(wǎng)絡(luò)波動(dòng)，無法滿足收貨場(chǎng)景中復(fù)雜任務(wù)的實(shí)時(shí)性要求。本文基于移動(dòng)邊緣計(jì)算環(huán)境提出了漸進(jìn)式任務(wù)調(diào)度模型。復(fù)雜任務(wù)的傳輸和處理流程建模如圖1所示。

無人機(jī)將拍攝的視頻流逐幀處理，首先采用基于YOLO-V3tiny的目標(biāo)檢測(cè)算法[13]，快速篩選出含有人的視頻幀，并采用圖像分割算法去除冗余信息，將其中包含人的部分提取出來。上述流程稱為視頻流在無人機(jī)上的預(yù)處理過程。通過對(duì)視頻幀的初步篩選，可以大大降低數(shù)據(jù)的冗余度，減少任務(wù)的數(shù)據(jù)傳輸量和處理時(shí)間。最后，采用姿勢(shì)識(shí)別[14]和人臉識(shí)別(網(wǎng)址參考：https://github.com/ageitgey/face_recognition/)對(duì)包含人的圖片進(jìn)行進(jìn)一步識(shí)別，以定位目標(biāo)收貨人。而由于姿勢(shì)識(shí)別和人臉識(shí)別是資源密集型的計(jì)算任務(wù)，需要將其卸載到邊緣服務(wù)器上執(zhí)行?？紤]到不同邊緣服務(wù)器的計(jì)算負(fù)載以及未知的網(wǎng)絡(luò)波動(dòng)，需要做出合理的調(diào)度決策。

本文基于移動(dòng)邊緣計(jì)算環(huán)境提出的漸進(jìn)式任務(wù)調(diào)度模型，可以不斷地將無人機(jī)中已經(jīng)預(yù)處理完成的任務(wù)按照一定的調(diào)度算法調(diào)度到指定的邊緣服務(wù)器執(zhí)行。雖然邊緣服務(wù)器具備更多的計(jì)算資源，可以執(zhí)行復(fù)雜的深度學(xué)習(xí)算法，但是相對(duì)于云服務(wù)器，邊緣服務(wù)器的計(jì)算資源有限，不能同時(shí)處理全部任務(wù)，后到的任務(wù)需要在就緒隊(duì)列中等待。等到邊緣服務(wù)器有足夠的計(jì)算資源時(shí)，隊(duì)列中的任務(wù)才能再進(jìn)入邊緣服務(wù)器執(zhí)行。

在實(shí)際的無人機(jī)送貨場(chǎng)景中，無人機(jī)首先對(duì)拍攝的視頻流進(jìn)行預(yù)處理。這些計(jì)算任務(wù)在經(jīng)過預(yù)處理后按照一定的調(diào)度算法調(diào)度到邊緣服務(wù)器中執(zhí)行，經(jīng)過姿勢(shì)識(shí)別和人臉識(shí)別確認(rèn)和定位目標(biāo)收貨人，并將信息實(shí)時(shí)反饋給無人機(jī)。

1.2 端邊協(xié)同的并行任務(wù)處理框架

為了降低任務(wù)處理時(shí)延，提高無人機(jī)的配送效率，本文基于1.1節(jié)提出的漸進(jìn)式任務(wù)調(diào)度模型，構(gòu)建了一個(gè)基于端邊協(xié)同的并行任務(wù)處理框架，如圖2所示。這里的“并行”主要體現(xiàn)在以下兩方面：

(1) 多邊緣服務(wù)器并行處理任務(wù) 相比于傳統(tǒng)的串行計(jì)算架構(gòu)，多個(gè)邊緣服務(wù)器能夠并行處理來自無人機(jī)的計(jì)算任務(wù)。在實(shí)際的收貨場(chǎng)景中，一旦出現(xiàn)了收貨人，在某一小段視頻流的連續(xù)的若干幀中都能夠通過人臉識(shí)別算法判斷出收貨人。根據(jù)并行任務(wù)處理的特點(diǎn)，由這若干幀所形成的任務(wù)就會(huì)被卸載調(diào)度到就近的若干邊緣服務(wù)器中。從整個(gè)網(wǎng)絡(luò)環(huán)境來看，多個(gè)任務(wù)在若干邊緣服務(wù)器中并行執(zhí)行，相比多個(gè)任務(wù)只在單個(gè)邊緣服務(wù)器中執(zhí)行具有更高的系統(tǒng)效率，邊緣服務(wù)器之間的協(xié)同計(jì)算也能夠充分降低任務(wù)的處理時(shí)延。

(2)多個(gè)任務(wù)在邊緣服務(wù)器內(nèi)并行處理 雖然邊緣服務(wù)器的計(jì)算資源有限，但是可以在考慮任務(wù)負(fù)載的前提下，在同一邊緣設(shè)備內(nèi)并行處理多個(gè)計(jì)算任務(wù)。在傳統(tǒng)的串行任務(wù)計(jì)算架構(gòu)中，邊緣設(shè)備雖然只需保證其計(jì)算資源大于所有任務(wù)的最大負(fù)載，但并不是所有的任務(wù)都能達(dá)到邊緣設(shè)備的最大負(fù)載，這將導(dǎo)致計(jì)算資源剩余、利用率不高的問題。而將這些任務(wù)并行處理，雖然可能會(huì)降低每個(gè)任務(wù)的處理速率，但是基本不會(huì)出現(xiàn)計(jì)算資源剩余，從而能夠大大提高計(jì)算資源的利用率，任務(wù)處理速率自然也會(huì)隨之提高，整個(gè)端邊協(xié)同的并行任務(wù)處理框架就能夠有效地降低時(shí)延，提高定位收貨人的速度。

1.3 任務(wù)處理時(shí)延建模

根據(jù)1.1節(jié)中設(shè)計(jì)的漸進(jìn)式任務(wù)調(diào)度模型和1.2節(jié)中構(gòu)建的端邊協(xié)同的任務(wù)處理框架，下面給出任務(wù)處理總時(shí)延的計(jì)算方式，并對(duì)一些量進(jìn)行定義和說明。

根據(jù)1.2節(jié)提出的端邊協(xié)同的并行任務(wù)處理框架，考慮在無人機(jī)最后一公里配送場(chǎng)景中，有m架無人機(jī)Ui,i∈[1,m]，以及n臺(tái)邊緣服務(wù)器Ej,j∈[1,n]。假設(shè)在給定視頻幀數(shù)的情況下，整個(gè)端邊協(xié)同的并行任務(wù)處理框架中將產(chǎn)生N個(gè)任務(wù)?，F(xiàn)在考慮這些任務(wù)中的第t個(gè)任務(wù)(t∈[1,N])。需要通過定義一些指標(biāo)及其計(jì)算方式，來度量該任務(wù)處理總時(shí)延。根據(jù)1.1節(jié)中介紹的漸進(jìn)式任務(wù)調(diào)度模型，一個(gè)計(jì)算任務(wù)的執(zhí)行總時(shí)間主要由以下5部分構(gòu)成：任務(wù)在無人機(jī)中的預(yù)處理所花費(fèi)的時(shí)間Tuav、任務(wù)預(yù)處理完成在發(fā)送隊(duì)列中等待到卸載所經(jīng)過的時(shí)間Toffload、任務(wù)的傳輸時(shí)延Ttrans、任務(wù)卸載到邊緣服務(wù)器進(jìn)入就緒隊(duì)列后的等待時(shí)間Tready以及任務(wù)在邊緣服務(wù)器執(zhí)行的時(shí)間Tedge。于是，第t個(gè)任務(wù)的處理總時(shí)延為：

(1)

(2)

式中:Ft表示任務(wù)t所包含的圖片對(duì)應(yīng)的原始視頻幀的數(shù)據(jù)大小,它是根據(jù)原始視頻的分辨率換算成像素，然后按照每個(gè)像素3通道，每像素每通道1字節(jié)的方式進(jìn)行計(jì)算;fuav表示無人機(jī)的處理速率。

同理，在式(1)中，第t個(gè)任務(wù)在邊緣服務(wù)器執(zhí)行的時(shí)間也需要按照類似的公式計(jì)算：

(3)

式中：Ct表示任務(wù)t的計(jì)算量；fedge表示邊緣服務(wù)器的處理速率。

在式(1)中，第t個(gè)任務(wù)的傳輸時(shí)延具體表示如下：

(4)

式中：dt表示第t個(gè)任務(wù)的數(shù)據(jù)大小，即原始視頻幀經(jīng)過預(yù)處理后所得圖片的數(shù)據(jù)大小；B表示帶寬。

2 基于最短響應(yīng)時(shí)間優(yōu)先改進(jìn)的任務(wù)調(diào)度算法

為了滿足無人機(jī)最后一公里配送場(chǎng)景的實(shí)時(shí)性需求，第1章給出了漸進(jìn)式任務(wù)調(diào)度模型，設(shè)計(jì)了端邊協(xié)同的并行任務(wù)處理框架。然而，多邊緣服務(wù)器的協(xié)同與多任務(wù)并行處理帶來了新的挑戰(zhàn)，增加了網(wǎng)絡(luò)的不確定性。因此，傳統(tǒng)的移動(dòng)邊緣計(jì)算環(huán)境中的任務(wù)調(diào)度算法可能因?yàn)榫W(wǎng)絡(luò)的波動(dòng)而變得不穩(wěn)定。為此，本文參考移動(dòng)邊緣計(jì)算環(huán)境中SSLF調(diào)度算法[15]，并針對(duì)該算法優(yōu)化了預(yù)計(jì)響應(yīng)時(shí)間的更新策略，設(shè)計(jì)了改進(jìn)后的α-SSLF調(diào)度算法。

(5)

SSLF調(diào)度算法每次在進(jìn)行任務(wù)調(diào)度時(shí)會(huì)查找卸載該任務(wù)的無人機(jī)Ui，根據(jù)表P中的向量Pi，找到預(yù)計(jì)響應(yīng)時(shí)間最小的邊緣服務(wù)器Ej，將任務(wù)調(diào)度到該邊緣服務(wù)器上。

然而，在實(shí)際的網(wǎng)絡(luò)環(huán)境中，因?yàn)橐恍┎淮_定的因素會(huì)導(dǎo)致網(wǎng)絡(luò)的波動(dòng)，頻繁的、劇烈的網(wǎng)絡(luò)波動(dòng)會(huì)破壞SSLF調(diào)度算法的穩(wěn)定性。為了防止極個(gè)別任務(wù)的處理時(shí)延過大或者過小而導(dǎo)致表T頻繁地更新，本文引入?yún)?shù)α，在更新預(yù)計(jì)響應(yīng)時(shí)間的同時(shí)兼顧表T中原來的預(yù)計(jì)響應(yīng)時(shí)間。

(6)

式中α是一個(gè)給定的值，α∈[0,1)。當(dāng)α=0時(shí)，表示直接根據(jù)當(dāng)前已經(jīng)完成的任務(wù)的響應(yīng)時(shí)間更新預(yù)計(jì)響應(yīng)時(shí)間，這與傳統(tǒng)的SSLF調(diào)度算法一致。α越小，表示新的預(yù)計(jì)響應(yīng)時(shí)間受當(dāng)前已經(jīng)完成的任務(wù)的響應(yīng)時(shí)間影響越大，而受原來的預(yù)計(jì)響應(yīng)時(shí)間影響越??；α越大，則反之。

改進(jìn)后的預(yù)計(jì)響應(yīng)時(shí)間更新策略如下：

算法1改進(jìn)后的預(yù)計(jì)響應(yīng)時(shí)間更新策略。

輸入:預(yù)計(jì)響應(yīng)時(shí)間表P，當(dāng)前任務(wù)t，參數(shù)α;

輸出:更新后的預(yù)計(jì)響應(yīng)時(shí)間表P。

1 Tresp=當(dāng)前任務(wù)t的響應(yīng)時(shí)間

2 Ui當(dāng)前任務(wù)所屬的無人機(jī)

3 Ej=當(dāng)前任務(wù)調(diào)度到的邊緣服務(wù)器

5 returnP

與SSLF調(diào)度算法一樣，α-SSLF調(diào)度算法每次也按照相同的規(guī)則找到向量Ti，進(jìn)而找到預(yù)計(jì)完成時(shí)間最小的邊緣服務(wù)器并將任務(wù)調(diào)度到該邊緣服務(wù)器上。與SSLF調(diào)度算法不同的是，α-SSLF調(diào)度算法在更新和維護(hù)表P時(shí)，需要按照式(6)進(jìn)行更新。改進(jìn)后的α-SSLF調(diào)度算法如下所示：

算法2改進(jìn)后的α-SSLF調(diào)度算法。

輸入:預(yù)計(jì)響應(yīng)時(shí)間表P，當(dāng)前任務(wù)t;

輸出: 當(dāng)前任務(wù)調(diào)度到的邊緣服務(wù)器Ej。

1 Ui=當(dāng)前任務(wù)t所屬的無人機(jī)

2 j=find_min_index(Pi)

3 returnEj

新引入的參數(shù)α既反映了網(wǎng)絡(luò)的實(shí)時(shí)性，又保證了調(diào)度算法的穩(wěn)定性。改進(jìn)后的預(yù)計(jì)響應(yīng)時(shí)間更新策略兼顧了預(yù)計(jì)響應(yīng)時(shí)間表P原來的值，避免了因突然的、劇烈的網(wǎng)絡(luò)波動(dòng)而引起的表P的頻繁更新，使得α-SSLF調(diào)度算法相比于傳統(tǒng)的SSLF調(diào)度算法具有更好的穩(wěn)定性。實(shí)際上，當(dāng)網(wǎng)絡(luò)狀況不佳且持續(xù)了一段時(shí)間時(shí)，傳統(tǒng)的SSLF調(diào)度算法和α-SSLF調(diào)度算法的更新策略都可以讓表P的相應(yīng)數(shù)值增大，進(jìn)而迫使調(diào)度算法改變調(diào)度策略。而當(dāng)網(wǎng)絡(luò)狀況不佳僅只有一瞬間時(shí)，傳統(tǒng)的SSLF調(diào)度算法會(huì)立刻改變調(diào)度策略，而α-SSLF調(diào)度算法并不會(huì)立刻改變調(diào)度策略，而是可能會(huì)再等待一小段時(shí)間確認(rèn)當(dāng)前網(wǎng)絡(luò)狀況是突然的波動(dòng)還是持續(xù)的不佳。因此，改進(jìn)后的α-SSLF調(diào)度算法具有很好的穩(wěn)定性，可以避免因網(wǎng)絡(luò)的短暫波動(dòng)作出錯(cuò)誤的調(diào)度決策。

3 實(shí)驗(yàn)和結(jié)果分析

本文提出的基于端邊協(xié)同的并行任務(wù)處理框架能夠充分降低任務(wù)的處理時(shí)延。通過改進(jìn)SSLF算法，綜合考慮了網(wǎng)絡(luò)波動(dòng)的影響，可以在無人機(jī)最后一公里配送場(chǎng)景中找到最優(yōu)的任務(wù)調(diào)度方案。本章首先描述了實(shí)驗(yàn)的仿真環(huán)境和參數(shù)設(shè)置，然后對(duì)比了傳統(tǒng)的串行任務(wù)處理框架和本文提出的基于端邊協(xié)同的并行任務(wù)處理框架在任務(wù)處理時(shí)延方面的優(yōu)劣，證明了并行任務(wù)處理架構(gòu)在任務(wù)處理時(shí)延方面的優(yōu)越性。最后，在端邊協(xié)同的并行任務(wù)處理框架中，對(duì)比了傳統(tǒng)的SSLF調(diào)度算法和改進(jìn)的α-SSLF調(diào)度算法，從任務(wù)處理平均時(shí)延和最大時(shí)延兩個(gè)方面進(jìn)行了綜合評(píng)價(jià)。實(shí)驗(yàn)證明，當(dāng)參數(shù)α取得合適的值時(shí)，本文提出的α-SSLF調(diào)度算法可以取得顯著的效果。

3.1 實(shí)驗(yàn)環(huán)境及參數(shù)設(shè)置

本文仿真實(shí)驗(yàn)均運(yùn)行于PyCharm 2020.1 Version，Python3.6環(huán)境。硬件參數(shù)為IntelCorei5-6200 2.40 GHz CPU，12 GB RAM。實(shí)驗(yàn)所采用的視頻流通過大疆無人機(jī)在安徽大學(xué)校園內(nèi)拍攝，并且指定其分辨率分別為360 p、480 p、720 p和1 080 p。針對(duì)每一種分辨率的視頻流，截取其100幀、200幀、300幀和400幀分別作為仿真實(shí)驗(yàn)中無人機(jī)的輸入。根據(jù)第2章提出的α-SSLF調(diào)度算法，α的取值集合為{0,0.25,0.375,0.5,0.625,0.75}。仿真實(shí)驗(yàn)的網(wǎng)絡(luò)環(huán)境為100 Mbps帶寬，實(shí)時(shí)的數(shù)據(jù)率為小于100 Mbps，并且服從正態(tài)分布的隨機(jī)值[16]。

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

為了證明本文提出的漸進(jìn)式任務(wù)調(diào)度模型和端邊協(xié)同的并行任務(wù)處理框架可以充分降低時(shí)延，提高無人機(jī)配送效率，本節(jié)首先對(duì)比了傳統(tǒng)的串行任務(wù)處理架構(gòu)和端邊協(xié)同的并行任務(wù)處理架構(gòu)在任務(wù)處理總時(shí)延方面的優(yōu)劣，證明了并行任務(wù)處理架構(gòu)在任務(wù)處理時(shí)延方面的優(yōu)越性。本節(jié)還對(duì)比了傳統(tǒng)的SSLF調(diào)度算法和改進(jìn)的α-SSLF調(diào)度算法。結(jié)果表明，參數(shù)α取得一定的值時(shí)，改進(jìn)的α-SSLF調(diào)度算法在降低任務(wù)處理時(shí)延的同時(shí)，可以有效地防止短暫的網(wǎng)絡(luò)波動(dòng)帶來的影響。

第一部分實(shí)驗(yàn)按照視頻流的分辨率分組，并采用傳統(tǒng)的SSLF調(diào)度算法，對(duì)比在視頻幀數(shù)不斷增大的情況下，傳統(tǒng)的串行任務(wù)處理框架和本文提出的端邊協(xié)同的并行任務(wù)處理框架的優(yōu)劣。該部分實(shí)驗(yàn)針對(duì)單架無人機(jī)Ui,i∈[1,m]，測(cè)量其從開始預(yù)處理一段給定長(zhǎng)度的連續(xù)視頻幀到周圍所有邊緣服務(wù)器{Ej|j∈[1,n]}都處理完因其產(chǎn)生的任務(wù)所經(jīng)過的總時(shí)間，將之作為該部分實(shí)驗(yàn)的評(píng)價(jià)指標(biāo)。根據(jù)傳統(tǒng)的串行任務(wù)處理框架的特點(diǎn)，該部分實(shí)驗(yàn)設(shè)置整個(gè)移動(dòng)邊緣計(jì)算環(huán)境只有一臺(tái)邊緣設(shè)備，并且不支持多任務(wù)的并行執(zhí)行。而根據(jù)本文提出的端邊協(xié)同的并行任務(wù)處理框架的特點(diǎn)，該部分實(shí)驗(yàn)設(shè)置移動(dòng)邊緣計(jì)算環(huán)境中存在4臺(tái)邊緣設(shè)備，且其中2臺(tái)邊緣設(shè)備的最大負(fù)載為同時(shí)執(zhí)行4個(gè)計(jì)算任務(wù)，另外2臺(tái)邊緣設(shè)備的最大負(fù)載為同時(shí)執(zhí)行3個(gè)計(jì)算任務(wù)。

實(shí)驗(yàn)結(jié)果如圖3所示，可以看到，本文提出的端邊協(xié)同的并行任務(wù)處理框架在不同幀數(shù)和不同清晰度的情況下，效果均優(yōu)于傳統(tǒng)的串行任務(wù)處理框架，可以減少約20%左右的處理時(shí)延。分辨率較小的360 p因其原始視頻幀數(shù)據(jù)量小，最終兩種計(jì)算架構(gòu)的處理總時(shí)延相差并不大，總時(shí)延平均相差14.38%。而分辨率較大的1 080 p因其原始視頻幀數(shù)據(jù)量龐大，基于端邊協(xié)同的并行任務(wù)處理框架的優(yōu)勢(shì)更為明顯，總時(shí)延平均相差33.91%。因此，相比于傳統(tǒng)的任務(wù)并行計(jì)算架構(gòu)，本文提出的基于端邊協(xié)同的并行任務(wù)處理框架能夠有效地降低一段視頻流產(chǎn)生的任務(wù)處理總時(shí)延，并且視頻流的幀數(shù)和分辨率越高時(shí)，效果越明顯。

第二部分實(shí)驗(yàn)探究α的取值對(duì)本文提出的改進(jìn)的α-SSLF調(diào)度算法在端邊協(xié)同的并行任務(wù)處理架構(gòu)中對(duì)任務(wù)處理時(shí)延的影響。實(shí)驗(yàn)首先給定視頻流的幀數(shù)為100，改變視頻流的分辨率，對(duì)比α不同取值下的任務(wù)處理時(shí)延的優(yōu)劣；其次給定視頻流的分辨率為1 080 p，改變視頻流的幀數(shù)，對(duì)比α不同取值下的任務(wù)處理時(shí)延的優(yōu)劣。

實(shí)驗(yàn)需要用到所有任務(wù)處理總時(shí)延的最大值和所有任務(wù)處理總時(shí)延的平均值兩個(gè)評(píng)價(jià)指標(biāo)。根據(jù)木桶效應(yīng)，一段給定長(zhǎng)度的連續(xù)的視頻幀的處理時(shí)延很大程度上取決于其產(chǎn)生的所有計(jì)算任務(wù)中處理時(shí)延最大的任務(wù)。因此，所有計(jì)算任務(wù)的最大處理時(shí)延是一個(gè)有價(jià)值的評(píng)價(jià)指標(biāo)。而在實(shí)際的無人機(jī)最后一公里配送場(chǎng)景中，并不是所有的任務(wù)最終都能夠識(shí)別到收貨人姿勢(shì)，進(jìn)而校驗(yàn)其人臉。換言之，很大一部分計(jì)算任務(wù)因?yàn)闆]能識(shí)別出收貨人的姿勢(shì)而被丟棄。因此，所有計(jì)算任務(wù)的平均處理時(shí)延也同樣重要，這更能夠反映出整個(gè)系統(tǒng)的任務(wù)執(zhí)行效率。

當(dāng)視頻流的幀數(shù)不變時(shí)(均為100幀)，改變視頻流的分辨率，在α取不同值時(shí)平均任務(wù)處理總時(shí)延和最大任務(wù)處理總時(shí)延如圖4所示。僅從平均任務(wù)處理總時(shí)延來看，當(dāng)α=0.5時(shí)，平均任務(wù)處理總時(shí)延較優(yōu)。僅從最大任務(wù)處理總時(shí)延來看，當(dāng)α=0.5時(shí)，最大任務(wù)處理總時(shí)延較優(yōu)。雖然平均任務(wù)處理總時(shí)延和最大任務(wù)處理總時(shí)延并不只有一個(gè)最優(yōu)點(diǎn)，但綜合兩種指標(biāo)來看，當(dāng)α=0.5時(shí)，對(duì)于不同分辨率的視頻流都能有較好的降低時(shí)延的效果。

從任務(wù)處理總時(shí)延的平均值的大小來看，α取不同值時(shí)，其極差大約在10～50 ms。同理，從任務(wù)處理總時(shí)延的最大值的大小來看，α取不同值時(shí)，其極差大約在10～20 ms。在實(shí)際的無人機(jī)最后一公里收貨場(chǎng)景中，對(duì)收貨人的快速定位是整個(gè)系統(tǒng)所要實(shí)現(xiàn)的首要目標(biāo)。在一個(gè)計(jì)算任務(wù)中，平均能夠優(yōu)化10～50 ms的處理時(shí)延，最大的處理時(shí)延也能優(yōu)化10～20 ms，這對(duì)需要執(zhí)行大量計(jì)算任務(wù)的整個(gè)系統(tǒng)來說至關(guān)重要。這不僅能夠提升用戶的收貨體驗(yàn)，還能夠提高整個(gè)端邊協(xié)同的系統(tǒng)工作效率。

當(dāng)視頻流的分辨率不變時(shí)(均為 1 080 p)，改變視頻流的幀數(shù)，在α取不同值時(shí)任務(wù)平均處理總時(shí)延和最大處理總時(shí)延如圖5所示。僅從平均任務(wù)處理總時(shí)延來看，當(dāng)α=0.5時(shí)，平均任務(wù)處理總時(shí)延普遍較優(yōu)；僅從最大任務(wù)處理總時(shí)延來看，雖然當(dāng)α=0.5時(shí)，最大任務(wù)處理總時(shí)延在少數(shù)情況下并不是最優(yōu)的；綜合兩種指標(biāo)來看，當(dāng)α=0.5時(shí)，對(duì)于不同幀數(shù)的視頻流都能有較好的降低時(shí)延的效果。

綜上所述，本文提出的基于端邊協(xié)同的多邊緣服務(wù)器并行任務(wù)處理框架在處理時(shí)延上優(yōu)于傳統(tǒng)的串行任務(wù)處理框架，在此基礎(chǔ)上采用改進(jìn)后的SSLF調(diào)度算法在α=0.5時(shí)可以在確保算法穩(wěn)定的前提下充分降低任務(wù)處理時(shí)延，提高無人機(jī)配送效率。

4 結(jié)束語

本文研究了基于MEC的無人機(jī)最后一公里配送場(chǎng)景中復(fù)雜任務(wù)的調(diào)度問題，構(gòu)建了端邊協(xié)同的并行任務(wù)處理框架來模擬任務(wù)調(diào)度的執(zhí)行過程，包括計(jì)算負(fù)載、傳輸時(shí)延等?？紤]到網(wǎng)絡(luò)波動(dòng)的問題，根據(jù)已有的最短響應(yīng)時(shí)延優(yōu)先(SSLF)調(diào)度算法，優(yōu)化了響應(yīng)時(shí)延的更新策略，解決了因網(wǎng)絡(luò)波動(dòng)而產(chǎn)生的調(diào)度算法不穩(wěn)定的問題，可以大大減少任務(wù)的響應(yīng)時(shí)間，提高無人機(jī)配送的效率。本文在仿真的端邊協(xié)同的并行任務(wù)處理框架上進(jìn)行了實(shí)驗(yàn)，結(jié)果表明改進(jìn)后的α-SSLF算法可以有效降低任務(wù)的平均響應(yīng)時(shí)間，具有良好的穩(wěn)定性，提高整個(gè)無人機(jī)最后一公里配送系統(tǒng)的效率。

本文初步提出了基于端邊協(xié)同的并行任務(wù)處理架構(gòu)，后續(xù)還將在此基礎(chǔ)上進(jìn)一步優(yōu)化該系統(tǒng)架構(gòu)。未來將加入更多的調(diào)度算法進(jìn)行對(duì)比，并對(duì)其中效果不好的調(diào)度算法進(jìn)行優(yōu)化和改進(jìn)。另外，對(duì)于無人機(jī)配送場(chǎng)景中可能產(chǎn)生的其他實(shí)際問題也會(huì)進(jìn)一步展開研究。