An approximation algorithm for sensor network nodes deployment

In this era of rapid intelligent transportation system development, sensors are widely applied for detection and surveillance on the road. It is necessary to reduce the cost on the sensor devices by using fewer sensors to cover more roads, which is the prerequisite for its large-scale application. However, the sensors deployment for a network can be proved as a NP-complete problem, so the optimization is intractable. In this paper, two independent solutions for sensors deployment are proposed and analyzed. The comparison shows that one is relatively more suitable for a dense road network while the other is fit for a sparse one. Then, an approximation algorithm based on the combination of the two is proposed and evaluated, which is proved to be reasonable and efficient for engineering applications.