在使用資料匯集和可調整傳輸範圍機制的感測網路中建立最大生命週期資料收集樹

Constructing Maximum-lifetime Data Gathering Tree in Sensor Networks with Data Aggregation and Adjustable Transmission Ranges

陳威宇

指導教授 ： 林華君

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

摘要

在現今的感測網路應用下，進行資料收集時，節點對節點進行不使用Acknowledgement的傳輸資料是可被接受的；因此各節點於設定好的資料收集樹中，所應該使用的傳輸能量等級為足夠能將資料送至資料傳輸樹中的父節點即可。在此篇論文所討論的網路環境為所有sensor都採用可調整機制且彼此能互不相同的傳輸能量等級。在此情況下探討如何建立最大生命週期的資料收集樹。在我們所討論的網路中，由sensor所收集的資料在傳往base station的過程中，於各sensor皆會使用資料匯集方法將各個sensor的資料進行彙整。
在2010年Wu et al. 率先於網路環境定義為所有sensor都採用相同且固定的傳輸能量等級的情況下，計算出屬於此情況之最佳資料收集樹的生命週期倒數的最小底限並提出使用tree approach的approximation algorithm。在此篇論文中，我們對更普遍的網路環境也就是所有sensor都採用可調整機制且能互不相同的傳輸能量等級的情況，同樣的計算出於此情況下最佳資料收集樹的生命週期倒數之最小底限並且提出了在適合此情況下使用之tree approach的approximation algorithm。

關鍵字

資料匯集 ； 可調整傳輸範圍 ； 感測網路 ； 資料收集樹

並列摘要

In sensor network applications where data collection is acceptable or sufficient, hop-by-hop acknowledgement is not required for data delivery. The power level of each node on a data gathering tree can be adjusted to be just high enough to reach its parent node. This paper studies the problem of constructing maximum-lifetime data gathering trees in sensor networks in which the power levels of sensors are heterogeneous and adjustable. In-network data aggregation is also employed to aggregate sensor data while they are being forwarded toward the base station. This paper derives an upper bound on the lifetime of the optimal data gathering tree. For a given initial tree, an algorithm is developed to construct a data gathering tree by iteratively rearranging the current tree and improving the lifetime. Simulations are performed to study the performance of the algorithm.

參考文獻

[2] K. Kalpakis, K. Dasgupta, and P. Namjoshi, “Efficient algorithms for maximum lifetime data gathering and aggregation in wireless sensor networks,” Computer Networks, Vol. 42, no. 6, pp. 697-716, Aug. 2003.

[3] N. Garg and J. K¨onemann, “Faster and simpler algorithms for multicommodity flow and other fractional packing problems,” in Proceedings of the IEEE Symposium on Foundations of Computer Science, pp. 300-309,Nov. 1998.

[4] Y. Xue, Y. Cui, and K. Nahrstedt, “Maximizing lifetime for data aggregation in wireless sensor networks,” Mobile Networks and Applications,vol. 10, no. 6, pp. 853-864, Dec. 2005.

[5] J. Stanford and S. Tongngam, “Approximation algorithm for maximum lifetime in wireless sensor networks with data aggregation,” in Proceedings of the Seventh ACIS International Conference on Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing (SNPD), pp. 273-277, June 2006.

[6] K. Kalpakis and S. Tang, “A combinatorial algorithm for the Maximum Lifetime Data Gathering and Aggregation problem in sensor networks,”in Proceedings of the International Symposium on a World of Wireless,Mobile and Multimedia Networks (WoWMoM), pp. 1-8, June 2008.