Collaborative routing in mobile partitioned networks

Embedded wireless networks find a broad spectrum of applications in transportation, environmental monitoring, logistics, supply chain management, and "pocketswitched" communication. The node mobility patterns in these applications tend to give rise to spatially heterogeneous node distributions, which may cause network partitions. In this thesis, we consider the problem of routing in mobile networks under such challenging conditions. More specifically, we endeavor to identify features of mobility common to different applications, in order to devise routing methods that are tailored to exploit these features. We explore two features in particular, (i) predictability and (ii) stable and heterogeneous spatial node distribution. A mobility process is predictable if the future location of a node can be well estimated, given knowledge of its current and past locations and possibly other statistics. We show how the performance of routing can be improved by explicitly incorporating mobility prediction. Specifically, we consider the performance of Last Encounter Routing (LER) under a simple synthetic random waypoint (RWP) mobility model. We extend the LER algorithm so that it takes into account predicted node trajectories when making routing decisions, and we show that this significantly improves its performance. A mobility process has a stable spatial node distribution if, informally, the node density remains the same over time, even though individual nodes are not constrained in space. This is a common feature of many mobility patterns because the spatial distribution is determined by the natural or constructed environment, regardless of the behavior of individual nodes. This typically leads to heterogeneous connectivity and to network partition, where highly connected clusters are interspersed with low-connectivity regions. We model such a situation with a set of stable concentration points (CPs) characterized by high node density, and with a mobility process that describes how nodes move between these islands of connectivity. We study two instances of this model: the G-model, where the CPs and the flow of nodes are abstracted as a graph, and the H-model, where nodes perform heterogeneous random walks on the plane. We exploit the presence of this stable CP topology in order to develop an efficient routing algorithm under these two mobility models. Our routing algorithm, Island Hopping (IH), exploits knowledge of the CP topology to make routing decisions. IH achieves a very good delay-throughput trade-off compared with several other existing routing algorithms, and it scales well with the network size. In many situations, it would be unrealistic to assume that CPs and the flows of mobile nodes among them are known a-priori. We develop methods, collectively called Collaborative Graph Discovery (COGRAD), that allow the nodes to discover the CP graph without any explicit signals from the environment (such as GPS coordinates or fixed beacons). We show that COGRAD can replace an oracle with knowledge of the CP topology after a sufficient warm-up period, allowing IH to operate even in scenarios without any cues from the environment.

Hierarchical Routing over Dynamic Wireless Networks

Suhas Diggavi, Matthias Grossglauser, Dominique Florian Tschopp

Dynamic networks are those where the topology changes over time and therefore efficient routes need to be maintained by frequent updates. Such updates could be costly in terms of consuming throughput available for data transmission, which is a precious resource in wireless networks. In this paper, we ask the question whether there exist low-overhead schemes for dynamic wireless networks, that could produce routes that are within a small constant factor (stretch) of the optimal route-length. This is studied by using the underlying geometric properties of the connectivity graph in wireless networks. For a class of models for mobile wireless network that fulfill some mild conditions on the connectivity and on mobility over the time of interest, we can design distributed routing algorithm that maintains the routes over a changing topology. This scheme needs only node identities and therefore integrates location service along with routing, therefore accounting for the complete overhead. We analyze the worst-case (conservative) overhead and route-quality (stretch) performance of this algorithm for the aforementioned class of wireless network connectivity and mobility models. In particular for these models, we show that our algorithm allows constant stretch routing with a network wide control traffic overhead of

O(n\log^2 n)

bits per mobility time step (time-scale of topology change) translating to

O(\log^2 n)

overhead per node (with high probability for wireless networks with such mobility model). Additionally, we can reduce the maximum overhead per node by using a load-balancing technique at the cost of a slightly higher average overhead. We also demonstrate through numerics that these worst-case bounds are quite conservative in terms of the constants derived theoretically.

2007

On Clustering Phenomenon in Mobile Partitioned Networks

Matthias Grossglauser, Natasa Sarafijanovic-Djukic

According to different kinds of connectivity, we can distinguish three types of mobile ad-hoc networks: dense, sparse and clustered networks. This paper is about modeling mobility in clustered networks, where nodes are concentrated into clusters of dense connectivity, and in between there exists sparse connectivity. The dense and sparse networks are extensively studied and modeled, but not much attention is paid to the clustered networks. In the sparse and clustered networks, an inherently important aspect is the mobility model, both for the design and evaluation of routing protocols. We propose a new mobility model for clustered networks, called Heterogeneous Random Walk. This model is simple, mathematically tractable and most importantly it captures the phenomenon of emerging clusters, observed in real partitioned networks, in an elegant way. We provide a closed-form expression for the stationary distribution of node position and we give a recipe for the "perfect simulation". Moreover, based on the real mobility trace we provide strong evidence for the main macroscopic characteristics of clustered networks captured by the proposed mobility model. For the very first time in the literature we show evidence for the correlation between the spatial speed distribution and the cluster formation. We also present the results of the analysis of real cluster dynamics caused by nodes' mobility.

ACM2008

A Parsimonious Model of Mobile Partitioned Networks with Clustering

Matthias Grossglauser

Mobile wireless networks frequently possess, at the same time, both dense and sparse regions of connectivity; for example, due to a heterogeneous node distribution or radio propagation environment. This paper is about modeling both the mobility and the formation of clusters in such networks, where nodes are concentrated in clusters of dense connectivity, interspersed with sparse connectivity. Uniformly dense and sparse networks have been extensively studied in the past, but not much attention has been devoted to clustered networks. We present a new mobility model for clustered networks, which is important for the design and evaluation of routing protocols. We refer to our model as Heterogeneous Random Walk (HRW). This model is simple, mathematically tractable, and it captures the phenomenon of emerging clusters, observed in real partitioned networks. We provide a closed-form expression for the stationary distribution of node position and we give a method for “perfect simulation”. Moreover, we provide evidence, based on mobility traces, for the main macroscopic characteristics of clustered networks captured by the proposed mobility model. In particular, we show that in some scenarios, nodes have statistically very similar mobility patterns. Also, we discuss cluster dynamics and the relationship between node speed and node density.

2009

Hierarchical Routing over Dynamic Wireless Networks

Suhas Diggavi, Matthias Grossglauser, Dominique Florian Tschopp

O(n\log^2 n)

bits per mobility time step (time-scale of topology change) translating to

O(\log^2 n)

2007