基于多Agent技术的云计算任务分解方法研究

赵 莉,李君茹

(信阳农林学院 信息工程学院,河南 信阳 464000)

随着移动通信网的飞速发展和智能终端的快速普及,云计算技术在人们日常工作和生活中得到了广泛的应用。人们在云计算模式下通常会在不同设备资源、网络和工作场景中变换计算模式[1]。在上述环境中,为了完成终端无法完成或未完成的任务,需要在短时间内将任务迁移到云端平台中。任务迁移指的是在保持任务运行的状态下在主机节点中将任务转移到另一个节点中,在任务迁移中任务分解是最重要的步骤,直接影响着任务迁移的效果[2]。

王晨旭等[3]对任务粒度进行计算,在设计结构矩阵中分析任务的分布情况,根据分析结果获得任务的解耦水平,在动态解耦的基础上实现任务分解,但是该方法无法获取云计算任务之间存在的联系,导致网络负载高,任务分解次数多。胡亚楠等[4]对激活权重和激活规则的不一致性进行分析,根据分析结果构建任务分解目标函数,采用改进粒子群优化(Modified particle swarm optimization,MPSO)算法对目标函数求解,实现任务分解,但是该方法分解任务所用的时间较长,进而增加了任务执行时间。

为了解决上述方法中存在的问题,本文提出基于多Agent技术的云计算任务分解方法。首先,采用与或依赖图分析云计算任务之间存在的联系,依据分析结果采用模糊聚类方法对云计算任务进行聚类处理;然后,通过多Agent技术对云计算任务进行分解,以提高任务执行效率,降低网络负载与任务分解次数,缩短分解与执行时间;最后,与其它算法进行云计算任务分解对比实验,以验证本文方法的优越性。

1 云计算任务分析与处理

用四元组Y=〈L,S,O,H〉表示云计算任务,其中L描述的是由任务的中间结果、初始条件、目标、局部数据和全局数据构成的知识集;S代表的是云计算任务对应的操作集;O代表的是云计算任务中初始条件构成的集合;H={l1,l2,…,ln} 描述的是目标集,里面通常存在一些相关知识,是知识集L的子集。

用三元组〈M,E1,E2〉表示操作集对应的与或依赖图。其中,集合M由云计算任务的操作构成,即节点集;E1⊆s×s、E2⊆s×s均代表的是边集,其主要作用是描述操作之间存在的依赖关系;用〈s1|s2〉⊆E1表示在网络中节点s1与节点s2之间为或依赖关系,用〈s1&s2〉⊆E2表示在网络中节点s1与节点s2之间为与依赖关系。

用{si|〈s,si〉E1}表示操作s在网络中对应的或依赖集,其中E1为或连接边集,存在于与或依赖图〈S,E1,E2〉中,其中节点s、si均存在于集合S中。

用{si|〈s,si〉E2}表示操作s在网络中对应的与依赖集,其中E2为与连接边集,存在于与或依赖图〈S,E1,E2〉中。

针对云计算任务Y1=〈L,S,O,H〉进行考虑,其中L={l0,l1,l2,…,l11},O={o0,o1,o2,o3,o4},S={s0,s1,s2,s3,s4,s5},不同操作下存在的输入与输出信息如下:

(1)s1为输入信息{l1,l2,l3,l4},输出信息{l11};

(2)s2为输入信息{l0,l2,l3,l8,l11},输出信息{l6};

(3)s3为输入信息{l0,l1,l3,l8},输出信息{l7};

(4)s4为输入信息{l1,l11},输出信息{l8};

(5)s5为输入信息{l0,l11},输出信息{l8}。

根据上述信息,获得不同操作在任务Y1中的与或依赖图,如图1所示。

图1 操作的与或依赖图

图1中s0表示整个任务,与依赖关系用小段圆弧表示。通过图1获得云计算任务之间存在的关系,在此基础上基于多Agent技术的云计算任务分解方法采用模糊聚类方法[5]对云计算任务进行聚类处理,具体步骤如下:

(1)根据云计算任务在云环境中的依赖关系Wi建立初始化样本矩阵;

(2)为了消除初始化样本矩阵中存在的量纲,标准化处理初始化样本矩阵[6]

(1)

(2)

通过标准化处理压缩数据,将其控制在区间[0,1]内。

(3)用tij表示不同云计算任务的相似度,其计算公式如下

(3)

(4)

(5)设置阈值β,当阈值在区间[0,1]内取值时,表示云计算任务完成聚类。

2 任务分解方法

采用多Agent技术[7,8]对云计算任务进行分解,分析Agent能力特征,获取云计算任务分解过程中的主要任务,在层次规范分解法的基础上完成云计算任务的分解。

用Dij表示用户j对云计算任务的满意度,采用模糊表示法对用户满意度进行量化处理,将其转变为{0,0.25,0.5,0.75,1},其中1表示用户对云计算任务非常满意,0表示用户对云计算任务非常不满意[9]。

(5)

将任务根据结构和功能进行分解,获得多个子任务,当子任务无法继续分解时,获得云计算的最小任务,此时停止分解任务;如果子任务还能够继续分解,测评用户对云计算子任务的满意度[11],设置阈值μ,当用户满意度达到阈值μ时,停止任务分解。

在任务分解过程中,设置的阈值μ需要满足下述条件:

(1)当sj属于最小的任务时,停止对任务的分解操作,当sj不属于最小的任务时,测评用户对任务sj的满意度[12];

(2)当si大于阈值μ时,停止对任务的分解操作,当si小于阈值μ时,继续分解任务sj。

采用多Agent技术对任务分解时,需要确定任务的主要内容和主要活动。根据活动和内容的特点,对任务进行分解,用Y表示初始任务,存在于网络的任务系统中,即根节点;用Q、A表示中层任务,即分支节点,上层任务通常由中层任务构成,因利用单一的Agent无法实现中层任务,因此要继续分解中层任务,用Qi、Aj表示简单任务,该任务可通过Agent单独执行,即子节点。

