| Even though wireless technology has been around for more than a decade, routing in wireless multihop networks is still challenging due to the high loss rate, dynamic quality, and broadcast nature of wireless links. In this thesis we propose novel routing paradigms for these networks in order to cope with the intermittent conditions of the wireless channel. In addition, we also introduce a theoretical model that captures the interference and contention in the wireless medium to predict the actual throughput of each multihop flow in wireless networks.;We introduce two new routing paradigms that generalize opportunistic routing in wireless multihop networks. In multirate anypath routing, each node uses both a set of next-hops and a selected transmission rate to reach a destination. Using this rate, a packet is broadcast to the nodes in the set and one of them forwards the packet towards the destination. To date, there is no theory capable of jointly optimizing both the set of next-hops and the transmission rate used by each node. We solve this by introducing two new routing algorithms to this problem, and provide a proof of their optimality. Our algorithms generalize the well-known Dijkstra and Bellman-Ford algorithms for the anypath routing case. Different from the common belief that anypath routing algorithms take exponential time, we prove that the proposed optimal algorithms run in polynomial time. In fact, these algorithms have roughly the same running time as regular shortest-path algorithms, and are therefore suitable for deployment. We collected traces from a 802.1 lb testbed network, and our results show that multirate anypath routing performs on average 80%, and up to 6.4x better, than anypath routing with a fixed rate of 11 Mbps.;In another paradigm, called plasma anypath routing, we generalize the previous multirate anypath routing to anycast delivery. This is motivated by the traffic pattern in wireless multihop networks, where each node communicates with a single Internet gateway. However, the specific gateway to which traffic is delivered is not important, as long as the packets reach any gateway. In plasma anypath routing, packets traverse one of the several available paths to reach one of the gateways. The decision of which particular path to take, however, is made on the fly, on a hop-by-hop basis, as the packet traverses the network. We propose an optimal polynomial-time distributed algorithm to find the forwarding set and the bit rate that minimize the cost of each node to the gateways. We also introduce a load balancing scheme to allow overloaded gateways to shift some of the traffic to other underloaded gateways. Using simulations, we show that plasma achieves a 2x throughput gain and a 2.2x delay decrease over multirate anypath routing. If compared to single-path routing, the throughput gain increases to almost 6x.;Finally, we present a new theory which models the behavior of wireless networks using carrier sense multiple access with collision avoidance (CSMA/CA) as the MAC protocol. The proposed theory is able to predict the throughput of each multihop flow in an arbitrary wireless network. The theory respects the interference constraints of the wireless medium and also models the buffer dynamics of multihop flows, where the traffic of the different links used by the same flow is correlated. We show that the behavior of CSMA/CA networks converge to a steady state, which is characterized by each probability π S that an independent link set S is transmitting. We demonstrate that the problem of calculating these steady-state probabilities can be formulated as a system of equations, which is nonlinear for the general case, but linear for the particular case where all nodes are within carrier-sense range. We study the conditions under which the network is stable and the steady-state solution holds. In addition, we show possible extensions and applications for our model, its limitations, and how to apply the developed theory to anypath routing. |
PDF Full Text Request