The Problem Of Data Aggregtion Routing In Wireless Sensor Networks

Wireless sensor networks are composed of a large number of autonomous sensor nodes which consist of sensing, data processing, and communicating components. They are a new kind of network for information collection and processing and can be widely used in many application areas, such as military, health, security, environment protection, industry, algriculture, space explore, and disaster salvage. Therefore, they attract attention from both industry and academia. One of the key challenges in wireless sensor networks is how to improve the enery efficiency. In-network processing is a common technique for energy conservation and combining data aggregation with data routing is the main method for in-network processing. This paper aims at the energy efficiency in wireless sensor networks and studies the problem of data aggregation routing. The research aspects in this paper are as follows.(1) We first study the energy consumption at each sensor node when using different data aggregation techniques. By analyzing the conclusions from other researchers and our own experiments, we find that it is needed to jointly consider of both the aggregation and transmission costs in the problem of minimum energy data aggregation routing if using data aggregation scheme in data gathering.(2) For the problem of minimum energy data aggregation routing, we formulate it first and then present a randomized algorithm termed Minimum Fusion Steiner Tree (MFST) that jointly optimizes over both the aggregation and transmission costs to minimize overall energy consumption. MFST is proved to achieve a routing tree that exhibits 4/5log(k+1) approximation ratio to the optimal solution, where k is the number of sources.(3) To improve the performance of MFST when data correlation is low, we propose an enhanced data aggregation routing algorithm termed Adaptive Fusion Super-Tree (AFST), a routing scheme that can adaptively adjust whether aggregation shall be performed by evaluating whether aggregation is beneficial to the network based on aggregation/transmission costs and data correlations. AFST dynamically assigns aggregation decisions to routing nodes during the route construction process, so it can save more energy in data gathering process and prolong the system lifetime. Analytically and experimentally, we show that AFST outperforms MFST especially in the cases of low data correlation and high aggregation cost. Furthermore, we find that AFST can also be used as an aggregation-benefit-based clustering algorithm.(4) Considering the variation of network structure, we propose an online algorithm based on AFST. AFST-online can surport the dynamic arrival and departure of sources and can be easily implemented in a distributed manner requiring only localized information. Analytically and experimentally, we show that the online algorithm promises extremely small performance deviation from the offline version and the performance of AFST-online under the worst case is bounded by the difference of MFST and SPT.