Jorjeta G. Jetcheva

Adaptive Demand-Driven Multicast Routing in Multi-Hop Wireless Ad Hoc Networks Degree Type: Ph.D. in Computer Science
Advisor(s): David Johnson
Graduated: May 2004

Abstract:

An ad hoc network does not require any pre-existing infrastructure or configuration but is formed spontaneously by (possibly mobile) nodes that wish to communicate. Each node in the ad hoc network acts as a router and forwards packets on behalf of other nodes, allowing nodes that are not within wireless range of each other to communicate over multi-hop paths. Example ad hoc network applications include disaster relief scenarios, conference attendees who want to form a network in order to exchange documents, friends involved in a distributed outdoors game, surveillance teams composed of persons or robots exploring a dangerous area, or another planet.

Previous efforts to design general-purpose on-demand multicast routing protocols for ad hoc networks have utilized periodic (non-on-demand) mechanisms within some portions of the protocol. The overall on-demand nature of such protocols derives from the fact that significant portions of their operation are active only for active multicast groups. However, the periodic mechanisms within the protocol are responsible for core routing functionality and significantly affect overall protocol performance.

My thesis in this dissertation is that on-demand multicast that does not rely on periodic techniques is more efficient and performs better than multicast that utilizes such techniques.

To support my thesis statement, in this dissertation I present the design and evaluation of a new multicast protocol, the Adaptive Demand-Driven Multicast Routing protocol (ADMR) for multi-hop wireless ad hoc networks. ADMR uses no periodic control packet network-wide floods, periodic neighbor sensing, or periodic routing table exchanges, and adapts its behavior based on network conditions and application sending pattern, allowing efficient detection of broken links and expira-tion of routing state that is no longer needed. I conduct an extensive simulation of ADMR and show that it compares well against protocols that utilize proactive mechanisms, and typically generates three to five times less packet overhead.

In addition, in this dissertation, I study the impact of unidirectional links on the routing characteristics of ad hoc networks, and use this study to explore the effect of unidirectional links on multicast routing performance. Using the lessons learned from this work, I extend ADMR with mechanisms that enable it to route over unidirectional links, and show that the unidirectional extensions improve the performance of the protocol by increasing packet delivery ratio by up to 45% and decreasing overhead by up to 68%.

Thesis Committee:
David B. Johnson (Chair)
Jim Kurose
Srinivasan Seshan
Daniel P. Siewiorek

Randy Bryant, Head, Computer Science Department
James Morris, Dean, School of Computer Science

Keywords:
Wireless, ad hoc networks, routing, multicast, unidirectional links, mesh networks