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

摘要

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.