Characteristics comparison of DTN networks routing protocols using hybrid model of nodes’ mobility A.A. Tsarev1, A.Yu. Privalov1 1 Samara National Research University, 34 Moskovskoe Shosse, 443086, Samara, Russia Abstract 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. Keywords: delay tolerant network; routing protocols; human’s mobility model; simulation modeling; OMNeT++ 1. Introduction 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. 2. Short description of the hybrid mobility model The detailed description of the hybrid model is given in [9, 14], so here we will only briefly describe its main features and some details which were not considered previously so much. Movements of one single node (i.e., a person) are considered as straight-line movements between waypoints, where nodes stop at a random time. Lengths of these displacements and pause times are random variables, with distributions close to the Levy distributions. Moreover, waypoints are grouped into clusters, also called hot spots, because they actually correspond to places (we will call them locations) where people spend considerable time during their daily activities (for example, buildings, where they work). In this case, to take into account the routes’ persistence, the coefficient of persistence is introduced, which is equal to the fraction of locations that are stored in the routes of one node in different days. Since the modeling of mobility in a period of several days in previous works was considered small, here we will consider it in more detail. For better adequacy of the hybrid model, both the locations and durations of the daily nodes’ routes are taken from the real data from [13]. In particular, we used the traces dataset from the territory of KAIST. It contains data of the one-day travel of several dozen students across the campus of the Korea Advanced Institute of Science and Technology. In the records of real routes, the movements take an average of 12 hours. The minimum route takes 4.2 hours and the maximum route – 23.3 hours. Because of durations of the routes are different, the model allows the forced end of the route, which happens after a predetermined constant time interval – a model day. The duration of model day d can be changed, depending on the nature of movements in a particular area. This article presents the simulation results with duration of the model day equal to the average route’s duration of all nodes from real traces. Due to the fact that different routes take different time, each user who finishes his route (including compulsory endings), returns to the home location – the location from which the movement is started. If the user's route is longer than the model day, 3rd International conference “Information Technology and Nanotechnology 2017” 187 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 [9, 14] with the parameters c and α. To change pause times, the scaling parameter c was chosen to minimize the mean square deviation of the route durations for the first day of real traces from the route durations of the first day for simulated traces. 3. Routing protocols 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, [10]):  The Last Encountered Time (LET) protocol;  More Frequently Visible (MFV) protocol;  proposed LET-MFV protocol with switching threshold (hybrid protocol);  PROPHET protocol [15]. 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” [15]. 4. Experimental results Hybrid model was implemented in the OMNeT ++ simulation environment [11] using the INET framework [12] (more detailed in [9, 14]) to compare simulation results of routing protocols. The purpose of the experiments is to research the 3rd International conference “Information Technology and Nanotechnology 2017” 188 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 [13]. All traces were collected in the same way: a number of volunteers (university students) wore GPS receivers in their pocket during the day and these receivers record their position every 30 seconds. These data were used to find real waypoints, waypoint clusters and other parameters for the hybrid model. 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 [9, 14]. The radius of the transmitters of nodes is 100 meters. Fig. 1. Comparison of distributions 𝐶𝐶𝐷𝐹(𝑇𝑇𝐿) Fig. 2. Comparison of distributions 𝐶𝐶𝐷𝐹(𝑇𝑇𝐿) for 𝑁 = 12 and 𝑝 = 0.5. for 𝑁 = 23 and 𝑝 = 0.5. Fig. 3. Comparison of distributions 𝐶𝐶𝐷𝐹(𝑇𝑇𝐿) Fig. 4. Comparison of distributions 𝐶𝐶𝐷𝐹(𝑇𝑇𝐿) for 𝑁 = 46 and 𝑝 = 0.5. for 𝑁 = 12 and 𝑝 = 0.9. Fig. 5. Comparison of distributions 𝐶𝐶𝐷𝐹(𝑇𝑇𝐿) Fig. 6. Comparison of distributions 𝐶𝐶𝐷𝐹(𝑇𝑇𝐿) for 𝑁 = 23 and 𝑝 = 0.9. for 𝑁 = 46 and 𝑝 = 0.9. 3rd International conference “Information Technology and Nanotechnology 2017” 189 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. ̅̅̅̅̅ (measured in simulation seconds). Table 1. Estimation of average time-to-live 𝑇𝑇𝐿 Count of 𝑝 = 0.5 𝑝 = 0.9 nodes (N) LET MFV LET-MFV PROPHET LET MFV LET-MFV PROPHET 46 52060.2 49784.8 49575.9 56642.8 45952.1 43695.7 43022.3 43560.5 23 52522.1 50324.6 50176.4 55306.7 43013.1 35147.3 34871.2 37608.1 12 63177.9 63177.9 62928.5 80434.9 45022.8 42577.7 42405.2 46661.0 Table 2. Probability estimation of delivery of packets 𝑃𝑟(𝑑𝑒𝑙𝑖𝑣𝑒𝑟𝑦). Count of 𝑝 = 0.5 𝑝 = 0.9 nodes (N) LET MFV LET-MFV PROPHET LET MFV LET-MFV PROPHET 46 0.6786 0.6939 0.6938 0.6695 0.7945 0.8006 0.8026 0.7742 23 0.6390 0.7375 0.7361 0.6963 0.8072 0.7909 0.7923 0.7575 12 0.6951 0.6951 0.6935 0.8023 0.7387 0.7009 0.7011 0.7077 5. Conclusion 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 [15] without deep optimization. So, investigation of applicability of our hybrid mobility model and more deep comparison of considered routing algorithms is the direction of our further research. References [1] Brockmann D, Hufnagel L, Geisel T. The scaling laws of human travelю Nature 2006; 439: 462–465. [2] Gonzalez MC, Hidalgo CA, Barabasi AL. Understanding individual human mobility patterns. Nature 2008; 453: 779–782. [3] Rhee I, Shin M, Hong S, Lee K, Chong S. On the Levy walk nature of human mobility. Proc. IEEE INFOCOM, Phoenix, AZ 2008; 924–932. [4] Rhee I, Shin M, Hong S, Lee K, Kim SJ, Chong S. On the Levy-walk nature of human mobility. IEEE/ACM Trans. on Networking 2011; 19(3): 630–643. [5] Lim S, Yu C, Das CR. Clustered mobility model for scale-free wireless networks. Proc. IEEE LCN Tampa, FL 2006; 231–238. [6] Ghosh J, Philip SJ, Qiao C. Sociological orbit aware location approximation and routing (solar) in MANET. Ad hoc Netw. 2007; 5: 189–209. [7] Lee K, Hong S, Kim SJ, Rhee I, Chong S. SLAW: Self-Similar Least-Action Human Walk. IEEE/ACM Trans. on Networking 2012; 20(2): 515–529. [8] Lee K, Hong S, Kim SJ, Rhee I, Chong S. Demystifying Levy Walk Patterns in Human Walks. Technical Report in CSC, NCSU 2008. URL: https://www.csc.ncsu.edu/research/tech/reports.php/Demystifying_Levy_Walk_Patterns.pdf (28.01.2017). [9] Privalov AYu, Tsarev AA. Hybrid Model of Human Mobility for DTN Network Simulation. Proceedings of 30th European Conference on Modelling and Simulation (ECMS2016). Regensburg university of applied sciences, Regensburg, Germany 2016; 419–424. [10] Dubois-Ferriere H, Grossglauser M, Vetterli M. Age matters: Efficient route discovery in mobile ad hoc networks using encounter ages. Proc. ACM MobiHoc, Annapolis, MD 2003; 257–266. [11] Varga A. The OMNeT++ discrete event simulation system. Proceedings of the European simulation multiconference 2001; 9(185.sn). [12] Till S, Kenfack HD, Korf F, Schmidt ThC. An extension of the OMNeT++ INET framework for simulating real-time ethernet with high accuracy. Proceedings of the 4th International ICST Conference on Simulation Tools and Techniques, ICST. Brussel, Belgium 2011; 375–382. [13] Kotz D. Community Resource for Archiving Wireless Data at Dartmouth. Dartmouth College 2015. URL: http://www.crawdad.org/index.html (28.01.2017). [14] Tsarev AA, Privalov AYu. Hybrid Model of Human Mobility for DTN Network Simulation in Comparison with SLAW-type Model. Proceedings of 10th International Symposium on Communication Systems, Networks and Digital Signal Processing (CSNDSP16). Czech Republic 2016. URL: http://www.csndsp16.com/csndsp16.zip (28.01.2017). [15] Lindgren A, Doria A, Davies E, Grasic S. Probabilistic Routing Protocol for Intermittently Connected Networks 2012. URL: https://tools.ietf.org/html/rfc6693 (28.01.2017). 3rd International conference “Information Technology and Nanotechnology 2017” 190