9512.net
甜梦文库
当前位置:首页 >> IT/计算机 >>

A New Energy-Efficient Routing Algorithm Based on Ant Colony System for Wireless Sensor Networks



2009 Fourth International Conference on Internet Computing for Science and Engineering

A New Energy-Efficient Routing Algorithm based on Ant Colony System for Wireless Sensor Networks

Songzhu Xia1, Su Wu1, Jun Ni1
College of Computer Science and Technology Harbin Engineering University Harbin, China xiasongzhu@hrbeu.edu.cn

Jun Ni2 Department of Radiology College of Medicine, University of Iowa Iowa, USA jun-ni@uiowa.edu energy-efficient routing mechanism always means longer network lifetime. This paper presents a new energy-efficient routing algorithm based on ant colony system. The algorithm utilizes the self-organization, self-adaptability and dynamic optimization capability of ant colony system to find the optimal path and multiple candidate paths from source nodes to sink nodes. In the process of routing, the algorithm considers the available power of nodes and the energy consumption of each path as the reliance of routing selection to avoid losing network connectivity caused by the exhaustion of some sensor nodes. Performance evaluation shows that it can effectively save energy. II. ANT COLONY SYSTEM

Abstract—Due to the limited availability of energy within network nodes, energy-efficient routing mechanism is one of the most critical issues in wireless sensor networks. In this paper, we propose a multi-path routing algorithm with energyaware based on ant colony system. The algorithm introduces three improved rules: Ant Marginalization Rule, State Transition Rule and Global Pheromone Update Rule to solve the problems of local convergence, local optimization and multi-path for transferring data respectively. It can avoid using up the energy of nodes on the optimal path while preserving network connectivity. Compared with traditional routing methods, simulation results demonstrate that the algorithm can help save energy and prolong the lifetime of

the network.
Keywords-wireless sensor networks; ant colony system; multi-path routing; energy consumption

I.

INTRODUCTION

Wireless Sensor Network (WSN), which enables reliable monitoring and analysis of the unknown and untested environment, has attracted more attention and gets fast development for its high dependability, easily distributable and extensible features [1]. It is the integration of sensor technique, nested computation, distributed computation and wireless communication. A typical sensor network is usually composed of hundreds or thousands of low-cost and lowpowered sensors equipped with computation, sensing and communication devices, which are coordinated in a distributed mode in order to collect information on their surroundings. During the lifetime of network, the information collected by the sensors is periodically transmitted to sink nodes, which can be either mobile or base stations. Equipped with a database system, the sink nodes can send queries or control commands to sensor nodes, collect information from sensors and transfer the processed information to users. Since the sensor nodes are microelectronic devices, they can only be supported by a limited power source. The sources of power consumption are communication and computation and the communication between nodes is the main source of energy consumption as node communication tends to be the most expensive aspect of operation in wireless sensor networks [2]. Therefore, an
978-0-7695-4027-6/10 $26.00 ? 2010 IEEE DOI 10.1109/ICICSE.2009.27 176

A. Background knowledge Ant Colony System (ACS) is a new biological algorithm from mimic the behavior of ant colony, proposed by Italy scholar M. Dorigo in 1990’s and first used to address the Traveling Salesman Problem (TSP) [3-5]. This optimization algorithm, which has the characters of positive feedback and parallel processing, is inspired by the ants’ foraging behavior. At present, there are numerous successful applications of the ACS meta-heuristic, including quadratic assignments [6], vehicle routing [7-9], sequential orderings [10], job shop scheduling [11], network routing [12], and logic circuit design [13]. Due to the high social organization, ants can find a short path even the nearest one between their nest and food sources in a shortest time. Biologists find that in the process of search, every ant deposits a kind of chemical called pheromone, which is used as a medium for communication and an indirect form of memory of previously found solutions. Other ants can be affected by the pheromone in every path, and they will follow the trail. The more pheromone there is, the more opportunity there is for the ant to choose the path. Ants communicate with each other by pheromone, identify a new short path, and finally all ants will choose the nearest one. A typical ACS algorithm works as follows. Some artificial ants are generated and initially placed on n nodes according to uniform randomization rule. Each ant carries a

