Trading Latency for Load Balancing in Many-to-One Wireless Networks

Wireless networks that combine a many-to-one traffic flow with multi-hop communication suffer from a funnelling effect that inevitably overburdens nodes closer to the base station. In sensor networks this is known as the energy hole problem. A routing protocol that constructs a shortest path tree exacerbates this problem by leaving some of the most critical nodes with more descendants than others and hence more relaying work to do. In this paper we propose a novel, fully distributed tree construction algorithm for building a load-balanced tree. Our algorithm, Degree Constrained Routing (DECOR), trades off latency for load balancing. We simulated the algorithm using a sensor network as an example. The results show that a small increase in latency, of less than 10%, can be sacrificed for a larger increase in balance of up to 80%. The lifetime of a sensor network using DECOR can be extended by up to 150% compared to the next best algorithm.