# An Effective Hybrid Routing Algorithm in WSN:  
Ant Colony Optimization in combination with  
Hop Count Minimization  
[PERSON]  
1 Department of Computer Science, Taiyuan University of Technology, Taiyuan 030600, China;  
[EMAIL_ADDRESS]  
2  
[PERSON]  
and minimum hop count (MHC)-based WSN routing algorithm [4; 5] show superior capability in finding the shortest path. The paper conducts a thorough analysis of the advantages and disadvantages of the existing ant colony optimization WSN routing algorithms, as well as minimum hop count-based WSN routing algorithms. Then we integrate the two algorithms as a hybrid WSN routing algorithm, comprehensively taking into consideration several critical factors specific to WSN, including energy constraint of sensor nodes, network load balancing, and dynamic network topology. Hereinafter the proposed algorithm refers to ant colony optimization in combination with hop count minimization WSN routing algorithm (ACOHCM). The new hybrid algorithm, ACHCM, has unique superiority in terms of topology maintenance, searching the optimal path, and the network load balancing. A common topology of WSNs has a group of nodes that includes a sink node and a number of sensor nodes. ACHCM borrows the idea of hop count-classification in MHC algorithms. The sensor nodes are firstly marked as different gradations according to their hop count distance to the sink node. So a node will prefer the neighbor nodes who have a lower hop count than the node itself, that is, which are closer to the sink node, as the alternative next hop nodes for data transmission. Therefore, the new proposed algorithm reduces attempts at choosing the nodes which are farther from the sink node to transfer the data. So, the optimal path can be identified much more quickly, and the convergence speed of the algorithm increases rapidly, compared with the conventional ant colony optimization WSN routing algorithms. In the aspect of searching for the optimal path, which is one of the challenging issues in a dynamically changing environment of WSN, we integrate the two algorithms, taking advantages of the two in finding the shortest path and overcoming their disadvantages which will be reviewed in the part of related works. The paper defines a WSN-specific heuristic factor for path selection and proposes a new pheromone update formula. The mutation strategy is also introduced to the algorithm to improve the success rate of searching for the global optimal solution for the optimal path. Regarding balancing the network load, many of the existing routing algorithms use a multi-path routing approach to achieve load balancing. The issue is the fact that using the minimum energy consumption path all the time depletes the energy of nodes on that path. Hence, it encourages the use of multiple paths with a certain probability, which favors battery depletion of different nodes at a comparable rate. However, this kind of multi-path routing approach must take into account the resulting communication interference problem. Different from the multi-path approach, we propose a dynamic energy threshold strategy. This strategy strictly takes control of the energy consumption of each sensor node in an effort to achieve a similar rate of energy depletion of each node so as to avoid premature death of some nodes due to energy depletion. ACOMHC also uses this strategy to trigger route update to prevent the sensor nodes on the routing path from over-consuming of energy and premature death due to data forwarding so as to resolve the problem of \"Hot Spot\". By equalizing the data transmission workload, ACOMHC achieves load balancing. Simulation experiment results verify that ACHCM algorithm has high performances in these respects, including the convergence speed, the success rate of searching for the optimal solution and the network lifetime. The structure of this paper is as follows. In Section 2 we give a review on the ACO-based algorithms and MHC-based algorithms. Section 3 presents our system model and we discuss our proposed method in Section 4.