基于混合蟻群優(yōu)化的邊緣計(jì)算細(xì)粒度任務(wù)調(diào)度方法

陳 剛,王志堅(jiān)

(廣州華商學(xué)院 數(shù)據(jù)科學(xué)學(xué)院,廣州 511300)

0 引言

云計(jì)算為客戶端提供了海量的可以訪問(wèn)的數(shù)據(jù)資源以及計(jì)算資源，因此每時(shí)每刻都有大量的用戶向云平臺(tái)提交任務(wù)申請(qǐng)，而云平臺(tái)也需要根據(jù)申請(qǐng)來(lái)處理這些任務(wù)。面對(duì)用戶申請(qǐng)的大規(guī)模任務(wù)，云平臺(tái)原有的網(wǎng)絡(luò)架構(gòu)出現(xiàn)了較為嚴(yán)重的時(shí)延問(wèn)題[1]。為此，近年來(lái)邊緣計(jì)算的觀點(diǎn)被提出來(lái)。邊緣計(jì)算旨在分擔(dān)云計(jì)算中心的任務(wù)處理壓力，提高服務(wù)質(zhì)量。然而，由于邊緣計(jì)算節(jié)點(diǎn)的資源和計(jì)算能力都是有限的，它只能處理少量的部分任務(wù)。面對(duì)這種情況，如何合理地將任務(wù)調(diào)度給對(duì)應(yīng)的邊緣節(jié)點(diǎn)[2]，成為了新的難題問(wèn)題。造成任務(wù)調(diào)度困難的原因有二個(gè)，一是邊緣節(jié)點(diǎn)距離云計(jì)算中心的距離不同，距離越遠(yuǎn)，任務(wù)調(diào)度所耗費(fèi)的時(shí)間和能耗就越多；二是不同任務(wù)所需要的計(jì)算資源是不同的，若是將小任務(wù)調(diào)度給計(jì)算能力很強(qiáng)的邊緣節(jié)點(diǎn)上，將造成資源浪費(fèi);反之，邊緣計(jì)算因?yàn)槟芰Σ粔颍瑢o(wú)法處理任務(wù)，服務(wù)質(zhì)量受到嚴(yán)重限制[3]。所以如何根據(jù)任務(wù)的特征以及邊緣節(jié)點(diǎn)的計(jì)算資源、距離，將任務(wù)合理地調(diào)度給合適的邊緣計(jì)算節(jié)點(diǎn)至關(guān)重要。

國(guó)內(nèi)外針對(duì)邊緣計(jì)算的任務(wù)調(diào)度都進(jìn)行相關(guān)研究。文獻(xiàn)[4]首先將計(jì)算任務(wù)描述為一個(gè)有向無(wú)環(huán)圖，然后將系統(tǒng)的延遲作為優(yōu)化目標(biāo)，并在截止期限、優(yōu)先級(jí)、節(jié)點(diǎn)完成期限等三個(gè)約束條件下，利用改進(jìn)的NSGA-Ⅱ算法求解獲取了任務(wù)卸載調(diào)度方案。文獻(xiàn)[5]以系統(tǒng)總開(kāi)銷為優(yōu)化問(wèn)題，并將其細(xì)化分為三個(gè)子問(wèn)題，以方便求解，利用自適應(yīng)遺傳算法對(duì)其逐一求解，得到綜合任務(wù)調(diào)度卸載方案。文獻(xiàn)[6]以任務(wù)滿意度最大化為目標(biāo)，將多個(gè)任務(wù)調(diào)度到邊緣服務(wù)器上配置的虛擬機(jī)上，利用深度強(qiáng)化學(xué)習(xí)解決了時(shí)間調(diào)度和資源分配的問(wèn)題。文獻(xiàn)[7]提出了一種基于煙花模型的調(diào)度方法，首先采用焰火視圖來(lái)搜索資源，以滿足任務(wù)的功能需求，然后根據(jù)任務(wù)相關(guān)性和資源對(duì)任務(wù)進(jìn)行分包，最后通過(guò)構(gòu)建三維空間距離來(lái)計(jì)算任務(wù)包與資源之間的匹配度。上述調(diào)度算法在時(shí)間延遲和調(diào)度能耗上都不是很理想，需要采用新型智能算法對(duì)邊緣計(jì)算的任務(wù)調(diào)度進(jìn)行改進(jìn)與優(yōu)化。

