邊緣計算環境下改進蟻群算法的任務調度算法

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

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

0 引 言

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

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

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

1 邊緣計算

1.1 任務調度

邊緣計算的研究現在仍然處于研究的初級階段，不同應用領域的人都對它的定義有著自己的理解，但是其內容實質已然確定：在靠近數據源的網絡邊緣存儲和處理數據，與云端協作為用戶提供低時延、高效的服務。而任務調度便是實現邊緣計算十分重要的一個環節，一個優秀的調度算法可以充分利用設備上的計算和存儲資源，實現數據傳輸的最小化和應用程序執行性能的最大化，在有限的資源中為用戶創建更優秀的服務效果。

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

圖1 邊緣網絡調度模型

為了簡化任務的調度，作如下假設：

(1)默認任務之間為相互獨立的沒有依賴關系；

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

(3)任務執行中不存在間斷執行。

1.2 問題定義

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

任務TN到節點PM的分配關系可以用矩陣A表示為：

(1)

這里的aij表示為任務Ti和節點Pj的對應關系，aij∈{0，1}，i∈{0,1,…,n}，j∈{0，1，…，n}，如果aij=1則表示任務i分配在了節點j上。

2 基于改進蟻群算法的多目標優化邊緣計算任務調度

文中是在標注蟻群算法的基礎上，對于信息素的初始化、更新，以及啟發因子的設置等進行優化改進，以達到目標任務以及適應邊緣計算環境下的要求。

2.1 定義問題解

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

(2)

2.2 啟發式因子的設置

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

ηij=Q/MDij(t)

(3)

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

(4)

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

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

(5)

(6)

(7)

其中，vcpuij、vgpuij、vmemij分別表示任務TNj在邊緣節點PMi上CPU、GPU、內存的使用量；rcpui、rgpui、rmemi分別表示邊緣節點PMi關于CPU、GPU、內存的可使用量。

2.3 信息素的更新

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

(8)

2.4 算法總體流程

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

輸出：最優的任務分配方案和負載不均衡度。

Step1：初始化螞蟻個數AntNum并且按照任務提交的順序將任務的需求資源附加在每一個任務上，迭代次數maxIter，啟發式因子α和β以及相關參數。

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

(9)

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

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

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

Step6：判斷是否滿足迭代次數或者滿足了預先設置的負載均衡度，算法迭代結束返回最優路徑解。否則，返回Step2。

3 實驗分析

3.1 仿真實驗參數配置

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

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

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

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

表1 α、β對算法的影響

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

表2 ρ對算法性能的影響

3.2 實驗結果與分析

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

圖2 大型任務時各算法最大承載任務數對比

圖3 混合任務時各算法最大承載任務數對比

圖4 小型任務時各算法最大承載任務數對比

圖5 不同任務數時各算法負載均衡度對比

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

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

4 結束語

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