# Dynamic Rendezvous Based Routing Algorithm on Sparse Opportunistic Network Environment

Authors: Jiradett Kerdsri; Komwut Wipusitwarakun
Journal: International Journal of Distributed Sensor Networks
 (2015)

---

## Abstract

An opportunistic network is a network where the nodes need to communicate with each other even if existing routes between them may not permanently exist due to the nodes’ random movement. Most routing algorithms employ a paradigm by which a node can keep the receiving messages, carrying the messages with them when moving and then forwarding the messages to the opportunistic meeting nodes when possible. This routing model works well in the networks with high-to-moderate node density in which the opportunity that the moving nodes can meet with each other is rather high. On the other hand, the delivery ratio becomes remarkably low in the sparse network environment especially when there is a strict constraint on message delivery deadline. In this paper, we introduce the novel concept of rendezvous place where the passing nodes can announce, deposit, or pick up their own messages without having to meet the other nodes carrying the desired message. The rendezvous place can be detected automatically and its area’s shape is dynamically changed according to the interaction among nodes. The results from extensive simulations show that our routing algorithm can achieve higher delivery ratio and utilize lower energy consumption than traditional opportunistic routing algorithms especially in sparse network environment.


---

## Body

## 1. Introduction

An opportunistic network (OppNet) is an extreme type of delay tolerant networks (DTNs) where the source and destination nodes might never be fully connected at the same time. Thus there is no guarantee of the existence of a complete path between two nodes wishing to communicate [1]. This intermittent connections may result from several factors such as high node mobility, low node density, environmental interference and obstruction, short radio range, and malicious attacks [2]. The node movement in OppNet is extremely random in some networking environment; thus the probability of message delivery from source to destination is difficult to ensure. Examples of such networks are sparse mobile ad hoc networks [3], military tactical networks [4, 5], or sensor networks, such as ZebraNet [6], SWIM [7] in which nodes move throughout an environment, working to gather and process information about their surroundings. Commonly, the key differentiating factors among these scenarios are the levels of predictability and control over the contacts between the message carriers [8]. A key concept behind opportunistic routing (OR) is overhearing and cooperation among relaying nodes to overcome the drawback of unreliable wireless transmission [9]. Since the mobile nodes are not always connected to each other, the forwarding algorithms in such networks commonly follow astore-carry-forward (SCF) paradigm. This SCF employs storage space and node mobility to overcome the intermittent connectivity [10]. The messages sent from the source node are carried by intermediate nodes to other geographical areas and transferred to adjacent nodes until the destination node receives this message. Since this fundamental SCF routing model realistically requires a certain sufficient occasion ofdirect encounter among moving nodes to exchange messages, its routing performance will highly degrade in the low-node-density sparse network [11]. Although there are several existing OppNet routing solutions [5, 12–16] proposed in the literature, very few proposals address the problem in this sparse network environment especially when the OppNet nodes are energy-constrained [17, 18] and the direction of their movement cannot be controlled.In this paper, we proposed a novel dynamic rendezvous based routing algorithm (DRRA) to increase message exchanging opportunity even in the sparse network environment. We utilize the fact that there should be some node-gathering (rendezvous) places forming somewhere at some specific time in the real network. These rendezvous places may be either predictable such as mobile command post in military tactical network applications or nonpredictable such as disaster and emergency networks. An energy-constrained node should maximize its resource usage to communicate with the others only when entering into the rendezvous area. In the proposed scheme, the rendezvous place is dynamically marked by the help of a special controllable rendezvous node and the proposed rumor protocol to let nodes in the rendezvous area exchange messages more efficiently without having to directly meet with the other nodes.The rest of the paper is organized as follows. In Section2, we discuss the overview of OppNet routing model applications and existing works. The detail of rendezvous based routing model is elaborated in Section 3. In Section 4, we present the result of our simulation and show the performance of our scheme under different conditions. We conclude the paper and point out some future research directions in Section 5.


## 2. The OppNet Routing Model Applications and Existing Works

### 2.1. OppNet Routing Model and Its Applications

In OppNet, the messages are delivered using store-carry-forward routing by which the nodes can exchange data whenever they come close. If there is no direct connection from source to destination, data holding nodes will discover their nearest neighbor nodes to forward messages toward the destination node as shown in Figure1. There are several existing works in the literature [5, 16, 19–23] with the aim of 100% delivery ratio which is quite difficult to achieve especially in sparse networks with constraints in energy consumption and message delivery deadline. In addition, it has been reported that most recent well-known opportunistic routing [23–29] is unable to always achieve 100% delivery ratio [30].Figure 1
Store-carry-forward routing model.An OppNet routing is designed to address an extreme network environment where the source and destination node might never be fully connected at the same time. The OppNet routing can be used in several recent applications such as Social Mobile Network, Disaster Recovery Networks, Military Tactical Network, and Movable Sensor Networks as described in the recent books [31–33].(i)
Social Mobile Network [34–37]: the OppNet nodes are represented by mobile application utilizing available nearby communication channels to relay the messages toward the destination.(ii)
Disaster Recovery Networks [38–41]: when a stable infrastructure is destroyed by a natural disaster, the mobile agents are utilized to exchange the messages between victims, first responders, or rescue teams without long range wireless transmission.(iii)
Military Tactical Network [42–44]: the OppNet nodes are represented by soldiers equipped with communication devices to communicate with each other and mobile command post to facilitate the data exchange in the operational area.(iv)
Movable Sensor Networks [45–47]: the data collection is done utilizing stationary sensor node and movable sensor node.The key characteristics in the OppNet environment are(i)
uncontrollable nodes,(ii)
difficulty of predicting the movement path,(iii)
limited short length communication channel.


### 2.2. Existing Works

