CHEMICAL ENGINEERING TRANSACTIONS VOL. 51, 2016 A publication of The Italian Association of Chemical Engineering Online at www.aidic.it/cet Guest Editors: Tichun Wang, Hongyang Zhang, Lei Tian Copyright © 2016, AIDIC Servizi S.r.l., ISBN 978-88-95608-43-3; ISSN 2283-9216 Application of an Improved Ant Colony Algorithm in Routing of Wireless Sensor Networks Jinhui Lei*, Xiyan Tian School of Information and Engineering, Henan Institute of Science and Technology, Henan Xinxiang 453003, China ljh@hist.edu.cn Wireless sensor networks can effectively collect and transmit sensor data, and provide users with a wealth of information. It has broad application prospects in the military, civil and industrial production and so on. Then, it has become one of the hot spots in the current research field. However, compared with other communication networks, wireless sensor networks have some disadvantages, such as no global address mechanism, no dynamic topology and very limited resources. So, after analyzing and comparing some routing protocols, this paper derives the advanced algorithms and proposes a routing algorithm based on ant colony optimization algorithm for wireless sensor networks. The characteristics of self organization, dynamic and multi path of ant colony optimization make it especially suitable for routing in wireless sensor networks. In this paper, a hybrid pheromone updating strategy is adopted. Ant colony algorithm can converge to the optimal solution, it can not only find more feasible solutions, but also maintain the ability to continue to search the optimal solution. In this way, the convergence speed is maintained, and the defect that the update with the global optimal solution is easy to fall into local optimum is overcome. Simulation analysis shows that the algorithm is similar to the directed diffusion algorithm in terms of average transmission delay, but there is a significant improvement in the average energy consumption of the network. 1. Introduction Wireless sensor network is a new technology, which combines sensor technology, microprocessor technology, network and wireless communication technology, distributed processing technology, and so on. It can effectively collect and transmit sensor data, and provide users with a wealth of information. It has broad application prospects in the military, civil and industrial production and so on. Then, it has become one of the hot spots in the current research field. However, compared with other communication networks, wireless sensor networks have some disadvantages, such as no global address mechanism, no dynamic topology and very limited resources. It is particularly important to design an efficient, energy saving, and energy balanced routing protocol(Li et al., 2005; Brayner et al., 2007; Callaway and Jr, 2007). In the military field, wireless sensor networks are composed of dense placement and low cost sensor nodes. In this way, when the enemy has a malicious attack on some nodes, the self organizing and fault tolerance ability will not make the whole system collapse(Walrod, 2002). In the environmental field, the researchers use a number of sensors in the system to monitor rainfall, river water level and soil moisture to predict the possibility of flash floods (Edgar and Callaway, 2003). In the traffic field, the traffic information is collected by the wireless sensor, and it can control the passage of a vehicle and guide the vehicle to reach the preset target(Zhang and Wang, 2010). Although traditional routing protocols are widely used, they are mostly aimed at convergence to the optimal path. This ignores the energy limitation of node of wireless sensor network. Therefore, the energy consumption of nodes on the optimal path is too fast, and the energy of all nodes in the network is not balanced. In this regard, the researchers begin to introduce ant colony algorithm to solve the problem of energy balance. Wang Xiaoming, An Xiaoming(2010) propose the WSN routing algorithm which is based on ACO with energy and position awareness. By fusing the residual energy and position information, the algorithm can better balance the energy consumption and prolong the service life of the network. Wang Min, Li Shining, and Li Zhigang(2011) propose an routing model with multi path load balancing which is based on the ant colony algorithm. Liang Huawei et al(2007) propose the ARAWSN algorithm based on the directed DOI: 10.3303/CET1651054 Please cite this article as: Lei J.H., Tian X.Y., 2016, Application of an improved ant colony algorithm in routing of wireless sensor networks, Chemical Engineering Transactions, 51, 319-324 DOI:10.3303/CET1651054 319 diffusion algorithm. The algorithm can effectively utilize the characteristics of ant colony optimization, and improve the ability of saving energy consumption, while the transmission delay is not greatly improved. 2. Architecture and basic knowledge of Wireless Sensor Networks 2.1 Architecture of Wireless Sensor Networks Wireless sensor network is composed of sensor nodes, sink node and management node. As shown in figure 1, a large number of sensor nodes are randomly distributed inside or near the monitoring area, and the nodes form the network by self-organizing. Then, the sensor nodes can monitor the object. After the data is initially processed, the data is transmitted by using multi-hop relay and according to the unique routing protocol. In the transmission process, the monitored data are processed by multiple nodes and transmitted to the sink node. And then, through satellite, Internet and mobile communication network to reach the management node. Through the effective configuration and management of the sensor network, the end user can release the monitoring mission and collect the monitoring data. Figure 1: The Wireless sensor network 2.2 Characteristics of routing in Wireless Sensor Networks The design of routing protocols in wireless sensor networks is very challenging. Compared with the traditional wireless Ad hoc network, in the design of the routing protocol, it needs to consider the following characteristics(Heidemann et al., 2001; Heinzelaman et al., 2000; Ganesan et al., 2002): (1) Energy is preferred. Traditional routing protocols rarely consider the energy consumption of nodes when selecting the optimal path. In wireless sensor networks, the energy of the nodes is highly limited, and high efficient use of energy is almost the first purpose of the design. Therefore, it is important to consider the energy consumption of nodes and the balance of the network energy, so as to prolong the lifetime of the whole network. (2) No global address. The number of sensor nodes is huge, and maintaining global identity requires a lot of overhead. Therefore, it is different from the traditional routing protocol which is based on the IP. In wireless sensor networks, the global address is generally not used for communication, and the communication mechanism is based on data or location. (3) Communication is not balanced. Different from the traditional network communication mechanism of P2P, almost all applications in sensor networks require a number of sensor nodes to transmit data streams to a specific sink node. This requires the routing strategy to simultaneously consider the problem of the data correlation, node energy consumption and communication load balance. 2.3 Classification of routing algorithms in Wireless Sensor Networks (1) The flooding method As shown in figure 2, if the source node S wants to send a set of data to the target node D, node S will send a copy of the data to each of its neighbor nodes which are A, B and C. Then, each neighbor node transmits a copy of the data to each of its neighbors. In addition to node S, the data is passed in this manner until the data is transmitted to the target node D. 320 Figure 2: Flooding protocol (2) Herarchical routing LEACH is the most representative routing protocol in hierarchical routing protocol, and other hierarchical routing protocols are mostly developed by LEACH. This is the first hierarchical routing protocol by using data aggregation technology. In order to balance the energy consumption of each node in the network, cluster heads are periodically and randomly elected. Each round of elections is that each node generates a random number between 0 and 1, and If the number is less than T(n), the node is used as the cluster head. The calculation formula of ( )T n is as follows: 1 1 ( mod )( ) 0 P P rT n P       (1) In the formula 1, n represents the total number of sensor nodes in the network; P is the percentage of cluster head and the total number of nodes in the network; r is the number of rounds of current electoral. In this protocol, the manner of random election cluster head is used to avoid the excessive consumption of energy and improve the survival time of the network. (3) Directed diffusion protocol Diffusion Directed is a data centric routing protocol, which is a routing protocol specifically designed for wireless sensor networks. It includes three stages that are interest diffusion, gradient establishment and path strengthening. In the phase of interest diffusion, the sink node periodically sends the interest message to the neighbor nodes in a broadcast manner. In the phase of gradient establishment, when the data matched with interest is collected, the algorithm sends the data to the adjacent points of the gradient. After receiving the data from the source node, the sink node starts the path enhancement mechanism to establish the strengthening path from sink node to the target node, and the subsequent data will be transmitted along this path. 3. An improved ant colony algorithm in routing of WSN Ant colony algorithm is a branch of swarm intelligence, which can make the behavior of the whole group to be consistent through the communication between individuals and individuals adaptation to the environment. According to the characteristics of the wireless sensor networks introduced in section second, we find that the ant colony algorithm can better adapt to them. First of all, each individual has a simple function in the ant colony algorithm, and they work according to some simple rules. The routing algorithm is designed by means of this method that is bound to make the routing algorithm of wireless sensor network simpler. Therefore, it can reduce the amount of computation and storage, and reduce the effect of energy consumption. Secondly, when some individuals can not work or the environment changes, other individuals will continue to operate in accordance with the rules in advance. Therefore, ant colony algorithm can find a new path in the shortest possible time. Next, we will introduce the specific methods and steps of improved ant colony algorithm in wireless sensor routing. First of all, we put the m ants into the n nodes which are randomly selected, then each ant will choose the next node that it has not visited by a certain basis. At the same time, after the completion of one step or a cycle, update the pheromone concentration of residual information on all paths. Select the next node is mainly based on two points. The one is Tij(t), which is the pheromone concentration of residual information on the path of nodes i and j on time t. The information is provided by the algorithm itself. Another one is heuristic information 321 ij which is transferred from node i to node j. The heuristic information is given by the problem to be solved. Generally the heuristic factor is ij=1/dij, and dij represents the distance between the nodes i and j. Then, the probability of ant k which is located in the node i selects the node j as the target node on time t is that: ( ) ( ) ( ) ( ) 0 k ij ij k k is is ij s A k t t s A t tP s A                  (2) Where,  represents the relative importance of residual information,  represents the relative importance of expectations, and Ak represents a collection of all the target nodes that may be accessed. In order to avoid repeated visits to the same node, each ant has a list of forbidden tabu (k), which is used to record the nodes that have been visited so far. After each ant completes the access to all the nodes, it is necessary to update the information in the process. At the same time, the pheromone concentration must be updated. 1 1 ( ) ( ) m k ij ij ij k t n t       (3) Where, 1 represents the retention portion of the residue information, kij represents the pheromone concentration of residual information on the path of nodes i and j between the time t and t+n. At this time, 1 ( ) k ij best best f s    (4) Where, f(1) ( ) best f s represents the optimal solution or the global optimal solution in this iteration. Communication between nodes is the main aspect of energy consumption of sensor nodes. At the same time, there is a corresponding energy consumption in the process of sensing the surrounding environment and obtaining the data. Therefore, we set the energy update formula as shown below. 2 (1 ) i i E E E   (5) The specific process of the algorithm is shown in figure 3. Initialization tabu(i,j)=(0,0),route(M.N)=0,NC=0 Calculate the distance between nodes N ants are distributed to the source node Calculate the Ak Using formula 2 to calculate the transition probability P Use formula 5 to update the energy. If the number of iterations is less than half of the maximum value, the local update is used, otherwise, the global update is used greater than the maximum number of iterations？ End Whether or not to reach the target node N Y Y N Figure 3: Specific process of the GA algorithm 322 4. Simulation experiment and result analysis 4.1 Environment and parameters Simulation conditions: in the 100mx100m square area, The topological structure of the coordinate data randomly generated with 50, 100, 150, 200 and 250 nodes, the communication distance of the nodes is 50m. and the other parameters as shown in table 1. Table 1: Parameter setting parameter numerical value The energy consumption of nodes send and receive messages E 200mW The initial energy of each wireless sensor node 0 E 10J The relative importance of residual information  0.2 The relative importance of expectations  0.1 Retention of residual information 1  0.5 Energy consumption of sensing the surrounding environment and obtaining the data 2  0.5 initial value of Pheromone 0  100 Size of each packet 32 bytes 4.2 The experiment steps and the result analysis Next, we respectively use the flooding algorithm, the diffusion directed (DD) algorithm, and the improved ant colony algorithm to carry out the experiment. The experiment is divided into two parts that are the residual energy and the effective survival time of the network. (1) Residual Energy The residual energy of the node is the difference between the initial value and the consumption value of the node. The average residual energy of nodes in wireless sensor network refers to the average value of the residual energy of all nodes, and it is an important index to judge whether the network routing algorithm is efficient. The higher the average residual energy, the less the energy consumption of the data transfer task, and the longer the effective time of the network. Figure 4: comparison of average residual energy As can be seen from Figure 4, the energy consumption of the flooding algorithm is the largest, the average energy consumption of DD algorithm is about half of flooding, while the average energy consumption of the improved ant colony algorithm is minimum, which is about 10% less than DD algorithm. In addition, the average energy consumption of the improved ant colony algorithm is the smallest, and the life cycle of the node and network is also the longest. This has reached the design goal that wireless sensor network protocol can reduce energy consumption and increase energy efficiency. (2) Network Average Delay Time As can be seen from Figure 5, the average time delay of flooding is the maximum, and the average time delay of DD is the smallest. This is because the data packet in DD algorithm that is always along a shortest path of the largest gradient from the target node to the Sink node for transmission, and its average delay is the best of the three algorithms. The average delay of the improved ant colony algorithm is slightly larger than that of the DD, but it is also very close. This is due to the following reasons. In the selection of routing, the improved ant 323 colony algorithm not only needs to satisfy the requirements of the shortest path, but also needs to consider the residual energy of the node, so the delay is slightly increased. Figure 5: Comparison of average delay 5. Conclusion In this paper, a hybrid pheromone updating strategy is adopted. Ant colony algorithm can converge to the optimal solution, it can not only find more feasible solutions, but also maintain the ability to continue to search the optimal solution. In this way, the convergence speed is maintained, and the defect that the update with the global optimal solution is easy to fall into local optimum is overcome. Simulation analysis shows that the algorithm is similar to the directed diffusion algorithm in terms of average transmission delay, but there is a significant improvement in the average energy consumption of the network. References Brayner A, Lopes A, Meira D, et al., 2007, Toward adaptive query processing in wireless sensor networks[J], Signal Processing, 87(12): 2911-2933 Callaway E.H., Jr, 2007, Wireless sensor network: Architecture and protocol[M]. Beijing, publishing house of electronics industry. Cui L., Ju H.L., Miao Y. et al., 2005, Research progress in wireless sensor networks[J]. computer research and development, 42(1):163-174. Edgar H., Jr. Callaway, 2003, Wireless Sensor Networks Architectures and protocols[M]. Auerbach publications. Ganesan D., Govindan R., Shenker S., et al., 2002, Energy Efficient Multipath Routing in Wireless Sensor Networks[J]. ACM Mobile Computing and Communications Review, 1(2):24-28. Heidemann J., Silva F., Intanagonwiwat C., et al., 2001, Building efficient wireless sensor networks with low- level naming[C]. In Proceedings of the ACM Symposium on Operating Systems Principles, Banff, Canda. Heinzelaman W., Chandrakasan A., Balakrishnan H., 2000, Energy-Efficient Communication Protocols for Wireless Micro sensor Networks[C]. Proc. Hawaiian Conference on Systems Science. Liang H.W., Chen W.M., Li S., et al., 2007, An ant colony optimization routing algorithm for wireless sensor networks[J]. Journal of sensing technology, 20(11): 2450-2455. Walrod J., 2002, Sensor Network Technology for Joint Undersea Warfare[C]. In proceedings of the NDIA Joint Undersea Warfare Technology Conference, San Diego, 246-254. Wang M., Li S.N., Li Z.G., 2011, WSN multi path load balancing routing based on Ant colony algorithm[J]. Computer Engineering, 37(14):1-2. Wang X.M., An X.M., 2010, WSN routing algorithm based on ACO with energy and location awareness[J]. Journal of Electronic Science, 38(8):1-2. Zhang Z.S., Wang Z.Q., 2010, Intelligent transportation system based on wireless sensor networks [J]. BATR, 4(5):37-42. 324