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

陳 剛,王志堅

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

0 引言

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

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

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

1 邊緣計算細粒度任務調(diào)度的原理

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

1.1 問題描述

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

圖1 移動計算任務調(diào)度的傳統(tǒng)模型

圖2 現(xiàn)代移動邊緣計算任務調(diào)度模型

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

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

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

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

1.3 細粒度任務調(diào)度的原理

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

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

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

2 邊緣計算細粒度任務調(diào)度的設計

2.1 假設條件設置

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

假設條件1：任務調(diào)度時不能只考慮一個邊緣節(jié)點作為調(diào)度對象；

假設條件2：邊緣節(jié)點的計算資源存在能源耗盡的情況；

假設條件3：邊緣網(wǎng)絡拓撲已知，且拓撲中每個服務器節(jié)點與本地服務器、中心云端的距離是已知的；

假設條件4：每個任務對計算資源的需求都是已知且存在差異的；

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

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

假設條件7：任務傳輸信道的信息是已知的。

2.2 任務調(diào)度順序設計

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

(1)

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

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

2.3 邊緣服務器性能特征分析

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

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

2.4 任務調(diào)度方案設計

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

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

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

minY=y1∪y2

(2)

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

2.4.2 約束條件設置

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

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

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

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

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

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

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

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

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

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

步驟2：對邊緣計算細粒度任務調(diào)度問題進行編碼處理；

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

步驟4：初始化種群；

步驟5：種群個體解碼；

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

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

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

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

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

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

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

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

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

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

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

步驟5：當每一只螞蟻均找到一個邊緣服務器節(jié)點方案后，更新邊緣服務器節(jié)點的信息素；

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

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

4 仿真測試與分析

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

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

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

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

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

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

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

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

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

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

圖6 算法收斂速度測試

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

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

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

4.4 結(jié)果分析

4.4.1 能耗和時延分析

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

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

圖8 任務調(diào)度的時延

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

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

4.4.2 用戶碰撞概率測試

為了進一步驗證本文方法的有效性，以不同數(shù)量的競爭用戶碰撞的概率為測試指標，測試五種方法的沖突概率，如圖9所示。

圖9 用戶碰撞概率測試

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

5 結(jié)束語

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