Consensus propagation in wireless sensor networks

Abstract

Verteilten Verfahren zur Lösung von Inferenz-Problemen wird in jüngster Vergangenheit immer mehr Bedeutung zugesprochen. Im Speziellen bietet verteilte Mittelwertbildung eine ausbaufähige Basis für zahlreiche Problemstellungen. Daher haben wir Consensus Propagation, einen asynchronen Algorithmus, der ein Spezialfall von Gaussian Belief Propagation ist, als Ausgangsbasis für diese Arbeit gewählt.<br />Üblicherweise ist Konvergenz für Gaussian Belief Propagation nicht zwingend, im Gegensatz dazu konvergiert Consensus Propagation jedoch in jeder möglichen Anwendung. Damit der Leser über das nötige Vorwissen verfügt, geben wir im ersten Teil dieser Arbeit eine Einführung zu theoretischen Gebieten, die für das Verständnis von Consensus Propagation wichtig sind. Neben einer Kurzeinführung in Graphentheorie werden auch verschiedene Netzwerk-Modelle erklärt, welche zufällig erzeugt werden können.<br />Zusätzlich präsentieren wir graphische Lösungsmethoden, wobei wir uns auf den Message-Passing-Algorithmus konzentrieren. Der Hauptteil dieser Arbeit beschäftigt sich mit Consensus Propagation.<br />Zum einen betrachten wir den Algorithmus etwas näher und zum anderen untersuchen wir die Konvergenzeigenschaft anhand verschiedener Graphen und bei verschiedenen Rahmenbedingungen. Außerdem untersuchen wir Szenarien mit limitierter Übertragungskapazität und beschäftigen uns mit Situationen, bei denen die zu beobachtenden Größen dynamisch variieren. Zusammenfassend können wir sagen, dass die Konvergenzgeschwindigkeit von Consensus Propagation sehr stark von der Graphenstruktur abhängt.<br />Darüber hinaus haben wir festgestellt, dass man mit Consensus Propagation dynamischen Signalen folgen kann, wobei dieses Verhalten in früheren Arbeiten noch nicht untersucht worden ist.<br />

Distributed methods for solving inference problems have received increased attention during the last decades. Methods for distributed averaging offer an extendable basis for many inference problems and thus we focus in this work on consensus propagation which is a new asynchronous approach related to Gaussian belief propagation. Usually convergence of Gaussian belief propagation for general settings is not guaranteed, nevertheless consensus propagation converges for arbitrary settings.<br />To provide the reader with the necessary prerequisites, some of the basic principles used by consensus propagation are introduced in the first part of this work. Besides summarizing graph theory, different network models based on random graphs are presented. Furthermore, the idea and functionality of graphical methods are considered, with particular focus on the message passing algorithm. In the main part of this work we concentrate on investigating consensus propagation the one hand and studying its convergence behavior in different graph topologies and different simulation settings on the other hand. We further consider communication constraints on the messages and dynamically varying settings.<br />We found out that the convergence speed of consensus propagation is highly dependent on the graph topology. Moreover consensus propagation was seen to possess suitable tracking abilities which have not been studied previously.