群智感知计算下多终端引擎任务有效分配方法

张 洋,郑云鹏

(长春工业大学人文信息学院,吉林 长春 130000)

1 引言

计算机在当前的工作、日常生活中应用广泛[1],随着企业的生产、经营等多任务的信息化,工作流管理系统得到了关注。工作流主要是指业务在计算机环境下进行自动化[2],其中包括工作流多终端引擎。多终端引擎的一个重要功能就是将业务内的各项任务分发到合适的执行者中,以此执行任务。但多终端引擎也存在任务过多导致出现分配错乱的问题。

为了解决这一问题,需要对多终端引擎任务分配方法进行研究。范泽军[3]等人提出基于约束的空间众包多阶段任务分配方法,该方法首先对不同的目标进行优化并对任务路径集合进行获取,将路径起点及终点处对任务的参与者进行确立,根据上述流程,将任务分解成不同的子任务,以此提升任务分配效率,该方法分解子任务时分解效果不明显,但是存在分配效能低的问题。张涛[4]等人提出基于改进烟花算法的多目标多机器人任务分配方法,该方法优先探讨了目标排序方法,确立的目标选择策略为了明确所提方法的性能是否最优,选取七个实例与其进行对比测试,并对所提方法与四种多目标算法进行比较分析,根据目标的解集质量与覆盖度,对任务进行规划分配,实现任务分配方法,但是该方法进行对比测试时效果不明显,导致任务在分配过程中分配时间长。陈侠[5]等人提出多UAV攻击移动目标的协同任务分配与航迹规划方法,该方法首先构建了任务分配模型,采用蚁群算法对模型中的多个移动目标进行规划,从中得出效费差最大的任务分配和规划方案,但是该方法规范效果不完善,存在负载均衡度差的问题。

为了解决上述方法中存在的问题,提出基于群智感知计算的多终端引擎任务分配方法。

2 基于群智感知计算的多终端引擎数据采集

群智感知计算[6]的本质是一种特殊的无线传感网络,节点的移动性是它的主要特征。由于群智感知涉及的方面比较广,其中有感知数据采集、数据分析和处理等。为了实现多终端引擎任务分配方法,首先需要采用群智感知计算方法对多终端引擎的状态数据进行采集。

2.1 群智感知系统建模

多终端引擎中存在大部分冗余感知数据,所以针对这些冗余感知数据对感知区域进行时空域划分,根据划分过程对建立模型,以达到降低多终端引擎节点数据采样次数和冗余数据的目的,最终对处理的数据进行采集,实现基于群智感知计算的多终端引擎数据采集。

2.1.1 群智感知时空域划分

多终端引擎通过群智感知计算进行数据采集及范围感知,从中增强了时空数据的特征,为了便于更好的处理感知数据,需要对时空域进行离散化[7]。

假设n个节点会组建成群智感知节点网络,那么它的集合就由U={u1,u2,u3,…,un}来描述。在感知区域中,这些节点以固定轨迹进行移动,根据移动的固定频率对多终端引擎数据进行信息采集。在t时刻时,节点ui的位置标记为Loci(t),这时划分的时空域流程如下所示:

1)将感知区域在空间域中划分成相同的单元格,它的大小就是感知空间粒度。设置划分的单元格为m个,那么感知区域标志为C={c1,c2,c3,…,cm}。

2)对节点感知时长进行划分,取得感知周期Tsp,当开始进行感知周期时,节点会自行采样,将数据输送到远程服务器中,为了便于建立感知系统模型,需要满足于下述条件:

①通过多个感知周期r构建成的覆盖周期Tcp,即Tcp=rTsp。

②经多个覆盖周期组成的节点就是时间跨度。

满足上述条件后,构建出群智感知系统模型,这时感知节点时空域划分如图1所示。

图1 感知空间域划分

2.2 群智感知网络相关概念

定义1:感知覆盖。当感知周期更新时,有某个移动节点位置在单元格中,这时单元格已经被覆盖。将δj(Loci(t))标记为t时刻节点ui是否对单元格cj进行覆盖,那么方程表达式定义为

δj(Loci(t))

(1)

式中,δj(Loci(t))=1时,标记为单元格cj被ui覆盖;当δj(Loci(t))=0时,标记为没有被覆盖。and标记为连接词,if标记为如果,otherwise标记为除此之外。在采样过程中,单元格只需要被覆盖一次,不需要重复覆盖,而覆盖周期就是感知粒度。

定义2:设置(1,2,3,…,d)为覆盖周期,在(1,2,3,…,d)中节点集合U覆盖单元格cj节点的总次数为

(2)

式中,CSDj(k)表示覆盖总次数。

定义3:当第k个覆盖周期存有一个单元格cj∈C时,它的覆盖总次数要高于覆盖因子ε(ε≥1),这说明单元格已经被覆盖,定义为:CSDj(k)≥ε,即充足感知覆盖。

定义中,传统无线网的K-覆盖就是覆盖因子[8]的范围,它决定了数据的冗余程度。同理,当ε的取值越大时,冗余数据逐渐增多,产生的耗能影响越大。对相同单元格的ε感知数据进行融合后,就可以提升感知数据的精确度。

2.3 基于群智感知的多终端引擎状态数据采集

基于上述分析,采用群智感知计算方法对多终端引擎数据进行采集,具体采集流程如下所示:

当覆盖周期开始时,就需要通过节点对覆盖感知表SCT进行清理,将其数据清空,cj被ui采样前,应优先对SCT进行判断,判断在SCTi中是否存在与cj相对应的元组,若元组内有和覆盖因子相同的采样次数,那么不进行采样,若没有,就进行采样,同时对SCT进行更新。如果SCT没有对应的元组,就直接将小于cj、大于1的元组加入到SCT中;如果SCT具有对应的元组,那么就将采样后的单元格更新为ej+1,ej+1就是采集后的多终端引擎状态数据,以此完成多终端引擎状态数据的采集。

