Wireless sensor networks provide an alternative way of improving our environments, such as environment surveillance, hazard monitoring, and other customized environment application, especially in military applications. Furthermore, the coverage issue in wireless sensor networks also plays an important role. Good coverage of a sensor network is an essential issue to ensure the quality of service. This paper studies the barrier coverage problems of a sensor networks, and will find the optimized straight-line path for both best-case and worst-case coverage problems. The optimal algorithm we proposed has a quadratic time complexity and is based on computational geometry. We proposed the distance function theory and applied it in our problems and we used the sweep and divide concept to solve the problems. Furthermore, the correctness of the proposed method is validated and simulated by experiments.

Wireless sensor networks provide a wide range of applications, such as environment surveillance, hazard monitoring, traffic control, and other commercial or military applications. The quality of service provided by a sensor network relies on its coverage, i.e., how well an event can be tracked by sensors. This research studies issues about sensor coverage: (1) how to optimally deploy new sensors in order to improve the coverage of an existing network, (2) how to properly measure the coverage when the path is a line. The best- and worst-case coverage problems that are related to the observability of a path are addressed and formulated into computational geometry problems. We prove that there exists a duality between the two coverage problems, and then solve the two problems together. The presented new-node placement algorithm is shown to deploy new nodes optimally in polynomial time. However, in some applications, such as highway monitoring and anti-missile interception systems, the trajectory of a target is linear but we can not find suitable coverage measurement for the straight-line path in previous research. Therefore, this research presents novel algorithms for coverage measurement of straight-line paths. Based on computational geometry and graph theory, we propose plane sweep algorithms to find the optimal straight-line paths for both the best-case and worst-case coverage problems in polynomial time. Both mathematical analysis and simulations are used to prove the optimality of our algorithms.