邊緣計(jì)算任務(wù)調(diào)度是一個(gè)大規(guī)模且復(fù)雜的問(wèn)題，單一的蟻群算法的優(yōu)化能力并不能很好地應(yīng)對(duì)，因此，本文將基礎(chǔ)蟻群算法與遺傳算法相結(jié)合，實(shí)現(xiàn)邊緣計(jì)算細(xì)粒度任務(wù)高效率調(diào)度，以期為邊緣計(jì)算任務(wù)調(diào)度問(wèn)題提供參考和借鑒。

1 邊緣計(jì)算細(xì)粒度任務(wù)調(diào)度的原理

邊緣計(jì)算細(xì)粒度任務(wù)調(diào)度屬于一種連續(xù)性問(wèn)題，使用單一的蟻群算法進(jìn)行調(diào)度，容易產(chǎn)生收斂速度慢，計(jì)算時(shí)間長(zhǎng)，易于過(guò)早陷入局部最優(yōu)的問(wèn)題。為此，本文引入遺傳算法，構(gòu)建混合蟻群算法對(duì)細(xì)粒度任務(wù)調(diào)度進(jìn)行優(yōu)化，解決單一蟻群算法易于過(guò)早陷入局部最優(yōu)的問(wèn)題，提高邊緣計(jì)算細(xì)粒度任務(wù)調(diào)度性能，具體描述如下。

1.1 問(wèn)題描述

邊緣計(jì)算任務(wù)調(diào)度是指將原本應(yīng)由本地服務(wù)器或中心云端處理的任務(wù)合理地分配給網(wǎng)絡(luò)邊緣端的服務(wù)器節(jié)點(diǎn)，以緩解本地服務(wù)器或中心云端的任務(wù)處理壓力，減少任務(wù)處理延遲[8-9]。邊緣計(jì)算任務(wù)調(diào)度傳統(tǒng)模型如圖1所示，本文邊緣計(jì)算細(xì)粒度任務(wù)調(diào)度模型如圖2所示。本文調(diào)度模型分為底部的終端設(shè)備層和上端的邊緣層。終端設(shè)備層主要包括客戶端中用到的手機(jī)、平板電腦等，其中一部分會(huì)產(chǎn)生計(jì)算密集型任務(wù)，這些任務(wù)無(wú)法在本機(jī)設(shè)備提供的資源下完成任務(wù)，需要為其制定合理的調(diào)度策略將任務(wù)遷移到合適的地方，可以在滿足任務(wù)時(shí)延要求的情況下完成任務(wù)。終端設(shè)備層的另一部分設(shè)備由沒(méi)有任務(wù)處理的閑置終端用戶組成。在某些時(shí)刻其CPU處于閑置狀態(tài)，可以為其他CPU過(guò)載的終端用戶提供計(jì)算資源。

圖1 移動(dòng)計(jì)算任務(wù)調(diào)度的傳統(tǒng)模型

圖2 現(xiàn)代移動(dòng)邊緣計(jì)算任務(wù)調(diào)度模型

由圖2可知，每個(gè)邊緣服務(wù)器都帶有一個(gè)基站，其作用是接收發(fā)送過(guò)來(lái)的任務(wù)，當(dāng)任務(wù)處理完成后再將處理結(jié)果通過(guò)基站發(fā)送給移動(dòng)用戶，完成任務(wù)調(diào)度[10]。

1.2 移動(dòng)邊緣計(jì)算任務(wù)調(diào)度的總體架構(gòu)

