论文研究-基于雾计算的动态任务规划 .pdf-资料库

5 10 15 20 25 30 35 中国科技论文在线 http://www.paper.edu.cn 基于雾计算的动态任务规划# 黄兴勃，林荣恒，邹华** （北京邮电大学网络与交换国家重点实验室，北京 100876）摘要：在雾计算相关的技术越来越广泛地应用于各个领域，在我们的雾计算业务场景下，需要解决动态的任务规划问题，如何在雾计算场景下解决动态任务规划的问题，从而更好分配任务，从而优化整个流程，亟需解决。本文提出基于雾计算的动态任务规划的方法，该方法通过模拟了一个一个虚拟的雾计算的边缘区域，通过路径预测规划，动态的进行任务规划和分配。通过随机生成的场景，预先分配小任务，最终使得整个流程中小任务能够正确分配准确率从贪心规则的方案提升了 10 个百分点。关键词：雾计算；动态任务规划；路径预测；任务分配中图分类号：TP31 Dynamic task planning based on fog calculation huangxingbo, linrongheng, zouhua Telecommunications, Beijing 100876) (Sate Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Abstract: The technology of fog calculation is more and more widely used in various fields, in our fog computing business scenario, We need to solve the dynamic task planning problem, How to solve the problem of dynamic task planning under the fog calculation scenario, so as to better distribute the task, so as to optimize the whole process and urgently need to Solve. In this paper, a method of dynamic task planning based on fog calculation is proposed, which simulates a virtual fog computing edge region, and dynamically carries out task planning and allocation through path prediction Planning. By randomly generating the scene, pre-allocating small tasks, resulting in the entire process small and medium-sized tasks can be correctly assigned accuracy rate reached at 10% Keywords: fog compute;dynamic task planning problem;path prediction;task allocation 0 引言当今世界，云计算凭借强大的计算能力和存储能力，成为大数据分析处理的支撑平台，但是物联网终端设备数量的爆发式增长，给传统的云计算框架带来了新的挑战。云计算框架先将数据集中存储在云端，再从云端发送到移动用户，云服务器远离移动设备，数据传输的距离大，导致延迟和通信开销增大。“雾计算”的概念在 2012 年被思科 (CISCO) 公司首次提出[1]，核心思想是“智能前端化”，即在云服务器和终端设备之间，利用网络设备或者专用设备提供计算、存储和网络通信服务，使得数据和计算更靠近终端设备，进而降低云服务器的计算和存储开销，并且提高了应用系统的响应速度，节约了网络带宽。在雾计算的业务场景中，一个大的任务在完成过程中需要时刻与任务发起的方进行交互，但是发起的 client 往往会在多个边缘节点区域进行移动，所以需要能够预测出节点的运行轨迹，预测出会经过哪些对应的区域，将大的任务进行切分成一些可以独立运行的小任务，然后把这些小任务分配到预测的会经过的区域的边缘服务节点上去执行。本文的章节安排如下：第 2 章将介绍在雾计算中的动态任务规划其他人的相关工作，第基金项目：通信网信息传输与分发技术重点实验室开放课题(XX17641X011-06) 作者简介：黄兴勃（1992 年），男，硕士研究生，主要研究领域是大数据技术，边缘计算技术，SDN 技术通信联系人：林荣恒，男，副教授，主要研究领域为云计算、大数据分析与处理、服务计算支撑. E-mail: rhlin@bupt.edu.cn - 1 -

