Mobile Crowdsensing from a Selfish Routing Perspective
Julia Buwaya, Andrea Roli · 2017
We present a selfish routing model to optimize the allocation of tasks in a mobile crowdsensing (MCS) system. The players of our game are sensing service requesters that wish to route their demand along paths that are made up of resources belonging to the crowd participants. Resource usage involves load-dependent costs and one resource may serve several requests at the same time. Due to human involvement and mobility there exists uncertainty, which we address by introducing certainty parameters. For the Nash equilibria of our game, we can transfer efficiency guarantees, i.e., the worst-case ratio between the welfare of an equilibrium and the welfare of a social optimum is provably bounded by a small constant when cost functions are polynomials. An epsilon-approximation of a Nash equilibrium solution can be computed in polynomial time for affine cost functions. Based on our model, we develop a mechanism for the automation of efficient task allocations in MCS systems and we present a proof for the truthfulness of this mechanism.