面向智慧校园工作流应用的多目标计算迁移方法及装置

1.本发明涉及计算机技术领域，具体涉及一种面向智慧校园工作流应用的多目标计算迁移方法及装置。


背景技术：

2.近年来，新一代信息通信技术、移动云计算和物联网技术不断更新与发展，给高校教育的信息化建设带来了深刻的影响。在智慧校园中，存在一些非结构化的工作流，如：多媒体互动教学、校园智能监控、一卡通系统等。这类任务对后台算力、存储能力的要求较高，而传统的智能设备往往内存较小、耗电快，在一定程度上限制了智慧校园的发展。
3.移动边缘计算(mobile edge computing，mec)的出现为解决这个问题提供了希望。在mec赋能的智慧校园场景中，边缘服务器通常被安排在离用户更近的网络边缘，以提供低响应延迟和高质量服务。移动用户产生的计算任务可以选择迁移到最近的边缘服务器进行处理。
4.针对现有的mec环境下的研究，大部分文献未充分考虑到智慧校园用户的真实需求。gholami等人在文献“collaborative cloud-edge-local computation offloading for multi-component applications”中讨论了多组件应用的计算迁移问题，使用多目标混合整数线性规划算法有效地降低了系统的能耗和端到端的延迟。dong等人在文献“elastic container scheduling for stochastically arrived workflows in cloud and edge computing”提出了一种针对云和边缘中随机到达的工作流的弹性资源调度方法，在满足服务质量约束的同时最小化长期运营成本。上述工作可能并不能满足智慧校园中用户的真实需求，如，用户对优化指标的偏好性，不同的用户可能对时间消耗或能量消耗等指标的优化重要性程度是不同的；且仅从用户设备方面考虑优化，未考虑边缘服务器集群的状态，如，边缘服务器的资源利用率、负载均衡等。


技术实现要素：

