臺灣博碩士論文加值系統

覆蓋率的判定係無線感測網路的一項基本議題。普遍決定覆蓋率的演算法均需仰賴精確的感測器位置資訊。本篇論文探討在無法獲得位置資訊的前提之下，將覆蓋問題定義為尋找一個感測器所組成的最大集合，而此集合中的每個感測器的服務區域至少都被k個感測器所覆蓋，此處的k是一個給定的整數。在我們提出的分散式演算法中，每個感測器僅需鄰居資訊即可判斷其感測區域是否為k-覆蓋。最後，我們利用模擬通訊範圍與覆蓋範圍的比率變化來評估此演算法的效能。

Determining the coverage of a wireless sensor network is a
fundamental issue. Most coverage determination algorithms rely on accurate location information of sensors. In this paper, assuming no location knowledge, the coverage problem is defined as one of finding a maximum set of sensor nodes whose service areas are covered by at least k sensors, where k is a given integer. We propose distributed algorithms where each sensor only depends on neighborhood information to determine if its sensing area is k-covered or not. We evaluate the performance of these algorithms with simulations by varying the ratio of sensors'
communication distance to sensing distance.

摘要 i
Abstract ii
Acknowledgments iii
Contents iv
List of Figures vi
List of Tables vii
1 Introduction 2
2 RelatedWorks 4
3 Problem Statement 7
4 A Distributed k-CNL Solution 8
4.1 Main Steps . . . . . . 8
4.2 Determining Sensors’Relative Locations . . . 11
4.2.1 Case of RC = . . . . . . . . . . . . . . . . 11
4.2.2 Case of RC >= 4RS. . . . . . . . . . . . . . 13
4.2.3 Case of RC < 4RS . . . . . . . . . . . . . . 14
5 Simulation Results 16
5.1 The Effect of Node Density . . . . . . . . . . 16
5.2 The Effect of RC/RS Variation . . . . . .. . . 19
5.3 The Effect of Heterogeneous Sensor Networks . 19
6 Conclusions 22
Bibliography 23
Curriculum Vita 26

[1] C.-F. Huang and Y.-C. Tseng. The coverage problem in a wireless sensor network. In ACM Int’l Workshop on Wireless Sensor Networks and Applications (WSNA), pages 115–121, 2003.
[2] M. Cardei and J. Wu. Coverage in wireless sensor networks. In CRC Presee, 2004.
[3] B. Chen, K. Jamieson, H. Balakrishnan, and R. Morris. Span: An energy-efficient coordination algorithm for topology maintenance in ad hoc wireless networks. In ACM/Kluwer Wireless Networks, 8(5), pages 481–494, Sep. 2002.
[4] T. Clouqueur, V. Phipatanasuphorn, P. Ramanathan, and K. K. Saluja. Sensor deployment strategy for target detection. In ACM Int’l workshop on Wireless Sensor
Networks and Applications (WSNA), 2002.
[5] D.Nicules and B.Nath. Ad-hoc positioning system (APS) using AoA. In IEEE INFOCOM, 2003.
[6] F. Ye and G. Zhong. and S. Lu. and L. Zhang. PEAS: a robust energy conserving protocol for long-lived sensor networks. In the 23nd Int’l Conf. on Distributd Computing Systems (ICDCS), 2003.
[7] S. Meguerdichian, F. Koushanfar, M. Potkonjak, and M. Srivastava. Coverage problems in wireless ad hoc sensor networks. In IEEE INFOCOM, 2001.
[8] S. Meguerdichian, F. Koushanfar, G. Qu, and M.Potkonjak. Exposure in wireless ad-hoc sensor networks. In ACM Int’l Conf. on Mobile Computing and Networking
(MobiCom), 2001.
[9] J. B. M. Melissen and P. C. Schuur. Improved coverings of a square with six and eight equal circles. In Electronic Journal of Combinatorics, 3(1), 1996.
[10] K. J. Nurmela and P. R. J. ÄOster _ gard. Coverings a square with up to 30 equal circles. Technical Report Research Report A62, Helsinki University of Technology,
Laboratory for Theoretical Computer Science, Espoo, Finland, 2000.
[11] J. O’Rourke. Computational Geometry column 15. In Int’l Journal of Computation Geometry and Applications, volume 2(2), pages 215–217, 1992.
[12] A. Savvides, C.-C.Han, and M.B.Strivastava. Dynamic fine-grained localization in ad-hoc networks of sensors. In ACM Int’l Conf. on Mobile Computing and networking (MobiCom), pages 166–179, 2001.
[13] S. Slijepcevic and M. Potkonjak. Power efficient organization of wireless sensor networks. In IEEE Int’l Conf. on Communication (ICC), 2001.
[14] Y.-C. Tseng, S.-P. Kuo, H.-W. Lee, and C.-F. Huang. Location tracking in a wireless sensor network by mobile agents and its data fusion strategies. Int’l Workshop on
Information Processing in Sensor Networks (ISPN), 2003.
[15] G. Veltri, Q. Huang, G. Qu, and M. Potkonjak. Minimal and maximal exposure path algorithms for wireless embedded sensor networks. In ACM Int’l Conf. on Embedded Networked Sensor System (SenSys), 2003.
[16] X. Wang, Y. Z. G. Xing, C. Lu, R. Pless, and C. Gill. Integrated coverage and connectivity configuration in wireless sensor networks. In ACM Int’l Conf. on Embedded
Networked Sensor Systems (SenSys), pages 28–39, 2003.
[17] R. Williams. The geometrical foundation of natural structure; a source book of design. Dover Publications, 1979.
[18] T.-T. Wu and K.-F. Ssu. Determining active sensor nodes for complete coverage without location information. In Int’l Journal of Ad Hoc and ubiquitous Computing,
volume 1, pages 38–46, 2005.
[19] H. Zhang and J. Hou. Maintaining sensing coverage and connectivity in large sensor networks. In NSF Internation Workshop on Theoretical and Algorithmic Aspects of Sensor, Ad Hoc Wireless, and Peer-to-Peer Networks, 2002.
[20] R. Zheng, G. He, and X. Liu. Location-free coverage maintenance in wireless sensor network. Technical Report UH-CS-05-1, Department of Computer Science, University of Houston, Houston, TX, 77204, USA, 2005.
[21] Z. Zhou, S. Das, and H. Gupta. connected k-coverage problem in sensor networks. In Int’l Conf. Computer Communications and Networks (ICCCN), 2004.