Entwicklung und Validierung eines Kalküls zur deterministischen und stochastischen Leistungsanalyse von drahtlosen Sensornetzen
Final Report Abstract
Im Rahmen des Projekts wurden analytische Methoden zur Leistungsmodellierung von Netzwerken untersucht. Der Fokus lag auf der Betrachtung von drahtlosen Sensornetzen (DSN, Englisch: wireless sensor networks, WSN); die grundsatzlichen Methoden sind dabei jedoch nicht unbedingt auf eine Technologie beschrankt, sondern lassen sich prinzipiell auf viele Netzwerktypen anwenden, die sich hinsichtlich Topologie und Verkehrsverhalten entsprechend der Rahmenbedingungen des Netzwerkkalküls modellieren lassen. Das Projekt sah eine grobe Aufteilung der Arbeit in zwei Teilbereiche vor: den deterministischen und den stochastischen Sensornetzkalkul (SNK). Wahrend die deterministische Betrachtung durch die Berechnung absoluter Schranken zwar pessimistische, aber dafür harte Grenzwerte liefert, soll im stochastischen Fall durch eine Relaxation die Berechnung “weicherer” (in einem probablistischen Sinne), aber dafür teils wesentlich einfacher einzuhaltende Grenzen möglich werden. Wahrend für die deterministische Betrachtung schon einige Resultate vorlagen, war zu Projektbeginn der stochastische Netzwerkalkül ein recht junger Forschungszweig, in dem es noch keine vollständig anerkannte Methodik gab. Der deterministische Kalkül wurde im Verlauf des Projekts um eine Methode zur Berechnung scharfer Schranken ergänzt, die aus den Charakteristika von Netzwerk und Datenverkehr ein Optimierungsproblem konstruiert. Dieses Verfahren und eine daraus resultierende Implementierung auf Basis des sogennanten DISCO Network Calculator wurde veroffentlicht. Grundsätzlich ist es somit möglich, präzise Schranken zu ermitteln, in der Praxis skaliert die Methode jedoch zunehmend schlechter bei zunehmender Größe und Komplexität der betrachteten Netze. Darum wurden auch heuristische Verfahren zur Berechnung dieser Schranken entwickelt, welche relativ nah an den optimalen Schranken bleiben, diese aber in keinem Falle unterschreiten, also in diesem Sinne korrekt sind. Ein weiterer Aspekt war die Betrachtung von Bedienstrategien, die nicht dem FIFO-Prinzip folgen. Dies ist ein häufiger Fall in DSNen, da diese of datenabhängige Bedienstrategien verwenden. Wie dargestellt ist, lasst sich eine wesentliche Eigenschaft des deterministischen Netzwerk-Kalküls nicht auf solche nicht-FIFO Netzwerke übertragen: das sogenannte “Pay Bursts Only Once” (PBOO)-Prinzip. Das PBOO-Prinzip nutzt die Verkettung von Dienstkurven über einen Pfad von mehreren Servern, und erreicht so eine lineare Skalierung der Obergrenze für die Verzögerung anstatt der “traditionell” errechneten quadratischen Skalierung. Es wird ein Verfahren prasentiert, durch das unter gewissen Bedingungen und mit Hilfe einer alternativen Charakterisierung der Server auch in nicht-FIFO Systemen wieder linear skalierende Verzögerungsschranken erreicht werden. Die stochastische Betrachtung des grundlegenden Kalküls steckte zu Beginn des Projekts noch in den Kinderschuhen; es gab bereits einige Ansatze, aber keine einheitliche Herangehensweise. Darum kann man es durchaus als Projektbeitrag sehen, hier zunächst eine gewisse Vereinheitlichung durchzuführen (daraus enstand ein Tutorium zum stochastischen Netzwerkkalkül). Im weiteren Verlauf des Projekts wurden dann unter anderem Methoden zur Betrachtung von zufälligen Topologien und zur Modellierung von transformierenden Netzwerk-Elementen entwickelt und analysiert. Hier soll besonders letzteres hervorgehoben werden, da diese transformierenden Netzwerkelemente den stochastischen Sensornetzkalkül derart erweitern, dass man damit das Verlustverhalten von drahtlosen Übertragungsstrecken sehr genau modellieren kann. Dies erweitert das Anwendungsspektrum des Sensornetzwerk-Kalkül und ist darüberhinaus auch allgemeiner für viele komplexe Szenarien von verteilten Systemen interessant. Über die gesamte Laufzeit fanden begleitende Arbeiten statt, die diverse Resultate des Sensor-netzkalküls praktisch und simulativ validieren.
Publications
- Dynamic Demultiplexing in Network Calculus – Theory and Application. Performance Evaluation, Elsevier, 68(2):201
H. Wang, J. B. Schmitt, und I. Martinovic
- Searching for Tight Performance Bounds in Feed-Forward Networks. In B. Müller-Clostermann, K. Echtle, und E. P. Rathgeb, editors, 15th International GI/ITG Conference on “Measurement, Modelling and Evaluation of Computing Systems” and “Dependability and Fault Tolerance” (MMB/DFT 2010), volume 5987 of Lecture notes in Computer Science, Seiten 227–241, Essen, Germany, März 2010. GI/ITG, Springer
A. Kiefer, N. Gollan, und J. B. Schmitt
- On Expressing Networks with Flow Transformations in Convolution-Form. In The 30th IEEE International Conference on Computer Communications (INFOCOM 2011), Shanghai, China, April 2011
F. Ciucu, J. B. Schmitt, und H. Wang
- Pay Bursts Only Once Holds for (Some) Non-FIFO Systems. In The 30th IEEE International Conference on Computer Communications (INFOCOM 2011), Shanghai, China, April 2011
J. B. Schmitt, N. Gollan, S. Bondorf, und I. Martinovic
- Planning the Trajectories of Multiple Mobile Sinks in Large-Scale, Time-Sensitive WSNs. In The 7th IEEE International Conference on Distributed Computing in Sensor Systems (IEEE DCOSS 2011), Barcelona, Spain, Juni 2011
W. Y. Poe, M. Beck, und J. B. Schmitt
