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.
| Identifer | oai:union.ndltd.org:NSYSU/oai:NSYSU:etd-0610109-130053 |
| Date | 10 June 2009 |
| Creators | Hou, Yung-tsung |
| Contributors | D.J. Guan, Bingchiang Jeng, Chi-Sung Laih, Jung-Shian Li, Chia Mei Chen |
| Publisher | NSYSU |
| Source Sets | NSYSU Electronic Thesis and Dissertation Archive |
| Language | English |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | http://etd.lib.nsysu.edu.tw/ETD-db/ETD-search/view_etd?URN=etd-0610109-130053 |
| Rights | withheld, Copyright information available at source archive |
Page generated in 0.0065 seconds