基于模拟退火的多核多用户任务卸载调度

鲁 伟，宋荣方

(南京邮电大学 通信与信息工程学院，江苏 南京 210003)

0 引 言

随着物联网、移动互联网、大数据技术的快速发展，人类进入了一个万物互联的智能时代，移动智能终端随时随地在线，服务于移动终端上的交互式游戏、智慧城市等计算密集型的业务也正在兴起[1]，这些业务需要大量的计算资源才能满足自身对低时延的要求[2]。由于移动智能设备处理能力、存储容量有限，因此大量的计算需要在云端进行[3]，而云端存在较大的传输时延，当云端资源不足时，甚至存在较大的排队等待时延，这些时延严重影响了众多业务的服务质量。为了使用户能获得良好的体验，减轻云端服务器的负担，移动边缘计算(mobile edge computing，MEC)概念孕育而生[4-5]。与传统的集中式网络架构不同，MEC将边缘服务器部署在靠近用户的一端，缩短了用户与服务器之间的距离，从而大大降低了用户设备的传输时延。在移动边缘计算系统中，任务卸载调度策略的好坏也会直接影响到系统时延和用户体验。终端将业务卸载至边缘计算服务器时，服务器通过优化业务调度顺序可以进一步降低时延和系统能耗。目前已有许多文献对MEC任务卸载调度进行了研究，MEC卸载常见的衡量指标有时延、能耗以及时延和能耗综合权衡问题[6]。文献[7]研究了单用户单核服务器任务卸载情景，提出了一种基于李雅普诺夫优化的动态计算迁移算法，旨在优化应用的执行时延。文献[8]研究了单用户单核服务器任务卸载情景，提出了二进制粒子群优化算法，旨在优化系统的能耗。文献[9]利用流水车间调度模型对任务卸载调度进行建模，以交替最小化优化方法研究系统时延与能耗关系。文献[10]研究单用户多核任务卸载情景，利用遗传算法对单用户的能耗与时延关系进行了优化分析。受以上文献的启发，且目前多核多用户任务卸载研究较少，该文研究多核多用户任务卸载情景，采用混合流水车间模型进行建模，以最小化系统时延和能耗加权和为优化目标，采用模拟退火算法进行求解，通过仿真获得了多用户最优的任务卸载策略，最后对系统时延和能耗关系进行了分析。

1 系统模型与问题建模

该文研究多用户多核任务卸载情景。该边缘任务卸载系统包含了多个用户和一个多核的MEC服务器。每个用户之间卸载相互独立互不影响，每个用户的多个可卸载任务也相互独立互不影响。用户可以通过无线信道将任务上传至边缘服务器进行任务卸载。由于每个任务上传所需的时间和在核服务器上卸载的时间的不同，不合理的任务卸载顺序必将导致系统的总体时延较大，因此确定合理的任务卸载顺序至关重要。

1.1 任务调度与传输速率的定义

移动终端将各自的N项独立的计算任务卸载到MEC[11]。记各自的任务集合为R={T1,T2,…,TN}，每个任务T用一对参数〈Di,Ci〉来表示，其中Di(bits)表示任务的数据量，Ci(cycles/bit)表示每比特的数据所需的计算资源。每个用户N个任务的卸载调度顺序定义为σ={σ1,σ2,…,σN}，其中TNσi表示该任务N于第i次卸载到MEC服务器上。该文研究移动端配置单天线情景，一次只能发一个任务，任务TNσi的传输速率定义为:

(1)

其中，Pi是任务TNσi的传输功率，g0是路径损耗常数，θ是路径损耗指数，取值范围一般为2～4，L0是参考距离，L是终端与MEC服务器之间的距离，w是系统带宽，N0是MEC服务器接收端的噪声功率谱密度。

1.2 系统时延和能耗模型

混合流水车间调度(hybrid flow-shop scheduling problem，HFSP)是一种车间作业排序问题[12]。如图1所示，设有n个独立的工件按照相同加工方向在m道工序上加工，m道工序中至少有一道工序包含多台并行处理器[13]。

图1 混合流水车间调度模型

