Observations on non-silent self-stabilizing algorithms in sensor networks with probabilistically intermittent link failures

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 Sensor-net 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. (C) 2010 Elsevier B.V. All rights reserved.