Loading…
Engineering a communication protocol stack to support consensus in sensor networks
Köpke, Andreas
Das Thema dieser Arbeit ist der Entwurf und Evaluierung eines Protokoll-Stacks, der die erfolgreiche Koordination von Aktoren in einer Gebäudeautomatisierung ermöglicht. Mit der Einführung einer solchen kann Energie gespart werden, ohne dass es zu Einbussen im Komfort kommt. Für Gebäude im Bestand eignen sich drahtlose Sensornetze: hier müssen keine Kabel verlegt werden. Drahtlose Sensornetze bestehen aus einzelnen Sensorknoten, die jeweils über Sensoren, einen Mikroprozessor, ein preiswertes Radio-Modem und häufig eine autonome Energieversorgung, wie z.B. eine Batterie, verfügen. Damit können die Sensoren untereinander Daten austauschen und an Aktoren, wie z.B. Lampen oder Heizkörper weiterleiten. Die Aktoren müssen zusammenarbeiten, um ein bestimmtes Ziel zu erreichen. Dieses Koordinations-Problem ist in verteilten Systemen als Konsens-Problem bekannt. Es kann in Sensornetzen nicht immer gelöst werden, und in dieser Arbeit wird der Frage nachgegangen, wie die Kommunikations-Protokolle gestaltet werden sollten, damit die Aktoren möglichst häufig einen Konsens erzielen. Die besondere Herausforderung ist hier, dass drei Ziele -- Latenz, Zuverlässigkeit und Energiebedarf -- zusammen betrachtet werden müssen. Die Aktoren haben nur wenig Zeit, ihre Aktionen zu koordinieren, sonst kann es zu Komfort-Einbussen kommen. Die von den Sensoren und Aktoren übertragenen Nachrichten müssen zudem mit einer hohen Wahrscheinlichkeit ankommen. Sonst verlängert sich der Koordinationsprozess und es kommt zu einem erhöhten Energiebedarf der Sensorknoten. Deren autonome Energieversorgung muss häufig für mehrere Jahre Betrieb reichen: Für einige Sensoren sind acht bis zehn Jahre in den einschlägigen Normen und Vorschriften vorgesehen. In dieser Arbeit wird ein Protokoll-Stack entworfen und evaluiert, der diese Anforderungen erfüllt. Er besteht zum einen aus einem neuartigen Medienzugriffsprotokoll RedMac und zum anderen aus einem Routing Protokoll Net. Bei RedMac haben die Sensorknoten das Radio-Modem meistens ausgeschaltet: das spart Energie. Die Knoten koordinieren ihre Schlafzyklen nicht, die Zyklen müssen noch nicht einmal dieselbe Länge haben. Zudem wird das Routing Protokoll Net unterstützt. Bei Net stellt der Empfänger fest, ob er sich in einer geeigneten Position befindet um die Nachricht zum Ziel weiterzuleiten. Die dazu notwendige Information wird dabei in einer pro-aktiven Routing-Phase berechnet. Anschliessend reagiert das Protokoll nur noch, wenn die Verbindungen abreissen. Dadurch hat Net einen sehr niedrigen Koordinationsbedarf. In Net schickt ein Knoten eine Nachricht an alle Knoten, die näher am Ziel sind. Dadurch werden verschiedene, parallele Verbindungen für die Übertragung genutzt, was zu einer niedrigen Latenz und einer hohen Zuverlässigkeit führt. Durch das Zusammenspiel der beiden Protokolle Net und RedMac konnten 99,95% der Koordinationsversuche erfolgreich innerhalb einer bestimmten Zeit abgeschlossen werden. Das ist umso bemerkenswerter, als das die Versuche mit einfachen, qualitativ eher unterdurchschnittlichen Radio-Modems gemacht wurden und das Netz bei den Experimenten gerade noch verbunden war. In einigen Fällen wurden alle Koordinationsversuche erfolgreich abgeschlossen, in anderen Fällen weniger: Das ist speziell dann der Fall, wenn einige der Grundanforderungen verletzt sind. Die Herausarbeitung der notwendigen Vorraussetzungen ist ein weiterer Beitrag dieser Arbeit. Eine dieser Vorraussetzungen ist, dass mindestens 98% der Nachrichten von einem Knoten am Ziel ankommen sollten. Das Design der Protokolle basiert zudem auf wenigen Regeln, die in dieser Arbeit abgeleitet und erprobt werden. Sie helfen, die drei Ziele schon im Protokoll-Design zu berücksichtigen und verschiedene mögliche Mechanismen a-priori in ihren Auswirkungen einzuschätzen. Damit leistet diese Arbeit einen Beitrag, der über die hier vorgeschlagenen Protokolle hinausgeht und eine Anpassung an andere Anwendungsgebiete ermöglicht.
In this thesis, a communication protocol stack is designed and evaluated that enables successful coordination of actuators in a building automation. Using one can lead to substantial energy savings without sacrificing comfort. For already existing buildings, wireless sensor networks are suitable solution: There is no need to pull cables. Wireless sensor networks consists of single sensor nodes, each equipped with sensors, a microprocessor and a low cost radio modem. They are often powered by an autonomous power supply, for instance a battery. This allows sensors to exchange data and send it to actuators, for instance lamps and heaters. These actuators have to work together to reach a common goal. This coordination problem is known as consensus problem in distributed systems. It cannot be solved in sensor networks. However, with the right support from the protocol stack, actuators can achieve a consensus most of the time. The major challenge is that three goals -- latency, reliability and energy expenditure -- have to be considered all at once. The actuators have to coordinate their actions fast, otherwise comfort may suffer. The messages transmitted by sensors and actuators have to reach their destination with a high probability. Otherwise, the coordination process takes longer and the energy expenditure of the sensor nodes rises. Their autonomous power supply often has to last for several years of operation: For some sensors, the applicable standards and regulations require eight to ten years of continuous operation. In this thesis, a protocol stack is designed and evaluated that fulfills these requirements. It consists of a novel media access protocol RedMac and a routing protocol Net. Using RedMac, the sensor nodes have their radio modem usually switched off: This saves energy. The nodes do not coordinate their sleep cycles. In fact, these cycles are not even required to have the same length. In addition, RedMac supports the routing protocol Net. In Net, the receiver decides, whether it is in a suitable position to forward a message towards the destination. The necessary information is computed in a pro-active routing phase. Afterwards, it just reacts when connections break. For this reason, Net has a very low coordination overhead. In Net, each node sends its message to all nodes closer to the destination. Hence, several, parallel connections are used to deliver the message which leads to a low latency and a high reliability. When using Net and RedMac, 99.95% of all coordination attempts are successful within a given time bound. This is even more remarkable, as simple radio modems with lower than average quality have been used for the experiments to form a barely connected network. In some cases, all coordination attempts were finished successfully, in some cases less. This happens, when certain basic requirements are violated. This thesis identifies these basic requirements. For instance, one requirement is that at least 98% of all messages have to arrive at the destination. In addition, the design of the protocols relies on a few rules that are derived and evaluated in this thesis. They help to incorporate the three goals already in the design process and allow an a priori estimation of the influence of certain protocol mechanisms. This is a contribution of the thesis that goes beyond the proposed protocols: It allows an adaptation to other application areas.
