边缘计算中面向数据流的实时任务调度算法  

Task Offloading Online Algorithm for Data Stream Edge Computing

作　　者：张翀宇 陈彦明 李炜[1] ZHANG Chong-yu;CHEN Yan-ming;LI Wei(School of Computer Science and Technology,Anhui University,Hefei 230601,China)

机构地区：[1]安徽大学计算机科学与技术学院,合肥230601

出　　处：《计算机科学》2022年第7期263-270,共8页Computer Science

基　　金：国家自然科学基金(61802001)。

摘　　要：近年来,随着物联网(Internet of Things,IoT)技术的发展,其应用场景呈爆炸式增长,这类应用一般具有时延敏感性和资源受限性。如何在有限的资源环境下实现任务的实时分配是当前的一个研究热点,而将这些有限的计算资源动态分配给实时任务,一般来说是一个NP-hard的组合优化问题。为解决此问题,设计了一种基于李雅普诺夫优化的实时调度算法,在保持虚拟队列稳定的情况下优化长期平均总能耗和总效用。首先在计算资源和通信资源约束下建立联合总能耗和加权总效用的优化模型,该模型包含两层虚拟缓冲队列,通过端到端(Device-to-Device,D2D)的调度方式进行任务卸载;然后基于李雅普诺夫优化,将长期平均总能耗和总效用的联合优化问题转化为一系列实时优化问题,为此还设计了一种基于贪心的设备匹配算法。数值实验的结果显示,该算法的效果比随机法所能达到的最好情况提升了8.6%,并且在不同连接概率下其效果逼近穷举法。With the development of Internet of Things(IoT)technology,its application scenarios have exploded recently,and such applications are generally delay-sensitive and resource-constrained.It is a focused issue in the way of offloading the real-time tasks under the condition of limited resource.Besides,it is a NP-hard combinatorial optimization problem to allocate limited computational resources for the real-time tasks.To solve this problem,this paper proposes a real-time resource management algorithm based on Lyapunov optimization,aiming at stabilizing the virtual queues while optimizing the total power consumption and total utility.Firstly,the optimization model for the total power consumption and weighted total utility is proposed under the constraint of computation and communication resources.This model contains of two virtual buffer queues,and tasks are unloaded in a device-to-device(D2D)scheduling model.Then,an optimization algorithm is proposed based on Lyapunov optimization to decompose the joint long-term average sum energy consumption and sum utility optimization problem into a series of real-time optimization problems.To solve these problems,a greedy-based matching algorithm is proposed.Experimental results demonstrate that the performance of the proposed algorithm is 8.6%better than the best result of random method and can approximate the exhaustive attack method under different connection degrees.

关 键 词：物联网 计算卸载 李雅普诺夫优化 贪心算法 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]