5.针对上述提到的技术问题。本技术的实施例的目的在于提出了一种面向智慧校园工作流应用的多目标计算迁移方法及装置，来解决以上背景技术部分提到的技术问题，完成对智慧校园中设备所产生的工作流应用的计算迁移，实现了符合用户偏好的针对系统时间消耗、能量消耗以及边缘服务器负载均衡的多目标优化。
6.第一方面，本发明提供了一种面向智慧校园工作流应用的多目标计算迁移方法，包括以下步骤：
7.获取用户集合和用户的任务集合，根据用户的任务集合构建工作流集合，根据用户集合和工作流集合随机初始化构建父代种群；
8.基于父代种群进行二元锦标赛填充交配池，进行交叉变异生成子代种群；
9.将父代种群加入子代种群生成混合种群，计算各解决方案的指标，根据各解决方案的指标对混合种群进行非支配排序，得到非支配排序结果，根据非支配排序结果迭代更
新候选解；
10.在迭代过程中，响应于确定所选出的下一代父代种群符合种群大小，构建用户关于各项指标的重要性程度的判断矩阵，基于判断矩阵计算符合用户偏好的指标权重，基于指标权重构建归一化方程，并通过归一化方程寻找出最优迁移策略。
11.作为优选，根据用户的任务集合构建工作流集合，根据用户集合和工作流集合随机初始化构建父代种群，具体包括：
12.根据任务集合t＝{t1,t2,...t
t
}的顺序结构构建工作流集合w＝{w1,w2,...,ww}，采用两元组w＝g(t,b)表示设备需要计算的工作流，采用有向无环图表示工作流的建模，其中，b表示任务之间的依赖关系；
13.针对用户集合m∈{1,2,3,...,m}与工作流集合w＝{w1,w2,...,ww}随机初始化构建父代种群，其中，每一个任务对应一个基因，每一个计算迁移策略对应一条染色体，每一个任务的计算位置被编码为基因数n∈{0,1,...,n,n+1}，其中，n为0表示任务在本地终端执行，n为n+1表示任务在云端执行，其他则表示任务在边缘服务器集群执行。
14.作为优选，基于父代种群进行二元锦标赛填充交配池，进行交叉变异生成子代种群，具体包括：
15.计算父代种群各个染色体的所支配的解决方案的数量，在多目标优化问题中，对于两个任意解s1及解s2的所有目标而言，解s1的所有目标值都优于解s2的目标值，则解s1支配解s2，其中，用υ(s)表示解s所支配的解决方案的数量；
16.通过适应度函数计算父代种群各个染色体的适应度：
17.fit(s)＝η(s)+κ(s)；
18.其中，η(s)为所有支配解s2的解的υ(s)值之和，κ(s)的计算公式如下：
[0019][0020]
其中，表示解s和距离解s第k近的解之间的距离；
[0021]
从父代种群中随机选取两个染色体；比较两个染色体的适应度，选择适应度更高的染色体加入交配池；重复以上步骤，直到交配池中染色体的数量达到一定数量为止；
[0022]
对父代种群进行随机交叉、变异操作生成子代种群。
[0023]
作为优选，指标包括时间消耗、能量消耗、负载均衡，计算各解决方案的指标，具体包括：
[0024]
通过时间消耗函数计算各解决方案的总时间消耗：
[0025][0026]
其中，f
m,n
是一个用来判断用户m的任务是否迁移到服务器n迁移的标志，当任务在用户的本地终端进行计算时，f
m,n
是0，其他情况则f
m,n
是1；是总时间消耗，是任务在本地终端计算的时间消耗，是任务迁移时所消耗的时间；
[0027]
任务在本地终端计算的时间消耗计算为：
[0028][0029]
其中，d
m,n
表示待处理任务的数据大小，ξ
m,n
表示处理设备的计算能力；
[0030]
任务迁移时所消耗的时间计算为：
[0031][0032]
其中，表示任务的传输时间，主要由任务上传数据以及下载数据的时间组成；表示任务的执行时间，主要由计算任务数据量和计算能力计算得出；任务的传输时间与任务的执行时间可分别计算为：
[0033][0034][0035]
其中，v
m,n
表示用户m迁移到计算节点n的传输速率，表示为：
[0036][0037]
其中，bn表示计算节点的带宽，χ是信道的噪声功率密度，是设备的传输功率，和φ
m,n
分别表示用户与边缘服务器之间的无线信道增益和带宽；
[0038]
通过能量消耗函数计算各解决方案的总能量消耗：
[0039][0040]
其中，是总能量消耗，是任务在本地终端计算的能量消耗，是任务迁移时所消耗的能量，与分别计算为：
[0041][0042][0043]
其中，是设备的运行功率，和分别是任务传输能耗和闲时能耗；与可分别计算为：
[0044][0045][0046]
其中，是设备的传输功率，是设备的闲时功率；
[0047]
通过负载均衡函数计算各解决方案的负载均衡：
[0048][0049]
其中，on是边缘服务器集群中被占用的边缘服务器数量，rn与arn分别表示边缘服务器的资源利用率及平均资源利用率，rn和arn可分别计算为：
[0050][0051][0052]
其中，tn表示边缘服务器集群中边缘服务器n完成的任务数，w
m,n
表示用户m迁移到边缘服务器n的任务数。
[0053]
作为优选，根据各解决方案的指标对混合种群进行非支配排序，得到非支配排序结果，根据非支配排序结果迭代更新候选解，具体包括：
[0054]
根据各解决方案的各指标计算混合种群各个染色体的所支配的解决方案的数量，并对混合种群各个染色体进行非支配排序，将混合种群的各个染色体根据不同的支配关系划分为不同层；
[0055]
根据支配关系筛选填充下一代父代种群；
[0056]
判断所选出的下一代父代种群是否符合种群大小，响应于确定所选出的下一代父代种群不符合种群大小，根据支配关系填满下一代父代种群或根据聚类分析删除多余的解。
[0057]
作为优选，构建用户关于各项指标的重要性程度的判断矩阵，基于判断矩阵计算符合用户偏好的指标权重，具体包括：
[0058]
用户关于各项指标的重要性程度的判断矩阵为：
[0059][0060]
其中，a
11
至a
33
是基于用户偏好的重要性程度对比打分，其范围是1～3；
[0061]
对所述判断矩阵列中的元素进行归一化，将归一化后的元素以行为单位计算平均值，得到每个指标的指标权重α、β、γ。
[0062]
作为优选，基于指标权重构建归一化方程，并通过归一化方程寻找出最优迁移策略，具体包括：
[0063]
在每次迭代过程中根据归一化方程计算总收益
[0064][0065]
其中，α、β、γ是各指标权重，是各指标归一化后的数值；
[0066]
对比每次迭代的总收益，确定总收益的最大值所对应的计算迁移测量为最优迁移策略，并得到最优迁移策略对应的指标。
[0067]
第二方面，本发明提供了一种面向智慧校园工作流应用的多目标计算迁移装置，
包括：
[0068]
父代种群构建模块，被配置为获取用户集合和用户的任务集合，根据用户的任务集合构建工作流集合，根据用户集合和工作流集合随机初始化构建父代种群；
[0069]
交叉变异模块，被配置为基于父代种群进行二元锦标赛填充交配池，进行交叉变异生成子代种群；
[0070]
迭代模块，被配置为将父代种群加入子代种群生成混合种群，计算各解决方案的指标，根据各解决方案的指标对混合种群进行非支配排序，得到非支配排序结果，根据非支配排序结果迭代更新候选解；
[0071]
最优迁移策略寻找模块，被配置为在迭代过程中，响应于确定所选出的下一代父代种群符合种群大小，构建用户关于各项指标的重要性程度的判断矩阵，基于判断矩阵计算符合用户偏好的指标权重，基于指标权重构建归一化方程，并通过归一化方程寻找出最优迁移策略。
[0072]
第三方面，本发明提供了一种电子设备，包括一个或多个处理器；存储装置，用于存储一个或多个程序，当一个或多个程序被一个或多个处理器执行，使得一个或多个处理器实现如第一方面中任一实现方式描述的方法。
[0073]
第四方面，本发明提供了一种计算机可读存储介质，其上存储有计算机程序，该计算机程序被处理器执行时实现如第一方面中任一实现方式描述的方法。
[0074]
相比于现有技术，本发明具有以下有益效果：
[0075]
(1)本发明提出的面向智慧校园工作流应用的多目标计算迁移方法及装置利用有向无环图构建工作流模型，再利用层次分析法分析符合用户偏好的目标权重，最终通过遗传算法针对智慧校园中智能设备所产生的工作流进行任务迁移，为智慧校园用户任务制定合适的计算迁移策略。
[0076]
(2)本发明提出的面向智慧校园工作流应用的多目标计算迁移方法及装置实现了符合用户偏好的针对系统时间消耗、能量消耗以及边缘服务器负载均衡的多目标优化。
附图说明
[0077]
为了更清楚地说明本发明实施例中的技术方案，下面将对实施例描述中所需要使用的附图作简要介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域的普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。
[0078]
图1是本技术的一个实施例可以应用于其中的示例性装置架构图；
[0079]
图2为本技术的实施例的面向智慧校园工作流应用的多目标计算迁移方法的流程示意图；
[0080]
图3为本技术的实施例的面向智慧校园工作流应用的多目标计算迁移方法的模拟的智慧校园云边端协同网络结构图；
[0081]
图4为本技术的实施例的面向智慧校园工作流应用的多目标计算迁移方法的模拟的工作流的任务模型图；
[0082]
图5为本技术的实施例的面向智慧校园工作流应用的多目标计算迁移方法的基因交叉示意图；
[0083]
图6为本技术的实施例的面向智慧校园工作流应用的多目标计算迁移方法的基因变异示意图；
[0084]
图7为本技术的实施例的面向智慧校园工作流应用的多目标计算迁移装置的示意图；
[0085]
图8是适于用来实现本技术实施例的电子设备的计算机装置的结构示意图。
具体实施方式
[0086]
为了使本发明的目的、技术方案和优点更加清楚，下面将结合附图对本发明作进一步地详细描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其它实施例，都属于本发明保护的范围。
[0087]
图1示出了可以应用本技术实施例的面向智慧校园工作流应用的多目标计算迁移方法或面向智慧校园工作流应用的多目标计算迁移装置的示例性装置架构100。
[0088]
如图1所示，装置架构100可以包括终端设备101、102、103，网络104和服务器105。网络104用以在终端设备101、102、103和服务器105之间提供通信链路的介质。网络104可以包括各种连接类型，例如有线、无线通信链路或者光纤电缆等等。
[0089]
用户可以使用终端设备101、102、103通过网络104与服务器105交互，以接收或发送消息等。终端设备101、102、103上可以安装有各种应用，例如数据处理类应用、文件处理类应用等。
[0090]
终端设备101、102、103可以是硬件，也可以是软件。当终端设备101、102、103为硬件时，可以是各种电子设备，包括但不限于智能手机、平板电脑、膝上型便携计算机和台式计算机等等。当终端设备101、102、103为软件时，可以安装在上述所列举的电子设备中。其可以实现成多个软件或软件模块(例如用来提供分布式服务的软件或软件模块)，也可以实现成单个软件或软件模块。在此不做具体限定。
[0091]
服务器105可以是提供各种服务的服务器，例如对终端设备101、102、103上传的文件或数据进行处理的后台数据处理服务器。后台数据处理服务器可以对获取的文件或数据进行处理，生成处理结果。
[0092]
需要说明的是，本技术实施例所提供的面向智慧校园工作流应用的多目标计算迁移方法可以由服务器105执行，也可以由终端设备101、102、103执行，相应地，面向智慧校园工作流应用的多目标计算迁移装置可以设置于服务器105中，也可以设置于终端设备101、102、103中。
[0093]
应该理解，图1中的终端设备、网络和服务器的数目仅仅是示意性的。根据实现需要，可以具有任意数目的终端设备、网络和服务器。在所处理的数据不需要从远程获取的情况下，上述装置架构可以不包括网络，而只需服务器或终端设备。
[0094]
图2示出了本技术的实施例提供的一种面向智慧校园工作流应用的多目标计算迁移方法，包括以下步骤：
[0095]
s1，获取用户集合和用户的任务集合，根据用户的任务集合构建工作流集合，根据用户集合和工作流集合随机初始化构建父代种群。
[0096]
在具体的实施例中，步骤s1中根据用户的任务集合构建工作流集合，根据用户集
合和工作流集合随机初始化构建父代种群，具体包括：
[0097]
根据任务集合t＝{t1,t2,...t
t
}的顺序结构构建工作流集合w＝{w1,w2,...,ww}，采用两元组w＝g(t,b)表示设备需要计算的工作流，采用有向无环图表示工作流的建模，其中，b表示任务之间的依赖关系；
[0098]
针对用户集合m∈{1,2,3,...,m}与工作流集合w＝{w1,w2,...,ww}随机初始化构建父代种群，其中，工作流可以划分为多个子任务，每个子任务可以在用户终端、边缘服务器、远程云中心上执行。每一个任务对应一个基因，每一个计算迁移策略对应一条染色体，每一个任务的计算位置被编码为基因数n∈{0,1,...,n,n+1}，其中，n为0表示任务在本地终端执行，n为n+1表示任务在云端执行，其他则表示任务在边缘服务器集群执行。
[0099]
具体的，在构建父代种群之前还需输入遗传算法的关键参数，如迭代总次数、种群大小等。参考图3，用户的计算任务由终端设备产生。考虑到工作流应用的结构复杂性与终端设备在计算能力、内存上存在的局限性，一些计算密集型任务(控制任务、文件管理任务)可以迁移至边缘服务器、远程云中心上进行计算，计算完毕后仅将最终数据返回至终端设备。
[0100]
参考图4，智慧校园中结构复杂的任务(如：多媒体任务、学工信息门户等)被定义为工作流；工作流可以划分为多个子任务，且子任务之间存在时间及顺序依赖性；前驱任务计算完毕后可以传输相应的数据到后继任务，且后继任务必须将所有来自前驱任务的数据收集完毕才能开始计算。如：子任务1在计算完毕后传输相应的数据(15字节、25字节、35字节)到下一个任务节点(任务2、任务3、任务4)；对于任务5而言，必须将前驱任务(任务2、任务3、任务4)的传输数据(33字节、22字节、11字节)收集完毕后才能开始计算。
[0101]
s2，基于父代种群进行二元锦标赛填充交配池，进行交叉变异生成子代种群。
[0102]
在具体的实施例中，步骤s2具体包括：
[0103]
计算父代种群各个染色体的所支配的解决方案的数量，在多目标优化问题中，对于两个任意解s1及解s2的所有目标而言，解s1的所有目标值都优于解s2的目标值，则解s1支配解s2，其中，用υ(s)表示解s所支配的解决方案的数量；
[0104]
通过适应度函数计算父代种群各个染色体的适应度：
[0105]
fit(s)＝η(s)+κ(s)；
[0106]
其中，η(s)为所有支配解s2的解的υ(s)值之和，κ(s)的计算公式如下：
[0107][0108]
其中，表示解s和距离解s第k近的解之间的距离；
[0109]
从父代种群中随机选取两个染色体；比较两个染色体的适应度，选择适应度更高的染色体加入交配池；重复以上步骤，直到交配池中染色体的数量达到一定数量为止；
[0110]
对父代种群进行随机交叉、变异操作生成子代种群。
[0111]
具体的，解s对应一个染色体，适应度函数用于计算每个染色体对应解的适应度值，从而用来衡量解的质量。κ(s)是一个衡量解之间密度的值，为了避免不同解的η(s)相同而导致无法判断的情况，κ(s)与解决方案之间的距离有关。二元锦标赛通过不断进行比较，从而筛选出适应度更高的个体，并将其放入交配池中，这种方法可以有效地提高种群的适
应度，从而更快地收敛到最优解。交叉和变异是用于生成下一代种群的重要操作。如图5所示，交叉操作是指通过在染色体上随机选取两个交叉点，然后将对应的基因交换，形成两个子代的过程。如图6所示，变异操作是指对于每个染色体，以一定概率随机选择其中的一个基因，并以一定概率将其改变为另一个值，从而产生一个新的染色体的过程。通过这两种操作可以生成一批新的个体，即子代种群。
[0112]
s3，将父代种群加入子代种群生成混合种群，计算各解决方案的指标，根据各解决方案的指标对混合种群进行非支配排序，得到非支配排序结果，根据非支配排序结果迭代更新候选解。
[0113]
在具体的实施例中，指标包括时间消耗、能量消耗、负载均衡，步骤s3中计算各解决方案的指标，具体包括：
[0114]
通过时间消耗函数计算各解决方案的总时间消耗：
[0115][0116]
其中，f
m,n
是一个用来判断用户m的任务是否迁移到服务器n迁移的标志，当任务在用户的本地终端进行计算时，f
m,n
是0，其他情况则f
m,n
是1；是总时间消耗，是任务在本地终端计算的时间消耗，是任务迁移时所消耗的时间；
[0117]
任务在本地终端计算的时间消耗计算为：
[0118][0119]
其中，d
m,n
表示待处理任务的数据大小，ξ
m,n
表示处理设备的计算能力；
[0120]
任务迁移时所消耗的时间计算为：
[0121][0122]
其中，表示任务的传输时间，主要由任务上传数据以及下载数据的时间组成；表示任务的执行时间，主要由计算任务数据量和计算能力计算得出；任务的传输时间与任务的执行时间可分别计算为：
[0123][0124][0125]
其中，v
m,n
表示用户m迁移到计算节点n的传输速率，表示为：
[0126][0127]
其中，bn表示计算节点的带宽，χ是信道的噪声功率密度，是设备的传输功率，gm和φ
m,n
分别表示用户与边缘服务器之间的无线信道增益和带宽；
[0128]
通过能量消耗函数计算各解决方案的总能量消耗：
[0129][0130]
其中，是总能量消耗，是任务在本地终端计算的能量消耗，是任务迁移时所消耗的能量，与分别计算为：
[0131][0132][0133]
其中，是设备的运行功率，和分别是任务传输能耗和闲时能耗；与可分别计算为：
[0134][0135][0136]
其中，是设备的传输功率，是设备的闲时功率；
[0137]
通过负载均衡函数计算各解决方案的负载均衡：
[0138][0139]
其中，on是边缘服务器集群中被占用的边缘服务器数量，rn与arn分别表示边缘服务器的资源利用率及平均资源利用率，rn和arn可分别计算为：
[0140][0141][0142]
其中，tn表示边缘服务器集群中边缘服务器n完成的任务数，w
m,n
表示用户m迁移到边缘服务器n的任务数。
[0143]
在具体的实施例中，步骤s3中根据各解决方案的指标对混合种群进行非支配排序，得到非支配排序结果，根据非支配排序结果迭代更新候选解，具体包括：
[0144]
根据各解决方案的各指标计算混合种群各个染色体的所支配的解决方案的数量，并对混合种群各个染色体进行非支配排序，将混合种群的各个染色体根据不同的支配关系划分为不同层；
[0145]
根据支配关系筛选填充下一代父代种群；
[0146]
判断所选出的下一代父代种群是否符合种群大小，响应于确定所选出的下一代父代种群不符合种群大小，根据支配关系填满下一代父代种群或根据聚类分析删除多余的解。
[0147]
具体的，判断所选出的下一代父代种群是否符合种群大小。若不符合，根据支配关系填满所述下一代种群或根据聚类分析减少多出的解。若符合，则转至步骤s4。
[0148]
s4，在迭代过程中，响应于确定所选出的下一代父代种群符合种群大小，构建用户
关于各项指标的重要性程度的判断矩阵，基于判断矩阵计算符合用户偏好的指标权重，基于指标权重构建归一化方程，并通过归一化方程寻找出最优迁移策略。
[0149]
在具体的实施例中，步骤s4中构建用户关于各项指标的重要性程度的判断矩阵，基于判断矩阵计算符合用户偏好的指标权重，具体包括：
[0150]
用户关于各项指标的重要性程度的判断矩阵为：
[0151][0152]
其中，a
11
至a
33
是基于用户偏好的重要性程度对比打分，其范围是1～3；
[0153]
对判断矩阵列中的元素进行归一化，将归一化后的元素以行为单位计算平均值，得到每个指标的指标权重α、β、γ。
[0154]
具体的，以a
23
为例，当分数为1时，表示指标2和指标3同样重要；当分数为2时，表示指标2较指标3略微重要；当分数为3时，表示指标2较指标3非常重要。每个指标的指标权重(即矩阵的特征向量)通过和积法得出的。首先，对判断矩阵列向量进行归一化。随后，用归一化后的值，以行为单位算出平均值。所求得的平均值即为每个评价指标的指标权重α、β、γ。
[0155]
在具体的实施例中，步骤s4中基于指标权重构建归一化方程，并通过归一化方程寻找出最优迁移策略，具体包括：
[0156]
在每次迭代过程中根据归一化方程计算总收益
[0157][0158]
其中，α、β、γ是各指标权重，是各指标归一化后的数值；
[0159]
对比每次迭代的总收益，确定总收益的最大值所对应的计算迁移测量为最优迁移策略，并得到最优迁移策略对应的指标。
[0160]
具体的，α,β,γ是基于上述重要性程度的判断矩阵所得到的各评价指标权重，为总收益，是通过各候选解的指标经归一化后所得到。
[0161]
判断当前迭代次数是否为迭代总次数，若否，则进入步骤s2；若是，则寻找出最优迁移策略。每迭代一次，对应的各指标、收益、计算迁移策略都会被记录在文件中。通过归一化方程计算出每次迭代的总收益，通过不断对比每代的总收益，就可以得到收益的最大值，记为此时，收益所对应的计算迁移策略则为最优迁移策略。输出最优迁移策略及最优迁移策略对应的目标值。其中，所对应的计算迁移策略与各指标则为最优迁移策略及最优迁移策略对应的目标值。
[0162]
以上步骤s1-s4仅为步骤符号表示。
[0163]
进一步参考图7，作为对上述各图所示方法的实现，本技术提供了一种面向智慧校园工作流应用的多目标计算迁移装置的一个实施例，该装置实施例与图2所示的方法实施例相对应，该装置具体可以应用于各种电子设备中。
[0164]
本技术实施例提供了一种面向智慧校园工作流应用的多目标计算迁移装置，包
括：
[0165]
父代种群构建模块1，被配置为获取用户集合和用户的任务集合，根据用户的任务集合构建工作流集合，根据用户集合和工作流集合随机初始化构建父代种群；
[0166]
交叉变异模块2，被配置为基于父代种群进行二元锦标赛填充交配池，进行交叉变异生成子代种群；
[0167]
迭代模块3，被配置为将父代种群加入子代种群生成混合种群，计算各解决方案的指标，根据各解决方案的指标对混合种群进行非支配排序，得到非支配排序结果，根据非支配排序结果迭代更新候选解；
[0168]
最优迁移策略寻找模块4，被配置为在迭代过程中，响应于确定所选出的下一代父代种群符合种群大小，构建用户关于各项指标的重要性程度的判断矩阵，基于判断矩阵计算符合用户偏好的指标权重，基于指标权重构建归一化方程，并通过归一化方程寻找出最优迁移策略。
[0169]
下面参考图8，其示出了适于用来实现本技术实施例的电子设备(例如图1所示的服务器或终端设备)的计算机装置800的结构示意图。图8示出的电子设备仅仅是一个示例，不应对本技术实施例的功能和使用范围带来任何限制。
[0170]
如图8所示，计算机装置800包括中央处理单元(cpu)801和图形处理器(gpu)802，其可以根据存储在只读存储器(rom)803中的程序或者从存储部分809加载到随机访问存储器(ram)804中的程序而执行各种适当的动作和处理。在ram 804中，还存储有装置800操作所需的各种程序和数据。cpu 801、gpu802、rom 803以及ram 804通过总线805彼此相连。输入/输出(i/o)接口806也连接至总线805。
[0171]
以下部件连接至i/o接口806：包括键盘、鼠标等的输入部分807；包括诸如、液晶显示器(lcd)等以及扬声器等的输出部分808；包括硬盘等的存储部分809；以及包括诸如lan卡、调制解调器等的网络接口卡的通信部分810。通信部分810经由诸如因特网的网络执行通信处理。驱动器811也可以根据需要连接至i/o接口806。可拆卸介质812，诸如磁盘、光盘、磁光盘、半导体存储器等等，根据需要安装在驱动器811上，以便于从其上读出的计算机程序根据需要被安装入存储部分809。
[0172]
特别地，根据本公开的实施例，上文参考流程图描述的过程可以被实现为计算机软件程序。例如，本公开的实施例包括一种计算机程序产品，其包括承载在计算机可读介质上的计算机程序，该计算机程序包含用于执行流程图所示的方法的程序代码。在这样的实施例中，该计算机程序可以通过通信部分810从网络上被下载和安装，和/或从可拆卸介质812被安装。在该计算机程序被中央处理单元(cpu)801和图形处理器(gpu)802执行时，执行本技术的方法中限定的上述功能。
[0173]
需要说明的是，本技术所述的计算机可读介质可以是计算机可读信号介质或者计算机可读介质或者是上述两者的任意组合。计算机可读介质例如可以是——但不限于——电、磁、光、电磁、红外线或半导体的装置、装置或器件，或者任意以上的组合。计算机可读介质的更具体的例子可以包括但不限于：具有一个或多个导线的电连接、便携式计算机磁盘、硬盘、随机访问存储器(ram)、只读存储器(rom)、可擦式可编程只读存储器(eprom或闪存)、光纤、便携式紧凑磁盘只读存储器(cd-rom)、光存储器件、磁存储器件或者上述的任意合适的组合。在本技术中，计算机可读介质可以是任何包含或存储程序的有形介质，该程序可以
被指令执行装置、装置或者器件使用或者与其结合使用。而在本技术中，计算机可读的信号介质可以包括在基带中或者作为载波一部分传播的数据信号，其中承载了计算机可读的程序代码。这种传播的数据信号可以采用多种形式，包括但不限于电磁信号、光信号或上述的任意合适的组合。计算机可读的信号介质还可以是计算机可读介质以外的任何计算机可读介质，该计算机可读介质可以发送、传播或者传输用于由指令执行装置、装置或者器件使用或者与其结合使用的程序。计算机可读介质上包含的程序代码可以用任何适当的介质传输，包括但不限于：无线、电线、光缆、rf等等，或者上述的任意合适的组合。
[0174]
可以以一种或多种程序设计语言或其组合来编写用于执行本技术的操作的计算机程序代码，所述程序设计语言包括面向对象的程序设计语言—诸如java、smalltalk、c++，还包括常规的过程式程序设计语言—诸如“c”语言或类似的程序设计语言。程序代码可以完全地在用户计算机上执行、部分地在用户计算机上执行、作为一个独立的软件包执行、部分在用户计算机上部分在远程计算机上执行、或者完全在远程计算机或服务器上执行。在涉及远程计算机的情形中，远程计算机可以通过任意种类的网络——包括局域网(lan)或广域网(wan)—连接到用户计算机，或者，也可以连接到外部计算机(例如利用因特网服务提供商来通过因特网连接)。
[0175]
附图中的流程图和框图，图示了按照本技术各种实施例的装置、方法和计算机程序产品的可能实现的体系架构、功能和操作。在这点上，流程图或框图中的每个方框可以代表一个模块、程序段或代码的一部分，该模块、程序段或代码的一部分包含一个或多个用于实现规定的逻辑功能的可执行指令。也应当注意，在有些作为替换的实现中，方框中所标注的功能也可以以不同于附图中所标注的顺序发生。例如，两个接连地表示的方框实际上可以基本并行地执行，它们有时也可以按相反的顺序执行，这依所涉及的功能而定。也要注意的是，框图和/或流程图中的每个方框以及框图和/或流程图中的方框的组合，可以用执行规定的功能或操作的专用的基于硬件的装置来实现，或者可以用专用硬件与计算机指令的组合来实现。
[0176]
描述于本技术实施例中所涉及到的模块可以通过软件的方式实现，也可以通过硬件的方式来实现。所描述的模块也可以设置在处理器中。
[0177]
作为另一方面，本技术还提供了一种计算机可读介质，该计算机可读介质可以是上述实施例中描述的电子设备中所包含的；也可以是单独存在，而未装配入该电子设备中。上述计算机可读介质承载有一个或者多个程序，当上述一个或者多个程序被该电子设备执行时，使得该电子设备：获取用户集合和用户的任务集合，根据用户的任务集合构建工作流集合，根据用户集合和工作流集合随机初始化构建父代种群；基于父代种群进行二元锦标赛填充交配池，进行交叉变异生成子代种群；将父代种群加入子代种群生成混合种群，计算各解决方案的指标，根据各解决方案的指标对混合种群进行非支配排序，得到非支配排序结果，根据非支配排序结果迭代更新候选解；在迭代过程中，响应于确定所选出的下一代父代种群符合种群大小，构建用户关于各项指标的重要性程度的判断矩阵，基于判断矩阵计算符合用户偏好的指标权重，基于指标权重构建归一化方程，并通过归一化方程寻找出最优迁移策略。
[0178]
以上描述仅为本技术的较佳实施例以及对所运用技术原理的说明。本领域技术人员应当理解，本技术中所涉及的发明范围，并不限于上述技术特征的特定组合而成的技术
方案，同时也应涵盖在不脱离上述发明构思的情况下，由上述技术特征或其等同特征进行任意组合而形成的其它技术方案。例如上述特征与本技术中公开的(但不限于)具有类似功能的技术特征进行互相替换而形成的技术方案。

