Opportunistic networks (OPPNETs, also known as pocket switched networks) have become one of the emerging wireless communication techniques due to the appearance of smart mobile devices such as cell phones and tablets. OPPNETs enable mobile users to communicate with their social contacts [1]. However, the frequent disconnection and sparse density in OPPNETs cause virtually no complete paths to be found between the source and destination. Such a network falls into the category of mobile ad hoc networks (MANETs) and delay-tolerant networks (DTNs) [2].

In OPPNETs, nodes communicate in multiple hops and relay nodes forward messages to other nodes. Furthermore, forwarding does not work on-the-fly, because the relay nodes store the messages when no forwarding opportunity exists. A node should use any other node with connection opportunities to forward the messages [3]; this forwarding process is called a store, carry, and forwarding scheme.

Fig. 1 illustrates an example of message forwarding in OPPNETs. The arrows indicate the moving directions of the nodes and the circles are their communication ranges. The source node S wants to send a message to the destination node D. However, there may be no complete route between S and D. Thus, S sends its message to its neighbor node N₁, which carries the message until it encounters node N₃ to which it forwards the message and then N₃ carries the message until it meets the destination D. As a result, S’s message is successfully delivered to the destination node D.

The problem of message forwarding is thus the selection of proper relay nodes to which the message (or duplicate of the message for a multi-copy scheme) should be sent [4].

The representative social-unaware scheme, Epidemic [5], shows the highest network traffic, since it duplicates messages to any nodes without social information.

On the other hand, the other social-unaware scheme, WAIT, has the longest transmission delay and the lowest network traffic, because it uses a single copy of the message and waits until the source node meets the destination.

Even if ProPHET [6] is a social-aware scheme, it also has higher network traffic, because it still spreads the message to the nodes with a higher delivery predictability. It is very difficult for these schemes to optimize the equilibrium between the network traffic and transmission delay. Thus, it is important to select proper relay nodes as the next hops and to use an appropriate number of copies of the message considering both the network traffic and transmission delay.

To resolve this problem, we propose a new forwarding scheme, called the direction entropy-based forwarding scheme (DEFS), in order to achieve equilibrium between the network traffic and transmission delay. People usually move around with different speeds, locations, and directions. If we give a message to people going to different locations to which we may not go ourselves, we have a better chance of delivering the message to the destination more quickly. To take advantage of this concept, DEFS uses the main direction and the direction entropy of a node. By the main direction of a node, we mean the direction that the nodes move with the highest frequency among the four cardinal directions. In DEFS, the direction entropy captures the certainty of the direction of a node. The lower the direction entropy a node has, the greater the certainty of direction it has; that is, the likelihood that the node moves in a certain direction. Since each node sends a message to another node with a different location and less direction entropy, DEFS utilizes those nodes that are more likely to travel to various locations to forward the messages to the destination node. For these reasons, DEFS selects the proper number of relay nodes during forwarding and, thus, it balances the network traffic and transmission delay quite well.

This paper is organized as follows. We first discuss related work in Section II. Section III introduces the proposed scheme in more detail. The simulation environment and experimental results are provided in Section IV. Finally, our conclusions are drawn and future work is discussed in Section V.

Opportunistic routing schemes can be classified into two categories: social-unaware and social-aware ones. Social-unaware schemes do not use the social information at all, whereas social-aware ones take advantage of the information about the nodes’ behaviors or social relations to make decisions about forwarding messages.

Routing schemes, such as Epidemic and Spray-and- Wait [7], can be considered as social-unaware routing schemes, as they do not need to any specific social information for routing. In Epidemic, a node duplicates the message to others whenever the node encounters other nodes. In Spray-and-Wait, a node sprays a fixed number k of duplicates of the message into some encountered nodes and then waits until these nodes meet the destination.

Various social-aware routing schemes have been proposed in OPPNETs [4, 6, 8-10]. SimBet [8] uses the locally determined social similarity and the betweenness centrality to the destination. When a node meets other nodes, it sends the message to the node that has a higher value computed with the similarity and betweenness centrality. Bubble rap [9] makes use of both the global and local centralities. Bubble rap sends a message to the destination or its community. However, when the destination belongs only to a community whose members have a low global centrality value, this scheme may fail to deliver the message. In this case, a relay node cannot be identified as the destination in the same local community. PRoPHET [6] estimates a probabilistic metric called the delivery predictability. When the nodes are near enough to the destination, they exchange the vector of the information on the messages and the delivery predictability vector. The information in the vector is used to determine which message should be sent. PeopleRank [10] uses the PageRank algorithm of Google for forwarding decisions. When the adjacent nodes meet in the social network, they exchange their current values of PeopleRank and the numbers of neighbors in the social network. In [4], an analytical model based on Markov processes for socialaware routing in OPPNETs was proposed.