根据时间对任务中存在的主要活动进行划分。如果任务对时间顺序的要求较高,可以先分析任务的流程,获取子任务。在任务的任务树中包含了较多分支,每个子节点在任务数中都可以描述1个简单的任务,即具体的分解步骤,任务主要活动对应的顺序可通过分解树得以体现,满足任务在分解过程中的时间要求[13,14]。

根据任务功能对任务的主要内容进行分解。任务数可以体现任务的主要内容,根据并行的规则对任务进行执行。根据Agent之间的交互和通信完成任务的分解,具体步骤如下:

(1)在主要活动和主要内容的基础上,根据任务自身的特点,获得n个任务的子任务s1,s2,…,sn。

(2)对上述过程获得的子任务的完整度进行检查,即子任务s1,s2,…,sn是否可以表达原始的任务。如果可以则运行步骤(3),如果不可以则返回步骤(1)。

(3)检查子任务s1,s2,…,sn之间是否存在联系,即子任务是否独立,执行子任务对其它子任务的执行会不会产生影响。如果子任务之间不存在联系,判定任务独立,则运行步骤(4),如果子任务之间存在联系,返回步骤(2)。

(4)在执行任务中,对任务的可行性进行检查,即是否能够通过单独的Agent完成子任务si。子任务的可行性对其分解过程的合理性产生直接影响,是子任务分解过程中的重要步骤[15]。当子任务si中i>0时,则判定子任务具有可行性,运行步骤(5),反之不可行,返回步骤(3)。

(5)确保所有子任务在分解过程中都有对应的Agent执行,即对任务分解的完整性进行检查,如果子任务完成分解,运行步骤(6),如果任务没有完全分解,返回步骤(4)。

(6)每个子任务通过上述处理后,获得对应的输出和输入,并有对应的Agent执行任务,完成任务的分解。

基于多Agent技术的任务分解方法对任务分解的具体流程如图2所示。

图2 云计算任务的分解流程图

3 实验与分析

为了验证基于多Agent技术的云计算任务分解方法的整体有效性,本文以云计算平台为实验对象,环境为网络仿真器2.0(Network simulator 2.0,NS2.0)仿真软件、Microsoft Windows XP操作系统、Intel(R)Celeron(R)2.6 GHz处理器、16 GB内存,进行1次仿真实验测试。设定实验参数为Windows10操作系统、20 min操作时间、150 Hz工作频率、JAVA编程语言。

将网络负载、任务分解次数、任务分解时间和任务执行时间作为指标,采用基于多Agent技术的云计算任务分解方法,与文献[3]和文献[4]方法进行对比测试。

(1)网络负载。

网络负载受任务分解情况的影响,任务分解效果越好网络负载越低,本文方法、文献[3]方法和文献[4]方法的网络负载情况如图3所示。

分析图3可知,在多次云计算任务分解测试中,本文方法的网络负载均在104byte以下,文献[3]方法和文献[4]方法的网络负载均高于1.5×104byte。对比上述方法的测试结果可知,本文方法在云计算任务分解后的网络负载较低,表明本文方法可高质量地完成云计算任务的分解。因为本文方法对云计算任务分解之前,分析了云计算任务之间存在的关系,在分析结果的基础上对云计算任务进行分解,降低了网络负载。

图3 网络负载情况图

(2)任务分解次数。

采用本文方法、文献[3]方法和文献[4]方法对5个云计算任务进行分析,对比不同方法所用的分解次数,测试结果如图4所示。

图4 不同方法的任务分解次数棒图

分析图4可知,对5个云计算任务进行分解时,本文方法所用的分解次数均控制在5次以内,与文献[3]方法和文献[4]方法相比,本文方法对同一个云计算任务进行分解时,所用的分解次数较少,验证了本文方法的有效性。

(3)任务分解时间。

采用本文方法、文献[3]方法和文献[4]方法对云计算任务进行分解,对比不同方法分解云计算任务所用的时间,测试结果如表1所示。

由表1可知,任务分解时间与任务数量之间呈正比关系。随着任务数量的增加,本文方法、文献[3]方法和文献[4]方法分解任务所用的时间不断增加,但在任务数量相同时,本文方法所用的分解时间均低于文献[3]方法和文献[4]方法,表明本文方法可在较短的时间内完成云计算任务的分解,具有较高的任务分解效率。

表1 云计算任务分解时间表

(4)任务执行时间。

将任务执行时间作为指标,采用本文方法、文献[3]方法和文献[4]方法对2 000个以下和2 000个以上的云计算任务量进行分解,对比分解后任务的执行时间,执行时间越短,表明方法越有效,测试结果如图5所示。

图5 任务执行时间棒图

通过图5可知,采用本文方法对2 000个以下和2 000个以上的云计算任务量进行分解后,任务的执行时间均控制在1 s以内,远远低于其他2种方法,因为本文方法可在短时间内完成云计算任务的分解,进而降低了任务执行所用的时间,验证了本文方法的有效性。

4 结束语

任务分解是管理系统研究的重要内容,通过任务分解可以有效减少任务执行时间、优化网络资源、提高网络工作效率。由于进行云计算任务分解时,传统方法分解次数过高,任务执行时间较长,且网络负载量较大,故本文采用多Agent技术对云计算任务分解方法展开研究。本文方法根据云计算任务之间存在的联系,采用多Agent技术实现云计算任务的分解,不仅解决了目前方法中存在的问题,还能更快速、精准地分解云计算任务。在后续研究中,将对本文算法进行改进,缩短运算时间,旨在进一步提高云计算任务分解效率。