Routing and Transport Challenges in Multi-hop Wireless Networks

Konstantinos Psounis, USC

Several kinds of multi-hop wireless networks have been proposed in the research literature: wireless mesh networks, an attractive choice for network access in rural communities, office buildings, etc., mobile ad hoc networks that may be intermittently-connected, useful to connect vehicles, underwater monitoring stations, handhelds, etc., and wireless sensor networks with various scientific and industrial applications. Despite the plethora of applications of such networks, low performance issues have prevented them from being widely adopted.

In this work we argue that the performance of multi-hop networks can be significantly improved by clean-slate designs at major network layers. We present two such case-studies. First, in the context of mobile ad hoc networks that may be intermittently connected, we propose to use node mobility to carry data around the network instead of transmitting them.

The main motivation for this approach comes from the disconnected nature of some networks like vehicular and disaster ad hoc networks. Instead of resorting to flooding-based routing techniques, which lead to significant waste of resources and eventually to bad performance, we present a family of routing algorithms that spray a small, fixed number of copies to a carefully selected number of relays, and intelligently route each copy towards the destination. Realistic analysis and extensive simulations show that the proposed schemes are highly scalable, perform very close to an oracle-based optimal scheme, and, interestingly, outperform all existing practical schemes with respect to both delivery delay and number of transmissions per message delivered.

The second case-study investigates transport layer issues. The emphasis is on congestion control and fair rate allocation in the context of static nodes that may form a sensor or a mesh network. A central challenge to improving transport performance in such scenarios is to add contention-awareness. To understand what this means, consider two flows f1 and f2 that share no links or nodes, yet a node that forwards f1's data is within range of a node that forwards f2's data. In contention-based medium access layers, these two nodes would be prevented from transmitting simultaneously. Thus, to ensure that f1 and f2 can effectively contend for the medium, these nodes must detect that they interfere with each other, and exchange signals in case of congestion. With this in mind, we propose distributed, light weight algorithms that detect congestion, determine the exact set of nodes that contend with each other, and appropriately signal this set of nodes to ensure a fair and efficient rate allocation among the flows that traverse them. Analytical and experimental results with TinyOS motes show that the proposed algorithms ensure fairness and yield close to optimal rates.

close this window