# An Adaptive Routing Algorithm Based on Relation Tree in DTN
## 2 Related Work  
The routing problem is one of the hot issues in DTN research. DTN routing algorithms can be divided into two types, zero-information type and auxiliary information type, depending on whether external auxiliary information is required [11]. Direct delivery [12] is the simplest zero-information routing algorithm, where the source node generates a message and will always carry it in the network and will not forward it additionally. This algorithm has the lowest network overhead due to the absence of redundant relay operations, but its performance in terms of transmission efficiency and the average delay is poor. The Epidemic routing algorithm [13] simulates the propagation of an infectious virus in a biological environment by forwarding the message to each node it encounters. However, with limited resources, the nature of blind message propagation will lead to a buffer overflow, and as the number of copies in the network increases, a large number of copies take up network resources and can easily cause network congestion. To overcome the problems caused by the Epidemic routing algorithm, the Spray-and-Wait routing algorithm [14] was proposed, which is divided into two main phases: spray and wait. In the spray phase, the source node copies the maximum number of message copies, which is fixed, and forwards a copy of the message every time it encounters an intermediate node until only one copy of the message remains. If the node carries only a copy of the message, it will enter the waiting phase, in which the message is forwarded only when the target node is encountered. The Binary Spray-and-Wait algorithm [15] is an improvement of the original Spray-and-Wait algorithm. In the spray phase, half forwarding is used to effectively improve the message delivery rate. The maximum message copy number, L, is the key parameter that determines the performance of the Spray-and-Wait algorithm. The paper [16] controls L by controlling message regeneration and deletion. This method extends the application of the algorithm by changing the value of the maximum message copy number, L, from a fixed value to a variable value that can be adapted to the application environment. However, the above zero-information routing algorithms do not consider the differences between nodes [17]. They cannot develop a reasonable routing strategy based on the differences, resulting in inefficient transmission. The external auxiliary information includes historical encounter probability, geographic location, etc. This external auxiliary information plays a huge role in improving forwarding efficiency. Prophet [18] is a probability-based routing algorithm that uses historical transmission probabilities to calculate the current transmission probability. The node carrying the message will decide whether it should forward by comparing the expectedprobability of encountering the destination node. In order to improve the delivery rate of IoT applications in DTN, the authors of [19] propose a scheduling-probability routing algorithm based on node encounter history and convertibility, using two scheduling mechanisms to extend the traditional Prophet algorithm. The authors of [20] proposed the Sharing Spray-and-Wait algorithm. This algorithm uses the Markov chain network model to analyze the message carrying time and delivery predictability, and then uses the results to select the next node and the number of message copies to be delivered in the next hop. The authors of [21] enhanced the Spray-and-Wait algorithm by changing the number of copies sent from the sender to the receiver. The authors of [22] proposed the Geography-Based Adaptive Spray (GBAS) routing algorithm to improve the Spray-and-Wait routing algorithm in many aspects, mainly by calculating the activity range of the destination node in the spray phase to select the appropriate next-hop node. Considering that the social attributes of nodes are stable over time, researchers have proposed many social-based routing algorithms.