Wireless Sensor and Actuator Networks: Algorithms and Protocols for Scalable Coordination and Data Communication

7.5 SPANNING TREES IN UNCONTROLLED DYNAMIC TOPOLOGIES

The discussion below addresses the scenarios where sensors are to move in an uncontrolled fashion, which is for example the case when they are carried by some physical actors of the considered scene (e.g., animals, vehicles, virtual insects, or robots whose movements are to be determined by external parameters). The problem of maintaining distributed spanning trees over dynamic topologies has been extensively studied these past few decades, especially in the two research areas of dynamic graphs and mobile ad hoc networks. To the best of our knowledge, a vast majority of approaches, if not all of them, considered the problem of building a single spanning tree to cover the whole network. Generally, tackled from the angle of self-stabilization, these approaches consider topological events as faults that induce a nonlegal state, which the algorithm must correct. The correction is then achieved when the whole network is covered by a single tree, which is the legal state. To give a few references on this family of approaches, one can cite the distributed graph algorithm in Awerbuch et al. (1993), which exhibits the shortest construction time “from scratch” [recently adapted to the message passing model in Burman and Kutten (2007)], and Gaertner (2003) that describes a number of comparable approaches.

While most proposed algorithms engage a complete reconstruction of the tree after each topological failure, some other more realistic ...