# An Effective Hybrid Routing Algorithm in WSN:
## 4 ACOHCM Routing Algorithm
### Analysis of the Convergence Speed of the Algorithm  
The ant colony optimization algorithm, as a swarm intelligence randomized search heuristics (RSHs), is characterized by randomness, teamwork, universality and so on. With such features the ant colony optimization algorithms show a good way to simulate complex dynamic behavior. However, the complex stochastic process caused by such a complex dynamic behavior makes ant colony optimization algorithms experience difficulty in their theoretical analysis, such as convergence analysis and time complexity analysis [30]. [PERSON] [31] developed a Graph-based Ant System, a metaheuristic which can treat arbitrary static combinatorial optimization problems, and for the first time proved that under certain conditions (by a suitable choice of the parameters of the heuristic), the solutions generated in each iteration of this Graph-based Ant System converge with a probability that can be made arbitrarily close to one to the optimal solution of the given problem instance. [PERSON] and [PERSON] [32] presented a short convergence proof for an ant colony system (ACS) and max-min ant system (MMAS). The convergence analysis theory only tells us that ant colony optimization algorithms have the possibility of finding the global optimal solution, and it is hard to evaluate the performance of actual algorithms as what we expected. Hence, it is necessary to analyse the convergence speed of ant colony algorithms so that we can know how quick the algorithms are to find the optimal solution. [PERSON] in 2005 explicitly listed the research on convergence speed for ACO algorithms as the first open problem of ACO research field [33]. Moreover, [PERSON] [34] conducted research about the influence of the pheromone evaporation factor \(\rho\) on the time complexity of ACO algorithm. He showed that for \(\rho=O(n^{-1-\epsilon})\), \(\epsilon>0\), the optimization time of 1-ANT on OneMax is \(2^{\Omega(n^{\epsilon/3})}\) with probability of \(1\)-\(2^{-\Omega(n^{\epsilon/3})}\), whereas for \(\rho=O(n^{-1+\epsilon})\), \(\epsilon>0\). An \(O(n^{2})\) upper optimization bound holds with overwhelming probability of \(1\)-\(2^{-\Omega(n^{\epsilon/3})}\). This reveals a phase transition phenomenon from exponential expected optimization time to polynomial expected optimization time of 1-ANT on OneMax occurring for a fast decrement of \(\rho\). [PERSON] et al. [35] also analyzed rigorously the influence of \(\rho\) has on the performance of 1-ANT algorithm. Lower bounds of optimization time for 1-ANT on two sample functions: LeadingOnes and BinVal, are provided. The authors showed that there is also a phase transition from exponential to polynomial runtimes for \(\rho\sim 1/(nlogn)\) using the two sample functions. Furthermore, in [36], [PERSON] gave a more specific result and proof that with probability \(2^{-\Omega(min(1/n\rho,n))}\) the optimization time of 1-ant on LeadingOnes is \(2^{\Omega(min(1/n\rho,n))}\). Later, [PERSON] [37] studied the influence of pheromone control parameter \(\alpha\) and heuristic information control parameter \(\beta\) on the computation time of the algorithm by constructing the traveling sales person problem (TSP) instances, which is a well-known NP-hard problem. It is showed clearly that for a complete graph instance, when the parameter is set from \(\alpha=1\), \(\beta=0\) to \(\alpha=1\), \(\beta=1\), the upper bound of its expected computing time is also changed from \(O(n^{6})\) to \(O(n^{5})\). In addition, [PERSON] et al. [38] analysed the influence of heuristic information on the performance of the algorithm by constructing the TSP instance. It is stated that with \(\alpha=\)1, If \(\beta=1\), the algorithm needs exponential run time to find the optimal tour, while with \(\beta=n\), it finds the optimum in one iteration with almost the probability of 1. Apparently the ant colony algorithm has less parameters to be pre-defined, but the optimal selection of these parameters is complicated.