Back to Search
Start Over
Observations on non-silent self-stabilizing algorithms in sensor networks with probabilistically intermittent link failures
- Source :
-
Theoretical Computer Science . Jul2011, Vol. 412 Issue 33, p4336-4349. 14p. - Publication Year :
- 2011
-
Abstract
- Abstract: A wireless sensor network is a set of nodes, each is equipped with a sensing device and a wireless communication device. Because centralized control is hard to achieve in a large scale sensor network, self- is a key concept in the design of a wireless sensor network. Self-stabilization is one of the self- properties, and it is one of the most promising theoretical backgrounds for self-organizing wireless sensor network protocols. Herman [T. Herman, Models of self-stabilization and sensor networks, in: Proceedings of the 5th International Workshop of Distributed Computing, IWDC, 2003, pp. 205–214] proposed Cached Sensornet Transform (CST for short) for design and implementation of self-stabilizing algorithms for sensor networks. It transforms a self-stabilizing algorithm in a high-level computational model to a program for sensor networks. Our contribution in this paper is threefold. We show that there exists a non-silent algorithm that behaves correctly in a high-level computational model but its transformed version by CST does not behave correctly if packets are lost. We show a sufficient condition for original algorithms and networks such that the algorithm transformed by CST behaves correctly. As a case study, we present a token circulation algorithm that behaves correctly by CST and derive the upper bound of its expected convergence time. [Copyright &y& Elsevier]
Details
- Language :
- English
- ISSN :
- 03043975
- Volume :
- 412
- Issue :
- 33
- Database :
- Academic Search Index
- Journal :
- Theoretical Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 61921808
- Full Text :
- https://doi.org/10.1016/j.tcs.2010.11.013