Title page for etd-0610109-130053


[Back to Results | New Search]

URN etd-0610109-130053
Author Yung-tsung Hou
Author's Email Address No Public.
Statistics This thesis had been viewed 5652 times. Download 1761 times.
Department Information Management
Year 2008
Semester 2
Degree Ph.D.
Type of Document
Language English
Title The Worst-case and Best-case Coverage Problems in Wireless Sensor Networks
Date of Defense 2009-05-21
Page Count 56
Keyword
  • Worst-case coverage
  • Line Coverage
  • Wireless sensor networks
  • Best-case Coverage
  • Abstract 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.
    Advisory Committee
  • D.J. Guan - chair
  • Jung-Shian Li - co-chair
  • Chi-Sung Laih - co-chair
  • Bingchiang Jeng - advisor
  • Chia Mei Chen - advisor
  • Files
  • etd-0610109-130053.pdf
  • indicate accessible in a year
    Date of Submission 2009-06-10

    [Back to Results | New Search]


    Browse | Search All Available ETDs

    If you have more questions or technical problems, please contact eThesys