40 45 50 55 60 65 中国科技论文在线 http://www.paper.edu.cn 3 章给出对本文雾计算场景和任务动态规划的场景模拟和问题建模，第 4 章提出解决该问题的模型和解决算法，第五章对一个具体的例子进行实验及效果分析，第 6 章是结论。 1 相关工作随着大数据时代的到来，为了解决云计算中心负载和数据带宽的问题，研究者也提出多种关于计算任务从云计算中心迁移到网络的边缘的技术，其中主要典型模型包括：分布式数据库模型，P2P 模型，CDN 模型，移动边缘计算模型，雾计算模型以及海云计算。分布式任务分配策略一般分为静态分配策略和动态分配策略。由于在实际应用中，情况复杂，静态的分配方式往往会因为环境的改变导致任务的失败，所以选择动态分配。动态分配策略是在运行过程中，将任务分配给各处理机，并对其上的任务数进行动态调整。尽可能使系统中各处理机上的负载达到动态基本平衡，减少平均响应时间。动态任务分配策略又被称为动态负载平衡策略。在动态分配策略中，比较有代表性的算法是发送者主动算法，接受者主动算法，双向主动算法。动态任务在雾计算场景中的应用，需要考虑几个方面的因素：一是需要考虑到在雾计算的分布式场景中，分布式的完成任务指的是多个边缘区域的计算中心。二是因为移动目标是会在多个区域间进行移动，所以需要将小任务分发到对应区域去进行执行。三是因为在移动目标进行移动的过程中，因为事先规划路线上需要经过的区域由于计算负载等原因，移动目标需要重新规划路线，这时候需要重新分配小任务到新规划的路线上去，动态的根据路线进行任务的分配的工作。为了实现动态的任务规划，有人提出了一种多 Agent 设计系统中的协作方法[2]，提出了支持动态任务分配的支持动态任务分配的公告板机制以及设计过程中的冲突协调方法[3]。有人针对无人作战飞机（UCAV）分布式协同任务分配问题展开研究[4]。在多 UCAV 任务分配问题进行分析的基础上，提出了基于市场协调机制的多 UCAV 分布式协同任务分配体系结构[5]。有人采用蚁群算法对无人机协同多任务分配问题（CMTAP）进行研究[6]。在通用 CMTAP 模型的基础上，综合考虑包括动态任务时间约束和无人机任务能力的差别多类复杂条件，建立扩展的协同多任务分配模型[7]。在多子群蚁群算法的基础上，提出了基于分工机制的蚁群算法对 CMTAP 进行求解[8]。设计了基于任务能力评估的问题解构造策略和基于任务代价的状态转移规则[9]。提高了算法的性能。有人根据物联网场景，在无线传感器网络中，构造了无线传感器网络任务分配的动态任务模型[10]，继而提出了一种基于离散粒子群优化的任务分配算法[11]。 2 问题定义本章将给出关于雾计算场景下的动态任务规划的定义，并对解决问题进行定义和建模。 70 2.1 问题描述目标用户在不同的边缘的区域之间进行移动时，其提交的任务无法在一个边缘服务器上进行计算完成，这时候需要用户路线上的边缘服务区域服务器协同来完成这个任务。首先需要能够准确的预测出物体的移动的路线，经过哪一些边缘服务器区域，然后根据当前区域的大小，按照比例值将指定数量的小任务分配给对应的边缘区域来完成。由于在移动的过程中， 75 会受到很多其他外界因素的干扰，比如气候环境，电磁波干扰等，需要重新规划路线，有效的做到动态的调整任务的分配，使得任务能够尽可能多的被完成。 - 2 -