移動(dòng)邊緣計(jì)算是一種新型移動(dòng)通信網(wǎng)絡(luò)技術(shù)，在移動(dòng)網(wǎng)絡(luò)邊緣提供網(wǎng)絡(luò)環(huán)境，將網(wǎng)絡(luò)大量的任務(wù)進(jìn)行緩存，該技術(shù)可以處理比較復(fù)雜的網(wǎng)絡(luò)邊緣任務(wù)，移動(dòng)邊緣計(jì)算具有較好的任務(wù)計(jì)算能力，可以分析、處理海量網(wǎng)絡(luò)任務(wù)。該移動(dòng)邊緣計(jì)算節(jié)點(diǎn)在地理位置方面與信息源比較接近，用戶發(fā)送請(qǐng)求時(shí)，網(wǎng)絡(luò)能快速響應(yīng)用戶的請(qǐng)求，極大地減小了響應(yīng)的時(shí)延，使網(wǎng)絡(luò)中的數(shù)據(jù)傳輸網(wǎng)和核心網(wǎng)絡(luò)不會(huì)發(fā)生網(wǎng)絡(luò)擁塞，移動(dòng)邊緣計(jì)算技術(shù)還可以實(shí)時(shí)獲取各大網(wǎng)絡(luò)基站ID、用戶的網(wǎng)絡(luò)數(shù)據(jù)、用戶請(qǐng)求等信息，對(duì)網(wǎng)絡(luò)中的鏈路可進(jìn)行有效的感知自適應(yīng)，為用戶在網(wǎng)絡(luò)邊緣處部署位置應(yīng)用，從而提升網(wǎng)絡(luò)用戶的服務(wù)質(zhì)量。本文采用的基于移動(dòng)邊緣計(jì)算總體組成結(jié)構(gòu)如圖3所示。

圖3 基于移動(dòng)邊緣計(jì)算任務(wù)調(diào)度的總體結(jié)構(gòu)

1.3 細(xì)粒度任務(wù)調(diào)度的原理

移動(dòng)邊緣計(jì)算是將網(wǎng)絡(luò)控制、數(shù)據(jù)處理和相關(guān)存儲(chǔ)遷移到網(wǎng)絡(luò)邊緣，為覆蓋范圍內(nèi)的移動(dòng)用戶提供較好的密集型計(jì)算服務(wù)。任務(wù)調(diào)度方法就是要實(shí)現(xiàn)基站與用戶之間的互動(dòng)，在用戶密集且流動(dòng)性大的情況下實(shí)現(xiàn)任務(wù)合理分配，其多基站協(xié)同合作的示意圖如圖4所示。

圖4 移動(dòng)邊緣云服務(wù)器任務(wù)調(diào)度示意圖

移動(dòng)邊緣計(jì)算任務(wù)調(diào)度質(zhì)量取決于邊緣基站計(jì)算資源的分配。要想實(shí)現(xiàn)邊緣服務(wù)器中的資源公平合理的分配，就要對(duì)智能邊緣基站進(jìn)行研究。邊緣計(jì)算節(jié)點(diǎn)為基站調(diào)度任務(wù)時(shí)，主要考慮兩個(gè)性能指標(biāo)，分別為數(shù)據(jù)傳輸速率和任務(wù)執(zhí)行能耗。通過(guò)任務(wù)分類合理化的方式提高數(shù)據(jù)傳輸速率，將優(yōu)先級(jí)高的任務(wù)調(diào)度到邊緣基站中，優(yōu)化資源調(diào)度程序。除此之外，基站的能耗是一定有的，應(yīng)在提供能量一定的前提下，讓基站能源的總消耗小于所有任務(wù)執(zhí)行任務(wù)結(jié)束時(shí)的總和。

2 邊緣計(jì)算細(xì)粒度任務(wù)調(diào)度的設(shè)計(jì)

2.1 假設(shè)條件設(shè)置