Vahdat and Becker [16] proposed the epidemic routing using the uncontrolled flooding algorithm in which the replication of source data is not restricted with any limits in order to route the message from source to destination in the intermittently connected network. However, this type of routing incurs a significant demand on both bandwidth and buffer capacity. To address the excess traffic overhead, Harras et al. [19] proposed a controlled flooding scheme which can limit the flooding by three parameters: willingness probability, time-to-live, and kill time. Nevertheless, flooding based routing performance degradation has been reported in a very sparse network [20].Lindgren et al. [21] proposed a prediction based routing called PROPHET (Probabilistic Routing Protocol using History of Encounters and Transitivity) by estimating the delivery predictability to indicate the probability of success in delivering a message to the destination from the local node. In this prediction based routing category, Burns et al. [22] also proposed a protocol utilizing the motion vector of mobile nodes to predict the future location of mobile nodes by using the knowledge of relative velocities of a node and its neighbor nodes to predict the closest distance between two nodes. Although the prediction based approach can reduce traffic overhead in the network, it fails to improve the performance in an extremely low-node-density scenario and, in some cases, results in the delivery ratio reduction.To refine the prediction based routing, Boldrini et al. [23] proposed the history based routing (HiBOp) which exploits current context information for data forwarding decisions. Even though this context based routing approach can reduce the resource consumption in terms of network traffic and storage, its delay performance is significantly inferior to that of the epidemic algorithm. Kerdsri and Wipusitwarkun [5] proposed the DORSI protocol with the concept of content based routing which aims to classify the data in the network by messages’ significance level in order to guarantee the delivery of more important data.The concept of passive relay node can be found on several recent research proposals such as throwbox [48–51], FINs (fixed infrastructure nodes) [12], fixed point [52], or passive relay points [53]. These relay nodes are stationary wireless devices injected into the infrastructure of network in order to create additional contact opportunities and increase the connectivity between mobile nodes.Some proposals such as WSNs [54–57], data mules [58, 59], or message ferries [60–63] use a similar approach of path planning to program mobile robots to collect information from sensor nodes. However, it may be effective only in the case that sensor nodes are stationary.Nevertheless, the decreasing in network performance under sparse environment is not mentioned in this proposed protocol. Overall, the performance of most existing algorithms is degrading in very sparse node density, and the energy consumption is not taken into consideration which is a crucial factor in mobile devices.


## 2.1. OppNet Routing Model and Its Applications

In OppNet, the messages are delivered using store-carry-forward routing by which the nodes can exchange data whenever they come close. If there is no direct connection from source to destination, data holding nodes will discover their nearest neighbor nodes to forward messages toward the destination node as shown in Figure1. There are several existing works in the literature [5, 16, 19–23] with the aim of 100% delivery ratio which is quite difficult to achieve especially in sparse networks with constraints in energy consumption and message delivery deadline. In addition, it has been reported that most recent well-known opportunistic routing [23–29] is unable to always achieve 100% delivery ratio [30].Figure 1
Store-carry-forward routing model.An OppNet routing is designed to address an extreme network environment where the source and destination node might never be fully connected at the same time. The OppNet routing can be used in several recent applications such as Social Mobile Network, Disaster Recovery Networks, Military Tactical Network, and Movable Sensor Networks as described in the recent books [31–33].(i)
Social Mobile Network [34–37]: the OppNet nodes are represented by mobile application utilizing available nearby communication channels to relay the messages toward the destination.(ii)
Disaster Recovery Networks [38–41]: when a stable infrastructure is destroyed by a natural disaster, the mobile agents are utilized to exchange the messages between victims, first responders, or rescue teams without long range wireless transmission.(iii)
Military Tactical Network [42–44]: the OppNet nodes are represented by soldiers equipped with communication devices to communicate with each other and mobile command post to facilitate the data exchange in the operational area.(iv)
Movable Sensor Networks [45–47]: the data collection is done utilizing stationary sensor node and movable sensor node.The key characteristics in the OppNet environment are(i)
uncontrollable nodes,(ii)
difficulty of predicting the movement path,(iii)
limited short length communication channel.


## 2.2. Existing Works

Vahdat and Becker [16] proposed the epidemic routing using the uncontrolled flooding algorithm in which the replication of source data is not restricted with any limits in order to route the message from source to destination in the intermittently connected network. However, this type of routing incurs a significant demand on both bandwidth and buffer capacity. To address the excess traffic overhead, Harras et al. [19] proposed a controlled flooding scheme which can limit the flooding by three parameters: willingness probability, time-to-live, and kill time. Nevertheless, flooding based routing performance degradation has been reported in a very sparse network [20].Lindgren et al. [21] proposed a prediction based routing called PROPHET (Probabilistic Routing Protocol using History of Encounters and Transitivity) by estimating the delivery predictability to indicate the probability of success in delivering a message to the destination from the local node. In this prediction based routing category, Burns et al. [22] also proposed a protocol utilizing the motion vector of mobile nodes to predict the future location of mobile nodes by using the knowledge of relative velocities of a node and its neighbor nodes to predict the closest distance between two nodes. Although the prediction based approach can reduce traffic overhead in the network, it fails to improve the performance in an extremely low-node-density scenario and, in some cases, results in the delivery ratio reduction.To refine the prediction based routing, Boldrini et al. [23] proposed the history based routing (HiBOp) which exploits current context information for data forwarding decisions. Even though this context based routing approach can reduce the resource consumption in terms of network traffic and storage, its delay performance is significantly inferior to that of the epidemic algorithm. Kerdsri and Wipusitwarkun [5] proposed the DORSI protocol with the concept of content based routing which aims to classify the data in the network by messages’ significance level in order to guarantee the delivery of more important data.The concept of passive relay node can be found on several recent research proposals such as throwbox [48–51], FINs (fixed infrastructure nodes) [12], fixed point [52], or passive relay points [53]. These relay nodes are stationary wireless devices injected into the infrastructure of network in order to create additional contact opportunities and increase the connectivity between mobile nodes.Some proposals such as WSNs [54–57], data mules [58, 59], or message ferries [60–63] use a similar approach of path planning to program mobile robots to collect information from sensor nodes. However, it may be effective only in the case that sensor nodes are stationary.Nevertheless, the decreasing in network performance under sparse environment is not mentioned in this proposed protocol. Overall, the performance of most existing algorithms is degrading in very sparse node density, and the energy consumption is not taken into consideration which is a crucial factor in mobile devices.


