Given a probabilistic graph G representing an intermittently connected network and routing algorithm A, we wish to determine a delivery subgraph G[A] of G with at most k edges, such that the probability Conn2(G[A]) that there is a path from source s to destination t (in a graph H chosen randomly from the probability space defined by G[A]) is maximized. To the best of our knowledge, this problem and its complexity has not been addressed in the literature. Also, there is the corresponding distributed version of the problem where the delivery subgraph G[A] is to be constructed distributively, yielding a routing protocol. Our proposed solution to this routing problem is multi-fold: First, we prove the hardness of our optimization problem of finding a delivery subgraph that maximizes the delivery probability and discuss the hardness of computing the objective function Conn2(G[A]); Second, we present an algorithm to approximate Conn2(G[A]) and compare it with an optimal algorithm; Third, we focus on intermittently connected networks, and model the users' mobility within them; and Fourth, we propose an edge-constrained routing protocol (EC-SOLAR-KSP) based on the insights obtained from the first step and the contact probabilities computed in the third step. We then highlight the protocol's novelty and effectiveness by comparing it with a probabilistic routing protocol, and an epidemic routing protocol proposed in literature.

Geometric routing using source-destination locations has been widely suggested as a scalable alternative to conventional routing approaches in mobile ad hoc networks. Recently, there has been considerable attention on face routing in planar graphs constructed from overlay graphs in wireless networks. Given a plane tiled into an infinite mesh of polygons, an overlay graph is defined as one in which a graph edge is defined between two adjacent polygons if a radio link exists between any two nodes located in these polygons. We consider the problem of constructing a connected planar graph from the overlay graph, and geometric routing in such graphs. We prove a specific property of such graphs known as the redundancy property and propose a distributed routing algorithm called grid traversal algorithm (GTA) based on the redundancy property of overlay graphs. The algorithm is both localized and energy efficient, but may not guarantee connectivity in pathological cases. Simulations show that such disconnections are rare in practise and that GTA performs very well in terms of percentage of data delivered, data delay and overhead compared to GPSR, a geometric routing protocol that routes on a planar graph extracted from the unit disk graph.

Routing in Intermittently Connected Networks (ICN) is a challenging problem due to the time varying nature of network connectivity. In this work, we focus on a special class of ICN formed by mobile ad hoc users called ICMAN. A recent study of wireless users' mobility traces revealed that users usually move between a small set of socially significant places called hubs to form so-called orbits [6]. To exploit the knowledge about such mobility profiles, we propose a hub-level routing method, and two versions of user-level routing methods. We compare these approaches with Epidemic routing [21] to highlight the advantages of sociological orbit aware routing within ICMAN in terms of achieving a higher throughput and a lower overhead.

In this paper, we introduce a novel concept of integrating ''macro-mobility" information obtained from the sociological movement pattern of mobile MANET users into routing. The extraction of this mobility information is based on our observation that the movement of a mobile user exhibits a partially repetitive "orbital" pattern involving a set of "hubs" in practice. This partially deterministic movement pattern is both practical and useful in locating nodes and routing packets to them without the need for constant tracking or flooding. Leveraging on this hub-based orbital pattern, we propose a sociological orbit aware location approximation and routing (SOLAR) protocol. Through extensive performance analysis we show that SOLAR significantly outperforms conventional routing protocols like dynamic source routing (DSR) and location aided routing (LAR) in terms of higher data throughput, lower control overhead, and lower end-to-end delay.

A major challenge faced in mobile ad hoc networks (MANET) is locating the devices for communication, especially with high node mobility and sparse node density. Present solutions provided by the ad hoc routing protocols range from flooding the entire network with route requests, to deploying a separate location management scheme to maintain a device location database. In this work, we propose a novel scheme called acquaintance based soft location management (ABSLM) in MANET. In ABSLM, nodes make use of the real life concept of making acquaintances and keeping in touch with them regarding each other's current locations. ABSLM has a two-fold aim: to avoid the overhead of flooding: and to use a 'soft' location management setup that does not require a strict location management strategies and is thus computationally less expensive than the standard 'hard' location management schemes. Simulation results show that the ABSLM not only outperforms the existing flooding schemes in terms of throughput, overhead and location discovery latency, but also achieves a performance comparable to 'hard' grid based location management schemes with a much lower control overhead.

Geography based routing in mobile ad hoc networks is an application that uses the location information of nodes in a network to route data packets. Since the amount of network state information that each node needs to maintain in order to route packets is minimal, location based routing is considered scalable compared to existing routing protocols in ad hoc networks. However, geographic routing requires location management, where the locations of destination nodes needs to be found before the actual routing can begin. Many location management schemes have been proposed in the literature, but no prior work has quantitatively compared the scalability of these protocols with respect to the increase in the number of nodes in the network. In this work, we use a theoretical framework to show the asymptotic scalability of three location management protocols. We also carry out extensive simulations to study the performance of these protocols under practical considerations. Our results indicate that all protocols perform well, with a slight performance degradation with the increasing network size. In particular, the hierarchical grid location management protocol (HGRID) performs the best for all practical purposes, and is a candidate for location management in a wireless network architecture.