Profile
International Journal of Computer & Software Engineering Volume 4 (2019), Article ID 4:IJCSE-145, 7 pages
https://doi.org/10.15344/2456-4451/2019/145
Research Article
An Efficient Message Forwarding Scheme with Epidemic Routing Considering the Number of Stopover Nodes in Delay Tolerant Network Environment

Yusuke Ishibayashi1* and Shinji Sugawara2

1Graduate School of Engineering, Chiba Institute of Technology, Chiba 275-0016, Narashino, Japan
2Faculty of Engineering, Chiba Institute of Technology, Chiba 275-0016, Narashino, Japan
Yusuke Ishibayashi, Graduate School of Engineering, Chiba Institute of Technology, Chiba 275-0016, Narashino, Japan; E-mail: s1422030dm@s.chibakoudai.jp
06 March 2019; 23 April 2019; 25 April 2019
Ishibayashi Y, Sugawara S (2019) An Efficient Message Forwarding Scheme with Epidemic Routing Considering the Number of Stopover Nodes in Delay Tolerant Network Environment. Int J Comput Softw Eng 4: 145. doi: https://doi.org/10.15344/2456-4451/2019/145
This work was partially supported by JSPS KAKENHI Grant Number JP17K00134.

Abstract

This paper proposes an efficient message transmission method by direct short-range communications with mobile terminals based on epidemic routing. In a previous study, when a message packet arrives at its destination node, it floods the network with packets called “anti-packets,” and deletes packets with the same message in an effort to enhance the efficiency of the buffer memories of the other terminals. Because anti-packets are not issued until the message arrives at its destination, there is not an efficient termination process. In this paper, the timing to issue anti-packets is accelerated by observing the number of nodes that a message packets has gone through, allowing wasted message packets to be eliminated earlier. Computer simulations show that the proposed method improves the messagearrival rate and reduces the average time required for message arrival.


1. Introduction

In recent years, broadbandization and the improvement of wireless communication terminals have realized easy access and exchange of a wide variety of information. However, when base stations fail in case of disaster or terminals are out of communication range, most mobile communications cannot be established. Nevertheless, if direct communications are available, communications between two terminals are possible even in an environment where the connection is unstable. This paper proposes a method for efficient data transfer by direct communications between mobile terminals while securing the storage capacity of each terminal. Taking advantage of epidemic routing in an ad-hoc network, the proposed method improves the Vaccine method [2], which transmits packets to delete unnecessarily duplicated messages. The rest of the article is organized as follows. First, section II reviews related works. Section III shows the assumed environment. Section IV explains the proposed method, which is evaluated by computer simulations in section V. Finally, section VI concludes the paper.

2. Related Work

The epidemic routing method [1] seems to be effective in cases where the network is unstable such as a mobile sensor network, smart dust, disaster network, etc. In this method, messages are duplicated individually from one node to another and are routed so that they arrive their destinations. As described below, other similar methods include Epidemic [1], Spray and Wait [3], and MaxProp [5].

2.1 Epidemic routing

In the simplest stochastic relay transfer method, which was proposed in the earliest days based on store-carry-forward, message data is sent to some or all nodes in a contact state. When a terminal holding a message waiting to be transferred becomes communicable with another terminal due to its physical movement, a copy of the message is transmitted to the other terminal. In this way, replicated messages are scattered on various terminals with the aim of reaching the destination terminal. This technique is called Epidemic Routing (Figure 1).

figure 1
Figure 1: Epidemic Routing.

Since a terminal with a message to be sent transmits the replicated message to all routes that can reach the destination terminal and the terminal receiving the message also has the right to replicate and resend the message to the neighbors, this method has a high message reachability. However, there is a trade-off between reachability and consumption of resources. In addition, when a message reaches the destination, the replicated messages remain in the network, wastefully consuming the buffer memory of the terminals. Because the terminals do not know whether a message has reached its destination, they continue to distribute the message in the network. Consequently, a relay transfer method should use a recovery method (Recovery Scheme) that erases unnecessary messages from the network.

2.2 Spray and Wait

Spray and Wait [3] is a method proposed by Spyropoulos et al. in 2005. This method aims to improve the efficiency in the use of contact bandwidth and storage capacity by limiting the number of replicas that can be created per message (Figure 2).

figure 2
Figure 2: Spray and Wait.

