Research On Loading Balance Algorithm Based On Tree In Wireless Sensor Networks

With the development of sensor technology, wireless communication technologyand distributed information processing technology, wireless sensor network(WSN)develops rapidly and becomesan emerging subject of computer science. It has avery broad prospect, and has been applied to the military, commercial, health,environment and other fields.In this paper, we focus on the problem of data collection. Our goal is to maximizethe network lifetime. On the base of analyzing a large number of network protocols, westudy different data collections, build different models and present two algorithms.Finally, we check the performance of the algorithm through the experiments. This papercontains two parts mainly:①For accurate data collection, we propose an algorithm(LBAPDG) of networkloading balance in the case of unknowing the geographical position of the nodes. Itsgoal is to maximize the network lifetime by solving a problem perfectly. The problem isa NP complete problem to construct a spanning tree. It issolved by using a polynomialalgorithm. The algorithm constructs a spanning tree with the most children through theSink node. On the basis of this tree, LBAPDG translates the nodes from a heavy loadtree to a light one using the search-based method. The network reaches the balance fromthe top to the lower such that it cannot influence the top nodes when moving the lowernodes. It runs on a subtree. The tree reaches the balance layer by layer.②For the problem which cannot be solved by the LBAPDGalgorithm, we proposea LBACDG algorithm,the goal of which is to maximize the network lifetime. Accordingto the characteristics of dense network and using the relationship between thetransmission power and the received power, the algorithm simplifies the network model.It builds a spanning tree whose load is balancedby the greedy strategy. LBACDGtransfers the nodes from a heavy load tree to a light one using the recursive methodsuntil the tree is balanced. Different from LBAPDGalgorithm it uses the depth firstsearch to transfer both the nodes and the subtrees. The greedy strategy at the beginningcan reduce the depth and time of the recursiveness and the complexity of the algorithm.