Routing and multicast in ad hoc networks: The case for cross layer interaction

Over the last few years, the most interesting research agenda for ad hoc routing (and more generally, ad hoc networking) has been the attempt to improve network layer performance by leveraging the so called cross layer interaction, that is, the assistance of layers below and above. For example, physical layer measurements assist in seeking more reliable routes. And, knowledge about application duty cycles helps to determine the best route refresh policy. In this thesis, we investigate the interactions between the network layer, i.e., routing and multicast, and the upper and lower layers. We study, for example, the impact of application behavior prediction on multicast performance, and we design efficient multicast schemes that are "aware" of asymmetric physical links. The main focus of this research, however, has been on two recent breakthroughs in lower layer designs made possible by advances in Communications and Information Theory, namely, Multiple-Input Multiple-Output (MIMO) antenna systems and Network Coding. MIMO systems have been extensively studied in point-to-point link settings and Network Coding in static multicast environments. Yet, it is not clear how these techniques can be fully exploited in the design of novel network layer protocols for very general ad hoc, mobile networks. In this thesis, we investigate the full impact of these new technologies on routing and multicast.; MIMO systems use multiple antenna elements at both transmitter and receiver and such systems can be utilized in wireless ad hoc networks for improved throughput in several ways. A straightforward way is to regard the MIMO system just as a new physical layer technology that provides a higher data rate. This approach allows MIMO systems to be integrated with legacy Media Access Control (MAC) and routing protocols such as IEEE 802.11 MAC but it does not fully utilize MIMO systems. Recent studies have proposed MAC protocols leveraging the advantages of MIMO systems in a different way, enabling simultaneous multiple communications at a lower rate rather than a single communication at a higher rate in a single collision domain. In this thesis, we present a new MIMO MAC protocol for ad hoc networks called SPACE-MAC. The protocol further increases the network throughput by combining the two approaches, i.e., allowing simultaneous multiple communications at a higher data rate. The spatial reuse among MIMO links is enabled in the protocol using a set of new beamforming algorithms proposed as part of the protocol.; Network Coding refers to the notion of performing coding operations on the contents of packets throughout a network. In this thesis, we develop CodeCast, an ad hoc multicast protocol based on network coding. Major applications of wireless ad hoc multicast include disaster relief and battlefield operations which are group-oriented and mission-critical, requiring both reliable data delivery and timeliness. Undoubtedly, a low loss and low latency multicast solution will be a breakthrough in such applications. CodeCast achieves low loss and low latency with the help of localized loss recovery and path diversity. The key ingredient of CodeCast is random network coding which transparently implements both localized loss recovery and path diversity with very low overhead. In our work we show how CodeCast can yield significant performance improvements in a variety of ad hoc network scenarios.