Events & News
Computer Science Colloquium
| Category | Lecture |
| Date | Monday, August 4, 2008 |
| Time | 10:00 am |
| Location | GS 701 |
| Details | Light refreshments will be served at 9:45 AM in the 7th floor lobby |
| Speaker | Huilong Huang |
| Title | Doctoral Candidate |
| Affiliation | Department of Computer Science |
Efficient Routing in Wireless Ad Hoc Networks
PhD Dissertation
Committee Chair: John Hartman
Routing is a 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 deficiency in one or more aspects including efficiency, scalability, robustness, complexity, etc.
For MANETs, the traditional routing protocols rely on flooding search that is neither efficient nor scalable, or pre-computing routes that cannot handle mobility well, or special positioning equipment that limits the application. Newer protocols considered self organized hierarchical routing and indexing mechanism, but the solutions lack simplicity and robustness.
WSNs is usually application specific. Different application scenarios make the network characteristics and the routing requirements different. Various designs have been proposed for different routing scenarios, typically flooding for generic routing, random walk for query processing and location-aided routing in location-aware networks. The existing ones, however, are still not the best solution for scenarios such as short-term data centric communication, query processing in mobile networks, 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.
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 pro-actively 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 also having less routing failures than pre-computing routes to all nodes. Compared with existing popular protocols, AAR shows better performance in delivery rate, message overhead and latency, and has better scalability.