使用可移動感測器之無線感測網路的缺洞偵測及修補

Hole Detection and Healing in Mobile Wireless Sensor Networks

彭元璟(Yuan-Ching Peng)

指導教授 ： 陳秋媛

國立交通大學/理學院/應用數學系暨研究所/碩士(2015年)

https://doi.org/10.6842/NCTU.2015.00312

摘要

無線感測網路可廣泛地應用在特定的、我們感興趣的區域（亦即監控區域，英文全名為region of interest,習慣上簡記為RoI）的監控上。維持監控區域被完整且持續地覆蓋是很重要的問題。然而，由於外在環境的因素，以及感測器本身的脆弱性，維持完整覆蓋是很困難的。因此，監控區域產生缺洞是一個無法避免的問題。本論文之目的即在於探討使用可移動感測器之無線感測網路的監控區域之缺洞問題。我們提出一個可幫助我們計算需要感測器的位置之修補模型。與已存在的方法[8]比較，我們的演算法有三個優點： (1)感測器的不均勻分佈不會影響總計算量，(2)決定缺洞修補範圍時使用的感測器數量較[8]可行，(3)我們的演算法在執行一次之後便能完全修補缺洞([8]的演算法通常需要執行數次才能完全修補缺洞)。

關鍵字

使用可移動感測器之無線感測網路 ； 覆蓋 ； 缺洞檢測 ； 缺洞修補 ； 演算法

並列摘要

Wireless sensor networks (WSNs) have a wide array of applications in monitoring of a specified region of interest (RoI).
To maintain an RoI to be completely and continuously covered is a very important task.
However, the environmental factors and the intrinsic fragility of sensors make the complete cover of RoI difficult.
Thus, the emergence of holes in an RoI is unavoidable.
In this thesis, we intend to address the hole healing problem in mobile WSNs.
We propose a healing model that can help us to determine the locations that require dispatched sensors.
As compared with the existing solution [8], our algorithm has the following three advantages: (1) the non-uniform distribution of sensors will not affect the amount of calculation for the healing process, (2) the number of sensors used by our healing process is more feasible than the number of sensors used by [8], and (3) the number of dispatched sensors used by our algorithm can guarantee that the holes will be healed after running our algorithm once.
Notice that the algorithm in [8] may need to run several times to heal the holes.

並列關鍵字

mobile wireless sensor network ； coverage ； hole detection ； hole healing ； algorithm

參考文獻

[2] N. Bulusu, J. Heidemann, D. Estrin, GPS-less low cost outdoor localization for very small devices, IEEE Personal Communications, vol. 7, no. 5, pp. 28-34, 2002.

[3] B.N. Clark, C.J. Colbourn, and D.S. Johnson, Unit disk graphs, Discrete Mathematics, vol. 86, pp. 165-177, 1990.

[4] Q. Fang, J. Gao, and L.J. Guibas, Location and bypassing hole in sensor networks, Mobile Networks and Applications, vol. 11, no. 2, pp. 187-200, 2006.

[5] W.B. Heinzelman, A.P. Chandrakasan, and H. Balakrishnan, An application-specific protocol architecture for wireless microsensor networks, IEEE Transactions on Wireless Communications, vol. 1, no. 4, pp. 660-670, 2002.

[7] K. Langendoen and N. Reijers, Distributed localization in wireless sensor networks: a quantitative comparison, Computer Networks, vol. 43, no. 4, pp. 499-518, 2003.