Accelerated distributed average consensus algorithms based on advection diffusion processes

Abstract

Diese Arbeit beschäftigt sich mit verteilten Mittelungsverfahren in Sensornetzen, wobei eine Analogie zwischen Strömungsmechanik und sogenanntem "average consenus" (AC) ausgenutzt wird. Unser Ziel ist es, den Mittelwert der Sensormesswerte mit AC zu berechnen, indem ein Advektions-Diffusionsprozess nachgeahmt wird. Ein Advektions-Diffusionsprozess beschreibt die Strömung von Flüssigkeiten, Energie und anderen konservierten Größen aufgrund von Diffusion und eines externen Geschwindigkeitsfeldes (Advektion).<br />Um dem Leser das notwendige Basiswissen zu vermitteln, präsentieren wir zu Beginn die Grundlagen von AC. Des weiteren befassen wir uns mit Grundzügen der Graphentheorie sowie grundlegenden Graphtopologien, welche für die Modellierung von Sensornetzen geeignet sind.<br />Unsere Arbeit baut auf die von Sardellitti et al. auf, in der gezeigt wird, dass durch zeitlich veränderliche asymmetrische Kantengewichte die Konvergenzgeschwindigkeit von AC gegenüber dem traditionellen symmetrischen Ansatz gesteigert werden kann. Diese asymmetrischen Gewichte werden über die Parallele zwischen AC und Advektions-Diffusionsprozessen motiviert. Ein Nachteil der ursprünglichen Methode ist, dass die Sensoren auf einem Torus angeordnet sein müssen, damit der Anosov Flow, ein spezieller Advektionsprozess, angewandt werden kann.<br />In dieser Arbeit zeigen wir, dass der beschriebene Ansatz auch auf simple planare Netze erweitert werden kann und somit auch praktische Relevanz besitzt. Darüber hinaus entwickeln wir neue externe Strömungsfelder, die auf physikalischen Rotationsfeldern basieren.<br />Numerische Simulationen belegen den Nutzen der resultierenden Entwürfe für die AC-Kantengewichte.<br />

This thesis deals with distributed averaging methods in sensor networks by exploiting an analogy between fluid mechanics and average consensus (AC). Our goal is to compute the average of measurements through AC by mimicking an advection-diffusion processes. An advection-diffusion process describes physical phenomena where a fluid, energy, or any other conserved quantity is spatially transferred due to diffusion and bulk motion.<br />To provide the reader with the necessary background, we summarize the basic concepts of static average consensus, some elements of graph theory, and finally network topologies frequently used in literature to model wireless sensor networks (WSN).<br />In a paper by Sardellitti et al., it was shown that by introducing appropriate asymmetric interaction mechanisms, which yields time-varying AC weights on each edge, it is possible to obtain substantially improved convergence rates compared to the symmetric time-invariant case. The basic idea underlying this approach is to interpret AC as an advection-diffusion process governing the homogenization of fluid mixtures. A drawback of the method in Sardellitti et al. is that the sensors are assumed to be deployed on a torus (this is necessary to apply the Anosov flow, a specific advection process).<br />In this thesis we drop the toroidal assumption in order to render the advection-inspired AC method applicable to realistic WSN topologies. To that end we further replaced the Anosov flow with newly designed velocity fields that are inspired by physical rotation fields. Numerical simulations confirm the usefulness of the resulting AC weight designs.