Opportunistic Routing in Mobile Ad Hoc Networks

Abstract

Routing in opportunistic mobile ad hoc networks (MANETs) is characterized by intermittent and sporadic communication opportunities between portable devices. As a result, a path between the source and the destination(s) may only exist for a brief and unpredictable period of time, thereby leading to network partition. Most existing routing approaches store data packets locally and forward them when in reach of a mobile peer that carries the data packets closer to the destination. Through a survey of recent literature, this chapter will provide an overview of the routing protocols that exploit intermittent communication opportunities for increased data transmission success in MANETs, and characterize them using the following three aspects: (1) how does the protocol discover and exploit the intermittent communication opportunities in a mobile environment? (2) How does the protocol address multicast, which is a common data dissemination pattern in an opportunistic communication environment? and (3) What kind of real-world applications are enabled by the use of opportunistic routing protocols?

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

6.1 Introduction

Current trends in networking-architecture developments, e.g., delay and disruption-tolerant networks, aim to deal with the disconnections that naturally and frequently arise in wireless environments. There are many asynchronous applications, e.g., e-mail, multimedia messaging, cached web access, file sharing, and blogging, which do not require continuous network access. Opportunistic networks (OPNETs) is a fast emerging paradigm that is created out of mobile devices carried by people, without relying on any preexisting network topology [1]. In OPNETs, network irregularities such as frequent disconnection, network partition, and node mobility are considered as norms. To that end, some of these irregularities are even used as techniques to provide communication opportunities between disconnected groups of nodes, rather than a drawback to be solved.

Because of the above unconventional approach to handle network irregularities, routing is one of the most challenging issues in the design of OPNETs. To that end, a complete path between source and destination is often unavailable. OPNET routing protocols solve this problem by removing the assumption of physical end-to-end connectivity and allow disconnected nodes to exchange messages. In OPNETs, intermediate nodes store messages when there is no forwarding opportunity toward the destination, and exploit any future contact opportunity with other mobile devices to bring the messages closer to the destination [2–4]. Figure  6.1 illustrates an example of how opportunistic communications can be exploited to exchange messages between disconnected nodes in an urban environment. As shown in Fig.  6.1, Bob wishes to send a message to his family but has no 2G/3G connectivity. He opportunistically forwards the message using the Bluetooth radio in his phone to another car driving in the same direction as his residence. The car moves through the traffic in the city, and transfers the message using a Wi-Fi link to a school bus going in the same direction as Bob’s residence. Next, the bus forwards the message using its Bluetooth radio to the cellphone of a kid who is disembarking at bus stop in the same area where Bob lives. When the kid walks past Bob’s residence on his way to home, the message is finally delivered to its destination. As is shown in this example, a network connection between the source and destination was never available; however, by opportunistically exploiting contacts among heterogeneous devices, the message is delivered hop-by-hop closer to the destination, and eventually is received by the destination.

Fig. 6.1

An example of exploiting opportunistic communications

Through a survey of the key research approaches to routing in OPNETs, this chapter provides a detailed overview of the routing protocols that explicitly focus on exploiting connection opportunities for routing in an intermittently connected network. The remainder of this chapter is organized as follows: Section  6.2 discusses the various aspects of routing in OPNETs and proposes an analytical framework to characterize the recent relevant research approaches. Section 6.3 provides a detailed overview of a number of routing protocols designed for OPNETs. Section 6.4 discusses a few applications that are enabled by use of opportunistic communications. Section 6.5 identifies a few challenges in current research efforts and Sect. 6.6 concludes the chapter.

6.2 What is an Opportunistic Mobile Ad Hoc Network?

Opportunistic Networks is an emerging communications paradigm that supports a “whenever, wherever” style of communications between mobile nodes. In OPNETs, no assumption is made about the availability of an end-to-end path between the source and destination(s)—in fact they might never be connected to the same network at the same time, but still be able to exchange messages between them.

Figure  6.1 illustrates an example of how communication opportunities change with time in OPNETs due to node mobility. OPNETs typically comprise heterogeneous wireless devices in motion (e.g., portable devices carried by mobile users, vehicles, etc.) that form dynamic clusters or islands of connectivity. These devices take advantages of radio contacts with peers as and when they become available, and cooperate in routing data. It may take multiple discontinuous wireless contacts or hops before the data is transferred from the source to the destination over a period of time. As shown in Fig.  6.1, there is no direct path from node S to node D at any given time. Packets from S can be delivered to D if intermediate nodes store-and-forward the packets in the following fashion: at time $t_1$, node S sends the packet to node 2; at $t_2 > t_1$, node 2 forwards the packet to node 3; and at $t_3 > t_2 > t_1$, node 3 forwards the packet to node D.

Fig. 6.2

An example of how node mobility creates communication opportunities in OPNETs at time interval $t_1,t_2$ and $t_3$ $(t_3>t_2 > t_1)$

This section presents a set of definitions of OPNETs, elaborated by recent related research efforts, which in turn provide guidelines for building a framework that is used to analyze these existing research efforts.

6.2.1 Definition

The term “opportunistic” with regard to wireless networking implies the tendency of network devices to exploit available resources in the network as and when possible. Several concepts behind OPNETs originate from the research efforts on delay-tolerant networks (DTN) that has been conducted within the Internet Research Task Force.¹ DTNs are characterized by their lack of connectivity, resulting in unavailability of instantaneous end-to-end paths between source and destination(s). As a result, DTN routing protocols must take to a “store-and-forward” approach, where data is incrementally moved and stored throughout the network in hope that it will eventually reach its destination(s). Pelusi et al. [3] argues that there is no clear separation of concepts for OPNETs and DTNs; however, OPNETs correspond to a more general and flexible concept which includes DTNs. To that end, DTNs assume a priori knowledge of Internet-like topologies in which several links between gateways could be available just at certain (possibly unspecified) times, and routes are typically computed via legacy Internet techniques by taking into consideration the link unavailability just as another component of link cost. On the other hand, in OPNETs it is not mandatory to have a priori knowledge of the network topology—instead, routes are computed at every hop before a packet is forwarded and thus each single node acts as a gateway. Phanse et al. [5] proposed a more formal definition of OPNETs, which is the following: “Opportunistic networks are intrinsically fault tolerant for they are not limited by the end-to-end connectivity assumption. These networks are distributed and self-organizing in that the control and management is largely up to the individual devices or users (within the boundaries defined by the network operator’s policies, if part of a commercial network). The communication in these networks is localized, i.e., decisions such as routing are made by devices based on locally available information. Opportunistic also means being able to take advantage of locally accessed global information, where devices implicitly convey global reachability information strictly through local interaction.”

In the last few years, there have been a lot of research activities focusing on various applications of multi-hop mobile ad hoc networks (MANETs). Originally conceived for military applications, MANETs have recently found increasing applications in many civil scenarios such as search and rescue operations, sensor networks, connecting students on campus, sharing free Internet connection etc. MANETs are similar to OPNETs in that neither network relies on a centralized entity; their architecture is decentralized by definition. Due to node mobility, nodes connect and disconnect as they move in and out of communications range. Connection and disconnection may also happen because devices are turned on or off unpredictably. However, MANET routing algorithms focus on end-to-end communications paradigm, which takes both user mobility and limited resources into account. Link failures due to frequent connection/disconnection are treated as anomaly and handled by employing route management/recovery strategies. On the other hand, routes are formed online in OPNETs with the data message being forwarded one link at a time, as links in the route become available. OPNETs are, therefore, an extension of MANET with the end-to-end communications paradigm relaxed or removed, if necessary. Hence, the rest of this chapter will refer to OPNETs as opportunistic mobile ad-hoc networks (OPMANETs).

