智慧煤礦中邊緣計算任務分配研究

朱曉娟，張浩

(安徽理工大學 計算機科學與工程學院， 安徽 淮南 232001)

0 引言

隨著物聯網技術的不斷發展，智慧煤礦將物聯網、云計算、大數據、人工智能等與現代礦山開采技術相融合，實現對礦山生產、安全監控、技術支持和后勤保障等過程的主動感知、智能分析、快速處理，形成最優決策。云計算技術在礦山物聯網系統中起核心支撐作用[1-3]。傳統的云計算架構采用集中式數據處理方式，將數據傳輸到遠端的云中心進行分析處理。但是，有些關乎安全生產和礦工生命安全的數據往往需要進行實時處理，由于傳輸距離較遠、數據量較大、無線通信不穩定等，僅依靠云計算已無法保證智慧煤礦決策層的時效性、精確度及數據安全[4-6]。

邊緣計算作為云計算的擴展與延伸，可彌補集中式云計算的不足，與云計算協同,提供高質量的應用服務[7]。近幾年來，邊緣計算在智慧工廠[8]、智慧電網[9]、智慧醫療[10]及智慧交通[11]等工業場景中得到了廣泛應用。在智慧煤礦中，邊緣節點部署在網絡邊緣靠近終端用戶的位置。這些分散在不同位置的邊緣節點具有運算和存儲數據的能力[12]，有助于智慧煤礦進行全面自主感知、智能分析決策、動態預測預警，實現對礦井內環境和設備的高效穩定檢測，提高預警速度和故障位置識別精準度，從而保證煤礦生產的安全、高效、穩定。

考慮到不同的任務需求，為了進一步提高智慧煤礦的全局任務處理效率,優化資源分配，需要一個有效的任務分配策略。近年來的相關研究多致力于最小化任務處理延遲，并關注邊緣計算工作負載平衡。在邊緣計算中，以固定優先級的順序來處理任務，可能導致重要、緊迫的任務得不到及時處理。針對該問題，文獻[13]提出一種基于動態優先級的任務調度模型，文獻[14]提出根據任務平均處理價值賦予其相應的優先級。在任務分配方面，文獻[15]針對大規模多任務分配問題，提出了一種新型進化算法來進行求解。文獻[8，16]根據任務和邊緣節點的特性進行等級劃分，再根據啟發式算法得出目標函數的最優解，從而將任務分配到合適的邊緣節點上去處理，以達到使時延最小的目的。文獻[17-18]從負載均衡的角度出發，為邊緣節點動態設置一個負載閾值，將過載邊緣節點上的任務分配到相鄰未過載邊緣節點上進行處理。文獻[19-20]利用博弈論方法設計了一種分布式任務分配算法，以實現時延及能耗代價最小化。

目前智慧煤礦邊緣計算中的任務分配大多采用集中式分配算法，劃分任務優先級時考慮的因素較單一，未考慮煤礦網絡拓撲的窄長型特征。鑒于此，本文結合煤礦場景下任務的特點，提出了一種動態優先級任務隊列生成方法，采用實時競價算法對分布式邊緣節點的任務進行分配，以實現時延、能耗最小化和負載平衡等目標。

1 基于邊緣計算的智慧煤礦架構

智慧煤礦中的邊緣計算框架由終端設備層、邊緣計算層及云計算層組成，如圖1所示。

圖1 智慧煤礦中的邊緣計算框架Fig.1 Edge computing framework in intelligent coal mine

終端設備層由具有不同功能的終端設備組成：具有環境感知功能的傳感設備，如井下瓦斯傳感器、粉塵傳感器、溫度傳感器等；設備監測傳感節點，用于機械手、鉆井機械設備、運輸設備等的位置或狀態感知；人員隨身佩戴的感知設備，用于采集井下工人身體生理狀態信息、運動狀態信息及周邊環境信息等。

邊緣計算層由具有一定計算能力和存儲能力的邊緣設備組成。邊緣設備部署在巷道內，根據部署位置的需求從云服務器下載事先建立好的分析模型。當終端設備將檢測到的數據傳輸到邊緣設備時，邊緣設備通過分析模型實現數據分析、預警等。邊緣設備在本地緩存數據，并將數據和處理記錄上傳到云服務器，如果在上傳過程中出現網絡中斷，能夠在網絡恢復后繼續上傳至云端，保證數據安全。

