fr
Chapitre d'actes
Anglais

Load Balancing Mechanisms to Regulate Costs and Quality in Mobile Crowdsensing Systems

Contributeurs/tricesBuwaya, Julia; Rolim, Jose
Présenté à Ottawa (ON), 5-7 June 2017
Maison d'éditionIEEE
Date de publication2017
Résumé

We study the problem of distributing loads in mobile crowdsensing systems (MCS). In this context, we present a multi-commodity network game, more explicitly, an atomic routing game, to depict the linking of several crowd participants into bundles that are capable of successfully completing desired sensing tasks. The nodes of the network correspond to the resources of the crowd participants and the players of our game are sensing service requesters that wish to route their demand along paths trough the network. One resource may serve several requests at the same time, which can be modeled efficiently using the network structure. Resource usage involves load-dependent costs. Our model caters for the uncertainty inherent from crowd involvement and mobility by incorporating certainty parameters in the model. These certainty parameters describe the quality of the partial result a participant can produce. Requesters may set a minimum certainty level for the successful completion of their overall sensing tasks that has to be met. In our model, we analyze four different solution concepts for balancing loads with respect to costs and quality of results: (1) a distributed brute force approach (engaging all suitable crowd participants), (2) a random selection of suitable crowd participants, (3) a Nash equilibrium (as result of decentralized selfish cost-minimizing game play) and (4) a (centralized) social optimum. All considered distributed solutions or an epsilon-approximation of a solution can be computed efficiently (for affine cost functions). Furthermore, well-known results for the price of anarchy of atomic routing games can be transfered to our model, i.e., the relative solution quality of a Nash equilibrium compared to a social optimum is provably bounded. In addition, we provide an extensive experimental study that supports theoretical results and gives further suggestions on the impact of uncertainty. We merge the findings of our analysis into a truthful distributed mechanism such that requesters have no incentive to deviate from an efficient solution.

Mots-clés
  • Mobile Crowdsensing
  • Load Balance
  • Efficiency
  • Atomic Routing
  • Game Theory
Citation (format ISO)
BUWAYA, Julia, ROLIM, Jose. Load Balancing Mechanisms to Regulate Costs and Quality in Mobile Crowdsensing Systems. In: 13th International Conference on Distributed Computing in Sensor Systems (DCOSS 2017). Ottawa (ON). [s.l.] : IEEE, 2017. p. 215–222. doi: 10.1109/DCOSS.2017.38
Fichiers principaux (1)
Proceedings chapter (Published version)
accessLevelRestricted
Identifiants
ISBN978-1-5386-3991-7
174vues
0téléchargements

Informations techniques

Création06/05/2020 15:04:00
Première validation06/05/2020 15:04:00
Heure de mise à jour15/03/2023 21:54:32
Changement de statut15/03/2023 21:54:31
Dernière indexation17/01/2024 09:47:04
All rights reserved by Archive ouverte UNIGE and the University of GenevaunigeBlack