path list and a tabu list to record the nodes on the graph that the ant has visited. By repeatedly applying a stochastic greedy rule known as state transition rule, each ant will build a tour. In the process of building tour, each ant modifies the amount of pheromone on the edges that it just traveled by applying local update rule. Once all ants return to the start nodes, the amount of pheromone on edges is modified again by applying global update rule. During the tours construction, the ants apply state transition rule which makes use of both heuristic information and pheromone information to choose the next edge to travel from its current node. Repeat the process until the system finds the optimal path. B. Ant marginalization rule In the process of initialization for TSP, the ant number and the starting-city of each ant are defined. The number of ants has a great impact on the whole algorithm. In general, the more the number is, the greater the ability of global search of the algorithm has. However, with the increase of the number, the task of computation will exponentially grow. At present, the methods of defining the starting-position are all in a random way. But in simulation, the initial position of some ants is often too close in the random way. These ants tend to select the shorter path nearby, and this leads to the concentrated area locally converge too fast, narrows the solution space and finally affects the generation of the optimal solution. In view of early stagnation caused by the above situation, the paper proposes a method, called Ant Marginalization Rule, to fix the initial position. It is that try to select the marginal cities of the network as the starting cities to distribute the starting points. In this way, the ants will not affect each other too early at the time of selecting path. Thus the solution space will increase and the quality of solution will get improved. But in practical application, it is relatively difficult to judge the location of each city in the network because of the abstract data. So we have to get the group of marginal cities in another way. The paper uses a similar method to solve the problem. It is as follows. Step 1.For i from 1 to n (the sum of cities), we have

determine the relative importance of pheromone versus visibility. Keeping other parameters unchanged, Table I shows the result of the improved initial method compared with the random method.
TABLE I. THE FIRST GROUP COMPARISON
The optimal solution 2039 2020 The worst solution 2090 2057

Method Random Method Marginal Method

Average value 2076 2031

Analysis of the results: ? By marginal method, we can get the optimal solution 2020, while we can only get 2039 by random method. ? The difference between the average values of the two methods is 45 which is the average inter-city distance in bays29. That is to say, the solution by marginal method is shorter than that of random method about the distance from one city to another. To increase the reliability of the experiment, we use other data to conduct further experiments. So we use data gr48, in which the optimal solution is 5046. And we respectively set the ants number 24, 36, 48. Table II shows the result.
TABLE II. THE SECOND GROUP COMPARISON
Ants number 24 36 48 Average of MM 5117.3 5081.4 5074.2 Average of RM 5206.7 5134.1 5079 Time 65s 91s 136s

α
7 7 7

β
10 10 10

ρ
0.5 0.5 0.5

Si = ∑ dij
j =1

n

(i = 1, ???, n)

(1)

In which

dij is the distance between city i and city j, Si is

the sum of the distances from city i to other cities. Step 2.In practical, the marginal city or the scattered city is often relatively far from other cities. Get a sequence S by sorting Si order by descend. Step 3.Locate the ants according S. Use data bays29 offered by TSPLIB [14], in which the city number is 29 and the optimal solution is 2020. Set ants number 15, experiment 10 times. Each experiment includes 1000 times loop. Choose the best solution of 1000 times loop as the result of each experiment. Calculate the average value of the experiments. On the other hand, set the value of α , β , ρ 7, 10, and 0.5. 1 ? ρ (0 < ρ < 1) is the rate of pheromone volatilization.

As Table II shows, with the increase of ant number, the solution of the marginal method is still better than that of the random method. While the ant number gradually increases, the difference of the two methods’ solution becomes smaller. That’s because when the number of ants increases, the starting cities of the two methods are gradually similar to each other. And when the number of ants equals the number of cities, the situation of the two methods is the same. That is each city places an ant. At the same time, the program consumes more time. From the above comparison of the two groups, the performance of the marginal method is indeed stronger than that of the random method. When it contains a few more cities and requires relatively high speed, we can adopt the marginal method to initialize the system and set the ant number as 50-75 percent of the city number. This can reduce the computing time, improve the efficiency and easily get a better solution.

α,β

are

parameters

that

177

III.

MULTI-PATH ROUTING ALGORITHM WITH ENERGYAWARE BASED ON ANT COLONY SYSTEM

