Academic literature on the topic 'Average consensus algorithm'

The existing distributed spectrum sensing algorithms usually assume that the information in interaction channel is totally correct and did not consider noise effect. To solve these problems, a new distributed cooperative spectrum sensing scheme based on average consensus is investigated in this paper. Based on minimum mean square deviation criterion, we design an iterative matrix suitable for consensus algorithm with considering the noise of interaction channel. Simulation results show that the proposed method achieves better detection performance under noise effect of interaction channel and outperforms conventional scheme by 11% at-5dB signal to noise ratio (SNR) and 0.1 false alarm probability.

The convergence accuracy of distributed consensus with quantization communication depends on the quantization error and the convergence rate of the distributed consensus algorithm. In order to improve the accuracy and the convergence rate of distributed consensus under quantized communication, in the paper, based on the adaptively quantized scheme, we propose the pseudo multi-hop adaptively quantized distributed consensus algorithm. We analyze the convergence performance of the pseudo multi-hop adaptively quantized distributed consensus algorithm, and the algorithm can achieves a consensus in a mean square sense. Simultaneously, Simulations are present. Results show that the pseudo multi-hop adaptively quantized distributed consensus algorithm can reach an average consensus, and its convergence rate is higher than those of the other adaptive quantized distributed consensus algorithms.

The paper is concerned with the consensus problem in a multi-agent system such that each agent has boundary constraints. Classical Olfati-Saber’s consensus algorithm converges to the same value of the consensus variable, and all the agents reach the same value. These algorithms find an equality solution. However, what happens when this equality solution is out of the range of some of the agents? In this case, this solution is not adequate for the proposed problem. In this paper, we propose a new kind of algorithms called supportive consensus where some agents of the network can compensate for the lack of capacity of other agents to reach the average value, and so obtain an acceptable solution for the proposed problem. Supportive consensus finds an equity solution. In the rest of the paper, we define the supportive consensus, analyze and demonstrate the network’s capacity to compensate out of boundaries agents, propose different supportive consensus algorithms, and finally, provide some simulations to show the performance of the proposed algorithms.

The average consensus problem of distributed inference in a wireless sensor network under Markovian communication topology of uncertain transition probability is studied. A sufficient condition for average consensus of linear distributed inference algorithm is presented. Based on linear matrix inequalities and numerical optimization, a design method of fast distributed inference is provided.

A significant progress in the evolution of the computer systems and their interconnection over the past 70 years has allowed replacing the frequently used centralized architectures with the highly distributed ones, formed by independent entities fulfilling specific functionalities as one user-intransparent unit. This has resulted in an intense scientic interest in distributed algorithms and their frequent implementation into real systems. Especially, distributed algorithms for multi-sensor data fusion, ensuring an enhanced QoS of executed applications, find a wide usage. This doctoral thesis addresses an optimization and an analysis of the distributed systems, namely the distributed consensus-based algorithms for an aggregate function estimation (primarily, my attention is focused on a mean estimation). The first section is concerned with a theoretical background of the distributed systems, their evolution, their architectures, and a comparison with the centralized systems (i.e. their advantages/disadvantages). The second chapter deals with multi-sensor data fusion, its application, the classification of the distributed estimation techniques, their mathematical modeling, and frequently quoted algorithms for distributed averaging (e.g. protocol Push-Sum, Metropolis-Hastings weights, Best Constant weights etc.). The practical part is focused on mechanisms for an optimization of the distributed systems, the proposal of novel algorithms and complements for the distributed systems, their analysis, and comparative studies in terms of such as the convergence rate, the estimation precision, the robustness, the applicability to real systems etc.