6.2.2 Challenges of Routing in OPMANETs

OPMANETs are highly challenged networks with intermittent connectivity and variable link performance. In such environments, complete end-to-end routes from the source node to the destination(s) may not exist from time-to-time or at all. In addition, the links are unstable and may change or break quickly. In order to make communications possible in OPMANETs, the routing protocols often extend the “store-and-forward” approach used in DTNs to “store-carry-forward” approach—in this approach, there are situations when a suitable next-hop node may not be immediately found for the current node to forward the data to. In that case, the current node will need to buffer the data until the node gets an opportunity to forward the data and must be capable of buffering the data for a considerable duration [2]. The difficulties in designing a protocol for efficiently and successfully routing messages to their destination(s) in OPMANETs are outlined in Table  6.1.

Table 6.1 Challenges in routing in OPMANETs

6.2.3 Analysis Framework

Using these above perspectives, this book chapter proposes a simple framework to analyze the existing routing protocols in OPMANETs, choosing three main axes to characterize them. These axes refer to the following questions:

• Discovery and Dissemination. How does the protocol discover and exploit the intermittent communication opportunities in a mobile environment? How does the protocol provide reliable multi-hop, multi-destination data delivery, which is a common data dissemination pattern in an opportunistic communication environment?

• Resource Usage. How does the protocol impact on the battery power, CPU usage, and memory of the local device while participating in a peer-to-peer opportunistic communication environment with intermittent connectivity?

• Applications. What kind of real-world applications are enabled by the use of OPMANET routing protocols? What are their quality of service (QoS) requirements?

The remainder of this chapter will use these aspects to characterize a number of recent routing protocols in OPMANETs.

Fig. 6.3

A taxonomy of routing approaches in OPMANETs

6.3 Routing in Opportunistic Mobile Ad Hoc Networks

Routing is the one of the most compelling challenges in the design of OPMANETs due to intermittent and unpredictable connectivity, lack of knowledge about the frequently changing network topology, and resource constraints of mobile devices. Figure  6.3 shows a possible taxonomy of the routing algorithms in OPMANETs with respect to how they disseminate data to destinations. Based on the number of copies of a data message forwarded by each node, the routing algorithms can be broadly classified into four categories: Forwarding-based (single copy) approach, Flooding-based (multiple copies) approach, Hybrid approach, and Social behavior-based approach. In the forwarding-based approach, the data message is forwarded to only one single node in each step of routing. This approach tries to reduce the buffer usages and the number of messages transferred in the network at the expense of increased CPU usage (for finding a suitable next-hop node), long delays, and low delivery ratios. On the other hand, flooding-based approaches may generate multiple copies of the same data message—the copies of the message can either be spread in the network like a disease epidemic or each copy can be routed separately for increased efficiency and robustness. This approach achieves lower delays and higher delivery ratio at the cost of increased storage requirement and higher number of data message transmissions. The hybrid approaches combine features from forwarding-based approaches with flooding-based approaches to achieve low data dissemination latency while limiting the network overheads. Lastly, the social behavior-based approaches make forwarding decisions using locally observed patterns about social ties between nodes to predict future contact opportunities. This section provides an overview of these various routing algorithms and characterizes them using the analytical framework proposed in Sect.  6.2.

6.3.1 Forwarding-Based Approaches

Based on how the forwarding decision is made (i.e., how the best next-hop node is chosen), the forwarding-based routing approaches can be divided into the following two sub-categories, (1) direct transmission-based forwarding—protocols in this category limit the number of hops traveled by a data message, and (2) context-based forwarding—protocols in this category exploit the context in which the nodes are operating to decide which node to forward the data message to as well as whether it should transmit the message immediately or hold the message until it meets a better node. Context-based forwarding can further be divided into four sub-sub-categories, i.e., (1) history/estimation-based forwarding, (2) location-based forwarding, (3) mobility-based forwarding and (4) link asymmetry-based forwarding. History/estimation-based protocols allow a node to make better forwarding decision by estimating the forwarding probability of its neighbors based on historical data. Location-based forwarding protocols use locations of nodes as the context to make forwarding decisions—the best next-hop node is the one that moves the data message closest to the destination. Mobility-based protocols allow a node to make better forwarding decision by estimating the forwarding probability of its neighbors based on mobility patterns/traces. Link asymmetry-based protocols exploit asymmetric communication opportunities in heterogeneous OPMANETs for increased data transmission success and lower latency. This subsection provides a detailed overview of the forwarding-based approaches.

6.3.1.1 Direct Transmission-Based Forwarding

Direct transmission-based forwarding approaches minimize the number of data message transmissions by limiting the number of hops traveled by the data message between source and destination(s). Spyropoulos et al. [6] proposed a 1-hop forwarding approach which allows the source to hold onto the data message and deliver to the destination(s) only when they are within transmission range. This approach has minimal overhead, but the delay could be very long as it is unbounded. Grossglauser et al. [7] proposed a 2-hop forwarding approach based on a theoretical framework, in which nodes freely roam around the network and every node gets close to any other node for a random time duration per time slot. Within this framework, a node $s$gives a message, addressed to destination node $t$, to another randomly chosen 1-hop neighbor $r$. The node $r$ transmits the message to the destination $t$ when it happens to be within the communications range of $t$. Hence, a message will only travel 2-hops and no message will be transmitted more than twice. This scheme claims that a message is always guaranteed to be delivered, even if its delivery time is averaged over many time slots.

Fig. 6.4

Example of 1-hop direct transmission-based forwarding approach [6]

6.3.1.2 Context-Based Forwarding

Context-based forwarding approaches exploit the context in which nodes are operating so as to identify suitable next hops toward the eventual destinations. Context-based forwarding approaches can be divided into the following four types:

