一种基于优先级的分层边缘计算卸载方法
技术领域
本发明属计算机边缘计算技术领域，具体涉及了一种基于优先级的分层边缘计算卸载方法。
背景技术
随着5G通信技术和物联网的发展，大量的移动设备及其服务导致了移动数据流量的爆炸性增长，越来越多的移动应用对实时通信和密集计算提出了严格的要求。在传统的物联网网络中，终端设备的数据通常传输到云服务器进行处理，然而，海量的物联网设备数据给云服务器和无线链路带来了沉重的负担，系统性能将受到影响而急剧退化。为了改进用户的体验质量，尤其是减少端到端时延，移动边缘计算(Mobile Edge Computing,MEC)技术的出现得到了广泛关注。通过在蜂窝基站或者本地无线接入点上实现MEC服务器，它将计算任务的处理推向与本地用户接近的网络边缘，可以为物联网应用程序提供更高的服务质量(Quality of Service,QoS)，满足5G网络的关键端到端时延要求。
一方面，物联网的普及给人们的生活带来了极大的便利，它成为人与物、物与物之间沟通的桥梁。物联网与边缘计算的有机结合将会推动许多领域的发展，特别是智能家居、智能健康等。另一方面，物联网的许多应用也将面临更多的挑战，如时延敏感性、能源有效性和可靠性等问题。物联网中对时延要求最高的应用是与人体安全及健康密切相关的某些场景(如电子医疗用户突发疾病或不慎跌倒、某些灾害前的及时预警或者安防领域中出现危险状况等)。在这些场景下，降低用户的时延和区分事件的紧急程度成为一个关键问题。
近年来，对边缘计算的研究主要集中在卸载决策和资源管理。移动用户可以通过选择自己的计算卸载策略来实现不同的目标。在具有大量卸载用户的MEC系统中，有限的通信和计算资源对任务执行时延有很大的影响，因此有效的资源分配成为实现高效计算卸载的关键。一种典型的方案是将卸载决策与资源分配结合起来，构造出非线性整数规划(MINLP)问题。Tran等[Tran,Tuyen X.,and Dario Pompili."Joint task offloading andresource allocation for multi-server mobile-edge computing networks."IEEETransactions on Vehicular Technology 68.1(2018):856-868.]将原始MINLP问题分解为具有固定任务卸载决策的资源分配(RA)问题以及与RA问题对应的最优值函数的任务卸载(TO)问题。另一种方案是仅考虑无线与计算资源分配的优化。Ren等[Ren,Jinke,et al."Latency optimization for resource allocation in mobile-edge computationoffloading."IEEE Transactions on Wireless Communications 17.8(2018):5506-5519.]研究了局部压缩、边缘云压缩和部分压缩卸载三种模型，提出了一种最优的联合通信计算资源分配算法。由于有限且共享的资源导致用户的非合作竞争，有许多工作采取了博弈论的解决方案。Gu等[Gu,Yunan,et al."Joint radio and computational resourceallocation in IoT fog computing."IEEE Transactions on Vehicular Technology67.8(2018):7475-7484.]使用匹配的学生项目分配(SPA)博弈方法为制定的联合资源分配问题提供分布式解决方案。
除了资源分配，有效的任务调度也是减少系统总体时延的关键。Mukherjee等[Mukherjee,Mithun,et al."Deadline-aware Fair Scheduling for Offloaded Tasksin Fog Computing with Inter-fog Dependency."IEEE Communications Letters(2019).]利用队列长度上的Lyapunov漂移加上惩罚函数来调度队列中的任务，随后调度策略决定要卸载到卸载的雾节点的任务量。Madej等[Madej,Arkadiusz,et al."Priority-based Fair Scheduling in Edge Computing."arXiv preprint arXiv:2001.09070(2020).]比较了四种调度技术，分别是先到先得策略，以及客户公平、优先级公平和考虑到客户和工作两者优先级公平性的混合策略。
发明内容
发明目的：为了解决上述技术问题，本发明提供了一种基于优先级的分层边缘计算卸载方法，针对发生紧急情况的应用场景，可以向用户返回即时响应。紧急程度越高的用户将被分配越高的优先级，经历的时延更少。通过将物联网与边缘计算技术结合，可以为用户提供更高的QoS。
技术方案：本发明提出一种基于优先级的分层边缘计算卸载方法，该方法包括以下步骤：
步骤1：构建分层边缘计算卸载系统的架构，包括本地层、边缘层和雾层；其中,本地层包括一组用户设备，边缘层包括一组边缘节点，雾层包括一个服务器；边缘节点对任务执行边缘计算，服务器对任务执行雾计算；
步骤2：描述从本地设备产生的用户任务的特征参数，给出任务的初始要求元组；在任务经过边缘计算后，发往基站之前，更新任务的要求元组，并附加上无线资源分配比例和紧急优先级参数；
步骤3：为分层边缘计算卸载系统建模，包括队列模型、通信模型和计算模型；通信模型描述无线通信资源分配的关系，计算模型描述边缘节点和服务器中计算资源分配的关系，通过建立通信模型和计算模型构造出任务通信与计算时延的表达式；
步骤4：根据步骤3所得的时延表达式，对分层边缘计算卸载系统进行联合无线与计算资源分配优化；先构造优化问题，再分别求出无线资源分配比例与计算资源分配值的最优解，以最小化时延。
进一步的，服务器中的任务调度队列使用动态优先级的任务调度算法进行任务调度。
进一步的，步骤1中，构建分层边缘计算卸载系统的总体架构，系统架构包括一个服务器，一组边缘节点
进一步的，步骤2中，描述用户任务的特征参数和要求元组，从第i个边缘节点的第k个设备产生的任务记作τi,k，任务τi,k的初始要求表示为元组{Ci,k,Di,k,DLi,k}，其中，Ci,k表示该任务边缘计算所需的CPU循环周期数，Di,k表示任务的数据量大小，DLi,k表示任务完成截止时刻，任务应在该时刻前完成；边缘节点对任务τi,k进行快速计算后，任务被区分出优先级，处理后元组变为{C′i,k,D′i,k,DLi,k,p,αi,k}，其中，C′i,k为任务在服务器上进行计算所需要的CPU循环周期数，D′i,k为任务进行服务器计算所需的数据量，p表示按照紧急程度区分的三个优先级，αi,k为基站分配给该任务的无线资源比例。
进一步的，步骤3中，为分层边缘计算卸载系统建模，包括队列模型、通信模型和计算模型，构造通信与计算时延表达式，具体包括以下步骤：
(1)队列模型，队列模型包括边缘队列qedge、无线队列qtran和雾计算队列qfog，边缘队列和无线队列位于边缘节点中，而雾计算队列位于服务器中，整个系统中共有N个qedge队列和N个qtran队列，任务在到达边缘节点之前，还没有区分出优先级，qedge是普通的M/M/1队列，qtran是非抢占式优先级M/M/1队列，在雾计算队列中，使用动态优先级的任务调度算法进行任务调度；
(2)通信模型，该模型包含一个服务器、一个基站和N个边缘节点，基站与服务器相连，边缘节点通过基站将任务发送到服务器，基站将无线资源正交地分配给系统内所有用户设备的任务，总频谱带宽为B，将任务τi,k的上行传输速率记作Ri,k，其表示为：
其中，Pi是边缘节点i的发射功率，hi,B表示上行链路的信道衰落系数，di,B是基站和边缘节点i之间的距离，r表示路径损失指数，σ2表示噪声功率，αi,k表示分配给第i个边缘节点的第k个设备的上行频谱资源比例，αi,k∈[0,1]且
任务τi,k的通信时延为：
(3)计算模型，由于系统有两层需要计算的步骤，将计算模型分为两部分，第一部分是边缘节点上的计算资源分配，假设每个服务器相连的所有边缘节点的计算资源都相等，记作fn，用户设备k将任务卸载到对应的边缘节点上进行计算，将边缘节点分配给设备k的任务的计算能力记作
第二部分是服务器上的计算资源分配，边缘节点i将来自设备k的任务卸载到服务器上，将fs表示为服务器的最大计算能力，
计算时延表示为边缘计算与雾计算时延之和：
进一步的，步骤4中，根据步骤3构建的通信与计算模型，对系统进行联合无线与计算资源分配优化，以最小化时延，具体包括以下步骤：
步骤1：推导出任务通信时延与计算时延的表达式，已由公式(2)和(3)分别给出；
步骤2：构造资源分配优化问题，系统的时延最小化资源分配优化问题表述为：
其中，C1是无线资源分配比例的优化约束条件，保证分配给所有设备的无线资源总和不会超过系统最大带宽，并保证无线资源分配比例的非负性，C2和C3分别是边缘计算和服务器计算的优化约束条件，保证分配给所有设备的计算资源总和不会超过最大计算能力；
步骤3：将联合资源分配优化问题分解成两个子问题，分别是无线资源分配和计算资源分配；
无线资源优化问题表示为：
计算资源分配问题表示为
步骤4：求解无线资源分配问题，令
运用Karush-Kuhn-Tucker条件，解得无线资源分配比例的最优解为：
步骤5：求解计算资源分配问题，定义一个拉格朗日函数，它表示为：
边缘节点上的计算资源分配和服务器上的计算资源分配不相关，因此可将计算资源分配问题分为两部分分别求出最优解
运用Karush-Kuhn-Tucker条件解得边缘节点资源分配的最优解为：
以及服务器上资源分配的最优解为：
进一步的，步骤5中，根据步骤3构建的队列模型，在服务器的雾计算队列qfog中使用动态优先级调度算法，具体包括以下步骤：
步骤1：设置三个缓冲区，分别为高优先级class1、中优先级class2和低优先级class3，任务进入对应优先级的缓冲区中；
步骤2：依次执行class1、class2和class3中的任务，每个缓冲区各自调度；
步骤3：为该算法设置紧急度指标，综合了任务的可等待时间和任务执行时间，可等待时间越少、剩余执行时间越短的任务紧急度越高，将越先被执行，将紧急度记作e，任务可等待的时间记作x，任务剩余的执行时间记作y，任务的紧急度表示为：
其中，w1和w2分别为任务超时和未超时两种情况下x的权重值；
步骤4：在每个缓冲区中采用时间片轮转调度算法，每执行完一个时间片，如果该任务仍未执行完，重新回到该类别等待调度，再计算该类别里剩余所有任务的紧急度，取紧急度最大的任务执行，为任务设定一个age标志，一个任务每执行一次，标志将加一，下一次将为它分配更长的预设时间片，当任务标志达到设定的最大age，系统将把它剩下的部分执行完；
步骤5：将紧急度与本系统的参数联系起来，任务τi,k在用户设备中产生时就有一个截止时刻要求的属性DLi,k，即任务必须在该时间前完成，那么任务在系统中还可等待的时间x为DLi,k-CURi,k，CURi,k表示任务的当前时间，该时间可由系统得知；
由式(11)可得服务器分配给任务τi,k的计算资源
其中，age＝0表示任务是第一次执行，age>0表示由于任务已经执行过一部分了，
有益技术效果：与现有技术相比，本发明的技术方案具有以下有益技术效果：
1.本发明提出了基于优先级的分层移动边缘计算卸载方案，根据紧急程度区分用户的优先级，降低紧急任务所经历的时延，提高了系统的安全性。
2.本发明针对时延最小化问题提出了联合无线与计算资源分配方案，有效地降低系统总体时延，可以为用户提供QoS更高的服务。
3.本发明提出了基于动态优先级的任务调度算法，在服务器中任务密集的情况下，降低系统的总体时延以减少任务阻塞，并且保证最高优先级任务时延最低，提供系统的鲁棒性。
附图说明
图1示出了本发明的方案系统总体架构图；
图2示出了本发明的任务执行流程图；
图3示出了本发明的系统模型图；
图4示出了本发明的动态优先级调度算法(DPTSA)总体流程图；
图5示出了本发明的动态优先级调度算法(DPTSA)中每个缓冲区的任务调度流程图。
具体实施方式
以下将结合具体实施例对本发明提供的技术方案进行详细说明，应理解下述具体实施方式仅用于说明本发明而不用于限制本发明的范围。
本发明提出一种基于紧急优先级的分层边缘计算卸载框架。距离用户设备较近而计算资源较少的边缘节点处理简单任务，以快速返回警告信息，距离用户设备较远而计算资源较多的服务器处理复杂任务，最终返回精确结果。由于设备在有限资源上的竞争会增加用户所经历的时延，文中提出了基于服务紧急优先级的资源分配和任务调度优化方案，以最小化系统总时延，同时保证高优先级服务所经历的时延最小。首先，分别构造无线资源分配和计算资源的最小化时延凸优化问题表达式，再利用KKT条件对其求解得到资源分配最优解。然后，为了保证高优先级任务在非常密集的情况下时延依然最小，设计了在服务器上的动态优先级任务调度算法(DPTSA)。具体地说，本发明包括以下步骤：
1)首先构建本发明的系统总体架构，如图1所示。系统包括一个服务器，一组边缘节点
2)描述从本地设备产生的用户任务的特征参数。从第i个边缘节点的第k个设备产生的任务记作τi,k，任务τi,k的初始要求表示为元组{Ci,k,Di,k,DLi,k}，其中，Ci,k表示该任务边缘计算所需的CPU循环周期数，Di,k表示任务的数据量大小，DLi,k表示任务完成截止时刻，任务应在该时刻前完成；
3)明确本系统任务的执行流程，如图2所示。任务τi,k产生后，将进入边缘节点的边缘队列qedge中，接着边缘节点将对该任务进行快速处理，此时任务被区分出优先级，它的要求元组变为{C′i,k,D′i,k,DLi,k,p,αi,k}，其中，C′i,k为任务在服务器上进行精确计算所需要的CPU循环周期数，D′i,k为任务进行雾计算所需的数据量，p表示按照紧急程度区分的三个优先级，αi,k为基站分配给该任务的无线资源比例，接着任务将进行无线通信传输，任务τi,k经过边缘快速计算后，进入无线队列qtran等待，将按照无线资源比例αi,k被分配无线资源发往基站，任务再通过基站进入服务器，进行复杂处理，最后向本地用户返回精确的数据分析结果；
4)为分层边缘计算卸载系统建模，构造时延表达式。系统模型包括队列模型、通信模型和计算模型，如图3所示。具体描述如下：
(1)队列模型。队列模型包括边缘队列qedge、无线队列qtran和雾计算队列qfog，边缘队列和无线队列位于边缘节点中，而雾计算队列位于服务器中，整个系统中共有N个qedge队列和N个qtran队列。任务在到达边缘节点之前，还没有区分出优先级，qedge是普通的M/M/1队列(单服务器单队列排队模型)。qtran是非抢占式优先级M/M/1队列。
由于整个系统的任务都会进入服务器处理，在任务密度较大时容易造成雾计算队列qfog阻塞，使用单纯的非抢占式优先级队列无法满足要求，因此使用本发明提出的动态优先级任务调度算法(DPTSA)对雾计算队列qfog进行任务调度。
(2)通信模型。该模型包含一个服务器、一个基站和N个边缘节点，基站与服务器相连，边缘节点通过基站将任务发送到服务器，基站将无线资源正交地分配给系统内所有用户设备的任务，总频谱带宽为B，将任务τi,k的上行传输速率记作Ri,k，它表示为：
其中，Pi是边缘节点i的发射功率，hi,B表示上行链路的信道衰落系数，di,B是基站和边缘节点i之间的距离，r表示路径损失指数，σ2表示噪声功率，αi,k表示分配给第i个边缘节点的第k个设备的上行频谱资源比例，αi,k∈[0,1]且
任务τi,k的通信时延为：
(3)计算模型。由于系统有两层需要计算的步骤，将计算模型分为两部分。第一部分是边缘节点上的计算资源分配。假设每个服务器相连的所有边缘节点的计算资源都相等，记作fn，用户设备k将任务卸载到对应的边缘节点上进行计算，将边缘节点分配给设备k的任务的计算能力记作
第二部分是服务器上的计算资源分配。边缘节点i将来自设备k的任务卸载到服务器上，将fs表示为服务器的最大计算能力，
计算时延表示为边缘计算与雾计算时延之和：
5)由于系统总体资源有限，可能导致用户设备竞争而增加时延的问题。针对该问题，根据已经建好的通信模型与计算模型，对系统进行联合无线与计算资源分配优化，以最小化时延。具体包括以下步骤：
步骤1：推导出任务通信时延与计算时延的表达式，已由公式(2)和(3)分别给出。
步骤2：构造资源分配优化问题。系统的时延最小化资源分配优化问题表述为：
其中，C1是无线资源分配比例的优化约束条件，它保证分配给所有设备的无线资源总和不会超过系统最大带宽，并保证无线资源分配比例的非负性，C2和C3分别是边缘计算和雾计算的优化约束条件，它们保证分配给所有设备的计算资源总和不会超过最大计算能力。
步骤3：本系统中的无线资源和计算资源分配并没有直接的联系，于是将该联合资源分配优化问题分解成两个子问题，分别是无线资源分配(Radio Resource Allocation,RRA)和计算资源分配(Computing Resource Allocation,CRA)。
无线资源优化问题表示为：
计算资源分配问题表示为
步骤4：求解RRA问题。RRA问题是一个凸优化问题。为了解决这个凸问题，令
运用Karush-Kuhn-Tucker(KKT)条件，解得无线资源分配比例的最优解为：
步骤5：求解CRA问题。CRA问题是一个凸优化问题，为了求解该问题，定义一个拉格朗日函数，它表示为：
边缘节点上的计算资源分配和服务器上的计算资源分配不相关，因此可将CRA问题分为两部分分别求出最优解
运用Karush-Kuhn-Tucker条件条件解得边缘节点资源分配的最优解为：
以及服务器上资源分配的最优解为：
6)在服务器的雾计算队列qfog中，如果系统任务密度过大，就会造成任务阻塞。针对该问题，提出了一种基于动态优先级的任务调度算法(DPTSA)。该算法既考虑任务紧急程度又考虑任务的截止时间，保证优先级别更高的任务先得到运行，改进了调度性能。DPTSA总体流程如图4所示。具体包括以下步骤：
步骤1：设置三个缓冲区，分别为高优先级class1、中优先级class2和低优先级class3，任务进入对应优先级的缓冲区中；
步骤2：依次执行class1、class2和class3中的任务，每个缓冲区各自调度；
步骤3：为该算法设置紧急度(Emergency Degree)指标，它综合了任务的可等待时间和任务执行时间，可等待时间越少、剩余执行时间越短的任务紧急度越高，将越先被执行。随着等待时间的增加，所有任务的紧急度是动态变化的。将紧急度记作e，任务可等待的时间记作x，任务剩余的执行时间记作y，任务的紧急度表示为：
其中，w1和w2分别为任务超时和未超时两种情况下x的权重值。
步骤4：在每个缓冲区中，任务调度流程如图5所示。在每个缓冲区中采用时间片轮转调度算法，每执行完一个时间片，如果该任务仍未执行完，重新回到该类别等待调度，再计算该类别里剩余所有任务的紧急度，取紧急度最大的任务执行，为任务设定一个“age”标志，一个任务每执行一次，它的年龄将加一，下一次将为它分配更长的时间片，当任务达到设定的最大年龄，系统将把它剩下的部分执行完。
步骤5：将紧急度与本系统的参数联系起来。任务τi,k在用户设备中产生时就有一个截止时刻要求的属性DLi,k，即任务必须在该时间前完成。那么任务在系统中还可等待的时间x为DLi,k-CURi,k，CURi,k表示任务的当前时间，可由系统得知。
由式(11)可得服务器分配给任务τi,k的计算资源
其中，age＝0表示任务是第一次执行，age>0表示由于任务已经执行过一部分了，
