Distributed online optimization of fog computing for selfish devices with out-of-date information

By performing fog computing, a device can offload delay-tolerant computationally demanding tasks to its peers for processing, and the results can be returned and aggregated. In distributed wireless networks, the challenges of fog computing include lack of central coordination, selfish behaviors of devices, and multi-hop signaling delays, which can result in outdated network knowledge and prevent effective cooperations beyond one hop. This paper presents a new approach to enable cooperations of N selfish devices over multiple hops, where selfish behaviors are discouraged by a tit-for-tat mechanism. The tit-for-tat incentive of a device is designed to be the gap between the helps (in terms of energy) the device has received and offered; and indicates how much help the device can offer at the next time slot. The tit-for-tat incentives can be evaluated at every device by having all devices broadcast how much help they offered in the past time slot, and used by all devices to schedule task offloading and processing. The approach achieves asymptotic optimality in a fully distributed fashion with a time-complexity of less than O(N²). The optimality loss resulting from multi-hop signaling delays and consequently outdated tit-for-tat incentives is proved to asymptotically diminish. Simulation results show that our approach substantially reduces the time-average energy consumption of the state of the art by 50% and accommodates more tasks, by engaging devices hops away under multi-hop delays.