当前位置:首页 >> IT/计算机 >>

An Energy-Efficient Ant-Based Routing Algorithm for Wireless Sensor Networks

An Energy-E?cient Ant-Based Routing Algorithm for Wireless Sensor Networks
Tiago Camilo1 , Carlos Carreto2, Jorge S? Silva1 , and Fernando Boavida1 a
Laboratory of Communications and Telematics University of Coimbra, Coimbra, Portugal {tandre, sasilva, boavida}@dei.uc.pt 2 Escola Superior de Tecnologia e Gest?o a Instituto Polit?cnico da Guarda, Guarda, Portugal e ccarreto@ipg.pt

Abstract. Wireless Sensor Networks are characterized by having speci?c requirements such as limited energy availability, low memory and reduced processing power. On the other hand, these networks have enormous potential applicability, e.g., habitat monitoring, medical care, military surveillance or tra?c control. Many protocols have been developed for Wireless Sensor Networks that try to overcome the constraints that characterize this type of networks. Ant-based routing protocols can add a signi?cant contribution to assist in the maximisation of the network lifetime, but this is only possible by means of an adaptable and balanced algorithm that takes into account the Wireless Sensor Networks main restrictions. This paper presents a new Wireless Sensor Network routing protocol, which is based on the Ant Colony Optimization metaheuristic. The protocol was studied by simulation for several Wireless Sensor Network scenarios and the results clearly show that it minimises communication load and maximises energy savings.



Identi?ed as one of the most important technologies of the XXI century, Wireless Sensor Networks (WSNs), are becoming the next step in information revolution [1]. This enhancement was only possible due to the recent advances in electronic sensors, communication technologies and computation algorithms; however, because of their novelty, WSNs present new challenges compared to custom wireless networks. Although they can be considered ad hoc networks, WSNs present unique characteristics mainly due to their component devices, the sensor nodes. A sensor node, typically, contains signal-processing circuits, micro-controllers and a wireless transmitter/receiver antenna, and is characterized by limited resources: low memory, reduced power battery and limited processing capabilities. Sink-nodes are the devices responsible for managing the communication from the sensor network to the base station, normally located in the wired network where the observer keeps record of the sensor data. After receiving packets, sink-nodes can send them to the base station if it is located inside the communication range, or send them to other sink-nodes, through known ad hoc techniques. Furthermore,
M. Dorigo et al. (Eds.): ANTS 2006, LNCS 4150, pp. 49–59, 2006. c Springer-Verlag Berlin Heidelberg 2006


T. Camilo et al.

sink-nodes have distinctive characteristics when compared to typical sensor-nodes, such as more energy capacity, more processing power and more memory, which makes them perfect to perform high demand processing and storing tasks. Potential WSNs applications include security, tra?c control, industrial and manufacturing automation, medical or animal monitoring, and many more. This wide applicability range forces WSN protocols to become application-based, meaning that it is not feasible to build a WSN algorithm that ful?ls all application requirements. Instead it is important to build generic algorithms that somehow can be adapted to some application requirements and at the same time prolong the network lifetime as long as possible. The lifetime of a sensor network can be measured based on generic parameters, such as the time when half of the sensor nodes lose their transmitting capability, or through speci?c metrics of each application, e.g. minimum delay. This paper presents a new communication protocol for WSNs called energye?cient ant-based routing algorithm (EEABR), which is based on the Ant Colony Optimization (ACO) metaheuristic [13]. EEABR uses a colony of arti?cial ants that travel through the WSN looking for paths between the sensor nodes and a destination node, that are at the same time short in length and energy-e?cient, contributing in that way to maximise the lifetime of the WSN. Each ant chooses the next network node to go to with a probability that is a function of the node energy and of the amount of pheromone trail present on the connections between the nodes. When an ant reaches the destination node, it travels backwards trough the path constructed and updates the pheromone trail by an amount that is based on the energy quality and the number of nodes of the path. After some iterations the EEABR protocol is able to build a routing tree with optimized energy branches. In this paper we do not consider energy saving techniques based on the management of the node status [12]. These techniques are normally implemented in physical and access layers, and allow turning nodes from sleep mode to transmitting/receiving mode. The remainder of this paper is organized as follows. Section 2 describes the state-of-the-art of WSN protocols; wellknow algorithms are described as well as some approaches that combine ant-based algorithm with such networks. In Section 3 the EEABR protocol is described, in conjunction with two other approaches. Section 4 presents the studies performed to evaluate the proposed protocol; these simulation environments try to emulate real WSN deployment, so that real sensor characteristics can be studied. Conclusions and topics for further work are presented in Section 5.


