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

8.4 FLOODING-BASED ALGORITHMS

In this section, five representative flooding-based location service algorithms have been reviewed: doubling circle update (Amouris et al., 1999), direction-based update (Friedman and Korland, 2005), localized update (Yang et al., 2009), request zone search (Stojmenovic et al., 2003, 2006), and expanding ring search (Kasemann et al., 2002). The first three schemes belong to proactive category, while the last two belong to reactive category.

8.4.1 Doubling Circle Update

Amouris et al. (1999) presented a doubling circle location update scheme. In this scheme, each actuator propagates its location information within circles C(i) of increasing radii 2ⁱ R for i = 1, 2, 3, … Each of these circles is associated with a refreshment timer. Whenever the timer expires (time-based policy), the actuator broadcasts a location update message within the corresponding circle. In addition, whenever the actuator moves outside a circle C(t) for some t (distance-based policy), it broadcasts its location to all the nodes located within a circle of radius 2^t+1 R centered at its current position.

Actuator search (or direct routing to it) then follows these circles of last updates. Sensors (source or intermediate sensors) forward a search message toward the last reported position of target actuator, which since the last report may have moved within the circle of some radius. As the message moves closer to target actuator, its position information becomes more precise, and sensors ...