粒度指的是根據(jù)項(xiàng)目模塊劃分的細(xì)致程度區(qū)分的標(biāo)準(zhǔn)，一個(gè)邊緣計(jì)算任務(wù)調(diào)度模塊劃分得越多，每個(gè)子模塊越小，負(fù)責(zé)的工作越細(xì)致，即所屬認(rèn)為的粒度越細(xì)，因此在調(diào)度細(xì)粒度任務(wù)時(shí)的難度和能耗比較于粗粒度任務(wù)調(diào)度更高。通常來(lái)說(shuō)，在細(xì)粒度任務(wù)調(diào)度時(shí)，其可以根據(jù)自身的需要選擇合適的邊緣節(jié)點(diǎn)進(jìn)行卸載，但是如何選擇合適的邊緣節(jié)點(diǎn)成為細(xì)粒度任務(wù)調(diào)度時(shí)的關(guān)鍵問(wèn)題[11]。按照以往的調(diào)度方案，會(huì)選擇能耗最少或者延遲時(shí)間最短作為目標(biāo)，選擇距離最短的邊緣節(jié)點(diǎn)進(jìn)行任務(wù)調(diào)度。然而，這種調(diào)度方案并沒(méi)有將邊緣節(jié)點(diǎn)的資源容量考慮在內(nèi)，會(huì)發(fā)生任務(wù)擁塞問(wèn)題，導(dǎo)致任務(wù)調(diào)度失敗，而與此同時(shí)，邊緣網(wǎng)絡(luò)中有可能存在部分邊緣服務(wù)器節(jié)點(diǎn)閑置的狀態(tài)，造成了計(jì)算資源的浪費(fèi)[12]。針對(duì)上述問(wèn)題，在任務(wù)資源調(diào)度前，需要作出幾項(xiàng)假設(shè)條件。

假設(shè)條件1：任務(wù)調(diào)度時(shí)不能只考慮一個(gè)邊緣節(jié)點(diǎn)作為調(diào)度對(duì)象；

假設(shè)條件2：邊緣節(jié)點(diǎn)的計(jì)算資源存在能源耗盡的情況；

假設(shè)條件3：邊緣網(wǎng)絡(luò)拓?fù)湟阎彝負(fù)渲忻總€(gè)服務(wù)器節(jié)點(diǎn)與本地服務(wù)器、中心云端的距離是已知的；

假設(shè)條件4：每個(gè)任務(wù)對(duì)計(jì)算資源的需求都是已知且存在差異的；

假設(shè)條件5：邊緣節(jié)點(diǎn)內(nèi)部數(shù)個(gè)虛擬機(jī)工作模式為并行；

假設(shè)條件6：任務(wù)調(diào)度過(guò)程中為連續(xù)執(zhí)行，不存在間斷執(zhí)行；

假設(shè)條件7：任務(wù)傳輸信道的信息是已知的。

2.2 任務(wù)調(diào)度順序設(shè)計(jì)

任務(wù)調(diào)度器可以獲取任務(wù)調(diào)度的優(yōu)先級(jí)，即完成任務(wù)調(diào)度順序設(shè)計(jì)工作[13]。任務(wù)調(diào)度器對(duì)任務(wù)的排序規(guī)則是通過(guò)計(jì)算任務(wù)的優(yōu)先指數(shù)，然后從大到小的順序排列待調(diào)度任務(wù)[14]。優(yōu)先指數(shù)計(jì)算公式如下：

(1)

式中，Si代表細(xì)粒度任務(wù)i的優(yōu)先指數(shù)；Ai代表細(xì)粒度任務(wù)i的飽和度；di代表相對(duì)權(quán)重比；α代表平衡指數(shù)；bi代表細(xì)粒度任務(wù)i執(zhí)行的截止時(shí)刻；ci代表細(xì)粒度任務(wù)i執(zhí)行的開(kāi)始時(shí)刻；wi代表細(xì)粒度任務(wù)i執(zhí)行價(jià)值；W代表細(xì)粒度任務(wù)總價(jià)值；ti代表細(xì)粒度任務(wù)i執(zhí)行最長(zhǎng)耗時(shí)；n代表細(xì)粒度任務(wù)數(shù)量。

基于計(jì)算出來(lái)的任務(wù)優(yōu)先指數(shù)[15]，設(shè)計(jì)出任務(wù)調(diào)度順序方案。

2.3 邊緣服務(wù)器性能特征分析