Related Work

Wireless sensor networks can be considered, as mentioned before, ad-hoc networks. However, protocols for mobile ad hoc networks (MANETs) do not o?er some of the sensor networks requirements: sensors typically have low power battery, low memory, and the routing tables grow up with the network length and

An Energy-E?cient Ant-Based Routing Algorithm for WSNs


do not support di?usion communication. These are the main reasons why it is necessary to design new protocols, built on the most important criterion of energy-e?ciency. Low Energy Adaptive Clustering Hierarchy (LEACH), described in [2], is probably one of the more referenced protocols in the sensor networks area. It is a powerful, e?cient protocol created to be used in sensor networks with continued data ?owing (unstopped sensor activity). This is a protocol that uses a hierarchical topology, randomly creates cluesterheads, and presents data aggregation mechanisms. Power-E?cient GAthering inSensor Information Systems (PEGASIS), is a recently developed protocol, which is similar to LEACH but that requires less energy per round [3]. In PEGASIS, a chain is created so that each node receives aggregate information and forwards it to a nearby neighbour. It presents mechanisms that allow the variation of radio communications energy parameters. Compared to LEACH, the PEGASIS protocol obtains up to 100% of energy cost improvement per round [4]. However these two protocols are not suitable for mobility, and both assume that data packets can be aggregated at clusterheads. Direct Di?usion (DD) [5] is a data-centric protocol, which addresses nodes by the monitored data instead of their network addresses. In this protocol the application is responsible to query the network for a speci?c phenomenon value. Sensor nodes that satisfy the speci?c query start transmitting their data. Based on sink-nodes requests this protocol does not consider the node’s available energy when building their ?ood-based routing scheme. Jeon et al. [6] proposed an energy-e?cient routing protocol that tries to manage both delay and energy concerns. Based on AntNet protocol [7], this algorithm uses the concept of ant pheromone to produce two prioritized queues, which are used to send di?erentiated tra?c. However, such approach can be infeasible in current sensor nodes due to the memory required to save both queues. This can be even more problematic if the sensor network is very populated, since the routing table on each device depends on the number of neighbours. Zhang et al. [8], study three distinct Ant-based algorithms for WSNs. However, the authors only focus on the building of an initial pheromone distribution, good at system start-up. Finally in [9], the authors present an ant colony algorithm for Steiner Trees which can be ported to WSNs routing. However, no changes are considered regarding the speci?c WSNs requirements and also no considerations are made regarding the energy management essential to the WSNs performance. The ant-based algorithms presented above assume that communication between sensor nodes (end-to-end) is required by the WSN application, and build their algorithms based on such assumption. However this is not the case in most WSNs scenarios, where the hop-by-hop or single hop communication is performed from source node (sensor node) to sink node, which is responsible to collect sensor data from the network. This node presents di?erent characteristics compared with normal sensor nodes (more energy, more memory and more processing power), and such di?erences are not considered in the referred algorithms.


T. Camilo et al.


Energy-E?cient Ant-Based Routing Algorithm

