JISE


  [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20]


Journal of Information Science and Engineering, Vol. 30 No. 5, pp. 1303-1319


A Leader-Based k-Local Mutual Exclusion Algorithm Using Token for MANETs

ASHISH KHANNA1, AWADHESH KUMAR SINGH2 AND ABHISHEK SWAROOP3
1MAIT, Delhi, 110085 India
2NIT, Kurukshetra-136119, Haryana, India
3Galgotias University
Greater Noida, U.P. India
E-mail: ashishk746@yahoo.com; aksinreck@rediffmail.com; asa1971@gmail.com

 

    The k-local mutual exclusion is a generalization of local mutual exclusion problem introduced by Attiya et al.. In k-local mutual exclusion, it is assumed that the k identical copies of a resource are shared among the geographically close nodes. The paper proposes a solution to the k-local mutual exclusion problem in MANETs. The algorithm uses a leader-based approach and the leader is equipped with a token. It is suited to handle mobility that triggers the dynamism in topology of ad hoc networks. The algorithm satisfies safety, starvation freedom and l-deadlock avoidance properties. The best case message complexity of our algorithm is O(1) whereas the worst case message complexity is O(N). To the best of our knowledge, it is the first algorithm to solve k-local mutual exclusion problem in MANETs. The solution to token loss problem is also included in the present exposition.

 

Keywords: ad hoc network, local mutual exclusion, neighborhood, resource allocation, distributed system

  Retrieve PDF document (JISE_201405_02.pdf)