• 1. History/estimation-based forwarding. History/estimation-based protocols allow a node to make better forwarding decision by estimating the forwarding probability of its neighbors based on historical data. Protocols in this category differ in the parameters they use for making this estimation; commonly used parameters are previous connection/disconnection time between nodes, local residual battery level, mobility rate, and number of messages forwarded by a neighbor in the past, etc. Jain et al. [8] proposed a knowledge-based routing scheme, which is the first study in this area. Depending on the amount of knowledge available about network topology characteristics and traffic demand, they defined four knowledge oracles. Each oracle presents some particular knowledge of the network, e.g., schedule of meetings between nodes. This approach applies traditional shortest path routing techniques to OPNETs by exploiting the knowledge oracles. Messages are forwarded over the shortest path using source routing techniques. This approach was extended by Jones et al. [9], who proposed minimal estimated expected delay (MEED) routing. MEED computes the expected delay using the observed contact history, in which a node records the connection and disconnection time of each contact over a sliding history window. Link-state updates are propagated to all nodes in the network using an epidemic link-state protocol. The routing table is recomputed each time a contact arrives and before a message is to be forwarded, resulting in per contact routing. Tan et al. [10] proposed a shortest expected path routing (SEPR) to maintain a topology map at each node to every other node. SEPR calculates the link forwarding probability based on history data of the duration of last contact between two nodes. Each message stored in buffer is assigned an effective path length (EPL); the value is set at infinity when it is inserted in the cache for the first time. When two nodes meet, they exchange the EPL values—a smaller EPL value suggests a higher probability of delivery. When a node receives a smaller EPL, it will update its local EPL value. As a result, during the cache replacement procedure, those messages with smaller EPL values to the destination are removed first. EPL is also used in deciding which nodes to forward the messages. Using SEPR protocol, the same message could be forwarded to multiple nodes to increase reliability and to reduce delay. Musolesi et al. [11] proposed context-aware routing (CAR) protocol in which each node in the network is in charge of producing its own delivery probabilities toward each known destination node. Delivery probabilities are exchanged periodically so that, eventually, each node can compute the best carrier for each destination node. The best carriers are computed based on the multiattribute utility theory applied to generic attributes of the node’s context, e.g., the residual battery level, the rate of change of connectivity, the probability of being within reach of the destination, and the degree of mobility. When the best carrier receives a message for forwarding, it stores it in a local buffer and eventually forward it to the destination node when met or, alternatively, to another node with a higher delivery probability. Burgess et al. [12] proposed a protocol called MaxProp to schedule transmission of messages to its peers and determine which messages should be deleted when buffer space is almost full. Messages are scheduled based on the path likelihood to peers, which in turn is computed using historical data. In addition, several complementary mechanisms, e.g., acknowledgments, head-starts for new packets, and lists of previous intermediaries are used.

• 2. Location-based forwarding. In the location-based forwarding approaches, nodes will choose the neighbor which moves the data message closest to the destination(s). LeBrun et al. [13] proposed a method using the motion vector (MoVe) of mobile nodes to predict their future location. The MoVe scheme uses the knowledge of relative velocities of a node and its neighboring nodes to predict the closest distance between two nodes in future. After the future locations are calculated, messages are passed to nodes that are moving closer to the destination(s). Shen et al. [14] proposed a relay-based routing scheme, called interrogation-based relay routing (IBRR), for ad hoc satellite networks where nodes are required to buffer data for a certain period of time until the node gets an opportunity to forward it. In IBPR, the nodes interrogate each other to learn more about network topology and node capacity to make intelligent routing decisions. Given the dynamic topology and heterogeneity of an ad hoc satellite constellation, it is very difficult to decide whether or not to forward the data to a given node. To make good routing decisions, satellites use a one-hop look-ahead strategy in which the locations of neighboring nodes and their neighboring nodes are tracked. The parameters being used to make forwarding decisions are spatial and orbital locations of the candidates, bandwidth of the inter-satellite links, relative velocity/mobility between two nodes, vicinity to other satellites and ground stations, capability of the candidates satellites, and data transmission time. Lin et al. [15] propose indoor geographic routing protocol (INGEO) for mobile ad hoc networks, in which the velocity displacement vectors are used for relocating the mobile nodes. Basagni et al. [16] handle client mobility by forwarding messages to all one-hop neighbors located inside a Forwarding Zone (FZ) in the destination’s direction. To that end, they proposed distance routing effect algorithm for mobility (DREAM), which uses a probabilistic mathematical model to define the FZ, based on the locations of the source and destination(s) and nodes in one-hop neighborhood. The FZ covers a circular region capturing all possible locations of the roaming subscriber since the last location update. Location-based forwarding approaches incur additional overhead while obtaining location updates of their own and neighboring nodes.

• 3. Mobility-based forwarding. The mobile devices in OPMANETs move while following certain known patterns such as walking along a street or driving down the highway. Such regular motion patterns help the intermediate nodes to make accurate estimation of which nodes move toward the destination with higher probability. Leguay et al. [17] proposed a strategy that uses a high dimensional Euclidean space, called mobility pattern spaces (MobySpace) where each axis represents a possible contact between two nodes, and the distance along an axis measures the probability of that contact to occur. Two nodes that have similar sets of contacts, and that experience those contacts with similar frequencies, are close in the MobySpace. The best forwarding node for a message is the node that is as close as possible to the destination node in this space. In this virtual contact space, the knowledge of all the axes of the space also requires the knowledge of all the nodes that are circulating in the space. This full knowledge, however, might not be required for successful routing. Becker et al. [18] proposed model-based routing (MBR) that uses world models of the mobile nodes for a better estimation of the locations of the relaying nodes and the receiver, without flooding the network. World models contain location data (e.g., road maps or building charts) and user profiles indicating the motion pattern of users; these location and user profiles are used by MBR to choose a relay that moves toward the target with higher probability. Chen et al. [19] proposed a mobility-based forwarding approach for nodes moving along on a highway. This approach takes advantages of predictable node movement that creates connection opportunities to relay messages in a store-and-forward fashion in an intermittently connected vehicular ad hoc network with frequent network partitions. Messages are propagated greedily each time by forwarding it to the neighbor closest to the destination. Two kinds of transmission schemes are used, i.e., pessimistic forwarding and optimistic forwarding, which are distinguished by how long the messages are allowed to stay buffered at intermediate nodes. To that end, a pessimistic forwarding scheme drops a message when no suitable next-hop node is found. On the other hand, in optimistic forwarding, messages without next hops may remain on intermediate nodes for some time, hoping that physical movement of nodes eventually creates a forwarding opportunity. Jetcheva et al. [20] proposed a realistic approach in which traces from a real-life scenario are used for modeling of user mobility. This approach uses a fleet of city buses as mobile nodes to obtain mobility trace data which is then used to simulate potential latency and routing characteristics, assuming various radio coverage models. Su et al. [21] study the usage of real user mobility and opportunistic pair-wise contacts to form OPMANETs. Their study revealed that nodes exhibit signs of regularity and affinity of contact. Furthermore, in many cases, success of message delivery from any source to destination is not evenly distributed among the intermediary nodes—this observation can potentially be used by the source nodes for making better routing decisions.

