Mobility-Based Routing in Opportunistic Networks

Introduction

Opportunistic networks (OppNets) are made with the assumption of people or devices carrying mobile devices, without depending on an existing network topology. Disconnections and mobility in OppNets are considered as norms not exceptions (Verma & Srivastava, 2011). During node mobility when nodes come close to each other, devices can create small mobile ad hoc network. This might not last for a long time, since nodes may be frequently isolated from each other. In other words, nodes are only intermittently connected to each other, and this can change dynamically with time. End to end path can only exist when the sequence of connectivity graphs over time intervals overlap (D'Souza & Johny, 2010). This implies a message can be sent over an existing link which might not last for long. Sometimes end to end connectivity between both the source and the destination nodes is absent during message transmission. Thus message is buffered at the next hop waiting for the next link to come up; this is repeated until message reaches the destination node; this is known as store-carry-forward routing pattern.

Nonetheless, this has imposed a new model of routing in which forwarding decisions made locally, and predict future connectivity.

In brief, OppNets use mobility as a technique for communication between disconnected nodes (Verma & Srivastava, 2011).

Routing protocols in the mobility-based class of OppNets exploit node mobility information and patterns to make forwarding decisions. The effectiveness of routing in OppNets is highly dependent on node mobility. It has been proven that ad hoc networks performance in message routing is improved with node mobility, especially when efficient routing techniques are deployed (Hoang & Silvia, 2009).

Routing in mobility-based class comprises of various protocols. The protocols that lay in this category mostly exploit some context information. Context information includes nodes mobility patterns and places nodes often visit. Thus, availability of context information is vital for algorithms where they base their forwarding decisions on. According to Srivastava and Verma (2011) availability of context information affects performance in mobility-based routing protocols. The protocols that fall in this category are Probabilistic Routing Protocol using History of Encounters and Transitivity (PRoPHET), Meeting and Visits (MV), MobySpace, Bubble Rap, MaxProb and Context-aware Adaptive Routing (CAR).

PRoPHET is the evolved version of epidemic, a flooding-based context-oblivious algorithm, and it relies on the concept of delivery predictability. According to Lindgren et al. (2003) node movements can be predicted based on its repetitive behavior pattern, and nodes have greater delivery predictability when they visit more nodes (Chiara et al., 2008). PRoPHET calculates the delivery predictability from a node to the destination node according to the preserved contact history. The delivery predictability is the probability of a node meeting a certain destination. MV algorithm discovers information on meetings amongst peer nodes and their visiting locations. The information on meetings and visiting places stored at each node to estimate message delivery probability. While in MobySpace, source node’s mobility pattern is used as context information to forward message to the destination. Message is then forwarded to the node with similar mobility pattern to the destination node.

Bubble Rap is based on the assumption that nodes belong to social communities. It exploits context information such as popularity or sociability in the network. Nodes belonging to the same community as the destination node are usually referred to as good forwarders to the destination (Hoang & Silvia, 2011; Verma & Srivastava, 2011).