10.4 SENSOR PLACEMENT BY ACTUATORS
Till the time of this writing, only a few algorithms (Batalin and Sukhatme, 2005; Chang et al., 2007; Fletcher et al., 2009) were proposed to address how to deploy sensors by actuators. In this section these algorithms are reviewed in detail.
10.4.1 Least Recently Visited Approach
Batalin and Sukhatme (2005) presented a single-actuator-based sensor placement algorithm LRV (least recently visited), which assumes equal sensing and communication radii and guides actuator movement according to the suggestion of previously deployed sensors. The algorithm starts with an empty environment. At initiation, the actuator (robot) deploys a node at its current position. Each deployed sensor maintains a set of directions along which the robot can move away from it. Directions could follow a graph structure (e.g., tree) or could be predefined (e.g., four geographical directions). It also assigns a weight, initially equal to 0, to each direction, indicating the number of times that direction was traversed by the actuator.
Every sensor recommends its locally LRV direction to the actuator by message when the actuator is in its communication range. Directions are preordered so that a single direction is recommended in case of a tie. The actuator travels a predefined distance in recommended direction. If, however, the chosen direction is obstructed, it will inform the recommender and ask for a new suggested direction. Whenever the actuator departs or arrives, its ...