• 4. Link asymmetry-based forwarding. Link asymmetry is a common phenomenon in OPMANETs due to varying transmission ranges, node mobility, heterogeneous radio technologies, and irregularities in radio ranges and path and packet loss patterns. Link asymmetry-based forwarding approaches in OPMANETs exploit asymmetric communication opportunities for shorter delay; however, the cost of discovering asymmetric links in the network is often non-negligible. Sang et al. [22] proposed a novel neighbor discovery technique based on a new one-way link metric in order to identify high reliability forward asymmetric links. They presented a local procedure for their estimation. Duros et al. [23] proposed a modification to the well-known Internal Gateway Protocol OSPF to handle asymmetric satellite links by sharing neighbor tables in Hello packets. Wang et al. [24] proposed a routing protocol for power constrained networks with asymmetric links, where they discover an asymmetric neighbor with the help of a mutual third-party proxy set. Mitra et al. [25] proposed a protocol, called asymmetric geographic forwarding (A-GF), which discovers and exploits asymmetric links in a network, i.e., instead of eliminating these links, A-GF uses them for routing to reduce the routing hop count (and latency) and to increase the routing reliability when there are no symmetric paths available. A-GF modifies the “Hello message” approach of GF to discover asymmetric links, proactively monitors the changes in conditions of discovered links, and ranks neighbors based on perceived link stability. During routing, a node considers both this ranking and the progress a neighbor can make towards the sink location in terms of geographical distance (thereby considering both reliability and performance). Figure  6.5 shows the asymmetric link discovery and notification procedure in A-GF. In Fig.  6.5a, when node B gets a periodic Hello packet from node A, B checks if it is recorded in the neighbor list in the received packet. If B is listed in A’s neighbor list, then both A and B can hear each other and the link A$\leftrightarrow$B is symmetric. If B is not listed in A’s neighbor list, B knows that the link A$\rightarrow$B is asymmetric. In A-GF, node A and B are defined as the up-link node and the down-link node. In general, an asymmetric link is usable in the direction from the up-link node to the down-link node. However, only B is aware of the asymmetric link A$\rightarrow$B, but A would not be able to exploit it. Sending a direct (single hop) report from B to A is not possible. Therefore, A-GF routes a small control message, called asymmetric notification (AN), toward the location of the up-link node A, along a multi-hop tunneling path to notify node A of the existence of the outgoing asymmetric link.

Fig. 6.5

Asymmetric link discovery and notification in A-GF [25]

6.3.2 Flooding-Based Approaches

In OPMANETs, applications often require to distribute data among a group of nodes. When the group size is greater than one, the delivery semantics is usually multicast in which the data is intended to be delivered to all members in the same multicast group. Multicasting has often been realized by flooding in wireless networks. The heuristic used by flooding-based algorithms is that data should be diffused all over the network because no knowledge about an appropriate next-hop node is available. Flooding-based techniques work well in highly mobile networks with many communication opportunities between nodes. In addition, such routing approaches result in shorter message delivery delay in highly mobile networks, only at the expense of high resource consumption. To that end, flooding-based approaches suffer from high contention and may potentially lead to network congestion due to large number of data transmissions associated with flooding. Consequently, flooding-based approaches employ a variety of policies to limit flooding, e.g., imposing a maximum number of hops to each data message, or by limiting the total number of message copies present in the network at the same time.

6.3.2.1 Epidemic Routing Approaches

Epidemic routing algorithms constitute a key class of algorithms in OPMANETs that belong to the category of flooding-based approaches. As suggested by the term “epidemic”, the routing approaches in this category diffuse data in the network in a fashion similar to diseases or viruses (i.e., by means of pair-wise contacts between nodes). A node is susceptible to infection when it has not yet received the data message. A susceptible node becomes infected when it comes into contact with an infected node and receives the message from it. After catching the infection, the infected node stores the message locally and it is healed when (if at all) it delivers the message to the destination node(s). A healed node also becomes immune to the same disease and does not provide relaying of the same message. Vahdat et al. [26] proposed the first routing algorithm in this category; they showed that the epidemic algorithm ensures that a sufficient number of random exchanges of data in the network guarantee all nodes will eventually receive all messages. Due to their inherent flooding nature, epidemic routing algorithms result in high energy and bandwidth consumption. Vahdat et al proposed to set a bound on the flooding by assigning a hop count limit to each message when it is generated. When the hop count limit is one, the message can only be sent directly to the destination(s). Spyropoulos et al. [6] proposed a technique called spray-and-wait to control the amount of flooding. During the spray phase, L copies of the data message are initially spread over the network by the source node or other nodes to L distinct relays. If the destination was not found during the spray phase, each node holding a copy of the message will perform direct transmission during the wait phase. Binary spray-and-wait is another variant of the basic spray-and-wait protocol and produces better performance. In this approach, the source node sends half of the copies of the message to the new relay node, and keeps the other half. The source node and relay nodes repeat this procedure until there is only one copy left, at which point it switches to direct transmission. Su et al. [21] presented an experimental study to test the feasibility of using user mobility and consequent opportunistic pairwise contacts to form an OPMANET inside a college campus. Using commodity mobile devices, they instrumented two user studies for experimentally collecting trace data of user contacts. The approach is unique in that they did not have a predetermined model of user mobility. The results of the experiment are promising, showing that user mobility can potentially be used to form a network. Using this trace data, they simulated an idealized network using epidemic propagation, and observed that nodes exhibited signs of regularity and affinity of contact. The authors further observed that the success of message delivery from any source to destination(s) was not evenly distributed among the intermediate nodes, and they suggested that this fact should be used by source nodes for making better routing decisions.

6.3.2.2 Location-Based Approaches

Geocasting protocols [27–31] are a class of flooding-based protocols that send messages from a source to all hosts located in a specific geographical region. When a node inside the geocasting region receives the messages, it shares the messages with other group members inside the geocasting region by flooding the messages. Group membership changes whenever a mobile node moves in or out of the geocasting region. Leontiadis et al. [32] proposed a VANET-based routing protocol, which allows the publishers to produce events (traffic alerts/notifications) for a particular subscription area/point of interest described by a geographic grid. Multicasting is realized by restricted flooding inside the subscription area. To minimize the number of broadcasts in the subscription area, a small number of event/notification replicas are created, and vehicles carrying those replicas serve as mobile info stations. However, these protocols only consider a special case of multicast where all the subscribers are located inside a specific geographic region. Therefore, they are not suitable for more general cases where the subscribers are arbitrarily located anywhere in the network, as multicasting to the subscribers requires flooding the entire network. Various cluster-based protocols [33–35] have been proposed to alleviate flooding, where the network is partitioned into several disjoint and equally sized cell regions. A cluster manager handles all communications for its cluster, and is responsible for communications with managers of neighboring clusters. Cluster-based protocols thus alleviate flooding, but increase management overheads.

6.3.2.3 History/Estimation-Based Approaches

Burns et al. [36] proposed the meetings and visits (MV) routing protocol, which is a further step beyond epidemic routing. Messages are exchanged during pair-wise contacts as in epidemic routing. However, the MV protocol introduces a further complex method to select the messages to forward to a new contact. The choice depends on the probability of previously encountered nodes to successfully deliver messages to their eventual destinations. The delivery probability relies on recent-past observations of both the meetings between nodes and the visits of nodes to geographical locations. Lindgren et al. [37] proposed a similar approach, called probabilistic routing protocol using history of encounters and transitivity (PROPHET) that calculates a probabilistic metric for message forwarding. This metric is called delivery predictability and it indicates the probability of successfully delivering a message to the destinations from the local node. PROPHET operates in a similar way as the epidemic routing. When two nodes meet, they exchange summary vectors containing the delivery predictability vector. If two nodes meet very often, they have high delivery predictability to each other. On the other hand, if a pair of nodes does not meet each other in a while, they are intuitively not good forwarders of messages to each other. Hence, the delivery predictability values must age (i.e., be reduced) as time passes. The authors showed in their simulation results that the overhead of PROPHET is lower than that of epidemic routing. Balasubramanian et al. [38] proposed resource allocation protocol for intentional DTN (RAPID), in which they presented opportunistic routing as a resource allocation problem. The goal of RAPID is to minimize one of three routing metrics, e.g., average delay, missed deadlines, and maximum delay, using a utility function. This function assigns a utility value, $U_i$ to every packet $i$, based on the metric being optimized. To that end, $U_i$ is defined as the expected contribution of packet $i$ to this metric. RAPID  replicates those packets first which result in the highest increase in utility. For example, if the metric to optimize is average delay, the utility function is defined as $U_i = - D(i)$, i.e., the negative of the average delay. Hence, the protocol replicates the packet that results in the greatest decrease in delay. Due to the inherent flooding nature, RAPID attempts to replicate all packets if network resources are available.