A. Algorithm design Due to the limited energy supply of sensors in WSN, we improve the traditional ant colony system, in which we define optimized state transition rule and global pheromone update rule. In the state transition rule, we introduce the random parameter q and the constant parameter q0 to increase the possibility of ants to find a new path avoiding local optimization. The optimized global pheromone update rule can restrain stagnation of the system caused by the increasing gap of pheromone between the optimal path and others and maintain multi-path to transfer information which can prolong the network lifetime. Besides, the model of sensor network is similar with the TSP problem, so the issue of locate the ants in initialization applies the ant marginalization rule. The whole process of the algorithm is as follows. Step 1.Pheromone initialization. At the beginning, an initialization phase takes place during which ants are placed on different sensor nodes according to the ant marginalization rule and initialize the value τ ij (0) , a small positive constant C for pheromone intensity of each edge. Step 2.Path selection strategy. From the sensor nodes, the ants search the path to the sink nodes. According to the state transition rule, the ants choose the next hop node from the set of adjacent nodes. Step 3.Local pheromone update. Arriving at midway node, the ant firstly examines whether the node is closer to the sink node and farther from the sensor node than former node or not. If it is true, the ant modifies the pheromone of the edge according to the local pheromone update rule. Otherwise, the ant terminates search. Step 4.A complete routing. The system repeats Step2 and Step3 until all the ants finish a complete process of search. Step 5.Global pheromone update. The system records the optimal path of each complete search and modifies the pheromone of each edge according the global pheromone update rule. Step 6.Multipath routing. The system repeats Step2, Step3 and Step4 N (loop times) times to get the global optimal path and some suboptimal paths.

Figure 1. The flowchart of the algorithm

B. Algorithm implementation 1) The state transition rule Ant k at node r selects node s as the next hop according to (2) and (3). If q≤q0,

ρ k (r , s ) = ?
else,

?1 max(τ k (r , s )), s ∈ NTk (r ) ?0 otherwise

(2)

? τ k (r , s) s ∈ NTk (r ) ? ? ∑ (3) ρ k (r , s) = ? u∈NT ( r ) τ k (r , u ) k ? otherwise ?0 ?
q is a random number uniformly distributed in [0,1]. q0 is a constant number in [0,1], which determines the relative importance of previous information versus searching new path. ρ k ( r , s ) is the probability of ant k at node r choosing node s as the next hop.

τ k (r , s)

is the amount of

pheromone left by ant k on edge (r,s) and

NTk (r ) is the set

of adjacent nodes to be visited. Before choosing the next hop node, the system generates a random number q. If q≤ q0, the system will choose the node in NTk ( r ) which makes the value

τ k (r , s)

max depending on the previous

information. If q>q0, the system will choose the node in NTk (r ) which makes the value ρ k (r , s ) max in a random way. This method can weaken the trend of ants being trapped in a local optimization.

178

2) The local pheromone update rule If ant k moves from node r to node s according to the state transition rule, the system will modify the pheromone on edge (r,s) according to (4). (4) τ k (r , s ) ← (1 ? α 0 )τ k (r , s ) + Δτ

adjustment coefficient. The value of them depends on the energy of all the paths and nodes. IV. SIMULATION RESULTS AND ANALYSIS After the text edit has been completed, the paper is ready for the template. Duplicate the template file by using the Save As command, and use the naming convention prescribed by your conference for the name of your paper. In this newly created file, highlight all of the contents and import your prepared text file. You are now ready to style your paper. Focusing on energy consumption and network lifetime, we conduct two groups of simulation experiments to verify the efficiency of the energy-efficient algorithm compared with Directed Diffusion (DD) [15] algorithm in WSN. A. The simulation of energy consumption The limited availability of energy within network nodes is one of the most critical issues in WSN. To a large extent, whether a routing algorithm is effective or not depends on the total energy consumption. In this section, we compare the energy-saving ability of the energy-efficient algorithm with DD. 100M*100M area is set as the monitoring region, where sensor nodes are equally distributed. All the sensor nodes are static and a sink node is placed at the margin of the area. The communication radius of each sensor node is 30M. There will be a random sensor node to send data to sink node per 8 seconds and the length of the data frame is 256Bites. Each node’s initial energy is 30J. When nodes transfer data, sending data consumes 120nJ/Bit (1nJ=10-9J) and receiving data consumes 75nJ/Bit of each node every time. Apart from this, the parameters of the energy-efficient algorithm are set N=30, q0=0.45, α 0 =0.9, α1 =0.95, α =3,

α 0 (0 < α 0 < 1) is the evaporation coefficient of local
pheromone. Δτ , a constant number, is the amount of pheromone left by ant k on edge (r,s) in the process of search. The rule is to avoid the other ants only searching the paths nearby the traveled optimal path. 3) The global pheromone update rule When all the ants finish a complete search process, if ant k moves from node r to node s according to the state transition rule, the system will modify the pheromone on edge (r,s) according to (5). Otherwise, the system will apply (6). τ k (r , s ) ← (1 ? α1 )τ k (r , s ) + T (5) (6) τ k (r , s ) ← (1 ? α1 )τ k ( r , s ) α1 (0 < α1 < 1) is the evaporation coefficient of global pheromone. The rule is to get the global optimal solution. T is the restriction function, which is defined as (7).

