论文标题
在协作边缘计算中的最佳交通拥堵的路由和卸载
Optimal Congestion-aware Routing and Offloading in Collaborative Edge Computing
论文作者
论文摘要
协作边缘计算（CEC）是一个新兴的范式，在其中共享通信和计算资源通过共享诸如模型培训或视频处理之类的异质边缘设备协作以实现计算任务。然而，使用任意拓扑的CEC中的最佳数据/结果路由和计算策略仍然是一个开放的问题。在本文中，我们为任意可划分的任务制定了部分偏移和多跳路由的流程模型，其中每个节点分别决定其路由/卸载策略。与大多数现有作品相反，我们的模型适用于具有不可忽略的结果大小的任务，并允许数据源与结果目的地不同。我们提出了一个网络范围内的成本最小化问题，用于通信和计算的拥堵感知凸成本功能。这种凸成本涵盖了各种性能指标和约束，例如平均排队延迟，处理器容量有限。尽管问题是非凸的，但我们为全局最佳解决方案提供了必要的条件和足够的条件，并设计了一种完全分布的算法，该算法在多项式时间内收敛到最佳，允许异步的个体更新，并且可以适应任务模式的变化。数值评估表明，我们提出的方法在多个网络实例中，尤其是在拥挤的方案中明显优于其他基线算法。
Collaborative edge computing (CEC) is an emerging paradigm where heterogeneous edge devices collaborate to fulfill computation tasks, such as model training or video processing, by sharing communication and computation resources. Nevertheless, the optimal data/result routing and computation offloading strategy in CEC with arbitrary topology still remains an open problem. In this paper, we formulate the flow model of partial-offloading and multi-hop routing for arbitrarily divisible tasks, where each node individually decides its routing/offloading strategy. In contrast to most existing works, our model applies to tasks with non-negligible result size, and allows data sources to be distinct from the result destination. We propose a network-wide cost minimization problem with congestion-aware convex cost functions for communication and computation. Such convex cost covers various performance metrics and constraints, such as average queueing delay with limited processor capacity. Although the problem is non-convex, we provide necessary conditions and sufficient conditions for the global-optimal solution, and devise a fully distributed algorithm that converges to the optimum in polynomial time, allows asynchronous individual updating, and is adaptive to changes in task pattern. Numerical evaluation shows that our proposed method significantly outperforms other baseline algorithms in multiple network instances, especially in congested scenarios.
