【作者】 苏茜；

【导师】 张学杰；

【作者基本信息】 云南大学 ， 计算机科学与技术， 2023， 博士

【摘要】 计算迁移是云边协同的关键技术之一,面向具体应用场景和优化指标的迁移策略设计及其算法研究直接影响着计算迁移的效率和效果。在云边协同环境下,现有迁移策略缺乏对云端和边缘的各种约束和限制的充分考虑,异构的多维资源需求、实时的用户体验要求以及动态的应用场景给迁移算法设计带来挑战,对能耗也缺乏从系统整体视角的考量。针对这些问题,本文结合云边协同下的典型应用场景,以系统能耗最小化为优化目标,对计算迁移策略和算法设计展开研究,主要研究内容如下:(1)针对多边缘服务器对多终端用户的覆盖约束问题,本文以基站作为边缘服务器的物联网应用场景为例,基于覆盖半径和能耗的正比例关系,提出一种基站覆盖半径可调的云边协同计算迁移策略。通过建立基站-圆盘结构实现了基站到一系列半径不等的圆盘的映射以及从基站覆盖到圆盘覆盖的问题变换。将问题建模为满足圆盘覆盖要求和任务多维资源需求的整数线性规划后,分别设计了基于贪心策略和原始-对偶方法的计算迁移近似算法。对比实验表明两个算法在总能耗、基站覆盖半径等方面最接近最优解,同时又各具优点,前者执行效率快,后者能有效均衡基站负载及缓解核心网带宽压力。(2)针对云端的带宽瓶颈问题和实时的用户体验需求,本文以边缘处理结果需传输到云中心协同的应用场景为例,提出一种基于云端带宽数据压缩的近实时云边协同计算迁移策略。基于层次云边协同计算迁移架构及对系统能耗的全面考量,将问题形式化描述为一个带云-边多维资源约束和带宽压缩比的整数线性规划模型并证明其为NP-hard问题。然后结合原始-对偶理论和经济学中的边际价格概念设计了一个具有多项式时间复杂度的近实时计算迁移算法,并借助弱对偶性质和文中定义的“价格-资源增量关系”对算法近似比进行推导。对比实验表明该近似算法在降低系统能耗、充分利用边缘资源和平衡云中心负载等方面具有显著优势。(3)针对边缘服务器的能量预算约束问题和随时间动态到达的任务请求,本文以移动设备充当轻量型边缘服务器的场景为例,在时间槽结构上提出一种基于弹性任务窗口的动态云边协同计算迁移和资源分配策略。通过联合优化迁移决策、计算和通信资源分配,将问题建模为带时槽约束、多维资源约束和移动设备能量约束的混合整数非线性规划。鉴于迁移决策与资源分配的强耦合,结合给定窗口长度资源配置策略和移动设备机会因子策略,分别设计了最小能耗优先和最早截止时槽优先的在线计算迁移算法。实验表明,与离线方法和能耗优先算法相比,考虑截止时槽的迁移方法在节能及算法效率等方面具有较优的性能。更多还原

【Abstract】 Computation offloading is one of the key technologies in cloud-edge collaboration.The design of offloading strategies and algorithms for specific application scenarios and optimization goals directly affect the efficiency and effectiveness of computation offloading.In the cloud-edge collaborative environment,existing offloading strategies lack sufficient consideration of various constraints and restrictions on the cloud and edges.Heterogeneous multi-dimensional resource requirements,real-time user experience,and dynamic application scenarios pose challenges to the offloading algorithm design,and there is also a lack of measurement of energy consumption from the overall system perspective.To address these problems,the thesis combines typical application scenarios under cloud-edge collaboration,with the optimization goal of minimizing system energy consumption,to conduct research on offloading strategies and algorithms.The main research contents are as follows:(1)Aiming at the coverage constraints of multiple edge servers on multiple users,this thesis takes the IoT application scenario where base stations serve as edge servers as an example,and proposes a cloud-edge collaborative computation offloading strategy with adjustable base station radii based on the proportional relationship between coverage radius and energy consumption.The mapping from a base station to a series of disks with varying radii and the transformation from the base station coverage to the disk coverage are achieved by establishing the base station-disk structure.After modeling the problem as an integer linear programming that satisfies the disk coverage requirements and multidimensional resource demands,computation offloading approximation algorithms based on greedy strategy and primal-dual method are designed respectively.The comparative experiments show that both algorithms are close to the optimal solution in terms of total energy consumption and base station coverage radii,while each has its own advantages.The former is efficient,and the latter can effectively balance the load among base stations and alleviate bandwidth pressure on the core network.(2)For the bottleneck of cloud bandwidth and real-time user experience requirements,this thesis proposes a near real-time cloud-edge collaborative computation offloading strategy based on cloud bandwidth compression for an application scenario in which edge processing results need to be transmitted to the cloud for collaboration.Based on a hierarchical cloud-edge collaborative offloading architecture and comprehensive consideration of system energy consumption,the problem is formulated as an integer linear programming model with cloud-edge multi-dimensional resource constraints and bandwidth compression ratio,and is proven to be an NP-hard problem.Then,combining the primal-dual theory and the concept of marginal price in economics,a near real-time computation offloading algorithm with polynomial time complexity is designed.The approximation ratio of the algorithm is derived by the weak dual property and the priceresource incremental relationship defined in this thesis.Comparative experiments indicate that the approximation algorithm has significant advantages in reducing system energy consumption,fully utilizing edge resources,and balancing cloud load.(3)In view of energy budget constraints on edge servers and dynamic arrival of tasks over time,this thesis takes the scenario where mobile devices act as lightweight edge servers as an example,and presents a dynamic cloud-edge collaborative computation offloading and resource allocation strategy based on elastic task windows.By jointly optimizing offloading decisions,computation and communication resource allocation,the problem is modeled as a mixed integer nonlinear programming with time slot constraints,multi-dimensional resource constraints and mobile device energy constraints.Given the strong coupling between offloading decisions and resource allocation,combined with fixed window length resource allocation strategy and mobile device chance factor strategy,online computation offloading algorithms that prioritize minimum energy consumption and earliest deadline are designed,respectively.Experiments show that the earliest deadline first method has better performance in energy saving and algorithm efficiency than the offline method and the minimum energy consumption first.更多还原