T=

EC 2 ECk

(7)

EC is the energy consumption of the optimal path in the process of routing and ECk is the whole energy consumption of ant k. The method can restrain the stagnation of the system caused by the increasing gap of pheromone between the optimal path and others and maintain multi-path to transfer information which can prolong the network lifetime. ECk can be calculated by (8).
k ECk = ∑∑ Metricrs Prs r =1 s =1 n n

(8)

n is the sum of the network nodes. If ant k has traveled edge (r,s), the value of
k k Prs is 1.Otherwise, Prs is 0.

β =2. The number of the sensor nodes in networks is 50, 100, 200, 400, and 800 respectively. In the experiment, the monitoring area is changed based on the networks’ scale to keep the nodes density.
TABLE III. THE TOTAL ENERGY CONSUMPTION IN DIFFERENT ALGORITHMS WITH DIFFERENT SENSOR NODES

Metricrs is the standard energy consumption.
4) The calculation rule of standard energy consumption In the algorithm, an important part is the standard energy consumption, which measures path cost. Different calculation ways mean different factors considered. In this paper, we adopt the energy consumption of path and the available power of nodes as the main factors and calculate the value according to (9).
α Metricrs = ers Rsβ

Number of sensor nodes

The energy-efficient algorithm

Directed diffusion algorithm

50 100 200 400 800

15.61KJ 28.34KJ 48.74KJ 95.27KJ 157.60KJ

19.22KJ 34.17KJ 59.30KJ 114.85KJ 186.72KJ

(9)

ers is the energy consumption of the communication
between node r and node s.

Rs is the available power of

node s, which is normalized value compared to the initial energy value. α、 β , two constant number, are both

179

The result shows the energy consumption in the network with increasing nodes in the two algorithms. The ability of saving energy of the energy-efficient algorithm is obvious more effective than that of DD. Because DD is a query-based routing protocol and there will be a flooding communication of interest message in the process of establishing routing table which increases the cost. While the energy-efficient algorithm, considering the energy consumption of communication and the available power of nodes, can restrain the stagnation of the system and maintain multi-path to transfer information. So the energy-efficient algorithm is not only efficient in saving energy than DD, but can balance the whole energy consumption of the networks. B. The simulation of network lifetime The environment of the simulation of the network lifetime is the same as the previous experiment except the number of sensor nodes is set 120 all the time. The system keeps running until there are some nodes not having available power. The system applying DD keeps running for 62 hours 24 minutes and 31 seconds, while the system applying the energy-efficient algorithm is 96 hours 34 minutes and 4 seconds. It is obvious that the energyefficient algorithm can prolong the network lifetime. The distributed routing of the energy-efficient algorithm reduces the communication energy consumption and the ability of balancing the energy consumption of the network avoids the blind spot because of some nodes running out of their energy. V. CONCLUSIONS AND FUTURE WORK In this paper, we propose a multi-path routing algorithm with energy-aware based on ant colony system and validate the efficiency of saving energy and prolonging the network lifetime. The work of this paper has laid a foundation for further complex study of routing in WSN. And we will combine the algorithm with other effective routing algorithms to get better solution for the problem of limited energy in WSN. The energy-efficient algorithm can effectively reduce the energy consumption and prolong the network lifetime. However, the configuration of the algorithm under the condition of large sensor nodes is still needed more research, which we will focus on in our later studies. REFERENCES
[1] Li Zhiyu, Shi Haoshan,“A Data-aggregation Algorithm Based on Adaptive Ant Colony System in Wireless Sensor Networks,” Congress on Image and Signal Processin,. Sanya, 2008, Vol. 4, pp. 449-453. Incheon Park, Derrick Takeshi Mirikitani, “Energy Reduction in Wireless Sensor Networks through Measurement Estimation with Second Order Recurrent Neural Networks,” Third International Conference on Networking and Services, Athens, 2007, pp. 103-106. M. Dorigo, V. Maniezzo, and A. Colorni, “The Ant System: Optimization by a colony of cooperating agents,” IEEE Trans. on SMC, 1996, Vol. 26, pp. 1-13.

[4]

[5] [6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14] [15]

