Adapting the A* Algorithm to Increase Vehicular Crowd-Sensing Coverage

Current vehicles are incorporating an even wider number of environmental sensors, mainly needed to improve safety, efficiency and quality of life for passengers. These sensors bring a high potential to significantly contribute also to urban surveillance for Smart Cities by leveraging opportunistic crowd-sensing approaches. In this context, the achievable spatio-temporal sensing coverage is an issue that requires more investigations, since usually vehicles are not uniformly distributed over the road network, as drivers mostly select a shortest time path to destination. In this paper we present an evolution of the standard A∗∗ algorithm to enhance vehicular crowd-sensing coverage. In particular, with our solution, the route is chosen in a probabilistic way, among all those satisfying a constraint on the total length of the path. The proposed algorithm has been empirically evaluated by means of a public dataset of real taxi trajectories, showing promising performances in terms of achievable sensing coverage.