The Worst-case and Best-case Coverage Problems in Wireless Sensor Networks
| Autor: | Yung-tsung Hou, 侯雍聰 |
|---|---|
| Rok vydání: | 2009 |
| Druh dokumentu: | 學位論文 ; thesis |
| Popis: | 97 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. |
| Databáze: | Networked Digital Library of Theses & Dissertations |
| Externí odkaz: |
|