Sensor-MAC

Sensor Media Access Control [ˈsɛnsə ˈmiːdiə ˈæksɛs kənˈtɹəʊl] (S-MAC, engl. „Sensor-Medienzugriffskontrolle“) ist ein Netzwerkprotokoll für Sensornetze. Sensornetze bestehen aus winzigen, drahtlos kommunizierenden Computern (Sensorknoten), die in großer Zahl in einem Gebiet ausgebracht werden, sich selbständig vernetzen und ihre Umgebung in Gruppenarbeit solange mit Sensoren überwachen, bis ihre Energiereserven erschöpft sind. Als Sonderform des Ad-hoc-Netzes stellen sie gänzlich andere Anforderungen an ein Netzprotokoll, als beispielsweise das Internet und benötigen daher eigens für sie entwickelte Netzwerkprotokolle. Sensor Media Access Control legt bis ins Detail fest, wie die Knoten eines Sensornetzes Daten austauschen, steuert als Media Access Control (MAC) den Zugriff auf das gemeinsame Kommunikationsmedium des Netzes, regelt den Aufbau der Netztopologie und bietet ein Verfahren zur Synchronisation.

Obwohl heute von rein akademischem Interesse und ohne praktische Anwendung war S-MAC ein bedeutender Schritt in der Sensornetzforschung und inspirierte zahlreiche nachfolgende Netzwerkprotokolle. Es wurde 2001 von Wei Ye, John Heidemann und Deborah Estrin von der University of Southern California vorgestellt und zielt besonders darauf ab, die knappen, nicht wiederaufladbaren Energievorräte der Sensorknoten zu schonen.^[1] Die Entwicklung wurde von der US-amerikanischen Militäragentur Defense Advanced Research Projects Agency im Rahmen des Projekts Sensor Information Technology (SenSIT) finanziell gefördert.^[2]

Einordnung

Als S-MAC 2001 vorgestellt wurde, gab es durch Mobiltelefonie und die damals aufstrebende Technologie der Wireless Local Area Networks (WLAN) zur Vernetzung tragbarer Computer bereits ein breites Spektrum an Netzwerkprotokollen für die digitale drahtlose Kommunikation. Multiplexverfahren ermöglichten den gleichzeitigen Betrieb großer Zahlen an Mobiltelefonen, neuere Geräte stellten mit Bluetooth Kurzstreckenfunkverbindungen her und im Computersektor war mit IEEE 802.11g bereits die zweite Erweiterung des Industriestandards für WLANs angekündigt.

Die Forschung bei mobilen Ad-hoc-Netzen war indes noch nicht so weit gediehen, dass man von vorherrschenden Ansätzen oder gar absehbaren Standards sprechen konnte. Die bis dahin gemachten Vorschläge wandelten mehr oder weniger erfolgreich bestehende Protokolle ab. Die Variation Power Aware Multi-Access Protocol with Signaling Ad Hoc Networks (PAMAS) des Protokolls Multiple Access with Collision Avoidance ging verstärkt auf die Bedürfnisse mobiler Endgeräte mit beschränktem Energievorrat ein, benötigte jedoch einen zusätzlichen Kommunikationskanal, um gleichzeitigen Medienzugriff zu unterbinden.^[3] Time Division Multiple Access (TDMA) funktionierte in seiner Rohform bei Bluetooth mit maximal acht Endgeräten tadellos, ließ sich aber nicht ohne weiteres auf große Sensornetze übertragen. Eine namenlos gebliebene TDMA-Variation von Sohrabi und Pottie nutzte die zur Verfügung stehende Sendezeit nur ungenügend aus und senkte dadurch den Datendurchsatz drastisch.^[4] Piconet und verschiedene Abwandlungen von Carrier Sense Multiple Access (CSMA) erwiesen sich als vielversprechend, aber noch unausgereift.

