Titelaufnahme

Titel
Distributed averaging wireless sensor networks / von Valentin Schwarz
VerfasserSchwarz, Valentin
Begutachter / BegutachterinMatz, Gerald
Erschienen2014
UmfangXV, 130 S. : Ill., graph. Darst.
HochschulschriftWien, Techn. Univ., Diss., 2014
Anmerkung
Zsfassung in dt. Sprache
SpracheEnglisch
Bibl. ReferenzOeBB
DokumenttypDissertation
Schlagwörter (EN)wireless sensor networks / consensus / distributed algorithms
Schlagwörter (GND)Sensor / Funknetz / Effizienter Algorithmus / Mittelwert / Verteilter Algorithmus
URNurn:nbn:at:at-ubtuw:1-75412 Persistent Identifier (URN)
Zugriffsbeschränkung
 Das Werk ist frei verfügbar
Dateien
Distributed averaging wireless sensor networks [1.94 mb]
Links
Nachweis
Klassifikation
Zusammenfassung (Deutsch)

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.

Zusammenfassung (Englisch)

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.