The system used for the proposed scheme obeys the rules of typical data forwarding. Each node in a network has a unique identifier. The nodes in a network are denoted by N = {N₁, N₂, N₃, …, N_m}, where m is the number of nodes in the network. Every node periodically measures its own direction. To determine the direction, each mobile device is assumed to have a positioning system. A node determines the direction according to its position changes. Such processing incurs some additional computational overhead. However, this paper does not focus on the reduction of the computational cost. Note that this can be achieved with simple equations.

A source node is not aware of the current position of the destination node. Nodes move around with various directions. DEFS utilizes the information about the directions of the nodes. Each node accumulates its moving direction changes within a fixed angle for the four cardinal directions: north, south, west, and east. A fixed angle is a right angle, as illustrated in Fig. 2.

Each node determines the highest frequency of its moving direction changes for its main direction and also computes the entropy of the movement directions for certainty.

The direction entropy is based on the information entropy of information theory, in which the entropy is a measure of the uncertainty in a random variable [11]. The direction entropy is a numerical value, such that the smaller the value is, the more reliable it is; that is, a large value indicates less certainty.

The main direction of a node N_i is denoted as δ_i and E_i is the value of the direction entropy of N_i. σ_i is the total number of direction changes made by N_i. In this context, the direction entropy E_i of a node N_i is a numerical value about the certainty of direction, which is defined as follows.

In the equation above, p() is the probability mass function of N_i’s outcome (frequency) , indicating one of the four cardinal directions, where d = 1 (north), 2 (south), 3 (east), or 4 (west). The base of the logarithm is 4 in the equation, due to the entropy value normalization. Thus, the entropy value is between 0 and 1.0.

Fig. 3 shows an example of the direction information. The accumulated occurrences in each direction are recorded on the table. The direction of the maximum accumulated value is denoted as δ; thus δ = east in the example. The values of σ and E are calculated based on the accumulated values. In the example of Fig. 3, σ = 97; that is, the sum of accumulated values, 21 + 19 + 33 + 24 = 97.

E in the example is computed by applying the above equation as follows:

x1 = 21/97 = 0.2165, x2 = 19/97 = 0.1959 x3 = 33/97 = 0.3402, x4 = 24/97 = 0.2474 log4x1 = -1.1038, log4x2 = -1.1760 log4x3 = -0.7778, log4x4 = -1.0074 E = -(x1log4x1 + x2log4x2 + x3log4x3 + x4log4x4 ) = 0.9831

Each node calculates its σ and E as explained in the example.

In DEFS, a node N_i waits and carries its message until it meets the destination node or sends the message to an encountered node N_j with δ_j being different from δ_i and E_j being less than a threshold τ. The forwarding process is terminated when all the messages are delivered to their respective destinations. We determined the threshold τ with extensive experiments, as described in the next section.

A message M consists of the following components:

Mi = ,

where Data_i is the message content, S_i is the ID of the source that generated the data, D_i is the ID of the destination node, and t is the time at which M_i is generated.

Fig. 4 shows an example of the forwarding decisions made in DEFS. We assume that the threshold τ is 0.97 for the example. When N₂ meets N₁ and N₃, they exchange their direction information and direction entropies. Then N₂ finds that E₁ < 0.97 and δ₁ = north, which different from δ₂ = west. Hence N₂ forwards the message to N₁. However, N₂ does not send the message to N₃ since δ₂ = δ₃. In the meantime, N₄ does not transmit the message to N₅, since E₅ is 0.9957 > 0.97. However, since the direction entropy of N₄ is the less than the threshold and it has a different main direction from δ₅, N₅ transmits the message to N₄, if anywhere.

