Conference Paper2006Cited by 31

Asynchronous leader election in mobile ad hoc networks

Salahuddin Mohammad Masum, Amin Ahsan Ali, Mohammad Touhid-youl Islam Bhuiyan

20th International Conference on Advanced Information Networking and Applications-Volume 1 (AINA'06)

IEEE, Vol. 2, pp. 5–pp

DOI: 10.1109/aina.2006.106URL

Abstract

With the proliferation of portable computing platforms and small wireless devices, the classical dilemma of leader election in mobile ad hoc networks has received attention from the research community in recent years. The problem aims to elect a unique leader among mobile nodes regardless of their physical locations. But, existing distributed leader election algorithms do not cope with highly spontaneous nature of mobile ad hoc networks. This paper presents a consensus-based leader election algorithm that finds a local extrema among the nodes participating in leader election. The algorithm is highly adaptive with ad hoc networks in the sense that it can tolerate intermittent failures, such as link failures, sudden crash or recovery of mobile nodes, network partitions, and merging of connected network components associated with ad hoc networks. The paper also presents proofs of correctness to exhibit the fairness of this algorithm.

Keywords

  • mobile ad hoc networks
  • Leader election
  • local extrema
  • intermittent failures
  • consensus algorithms
  • fault tolerance
  • asynchronous algorithms
  • fairness
  • network partitions
  • correctness proofs

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.W.R. Heinzelman, A. Chandrakasan, H. Balakrishnan. (2005). Energy-efficient communication protocol for wireless microsensor networks. , vol.1, 10[10.1109/hicss.2000.926982]
  2. 2.C.E. Perkins, E.M. Royer. (1999). Ad-hoc on-demand distance vector routing. , 90–100[10.1109/mcsa.1999.749281]
  3. 3.(1992). Distributed Algorithms. Lecture notes in computer science[10.1007/bfb0022433]
  4. 4.V.D. Park, M.S. Corson. (2002). A highly adaptive distributed routing algorithm for mobile wireless networks. , 3, 1405–1413[10.1109/infcom.1997.631180]
  5. 5.Leeuwen, Jan van, International Workshop on Distributed Algorithms 1987 Amsterdam. (1988). Distributed Algorithms. Lecture notes in computer science[10.1007/3-540-61769-8]
  6. 6.S. Vasudevan, J. Kurose, D. Towsley. (2004). Design and analysis of a leader election algorithm for mobile ad hoc networks. , 350–360[10.1109/icnp.2004.1348124]
  7. 7.B. DeCleene, L. Dondeti, S. Griffin, T. Hardjono, D. Kiwior, J. Kurose, D. Towsley, S. Vasudevan, C. Zhang. (2002). Secure group communications for wireless networks. , 1, 113–117[10.1109/milcom.2001.985773]
  8. 8.Kostas P. Hatzis, George P. Pentaris, Paul G. Spirakis, Vasilis T. Tampakas, Richard B. Tan. (1999). Fundamental control algorithms in mobile networks. , 251–260[10.1145/305619.305649]

Cited By

  1. 1.Rebecca Ingram, Patrick Shields, Jennifer E. Walter, Jennifer L. Welch. (2009). An asynchronous leader election algorithm for dynamic networks. , 1–12[10.1109/ipdps.2009.5161028]
  2. 2.Orhan Dagdeviren, Kayhan Erciyes. (2008). A Hierarchical Leader Election Protocol for Mobile Ad Hoc Networks. Lecture notes in computer science, 509–518[10.1007/978-3-540-69384-0_56]
  3. 3.Carlos Gomez-Calzado, Alberto Lafuente, Mikel Larrea, Michel Raynal. (2013). Fault-Tolerant Leader Election in Mobile Dynamic Distributed Systems. , 78–87[10.1109/prdc.2013.17]
  4. 4.Luciana Arantes, Fabíola Greve, Pierre Sens, Véronique Simon. (2013). Eventual Leader Election in Evolving Mobile Networks. Lecture notes in computer science, 23–37[10.1007/978-3-319-03850-6_3]
  5. 5.Rebecca Ingram, Tsvetomira Radeva, Patrick Shields, Saira Viqar, Jennifer E. Walter, Jennifer L. Welch. (2013). A leader election algorithm for dynamic networks with causal clocks. Distributed Computing, 26(2), 75–97[10.1007/s00446-013-0184-1]
  6. 6.Abdelmoujib Megzari, P. V. Pravija Raj, Walid Osamy, Ahmed M. Khedr. (2023). Applications, challenges, and solutions to single- and multi-objective critical node detection problems: a survey. The Journal of Supercomputing, 79(17), 19770–19808[10.1007/s11227-023-05429-3]
  7. 7.Pijush Kanti Dutta Pramanik, Prasenjit Choudhury. (2020). Mobility-aware service provisioning for delay tolerant applications in a mobile crowd computing environment. SN Applied Sciences, 2(3)[10.1007/s42452-020-2212-7]
  8. 8.Gang Zhang, Xiaoyan Kuang, Jing Chen, Yu Zhang. (2009). Design and implementation of a leader election algorithm in hierarchy mobile ad hoc network. , 263–268[10.1109/iccse.2009.5228448]
  9. 9.Leila Melit, Nadjib Badache. (2011). An energy efficient leader election algorithm for mobile ad hoc networks. , 54–59[10.1109/isps.2011.5898893]
  10. 10.Negin Fathollahnejad, Raul Barbosa, Johan Karlsson. (2017). A Probabilistic Analysis of a Leader Election Protocol for Virtual Traffic Lights. , 311–320[10.1109/prdc.2017.56]
  11. 11.Brahim Ayari, Abdelmajid Khelil, Neeraj Suri. (2010). ParTAC: A Partition-Tolerant Atomic Commit Protocol for MANETs. , 135–144[10.1109/mdm.2010.25]
  12. 12.Bronislav Sidik, Rami Puzis, Polina Zilberman, Yuval Elovici. (2019). PALE: Time Bounded Practical Agile Leader Election. IEEE Transactions on Parallel and Distributed Systems, 31(2), 470–485[10.1109/tpds.2019.2933620]
  13. 13.Syed Asad Hussain, Naeem Akhtar Khan, Ayesha Sadiq, Farooq Ahmad. (2016). Simulation, modeling and analysis of master node election algorithm based on signal strength for VANETs through Colored Petri nets. Neural Computing and Applications, 29(11), 1243–1259[10.1007/s00521-016-2622-z]
  14. 14.Leila Melit, Nadjib Badache. (2012). An Ω-Based Leader Election Algorithm for Mobile Ad Hoc Networks. Communications in computer and information science, 483–490[10.1007/978-3-642-30507-8_41]
  15. 15.Ajoy K. Datta, Lawrence L. Larmore. (2017). Self-Stabilizing Leader Election in Dynamic Networks. Theory of Computing Systems, 62(5), 977–1047[10.1007/s00224-017-9758-9]
  16. 16.Sidik, Bronislav, Puzis, Rami, Zilberman, Polina, Elovici, Yuval. (2018). PALE: Partially Asynchronous Agile Leader Election. arXiv (Cornell University)[10.48550/arxiv.1801.03734]
  17. 17.Almetwally Mostafa, Ahmed E. Youssef. (2013). A Leader Replacement Protocol Based on Early Discovery of Battery Power Failure in MANETs. , 1–4[10.1109/icitcs.2013.6717777]
  18. 18.Rebecca Ingram, Mira Radeva, Patrick Shield, Jennifer E. Walter, Jennifer L. Welch. (2009). An Asynchronous Leader Election Algorithm for Dynamic Networks without Perfect Clocks.
  19. 19.Gang Zhang, Jing Chen, Yu Zhang, Chungui Liu. (2009). Research of Asynchronous Leader Election Algorithm on Hierarchy Ad Hoc Network. , 21, 1–4[10.1109/wicom.2009.5301989]
  20. 20.Brahim Ayari, Abdelmajid Khelil, Neeraj Suri. (2009). Exploring Delay-Aware Transactions in Heterogeneous Mobile Environments. Journal of Software, 4(7)[10.4304/jsw.4.7.634-643]
  21. 21.Mikel Larrea, Cristian Martin, Jose Javier Astrain. (2009). Fault-tolerant aggregator election and data aggregation in wireless sensor networks. International Journal of Communication Networks and Distributed Systems, 3(2), 93[10.1504/ijcnds.2009.026821]
  22. 22.Esunly Medina, David Lopez, Roc Meseguer, Sergio Ochoa, Dolors Royo, Rodrigo Santos. (2016). Mobile Autonomous Sensing Unit (MASU): A Framework That Supports Distributed Pervasive Data Sensing. Sensors, 16(7), 1062[10.3390/s16071062]
  23. 23.Tsvetomira Radeva. (2013). Properties of link reversal algorithms for routing and leader election. DSpace@MIT (Massachusetts Institute of Technology)[link]
  24. 24.Almetwally M. Mostafa, Ahmed E. Youssef. (2014). PRP: A primary replacement protocol based on early discovery of battery power failure in MANETs. Multimedia Tools and Applications, 74(16), 6243–6254[10.1007/s11042-014-2091-2]
  25. 25.Abdelmajid Khelil, Christian Reinl, Brahim Ayari, Faisal Karim Shaikh, Piotr Szczytowski, Azad Ali, Neeraj Suri. (2011). Wireless Sensor Cooperation for a Sustainable Quality of Information. , 71–100[10.1002/9781119970422.ch6]
  26. 26.Rasmeet S. Bali, C. Rama Krishna. (2010). New Distributed Initialization Protocols for IEEE 802.11 Based Single Hop Ad Hoc Networks. Communications in computer and information science, 179–190[10.1007/978-3-642-17878-8_19]
  27. 27.Arnaud Favier. (2022). Eventual Leader Elections in Dynamic Networks. [10.70675/f2b08af0z087dz4606zb83bzfebc42fc84a9]
  28. 28.Esunly Medina Medina. (2016). An approach to pervasive monitoring in dynamic learning contexts : data sensing, communication support and awareness provision. [10.5821/dissertation-2117-96258]
  29. 29.T. Subhashini, K Reeshma. (2015). EABPF: Efficient Algorithm to OvercomeBattery Power Failures in Mobile Ad HocNetworks. International Journal of Innovative Research in Computer and Communication Engineering, 2015(4), 3790–3798[10.15680/ijircce.2015.0304170]
  30. 30.Cheol Hoon Park, Young Su Son, Sang Yong Ham, Byung In Kim, Sung Whee Lee, Hyung Chul Lim. (2012). Controller Design and Experiment for Tracking Mount of Movable SLR, ARGO-M. DOAJ (DOAJ: Directory of Open Access Journals)[link]
  31. 31.Mikel Larrea. (2010). THE OMEGA FAILURE DETECTOR IN THE CRASH-RECOVERY MODEL.
← All publications