Distributed Load Balancing in Many-To-One Wireless Sensor Networks

A typical sensor network is conceived as being a very large collection of low-powered, homogeneous nodes that remain static post-deployment and forward sensed data to a single sink via multi-hop communication. For these types of networks there is an inherent funnelling effect whereby the nodes that can communicate directly with the sink must collectively forward the traffic of the entire network and therefore these nodes use more energy than the other nodes. This is known as the energy hole problem because after some time, these nodes deplete their batteries and leave an energy hole cutting the sink off from the network.In this thesis two new routing protocols are proposed that aim to maximise load balancing among these most critical nodes in order to maximise lifetime. They are the first fully distributed routing protocols that are designed to generate a load balanced routing tree to mitigate the energy hole problem. The results show that the better performing of the two is capable of creating a highly balanced tree at the cost of a small increase in latency.Although there have been other fully distributed protocols that aim at a similar form of load balancing, it is proven that the approach they take cannot guarantee perfect balance among the most critical nodes even in unrealistically generous scenarios. This suggests that they are not well suited to that task and the simulation results show that the novel protocols proposed in this thesis outperform the best of the alternatives.Before these protocols are proposed, the absolute reception-based blacklisting routing strategy is shown to be more energy efficient than previously thought and indeed more efficient than the strategy that has previously been considered optimal. This result is used to strongly justify the use of the unit disk graph model in simulations of sensor networks. Additionally, the relay hole problem in sensor networks is analysed for the first time.