Minimizing Deployment Cost for Vehicular Sensor Networks in Air Monitoring Applications

The vehicular sensor network (VSN) is a bright candidate for many applications owing to its particular advantages. Such an application is air pollution monitoring, a critical issue associated directly with public health. We also notice that public transports are well-suited to deploy the network for this type of application. In this article, we propose a practical approach that leverages public buses to build the vehicle network with attached sensors for air pollution monitoring toward minimizing the deployment cost. Therefore, we hereafter call this problem vehicular sensor deployment (VSD). We first convert the VSD issue to a flow network described by a directed graph. Then, based on air sampling requirements, capacity constraints, and flow conservation of the flow network, we formulate the problem as an integer linear programming (ILP) model that yields the optimal solution. In addition, we suggest an approximation algorithm implemented by the linear programming relaxation technique combined with the randomized rounding algorithm (LPR-RRA), which provides approximate solutions to large-scale VSD problems. We also propose a greedy-based algorithm (GBA) to solve the problem against the most effective sampling in each iteration. Finally, we conduct experiments to evaluate the performance of the proposed algorithms as well as the influences of associated factors on the deployment cost. Simulation results show that the approximation algorithm approaches the optimal and outperforms the greedy.