Conference Paper2006Cited by 1

Distributed allocation of identical resources in mobile ad hoc networks

Salahuddin Mohammad Masum, Amin Ahsan Ali

2006 4th International Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks

IEEE, pp. 1–10

DOI: 10.1109/wiopt.2006.1666527URL

Abstract

This paper addresses the l—Exclusion problem for mobile ad hoc networks. The l—Exclusion problem, a generalization of distributed mutual exclusion problem, involves a group of processes, each of which intermittently requires access to one of l identical resources or pieces of code called the critical section (CS). In literature, few token—based solutions to this l—Exclusion problem are available. Nevertheless, these solutions suffer from poor failure resiliency, as these do not consider failures associated with mobile ad hoc networks, such as loss or regeneration of tokens, crash or sudden recovery of nodes. This paper presents a consensus—based mobility—aware l—exclusion (LE) algorithm that operates asynchronously and copes explicitly with arbitrary (possibly concurrent) topology changes associated with such networks. The algorithm can tolerate link changes or failures, sudden crashes or recoveries of at most l—1 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 paper presents a simulation study to demonstrate that the proposed algorithm, as compared to the k—Reverse Link (KRL) algorithm, is quite effective to variety of operating conditions, and is highly adaptive to frequent and unpredictable topology changes due to link changes or failures or formations, sudden crashes or recoveries of at most l—1 mobile nodes, under different mobility settings.

Keywords

  • distributed mutual exclusion
  • mobile ad hoc networks
  • topology change
  • consensus algorithms
  • asynchronous algorithms
  • failure resilience

CCDS Authors

Amin Ahsan Ali, PhD
Amin Ahsan Ali, PhD

Amin Ahsan Ali, PhD

  • Director, AI/ML Wing

Professor

Department of Computer Science and Engineering

Independent University, Bangladesh

Published at

ACL, CHI, UbiComp, ECCV, IJCAI, ECAI, WACV, IPSN, PAKDD, LREC, IJCNN, ICPR, ICIP, BEA, BLP, ICMLA, Scientific Reports, Scientific Data, Pattern Recognition, Information Sciences, Ad Hoc Networks, Drug and Alcohol Dependence, PLOS ONE

Research Interests

Artificial Intelligence, Machine Learning

