## 3 The Proposed Algorithm
### The Ant Colony Optimization Method  
After completing the cluster-head election, an effective routing algorithm is needed to complete the end-to-end communication from the train to the station. In the routing process, the source node and destination node are train and station, respectively, and the intermediate nodes are cluster heads. As a classical swarm intelligence algorithm, ant colony optimization (ACO) was first proposed in ref. [21], and is usually used to solve the problem of complicated combination optimization. Considering the similarity between finding the best route and ant colony foraging, an improved ACO algorithm is proposed in this section. ACO uses the pheromone left by ants in foraging to find the optimal path. Pheromone is a substance left by ants on the path in the process of foraging, and ants can sense the pheromone intensity. Therefore, more ants pass along the path with stronger pheromone,and a positive feedback mechanism is formed, thereby gradually approaching the optimal path [22]. In the foraging process, the node with higher pheromone concentration has higher probability of being selected, but ants also choose the next hop based on higher heuristic information. Therefore, the next hop is determined according to the transition probability comprehensively calculated according to the pheromone concentration and heuristic information left on the current node path, which can be described by Equation (13) [21]:  
\[p_{ij}^{k}(t)= \begin{cases}\frac{[\tau_{ij}(t)]^{\alpha}[\eta_{ij}(t)]^{\beta}} {\sum_{u\in k_{jk}(i)}{[\tau_{u}(t)]^{\alpha}[\eta_{u}(t)]}^{\beta}},&j\in J_{ k}(i)\\ 0,&j\
otin J_{k}(i)\end{cases} , \tag{13}\]  
where \(p_{ij}^{k}(t)\) is the transition probability of ant \(k\) from node \(i\) to node \(j\) at time \(t\), \(\tau_{ij}(t)\) and \(\eta_{ij}(t)\) are the pheromone concentration and heuristic information, respectively, \(\alpha\) and \(\beta\) represent the importance of the pheromone concentration and heuristic information, and \(J_{k}(i)\) indicates the optional node set of ant \(k\) at node \(i\), which is the set of nodes that have not been visited. Based on Equation (13), ant \(k\) determines the next hop node until arriving at the destination node. After all ants arrive at the destination node, the shortest route is saved, and then the pheromone concentration of each route is updated. After a certain number of iterations, all ants tend to choose the same path, and the algorithm reaches convergence. \(\eta_{ij}(t)\) is usually calculated as \(1/d_{ij}(t)\) in traditional ACO, in which \(d_{ij}(t)\) is the distance between node \(i\) to node \(j\) at time \(t\). Compared with other ad hoc networks, the urban rail transit scenario has the characteristics of linear distribution and huge data traffic; thus, specifying the routing direction and avoiding node congestion should be considered. In this paper, three factors are considered when calculating \(\eta_{ij}(t)\), as shown in Equation (14):  
\[\eta_{ij}(t)=a_{1}\cdot norm[\frac{1}{d_{ij}(t)}]+a_{2}\cdot norm[\frac{1}{2- \cos\theta_{ij,id}(t)}]+a_{3}\cdot norm[(1-q_{j}(t))], \tag{14}\]  
in which \(norm[\cdot]\) indicates the normalization operation, \(\cos\theta_{ij,id}(t)\) indicates the cosine value of the angle between edge \(ij\) and edge \(id\), where node \(d\) represents the destination node. Assume that the train moves from \(z_{1}\) to \(z_{m}\), and the train's position is \(z_{t}\) at time \(t\). Based on the assumption, \(q_{j}(t)\) is the ratio of the number of times node \(j\) has been selected as the node on the best path in the process from \(z_{1}\) to \(z_{t}\) and the total path number from \(z_{1}\) to \(z_{t}\). According to Equation (14), \(\eta_{ij}(t)\) is constrained by \(d_{ij}(t)\), \(\cos\theta_{ij,id}(t)\), and \(q_{j}(t)\), which influence the route length, search direction, and node load, respectively.