L’avènement de composants électroniques compacts et bon marché présage d’une diversification rapide d’applications dans lesquelles des agents autonomes en réseau travaillent à réaliser un objectif commun. Ces tâches complexes, en dépit de leur diversité, dépendent de la maîtrise d’un petit nombre de primitives de coordination, dont l’implémentation programmatique par des agents à faible puissance et capacité calculatoire constitue l’un des enjeux majeurs du développement de telles applications réparties. Parmi ces dernières, citons par exemple la coordination du mouvement de réseaux mobiles et véhiculaires, l’aggrégation et le traitement distribué de mesures relevées par des réseaux de capteurs, et le a répartition de charge en temps réel au sein d’un réseau fournissant un service à grande échelle. L’implémentation distribuée de telles primitives se doit de répondre à différentes contraintes, qui ne résultent pas toutes de la nature numérique des entités constitutives du réseau ; en conséquence, l’étude théorique de ces primitives s’applique à la modélisation de comportements complexes de systèmes étudiés par les sciences naturelles, tels que les mouvements collectifs animaliers ou le système nerveux.Cette monographie traite spécifiquement d’algorithmes distribués qui réalisent le calcul asymptotique de la moyenne de valeurs initialement détenues par les agents d’un réseau dont les liens de communication sont amenés à changer au cours du temps, ceci en l’absence de coordination centralisée. Ces algorithmes doivent être implémentables localement, en n’exploitant que l’information qui peut être collectée par les agents lors de leurs interactions sur le réseau, et en l’absence de mécanisme particulier pour marquer le départ, tel qu’un signal global ou un agent initiateur.Nous développons des algorithmes qui réalisent un tel consensus de moyenne sur des réseaux dynamiques présentant certaines propriétés locales. Ces algorithmes sont simples à décrire, légers à implémenter, et opèrent en temps polynomial en le nombre d’agents.Sur des réseaux présentant des interactions bidirectionnelles, nous fournissons un algorithme déterministe qui réalise le calcul asymptotique de la moyenne dès lors que le réseau ne se sépare jamais de façon permanente. Pour le cas plus général d’interactions asymétriques, nous présentons un algorithme Monte Carlo stabilisant qui est efficace en termes de complexité spatiale et opère en temps linéaire. Ce dernier algorithme admet une extension dont les exécutions terminent en tolérant un départ asynchrone des agents. Nos algorithmes sont à considérer en regard de résultats et de méthodes qui reposent sur une information globale fournie externalement aux agents, sur des hypothèses de brisure initiale de symétrie, ou qui exploitent une topologie particulière et ne se généralisent pas à des réseaux quelconques. Dans ce contexte, nous contribuons des algorithmes dont les conditions de validité sont purement locales dans le temps et l’espace : pour le modèle d’interactions bidirectionnelles, nous montrons que le calcul asymptotique de la moyenne est réalisable par des agents déterministes, là où pour le modèle général nous fournissons des algorithmes randomisés dont les performances asymptotiques sont bien meilleures que celles de protocoles à information complète et robustes aux départs asynchrones.Par-delà l’intérêt immédiat à l’obtention d’algorithmes efficaces implémentables, notre étude s’inscrit dans un effort de cartographie des limites que la localité des interactions impose aux applications réparties
Compact and cheap electronic components announce the near-future development of applications in which networked systems of autonomous agents are made to carry over complex tasks. These, in turn, depend on a small number of coordination primitives, which need to be programmatically implemented into potentially low-powered, and computationally limited, agents.Such applications include for example the coordination of the collective motion of mobile and vehicular networks, the distributed aggregation and processing of data measured locally in sensor networks, and the on-line repartition of processing load in the computer farms powering wide-scale services. As they address constraints that are not specific to the digital nature of the network such primitives also serve to model complex behavior of natural systems, such as flocks and neural networks.This monograph focuses on providing distributed algorithms that asymptotically compute the average of initial values, initially present at each agent of a networked system with time-varying communication links and in the absence of centralized control. Additionally, we consider the weaker problem of getting the agents to asymptotically agree on any value within the initial bounds. We focus on locally implementable algorithms, which leverage no information beyond what the agents can acquire by themselves, and which need no bootstrapping mechanism like a global start signal or a leader agent.We provide distributed average consensus algorithms that operate over dynamic networks given different local assumptions. These algorithms are computationally simple and operate in polynomial time in the number of agents.For bidirectional communications, we give a deterministic algorithm which asymptotically computes the average as long as the network never becomes permanently disconnected. For the general case of asymmetric communications, we provide a stabilizing Monte Carlo algorithm that is efficient in bandwidth and memory and operates in linear time, along with an extension by which the algorithm can be made to uniformly terminate over any connected network in which agents may start asynchronously.This contrasts with a plethora of results and techniques in which agents are provided external information – the size of the system, a bound over their degree, – helped with exogenous symmetry breaking – a leader agent, unique identifiers, – or where the network is expected to conform to a specific shape – a ring, a a complete network, a regular graph. Indeed, because very different networks may look alike to the agents, they are limited in what they can learn locally, and many functions are impossible to compute in a fully distributed manner without assuming some structure in the network or additional symmetry-breaking device. Given these stringent constraints, our contribution is to offer algorithms whose validity depends uniquely on local and instantaneous conditions. In the bidirectional model, we show that anonymous deterministic agents can asymptotically compute the average in polynomial time. For the general model of directed interactions, we allow agents to consult random oracles. Under those conditions, full information protocols are capable of solving any problem, and so we focus on the spatial complexity and tolerance to a lack of initial coordination in the agents, while offering stronger termination guarantees than in the bidirectional case. Beyond the fact that locally implementable algorithms are eminently desirable, our study contributes to mapping the limits that local interactions impose on networks

