Evaluation of dynamic tree-based data gathering algorithms for wireless sensor networks

One major challenge in sensor networks is to maximize network life under the constraint of extremely limited power supply. Thus, two important design issues of routing and data-gathering protocols are 1) minimizing energy consumption in sensor nodes and 2) adapting to node failures. This paper studies two tree-based data gathering protocols, based on distributed versions of shortest path tree (SPT) and maximum leaf tree (MLT) algorithms. Furthermore, the two distributed algorithms are extended to be dynamic and robust. A localized tree-reconstruction scheme, localized flooding algorithm, is added to handle joining and leaving (death) of sensor nodes. Accurate energy consumption has been modeled for both leaf-nodes and intermediate nodes, when sending and receiving control and data packets. The resulting dynamic algorithms are fast to adapt network changes. Performance is evaluated through detailed simulation. Comparing with MLT, due to its simplicity and smaller number of control message exchanges, SPT achieves better energy efficiency and less delay in tree constructions, data transmissions, and dynamic tree reconstructions