Spray and Wait has two stages. The first is the Spray phase, where each node replicates and gives its holding message to another encountered node. The number of replicas per a message, which controls the spread in the network, is limited to N. Once the total number of replicas reaches N, this phase ends and the Wait phase begins. In the Wait phase, each node holding a message gives the message only when it encounters the message destination. The Binary Spray and Wait [4] is one type of Spray and Wait. Figure 2 illustrates a Binary Spray and Wait where original node A has N =16 as the number of replicas to be spread. When node A encounters B, A gives the replica to B and splits N in half with B. Then, N of A is reduced by half (8), while B receives the message and 1/2N (8). Similarly, when A encounters C, D, and E, it replicates the message and splits N in half each time. Consequently, each transfer reduces N by half. All nodes continue this process until N = 1. Then all nodes move into the Wait Phase. Overall, the message is spread to just N nodes.

2.3 MaxProp

MaxProp Figure 3 depicts MaxProp [4], which was proposed by Burgess et al. in 2006. Instead of selecting the transfer destination, MaxProp aims to improve the reachability of a message to its destination by selecting whether to transfer or discard a message. In MaxProp, each node prioritizes its holding messages, and messages with a lower priority are discarded when the storage capacity is insufficient. When a node comes into contact with another one, it replicates and gives the message with the highest priority to the encountered node.

figure 3
Figure 3: MaxProp strategy.

Priority is determined as follows. In this method, the number of times each message has been replicated so far, (i.e., h) is memorized. All the messages are divided into two groups: those where h is smaller than the threshold th (high rank group) and all others (low rank group). Each message in the high rank group with a smaller h is given priority so that messages with a smaller h have a higher priority. On the other hand, each message in the low rank group with a larger h is prioritized by communication cost. Messages in the low rank group with a smaller communication cost to the destination are given a higher priority. Note that all priority values for low rank group are less than any of those in the high rank group messages. The threshold th is determined by the node's average bandwidth of past communications with others and its currently used storage capacity.

2.4 ProPHET

This method was proposed by Lindgren et al. [6]. In ProPHET, each node sends the message with highest reachability preferentially to its destination among all the messages kept in its buffer. During every encounter, the reachability values are exchanged. The reachability values of a node without a chance to encounter other nodes are reduced according to the elapsed time from the last reachability exchange.

In this method, there are some variations in how messages are selected and sent to their destination nodes. In addition, a routing that combines ProPHET and Epidemic is proposed in [7]. Further improvements are expected.

2.5 Vaccine method

In Epidemic routing [1], the number of replications increases unintentionally. Although this can minimize delivery delays, this consumes the node buffers in the network. Because each buffer has a limited capacity, buffer overflow occurs, reducing the transmission success rate. To solve this problem, the Vaccine recovery method was proposed to suppress the numbers of replications in Epidemic Routing by issuing anti-packets [2].

In the conventional Vaccine recovery method, when the destination node receives a message, the node sends an antipacket, which includes the same ID with the message, via flooding. Nodes receiving the anti-packet remove messages with the same ID from their buffers. Moreover, the antipackets are kept in their buffers, and if the message is received again, it is removed. Because wasted messages are removed, the reachability of each message to be delivered to its destination should improve. The close relationship between MaxProp and the Vaccine recovery method is mentioned in [2].

figure 4
Figure 4: Vaccine Method.

Figure 5 shows the formats of a normal message and an anti-packet. The normal message includes the Message ID, Sender ID, Destination ID, Message issue time, and data to be sent. The anti-packet is generated by removing the data part from the normal message. Compared to a normal message, an anti-packet is very small in size.

figure 5
Figure 5: Clipping of OFDM signals.

Socievole et al. evaluated the routing performances of Epidemic, MaxProp, etc. as well as routing using both the Epidemic and Vaccine recovery methods [2]. Depending on the frequency of message issuance, there are cases where the Vaccine recovery method is insufficient.

3. Assumed Environment

In this research, we assume the following network environment:

  • Many users can communicate directly each other via mobile terminals such as smartphones.
  • Users can walk freely within a certain area with the terminal.
  • Each user has the right to forward the received and replicated messages, and if the two users enter into a mutual communication range, they can exchange messages.
  • Any user in the area can send and receive messages with other arbitrary users.
  • Each user terminal has a finite buffer size.

Based on the above assumptions, we strive to realize a method to maximize the arrival rate of messages while minimizing the average waiting time from the beginning of sending a message to its arrival at the destination.

4. Proposed Method

In the Vaccine method, unnecessarily replicated messages accumulated in the buffers of the users’ terminals are eliminated by via anti-packets. However, anti-packets cannot be issued until one of the replicated messages arrives at the destination. Due to the diffusion of excessive messages, the buffer capacity of each user terminal is squeezed.

