移动云计算嵌套式两阶段博弈计算卸载算法_裘华东

多用户D2D计算卸载与资源分配算法韩跃林;朱琦【期刊名称】《信号处理》【年(卷),期】2024(40)2【摘要】基于边缘服务器架构的移动计算卸载场景避免了核心网链路的网络延迟,在一定程度上提高了计算任务的处理效率,然而在移动用户密集分布的场景下,该计算卸载架构可能面临较高的蜂窝网络接入延迟。

为提高移动边缘计算的用户体验,本文在移动用户密集分布的场景下研究了基于D2D通信的多用户计算卸载问题。

根据是否具有任务处理需求将用户分为两类,定义拥有密集型计算任务需要处理的用户为需求用户,无任务需要处理且能够提供计算资源的用户为空闲用户。

需求用户可以将任务以整体的形式卸载至空闲用户进行辅助处理。

联合考虑需求用户与空闲用户在计算卸载中的收益,分别构建了各方的效用函数并形成了相应的优化问题。

为了提高各方用户的效用,本文提出了基于Stackelberg博弈与遗传算法相结合的计算卸载与资源分配算法,该算法为两层结构,内层基于Stackelberg博弈对需求用户计算资源租赁单价决策以及空闲用户计算资源分配决策进行优化,并证明了各方用户的策略存在唯一纳什均衡。

外层采用遗传算法对需求用户的任务卸载决策进行优化,根据内层算法的反馈结果,可以求解出能够有效提高需求用户效用的任务卸载决策。

为验证算法的性能,本文进行了大量的实验仿真工作,仿真结果表明,与其他方案相比,本文算法能够有效提高需求用户与空闲用户的效用。

同时,本文还对不同参数对算法有效性的影响进行了仿真分析。

【总页数】12页(P373-384)【作者】韩跃林;朱琦【作者单位】南京邮电大学江苏省无线通信重点实验室;南京邮电大学教育部泛在网络健康服务系统工程研究中心【正文语种】中文【中图分类】TN929.5【相关文献】1.无线充能边缘计算中最大化平均计算能力的任务卸载和资源分配算法2.基于深度强化学习的多用户边缘计算任务卸载调度与资源分配算法3.移动边缘计算中一种有效的计算资源分配和偏分任务卸载算法4.卫星边缘计算中任务卸载与资源分配联合优化算法5.车联网中面向依赖任务的联合计算卸载及资源分配算法因版权原因，仅展示原文概要，查看原文内容请购买。

