Maximum Lifetime Algorithm for Precise Data Gathering Based on Tree in Wireless Sensor Networks
Jun Sheng Liang · 2010
In multi-hop wireless sensor networks that contain a high density of nodes, precise data gathering makes that are close to the sink incur a heavier workload, which depletes their energy faster and can easily cause a hot spot that would shorten the network lifetime. The problem of constructing a tree that has a maximum lifespan is NP-complete. An algorithm called MAXLAT can be used to solve this problem without the need for the location of nodes. MAXLAT starts from a tree whose root has the largest number of children. The in the tree are classified into three subsets that go accordingly to their respective loads: nodes, sub-bottleneck nodes, and rich nodes. Next, the MAXLAT continues to transfer descendants of high-load to sub-trees of low-load by coloring. When MAXLAT is terminated, it constructs a tree in which bottleneck nodes carry a lighter load. Simulation results show that the tree achieved by MAXLAT has a longer lifetime than trees created by previous algorithms.