国科技论中国 2.2 论文在线线束条件问题约束 http ://www.paper.e edu.cn 边缘区域的的传感器数量量 num_i，区域域具备的计算算力，尽量将将任务分配到到计算力强的区域上每个区域有有个空闲系数数 a（0-1），区区域实际具备备的计算力，区域实际能能处理的任务务需要需要综合考考虑区域的传，区域当前的空闲状态，，以及距离区，每个边缘区区域都有一个个中心区域的的坐标(xi,yi) 区域中心的距距离，乘以以这个系数模拟的区域域图是在一个个二维的图上传感器的数量可能的小。来使 2.3 使得任务分配配的代价尽可模问题建模 x 轴是空间中在图 1 中，的位置是高斯感器，传感器的传感红色色是每个类的的聚类中心，聚聚类中心是每中的 x 坐标，斯分布随机打 y 轴是空间打出来的，然后间中 y 坐标，后使用 Kmea 边缘中心的位每个非红色 ans 聚类算法位置。根据这为每每个边缘区域域。同时设定定左下坐标为作为起始点，右上坐标为为终终点。目标物物体会从左下下角的起点沿边缘区域到达达右上角的终每个区域的边（0,0）的作途经过给个边个一个个类，域作的作色的点是一个法划分了 9 个这个中心划区（100,100）终点。 80 85 90 图 Fig. 1 S 1 传感器聚类 Sensor Clusterin 类图 ng diagram 95 3 案解决方案 3.1 （1）直接通过）每次选过建立传感器数量和距距离公式建立强规则的的数学模型径型来预测路径选择当前周围围区域相邻的的几个区域中中传感器数量量最多的那个个作为要选择的区 - 3 -

100 105 110 115 国科技论论文在线线 http ://www.paper.e edu.cn 中国域（2）（3））将沿途）将大任途要经过的区域加入到备任务分解成小小任务，然后将去选的队列中去配到这些区域将小任务分配域中去 - 前位置的距离离综合考虑设计一个决策公公式器的数量，c 为归一化的 (max n_sample_num m) 距离 x_sample_num m / 图 2 强 Fi g. 2 Path diag 00,100）这个空规则模型在（10 强规则贪心模型 gram of strong r 空间下得到的轨型的路径图 rule greedy mo 轨迹运行图 odel 就是根据强规图 2 3.2 （1）基于逻辑辑回归的雾计算动态任任务分配算法 3.2.1 1 建立逻辑辑回归的数学学模型，预测测飞行轨迹区域的数量 n 系数 q = (1- b) 超参数，d 为归 (cluster_ n，和距当前 )abs(log2(d)) 归一化的区域 _sample_num = + b * c 域内的传感器 - min m[i] e_num)。 ample_num = sample_num = ur_distance - 比例系数，进 = Min(cluster = Max(cluste min_distance 进行归一化 r_sample_sum er_sample_nu e) / bili m[i]) um[i]) ）根据每个区决策系其中 b 为超其中 d min_sample 其中 min_sa 其中 max_s 其中 c = (cu 其中 bili 是）根据决策参 ex_list.append （2） inde 参数每次选择 d(index) 择一个区域作作为下一次的的目标区域，加入到目标标区域队列 3.2.2 2 分配指定定数量的小任任务（1））选择前 80% %作为前后要要经过的区域域，并为每个个区域分配任任务，分配的的任务的数量量，与 - 4 -

120 125 130 135 中国国科技论论文在线线 http ://www.paper.e edu.cn 径的长度成正正比（这里半径的定义为 r = Max(dist tance(聚类中中每个点，聚聚类中个区域的半径每个心)) ）（2））每个被选中 cur_ _task_num = i 中 cur_r2 为当其中中 min_r2 为被中 base_task_n 其中其中中区域分配的 int(cur_r2 / m 当前区域的半的小任务数量 min_r2) * bas 半径长度域中最小的半被选中的区域 num 比例参数数用来控制最量为 e_task_num，，半径长度最小区域所包包含的小任务务的数量 3.2.3 3 设计实际线际的轨迹路线（1）（2））每次运动会会有一个高斯斯分布的波动）每个区域实实际能处理的的小任务的数差动的位置变差上空闲参数数量需要乘上 Fig. 3 Path 就是该算法得图 3 h diagram of dyn 得到的实际的运运行轨迹逻辑回归的雾 namic task assi 雾计算动态任务 gnment algorith 务分配算法的路 hm for fog calc 路径图 culation of logis stic regression 图 3 3.3 标优化目标小任务能够 Accuracy = ( 够正确被处理 (被处理处理理的数量的比的小任务) / 例（事先分配配的小任务的数量） 4 实验结果果分析本章将分成两，第一部分我两部分进行，一下该方法。分我我们将探讨一我们将对两种种方法的的准准确率的比较较和分析，第第二部 - 5 -