Avec l’arrivée massive des technologies sans fil, le nombre de terminaux mobiles n’a cessé de croître, pour des usages et des ressources de communication diversifiés. En intégrant les objets du quotidien, nos réseaux de communications sont devenus dynamiques aussi bien en termes de ressources que de topologie physique, offrant accès à des informations de plus en plus riches. La tâche de gestion s’est ainsi complexifiée et requiert des temps de réponse de plus en plus courts difficilement réalisables par un administrateur humain. Il devient indispensable de mettre en œuvre des capacités de gestion autonomes pour les nouveaux réseaux. Dans tous les cas, la gestion d’un système implique une étape essentielle : sa mesure et sa supervision. Peu importe sa nature, c’est cette étape de prise d’information qui permet sa caractérisation, son analyse et son contrôle. Le domaine des réseaux n’échappe pas à cette règle et les objets qui le composent auront besoin d’acquérir des informations sur leur environnement pour mieux s’y adapter. Dans cette thèse, nous nous intéressons au partage efficace de ces informations de mesures à des fins d’auto-analyse et d’évaluation distribuée de la performance. Après avoir formalisé le problème de la mesure distribuée, nous nous consacrons dans un premier temps à l’organisation des échanges de mesures dans les graphes dynamiques. Nous proposons une nouvelle heuristique pour le consensus de la moyenne qui converge plus rapidement que celles de l’état de l’art. Dans un second temps, nous considérons des topologies plus stables pouvant utiliser des flux TCP comme moyen d’échange. Nous proposons un mécanisme d’ordonnancement de ces flux qui conserve le même comportement face à la congestion, tout en réduisant leur latence moyenne. Enfin, nous nous intéressons à l’information de mesure échangée. Nous montrons comment les nœuds peuvent superviser diverses métriques telles que la performance d’un système en se basant sur l’utilité de ses agents, et proposons une méthode pour qu’ils puissent analyser l’évolution de cette performance
With the massive rise of wireless technologies, the number of mobile stations is constantly growing. Both their uses and their communication resources are diversified. By integrating our daily life objects, our communication networks become dynamic in terms of physical topology but also in term of resources. Furthermore, they give access to a richer information. As a result, the management task has become complex and requires shorter response time that a human administrator can not respect. It becomes necessary to develop an autonomic management behavior in next generation networks. In any manner, managing a system requires essential steps which are : its measurement and its supervision. Whatever the nature of a system, this stage of information gathering, allows its characterization and its control. The field of networks is not the exception to the rule and objects that compose them will need to acquire information on their environment for a better adaptation. In this thesis, we focus on the efficient sharing of this information, for self-analysis and distributed performance evaluation purposes. After having formalized the problem of the distributed measurement, we address in a first part the fusion and the diffusion of measures in dynamic graphs. We develop a new heuristic for the average consensus problem offering a better contraction rate than the ones of the state of the art. In a second part, we consider more stable topologies where TCP is used to convey measures. We offer a scheduling mechanism for TCP flows that guaranty the same impact on the network congestion, while reducing the average latency. Finally, we show how nodes can supervise various metrics such as the system performance based on their utilities and suggest a method to allow them to analyze the evolution of this performance

