Constant Approximation for Opportunistic Sensing in Mobile Air Quality Monitoring System <Abstract> Monitoring air quality plays a critical role in the sustainable development of developing regions where the air is severely polluted. Air quality monitoring systems based on static monitors often do not provide information about the area each monitor represents or represent only small areas. In addition, they have high deployment costs that reflect the efforts needed to ensure sufficient quality of measurements. Meanwhile, the mobile air quality monitoring system, such as the one in this work, shows the feasibility of solving those challenges. The system includes environmental sensors mounted on buses that move along their routes, broadening the monitoring areas. In such a system, we introduce a new optimization problem named opportunistic sensing that aims to find (1) optimal buses to place the sensors and (2) the optimal monitoring timing to maximize the number of monitored critical regions. We investigate the optimization problem in two scenarios: simplified and general bus routes. Initially, we mathematically formulate the targeted problem and prove its NP-hardness. Then, we propose a polynomial-time 1/ 2, (e?1)/(2e?1)-approximation algorithm for the problem with the simplified, general routes, respectively. To show the proposed algorithmsf effectiveness, we have evaluated it on the real data of real bus routes in Hanoi, Vietnam. The evaluation results show that the former algorithm guarantees an average performance ratio of 72.68%, while the latter algorithm achieves the ratio of 63.87%. Notably, when the sensors can be on (e.g., enough energy) during the whole route, the (e?1)/(2e?1)-approximation algorithm achieves the approximation ratio of (1?1/e). Such ratio, which is almost twice as (e?1)/(2e?1), enlarges the average performance ratio to 78.42%. |