In multiagent surveillance missions, a group of agents monitors some points of interest to provide situational awareness. For agents with local communication capabilities, one way to transmit the surveillance information to a base is streaming by the instantaneous data via multihop communications over a connected network. However, a connected communication network may become disconnected if some agents leave the surveillance area (for example, for refueling). This paper presents a locally applicable, efficient, and scalable strategy that guarantees a connected communication network between the base and the agents in the face of any agent removal. The proposed decentralized strategy is based on a sequence of local replacements, which are initiated by the agent leaving the network. It is shown that the replacement sequence always ends with the relocation of an agent, for which the absence from its current position does not disconnect the network. Furthermore, the optimality (that is, the minimum number of r...
Maintaining connectivity against the removal of multiple agents is a more challenging problem than maintaining connectivity against multiple edge removal @cite_9 . In the last few years, there has been a significant interest in addressing agent loss problem in networked systems. In @cite_9 and @cite_2 , the main focus is on the design of robust network topologies that can tolerate a finite number of agent removals. In @cite_2 and @cite_14 , the authors propose self-repair strategies that create new connections among the neighbors of the failing agent. In addition, a connectivity maintenance strategy based on decentralized estimation of algebraic connectivity is presented in @cite_7 . Based on their estimations, agents increase or decrease their broadcast radii for satisfying connectivity requirements.
@cite_9 @cite_14 @cite_7 @cite_2
2004805323 2081257635 2023766744 2093172757
Abstract In the studies on the localization of wireless sensor networks (WSN), it has been shown that a network is in principle uniquely localizable if its underlying graph is globally rigid and there are at least d + 1 non-collinear anchors (in d -space). The high possibility of the loss of nodes or links in a typical WSN, specially mobile WSNs where the localization often needs to be repeated, enforces to not only have localizable network structures but also structures which remain localizable after the loss of multiple nodes links. The problem of characterizing robustness against the loss of multiple nodes, which is more challenging than the problem of multiple link loss, is being studied here for the first time, though there have been some results on single node loss. We provide some sufficient properties for a network to be robustly localizable. This enables us to answer the problem of how to make a given network robustly localizable. We also derive a lower bound on the number of the links such a network should have. Elaborating it to the case of robustness against the loss of up to 2 nodes, we propose the optimal network structure, in terms of the required number of distance measurements. Dissensus is a modeling framework for networks of dynamic agents in competition for scarce resources. Originally inspired by biological cell behaviors, it also fits marketing, finance and many other application areas. Competition is often unstable in the sense that strong agents, those having access to large resources, gain more and more resources at the expenses of weak agents. Thus, strong agents duplicate when reaching a critical amount of resources, whereas weak agents die when losing all their resources. To capture all these phenomena we introduce discrete time gossip systems with unstable state dynamics interrupted by discrete events affecting the network topology. Invariancy of states, topologies, and network connectivity are explored. In this article, we propose a decentralised algorithm for connectivity maintenance in a distributed sensor network. Our algorithm uses the dynamics of a consensus algorithm to estimate the connectivity of a network topology in a decentralised manner. These estimates are then used to inform a decentralised control algorithm that regulates the network connectivity to some desired level. Under certain realistic assumptions we show that the closed-loop dynamics can be described as a consensus algorithm with an input, and eventually reduces to a scalar system. Bounds are given to ensure the stability of the algorithm and examples are given to illustrate the efficacy of the proposed algorithm. In this paper, we address the problem of agent loss in vehicle formations and sensor networks via two separate approaches: (1) perform a ‘self-repair’ operation in the event of agent loss to recover desirable information architecture properties or (2) introduce robustness into the information architecture a priori such that agent loss does not destroy desirable properties. We model the information architecture as a graph G(V, E), where V is a set of vertices representing the agents and E is a set of edges representing information flow amongst the agents. We focus on two properties of the graph called rigidity and global rigidity, which are required for formation shape maintenance and sensor network self-localization, respectively. For the self-repair approach, we show that while previous results permit local repair involving only neighbours of the lost agent, the repair cannot always be implemented using only local information. We present new results that can be applied to make the local repair using only local information. We describe implementation and illustrate with algorithms and examples. For the robustness approach, we investigate the structure of graphs with the property that rigidity or global rigidity is preserved after removing any single vertex (we call the property as 2-vertex-rigidity or 2-vertex-global-rigidity, respectively). Information architectures with such properties would allow formation shape maintenance or self-localization to be performed even in the event of agent failure. We review a characterization of a class of 2-vertex-rigidity and develop a separate class, making significant strides towards a complete characterization. We also present a characterization of a class of 2-vertex-global-rigidity. Copyright © 2008 John Wiley & Sons, Ltd.