6.3.2.4 Network Coding-Based Approaches

Flooding-based algorithms also include network coding-based approaches [39] that take an original approach to limit message flooding. Just to give a classical example, assume A, B, and C are the only three nodes of a small network. Let us assume that node A generates the data message “$a$” and node C generates the data message “$c$.” In order to distribute their data to all other nodes, nodes A and C send their messages to node B. Instead of sending two separate data messages for “$a$” and “$c$,” respectively, node B broadcasts a single message containing “$a$” XOR “$c$.” Once “$a$” XOR “$c$” is received, both nodes A and C can finally infer the data messages sent by the other source (i.e., node A can infer “$c$” and node C can infer “$a$”). Network coding-based routing approaches outperform basic flooding, as they are able to make data delivery with a fewer number of messages injected into the network.

Fig. 6.6

Example of network coding-based forwarding

6.3.3 Hybrid Approaches

As stated above, flooding-based approaches work well in highly mobile networks with many communication opportunities between nodes arising due to node mobility. However, these approaches generate high overhead, network congestion and may suffer from high contention. Several hybrid approaches have been proposed in recent literature, which combine features from forwarding-based approaches with flooding-based approaches to achieve low data dissemination latency while limiting the network overheads. To that end, a forwarding-based approach is used to get the data message as close to the destinations as possible. Once the data message gets close to the destinations, flooding-based approaches are used to disseminate the data in the surrounding. Tchakountio et al. [40] proposed the Spray routing protocol, which is an integrated location tracking and forwarding scheme. The idea behind spray routing is that even though a highly mobile node may not be in the location last reported by the location tracking mechanism, it is likely to be in one of the surrounding locations. Consequently, by “spraying” the data message to the vicinity of the destination’s last-known location, the algorithm attempts to deliver packets to the destination even if it moves to a nearby location during the location tracking convergence time. The data packet is first unicast along a ray to a node in the vicinity of the destination’s last known location before being multicast in that vicinity area. The magnitude of the spraying depends on the mobility; the higher the mobility, the larger the vicinity. Nain et al. [41] proposed a relay-based approach, called mobile relay protocol (MRP) that is used in conjunction with epidemic style broadcasting. To that end, MRP integrates message routing and storage in the network. The basic idea is that if a route to a destination is not available, a node performs a controlled local broadcast to its one-hop neighbors. All neighbors receiving this broadcast store the data message and enter the relaying mode. In the relaying mode, the MRP protocol first checks its routing table to see if an end-to-end route of less than $d$ hops exists. If so, the data message is forwarded to the destination(s). If no valid route is found, the MRP protocol enters the storage mode, which involves the following steps: if the message is already stored in the current node’s buffer, then the older version of the message is discarded and the new version is stored given the buffer is not full. In case the buffer is full, the MRP protocol removes the least recent message from the buffer and relays to a single random neighbor. In a network with sufficient mobility, it is quite likely that one of the relay nodes to which the packet has been relayed will encounter a node that has a valid route to the destination, thereby increasing the likelihood that the message will be successfully delivered. Mitra et al. [42] proposed a hybrid overlay multicast protocol for OPMANETs, called Courier that creates potential overlay multicast trees using the location and velocity of the source node and destinations. The construction of the overlay multicast tree is guided by a mobility prediction model. Each node is represented by a circular region called node forwarding zone (NFZ); the center of the NFZ is the last-known location of the node and its radius is equal to the last-known velocity of the node times the time duration since last location update. The NFZ, by definition, captures all possible locations in all directions to which the mobile destination could have moved to at its last-known velocity. During multicast, once the data message enters the NFZ of a destination, it is broadcasted by all nodes inside that circular region. Thus, Courier ensures that the data message is delivered to the mobile destination even if it is no longer at its last-known location. Courier reduces the overlay multicast group management cost by using a bandwidth efficient location update scheme. Between two overlay nodes in the multicast tree, the data message is forwarded using a location-based forwarding protocol that exploits transient communication opportunities between mobile nodes.

Fig. 6.7

Example of mobility prediction-based hybrid multicast in Courier [42]

6.3.4 Social Behavior-Based Approaches

Exploiting social behavior for increasing routing efficiency in OPMANETs has recently received considerable attention in research community. To that end, social behavior-based approaches use social-based metrics derived from contacts between devices to make opportunistic forwarding decisions with low overhead. Many approaches implicitly assess the strength of “social” ties between nodes, using metrics such as time of last encounters between nodes [43] or frequency of contacts as a hint of similarity between mobility patterns [44]. However, these simple metrics may only capture one facet of the underlying mobility patterns, which can in turn hinder good contact predictions. Complex network analysis is a further generic and powerful tool to formulate and solve the problem of future contact prediction. Past observed contacts between nodes are aggregated into a social graph, with graph edges representing past meetings between the vertices. Two nodes who often meet either have a strong social tie (friends), or they are frequently co-located without actually knowing each other (familiar strangers); thus, existence of an edge intends to have predictive capacity for future contacts. Protocols using such explicit knowledge of social relationships have been proposed to improve efficiency over socially agnostic protocols in OPMANETs. Hui et al. [45] proposed a routing protocol, called Bubble Rap that uses the patterns of contacts between users/nodes to classify the users into various distinct social communities, which in turn are used as context for routing. Bubble Rap gives preference to nodes belonging to the same community of the destinations as good forwarding candidates. If such nodes are not found, Bubble Rap forward the message to the nodes that have more chances of contact with the community of the destinations. Daly et al. [46] proposed SimBet that assesses “similarity” (i.e., the number of neighbors two nodes have in common) to detect nodes that are part of the same community, and “betweenness centrality” (the fraction of shortest paths between each possible pair of nodes going through this node) to identify bridging nodes, that could carry a message from one community to another. The decision to forward a message depends on the similarity and centrality values of the newly encountered node, relative to the current one. If the former node has a higher similarity with the destination, the message is forwarded to it; otherwise, the message stays with the most central node. The goal is to first use increasingly central nodes to carry the message between communities, and then use similarity to “home in” to the destination’s community. Mtibaa et al. [47] proposed PeopleRank in which nodes are ranked using a tunable weighted social behavior. Similar to the PageRank idea, PeopleRank gives higher weight to nodes if they are socially connected to other high profile nodes of the network. The authors developed centralized and distributed variants for computing the PeopleRank metric and used real mobility traces of nodes and their social interactions for evaluation. PeopleRank delivers messages with near optimal success rate close to epidemic routing, while reducing the number of message retransmissions by 50 % compared to epidemic routing. These approaches identify “strong social ties” among mobile devices, inferred either from contact behavior or declared friendship. Zyba et al. [48] explored the role and potential of non-social, vagabond devices for communication and data dissemination. They used experimental traces to study fundamental properties of human interaction; the traces were broken down in multiple areas and mobile users in each area were classified according to their social behavior. Socials are devices that show up frequently or periodically, while Vagabonds represented the rest of the population. Their study of the traces revealed that in some situations (specifically, beyond a "tipping point"), population size had a greater impact on the effectiveness of data dissemination than the social status of devices. To that end, an analytic model was proposed that formally characterizes the relationship between population size and the social behavior of users, and identifies a simple formula for determining when data dissemination through Vagabonds outperforms dissemination through Socials.