邊緣服務(wù)器受到其自身硬件資源的影響，其計(jì)算資源性能具有不同的特征，這就直接影響了對(duì)任務(wù)的處理能力[16]。為此，通過(guò)了解邊緣服務(wù)器性能特征對(duì)于細(xì)粒度任務(wù)調(diào)度至關(guān)重要，為調(diào)度可靠性和成功率判斷提供了重要依據(jù)。邊緣服務(wù)器的性能可以通過(guò)靜態(tài)指標(biāo)和動(dòng)態(tài)指標(biāo)兩類指標(biāo)表示，考慮到靜態(tài)指標(biāo)對(duì)邊緣計(jì)算細(xì)粒度任務(wù)調(diào)度性能的影響更高，因此，本文重點(diǎn)分析了邊緣服務(wù)器靜態(tài)指標(biāo)。

靜態(tài)指標(biāo)表示服務(wù)器硬件資源情況的基本性能指標(biāo)，其主要包括CPU中央處理單元的CPU頻率、計(jì)算能力等、存儲(chǔ)設(shè)備的任務(wù)數(shù)據(jù)量、任務(wù)達(dá)到率等。根據(jù)靜態(tài)指標(biāo)能夠直接明確邊緣服務(wù)器性能，為細(xì)粒度任務(wù)調(diào)度中邊緣服務(wù)器節(jié)點(diǎn)的選擇提供了重要的參考[17]。

2.4 任務(wù)調(diào)度方案設(shè)計(jì)

在上述各研究成果的基礎(chǔ)上，本章節(jié)基于混合蟻群優(yōu)化設(shè)計(jì)細(xì)粒度任務(wù)調(diào)度方案，該部分分為目標(biāo)函數(shù)構(gòu)建，約束條件設(shè)置[18]以及混合蟻群優(yōu)化算法求解三部分。

2.4.1 目標(biāo)函數(shù)構(gòu)建

細(xì)粒度任務(wù)調(diào)度旨在解決任務(wù)調(diào)度所需要的能量(能耗)以及任務(wù)調(diào)度所需要的時(shí)間(時(shí)延)兩個(gè)問(wèn)題。針對(duì)這兩個(gè)問(wèn)題，本研究中設(shè)置的目標(biāo)函數(shù)為多目標(biāo)函數(shù)[19]。函數(shù)描述如下：

minY=y1∪y2

(2)

式中，minY代表綜合目標(biāo)最小值；y1代表細(xì)粒度任務(wù)調(diào)度能耗；y2代表細(xì)粒度任務(wù)調(diào)度時(shí)延；Qi(1)、Ti(1)代表任務(wù)i在本地處理時(shí)的能耗、時(shí)延；Pi代表調(diào)度決策因子，當(dāng)?shù)扔?時(shí)，認(rèn)為任務(wù)i在本地處理，當(dāng)?shù)扔?時(shí)，任務(wù)i執(zhí)行調(diào)度處理；qij代表邊緣服務(wù)器分配因子，當(dāng)?shù)扔?時(shí)，任務(wù)i沒(méi)有被分配給邊緣服務(wù)器j進(jìn)行調(diào)度，當(dāng)?shù)扔?時(shí)，任務(wù)i被分配給邊緣服務(wù)器j進(jìn)行調(diào)度。Qi(2)、Ti(2)代表任務(wù)i在邊緣節(jié)點(diǎn)上處理的能耗、時(shí)延；m代表邊緣服務(wù)器數(shù)量[20]。

2.4.2 約束條件設(shè)置

為上述多目標(biāo)函數(shù)設(shè)置的約束條件如下。

約束條件1：細(xì)粒度任務(wù)調(diào)度時(shí)延y2小于任務(wù)最遲截止處理時(shí)間(最大時(shí)延限值)。

約束條件2：邊緣服務(wù)器性能約束，主要指的是1.4部分的靜態(tài)指標(biāo)。

約束條件3：任務(wù)只能調(diào)度到一個(gè)邊緣服務(wù)器處理，即細(xì)粒度任務(wù)調(diào)度只能在一個(gè)邊緣服務(wù)器j上完成。

3 混合蟻群算法完成細(xì)粒度任務(wù)調(diào)度實(shí)現(xiàn)