Les algorithmes distribués de consensus sont des algorithmes itératifs de faible complexité où les nœuds de capteurs voisins interagissent les uns avec les autres pour parvenir à un accord commun sans unité coordinatrice. Comme les nœuds dans un réseau de capteurs sans fil ont une puissance de calcul et une batterie limitées, ces algorithmes distribués doivent parvenir à un consensus en peu de temps et avec peu d’échange de messages. La première partie de cette thèse s’est basée sur l’étude et la comparaison des différents algorithmes de consensus en mode synchrone et asynchrone en termes de vitesse de convergence et taux de communications. La seconde partie de nos travaux concerne l’application de ces algorithmes de consensus au problème de la détection de trous de couverture dans les réseaux de capteurs sans fil.Ce problème de couverture fournit aussi le contexte de la suite de nos travaux. Il se décrit comme étant la façon dont une région d’intérêt est surveillée par des capteurs. Différentes approches géométriques ont été proposées mais elles sont limitées par la nécessité de connaitre exactement la position des capteurs ; or cette information peut ne pas être disponible si les dispositifs de localisation comme par exemple le GPS ne sont pas sur les capteurs. À partir de l’outil mathématique appelé topologie algébrique, nous avons développé un algorithme distribué de détection de trous de couverture qui recherche une fonction harmonique d’un réseau, c’est-à-dire annulant l’opérateur du Laplacien de dimension 1. Cette fonction harmonique est reliée au groupe d’homologie H1 qui recense les trous de couverture. Une fois une fonction harmonique obtenue, la détection des trous se réalise par une simple marche aléatoire dans le réseau
Distributed consensus algorithms are iterative algorithms of low complexity where neighboring sensors interact with each other to reach an agreement without coordinating unit. As the nodes in a wireless sensor network have limited computing power and limited battery, these distributed algorithms must reach a consensus in a short time and with little message exchange. The first part of this thesis is based on the study and comparison of different consensus algorithms synchronously and asynchronously in terms of convergence speed and communication rates. The second part of our work concerns the application of these consensus algorithms to the problem of detecting coverage holes in wireless sensor networks.This coverage problem also provides the context for the continuation of our work. This problem is described as how a region of interest is monitored by sensors. Different geometrical approaches have been proposed but are limited by the need to know exactly the position of the sensors; but this information may not be available if the locating devices such as GPS are not on the sensors. From the mathematical tool called algebraic topology, we have developed a distributed algorithm of coverage hole detection searching a harmonic function of a network, that is to say canceling the operator of the 1-dimensional Laplacian. This harmonic function is connected to the homology group H1 which identifies the coverage holes. Once a harmonic function obtained, detection of the holes is realized by a simple random walk in the network

In this chapter, autonomous mobile robots are deployed to measure an unknown scalar field and build its map. The development of a cooperative sensing and control method is presented for multi-robot swarming to build the scalar field map. The proposed method consists of two parts. First, the development of a distributed sensor fusion algorithm is obtained by integrating two different distributed consensus filters to achieve cooperative sensing among robots. This fusion algorithm has two phases. In the first phase, the weighted average consensus filter is developed which allows each robot to find an estimate of the value of the scalar field. In the second phase, the average consensus filter is used to allow each robot to find a confidence of the estimate. The final estimate of the value of the scalar field is iteratively updated during the movement of the robot via a weighted average protocol. Second, the distributed control algorithm is developed to control the mobile robots to form a network and cover the field. Experimental results are provided to demonstrate the proposed algorithms.