Research On Routing Optimization Problems In Wireless Data Aggregation Sensor Networks

Recently, the advances in Micro-Electro-Mechanical-Systems (MEMS) technol-ogy, wireless communications, and digital electronics have enabled the development of low-cost, low-power sensor motes that are widely deployed. A wireless sensor mote consists of sensing, data processing and communicating components and sensor motes cooperate as an Ad-hoc network.In wireless sensor networks, most applications are based on data processing and analyzing. So data collection is one of the most basic operations. During to the char-acters of sensor networks, the spanning tree is usually used as a routing structure in wireless sensor networks. However, in data collection trees, nodes closer to the sink node need to receive and forward more packets. It will cause high energy consumption and low network lifetime, which is also called the energy hole phenomenon. However, in some applications, the sink node does not need to collect all packets from every node. To alleviate this problem, some divisible functions (e.g., SUM, MAX, top-k, etc.) are used to fuse data packets and to eliminate redundant transmissions. In this article, we focus on data aggregation tree structures. We study the network lifetime problem, net-work reliability problem and network delay problem in data aggregation networks.(1) In wireless sensor networks, the spanning tree is usually used as a routing structure to collect data. In some situations, nodes do in-network aggregation to reduce transmissions, save energy and maximize network lifetime. Because of the restricted energy of sensor nodes, how to build an aggregation tree of maximum lifetime is an im-portant issue. It has been proved to be NP-complete in previous works. As shortest path spanning trees intuitively have short delay, it is imperative to find an energy-efficient shortest path tree for time-critical applications. In this paper, we first study the prob-lem of building optimal shortest path aggregation trees (in terms of lifetime) in wireless sensor networks. We show that when restricted to shortest path trees, building optimal aggregation trees can be solved in polynomial time. We present a centralized algorithm and design a distributed protocol for building such trees. Simulation results show that our approaches greatly improve the lifetime of the network and are very effective com-pared with other solutions. We extend our discussion to networks without aggregation and present interesting results.(2) Tree-based routing structures are widely used to gather data in wireless sen-sor networks. Along with tree structures, in-network aggregation is adopted to reduce transmissions, to save energy and to prolong the network lifetime. Most existing works that focus on the lifetime optimization for data aggregation do not take the link qual-ity into consideration. In this paper, we study the problem of Maximizing Reliability of Lifetime Constrained data aggregation trees (MRLC) in WSNs. Considering the NP-completeness of the MRLC problem, we propose an algorithm, namely Iterative Relaxation Algorithm (IRA), to iteratively relax the optimization program and to find the aggregation tree subject to the lifetime bound with a sub-optimal cost. To adapt to the distributed nature of the WSNs in practice, we further propose a Prufer code based distributed updating protocol. Through extensive simulations, we demonstrate that IRA outperforms the best known related work in term of reliability.(3) As wireless sensor nodes are usually battery powered and need to last a long time after deployment, it is important to cut unnecessary energy consumption. In-network aggregation functions and low duty cycle protocols are widely used to bridge the growing gap between the energy limitation and network lifetime. The upcoming problem is that aggregation delay could be significantly high in low duty cycle net-works. In this paper, we study the problem of minimizing aggregation delay in low duty cycle sensor networks. As the NP-hardness of the problem, we first introduce Binomial Tree (BT), which presents the optimal structure for networks with full con-nectivity. For networks with arbitrary topology, we propose an algorithm namely Bi-nomial Forest (BF) with the worst case delay performance of 20PT+2(?)2nP, where OPT is the optimal delay, n is the number of nodes and P is the duty cycle period. We also extend our discussion to networks with unreliable links. Through extensive simu- lations and implementations, the aggregation delay of BF is close to the optimum and BF outperforms existing data collection strategies in terms of aggregation delay.