Simulated Annealing Algorithm for Data Aggregation Trees in Wireless Sensor Networks and Comparison with Genetic Algorithm

In ad hoc networks, the main issue about designing of protocols is quality of service, so that in wireless sensor networks the main constraint in designing protocols is limited energy of sensors. In fact, protocols which minimize the power consumption in sensors are more considered in wireless sensor networks. One approach of reducing energy consumption in wireless sensor networks is to reduce the number of packages that are transmitted in network. The technique of collecting data that combines related data and prevent transmission of additional packages in network can be effective in the reducing of transmitted packages- number. According to this fact that information processing consumes less power than information transmitting, Data Aggregation has great importance and because of this fact this technique is used in many protocols [5]. One of the Data Aggregation techniques is to use Data Aggregation tree. But finding one optimum Data Aggregation tree to collect data in networks with one sink is a NP-hard problem. In the Data Aggregation technique, related information packages are combined in intermediate nodes and form one package. So the number of packages which are transmitted in network reduces and therefore, less energy will be consumed that at last results in improvement of longevity of network. Heuristic methods are used in order to solve the NP-hard problem that one of these optimization methods is to solve Simulated Annealing problems. In this article, we will propose new method in order to build data collection tree in wireless sensor networks by using Simulated Annealing algorithm and we will evaluate its efficiency whit Genetic Algorithm.

• Ladan Darougaran
• Hossein Shahinzadeh
• Hajar Ghotb
• Leila Ramezanpour

• Data aggregation
• wireless sensor networks
• energy efficiency
• simulated annealing algorithm
• genetic algorithm.

[1] Akyildiz I. F., W. Su, Y. Sankarasubramaniam, E. Cayirci.,"Wireless
sensornetworks: a survey", Journal of Computer Networks
March 2002, pp.393-422.
[2] Katz R. H., J. M. Kahn and K. S. J. Pister, "Mobile Networking for
Smart Dust", Proc. of the 5th Annual ACM/IEEE International
Conference on Mobile Computing and Networking
Seattle, USA, Aug. 1999, pp. 350
[3] Manjeshwar A. and D. P. Agarwal, "TEEN: A Routing Protocol for
Enhanced Efficiency in Wireless Sensor Networks",
IPDPS, San Francisco, USA, Apr. 2001, pp 23
[4] Rabaey J. M., M. J. Ammer, J. L. da Silva, D. Patel and S. Roundry,
"PicoRadio supports ad hoc ultra
Computer Magazine, Vol. 33, Jul. 2000, pp. 42
[5] Krishanamachari B., D. Estrin, S. Wicker, "Modeling Data Centric
Routing in Wireless Sensor Networks",
New York, USA, Jun. 2002.
[6] Metropolis, N., Rosenbluth, A.W., Rosenbluth, M.N., Teller, A.H.,
Teller, E. 1953. Equation of State Calculation by Fast Computing
Machines. J. of Chem. Phys., 21, 1087
[7] Luo H, Liu Y, Das SK. Routing correlated data with fusion cost in
wireless sensor networks.
2006;5(11):1620-32.
[8] Li D, Cao J, Liu M, Zheng Y. Construction of optimal data aggregation
trees for wireless sensor networks. In: International Conference on
Computer Communications and Networks (ICCCN), 2006.
[9] Dorigo M, Gambardella LM. Ant colony system: a cooperative learning
approach to the traveling salesman problem. IEEE Trans. Evol. Comput.
1997;1(1):53-66.
[10] Chen G, Guo T-D, Yang W-G, Zhao T. An improved ant-based routing
protocol in wireless sensor networks. In: International Conference on
Collaborative Computing: Networking, Applications and Worksharing
(CollaborateCom), 2006.
[11] Intanagonwiwat C, Govindan R, Estrin D, Heidemann J, Silva F.
Directed diffusion for wireless sensor networking. IEEE/ACM Trans.
Networking 2003;11(1):2-16.
[12] Misra R, Mandal C. Ant-aggregation: ant colony algorithm for optimal
data aggregation in wireless sensor networks. In: International
Conference on Wireless and Optical Communications Networks, 2006.
[13] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, "Optimization by
simulated annealing," Journal of Science, vol. 220, no.4598, May 1983
pp.671-680