3 多终端引擎任务分配

3.1 多终端引擎任务分配模型

多终端引擎是工作流系统的核心所在[9],它的主要任务在于内部的任务分配器分配系统任务,从而保证多终端引擎能够实现高效分配效率,那么多终端引擎任务分配器模型如图2所示。

图2 多终端引擎任务分配器模型

图2中,如果多终端引擎任务的总数目标记为S,运行节点标记为K,而R={R1,R2,…,Rn}标记为用户相关权限集合,任务集合通过W={W1,W2,…,Wn}来表示。当多终端引擎发出不同类型任务时,它的发送时间具有随机性,可以对人员Ri处理任务Wj时对其进行处理,处理的平均时间标记为Ti,j。

任务分配器[10,11]在第x天分配任务时,需要对不同类型任务负载相对均衡度进行确立,同时还要在流程动态变化的基础上,在规定时间内以最快速度完成任务分配,因此采用任务分配算法对多终端引擎任务进行分配。

3.2 任务分配算法

依据任务分配算法[12]的主要原则给出分配算法的具体步骤,多终端引擎任务分配算法的主要流程如下所示:

1)首先在候选用户集合中挑选出可以执行任务的用户,并对其角色进行匹配,依据待分配任务T对接受任务的用户角色进行确立。由于用户角色是动态变化的,可以将动态任务分配给具有多个任务角色的用户。即,在可以完成任务T的具体角色集合JX中进行选取,从中获取行的集合RJ。

2)技能匹配。用户接受任务T时必须具备能够完成该任务的技能,依据技能集合JT,在用户集合RJ中选出RJ的所有用户,取得集合RT,J。

3)相对局部负载LX和经验值EX需要在RT,J中进行确立,并权衡确立后的结果,从中选择最优用户接收该任务。设置两个权重系数a、b确定最佳用户,这时的最佳用户由RT来标记,从中得出:RT=aLX+bEX。式中,a,b均为大于0的常数,同时a+b=1,RT的值标记为最佳用户。

根据采集的多终端引擎状态数据,构建出多终端引擎任务分配器模型,依据多终端引擎在执行过程中的用户状态及负载运行状况,采用任务分配算法将任务分配到负载低、经验高的用户中,从而达到缩短任务执行时间,并提高了分配效率,实现多终端引擎任务分配方法。

4 实验与分析

为了验证多终端引擎任务分配方法的整体有效性,需要对该方法进行实验对比测试。

采用本文所提的基于群智感知计算的多终端引擎任务分配方法(方法1)、文献[3]提出的基于约束的空间众包多阶段任务分配方法(方法2)和文献[5]提出的多UAV攻击移动目标的协同任务分配与航迹规划(方法3)对多终端引擎任务分配方法进行测试对比。

为了验证多终端引擎任务的分配效率,采用方法1、方法2和方法3分别对多终端引擎任务分配时间进行对比测试,设定多终端引擎任务数目为500个,对其进行分配,分配时间越短,说明分配速度越快,分配效率越高,具体测试结果如图3所示。

图3 多终端引擎任务分配时间测试

根据图3中的数据发现,三种方法随着多终端引擎任务数目的增加,分配时间都呈现出上升趋势。从总体来看,方法1的分配时间要低于方法2和方法3,由此可见方法1的分配速度最快,分配效率最高。而方法3整个测试过程中,分配时间最高,可知方法3的分配速度最慢,同时分配效率最低。

基于上述对多终端引擎任务分配的测试,验证了方法1的分配时间速度快,在此基础上利用三种方法分别对多终端引擎任务分配效能进行测试,分配效能越高,说明多终端引擎任务分配效果越好,完成任务的速度越快,测试结果如图4所示。

图4 多终端引擎任务分配效能测试

分析图4中的数据可知,三种方法随着任务数目的增加,分配效能都呈现出下降趋势,在测试期间,方法1的分配效能要优于方法2和方法3,同时运动轨迹下降速度较慢,可见方法1的分配效能最高,多终端引擎任务分配效果最好。

而方法2和方法3在初始测试时,分配效能一致,当任务数目逐步增加后,方法3的运动轨迹下降速度要比方法2的下降速度快,可见方法3是三种方法中分配效能最差的,同时它的多终端引擎任务分配效果低。

综上所述,方法1的分配效能最高,这是因为方法1采集了多终端引擎任务状态数据,大大的提升了多终端引擎任务分配效果,进而降低了多终端引擎任务分配效能下降速度。

利用方法1、方法2和方法3分别对多终端引擎任务分配后的负载均衡度进行对比测试,负载均衡度越高,说明多终端引擎的稳定性越强,测试结果如表1所示。

表1 不同方法的负载均衡度对比测试

根据表1中的数据发现,在整体测试期间,方法1的负载均衡度始终保持最高,其次为方法2、方法3,这说明方法1的多终端引擎稳定性最高,方法3的稳定性最低。

5 结束语

传统的多终端引擎任务存在时间长、分配效能低、负载均衡度差的问题。针对上述问题,提出基于群智感知计算的多终端引擎任务分配方法,该方法首先采用群智感知方法对多终端引擎状态任务数据进行采集,根据采集的数据构建出任务分配模型,利用任务分配算法对多终端引擎任务进行分配,从而实现多终端引擎任务分配方法。该方法对多终端引擎任务分配方法的有效性有着显著的提升,在今后多终端引擎任务分配方法中占据着重要地位。