L-exclusion algorithm for mobile Ad Hoc networks

Abstract

With the proliferation of portable computing platforms and small wireless devices, ad hoc mobile networks have received a substantial attention from the research community as a means for providing data communications among devices regardless of their physical locations. Much of the research attention has spanned the design and standardization of routing, medium access control protocols, wireless channel allocation algorithms, protocols for broadcasting and multicasting. Instead, this thesis work addresses the [-Exclusion problem for mobile ad hoc networks. The [- Exclusion problem, a generalization of distributed mutual exclusion problem, involves a group of processes, each of which intermittently requires access to one of [ identical resources or pieces of code called the critical section (CS). However, characteristics of mobile ad hoc networks, such as concurrent and unpredictable topology changes due to arbitrary mobility pattern of nodes, shared broadcast channel, dynamic wireless link formation and removal, network partitioning and disconnections, location dependent errors, highly variable message delay, bandwidth, energy and battery power limitations, make devising of any distributed solution to the [-exclusion problem in such networks very challenging and exciting. In literature, few token-based solutions to this problem are available. Nevertheless, these solutions suffer from poor failure resiliency, as these do consider failures associated with mobile ad hoc networks, such as loss or regeneration of tokens, crash or sudden recovery of nodes. This research work presents a consensus-based mobility-aware [-exclusion (LE) algorithm that operates asynchronously and copes explicitly with arbitrary (possibly concurrent) topology changes associated with such networks. The algorithm is fault-resilient in the sense that it can tolerate loss of messages, link changes or failures, sudden crashes or recoveries of at most [-I mobile nodes. The algorithm is based on collection enough consensuses for a mobile node intending to enter CS, and uses diffusing computations for this purpose. The algorithm requires nodes to communicate only with their current neighbors, making it well-suited for use in mobile ad hoc networks. This thesis presents proofs of correctness to exhibit the fairness of the algorithm. This work is concluded by an extensive simulation study considering several performance metrics that significantly II impact the behavior of such an algorithm in various ad hoc settings. Simulation study demonstrates that the proposed algorithm is quite effective to variety of operating conditions, and is highly adaptive to frequent and unpredictable topology changes due to loss of messages, link changes or failures or formations, sudden crashes or recoveries of at most 1-1 mobile nodes, under different mobility settings. This research work also presents a simulation-based performance comparison between the proposed l-exclusion (LE) algorithm and the k-Reverse Link (KRL) algorithm. Simulation results sdemonstrate that our algorithm performs favorably at high crash/merge rate in terms of Message Overhead, particularly when nodes are mobile. The performance of our algorithm in terms of Average Waiting Time per CS Entry is remarkable, particularly under mobility and vulnerability. Simulation results also 'shows that the l-exclusion algorithm always allows more than 90% of nodes intending to enter CS to access and to control CS under a variety of vulnerable mobility settings, where at most I-I node(s) ,can crash independently or concurrently, and/or crashed node(s) may recover from failures.