# Energy-Balanced Routing Algorithm Based on Ant Colony Optimization for Mobile Ad Hoc Networks
## 2 Preliminaries
### Principle of the Ant Colony Optimization Algorithm  
In an ant colony optimization algorithm, the choice of each path depends on two aspects: pheromone concentration and heuristic information. Pheromone refers to the chemical substances secreted by each ant in the process of finding a path. When the ant successfully finds the target node, pheromones will increase in a certain proportion. Heuristic information is a priori knowledge about the link, and, in most cases, it refers to the cost of selecting the path or the connection state of the link. The ant colony optimization algorithm is mainly divided into two parts: the transition probability criterion and the parameter definition. The criterion of transition probability is how to choose the next hop according to the transition probability. The basic expression of transition probability is as follows:\[p_{ij}(t)=\left\{\begin{array}{cl}\dfrac{\tau_{ij}^{\alpha}(t)g\eta_{ij}^{\alpha}(t )}{\sum_{l\in N_{i}}\tau_{il}^{\alpha}(t)g\eta_{il}^{\beta}(t)},&\text{if}\quad j \in N_{i},\\ 0,&\text{if}\quad j\
otin N_{i},\end{array}\right. \tag{1}\]  
where \(p_{ij}(t)\) is the probability that the ant moves from node \(i\) to node \(j\) at time \(t\); \(N_{i}\) is the set of optional next hop nodes of node \(i\); \(\tau_{ij}(t)\) represents the pheromone concentration on the link at time \(t\); \(\eta_{ij}(t)\) denotes the heuristic information on the link at time \(t\), which usually refers to the connection status of the link or the cost of selecting the path. \(\alpha\) is the pheromone heuristic factor, indicating the role played by the pheromone released by the ant in the path selection. The greater its value is, the stronger the indirect effect between ants will be. In other words, the path taken by the forwarded data packet has a greater influence on the selection of the current path, then eventually all ants select the same path. If \(\alpha=0\), it degrades into the greedy algorithm (local optimum selection), and the ant selects only the path which is currently considered best. \(\beta\) is the expected heuristic factor, indicating the relative importance of heuristic information. The higher its value is, the greater the influence of link quality on the packet selection path will be. In the transfer probability formula, the emphasis is on pheromone and heuristic information. Other weight factors can be set according to different scenarios by using empirical values or simulation analysis. When an ant completes a routing or selects the next hop, or the update cycle set by the routing protocol comes, the pheromone of the selected path is updated according to Formula (2):  
\[\tau_{ij}(t+1)=(1-\rho)\tau_{ij}(t)+\rho\Delta\tau_{ij}(t), \tag{2}\]  
where \(\Delta\tau_{i,j}(t)\) is the amount of pheromone that the ant deposits this time on the link \((i,j)\); \(\rho\) is the pheromone evaporation rate, indicating the rate that the pheromone decays over time, and the value range of \(\rho\) is \(\rho\in[0,1]\), so \(1-\rho\) indicates the residual level of the pheromone. In different algorithms, the expressions of \(\Delta\tau_{i,j}(t)\) or \(p_{i,j}(t)\) are distinct depending on specific problems.