無線感測網路偵測覆蓋空洞機制之研究

無線感測網路中的應用已被廣泛使用在很多領域上，包括環境的監控、災難的救護及戰場監測等等。在無線感測網路的隨機初期佈建上，由於無法保證會有完全的覆蓋，加上佈建後感測器會因節點的電力耗盡與被外力破壞等因素，很難以避免在無線感測網路監控區域中會有覆蓋空洞的問題，而這些覆蓋空洞的存在，也因此會影響無線感測網路的效能在很多層面上，因此在無線感測網路，需要每一節點皆能執行簡單又有效的覆蓋空洞偵測方法，以提供無線感測網路所需的覆蓋品質，及確保網路之可靠性。基於此，因此在本論文中，我們提出以計算幾何為基礎，使用簡單而且有效率的覆蓋空洞偵測機制，經由此一機制可以有效偵測出存在於監控區域中的覆蓋空洞，在我們所設計協定中，藉由每一節點收集兩倍感測距離內相鄰節點的資訊並使用三角形及多邊形幾何法來找出此一節點附近的空洞，此一分散式偵測演算法亦可以應用在不同形狀與大小的監控區。另外在我們所提出的偵測演算法經所發展出理論定理證明，說明此演算法是完全正確的，並透過ns-2的模擬，結果顯示我們的覆蓋空洞偵測協定演算法在偵測時間上與能量消耗上，比其他方法還要好。

關鍵字

分散式；空洞偵測；無線感測網路；覆蓋空洞

並列摘要

Wireless sensor networks have been employed in many applications, such as environment monitoring, disaster relief operation and battlefield surveillance. However, in initial random deployment there is no guarantee of complete coverage. Besides, in the post deployment sensor nodes may fail due to power depletion, or physical destruction. Therefore, coverage holes problem can hardly be avoided in wireless sensor networks. The presences of holes have an influential impact on the performance of the sensor network at many levels. Thus, sensor nodes must execute simple and efficient coverage hole detection mechanism for providing the required QoS of coverage and ensuring network reliability. Accordingly, in this dissertation we propose the computational geometry based distributed coverage hole detection algorithm using both triangular and polygon methods to find out the holes. Detection of the holes are done using simple and efficient geometric methods taking only one and two-hop neighbors of each node to detect the hole around it and therefore requires less computation time. Global view of the coverage hole detection is proposed taking local information of the nodes. The algorithm is completely distributed and can also detect the coverage holes irrespective of any shape or size of the monitoring region. We also make proofs for each of the lemmas used in the construction of the algorithms. The algorithms are shown to be theoretically correct. Performance evaluation of our algorithm shows that the hole detection time and energy consumption due to hole detection outperforms over similar hole detection algorithms.

並列關鍵字

Wireless sensor networks ； hole detection ； coverage hole ； Distributed

參考文獻

[3] Haiyun Luo, Fan Ye, Jerry Cheng, Songwu Lu, and Lixia Zhang, “Two-tier data dissemination model for large-scale wireless sensors networks”, In Proceedings of ACM/IEEE MobiCom’02, September 2002

[4] Fan Ye, Gary Zhong, Songwu Lu, and Lixia Zhang, ”Gradient broadcast: A robust data delivery protocol for large scale sensor networks”, In IPSN, April 2003

[5] Brad Karp and H. T. Kung, GPSR: Greedy, “perimeter stateless routing for wireless networks”, In Proceedings of the ACM/IEEE MobiCom’2000, pp. 243–254, 2000

[6] John Heidemann, Fabio Silva, and Deborah Estrin, “Matching data dissemination algorithms to application requirements”, In Proceedings of the ACM SenSys ’03, Nov. 2003

[7] David Braginsky and Deborah Estrin, “Rumor routing algorithm for sensor networks”, In 1st ACM WSNA ’02, Sep. 2002

國際替代計量

無線感測網路偵測覆蓋空洞機制之研究

未授權

主題瀏覽