Abstract— In opportunistic environments data forwarding is challenging where connectivity is intermittent because of network partitioning, dynamic topologies and long delays. Traditional Delay Tolerant Network (DTN) routing protocols exploit “Store-Carry-and-Forward” strategy in such cases. But the difficulty of this approach is how to select the best relay node and determine the best time to transmit messages in dense and urban areas. To route data in such dynamic, heterogeneous networks social-based routing is an emerging technique that concerns social behaviors and interactions of nodes.
In this paper, we have investigated the performances of conventional DTN routing protocols, namely Epidemic, Spray and Wait (SNW) and PRoPHET with two social-aware routing protocols: SCORP and dLife by simulating in Opportunistic Network Environment (ONE) simulator on basis of three parameters namely delivery probability, average latency and overhead ratio with necessary simulation settings. The performances are evaluated by varying node density and message Time-To-Live (TTL). From the outcomes of this experiment, it is clear that dLife is best for delivery probability and worst for average latency.
On the other hand, SNW has best performance for average latency, Epidemic shows lowest performance for both delivery probability and overhead ratio, where SCORP as well as SNW show best performances for overhead ratio.Keywords— Spray and Wait (SNW); PRoPHET; SCORP; dLife Introduction Delay Tolerant Network (DTN) provides an alternative structure of traditional network. DTN architectures are generally used for challenging environments where routing protocols are designed for Mobile Ad hoc NETworks (MANETs), cannot perform effectively as these environments enduring from lack of connectivity, sparse network densities, long and variable delays, limited device capabilities and high bit error rate of the channels.
Conventional routing algorithms like Ad hoc On-Demand Distance Vector (AODV) or Dynamic Source Routing (DSR) require continuous end-to-end connectivity between source and destination end. So, in such challenging environments, they cannot be implemented to route data accurately. This situation can be overcome by exploiting intermittent connectivity through DTN 1 2. In DTN, intermittent connectivity is provided by node’s mobility. DTN represents a class of network where the existence of well-defined path is not considered. However, at the same time source and destination node may have temporal or no connection through the network. This type of network has scattering node density.
The communication capabilities are for short time of each node. Due to the node’s mobility, one hop energy conservation connections are disrupted 3. Most of the DTN routing protocols utilize “Store-Carry-and-Forward” approach for forwarding where data is transmitted to the next node from source node while connectivity is available, if connectivity is not available data is stored by source and not be neglected. Source node carries the data until it has the connectivity with the next available node and finally delivers to that node.
So, source node should choose relay node among the encountered nodes of it to take forwarding decisions in accordance with a specific routing protocol. Several routing protocols are designed for DTN environment depending on what kind of information is gathered by nodes and how they take routing decisions 4 5. Today, a multitude of energy-constraint mobile devices are carried and used by people. So, to keep pace with the requirement of high speed data transmission of user’s, connectivity is required while on the go.
Mobility is characterized by unpredictability, so, the networking scenario has turned into heterogeneous in nature and the change of topology is rapid. In this case, some characteristics of the network can be considered which are less volatile than mobility. People form the network and people’s social relationships may vary much slower than topology. This idea can be used for better forwarding decisions. Social-aware routing protocols try to detect these social mobility patterns and best suited for this situation 6 7 8.
Moreover, in a social-aware network, nodes are interacted in a diverse manner so that some nodes meet each other more frequently. Social relations and behaviors among the users are generally long-term characteristics and less volatile than node’s mobility. So, social-based routing protocols use various social characteristics to improve routing performance in DTN environment 4 6 9. In this paper, we investigated the performances between conventional DTN routing protocols and social-aware routing protocols in opportunistic environment and focused on routing protocols such as: Epidemic, PRoPHET, Spray and Wait (SNW), SCORP and dLife. The rest of the paper is organized as: Section II explains DTN routing protocols and social-aware routing protocols under investigation. Section III describes necessary simulation tool and environment, Section IV provides a comparative discussion of results and finally Section V provides the conclusions about this research.
Routing Protocols Under Investigation This section provides a brief overview of three traditional DTN routing protocols: Epidemic, Spray and Wait (SNW), PRoPHET and two social-aware routing protocols: SCORP and dLife with their summarized data routing mechanisms. Epidemic routing protocol is a flooding based routing algorithm for DTNs. In Epidemic, the node which receives a message, continuously replicates it and transmits the copies to newly discovered nodes that do not already have received a copy of the message. Thus, the message spreads the network by nodes in order to ensure that the destination is reached by the message 10 5. This protocol provides the message transmissions ensuring its delivery without regarding latency, storage space etc.
So, it is assumed that network resources e.g. bandwidth etc. are sufficient by Epidemic and it consumes a lot of network resources. It continues message propagation through the network even after message being delivered. That’s why message congestion can be occurred in the network 5.
Spray and Wait (SNW) protocol overcomes the situation of blind flooding from Epidemic. Its main difference from Epidemic is that it controls the level of spreading of messages through the network. It only spreads L copies of the message, where L indicates the maximum allowable copies of the message and this parameter is selected based on network density and desired average time. Spray and Wait consists two phases 5 3: Spray Phase: In this phase, the source node forwarding L copies of message to the first L encountered nodes, known as L distinct relays.Wait Phase: If the destination is not found in above phase, all nodes (each of L nodes) that received a copy of message are waited to meet the destination node in order to directly deliver the data. PRoPHET (Probabilistic Routing Protocol using History of Encounters and Transitivity) routing protocol assures the use of the resource properly. It conserves a set of probabilities in order to successful delivery of message to the destinations that are known.
PRoPHET utilizes real-world encounter’s likelihood and eliminates replications. When two nodes are encountered, messages are routed to the node in accordance with the higher predictability precedence. That means which node has higher delivery predictability; messages will be forwarded to that node 5 11. SCORP (Social-aware Content-based Opportunistic Routing Protocol) is a social-based routing protocol which focuses on message content rather than host. In addition, node’s social interactions and structure (i.e.
communities), social interaction levels increase the performance of routing in opportunistic environment. Content knowledge may be content type, interested parties etc. It implies the combined form of social proximity and content knowledge in challenging environments to take forwarding decisions 8.
In SCORP, when source node is encountered with another node, message will be forwarded from source node if that node has the same content interest of message carried by source or, that node has strong relationship to the source node 8. dLife is another social-aware routing protocol which considers the dynamism of user’s behavior based on their daily life. It takes advantage of time-evolving social structures in an opportunistic environment. In dLife protocol, if encountered node has better relationship with destination than the source node, a copy of message is received by it from source because in future it has much greater probability to meet the destination. But if its relationship to destination is unknown, then source node forwards the message in accordance with the node’s importance. So, nodes having higher importance will get the message from source 8 12.Simulation Tool And Environment In this paper, Opportunistic Network Environment (ONE) simulator is used as a simulation tool to simulate Epidemic, Spray and Wait (SNW), PRoPHET, SCORP and dLife. ONE simulator is written in Java.
It uses different movement models, supports new maps and visualizes mobility, message passing in its graphical user interface. It also provides a report for relevant simulated protocols 13. TABLE I. Parameters For Simulation SetupParametersValuesSimulation Time4 daysUpdate interval0.1Number of nodes in Group150, 160, 170, 180, 190, 200, 210InterfaceBluetoothInterface TypeSimple Broadcast InterfaceTransmit Speed250 kbpsTransmit Range10mRouting ProtocolsEpidemic, Spray and Wait, PRoPHET, SCORP, dLifeMessage TTL.
5 day, 1 day, 2 day, 3 day, 4 dayMessage Generation Rate2Buffer Size2 MBMovement ModelShortest Path Map BasedMessage Size500 KB-1 MB Simulation Area Size10,000m×10,000m TABLE II. Parameters For Routing AlgorithmsRouting AlgorithmParametersValuesEpidemicN/AN/ASpray and waitNo. of Copies10PRoPHETSeconds in Time Unit30SCORPGroup RouterDecision Engine RouterdLifeGroup RouterDecision Engine Router Decision Engine Router Familiar Threshold 700Results And EvaluationsIn this section, simulation results that obtained from simulations of investigated routing protocols in ONE simulator by using the parameters defined in Table I and II are evaluated based on three performance metrics: Delivery Probability, Average Latency and Overhead Ratio.Delivery Probability Delivery probability can be defined as the ratio of the total number of messages delivered to the destination over the total number of messages created at the source. This parameter simply reflects the probability of successful data delivery. With the increase of node density, the change of delivery probability is shown in Fig. 1. From that figure, it is realized that social-based routing protocols (dLife, SCORP) have higher delivery ratios as compared to DTN routing protocols (Epidemic, SNW, PRoPHET).
Because in a node’s community, node that has high centrality must delivers its messages in accordance with various relationships. However, dLife obtains best performances among SCORP, SNW, PRoPHET and Epidemic in terms of delivery probability. Fig. 2 displays that for varying message TTL (from .5 day to 4 day), dLife’s delivery probability decreases from the highest possible value 1 and it exhibits highest performance than others. Here, Epidemic and PRoPHET show lowest results.
In both cases, Epidemic provides lowest delivery ratio since it does not imply any strategy to stop its blind replication of messages. Fig. 1. Delivery probability with number of nodes per group.Fig. 2.
Delivery probability with message TTL.Average Latency Average latency can be defined as the measure of average time required between messages generation of source node and successful reception of destination node. For effective network operation it is desired to be low. As shown in Fig. 3, social-based routing protocols (e.g.
dLife) have higher latency than DTN routing protocols with varying number of nodes per group since nodes will deliver messages to their relative node with delay. SNW has significantly lowest latency than others. So, it has much improved performance as compared to others. Fig. 4 shows that average latency of dLife is significantly high than SCORP, Epidemic, PRoPHET, SNW and increases with message TTL where in same case, SNW has lowest latency than others.
So, in both cases, SNW exhibits highest and dLife provides lowest performances.Fig. 3. Average latency with number of nodes per group.Fig. 4. Average latency with message TTL.Overhead Ratio Overhead Ratio is a measure to deliver a single packet, how many redundant packets are relayed.
This parameter reflects the cost of transmission in a network. So, for better performance of a network, this parameter required to be low. From Fig. 5 and Fig. 6, it is observed that with increasing node density and message TTL, Epidemic has highest value of overhead ratio since its curve increases gradually. Because of its resource consumption characteristics due to flooding, it has high transmission cost. So, lowest performance is shown by Epidemic for overhead ratio. On the contrary, SCORP and SNW both achieve lowest overhead ratios than dLife, PRoPHET and Epidemic.
In SCORP, messages are routed based on interests, content types etc. So, fewer messages are deployed for a successful delivery of a message to destination where SNW replicates a minimum number of copies of message. Thus, SCORP and SNW both have best performances in terms of overhead ratio.Fig.
5. Overhead ratio with number of nodes per group.Fig. 6. Overhead ratio with message TTL. Conclusion And Future WorksIn this paper, the performances of socially aware routing protocols (SCORP, dLife) are analyzed with DTN routing protocols (Epidemic, Spray and Wait, PRoPHET) with the impact of node density and message TTL on behalf of delivery probability, average latency and overhead ratio. From the simulation results, social-aware protocols have high delivery ratios than the other DTN routing protocols.
But they have more latency than DTN routing protocols. From this research, it can be concluded that dLife has the highest delivery probability and Epidemic has the lowest delivery probability. So, dLife can be a better solution for routing messages in opportunistic environment if only delivery probability is considered. But, dLife has highest latency where SNW has the lowest latency. Furthermore, SCORP and SNW have low overhead ratios where Epidemic has the highest overhead ratio. Further investigation can be done in future to analyze the performances between social-aware routing protocols and DTN protocols considering changes of buffer size and mobility models. Moreover, an approach can also be investigated to reduce the latency of social-aware routing protocols which may help to design a new practical social-based protocol that would perform more efficiently.
ReferencesY. Cao and Z. Sun, “Routing in Delay/Disruption Tolerant Networks: A Taxonomy, Survey and Challenges,” IEEE Communications Surveys & Tutorials, vol. 15, pp.
654-677, 2013.Md. S. Hossen and Muhammad S. Rahim, “Performance Analysis of Delay-Tolerant Routing Protocols in Intermittently Connected Mobile Networks,” in Proc. of ICMEIE, Rajshahi, Bangladesh, June 2015.M. Gholibeigi, M.
Karimzadeh, Y. Koucheryavy and D. Moltchanov, “Information delivery in delay tolerant networks.” 2011.Y. Zhu, B. Xu, X. Shi, Y.
Wang, “A survey of Social-Based Routing in Delay Tolerant Networks: Positive and Negative Social Effects,” IEEE Communications Surveys & Tutorials, vol. 15, issue. 1, pp. 387-401, 2012.
E. A. A. Alaoui, S.
Agoujil, M. Hazar and Y. Qaraai, “The Performance of DTN Routing Protocols: A Comparative Study,” WSEAS TRANSACTIONS on COMMUNICATIONS, vol.
14, pp. 121-138, June 2015.F.
Xia, L. Liu, B. Jedari, Sajal K. Das, “PIS: A Multi-Dimensional Routing Protocol for Socially-Aware Networking,” IEEE Transactions on Mobile Computing, vol.
15, issue. 11, 2016, pp. 2825-2836.P.
Hui, J. Crowcroft and E. Yoneki, “Bubble Rap: Social-Based Forwarding in Delay Tolerant Network,” in Proc. Mobi Hoc, Hong Kong SAR, China, May 2008.W. Moreira, P.
Mendes and S. Sargento, “Social-aware Opportunistic Routing Protocol Based om User’s Interactions and Interests,” in Proc. of ADHOCNETS, Barcelona, Spain, Oct. 2013.Rados?aw O.
Schoeneich, Rafa? Surgiewicz, “SocialRouting: The social-based routing algorithm for Delay Tolerant Networks,” INTL JOURNAL OF ELECTRONICS AND TELECOMMUNICATIONS, vol. 62, 2016, pp. 167-172.Agussalim, M.
Tsuru, “Performance Analysis of Delay-Tolerant Routing Protocols in Intermittently Connected Mobile Networks,” in Proc. of INCoS, Salemo, Italy, 2014. Md. S. Hossen and Muhammad S. Rahim, “Performance Evaluation of Replication-based DTN Routing Protocols in Intermittently Connected Mobile Networks,” in Proc.
of ICEEE, Rajshahi, Bangladesh, Nov. 2015.W.
Moreira, P. Mendes, R. Ferreira, D. Cirqueira and E. Cerqueira, “Opportunistic Routing Based on Users Daily Life Routine,” in: IETF draft draft- moreira-dlife-03, work in progress, May 2014.Project page of the Opportunistic Network Environment (ONE) simulator. Online, http://www.
netlab.tkk.fi/tutkimus/dtn/theone, (Accessed: June 6, 2017).