面向移动边缘计算的联合计算卸载和资源分配策略研究作者：黄冬晴俞黎阳陈珏魏同权来源：《华东师范大学学报（自然科学版）》2021年第06期摘要：隨着无人驾驶、在线游戏、虚拟现实等低延迟应用的大量涌现，传统集中式的移动云计算范式越来越难以满足此类用户服务质量的需求.为弥补云计算的不足，移动边缘计算应运而生.移动边缘计算通过计算卸载，将计算任务迁移到网络边缘服务器来为用户提供计算和存储资源.然而，现有大部分工作仅考虑了延迟或能耗的单目标性能优化，未考虑延迟和能耗的均衡优化.为减少任务延迟和设备能耗，提出了一种面向多用户的联合计算卸载和资源分配策略.该策略首先利用拉格朗日乘子法获得给定卸载决策的最佳计算资源分配;然后，提出一个基于贪心算法的计算卸载算法获得最佳卸载决策;最后，通过不断迭代得到最终解.实验结果表明，与基准算法相比，所提算法最高可以降低40%的系统成本.关键词：移动边缘计算;计算卸载;资源分配;拉格朗日乘子法;贪心算法中图分类号：TP391文献标志码：ADOI：10.3969/j.issn.l000-5641.2021.06.010Research on joint computation offloading and resource allocation strategy for mobile edge computingHUANG Dongqing1，YU Liyang1，CHEN Jue2，WEI Tongquan1（1. School of Computer Science and Technology. East China Normal University，Shanghai 200062. China;2. School of Electronic and Electrical Engineering. Shanghai University of Engineering Science，Shanghai 201620，China）Abstract：With the emergence of low-latency applications such as driverless cars，online gaming，and virtual reality，it is becoming increasingly difficult to meet users7 demands for service quality using the traditional centralized mobile cloud computing model. In order to make up for the shortages of cloud computing，mobile edge computing came into being，which provides users with computing and storage resources by migrating computing tasks to network edge servers through computation offloading. However，most of the existing work processes only consider single-objective performance optimization of delay or energy consumption，and do not consider the balanced optimization of delay and energy consumption. Therefore，in order to reduce task delay and equipment energy consumption，a multi-user joint computation offloading and resource allocation strategy is proposed. In this strategy，the Lagrange multiplier method is used to obtain the optimal allocation of computing resources for a given offloading decision. Then，a computation offloading algorithm based on a greedy algorithm is proposed to obtain the optimal offloading decision：thefinal solution is obtained through continuous iteration. Experimental results show that，compared with the benchmark algorithm，the proposed algorithm can reduce system costs by up to 40%.Keywords：mobile edge computing;computation offloading;resource allocation;Lagrange multiplier method;greedy algorithm0引言随着移动互联网和5G通信技术[1]的不断发展，移动设备上需要处理越来越多的延迟敏感性应用，例如无人驾驶、在线游戏、虚拟现实和增强现实等[2].但是，由于计算和存储资源的限制，移动设备运行这些应用会造成很高的延迟和能耗.为解决该问题，移动云计算（Mobile Cloud Computing，MCC）诞生了，它将用户部分计算任务通过上行链路卸载到云端服务器，减少了任务的执行时间.然而在传统MCC中，集中式部署的云服务器与移动设备距离较远，两者数据传输过程中会占用大量网络带宽导致网络拥塞，从而增加了通信延迟和能量消耗.因此，传统的MCC范式越来越难以满足用户服务质量的需求.针对MCC中存在的问题，欧洲标准协会提出了移动边缘计算（Mobile Edge Computing，MEC）[3].在MEC系统中，具有计算和存储资源的边缘服务器被部署在更靠近用户的网络边缘，移动设备便能以更低的通信延迟进行任务卸载.MEC的优势包括低延迟、可靠的服务交付、高效的网络运营等.随着移动用户数目的增加，边缘服务器因其计算资源受限而影响了任务执行延迟和能耗.因此，计算卸载和资源分配策略成为实现系统高效卸载的关键.针对多用户MEC系统资源受限的场景，有些学者关注最大程度减少任务时延：Zhang等[4]研究了基于时分多址的MEC系统中计算和通信资源分配问题，设计了一个次梯度算法以最大程度减少设备延迟;Alam等[5]提出了一种基于深度Q学习的自主计算卸载框架，用于处理系统中资源分配和移动性问题;Paymard等[6]提出了一种高效可感知传输的任务调度和资源分配算法，联合优化上行/下行子载波、传输功率、计算资源分配及任务调度;Liu等[7]考虑任务随机性和计算强度，设计了一个卸载框架，并通过分析边缘服务器排队模型提出了基于Lyapunov优化的动态资源分配算法.这些工作通常针对时延敏感型应用，虽然都在一定程度上实现以极低的延迟进行任务卸载，但是忽略了系统中设备的能量消耗.此外，有学者重点关注进一步节省系统中设备的能量消耗，以最大程度延长系统设备的使用寿命：Guo等[8]考虑到高干扰、多路访问和有限资源，设计了一种基于遗传算法的次优卸载算法，以实现卸载决策、无线和计算资源分配的联合优化;Li等[9]基于Lyapunov优化框架，提出了一种在线能耗最小化的卸载算法，来实现最佳能量和数据传输时间分配、任务卸载比例、传输功率以及设备计算频率;Qian等[10]通过共同优化资源分配和连续干扰消除排序来减少能耗，即先基于Karush-Kuhn-Tucher （KKT）条件和梯度下降法获得最佳的传输功率和计算资源分配，然后提出基于禁忌搜索的排序算法;Zeng等[11]针对单小区中正交多址和非正交多址场景提出了近似最优的解决方案，以实现传输功率和计算资源最佳联合分配，同时也证明了非正交多址优于正交多址方案.这些工作通常针对能量消耗型應用，一般都是在满足任务计算时延约束下最大程度降低系统的能耗，但是以增加计算时延的开销为代价.以上研究工作都倾向于从延迟或能耗单目标性能进行系统优化，未实现系统延迟和能耗的均衡优化.在某些情况下，本文希望用更少的时间及更低的能耗完成系统所有计算任务，从而让服务器可以更早地完成计算任务，为更多的用户提供服务，同时延长系统寿命.因此，本文在考虑MEC系统场景下任务卸载中延迟和能耗两个因素之间的权衡的基础上，提出了一种面向多用户的联合计算卸载和资源分配策略.本文主要贡献概述如下.（1）考虑多用户单小区MEC系统场景，建立了本地计算模型和移动边缘计算模型.每个任务计算成本被表述为时延和能耗加权和，在有限的信道和计算资源约束下，优化问题被建模为一个混合整数非线性规划（Mixed Integer Nonlinear Programming，MINILP）问题.（2）提出了一种面向多用户的联合计算卸载和资源分配策略.针对资源分配子问题，采用拉格朗日乘子法获得最佳计算资源分配.针对计算卸载子问题，提出一种基于贪心算法的计算卸载算法.最后，通过不断迭代获得最优卸载决策和计算资源分配.（3）通过仿真实验，验证了本文所提算法的有效性.与本地执行算法、全卸载算法、分支定界算法以及带汉明距离终止的动态规划卸载算法进行比较，本文所提算法优于其他算法，且系统成本最高可以降低40%.1系统架构和计算模型在本章中，首先对系统架构进行详细介绍，然后给出任务计算模型，包括本地计算和移动边缘计算.1.1系统架构如图1所示，考虑1个多用户单小区MEC系统，有N个移动设备（Mobile Device，MD），每个移动设备都被视为用户，用户通过无线信道的方式连接附近基站（Base Station，BS）.假设在某一时刻每个用户仅产生1个计算任务，对于第i（i=1，2，…，N）个移动设备，定义表示其计算任务要求，其中B i表示计算任务的数据大小，即移动设备传输到边缘服务器的数据量，包括系统设置、程序代码和输入参数;C i表示任务所需的计算资源量，即完成计算任务需要的CPU周期数.电信运营商在基站附近部署有MEC服务器，其具有一定的存储容量和计算能力，可以存储用户的输入任务并提供计算服务.表1总结了本文所使用的关键符号及其含义.由于MEC服务器为多个移动用户提供服务，计算任务可以选择卸载到MEC服务器或本地设备执行.定义用户i的二进制卸载决策变量为a i∈{0，1}，其中a i=1表示其计算任务将决定通过无线信道卸载到MEC服务器，a i=0表示任务在本地设备上进行计算.因此，A= {a1，a2，…，a N}为所有用户卸载决策集合.对于小区中不同用户传输，采用正交频分多址方案.整个频谱被均匀的划分为K个子信道，将每个任务分配给1个子信道，确保用户上行链路传输信道的正交性.定义B为无线信道的系统带宽，W为用户带宽.因此，BS最多可以服务的用户数为每个移动用户通过正交频分复用信道接入小区基站，根据香农公式可知，移动用户i的上行链路传输速率为其中，为信噪比，p i表示用户i的传输功率，g i表示用户i与BS之间的信道增益，σ2为高斯信道噪声的方差.针对MCC中存在的问题，欧洲标准协会提出了移动边缘计算（Mobile Edge Computing，MEC）[3].在MEC系统中，具有计算和存储资源的边缘服务器被部署在更靠近用户的网络边缘，移动设备便能以更低的通信延迟进行任务卸载.MEC的优势包括低延迟、可靠的服务交付、高效的网络运营等.随着移动用户数目的增加，边缘服务器因其计算资源受限而影响了任务执行延迟和能耗.因此，計算卸载和资源分配策略成为实现系统高效卸载的关键.针对多用户MEC系统资源受限的场景，有些学者关注最大程度减少任务时延：Zhang等[4]研究了基于时分多址的MEC系统中计算和通信资源分配问题，设计了一个次梯度算法以最大程度减少设备延迟;Alam等[5]提出了一种基于深度Q学习的自主计算卸载框架，用于处理系统中资源分配和移动性问题;Paymard等[6]提出了一种高效可感知传输的任务调度和资源分配算法，联合优化上行/下行子载波、传输功率、计算资源分配及任务调度;Liu等[7]考虑任务随机性和计算强度，设计了一个卸载框架，并通过分析边缘服务器排队模型提出了基于Lyapunov优化的动态资源分配算法.这些工作通常针对时延敏感型应用，虽然都在一定程度上实现以极低的延迟进行任务卸载，但是忽略了系统中设备的能量消耗.此外，有学者重点关注进一步节省系统中设备的能量消耗，以最大程度延长系统设备的使用寿命：Guo等[8]考虑到高干扰、多路访问和有限资源，设计了一种基于遗传算法的次优卸载算法，以实现卸载决策、无线和计算资源分配的联合优化;Li等[9]基于Lyapunov优化框架，提出了一种在线能耗最小化的卸载算法，来实现最佳能量和数据传输时间分配、任务卸载比例、传输功率以及设备计算频率;Qian等[10]通过共同优化资源分配和连续干扰消除排序来减少能耗，即先基于Karush-Kuhn-Tucher （KKT）条件和梯度下降法获得最佳的传输功率和计算资源分配，然后提出基于禁忌搜索的排序算法;Zeng等[11]针对单小区中正交多址和非正交多址场景提出了近似最优的解决方案，以实现传输功率和计算资源最佳联合分配，同时也证明了非正交多址优于正交多址方案.这些工作通常针对能量消耗型应用，一般都是在满足任务计算时延约束下最大程度降低系统的能耗，但是以增加计算时延的开销为代价.以上研究工作都倾向于从延迟或能耗单目标性能进行系统优化，未实现系统延迟和能耗的均衡优化.在某些情况下，本文希望用更少的时间及更低的能耗完成系统所有计算任务，从而让服务器可以更早地完成计算任务，为更多的用户提供服务，同时延长系统寿命.因此，本文在考虑MEC系统场景下任务卸载中延迟和能耗两个因素之间的权衡的基础上，提出了一种面向多用户的联合计算卸载和资源分配策略.本文主要贡献概述如下.（1）考虑多用户单小区MEC系统场景，建立了本地计算模型和移动边缘计算模型.每个任务计算成本被表述为时延和能耗加权和，在有限的信道和计算资源约束下，优化问题被建模为一个混合整数非线性规划（Mixed Integer Nonlinear Programming，MINILP）问题.（2）提出了一种面向多用户的联合计算卸载和资源分配策略.针对资源分配子问题，采用拉格朗日乘子法获得最佳计算资源分配.针对计算卸载子问题，提出一种基于贪心算法的计算卸载算法.最后，通过不断迭代获得最优卸载决策和计算资源分配.（3）通过仿真实验，验证了本文所提算法的有效性.与本地执行算法、全卸载算法、分支定界算法以及带汉明距离终止的动态规划卸载算法进行比较，本文所提算法优于其他算法，且系统成本最高可以降低40%.1系统架构和计算模型在本章中，首先对系统架构进行详细介绍，然后给出任务计算模型，包括本地计算和移动边缘计算.1.1系统架构如图1所示，考虑1个多用户单小区MEC系统，有N个移动设备（Mobile Device，MD），每个移动设备都被视为用户，用户通过无线信道的方式连接附近基站（Base Station，BS）.假设在某一时刻每个用户仅产生1个计算任务，对于第i（i=1，2，…，N）个移动设备，定义表示其计算任务要求，其中B i表示计算任务的数据大小，即移动设备传输到边缘服务器的数据量，包括系统设置、程序代码和输入参数;C i表示任务所需的计算资源量，即完成计算任务需要的CPU周期数.电信运营商在基站附近部署有MEC服务器，其具有一定的存储容量和计算能力，可以存储用户的输入任务并提供计算服务.表1总结了本文所使用的关键符号及其含义.由于MEC服务器为多个移动用户提供服务，计算任务可以选择卸载到MEC服务器或本地设备执行.定义用户i的二进制卸载决策变量为a i∈{0，1}，其中a i=1表示其计算任务将决定通过无线信道卸载到MEC服务器，a i=0表示任务在本地设备上进行计算.因此，A= {a1，a2，…，a N}为所有用户卸载决策集合.对于小区中不同用户传输，采用正交频分多址方案.整个频谱被均匀的划分为K个子信道，将每个任务分配给1个子信道，确保用户上行链路传输信道的正交性.定义B为无线信道的系统带宽，W为用户带宽.因此，BS最多可以服务的用户数为每个移动用户通过正交频分复用信道接入小区基站，根据香农公式可知，移动用户i的上行链路传输速率为其中，为信噪比，p i表示用户i的传输功率，g i表示用户i与BS之间的信道增益，σ2为高斯信道噪声的方差.针对MCC中存在的问题，欧洲标准协会提出了移动边缘计算（Mobile Edge Computing，MEC）[3].在MEC系统中，具有计算和存储资源的边缘服务器被部署在更靠近用户的网络边缘，移动设备便能以更低的通信延迟进行任务卸载.MEC的优势包括低延迟、可靠的服务交付、高效的网络运营等.随着移动用户数目的增加，边缘服务器因其计算资源受限而影响了任务执行延迟和能耗.因此，计算卸载和资源分配策略成为实现系统高效卸载的关键.针对多用户MEC系统资源受限的场景，有些学者关注最大程度减少任务时延：Zhang等[4]研究了基于时分多址的MEC系统中计算和通信资源分配问题，设计了一个次梯度算法以最大程度减少设备延迟;Alam等[5]提出了一种基于深度Q学习的自主计算卸载框架，用于处理系统中资源分配和移动性问题;Paymard等[6]提出了一种高效可感知传输的任务调度和资源分配算法，联合优化上行/下行子载波、传输功率、计算资源分配及任务调度;Liu等[7]考虑任务随机性和计算强度，设计了一个卸载框架，并通过分析边缘服务器排队模型提出了基于Lyapunov优化的动态资源分配算法.这些工作通常针对时延敏感型应用，虽然都在一定程度上实现以极低的延迟进行任务卸载，但是忽略了系统中设备的能量消耗.此外，有学者重点关注进一步节省系统中设备的能量消耗，以最大程度延长系统设备的使用寿命：Guo等[8]考虑到高干扰、多路访问和有限资源，设计了一种基于遗传算法的次优卸载算法，以实现卸载决策、无线和计算资源分配的联合优化;Li等[9]基于Lyapunov优化框架，提出了一种在线能耗最小化的卸载算法，来实现最佳能量和数据传输时间分配、任务卸载比例、传输功率以及设备计算频率;Qian等[10]通过共同优化资源分配和连续干扰消除排序来减少能耗，即先基于Karush-Kuhn-Tucher （KKT）条件和梯度下降法获得最佳的传输功率和计算资源分配，然后提出基于禁忌搜索的排序算法;Zeng等[11]针对单小区中正交多址和非正交多址场景提出了近似最优的解决方案，以实现传输功率和计算资源最佳联合分配，同时也证明了非正交多址优于正交多址方案.这些工作通常针对能量消耗型应用，一般都是在满足任务计算时延约束下最大程度降低系统的能耗，但是以增加计算时延的开销为代价.以上研究工作都倾向于从延迟或能耗单目标性能进行系统优化，未实现系统延迟和能耗的均衡优化.在某些情况下，本文希望用更少的时间及更低的能耗完成系统所有计算任务，从而让服务器可以更早地完成计算任务，为更多的用户提供服务，同时延长系统寿命.因此，本文在考虑MEC系统场景下任务卸载中延迟和能耗两个因素之间的权衡的基础上，提出了一种面向多用户的联合计算卸载和资源分配策略.本文主要贡献概述如下.（1）考虑多用户单小区MEC系统场景，建立了本地计算模型和移动边缘计算模型.每个任务计算成本被表述为时延和能耗加权和，在有限的信道和计算资源约束下，优化问题被建模为一个混合整数非线性规划（Mixed Integer Nonlinear Programming，MINILP）问题.（2）提出了一种面向多用户的联合计算卸载和资源分配策略.针对资源分配子问题，采用拉格朗日乘子法获得最佳计算资源分配.针对计算卸载子问题，提出一种基于贪心算法的计算卸载算法.最后，通过不断迭代获得最优卸载决策和计算资源分配.（3）通过仿真实验，验证了本文所提算法的有效性.与本地执行算法、全卸载算法、分支定界算法以及带汉明距离终止的动态规划卸载算法进行比较，本文所提算法优于其他算法，且系统成本最高可以降低40%.1系统架构和计算模型在本章中，首先对系统架构进行详细介绍，然后给出任务计算模型，包括本地计算和移动边缘计算.1.1系统架构如图1所示，考虑1个多用户单小区MEC系统，有N个移动设备（Mobile Device，MD），每个移动设备都被视为用户，用户通过无线信道的方式连接附近基站（Base Station，BS）.假设在某一时刻每个用户仅产生1个计算任务，对于第i（i=1，2，…，N）个移动设备，定义表示其计算任务要求，其中B i表示计算任务的数据大小，即移动设备传输到边缘服务器的数据量，包括系统设置、程序代码和输入参数;C i表示任务所需的计算资源量，即完成计算任务需要的CPU周期数.电信运营商在基站附近部署有MEC服务器，其具有一定的存储容量和计算能力，可以存储用户的输入任务并提供计算服务.表1总结了本文所使用的关键符号及其含义.由于MEC服务器为多个移动用户提供服务，计算任务可以选择卸载到MEC服务器或本地设备执行.定义用户i的二进制卸载决策变量為a i∈{0，1}，其中a i=1表示其计算任务将决定通过无线信道卸载到MEC服务器，a i=0表示任务在本地设备上进行计算.因此，A= {a1，a2，…，a N}为所有用户卸载决策集合.对于小区中不同用户传输，采用正交频分多址方案.整个频谱被均匀的划分为K个子信道，将每个任务分配给1个子信道，确保用户上行链路传输信道的正交性.定义B为无线信道的系统带宽，W为用户带宽.因此，BS最多可以服务的用户数为每个移动用户通过正交频分复用信道接入小区基站，根据香农公式可知，移动用户i的上行链路传输速率为其中，为信噪比，p i表示用户i的传输功率，g i表示用户i与BS之间的信道增益，σ2为高斯信道噪声的方差.针对MCC中存在的问题，欧洲标准协会提出了移动边缘计算（Mobile Edge Computing，MEC）[3].在MEC系统中，具有计算和存储资源的边缘服务器被部署在更靠近用户的网络边缘，移动设备便能以更低的通信延迟进行任务卸载.MEC的优势包括低延迟、可靠的服务交付、高效的网络运营等.随着移动用户数目的增加，边缘服务器因其计算资源受限而影响了任务执行延迟和能耗.因此，计算卸载和资源分配策略成为实现系统高效卸载的关键.针对多用户MEC系统资源受限的场景，有些学者关注最大程度减少任务时延：Zhang等[4]研究了基于时分多址的MEC系统中计算和通信资源分配问题，设计了一个次梯度算法以最大程度减少设备延迟;Alam等[5]提出了一种基于深度Q学习的自主计算卸载框架，用于处理系统中资源分配和移动性问题;Paymard等[6]提出了一种高效可感知传输的任务调度和资源分配算法，联合优化上行/下行子载波、傳输功率、计算资源分配及任务调度;Liu等[7]考虑任务随机性和计算强度，设计了一个卸载框架，并通过分析边缘服务器排队模型提出了基于Lyapunov优化的动态资源分配算法.这些工作通常针对时延敏感型应用，虽然都在一定程度上实现以极低的延迟进行任务卸载，但是忽略了系统中设备的能量消耗.此外，有学者重点关注进一步节省系统中设备的能量消耗，以最大程度延长系统设备的使用寿命：Guo等[8]考虑到高干扰、多路访问和有限资源，设计了一种基于遗传算法的次优卸载算法，以实现卸载决策、无线和计算资源分配的联合优化;Li等[9]基于Lyapunov优化框架，提出了一种在线能耗最小化的卸载算法，来实现最佳能量和数据传输时间分配、任务卸载比例、传输功率以及设备计算频率;Qian等[10]通过共同优化资源分配和连续干扰消除排序来减少能耗，即先基于Karush-Kuhn-Tucher （KKT）条件和梯度下降法获得最佳的传输功率和计算资源分配，然后提出基于禁忌搜索的排序算法;Zeng等[11]针对单小区中正交多址和非正交多址场景提出了近似最优的解决方案，以实现传输功率和计算资源最佳联合分配，同时也证明了非正交多址优于正交多址方案.这些工作通常针对能量消耗型应用，一般都是在满足任务计算时延约束下最大程度降低系统的能耗，但是以增加计算时延的开销为代价.以上研究工作都倾向于从延迟或能耗单目标性能进行系统优化，未实现系统延迟和能耗的均衡优化.在某些情况下，本文希望用更少的时间及更低的能耗完成系统所有计算任务，从而让服务器可以更早地完成计算任务，为更多的用户提供服务，同时延长系统寿命.因此，本文在考虑MEC系统场景下任务卸载中延迟和能耗两个因素之间的权衡的基础上，提出了一种面向多用户的联合计算卸载和资源分配策略.本文主要贡献概述如下.（1）考虑多用户单小区MEC系统场景，建立了本地计算模型和移动边缘计算模型.每个任务计算成本被表述为时延和能耗加权和，在有限的信道和计算资源约束下，优化问题被建模为一个混合整数非线性规划（Mixed Integer Nonlinear Programming，MINILP）问题.。

