Call for Paper - August 2022 Edition
IJCA solicits original research papers for the August 2022 Edition. Last date of manuscript submission is July 20, 2022. Read More

A Stable CoveringSet-based Leader Election Algorithm (SCLEA) for Mobile Ad hoc Distributed Systems

Print
PDF
International Journal of Computer Applications
© 2012 by IJCA Journal
Volume 54 - Number 2
Year of Publication: 2012
Authors:
Sanaa A. Alwidian
Alaa N. Alslaity
10.5120/8539-2083

Sanaa A Alwidian and Alaa N Alslaity. Article: A Stable CoveringSet-based Leader Election Algorithm (SCLEA) for Mobile Ad hoc Distributed Systems. International Journal of Computer Applications 54(2):25-32, September 2012. Full text available. BibTeX

@article{key:article,
	author = {Sanaa A. Alwidian and Alaa N. Alslaity},
	title = {Article: A Stable CoveringSet-based Leader Election Algorithm (SCLEA) for Mobile Ad hoc Distributed Systems},
	journal = {International Journal of Computer Applications},
	year = {2012},
	volume = {54},
	number = {2},
	pages = {25-32},
	month = {September},
	note = {Full text available}
}

Abstract

Leader election process is known as the task of selecting a particular node or a process to be a unique leader of the distributed system. Many algorithms were proposed for leader election in classical, wired distributed systems. However, with the advent of wireless communication technology, the domain of distributed computing becomes much wide, and the concept of leader election in such environments has been changed due to the dynamic topology resulted from nodes' mobility. The existing classical leader election algorithms do not adapt well in mobile ad hoc environments. In this paper, we propose a new leader election algorithm that is conscious about nodes' mobility and the dynamic topology of ad hoc networks. The main idea of our algorithm is to select a subset of the nodes to participate in the election process, the selected nodes should ensure coverage of other nodes and that are of low mobility. We show through mathematical analysis that our proposed algorithm, the "Stable CoveringSet-Based Leader Election Algorithm (SCLEA)" outperforms any other algorithm that depends on the simple flooding to perform leader election. The enhancement of our algorithm is advent in terms of reducing the message overhead associated with leader election process and minimizing the number of redundant ELECTION messages as much as possible.

References

  • Sung-Hoon Park "A Stable Election Protocol based on an Unreliable Failure Detector in Distributed Systems". 2011 Eighth International Conference on Information Technology: New Generations. pp. 979 – 984, April 2011.
  • Haddar, M. A. , Hadj Kacem, A. , Metivier, Y. , Mosbah, M. and Jmaiel, M. "Electing a leader in the local computation model using mobile agents", IEEE/ACS International Conference on Computer Systems and Applications, 2008. AICCSA 2008. pp. : 473 – 480, April, 2008.
  • Mehdi Mirakhorli, Amir A. Sharifloo, Maghsoud Abbaspour, "A Novel Method for Leader Election Algorithm". The 7th IEEE International Conference on Computer and Information Technology (CIT 2007), pp. 452-456, October 2007.
  • Mina Shirali, Abolfazl Haghighat Toroghi, and Mehdi Vojdani "Leader election algorithms: History and novel schemes". Third 2008 International Conference on Convergence and Hybrid Information Technology(ICCIT'08),pp. 1001-1006, November 2008.
  • Scott D. Stoller. "Leader Election in Asynchronous Distributed Systems". IEEE Transaction on Computers Journal, volume 49, no. 3 pp. 283- 284, March 2000.
  • G. L. Lann, "Distributed Systems - Towards a Formal Approach", in Proc. IFIP Congress, pp. 155-160, 1977.
  • Randolph Franklin "An improved algorithm for decentralized extrema-finding in circular configurations of processes". Communications of the ACM Magazine. pp. 336–337, May 1982.
  • Nourddine E, Mohammed K, Amine B. "Enhancing AODV Performance based on Statistical Mobility Quantification". The IEEE International Conference on Information & Communication Technology (ICTTA06), pp. 2455-2460, 2006.
  • Gerard Tel "Introduction to Distributed Algorithms. Second Edition", Cambridge University Press, 1995.
  • Garcia-Molina H. "Election in a distributed Computing System". IEEE Transaction on Computers Journal, vol31, no. 1 pp. 48-59. 1982.
  • Quazi Ehsanul Kabir Mamun, Salahuddin Mohammad Masum, and Mohammad Abdur Rahim Mustafa. "Modified bully algorithm for electing coordinator in distributed systems". WSEAS Transactions on Computers, Issue 4, Volum 3, pp. 948-953, October 2004.
  • Muneer Bani Yassein, Ala'a N Alslaity and Sana'a A Alwidian "An Efficient Overhead-aware Leader Election Algorithm for Distributed Systems. " International Journal of Computer Applications, volume 49 no. 6, pp: 10-15, July 2012.
  • J. Brunekreef, J. Katoen, R. Koymans and S. Mauw. "Design and Analysis of Leader Election Protocols in Broadcast Networks". In Distributed Computing Journal, vol. 9 no. 4, pp. 157-171, February 1996.
  • G. Taubenfeld. "Leader Election in presence of n-1 initial failures". In Information Processing Letters, Journal vol. 33, no. 1, pp. 25-28, October 1989.
  • Tai Woo Kim, Eui Hong Kim, Joong Kwon Kim, and Tai Yun Kim. "A leader election algorithm in a distributed computing system". Proceedings of the 5th IEEE Workshop on Future Trends of Distributed Computing Systems, page 481, August 1995.
  • N. Malpani, J. Welch and N. Vaidya. "Leader Election Algorithms for Mobile Ad Hoc Networks". DIALM '00 Proceedings of the 4th international workshop on Discrete algorithms and methods for mobile computing and communications, Boston, MA, pp. 96-103, August 2000.
  • Sudarshan Vasudevan, Jim Kurose, and Don Towsley. "Design and analysis of a leader election algorithm for mobile ad hoc networks". Proceedings of the 12th IEEE International Conference on Network Protocols, 2004. (ICNP04), pp:350–360, October 2004
  • K. Hatzis, G. Pentaris, P. Spirakis, V. Tampakas and R. Tan. "Fundamental Control Algorithms in Mobil Mobile Networks". In Proc. of 11th ACM SPAA, pp: 251-260, March 1999.
  • Abdalla MH, Aamir S, Irfan A, Mike W. "Dynamic Probabilistic Flooding Performance Evaluation of On-Demand Routing Protocols in MANETs CISIS '08 Proceedings of the 2008 International Conference on Complex, Intelligent and Software Intensive Systems, IEEE,pp. 200-204, 2008.
  • Ala'a N. Alslaity "Stable Neighborhood-Based Route Discovery Protocol For Mobile Ad Hoc Networks", Dissertation, Jordan University of Science and Technology. May, 2012.
  • V. D. Park and Scott. M. Corson, "A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks", INFOCOM '97 Proceedings of the INFOCOM '97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution, pp. 1405, 1997.