Table 6.2 Summary of the OPMANET routing protocols

Summary: Section  6.3 classified routing protocols in OPMANETs into four different categories: forwarding-based, flooding-based, hybrid, and social behavior-based. The forwarding-based approaches were further divided in two categories: direct transmission-based and context-based. Table  6.2 summarizes the various categories of routing protocols, using the analytical framework proposed in Sect.  6.2.

6.4 Real-Life Applications of Opportunistic Networks

In OPMANETs a network is typically separated into several network partitions called regions. Traditional applications are not suitable for such environments because they normally assume an end-to-end connection from the source to the destination(s). The applications that are suitable for OPMANETs are typically asynchronous in nature and tolerant of long delay and high error rates. This section discusses in detail of a few applications of OPMANETs and specifically provides insights on the routing approaches used by these applications.

Fig. 6.8

Example of social community-based forwarding in Bubble Rap [45]

6.4.1 Urban Environments

The Haggle project ² was a four-year project, started in January 2006 and funded by the European Commission³ and was targeted at providing solutions for communications in OPNETs. Haggle performed an extensive study of the properties of pocket switched networks (PSNs), i.e., OPNETs that can exploit any contact opportunities between devices (e.g., cell phones and PDAs that users carry in their pockets) to forward messages. The project put special emphasis on measuring and modeling pair-wise contacts between devices. To that end, pair-wise contacts between devices were characterized by the means of two parameters: contact durations and inter-contact times. The duration of a contact is the total time that two tagged mobile devices are within reach of each other. On the other hand, the inter-contact time is defined as the time in between two contact opportunities between the same two tagged devices. While the contact duration directly influences the capacity of OPNETs because it limits, the amount of data that can be transferred between nodes, the inter-contact time influences the feasibility of OPNETs and the delay associated with them. To characterize contact durations and inter-contact times occurring in real-world environments, various sets of traces, e.g., logs collected by the APs of university campuses, by devices carried by students and researchers in their university and laboratories, and by the participants to some international conferences, were collected and analyzed. The analysis of all the traces had led to the conclusion that both inter-contact times and contact durations are characterized by heavy-tailed distribution functions that approximately follow power laws. The Haggle architecture enables a social and context-aware content-sharing service that exploits a context definition designed for OPNETs. The service uses the users’ social behavior patterns to identify content that might be relevant to the communities a user interacts with. More specifically, these interaction patterns allow the system to improve forwarding decisions by probabilistically predicting future user contacts.

Heinemann et al. [1] proposed adPASS, an OPNET framework that disseminates advertisements among interested users in an urban environment, using a word-of-mouth recommendation style approach. For example, assume Alice carries a mobile device with her. A personal profile, stored on her device, stores her interests and knowledge. The device is able to match her profile with other nearby devices by communicating wirelessly and without user interaction. On the other hand, a shop has put a fixed device next to the shop window. This device announces digital advertisements from the shop to passersby. As Alice passes the shop window, her device learns about the special offer for digital cameras. Alice physically carries the advertisement with her and passes it further to other users she encounters. All users interested in the ad (including herself and her colleague Bob) might take the chance and visit the shop in order to buy the advertised product. Data dissemination relies solely on one-hop communications and uses a node’s profile to carry out its task. When two nodes detect a match in their node profiles, they exchange data. The physical movement of nodes is utilized to distribute the data. adPASS also makes use of Information Sprinklers for implementing time-shifted information pass, i.e., users who are at the same place but at a different time are able to share information with one another. As an example, consider a user Alice who goes to a local coffee bar at 10 every morning. User Bob visits the same place each afternoon. Alice and Bob will never meet and thus come into communications range while visiting that coffee bar. In this situation, an Information Sprinkler installed in the bar can collect all information of all users visiting the bar. This allows Alice to leave her information at the Sprinkler in the morning and Bob to learn about this information from the Sprinkler in the afternoon.

6.4.2 Monitoring

Wildlife monitoring is another possible domain of applications of OPMANETs. It focuses on tracking wild species to understand their behavior, interaction, and mutual influence on one another, and as well as their reaction to the ecosystem changes caused by human activities. Researchers use OPMANETs as a reliable, cost-effective, and non-intrusive means to monitor large population of animals roaming in vast regions. Systems for wildlife monitoring generally include special tags with sensing capacity to be carried by the animals under study, and one or more base stations to collect the data from the tags and send them to the processing center. Base stations can be fixed or mobile; however, in both cases data collection from all the deployed tags is quite challenging. As a consequence, routing protocols exploit pair-wise contacts between the animals to let them exchange the data already collected. Eventually, each animal carries the data collected on its own and the data collected by other animals it has encountered. ZebraNet [49] is an interdisciplinary ongoing project at Princeton University and its deployment scenario is the vast savanna area of central Kenya. The animals to be tracked are zebras wearing special collars. The base station consists of a mobile vehicle for the researchers, which periodically moves around in the savanna and collects data from the zebras encountered. Two alternative protocols have been considered for data collection in ZebraNet. The first one is simple flooding-based; each collar sends all its data to each encountered neighbor until the data eventually reaches the base station. The second one, named history-based protocol, proposes that each node selects only one of its neighbors as relay for its data. The selected node is the one with the highest probability to eventually encounter the base station. Each node is thus assigned a hierarchy level (initially zero) that increases each time it encounters the base station, and conversely decreases after not having seen the base station for a certain amount of time. When sending data to a relay node, the neighbor to be selected is the one with the highest hierarchy level. Simulation results show that both forwarding protocols outperform the direct protocol, in which each collar has to directly communicate with the base station to upload data. Moreover, the history-based protocol outperforms flooding in terms of bandwidth and energy consumption. Small et al. [50] proposed the shared wireless infostation model (SWIM) that monitors whales using special tags. Data is replicated and diffused at each pair-wise contact between whales (similar to the flooding protocol of ZebraNet) and finally arrives to special SWIM stations that can be fixed (on buoys) or mobile (on seabirds). Hence, both whale-to-whale and whale-to-base station communications are allowed. From the SWIM stations, data messages are eventually forwarded onshore for final processing and utilization.