云計算層由高性能服務器集群組成，用于處理邊緣計算層無法處理的大規模、非實時計算，如模型訓練、全局優化決策等任務，并存儲和分析生產過程中產生的海量數據和邊緣計算層處理結果。

2 邊緣計算任務分配策略

2.1 邊緣計算網絡拓撲

由于地下煤礦開采范圍廣、地形復雜、巷道窄長、無線通信環境惡劣等，很難通過部署一個中心邊緣節點來快速、實時地管理整個邊緣網絡。因此，將邊緣計算層設計為分布式結構。部署在多條巷道之間的邊緣計算網絡拓撲如圖2所示，邊緣節點與終端節點之間采用無線方式進行數據傳輸。

圖2 邊緣計算網絡拓撲Fig.2 Edge computing network topology

當任務提交到邊緣計算層時，需要確定哪個任務先卸載，任務要卸載到哪個邊緣節點上處理，才能高效地進行任務處理并保證資源充分利用。設定任務分配僅在請求節點2跳范圍內進行，原因如下：① 滿足實時性需求。與監控相關的任務，如井下瓦斯濃度監測、火災監測、生產過程設備狀態監測等，以及無線視頻監控中的圖像識別、預警等都對實時性有較高的要求。異常情況預警包含信息感知、異常識別請求、邊緣節點競價、網絡傳輸、邊緣計算等過程，將任務分配范圍限制在任務請求節點的2跳之內，能較好地降低整體預警過程的時延。② 避免僅根據綜合算力將任務分配到距離較遠的邊緣節點處，從而增加網絡傳輸代價和無線傳感器節點能耗。

2.2 動態任務隊列生成

在智慧煤礦中，各種任務不斷被提交到邊緣網絡中等待處理，如果按照先來先服務策略，可能導致重要、緊迫的任務得不到及時處理，無法保證生產效率和安全。為了保證煤礦安全高效運作，必須對任務進行分類。一方面，將計算量超過邊緣節點計算能力的任務直接上傳至云端進行處理，如大規模的數據挖掘和深度知識發現等。另一方面，將能夠在邊緣計算層處理的任務按重要程度劃分為3個等級：第1等級為環境監控相關任務及工作人員安全操作規程檢測相關任務；第2等級為生產過程設備狀態監控相關任務，快速響應這類任務是為了防止設備故障導致事態進一步惡化；第3等級為其他常規任務。但僅僅按照這3個等級進行任務分配，會導致優先級低的任務被優先級高的任務阻塞。為此，還需考慮任務的緊迫程度，對臨近截止時間的任務提高優先級。

(1)

(2)

(3)

在智慧煤礦相關研究中大多更傾向于優先處理重要程度和緊迫程度高的任務，因此，本文設置λ1，λ2值為0.4，λ3值為0.2。

2.3 基于實時競價的任務分配策略

實時競價策略與傳統拍賣算法類似，賣家提供商品報價，買家選擇購買滿足自己需求且報價最低的商品，拍賣師決定將商品賣給出價高的買家。但傳統基于1個拍賣師的任務分配模型不適合本文應用場景，因為智慧煤礦覆蓋面積廣且傳輸路徑長，若由1個邊緣管理節點作為拍賣師來控制整個煤礦系統中所有邊緣節點和任務的分配，不僅增加了任務響應時延，還無法保證數據傳輸的可靠性。為此，本文改進了拍賣規則，由買家來決定商品的選擇，且僅允許請求節點2跳內的邊緣節點競價，從而提高商品拍賣效率，減少數據傳輸距離。任務分配實時競價模型如圖3 所示，其中E1—E8為邊緣節點。終端節點將任務提交到E1，E1作為請求任務分配的節點，根據周圍邊緣節點的報價信息，選擇2跳內能夠滿足任務算力需求的邊緣節點進行任務卸載。E4,E8與E1之間超過2跳,不參與報價。

圖3 任務分配實時競價模型Fig.3 Real-time bidding model for task allocation

