Persistent Link:
http://hdl.handle.net/10150/196105
Title:
Efficient Routing in Wireless Ad Hoc Networks
Author:
Huang, Huilong
Issue Date:
2008
Publisher:
The University of Arizona.
Rights:
Copyright © is held by the author. Digital access to this material is made possible by the University Libraries, University of Arizona. Further transmission, reproduction or presentation (such as public display or performance) of protected items is prohibited except with permission of the author.
Abstract:
Routing is the fundamental problem for Wireless Ad hoc networks, including Wireless Mobile Ad hoc networks (MANETs) and Wireless Sensor networks (WSNs). Although the problem has been extensively studied in the past decade, the existing solutions have deficiencies in one or more aspects including efficiency, scalability, robustness, complexity, etc.This dissertation proposes several new solutions for routing in WSNs and MANETs. Spiral is a data-centric routing algorithm for short-term communication in unstructured static WSNs. Spiral is a biased walk that visits nodes near the source before more distant nodes. This results in a spiral-like search path that is not only more likely to find a closer copy of the desired data than random walk, but is also able to compute a shorter route because the network around the source is more thoroughly explored. Compared with existing flooding and random walk approaches, Spiral has a lower search cost than flooding and returns better routes than random walk.Closest Neighbor First Search (CNFS) is a query processing algorithm for mobile wireless sensor networks. It is also walk-based and biased to visit nodes close to the source first. Different from Spiral, CNFS collects topology information as the search progresses. The topology information is used to compute the shortest return path for the query result and to tolerate the network topology changes caused by node mobility, which could otherwise cause the query to fail. CNFS requires fewer messages to process a query than flooding-based algorithms, while tolerating node mobility better than random walk-based algorithms.Address Aggregation-based Routing (AAR) is a novel routing protocol designed for MANETs. It reactively performs route discovery, but proactively maintains an index hierarchy called a Route Discovery DAG (RDD) to make route discovery efficient. The RDD contains aggregated node address information, requiring fewer packets for route discovery than the flooding used in existing protocols, while handling mobility better than pre-computing routes to all nodes. Compared with some existing popular protocols, AAR shows better performance in delivery rate, message overhead, latency and scalability.
Type:
text; Electronic Dissertation
Keywords:
Wireless Sensor Networks; Mobile Ad Hoc Networks; Routing
Degree Name:
PhD
Degree Level:
doctoral
Degree Program:
Computer Science; Graduate College
Degree Grantor:
University of Arizona
Advisor:
Hartman, John H.
Committee Chair:
Hartman, John H.

Full metadata record

DC FieldValue Language
dc.language.isoENen_US
dc.titleEfficient Routing in Wireless Ad Hoc Networksen_US
dc.creatorHuang, Huilongen_US
dc.contributor.authorHuang, Huilongen_US
dc.date.issued2008en_US
dc.publisherThe University of Arizona.en_US
dc.rightsCopyright © is held by the author. Digital access to this material is made possible by the University Libraries, University of Arizona. Further transmission, reproduction or presentation (such as public display or performance) of protected items is prohibited except with permission of the author.en_US
dc.description.abstractRouting is the fundamental problem for Wireless Ad hoc networks, including Wireless Mobile Ad hoc networks (MANETs) and Wireless Sensor networks (WSNs). Although the problem has been extensively studied in the past decade, the existing solutions have deficiencies in one or more aspects including efficiency, scalability, robustness, complexity, etc.This dissertation proposes several new solutions for routing in WSNs and MANETs. Spiral is a data-centric routing algorithm for short-term communication in unstructured static WSNs. Spiral is a biased walk that visits nodes near the source before more distant nodes. This results in a spiral-like search path that is not only more likely to find a closer copy of the desired data than random walk, but is also able to compute a shorter route because the network around the source is more thoroughly explored. Compared with existing flooding and random walk approaches, Spiral has a lower search cost than flooding and returns better routes than random walk.Closest Neighbor First Search (CNFS) is a query processing algorithm for mobile wireless sensor networks. It is also walk-based and biased to visit nodes close to the source first. Different from Spiral, CNFS collects topology information as the search progresses. The topology information is used to compute the shortest return path for the query result and to tolerate the network topology changes caused by node mobility, which could otherwise cause the query to fail. CNFS requires fewer messages to process a query than flooding-based algorithms, while tolerating node mobility better than random walk-based algorithms.Address Aggregation-based Routing (AAR) is a novel routing protocol designed for MANETs. It reactively performs route discovery, but proactively maintains an index hierarchy called a Route Discovery DAG (RDD) to make route discovery efficient. The RDD contains aggregated node address information, requiring fewer packets for route discovery than the flooding used in existing protocols, while handling mobility better than pre-computing routes to all nodes. Compared with some existing popular protocols, AAR shows better performance in delivery rate, message overhead, latency and scalability.en_US
dc.typetexten_US
dc.typeElectronic Dissertationen_US
dc.subjectWireless Sensor Networksen_US
dc.subjectMobile Ad Hoc Networksen_US
dc.subjectRoutingen_US
thesis.degree.namePhDen_US
thesis.degree.leveldoctoralen_US
thesis.degree.disciplineComputer Scienceen_US
thesis.degree.disciplineGraduate Collegeen_US
thesis.degree.grantorUniversity of Arizonaen_US
dc.contributor.advisorHartman, John H.en_US
dc.contributor.chairHartman, John H.en_US
dc.contributor.committeememberHartman, John H.en_US
dc.contributor.committeememberKobourov, Stephenen_US
dc.contributor.committeememberZhang, Beichuanen_US
dc.contributor.committeememberKrunz, Marwanen_US
dc.identifier.proquest2894en_US
dc.identifier.oclc659749543en_US
All Items in UA Campus Repository are protected by copyright, with all rights reserved, unless otherwise indicated.