Optimal Congestion-aware Routing and Offloading in Collaborative Edge Computing
Optimal Congestion-aware Routing and Offloading in Collaborative Edge Computing
复制标题
DOI：
10.23919/wiopt56218.2022.9930581
复制
发表时间：
2022-05
期刊：
影响因子：
--
通讯作者：
Jinkun Zhang;Yuezhou Liu;E. Yeh
中科院分区：
文献类型：
--
作者：
Jinkun Zhang;Yuezhou Liu;E. Yeh
协同边缘计算（CEC）是一种新兴的范例，其中异构边缘设备通过共享通信和计算资源来协作以完成计算任务，例如模型训练或视频处理。然而，当考虑网络拥塞时，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, when considering network congestion, the optimal data/result routing and computation offloading strategy of CEC still remains an open problem. In this paper, we formulate a flow model of partial-offloading and multi-hop routing in CEC network with arbitrarily topology and heterogeneous communication/computation capability. 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. 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. Our proposed method allows asynchronous individual updating, and is adaptive to changes of network parameters. Numerical evaluation shows that our method significantly outperforms other baseline algorithms in multiple network instances, especially in congested scenarios.