Abstract
Clustering is a crucial network design approach to enable large-scale wireless sensor networks (WSNs) deployments. A large variety of clustering approaches has been presented focusing on various aspect such as minimizing communication overhead, controlling the network topology etc. Simulations on such protocols are performed using theoretical models that are based on unrealistic assumptions like ideal wireless communication channels and perfect energy consumption estimations. With these assumptions taken for granted, theoretical models claim various performance milestones that cannot be achieved in realistic conditions. In this paper, we design a new clustering protocol that adapts to the changes in the environment and the needs and goals of the user applications. We provide a protocol that is deployable protocol in real WSNs. We apply our protocol in multiple indoors wireless sensor testbeds with multiple experimental scenarios to showcase scalability and trade-offs between network properties and configurable protocol parameters. By analysis of the real world experimental output, we present results that depict a more realistic view of the clustering problem, regarding adapting to environmental conditions and the quality of topology control. Our study clearly demonstrates the applicability of our approach and the benefits it offers to both research & development communities.
This work has been partially supported by the European Union under contract numbers ICT-2008-215270 (FRONTS) and ICT-2010-258885 (SPITFIRE).
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.
Similar content being viewed by others
References
Abbasi, A.A., Younis, M.: A survey on clustering algorithms for wireless sensor networks. Comput. Commun. 30(14-15), 2826–2841 (2007)
Afek, Y., Dolev, S.: Local stabilizer. Journal of Parallel and Distributed Computing, Special Issue on Self-Stabilizing Distributed Systems 62(5), 745–765 (1997)
Anceaume, E., Défago, X., Gradinariu, M., Roy, M.: Towards a Theory of Self-organization. In: Anderson, J.H., Prencipe, G., Wattenhofer, R. (eds.) OPODIS 2005. LNCS, vol. 3974, pp. 191–205. Springer, Heidelberg (2006)
Baker, D., Ephremides, A.: The architectural organization of a mobile radio network via a distributed algorithm. IEEE Transactions on Communications 29(11), 1694–1701 (1981)
Baker, D.J., Ephremides, A.: A distributed algorithm for organizing mobile radio telecommunication networks. In: ICDCS, pp. 476–483. IEEE Computer Society (1981)
Bandyopadhyay, S., Coyle, E.J.: An energy efficient hierarchical clustering algorithm for wireless sensor networks. In: INFOCOM (2003)
Banerjee, S., Khuller, S.: A clustering scheme for hierarchical control in multi-hop wireless networks. In: INFOCOM, pp. 1028–1037 (2001)
Baumgartner, T., Chatzigiannakis, I., Fekete, S.P., Koninis, C., Kröller, A., Pyrgelis, A.: Wiselib: A Generic Algorithm Library for Heterogeneous Sensor Networks. In: Silva, J.S., Krishnamachari, B., Boavida, F. (eds.) EWSN 2010. LNCS, vol. 5970, pp. 162–177. Springer, Heidelberg (2010)
Chatterjee, M., Das, S.K., Turgut, D.: Wca: A weighted clustering algorithm for mobile ad hoc networks. Cluster Computing 5(2), 193–204 (2002)
Chatzigiannakis, I., Fischer, S., Koninis, C., Mylonas, G., Pfisterer, D.: WISEBED: An Open Large-Scale Wireless Sensor Network Testbed. In: Komninos, N. (ed.) SENSAPPEAL 2009. LNICST, vol. 29, pp. 68–87. Springer, Heidelberg (2010)
Chen, Y.P., Liestman, A., Liu, J.: Clustering algorithms for ad hoc wireless networks. Ad Hoc and Sensor Networks 30, 2826–2841 (2007)
Citysense - An Open, Urban-Scale Sensor Network Testbed, http://www.citysense.net/
Cournier, A., Datta, A., Petit, F., Villain, V.: Enabling snap-stabilization. In: Proc. of the 23rd International Conference on Distributed Computing Systems, pp. 12–19 (2003)
Ding, P., Holliday, J., Celik, A.: Distributed Energy-Efficient Hierarchical Clustering for Wireless Sensor Networks. In: Prasanna, V.K., Iyengar, S.S., Spirakis, P.G., Welsh, M. (eds.) DCOSS 2005. LNCS, vol. 3560, pp. 322–339. Springer, Heidelberg (2005)
Dolev, S., Tzachar, N.: Empire of colonies: Self-stabilizing and self-organizing distributed algorithm. Theoretical Computer Science 410, 514–532 (2008); FRONTS-TR-2008-22
Fekete, S.P., Kröller, A., Fischer, S., Pfisterer, D.: Shawn: The fast, highly customizable sensor network simulator. In: Proceedings of the Fourth International Conference on Networked Sensing Systems, INSS 2007 (2007)
Hay, S., Harle, R.: Bluetooth Tracking without Discoverability. In: Choudhury, T., Quigley, A., Strang, T., Suginuma, K. (eds.) LoCA 2009. LNCS, vol. 5561, pp. 120–137. Springer, Heidelberg (2009)
Heinzelman, W.R., Chandrakasan, A.P., Balakrishnan, H.: Energy-efficient communication protocol for wireless microsensor networks. In: 33rd IEEE Hawaii International Conference on System Sciences (HICSS 2000), p. 8020 (2000)
Iwanicki, K., van Steen, M.: Multi-hop Cluster Hierarchy Maintenance in Wireless Sensor Networks: A Case for Gossip-Based Protocols. In: Roedig, U., Sreenan, C.J. (eds.) EWSN 2009. LNCS, vol. 5432, pp. 102–117. Springer, Heidelberg (2009)
Iwanicki, K., van Steen, M.: On hierarchical routing in wireless sensor networks. In: Proceedings of the Eighth ACM/IEEE International Conference on Information Processing in Sensor Networks (IPSN 2009), IP Track, San Francisco, CA, USA, pp. 133–144 (April 2009)
Jiang, C., Yuan, D., Zhao, Y.: Towards clustering algorithms in wireless sensor networks: a survey. In: WCNC 2009: Proceedings of the 2009 IEEE Conference on Wireless Communications & Networking Conference, pp. 2009–2014. IEEE Press, Piscataway (2009)
Karl, H., Willig, A.: Protocols and Architectures for Wireless Sensor Networks. John Wiley & Sons (2005)
Katz, S., Perry, K.: Self-stabilizing extensions for message-passing systems. In: Proceedings of the Ninth Annual ACM Symposium on Principles of Distributed Computing, pp. 91–101 (1990)
Levis, P., Lee, N., Welsh, M., Culler, D.: TOSSIM: Accurate and scalable simulation of entire tinyos applications. In: 1st ACM International Conference on Embedded Networked Sensor Systems (SENSYS 2003), pp. 126–137 (2003)
Mamalis, B., Gavalas, D., Konstantopoulos, C., Pantziou, G.: RFID and Sensor Networks: Architectures, Protocols, Security and Integrations. In: Clustering in Wireless Sensor Networks. Taylor & Francis Group (2009)
Moscibroda, T., Wattenhofer, R.: Maximal independent sets in radio networks. In: PODC 2005: Proceedings of the Twenty-Fourth Annual ACM Symposium on Principles of Distributed Computing, pp. 148–157. ACM, New York (2005)
Parekh, A.: Selecting routers in ad hoc wireless networks. In: Proccedings of ITS, Rio-de-Janeiro, Brazil, pp. 420–424 (1994)
Selvakennedy, S., Sinnappan, S.: An adaptive data dissemination strategy for wireless sensor networks. IJDSN 3(1), 23–40 (2007)
SmartSantander - A unique in the world city-scale experimental research facility, http://www.smartsantander.eu/
Varghese, G.: Self-stabilization by counter flushing. SIAM Journal on Computing 30(2), 486–510 (2000)
Ye, M., Li, C., Chen, G., Wu, J.: An energy efficient clustering scheme in wireless sensor networks. Ad Hoc & Sensor Wireless Networks 3(2-3), 99–119 (2007)
Younis, O., Fahmy, S.: Heed: A hybrid, energy-efficient, distributed clustering approach for ad hoc sensor networks. IEEE Trans. Mob. Comput. 3(4), 366–379 (2004)
Younis, O., Fahmy, S.: An experimental study of routing and data aggregation in sensor networks. In: Proceedings of the IEEE International Workshop on Localized Communication and Topology Protocols for Ad Hoc Networks (IEEE LOCAN), pp. 50–57 (2005)
Youssef, A.M., Younis, M.F., Youssef, M., Agrawala, A.K.: Distributed formation of overlapping multi-hop clusters in wireless sensor networks. In: GLOBECOM. IEEE (2006)
Zhang, H., Arora, A.: Gs3: Scalable self-configuration and self-healing in wireless networks. In: Symposium on Principles of Distributed Computing, pp. 58–67 (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 ICST Institute for Computer Sciences, Social Informatics and Telecommunications Engineering
About this paper
Cite this paper
Amaxilatis, D., Chatzigiannakis, I., Dolev, S., Koninis, C., Pyrgelis, A., Spirakis, P.G. (2012). Adaptive Hierarchical Network Structures for Wireless Sensor Networks. In: Simplot-Ryl, D., Dias de Amorim, M., Giordano, S., Helmy, A. (eds) Ad Hoc Networks. ADHOCNETS 2011. Lecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering, vol 89. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-29096-1_5
Download citation
DOI: https://doi.org/10.1007/978-3-642-29096-1_5
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-29095-4
Online ISBN: 978-3-642-29096-1
eBook Packages: Computer ScienceComputer Science (R0)