雖然基礎(chǔ)蟻群算法具有并行計(jì)算、擴(kuò)展能力好和較好全局搜索能力等優(yōu)點(diǎn)，但當(dāng)達(dá)到一定迭代次數(shù)后，會(huì)出現(xiàn)解趨于一致現(xiàn)象，使得基礎(chǔ)蟻群算法呈現(xiàn)收斂速度慢和容易陷入局部最優(yōu)解的缺點(diǎn)。本文提出的混合蟻群算法采用了遺傳算法對(duì)數(shù)據(jù)特征進(jìn)行預(yù)選擇，一定程度上克服了基礎(chǔ)蟻群算法的上述缺點(diǎn)，可以進(jìn)一步解決該問(wèn)題，提高基礎(chǔ)蟻群算法的性能，對(duì)其初始解的選擇方法和信息素更新策略進(jìn)行改進(jìn)。

混合蟻群算法是在原有蟻群算法的基礎(chǔ)上結(jié)合遺傳算法，以彌補(bǔ)基礎(chǔ)蟻群算法存在的缺陷[21]。本文先利用遺傳算法求出多目標(biāo)函數(shù)的初始解，并將其轉(zhuǎn)換為蟻群算法的初始路徑信息素分布，最后再執(zhí)行蟻群算法尋優(yōu)程序，完成進(jìn)行任務(wù)調(diào)度方案求解[22]。針對(duì)前面章節(jié)描述的目標(biāo)函數(shù)，設(shè)置相應(yīng)的約束條件后，將遺傳算法與基礎(chǔ)蟻群算法相結(jié)合構(gòu)成混合蟻群算法，求出最優(yōu)解，即任務(wù)調(diào)度方案。具體過(guò)程如圖5(a)和圖5(b)所示：

圖5 混合蟻群優(yōu)化算法求解任務(wù)調(diào)度流程

針對(duì)于圖5(a)，可以按照下面的步驟與文字進(jìn)行詳細(xì)描述。

步驟1：初始化蟻群算法，并設(shè)置相關(guān)參數(shù)；

步驟2：對(duì)邊緣計(jì)算細(xì)粒度任務(wù)調(diào)度問(wèn)題進(jìn)行編碼處理；

步驟3：定義適應(yīng)度函數(shù)；

步驟4：初始化種群；

步驟5：種群個(gè)體解碼；

步驟6：計(jì)算種群個(gè)體的適應(yīng)度函數(shù)值，篩選出優(yōu)良父代個(gè)體；

步驟7：執(zhí)行遺傳算法的操作，得到新一代群體；

步驟8：將新一代群體與父代個(gè)體進(jìn)行優(yōu)劣替換；

步驟9：得到最終子代個(gè)體(多目標(biāo)函數(shù)的初始解)；

步驟10：判斷當(dāng)前的進(jìn)化代數(shù)是否位于最小和最大進(jìn)化代數(shù)之間，且連續(xù)進(jìn)化停滯代數(shù)的進(jìn)化率大于等于最小進(jìn)化率，若滿足上述條件，則進(jìn)入下一步；否則返回步驟6；

步驟11：將初始解轉(zhuǎn)換為蟻群算法的路徑信息素值分布；

至此完成第一部分的多目標(biāo)函數(shù)求解。為了避免使用基礎(chǔ)蟻群算法陷入局部最優(yōu)，因此引入蟻群算法執(zhí)行邊緣計(jì)算細(xì)粒度任務(wù)調(diào)度尋優(yōu)程序，具體流程如圖5(b)，可以按照下面的步驟與文字進(jìn)行詳細(xì)描述。

步驟1：將m只螞蟻(任務(wù))任意放置在n個(gè)邊緣服務(wù)器節(jié)點(diǎn)上；

步驟2：計(jì)算每只螞蟻的t時(shí)刻的轉(zhuǎn)移概率；

步驟3：根據(jù)轉(zhuǎn)移概率選擇下一個(gè)邊緣計(jì)算細(xì)粒度任務(wù)調(diào)度的邊緣服務(wù)器節(jié)點(diǎn)；

步驟4：更新被選邊緣服務(wù)器節(jié)點(diǎn)的信息素，并將該節(jié)點(diǎn)加入到禁忌表中；

步驟5：當(dāng)每一只螞蟻均找到一個(gè)邊緣服務(wù)器節(jié)點(diǎn)方案后，更新邊緣服務(wù)器節(jié)點(diǎn)的信息素；

