智慧煤矿中边缘计算任务分配研究

2021-07-02朱晓娟张浩

工矿自动化 2021年6期

朱晓娟，张浩

(安徽理工大学计算机科学与工程学院，安徽淮南 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]仅基于平衡分配的思想，按照计算量的降序和任务的最大时延限制来生成任务队列，而本文基于动态优先级生成任务队列，综合考虑了任务的计算量、紧迫程度和固定优先级(重要程度)，优先处理紧迫且重要的任务，具有较低的平均处理时延，在同等时间内完成了更多任务。