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(N2). 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.
Bibliographical noteFunding Information:
Manuscript received April 18, 2018; revised July 12, 2018; accepted September 5, 2018. Date of publication September 18, 2018; date of current version November 9, 2018. This work was supported in part by NSFC under Grant 61790553, and in part by the National Key Research and Development Program of China under Grant 2017ZX03001003. The associate editor coordinating the review of this paper and approving it for publication was A. Banchs. (Corresponding author: Hui Tian.) X. Lyu is with the State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China, and also with the Global Big Data Technologies Center, University of Technology Sydney, Ultimo, NSW 2007,Australia.
- Distributed fog computing
- Lyapunov optimization
- out-of-date information
- selfish devices