Keith Decker, Victor Lesser
This paper presents a simple, fast coordination algorithm for the dynamic reorganization of agents in a distributed sensor network. Dynamic reorganization is a technique for adapting to the current local problem-solving situation that can both increase expected system performance and decrease the variance in performance. We compare our dynamic organization algorithm to a static algorithm with lower overhead. 'One-shot' refers to the fact that the algorithm only uses one meta-level communication action. The other theme of this paper is our methodology for analyzing complex control and coordination issues without resorting to a handful of single-instance examples. Using a general model that we have developed of distributed sensor network environments [Decker and Lesser, 1993a], we present probabilistic performance bounds for our algorithm given any number of agents in any environment that fits our assumptions. This model also allows us to predict exactly in what situations and environments the performance benefits of dynamic reorganization outweigh the overhead.