2017年6月计算机工程与设计June2017第 38 卷第 6 期 COM PUTERENGINEERINGANDDESIGN Vol.38 No.6云计算中面向多目标的两阶段任务调度算法武小年1!，郑鑫8，孟川8，何庆志1(1.桂林电子科技大学广西无线宽带通信与信号处理重点实验室，广西桂林541004$2.桂林电子科技大学广西密码学与信息安全重点实验室，广西桂林541004)摘要"为根据云用户的需求提供高质量、低成本的服务，提出一种面向多目标的两阶段任务调度算法。

在预调度阶段，通过计算任务的完成时间、服务费用和损失度，对任务排序，为任务选择满足其对时间-费用偏好的最小资源；在重调度阶 段，根据P e rato最优原则，在不增加服务费用的条件下，重新调度任务到完成时间与负栽较小的资源上。

仿真结果表明，该算法能够根据云用户的任务需求和偏好选择合适的服务，降低任务的完成时间和服务费用，提高了服务质量，具有较好 的负栽均衡性。

关键词"云计算；任务调度；任务损失度；P e rato最优原则；负栽均衡中图法分类号！TP393 文献标识号：A 文章编号：1000-7024 (2017)06-1551-05d o i：10. 16208/1. iss n l000-7024. 2017.06.028T w o-phase ta sk scheduling alg o rith m for m ulti-objective in cloud com putingW U Xiao-nian1，2!ZHENG Xin1!M ENG Chuan1!H E Q in g ah i1(1. Guangxi Wireless Broadband Communication and Signal Processing Key Laboratory, Guilin University ffElectronic Technology，Guilin 541004，China; 2. Guangxi Key Laboratory of Cryptography andInformation Security，GuilinUniversity of Electronic Technology，Guilin 541004，China)A b stract：To provide high-quality and low-cost services according to the needs of cloud users，a two-ph rithm for multi-objective in cloud computing was proposed In the prt^scheduling phase，the tasks were of task completion time，service cost and loss degree. The resource with minimal time-cost the task user preferred was allocated to the task. In the re-scheduling phase，according to Perato optimal principle，the task was rescheduled to the resource with less completing time and less load , in the condition of not increasing the cost of services. Experimental results show that the algo­rithm can select the appropriate service according to cloud users?demand and preference，efficiently decreases the costs of com­pleting time and services. tt also improves the quality of service with better load balance.K ey w ord s：cloud computing；task scheduling；task loss degree；Perato optimll principle；load balanc〇引言现有的云计算任务调度[1’2]算法中，为减小时间跨度，文献[2]融合Mm-mm与Max-mm算法，将大任务与小任 务进行“捆绑”式调度；文献,]则改进Max-mm算法进 行任务-资源映射，将最大任务安排到对其最小执行时间的 资源上；文献[4]针对用户服务质量需求，修改粒子群算法（P S O)的适应度函数，采用分级PSO算法提高对QoS 偏好的感知能力；以节能调度为目的，文献[5]采用滚动 优化策略分析并构建任务能量消耗模型，有效提高云系统 性能；文献[6]将服务费用作为调度目标，基于蜜蜂觅食 算法调整系统负载均衡；文献[7]则给出在用户期望的截 止时间内尽可能最小化执行费用。