Abstract
Nowadays, Delay Tolerant Network plays an important role in improving the communication between the network nodes. Applications of Delay Tolerant Network are disaster recovery, vehicular communication, sensor networks, interplanetary networks, and communication in remote and rural areas. Routing is one of the important tasks for enhancing the energy effectiveness of data transmission among the mobile nodes under network congestion and dynamic topology. Machine Learning-based routing algorithms are used for improving network communication in Delay Tolerant Networks. Its objective is to reduce the delay, minimize the overhead, reduce energy consumption, improve throughput, minimize packet loss, and efficient data transmission. This paper presents a comprehensive review of routing algorithms using machine learning for Delay Tolerant Networks.
Introduction
Intermittently Connected Mobile Network (ICMN) is among the broad categories of Delay Tolerant Network (DTN). Delay Tolerant Networks aims to support data loss and long delays in difficult environment changes and disaster scenarios [1]. Delays in ICMN networks can be quite significant and unpredictable. These networks may not have host-to-host route between a source node address and a destination node address in the ICMN model and traditional ad-hoc network. The Adhoc network routing algorithms like Dynamic Source Routing (DSR), Optimized Link State Routing (OLSR), Ad hoc On-demand Distance Vector (AODV), and others would fail for routing between the nodes [2]. Machine learning-based routing algorithms are used for classification and prediction. Using Machine earning algorithms, we can achieve the throughput, minimize the overhead and reduce the delivery time. DTN might lead to inconsistent findings since delay periods can vary depending on network factors that are outside the learner’s control (for example, propagation delays between nodes) or bad routing selections. Although predictability of delivery is a reliable predictor for routing performance in various circumstances with DTN, the source node may not know if the message was delivered [3]. Machine learning techniques are used for relay selection have the potential to improve the performance.
A network is a collection of various nodes, which are used for communication between the different nodes like from one node to another node. Nodes can send messages from source to destination. Only data can be used to communicate between nodes. After that data communication was extended to various formats including voice, images, videos, etc. [4]. The wireless network plays an important role in communicating over multiple nodes. Wireless technologies such as Radio Frequency (RF), acoustic (ultrasonic or sonar), Ultra-Wide Band (UWB), and free-space optical technologies are examples of wireless technologies. Using store-and-forward message switching, the above types of networks overcome the various type of network issues such as intermittent connectivity and high error rates. The wireless network is classified into infrastructure-based networks and infrastructure-less networks [5].
The infrastructure-based networks are used for communication between each other nodes with one central access point (wireless fixed point) within the region of the wireless network. These types of networks are used in cellular networks to enable communication between the mobile networks [6]. They are appropriate for locations where infrastructure devices can be easily placed at an acceptable cost and efficiency, and when the network infrastructure can be established at the appropriate time. These cellular networks are having delay is small and capacity also limited [7].
Another type of wireless network is infrastructure-less network which is also called Adhoc networks. There is no requirement of infrastructure within the network such as base station or access point. So, these types of networks are suitable for the areas where there is no infrastructure is available such as disaster areas, rural and urban areas. Ad hoc networks have significantly shorter transmission ranges than cellular networks, and radio channel utilization can dramatically increase the network capacity and bandwidth. These networks are suitable for fast communication.
Mobile Ad-hoc Networks (MANETs) are one of the infrastructures-less wireless networks, in which the nodes are moving constantly in the network [8]. The node can communicate directly with each other within the network range. A network node can transmit the packets, terminate, and forward the packets are being forwarded from one node to the next until it arrives at the destination node. The success of node transmission is one of the challenging tasks because there is a continuous change in the network topology. In Mobile Ad-hoc Networks, finding a destination, routing to that destination, and ensuring reliable communication in the aspect of persistent dynamic topology change have all been significant challenges.
Routing is an important task in Adhoc networks for transferring data and packets from the source node point to the destination node point. Recently, a plethora of routing protocol algorithms has been proposed to help with the node mobility of Mobile Ad-hoc Networks. The routing algorithms are classified as proactive and reactive routing algorithms such as Destination Sequenced Distance Vector (DSDV), Optimized Link State Routing (OLSR), Global State Routing (GSR), Ad hoc On-demand Distance Vector (AODV), Dynamic Source Routing (DSR), Associativity-based routing (ABR) and Zone Routing Protocol (ZRP) and many other algorithms. When nodes move in a MANET, links can be obstructed by intervening objects. Links are shut down regularly when nodes need to conserve power. As a result of these occurrences, connectivity is only intermittent. A network partition occurs when no path exists between the source node point and the destination node point at any given time.
To resolve intermittent node-to-node connectivity, MANETs employ the Store, Carry, and Forward (SCF) principle. This SCF principle is the foundation for Delay Tolerant Networks, which is a method of delivering messages in communication systems without establishing communication paths between source node point and target node point [9]. Delay Tolerant Networks (DTNs) are a type of Ad-hoc Networks that are highly partitioned and intermittently connected to support data loss and long delays in difficult scenarios and ecosystems. Applications of Delay Tolerant Networks are classified as Interplanetary networking, data offloading networks, tactical and military systems, wildlife tracking, disaster recovery management, sensor monitoring networks, crowd mobile sensing networks, communication in rural and urban areas, vehicular communication, and communication in emerging countries are a few of the applications of DTNs.
DTN routing algorithms are classified as a number of destinations, a number of copies, and network topology. Based on network topology, the routing algorithms are epidemic, PROPHET, spray and wait, first contact and direct delivery, Q-Routing, naïve bayes, decision tree, K-Means, MLProph, KNN and ANN algorithms as shown in Fig. 1.
DTN Routing Algorithms.
These DTN routing protocols adapt to this difficult environmental scenario by transmitting multiple copies of data packets data to increase the likelihood that one of the multiple copies reaches the destination node. Packet copies are kept by nodes until they encounter other nodes or reach one of their destinations [10]. We glanced at machine learning techniques for reducing network overhead in DTN routing by identifying its worst intermediate nodes for message copy transmission.
To predict reliable relay nodes, existing work [11] considered encounter frequency, topological information, encounter duration, and so on. According to the theoretical analysis, only a few protocols take energy consumption into account. The [11] also conducted an extensive experimental analysis. It’s difficult to compare the performance of different routing protocol algorithms because they are all designed for a specific environment and aim to optimize different goals. With an infinite buffer size, Epidemic achieves a 100 percent delivery probability. Because of the small buffer size, Epidemic performs poorly in this simulation [11]. In the above-mentioned simulation settings, Spray and Wait (SNW) and Inter Contact Routing (ICR), performed admirably, achieving higher delivery ratios and throughput with less overhead.
The remaining portion of this paper is organized as follows: Some related work on routing methods for delay tolerant networks and tabular form for different papers methodology, advantages, disadvantages, and future scope is presented in Section 2. The routing protocols in Delay Tolerant Networks and Machine Learning-Based routing Protocols are defined in Section 3. The performance analysis of routing algorithms for different parameters is described in Section 4. The final section of the paper is the conclusion in Section 5.
Literature review in DTN
Literature review in DTN
In the literature survey, different routing protocol algorithms for Delay Tolerant Networks have already been proposed. Most of the representative ones are as follows:
In Le [1] the large data communication is going to be a challenging task in Delay Tolerant Network due to lack of short contacts and connectivity with network nodes. Existing work ignores the size of data and contact duration. For this, the author proposed a Large Data Routing protocol (LDR) for large data/messages communication in Delay tolerant network. Initially, large messages are chopped into chunks and forwarded these chunks into successive multiple contact nodes through the multi-hop path for successive nodes. The delivery probability model was developed for contact duration; inter contact time, contact frequency, chunk size, message deadline, and message size. This model achieved a 53% delivery rate compared to existing routing protocols.
Dudukovich and Papachristou [3] presented a Machine learning classifier-based routing algorithm for predicting the set of neighboring message delivery nodes to deliver the messages to a specific location depending on message delivery history information.
Kang et al. [4] present internet communication on the planets called as Internet of Planet (IoP). For this, the information-based time-delay DETN (Delay Efficient Tolerant Networking) routing method was proposed for the efficient way of transmission of data between different mobile nodes used for finding the efficient way of the relay node. This proposed algorithm gives less energy consumption, faster average and response time, and is compared with the previous DTN.
Babu et al. [5] observed that distributed tolerant networks may underperform due to resource constraints. To handle medium term disruptions the authors proposed Medium-Term Disruption Tolerant Software Defined Network (MDT-SDN). This framework used chronological graphs and Earliest Arrival Path with Minimal Storage Time (EAPMST) controller algorithm for buffering packets in wireless networks. This was used to switch medium-term disruptions from 10 sec to 6 min. and it uses the three mobility modes: group mobility, stationary nodes, and random mobility used in-band control for defining wireless mesh testbed. The experimental results are observed as EAPMST enhances throughput by more than 25% for the Random mobility model (RMM), and is capable of handling data packets and maintaining data sessions while using the existing TCP/IP stack during medium-term disruptions. In group mobility, using EAPMST minimizes packet buffering time is 24.45%, but buffering time increases by 5.82% in random mobility. EAPMST reduces buffer occupancy by 44.49% and 60.28% for random and group mobility dramatically. MDT-SDN, and EAPMST were performed similar or better throughput than the standard SDN. Implementation of the EAPMST algorithm also highlighted its impact on reducing node-to-node delay, Open Flow overhead, buffering time, and buffer occupancy.
Portugal-Poma et al. [9] presented a machine learning decision tree classification algorithm for multi-copy Delay Tolerant Networks to reduce the network overhead without decreasing the probability of timely delivery in Vehicular networks. Classification is applied with epidemic and SNW-DTN routing algorithms to check performance improvement. The performance of these two routing algorithms was observed to reduce the overhead and also show a minor increase in delivery ratio due to the use of fewer copies.
Rosas et al. [12] observed communication loss, and congested network topology is the problems of disaster communication infrastructure. This problem can be overcome using Mobile Adhoc Networks in the affected areas around interruptions of the network. Rosas et al. [12] proposed Context-aware Self-Adaptive Routing protocol for DTN. This routing protocol adapts various scenarios and allows network nodes to automatically select a DTN protocol based on the existing performance of routing protocols. Three different ways of mobility models are the Post-Disaster Mobility model (PDM), Valparaiso Mobility Model (VMM), and Cluster Mobility Model (CMM) are used for defining the overhead and delivery rate metrics for the proposed protocol in the field of disaster management. The CSAR methodology is proposed for minimizing the cost of energy and maximizing the delivery rate.
Lent [13] presented bundle transmission over delay tolerant networks for routing techniques. The author proposed Spiking Neural Networks (SNN) to decide the routing packet decisions of various autonomous agents. The routing decisions make finding the local link state for data bundles in a neuromorphic networking strategy that provides Disruption-Tolerant Networks (DTN) using an adaptive bundle routing algorithm. This SNN consumes low energy for Delay Tolerant Networks applications with inadequate energy sources. In a neuromorphic networking solution, a spiking neural network maintains relative cost estimates and makes routing decisions. To address this issue, a reward-shaping approach allows determining the node immediate incentives from a data bundle transmission model. Also, a contact plan was presented for an autonomic loop. The proposed method with Licklider transmission protocol allows cognitive space gateways (CSG). CSG provides a network overlay with intelligent bundle routing. The proposed routing method can reduce response time and improve the performance of bundle delivery in congested networks as compared with existing Contact Graph Routing.
Wu et al. [14] presents the attributes of social nodes that indicate long-term stability, which can be used to improve routing efficiency for the delay-tolerant network. In this, firstly social circles are constructed based on the grouping or clustering phenomenon of the delay-tolerant network’s nodes. Each node forwards its capabilities in different ways to other nodes. For improvement of spray and wait routing algorithm, the authors proposed a Spray Strategy for Social Circles (SC-SS). To enhance the performance of SC-SS, they designed an Adaptive Multiple Spray and Wait for routing method for the Social Circles for routing (SC-AMSW). This SC-AMSW method selectively forwards messages to nodes multiple times for improvement of wait phase and finds the number of duplicate messages based on the predictability of delivery. If, the destination node wasn’t in the social circle then, SC-SS will retransmit the message to the social circle’s destination node point or accept a routing protocol forwarding strategy depending on the geographic information (GI-RFS). The results observed as SC-AMSW gives the finest performance for the rate of delivery, average delay, average hop count, and overhead. This method was not supported for the identification of deleting useless and redundant copies of the nodes for the flooding mechanism.
Wu et al. [15] presented different routing algorithms using machine learning for Vehicular delay tolerant networks. Machine learning using the Bayesian Network (BN) algorithm is K2 based on the Genetic algorithm (K2-GA) was proposed by Wu et al. [15]. This K2-GA is focused on the BN algorithm proposed for the problem of message forwarding for Vehicular Delay Tolerant Networks (VDTN). The Bayesian Network is utilized as a prediction model for the vehicle movement pattern of nodes in VDTN. A Genetic algorithm-based K2 algorithm is proposed to find the best structure of the BN for reducing the problem of structure learning complexity. To speed up the BN process of inference by eliminating variables and sharing calculations can be done using Junction Tree Algorithm (JTA). The results were observed as less forwarding overhead, and the delivery ratio was improved.
Lent [16] proposed anycast routing method for cognitive networks. This method is mainly used for space and ground communication and other fields like lengthy disruptions, long propagation delays, and communication asymmetry. This proposed method allows network gateways that function independently to determine the optimal outgoing link to use, delivering data to one of the anycast group’s members in the quickest time possible.
MLProph is proposed by Sharma et al. [17] which uses novel machine learning-based routing protocol in opportunistic networks. The machine learning algorithms in the technique include neural networks and decision trees to find or determine the probability of successful delivery. The Machine learning models are trained with different factors namely predictability value, power consumption, location, speed, and node popularity. The results observed that MLProph gives the outperformed results compared with PROPHET+ routing algorithm for opportunistic networks in terms of overhead ratio, delivery probability, average latency, next-hop count, packet loss and buffer size. This proposed algorithm with neural networks shows the best performance compared with the decision tree for the above parameters.
Singh et al. [18] proposed a vehicular relay selection routing strategy for improving the parameters performance of vehicle nodes. This scheme selects the best performance vehicular nodes and restricts the low-performance relay nodes. This algorithm gives better optimization and shows that decreasing average latency, and overhead ratio, increases the delivery probability and also decreases the dropped packets in vehicular nodes.
Dudukovich, et al. [19] proposed Naïve Bayes and Q-Routing classification learning algorithms using contact Graph Routing based routing for space delay tolerant networks. These techniques are used for finding the routing decisions with a standard contact graph routing algorithm.
In this Literature review, the Authors summarized different algorithms proposed by different researchers. There has been much work done in the field of opportunistic routing for Delay Tolerant Networks (DTNs). There are different routing protocols developed for DTNs. Every routing protocol has its advantages and disadvantages in terms of various metrics. Some of the authors used machine learning techniques in the routing of Delay tolerant networks. This paper also reviews the routing based on Machine learning. Machine learning-based routing extends the lifetime of a network, it aids routing by adjusting to network changes, reducing congestion and overhead. The authors have used the encounter value between nodes’ contacts, replication copy methods, history of encounters, etc. parameters to select the most appropriate node for forwarding the message. The nodes are in the range of each other for different durations and the duration measurement may be an important parameter for selecting the most appropriate node for message forwarding. The contact duration may be an important parameter to reduce replication to increase the delivery ratio and hence reduce the overhead ratio in DTNs. The overall objective of this review is to address the research on the routing of Delay tolerant networks, in line with this paper summarizes the various routing protocols, methodologies used, limitations and major research gap in DTN routing.
Routing protocols for DTN strive for a high message delivery rate and minimal latency while maintaining a low overhead created a probabilistic routing protocol that chooses intermediate nodes based on previous encounters and transmission. Traditional Routing Protocols and Machine Learning based routing protocols are discussed below.
Routing algorithms
Epidemic routing: Epidemic routing Jones et al. [20] works by replicating messages using random node-to-node exchanges until every node has a copy of each message. Each node stores these messages in a buffer for getting efficiency. When the node enters into contact with some other node, it sends messages to some other node until its buffer contents are synchronized. This method has a high delivery ratio and doesn’t require any understanding of the communication pattern. It performs well in networks with unpredictable node-to-node connections. Unfortunately, it is prohibitively expensive in terms of transmission volume and buffer space. This strategy, in general, and especially, does not show up to be robust as the total number of node messages passing through the network will increase.
PRoPHET routing: PRoPHET means Probabilistic Routing Protocol Using History of Encounters and Transitivity, which is one of the important routing protocols for the Delay Tolerant Networks. Each node in PRoPHET utilizes previous encounters to forecast the optimal route for the future. Each node keeps track of the number of times it has contacted another data node in Delivery Predictabilities (DPs). A data node’s DPs are exchanged when it comes into direct touch with another node. After receiving these, each node modifies its DPs and compares them to those of the encountered node. The message is duplicated and sent to the node with the highest DPs by the node with the lowest DPs. When a node’s buffer is full of messages and a new message arrives from an encountered data node, previous messages are deleted to make room for the unique message, resulting in increased message transmission.
Di-PRoPHET Sok et al. [21] was proposed for improving the overhead, high delay, and low delivery ratio. Distance-based Prophet is a revised version of the prophet for DTN which is used for Distance value retrieval with a cross-layer implementation.
Prophet routing may not be effective with mobiles devices since it works well with devices that consume less energy. Note that mobiles require more energy consumption. For this purpose, Energy-based PRoPHET Bista and Rawat [22] routing was proposed. This E-PRoPHET routing algorithm is used for minimizing energy consumption and also reduces network overhead.
Spray-and-Wait routing: Spray phase sprays a large number of message copies throughout the network area, and then waits for a node until one of those nodes reaches the target. The overall performance of this is an optimal scheme Spyropoulos et al. [2]. This algorithm was divided into two phases are spray phase and wait phase.
Spray Phase: Initially, L node message copies are disseminated – sent by the source node, and maybe remaining nodes deliver a copy to L separate “relays” for every message that originates at a source node.
Wait Phase: If, the destination node is not discovered during the spraying phase, and each of the L message nodes trying to carry a node message copy needs to perform direct data transmission.
MaxProp Routing: MaxProp Mangrulkar [28] divides the buffer into two phases. Based on the hop count information of each message, the first phase transactions stored messages from low to high. The second stage is to sort messages based on their cost, from most expensive to least expensive. From both ends, the buffer is used. The first phase employs the buffer’s front end, while the second phase employs the buffer’s back end.
Contact Graph Routing algorithm: The backbone of contact graph routing has a “contact plan”, time scheduled list of predicted topologies in the network. The contact plan is used by every node in the network to create a routing table. This routing table is used to send the data from the source node point to the destination node point. Contact Graph Routing is used for efficient processing to determine the contact Graph. Contact Graph Routing algorithm Araniti et al. [26] is mainly used for interplanetary networks like space networks and CGR with Machine learning algorithms are used for classification problems.
Machine learning-based routing algorithms
Q-Routing: Reinforcement learning is widely used for machine earning algorithms, which is discovering how to achieve the desired outcome. Q-Routing is the type of Q-Learning algorithm that was developed for data packet transmission routing. Its Q-Table has row information for each neighbour link and column information for every possible network destination. Each column’s index corresponds to a node’s address. Because it will not transmit data to itself, the element corresponding node to each node address is assigned a value of zero. Q-table has the efficient node-to-node packet delivery time used by Q-routing which finds minimized the delay time. The expected time is required for transmitting the node from one of the neighbouring nodes to reach its destination node. This node was selected from row-column pairs in the table. Once the data packet has been sent to the specified nearby node, the neighbour will respond with an estimate of how much time the packet will take to reach its final destination. The first node will use this answer to update its Q-Table. Because nodes closer to the destination node should have a greater understanding of the remaining node delivery time, each refresh should gradually improve the Q-accuracy table’s Dudukovich et al. [19].
Naïve Bayes classifier: Bayesian machine learning algorithm is well-known defined on conditional probability that a given result has some probability if it has a certain collection of attributes. When the beginner is presented with a new node occurrence, the training probabilities are also used to determine the value
Contact Graph Routing has the node attributes of every contact node to create a network model using Naïve Bayes for space Delay Tolerant Network. These attributes are used for finding the prediction of reliability for every node of a neighbouring node Dudukovich et al. [19].
Analysis of different routing algorithms
Decision Tree Classifier: Machine Learning Decision Tree Portugal-Poma et al. [9] with epidemic routing algorithm used for classifying the nodes with attributes and class values for vector and classification label which gives the best performance and decreases the network overhead. The attribute parameters are node id, message reception time, region code, lobby index, and distance between source and destination, and interval of time between every message copy reception and node successful copy transmission. These parameters are used for classifying and generating the class labels. The class label (
After generating the class labels
K-Means clustering: Throughout the simulation time, the K-Means clustering Dudukovich and Papachristou [3] algorithm was utilized to allocate regions depending on the location of nodes. The node coordinates from the previous epoch are recorded in the database, and the node regions are determined using K-means clustering, only with several node clusters varied between 5 and 17 in different simulation runs. These node cluster regions are then utilized to assess whether or not a bundle should be transmitted to another node. The bundle will be transmitted if the nearby node could be in the delivery node’s region between the current time and a “look ahead” time for 10% of the total emulation duration. This time frame was chosen at random to allow for the evaluation of contacts that do not yet exist but will in the future.
MLProph Protocol: MLProph Sharma et al. [17] protocol is a machine learning based on PRoPHET Protocol using opportunistic Networks, which uses the neural networks and decision tree to find the chances of successful delivery. PRoPHET
K-Nearest Neighbour: K-Nearest Neighbour (KNN) classifier algorithm in Machine Learning is a supervised learning algorithm, which finds the K packets in the feature space with the shortest distance to m. KNN, on the other hand, traverses all packets during matching, resulting in a high cost of less contact length time and online computation for data transmission of nodes. Although various approaches to increase its online matching of time have been presented, they are as well complicated to be used on DTN nodes. For solving this challenge, Li et al. [24] present a two-phase method that combines KNN with the K center algorithm for the Social Selfishness Aware Routing algorithm (SSAR).
Artificial Neural Network (ANN): Urban Bus Transportation System uses the Artificial Neural Network (ANN) to predict the contacts Segundo et al. [25]. The ANN network contact predictor is a component of a message routing solution that allows for better management of hidden structures in contact occurrences. The ANN was trained using historical contact data. This type of ANN contact predictor has previously been successfully deployed in a message node forwarding design without message node replication. The strategy’s purpose is to reduce resource consumption and online calculation time while increasing message delivery rate. A multi-copy node routing strategy based on an improved version of the ANN contact predictor has been proposed. It is used by a journey node predictor to generate a multi-graph that represents possible routes to the destination node. The best journey is chosen based on travel selection parameters that reduce message latency. A controlled copy mechanism of relay node messages was created to improve system performance without jeopardising network resources.
I want to do research on various machine learning algorithms that can apply to the performing routing operation in Delay Tolerant Network such as Support Vector Machine (SVM) and regression algorithms.
The performances of different routing algorithms are shown in the above Table 2. From this analysis, the majority of the works used ONE (Opportunistic Network Environment) Simulator for implementing the Delay Tolerant Network routing in most of the papers. DTN gives better performance results with ONE simulator, NS3, and integration of NS3 and MATLAB simulators.
Conclusion
Routing technique is one of the most important tasks in Delay Tolerant Networks. Routing algorithms are used for achieving high performance, decreasing overhead, energy efficiency, and low delivery time. Machine learning is used for classifying the data and prediction. Traditional Adhoc networks are having proactive and reactive routing algorithms. These algorithms would fail and give less performance for Delay Tolerant Networks. In this context, routing algorithms and machine learning-based routing algorithms are reviewed and presented here for Delay Tolerant Networks. For DTN, there is a lot of potentials for machine learning algorithms to be developed for improving the performance of routing. Machine Learning methods can also be used to adapt to network changes, efficiently route packets, reduce overhead, and regulate congested nodes. Machine Learning techniques are reliable in prediction, quick convergence, and learning from knowledge, all of which will aid in energy and resource conservation in a resource-constrained DTN.