Search

Verteilte Algorithmen sind bereits seit Jahrzehnten ein Forschungsthema in der Informatik. In der Elektrotechnik hat die Miniaturisierung dazu gef��hrt, dass man mittlerweile preiswerte und effiziente drahtlose Sensornetze herstellen kann. Somit wurde ein neues, relativ unerforschtes Anwendungsgebiet f��r verteilte Algorithmen erschlossen. In letzter Zeit wurden daher einige Algorithmen entwickelt, die speziell f��r drahtlose Sensornetze konzipiert sind, wobei manche dieser Algorithmen noch immer zu viele Ressourcen wie Leistung oder Zeit ben��tigen und somit nicht umsetzbar sind. Ein einfacher effizient in Sensornetzen anwendbarer Algorithmus ist die verteilte Mittelwertbildung. Wir behandeln zwei Varianten in dieser Arbeit: Consensus Propagation und Average Consensus. Beide Algorithmen ben��tigen nur drahtlose Kommunikation zwischen benachbarten Sensoren und der Mittelwert wird iterativ an jedem Knoten ermittelt. In dieser Dissertation befassen wir uns mit der Weiterentwicklung dieser Algorithmen und analysieren den erbrachten Nutzen. Im ersten Teil dieser Arbeit stellen wir eine dynamische Version von Consensus Propagation vor, mit der man zeitlich ver��nderliche Messwerte mitteln kann. Wir beweisen die Stabilit��t dieses Algorithmus und vergleichen dessen Konvergenzverhalten mit dem von Average Consensus, von dem es bereits eine dynamische Variante gibt. Dies gelingt uns zum Teil durch die Analyse der ��bertragungsfunktionen beider Algorithmen im Frequenzbereich. Au��erdem zeigen wir, dass man durch lineare Filter eine zeitliche Verz��gerung von Consensus Propagation beinahe g��nzlich beseitigen kann. Damit Consensus Propagation in der Praxis funktioniert, muss man sich auch Gedanken ��ber ein Kommunikationsprotokoll machen. Hierf��r pr��sentieren wir eine Modifikation des bekannten ALOHA-Protokolls, welches relativ gut und vor allem einfach funktioniert. Zuletzt betrachten wir die verteilte Feldrekonstruktion als Anwendungsfall der Mittelwertbildung. Hierbei wird Feldrekonstruktion als verteiltes kleinste Quadrate Problem formuliert, welches durch eine simple Adaption von Consensus Propagation gel��st werden kann. Numerische Simulationen zeigen abschlie��end die Leistungsf��higkeit der Algorithmen, wobei das drahtlose Sensornetzwerk mittels geometrischer Zufallsgraphe modelliert wird. Der n��chste Teil dieser Arbeit befasst sich mit dem Entwurf der Gewichts-Koeffizienten bei Average Consensus, welche die Effizienz und die Konvergenzgeschwindigkeit erh��hen. Als erstes untersuchen wir die bereits bekannten Metropolis-Hastings Gewichte und leiten neue Bedingungen f��r die Konvergenz her. Danach stellen wir eine Methode vor, mit der man die Gewichte in jedem Zeitschritt optimiert, um die bestm��gliche Fehlerreduktion zu erreichen. Leider ist diese Methode in der Praxis nicht einfach realisierbar, man kann sie jedoch als Vergleichsma�� f��r andere zeitvariante Gewichts-Entw��rfe heranziehen. In diesem Zusammenhang schlagen wir eine Methode vor, bei der ein Gewichts-Design in ein anderes dynamisch ��bergef��hrt wird. Das f��hrt zu verbesserter Konvergenz, weil man immer jene Gewichte verwenden kann, welche f��r die aktuelle Korrelationsstruktur der zu mittelnden Werte besonders geeignet sind (z.B. Metropolis-Hastings Gewichte f��r unkorrelierte Daten). Weiters stellen wir eine M��glichkeit vor mit der man ein Geschwindigkeitsfeld, welches dem einer Fl��ssigkeit in einem Mixer gleicht, Average Consensus ��berlagert und damit die Mittelwertbildung beschleunigt. F��r diesen Ansatz zeigen wir auch, welche Eigenschaften erf��llt sein m��ssen, damit das Gesamtsystem konvergiert. Schlussendlich vergleichen wir das Konvergenzverhalten all unserer neuen Gewicht-Designs anhand von geometrischer Zufallsgraphen. Im letzten Teil dieser Arbeit widmen wir uns mobilen Szenarien. Darunter verstehen wir, wenn sich Sensoren w��hrend der Mittelwertbildung bewegen. Wir leiten zur Effizienzanalyse eine obere und untere Konvergenzschranke her und zeigen damit, dass sich Mobilit��t fast immer positiv auf die Konvergenzgeschwindigkeit auswirkt. Zuletzt berechnen wir noch analytisch die untere Schranke f��r ein spezielles Bewegungsmodell, bei dem sich die Sensoren sprunghaft bewegen und vergleichen das Ergebnis mit numerischen Simulationen., Distributed computation emerged in computer science already some decades ago. Miniaturization led to efficient and low-cost designs of wireless sensor nodes and thus to a revival of distributed algorithms in the novel application area of wireless sensor networks. Many distributed algorithms have been developed for wireless sensor networks, but some are not efficient, i.e., they require a lot of communication or computational power at each sensor. A simple algorithm that runs efficiently in such networks is distributed averaging. We consider two distributed averaging schemes in detail: consensus propagation and average consensus. Both require only local communication and each sensor obtains the desired average in an iterative fashion. The main contribution of this thesis is to investigate their performance and introduce practical relevant extensions. The first contribution in our work is an extension of consensus propagation that tracks the average of time-varying measurements. Our approach is shown to be stable and the performance is compared to an existing dynamic version of average consensus. A transformation of the update equations to the frequency domain allows us to study the behavior of both dynamic averaging algorithms through their transfer functions. We also introduce a linear filter to combat the delay inherent to dynamic consensus propagation. Moreover, we propose an efficient medium access protocol which is motivated by the well known ALOHA protocol and implement it in consensus propagation scenarios. Finally, it is shown how to use consensus propagation for field estimation through solving a least squares problem via distributed averaging. Numerical results that use random geometric graphs to model realistic wireless sensor networks verify our findings. The next part of the thesis considers novel weight design methods for average consensus to improve performance. We start with analyzing the stability of the already known Metropolis-Hastings weights, where we derive novel conditions for the convergence. Furthermore, we present a method to design weights that achieve the best per-step mean squared error improvement assuming that the initial correlation of the measurements is known. These weights need to be computed every iteration and hence they are hard to use in practice. However, they provide a good performance benchmark for other weights that vary over time. One such weight design that we propose is called weight morphing. This method switches between two different weights (more precisely, one weight design morphs into another), by trying to use the better performing weight for the corresponding situation adaptively. In particular, we morph Metropolis-Hasting weights, which perform well for uncorrelated measurements, and the weights with the best possible asymptotic behavior, which yield good convergence for correlated measurements. The last contribution of this part of the work introduces blending with average consensus. Motivated by physics, we add an advective flow to the diffusive structure of average consensus. These flows are similar to the behavior of fluids in a blender. Besides a detailed derivation of the theory, we prove the convergence of our method. Finally, we numerically compare all our weight designs in random geometric graphs. The last part of our work addresses the behavior of average consensus when nodes are mobile. We derive generic lower and upper bounds on the mean-squared error, which verify the beneficial impact of mobility. Additionally, we provide a closed form expression for the lower bound in random geometric graphs with random hopping and compare it to numerical results.