## 3. The Proposed Rendezvous Based OppNet System

### 3.1. System Model

The proposed system is designed to efficiently use the node-gathering area, that is, rendezvous place, for depositing the delivered messages as much as possible so that the messages can be picked up by the destination node without requiring the exact timing of direct contact between the node carrying a message and the desired destination node. In addition, all nodes should reserve their energy as much as possible when they are out of the rendezvous area.As shown in Figure2, the OppNet node, Nc, whose movement direction is uncontrollable, moves in the system usingpower saving mode until it reaches the rendezvous place where it will turn itself tofull power mode in order to announce its arrival, deposit its carried messages, and pick up the messages destined to itself, to/from the rendezvous place. The rendezvous rumor protocol and the rendezvous node sweeping mechanism are used inside the rendezvous area to facilitate the message exchange more effectively without the need of direct contact between the OppNet node and the high-resource direction-controllable rendezvous node, Nrv, which acts as the center of the rendezvous place. The rendezvous nodes will move around the OppNet network to create suitable rendezvous places according to the proposedrendezvous place searching algorithm.Figure 2
System model.


### 3.2. OppNet Node’s Operational Modes: “Full Power” and “Power Saving”

The OppNet node (Nc) is a mobile node equipped with a radio interface whose transmission range is adjustable in range of [rcmin⁡,rcmax⁡]. The node will operate in eitherfull power mode orpower saving mode according to its location.(
1) Full Power Mode. In this mode, the node will use its full transmission power, rcmax⁡, to search for nearby nodes and exchange messages. It will switch to this mode only when getting into the rendezvous area.(
2) Power Saving Mode. The node, by default, operates in this mode if it is outside the rendezvous place. In this mode, it will alternately change its transmission range between rcmin⁡ and rcmax⁡ in the process of searching for nearby nodes. However, if it receives the searching signal from the other node, it will switch to its full rcmax⁡ immediately in order to increase opportunity to exchange messages with the encountered node as much as possible. Then, it will switch back to minimum rcmin⁡ when departing from the communicating node. Besides the rcmin⁡ and rcmax⁡ values, the ratio of the time interval being in its full rcmax⁡ over the whole time period is a configurable parameter, τs, as shown in Figure 3.Figure 3
Operational modes.


### 3.3. Rendezvous Place and Its Rumor Protocol

The rendezvous place is a dynamic area centered by a special controllable rendezvous node,Nrv. This Nrv node is full of resources such as large message storage and high radio power with maximum transmission range Rrv. The rendezvous place is controlled by the rendezvous node using the rendezvous rumor protocol.The area in a rendezvous place is not fixed as the maximum radio range,Rrv, of the rendezvous node; instead it is virtually determined by the covering radio range of the most outer OppNet nodes which can relay the data messages from the rendezvous node, as shown in Figure 2. The center location of sweeping algorithm is where a rendezvous node stops after moving from other locations.When an OppNet node detects therendezvous area(RA)rumor message broadcasted from the rendezvous node, it learns that it has entered to the rendezvous area. Then, it will switch its operational mode tofull power mode and try to rebroadcast such arendezvous arearumor message so that the other reachable nearby nodes can learn about the rendezvous place and adaptively expand the area on demand. Additionally, the OppNet node in the rendezvous area will periodically announce its arrival and upload its carried data messages to the rendezvous node via thekeep-alive(KA) rumor message and thedeposit(DP) rumor message, respectively. Note that all types of rumor messages will be automatically repeated with aduplication filtering function throughout the area by other OppNet nodes.Once the rendezvous node receives thekeep-alive rumor message which contains the sending node ID, it will gather all data messages destined to the node with that ID from its message storage, encapsulate those found messages into the createdpick-up rumor message, and then broadcast thepick-up(PU) message throughout the rendezvous area. On the other hand, the rendezvous node will keep all of the data messages contained in the receiveddeposit rumor messages in its storage for later sending out to the area when the target node appears later, as seen in Figure 4. The messages will be indefinitely stored in the rendezvous node buffer waiting for the destination nodes to pick up the messages. However, the expired messages will be removed once they reach the message deadline (time-to-live) in order to clear the storage in the buffer.Figure 4
Rendezvous place.In addition to the rendezvous rumor protocol, the rendezvous node implements the rumor message sweeping algorithm in order to increase the chance to collect as many rumor messages as possible. Instead of always being stationary at the center location of the rendezvous place, the rendezvous node will periodically move to its four cardinal directions (north, east, west, and south) by the distance of its radio transmission range as shown in Figure5. This design lets the OppNet nodes on the edge of rendezvous node’s radio range, whose radio signal may not reach to the rendezvous node due to the difference in their radio transmission range, be able to speak back to the rendezvous node.Figure 5
Sweep mechanism.


### 3.4. Rendezvous Place Searching Algorithm

