Rethinking the link abstraction for multihop wireless networks: Implications, cross-layer protocols and deployment

The link abstraction defines to a large extent the basis for the research and development of medium access control (MAC) and routing protocols for multihop wireless networks. Traditionally, an abstraction similar to the one commonly used to model the link of the wire-line networks has been adopted. However, the first wide-scale experimental deployments of multihop wireless networks have shown that the protocols designed based on this abstraction perform poorly in practice. The insights gained from the experimental deployments, coupled with significant advances in physical layer research in the early 2000's, have led to rethinking on what is the right link abstraction for multihop wireless networks. As a result, a new link abstraction has emerged based on the following generalizations. First, multiple nodes can cooperate together to create many-to-one links, an approach formally known as cooperative diversity. Multiple studies have shown that cooperative diversity can multiplicatively increase the link capacity and/or range. Second, the wireless links are intermittent.;In light of these major changes to the link abstraction, the key challenge is identifying the implications these changes have on the fundamental design principles of the higher layer protocols and, if necessary, the redesign, in part or in their entirety, of the MAC and routing protocols for multi-hop wireless networks.;In this dissertation, we attempt to address this challenge. We design cross-layer protocols that exploit cooperative diversity to improve the performance of the unicast and broadcast communications in multi-hop wireless networks. For unicast, we present a novel multi-layer protocol that spans the physical, MAC and routing layers. Extensive simulations show that our protocol achieves an increase of up to 150% in the end-to-end throughput and a decrease of up to 75% in the end-to-end delay. For network-wide broadcasting, we show that computing the optimal solution to the broadcasting with cooperative diversity is NP-Complete. Furthermore, we construct centralized and distributed approximation algorithms that significantly improve the performance of the broadcasting. Finally, we propose ETOP, a new path metric that accurately captures the packet delivery cost of a multi-hop path consisting of intermittent links. We analytically compute ETOP and prove that the problem of computing paths with the minimum ETOP cost can be solved by a greedy algorithm. We design such an algorithm and implement it in Linux as part of a legacy routing protocol. Experiments on a 25 IEEE 802.11 node testbed show that in a real environment our algorithm increases the end-to-end TCP goodput by over 50% compared to the best alternative algorithm.