The results of simulation of popular routing protocols in DTN wireless networks with the hybrid mobility model of DTN's nodes are presented. The purpose was to evaluate the message delivery probability and the average time of message delivery. The simulation model is implemented in the OMNeT ++ simulation system. From the simulation experiments it has been found that the daily periodic repeatability of node's movements has a sufficient influence on the performance of routing protocols with different principles of route determination. Due to the great complexity of modeling of mobile wireless networks in general, and so-called delay-tolerated networks (DTNs) in particular, computer simulation plays a leading role in the study of such networks, including the characteristics of routing protocols. It is obvious that the mobility model used in simulation of such networks has a very strong effect on the considered protocol characteristics. Therefore the mobility model should reflect the features of network nodes real mobility as closely as possible. As a results of human's mobility researches, which attracted much attention of the scientific community in the last decade, a number of important features were revealed. These features are: the clustering of waypoints in real mobility traces, the Levy distribution of the distances between waypoints, and the so-called persistence (i.e. approximate constancy) of the daily routes of one user, if the system is considered for several days (see, for example, [1-4]). These features must be captured by an adequate model. In [9, 14] wet proposed the hybrid model of human mobility that combines all the important features of human mobility listed above. Our models are based on the models proposed in [7, 8], but more effective in the simulation. Also in the model presented in this report, the persistence of individual routes was more consistently captured by introducing a special characteristic - the coefficient of persistence. In this report we present the results of implementation of our mobility model in the OMNET ++ simulation system. The characteristics of some popular routing protocols of DTN networks are investigated, namely, the LET (Last Encounter Time) protocol, the MFV (Most Frequent Visible) protocol, and the PROPHET (Probabilistic Routing Protocol using History of Encounters and Transitivity) protocol [15]. For these protocols, the message delivery probability Pr (delivery) and the average message delivery time (̅̅̅̅̅) for various network scenarios are evaluated and compared to find the most effective protocol for considered scenarios.
Mathematical Modeling / A.A. Tsarev, A.Yu. Privalov then at the end of the model day the user should go home. After returning to the home location the user “falls asleep” until the next model day, i.e. ceases to be the source of messages on the network.
Before the start of a new day, routes are changed according to the coefficient of persistence p – which means the proportion of replaceable visited locations in the entire route. The coefficient p was introduced to allow the route to be changed day by day for the purpose of simulation the changes in daily route in reality.
Each location in a real route can be visited several times by the user. The number of such possible visits is called the multiplicity of the location. While forming a new route, all visits from all locations are summed up and part of the total sum is excluded from new route (this part is determined by the coefficient of persistence p). Further, the number of waypoints in the excluded locations is counted to be added later. After deleting visits, some locations are added randomly in the route from a set of all locations, except remaining in the route after the deletion. Adding locations can be repeated to reproduce the multiplicity of locations. Waypoints in new locations are added based on the previously calculated sum of excluded waypoints, in order to save the total number of waypoints in the new route the same as before the change. This logic of generating a new route is designed to ensuring that new route’s duration is close to the duration of the previous route.
However, in addition to fitting new generated routes to previous routes (or to the first one), the first model route should be
fitted to the real route by duration. For this purpose, the parameters of the pause time generator are used. The durations of the
pauses between have Levy distribution [
To describe the routing protocols discussed in this report, we introduce several definitions. Direct neighbors or simply neighbors are those nodes that have an active network connection with the current node at a given time (i.e., in the range of the communication device). The process of packet routing is that it is necessary to determine which of the neighbors at the given time is the most profitable to transfer this packet, so that it subsequently reaches the target node with the greatest probability if there is no direct connection with the target node at the given time.
First of all, all DTN protocols use packet transfer logic in one hop – if node i has a packet addressed to node j, then check the direct connection to node j and the packet is transmitted to it if there is a connection. If there is no target node in the number of neighbors, but there is a neighbor who is also a neighbor for the target node, then the packet is sent to this neighbor (if there are several of them, then any of them). This is a two-hop packet transmission logic, which is also always used.
If simple logics cannot find the target node or a suitable transit node, then one of the protocols starts (for example, [
The LET protocol sends a packet from node i to that neighbor, who later than another “saw” the target node j (i.e., had an active network connection with this node). Comparison is made also with the current node i. If there are several such nodes, then the packet is sent to the random one. If none of the neighbors have “seen” the target node, then the packet is not being transferred to anyone. In general, during the routing process, the packet "strives to catch up" with its target node.
The MFV protocol works by using the history of the frequency of meeting nodes with each other. The packet is sent from node i, to that transit node k, which more often sees the target node j. The measure of the meeting frequency between nodes is defined as the ratio of the total duration of the network connection between two nodes to the entire simulation time. The total duration is calculated by the width of the sliding “window” in simulation days. The width of this sliding “window” (in model days) is a parameter of the model.
For the availability of the MFV protocol, firstly we have to collect a story about the frequency of meetings between nodes. For this purpose, the model has the download phase, during which the collection of statistics is disabled. The duration of this phase is equal to the width of the sliding “window”, i.e. as soon as the required number of days has passed, equal to the width of the window, statistics collection begins.
The hybrid protocol based on LET and MFV (LET-MFV) protocols is implemented. It uses LET only up to a certain time threshold, after which the MFV protocol starts to work. First the LET protocol tries to find a solution about the best transit node. If all neighbors for the current node “saw” the target node later than the threshold, then the protocol switches to the MFV part. Such logic should make the routing situation more optimistic, because of it simulates the accounting for obsolescence of information about when the nodes “saw” each other. After the threshold has been reached the MFV protocol based on the collected statistics about the frequency of meetings starts to work.
Finally, a simplified version of the PROPHET protocol is implemented. Instead of doing unassembled replication of packets
on network nodes during the distribution of packets, as simple protocols based on replication do, PROPHET implements
“probabilistic routing” [
Hybrid model was implemented in the OMNeT ++ simulation environment [
Mathematical Modeling / A.A. Tsarev, A.Yu. Privalov behavior of the LET, MFV, LET-MFV, and PROPHET protocols depending on the number of nodes N and the coefficient of persistence p of traces. Research provided by comparing the target characteristics of the routing protocols: the PDF of packet’s delivery delay or time of live of packet ( ) and probability of delivery ( ).
This report uses the traces dataset from the territory of KAIST from collection [
For the MFV part of hybrid protocol: the width of the “window” during which the information about the meetings is collected
is equal to 5 model days. The duration of the threshold is also equal to 5 model days. As mentioned above, this threshold is
required to “load” the information about the meetings before the MFV part starts to work. The parameters of the generator of
pause times are = 18 and = 0.5. The parameters of the generator for movements’ length are the same as in works [
Fig. 1. Comparison of distributions for = 12 and = 0.5.
( ) ).
Mathematical Modeling / A.A. Tsarev, A.Yu. Privalov
The experiments were made with a coefficient of persistence = 0.5 and = 0.9. The number of nodes is varied in the experiments: 12, 23, and 46. The duration of model day was equal to 12 model hours – this value based on a selective average of the durations of all real routes from the given territory. In figures 1, 2, and 3 the ( ) functions for packet’s PDF of time to live for a different number of nodes with a coefficient of persistence = 0.5 are shown. In figures 4, 5 and 6 ( ) functions for a different number of nodes with a coefficient of persistence = 0.9 are shown. The estimations of the average packets’ time to live ̅̅̅̅̅ are presented in Table 1. The estimated probabilities of packets’ delivery ( ) for all runs of models are shown in Table 2.
The results of simulating of popular routing protocols in DTN networks with a hybrid mobility model of nodes are presented. The message delivery probability and average time-to-live of message was evaluated. As a result of the experiments, it was found that with a small average density of nodes and with an average persistence coefficient, the MFV protocol surpass the other protocols in case of the probability of message delivery. With a large density of nodes and a large coefficient of route persistence, the LET protocol has the advantage in the probability of message delivery, however the best protocol in case of the average delivery time for all considered parameters of nodes’ mobility is the protocol LET-MFV.
PROPHET protocol has worse characteristics than others, but it is necessary to note that our implementation of this protocol
was simplified (for example, without implementation of replication of packets) and we used the recommended parameters in
[