In the proposed system, the rendezvous node should move to find the node-gathering area corresponding with the real behavior of OppNet nodes.(
1) Predictable Behavior OppNet Nodes. In some applications, the movement of OppNet nodes is somehow predictable. For example, the movement of human during the day can be predicted in the opportunistic mobile social network environment [33]. In these applications, the rendezvous nodes can be programmed to be stationed at those areas at the proper time in order to maximize the effectiveness of the proposed system.(
2) Nonpredictable Behavior OppNet Nodes. Without any a priori knowledge about OppNet nodes, the proposeddynamic rendezvous place searching algorithm can be used to guide the rendezvous nodes to the node-gathering area. The rendezvous node will decide to move to the new node-gathering location if the number of OppNet nodes in the current rendezvous place (ηc) falls below the predefined departure node threshold, Hd. The movement direction, Δ→, will be determined periodically based on the collected statistical data from both previously contacting OppNet nodes and other neighboring rendezvous nodes as in (1). In the equation, wc→ is the departure directional unit vector of the contacted OppNet nodes, wr→ is the directional unit vector of the other rendezvous nodes, and φ is a configurable weighting factor between a group of OppNet nodes and a group of other rendezvous nodes in the area,
(1)Δ→=∑i=1C‍ωci→+φ∑j=1R‍δdjwrvj→,
while δdj is the on-off function to include only the other rendezvous nodes whose distance dj is the range of cutoff distance perimeter, Dcc, and C and R are the number of contacted OppNet nodes and the number of other rendezvous nodes, respectively. Consider
(2)δdj=1;dj≤Dcc0;dj>Dcc.The rendezvous node will decide to stop at the expected node-gathering area when the number of OppNet nodes in the current rendezvous place (γc) becomes greater than the predefined rendezvous place node threshold, Γc, as shown in Figure 6.Figure 6
Rendezvous place searching.Note that, the rendezvous nodes will keep moving until they meet the desired conditions. In addition, in the process of moving, the rendezvous node will keep broadcasting the rendezvous area (RA) rumor message, so the OppNet nodes can learn that they are in the rendezvous zone when they detect the RA messages.In fact, the ratio of rendezvous node movement (in searching) time and stop (sweeping) time might be an indicator for the sparseness of the OppNet nodes in the network.


## 3.1. System Model

The proposed system is designed to efficiently use the node-gathering area, that is, rendezvous place, for depositing the delivered messages as much as possible so that the messages can be picked up by the destination node without requiring the exact timing of direct contact between the node carrying a message and the desired destination node. In addition, all nodes should reserve their energy as much as possible when they are out of the rendezvous area.As shown in Figure2, the OppNet node, Nc, whose movement direction is uncontrollable, moves in the system usingpower saving mode until it reaches the rendezvous place where it will turn itself tofull power mode in order to announce its arrival, deposit its carried messages, and pick up the messages destined to itself, to/from the rendezvous place. The rendezvous rumor protocol and the rendezvous node sweeping mechanism are used inside the rendezvous area to facilitate the message exchange more effectively without the need of direct contact between the OppNet node and the high-resource direction-controllable rendezvous node, Nrv, which acts as the center of the rendezvous place. The rendezvous nodes will move around the OppNet network to create suitable rendezvous places according to the proposedrendezvous place searching algorithm.Figure 2
System model.


## 3.2. OppNet Node’s Operational Modes: “Full Power” and “Power Saving”

The OppNet node (Nc) is a mobile node equipped with a radio interface whose transmission range is adjustable in range of [rcmin⁡,rcmax⁡]. The node will operate in eitherfull power mode orpower saving mode according to its location.(
1) Full Power Mode. In this mode, the node will use its full transmission power, rcmax⁡, to search for nearby nodes and exchange messages. It will switch to this mode only when getting into the rendezvous area.(
2) Power Saving Mode. The node, by default, operates in this mode if it is outside the rendezvous place. In this mode, it will alternately change its transmission range between rcmin⁡ and rcmax⁡ in the process of searching for nearby nodes. However, if it receives the searching signal from the other node, it will switch to its full rcmax⁡ immediately in order to increase opportunity to exchange messages with the encountered node as much as possible. Then, it will switch back to minimum rcmin⁡ when departing from the communicating node. Besides the rcmin⁡ and rcmax⁡ values, the ratio of the time interval being in its full rcmax⁡ over the whole time period is a configurable parameter, τs, as shown in Figure 3.Figure 3
Operational modes.


## 3.3. Rendezvous Place and Its Rumor Protocol

The rendezvous place is a dynamic area centered by a special controllable rendezvous node,Nrv. This Nrv node is full of resources such as large message storage and high radio power with maximum transmission range Rrv. The rendezvous place is controlled by the rendezvous node using the rendezvous rumor protocol.The area in a rendezvous place is not fixed as the maximum radio range,Rrv, of the rendezvous node; instead it is virtually determined by the covering radio range of the most outer OppNet nodes which can relay the data messages from the rendezvous node, as shown in Figure 2. The center location of sweeping algorithm is where a rendezvous node stops after moving from other locations.When an OppNet node detects therendezvous area(RA)rumor message broadcasted from the rendezvous node, it learns that it has entered to the rendezvous area. Then, it will switch its operational mode tofull power mode and try to rebroadcast such arendezvous arearumor message so that the other reachable nearby nodes can learn about the rendezvous place and adaptively expand the area on demand. Additionally, the OppNet node in the rendezvous area will periodically announce its arrival and upload its carried data messages to the rendezvous node via thekeep-alive(KA) rumor message and thedeposit(DP) rumor message, respectively. Note that all types of rumor messages will be automatically repeated with aduplication filtering function throughout the area by other OppNet nodes.Once the rendezvous node receives thekeep-alive rumor message which contains the sending node ID, it will gather all data messages destined to the node with that ID from its message storage, encapsulate those found messages into the createdpick-up rumor message, and then broadcast thepick-up(PU) message throughout the rendezvous area. On the other hand, the rendezvous node will keep all of the data messages contained in the receiveddeposit rumor messages in its storage for later sending out to the area when the target node appears later, as seen in Figure 4. The messages will be indefinitely stored in the rendezvous node buffer waiting for the destination nodes to pick up the messages. However, the expired messages will be removed once they reach the message deadline (time-to-live) in order to clear the storage in the buffer.Figure 4
Rendezvous place.In addition to the rendezvous rumor protocol, the rendezvous node implements the rumor message sweeping algorithm in order to increase the chance to collect as many rumor messages as possible. Instead of always being stationary at the center location of the rendezvous place, the rendezvous node will periodically move to its four cardinal directions (north, east, west, and south) by the distance of its radio transmission range as shown in Figure5. This design lets the OppNet nodes on the edge of rendezvous node’s radio range, whose radio signal may not reach to the rendezvous node due to the difference in their radio transmission range, be able to speak back to the rendezvous node.Figure 5
Sweep mechanism.


## 3.4. Rendezvous Place Searching Algorithm

