邊緣計算環(huán)境下改進蟻群算法的任務(wù)調(diào)度算法

張云飛，高 嶺，丁彩玲，趙 輝，金 帥，高全力

(1.西安工程大學(xué) 計算機科學(xué)學(xué)院，陜西 西安 710048；2.山東如意毛紡服裝集團股份有限公司，山東 濟寧 272044)

0 引 言

由于現(xiàn)有的計算架構(gòu)難以滿足以無人駕駛為代表的移動端應(yīng)用對于低時延、高數(shù)據(jù)量的需求，邊緣計算作為云計算等現(xiàn)有運算模式的補充被提了出來。邊緣計算就是在靠近用戶終端的地方設(shè)置計算/存儲節(jié)點以此來滿足移動端用戶的需求，可以有效緩解云中心以及網(wǎng)絡(luò)傳輸中的壓力，提高數(shù)據(jù)處理的實時性。目前邊緣計算中計算和任務(wù)的調(diào)度、體系結(jié)構(gòu)、安全性等問題是領(lǐng)域內(nèi)的熱點研究方向，軟件定義網(wǎng)絡(luò)[1]、區(qū)塊鏈[2]、機器學(xué)習(xí)[3]等新興的技術(shù)也應(yīng)用到了邊緣計算中，并且邊緣計算同樣地也在醫(yī)療[4]、智能城市[5]、虛擬現(xiàn)實[6]、智慧工業(yè)[7]、無人駕駛[8]、環(huán)境監(jiān)測[9]等方面取得了不錯的進展。

經(jīng)過這幾年的發(fā)展，許多人也在邊緣計算的不同領(lǐng)域做出了許多的貢獻，為后續(xù)的發(fā)展提供了強有力的支持。文獻[10]總結(jié)了邊緣計算的背景、概念、發(fā)展現(xiàn)狀、核心技術(shù)以及面臨的問題。文獻[11]考慮到有效技術(shù)傳輸和處理所需的資源，于是提出了云-邊耦合的新式架構(gòu)，通過邊緣層對物聯(lián)網(wǎng)設(shè)備的完整分析管道進行動態(tài)管理從而生成大型數(shù)據(jù)集以達到最終目的。文獻[12]則設(shè)計了一個輕量級的調(diào)度器，它利用深度神經(jīng)網(wǎng)絡(luò)來實現(xiàn)數(shù)據(jù)中心和移動設(shè)備的自動分配，通過這種方式來實現(xiàn)云中心和邊緣節(jié)點之間的數(shù)據(jù)交換。以上這些工作均是在討論云邊之間的協(xié)同與交互問題，但是并沒有關(guān)注邊緣設(shè)備間的交互與任務(wù)分配問題。

由于邊緣計算中數(shù)據(jù)的異構(gòu)性、計算和存儲資源的局限性，導(dǎo)致利用有限的資源實現(xiàn)對于時延敏感應(yīng)用的有效支撐是目前要亟待解決的關(guān)鍵問題。那么，能否實現(xiàn)任務(wù)的合理調(diào)度是解決上述問題的思路之一。目前針對任務(wù)調(diào)度已有部分研究者提出了一些解決方案，具體有：文獻[13]使用動態(tài)資源調(diào)度算法實現(xiàn)邊緣端的資源分配；利用資源匹配算法來將云數(shù)據(jù)中心的資源分配在邊緣上，通過二者的協(xié)作實現(xiàn)邊緣計算的低時延和高服務(wù)質(zhì)量。文獻[14]通過改變Storm的Task實例的排序分配方式以及二者的映射關(guān)系實現(xiàn)全局的優(yōu)化調(diào)度;同時,針對拓?fù)淙蝿?wù)并發(fā)度的缺陷,提出了一種基于蝙蝠算法的調(diào)度策略，以滿足邊緣節(jié)點之間的高實時性處理要求。文獻[15]是在邊緣網(wǎng)絡(luò)上搭建一個實時數(shù)據(jù)處理的應(yīng)用程序，希望通過這種方式減少數(shù)據(jù)傳輸量來降低能耗。文獻[16]將數(shù)據(jù)塊的最佳放置和任務(wù)的最佳調(diào)度相結(jié)合，以減少提交任務(wù)的計算延遲和響應(yīng)時間，改善邊緣計算用戶的體驗。以上這些算法從不同的需求角度提高了任務(wù)的完成效率，但較少有人關(guān)注由于任務(wù)調(diào)度的不合理導(dǎo)致的計算資源的負(fù)載不均衡，使得邊緣環(huán)境下有限的資源無法得到充分利用，進而提高了用戶的響應(yīng)時間。文中將在蟻群算法的基礎(chǔ)上，以任務(wù)的資源需求為約束實現(xiàn)邊緣端任務(wù)分配的負(fù)載均衡，讓有限的邊緣資源發(fā)揮最大的功效。

