無線感測網路的應用遍及於不同的商業或是軍事領域，包括環境監測、災難監控、交通管制等等。而無線感測網路之服務品質取決於網路的覆蓋率，亦即感應器對監測事件的偵測能力。本論文研究無線感測網路的覆蓋率，包含以下兩個主題: (1) 如何佈署新的感測器以達到最佳覆蓋率改進; (2) 對於直線路徑如何適當的測量覆蓋率。此論文使用了計算幾何及圖論的方法來進行對最佳情況及最差情況下的覆蓋率問題，並証明此兩種問題可互相轉換成另一種問題。論文提出了有效率的多項式時間演算法來佈置新加入的感測器，新的佈署位置將可達到最佳的覆蓋率改善。而在某些感測網路的應用當中，感測目標物的移動路徑是直線路徑，例如高速公路監測或是飛彈攔截系統，這些應用需要對於直線行進路徑計算其覆蓋率。因此本論文提出新的平面掃描演算法來計算直線路徑下的無線感測網路路徑覆蓋率。

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.

1. Introduction 1
2. Related Work 6
3. Preliminaries 8
3.1 Sensor Network Model 8
3.2 Computational Geometry 8
3.3 Problem Formulation of New-node Deployment 10
3.4 Problem Formulation of Line Coverage 12
4. The Best- and Worst-case Coverage Deployment Problems 14
4.1 Duality 14
4.2 The Best-case Coverage Deployment Algorithm 17
4.3 Time Complexity 29
5. Line Coverage Algorithms 31
5.1 Distance Function of a Straight-line Path 31
5.2 Algorithm for Worst-case Line Coverage 33
5.3 Algorithm for Best-case Line Coverage 34
5.4 Time Complexity 40
6. Experiments 41
6.1 The Best-case Coverage Deployment Algorithm 41
6.2 The Best-case Line Coverage Algorithm 42
7. Conclusion 45
Bibliography 46