模型一般满足以下条件：(1)同一阶段中所有机器都相同；(2)每个工件可以在某阶段的任意一台机器上进行加工；(3)任意时刻每个工件至多在一台机器上加工；(4)每台机器某时刻只能加工一个工件；(5)工件的加工过程不允许中断；(6)每台机器都有一个无限的存储空间。

在多用户多核服务器MEC系统中，可将卸载的任务看成是待加工的工件，每个计算任务都需要经过本地传输和服务器执行两道工序。在第一道工序中，移动设备负责任务的上传，在第二道工序中，MEC服务器具有M个计算能力相同的处理器，因此可以利用混合流水车间模型对多用户多核服务器MEC系统的任务卸载调度进行建模。当任务TNσi卸载到MEC服务器上执行时，系统时延由三部分组成，即任务上传到服务器的时间t(1,σj)、任务在服务器执行的时间t(2,σj)和任务结果反馈到移动设备的时间，通常由于下行速率远远高于上行速率，因此可忽略结果的反馈时间。

(2)

(3)

σj∈(1,2,…,N)

在多用户多核MEC系统中，每个用户完工时间定义为该用户最后一个任务在某个核上的完工时间[14],系统时延定义为每个用户最后一个任务在某个核上的完工时间的累加和，即：

(4)

系统能耗定义为每个用户每个任务上传所消耗能耗的累加和，即：

(5)

2 问题建模

基于以上分析，该文以最小化时延和能耗的加权和为目标，即：

(6)

s.t. 0≤pi≤pmax,i=1,2,…,N

σ={σ1,σ2,…,σN}，其中σi∈{1,2,…,N},i≠j,σi≠σj,∀i,j,i,j=1,2,…,N

其中，η为权重因子，用于调节系统时延和能耗之间的数量级，当其较大时，表示对系统能耗的优化更加看重。该求解问题是一个优化问题，可以使用穷举算法遍历所有情况，但复杂度太高。考虑到模拟退火算法是一种借鉴于固体的退火原理的优化算法，计算过程简单，通用，鲁棒性强，适用于并行处理，可用于求解复杂的优化问题，所以用模拟退火算法对问题p进行求解。

3 模拟退火算法

模拟退火算法(simulated annealing algorithm，SAA)是一种基于蒙特卡洛迭代的随机寻优算法，其出发点是模仿物理中固定物质的退火过程与一般组合优化问题之间的相似性[15]。模拟退火算法在某一初温下，随着温度参数的不断下降，以一定的概率突跳，在解空间中随机寻找目标函数的全局最优解。为方便表示，将适应度函数fitness表示为目标函数值E，目标函数值E越低，表示可行解越接近最优解。

(7)

算法流程：

(1)设定当前解：T=T0，即开始退火的初始温度，随机生成一个初始解Xbest=X0，并计算相应的目标函数值E(x0)，令T等于冷却进度表中的下一个温度值Ti。

(2)产生新解与当前解的差值：对当前解Xi进行扰动，产生一个新解Xnew，并计算相应的目标数值E(Xnew)进而得到ΔE=E(Xnew)-E(Xi)。

(4)更新温度，Tk+1=update(Tk)，在温度Tk+1下，再经过k次扰动和接受，即执行步骤2和步骤3。

(5)找到可行解：判断T是否达到了终止温度，是，终止算法；否，则转到步骤2继续执行。

4 仿真结果与分析

下面对多用户多核服务器的MEC系统分别用基于混合流水车间模型的模拟退火算法(HFSP-SAA)与随机任务卸载(random task offload strategy，RTOS)的任务数与时延的关系任务卸载调度进行仿真并分析。仿真中计算任务的数据量Di和所需的计算资源Ci都服从均匀分布，即Di～U(2 davg，20 davg)，Ci～U(5 cavg，27.975 cavg)，其中davg=1 kbit，cavg=797.5 cycles/bit。表1列出了仿真所需要的参数及取值。

表1 仿真参数与取值

图2展示了η=0时基于混合流水车间模型模拟退火算法在不同传输功率下2核2用户时延与卸载任务数的关系。

图2 时延与卸载任务之间关系(M=2)

