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).
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).
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.
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 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.
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.
- Send the message. At the onset, the message’s NPT (the number of Nodes the message Passed Through) is 0.
- Wait until the terminal receives the same message that it issued.
- If the number of NPT is less than the threshold, go to step 4. Otherwise, go to step 5.
- Discard the received message, and return to step 2.
- Start issuing anti-packet and discard the received message.
- 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.
- Continue moving with the terminal holder.
- 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.
- When a terminal’s buffer overflows, delete the oldest messages in order, and store the new messages in the buffer.
- 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.
- Increment the newly reached messages’ number of NPT by 1.
- If the terminal receives a message whose message ID matches the ID of an anti-packet, discard the message.
- If the terminal receives an anti-packet whose message ID matches the ID of a message kept in the buffer, discard the message.
- If the terminal receives anti-packets but the IDs do not match, keep the anti-packets prime in the buffer.
- 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.
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.
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.
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 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.
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.
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.
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.
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.