Two algorithms for leader election and network size estimation in mobile ad hoc networks
MetadataShow full item record
We develop two algorithms for important problems in mobile ad hoc networks (MANETs). A MANET is a collection of mobile processors (nodes) which communicate via message passing over wireless links. Each node can communicate directly with other nodes within a speciﬁed transmission radius; other communication is accomplished via message relay. Communication links may go up and down in a MANET (as nodes move toward or away from each other); thus, the MANET can consist of multiple connected components, and connected components can split and merge over time. We ﬁrst present a deterministic leader election algorithm for asynchronous MANETs along with a correctness proof for it. Our work involves substantial modiﬁcations of an existing algorithm and its proof, and we adapt the existing algorithm to the asynchronous environment. Our algorithms running time and message complexity compare favorably with existing algorithms for leader election in MANETs. Second, many algorithms for MANETs require or can beneﬁt from knowledge about the size of the network in terms of the number of processors. As such, we present an algorithm to approximately determine the size of a MANET. While the algorithms approximations of network size are only rough ones, the algorithm has the important qualities of requiring little communication overhead and being tolerant of link failures.
Subjectmobile ad hoc networks
network size estimation
Neumann, Nicholas Gerard (2004). Two algorithms for leader election and network size estimation in mobile ad hoc networks. Master's thesis, Texas A&M University. Texas A&M University. Available electronically from