从图中可以看出，随着卸载任务数量的增大，时延呈现上升趋势。传输功率从0.5 mW增大至16 mW，时延显著降低，但传输功率从16 mW增大至32 mW，时延降低并不明显。

图3～图5分别展示了在不同的传输功率下2核2用户的卸载任务调度的甘特图。用户的任务数字表示正在上传的任务序号，而核服务器上的数字表示该任务的归属，例如核2上数字的2|5，表示核2正在处理用户2的第5个任务。

图3 P=0.5 mW任务卸载甘特图

图4 P=16 mW任务卸载甘特图

图5 P=32 mW任务卸载甘特图

从甘特图中可以看出，当传输功率P=0.5 mW时，核服务器一开始等待时间较长，任务上传时间过长，从而导致MEC服务器资源无法充分得到利用，且在处理任务过程中，因为传输功率低而导致核服务器有空闲等待的时刻，从而导致时延较高，且当卸载任务数量显著增大时，这种空闲等待情况更加明显，因此时延会显著增大。而当传输功率P=16 mW时，任务上传时间减少，核服务器等待时间减少，且核服务器无空闲等待时刻，因此时延降低。当P=32 mW时，尽管任务上传时间减短，但核服务器因为资源有限，上传的任务进入了缓存等待区域，因此传输功率的再次增大并没有换取时延的显著降低。

图6展现了基于混合流水车间模型的模拟退火算法(HFSP-SAA)与随机任务卸载(random task offload strategy，RTOS)的任务数与时延的关系。

图6 系统时延与卸载任务数量关系(P=16 mW)

从图中可以看出，随着任务数的增大，基于HFSP-SAA卸载策略比RTOS卸载策略的系统时延要少，这是因为HFSP-SAA卸载策略综合考虑了两道工序的加工时间，确定了合理的任务卸载顺序，从而使得系统时延得以减少，且随着任务数量的增大，HFSP-SAA卸载策略的优势更加明显，因此提出的卸载策略可以有效降低时延，提高用户体验。

图7展示了在2用户不同核数情况下，系统时延与卸载任务数量的关系。从图中可以看出，当核数小于用户数时，系统时延优化瓶颈在核服务器等待和空闲时延上，此时核数的增加可以显著减少时延，而当核数大于或等于用户数时,核数的增加不会显著减少时延，系统时延优化瓶颈在第一道工序的任务上传上。由此可得出参与计算卸载最佳的核数应该等于或近似于参与任务卸载的用户数，由此可以实现服务器端能耗的节约，当参与调度的用户数改变时，动态调节核数，保证核数等于或近似于用户数时，从而可以有效降低用户任务卸载时延。

图7 不同核数下时延与卸载任务数量关系

图8展示了2用户情景下，不同核数不同的权重下，能耗与时延的优化关系。从图中可以看出，当用户数大于核数时，增加核数可以显著减少时延。系统时延随着η增大而增大，系统能耗随着η增大而减小，但能耗呈现先陡峭后平缓减少的走势;陡峭部分的能耗说明当能耗增大到某一程度后，能耗的增加不会降低时延，当能耗小到某一程度，能耗与时延成反比关系，能耗降低会引起时延的增大。当M=1时，用户数大于核服务器数量时，此时能耗的增加并不会引起时延降低，可取η=10 000，作为优化权重，从而实现节约能耗，对于用户数小于核数的M=4和M=2的情况，可取η=10作为优化权重，此时能耗较低，时延较低，由此实现节约能耗的目的。

图8 系统时延与能耗关系

5 结束语

该文研究了多用户多核情景下多个独立任务调度和功率分配问题。基于混合流水车间调度模型和模拟退火算法，对系统时延和能耗进行加权和优化，获得了最佳的任务卸载调度甘特图。与随机任务卸载调度相比，提出的卸载调度策略时延较小。找到了一种基于混合车间模型的核服务器数量与参与调度的用户数的关系，从而确定最佳的核服务器数量，解决了当用户数大于核数时，系统时延的优化瓶颈。最后揭示时延与能耗之间的关系，根据核数与用户数关系，找到了不同情况下最佳的优化权重，从而达到了节约能耗的目的。