CN114610463B 一种基于稳定性理论的边云协同任务调度方法及系统 （广东石油化工学院）

一种基于稳定性理论的边云协同任务调度本发明公开了一种基于稳定性理论的边云2所述边缘服务器接收对应物联网终端上传的任务；所述任务包括第一类表示边缘服务器u中第一队列的负载，I%n(t)表示迁移策略变量，表示任务分割策邻居边缘服务器或云数据中心，以使所述邻居边缘服务器或云数据中心处理已迁移的任所述边缘服务器处理自身接收到的未迁移的任务以及邻居边缘服务器的已迁移的任其中，所述迁移策略为在保证所述任务的延迟要所述边缘服务器设置存放任务的第一队列以及第二队列；所述边缘服务器将接收到的第一类任务顺序放入第一队列的尾部3所述边缘服务器确定任务调度策略，并按照所述任务调度策略从所顺序调度第一类任务进行处理或者从所述第二队列的头部顺序调度第二类任务进行当所述边缘服务器接收到的所述任务为第二类任务时，所述边缘服务器计算第二迁移策所述第二迁移策略%(t)满足：。所述边缘服务器获取第一队列长度以及第二队列采用以下规则根据累积业务权重n确定任务调度策略变量Tm(t)的取值：其中，QW(t)表示边缘服务器u中第一队列的负载，Qut?(t表示边缘服务器u中第二变量Tm(t)=0；变量Tm(t)=1；所述第一队列的头部顺序调度第一类任务进所述第二队列的头部顺序调度第二类任务进6.一种基于稳定性理论的边云协同任务调度系统，任务接收模块，用于边缘服务器接收对应物联网终端上传的任务4迁移模块，用于边缘服务器计算迁移策略，并执行所述迁移其中当所述边缘服务器接收到的所述任务为第一类任务时，所表示边缘服务器u中第一队列的负载，I%n(t)表示迁移策略变量，表示任务分割策任务处理模块，用于边缘服务器处理自身接收到的未迁移其中，所述迁移策略为在保证所述任务延迟要求的前提下所述任务处理模块中，所述边缘服务器处理自身接收到的未迁移的所述边缘服务器设置存放任务的第一队列以及第二队列；所述边缘服务器将接收到的第一类任务顺序放入第一队列的尾部所述边缘服务器确定任务调度策略，并按照所述任务调度策略从所59.一种计算机设备，包括存储器和处理器，所述存储器存被处理器执行时实现权利要求1至5任一项所述边云协同6有随机性，离线优化算法因无法准确描述任务的到达特性而难以做出精确的优化调度决7[0010]所述边缘服务器处理自身接收到的未迁移的任务以及邻居边缘服务器的已迁移[0012]李雅普诺夫稳定性理论是俄国数学家和力学家A.M.李雅普诺夫在1892年所创立选择能使得系统任务负载队列的李雅普诺夫漂移函数加以系统能耗作为惩罚函数最小化[0014]所述边缘服务器处理自身接收到的未迁移的任务以及邻居边缘服务器的已迁移头部顺序调度第一类任务进行处理或者从所述第二队列的头部顺序调度第二类任务进行89第一队列的头部顺序调度第一类任务进行处理或者从所述第二队列的头部顺序调度第二[0032]所述边缘服务器获取第一队列长度QH(e)以及第二队列长度确定所述边缘服务器中第一队列的累积业务权重η:[0038]当所述第一队列长度Q(t)>0且所述第二队列长度时，所述任务调[0039]当所述第二队列长度且所述第一队列长度时，所述任务调头部顺序调度第一类任务进行处理或者从所述第二队列的头部顺序调度第二类任务进行[0062]图4为本发明中边云协同任务调度方法在不同控制参数V下对系统平均延迟和能[0063]图5为本发明中不同任务速率下的不同方法的性能比较实验结果图(其中DGEM代[0064]图6为本发明中不同任务大小下的不同方法的性能比较实验结果图(其中DGEM代[0065]图7为本发明中不同延迟界下的不同方法的性能比较实验结果图(其中DGEM代表边缘子系统的边缘服务器称为该终端的邻居第m个边缘服务器的物联网终端数量，则系统总的物联网终端数量可表示为N=zmexNm,令Nm={1,2,……,NMm}和N={NmImEM}分别表示对应的集合，令表示第m台边缘服务器的计算能力(处理计算任务的速率)，fC表示云数据中心分配给每个任务的计算速率，假设础>f"。缘计算系统的李雅普诺夫漂移函数与惩罚函数[0078]具体的，令QU(t)=(Quf(t),QU⃞"(t),…,QU(t),Qwf"(t),QU(t),……,QU(t))[0082]将每时隙系统能耗E(t)作为惩罚函数加入系统任务负载队列的李雅普诺夫漂移第一类任务进行处理或者从第二队列的头部顺序调度第二队列的头部顺序调度第一类任务进行处理或者从所述第二队列的头部顺序调度第二类任[0102]当第一队列长度Q张(t)>0且第二队列长度Q铝(t)>0时，采用以下规则确定边缘服务器中第一队列的累积业务权重η:Quf(t)表示边缘服务器u中第一队列的负载，表示边缘服务器u中[0107]当第一队列长度Q册(t)>0且第二队列长度时，任务调度策略变量πm[0108]当第二队列长度且第一队列长度QH(t)x0时，任务调度策略变量πm[0115]令Taskm,n(t)表示第m个边缘子系统的第n台物联网终端在时隙t产生的任务，令[0132]上式中，K=Muf云数据中心}表示计算节点集合。(0,1)时，表示任务属于第一类任务，任务分流到边缘服务器k的比重为a，即大小为⃞n(t)smn(t),则分配到另一边缘服务器的大小为(1-⃞n(t))smnn(r)。[0141]当主边缘服务器(边缘服务器m)确定将该任务迁移到云数据中心处理时，该任务将产生从主边缘到云数据中心的传输延迟和在云数据中[0142]令BC表示图1中边缘服务器与云数据中心之间瓶颈链路的带宽，采用加权公平带[0159]当主边缘服务器(边缘服务器m)确定将该任务分割并分配到边缘服务器u、输延迟和任务在这两个边缘服务器的排队延迟和计算延[0160]令BE表示如图1所示的相邻基站链路的带宽，同样采用加权公平带宽调度策略分f(r)表示任务Taskk迁移到边缘服务器u的任务比例，表示边缘服务器u分配给Type-1[0180]其中，表示传输延迟，D""()表示排队延迟，表示计算延""()表示计算能耗。n(e)由(1-26)确定。(e)由(1-27)确定。[0199]类似于第一类任务，当主边缘服务器(边缘服务器m)确定将该任务迁移到云数据[0200]任务传输延迟和在云数据中心的计算延迟模型类似于第一类任务的云计算模[0202]不同于第一类任务，第二类任务在任何的边缘服务器处理都不需要进行任务分mEM,nENm的端到端延迟可统一化表示为mEM,nENm所消耗的能量可统一化表示为[0235]Q"<,UEM,#(1-44)[0238]其中，和础2,m,UEM,nENm,t＝0,...,∞是决策变量。限制条件(1-41)表示第一类任务的端到端延迟不能超过阈值dT1；条件(1-42)是边缘服务器的计算能力[0248](1-45)和(1-46)分别表示该边缘服务器Type-1队列和Type-2队列从任务负载角来表示。李雅普诺夫函数从一个时隙到下一时隙之间的变化被称为李雅普诺夫漂移[0257]令QU(t)=(Qwf(t),QW引(t),.…,QW(t),Qwf"(t),QW(t),……,QU(t))表示系统在时隙t的任务负载队列向量，令L(t)表示任务负载队列的李雅普诺夫函数，定义云协同任务调度方法，优化的迁移策略Imn(t)、第一类任务在边缘计算的任务分割策略着通过与其他算法进行比较来评估所述基于稳定性理论的边云协同任务调度方法在保证第一类任务的严格延迟要求和降低系统能耗等Type-1和Type-2队列任务的调度[0273]首先评估控制参数V的取值对本实施例方法性能的影响。本实施例队列内任务是的平均延迟的变化实际上反映了系统队列长度的变化，可作为衡量系统稳定性的性能指的性能指标。本实施例中边云协同任务调度方法在不同控制参数V下对系统平均延迟和能中边云协同任务调度方法能够在能耗最小化与第一类任务的延迟保障以及平均延迟最小[0277]在图5(a)中，四种算法的第一类任务延迟保证率(实际延迟低于延迟界的任务数子系统的所有物联网终端都只产生第一类任务(每时隙每个物联网终端产生1个第一类任[0278]EnergyMin-greedy算法在第一类任务延迟保证率方面优于Cloud-greedy和Edge-到云数据中心处理，在瓶颈链路资源限制下，任务经历了较长的通信延迟；尽管Edge-法也是以能耗最小化为目标，但由于是在边缘服务器和云数据中心之间进行计算迁移决[0279]本实施例中边云协同任务调度方法的第一类任务延迟保证率明显优于其他三个[0280]正是因为本实施例中边云协同任务调度方法要在保证系统延迟符合要求前提下云协同任务调度方法的能耗并不是最低的，但仍然低于Edge-greedy和EnergyMin-greedy[0285]在其它参数不变情况下，增加第二类任务的任务大小等效于增加系统的业务负降到0，这意味着所有第一类任务的端到端延迟都超过了延迟界。这是因为，在Cloud-[0286]由于Edge-greedy算法只在边缘服务器之间进行计算迁移决策，而且以能耗最小性能。但在第一类任务的严格延迟保证方面，本实施例中边云协同任务调度方法优于边云协同任务调度方法仍能保证第一类任务的延迟保证率高于法能够在系统能耗和延迟之间均衡，其始终能够对第一类任务提供90％以上的延迟保证[0292]尽管Edge-greedy和EnergyMin-greedy算法也能根据延迟界的变化自动调整计算几乎都能保证所有仿真期间产生的任务都能在仿真期间处理完毕，但是，Edge-greedy及EnergyMingreedy算法却不能(如图7(c))所示，进一步验证了本实施例中边云协同任务调[0298]任务处理模块300，用于边缘服务器处理自身接收到的未迁移的任务以及邻居边[0304]将每时隙系统能耗E(t)作为惩罚函数加入系统任务负载队列的李雅普诺夫漂移[0307]任务处理模块300中，边缘服务器处理自身接收到的未迁移的任务以及邻居边缘调度第一类任务进行处理或者从第二队列的头部顺序调度队列的头部顺序调度第一类任务进行处理或者从所述第二队列的头部顺序调度第二类任[0313]当第一队列长度Q(t)>0且第二队列长度时，采用以下规则确定边缘服务器中第一队列的累积业务权重η:[0318]