In this research, we give each message information about how many terminals the message has passed through so far. This allows the proliferation of the messages to be determined, improving the timing of anti-packet's issue. A sufficient number of replicated messages can be deleted from inside of the network. In this paper, the proposed method is called “anti-packet prime,” and an anti-packet issued in this method is also called an anti-packet as is the case with the conventional Vaccine recovery method. The behavior of this method is illustrated as follows.

4.1 Message sending with anti-packet prime (Source node)

The operation algorithm of the message sending terminal of this method is shown below, and Figure 6 illustrates its flowchart.

figure 6
Figure 6: Flow chart of message sending operation.

  1. Send the message. At the onset, the message’s NPT (the number of Nodes the message Passed Through) is 0.
  2. Wait until the terminal receives the same message that it issued.
  3. If the number of NPT is less than the threshold, go to step 4. Otherwise, go to step 5.
  4. Discard the received message, and return to step 2.
  5. Start issuing anti-packet and discard the received message.
  6. End the operation of message sending.

4.2 Operation of message transmission (All nodes except the original source)

In addition to the above message sending operation, each terminal except source repeats the following procedure as part of normal operations for message transmission. Figure 7 shows the flowchart.

figure 7
Figure 7: Flow chart of message receiving operation.
(common in all terminals).

  1. Continue moving with the terminal holder.
  2. Once another terminal has entered into the terminal’s communication range, exchange messages according to the FIFO principle as long as they remain within the range.
  3. When a terminal’s buffer overflows, delete the oldest messages in order, and store the new messages in the buffer.
  4. If the terminal receives a message whose destination is this terminal, give the message to the user, remove the message from the buffer, and issue an anti-packet to eliminate the message from the whole network.
  5. Increment the newly reached messages’ number of NPT by 1.
  6. If the terminal receives a message whose message ID matches the ID of an anti-packet, discard the message.
  7. If the terminal receives an anti-packet whose message ID matches the ID of a message kept in the buffer, discard the message.
  8. If the terminal receives anti-packets but the IDs do not match, keep the anti-packets prime in the buffer.
  9. Return to step 1.

Figure 8 shows the configuration of the anti-packets. In the format of anti-packet prime, the NPT information is added.

figure 8
Figure 8: Anti-packet & Proposed Format.

5. Evaluation

A computer software simulation, The ONE [8], was used to verify the effectiveness of the proposed method. Table 1 depicts the simulation conditions and parameters. The Default-map (Helsinki regional schematic drawing) originally included in this simulator and the Narashino-map (map of Narashino city) extracted from OpenStreetMap [9], shown in Figure 9, are used as the stages of the simulation. In this simulation, users send and receive messages while going in between two randomly determined points. Epidemic Routing (Epidemic), Epidemic routing including the Vaccine method (Vaccine), and the proposed method (Proposed) are executed on these two maps. In all methods, the destinations and the nodes issuing the messages are randomly selected.

table 1
Table 1: Simulation Parameters.
figure 9
Figure 9: Two maps used in the simulation.

Proposed issues an anti-packet once a transmitted message returns to the source terminal after passing through a certain number of nodes. The threshold is set to the average number of hops until a message arrives at its destination during simulations of the conventional method (Table 2). There are several ways to determine this threshold. This time, the values shown above are used as the predicted value of the timing when the message reaches the destination node, in order to start the deletion of the wasted messages from the source side too, at the same timing of that from the destination side. It is a future work how to dynamically give the threshold which adapted to the situation.

table 2
Table 2: Average number of hops 500 nodes.

The simulation results are shown in Figure 10 through 17. Figure 10 and figure 11 show the message arrival rates according to changing TTL value in the cases of using Default map and Narashino map, respectively. The proposed method achieves the highest message arrival rates regardless of used maps. In the case of using Default map, Proposed and Vaccine keep almost the constant message arrival rates, however in the case of using Narashino map, those two methods increase the rates gradually according to the increment of TTL until 540. Furthermore, we can see that the rates achieved in the case of using Default map is higher than those of using Narashino map. These results are caused by the following reasons. Narashino map covers larger area than Default map, so the frequency to encounter the other nodes while using Narashino map is smaller than that while using Default map. Therefore, message diffusion speed using Narashino map is much slower than using Default map.

figure 10
Figure 10: Message Arrival Success Rate. (Default_map).
figure 11
Figure 11: Message Arrival Success Rate. (Narashino_map).

Figure 12 and figure 13 illustrate the average latency of message transmissions. The average latency is derived only from the messages successfully reached their destinations. The reason why the latency of Epidemic decreases from 480 of TTL in figure 12 is that message arrival rate of the method keeps decreasing as shown in figure 10. Also, the reason why Epidemic with the smallest message arrival rate achieves the fastest transmissions in the case of using Narashino map shown in figure 13 is the same, i.e., very few messages reach their destinations. Totally, we can say that the proposed method achieves the highest message arrival rate among the three methods, and smaller message delivery latency than Vaccine method.