S-MAC wurde von PAMAS und IEEE 802.11 angeregt. Es kombiniert die beiden Techniken Carrier Sense Multiple Access und Time Division Multiple Access, um gezielt auf die speziellen Anforderungen der Sensornetze einzugehen. Dabei trägt S-MAC dem Umstand Rechnung, dass im Gegensatz zu den Annahmen von PAMAS in der Regel nur ein einziger Kommunikationskanal zur Verfügung steht und bricht mit dem Prinzip der Fairness in Rechnernetzen. In gewöhnlichen Rechnernetzen konkurrieren verschiedene Benutzer und Prozesse um das gemeinsame Medium, so dass eine faire Medienzugriffsregelung sinnvoll ist. In Sensornetzen gibt es jedoch nur eine einzige, netzweite Anwendung, die gewissermaßen mit sich selbst konkurriert, und deren Gesamtziel Vorrang hat vor der Fairness gegenüber einzelnen Netzknoten.

Sensornetze sind bislang ein Forschungsgebiet ohne praktische Anwendungen, so dass auch S-MAC ausschließlich von akademischem Interesse ist. Die Stärke des Entwurfs lag vor allem darin, eine Ausgangsbasis für eine ganze Reihe ähnlich gelagerter weiterer Protokolle zu schaffen: T-MAC, WiseMAC, DSMAC, B-MAC, μ-MAC, M-MAC und Z-MAC orientierten sich nicht nur namentlich an ihrem gemeinsamen Vorreiter. S-MAC wurde unter anderem mit TinyOS implementiert, einem Betriebssystem speziell für Sensorknoten, und wird als „Urahn“ der spezialisierten Sensornetzprotokolle gerne für Vergleiche herangezogen.

Protokollaufbau

Das Protokoll beruht auf der Rendezvous-Technik, die auch in anderen Anwendungsgebieten der Informatik zum Einsatz kommt. Ein Netzwerkknoten, der eine Nachricht senden möchte, schickt zunächst eine Sendeanfrage (RTS, request to send) an den Adressaten. Bei Empfangsbereitschaft antwortet der Angesprochene darauf mit einer Sendebestätigung (CTS, clear to send). Daraufhin versendet der Sender das eigentliche Datenpaket, das der Empfänger mit einer Empfangsbestätigung (ACK, acknowledgement) quittiert. Diese Verabredung zum Datenaustausch versichert dem Sender, dass der Adressat wirklich zuhört und ermöglicht es dem Empfänger, eine Datensendung ohne Zutun abzulehnen, weil er gerade anderweitig kommuniziert.

Der Rest des Protokolls ist in drei Aufgabenbereiche gegliedert: Tagesablauf, Kommunikationsstörungen und Nachrichtenübermittlung.

Tagesablauf

Sensorknoten besitzen die Fähigkeit, in einen Standby-Modus zu wechseln, in dem alle Bauteile bis auf die Uhr abgeschaltet werden. In dieser „Schlafphase“ ist ihr Energieverbrauch minimal, sie sind aber inaktiv und können insbesondere keine Nachrichten entgegennehmen. S-MAC gibt den Sensorknoten mit regelmäßigen Wach-und-Schlaf-Zyklen einen festen „Tagesablauf“ vor. Dabei sollten möglichst viele Knoten demselben Tagesablauf folgen, um die sichere Kommunikation während der gemeinsamen Wachzeit zu gewährleisten.