140 145 150 155 160 国科技论论文在线线 http ://www.paper.e edu.cn 中国 4.1 方法的准设置了 100* 大小的平面区 00,300,500,1 设置 8 个任务的区域，将拆种大成 1 后设过的准确性比较 *100,300*300 区域，起点和 1000,3000,50 务，将这些任务定的场景设定 000*1000,300 0,500*500,10 置在左下角和终点分别设置 000,10000 个务按照不同的的策略分成指点，然后用聚 00*3000，50 和右上角。然聚类算法让这指定数量的小 000*5000，1 然后在对应的这些点生成 9 小任务，然后 0000*10000 的区域内，随 9 个边缘区域后根据预测的这 7 随机生域。然要经拆分后的小任务分配上去。。实际的运动动路线也是根根据距离，处处理能力，繁繁忙程度模模拟出来的一一条路线，但有有加上一部分数的误差模拟拟出来的。然然后就可以根根据此计算算出来对应的的小任务的分分配成功的比分的高斯函数例。 4.2 方法的结将两种方法在状图图可以得到如结果准确性析的比较分析 0 次试验取均图上做 1000 在不同点的图如下的结果图均值得到不同同的任务分配配的准确率，做柱图 4 F Fig. 4 Accurat 算法的准确率 te rate comparis 率比较 son of algorithm ms 在图 4 中我准确性的提升的准我们可以看到升。，优化后的算算法，在各种种维度的图上上，都能有大大约 10 个百分点 5 结论本文提出了了基于雾计算算的动态任务分配的应用和和场景，并提提出了一种基基于逻辑回归的雾计算算动态任务分著的提升。显著分配算法来进进行优化提升传传统的基于简简单贪心的任任务分配算法法，在准确率率上有 - 6 -

中国科技论文在线 http://www.paper.edu.cn 致谢本论文受通信网信息传输与分发技术重点实验室开放课题(XX17641X011-06)资助，在此表示衷心的感谢 [参考文献] (References) 165 170 175 [1] 王庆.从云计算跨越到边缘计算[J].信息通信技术,2018,12(05):4-8. [2] 张家良,王迎磊,李复名,周涛.多 Agent 动态任务分配问题[J].电子技术与软件工程,2018(18):255-258. [3] 刘鹏飞,毛莺池,王龙宝.基于云雾协作模型的任务分配方法[J/OL].计算机应用:1-8[2018-12-03]. [4] 吴蔚楠. 多无人飞行器分布式任务规划技术研究[D].哈尔滨工业大学,2018. [5] 冯珊珊. 基于适应度与蚁群分散搜索的多机器人任务分配[D].郑州大学,2018. [6] 杜继永 , 张凤鸣 , 杨骥 , 吴虎胜 . 多 UCAV 协同任务分配模型及粒子群算法求解 [J]. 控制与决策,2012,27(11):1751-1755. [7] 邓可, 连振江, 周德云, 李枭扬. 基于改进量子粒子群算法的多无人机任务分配[J]. 指挥控制与仿真,2018,40(05):32-36. [8] 陈岩. 蚁群优化理论在无人机战术控制中的应用研究[D].国防科学技术大学,2007. [9] 苏菲. 动态环境下多 UCAV 分布式在线协同任务规划技术研究[D].国防科学技术大学,2013. [10] 郭凤. 无线传感器网络中任务调度优化方法研究[D].北京邮电大学,2018. [11] 梁国强 , 康宇航 , 邢志川 , 尹高扬 . 基于离散粒子群优化的无人机协同多任务分配 [J]. 计算机仿真,2018,35(02):22-28. - 7 -

资料库

论文研究-基于雾计算的动态任务规划 .pdf

相关推荐

开发技术

热门标签

最新资料