A framework for reliable and dynamic wireless sensor-actuator networks
Gruhn, Helena
The number of persons requiring medical assistance in industrial nations grows with the demographic change. Unfortunately, the growth is unproportional to the availability of well-trained care personal. Wireless sensor-actuator networks have the potential to support care personal. Nodes worn by patients may supervise individually critical vital parameters and trigger an alarm if a critical value is reached. Medical help can be provided earlier lowering the risk of permanent health issues. Nevertheless, wireless sensor-actuator networks are error-prone. They have to be designed fault-tolerant to function reliably. However, an approach for provably reliable wireless networks is still non-existing.
This thesis proposes a solution for this problem by providing a framework for the generation, supervision and maintenance of fault-tolerant wireless sensor actuator networks. A network is defined as fault-tolerant and reliable, if it is biconnected. At least two node-disjoint paths between every pair of nodes have to exist within the network.
The main contributions of this thesis are threefold. First, an algorithm for
the generation of fault-tolerant networks for given floor plans is provided. The generated topologies are biconnected and require only a reasonable number of nodes. Furthermore, they provide the infrastructure for a localization of nodes by covering each position within the floor plan with three signals. Second, a heuristic and distributed algorithm for the detection of bottlenecks in dynamic networks is introduced. Bottlenecks are possible breakpoints of the network and have to be discovered early to avoid a disconnection of nodes.
The core is the assumption that every network is representable in the form of a graph. Graph theoretic measures are applied to detect topological changes. The two characteristics used for the heuristic are the algebraic connectivity and the Fiedler vector, both reflect the connectivity of the network. Time variations indicate critical topological changes in dynamic networks. A decentralized continuous algorithm is proposed, which estimates both characteristics utilizing the properties of a propagating discrete wave. The algorithm requires only local information avoiding a single-point of failure in the form of a central
node. Third, an algorithm for the analysis and correction of faulty topologies is introduced. The topology of a network is analyzed using the well-known Ford-Fulkerson algorithm. The Ford-Fulkerson algorithm determines the maximal flow within a flow network. The maximal flow equals the number of edge-disjoint paths within a network with an edge capacity of one. Through a slight modification of the network, node-disjoint paths are found. If the number of node-disjoint paths is less than two, a bottleneck exists within the network. The bottleneck node is then identified and the network corrected through the
placement of correction nodes. Finally, the placements are examined to avoid redundant correction nodes. The correct function of the algorithms is validated using a case study of a retirement home. All algorithms work without human interaction. Their application
facilitates and accelerates the design, supervision and maintenance of
wireless networks. The described framework provides a basis for the reliable application of sensor-actuator network in health care facilities.
Der demographische Wandel in den Industrienationen führt zu einem Anstieg der Anzahl pflegebedürftiger Personen. Damit einhergehend steigt der Bedarf nach qualifiziertem Pflegepersonal. Dieser ist schwierig abzudecken. Gesundheitsassistenzsysteme in Form von drahtlosen Sensor-Aktornetzwerken könnten das Pflegepersonal in der täglichen Routine unterstützen. Patienten könnten mit Sensoren zur Beobachtung wesentlicher Vitalparameter ausgestattet werden, die bei Erreichen eines kritischen Wertes einen Alarm auslösen.
Drahtlose Netzwerke sind im Allgemeinen fehleranfällig, müssen aber angewandt im Gesundheitswesen zuverlässig funktionieren. Knoten und Verbindungen können ausfallen. Bisher gibt es noch keinen Ansatz für den Entwurf und Betrieb von nachweislich zuverlässigen drahtlosen Netzwerken.
Diese Arbeit präsentiert ein Framework zur Generierung, Überwachung und Wartung zuverlässiger drahtloser Sensor-Aktornetzwerke. Im Fokus steht dabei die Topologie des Netzwerkes. Die Zuverlässigkeit eines Netzwerkes wird über seine Konnektivität definiert: jedes Netzwerk muss fehlertolerant sein und im Notfall zwei voneinander unabhängige Kommunikationspfade für Alarmnachrichten bereitstellen, falls ein Pfad korrumpiert ist. Somit muss jedes Netzwerk zweifach zusammenhängend sein.
Die wichtigsten Beiträge dieser Arbeit sind: ein Algorithmus zur Generierung fehlertoleranter Netzwerke für einen gegebenen Grundriss, eine Heuristik sowie ein Algorithmus zur Erkennung von Kommunikationsengpässen in dynamischen Netzwerken und ein Algorithmus zur Analyse und Korrektur fehlerhafter Netzwerktopologien. Der Generator erzeugt zweifach zusammenhängende Netzwerktopologien mit Signalabdeckungsraten, die eine Lokalisation von Knoten im Netzwerk durch Triangulierung erlauben. Die Erkennung von Kommunikationsengpässen beruht auf der Annahme, dass sich jedes Netzwerk als Graph darstellen lässt. Topologieänderungen werden durch die Evaluierung zeitlicher
Änderungen zweier Konnektivitätsmaße, der algebraische Konnektivität und des Fiedler-Vektors, erkannt. Der Algorithmus zur Kommunikationsengpassdetektion ermöglicht eine dezentrale Selbstüberwachung des Netzwerkes ohne externe Intervention. Zur Berechnung der Konnektivitätsmaße werden nur lokal auf einem Knoten vorhandene Informationen benötigt. Die Korrekturroutine nutzt den bekannten Ford-Fulkerson Algorithmus zur Berechnung des maximalen Flusses innerhalb des Netzwerkes. Bei einer Kantenkapazität von eins und durch eine Modifikation des Netzwerkes entspricht dieser der Anzahl der Knoten-disjunkten Pfade im Netzwerk. Wenn nur ein Pfad gefunden wird, existiert ein Kommunikationsengpass. Dieser wird lokalisiert und mithilfe
eines neuplatzierten Korrekturknotens behoben. Die Platzierung redundanter Knoten wird durch einen zusätzlichen Optimierungsschritt vermieden. Die Anwendbarkeit des Ansatzes wird durch eine ausführliche Evaluierung gezeigt. Alle Algorithmen wurden dazu implementiert bzw. im Falle des verteilten Netzwerkalgorithmus simuliert und anschließend anhand von unterschiedlichen Fallbeispielen getestet.
Das präsentierte Framework ermöglicht und vereinfacht den Entwurf, die autonome Überwachung und die Wartung fehlertoleranter drahtloser Sensor-Aktornetzwerke.