Whenever a WSN protocol is designed, it is important to consider the energy e?ciency of the underlying algorithm, since this type of networks have strict power requirements. In this section we describe a new energy-constrained protocol, the EEABR protocol, which is based on the Ant Colony Optimization heuristic and is focused on the main WSNs constraints. On such networks deployed in real environment it is important to point out that sensor nodes may not have energy replenishment capabilities. This assumption forces the use of energy-e?cient algorithms in order to maximize the network’s life time. In contrast, in timely delivery packet networks, a routing algorithm attempts to ?nd the shortest path between two distinct devices (source and receiver), which can be easily done by choosing the path with less communication hops. In WSNs such requirements are relegated to second plane, since quality of service and service awareness are not as important as in normal MANETs, where running protocols required low communication delays. The remainder of this section summarizes the idea behind EEABR. First, a basic ant-based routing algorithm for WSNs is presented that describes the adaptation of the ACO metaheuristic to solve the routing problem in WSNs. Next, an improved algorithm is presented that reduces the memory used in the sensor nodes and also considers the energy quality of the paths found by the ants. Finally the EEABR protocol is presented and further improvements are described to reduce the communication load and the energy spent with communications. 3.1 Basic Ant Based Routing for WSNs

The ACO metaheuristic has been applied with success to many combinatorial optimisation problems [13]. Its optimization procedure can be easily adapted to implement an ant based routing algorithm for WSNs. A basic implementation of such algorithm can be informally described as follows. 1. At regular intervals, from every network node, a forward ant k is launched with the mission to ?nd a path until the destination. The identi?er of every visited node is saved onto a memory Mk and carried by the ant. 2. At each node r, a forward ant selects the next hop node using the same probabilistic rule proposed in the ACO metaheuristic: ? α β ? [T (r,s)] [E(s)] if s ∈ Mk / ? ? [T (r,s)]α [E(s)]β (1) pk (r, s) = ? u∈Mk ? / ? 0 otherwise where pk (r, s) is the probability with which ant k chooses to move from node r to node s, T is the routing table at each node that stores the amount of pheromone trail on connection (r, s), E is the visibility function given 1 by (C?es ) (C is the initial energy level of the nodes and es is the actual

An Energy-E?cient Ant-Based Routing Algorithm for WSNs


energy level of node s), and α and β are parameters that control the relative importance of trail versus visibility. The selection probability is a tradeo? between visibility (which says that nodes with more energy should be chosen with high probability) and actual trail intensity (that says that if on connection (r, s) there has been a lot of tra?c then it is highly desirable to use that connection. 3. When a forward ant reaches the destination node, it is transformed in a backward ant which mission is now to update the pheromone trail of the path it used to reach the destination and that is stored in its memory. 4. Before backward ant k starts its return journey, the destination node computes the amount of pheromone trail that the ant will drop during its journey: ΔTk = 1 N ? F dk (2)

where N is the total number of nodes and F dk is the distance travelled by the forward ant k (the number of nodes stored in its memory). 5. Whenever a node r receives a backward ant coming from a neighbouring node s, it updates its routing table in the following manner: Tk (r, s) = (1 ? ρ) Tk (r, s) + ΔTk (3)

where ρ is a coe?cient such that (1 ? ρ) represents the evaporation of trail since the last time Tk (r, s) was updated. 6. When the backward ant reaches the node where it was created, its mission is ?nished and the ant is eliminated. By performing this algorithm several iterations, each node will be able to know which are the best neighbours (in terms of the optimal function represented by (2)) to send a packet, towards a speci?c destination. 3.2 Improved Ant Based Routing for WSNs

In this section we propose two improvements in the basic ant-based routing algorithm described in the previous section in order to reduce the memory used in the sensor nodes and also to consider the energy quality of the paths found by the ants. In the basic algorithm the forward ants are sent to no speci?c destination node, which means that sensor nodes must communicate with each other and the routing tables of each node must contain the identi?cation of all the sensor nodes in the neighbourhood and the correspondent levels of pheromone trail. For 只保存通往sink的邻居 large networks, this can be a problem since nodes would need to have big amounts of memory to save all the information about the neighbourhood. Nevertheless, the algorithm can be easily changed to save memory. If the forward ants are sent directly to the sink-node, the routing tables only need to save the neighbour nodes that are in the direction of the sink-node. This considerably reduces the size of the routing tables and, in consequence, the memory needed by the nodes.


T. Camilo et al.

As described in the Introduction, sensor nodes are devices with a very limited energy capacity. This means that the quality of a given path between a sensor node and the sink-node, should be determined not only in terms of the distance (number of nodes of the path), but also in terms of the energy level of that path. For example, it would be preferable to choose a longer path with high energy 信息素更新考虑能量 level than a shorter path with very low energy levels. To consider the energy quality of the paths on the basic algorithm a new function is proposed to determine the amount of pheromone trail that the backward ant will drop during its returning journey: ΔTk = 1 C ? avg (Ek ) ?
1 min(Ek )


where Ek is a new vector carried by forward ant k with the energy levels of the nodes of its path, C is the initial energy level of the nodes, avg (Ek ) is the average of the vector values and min (Ek ) is the minimum value of the vector. 3.3 Energy-e?cient Ant Based Routing for WSNs

In this section we propose further improvements in the routing algorithm described in the previous section in order to reduce the communication load related to the ants and the energy spent with communications. We also propose new functions to update the pheromone trail. It has been proved that the tasks performed by the sensor nodes that are related with communications (transmitting and receiving data), spend much more energy than those related with data processing and memory management [10,11]. Since one of the main concerns in WSNs is to maximise the lifetime of the network, which means saving as much energy as possible, it would be preferable that the routing algorithm could perform as much processing as possible in the network nodes, than transmitting all data through the ants to the sink-node to be processed there. In fact, in huge sensor networks where the number of nodes 减少蚂蚁包的大小 can easily reach more than 1000 units, the memory of the ants would be so big that it would be unfeasible to send the ants through the network. To implement these ideas, the memory Mk of each ant is reduced to just two records, the last two visited nodes. Since the path followed by the ants is no more in their memories, a memory must be created at each node that keeps record of each ant that was received and sent. Each memory record saves the previous node, the forward node, the ant identi?cation and a timeout value. Whenever a forward ant is received, the node looks into its memory and searches the ant identi?cation for a possible loop. If no record is found, the node saves the required information, restarts a timer, and forwards the ant to the next node. If a record containing the ant identi?cation is found, the ant is eliminated. When a node receives a backward ant, it searches its memory to ?nd the next node to where the ant must be sent. The timer is used to delete the record that identi?es the backward ant, if for any reason the ant does not reach that node within the time de?ned by the timer.

An Energy-E?cient Ant-Based Routing Algorithm for WSNs


The vector Ek was erased from the forward ants k, that now only carry the average energy till the current node (Eavgk ), and the minimum energy level registered (E mink ). These values are updated by each node that receives the forward ants. When the forward ant reaches the sink-node these values are used to calculate the amount of pheromone trail used by the corresponding backward ant:

ΔTk =

1 C?
E mink ?F dk E avgk ?F dk


With these changes it is possible to reduce the ant’s length by ? =700%, and save on each ant hop the transmission of ? =250 bytes. This is a signi?cant achievement, since it allows the saving of precious energy levels on sensor nodes. Calculating ΔTk only as a function of the energy levels of the path, as it is done in (4), can bring no optimized routes, since a path with 15 nodes can have the same energy average as a path with only 5 nodes. Therefore ΔTk must be calculated as a function of both parameters: the energy levels and the length of the path. This can be achieved by introducing the parameter F dk in the (5), which represents the number of nodes that the forward ant k has visited. The equation used to update the routing tables at each node is now changed to: ΔTk Tk (r, s) = (1 ? ρ) Tk (r, s) + (6) ?Bdk where ? is a coe?cient and Bdk is the travelled distance (the number of visited nodes), by backward ant k until node r. These two parameters will force the ant to loose part of the pheromone strength during its way to the source node. The idea behind this behaviour is to build a better pheromone distribution (nodes near the sink-node will have more pheromone levels) and will force remote nodes to ?nd better paths. Such behaviour is extremely important when the sink-node is able to move, since the pheromone adaptation will be much quicker.


Experimental Results

In this section we present the experimental results obtained for the three algorithms described in section 3: the basic ant-based routing algorithm (BABR), described in section 3.1, the improved ant-based routing algorithm (IABR), presented in section 3.2, and the energy-e?cient ant-based routing algorithm (EEABR), presented in section 3.3. The algorithms were tested using the well known ns-2 simulator [14], with the two-ray ground re?ection model. To better understand the di?erences between the three algorithms, three distinct scenarios were used, each one trying to represent real WSN deployment environments, as well as possible. On all scenarios the nodes were deployed in random fashion, since in real sensor networks the device deployment, in general, cannot be controlled by an operator due to the environment characteristics. The number of deployed sensor nodes varied between 10 and 100 nodes. In terms of


T. Camilo et al.

(a) Average Energy

(b) Minimum Energy

(c) Standard Deviation

(d) Energy E?ciency

Fig. 1. Performance in sensor network with static phenomenon

simulated area it also varied, forcing the connectivity between all nodes, from 200x200 m2 (10 nodes), 300x300 m2 (20 nodes), 400x400 m2 (30 nodes), 500x500 m2 (40 nodes) and 600x600 m2 when 50, 60, 70, 80, 90 and 100 nodes were used. For each environment four metrics were used to compare the performance of the algorithms: the Average Energy, which gives the average of energy of all nodes at the end of simulation; the Minimum Energy, which gives the lowest energy amount of all nodes; the Standard Deviation, which gives the average variance between energy levels on all nodes; and ?nally the Energy E?ciency, which gives the ratio between total consumed energy and the number of packets received by the sink-node. The ?rst scenario simulates a static WSN where the sensor nodes were randomly deployed with the objective to monitor a static phenomenon. The location of the phenomenon and the sink-node are not known. Nodes are responsible to monitor the phenomenon and send the relevant sensor data to the sink-node. In this peculiar scenario the nodes near the phenomenon will be a?ected in terms of energy consumption, since they will be forced to periodically transmit data. Figure 1 presents the results of the simulation for the studied parameters. In the majority of the scenarios (from 10 till 100 nodes) the EEABR protocol gives the best results. In Figure 1b) the minimum energy in both protocols, BABR and IABR, present a very low value when the network has 30 nodes, however in the EEABR protocol this does not happen. This behaviour is also visible in Figure 1c) where the standard deviation shows us the same distinctive values. This behaviour can be explained considering the used network topology, where there exist few communication paths from source to the sink-node.