Die Abstimmung der Tagesabläufe erfolgt über Synchronisationsimpulse (SYNCs), kurze Nachrichten mit dem sinngemäßen Inhalt: „Es ist jetzt … Uhr. Ich gehe in x Sekunden schlafen.“ Nach dem Anschalten wartet jeder Sensorknoten auf eine SYNC-Nachricht eines anderen Knoten. Empfängt er keine, sendet er nach einer zufälligen Zeitdauer selbst eine. Wer ein SYNC empfängt, passt sich dem darin angegebenen Tagesablauf an. War es das erste empfangene SYNC, ermittelt er den Zeitunterschied d zwischen seiner aktuellen Uhrzeit und der Uhrzeit der Nachricht und sendet ein neues SYNC mit Inhalt: „Es ist jetzt … Uhr. Ich gehe in x - d Sekunden schlafen.“ Jeder Knoten merkt sich die Tagesabläufe seiner Nachbarknoten, um bei Bedarf durch Bruch mit dem eigenen Tagesablauf Kontakt herzustellen.

Da mehrere Synchronisationsimpulse gleichzeitig oder zeitlich versetzt an verschiedenen Enden des Netzes starten können, kann das Netz bei diesem Verfahren in Verbünde zerfallen, die unterschiedlichen Tag-und-Nacht-Rhythmen folgen. An den Grenzen dieser Gruppen sitzen dann Sensorknoten, die den Tagesabläufen aller benachbarten Verbünde folgen. Dies stellt zwar die Kommunikation zwischen den Knotenverbänden sicher, da die Grenzknoten aber mehr Wachzeiten haben als innere Knoten verbrauchen sie mehr Energie und fallen früher aus.

Selbst elektronische Uhren gehen niemals völlig gleich. Es ist daher notwendig, durch erneute Synchronisationsimpulse das allmähliche „Auseinanderdriften“ der Uhrzeiten zu verhindern. S-MAC sieht dazu eine Aufteilung der Wachphase in zwei Unterphasen vor: Die kürzere erste ist für Versand und Empfang von Synchronisationsnachrichten bestimmt, die längere zweite für den eigentlichen Datenaustausch.

Häufig erneute Synchronisationsimpulse ermöglichen es zudem, neue Knoten bei fortlaufendem Betrieb in das Netz aufzunehmen. Sie empfangen ein SYNC des bestehenden Netzes und passen sich dem erhaltenen Tagesablauf an.

Kommunikationsprobleme

Kommunikationsprobleme in Rechnernetzen führen zu Datenverlust und Energieverschwendung und müssen daher vermieden werden. S-MACs Rendezvousschema reduziert von Natur aus das Problem der Hidden Stations, weitere Bestandteile des Protokolls zur Vermeidung anderer Störungen werden im Folgenden dargestellt.

Datenkollisionen treten auf, wenn zwei Knoten gleichzeitig über das gemeinsame Kommunikationsmedium senden: Die Signale überlagern sich und beide Nachrichten werden unbrauchbar. Um Kollisionen zu vermeiden, baut S-MAC auf physische und virtuelle Trägerprüfung (Carrier Sense), also die Fähigkeit, eine Belegung des Kommunikationsmediums vor dem Senden auszuschließen. Dabei bezeichnet physische Trägerprüfung das tatsächliche kurze Abhören des Mediums, um eine anderweitige Nutzung auszuschließen, virtuelle Trägerprüfung das Vorausahnen anderer Kommunikation aufgrund vorweg bekanntgegebener Sendewünsche.

Die virtuelle Trägerprüfung vermeidet gleichzeitig Overhearing. Beim Overhearing verschwendet ein Knoten Energie, weil er Datenaustausch mitanhört, der nicht für ihn bestimmt ist und mit dem er nichts anfangen kann. Die virtuelle Trägerprüfung wird umgesetzt, indem in jeder Sendeanfrage gleichzeitig die Länge der zu sendenden Nachricht mitgeteilt wird. Mithörende Knoten können daraus schließen, wie lange das Kommunikationsmedium nach Beginn der Datenübertragung belegt sein wird, und können sich für diese Zeit schlafen legen. Dies wird mit Hilfe eines Netzbelegungsvektors (NAV, network allocation vector) umgesetzt. Der NAV wird auf den in der Sendeanfrage mitgeteilten Wert gesetzt und über einen Zeitgeber nach und nach herunter gezählt. Erreicht der NAV den Wert 0, so ist das Medium laut virtuellem Carrier Sense frei und der Knoten wird aufgeweckt. Nach Rückversicherung mit dem physischen Carrier Sense kann der Knoten dann die eigene Datenübertragung anstoßen.