1. M. Cardei and J. Wu, Handbook of Sensor Networks, chapter Coverage in Wireless Sensor Networks, CRC Press, July 2004.
2. S. Meguerdichian, F. Koushanfar, M. Potkonjak and M. Srivastava, Worst and Best-Case Coverage in Sensor Networks, IEEE Transactions on Mobile Computing Vol. 4(1), pp. 84-92, 2005.
3. X.-Y. Li, P.-J. Wan and O. Frieder, Coverage in Wireless Ad-Hoc Sensor Networks, IEEE Transactions on Computers Vol. 52(6), pp. 753-763, 2003.
4. S. Slijepcevic and M. Potkonjak, Power Efficient Organization of Wireless Sensor Networks, In Proceedings of IEEE International Conference on Communications Vol. 2, pp. 472-476, 2001.
5. D. Tian and N.D. Georganas, A coverage-preserving node scheduling scheme for large wireless sensor networks, in Proceedings of the first ACM International Workshop on Wireless Sensor Networks and Applications (2002), pp. 32-41.
6. C.F. Huang and Y.C. Tseng, The Coverage Problem in a Wireless Sensor Network, Springer, Mobile Networks and Applications, Vol. 10(4), pp. 519-528, 2001.
7. M. Cardei and D.-Z. Du, Improving Wireless Sensor Network Lifetime through Power Aware Organization, Springer, Wireless Networks, Vol. 11(3),pp. 333-340, 2005.
8. K. Kar and S. Banerjee, Node Placement for Connected Coverage in Sensor Networks, in Proceedings of WiOpt 2003: Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (2003).
9. T.J. Cormen, C.E. Leiserson and R.L. Rivst. Introduction to Algorithms, MIT Press, Cambridge, MA, 1990.
10. H. Huang and A.W. Richa, Dynamic Coverage in Ad-Hoc Sensor Networks, Springer, Mobile Networks and Applications, Vol. 10(1) pp. 9-17, 2005.
11. S. Meguerdichian, F. Koushanfar, G. Qu and M. Potkonjak, Exposure in Wireless Ad-Hoc Sensor Networks, in Proceedings of the 7th Annual International Conference on Mobile Computing and Networking (2001) pp. 139-150.
12. A. Savvides, C.C. Han and M.B. Srivastava, Dynamic Fine-Grained Localization in Ad Hoc Networks of Sensors, in Proceedings of the 7th Annual Internat. Conference on Mobile Computing and Networking (2001) pp. 166-179.
13. F.P. Preparata, M.I. Shamos, Computational Geometry: An Introduction ,Springer-Verlag, 1985.
14. S. Fortune,Voronoi Diagrams and Delaunay Triangulations, Handbook of discrete and computational geometry, CRC Press, 1997.
15. J. O’Rourke, Combinatorial Geometry in C, Cambridge, 1998.
16. J.W. Jaromczyk and G.T. Toussaint, Relative Neighborhood Graphs and Their Relatives, Proceedings IEEE, Vol. 80(9), pp. 1502-1517, 1992.
17. K.R. Gabriel and R.R. Sokal, A New Statistical Approach to Geographic Variation Analysis, Systematic Zoology, Vol. 18(3), pp. 259-278, 1969.
18. Liu B., Towsley D. A Study of the Coverage of Large-scale Sensor Networks. In IEEE International Conference on Mobile Ad-hoc and Sensor Systems 2004, pp. 475-483.
19. Adlakha S. and Srivastava M., Critical Density Thresholds for Coverage in Wireless Sensor Networks. In Proceedings of the IEEE WCNC 2003, Vol. 3, pp. 1615-1620.
20. Xing K., Ding M., Cheng X., Rotenstreich S. Safety Warning Based on Highway Sensor Networks. In Proceedings of the IEEE WCNC 2005, Vol. 3, pp. 2355-2362.
21. Song L. and Hatzinakos D., Architecture of Wireless Sensor Networks with Mobile Sinks: Sparsely Deployed Sensors. IEEE Transactions on Vehicular Technology, Vol. 56(4), pp. 1826-1836, 2004.
22. Xu N., A Survey of Sensor Network Applications. IEEE Communications Magazine, Vol. 40(8), pp. 102–114, 2002.
23. Anjum F., Subhadrabandhu D., Sarkar S. and Shetty, R, On optimal placement of intrusion detection modules in sensor networks. In Proceedings of 1st International Conference on Broadband Networks 2004, pp. 690-699.
24. Hamilton M., CENS: New Directions in Wireless Embedded Networked Sensing of Natural and Agricultural Ecosystems. In Proceedings of Converging Technologies for Agriculture and Environment: Sir Mark Oliphant Conference 2004.
25. Zhang J., Zhou G., Son S. H., Stankovic J. A. and Whitehouse K., Performance Analysis of Group Based Detection for Sparse Sensor Networks. In Proceedings of the 28th International Conference on Distributed Computing Systems 2008, pp. 111-122.
26. Lazos L., Poovendran R. and Ritcey J. A., On the Deployment of Heterogeneous Sensor Networks for Detection of Mobile Targets. In Proceedings of the 6th international conference on Information processing in sensor networks 2007, pp. 519-528.
27. Dousse O., Tavoularis C. and Thiran P., Delay of Intrusion Detection in Wireless Sensor Networks. In Proceedings of the 7th ACM international symposium on Mobile ad hoc networking and computing 2006, pp. 155-165.
28. Ram S. S., Manjunath D., Iyer S. K. and Yogeshwaran D., On the Path Coverage Properties of Random Sensor Networks. IEEE Transactions on Mobile Computing, Vol. 6(5), pp. 494-506, 2007.
29. Cao Q., Yan T., Stankovic J. and Abdelzaher T., Analysis of Target Detection Performance for Wireless Sensor Networks. In International Conference on Distributed Computing in Sensor Networks (DCOSS) 2005.
30. Gupta R. and Das S.R., Tracking Moving Targets in a Smart Sensor Network. In Proceedings of IEEE Vehicular Technology Conference 2003, Vol. 5, pp. 3035-3039.
31. Gui C. and Mohapatra P., Power Conservation and Quality of Surveillance in Target Tracking Sensor Networks. Proceedings of the 10th annual international conference on Mobile computing and networking 2004, pp.129-143.
32. Tim Tau Hsieh., Using sensor networks for highway and traffic applications. IEEE Potentials, Vol. 23(2), pp. 13-16, 2004.
33. Robert Sedgewick, Algorithms in C++. Addison-Wesley, 2002.
34. Reinhard Diestel, Graph Theory (Graduate Texts in Mathematics), Springer, 2006.
35. I.F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, Wireless sensor networks: a survey, Computer Networks, Vol. 38(4), pp. 393-422, 2002.
36. A. Mainwaring, J. Polastre, R. Szewczyk, D. Culler and J. Anderson, Wireless sensor networks for habitat monitoring, In Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, pp. 88-97, 2002.
37. D. Estrin, L. Girod, G. Pottie and M Srivastava, Instrumenting the world with wireless sensor networks, In Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing, pp. 2033-2036, 2001.
38. S. Kumar, T.H. Lai and A. Arora, Barrier coverage with wireless sensors, Wireless Networks, Vol. 13(6), pp. 817-834, 2007.
39. A. Chen, S. Kumar and T.H. Lai, Designing localized algorithms for barrier coverage, In Proceedings of the 13th annual ACM international conference on Mobile Computing and Networking, pp. 63-74, 2007.
40. B. Liu, O. Dousse, J. Wang and A. Saipulla, Strong barrier coverage of wireless sensor networks, In Proceedings of the 9th ACM international symposium on Mobile Ad Hoc Networking & Computing, pp. 411-420, 2008.
41. C. Savarese, J.M. Rabaey and J. Beutel, Locationing in distributed ad-hoc wireless sensor networks, In Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing, pp. 1045-1049, 2001.
42. L. Doherty, K.S.J. Pister and L. E.l. Ghaoui, Convex Position Estimation in Wireless Sensor Networks, In Proceedings of Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), pp. 1655-1663, 2001.