On Cost-Driven Computation Offloading in the Edge: A New Model Approach

摘要

Computation offloading is an often-used optimization method that exploits servers with powerful and plentiful resources to maximize computation efficiency with minimum cost. In this method, a client application is usually modeled as a weighted directed acyclic graph (DAG), which is typically split into two distinct parts - one running on client device and the other on server machine. To simplify the model, the inter-part communication costs are always assumed to be symmetric and the intra-part communication costs are commonly ignored. Although these assumptions are reasonable to the offloading in traditional mobile computing, they are not valid anymore when considering the problem in the edgecloud environment, especially with the development of microservice, where a provisioned multi-machine cluster at each side is involved. To address this problem, we propose a new offloading model in this paper, where both the intra-part communication costs as well as the asymmetry of inter-part communication costs are incorporated to carry out the client application, which are not a part of previous approaches. Given this model, we first prove the offloading problem is NP-hard, then design an efficient greedy algorithm to obtain a sub-optimal solution. Our numerical results show that our algorithm for the new model is always efficient to find a better offloading scheme, compared with other existing algorithms that lack the notion of communication costs between tasks co-located at the same side and the asymmetry of communication costs crossing sides.