Routing Strategies In Ad Hoc Wireless Networks

Ad-hoc wireless networks present a unique design problem for routing. Wireless networks suffer from low bandwidth due to high rates of interference and inherent limitations of the medium. Mobility also increases the bandwidth used for control packets. To conserve on precious bandwidth, routing protocols should generate as few updates as possible. In this dissertation, we propose distance vector solutions to ad-hoc routing because unlike existing routing solutions our solutions do not use sequence numbers and thus are not prone to inefficient or wrong behavior in the presence of node failures. First, we introduce ROAM, the first protocol to correctly tackle the "searching to infinity" problem found in on-demand routing protocols. ROAM can be used in networks with low rates of topology changes because it required reliable updates. Next, we describe two protocols DST (on-demand) and BEST (table-driven) for networks with high rates of topology change. Simulation experiments carried out in two different simulation packages show that these protocols perform an order of magnitude better than representative on-demand and table-driven routing solutions for ad-hoc networks. Finally, we introduce MDST, an on-demand protocol that extends the source tracing algorithm used in DST to create and maintain multiple paths in an ad-hoc wireless network. Multipath routing can be used in ad hoc networks to achieve greater resilience to route failures and better end-to-end delays. Multipath routing is also essential when using QoS metrics like delay in order to avoid route oscillation. We show that multiple paths that are node disjoint and loop free can be maintained with less overhead than DST. Further, these multiple paths decrease the delay of packet delivery and increase the throughput of the network.