In this paper, we use the network simulator NS-2 v.2.35 [12] for the simulations. The number of nodes is set to 40. The network area is set to 450 m × 450 m and the communication range is 10 m. The movement of a node follows the HCMM [13] which is a frequently used moving pattern in OPPNET simulations. The velocity of a node ranges from 1 to 9 m/s, which is appropriate for pedestrians and vehicles. In our simulator, a mobile node issues a single message. The total simulation time is 9,600 seconds. The warm-up time for estimating the direction entropies is 600 seconds. After transmitting a message to other nodes, the originating node does not delete it. In addition, for the sake of simplicity, we do not consider the buffer size, bandwidth, or power. We run each scheme 20 times to calculate the average of the results. Table 1 shows the parameters used in our simulation. In this experiment, we evaluate three metrics: the delivery success ratio, the network traffic, and the delay time. The delivery success ratio is the ratio of the number of messages reaching the destination to the total number of messages generated. The network traffic is the number of packets sent and received between nodes. The delay time is the time period from the moment that a message is generated to the time at which it is delivered to the destination. Our simulation followed the hotspot [14].

We examine the performance of DEFS at different values of the threshold, τ. Fig. 5 shows the results of the experiments in terms of the delivery ratio, the network traffic and the delay time with various values of τ. The threshold τ may vary up to 1.0 from 0.90.

Fig. 5(a) shows the variation of the delivery ratio as the simulation time increases. The delivery ratio increases with increasing threshold τ.

As shown in Fig. 5(b), the y-axis is on the log-scale and the x-axis represents the threshold τ varying from 0.91 to 1.00 in increments of 0.01. When the threshold τ is small, DEFS exhibits low traffic, while when it is large, DEFS show high traffic. Such a phenomenon arises since, in DEFS, a node forwards the message to other nodes with direction entropies less than τ and different main directions.

On the other hand, in Fig. 5(c), as the threshold τ increases, DEFS shows a lower delay, since in DEFS nodes have a better chance of forwarding the messages to more nodes; hence, the forwarding process is done more quickly. However, when the threshold τ is large, DEFS has similar performance to the flooding-based scheme, since there are more and more nodes that participate in forwarding process.

Note that when τ = 1.0, all the nodes in the network have a chance of being involved in forwarding, as long as they have different main directions, because the maximum value of the direction entropy is 1.0.

However, since DEFS allows forwarding to the nodes with direction entropies of less than τ and different main directions, its traffic amount is still smaller than those of the flooding-based schemes.

From the results in Fig. 5, we determined that the value of the threshold τ = 0.97 for our simulation, because when τ = 0.97 the delivery ratio approaches 1.0 after 2,800 seconds and a good balance is achieved between the network traffic and the delay time.

First, we evaluate the performance based on the simulation time for each of the three schemes: Epidemic, PRoPHET, and WAIT. We set the threshold τ to 0.97 for DEFS. Fig. 6(a) shows the delivery ratios of the schemes as the simulation time increases. The results are shown after 600 seconds due to the warm-up period. The flooding- based schemes achieve the maximum delivery ratio faster, due to the use of multiple copies of the messages. WAIT does not distribute the message and waits for the destination instead.

Therefore, WAIT requires a longer time to reach a delivery ratio of 1.0. In DEFS, the nodes basically forward the packets by flooding. Hence, DEFS is faster than the other schemes except for Epidemic.

Fig. 6(b) shows the results of the network traffic for the various schemes. Note that the y-axis of the figure is on the log-scale. DEFS exhibits much lower traffic than Epidemic and PRoPHET with 93.7% and 74.4% improvements, respectively. DEFS shows higher traffic than WAIT, because the nodes in WAIT forward the packets only when they meet the destination nodes.

The reason why DEFS shows such a reduction in traffic is that the relay nodes are suitably selected. Observe that those nodes with the same δ tend to head in the same direction and those that move in the four directions evenly are highly likely to crisscross with other nodes. Thus, DEFS selects a relay node that has a different δ from that of the neighboring node with the message, as well as a low entropy value.

Note that the traffic of WAIT is equivalent to the number of messages generated for the simulation. Fig. 6(c) compares the delay times of the schemes, showing almost a reverse trend compared to the network traffic results in Fig. 6(b). The average delay time of DEFS is about 198 seconds longer than that of Epidemic, while it is 84 seconds shorter than that of PRoPHET. In DEFS, relaying nodes with lower entropies move all around the network, resulting in faster delivery of the message, although a source node doesn’t know where the destination node is. The results of the experiments show that DEFS outperforms PRoPHET in terms of both the network traffic and delay.

In OPPNETs, the use of flooding-based schemes results in higher network traffic and lower transmission delays. On the other hand, the wait-based schemes suffer from unbearable transmission delays. In order to resolve this problem of imbalance between the traffic and delay, we proposed an effective forwarding scheme using the direction entropy and main direction, which capture the uncertainty in people’s mobility. As a future work, we plan to study more enhanced predictable forwarding schemes with the coordinates of the nodes in OPPNETs.