Computational Offloading for Energy Constrained Devices in Multi-Hop Cooperative Networks

As the number of mobile devices that natively support ad hoc communication protocols increase, large ad hoc networks can be created not only to facilitate communication among the mobile devices, but also to assist devices that are executing computationally intensive applications. Prior work has developed computation offloading systems for mobile devices, but this work has focused exclusively on offloading to single hop neighbors, due in part to the practical challenges of setting up multi-hop networks using existing ad hoc communication protocols. However, limiting the offloading of computation to one-hop neighbors inherently restricts the number of devices that can participate in the distributed computation. By presenting a heuristic, aimed at avoiding partitioning the network, as well as an iterative task assignment algorithm that can optimize the assignment of computational tasks to devices in a multi-hop cooperative network, we are able to evaluate the effect of computational offloading in multi-hop networks. Experimental results, obtained from an implementation on Android devices, are integrated with an analytical model that enables the evaluation of system performance under a variety of conditions. These experimental and analytic results demonstrate the benefit of enabling computation offloading to all devices in a multi-hop cooperative network.