International Journal of Wireless and Microwave Technologies (IJWMT)
IJWMT Vol. 5, No. 4, 26 Jul. 2015
Cover page and Table of Contents: PDF (size: 673KB)
Dynamic Request Set based Mutual Exclusion Algorithm in MANETs
Full Text (PDF, 673KB), PP.1-14
Views: 0 Downloads: 0
Author(s)
Index Terms
Resource Allocation, Mobile Ad Hoc Networks (MANETS), Distributed Algorithms, Distributed Computing, Mutual Exclusion
Abstract
Mutual Exclusion (ME) problem involves a group of processes, each of which intermittently requires access to the only resource present in the environment. Handling ME problem becomes difficult due to the dynamic nature of the ad hoc environment. This paper presents a token-based solution to ME problem in the mobile ad hoc environment. The proposed token based algorithm is sensitive to link forming and link breaking and thus is suitable for MANET. The algorithm uses the concept of dynamic request set (DRS). As the request set is dynamically updated, the average size of request set is reduced resulting in less number of messages exchanged per critical section. The algorithm satisfies mutual exclusion, starvation freedom, and freedom from deadlock. The present algorithm has been compared with DRS based ME algorithms for static distributed systems. The results show that the concept of DRS in MANETs can be successfully used. Token loss problem has also been handled separately in the present exposition.
Cite This Paper
Ashish Khanna, Awadhesh Kumar Singh, Abhishek Swaroop,"Dynamic Request Set based Mutual Exclusion Algorithm in MANETs", IJWMT, vol.5, no.4, pp.1-14, 2015. DOI: 10.5815/ijwmt.2015.04.01
Reference
[1]Kshemkalyani AD, Singhal M. Distributed Computing Principles, Algorithms, Systems. Cambridge University Press; 2009.
[2]Dijkstra E W. Hierarchical Ordering of Sequential Processes. Acta Informatica 1971; 115-138.
[3]Chandy KM, Mishra J. The drinking philosopher's problem. ACM transactions on programming languages and systems, Vol. 6, no.4, 1984; 632-646.
[4]Swaroop A. Efficient Group Mutual Exclusion Protocols for Message Passing Distributed Computing System doctoral diss., NIT, Kurukshetra, India; 2009.
[5]Weigang W, Jiannong Ca, Jin Y. A Fault Tolerant mutual exclusion algorithm for mobile ad hoc networks, Pervasive and Mobile Computing, Vol. 4, no. 1, 2008; 139-160.
[6]Suzuki I, Kasmi T. A distributed mutual exclusion algorithm. ACM transactions on computer systems, Vol. 13, no. 4, 1985; 344-349.
[7]Chang YI, Singhal M, Liu MT. A dynamic token-based distributed mutual exclusion algorithm. In the proceedings of the 10th annual international phoenix conference on computers and communications, 1991; 240-24.
[8]Singhal M. A heuristically-aided algorithm for mutual exclusion in distributed systems. IEEE transactions on computers, Vol. 38, no. 5, 1989; 651-662.
[9]Badrinath BR, Acharya A, Imielinski T. Structuring Distributed Algorithms for Mobile Hosts. Proceedings of the 14th International Conference Distributed Computing Systems, 1994; 21–28.
[10]Walter JE, Kini S. Mutual exclusion on Multi–Hop, Mobile Wireless Networks", Technical Report, Texas A&M University, College Station, TX 77843–3112 TR97–014.; 1997.
[11]Walter JE, Welch J, Vaidya NH. A Mutual Exclusion Algorithm for Ad Hoc Mobile Networks, Wireless Networks, Vol. 7, 2001; 585–600.
[12]Baldoni R, Virgillito A, Petrassi R. A Distributed Mutual Exclusion Algorithm for Mobile Ad Hoc Networks. Proceedings of the 7th IEEE International Symposium Computers & Communications, 2002; 539–544.
[13]Kakugawa H and Yamashita M. Self-Stabilizing Local Mutual Exclusion on Networks in which Process Identifiers are not Distinct, in proceeding of 21st symposium on Reliable Distributed Systems (SRDS), 2002; 202-211.
[14]Beauquier J, Datta AK, Gradinariu M, Magniette F. Self-Stabilizing Local Mutual Exclusion and Daemon Refinement, in Proceedings of 13th International symposium on Distributed computing DISC 2000; 223-227.
[15]Attiya H, Kogan A, Welch JL. Efficient and Robust Local Mutual Exclusion in Mobile Ad hoc Networks, IEEE Transactions on Mobile Computing, Vol. 9(3), 2010; 361–375.
[16]Kogan A. Efficient and Robust Local Mutual Exclusion in Mobile Adhoc Networks, Masters Research thesis, Technion- Israel Institute of Technology, Israel; 2008.
[17]Khanna A, Singh AK, Swaroop A.A Leader-Based k-Local Mutual Exclusion Algorithm Using Token for MANETs. J. Inf. Sci. Eng. 30(5), 2014; 1303-1319.
[18]Khanna A, Singh AK, Swaroop A. Token Based Group Local Mutual Exclusion Algorithm in MANETs.In: Proceedings of Intelligent Computing, Communication and Devices (ICCD), Advances in Intelligent Systems and Computing (Springer) 309, 2014; 105-113.
[19]Khanna A, Singh AK, Swaroop A. Token Based Group Local Mutual Exclusion Algorithm in MANETs. Recent Development in Wireless Sensor and Ad-hoc Networks: 978-81-322-2128-9; 2014.
[20]Wu AW, Cao J, Raynal M. A Generalized Mutual Exclusion Problem and Its Algorithm. AoxueLuo, Weigang Wu, In: International Conference on Parallel Processing, Vol. 42, 2013; 300-309.
[21]Tamhane SA, Kumar M. A Token Based Distributed Algorithm for Supporting Mutual Exclusion in Opportunistic Networks. Pervasive and Mobile Computing, Vol. 8(5), 2012; 795-809.
[22]Parameswaran M, Hota C. Arbitration-based Reliable Distributed Mutual Exclusion for Mobile Ad-hoc Networks. in Proceedings of Modelling & Optimization in Mobile, Ad Hoc & Wireless Networks, Vol. 11, 2013; 380-387.
[23]Mallikarjuna B, Saritha V, Puspalatha C. Fault Tolerant Resource Management with Mutual Exclusion Algorithm for Mobile Adhoc Networks. International Journal of Scientific and Research Publication, Vol. 2(4), 2012; 1-6.
[24]Karthik R, Gopinath B. Efficient Algorithms for Distributed Mutual Exclusion in Mobile Ad-hoc Network. Indian Journal of Computer Science and Engineering (IJCSE), Vol. 2(6), 2012; 873-884.
[25]Hosseinabadi G, Vaidya NH. Exploiting Opportunistic Overhearing to Improve Performance of Mutual exclusion in Wireless Ad Hoc Networks. in proceeding of Int. conf. on wired/wireless Internet Communications (WWIC), 2012; 162-173.
[26]Itriq M, Dbabat W, Sharieh P. Adaptive Dynamic Resource Synchronization Distributed Mutual Exclusion Algorithm, Journal of Theoretical & Applied Information Technology, Vol. 53(3), 2013; 392-401.
[27]Weigang W, Jiannong C, Yang J. A Fault Tolerant mutual exclusion algorithm for mobile ad-hoc networks. Pervasive and Mobile Computing Vol. 4(1), 2008; 139-160.
[28]Wu W, Zhang J, Luo A, Cao J. Distributed Mutual Exclusion Algorithms for Intersection Traffic Control. IEEE Transactions on Parallel and Distributed System Vol. 26(1), 2015; 65-74.