## 4 Algorithm Description
### Improved AODV Routing Discovery Algorithm  
AODV is a classic on-demand routing protocol in Ad Hoc networks. It does not need to maintain the routing to all nodes and searches for the desired route only when needed [9]. When the source node wants to send a data packet to the destination node, the source node will start the route discovery process and establish a positive and reverse path. As shown in Figure 2, the letters A-E in Figure 2 represent nodes, source node A broadcasts a route request (RREQ) message to adjacent node B and C, then C and B will establish a reverse routing, and B will continue to forward the RREQ message to C. At this time, C returns to A with two reverse paths. So, the minimum jump path is selected to forward route reply (RREP) to find the shortest path from the source node to the target node [28]. Figure 2: Route establishment process. Because of its on-demand characteristics, the AODV routing protocol only establishes and maintains the required routes, reducing the burden of routing tables. Therefore, it has certain advantages in saving network overhead and channel resources, but it still has the following shortcomings:  
1. In the route discovery process, it broadcasts RREQ messages to the target node in the form of flooding [12]. Since each node rebroadcasts the RREQ packet when each node receives the RREQ packet, the possible number of rebroadcasts when the destination node is reached at the destination node is around N\({}^{2}\), where N is the total number of network nodes. This method of broadcasting may lead to excessive redundant retransmissions in the congestion network, bring a large delay, and result in a large network overhead [22]. 2. The AODV routing protocol is based on the fewest hops as the basis for the chosen path. This method of judgment is not very reasonable in actual applications because the minimum jump is not the same as the shortest communication distance. The farther the distance is, the greater the loss. To address the shortcomings of the AODV routing discovery algorithm, a better algorithm is designed in this paper to decrease routing discovery overhead and avoid route breaking. First, this paper adds a routing cost to RREQ messages to reflect the link quality of the path. Every intermediate node which receives the RREQ packet computes the routing cost and records it to evaluate the path performance instead of using the minimum number of hops as the only judgment basis for selecting the path. Secondly, a probabilistic approach to flooding is considered to select the flood area to reduce the number of RREQs. In the fixed probability route discovery, the possible broadcast number of RREQ packets is p \(\times\) N\({}^{2}\)[22]. In the improved algorithm, a special zone for routing discovery is defined according to the nodes' geographic positions, which are known due to the fixed characteristics of the trackside nodes in the urban rail scenario, so flooding in the whole network is no longer needed. The improved algorithm restricts the flooding to the area in the direction of the source and direction node, which greatly reduces the overhead of route discovery. At the same time, in the application scenario of urban rail in this paper, because of the continuous power supply of trackside nodes, the situation of energy exhaustion does not exist. Therefore, this paper considers the direct use of existing paths, reducing the number of broadcast RREQ messages and further reducing the overhead of routing discovery. The specific improved routing discovery algorithm in this paper is as follows. The algorithm improves the judgment basis for selecting the path. A path \(P\) with length \(L\) is assumed, consisting of device D1, D2,..., Dn, and the corresponding link is [Di, Di+1]. The calculation of the cost of path \(P\) is shown in (1), where \(C([D_{i},D_{i+1}])\) is the link cost, which is shown in (2) [16]. \[C(P)  
When the source node initiates the routing discovery algorithm, it selects the flooding area according to the location of the destination node.