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.