技术特征：
1.一种面向智慧校园工作流应用的多目标计算迁移方法，其特征在于，包括以下步骤：获取用户集合和用户的任务集合，根据所述用户的任务集合构建工作流集合，根据所述用户集合和工作流集合随机初始化构建父代种群；基于所述父代种群进行二元锦标赛填充交配池，进行交叉变异生成子代种群；将所述父代种群加入所述子代种群生成混合种群，计算各解决方案的指标，根据所述各解决方案的指标对所述混合种群进行非支配排序，得到非支配排序结果，根据所述非支配排序结果迭代更新候选解；在迭代过程中，响应于确定所选出的下一代父代种群符合种群大小，构建用户关于各项指标的重要性程度的判断矩阵，基于所述判断矩阵计算符合用户偏好的指标权重，基于所述指标权重构建归一化方程，并通过所述归一化方程寻找出最优迁移策略。2.根据权利要求1所述的面向智慧校园工作流应用的多目标计算迁移方法，其特征在于，所述根据所述用户的任务集合构建工作流集合，根据所述用户集合和工作流集合随机初始化构建父代种群，具体包括：根据任务集合t＝{t1,t2,...t
t
}的顺序结构构建工作流集合w＝{w1,w2,...,w
w
}，采用两元组w＝g(t,b)表示设备需要计算的工作流，采用有向无环图表示工作流的建模，其中，b表示任务之间的依赖关系；针对用户集合m∈{1,2,3,...,m}与所述工作流集合w＝{w1,w2,...,w
w
}随机初始化构建父代种群。其中，每一个任务对应一个基因，每一个计算迁移策略对应一条染色体，每一个任务的计算位置被编码为基因数n∈{0,1,...,n,n+1}，其中，n为0表示任务在本地终端执行，n为n+1表示任务在云端执行，其他则表示任务在边缘服务器集群执行。3.根据权利要求1所述的面向智慧校园工作流应用的多目标计算迁移方法，其特征在于，所述基于所述父代种群进行二元锦标赛填充交配池，进行交叉变异生成子代种群，具体包括：计算所述父代种群各个染色体的所支配的解决方案的数量，在多目标优化问题中，对于两个任意解s1及解s2的所有目标而言，解s1的所有目标值都优于解s2的目标值，则解s1支配解s2，其中，用υ(s)表示解s所支配的解决方案的数量；通过适应度函数计算所述父代种群各个染色体的适应度：fit(s)＝η(s)+κ(s)；其中，η(s)为所有支配解s2的解的υ(s)值之和，κ(s)的计算公式如下：其中，表示解s和距离解s第k近的解之间的距离；从所述父代种群中随机选取两个染色体；比较两个染色体的适应度，选择适应度更高的染色体加入交配池；重复以上步骤，直到交配池中染色体的数量达到一定数量为止；对所述父代种群进行随机交叉、变异操作生成子代种群。4.根据权利要求1所述的面向智慧校园工作流应用的多目标计算迁移方法，其特征在于，所述指标包括时间消耗、能量消耗、负载均衡，所述计算各解决方案的指标，具体包括：通过时间消耗函数计算各解决方案的总时间消耗：
其中，f
m,n
是一个用来判断用户m的任务是否迁移到服务器n迁移的标志，当任务在用户的本地终端进行计算时，f
m,n
是0，其他情况则f
m,n
是1；是总时间消耗，是任务在本地终端计算的时间消耗，是任务迁移时所消耗的时间；所述任务在本地终端计算的时间消耗计算为：其中，d
m,n
表示待处理任务的数据大小，ξ
m,n
表示处理设备的计算能力；所述任务迁移时所消耗的时间计算为：其中，表示任务的传输时间，主要由任务上传数据以及下载数据的时间组成；表示任务的执行时间，主要由计算任务数据量和计算能力计算得出；所述任务的传输时间与任务的执行时间可分别计算为：可分别计算为：其中，v
m,n
表示用户m迁移到计算节点n的传输速率，表示为：其中，b
n
表示计算节点的带宽，χ是信道的噪声功率密度，是设备的传输功率，g
m
和φ
m,n
分别表示用户与边缘服务器之间的无线信道增益和带宽；通过能量消耗函数计算各解决方案的总能量消耗：其中，是总能量消耗，是任务在本地终端计算的能量消耗，是任务迁移时所消耗的能量，与分别计算为：分别计算为：其中，是设备的运行功率，和分别是任务传输能耗和闲时能耗；与可分别计算为：
其中，是设备的传输功率，是设备的闲时功率；通过负载均衡函数计算各解决方案的负载均衡：其中，o
n
是边缘服务器集群中被占用的边缘服务器数量，r
n
与ar
n
分别表示边缘服务器的资源利用率及平均资源利用率，r
n
和ar
n
可分别计算为：可分别计算为：其中，t
n
表示边缘服务器集群中边缘服务器n完成的任务数，w
m,n
表示用户m迁移到边缘服务器n的任务数。5.根据权利要求1所述的面向智慧校园工作流应用的多目标计算迁移方法，其特征在于，所述根据所述各解决方案的指标对所述混合种群进行非支配排序，得到非支配排序结果，根据所述非支配排序结果迭代更新候选解，具体包括：根据各解决方案的各指标计算所述混合种群各个染色体的所支配的解决方案的数量，并对所述混合种群各个染色体进行非支配排序，将所述混合种群的各个染色体根据不同的支配关系划分为不同层；根据所述支配关系筛选填充下一代父代种群；判断所选出的下一代父代种群是否符合种群大小，响应于确定所选出的下一代父代种群不符合种群大小，根据所述支配关系填满所述下一代父代种群或根据聚类分析删除多余的解。6.根据权利要求1所述的面向智慧校园工作流应用的多目标计算迁移方法，其特征在于，所述构建用户关于各项指标的重要性程度的判断矩阵，基于所述判断矩阵计算符合用户偏好的指标权重，具体包括：用户关于各项指标的重要性程度的判断矩阵为：用户关于各项指标的重要性程度的判断矩阵为：其中，a
11
至a
33
是基于用户偏好的重要性程度对比打分，其范围是1～3；对所述判断矩阵列中的元素进行归一化，将归一化后的元素以行为单位计算平均值，得到每个指标的指标权重α、β、γ。7.根据权利要求1所述的面向智慧校园工作流应用的多目标计算迁移方法，其特征在
于，所述基于所述指标权重构建归一化方程，并通过所述归一化方程寻找出最优迁移策略，具体包括：在每次迭代过程中根据归一化方程计算总收益在每次迭代过程中根据归一化方程计算总收益其中，α、β、γ是各指标权重，是各指标归一化后的数值；对比每次迭代的总收益，确定总收益的最大值所对应的计算迁移测量为所述最优迁移策略，并得到所述最优迁移策略对应的指标。8.一种面向智慧校园工作流应用的多目标计算迁移装置，其特征在于，包括：父代种群构建模块，被配置为获取用户集合和用户的任务集合，根据所述用户的任务集合构建工作流集合，根据所述用户集合和工作流集合随机初始化构建父代种群；交叉变异模块，被配置为基于所述父代种群进行二元锦标赛填充交配池，进行交叉变异生成子代种群；迭代模块，被配置为将所述父代种群加入所述子代种群生成混合种群，计算各解决方案的指标，根据所述各解决方案的指标对所述混合种群进行非支配排序，得到非支配排序结果，根据所述非支配排序结果迭代更新候选解；最优迁移策略寻找模块，被配置为在迭代过程中，响应于确定所选出的下一代父代种群符合种群大小，构建用户关于各项指标的重要性程度的判断矩阵，基于所述判断矩阵计算符合用户偏好的指标权重，基于所述指标权重构建归一化方程，并通过所述归一化方程寻找出最优迁移策略。9.一种电子设备，包括：一个或多个处理器；存储装置，用于存储一个或多个程序，当所述一个或多个程序被所述一个或多个处理器执行，使得所述一个或多个处理器实现如权利要求1-7中任一所述的方法。10.一种计算机可读存储介质，其上存储有计算机程序，其特征在于，该程序被处理器执行时实现如权利要求1-7中任一所述的方法。

技术总结
本发明公开了一种面向智慧校园工作流应用的多目标计算迁移方法及装置，获取用户集合和用户的任务集合，构建工作流集合，根据用户集合和工作流集合随机初始化构建父代种群；基于父代种群进行二元锦标赛填充交配池，进行交叉变异生成子代种群；将父代种群加入子代种群生成混合种群，计算各解决方案的指标，根据各解决方案的指标对混合种群进行非支配排序，根据非支配排序结果迭代更新候选解；在迭代过程中，响应于确定所选出的下一代父代种群符合种群大小，构建用户关于各项指标的重要性程度的判断矩阵，基于判断矩阵计算符合用户偏好的指标权重，基于指标权重构建归一化方程，并通过归一化方程寻找出最优迁移策略，实现符合用户偏好的多目标优化。偏好的多目标优化。偏好的多目标优化。


技术研发人员：彭凯 王寒梦 赵博海
受保护的技术使用者：华侨大学
技术研发日：2023.07.03
技术公布日：2023/10/15