An Energy Efficient Algorithm for Distributed Mutual Exclusion in Mobile Ad-hoc Networks

Authors: Sayani Sil, Sukanta Das

Abstract:

This paper reports a distributed mutual exclusion algorithm for mobile Ad-hoc networks. The network is clustered hierarchically. The proposed algorithm considers the clustered network as a logical tree and develops a token passing scheme to get the mutual exclusion. The performance analysis and simulation results show that its message requirement is optimal, and thus the algorithm is energy efficient.

Keywords: Critical section, Distributed mutual exclusion, MobileAd-hoc network, Token-based algorithms.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1058559

References:

[1] G.Ricart And A. K Agrawala. An optimal algorithm for mutual exclusion in computer networks. In Commun.ACM, Jan. 1981.
[2] R. Baldoni and A. Virgilito. A token-based mutual exclusion algorithm for mobile ad-hoc networks. In Dipartimento di Informatica e Sistemistica, Universita di Roma La Sapienza, Viasalaria 113, 00198 Roma, Italia, Technical Report 28-01.
[3] A. Acharya B.R.Badrinath and T. Imielinski. Structuring distributed algorithms for mobile hosts ,. In Proc. of the 14th Intern. Conf. on Distr. Comp., 1994.
[4] P.J. Denning E.G. Co.man Jr. Operating systems theory, prentice-hall, new york. 1973.
[5] Mohsen Tolou Honary Hamid Shokrzadeh Farzad Tashtarian, A. T. Haghighat. A new energy-efficient clustering algorithm for wireless sensor networks. In IEEE, 2007.
[6] A. Arora H. Zhang. scalable self-configuration and self-healing in wireless networks. In in: Proceedings of the 21st ACM Symposium on Principles of Distributed Computing (PODC 2002), July 2002.
[7] P.B. Hansen. Operating system concepts, prentice hall, new york,. 1973.
[8] J. Welch J. E. Walter and N.Vaidya. A mutual exclusion algorithm for mobile ad-hoc networks. In accepted to the ACM and wareless networks journal special issue on Dialm papers, 2001.
[9] A. Silberschatz L. Peterson. Operating systems concepts, addson-wesley, new york. 1986.
[10] L. Lamport. Time, clocks, and the ordering of events in a distributed system,. In Communications of the ACM 21,, 1978.
[11] Mohd Fadlee A. Rasid M. Hossein Fotouhi Ghazvini, Maryam Vahabi and Raja Syamsul Azmir Raja Abdullah. Optimizing energy consumption in hierarchical clustering algorithm for wireless sensor networks. In IEEE, 2007.
[12] R. Oldehoeft M. Maekawa, A.E. Oldehoeft. Operating systems: Advanced concepts, the benjamin/cummings, menlo park, ca,. 1987.
[13] Hsiou Mien Lien amd Shyan-Ming Yuan. A new approach of coiistructiiig informatioii structure for mutual exclusioii in distributed systems. In IEEE, 1994.
[14] M.Maekawa. A N algorithm for mutual exclusion in decentralised system. In ACM Trans.Comput.Syst., May 1985.
[15] J. L. Welch N. Malpani, N. H. Vaidya. Distributed token circulation on mobile ad-hoc networks ,. In Technical report, Intel Corporation 505 E. Huntland Dr. Suit 550, Austin TX 78752.
[16] Mehmet Hakan Karaata Pranay Chaudhuri. An o(n1/3) algorithm for distributed mutual exclusion. In Journal of Systems Architecture, 1998.
[17] Neeraj Mittal Ranganath Atreya. A quorum-based group mutual exclusion algorithm for a distributed system with dynamic group set. In IEEE Transactions on parallel and distributed systems, Vol. 18, No. 10, OCT 2007.
[18] KERRY RAYMOND. A tree-based algorithm for distributed mutual exclusion. In ACM Transactions on Computer Systems, Vol. 7, No. 1,, February 1989,.
[19] Jean-Frederic Myoupo Romain Mellier. A clustering mutual exclusion protocol for multi-hop mobile ad hoc networks. In IEEE International Conference on Networks (ICON 2005), pp. 250-255, IEEE Press, 2005.
[20] E. Coyle S. Bandyopadhyay. An energy efficient hierarchical clustering algorithm for wireless sensor networks. In in: Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2003), San Francisco, California, April 2003.
[21] Sandeep Lodha and Ajay Kshemkalyani. A fair distributed mutual exclusion algorithm. In IEEE Transactions on Parallel and Distributed Systems, vol. 11, 2000.
[22] I. Suzuki and T. Kasami. A distributed mutual exclusion algorithm. In ACM TOCS, 1985.
[23] J.E. Walter and S. Kini. Mutual exclusion on multihop, mobile wireless networks. In Texas A and M Univ,College Section, TX 77843-3112, TR97-014, Dec 9 1997.
[24] H. Balakrishnan W.B. Heinzelman, A.P. Chandrakasan. Application specific protocol architecture for wireless microsensor networks. In IEEE Transactions on Wireless Networking, 2002.