Abstract

In this thesis we study the load distribution and load balancing problem in wireless ad hoc networks. Using a discrete unit disk graph model of the network, we analyze the distribution of load induced by greedy routing in the network with an all-to-all communication pattern between the nodes. We derive an estimate for average load of the nodes in the network. We also calculate the expected load of a node as a function of its geometric coordinates in the network. We express the actual load of a node in the network as a random variable and obtain the parameters of this random variable. Using this random variable we derive an estimate for the maximum load of the nodes in the network. Our result is more accurate than previous studies which were based on a continuous model of the network. We analyze how different parameters of the network, i.e., number of nodes, transmission range, and different routing algorithms can affect the parameters of the load distribution. We give a technique to reduce the variance of the load distribution, and hence decrease the maximum load of the nodes in the network. Our technique can be combined with any location-based routing algorithm. We also introduce a class of algorithms that improve the maximum expected load of nodes in the network. Experimental results show that our algorithms outperform other existing algorithms in reducing the maximum load of the network