Distributed Algorithm for Energy Efficient Multi-Hop Computation Offloading

Computation offloading is a promising approach for reducing the computational load and extending the battery lifetime of mobile nodes. A network consisting of several wireless nodes accessing the cloud in a multi-hop fashion is considered. In multi-hop networks, offloading a computational task requires relaying the task by the intermediate nodes along the path towards the cloud. If the nodes are autonomous and rational, the intermediate nodes need to be incentivized for forwarding the tasks of other nodes. In this paper, a distributed decision algorithm which determines the set of tasks to be offloaded and the set of tasks to be locally computed for total energy minimization is proposed. Since a task needs to be sequentially forwarded by multiple nodes, each of which decides independently, decision conflicts on forwarding a task can occur. Accordingly, a novel coordination mechanism is proposed by which the forwarding nodes resolve their decision conflicts. In this coordination mechanism, nodes need only to exchange their forwarding decisions to resolve the conflicts. The results show that the proposed distributed algorithm achieves a performance close to the performance of the centralized algorithm.