Two algorithms for leader election and network size estimation in mobile ad hoc networks
dc.contributor.advisor | Welch, Jennifer | |
dc.creator | Neumann, Nicholas Gerard | |
dc.date.accessioned | 2005-02-17T20:58:52Z | |
dc.date.available | 2005-02-17T20:58:52Z | |
dc.date.created | 2004-12 | |
dc.date.issued | 2005-02-17 | |
dc.identifier.uri | https://hdl.handle.net/1969.1/1321 | |
dc.description.abstract | 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 specified 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 first present a deterministic leader election algorithm for asynchronous MANETs along with a correctness proof for it. Our work involves substantial modifications 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 benefit 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. | en |
dc.format.extent | 320290 bytes | en |
dc.format.medium | electronic | en |
dc.format.mimetype | application/pdf | |
dc.language.iso | en_US | |
dc.publisher | Texas A&M University | |
dc.subject | mobile ad hoc networks | en |
dc.subject | leader election | en |
dc.subject | network size estimation | en |
dc.subject | distributed computing | en |
dc.subject | randomized algorithms | en |
dc.title | Two algorithms for leader election and network size estimation in mobile ad hoc networks | en |
dc.type | Book | en |
dc.type | Thesis | en |
thesis.degree.department | Computer Science | en |
thesis.degree.discipline | Computer Science | en |
thesis.degree.grantor | Texas A&M University | en |
thesis.degree.name | Master of Science | en |
thesis.degree.level | Masters | en |
dc.contributor.committeeMember | Klappenecker, Andreas | |
dc.contributor.committeeMember | Larson, David | |
dc.type.genre | Electronic Thesis | en |
dc.type.material | text | en |
dc.format.digitalOrigin | born digital | en |
Files in this item
This item appears in the following Collection(s)
-
Electronic Theses, Dissertations, and Records of Study (2002– )
Texas A&M University Theses, Dissertations, and Records of Study (2002– )