1 邊緣計算

1.1 任務(wù)調(diào)度

邊緣計算的研究現(xiàn)在仍然處于研究的初級階段，不同應(yīng)用領(lǐng)域的人都對它的定義有著自己的理解，但是其內(nèi)容實質(zhì)已然確定：在靠近數(shù)據(jù)源的網(wǎng)絡(luò)邊緣存儲和處理數(shù)據(jù)，與云端協(xié)作為用戶提供低時延、高效的服務(wù)。而任務(wù)調(diào)度便是實現(xiàn)邊緣計算十分重要的一個環(huán)節(jié)，一個優(yōu)秀的調(diào)度算法可以充分利用設(shè)備上的計算和存儲資源，實現(xiàn)數(shù)據(jù)傳輸?shù)淖钚』蛻?yīng)用程序執(zhí)行性能的最大化，在有限的資源中為用戶創(chuàng)建更優(yōu)秀的服務(wù)效果。

邊緣計算的典型任務(wù)調(diào)度場景如圖1所示，可以描述為n個相互獨立的任務(wù)分配到m個不同的計算能力的邊緣節(jié)點上，n通常大于m。其中每個邊緣節(jié)點的計算資源差距很大而且任務(wù)n的需求也將呈現(xiàn)不同的狀態(tài)。根據(jù)需要實現(xiàn)的優(yōu)化目標(biāo)，建立任務(wù)與邊緣節(jié)點之間的匹配關(guān)系，實現(xiàn)任務(wù)分配的最優(yōu)。

圖1 邊緣網(wǎng)絡(luò)調(diào)度模型

為了簡化任務(wù)的調(diào)度，作如下假設(shè)：

(1)默認(rèn)任務(wù)之間為相互獨立的沒有依賴關(guān)系；

(2)每個任務(wù)的需求都是已知的；

(3)任務(wù)執(zhí)行中不存在間斷執(zhí)行。

1.2 問題定義

在某一時刻一個邊緣節(jié)點接收到的任務(wù)數(shù)為n，表示為TN={tn1,tn2,…,tnn}；任務(wù)i對于資源的需求描述為(dcpui,dgpui,dmemi)，其中dcpui表示該任務(wù)對于CPU的需求，dgpui表示該任務(wù)對于GPU的需求，dmemi表示該任務(wù)對于內(nèi)存的需求；而該節(jié)點需要將這些任務(wù)合理分配至其所在的邊緣網(wǎng)絡(luò)當(dāng)中，邊緣網(wǎng)絡(luò)中可分配的計算節(jié)點數(shù)量為m，表示為PM={pm1,pm2,…,pmn}；節(jié)點j中可用的資源描述為(rcpuj,rgpuj,rmemj)，其中rcpuj表示該節(jié)點CPU可用量，rgpuj表示該節(jié)點GPU的可用量，rmemj表示該節(jié)點內(nèi)存的可用量。

任務(wù)TN到節(jié)點PM的分配關(guān)系可以用矩陣A表示為：