References

  1. 1.David B. Johnson, David A. Maltz. (2007). Dynamic Source Routing in Ad Hoc Wireless Networks. , 153–181[10.1007/978-0-585-29603-6_5]
  2. 2.Leslie Lamport. (1978). Time, clocks, and the ordering of events in a distributed system. Communications of the ACM, 21(7), 558–565[10.1145/359545.359563]
  3. 3.Josh Broch, David A. Maltz, David B. Johnson, Yih-Chun Hu, Jorjeta Jetcheva. (1998). A performance comparison of multi-hop wireless ad hoc network routing protocols. , 85–97[10.1145/288235.288256]
  4. 4.Edsger W. Dijkstra. (1974). Self-stabilizing systems in spite of distributed control. Communications of the ACM, 17(11), 643–644[10.1145/361179.361202]
  5. 5.Young-Bae Ko, Nitin H. Vaidya. (1998). Location-aided routing (LAR) in mobile ad hoc networks. , 66–75[10.1145/288235.288252]
  6. 6.Leslie Lamport. (2019). Time, clocks, and the ordering of events in a distributed system. [10.1145/3335772.3335934]
  7. 7.Stefano Basagni, Imrich Chlamtac, Violet R. Syrotiuk, Barry A. Woodward. (1998). A distance routing effect algorithm for mobility (DREAM). , 76–84[10.1145/288235.288254]
  8. 8.Elizabeth M. Royer, Charles E. Perkins. (1999). Multicast operation of the ad-hoc on-demand distance vector routing protocol. , 207–218[10.1145/313451.313538]
  9. 9.Per Johansson, Tony Larsson, Nicklas Hedman, Bartosz Mielczarek, Mikael Degermark. (1999). Scenario-based performance analysis of routing protocols for mobile ad-hoc networks. , 195–206[10.1145/313451.313535]
  10. 10.Edsger W. Dijkstra, C.S. Scholten. (1980). Termination detection for diffusing computations. Information Processing Letters, 11(1), 1–4[10.1016/0020-0190(80)90021-6]
  11. 11.E. W. Dijkstra. (1965). Solution of a problem in concurrent programming control. Communications of the ACM, 8(9), 569[10.1145/365559.365617]
  12. 12.R. Bagrodia, R. Meyer, M. Takai, Yu-An Chen, Xiang Zeng, J. Martin, Ha Yoon Song. (1998). Parsec: a parallel simulation environment for complex systems. Computer, 31(10), 77–85[10.1109/2.722293]
  13. 13.Kerry Raymond. (1989). A tree-based algorithm for distributed mutual exclusion. ACM Transactions on Computer Systems, 7(1), 61–77[10.1145/58564.59295]
  14. 14.E. Gafni, D. Bertsekas. (1981). Distributed Algorithms for Generating Loop-Free Routes in Networks with Frequently Changing Topology. IRE Transactions on Communications Systems, 29(1), 11–18[10.1109/tcom.1981.1094876]
  15. 15.Divyakant Agrawal, Amr El Abbadi. (1991). An efficient and fault-tolerant solution for distributed mutual exclusion. ACM Transactions on Computer Systems, 9(1), 1–20[10.1145/103727.103728]
  16. 16.Leslie Lamport. (1986). The mutual exclusion problem. Journal of the ACM, 33(2), 327–348[10.1145/5383.5385]
  17. 17.Jennifer E. Walter, Jennifer L. Welch, Nitin H. Vaidya. (2001). A Mutual Exclusion Algorithm for Ad Hoc Mobile Networks. Wireless Networks, 7(6), 585–600[10.1023/a:1012363200403]
  18. 18.Michael J. Fischer, Nancy A. Lynch, James E. Burns, Allan Borodin. (1979). Resource allocation with immunity to limited process failure. , 234–254[10.1109/sfcs.1979.37]
  19. 19.Edsger W. Dijkstra. (2001). Solution of a Problem in Concurrent Programming Control. , 289–294[10.1007/978-3-642-48354-7_10]
  20. 20.Robert Castañeda, Samir R. Das. (1999). Query localization techniques for on-demand routing protocols in ad hoc networks. , 186–194[10.1145/313451.313534]
  21. 21.M. Singhal. (1989). A heuristically-aided algorithm for mutual exclusion in distributed systems. IEEE Transactions on Computers, 38(5), 651–662[10.1109/12.24268]
  22. 22.N. Malpani, Yu Chen, N.H. Vaidya, J.L. Welch. (2005). Distributed token circulation in mobile ad hoc networks. IEEE Transactions on Mobile Computing, 4(2), 154–165[10.1109/tmc.2005.25]
  23. 23.B.R. Badrinath, A. Acharya, T. Imielinski. (2002). Structuring distributed algorithms for mobile hosts. , 21–28[10.1109/icdcs.1994.302386]
  24. 24.Vassos Hadzilacos. (2001). A note on group mutual exclusion. , 100–106[10.1145/383962.383997]
  25. 25.R. Baldoni, A. Virgillito, R. Petrassi. (2003). A distributed mutual exclusion algorithm for mobile ad-hoc networks. , 539–544[10.1109/iscc.2002.1021727]
  26. 26.M. Benchaïba, A. Bouabdallah, N. Badache, M. Ahmed-Nacer. (2004). Distributed mutual exclusion algorithms in mobile ad hoc networks. ACM SIGOPS Operating Systems Review, 38(1), 74–89[10.1145/974104.974111]
  27. 27.Yu Chen, Jennifer L. Welch. (2002). Self-stabilizing mutual exclusion using tokens in mobile ad hoc networks. , 34–42[10.1145/570810.570815]
  28. 28.Y.-I. Chang, M. Singhal, M.T. Liu. (2002). A fault tolerant algorithm for distributed mutual exclusion. , 146–154[10.1109/reldis.1990.93960]
  29. 29.N. Malpani, N.H. Vaidya, J.L. Welch. (2005). Distributed token circulation on mobile ad hoc networks. , 4–13[10.1109/icnp.2001.992755]
  30. 30.Jennifer E. Walter, Savita Kini. (1997). Mutual Exclusion on Multihop, Mobile Wireless Networks.
  31. 31.Leslie Lamport. (2019). The mutual exclusion problem: part II---Statement and solutions. [10.1145/3335772.3335938]
  32. 32.Dhananjay M. Dhamdhere, Sandeep S. Kulkarni. (1994). A token based k-resilient mutual exclusion algorithm for distributed systems. Information Processing Letters, 50(3), 151–157[10.1016/0020-0190(94)00019-0]
  33. 33.Yu Chen, Jennifer L. Welch. (2002). Self-stabilizing mutual exclusion using tokens in mobile ad hoc networks. [10.1145/570811.570815]
  34. 34.Gérard Le Lann. (1977). Distributed Systems--Towards a Formal Approach. HAL (Le Centre pour la Communication Scientifique Directe), 155–160[link]

Cited By

  1. 1.Salahuddin Mohammad Masum, Mohammad Mostofa Akbar, Amin Ahsan Ali, Mohammad Ashiqur Rahman. (2009). A consensus-based ℓ-Exclusion algorithm for mobile ad hoc networks. Ad Hoc Networks, 8(1), 30–45[10.1016/j.adhoc.2009.03.002]
← All publications