Computation offloading in wireless multi-hop networks: Energy Minimization via multi-dimensional knapsack problem

Computation offloading is an upcoming approach to increase battery life of mobile devices overburdened by resource-consuming applications. In multi-hop networks, computation offloading poses new challenges since intermediate devices are required to relay tasks of others along the path to the server. The decision of a device about whether to offload or not depends thus on the provided energy of relay devices and on the decisions of other offloading devices since relay resources need to be shared. This also implies that for energy minimization, optimal decisions are topology-dependent. This paper introduces a novel theoretical framework for energy minimization of computation offloading in multi-hop wireless networks which formulates the energy minimization problem as a binary linear problem. Proving its equivalence to a multi-dimensional knapsack problem allows us to specify a greedy heuristic, which shows very good performance, with a maximal deviation of less than 5% from the optimal results. From simulations and analytical results for different topologies, we derive under which conditions computation offloading in multi-hop networks is beneficial.