(1)

這里的aij表示為任務(wù)Ti和節(jié)點Pj的對應(yīng)關(guān)系，aij∈{0，1}，i∈{0,1,…,n}，j∈{0，1，…，n}，如果aij=1則表示任務(wù)i分配在了節(jié)點j上。

2 基于改進蟻群算法的多目標(biāo)優(yōu)化邊緣計算任務(wù)調(diào)度

文中是在標(biāo)注蟻群算法的基礎(chǔ)上，對于信息素的初始化、更新，以及啟發(fā)因子的設(shè)置等進行優(yōu)化改進，以達到目標(biāo)任務(wù)以及適應(yīng)邊緣計算環(huán)境下的要求。

2.1 定義問題解

文中對邊緣節(jié)點的負(fù)載均衡性采用負(fù)載不均衡度來度量，該值在0～1之間取值，該值越小則表示邊緣節(jié)點的任務(wù)的負(fù)載分布越均勻，系統(tǒng)的整體性能越高。具體表示為：

(2)

2.2 啟發(fā)式因子的設(shè)置

ηij表示的是啟發(fā)式因子，主要表示的是任務(wù)i布置在邊緣節(jié)點j的期望強度，ηij的值越大則任務(wù)布置在該節(jié)點的可能性也越大：

ηij=Q/MDij(t)

(3)

其中，Q為任意常數(shù)(建議選擇值在1附近選擇)，MDij(t)則可以定義為等待分配的任務(wù)對于所需求的資源與節(jié)點空閑資源之間的余弦相似度，相當(dāng)于是任務(wù)i與節(jié)點j之間的相似程度用二者之間的夾角表示。夾角越小，則代表著二者之間的相似程度越高，任務(wù)分配在該節(jié)點的可能性也越高：

(4)

根據(jù)公式(4)可以得出：待分配任務(wù)與邊緣節(jié)點之間的匹配度越小，節(jié)點越能適應(yīng)任務(wù)對于節(jié)點的性能要求，該任務(wù)分配在此節(jié)點的可能性也應(yīng)該越高。在任務(wù)的分配過程中，匹配度也在隨著時間的變化在不停的變化，令WDij(t)表示時刻t邊緣節(jié)點PMi與任務(wù)TNj的匹配度，如果任務(wù)TNj放置在邊緣節(jié)點PMi上，則在下次邊緣節(jié)點PMi與其他任務(wù)的匹配度計算要在分配了任務(wù)TNj所需資源后的空閑資源進行計算。

任務(wù)與節(jié)點之間的分配為多對一的映射關(guān)系，在任務(wù)的分配中需要保證任務(wù)對于每一種資源的需求量都應(yīng)該小于節(jié)點空閑的資源量，通過對比任務(wù)對CPU、GPU和內(nèi)存的需求和節(jié)點可利用資源進行對比防止將任務(wù)分配在資源不足的節(jié)點上面，即：

(5)

(6)

(7)

其中，vcpuij、vgpuij、vmemij分別表示任務(wù)TNj在邊緣節(jié)點PMi上CPU、GPU、內(nèi)存的使用量；rcpui、rgpui、rmemi分別表示邊緣節(jié)點PMi關(guān)于CPU、GPU、內(nèi)存的可使用量。

2.3 信息素的更新

初始蟻群算法的信息素更新對于全部的路徑揮發(fā)，這樣會導(dǎo)致經(jīng)常未走過的節(jié)點的信息素會越來越低甚至趨近于零。所以，文中對于沒有走過的路徑不進行揮發(fā)，具體更改如下：

(8)

2.4 算法總體流程

輸入:邊緣節(jié)點集合PM={pm1,pm2,…,pmn}，任務(wù)需求集合TN={tn1,tn2,…,tnn}，信息素啟發(fā)因子α，期望啟發(fā)因子β，信息素?fù)]發(fā)率ρ等初始需求。