Pompili et al. [51] proposed a geographic routing solution for delay-insensitive underwater sensor network applications. Such networks consist of sensors and vehicles deployed to perform collaborative monitoring tasks over a given underwater region for a variety of applications, e.g., oceanographic data collection, pollution monitoring, offshore exploration, disaster prevention, assisted navigation, tactical surveillance, and mine reconnaissance. The proposed solution aims to efficiently exploit the underwater acoustic channel and minimize the energy consumption. The protocol increases the efficiency of the channel by transmitting a train of short packets back-to-back and limiting the packet error rate by keeping the transmitted packets short. Each node is allowed to select its best next-hop node, the transmission power, and the forward error correction code rate for each packet. Furthermore, it tries to exploit those links that guarantee a low packet error rate, in order to maximize the probability that the packet is correctly decoded at the receiver. For these reasons, the energy efficiency of the links is weighted with the number of retransmissions required to achieve link reliability, with the objective of saving energy.

6.4.3 Connecting Developing Areas

OPMANETs can be used to provide Internet connectivity to rural and developing areas where they are typically the only affordable way to help bridge the digital divide. One such example is the DakNet Project [52] which is aimed at realizing a very low-cost asynchronous ICT infrastructure so as to provide connectivity to rural villages in India. To that end, kiosks are built up in villages and equipped with digital storage and short-range wireless communications. Periodically, mobile access points (MAPs) mounted on buses, motorcycles, or even bicycles pass by the village kiosks and exchange data with them wirelessly. MAPs can download data stored at the kiosks, and upload them to the Internet when passing by an access point (AP) in a nearby town. Similarly, MAPs may download, from the Internet, the requested data and bring it to villages. DakNet has the potential to support Internet/Intranet messaging (e.g., email, audio/video messaging, and mobile e-commerce), data distribution (e.g., public health announcements, community bulletin boards, news, and music), and collection (e.g., environmental sensing, voting, health records, and census). A similar model is used to implement a hybrid real-time and store-and-forward Wi-Fi mesh network in Kigali, Rwanda.⁴ As part of a hybrid village area network (VAN) implemented to provide real-time Internet access at various sites throughout the capital of Kigali, a unique store-and-forward connectivity is demonstrated in the countryside. Throughout all the implementation, major emphasis is put in the formation and training of a local technical team in order to ensure the proper transfer of technology and its associated knowledge. Eventually, the local team is capable of operating, troubleshooting, and expanding the network at will. The Saami network connectivity (SNC) project [53] aims to provide network connectivity to the nomadic Saami population of the reindeer herders. Saami herders live in the northeast part of Sweden, Norway, and Finland and move from their villages through the year following the migration of reindeers. Providing network connectivity to the Saami population is a means to protect and defend their habitats, culture, and traditions while also supporting their integration into the modern society of their countries. The network connectivity enables the Saami to achieve economic growth through distance work and Internet-based business. Network-based services can also allow Saami children to receive their education without the need to leave their parents to attend boarding schools. Network connectivity can also give Saami more visibility, and let them have more influence in the political and economic affairs of their country. In its initial stage, the SNC project has only focused on providing email, file transfer, and cached web services to the Saami people. Reindeer herd telemetry is also going to be provided to support the herding activity itself.

6.5 Discussion

Based on the existing researches and the unique characteristics of OPMANETs, there are still a few research issues that are far from being adequately addressed. To that end, this chapter found a few gaps in many of the current OPMANET routing approaches that will pose significant challenges in future as more applications targeted at OPMANETs come into existence. The key observations made in this chapter are listed below.

6.5.1 Advanced Personal Mobile Devices Should be Used for Increasing Network Capacity

The rapid proliferation of sophisticated mobile devices (e.g., smartphones and tablets) equipped with powerful processors, abundant memory, and an ever-increasing number of sensors (e.g., to capture user location, audio/video, ambient light, etc.) presents the potential of building large-scale dynamic OPMANET applications. These devices are suited for large-scale OPMANET applications because they are always mobile, which makes it very likely that there will be devices at the right place at the right time to successfully accomplish the required forwarding task, thereby increasing the network capacity.

6.5.2 Use of Heterogeneous Devices and Radio Technologies Should be Encouraged for Increasing the Number of Communication Opportunities in the Network

One major limitation in all approaches discussed in this chapter is that developers are currently tied to the specifics of one particular wireless communications technology. However, the number of devices with diverse radio communications technologies is increasing (e.g., smartphones and tablets are equipped with multiple radio technologies such as Wi-Fi, Bluetooth, and RFID) and one should exploit such heterogeneous communication opportunities for increased data delivery success in OPMANETs. A solution targeted at providing this type of interoperability should focus on developing a technology-independent, high-level software application programming interface (API) for OPMANET applications. Given that many of these heterogeneous devices use heterogeneous operating systems with some of them being proprietary, the obvious level for implementing such API is at the middleware level. Such an API will not only increase the usage lifetime of the applications but also encourage the creation of new applications by helping to amortize development efforts.

6.5.3 Privacy and Security

OPMANET applications communicate with their surroundings without active user interaction, and this raises many privacy issues with increasing use of personal mobile devices in urban environments. These devices store personal data and interests and thus, while participating in data forwarding, they become vulnerable to the danger of tracking and monitoring user behavior for constructing user profiles and compromising user anonymity in the network. Current applications that address the issue of protecting user privacy in OPMANETs either focus on protecting location privacy [54, 55] or are heavily tailored to the respective applications [56, 57]. Future research efforts should focus on developing generic privacy and user identity protection techniques targeted at OPMANET applications. In addition, new security and data encryption mechanisms should be developed for devices with limited resources working in a dynamic and distributed environment, as techniques that rely on access to a centralized service cannot be used, or the assumption that all the intermediate nodes are trustworthy is no longer valid.

6.5.4 Applications Should be able to Specify Their Quality of Service Requirements

In OPMANETs, both source and destinations frequently switch states between connection and disconnection to and from the network; as a result, it is very challenging to ensure reliable data delivery in such environments. To that end, the loosely coupled and asynchronous nature of OPMANETs introduces a non-deterministic behavior in the system, thereby making it very hard to provide QoS guarantees. Future research approaches should aim at enabling the applications to specify their own QoS requirements to the routing protocol, which in turn should include approaches for meeting those requirements. For example, applications can specify that they require their multicast data to be persistent, thus ensuring that the messages will not be lost in the event of a source node failure. Persistent data delivery could be implemented using policies such as durability of subscription and multicast data storage and retransmission. To that end, routing protocols could require the source node to log messages in a stable storage. On the other hand, durability of subscription will allow destinations to receive the messages sent while they were disconnected from the network. This will require implementing reliable queues on part of the source nodes—when a destination that was disconnected rejoins the network and the durability of its subscription is still valid, the source node resends the stored messages to the client. In order to minimize duplicated messages and reduce the associated communications overhead, routing protocols could attach an expiration time to each multicast data message.

6.5.5 Node Location and Velocity Should be Used by Routing Approaches

Although many of the current OPMANET routing approaches already use node location, only a handful of them use both location and velocity for making mobility prediction. To that end, the forwarding approaches should leverage node location and velocity with simple and accurate link availability estimation algorithms for making intelligent forwarding decisions. For example, if a contact is not going to be available until the data message transfer is finished, the routing protocol should store the message in buffer and wait for future communication opportunities, thereby saving on bandwidth and energy resources.

6.5.6 Social Behavior-Driven Traces Should be Used for Deriving Realistic Mobility Models

