Route selection for mobile sensor nodes on public transport networks

The sensing range of a sensor is spatially limited. Thus, achieving a good coverage of a large area of interest requires installation of a huge number of sensors which is cost and labor intensive. For example, monitoring air pollution in a city needs a high density of measurement stations installed throughout the area of interest. As alternative, we install a smaller number ofmobile sensing nodes on top of public transport vehicles that regularly traverse the city. In this paper, we consider the problemof selecting a subnetwork of a city's public transport network to achieve a good coverage of the area of interest. In general case, public transport vehicles are not assigned to fix lines but rather to depots where they are parked overnight. We introduce an algorithm that selects the installation locations, i. e., number of vehicleswithin each host depot, such that sensing coverage ismaximized. Since we are working with low-cost sensors, which exhibit failures and drift over time, vehicles selected for sensor installation have to be in each other's vicinity from time to time to allow comparing sensor readings. We refer to such meeting points as checkpoints. Our algorithmoptimizes sensing coveragewhile providing a sufficient number of checkpoint locations. We evaluate our algorithm based on the tram network of Zurich and show how an accurate selection of vehicles for installing measurement stations affects the overall system quality. We show that our algorithm outperforms random search, simulated annealing, and the greedy approach.