佈置最少感測器以建立覆蓋所有重要區域無線感測網路之研究

Study of Constructing a Wireless Sensor Network to Fully Cover Critical Areas by Deploying Minimum Sensors

柯崴傑(Wei-Chieh Ke)

指導教授 ： 蔡明哲

國立清華大學/電機資訊學院/資訊工程學系/博士(2011年)

摘要

無線感測器網路由多個感測器連結而成，每個感測器都具有收集、處
理、儲存環境資訊的能力，並且能夠藉由無線通訊與網路中其他感測器溝通。這些特質使得無線感測器網路被廣泛的應用在不同的實例中。許多應用中，譬如環境掌控、戰場監視、核武、生化、化學攻擊偵測等等，重要的區域和普通區域應該要被適當的鑑別。若感測區域過大，我們無法提供足夠預算或足夠數目的感測器覆蓋所有的感測區域，則監控重要區域比起普通區域更實際也更有效率。本論文證明了使用最少的感測器將感測器放置在格子點上建立一個可以覆蓋所有重要正三角形格子(或正方形格子)，稱為CRITICAL-GRID COVERAGE (或CRITICAL-SQUARE-GRID COVERAGE)是NP-Copmlete問題。除此之外，一個逼近演算法被提出以解決CRITICAL-SQUARE-GRID COVERAGE問題。實驗結果顯示我們的演算法可以找出有效率的布置方法以解決CRITICAL-SQUARE-GRID COVERAGE問題。

關鍵字

無線感測網路

並列摘要

Wireless sensor networks are formed by connected sensors that each have the ability to collect, process, and store environmental information as well as communicate with others via inter-sensor wireless communication. These characteristics allow wireless sensor networks to be used in a wide range of applications. In many applications, such as environmental monitoring, battlefield surveillance, nuclear, biological, and chemical (NBC) attack detection, and so on, critical areas and common areas must be
distinguished adequately, and it is more practical and efficient to monitor critical areas rather than common areas if the sensor field is large, or the available budget cannot provide enough sensors to fully cover the entire sensor field. This thesis proves that deploying sensors on grid points to construct a wireless sensor network that fully covers critical equilateral (or, square) grids using minimum sensors, termed CRITICAL-GRID COVERAGE (or, CRITICAL-SQUARE-GRID COVERAGE), is NP-Complete. In addition, approximation algorithms are proposed for CRITICAL-SQUARE-GRID COVERAGE.
Simulations show that the proposed algorithms provide good solutions for CRITICAL-SQUARE-GRID COVERAGE.

並列關鍵字

wireless sensor network ； coverage ； NP-Complete

參考文獻

[1] X. Bai, S. Kumar, Z. Yun, D. Xuan, and T. H. Lai. Deploying wireless sensors to achieve both coverage and connectivity. In Procedings of ACM MobiHoc, Florence, Italy, 2006.

[2] M. Cardei and D. Z. Du. Improving wireless sensor network lifetime through power aware organization. ACM/Springer J. Wireless Networks, 11(3):333–340, May 2005.

[3] M. Cardei, M. T. Thai, Y. Li, and W. Wu. Energy-efficient target coverage in wireless sensor networks. In Proceedings of IEEE INFOCOM, Miami, FL, 2005.

[4] K. Chakrabarty, S. S. Iyengar, H. Qi, and E. Cho. Grid coverage for surveillance and target location in distributed sensor networks. IEEE Trans. Computers, 51(12):1448–1453, Dec. 2002.

[5] C. Y. Chang, C. T. Chang, Y. C. Chen, and H. R. Chang. Obstacle-resistant deployment algorithms for wireless sensor networks. IEEE Trans. Vehicular Technology, 58(6):2925–2941, July 2009.