In the proposed system, the rendezvous node should move to find the node-gathering area corresponding with the real behavior of OppNet nodes.(
1) Predictable Behavior OppNet Nodes. In some applications, the movement of OppNet nodes is somehow predictable. For example, the movement of human during the day can be predicted in the opportunistic mobile social network environment [33]. In these applications, the rendezvous nodes can be programmed to be stationed at those areas at the proper time in order to maximize the effectiveness of the proposed system.(
2) Nonpredictable Behavior OppNet Nodes. Without any a priori knowledge about OppNet nodes, the proposeddynamic rendezvous place searching algorithm can be used to guide the rendezvous nodes to the node-gathering area. The rendezvous node will decide to move to the new node-gathering location if the number of OppNet nodes in the current rendezvous place (ηc) falls below the predefined departure node threshold, Hd. The movement direction, Δ→, will be determined periodically based on the collected statistical data from both previously contacting OppNet nodes and other neighboring rendezvous nodes as in (1). In the equation, wc→ is the departure directional unit vector of the contacted OppNet nodes, wr→ is the directional unit vector of the other rendezvous nodes, and φ is a configurable weighting factor between a group of OppNet nodes and a group of other rendezvous nodes in the area,
(1)Δ→=∑i=1C‍ωci→+φ∑j=1R‍δdjwrvj→,
while δdj is the on-off function to include only the other rendezvous nodes whose distance dj is the range of cutoff distance perimeter, Dcc, and C and R are the number of contacted OppNet nodes and the number of other rendezvous nodes, respectively. Consider
(2)δdj=1;dj≤Dcc0;dj>Dcc.The rendezvous node will decide to stop at the expected node-gathering area when the number of OppNet nodes in the current rendezvous place (γc) becomes greater than the predefined rendezvous place node threshold, Γc, as shown in Figure 6.Figure 6
Rendezvous place searching.Note that, the rendezvous nodes will keep moving until they meet the desired conditions. In addition, in the process of moving, the rendezvous node will keep broadcasting the rendezvous area (RA) rumor message, so the OppNet nodes can learn that they are in the rendezvous zone when they detect the RA messages.In fact, the ratio of rendezvous node movement (in searching) time and stop (sweeping) time might be an indicator for the sparseness of the OppNet nodes in the network.


## 4. Evaluation

The objective of the evaluation is to analyze the performance of our proposed protocol on the sparse network environment comparing with traditional OppNet protocols. We compare both predictable and nonpredictable behavior OppNet nodes with the commonly well-known epidemic protocol [16] under different node-density environments.


### 4.1. Simulation Setup

We set up a simulation environment using ONE (opportunistic network environment) [64], which is a powerful tool designed for running opportunistic network simulation with various routing protocols and different movement models. All the results are obtained by averaging over a few hundreds of independent simulation runs with different seeds. For the OppNet simulation model, the main parameter that largely affects the evaluation performance is the movement model. In our evaluation, we deploy the group movement model instead of the most commonly used random way point (RWP) model [65], to correctly capture the actual behavior of node movements. In fact, several multihop wireless network scenarios are most realistically represented using the group movement model [66] which represents the random motion of a group of mobile nodes as well as the random motion of each individual mobile node within the group. This is the vital case for modeling the routing simulation in OppNet since the movements in several cases are in swarm behavior, in which nodes are aggregating together and moving in some directions, such as the movement of humans in disasters or military tactical operations. The other parameters that mainly affect the evaluation performance are the area of operation, the wireless range of the nodes, node velocity, and spatial locations of the nodes [65]. In our simulation, we fix the number of nodes while increasing and decreasing the area of operation which results in a wide range of node-density parameters for evaluation. Node density (λ) is defined as the number of nodes per unit area. If N nodes are distributed in a square grid of size M×Mm2 then the λ is given by λ=N/M2. The wireless range of our OppNet node can be adjusted depending on the environment, while the node velocity is equal to the normal human walking speed. The common parameters are summarized in Table 1.Table 1
Simulation variables.
Parameters
N
c
N
rv
Message size
500 KB–1 MB
Maximum radio range
30 meters
100 meters
Transmission speed
54 Mbps
Router
DRRA—epidemic
Moving speed
0.5–1.5 m/s
Movement model
Group movement model


### 4.2. Metric

Opportunistic routing protocols are commonly evaluated by delivery ratio, median latency, and network overhead. In this paper, we focus on delivery ratio and network overhead in terms of energy consumed to deliver a message within a specific message deadline. We assume that all messages delivered within the deadline have no difference in protocol performance.(a) Delivery Ratio (
D
r
). It is defined as the ratio of the total number of messages successfully delivered within the deadline (Mdelivered) to the total number of messages created from the source nodes that need to be delivered (Mcreated) as shown in
(3)Dr=MdeliveredMcreated.(b) Energy Consumption (
E
c
). It is defined as the amount of energy consumption required by all related OppNet nodes to deliver one Mcreated message. We simplify the energy consumption model by only considering the communication energy consumption of the wireless interface to transmit a message by determining the number of all necessary protocol packets, Mpacket, per number of Mcreated messages. To transmit an L-bit-length packet using a radio interface with transmission range, d, the consumed energy, ET, can be determined by the following equation [67, 68], where α is the power loss component with α∈2,4 and ϵfsJ/(bit/mα) is the amount of energy consumed by an amplifier to transmit one-bit data at an acceptable quality level:
(4)ET=L·ϵfs·dα.As a result, the energy consumption (Ec) can be derived as
(5)Ec=MpacketMcreated·Lp·ϵfs·r2.Note thatLp is the size of a protocol packet, r is the radio transmission range of the protocol packet, and α is equal to two in our simulations.(c) Protocol Performance (
P
Ψ
). It is a composite metric to capture the gain in both delivery capability and energy saving capability of a specific protocol, compared with the baseline protocol, epidemic. The PΨ can be calculated from
(6)PΨ=DrP,B·1EcP,B=DrPDrB·EcBEcP.In this equation,P is the target protocol while B is the baseline protocol (epidemic protocol, e.g.) to be used as comparative energy reference.


