Research On Energy-Efficient Data Gathering In Wire-less Sensor Networks

Wireless sensor network (WSN) is a new hot-spot in current research, and it has broad application foreground. In WSN, the nodes have some characteristics such as limited communication ability, limited computa-tional ability, limited storage space and limited energy, etc. The number of the nodes is large. Moreover, the nodes are difficult to be replaced since they are often deployed in remote or inaccessible environments. Data gathering is one of the most important operations in the network, which means that the data sensed by nodes should be transmitted to the sink for further processing.In the process of data gathering, an important issue is to conserve the limited energy of the nodes and extend their lifetime. This dissertation researches how to find some ways to effectively decrease energy con-sumption of the nodes and the network delay, and improve the fault-tolerance and scalability of the network. The main contributions of this dissertation are showed as follows.(1) A tree-based algorithm for data gathering without aggregation is proposed. First, the problem of constructing an energy-balanced data gathering tree is proved to be NP-complete. Then, an approximation al-gorithm MITT is proposed. The algorithm uses coloring to achieve bal-anced energy consumption among nodes with different energies by bal-ancing the descendant numbers of the nodes. The approximation ratio of the algorithm is proved to be Q(logn/loglogn), where n is the number of nodes in the network. Simulation results show that, by comparing with the current best algorithm, MITT can effectively extend the network life-time in different size of networks.(2) An energy-balanced tree-based algorithm that can constrain the data gathering delay for data gathering with aggregation is proposed. The problem of constructing an energy-balanced and delay-constrained data gathering tree is NP-complete. Based on the basic characteristic of tree that a cycle can be made when an extra edge is added to the tree and the degrees of the two end nodes of the edge should increase by 1, and vice versa, an approximation algorithm MILD is proposed. The algorithm achieves balanced energy consumption among nodes by balancing the degrees of the nodes in the tree according to their energies under limited tree height, and it achieves an approximation ratio of Q(\ogn). Simulation results show that, by comparing with the current best algorithm, MILD can effectively balance the energy consumption of the nodes in different size of networks under constrained delay.(3) A LT-codes based protocol for mobile data gathering is proposed. In a network that a fixed sink cannot be deployed, source nodes should disseminate their data to a subset of other nodes for storage so as to avoid the data loss because of the death of source nodes. A decentralized pro-tocol LTSIDP is proposed, which does not need the supports of geo-graphical information and global information of the network. The proto-col adopts an overhearing-based data forwarding mechanism to dissemi-nate the data with unequal probability, and makes each node store the data based on LT-codes. The protocol has high scalability. Theoretical analyses and experiments show, by comparing with the current best pro-tocol, LTSIDP achieves lower energy consumption in the network. Moreover, LTSIDP can make a mobile sink recover all source data even if it visits fewer nodes in the network.(4) A LT-codes based mobile data gathering protocol that can achieve the minimum data dissemination delay is proposed. First, the ef-fects of node's distribution and node's communication mode on the probability that a node should broadcast a packet are analyzed. Then, an adaptive probability broadcast-based data dissemination mechanism is proposed. Based on the mechanism, a decentralized protocol that does not need the supports of geographical information and global information of the network is proposed. Theoretical analyses and experiments show, by comparing with the current best protocol, APBDP does not require that each node has a storage space proportional to the network size, and it can finish the process of rapid data dissemination and coded storage with lower energy consumption.In a word, the dissertation performs an in-depth study on the data gathering of wireless sensor networks. Moreover, several energy-efficient data gathering protocols with higher performance are proposed. There-fore, the research of the dissertation has strong theoretical and practical significances.