An Energy-E?cient Ant-Based Routing Algorithm for WSNs


(a) Average Energy

(b) Minimum Energy

(c) Standard Deviation

(d) Energy E?ciency

Fig. 2. Performance in sensor network with mobile phenomenon

The results illustrated in Figure 2 correspond to the second scenario, where the phenomenon is mobile. Comparing with results from previous scenarios, the phenomenon mobility decreases the performance of the algorithm, which is understandable and expected since more nodes become sources of data packets, increasing the number of packets in the network. Once again the EEABR protocol presents the best results when compared to the others protocols, but results can easily be compared to scenarios where all environment variables are static. The ?nal study simulates a mesh sensor network. These networks are composed of several nodes with di?erent capabilities. On each network three energy levels were used: 50, 30 and 20 joules. These levels were uniformly distributed over the nodes. Figure 3 shows the simulation results. The EEABR protocol had better ?nal results compared to the previous studies. This can be explained by the adaptability of the protocol, which e?ciently tries to balance the energy levels on all nodes. This conclusion is more evident in Figure 3d). When compared with the other algorithms the EEABR presents a signi?cant reduction in relation to the standard deviation. In terms of average energy levels the EEABR always presents the best results. When compared to the IABR the di?erence between the average values varied between 3% and 10%, and when compared with BABR varied between 17% and 25%. In terms of the minimum energy of the nodes at the end of the simulation, no algorithm could avoid the existence of “dead” nodes, however BABR and IABR presented two “dead” nodes contrasting to only one presented by the EEABR protocol. This is due to the random node distribution, where only two nodes were responsible to provide connectivity between the source and the sink-node, since the phenomenon was static.