競價模型中，只有買方和賣方2種角色。賣方提供商品和報價，買方選擇低于自身出價且報價最低的賣家購買。買方是需要任務卸載的邊緣節點，可購買其他邊緣節點資源；賣方是周邊2跳內的邊緣節點，可根據計算任務的算力需求、緊迫程度和邊緣節點自身當前狀態為待處理的任務給出報價。

任務分配的目的是解決邊緣節點計算能力不足的問題，平衡負載，保證任務高效完成。因此，邊緣節點j對任務i的報價Mj通過邊緣節點計算能力、處理時間、能耗和等待時間4個因素來描述：

(4)

式中：Tj為任務在邊緣節點j上的處理時間,j=1,2,…,m,m為邊緣節點個數；Wj為響應時間比；Pj為邊緣節點的綜合算力；ej為計算過程所產生的總能耗；α1，α2，α3，α4分別為Tj，Wj，Pj，ej的權重參數，α1+α2+α3+α4=1，α1，α2，α3，α4∈[0,1]；Tj,wait為任務在該節點上等待時間；Sj,free為邊緣節點剩余存儲容量。

邊緣節點j處理任務i所需的時間Tj包括任務計算時間Tcij和數據傳輸時間Trij：

Tj=Tcij+Trij

(5)

(6)

(7)

式中：Cj為邊緣節點j的計算能力；N為請求節點到報價節點所經過的跳數；B為邊緣節點間的網絡帶寬。

系統中任務在實時大量產生，邊緣節點的處理能力有限，不可能任務產生后立刻得到處理，因此，任務在邊緣節點的等待時間也是影響實時任務分配的一個重要參數。用Tj,wait記錄任務需等待時間，當任務分配到邊緣節點j上進行處理時，將該任務在本節點的預計計算時間Tcij進行累加；當有任務完成處理時，從Tj,wait中減去該任務處理時間。邊緣節點響應時間比Wj計算公式為

(8)

本文所研究的邊緣節點是異構型的，必須考慮邊緣節點的計算能力和剩余存儲容量。用Pj來衡量邊緣節點的綜合算力，Pj值越大表示其綜合算力越強，該節點越容易被任務選中作為卸載節點。

(9)

式中：a，b為計算能力和剩余存儲容量的權重參數，a+b=1，a，b∈[0，1]；Sj為節點j的總存儲容量。

在競價算法中，邊緣節點對任務報價時，約束條件限制了剩余存儲容量必須大于任務的數據量，因此，衡量邊緣節點綜合算力時，主要參考邊緣節點的計算能力。添加剩余存儲容量作為一個衡量依據是為了平衡各邊緣節點的存儲容量，在邊緣節點計算能力相近時，選擇存儲容量剩余較多的邊緣節點，防止某些邊緣節點因存儲容量不足而無法完成任務。經測試，邊緣節點的計算能力與剩余存儲容量的權重取值不同時算法性能具有差異。當權重參數a，b的值分別設置為0.7和0.3時，任務處理時延相對較低，存儲容量利用率較為均衡。

總能耗ej由計算能耗ecij和傳輸能耗erij組成：

ej=ecij+erij

(10)

ecij=Tcijpcj

(11)

erij=Trijprj

(12)

式中：pcj為邊緣節點j的計算功率；prj為傳輸功率。

2.4 具體流程和算法

(1) 當任務提交到邊緣節點時，邊緣節點根據任務計算量、數據量等信息判斷能否在邊緣計算網絡中處理，若邊緣節點可以處理則進行步驟(2)，否則提交到云平臺進行處理。

(2) 邊緣節點首先根據任務類型給出固定優先級，然后基于任務信息動態生成優先級隊列(算法1)。

(3) 開始進行任務分配時，邊緣節點(請求節點)將任務信息發送給周邊2跳之內的邊緣節點，這些邊緣節點根據式(4)為該任務提出報價。

(4) 請求節點將各邊緣節點的報價和自身處理所需代價進行比較，選擇代價最低的邊緣節點進行任務卸載(算法2)。

(5) 請求節點根據競價結果將任務傳輸到競價成功的邊緣節點上執行。如果競價失敗，則進入下一次競價過程。

(6) 請求節點更新自身狀態，刷新任務優先級隊列。成功競價的邊緣節點更新自身狀態(算法3)，并為下一個任務進行競價。

