Routing With Node Mobility in Wireless Networks

Introduction

Mobile wireless networks help us produce and consume information anytime and anywhere. In ad hoc mobile wireless networks, due to the lack of communication infrastructure, the problem of information delivery becomes harder. In this project, we try to understand the properties and performance limits of mobile ad hoc networks. We also leverage stable properties of these mobile networks to design efficient information delivery algorithms.

Understanding the Performance of Mobile Networks

We try to estimate the maximum achievable performance of a mobile wirelss network. Analysis of mobile networks is challenging because such analysis must take into account the link volatility caused by network dynamics as well as node mobility. Although a network is partitioned at a given time instant, the routing might still be feasible if we consider a time interval. We build on prior work on time-expanded graphs and apply it to the analysis of mobile ad hoc networks. We also reduce the number of nodes in the time expanded graph, and hence space complexity of the analysis, by pruning the nodes that remain static over multiple intervals. We were able to scale the performance analysis to hundreds of nodes.

Predictive Routing to Mobile Sinks

If the mobility of the mobile sink has some structure to it or is predictable to some extent, we can exploit the knowledge about the trajectory to perform predictive routing. We can route data, not to the sink directly, but to the relay nodes along the predicted path of the mobile node. The data remain stashed on those nodes until the mobile node passes by and picks up the data. We use linear programming to find the choice of stashing nodes that minimizes the communication overhead while guaranteeing robustness against link and node failures, as well as trajectory uncertainty. We found that this technique achieves data delivery efficiency comparable to what is possible with perfect knowledge about future trajectory of the mobile node.

Hierarchical Routing Robust to Sink Mobility

To make information delivery to mobile sinks efficient, our strategy is to select, in a distributed manner, a set of well-placed nodes (warehouses) to act as intermediaries between the information sources and clusters of nearby users. Warehouses are selected via the distributed construction of hierarchical well-separated trees (HSTs), which are sparse structures that induce a natural spatial clustering of the network. These trees are agnostic to the number and position of sources as well as to the mobility patterns of users. Our sparse and flexible infrastructure is precomputed and efficiently reused by sources and users, its cost amortized over time. Our algorithm ensures with high probability a guaranteed stretch bound for the information delivery path, and is robust to lossy links and node failure by providing alternative HST-induced routes. Nearby users are clustered and their requests aggregated, further reducing communication overhead.

Publications