On Cost-Based Task Assignment And Offloading In The Edge

Computation offloading is an often-used optimization method that exploits servers with powerful and plentiful resources to maximize computation efficiency with mini-mum 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 communi-cation costs are commonly ignored.Although these assumptions are reasonable to the offloading in traditional mobile computing,they are not valid anymore when consid-ering the problem in the edge-cloud 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 previ-ous 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.Beside,we propose a homogeneous model to show that,under certain conditions when the commu-nication cost between two tasks is symmetric,there exists an optimal offloading strategy since the homogeneous model can be transformed to a classical min-cut problem.And we design an algorithm to get the optimal solution.Our numerical results show that our algorithms for the new model are 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.