DECOR: Distributed construction of load balanced routing trees for many to one sensor networks

Many sensor networks suffer from the energy hole problem which is a special case of load imbalance caused by the funnelling effect of many sensor nodes transmitting their data to a single, central sink. In order to mitigate the problem, a balanced routing tree is often required and this can be constructed with either a centralised or distributed algorithm. Distributed solutions are typically less effective but are significantly cheaper than centralised solutions in terms of communication overhead and they scale better for the same reason.In this paper we propose a novel distributed algorithm for the construction of a load balanced routing tree. Our proposed solution, Degree Constrained Routing, is unique in that it aims to maximise global balance during construction rather that relying on rebalancing an arbitrary tree or only maximising local balance. The underlying principle is that if all nodes adopt the same number of children as each other while the routing tree grows, then the final tree will be globally balanced. Simulation results show that our algorithm can produce trees with improved balance which results in lifetimes increased by up to 80% compared to the next best distributed algorithm.