輸出：最優(yōu)的任務(wù)分配方案和負(fù)載不均衡度。

Step1：初始化螞蟻個數(shù)AntNum并且按照任務(wù)提交的順序?qū)⑷蝿?wù)的需求資源附加在每一個任務(wù)上，迭代次數(shù)maxIter，啟發(fā)式因子α和β以及相關(guān)參數(shù)。

Step2：隨機將n個攜帶著任務(wù)需求的螞蟻分配在隨機節(jié)點上面(因為不同任務(wù)可以放置在同一節(jié)點上，所以禁忌表Tabuk僅為不滿足公式(5)到公式(7)的節(jié)點)，計算第k只螞蟻將任務(wù)i分配在節(jié)點j的概率。之后利用輪盤賭的方式從滿足條件的節(jié)點中隨機選擇一個節(jié)點作為該任務(wù)的分配節(jié)點，并將該任務(wù)部署在該節(jié)點上。概率選擇公式為：

(9)

Step3：第k只螞蟻完成所有的任務(wù)分配之后，對所分配的節(jié)點按照公式(6)進行局部更新。

Step4：完成該螞蟻的部署之后按照公式(2)計算該分配方案的負(fù)載不均衡度，并與歷史記錄對比并記錄最優(yōu)分配方案和最小負(fù)載不均衡度。

Step5：判斷所有的螞蟻是否全部結(jié)束，如果有螞蟻沒有完成則跳至Step2；如果所有的螞蟻均完成了本次迭代，計算出全局最優(yōu)解并保存，最后按照最優(yōu)的放置方案根據(jù)公式(8)進行信息素的全局更新。

Step6：判斷是否滿足迭代次數(shù)或者滿足了預(yù)先設(shè)置的負(fù)載均衡度，算法迭代結(jié)束返回最優(yōu)路徑解。否則，返回Step2。

3 實驗分析

3.1 仿真實驗參數(shù)配置

為了驗證算法的有效性，進行仿真實驗。利用輪詢算法(PA)、最大內(nèi)存分配算法(MMA)以及文中算法(IAC)進行比較，在一臺計算機(四核，2.5 GHz的CPU主頻，8.0 GB的內(nèi)存)上采用python語言編程進行模擬仿真，驗證算法的性能。將任務(wù)分配后邊緣節(jié)點的整體的負(fù)載不均衡度(公式(2))以及該邊緣云的最大承載任務(wù)數(shù)作為最終判斷算法優(yōu)劣的依據(jù)。

為了使硬件設(shè)備的計算和存儲能力有更好可視性，所以對硬件和任務(wù)需求的數(shù)據(jù)進行了數(shù)字化描述。由于邊緣節(jié)點的異構(gòu)性，所以CPU與GPU的處理能力在100～200間隨機取得，內(nèi)存的存儲能力也在300～600間隨機取得；根據(jù)文獻[17]的流量模型，其中假設(shè)任務(wù)的15%為大型任務(wù)，每個任務(wù)的CPU、GPU需求量在30～70之間隨機取得，內(nèi)存需求也在50～200間隨機取得；小型任務(wù)的數(shù)量在85%，每個任務(wù)的CPU、GPU需求量在1～30之間隨機取得，內(nèi)存需求也在3～50間隨機取得。

由于蟻群算法的參數(shù)對算法的性能有著較大的影響，因此對算法的各種參數(shù)組合進行實驗并對比。采用控制變量法，分別對α、β、ρ設(shè)定數(shù)值，設(shè)置任務(wù)數(shù)量為200(均為大型任務(wù)，可以使得對比變化更明顯)，邊緣節(jié)點數(shù)為100，迭代次數(shù)為50，取10次平均結(jié)果作為最終結(jié)果。

