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

Authors: Ladan Darougaran, Hossein Shahinzadeh, Hajar Ghotb, Leila Ramezanpour

Abstract:

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.

Keywords: Data aggregation, wireless sensor networks, energy efficiency, simulated annealing algorithm, genetic algorithm.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1333110

References:

[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