可用於大型無線感測網路之節能式空間關聯性資料收集演算法

Energy Efficient In-Network Spatial-Correlated Data Gathering Algorithm in Large Scale Wireless Sensor Networks

顏志安(Jhih-An Yan)

指導教授 ： 黃俊龍

國立交通大學/資訊學院/資訊科學與工程研究所/碩士(2009年)

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

摘要

由於無線感測網路具有輕巧以及可大量佈建的特質，應用無線感測網路來做環境監測以及災害預防已成為一種可預見的趨勢。目前的無線感測器受限於能源的容量，以及大型無線感測網路中能源替換的困難度，其網路的使用時間相當有限，因此如何減少感測器的能源消耗延長無線感測網路的使用時間是許多研究人員相當關心的問題。先前有許多研究觀察到溫度，濕度等自然讀數都具有空間關聯性，即在空間上擁有相近位置的無線感測器其感測讀數亦會相近，根據此一特性可以把讀數相近的集合成一群集，每一群集僅由一個感測器負責回報讀數降低網路中所需傳輸的訊息數量進而達到延長網路使用時間的效果。

在建立群集的過程中，感測器之間必須互相交換訊息或是由一主機負責收集網路中的資料。由於此一過程會增加感測器額外的負擔，因此如何降低建立群集時的能源消耗以及有效率的調整群集的結構，為這類群集演算法的重要問題。一些典型的分散式或集中式演算法針對資料之間的空間關聯性提出了建立群集的方式，但是在這些演算法中，
對於群集的結構調整以及演算法的可擴充性都沒有辦法有效的解決。有鑑於此，我們分析群集的特性並且設計了一個In-Network的群集建立演算法(ISCDG)，首先定義回傳訊息和接收者之間的空間關聯性，並且對兩個具有高度空間關聯性的群集進行合併的檢查，由於我們的演算法僅在網路中局部進行且可以有效率調整群集的結構，因此可以用於大型的無線感測網路。在實驗的章節，我們比較了我們的演算法與典型的分散式以及集中式演算法之間的效能差異，也說明了In-Network的做法的確可以增加演算法的可擴充性。

關鍵字

無線感測網路 ； 空間關聯性群集 ； 資料收集 ； 節能

並列摘要

Many popular applications are developed on wireless sensor networks such as environment monitoring and disaster detection. The first characteristic of these applications is that sink periodically gather data from entire wireless sensor network, it makes the battery-powered sensors run of their energy fast. The other characteristic is that some error is accepted by user. According to these characteristics, an energy efficient way to gather approximately result can be a solution to extend lifetime of wireless sensor networks.

Some clustering algorithm were published to cluster sensor nodes, and let cluster heads are in charge of reporting
sensing data to reduce the total number of reporting messages. These clustering algorithm consider the spatial
correlation of sensing data to provide an user-tolerable approximately result. But the energy cost on the process of
clustering and cluster maintenance may add some overhead to entire WSN. The other problem is that spatial correlation
can not be used effectively since energy of sensor device is limited, they can not communicate with close nodes frequantly. In order to solve this problem, we analysed the spatial correlation between clusters, and design an in-network algorithm(ISCDG) to provide a better clustering result. A simple mechanism to do cluster maintenance is also provided in our algorithm.

Finally, we evaluate our work with different size of network, and show that the scalability of ISCDG is good.
That means ISCDG can used on large scale wireless sensor network.

並列關鍵字

wireless sensor networks ； spatial correlation ； data gathering ； clustering ； energy efficient

參考文獻

[2] C. C. Hung, W. C. Peng, Y. S. H. Tsai, and W. C. Lee. Exploiting spatial and data correlations for approximate data collection in wireless sensor networks. In 2nd

International Workshop on Knowledge Discovery from Sensor Data, 2008.

[3] C. Intanagonwiwat, R. Govindan, and D. Estrin. Directed diffusion: a scalable and robust communication paradigm for sensor networks. In Proceedings of the 6th annual

[4] Y. Kotidis. Snapshot queries: towards data-centric sensor networks. In Proceedings of 21st International Conference on Data Engineering, 2005.

[6] S. Madden, M. J. Franklin, J. M. Hellerstein, and W. Hong. Tag: a tiny aggregation service for ad-hoc sensor networks. In Proceedings of the 5th symposium on Operating