大範圍無線感測網路下分散式資料壓縮收集演算法

Distributed Compressive Data Aggregation in Large-Scale Wireless Sensor Networks

蔡宗益(Tsung-Yi Tsai)

指導教授 ： 孫敏德

國立中央大學/資訊電機學院/資訊工程學系/碩士(2012年)

摘要

最近幾年，壓縮式取樣技術(compressive sampling theory)正被廣泛地使用在
無線感測網路的資料收集應用上。藉由結合壓縮式取樣技術和路由路徑(routing
path)，有些研究提供了集中式的演算法來最小化整體網路的資料傳輸。然而這些
演算法通常需要完整的網路拓樸資訊和複雜的運算來取得最佳解。因此，當網路
的拓樸變動時，這些集中式演算法往往需要耗費許多的傳輸來重建整個路由路
徑。在這篇論文，我們提出了第一個分散式演算法來解決這個問題。我們首先介
紹兩個分散式路由路徑建構演算法來算建立路由路徑。接著，我們發表一個最小
化區域資料傳輸演算法來減少整體網路的資料傳輸量。模擬結果顯示出我們的演
算法所耗費的建置成本遠低於集中式演算法。

關鍵字

資料收集 ； 無線感測網路

並列摘要

As compressive sampling theory has been extensively used for data aggregation
in wireless sensor network, some researches provide a centralize protocol that can
minimize the data traffic in the network through the combination of routing and
compressive sampling. However, these protocols require the entire network topology
information to compute the optimal solution. As a result, when the network
environment is not stable, these protocols incur too much overhead. In this thesis, we
investigate the decentralized scheme that can efficiently construct the routing path for
compressive data aggregation. We first propose two distributed algorithms, namely
MRT and MAT, to construct the routing path for compressive data aggregation. After
works, an adjustment algorithm is proposed to locally redirect the data flow and
further minimize the data traffic. The simulation results indicated that the construction
overhead of our approaches is much lower than the centralize protocol.

並列關鍵字

Compressive Data Aggregation ； Wireless Sensor Networks

參考文獻

[1] R. Szewczyk, A. Mainwaring, J. Polastre, J. Anderson, and D. Culler. ”An

analysis of a large scale habitat monitoring application,” In Proc. of ACM

Estrin, ”A wireless sensor network for structural monitoring,” In Proc. of ACM

[3] C. W. Chen and Y. Wang. ”Chain-type wireless sensor network for monitoring

long range infrastructures: architecture and protocols,” International Journal