Abstract
Wireless sensor networks (WSNs) pose challenges not pre- sent in classical distributed systems: resource limitations, high failure rates, and ad hoc deployment. The lossy nature of wireless communication can lead to situations, where nodes lose synchrony and programs reach arbitrary states. Traditional approaches to fault tolerance like replication or global resets are not feasible. In this work, the concept of self-stabilization is applied to WSNs. The majority of self-stabilizing algorithms found in the literature is based on models not suitable for WSNs: shared memory model, central daemon scheduler, unique processor identifiers, and atomicity. This paper proposes problem-independent transformations for algorithms that stabilize under the central daemon scheduler such that they meet the demands of a WSN. The transformed algorithms use randomization and are probabilistically self-stabilizing. This work allows to utilize many known self-stabilizing algorithms in WSNs. The proposed transformations are evaluated using simulations and a real WSN.
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
Turau, V., Weyer, C., Witt, M.: Analysis of a Real Multi-hop Sensor Network Deployment: The Heathland Experiment. In: 3rd Int. Conf. on Networked Sensing Systems (INSS 2006), pp. 6–13 (2006)
Dijkstra, E.: Self stabilizing systems in spite of distributed control. Communications of the ACM 17(11), 643–644 (1974)
Dolev, S.: Self-Stabilization. MIT Press, Cambridge (2000)
Schneider, M.: Self-stabilization. ACM Comput. Surv. 25(1), 45–67 (1993)
Gradinariu, M., Tixeuil, S.: Self-stabilizing vertex coloration and arbitrary graphs. In: Butelle, F. (ed.) OPODIS, pp. 55–70 (2000)
Karaata, M.: A self-stabilizing algorithm for finding articulation points. Theoretical and Mathematical Aspects of Computer Science 10(1), 33–46 (1999)
Goddard, W., Hedetniemi, S.T., Jacobs, D.P., Srimani, P.K.: A self-stabilizing distributed algorithm for minimal total domination in an arbitrary system graph. In: IPDPS, pp. 240–243. IEEE Computer Society, Los Alamitos (2003)
Chaudhuri, P.: A self-stabilizing algorithm for minimum-depth search of graphs. Information Sciences 118(1-4), 241–249 (1999)
Higham, L., Liang, Z.: Self-stabilizing minimum spanning tree construction on message-passing networks. In: Welch, J.L. (ed.) DISC 2001. LNCS, vol. 2180, pp. 194–208. Springer, Heidelberg (2001)
Beauquier, J., Datta, A.K., Gradinariu, M., Magniette, F.: Self-stabilizing local mutual exclusion and daemon refinement. Chicago Journal of Theoretical Computer Science 2002(1) (2002)
Shukla, S., Rosenkrantz, D., Ravi, S.: Observations on self-stabilizing graph algorithms for anonymous networks. In: 2nd Workshop on Self-Stabilizing Systems, pp. 7.1–7.15 (1995)
Mizuno, M., Nesterenko, M.: A transformation of self-stabilizing serial model programs for asynchronous parallel computing environments. Inf. Process. Lett. 66(6), 285–290 (1998)
Herman, T.: Models of self-stabilization and sensor networks. In: IWDC 2003. LNCS, vol. 2918, pp. 205–214. Springer, Heidelberg (2003)
Hedetniemi, S., Hedetniemi, S., Jacobs, D., Srimani, P.: Self-stabilizing algorithms for minimal dominating sets and maximal independent sets. Comput. Math. Appl. 46(5–6), 805–811 (2003)
Römer, K., Blum, P., Meier, L.: Time synchronization and calibration in wireless sensor networks. In: Stojmenovic, I. (ed.) Handbook of Sensor Networks: Algorithms and Architectures, pp. 199–237. John Wiley & Sons, Chichester (2005)
ScatterWeb (2006), http://www.scatterweb.net
Kulkarni, S.S., Arumugam, M.U.: Transformations for Write-All-with-Collision Model. In: Papatriantafilou, M., Hunel, P. (eds.) OPODIS 2003. LNCS, vol. 3144, pp. 184–197. Springer, Heidelberg (2004)
Herman, T., Tixeuil, S.: A Distributed TDMA Slot Assignment Algorithm for Wireless Sensor Networks. In: Nikoletseas, S.E., Rolim, J.D.P. (eds.) ALGOSENSORS 2004. LNCS, vol. 3121, pp. 45–58. Springer, Heidelberg (2004)
Frank, C., Römer, K.: Algorithms for generic role assignment in wireless sensor networks. In: 3rd ACM Conf. on Embedded Networked Sensor Systems (2005)
Kakugawa, H., Mizuno, M., Nesterenko, M.: Development of self-stabilizing distributed algorithms using transformation: case studies. In: 3rd Workshop on Self-Stabilizing Systems, pp. 16–30 (1997)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Turau, V., Weyer, C. (2006). Randomized Self-stabilizing Algorithms for Wireless Sensor Networks. In: de Meer, H., Sterbenz, J.P.G. (eds) Self-Organizing Systems. EuroNGI IWSOS 2006 2006. Lecture Notes in Computer Science, vol 4124. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11822035_8
Download citation
DOI: https://doi.org/10.1007/11822035_8
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-37658-3
Online ISBN: 978-3-540-37669-9
eBook Packages: Computer ScienceComputer Science (R0)