Nachrichtenübermittlung

Bei Rechnernetzen ist es üblich, große zusammenhängende Dateneinheiten in kleine Pakete oder Fragmente aufzuspalten. Tritt beim Übermitteln einer großen Dateneinheit ein Fehler auf, so müssen alle Daten erneut gesendet werden, tritt in einem Paket ein Übermittlungsfehler auf, so genügt es, das einzelne Datenfragment zu wiederholen. Dieser Ansatz wird auch bei S-MAC verfolgt. Üblicherweise würde das Rendezvousschema nun auf Paketebene angewandt, also jedes Einzelpaket mit einem kompletten Satz Rendezvousnachrichten RTS, CTS und ACK bestätigt. Dieser unnötige Mehraufwand wird in S-MAC reduziert, indem alle zusammenhängenden Pakete an einem Stück hintereinander gesendet werden, so dass nur ein RTS und CTS pro kompletter Dateneinheit benötigt werden.

S-MAC-Protokoll. Jedes Paket wird mit einem ACK bestätigt. Paket 2 geht verloren und wird wegen ausbleibendem ACK wiederholt.

Der Empfänger bestätigt jedes erhaltene Paket mit einem ACK, bei dessen Ausbleiben der Sender das letzte Fragment wiederholt. Man könnte sich auch hier auf ein einzelnes ACK am Ende der Gesamtnachricht beschränken, die Entwickler haben sich jedoch gezielt dagegen entschieden, um eine Rückversicherung gegen die Kommunikationsstörung Hidden Station aufzubauen: Das fortlaufende Versenden der ACKs hält Knoten im Umfeld des Empfängers davon ab, eine Kommunikation zu starten, selbst wenn sie vom RTS-CTS-Austausch der Kommunizierenden nichts mitbekommen haben. Für eine weitere Verbesserung empfiehlt S-MAC, die erwartete Restdauer des Datenaustauschs auch in jedem Paket und ACK mit anzugeben; neu hinzugekommene oder „falsch“ erwachte Knoten können sich so noch einmal schlafen legen.

Effizienz

Da S-MAC eines der ersten umfassenden Netzwerkprotokolle für Sensornetze war, verglichen die Entwickler ihr Verfahren nicht mit anderen Sensornetzprotokollen, sondern mit dem Industriestandard IEEE 802.11 für drahtlose Netzwerkkommunikation. Da Sensornetze Ad-hoc-Netze bilden, käme auch 802.11 in dessen Ad-hoc-Modus als Protokoll für Sensornetze in Frage. Tatsächlich wurde 802.11 aber für völlig andere Anforderungen geschaffen und geht beispielsweise in keiner Weise auf das Thema Energieeffizienz ein. S-MAC ist in Sensornetzen dementsprechend deutlich effizienter als 802.11.^[1]

S-MAC weist zwei große Schwachpunkte auf. Zum einen ist dies die bereits oben dargestellte Entstehung von mehrfach belasteten Grenzknoten, wenn das Netz von den Synchronisationsimpulsen in mehrere Verbünde zerlegt wird. Da die Grenzknoten mehreren Tagesabläufen gleichzeitig folgen, also mehr Wachzeiten haben als andere Knoten, verbrauchen sie mehr Energie und fallen früher aus. Gerade die Grenzknoten sind aber besonders wichtig, da ohne sie das Gesamtnetz in mehrere Einzelnetze zerfällt.