步驟6：更新全局信息，清空禁忌表；

步驟7：判斷是否達(dá)到最大循環(huán)次數(shù)[23]，若是，輸出邊緣計(jì)算細(xì)粒度任務(wù)調(diào)度方案；否則，回到步驟1，直至達(dá)到最大循環(huán)次數(shù)。至此完成基于混合蟻群優(yōu)化的邊緣計(jì)算細(xì)粒度任務(wù)調(diào)度。

4 仿真測(cè)試與分析

4.1 仿真測(cè)試參數(shù)設(shè)置

在Intel Corei7 CPU@2.80 GHz，NVIDIA Ge G Force GTX1050Ti 和8GB RAM 配置的工作站中進(jìn)行調(diào)度仿真測(cè)試。

目標(biāo)工作站在圖2的調(diào)度模型中完成細(xì)粒度任務(wù)調(diào)度，此次測(cè)試的應(yīng)用場(chǎng)景為某地區(qū)的交通視頻監(jiān)控。使用邊緣計(jì)算可以讓服務(wù)器能夠在網(wǎng)絡(luò)邊緣完成對(duì)視頻流的采集、壓縮、存儲(chǔ)、檢測(cè)、顯示以及最終的控制等整個(gè)監(jiān)控流程，同時(shí)可以解決核心網(wǎng)壓力過(guò)大無(wú)法對(duì)其及時(shí)轉(zhuǎn)發(fā)而造成不連續(xù)等問(wèn)題。

考慮到移動(dòng)性是邊緣計(jì)算服務(wù)器的固有屬性。當(dāng)用戶在小區(qū)間切換時(shí)，可能會(huì)導(dǎo)致服務(wù)器的切換，而且不同服務(wù)器的屬性與配置也存在差異，因此本文通過(guò)邊緣計(jì)算系統(tǒng)與歸屬位置寄存器的配合實(shí)現(xiàn)移動(dòng)性管理。

具體測(cè)試參數(shù)如表1所示。

表1 仿真試驗(yàn)參數(shù)表

4.2 細(xì)粒度任務(wù)優(yōu)先指數(shù)計(jì)算

按照公式(1)計(jì)算100個(gè)細(xì)粒度任務(wù)的優(yōu)先指數(shù)，并組成任務(wù)調(diào)度隊(duì)列。其中，前20個(gè)任務(wù)的優(yōu)先指數(shù)如表2所示。

4.3 混合蟻群算法參數(shù)設(shè)置

在表1所示的參數(shù)下，利用文章提出的混合蟻群算法對(duì)1 000個(gè)細(xì)粒度任務(wù)進(jìn)行調(diào)度，測(cè)試其收斂性能。該測(cè)試通過(guò)適應(yīng)度函數(shù)最優(yōu)值體現(xiàn)，適應(yīng)度函數(shù)越快達(dá)到最低點(diǎn)，表明算法性能更好，測(cè)試結(jié)果如圖6所示。

圖6 算法收斂速度測(cè)試

由圖6可知，本文方法適應(yīng)度函數(shù)值在迭代次數(shù)為200次時(shí)達(dá)到最低點(diǎn)，即此時(shí)本文方法實(shí)現(xiàn)收斂。表明本文方法細(xì)粒度任務(wù)調(diào)度能力較強(qiáng)，能夠有效提高細(xì)粒度任務(wù)調(diào)度的可靠性。此時(shí)混合蟻群算法的參數(shù)情況如表3所示。

表2 前20個(gè)細(xì)粒度任務(wù)優(yōu)先指數(shù)表

表3 混合蟻群算法參數(shù)表

4.4 結(jié)果分析

4.4.1 能耗和時(shí)延分析

