一种基于截止时间感知的边云协同任务调度方法及系统

IPRDB

API 数据接口

专利申请

使用指引 chat嘟嘟

会员体验

联系我们

交流群

现在联系顾问~

一种基于截止时间感知的边云协同任务调度方法及系统
申请号	CN202110229562.3	申请日	2021-03-02	公开(公告)号	CN113132456B	公开(公告)日	2022-09-30
申请人	西安电子科技大学;			发明人	沈玉龙; 贺梦帅; 滕跃; 张志为; 张涛; 李光夏;
摘要	本发明属于计算机应用技术领域，公开了一种基于截止时间感知的边云协同任务调度方法及系统，所述基于截止时间感知的边云协同任务调度方法包括：终端设备数据发送至统一接入模块；对任务预分类，分别发送至不同目的地；任务调度中心提取任务类型和任务截止时间，查询安装了对应服务的服务器集合Stargetl；将任务拟分配至Starget1中的服务器，计算时延是否满足截止时间，将任务分配给至满足条件的服务器；任务到达目标服务器，生成新的任务执行队列。本发明由统一接入模块接收终端设备产生的任务数据，对任务预分类后发送到远程云中心或任务调度中心，保证边缘云系统负载均衡，提高整体边云架构的资源利用率。
权利要求	1.一种基于截止时间感知的边云协同任务调度方法，其特征在于，所述边云协同任务调度方法包括：终端设备数据发送至统一接入模块；对任务预分类，分别发送至不同目的地；任务调度中心提取任务类型和任务截止时间，查询安装了对应服务的服务器集合Starget1；将任务拟分配至Starget1中的服务器，计算时延是否满足截止时间，将任务分配给至满足条件的服务器；任务到达目标服务器，生成新的任务执行队列；所述对任务预分类，分别发送至不同目的地具体过程为：根据终端数据类型和业务特性，将终端设备产生的任务预分类，在统一接入模块将计算开销大且时延不敏感型任务发送到远程云中心处理，其余任务发送到任务调度中心；任务调度中心对接收到的任务数据处理，提取出任务类型及任务完成截止时间的关键信息，根据任务类型判断处理该任务所需的服务，然后从服务注册表中查询安装了该服务的边缘服务器，得到满足条件的服务器集合Starget1；所述将任务拟分配至得到的Starget1中的每台服务器，计算任务传输时延、计算时延和分配该任务造成其它任务增加的等待时间，将满足任务截止时间的服务器集合记为Starget2；其中，传输时延根据任务数据量的大小和任务调度中心到目标服务器的实时网络状况计算，计算时延包括等待时延和执行时间；传输时延加上计算时延小于任务截止时间为满足任务截止时间要求；如果得到的Starget2为空，即没有能够满足该任务截止时间的边缘服务器，则丢弃该任务并发出通知；如果Starget2中只有一个满足条件的服务器，则将任务分配至该服务器处理；如果Starget2中有多个满足条件的服务器，则选择分配该任务造成其它任务增加等待时间最短的服务器；所述任务到达得到的目标服务器starget，执行单服务器中的任务调度算法：如果starget中没有其他任务等待处理，则直接处理该任务；如果starget中有任务等待队列，首先将任务拟放置在队列尾部，所有前置任务的执行时间即为该任务当前位置的等待时延，判断等待时延和该任务的执行时间之和是否满足任务截止时间，如果满足，则任务在队尾等待执行；如果超过截止时间，则将该任务依次往前移动，计算该任务的插入对其他任务等待时延的影响，如果造成其他任务超时，则丢弃该任务，即服务器不能在规定截止时间内完成该任务；如果没有造成其他任务超时，计算当前位置该任务等待时间，并判断是否满足截止时间，如果满足，则将该任务插入当前位置生成新的任务执行队列；其中，新到达任务的插入会造成其他任务执行顺序延后进而等待时间增加；任务执行时间的计算步骤如下：服务器记录最近时间t内每次执行某类任务的数据量大小和执行时间，由数据量除以执行时间计算出最近处理该任务的单位执行时间；任务数据量大小除以最近该任务单位执行时间计算出任务执行时间。 2.如权利要求1所述的边云协同任务调度方法，其特征在于，所述服务注册表的创建和更新步骤如下：远程云中心创建并维护服务注册表，该注册表主要记录每个边缘服务器上当前已安装的服务列表，远程云被标识安装了所有服务的边缘服务器；每当边缘服务器有安装或者卸载服务的操作，该操作会被更新到远程云中心的服务注册表；远程云中心的服务注册表发生更新后，会自动同步到任务调度中心的服务注册表。 3.一种终端设备，其特征在于，所述终端设备使用计算机可执行指令和/或包含在处理器控制代码中来实现权利要求1～2任意一项所述的边云协同任务调度方法。 4.一种实施如权利要求1～2任意一项所述边云协同任务调度方法的边云协同任务调度系统，其特征在于，所述边云协同任务调度系统，包括：统一接入模块，对终端设备产生的计算任务数据统一接收并预分类处理；任务调度中心，接收提取任务关键信息，保存服务器相关状态信息，包括实时网络通道状况，服务器所安装服务；边缘服务器集群和远程云，确定任务执行顺序并处理。
说明书全文	一种基于截止时间感知的边云协同任务调度方法及系统技术领域 [0001] 本发明属于计算机应用技术领域，尤其涉及一种基于截止时间感知的边云协同任务调度方法及系统。背景技术 [0002] 目前，随着物联网、移动互联网等技术的快速发展，终端设备数据量正以井喷式上涨。持续快速的数据量增长推动了整个计算模式的演变，同时也对数据存储与处理技术提出了更高要求，尤其是网络边缘侧业务的实时处理和智能分析。得益于云计算技术，越来越多的移动应用程序和物联网设备可以利用远程云中心丰富的计算资源处理本地的计算密集型任务(如图像处理任务)。从理论上来讲，这种任务分流可以显著扩展移动设备的能力，但是设备到远程云端的高通信时延可能会严重降低服务质量。由于传统云计算固有的弊端，如实时性不够、带宽不足、能耗较大、缺乏移动性等，其关键技术已经不能高效地处理边缘设备所产生的海量数据及计算任务。因此，边缘计算作为一种新的计算模式应运而生，通过将计算能力从云数据中心扩展至网络边缘，减少了互联网数据量传输，从而降低时延，节省带宽，同时提升系统整体的可用性和可扩展性。 [0003] 许多计算工作由远程云端转移到了边缘服务器处理，特别是时延敏感型任务，该类任务通常需要很快的响应速度。由于边缘服务器的存储资源和计算能力有限，那么就需要高效的任务调度算法以保证边缘设备产生的任务在合适的地方以合理的顺序执行。当前常见的任务调度算法如先来先服务调度算法，按照任务到来的顺序执行任务，没有考虑任务的优先级别致使时延敏感型任务不能得到及时处理；最短作业优先算法优先考虑完成时间最短的任务，在大型任务的数量超过小型任务的情况下，该算法性能开始下降。而且这些基本的任务调度算法在复杂的“端‑边‑云”计算模型中不再适用。一些基于端边云协同的任务调度算法通过协作将终端任务卸载到边缘计算节点，允许资源受限的边缘云将部分或全部任务卸载到远程云以实现资源协同共享，该类技术主要关注边缘云到远程云的卸载策略，而忽视了边缘云系统中众多服务器的资源利用率和负载均衡。相关的研究还提出一种利用数据挖掘来调度物联网任务的方法，使用改进的Apriori关联规则算法来对任务进行分类，然后应用一种名为TSFC(雾计算中的任务调度)的新算法来执行调度。这种方法完全是基于时间的，但是忽略了网络和雾节点资源的可用性。 [0004] 通过上述分析，现有技术存在的问题及缺陷为： [0005] (1)现有技术中忽视了边缘云系统中服务器的负载均衡，整体资源利用率不高。 [0006] (2)在任务调度算法中没有综合考虑服务器网络资源、计算资源，存储资源以及任务完成截止时间、整体服务质量等因素，大多数技术只考虑部分影响因素导致不能达到最优的调度结果。 [0007] 解决以上问题及缺陷的难度为：在边缘云和远程云中心协同作业的系统架构中，终端计算任务调度的影响因素很多，诸如计算资源、存储资源、网络状况等，将这些影响因素统筹考虑，作为调度方法的重要参数，然后建立合理的调度模型达到最优的调度效果，使计算任务高效完成，边缘云负载均衡，具备很大的难度。 [0008] 解决以上问题及缺陷的意义为：随着时延敏感型服务的需求不断增多，边缘云上的节点和资源将会持续增加，将终端设备产生的任务合理地分配到边缘服务器或云中心显得尤为重要，不仅可以提高云中心和边缘云整体资源利用率，对服务质量的提升也有很大帮助。本发明创新地提出一种边云协同任务调度方法，实现对实时任务的在线调度，保证边缘云服务器的负载均衡，并且确保时延敏感型任务的按时处理完成。发明内容 [0009] 针对现有技术存在的问题，本发明提供了一种基于截止时间感知的边云协同任务调度方法及系统。本发明提出了一种新的边云协同计算模型架构，并在该基础上提出一种于截止时间感知的边云协同任务调度方法，该算法可以高效地对终端任务在线调度，保证边缘云系统负载均衡，提高整体边云架构的资源利用率。 [0010] 本发明是这样实现的，一种基于截止时间感知的边云协同任务调度方法，所述基于截止时间感知的边云协同任务调度方法，包括： [0011] 步骤一，终端设备数据发送至统一接入模块，接入模块对异构数据统一处理，消除数据的差异性，对任务数据进行标识，便于后续计算任务的调度； [0012] 步骤二，对任务预分类，分别发送至不同目的地，根据先验经验对任务进行的预分类，加快了任务处理的效率，减少了任务调度中心的压力； [0013] 步骤三，任务调度中心提取任务类型和任务截止时间，查询安装了对应服务的服务器集合Stargetl，保证任务被准确地调度到能够执行处理的服务节点； [0014] 步骤四，将任务拟分配至Starget1中的服务器，计算时延是否满足截止时间，将任务分配至满足条件的服务器，通过对传输时延、等待时延以及计算时间的预估，确保了任务被调度到能满满足截止时间的服务器； [0015] 步骤五，任务到达目标服务器，生成新的任务执行队列，任务在此队列等待执行可最终在满足截止时间要求的情况下最快完成。 [0016] 进一步，所述步骤二，具体过程为：根据终端数据类型和业务特性，将终端设备产生的任务预分类，在统一接入模块将计算开销大且时延不敏感型任务发送到远程云中心处理，其余任务发送到任务调度中心。 [0017] 进一步，所述步骤三中，任务调度中心对接收到的任务数据处理，提取出任务类型及任务完成截止时间等关键信息，根据任务类型判断处理该任务所需的服务，然后从服务注册表中查询安装了该服务的边缘服务器，得到满足条件的服务器集合Starget1。 [0018] 进一步，所述将任务拟分配至得到的Starget1中的每台服务器，计算任务传输时延、计算时延和分配该任务造成其它任务增加的等待时间，将满足任务截至时间的服务器集合记为Starget2； [0019] 其中，传输时延根据任务数据量的大小和任务调度中心到目标服务器的实时网络状况计算，计算时延包括等待时延和执行时间；传输时延加上计算时延小于任务截止时间为满足任务截至时间要求。 [0020] 进一步，所述如果得到的Starget2为空，即没有能够满足该任务截止时间的边缘服务器，则丢弃该任务并发出通知； [0021] 如果Starget2中只有一个满足条件的服务器，则将任务分配至该服务器处理； [0022] 如果Starget2中有多个满足条件的服务器，则选择分配该任务造成其它任务增加等待时间最短的服务器。 [0023] 进一步，所述任务到达得到的目标服务器starget，执行单服务器中的任务调度算法： [0024] 如果starget中没有其他任务等待处理，则直接处理该任务；如果starget中有任务等待队列，首先将任务拟放置在队列尾部，所有前置任务的执行时间即为该任务当前位置的等待时延，判断等待时延和该任务的执行时间之和是否满足任务截止时间，如果满足，则任务在队尾等待执行； [0025] 如果超过截止时间，则将该任务依次往前移动，计算该任务的插入对其他任务等待时延的影响，如果造成其他任务超时，则丢弃该任务，即服务器不能在规定截止时间内完成该任务； [0026] 如果没有造成其他任务超时，计算当前位置该任务等待时间，并判断是否满足截止时间，如果满足，则将该任务插入当前位置生成新的任务执行队列；其中，新到达任务的插入会造成其他任务执行顺序延后进而等待时间增加。 [0027] 进一步，所述任务执行时间的计算步骤如下： [0028] 服务器记录最近时间t内每次执行某类任务的数据量大小和执行时间，由数据量除以执行时间计算出最近处理该任务的单位执行时间； [0029] 任务数据量大小除以最近该任务单位执行时间计算出任务执行时间。 [0030] 进一步，所述服务注册表的创建和更新步骤如下： [0031] 远程云中心创建并维护服务注册表，该注册表主要记录每个边缘服务器上当前已安装的服务列表，远程云被标识安装了所有服务的边缘服务器； [0032] 每当边缘服务器有安装或者卸载服务的操作，该操作会被更新到远程云中心的服务注册表； [0033] 远程云中心的服务注册表发生更新后，会自动同步到任务调度中心的服务注册表。 [0034] 本发明的另一目的在于提供一种实施所述边云协同任务调度方法的边云协同任务调度系统，所述边云协同任务调度系统，包括： [0035] 统一接入模块，对终端设备产生的计算任务数据统一接收并预分类处理； [0036] 任务调度中心，接收提取任务关键信息，保存服务器相关状态信息，包括实时网络通道状况，服务器所安装服务等； [0037] 边缘服务器集群和远程云，确定任务执行顺序并处理。 [0038] 结合上述的所有技术方案，本发明所具备的优点及积极效果为：对于传统的“端‑边‑云”计算模型进行优化，拓展边缘云中服务器的协同能力，提出一种基于截止时间感知的边云协同任务调度方法，由统一接入模块接收终端设备产生的任务数据，对任务预分类后发送到远程云中心或任务调度中心，任务调度中心主要基于任务截止时间，综合考虑服务器网络状况，计算资源等因素，对任务进行在线调度，保证边缘云系统负载均衡，提高整体边云架构的资源利用率。附图说明 [0039] 为了更清楚地说明本申请实施例的技术方案，下面将对本申请实施例中所需要使用的附图做简单的介绍，显而易见地，下面所描述的附图仅仅是本申请的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下还可以根据这些附图获得其他的附图。 [0040] 图1是本发明实施例提供的边云协同任务调度方法流程图。 [0041] 图2是本发明实施例提供的边云协同计算模型架构图。 [0042] 图3是本发明实施例提供的“端‑边‑云”计算模型架构图。 [0043] 图4是本发明实施例提供的单服务器节点中的任务调度方法流程图。具体实施方式 [0044] 为了使本发明的目的、技术方案及优点更加清楚明白，以下结合实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅仅用以解释本发明，并不用于限定本发明。 [0045] 针对现有技术存在的问题，本发明提供了一种基于截止时间感知的边云协同任务调度方法及系统，下面结合附图对本发明作详细的描述。 [0046] 如图1所示，本发明实施例提供的基于截止时间感知的边云协同任务调度方法，包括： [0047] S101：终端设备数据发送至统一接入模块。 [0048] S102：对任务预分类，分别发送至不同目的地。 [0049] S103：任务调度中心提取任务类型和任务截止时间，查询安装了对应服务的服务器集合Stargetl。 [0050] S104：将任务拟分配至Starget1中的服务器，计算时延是否满足截止时间，将任务分配给至满足条件的服务器。 [0051] S105：任务到达目标服务器，生成新的任务执行队列。 [0052] 本发明提供的基于截止时间感知的边云协同任务调度方法业内的普通技术人员还可以采用其他的步骤实施，图1的本发明提供的基于截止时间感知的边云协同任务调度方法仅仅是一个具体实施例而已。 [0053] 本发明实施例提供的S102，具体过程为：根据终端数据类型和业务特性，将终端设备产生的任务预分类，在统一接入模块将计算开销大且时延不敏感型任务发送到远程云中心处理，其余任务发送到任务调度中心。 [0054] 本发明实施例提供的S103，任务调度中心对接收到的任务数据处理，提取出任务类型及任务完成截止时间等关键信息，根据任务类型判断处理该任务所需的服务，然后从服务注册表中查询安装了该服务的边缘服务器，得到满足条件的服务器集合Starget1。 [0055] 将任务拟分配至得到的Starget1中的每台服务器，计算任务传输时延、计算时延和分配该任务造成其它任务增加的等待时间，将满足任务截至时间的服务器集合记为Starget2。其中，传输时延根据任务数据量的大小和任务调度中心到目标服务器的实时网络状况计算，计算时延包括等待时延和执行时间。传输时延加上计算时延小于任务截止时间为满足任务截至时间要求。 [0056] 如果得到的Starget2为空，即没有能够满足该任务截止时间的边缘服务器，则丢弃该任务并发出通知；如果Starget2中只有一个满足条件的服务器，则将任务分配至该服务器处理；如果Starget2中有多个满足条件的服务器，则选择分配该任务造成其它任务增加等待时间最短的服务器。 [0057] 任务到达得到的目标服务器Starget，执行单服务器中的任务调度算法：如果Starget中没有其他任务等待处理，则直接处理该任务；如果Starget中有任务等待队列，首先将任务拟放置在队列尾部，所有前置任务的执行时间即为该任务当前位置的等待时延，判断等待时延和该任务的执行时间之和是否满足任务截止时间，如果满足，则任务在队尾等待执行；如果超过截止时间，则将该任务依次往前移动，计算该任务的插入对其他任务等待时延的影响，如果造成其他任务超时，则丢弃该任务，即服务器不能在规定截止时间内完成该任务；如果没有造成其他任务超时，计算当前位置该任务等待时间，并判断是否满足截止时间，如果满足，则将该任务插入当前位置生成新的任务执行队列。其中，新到达任务的插入会造成其他任务执行顺序延后进而等待时间增加。 [0058] 所述服务注册表的创建和更新步骤如下： [0059] 远程云中心创建并维护服务注册表，该注册表主要记录每个边缘服务器上当前已安装的服务列表，特殊的，远程云被标识安装了所有服务的边缘服务器。 [0060] 每当边缘服务器有安装或者卸载服务的操作，该操作会被更新到远程云中心的服务注册表。 [0061] 远程云中心的服务注册表发生更新后，会自动同步到任务调度中心的服务注册表。 [0062] 所述任务执行时间的计算步骤如下： [0063] 服务器记录最近时间t内每次执行某类任务的数据量大小和执行时间，由数据量除以执行时间计算出最近处理该任务的单位执行时间； [0064] 任务数据量大小除以最近该任务单位执行时间计算出任务执行时间。 [0065] 本发明实施例提供的边云协同任务调度系统包括： [0066] 统一接入模块，对终端设备产生的计算任务数据统一接收并预分类处理； [0067] 任务调度中心，接收提取任务关键信息，保存服务器相关状态信息，包括实时网络通道状况，服务器所安装服务等； [0068] 边缘服务器集群和远程云，确定任务执行顺序并处理。 [0069] 下面结合具体实施例对本发明的技术方案作进一步的描述。 [0070] 本发明是这样实现的，一种基于截止时间感知的边云协同任务调度方法，所述基于截止时间感知的边云协同任务调度方法包括以下步骤： [0071] 步骤一，在传统“端‑边‑云”计算模型基础上扩展边缘服务器之间的协同能力，在边缘云中设置统一接入模块和任务调度中心，设计一种新的边云协同计算模型，如图2所示。 [0072] 步骤二，终端设备产生的数据和计算任务发送至统一接入模块。 [0073] 步骤三，根据终端数据类型和业务特性，将终端设备产生的任务预分类，在统一接入模块将计算开销大且时延不敏感型任务发送到远程云中心处理，其余任务发送到任务调度中心。 [0074] 表1任务预分类 [0075] [0076] [0077] 步骤四，任务调度中心对接收到的任务数据处理，提取出任务类型及任务完成截止时间等关键信息，根据任务类型判断处理该任务所需的服务，然后从服务注册表中查询安装了该服务的边缘服务器，得到满足条件的服务器集合Starget1。 [0078] 步骤五，将任务拟分配至步骤四得到的Starget1中的每台服务器，计算任务传输时延、计算时延和分配该任务造成其它任务增加的等待时间，将满足任务截至时间的服务器集合记为Starget2。其中，传输时延根据任务数据量的大小和任务调度中心到目标服务器的实时网络状况计算，计算时延包括等待时延和执行时间。传输时延加上计算时延小于任务截止时间为满足任务截至时间要求。 [0079] 步骤六，如果步骤五得到的Starget2为空，即没有能够满足该任务截止时间的边缘服务器，则丢弃该任务并发出通知；如果Starget2中只有一个满足条件的服务器，则将任务分配至该服务器处理；如果Starget2中有多个满足条件的服务器，则选择分配该任务造成其它任务增加等待时间最短的服务器。 [0080] 步骤七，任务到达步骤六得到的目标服务器Starget，执行单服务器中的任务调度算法：如果starget中没有其他任务等待处理，则直接处理该任务；如果starget中有任务等待队列，首先将任务拟放置在队列尾部，所有前置任务的执行时间即为该任务当前位置的等待时延，判断等待时延和该任务的执行时间之和是否满足任务截止时间，如果满足，则任务在队尾等待执行；如果超过截止时间，则将该任务依次往前移动，计算该任务的插入对其他任务等待时延的影响，如果造成其他任务超时，则丢弃该任务，即服务器不能在规定截止时间内完成该任务；如果没有造成其他任务超时，计算当前位置该任务等待时间，并判断是否满足截止时间，如果满足，则将该任务插入当前位置生成新的任务执行队列。其中，新到达任务的插入会造成其他任务执行顺序延后进而等待时间增加。 [0081] 所述服务注册表的创建和更新步骤如下： [0082] 远程云中心创建并维护服务注册表，该注册表主要记录每个边缘服务器上当前已安装的服务列表，特殊的，远程云被标识安装了所有服务的边缘服务器。 [0083] 每当边缘服务器有安装或者卸载服务的操作，该操作会被更新到远程云中心的服务注册表； [0084] 远程云中心的服务注册表发生更新后，会自动同步到任务调度中心的服务注册表。 [0085] 所述任务执行时间的计算步骤如下： [0086] 服务器记录最近时间t内每次执行某类任务的数据量大小和执行时间，由数据量除以执行时间计算出最近处理该任务的单位执行时间。 [0087] 任务数据量大小除以最近该任务单位执行时间计算出任务执行时间。 [0088] 本发明实施例提供的边云协同任务调度系统包括： [0089] 统一接入模块，对终端设备产生的计算任务数据统一接收并预分类处理。 [0090] 任务调度中心，接收提取任务关键信息，保存服务器相关状态信息，包括实时网络通道状况，服务器所安装服务等。 [0091] 边缘服务器集群和远程云，确定任务执行顺序并处理。 [0092] 应当注意，本发明的实施方式可以通过硬件、软件或者软件和硬件的结合来实现。硬件部分可以利用专用逻辑来实现；软件部分可以存储在存储器中，由适当的指令执行系统，例如微处理器或者专用设计硬件来执行。本领域的普通技术人员可以理解上述的设备和方法可以使用计算机可执行指令和/或包含在处理器控制代码中来实现，例如在诸如磁盘、CD或DVD‑ROM的载体介质、诸如只读存储器(固件)的可编程的存储器或者诸如光学或电子信号载体的数据载体上提供了这样的代码。本发明的设备及其模块可以由诸如超大规模集成电路或门阵列、诸如逻辑芯片、晶体管等的半导体、或者诸如现场可编程门阵列、可编程逻辑设备等的可编程硬件设备的硬件电路实现，也可以用由各种类型的处理器执行的软件实现，也可以由上述硬件电路和软件的结合例如固件来实现。 [0093] 以上所述，仅为本发明的具体实施方式，但本发明的保护范围并不局限于此，任何熟悉本技术领域的技术人员在本发明揭露的技术范围内，凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等，都应涵盖在本发明的保护范围之内。