### 4.3. Simulation Results

This section shows the results of the different sets of simulation runs that have been performed to study the performance of the proposed routing protocol and its behaviors when changing the protocol’s key parameters.(
1) General Protocol Performance. Firstly, the comparison of delivery ratio is shown in Figure 7, where the x-axis represents the node density (the number of nodes in the area of one km2) and the y-axis shows the delivery ratio. In our simulation, we assume the environment of one rendezvous node and the ratio of time interval between full power and power saving, τs, of 0.5. Figure 7 shows that our proposed protocols gain slightly better delivery ratio in the dense environment. On the other hand, the proposed protocols gain significantly higher delivery ratio in the sparse environment by maintaining the ratio up to 80%, even when node density is as low as 50 nodes/km2 in nonpredictable behavior or as low as 5 nodes/km2 nodes in predictable behavior. Overall, on average, our proposed protocols gain approximately 40% higher delivery ratio than existing traditional epidemic routing in sparse networks.Figure 7
Delivery ratio per node density.The reason behind this is that the proposed rendezvous concept can facilitate a message exchanging process between nodes passing through the same area but on the different timeline as designed. Those nodes cohabiting on both time and space domains are more likely to appear in dense networks but less likely to emerge in sparse networks. In addition, with the knowledge of node-gathering areas (predictable behavior), the delivery ratio of the proposed protocol can be further increased especially in the extremely low-node-density scenario.Additionally, if the nodes passively wait for the target node to enter the rendezvous place, it can harm the efficiency of packet delivery as in Figure7. The relay points algorithm is a relay node implemented from the concept of recent relay node protocol [50, 51] such as throwboxes which is a passive stationary node waiting for the target node to encounter. The result shows that the relay point gains slightly higher delivery ratio than epidemic protocol but significantly lower delivery ratio than rendezvous protocol especially in the sparse area. The reason behind this is because rendezvous protocol can increase the zone of transmission range, thus facilitating gaining efficient node contact opportunities. In plan path, the relay nodes are moving according to the designed plan. In the simulation, the plan path is a zigzag path which can cover all coverage area in a certain time. The result from Figure 7 shows that the plan path presents a similar trend to epidemic protocol while gaining slightly delivery ratio than fixed relay points. However, it cannot achieve delivery ratio as high as that of the proposed rendezvous based protocol due to the dynamic nonstationary movement of OppNet node and the lack of contact activity enhancement like rendezvous protocol.Secondly, the energy consumption (Ec), which is another vital factor in opportunistic networks where most mobile nodes are usually equipped with limited power resources, is shown in Figure 8. The x-axis represents node density and the y-axis is the Ec in unit of energy consumption per 1,000 messages. This graph shows that the value of Ec linearly increases when a network becomes more dense. The trend on the graph is similar to the number of generated protocol packets per created message on the node-density graph in Figure 9. The predictable behavior saves energy consumption by 80% compared to the epidemic protocol while the nonpredictable behavior can save around 60% compared to the epidemic counterpart. On the other hand, the number of generated protocol packets per created message of the predictable behavior scenario is 60% and for the nonpredictable behavior is 30% lower than the epidemic protocol. The reason for Ec rising in the dense environment results from the increasing of node meeting activities from the growing number of nodes generating messages. The trend similarity in Figures 8 and 9 is derived from the increasing number of messages in (5) which results from the rising energy consumption. Our proposed protocols require the lower number of generated messages while presenting a significantly lower Ec which results from the fact that the rendezvous protocols utilize a shorter average wireless radius.Figure 8
Energy consumption per node density.Figure 9
Number of generated protocol packets per created message on node density.Combining both gains in delivery ratio and energy consumption savings, the proposed general protocol performance can be seen in Figure10. The epidemic protocol is used as the baseline protocol in Pψ calculations so its value in Figure 10 is 1. The proposed general protocol performance can rise up to 20 times compared to the existing epidemic protocol when a network is very sparse and on average about 5–10 times in general network environments compared to the epidemic protocol.Figure 10
General protocol performance per node density.(
2) Impacts of the Power Saving Factor. In this subsection, we study protocol parameters relevant to the power saving factor and the tradeoffs between power consumption and delivery ratio. We define the power saving factor, nps, as the composite parameters of the proposed protocol as in
(7)nps=τs·rcmax⁡-rcmin⁡rcmax⁡.
The nps is mainly calculated from the time being in power saving mode, τs, and the portion of energy consumption used when being in such power saving mode. The value of nps is in range [0,1] where its minimum value (no saving) represents the fact that either OppNet nodes never operate in power saving mode of the proposed protocol or the maximum energy consumption (rcmin⁡=rcmax⁡) is used in such mode. The opposite behavior in power saving mode applies for the maximum nps. Figure 11 shows both delivery ratio (Dr on solid line) and energy consumption (Ec on dash line) when varying the power saving factor (nps) for the node density (α) = 100 and 300 nodes/km2. The graph shows that when nps increases, the value of Ec and Dr decreased as expected. The delivery ratio for more sparse networks significantly drops when the nps increases because the saving factor can degrade the delivery performance if the nodes spend more time in saving mode. In fact, the optimum of nps depends on the real applications. In the application with the level of acceptable minimum Dr as a threshold, we can select the nps that gives the minimum Ec. On the other hand, we can select the nps that gives the maximum Dr if the threshold of acceptable maximum Ec is defined. Finally, if both the minimum Dr and maximum Ec are defined, we can get the nps value that suits the application.Figure 11
Delivery ratio and energy consumption on power saving factor.(
3) Other Network Environment Parameters. In this subsection, we investigate other protocol and environmental parameters which may have effects on the proposed protocol performance. Figure 12 presents the variation on the number of rendezvous nodes to analyze the impacts on delivery ratio per node density. This graph shows that more rendezvous nodes can achieve more Dr as expected. In Figure 13, the effect of Rrv/Rcmax⁡ ratio on delivery ratio is studied. By increasing Rrv (maximum radio transmission of rendezvous node), the Dr will not increase but slightly decrease. This is the result from the asymmetry in transmission ranges of OppNet nodes which can degrade the delivery ratio performance in the rendezvous area, since the nodes with a longer transmission range can send the messages to other nodes with shorter ranges but cannot receive the messages back. Finally, Figure 14 shows that our proposed rendezvous protocol performance will drop if node movements become more random since the proposed protocol utilizes the group gathering behavior to increase message exchanging activities.Figure 12
Multiple rendezvous nodes.Figure 13
R
rv
/
R
c
max
⁡ ratio.Figure 14
Movement model comparison.


