Cooperative-Competitive Task Allocation in Edge Computing for Delay-Sensitive Social Sensing
Authors:
- Daniel ZhangDZDaniel Zhang
- Yue MaYMYue Ma
- Chao ZhengCZChao Zheng
- Yang ZhangYZYang Zhang
- X. Sharon HuXHX. Sharon Hu
- Dong WangDWDong Wang
- 1 October 2018
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 243-259
Abstract
With the ever-increasing data processing capabilities of edge computing devices and the growing acceptance of running social sensing applications on such cloud-edge systems, effectively allocating processing tasks between the server and the edge devices has emerged as a critical undertaking for maximizing the performance of such systems. Task allocation in such an environment faces several unique challenges: (i) the objectives of applications and edge devices may be inconsistent or even conflicting with each other, and (ii) edge devices may only be partially collaborative in finishing the computation tasks due to the "rational actor" nature and trust constraints of these devices, and (iii) an edge device's availability to participate in computation can change over time and the application is often unaware of such availability dynamics. Many social sensing applications are also delay-sensitive, which further exacerbates the problem. To overcome these challenges, this paper introduces a novel game-theoretic task allocation framework. The framework includes a dynamic feedback incentive mechanism, a decentralized fictitious play with a new negotiation scheme, and a judiciously-designed private payoff function. The proposed framework was implemented on a testbed that consists of heterogeneous edge devices (Jetson TX1, TK1, Raspberry Pi3) and Amazon elastic cloud. Evaluations based on two real-world social sensing applications show that the new framework can well satisfy real-time Quality-of-Service requirements of the applications and provide much higher payoffs to edge devices compared to the state-of-the-arts.Keywords
This publication has 55 references indexed in Scilit:
- Optimization of task allocation and priority assignment in hard real-time distributed systemsACM Transactions on Embedded Computing Systems, 2012
- Non-interactive Verifiable Computing: Outsourcing Computation to Untrusted Workers2010
- A game-theoretic method of fair resource allocation for cloud computing servicesThe Journal of Supercomputing, 2009
- A Game-Theoretic Approach to Efficient Power Management in Sensor NetworksOperations Research, 2008
- MapReduceCommunications of the ACM, 2008
- Exponential weight algorithm in continuous timeMathematical Programming, 2007
- Opportunistic Spectrum Access in Fading Channels Through Collaborative SensingJournal of Communications, 2007
- A new remote user authentication scheme using smart cardsIEEE Transactions on Consumer Electronics, 2000
- Allocating hard real-time tasks: An NP-Hard problem made easyReal-Time Systems, 1992
- Nash equilibrium with strategic complementaritiesJournal of Mathematical Economics, 1990