相同仿真測(cè)試條件下，利用基于改進(jìn) NSGA-Ⅱ的調(diào)度方法、基于自適應(yīng)遺傳算法的調(diào)度方法、基于DRL的調(diào)度方法、基于煙花模型的調(diào)度方法求解調(diào)度方案，并與本文的混合蟻群優(yōu)化算法做比較，然后同時(shí)模擬運(yùn)行5個(gè)任務(wù)調(diào)度方案，將100個(gè)任務(wù)調(diào)度給10個(gè)邊緣服務(wù)器節(jié)點(diǎn)，統(tǒng)計(jì)其調(diào)度的能耗以及時(shí)延。結(jié)果如圖7和圖8所示。

圖7 任務(wù)調(diào)度的能耗

圖8 任務(wù)調(diào)度的時(shí)延

由圖7可知，在同一基站帶寬下，本文方法的任務(wù)調(diào)度能耗更低，最高調(diào)度能耗為基站帶寬1.4 kHz時(shí)的150 kWh，本文方法調(diào)度能耗更低的原因是在調(diào)度過(guò)程中利用混合蟻群算法根據(jù)轉(zhuǎn)移概率選擇下一個(gè)任務(wù)調(diào)度的邊緣服務(wù)器節(jié)點(diǎn)，減少了選擇帶寬時(shí)干擾因素的影響。

由圖8可知，在前傳鏈路速率一致時(shí)，本文方法的細(xì)粒度任務(wù)調(diào)度時(shí)延更小，最高時(shí)延為5 s，其主要原因是本文方法利用遺傳算法優(yōu)化了蟻群算法，提高了算法的調(diào)度性能，避免陷入局部最優(yōu)。因此，綜合圖7和圖8中可以看出，與其他4種調(diào)度方法相比，混合蟻群任務(wù)調(diào)度能耗和時(shí)延均要更小，這也說(shuō)明本文的調(diào)度方法表現(xiàn)更好，所求出的調(diào)度方案更為合理。

4.4.2 用戶碰撞概率測(cè)試

為了進(jìn)一步驗(yàn)證本文方法的有效性，以不同數(shù)量的競(jìng)爭(zhēng)用戶碰撞的概率為測(cè)試指標(biāo)，測(cè)試五種方法的沖突概率，如圖9所示。

圖9 用戶碰撞概率測(cè)試

由圖9可知，五種方法的沖突概率隨著用戶數(shù)量的增加而增加，其主要原因是隨著用戶數(shù)量的增加，用戶選擇同樣的子載波的概率變得更高，因此提高了用戶沖突概率。而本文方法在五種方法中，用戶沖突概率更低，最高用戶沖突概率為0.27%，本文方法用戶沖突概率較低的原因是在求解目標(biāo)函數(shù)時(shí)，設(shè)定了細(xì)粒度任務(wù)只能調(diào)度到一個(gè)邊緣服務(wù)器上處理的約束條件，降低了用戶數(shù)量增加對(duì)邊緣服務(wù)器帶寬造成的影響，減少了用戶沖突。同時(shí)，當(dāng)發(fā)生較高概率的用戶碰撞時(shí)，可以增加子信道帶寬來(lái)減少多用戶之間的碰撞概率。通過(guò)增加子信道帶寬，為任務(wù)調(diào)度帶來(lái)了足夠大的競(jìng)爭(zhēng)空間，可以為用戶提供更多的選擇機(jī)會(huì)，去選擇不同的競(jìng)爭(zhēng)子載波，從而提供更好的完成細(xì)粒度任務(wù)調(diào)度。

5 結(jié)束語(yǔ)

邊緣計(jì)算支持在網(wǎng)絡(luò)邊緣提供低延遲服務(wù)，以緩解中心服務(wù)器的壓力。然而，邊緣服務(wù)器上計(jì)算資源的有限容量給調(diào)度應(yīng)用程序任務(wù)帶來(lái)了巨大挑戰(zhàn)。針對(duì)上述問(wèn)題，本文將遺傳算法與蟻群算法相結(jié)合，通過(guò)混合算法實(shí)現(xiàn)邊緣計(jì)算細(xì)粒度任務(wù)調(diào)度。仿真測(cè)試結(jié)果證明了其有效性，求出的調(diào)度方案更為合理。下一步研究中，將針對(duì)不同類型的任務(wù)調(diào)度、任務(wù)卸載等問(wèn)題進(jìn)行分析，以提高本文方法的綜合性能。