figure 12
Figure 12: Average Transmission Latency. (Default_map).
figure 13
Figure 13: Average Transmission Latency. (Narashino_map).

Next, we compare Proposed and Vaccine from the viewpoint of the number of messages that do not reach their destination. Henceforth, the number of the messages that anti-packets remove, the number of the messages disappearing due buffer overflows or TTL expirations, and the total number of all the lost messages are referred to be as the numbers of removals, disappearances, and total losses, respectively.

Figures 14 and 15 show the three numbers for lost messages in the case using the Default map. According to the TTL increment, both methods have a similar number of total losses. This is because the small area of the Default map limits the number of times that a message is exchanged. On the other hand, the number of removals of Proposed is larger than that of Vaccine. This is because the anti-packet is sent to remove wasted messages not only from the destinations but also from the sources in proposed method.

figure 14
Figure 14: Number of Deleted Massage in Default_map. (Vaccine).
figure 15
Figure 15: Number of deleted massages in Default_map. (Proposed).

Figures 16 and 17 show the results of the numbers of lost messages in the case using the Narashino map. Although both methods have a similar number of total losses in the Narashino map, Proposed increases the number of removals and reduces the number of disappearances compared to Vaccine. Hence, Proposed realizes more efficient communications than Vaccine, improving the message arrival rates and transmission latencies.

figure 16
Figure 16: Number of deleted massages in Narashino_map. (Vaccine).
figure 17
Figure 17: Number of deleted massages in Narashino_map. (Proposed).

Table 3 shows the average number of anti-packet issued in the cases of using Vaccine and Proposed. Actually, Proposed issues more anti-packets compared to Vaccine and there exists some additional overhead if Proposed is used instead of Vaccine. However, since the capacity of each anti- packet itself is very small in the first place, and the impact on the network traffic due to the increase in the number of issues is limited.

table 3
Table 3: Average number of Issued Anti-packets.

6. Conclusion

In this research, we propose a method to efficiently transmit messages using short-range communications between terminals under the condition where the mobile terminals’ network via a base station is unusable. We shortened the average waiting time while improving the message arrival rate compared with the conventional methods. In the future, we need to add a function to automatically judge the appropriate timing to issue an antipacket according to the conditions.

Competing Interests

The authors declare that they have no competing interests.


References

  1. Vahdat A, Becker D (2005) Epidemic Routing for Parti6ally Connected Ad Hoc Networks. Duke Tech 62: 210-228. View
  2. Socievole A, Rango FD, Coscarella C (2011) “Routing Approaches and Performance Evaluation in Delay Tolerant Networks”, Telecommunications Symposium (WTS), New York City, NY, 2011, pp. 1-6. View
  3. Spyropoulos T, Psounis K, Raghavendra CS (2005) “Spray and wait: an efficient routing scheme for intermittently connected mobile networks”, In Proceedings of the 2005 ACM SIGCOMM workshop on Delay-tolerant networking, ACM, pp 252- 259.
  4. Maitreyi P, Rao MS (2017) “Design of Binary Spray and wait protocol for intermittently connected mobile networks.” In 2017 IEEE 7th Annual Computing and Communication Workshop and Conference (CCWC), Las Vegas, NV, pp. 1-3. View
  5. Burgess J, Gallagher B, Jensen D, Levine BN (2006) “MaxProp: Routing for Vehicle-Based Disruption- Tolerant Networks”, Proceedings IEEE INFOCOM 2006. 25TH IEEE International Conference on Computer Communications, Barcelona, pp. 1-11. View
  6. Lindgren A, Doria A, Schelen O (2004) Probabilistic Routing in Intermittently Connected Networks. In: Dini P., Lorenz P., de Souza J.N. (eds) Service Assurance with Partial and Intermittent Resources. SAPIR 2004. Lecture Notes in Computer Science, vol 3126. Springer, Berlin, Heidelberg. View
  7. Ariwibisono FX, Basuki A, Ramdani F () Hybrid PRoPHET-Epidemic Routing Protocol for Optimizing Possibility of Sending Messages in Remote Fishermen Residential Area" Journal of Telecommunication, Electronic and Computer Engineering 10: 31-36. View
  8. Keranen A (2008) “Opportunistic Network Environment simulator”, Special Assignment Report, Helsinki University of Technology Department of Communications and Networking. View
  9. OpenStreetMap Foundation(OSMF), OpenStreetMap. View
  10. MapBasedMovement. View