Since OPMANETs exploit users’ mobility to bridge disconnections and partitions in the network, it is of high importance to identify realistic mobility models, both to drive the protocols’ design, and to provide sensible performance results. Mobility modeling for OPMANETs is emerging as a hot topic since last few years. To that end, popular models used in MANET research (e.g., the random waypoint model) generate unrealistic user behavior. To address this problem, mobility models are being reconsidered or redesigned based on real users’ mobility traces. A few research projects have found that mobility traces can be strongly associated with sociological-inspired concepts, e.g., periodic association patterns follow sociological orbits defined by the social behavior and relationship of users. Such social-aware mobility models have been shown to closely reproduce statistical features of real movement traces, and are thus very good candidates for designing and evaluating OPMANET routing approaches. Future research efforts should focus on analyzing mobility traces from a variety of diverse real-life scenarios for developing realistic social-aware mobility models.

6.5.7 Hybrid Routing Protocols Should be Further Investigated for Increasing Data Dissemination Efficiency in OPMANETs

Hybrid routing protocols combine features from forwarding-based approaches with flooding-based approaches to achieve low data dissemination latency while limiting the network overheads. Although Sect.  6.3.3 discusses a few such protocols, we feel that this class of routing approaches has not been adequately investigated. Future research efforts should focus on developing hybrid approaches that can dynamically mix-and-match approaches from the set of forwarding-based approaches with the ones from the set of flooding-based approaches, as the multicast group size and resources capabilities of the nodes vary in the network. For example, hybrid approaches typically flood the data message once it gets closer to the destinations. The size of the flooding region varies depending on a number of factors (e.g., node mobility, the time duration since last location update from destinations, etc.); if the flooding region becomes too big, then the hybrid routing protocol should dynamically switch from the basic flooding scheme to a history-based flooding scheme that will predict the region where the mobile destination is likely to be found, thereby minimizing the flooding overhead.

6.5.8 Communication Opportunities can be Artificially Created

This chapter focused on the routing protocols that exploit only those communication opportunities that arise spontaneously when nodes come into contact due to node mobility, changes in transmission power, etc. On the other hand, there is another class of routing protocols targeted at sensor networks (which are beyond the scope of this chapter); this class of routing approaches opportunistically employs additional mobile nodes to offer a message relaying service as message ferries [58, 59]. These ferry nodes move around in the network following a predefined trajectory and collect messages from source nodes. To that end, a source node wishing to deliver data messages sends a request message to the ferry with its current position and then the ferry changes its trajectory to meet up with source node. These ferry-based routing protocols artificially create communication opportunities in a sensor network, and they can be further investigated to draw insights to be used in other application scenarios in OPMANETs, e.g., in an urban scenario, buses that follow a predefined trajectory can be used as message ferries.

6.5.9 Multi-Tier Routing Protocols can Increase Network Connectivity at Scale

This chapter discussed routing approaches that focus on a single-tier OPMANET. However, as suggested by Pelusi et al. [3], future routing approaches should investigate the feasibility of building multi-tier OPNETs, in which each tier of the network is an OPNET in itself with its own routing protocol that provides communications among nodes in that tier. Nodes would rely on the upper tiers to reach nodes that are too far away, thus enabling connection among various groups of disconnected lower tier nodes in a sparse/partitioned network. The data mule-based routing approach [60], originally targeted at building multi-tier sensor networks, can provide meaningful insights about building multi-tier OPMANETs for increased connectivity in large-scale systems.

6.5.10 User Participation Should be Rewarded to Increase Message Forwarding

Most of the current OPMANET applications typically share a common goal they want to accomplish (e.g., wildlife/environmental monitoring, providing Internet connectivity to developing areas, etc.). With the increasing use of personal mobile devices (e.g., smartphones, tablets) for implementing OPMANET applications, the assumption of an altruistic resource sharing environment is no longer feasible. These personal user devices serve a variety of strictly personal purposes, e.g., surfing the web, playing games, running other applications, storing calendar, schedules, and contact lists, etc. Since battery, storage, and processing power are limited and precious resources on such personal user devices, OPMANET applications should provide means to reward participating users that help in forwarding/disseminating the data messages. A few recent research efforts [1, 61, 62] have proposed incentive-based solutions for increasing user participations in OPMANETs; these solutions are similar to the incentive-based schemes used by peer-to-peer file sharing systems. Future research efforts should investigate other approaches for rewarding user participations in OPMANETs.

6.6 Conclusion

This chapter provides an overview of the emerging research area of routing in OPMANETs. While this chapter has not covered all aspects of research or all projects in this area, it attempts to provide insights in this evolving area by characterizing a few key research projects using a simple analytical framework—this framework characterizes the routing approaches in terms of three aspects, i.e., data dissemination, resource management, and applications. The framework reveals that the flooding-based approaches work best in highly mobile networks in which many communication opportunities between nodes arise due to node mobility. These approaches are simple to implement and have the highest number of real-life applications; however, they generate high networking overhead, network congestion and contention, etc. On the other hand, hybrid approaches achieve low data dissemination latency while limiting the networking overheads but they are only suitable for applications that require multicast/group-based communication semantics. With the recent growth in use of smartphones and tablets, the social behavior-based approaches are getting a lot of attention. These approaches use real-life mobility traces to make forwarding decisions. As a consequence, they result in very high contact prediction accuracy and low communications overhead. However, they incur high computational and storage overheads because they need to maintain state information of the encountered nodes in order to assess their social behavior.

This chapter also outlines a few gaps in the recent research efforts and provides insights on how to address those gaps in future work. Lack of interoperability is one of the main shortfalls in the existing OPMANET routing approaches. The accelerating global popularity of advanced mobile devices boasting powerful processors, abundant memory, and complex sensor capabilities has opened the gateway to building and deploying large-scale OPMANET applications anytime, anywhere. In order to be able to completely exploit the benefits offered by these widely available, sophisticated mobile devices which often come with heterogeneous platforms and radio communications technologies, we need to provide interoperability between the routing approaches designed for specific platforms/wireless technologies. Future research should investigate the feasibility of developing high-level software API for providing interoperability to OPMANET applications—such an API has the capability of not only increasing the usage lifetime of the applications but also encourage the creation of new applications by helping to amortize development efforts. Another important aspect of deploying collaborative OPMANET applications on personally owned mobile devices is that we need to provide means to reward the participating users—these users share the resources of their personal devices for a common goal that the OPMANET applications want to accomplish, e.g., wildlife/environmental monitoring, providing Internet connectivity to developing areas, etc. As a final point, Lilien et al. [63] argues that OPMANETs are one possible approaches of ultimately moving toward the goal of pervasive computing, and hence it will be increasingly important for OPMANET routing solutions to ensure privacy protection on the consumer mobile devices. Future solutions should investigate different approaches for privacy protection, e.g., encryption of private data and resources, use of adaptive sharing policies, etc.

The future research efforts in routing in OPMANETs will require drawing on expertise from a number of disciplines including (but not limited to) wireless sensor networks, social sciences, network security, algorithm design and evaluation, distributed file systems, e-commerce, etc. Our hope is that this book chapter will stimulate discussion and aid research in this area.