T. Camilo et al.

(a) Average Energy

(b) Minimum Energy

(c) Standard Deviation

(d) Energy E?ciency

Fig. 3. Performance in sensor network with di?erent initial energy levels

In relation to energy e?ciency, the results were very similar in all scenarios. EEABR and IABR present the best results, which are also very similar because both algorithms are energy-aware. However, in terms of the other parameters, the di?erence between both protocols became higher, meaning EEABR performance is better since it signi?cantly reduces the energy consumed in communications. On the other hand, the BABR algorithm presents the worst results for all the studied parameters, although in some cases it reaches the same values as the IABR protocol, due to the ine?ciency of the IABR in reducing the overhead in exchange messages.



In this paper we studied the application of the Ant Colony Optimization metaheuristic to solve the routing problem in wireless sensor networks. A basic antbased routing algorithm was proposed, and several improvements, inspired by the features of wireless sensor networks (low energy levels, low processing and memory capabilities), were considered and implemented. The resulting routing protocol, called Energy-E?cient Ant Based Routing (EEABR), uses “lightweight” ants to ?nd routing paths between the sensor nodes and the sink nodes, which are optimised in terms of distance and energy levels. These special ants minimise communication loads and maximise energy savings, contributing to expand the lifetime of the wireless network. The experimental results showed that the algorithm leads to very good results in di?erent WSN scenarios.

