A Truthful Online Mechanism for Allocating Fog Computing Resources

Abstract The Internet of Things (IoT) is developing rapidly, and it is estimated that by 2025 22 billion active devices will be in the IoT [13]. Since it is impossible to let the often low-powered IoT devices perform all computing tasks, some of which are highly computationally demanding, fog computing, which extends the cloud to be closer IoT devices, has been proposed as a solution [3].To make the most of the fog resources and maximise the efficiency, good fog computing resource allocation mechanisms are needed. To address this challenge, researchers have proposed many resource allocation mechanisms for fog computing or similar computing paradigms [2, 4, 7, 8, 10, 19, 20]. However, most of these mechanisms were not specifically designed for settings where users act strategically to maximise their utility. Therefore, some researchers have proposed truthful mechanisms that incentivise users to truthfully reveal their private information [5, 12, 16–18, 21, 22]. However, these approaches cannot be applied directly to our model due to subtle but important differences. For example, [18] assumes singleminded users (i.e., users who do not get any value for a partially executed task). However, users in our model can get partial value for a partially executed task. In this paper, we are the first to formulate the fog computing resource allocation problem as a constraint optimisation problem that considers bandwidth constraints (a key challenge in IoT settings) and allows flexible allocation of virtual machines (VMs) and of the bandwidth. Furthermore, we introduce a novel dominant-strategy incentive compatible (DSIC) and individually rational (IR) mechanism to maximise social welfare.1 DSIC mechanisms guarantee that regardless of others' behaviours, users always maximise their utility by reporting truthfully. Furthermore, under an IR mechanism, no user will get a negative utility by participation.
  • Fan Bi (Southampton)
  • Sebastian Stein (Southampton)
  • Enrico Gerding (Southampton)
  • Nick Jennings (Imperial)
  • Tom La Porta (PSU)
Date May-2019
Venue International Conference on Autonomous Agents and Multiagent Systems (AAMAS) 2019 [link]