基于可行点追踪-连续凸逼近的移动边缘计算任务卸载.pdf

计算机与现代化JISUANJI YU XIANDAIHUA2023年第8期总第336期文章编号：1006-2475（2023）08-0093-05收稿日期：2023-01-19；修回日期：2023-03-13基金项目：国家自然科学基金面上项目（61772221）；广州华商学院校内导师制科研项目资助（2023HSDS07）作者简介：陈刚（1973），男，湖南长沙人，副教授，硕士，研究方向:信息安全与云计算，Email:chengang_；王志坚（1970），男，湖南长沙人，教授，博士，研究方向：控制理论与控制工程；徐胜超（1980），男，湖北武汉人，副教授，硕士，研究方向：并行分布式处理软件。0引言核心网在用网高峰期需要传输的数据量远高于其他阶段，承担的负载压力过大，再加上云数据中心通常与用户的智能设备之间存在一定的距离，增加了网络延迟1。为了解决上述问题，一些专家和学者提出了移动边缘计算技术2，但在单位时间内，本地设备只能处理有限的数据，需要将计算任务卸载到靠近网络边缘的服务器上，以提高核心网的整体计算能力。因此，进行边缘计算任务卸载方法的研究成为了相关领域研究的热点3。文献 4 考虑业务优先级和长期能耗约束，建立任务卸载模型，在 Lyapunov优化的基础上将任务卸载问题转变为确定性优化问题，采用基于梯度价格拍卖算法求解任务卸载问题。文献 5 在考虑系统延迟和能耗的基础上，建立了任务卸载优化模型，并在任务卸载过程中引入免疫优化算法对卸载优化模型进行求解。文献 6 将负载、延迟和能耗最小作为目标，建立移动边缘计算任务卸载模型，通过遗传算法获取模型最优解，完成任务卸载。上述方法在任务卸载过程中，无法准确地选择任务卸载的地点，存在任务卸载精度低的问题。文献 7 以5G网络为基础，在V2X架构下开展网络应用的边缘云计算任务卸载研究。以降低任务卸载延迟为目标，采用多址边缘计算使云资源逐渐接近网络边缘。在移动环境下完成边缘云计算任务的远程卸载。文献 8 提出基于改进蝴蝶优基于可行点追踪-连续凸逼近的移动边缘计算任务卸载陈刚，王志坚，徐胜超（广州华商学院数据科学学院，广东 广州 511300）摘要：移动边缘计算任务卸载会受到邻近服务器的干扰，导致计算任务难以准确卸载到网络边缘服务器，因此设计基于可行点追踪-连续凸逼近的移动边缘计算任务卸载方法。该方法首先建立移动边缘计算任务的依赖模型，分析移动边缘计算任务的卸载需求。其次，考虑任务卸载时延和卸载能耗，以任务依赖模型为依据，建立任务卸载模型。最后，采用可行点追踪-连续凸逼近，将求解卸载模型的求解问题转变为线性松弛问题，引入迭代过滤函数追踪可行点，避免邻近服务器的干扰，对松弛变量进行连续凸逼近获取任务卸载模型的最优解，实现移动边缘计算任务的卸载。实验结果表明，本文方法负载低、卸载能耗低、卸载精度高。关键词：可行点追踪-连续凸逼近法；移动边缘计算；任务依赖模型；线性松弛问题；任务卸载中图分类号：TP393.4文献标识码：ADOI：10.3969/j.issn.1006-2475.2023.08.015Mobile Edge Computing Task Offloading Based on Feasible Point Tracking ContinuousConvex ApproximationCHEN Gang，WANG Zhi-jian，XU Sheng-chao（School of Data Science，Guangzhou Huashang College，Guangzhou 511300，China）Abstract:The task unloading of mobile edge computing will be interfered by adjacent servers，which makes it difficult to accurately unload computing tasks to network edge servers.Therefore，a task unloading method of mobile edge computing based onfeasible point tracking continuous approximation method is designed.This method firstly establishes the dependency model of mobile edge computing tasks，and analyzes the unloading requirements of mobile edge computing tasks.Secondly，considering thetask unloading delay and energy consumption，the task unloading model is established based on the task dependency model.Finally，the feasible point tracking continuous convex approximation method is used to transform the problem of solving the unloading model into a linear relaxation problem.Iterative filter functions are introduced to track the feasible points to avoid interferencefrom adjacent servers.The relaxation variables are continuously convex approximated to obtain the optimal solution of the task unloading model，so as to realize the unloading of mobile edge computing tasks.The experimental results show that the proposedmethod has low load，low energy consumption and high unloading accuracy.Key words:feasible point tracking continuous convex approximation method；mobile edge computing；task dependency model；linear relaxation problem；task unloading计算机与现代化2023年第8期化算法的移动边缘计算任务卸载方法，该方法采用任务优先级排序，对边缘云计算任务卸载执行顺序排序。采用Levy飞行方法对蝴蝶优化算法进行改进，避免陷入局部最优问题，采用改进的蝴蝶优化算法构建任务卸载模型。文献 9 提出基于优先级的移动边缘计算任务卸载方法，根据卸载任务分配的周期，判断任务卸载的优先级，根据优先级结果将任务卸载到边缘服务器上。上述方法，虽然能够完成边缘计算任务的卸载，但是卸载任务时消耗能量较多，存在能耗高的问题。可行点追踪-连续凸逼近（Feasible Point Pursuit-Successive Convex Approximation，FPP-SCA）方法是一种通过追踪可行解点来求解非凸优化问题的处理方法，它将非凸优化问题转化为一系列凸问题，从而得到准确的求解结果。为了获得移动边缘计算任务卸载模型的最优解，将任务准确地卸载到边缘服务器中，本文提出基于可行点追踪-连续凸逼近法的移动边缘计算任务卸载方法。本文最后通过仿真实验的方式，验证了可行点追踪-连续凸逼近法的优秀性能。1边缘计算组成移动边缘计算由3个部分构成，具体结构如图1所示。1）用户设备层：该层由手机、电脑和传感器构成。2）边缘服务器层：划分边缘服务器的区域时，主要是以距离为依据，不同区域中存在若干个边缘服务器。3）云数据中心层：该层的主要任务是为用户提供相关服务，由物理服务器构成。图1移动边缘计算的组成结构当计算任务需要卸载到网络边缘服务器时，采用切分算法对移动边缘计算任务进行划分，获得若干个子任务，从而提高任务卸载的效率与精准性。边缘计算任务中存在的数据量较大，因此任务卸载的计算量也较大。通过任务划分后获得的子任务之间通常存在数据交互，但子任务在移动边缘计算过程中可以独立执行，可将其作为前提条件，展开移动边缘计算任务卸载。2移动边缘计算任务卸载方法设计根据移动边缘计算的组成分析，对移动边缘的可用有向图Loop=（B，R）描述子任务在移动应用中存在的依赖关系，有向图如图2所示。图2有向图如图2所示，拆分后获得的子任务可用图中存在的节点biB描述，任务在移动应用中存在的依赖关系可用图中的边rij R描述。执行完任务后，可向bi传输数据，只有接收到数据后，才可以继续执行任务bi。用B=b1，b2，b3，b4，b5表示子任务构成的集合，其中在本地设备中需要执行任务b1、b5，分析需求可卸载其余任务。2.1任务卸载模型设计基于可行点追踪-连续凸逼近法的移动边缘计算任务卸载方法，考虑卸载能耗和时间，建立移动边缘计算任务卸载模型。2.1.1任务卸载时间任务卸载时间由2个部分构成，分别是数据传输时间和任务计算时间。1）任务计算时间。分配任务bi时，通过下式获取计算任务所需的时间ti(i)，如公式（1）所示。ti(i)=Eii，i c（1）公式（1）中，Ei表示任务bi对应的负载；c表示边缘服务器；i表示边缘服务器c的计算速度；i表示边缘服务器中第i个节点。2）数据传输时间。由于不同设备的传输带宽不同，因此统一计算数据传输的总时间tj，如公式（2）所示。tj=Ft(bi)+ti(i)（2）公式（2）中，Ft(bi)表示任务bi的传输时间。2.1.2任务卸载能耗移动边缘计算任务卸载处理过程中终端设备的能耗计算，如公式（3）所示。Rend=AendTend+AupTup+AdownTdown+Ajtj（3）公式中，Aend表示终端执行任务的功率，Tend表示终端执行任务的时间，Aup表示终端执行上传任务的功率，Tup表示终端上传任务的时间10-11。Adown表示终端云数据中心层转换器区域1边缘服务器1边缘服务器2边缘服务器3.区域2边缘服务器1边缘服务器2边缘服务器3.区域n边缘服务器1边缘服务器2边缘服务器3.接入点接入点接入点电脑手机传感器.电脑手机传感器.电脑手机传感器.RBrij1b4b3b2b5b942023年第8期下载任务的功率，Tdown表示终端下载任务的执行时间，Aj表示计算数据传输总功率，传输的总时间为tj。2.1.3移动边缘计算任务卸载模型在任务卸载过程中，根据网络传感器采集的数据量，来确定任务卸载执行的位置12-13，在降低移动设备能耗的同时，还需要满足延迟的要求。基于可行点追踪-连续凸逼近法的任务卸载方法，是利用数据聚类理论中的二进制形式，采用二进制变量ui描述是否在位置Zi处执行任务bi的卸载；用二进制变量xi描述是否由无线接入点Ai执行任务bi的传输，当变量xi的值为1时，表明利用无线接入点Ai卸载任务bi。根据上述理论建立任务卸载模型ILP，如公式（4）所示。ILP=mint=1Ti=1M(Rlocali,t+Rend)M T（4）式中，T表示任务卸载的监视周期；M表示移动设备的数量；Rlocali,t表示设备运行任务bi的能耗14-15。2.2基于可行点追踪-连续凸逼近法的模型求解利用可行点追踪-连续凸逼近法求解移动边缘计算任务卸载模型主要分为以下步骤。1）用线性规划问题描述任务卸载问题，并引入迭代过滤函数G（x）和函数(x)进行可行点的跟踪，如公式（5）所示。ui=i=1Mt=1TZhG(x)(EiWdle/WL-EiWu/Wu)xi=i=1Mt=1TAi(x)gi(i+i)（5）公式（5）中，Wdle表示移动设备在待机状态下对应的功率；WL表示数据中心或边缘服务器在任务卸载过程中的计算速度，可通过支持向量机计算得到16-18；Ei表示任务bi对应的负载；Wu表示移动设备计算任务的速度；gi表示任务bi中存在的数据量19；i表示能耗因子；为常数。2）引入限制条件，根据上述过程提取的可行点，创建任务卸载的分支问题，通过迭代学习进行松弛变量的连续凸逼近，获得任务卸载模型的最优解，如公式（6）所示。y=ILP+i=1iv*isubject to v*i 0（6）公式（6）中，y表示获得任务写在模型的最优解，表示正定系数，v*i表示松弛变量，正定系数可以使松弛变量逼近于零20-23。通过上述计算，使用可行点追踪-连续凸逼近法，完成任务卸载模型的求解，实现计算任务的卸载。3仿真实验与性能分析3.1仿真实验环境为了验证基于可行点追踪-连续凸逼近法的移动边缘计算任务卸载方法的整体有效性，需要对其展开测试。此次实验使用的微云移动云计算系统，微云系统具备了一个较小规模的云系统能力。从一个工作站到一个复杂的物理服务器集群不等。微云使用虚拟化中间件，将其硬件组成一套虚拟元件封装在虚拟机中，每个虚拟机均可以分配到可用的硬件资源的一部分。更大的内存容量有助于微云系统支持更多的高效率的虚拟机。它包含中等大小容量的存储和可达到千兆规模的一组处理器。同时，微云系统必须配置一组收发基站，用以接收和发送数据包到实体，其架构如图3所示。图3微云移动云计算系统架构从图3可知，该移动云计算系统通过WLAN实现多个微云的共同服务，与传统的无线基站访问方式相比，直接可以通过微云实现移动设备与远端设备的连接。本次测试的移动边缘环境，如表1所示。表1移动边缘测试环境参数移动边缘的计算能力/（GHz/周期）子信道带宽/MHz容忍最大时延/s子信道数量需要的CPU周期/GHz最大发送功率/dBm计算任务大小/kB计算能力/(GHz/周期)背景噪声功率/dBm电路空闲状态下的功率消耗/mW数值40.315300.31.12550010000.10.8-100103.2实验结果与性能分析采用本文方法、文献 4 方法和文献 5 方法进行多次迭代任务卸载测试来测试任务卸载产生的网络负载，网络负载即任务卸载占用的网络带宽。3种方法的网络负载情况，如图4所示。由图4可知，随着迭代次数的增加，3种方法的负载逐渐降低，在测试过程中，本文方法的负载最终降低至50 Mbps以内，文献 4 方法在测试过程中，在前期阶段和中期阶段的负载波动较大，但最终负载控制在100 Mbps以内。文献 5 方法测试过程中，负载波动相对小于文献 4 方法，但最终负载高于其他2种方法。对比本文方法、文献 4 方法和文献 5 方法的测试结果可知，在移动边缘计算任务卸载过程中，本远端云服务器移动设备微云微云微云基站无线连接有线连接陈刚，等：基于可行点追踪-连续凸逼近的移动边缘计算任务卸载95计算机与现代化2023年第8期文方法具有较小的负载，这是由于本文方法引入迭代过滤函数追踪可行点，避免了邻近服务器的干扰，从而降低了负载。为了进一步验证本文方法在移动边缘计算任务卸载性能，以任务卸载处理过程中终端设备的能耗为指标，进行对比实验。终端设备能耗通过公式（3）计算获得，对比结果如图5所示。图5不同方法的任务卸载能耗由图5可知，随着任务的增大3种方法卸载任务的能耗不断增加，在相同任务大小和测试环境中，本文方法卸载任务的能耗均低于其他2种方法，因为本文方法在建立移动边缘计算任务卸载模型之前，考虑了任务卸载能耗，所以降低了卸载任务消耗的能量。在任务卸载过程中存在一部分任务需要卸载在本地设备中，一部分任务需要卸载到远端服务器中的情况，现采用上述方法任务展开卸载测试，通过显示器显示任务卸载精度。不同方法的任务卸载精度结果，如图6所示。（a）本文方法（b）文献 4 方法（c）文献 5 方法图6不同方法的任务卸载精度由图6可知，本文方法可准确地将不同类型的任务卸载到指定区域，而文献 4 方法和文献 5 方法的任务卸载结果存在较大误差，表明本文方法具有较高（a）本文方法（b）文献 4 方法（c）文献 5 方法图4不同方法的负载堆积折线图任务卸载时间/s10203040500100200300400500网络传输负载/Mbps06010203040500100200300400500060任务卸载时间/s网络传输负载/Mbps10203040500100200300400500060任务卸载时间/s网络传输负载/Mbps任务大小/kB5006007008009000515202530终端设备能耗/J400100本文方法文献4方法文献5方法本地设备远端服务器本地卸载的任务服务器卸载的任务本地设备远端服务器本地设备远端服务器本地卸载的任务服务器卸载的任务本地卸载的任务服务器卸载的任务962023年第8期的任务卸载精度。本文方法具有较高卸载精度的原因在于其采用可行点追踪-连续凸逼近法将卸载模型求解问题转化为线性松弛问题，通过连续凸逼近获取任务卸载模型的最优解，从而完成了高精度卸载。4结束语为了满足任务的计算需求，需要研究移动边缘计算任务卸载方法。目前移动边缘计算任务卸载方法存在负载高、卸载能耗高和卸载精度低的问题24-27，为此本文提出基于可行点追踪-连续凸逼近法的移动边缘计算任务卸载方法，该方法根据任务依赖关系建立移动边缘计算任务卸载模型，通过求解模型，实现移动边缘计算任务的卸载。本文方法有效解决了目前移动边缘计算任务卸载方法中存在的问题，有效降低了负载和卸载能耗，提高了任务卸载精度。参考文献：1DAS S，SAHNI S.Two-aggregator topology optimizationusing single paths in data center networks J.IEEE Transactions on Cloud Computing，2021，9（2）:807-820.2 MARCH R D，LEUZZI C，DEFFACIS M，et al.Innovativeapproach for PMM data processing and analytics J.IEEETransactions on Big Data，2020，6（3）:452-459.3PUSHPA J，KALYANI S A.Using fog computing/edgecomputing to leverage digital twin J.Advances in Computers，2020，117（1）:51-77.4 毛水强，洪健，任华，等.面向电力物联网的5G移动边缘计算任务卸载方法 J.电测与仪表，2022，59（2）:105-111.5 朱思峰，孙恩林，柴争义.移动边缘计算场景下基于免疫优化的任务卸载 J.西安电子科技大学学报，2022，49（1）:152-160.6 贾觐，暴占彪.改进GA的边缘计算任务卸载与资源分配策略 J.计算机工程与设计，2021，42（11）:3009-3017.7 BREHON-GRATALOUP L，KACIMI R，BEYLOT A.Mobile edge computing for V2X architectures and applications:A survey J.Computer Networks，2022，206.DOI:10.1016/net.2022.108797.8 HOSSEINZADEH M，MASDARI M，RAHMANI A M，etal.Improved butterfly optimization algorithm for data placement and scheduling in edge computing environmentsJ.Journal of Grid Computing，2021，19（2）:1-27.9 FAROOQ M O.Priority-based servicing of offloaded tasksin mobile edge computing C/2021 IEEE 7th World Forum on Internet of Things（WF-IoT）.2021:581-585.10 ALKHALAILEH M，CALHEIROS R N，NGUYEN Q V，et al.Data-intensive application scheduling on mobile edgecloud computing J.Journal of Network and Computer Applications，2020，167.DOI:10.1016/j.jnca.2020.102735.11 ZHOU H，XIANG Y，LI H F，et al.Task offloading strategy of 6G heterogeneous edge-cloud computing model considering mass customization mode collaborative manufacturing environmentJ.Mathematical Problems in Engineering，2020，2020.DOI:10.1155/2020/1059524.12 SAEIK F，AVGERIS M，SPATHARAKIS D，et al.Taskoffloading in edge and cloud computing:A survey on mathematical，artificial intelligence and control theory solutionsJ.Computer Networks，2021，195（4）.DOI:10.1016/net.2021.108177.13 LI B，HOU P，WU H，et al.Placement of edge serverbased on task overhead in mobile edge computing environmentJ.Transactions on Emerging TelecommunicationsTechnologies，2021，32（9）.DOI:10.1002/ett.4196.14 LIU D Y，CHEN X，ZHOU Z，et al.HierTrain:Fast hierarchical edge AI learning with hybrid parallelism inmobile-edge-cloud computingJ.IEEE Open Journal ofthe Communications Society，2020，1:634-645.15 CHENG S T，XU Z H，LI X H，et al.Task offloading forautomatic speech recognition in edge-cloud computingbased mobile networksC/2020 IEEE Symposium onComputers and Communications（ISCC）.2020:1-6.16 刘俐，李勇，曹一家，等.基于支持向量机和长短期记忆网络的暂态功角稳定预测方法 J.电力自动化设备，2020，40（2）:129-139.17 YANG X，HAN M R，TANG H L，et al.Detecting defectswith support vector machine in logistics packaging boxesfor edge computingJ.IEEE Access，2020，8:64002-64010.18 PRIYADARSHINI R，BARIK R K，DUBEY H.FogSDN:A light mitigation scheme for DDoS attack in fog computingframework J.International Journal of Communication Systems，2020，33（9）.DOI:10.1002/dac.4389.19SUN C，LI H，LI X H，et al.Task offloading for end-edge-cloud orchestrated computing in mobile networksC/2020 IEEE Wireless Communications and Networking Conference（WCNC）.2020:1-6.20CHEN Z Y，HU J Q，CHEN X，et al.Computation offloading and task scheduling for DNN-Based applications incloud-edgeComputing J.IEEEAccess，2020，8:115537-115547.21TONG Z，YE F，MEI J，et al.A novel task offloading algorithm based on an integrated trust mechanism in mobileedge computingJ.Journal of Parallel and DistributedComputing，2022，169:185-198.22 ZHANG J W，JIANG B，ZHAO H，et al.Time-sensitivemulti-user oriented mobile edge computing task scheduling algorithmC/2020 2nd International Conference onComputer Communication and the Internet（ICCCI）.2020:145-149.23 DELOWAR H M，ABU L M，SULTANA T，et al.Orchestration-based task offloading for mobile edge computing in small-cell networks C/Proceedings of International Joint Conference on Computational Intelligence.2020:629-641.24 AMER D A，ATTIYA G，ZEIDAN I，et al.Elite learningHarris hawks optimizer for multi-objective task schedulingin cloud computingJ.The Journal of Supercomputing，2022，78（2）:2793-2818.25 SMYS D，RANGANATHAN D.Performance evaluation ofgame theory based efficient task scheduling for edge computing J.Journal of ISMAC，2020，2（1）:50-61.26 QIAN Y W，SHI L，LI J，et al.An edge-computing paradigm for Internet of Things over power line communicationnetworks J.IEEE Network，2020，34（2）:262-269.27 WANG Y，RU Z Y，WANG K Z，et al.Joint deploymentand task scheduling optimization for large-scale mobile users in Multi-UAV-Enabled mobile edge computingJ.IEEE Transactions on Cybernetics，2020，50（9）:3984-3997.陈刚，等：基于可行点追踪-连续凸逼近的移动边缘计算任务卸载97