用於k夾角覆蓋問題之感測節點佈建演算法

Sensor Deployment Algorithm for k-Angle Coverage Problem

楊蘭智(Lan-Chih Yang)

指導教授 ： 陳文村

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

https://doi.org/10.6843/NTHU.2009.00631

摘要

在無線感測網路( wireless sensor network )中，最主要的功能是蒐集以及處理感測區域( sensing field )內的環境資訊。感測網路對目標造成的覆蓋( coverage )是其中很重要的議題，因為它會影響到感測的品質。過去有關覆蓋問題的研究大多數都集中於探討全向性( Omni-directional )的感測節點( sensor node )上，這些方法並不適用於如影像感測節點這類指向性的感測節點上。在這篇論文中，我們研究一個新的覆蓋問題。k-夾角覆蓋問題( k-angle coverage problem )探討指向性的感測節點，它利用覆蓋目標物的節點數目以及節點間覆蓋的夾角來衡量感測品質。研究的問題是要利用最少的感測節點去k-夾角覆蓋所有目標物。我們提出了一個貪婪演算法來解決這個問題。這個方法依照每個位置所提供的貢獻度來決定佈建的位置。我們提出了三個貢獻度函數( contribution function )來決定每個位置的貢獻度。實驗結果顯示了這個方法的特性以及在不同情情況下的效能。基於這個演算法，我們開發了一個幫助決定感測節點佈建位置的工具程式。這個工具程式可以讓使用者快速的得到一個低成本的感測節點的佈建結果，減少所需的人力與時間成本。

關鍵字

覆蓋問題 ； 佈建問題 ； 無線感測網路

並列摘要

Coverage problem is one of the most fundamental problems in wireless sensor networks since it reflects the sensing quality of a sensor network. Several coverage problems have been studied for different applications such as [1], [2] studies the coverage problem, and [12] discussed the barrier coverage problems. However, these works assume the sensor has Omni-directional sensing model which is not suitable in many applications such as video surveillance systems consisting of directional video sensors. In this thesis, we study a new coverage problem in wireless sensor networks. The k-angle coverage problem considers the problem using directional sensors which can only cover a limited angle and range. Given a set of targets to be monitored, the goal is to deploy minimal number of sensors to k-angle cover all the targets. We present a greedy algorithm to solve this problem. For this algorithm, we define three contribution functions to determine the location to deploy sensor. The proposed method greedily selects a maximal contribution location to deploy a sensor until the entire targets are k-angle covered. Simulation results exhibit the characteristic and performance of our algorithm. Based on the proposed algorithm, we develop a toolkit for emulating sensor deployment.

並列關鍵字

coverage problem ； sensor deployment ； sensor network

參考文獻

[1] S. Meguerdichian, F. Koushanfar, M. Potkonjak and M. B. Srivastava, “Coverage Problems in Wireless Ad-hoc Sensor Networks,” in Proc.of IEEE Int’l Conf. on Computer Communications (INFOCOM), 2001.

[2] C.-F. Huang and Y.-C. Tseng, “The Coverage Problem in a Wireless Sensor Network,” in Proc.of ACM International Workshop on Wireless sensor networks and applications (WSNA), 2003.

[3] C.-F. Huang, Y.-C. Tseng and H.-L. Wu, “Distributed protocols for ensuring both coverage and connectivity of a wireless sensor network,” ACM Transactions on Sensor Networks (TOSN), vol. 3, no. 1, March 2007.

[4] H. Gupta, S. R. Das, and Q. Gu, “Connected sensor cover: self-organization of sensor networks for efficient query execution,” in Proc. of ACM Int’l symposium on Mobile Ad Hoc Networking and Computing (MobiHoc), 2003.

[5] S. Shakkottai, R. Srikant, and N. Shroff, “Unreliable sensor grids:coverage, connectivity and diameter,” in Proc.of IEEE Int’l Conf. on Computer Communications (INFOCOM), 2003.