M. Dorigo, G. Di Caro, “The Ant Colony Optimization MetaHeuristic,” New Ideas in Optimization, McGraw-Hill, England, 1999, pp. 11-32. M. Dorigo, C. Blumb, “Ant colony optimization theory: A survey,” J. Theoretical Computer Science. 2005, pp. 243-278. Gambardella LM, Taillard E, Dorigo M, “Ant Colonies for the Quadratic Assignment Problem,” J of the Operational Research Society 1999, Vol. 50, pp. 167-176. Bullnheimer B,Hard R F,Strauss C, “Applying the ant system to the vehicle routing problem,” In: Voss S, Martello S, Osman IH, Roucairol C (eds.) Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization, Kluwer, 1999. Christofides N, Mingozzi A, Toth P, “The vehicle routing problem,” In: Christofides N, Mingozzi A, Toth P, Sandi C, (eds.) Combinatorial Optimization 1979, pp.315-338. Forsyth P, Wren A, “A hybrid ant system for bus driver scheduling,”7th Int Workshop on Computer-Aided Scheduling of Public Transport, Boston, USA, 1997. Gambardella LM, Dorigo M, “HAS-SOP: A hybrid ant system for the sequential ordering problem,” Tech Rep No IDSIA, Lugano, Switzerland, 1997, pp. 97-11. Colorni A, Dorigo M, Maniezzo V, Trubian M, “Ant system for jobshop scheduling,” Belgian Journal of Operations Research, Statistics and Computer Science 1994,Vol. 34, pp. 39-53. Di Caro G, Dorigo M, “AntNet: Distributed Stigmergetic Control for Communications Networks,” Journal of Artificial Intelligence Research (lAIR), 1998, Vol. 9 pp. 317-365. Coello CAC, Gutierrez RLZ, Garcia BM, Aguirre AH, “Automated design of combinational logic circuits using the ant system,” Engineering Optimization 2002, Vol. 34, pp. 109-127. Tsplib, http://www.iwr.uni-heidelberg.de/groups/comopt /software/TSPLIB95/index.html Intanagonwiwat C, Govindan R, Estrin D, “Directed diffusion: A scalable and robust communication paradigm for sensor network,” Proc.6th Annual Int’l Conf. on Mobile Computing and Networks, Boston, MA, August 2000.

[2]

[3]

180



更多相关文章:
Ant Colony Optimization
Ant colony algorithm Ant colony looking for food ...Network Model Problem ?Vehicle routing Conclusions ...algorithm is based on a series of random ...
英文摘要
( 3 ) Based on ant colony algorithm of ...show that the method is feasible and efficient. ...wiring problem, telecommunication network routing ...
无线传感器网络中分簇路由算法的研究
(WSN), and WSN has gradually become a new ...routing algorithm based on ant colony optimization ...Energy efficient routing in wireless sensor networks...
Basic Ant Colony Algorithm for TSP
Ant Colony Based Algor... 暂无评价 4页 ¥2...//Basic Ant Colony Algorithm for TSP #include <...[route[k][s-1]][j],alfa)*pow(yita[route[...
一种基于蚁群算法求方程组数值解的新方法
A New method based on ant colony system for resolving equation groups Ye...3.算法描述 (Algorithm description) 为描述问题清晰和压缩篇幅需要起见,对于涉及...
A Survey Ant Colony Optimization based recent resea...
. Energy aware and energy efficient routing ...(2010). A new clustering algorithm based on ...(2010). An emotionally biased ant colony ...
基于蚁群优化的无线传感器网络路由算法
(2014)03-0067-03 Ant Colony Optimization-based Routing Algorithm in Wireless Sensor Networks WU Huanhuan, ZHANG Ren (College of Information Engineering, ...
2017WSN中负载均衡的蚁群优化算法
Key Words: WSN; ant colony system; energy; load balance; life cycle 1 ...An Energy-Efficient Ant-Based Routing Algorithm for Wireless Sensor Networks....
Ant Colony Optimization
Ant Colony Optimization_互联网_IT/计算机_专业资料 暂无评价|0人阅读|0次下载|举报文档 Ant Colony Optimization_互联网_IT/计算机_专业资料。...
Inside an Ant Colony
An Ant Colony Algorithm ... 6页 免费 hybridization of an ant ... ...Then she sheds her wings and starts a new colony, or returns to her ...
更多相关标签:

All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。
甜梦文库内容来自网络,如有侵犯请联系客服。zhit325@126.com|网站地图