Agent-based sensor coalition formation

Large numbers of heterogeneous sensors the collect and fuse information in dynamic environments are envisioned in domains, such as military operations, disaster response or border surveillance. Depending on the dynamically evolving needs, operators will submit to groups of these sensors information acquisition and fusion goals that must be fulfilled within time constraints. To fulfill these goals, the sensors must autonomously and dynamically form coalitions. The problem that this paper addresses is the dynamic coalition formation problem and the evolving performance of coalitions over time. Coalition formation is an NP complete problem. One of the ways to mitigate the computational cost is to constrain the decentralized coalition formation problem by taking into consideration the underlying network structure. Has showed (a) that the network topology has a significant effect on the quality of the formed coalitions and their performance, and (b) that it is possible to develop agents that intelligently adapt the network structure to increase the ability of the organization to form good quality coalitions. However, that work used unrealistically simple coalitional models and did not perform an analysis of the network topologies and adaptation policies that could result. In this paper we make three contributions. First we present an analysis and results on the underlying network topologies that are formed. Second, we develop and analyze a more realistic coalition formation model. Third we present two new network adaptation policies. Experimental evaluation of our contributions are presented.