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 Optimization of Computer Network Energy Efficient Routing Based on Improved Ant Algorithm Hongyan Zhang*, Qinghong Liu Jilin Province Economic Management Cadre College, Changchun, Jilin 130012, China webuserzhy@126.com Computer network route optimization has been a subject of more attention in the art. This article routing optimization issues in-depth study of the ant colony algorithm to solve distributed parallelism, and propose measures for improvement ant colony algorithm node state transition rule. Pheromone updated rules and improved the classical ant colony algorithm performance. Simulation results show that the improved ant colony algorithm proposed in this paper can change according to the constraints, preferably the most appropriate routing information. Meanwhile, after two improvements, ant colony algorithm convergence rate may be raised, the probability fall into local extreme is also greatly reduced, more conducive to large-scale computer network routing optimization problem. 1. Introduction With the advancement of science and technology, the Internet and other new things have made considerable development. Advancement in people's daily lives more and more important (Balog, 2007). Enjoy the convenience of a computer network at the same time, many experts and scholars began to focus on optimization of network routing (Yao and Anwar, 2015). Due to the increasing size of modern networks, this delay, packet loss, bandwidth constraints and other issues often transfer data, seriously affected the normal operation of the network (Salehpour, 2008). Therefore, the need to study an excellent strategy to effectively manage and utilize network resources is required (Mohan, 2012). Computer network routing optimization problem, in essence, is a special kind of combinatorial optimization problems (Qu et al., 2016). Such optimization issues are difficult to solve combinatorial optimization problems, since many applications such issues, so are a lot of attention (Wang, 2009). Traditional optimization algorithms are generally based on statistical mathematical principles, under the premise needs precisely known or most of the known mathematical models, to be able to better address their optimization problems (Szekely, 2014). However, in practical applications, the mathematical model a lot of problems are very complex, involving cross-application multi-disciplinary, often unable to obtain accurate, especially in the case of many constraints (Camilo, 2006). The optimal solution of the optimization problem is difficult to obtain, even if can be solved, it takes a long time, so the traditional routing algorithm is not suitable for solving large-scale modern computer networks optimization problems (Dorigo, 2008). With the advent and advancement of the theory of NP-hard, many new intelligent algorithms such as neural networks, genetic algorithms and ant colony algorithm, began to be applied to the network routing optimization being achieved some results, but more or there are some small problems, such as neural networks easy to fall into local minimum, genetic algorithm premature convergence. Based on the above analysis, we study the ant colony algorithm to solve a computer network routing optimization problem. In this paper the mathematical essence of route optimization will be elaborated, and put forward the basic ant colony algorithm in two state transition rule and pheromone update rule improvements, ant colony algorithm can solve the slow convergence, very easy to fall into local of small value. Simulation results show that the proposed optimization method is better, it has a certain practicality. DOI: 10.3303/CET1651158 Please cite this article as: Zhang H.Y., Liu Q.H., 2016, Optimization of computer network energy efficient routing based on improved ant algorithm, Chemical Engineering Transactions, 51, 943-948 DOI:10.3303/CET1651158 943 2. Swarm optimization and improvement 2.1 Ant colony algorithm and its improvement The main idea is to simulate the collaborative nature of ant colony foraging behavior, known as ant colony algorithm (Kumar and Gajjar, 2016). According to the characteristics of foraging ants, they will stay on the path-finding pheromone, the shorter the path, the shorter the amount of time the ants back and forth, leaving the pheromone will be a corresponding increase in other ants will be conscious of the other paths the lure eventually find the shortest path to complete a task. Suppose ant k at time t is transferred from node to node J, state transition probabilities described by the following equation:           0 ij ij k is isij s allowed k t t j allowed k t tp t otherwise                                 (1) Ants to find the path of the process will continue to leave pheromones, pheromone when excessive accumulation, heuristic information will be affected, so the need to constantly update the pheromone update rule classical ant colony algorithm is:        1ij ij ijt n t t        (2)     1 m k ij ij k t t      (3) Wherein, ρ∈ (0,1) for the retention factor pheromone, under △ Ʈi (t) is the path, the sum of the newly added information element, △Ʈ (t) at time k ant (t, t + n) remaining on this path, which is calculated as follows.   1 , if ant k access this route at time(t,t+n) 0 otherwise k kij Lt        (4) Lk travels all paths of length. As it can be seen from the above basic principles of ant colony algorithm, and its essence is a distributed parallel algorithm, path planning process at the same time there is a positive feedback correction mechanism, which makes it has a strong ability to solve, and the robustness of the algorithm well. This paper studies the transfer of an improved method of ant colony algorithm pheromone update rules and rules both in the state. 2.2 Improved state transition rules Network routing optimization problems different from the conventional path planning, data exist delay, delay jitter and other phenomena in the transmission between the routing nodes, it must be considered. Therefore, this paper represents the delay by d, dj, b and c, delay jitter, bandwidth and energy consumption path. During the state transition process node, the delay and delay jitter impact into account, the improved state transition formula is as follows:      0max (1) otherwise is iss allowed k t t q q j choose j according                  (5) Wherein, q0 between 0-1, and q is uniformly distributed random number between 0-1. ƞij is no longer a function of the inverse of the path, but improved to delay and delay jitter and a countdown function, ηij=1/(dij+djij). After a so improved to ensure ants during state transitions, choose a higher intensity of pheromone path to avoid falling into local optimum. When an ant k a complete path from the beginning to the end of the selection later, according to the following formula for all its path through the pheromone global updating. 944  1 1 1 1 ij ij Q         (6) Pheromone other path is not passed on in accordance with the following formula update:  11ij ij     (7) According to the above-mentioned article improvement strategies, the improved ant colony algorithm implementation process was shown in Figure 1. Parameter initialization Route selection According equation(4) Calculated Result Optimal? Update information according equation(2) Loop condition Update information according equation(5)(6) Output End Start Y N Y N Figure 1: The improved ant colony algorithm implementation process In Figure 2 an example of the ant colony algorithm iteration process .A0, A1 on behalf of two ants, V0, V1 two nodes, there are two paths upper and down between them and the upper distance of 2. Assuming the initial time distance of each path have the same probability (each 0.5) is selected, the initial value pheromone, α = 1, ᵝ = 2, ρ = 0.6, Q = 1, two ants from V0 start looking for the shortest path. V0 V1 Obstacle Down A1 A0 P=0.5 τ=0.1 P=0.5 τ=0.1 Upper V0 V1 Obstacle Down A1 A0 P=0.8833 τ=1.06 P=0.1167 τ=0.56 Upper (a)Initial Time (b)End Time Figure 2: Iteration of ant colony algorithm 945 3. Experiments and results 3.1 Simulation and experiment Matlab software to construct a small network topology was shown in Figure 3. Required to achieve unicast routing optimization, respectively (1,6), (2,6) and (3,8), QoS parameter requirements: B = 70, D = 8, DJ = 5, PL = 0.0001 . Ant colony algorithm parameters are set: Ants 20, α = ᵝ = 1, ρ = ρ1 = 0.1, the maximum number of iterations of the algorithm 100. 1 2 3 5 4 8 6 7 9 (1.1.10-5) (3.1 .90. 2) （4.2.100.1） （ 3. 1. 11 0. 1） (12.1.120.4) ( 1 . 2 . 9 0 . 2 ) ( 4 . 0 . 9 0 . 2 ) ( 3 . 0 . 1 1 0 . 1 ) ( 1 2 . 2 . 8 0 . 1 2 ) (3.1.20.4) (2. 1.9 0.2 ) (1 .1 .8 0. 3) (6.1.30.8) (1.0.10-6) (1.1.10-6) (1.1.10-4) (1.1.10-5) (1.0.10-5) (1.0.10-6) (1.1.0) (7.2.10-3) Figure 3: Original network topology Since the ant colony algorithm is a distributed parallel algorithms, with possible local optimal solution, it is not every time successful selection to the desired optimal results. The paper selected Maflab software that come standard network test dataset 20 networks, including USA Network and other 17 small networks, including NASA Network, Mini Pacific Ocean Network Central bank Network and three medium-sized networks. Each network routing path 100 is set to be optimized, the results was shown in Figure 4. 0 5 10 15 20 0.6 0.7 0.8 0.9 1 Network Mark S u c c e s s R a te Improved Algorithm Classic Algorithm Figure 4: Route optimization success rate From the results of Figure 3, the improved ant colony algorithm, the route optimization success rate significantly higher than the classic colony algorithm, an average of 90.25 %, and the classic ant colony algorithm is only 84.45 percent. Especially for three of the larger medium-sized networks, improved ant colony algorithm, route optimization success rate reached 93%, 92% and 90%, classical ant colony algorithm 946 optimization results were less than 90%. Thus, in network size, parameter settings are the same, the improved algorithm has a very distinct advantage, greatly reducing the risk of falling into local optimal value, overall algorithm performance significantly. 3.2 Improved simulation of ant colony algorithm Use Matlab programming, in order to demonstrate the improved effectiveness and feasibility of the algorithm. Figure 5 is the best path found. 100 80 60 40 20 0 10080604020 1 2 18 3 9 19 20 21 1011 7 8 14 15 24 25 26 27 28 29 16 17 22 23 30 12 13 4 5 6 Best solution=423.7406 Figure 5: Optimal path As can be seen from the experimental figure, the improved algorithm at the beginning of the algorithm can quickly find the optimum solution, which is due to the partition search ideology, increasing the initial algorithm on each path pheromone quantity difference; in the latter algorithm out of local optimal solution, to find global optimal solution, which is due to the idea of variation. Secondly, from the experimental data in the table can be seen that the improved ant colony algorithm and ant colony algorithm, genetic algorithms and simulated annealing algorithm compared convergence speed significantly improved, greatly reducing the number of iterations, the global search capability has also increased, to find the optimal solution. As can be seen in Table 1 compares the improved algorithm greatly improves the speed of convergence to the optimal number of iterations required is greatly reduced. Table 1: The result of Improved Algorithm α β ρ Optimal solution Worst solution Mean Value Iteration number 0.5 5 0.1 423.7406 425.8201 424.3968 29 0.5 5 0.5 423.7406 426.6002 424.4393 29 1 5 0.1 423.7406 425.2667 424.1098 24 1 5 0.5 423.7406 429.4154 425.5556 27 2 5 0.1 423.7406 425.2667 424.4164 25 4. Conclusions Ant colony algorithm is a random search optimization method from nature, is a group of heuristic biological behavior, have now been applied to combinatorial optimization, fields of artificial intelligence, communications. The positive feedback and ant colony algorithm synergy it can be used for distributed systems, implicit parallelism more so that it has a strong potential for development. From the numerical results, it is more than the current rage of genetic algorithms, simulated annealing algorithm has a better adaptation nature. After all, 947 is a new ant colony algorithm simulated evolutionary algorithm, but also the lack of a solid theoretical foundation of mathematics, parameter selection. For further study, the optimal algorithm is also worth a stop condition where the study now, mostly on the parameter selection algorithm and application with specific issues, determined by experiment; and algorithm stop conditions are fixed number of cycles or iterations stop when the obvious evolution as a condition. Reference Anwar N., Deng H., 2015, November, Ant Colony Optimization based multicast routing algorithm for mobile ad hoc networks, In Advances in Wireless and Optical Communications (RTUWO), 2015 (pp. 62-67). IEEE. Balog K., Rijke M., 2007, Finding similar experts, In: Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, Amsterdam, The Netherlands, p 23–27, doi:10.1145/1277741.1277926 Camilo T., Carreto C., Silva J.S., Boavida F., 2006, An energy-efficient ant-based routing algorithm for wireless sensor networks. In Ant colony optimization and swarm intelligence (pp. 49-59). Springer Berlin Heidelberg. Dorigo M., Birattari M., Blum C., Clerc M., Stützle T., Winfield A., (Eds.), 2008, Ant colony optimization and swarm intelligence: 6th International Conference, ANTS 2008, Brussels, Belgium, September 22-24, 2008, Proceedings (Vol. 5217). Springer. Gajjar S., Sarkar M., Dasgupta K., 2016, FAMACROW: Fuzzy and ant colony optimization based combined mac, routing, and unequal clustering cross-layer protocol for wireless sensor networks, Applied Soft Computing, 43, 235-247. Kumar R., Kumar D., 2016, Hybrid swarm intelligence energy efficient clustered routing algorithm for wireless sensor networks, Journal of Sensors, 501, 5836913. Lakshmi C.B., Rao S.M., 2016, Enhancing network lifetime of a wireless sensor network using swarm Intelligence, International Journal of Applied Engineering Research, 11(1), 435-439. Mohan B.C., Baskaran R., 2012, A survey: Ant Colony Optimization based recent research and implementation on several engineering domain, Expert Systems with Applications, 39(4), 4618-4627. Prabaharan S.B., Ponnusamy R., 2016, Energy aware ant colony optimization based dynamic random routing strategy for MANET, Energy,5(2). Qu Y., Jiang D., Yang Q., 2016, Branch pipe routing based on 3D connection graph and concurrent ant colony optimization algorithm, Journal of Intelligent Manufacturing, 1-11. Salehpour A.A., Mirmobin B., Afzali-Kusha A., Mohammadi S., 2008, December, An energy efficient routing protocol for cluster-based wireless sensor networks using ant colony optimization. In Innovations in Information Technology, 2008. IIT 2008. International Conference on (pp. 455-459). IEEE. Szekely G., Valtcheva I.B., Kim J.F., Livingston A.G., 2014, React. Funct. Polym, DOI:10.1016/j.reactfunctpolym.2014.03.008. Wang J., Osagie E., Thulasiraman P., Thulasiram R.K., 2009, HOPNET: A hybrid ant colony optimization routing algorithm for mobile ad hoc network, Ad Hoc Networks, 7(4), 690-705. Yao Y., Cao Q., Vasilakos A.V., 2015, EDAL: An energy-efficient, delay-aware, and lifetime-balancing data collection protocol for heterogeneous wireless sensor networks, Networking, IEEE/ACM Transactions on, 23(3), 810-823. 948 http://dx.doi.org/10.1016/j.reactfunctpolym.2014.03.008#_blank