算法1:優先級隊列生成算法輸入:待處理任務Ia(a=1,2,…,n);當前任務隊列I輸出:待處理任務隊列I1: I=[I1 I2 … In]2: L=DetermineType(Ia) //給出任務固定優先級L3: Tave=EstimatedTime(Ia) //根據式(2)計算得到預計處理時延Tave4: Tw=tb-tk //Tw為任務等待分配時間,tb為隊列生成算法開始時間,tk為任務提交時間5: U =1/[Tmax-(Tave+Tw)] //U為當前任務緊迫程度,Tmax為任務最大容忍時間6: K=Priority(L,U,Q ) //Q為當前任務計算量 //根據式(1)生成此刻的動態優先級K //通過插入排序為Ia找到合適位置,更新優先級隊列7: l=I.Length //l為任務隊列I的長度8: While l>=1&&K(I[l])>K // K(I[l])為任務I[l]的動態優先級9: I[l+1]=I[l]10: l--11: I[l+1]=Ia12: return (I) //返回任務隊列I

算法2:任務分配節點選擇算法輸入:待處理任務i和周圍2跳內邊緣節點集合Edge輸出:被卸載的任務和邊緣節點1: Edge=[Edge1 Edge2 … Edgem] 2: for j=1:m 3: if (Ti,max>Tj+Tj,wait)&& Sj,free>Di //選擇滿足限制條件的邊緣節點j

4: Edge[j]→price(i) //節點j根據式(4)對任務i進行報價5: Min=price1 //price1為Edge中為第1個邊緣節點對任務i的報價6: if pricej

算法3:邊緣節點狀態更新算法輸入:分配到節點j的任務隊列I,節點Edgej及狀態信息輸出:邊緣節點狀態1: R=Get(Ia)//任務Ia被分配到該邊緣節點處理,R為待處理任務 2: PutDataIntoQueue(R) //將R加入待處理任務隊列//更新剩余存儲容量 3: STOREj=STOREj-DR //STOREj為邊緣節點j的剩余存儲容量,DR為任務R的數據量 //更新等待時間4: Tj,wait=Tj,wait+TcR//Tj,wait為處理當前所有任務所需時間,TcR為該邊緣節點處理任務R所需時間 //有任務處理結束5: G=GetDataFromQueue() //G為當前已完成的任務6: Tj,wait=Tj,wait-TcG//TcG為該邊緣節點處理任務G所需時間7: STOREj=STOREj+DG//DG為任務G的數據量8: return(Edgej, Tj,wait,STOREj)

3 仿真實驗與分析

3.1 仿真場景與參數設置

從平均處理時延、總能耗、資源利用率和完成任務總價值4個方面評估智慧煤礦中邊緣計算任務分配策略的性能，并與文獻[20-21]提出的任務分配策略進行對比。文獻[20]首先根據任務量和時延敏感程度生成任務隊列，然后采用競價策略對任務進行分配。文獻[21]采用集中式任務分配策略，將任務和邊緣節點信息提交到中心邊緣控制器，邊緣控制器根據任務量、傳輸時延、時延敏感度、邊緣節點利用率和計算能力等信息，利用模糊聚類將任務和邊緣節點分成高中低3個等級，再進行同等級之間的任務分配。

在云計算仿真平臺軟件CloudSim 2020中搭建智慧煤礦邊緣計算仿真環境，任務數量為[50，400]，邊緣節點為單核處理器，數量為10個，網絡結構與圖2所示邊緣計算網絡拓撲對應。為保證實驗的準確性，每組實驗進行50次，取均值作為最終值。具體的仿真參數見表1。

表1 仿真參數Table 1 Parameters of simulation

3.2 仿真結果與分析

