Distributed Sensor Networks

The problem of group decision making in a non-strategic environment is presented and analyzed. The main focus is on the decision problem of task assignment in situations in which tasks interact and information relevant to the assignment problem is distributed and is contained locally in the agents in the group. Practically, it may be impossible to communicate all relevant distributed information to a single central decision maker due to communication costs, the size of the set of information, or other limitations. Instead, we provide a method to coordinate the sharing of a limited amount of information while making satisfactory (though possibly suboptimal) task assignments via a center-based algorithm called Mediation. Mediation implements an iterative and interactive hill-climbing search in a subset of the solution space by making successive proposals and sending those proposals to the group. Each proposal provides a context on which group members base their responses which provide the mediator with information to find a satisfactory outcome to the assignment problem. The properties of Mediation are compared with other approaches including parallel and combinatorial auctions. The theory and analysis is illustrated with examples from the domain of multi-sensor intruder tracking. Dynamic mediation extends the algorithm to environments in which problem features change during the decision-making process and in which agents augment the information that they provide using the language of rich bids. Experiments are used to validate the usefulness of mediation in key problem domains, including multi-sensor tracking. Finally, an architecture for agents, who need not be stationary, is described whereby agents can monitor task progress at execution time and then modify existing resource allocations based on the evolving situation.

Distributed resource allocation, where a set of agents must assign their resources to a set of dynamic tasks, is a challenging, open problem in current multi-agent systems research. In this article, we present three advances in addressing distributed resource allocation. First, we propose a systematic formalization of the problem and a general solution strategy that maps a formal model of resource allocation into a key problem solving paradigm, namely, distributed constraint-based reasoning (DCR). Such formalizations are necessary to understand the complexity of different types of problems and to develop solution strategies that translate across domains. Second, we present a new algorithm for distributed constraint-based reasoning, called Adopt. Adopt has several novel characteristics necessary for addressing distributed resource allocation including the ability to deal with both soft and hard constraints. Finally, we investigate how our theoretical results and algorithm (developed on abstract problems), can be applied to the real-world resource allocation problem of target tracking in distributed sensor networks. In particular, we introduce a two-layered architecture, where the higher layer uses the DCR algorithm, while a lower layer uses a probabilistic representation of resources and tasks to deal with uncertainty and dynamics.

We introduce SensorDCSP, a naturally distributed benchmark based on a real-world application that arises in the context of networked distributed systems. In order to study the performance of Distributed CSP (DisCSP) algorithms in a truly distributed setting, we use a discrete-event network simulator, which allows us to model the impact of different network traffic conditions on the performance of the algorithms. We consider two complete DisCSP algorithms: asynchronous backtracking (ABT) and asynchronous weak-commitment search (AWC). In our study of different network traffic distributions, we found that random delays, in some cases combined with a dynamic decentralized restart strategy, can improve the performance of DisCSP algorithms. More interestingly, we also found that the active introduction of message delays by agents can improve performance and robustness while reducing the overall network load. Finally, our work confirms that AWC performs better than ABT on satisfiable instances. On unsatis-fiable instances, however, the performance of AWC is considerably worse than ABT.