An Energy-E?cient Ant-Based Routing Algorithm for WSNs


As future work we intend to study the initialization method to populate the routing tables with initial pheromone levels. As shown in the literature [8], such mechanisms can increase even more the e?ciency of the networks. Another approach to be studied is the integration of multiple sink-nodes. Acknowledgments. The work presented in this paper is partially ?nanced by the Portuguese Foundation for Science and Technology, FCT through the 6Mnet POSI/REDES/44089/2002 project. This work has been partly supported by the European Union under the ENext FP6-506869 NoE.

1. Estrin, D., et al.: Embedded, Everywhere: A research Agenda for Network Systems of Embedded Computers, National Research Council Report, 2001 2. Handy, M., Haase, M., Timmermann, D.: Low Energy Adaptive Clustering Hierarchy with Deterministic Cluster-Head Selection, 4th IEEE International Conference on Mobile and Wireless Communications Networks, Stockholm, 2002 3. Lindsey, S., Raghavendra, C.: PEGASIS: Power E?cient GAthering in Sensor Information Systems, ICC, 2001 4. Lindsey, S., Raghavendra, C., Sivalingam, K.: Data Gathering in Sensor Networks using the EnergyDelay Metric, 2000 5. Intanagonwiwat, C., Govindan, R., Estrin, D.: Directed Di?usion: a scalable and robust communication paradigm for sensor networks, ACM Press, 2000 6. Jeon, P., Rao, R., Kesidis, G.: Two-Priority Routing in Sensor MANETs Using Both Energy and Delay Metrics, in preparation, 2004 7. Di Caro G., Dorigo M.: AntNet: Distributed Stigmergetic Control for Communications Networks, Journal of Arti?cial Intelligence Research (JAIR), Vol. 9, Pag. 317-365, 1998 8. Zhang, Y., Kuhn, L., Fromherz, M.: Improvements on Ant Routing for Sensor Networks, In: Ants 2004, Int. Workshop on Ant Colony Optimization and Swarm Intelligence, Sept. 2004 9. Singh, G., Das, S. Gosavi, S., Pujar, S.: Ant Colony Algorithms for Steiner Trees: An Application to Routing in Sensor Networks, Recent Developments in Biologically Inspired Computing, Eds. L. N. de Castro, F. J. von Zuben, Idea Group Publishing, pp. 181-206, 2004 10. Zuniga, M. Z.; Krishnamachari, B.: Integrating Future Large-Scale Wireless Sensor Networks with the Internet, Department of Electrical Engineering, UNiversity of Southern California, 2002 11. Alonso, J., Dunkels, A., Voigt. T,: Bounds on the energy consumption of routings in wireless sensor nodes, WiOpt’04: Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks, Cambridge, UK, March 2004 12. Ye, W., Heidemann, J.: Medium Access Control in Wireless Sensor Networks, in Wireless Sensor Networks, Kluwer Academic Publishers, 2004 13. Dorigo, M., St¨tzle, T.: Ant Colony Optimization, MIT Press, 2004. u 14. Network Simulator-2: http://www.isi.edu/nsnam/ns/



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

copyright ©right 2010-2021。