Abstract
Wireless Sensor Networks (WSNs) are widely adopted for applications ranging from surveillance to environmental monitoring. While powerful and relatively inexpensive, they are subject to behavioural faults which make them unreliable. Due to the complex interactions between network nodes, it is difficult to uncover faults in a WSN by resorting to formal techniques for verification and analysis, or to testing. This paper proposes an evolutionary framework to detect anomalous behaviour related to energy consumption in WSN routing protocols. Given a collection protocol, the framework creates candidate topologies and evaluates them through simulation on the basis of metrics measuring the radio activity on nodes. Experimental results using the standard Collection Tree Protocol show that the proposed approach is able to unveil topologies plagued by excessive energy depletion over one or more nodes, and thus could be used as an offline debugging tool to understand and correct the issues before network deployment and during the development of new protocols.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
Barrenetxea, G., Ingelrest, F., Schaefer, G., Vetterli, M.: The hitchhiker’s guide to successful wireless sensor network deployments. In: Proc. 6th ACM Conference on Embedded Network Sensor Systems, SenSys 2008, pp. 43–56. ACM (2008)
Bucur, D., Kwiatkowska, M.: On software verification for sensor nodes. Journal of Systems and Software 84(10), 1693–1707 (2011)
D’Silva, V., Kroening, D., Weissenbacher, G.: A survey of automated techniques for formal software verification. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 27(7), 1165–1178 (2008)
Gandini, S., Ruzzarin, W., Sanchez, E., Squillero, G., Tonda, A.: A framework for automated detection of power-related software errors in industrial verification processes. Journal of Electronic Testing 26(6), 689–697 (2010)
Gnawali, O., Fonseca, R., Jamieson, K., Moss, D., Levis, P.: Collection tree protocol. In: Proceedings of the 7th ACM Conference on Embedded Networked Sensor Systems, SenSys 2009, pp. 1–14. ACM, New York (2009)
Jurdak, R., Wang, X.R., Obst, O., Valencia, P.: Wireless Sensor Network Anomalies: Diagnosis and Detection Strategies. In: Tolk, A., Jain, L.C. (eds.) Intelligence-Based Systems Engineering. ISRL, vol. 10, ch. 12, pp. 309–325. Springer, Heidelberg (2011)
Langendoen, K., Baggio, A., Visser, O.: Murphy loves potatoes: experiences from a pilot sensor network deployment in precision agriculture. In: Proc. Int. Conf. on Parallel and Distributed Processing, pp. 174–181. IEEE Computer Society (2006)
Lee, H., Cerpa, A., Levis, P.: Improving wireless simulation through noise modeling. In: Proceedings of the 6th International Conference on Information Processing in Sensor Networks, IPSN 2007, pp. 21–30. ACM, New York (2007)
Levis, P., Gay, D., Handziski, V., Hauer, J.H., Greenstein, B., Turon, M., Hui, J., Klues, K., Sharp, C., Szewczyk, R., Polastre, J., Buonadonna, P., Nachman, L., Tolle, G., Culler, D., Wolisz, A.: T2: A second generation OS for embedded sensor networks. Tech. Rep. TKN-05-007, Technische Universität Berlin (2005)
Levis, P., Lee, N., Welsh, M., Culler, D.E.: TOSSIM: Accurate and scalable simulation of entire TinyOS applications. In: Proceedings of the ACM Conference on Embedded Networked Sensor Systems (SenSys), pp. 126–137 (2003)
Li, P., Regehr, J.: T-Check: bug finding for sensor networks. In: Proceedings of the 9th International Conference on Information Processing in Sensor Networks (IPSN), pp. 174–185. ACM (2010)
Mottola, L., Voigt, T., Österlind, F., Eriksson, J., Baresi, L., Ghezzi, C.: Anquiro: Enabling efficient static verification of sensor network software. In: Workshop on Software Engineering for Sensor Network Applications (SESENA) ICSE(2) (2010)
Sacco, G., Barltrop, K., Lee, C., Horvath, G., Terrile, R., Lee, S.: Application of genetic algorithm for flight system verification and validation. In: Aerospace Conference, pp. 1–7. IEEE (2009)
Sanchez, E., Schillaci, M., Squillero, G.: Evolutionary Optimization: the μGP toolkit, 1st edn. Springer Publishing Company, Incorporated (2011)
Sasnauskas, R., Landsiedel, O., Alizai, M.H., Weise, C., Kowalewski, S., Wehrle, K.: KleeNet: discovering insidious interaction bugs in wireless sensor networks before deployment. In: Proceedings of the 9th ACM/IEEE International Conference on Information Processing in Sensor Networks (IPSN), pp. 186–196. ACM (2010)
Shyang, W., Lakos, C., Michalewicz, Z., Schellenberg, S.: Experiments in applying evolutionary algorithms to software verification. In: IEEE World Congress on Computational Intelligence (CEC), pp. 3531–3536. IEEE (2008)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bucur, D., Iacca, G., Squillero, G., Tonda, A. (2013). An Evolutionary Framework for Routing Protocol Analysis in Wireless Sensor Networks. In: Esparcia-Alcázar, A.I. (eds) Applications of Evolutionary Computation. EvoApplications 2013. Lecture Notes in Computer Science, vol 7835. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-37192-9_1
Download citation
DOI: https://doi.org/10.1007/978-3-642-37192-9_1
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-37191-2
Online ISBN: 978-3-642-37192-9
eBook Packages: Computer ScienceComputer Science (R0)