基于GA-BPSO算法的MEC卸载决策_王泽.pdf

年月第 卷第期计算机工程与设计 基于 算法的 卸载决策王泽，郭荣佐（四川师范大学 计算机科学学院，四川 成都 ）摘要：针对移动智能设备（）的算力、内存和能量等无法满足计算密集型需求的问题，提出一种应用任务卸载到高性能边缘服务器的计算卸载。根据任务计算、传输等情况下的能耗和时延，构建出卸载决策系统模型；根据 和边缘服务器的计算能力等情况，降低 能耗为目标，将任务卸载决策问题描述为一个非线性约束优化问题；为对约束优化问题求解提出 算法，算法中将静态学习因子改为动态学习因子，将最优个体引入交叉操作中，扩大算法在解空间中的探索能力。通过实验验证 算法能在较短时间内收敛，实现了 较低的能量消耗。关键词：移动边缘计算；计算卸载；卸载决策；移动智能设备；遗传算法；二进制粒子群算法；算法中图法分类号：文献标识号：文章编号：（）：收稿日期：；修订日期：基金项目：国家自然科学基金项目（、）作者简介：王泽（），女，重庆人，硕士研究生，研究方向为边缘计算、物联网技术；通讯作者：郭荣佐（），男，四川开江人，硕士，教授，会员，研究方向为嵌入式系统、物联网感知技术、边缘计算等。：，（，）：，（），：；引言 的能量、算力和存储等均受限，难以适应移动应用的密集计算任务。云计算技术将计算任务从 卸载到云服务器处理，云服务器位于核心网络且远离，可能会导致延迟敏感型应用的体验质量不佳。为给用户提供更 优 的 服 务，移 动 边 缘 计 算（，）技术在 附近的无线接入网络中提供云计算能力、计算资源和存储资源，是一种低延迟、高宽带、低能耗和计算灵活的计算模式。计算卸载是 中的一个重要研究方向，定义为 将全部或者部分计算任务卸载到 服务器或者云服务器的技术。使用计算卸载技术解决 产生的密集计算任务问题固然是好，但任务卸载过程中可能会受到网络宽带等其它因素的影响，使得任务卸载计算的代价大于在本地执行计算的代价，不适合将任务卸载。所以，找寻最优任务卸载方案是计算卸载中需要解决的一个重点问题。随着信息技术和通信技术的革新，计算密集型大数据分析和处理的能耗高并污染环境。为了减少能源消耗，减少温室气体排放，以及对环境的长期有害影响，绿色网第 卷第期王泽，郭荣佐：基于 算法的 卸载决策络的发展已成为未来无线通信设计和实施的重要课题。因此，降低 中的能耗也是一个重点问题。相关工作近年来，研究人员对 中的计算卸载进行了大量研究，并取得了丰硕的成果。文献 都是关于遗传算法在计算卸载中的应用。文献 中研究了哪些因素对计算卸载性能有影响，其中考虑了卸载决策和资源分配，提出一种基于改进遗传算法（）的边缘计算任务卸载策略。结合基于知识的交叉算子，改进了经典遗传算法的交叉和变异过程，从而扩大了可行解的范围，快速生成全局最优解。该算法在时延和负载均衡方面都取得了较好的效果，但在能耗方面表现一般。文献 中提出了一种任务调度方法，将延迟敏感且计算密集的任务通过并行和顺序卸载到多个 服务器。该问题描述为延迟和卸载故障概率的联合优化，并提出了两种分别基于遗传算法和 的调度算法，两种算法都可以在降低复杂度的同时，性能接近最优。文中指出遗传算法中需要对每条染色体重复计算适应度值，这是遗传算法的一大缺点。文献 中提出了一种基于遗传算法的优化方法，方法中综合考虑了信道带宽、任务卸载比例以及 服务器计算资源。利用遗传算法对最小化用户任务完成时间问题进行优化求解，得到的资源分配方案合理、任务卸载策略最优。文中是在多个移动设备和一台 服务器的情况下最小化总体完成时间，只考虑了用户的完成时间，并没有考虑能耗问题。文献 中针对多目标优化问题，提出了一种基于遗传算法的任务卸载策略，经过大约 次迭代后收敛，减少了系统的总开销。但是传统的遗传算法存在早熟收敛的问题，且可行解范围小，难以找到最优的策略。文献 的研究工作中提出了任务卸载框架和算法，以延长移动设备的电池寿命。文献 中提出一种细粒度的计算任务卸载方法，将问题描述为一个约束的规划任务卸载问题，并使用二进制粒子群（）算法得到最小时延条件下的能耗。文献 和文献 研究了单个移动设备和单个 服务器的计算卸载问题。文献 中通过联合优化移动设备的消耗能量、卸载率和计算延迟，提出了一种部分计算卸载方法。文献 中作者研究了最优部分计算卸载以及调制级数和发射功率的选择，以优化延迟约束下移动设备的能耗。文献 ，中研究了多个移动设备共享单个 服务器进行计算卸载的场景。文献 中研究了具有多用户和一台 服务器的移动边缘系统，其中用户们在基于非正交多址情况下，可以在相同的时隙或频率上同时将计算任务卸载到 服务器。文中计算延迟和下行传输延迟都是固定值，并重点 研究 了 上 行阶段 的 能 量 消 耗。文献 中提出了一种协作卸载框架，其中多个移动设备相互协作以提高移动边缘系统的计算能力。在这些文献工作中，移动设备可以与一个 服务器相关联，然而，将来在 服务器的密集部署中，将计算任务卸载到多个附近的 服务器可能会降低卸载过程带来的时延、能耗、通信等代价。以上文献为了进一步研究 中的计算卸载有着重要意义。在本文中，为了解决以降低移动智能设备能耗为目标的任务卸载决策问题，提出了 环境下基于 算法的任务卸载决策。系统模型本节首先对 卸载决策模型的系统场景进行描述，然后根据任务计算、传输等情况下的能耗和时延进行模型构建，最终得到对应的数学表达式。系统场景 卸载决策系统模型如图所示，系统由多个 和一个边缘云组成。边缘云部署在微蜂窝基站上，其中包括一个 服务器和一个边缘计算调度器，通过高宽带有线将基站与 服务器相连。通过无线链路发送任务和接受响应，且每个无线链路传输通道都支持上行和下行功能。边缘计算调度器负责收集相关信息，执行算法做出决策，将决策传输到 和 服务器。用户一旦开始卸载任务，将直至整个卸载完成，用户无法中途暂停，且信道模型为准静态信道模型，即信道状态始终保持一致。图 卸载决策系统模型为了便于分析，假设系统有个移动智能设备，。用，表示个，假设 在一定时间段内均只能产生一个待处理的不可分割任务，则在一定时间段内总共有个需要处理的计算任务，每个任务用一个 四 元 组，来 表 示，其中，表示第个任务的数据量大小；计算机工程与设计 年表示计算第个任务的 数据需要消耗的 周期数（即机器周期数）；，表示是否卸载：表示任务在本地执行计算；表示任务卸载到 服务器端执行计算；，表示第个任务对延迟的最大容忍度（阈值），在本文中值置为。假设 服务器的计算资源无限，且只考虑部署在单个固定地理位置。通信模型卸载决策过程为：通过上行链路将计算任务相关的数据传输到边缘调度器，边缘调度器收集、无线链路以及 服务器中的相关信息，然后执行 算法，对计算任务卸载做出决策，最后将决策通过下行链路传输到 端，以及传输给 服务器。由于计算卸载过程会产生传输时延和能耗，这对用户的 （，）影响较大，而链路传输数据的速率对传输时延和能耗有影响。系统的上行链路采用正交 频分 多 址（，）技术，假设移动运营商提供的总带宽为 ，总的通信频带被均分为个正交子频带，即 ，令其为，则表示每个任务在传输过程中占用的子频带。根据香农公式的定义可得出任务卸载到 服务器的传输速率 （）式中：表示 的发射功率；表示 与微蜂窝基站之间的上行链路信道增益；表示噪声功率频谱密度。传输时延传输数据量传输速率，则根据式（）可得上行链路上传任务的传输时延 （）在传输任务过程中，能耗传输功率传输时延，则根据式（）得到的传输时延可得上行链路上传任务的传输能耗 （）由于计算结果的数据量大小通常远远小于计算任务的数据量，服务器通过下行链路回传计算结果给 的回传速率也远远大于上行链路，所以 接收计算结果的能耗以及回传时延都可以忽略不计，故本文中不考虑回传时延和接收计算结果能耗。本地计算模型当时，表示任务在本地执行计算的时延，表示任务在本地执行计算的能耗。则 （）由于 （）表示 每个周期的能量消耗模型，其中表示 的 周期有关的能量消耗系数；，表示 提供的计算能力。则任务在本地执行计算时的能耗 表示为 （）（）根据式（）、式（），则全部在本地执行计算的任务，的总能耗 表示为 （）（）卸载计算模型当 时，任 务 卸 载 到 服 务 器 执 行 计 算，服务器对所有与之相连接的 都是资源开放的，假设 服务器的计算资源无限，能为多个 同时提供计算卸载服务。表示任务卸载到 服务器执行计算时，空闲等待的时延，则 （）式中：表示 服务器分配给任务的计算能力。表示任务卸载到 服务器执行计算时，空闲等待的能耗。则 （）式中：表示 空闲等待时的功率。任务卸载到 服务器执行计算，总的时延 包括 和 ，总的能耗 包括 和 ，即 （）（）全部卸载到 服务器执行计算的任务，的总能耗 为 （）由式（）、式（）的总体能耗为 （）（）设任务对延迟的最大容忍度为，以降低移动智能设备能耗为目标，提出优化目标函数及约束条件可以表示为 （），（）式中：表示 服务器的最大计算能力。约束条件 表示变量的取值范围。约束条件 和 表示任务的最大完成时间不可以超过预设的时延阈值。约束条件 表示单个卸载任务的计算量不能超过 服务器的最大计算能力。约束条件 表示 边缘服务器总的计算量不能第 卷第期王泽，郭荣佐：基于 算法的 卸载决策超过最大计算能力。算法在第小节末提出的问题 是一个非线性的约束优化问题，传统的搜索算法难以解决非线性优化问题，而遗传算法将问题参数进行基因编码成染色体后进行优化，不针对参数本身，从而不受约束条件的限制，且遗传算法对目标函数的连续性没有要求。因而，遗传算法适合用于解决非线性的约束优化问题，所以本文中提出遗传算法和二进制粒子群算法的混合算法。经典遗传算法（）通过对染色体进行选择、交叉和变异操作，再通过迭代运算得到最优解，具有过程简单、收敛性强、全局搜索能力强、可扩展性等优点，但是它有一个最大的缺点就是早熟，即对解空间的探索能力有限。二进制粒子群算法（）主要优化离散空间约束问题，具有较强的全局搜索能力，但随着算法迭代次数增加搜索随机性越来越强，且在算法迭代后期缺乏局部搜索能力。基于和 的优缺点，以及文献 中提出的改进遗传算法，本文提出 算法，算法中将 的学习因子改为动态学习因子，在交叉过程中引入最优个体，以提高全局搜索能力和扩大可行解范围，快速产生全局最优值。算法主要包括基因编码和初始种群、个体适应度评价、选择、速度更新和位置更新、交叉和变异几个步骤，接下来将详细描述利用 算法求解最优卸载决策问题的具体过程（在下文中，个体等同于染色体，粒子等同于基因）。基因编码和初始种群由于本文采用二进制卸载方法，且为了便于编码和解码，使用二进制编码的方法初始化染色体，每条染色体对应一种计算卸载决策方案。其中有个待处理的任务，对任务的决策向量进行编码，并采用随机构造方法生成规模为的初始种群，。如图所示，由个基因组成的一条染色体。图由个基因组成的一条染色体 个体适应度评价初始化种群后根据式（），将适应度函数定义为 （）（）（）式（）中取 的总体能耗值倒数作为个体的适应度值，那么适应度值越大，则表示该卸载决策越优。选 择为了尽可能保留适应度值较大的个体，采用轮盘赌方法进行选择操作。首先，由式（）计算出所有个体的适应度值，那么各个个体的选择概率为（），（）表示适应度值 越 大，该 个 体 被 选 中 的 概 率 越 大。（）的 计 算公式为（）（）（）（）然后，将 各 个 个 体 的 选 择 概 率 加 和 得 到 累 计 概 率（），（）相当于在轮盘上的“跨度”，“跨度”越大个体就更容易被选中。（）的计算公式为（）（）（）最后，产生，之间的一个随机数，若（）（），选中个体（）；若（），选中个体（）。速度更新和位置更新 速度更新粒子（基因）的速度更新的公式如下 （）（）（）式中：表示惯性权重；和表示，之间的一个随机数；对 和 进行重新定义：表示当前代中的最优个体（染色体），表示全部代中的最优个体（染色体）；和是学习因子，在传统方法中和一般为固定的某个值，为了提高 算法在解空间中的探索能力，将静态学习因子改为动态学习因子 （）（）式（）、式（