SREE-Tree: Self-reorganizing energy-efficient tree topology management in sensor networks

The evolving applications of Information and Communications Technologies (ICT), such as smart cities, often need sustainable data collection networks. We envision the deployment of heterogeneous sensor networks that will allow dynamic selfreorganization of data collection topology, thus coping with unpredictable network dynamics and node addition/ deletion for changing application needs. However, the self-reorganization must also assure network energy efficiency and load balancing, without affecting ongoing data collection. Most of the existing literature either aim at minimizing the maximum load on a sensor node (hence maximizing network lifetime), or attempt to balance the overall load distribution on the nodes. In this work we propose to design a distributed protocol for self-organizing energy-efficient tree management, called SREE-Tree. Based on the dynamic choice of a design parameter, the in-network selfreorganization of data collection topology can achieve higher network lifetime, yet balancing the loads. In SREE-Tree, starting with an arbitrary tree the nodes periodically apply localized and distributed routines to collaboratively reduce load on the multiple bottleneck nodes (that are likely to deplete energy sooner due to a large amount of carried data flow or low energy availability). The problem of constructing and maintaining optimal data collection tree (T_opt) topology that maximizes the network lifetime (L(T_opt)) is an NP-Complete problem. We prove that a sensor network running the proposed SREE-Tree protocol is guaranteed to converge to a tree topology (T) with sub-optimal network lifetime. (L(T)) such that 1/L(T) - 1/L(T_opt) < (ε + Q), where ε is the flexible design parameter and Q is a factor that can depend on system configuration. With the help of experiments using standard TinyOS based sensor network simulator TOSSIM, we have validated that SREE-Tree achieves better performance as compared to state-of-the-art solutions, for varying network sizes.