(1)保持ρ的數(shù)值不變，分別對α和β進行取值，具體的影響結(jié)果如表1所示。α越大，螞蟻在某個點容易陷入局部最短路徑，雖然收斂速度會增大，但是搜索過程中隨機性減弱，易陷入局部最優(yōu)；β越大，螞蟻越容易選擇原有路徑，搜索的隨機性減少，也會陷入局部最優(yōu)。由表1可以看出，在ρ不變的情況下，α=4，β=5時算法的性能最優(yōu)，負(fù)載不均衡度也最小。

表1 α、β對算法的影響

(2)保持α和β不變，對ρ進行取值，影響結(jié)果如表2所示。由表2可以看出，ρ的最優(yōu)選擇分別在0.2和0.6的周圍，此時的算法比較優(yōu)秀。但是ρ=0.2在計算過程中的運算時間大于ρ=0.6，所以最終選擇ρ=0.6。

表2 ρ對算法性能的影響

3.2 實驗結(jié)果與分析

為了驗證算法可以較為優(yōu)秀的對邊緣節(jié)點做到負(fù)載均衡，分別對文獻[18]的輪詢算法(RR)、傳統(tǒng)蟻群算法(ACO)以及文中算法(IAC)進行比較，得到最后全部為大型任務(wù)、文獻[17]的混合任務(wù)以及全部為小型任務(wù)的最大承載任務(wù)數(shù)，見圖2～圖4，以及相同任務(wù)數(shù)量上三種算法的負(fù)載均衡度的對比，見圖5。

圖2 大型任務(wù)時各算法最大承載任務(wù)數(shù)對比

圖3 混合任務(wù)時各算法最大承載任務(wù)數(shù)對比

圖4 小型任務(wù)時各算法最大承載任務(wù)數(shù)對比

圖5 不同任務(wù)數(shù)時各算法負(fù)載均衡度對比

由上面三幅圖均可以明顯看出，文中提出的算法相對其他兩種算法提高了最大任務(wù)可承載數(shù)，提高了邊緣節(jié)點的使用效率，從而降低了網(wǎng)絡(luò)中心總流量，降低了對用戶的響應(yīng)需求的平均響應(yīng)時間；而且IAC算法每次會有多個近似最優(yōu)解生成，可以根據(jù)需求自由選擇。通過三個圖的對比可以看出，全部為小型任務(wù)時各算法差距很小，當(dāng)加入大型任務(wù)時可以看出文中提出的算法更加優(yōu)秀。同時若是對負(fù)載需求不高的情景也可以通過減少螞蟻數(shù)的方式提高分配效率，降低算法的運行時間。

由圖5可知，在邊緣節(jié)點數(shù)不變的情況下，文中所提出的IAC算法的負(fù)載均衡度在隨著任務(wù)數(shù)的增長過程中均優(yōu)于剩余的兩種算法，且優(yōu)秀程度也有著一個較為明顯的差距。這是由于隨著任務(wù)數(shù)量的增多在分配過程中分配的可能性也就越多，也更有可能出現(xiàn)優(yōu)秀的分配方式，所以算法的整體負(fù)載均衡度呈現(xiàn)一個下降的趨勢。綜上可以得出結(jié)論，IAC算法無論是從負(fù)載均衡度還是任務(wù)的分配數(shù)上相對于剩余兩種算法均有一個良好的表現(xiàn)。

4 結(jié)束語

邊緣節(jié)點的負(fù)載均衡是邊緣計算下一個十分重要的問題。目前方法在資源分配方面主要以時延為準(zhǔn)則忽略了邊緣環(huán)境的局限性，文中針對邊緣環(huán)境下資源的局限性，首先對邊緣節(jié)點的任務(wù)分配問題進行描述；然后設(shè)計了一種改進的蟻群算法用來解決該問題。該算法將任務(wù)對資源的需求作為啟發(fā)因子，改變了信息素更新方式，加快了收斂速度，提高了最終解的質(zhì)量。通過仿真實驗結(jié)果表明，算法可以有效降低節(jié)點的負(fù)載不均衡度。