Zum anderen kann es vorkommen, dass Empfänger schlafen gehen, bevor der Absender sie mit einer Sendeanfrage kontaktieren kann. Läuft gerade eine Kommunikation, so kann ein anderer Sensorknoten, der Daten senden möchte, keine Sendeanfrage anbringen. Der Adressat der Daten bekommt daher von dem bestehenden Sendewunsch nichts mit und geht möglicherweise schlafen, bevor der Sender zum Abschicken der Sendeanfrage kommt. Hier setzt der S-MAC-Nachfolger Timeout Media Access Control (T-MAC) an, um eine Effizienzsteigerung zu erreichen.

Ferner wurde kritisiert, dass S-MAC deutlich über das Ziel eines MAC-Protokolls hinaus schießt, indem es gleichzeitig Netzinitialisierung, Synchronisation, Datenfragmentierung und Hidden-Station-Behandlung umsetzt. Diese Aufgaben sollten nach den Entwicklern der Berkeley Media Access Control (B-MAC) besser in eigene konfigurierbare Module ausgelagert werden.^[5]

Später entwickelte Sensornetzprotokolle gingen gezielt auf die Schwächen S-MACs ein und erwiesen sich erwartungsgemäß als effizienter. Bereits der direkte Nachfolger T-MAC konnte durch geringfügige Modifikationen die Energieausbeute gegenüber S-MAC verbessern.^[6] B-MAC überflügelte S-MAC hinsichtlich Datendurchsatz und Energieeffizienz.^[7] Großflächig angelegte Vergleiche von Sensornetzprotokollen gibt es nicht; einige Forscher bezweifeln die Sinnhaftigkeit solcher Studien und gehen davon aus, dass es bei Sensornetzen niemals das Protokoll geben wird, sondern immer eine Auswahl von Protokollen, die sich für unterschiedliche Szenarien unterschiedlich gut eignen.^[8]

Weblinks

• Sensor-MAC (S-MAC): Medium Access Control for Wireless Sensor Networks – Projektseite der S-MAC-Entwickler

Quellen

Hauptquelle:

• W. Ye, J. Heidemann, D. Estrin: An Energy-Efficient MAC Protocol for Wireless Sensor Networks. In: Proceedings of the 21st International Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2002), New York, USA, Juni 2002. Erstveröffentlichung als technischer Report ISI-TR-543, USC/ISI, September 2001.

Einzelnachweise:

1. ↑ ^{a b} s. Hauptquelle
2. ↑ W. Ye, University of Southern California: SCADDS: Scalable Coordination Architectures for Deeply Distributed Systems. Ausgewertet am 23. März 2007.
3. ↑ S. Singh, C. S. Raghavendra: PAMAS: Power aware multi-access protocol with signalling for ad hoc networks. In: ACM Computer Communication Review, 28(3), S. 5–26, Juli 1998
4. ↑ K. Sohrabi, G. J. Pottie: Performance of a novel self-organization protocol for wireless ad hoc sensor networks. In: Proceedings of the IEEE 50th Vehicular Technology Conference 1999, Vol. 2, S. 1222–1226.
5. ↑ J. Polastre, J. Hill, D. Culler: Versatile Low Power Media Access for Wireless Sensor Networks. In: Proceedings of the Second ACM Conference on Embedded Networked Sensor Systems (SenSys’04), 3. bis 5. November 2004.
6. ↑ T. van Dam, K. Langendoen: An Adaptive Energy-Effcient MAC Protocol for Wireless Sensor Networks. In: Proceedings of the First ACM Conference on Embedded Networked Sensor Systems (SenSys), Los Angeles, Kalifornien, November 2003.
7. ↑ I. Rhee, A. Warrier, M. Aia, J. Min: Z-MAC: A Hybrid MAC for Wireless Sensor Networks. Technischer Bericht, Department of Computer Science, North Carolina State University, April 2005.
8. ↑ I. Demirkol, C. Ersoy, F. Alagöz: MAC Protocols for Wireless Sensor Networks: A Survey. In: IEEE Communications. 44(4), S. 115-121. April 2006