## 4.1. Simulation Setup

We set up a simulation environment using ONE (opportunistic network environment) [64], which is a powerful tool designed for running opportunistic network simulation with various routing protocols and different movement models. All the results are obtained by averaging over a few hundreds of independent simulation runs with different seeds. For the OppNet simulation model, the main parameter that largely affects the evaluation performance is the movement model. In our evaluation, we deploy the group movement model instead of the most commonly used random way point (RWP) model [65], to correctly capture the actual behavior of node movements. In fact, several multihop wireless network scenarios are most realistically represented using the group movement model [66] which represents the random motion of a group of mobile nodes as well as the random motion of each individual mobile node within the group. This is the vital case for modeling the routing simulation in OppNet since the movements in several cases are in swarm behavior, in which nodes are aggregating together and moving in some directions, such as the movement of humans in disasters or military tactical operations. The other parameters that mainly affect the evaluation performance are the area of operation, the wireless range of the nodes, node velocity, and spatial locations of the nodes [65]. In our simulation, we fix the number of nodes while increasing and decreasing the area of operation which results in a wide range of node-density parameters for evaluation. Node density (λ) is defined as the number of nodes per unit area. If N nodes are distributed in a square grid of size M×Mm2 then the λ is given by λ=N/M2. The wireless range of our OppNet node can be adjusted depending on the environment, while the node velocity is equal to the normal human walking speed. The common parameters are summarized in Table 1.Table 1
Simulation variables.
Parameters
N
c
N
rv
Message size
500 KB–1 MB
Maximum radio range
30 meters
100 meters
Transmission speed
54 Mbps
Router
DRRA—epidemic
Moving speed
0.5–1.5 m/s
Movement model
Group movement model


## 4.2. Metric

Opportunistic routing protocols are commonly evaluated by delivery ratio, median latency, and network overhead. In this paper, we focus on delivery ratio and network overhead in terms of energy consumed to deliver a message within a specific message deadline. We assume that all messages delivered within the deadline have no difference in protocol performance.(a) Delivery Ratio (
D
r
). It is defined as the ratio of the total number of messages successfully delivered within the deadline (Mdelivered) to the total number of messages created from the source nodes that need to be delivered (Mcreated) as shown in
(3)Dr=MdeliveredMcreated.(b) Energy Consumption (
E
c
). It is defined as the amount of energy consumption required by all related OppNet nodes to deliver one Mcreated message. We simplify the energy consumption model by only considering the communication energy consumption of the wireless interface to transmit a message by determining the number of all necessary protocol packets, Mpacket, per number of Mcreated messages. To transmit an L-bit-length packet using a radio interface with transmission range, d, the consumed energy, ET, can be determined by the following equation [67, 68], where α is the power loss component with α∈2,4 and ϵfsJ/(bit/mα) is the amount of energy consumed by an amplifier to transmit one-bit data at an acceptable quality level:
(4)ET=L·ϵfs·dα.As a result, the energy consumption (Ec) can be derived as
(5)Ec=MpacketMcreated·Lp·ϵfs·r2.Note thatLp is the size of a protocol packet, r is the radio transmission range of the protocol packet, and α is equal to two in our simulations.(c) Protocol Performance (
P
Ψ
). It is a composite metric to capture the gain in both delivery capability and energy saving capability of a specific protocol, compared with the baseline protocol, epidemic. The PΨ can be calculated from
(6)PΨ=DrP,B·1EcP,B=DrPDrB·EcBEcP.In this equation,P is the target protocol while B is the baseline protocol (epidemic protocol, e.g.) to be used as comparative energy reference.


## 4.3. Simulation Results

