Delay-Optimal Distributed Edge Computation Offloading for Interdependent Computation and Communication Workloads

By integrating edge computing with parallel computing, distributed edge computing (DEC) makes use of distributed devices in edge networks to perform computing in parallel, which can substantially reduce service delay. In this paper, we explore DEC that offloads computation to distributed edge devices connected by a wireless network, where computation and communication workloads are interdependent. In particular, we study the fundamental problem of computation and communication scheduling for minimizing the total delay of computation offloading. We consider both preemptive and non-preemptive networks, where backward communications can or cannot be interrupted. For each setting, we first equivalently transform the problem to a simplified problem of workload allocation with non-interrupted communications and no communication interference constraints. Then we develop an efficient algorithm to solve the equivalent problem by exploiting specific structures of the problem. In particular, for non-preemptive networks, we show that the optimal communication order is determined by nodes’ communication rates only. Our results provides useful insights for the optimal computation-communication co-design. We evaluate the proposed algorithms using simulation results, which corroborate the advantages of the algorithms.