不同任務分配策略的平均時延對比如圖4所示。隨著任務數量的增加，3種任務分配策略的時延均呈現上升趨勢。本文的任務分配策略在時延方面優于文獻[20-21]，這是因為文獻[20-21]僅在任務提交時刻根據任務量的大小和時延敏感程度生成任務優先級隊列，而本文使用動態優先級算法生成任務隊列，綜合考慮了任務的緊迫程度、任務量和固定優先級，邊緣節點優先處理更高優先級和更緊迫的任務，從而減少了任務的整體等待時間。在邊緣節點選擇上，相比于文獻[20]，本文的任務分配策略加入了自身處理該任務的代價進行競價對比，防止任務分配到周圍邊緣節點上的處理代價高于自身處理代價，影響任務的整體處理時延。文獻[21]則是采用集中式任務分配的方式，將任務提交到管理節點再進行任務分配，在煤礦井下窄長型的網絡場景下傳輸時延較高。本文結合煤礦井下網絡拓撲特征，在一定范圍內為任務選擇算力匹配的邊緣節點進行任務卸載，進一步控制任務處理時延。

圖4 不同任務分配策略的平均時延對比Fig.4 Comparison of average delay of different task allocation strategies

不同任務分配策略的總能耗對比如圖5所示，可見本文所提出的分配策略的總能耗最低。相對于文獻[20-21]，本文的任務分配策略控制任務在請求節點2跳范圍內選擇邊緣節點，保證了傳輸能耗和時延較低，同時基于平衡分配的思想，增加任務計算量、邊緣節點的處理能力和等待時間作為任務分配參考依據，在保證等待時間較短的情況下，將計算量大的任務盡可能分配給處理能力強的邊緣節點，減少了任務的處理時延，降低了能耗。

圖5 不同任務分配策略的總能耗對比Fig.5 Comparison of total energy consumption of different task allocation strategies

資源利用率Z為所有任務計算總量與所有邊緣節點可以計算的最大計算總量的比值為

(13)

式中T為邊緣節點處理完所有任務所用時間。

不同任務分配策略對邊緣網絡資源的利用率對比如圖6所示，可見本文的分配策略資源利用率最高。相比于文獻[20-21]，本文的策略任務完成時間最短，傳輸時延較小，能夠實現更多任務分配。而文獻[20-21]的任務分配策略容易造成高等級的邊緣節點提前過載，從而影響資源利用率。

完成任務總價值J用任務的重要程度、緊迫程度和任務計算量來衡量：

(14)

式中：γ1，γ2，γ3為權重參數，γ1+γ2+γ3=1，γ1，γ2，γ3∈[0,1]；n′為單位時間內所完成的任務數量；ω為常數。

圖6 不同任務分配策略對邊緣網絡資源的利用率對比Fig.6 Comparison of edge network resource utilization rate of different task allocation strategies

隨機生成3種固定優先級的任務，隨著時間的增加，不同任務分配策略完成的任務總價值對比如圖7所示,可見本文策略所完成任務的總價值高于文獻[20-21]的分配方案。這是因為文獻[20-21]僅基于平衡分配的思想，按照計算量的降序和任務的最大時延限制來生成任務隊列，而本文基于動態優先級生成任務隊列，綜合考慮了任務的計算量、緊迫程度和固定優先級(重要程度)，優先處理緊迫且重要的任務，具有較低的平均處理時延，在同等時間內完成了更多任務。

圖7 不同任務分配策略完成的任務總價值對比Fig.7 Comparison of total value of completed tasks of different task allocation strategies

4 結論

(1) 在云服務器與終端節點之間構建一個分布式結構的邊緣計算層來進行任務分配。為滿足實時性需求，避免僅根據綜合算力將任務分配到距離較遠的邊緣節點處，設定任務分配僅在請求節點2跳范圍內進行。

(2) 根據任務的固定優先級、緊迫程度和計算量動態生成優先級并更新任務隊列，優先處理重要的、臨近截止時間的任務，使計算量大的任務盡可能分配給處理能力強的邊緣節點進行處理。

(3) 建立了任務分配的實時競價模型，通過邊緣節點計算能力、處理時間、能耗和等待時間4個因素來確定邊緣節點對任務的報價，請求節點將任務傳輸到競價成功的邊緣節點執行，從而完成任務分配。

(4) 從平均處理時延、總能耗、資源利用率和完成任務總價值4個方面評估智慧煤礦中邊緣計算任務分配策略的性能。仿真結果表明，提出的實時任務分配策略可有效降低智慧煤礦中任務處理的時延和能量消耗，并提高邊緣計算網絡資源的利用率及邊緣計算層完成任務的總價值。