Design and Analysis of Efficient Load Balancing and Congestion Avoidance Methods for Ad Hoc Networks

Abstract

Ad hoc networks are infrastnictureless and lack any central administration. Thus all basic tasks such as connection establishment, dialogue control, routing or network control require distributed participation. Mobile nodes add to scarcity of resources and therefore, efficiency and optimisation is the key to success of such applications. Routing is the most basic, yet an important task for any ad hoc operation. Most single path routing solutions use the shortest path approach for path establishment, as they provide efficient solutions for low load conditions. However, in situations of high load, these solutions tend to overload central nodes of a network, which creates a load asymmetry in the network. Multi path routing is considered as advantageous over single path routing, however, these benefits come at a cost and therefore, a trade-off is required between number of alternate paths and benefits accrued from them. Load balancing is applied to applications involving high traffic in a network, to prevent the worst effects of shortest path methods such as congestion, packet drops and high latency. The major work in this thesis is on design and analysis of efficient load balancing and congestion avoidance methods and metrics. newlineA mathematical model for congestion detection in a network is presented. This model is based on measurement of latency, jitter and data loss values across the network. The said model is an alternate to queue based models and more reliable in comparison. A metric called Congestion Index (CI) is also presented which measures severity of congestion on different links and paths. It is desirable to have paths with low CI values and a cut-off value of three is considered for a path to be useful. Based on CI metric, a dynamic congestion avoidance scheme is also proposed. Results have been adequately tested in Glomosim which proves the efficacy of the scheme. Supporting tools have been self created, wherever necessary. A mini simulator has also been developed. This simulator provides the capability...