Route selection for mobile sensors with checkpointing constraints

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 streets and courtyards. An alternative is to install a smaller number of mobile stations which traverse the city. The public transport network builds a perfect backbone for this purpose as public transport vehicles follow fixed and regular mobility patterns. In this paper, we consider the problem of selecting a subnetwork of a city´s public transport network to achieve a good coverage in the area. 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. Due to high computational complexity of the route selection problem, both with and without checkpointing support, we adapt an evolutionary algorithm solution and evaluate its output based on the tram network of Zurich.