This section shows the results of the different sets of simulation runs that have been performed to study the performance of the proposed routing protocol and its behaviors when changing the protocol’s key parameters.(
1) General Protocol Performance. Firstly, the comparison of delivery ratio is shown in Figure 7, where the x-axis represents the node density (the number of nodes in the area of one km2) and the y-axis shows the delivery ratio. In our simulation, we assume the environment of one rendezvous node and the ratio of time interval between full power and power saving, τs, of 0.5. Figure 7 shows that our proposed protocols gain slightly better delivery ratio in the dense environment. On the other hand, the proposed protocols gain significantly higher delivery ratio in the sparse environment by maintaining the ratio up to 80%, even when node density is as low as 50 nodes/km2 in nonpredictable behavior or as low as 5 nodes/km2 nodes in predictable behavior. Overall, on average, our proposed protocols gain approximately 40% higher delivery ratio than existing traditional epidemic routing in sparse networks.Figure 7
Delivery ratio per node density.The reason behind this is that the proposed rendezvous concept can facilitate a message exchanging process between nodes passing through the same area but on the different timeline as designed. Those nodes cohabiting on both time and space domains are more likely to appear in dense networks but less likely to emerge in sparse networks. In addition, with the knowledge of node-gathering areas (predictable behavior), the delivery ratio of the proposed protocol can be further increased especially in the extremely low-node-density scenario.Additionally, if the nodes passively wait for the target node to enter the rendezvous place, it can harm the efficiency of packet delivery as in Figure7. The relay points algorithm is a relay node implemented from the concept of recent relay node protocol [50, 51] such as throwboxes which is a passive stationary node waiting for the target node to encounter. The result shows that the relay point gains slightly higher delivery ratio than epidemic protocol but significantly lower delivery ratio than rendezvous protocol especially in the sparse area. The reason behind this is because rendezvous protocol can increase the zone of transmission range, thus facilitating gaining efficient node contact opportunities. In plan path, the relay nodes are moving according to the designed plan. In the simulation, the plan path is a zigzag path which can cover all coverage area in a certain time. The result from Figure 7 shows that the plan path presents a similar trend to epidemic protocol while gaining slightly delivery ratio than fixed relay points. However, it cannot achieve delivery ratio as high as that of the proposed rendezvous based protocol due to the dynamic nonstationary movement of OppNet node and the lack of contact activity enhancement like rendezvous protocol.Secondly, the energy consumption (Ec), which is another vital factor in opportunistic networks where most mobile nodes are usually equipped with limited power resources, is shown in Figure 8. The x-axis represents node density and the y-axis is the Ec in unit of energy consumption per 1,000 messages. This graph shows that the value of Ec linearly increases when a network becomes more dense. The trend on the graph is similar to the number of generated protocol packets per created message on the node-density graph in Figure 9. The predictable behavior saves energy consumption by 80% compared to the epidemic protocol while the nonpredictable behavior can save around 60% compared to the epidemic counterpart. On the other hand, the number of generated protocol packets per created message of the predictable behavior scenario is 60% and for the nonpredictable behavior is 30% lower than the epidemic protocol. The reason for Ec rising in the dense environment results from the increasing of node meeting activities from the growing number of nodes generating messages. The trend similarity in Figures 8 and 9 is derived from the increasing number of messages in (5) which results from the rising energy consumption. Our proposed protocols require the lower number of generated messages while presenting a significantly lower Ec which results from the fact that the rendezvous protocols utilize a shorter average wireless radius.Figure 8
Energy consumption per node density.Figure 9
Number of generated protocol packets per created message on node density.Combining both gains in delivery ratio and energy consumption savings, the proposed general protocol performance can be seen in Figure10. The epidemic protocol is used as the baseline protocol in Pψ calculations so its value in Figure 10 is 1. The proposed general protocol performance can rise up to 20 times compared to the existing epidemic protocol when a network is very sparse and on average about 5–10 times in general network environments compared to the epidemic protocol.Figure 10
General protocol performance per node density.(
2) Impacts of the Power Saving Factor. In this subsection, we study protocol parameters relevant to the power saving factor and the tradeoffs between power consumption and delivery ratio. We define the power saving factor, nps, as the composite parameters of the proposed protocol as in
(7)nps=τs·rcmax⁡-rcmin⁡rcmax⁡.
The nps is mainly calculated from the time being in power saving mode, τs, and the portion of energy consumption used when being in such power saving mode. The value of nps is in range [0,1] where its minimum value (no saving) represents the fact that either OppNet nodes never operate in power saving mode of the proposed protocol or the maximum energy consumption (rcmin⁡=rcmax⁡) is used in such mode. The opposite behavior in power saving mode applies for the maximum nps. Figure 11 shows both delivery ratio (Dr on solid line) and energy consumption (Ec on dash line) when varying the power saving factor (nps) for the node density (α) = 100 and 300 nodes/km2. The graph shows that when nps increases, the value of Ec and Dr decreased as expected. The delivery ratio for more sparse networks significantly drops when the nps increases because the saving factor can degrade the delivery performance if the nodes spend more time in saving mode. In fact, the optimum of nps depends on the real applications. In the application with the level of acceptable minimum Dr as a threshold, we can select the nps that gives the minimum Ec. On the other hand, we can select the nps that gives the maximum Dr if the threshold of acceptable maximum Ec is defined. Finally, if both the minimum Dr and maximum Ec are defined, we can get the nps value that suits the application.Figure 11
Delivery ratio and energy consumption on power saving factor.(
3) Other Network Environment Parameters. In this subsection, we investigate other protocol and environmental parameters which may have effects on the proposed protocol performance. Figure 12 presents the variation on the number of rendezvous nodes to analyze the impacts on delivery ratio per node density. This graph shows that more rendezvous nodes can achieve more Dr as expected. In Figure 13, the effect of Rrv/Rcmax⁡ ratio on delivery ratio is studied. By increasing Rrv (maximum radio transmission of rendezvous node), the Dr will not increase but slightly decrease. This is the result from the asymmetry in transmission ranges of OppNet nodes which can degrade the delivery ratio performance in the rendezvous area, since the nodes with a longer transmission range can send the messages to other nodes with shorter ranges but cannot receive the messages back. Finally, Figure 14 shows that our proposed rendezvous protocol performance will drop if node movements become more random since the proposed protocol utilizes the group gathering behavior to increase message exchanging activities.Figure 12
Multiple rendezvous nodes.Figure 13
R
rv
/
R
c
max
⁡ ratio.Figure 14
Movement model comparison.


## 5. Conclusion

Opportunistic routing techniques can be applied in a plentiful variety of scenarios such as Social Mobile Network, Disaster Recovery Networks, or Military Tactical Network. In this paper, we investigate the use of rendezvous points in opportunistic network routing to increase the delivery ratio in extreme sparse network environment. This novel protocol proposes the two new types of nodes, rendezvous node and OppNet node, which can help in maintaining the messages in one place as long as possible in order to bridge the gap of time and space domains. In this rendezvous place, the passing nodes can announce, deposit, and pick up their own messages without meeting with other nodes that carried desired messages. The size and shape of a rendezvous place can be adapted to the environment of OppNet nodes in the area. We define our routing model in two functions: predictable and nonpredictable behavior OppNet node functions. The results suggest that our protocols perform significantly higher in terms of general protocol performance which is the tradeoff of delivery ratio per energy consumption. This implies that if the location of rendezvous place can be predicted, we can achieve the highest overall performance. In the future work, this concept of smart nodes can be further extended to increase the intelligence of the node since the technologies can be rapidly advanced.



---

*Source: 819178-2015-02-26.xml*