1,721,105 research outputs found
Zeit- und speichereffiziente selbststabilisierende Algorithmen
No full textSelf-stabilization is a general approach to design a system to tolerate arbitrary transient faults. This thesis presents new time- and space-efficient self-stabilizing algorithms for well-known problems in graph theory and provides new complexity analyzes for existing algorithms. The main focus of this thesis is on the proof techniques used in the complexity analyzes and the design of the algorithms.Selbststabilisierung ist ein Ansatz, der ein verteiltes System in die Lage versetzt, beliebige transiente Fehler zu tolerieren. In dieser Dissertation werden neue selbststabilisierende Algorithmen für bekannte graphentheoretische Probleme vorgestellt. Darüber hinaus werden bestehende Verfahren auf ihre Komplexität untersucht. Der Schwerpunkt dieser Arbeit liegt auf den Beweismethoden, die in der Komplexitätsanalyse benutzt werden, sowie auf dem Design der Algorithmen
Scalable wireless multi-hop networks for industrial applications
No full textFunktechnik verspricht flexible und kosteneffiziente Maschinenkommunikation. Allerdings können gleichzeitige Übertragungen von vielen Geräten zu Paketverlust führen und die für industrielle Anwendungen notwendige Zuverlässigkeit untergraben. Die Dissertation untersucht und entwickelt Techniken für vermaschte IEEE 802.15.4 Netzwerke mit Fokus auf dem Zeitschlitzverfahren DSME. Die Nützlichkeit wird in einem ganzheitlichen Ansatz mit Simulationen, formalen und analytischen Analysen und realen Netzen gezeigt. Für Nutzungen in Forschung und Anwendungen wurde die frei verfügbare DSME Implementierung openDSME entwickelt und es werden anwendungsspezifische Einblicke gegeben.Wireless technology promises flexible and cost-efficient machine-to-machine communication. However, high packet loss can emerge from simultaneous transmissions of many devices, undermining the reliability required for industrial applications. This thesis analyzes and develops techniques for time-slotted multi-hop communication with focus on IEEE 802.15.4 DSME. In a holistic approach, simulations, formal and analytical analyses and testbed experiments are combined, concluding the utility of the proposed methods. For future usage in research and real-world deployments, openDSME is developed as open-source implementation of DSME and application-specific insights are provided
Forwarding strategies for 6LoWPAN-fragmented IPv6 datagrams
No full textDiese Arbiet untersucht verschiedene Implementierungsstrategien für den Weiterleitungsaspekt des
6LoWPAN protocols für „low power and lossy networks“ (LLNs). Die Leistungsfähigkeit in
Hinblick auf Latenz und Zuverlässigkeit wird für das LLN-typische Datensammlung-
Verkehrsmuster für direkte und reassemblierende Strategien untersucht. Ein neuartiger Ansatz
basierend auf Lauschen und dem Aussetzen von Transmissionen wird entwickelt und es wird
gezeigt, dass dieser die Ende-zu-Ende-Zuverlässigkeit in einem Großteil der untersuchten
Simulationsszenarien und Testnetzwerken signifikant verbessert.This dissertation explores different implementation strategies for the fragment-forwarding aspect of
the 6LoWPAN protocol for “low power and lossy networks” (LLNs). The performance in terms of
latency and reliability for the LLN-typical collection traffic pattern is analyzed for several “direct”
and “reassembling” strategies. A novel approach based on snooping and suspending transmissions is
developed and it is shown that this approach improves the end-to-reliability significantly in most of
the evaluated simulation and testbed scenarios
A reliable and redundant communication system for safe urban air mobility operations
No full textUrban Air Mobility (UAM) is a new concept that aims at supplementing current public transportation systems in dedicated use cases. UAM implementation requires complex integration of different engineering fields, including command, control, and communication for safe operation. This dissertation explores the aspect of communication and proposes solutions to enhance the performance to support reliable and redundant communication for safe UAM operations. Network planning, channel modeling, ground station infrastructure for redundancy provision, and interference management are investigated. Simulation results show that employing 5th generation communication standards with efficient network and resource management, particularly with device-to-device technology, provides the needed degree of performance.Urban Air Mobility (UAM) ist ein neues Konzept, das darauf abzielt, die derzeitigen öffentlichen Verkehrssysteme in bestimmten Anwendungsfällen zu ergänzen. Die Umsetzung von UAM erfordert eine komplexe Integration verschiedener Ingenieursbereiche, darunter Steuerung, Kontrolle und Kommunikation für einen sicheren Betrieb. Diese Dissertation untersucht den Aspekt der Kommunikation und schlägt Lösungen zur Leistungssteigerung vor, um eine zuverlässige und redundante Kommunikation für einen sicheren UAM-Betrieb zu unterstützen. Untersucht werden Netzwerkplanung, Kanalmodellierung, Bodenstationsinfrastruktur für die Bereitstellung von Redundanz und Interferenzmanagement. Simulationsergebnisse zeigen, dass der Einsatz von Kommunikationsstandards der 5. Generation mit effizientem Netzwerk- und Ressourcenmanagement, insbesondere mit Device-to-Device-Technologie, den erforderlichen Leistungsgrad bietet
Load shaping of thermostatically controllable devices by constructing retail prices
No full textIm Zuge der Energiewende wird der Prozess der Stromnetzstabilisierung durch Ausgleich von Einspeisung und Netzlast aufgrund der ungewissen Verfügbarkeit von erneuerbaren Energien erschwert.
Demand Response (DR) Mechanismen geben Verbrauchern Anreize ihren Stromverbrauch zu verändern, z. B. durch zeitabhängige Strompreise.
Diese Dissertation entwickelt ein preisbasiertes DR-Verfahren für kostenoptimierende Thermostat-gesteuerte Lasten, welches eine Gesamtlast annähernd einer Zielkurve erzeugt.
Es wird ein heuristischer Algorithmus entwickelt um entsprechende Preissignale zu berechnen. Die Funktionalität des Verfahrens wird durch realistische Simulationen validiert.In the course of the energy transition the process of balancing power supply and demand becomes more challenging due to the uncertainty of renewable energy sources.
Demand Response (DR) mechanisms encourage consumers to change their energy consumption, e.g. through time-varying electricity prices.
This dissertation develops a price-based DR mechanism for cost-optimizing thermostatically
controlled loads, which induces an aggregated load profile approximating a target schedule.
A heuristic algorithm is developed to calculate suitable price signals. Simulations of realistic scenarios are analyzed to validate the functionality
RFID based navigation for autonomous vehicles
No full textIn dieser Arbeit wurden die Möglichkeiten eines pheromonbasierten Navigationsverfahrens mittels wiederbeschreibbarer RFID-Tags untersucht. Im Gegensatz zu anderen Ansätzen wird hier auf eine eindeutige Fahrzeuglokalisierung verzichtet. Es wurden Algorithmen für die Navigation entwickelt und in einem Test-System evaluiert. Um eine höhere Fahrgeschwindigkeit zu erreichen, wurden Antikollisionsalgorithmen für das Inventory optimiert. Des Weiteren wurde ein neuer Inventory-Ansatz ausgearbeitet, der insbesondere für die untersuchten Navigationssysteme geeignet ist.In this thesis the possibilities of a pheromone-based navigation system using rewritable RFID tags have been examined. In contrast to other approaches, this system does not make use of an unambiguous localisation of vehicles. Navigation algorithms have been developed and evaluated in a test system. In order to achieve a higher driving speed, the optimisation of current anti-collision algorithms was necessary. Furthermore, a new inventory approach has been introduced, which has strengths in the examined navigation systems
Self-stabilizing algorithms in wireless sensor networks
No full textThe presented dissertation focuses on the applicability of self-stabilizing algorithms
in systems using wireless communication.
Especially wireless sensor networks
(WSN) which use low power radios that are prone to message loss and corruption.
Furthermore, temporary node failures (e.g., due to exhausted batteries) are common
sources of nonconformances. Thus, distributed algorithms, middleware systems, and
applications have to respond to these faults. A typical approach is to foresee such
error situations and program routines to react to them. Algorithms defined in a self-
stabilizing manner (SSA) on the other hand always converge to a defined system state
and remain in it while no fault occurs. Hence, the anticipation of error situations is
no longer a necessity.
Entities in a distributed system (nodes) share certain informations among their
neighborhood (adjacent nodes) and react following the distinct routine of the used
SSA. To this day self-stabilization is primarily a theoretical approach, well studied
concerning, e.g., the bounds of execution steps. Profound practical evaluation, espe-
cially in the presents of rapidly changing neighbor states, as common in WSNs, is
still an open issue.
This work firstly establishes necessities to use SSAs in the wireless domain, con-
cluding that a certain degree of forced stability concerning a nodes neighborhood is
vital. Nevertheless, such a topology control cannot be rigid, e.g., by using a fixed
predefined setup, because node additions or removals cannot be supported. Hence,
a topology control algorithm (TCA) is introduced, generating a trade-off between
forced stability and agility.
Using this TCA as a cornerstone, multiple SSAs are evaluated, and high level al-
gorithms are developed, culminating in a publish/subscribe middleware defined in
a self-stabilizing fashion. The publish/subscribe system relies on a self-stabilizing
spanning tree algorithm and a novel self-stabilizing virtual ring algorithm. Further-
more, the publication routing uses shortcuts in the virtual ring, decreasing routing
paths in the process.
The presented algorithms are evaluated using simulations employing realistic radio
models, as well as implementation on sensor node hardware with low power radios,
low computation power, and restricted memory. The novel publish/subscribe system
is executable on such limited hardware, uses less messages to deliver data to pub-
lishers than a comparable tree-based approach, due to the mentioned shortcuts, and
scales well with the network size. It achieves a compromise between the size and
maintenance effort for routing tables and the length of routing paths.
Concluding, the dissertation provides an incentive to use self-stabilization algo-
rithms in wireless sensor network applications. As shown, even high level systems
like a publish/subscribe middleware can be realized with this inherently fault-tolerant
approach
Cloned Transactions : A New Execution Concept for Transactional Memory
No full textTransactional memory aims to replace mutual exclusion in critical sections with
transactions on shared data to improve the scalability of concurrent
applications and eliminate traditional issues of parallel programming such as
deadlocks/livelocks. One key aspect of transaction processing is the concurrency
control, which is responsible to find an interleaving or overlapping schedule
for running transactions accessing the same shared data and provide a result
equal to some serial execution of the same transactions. In this regard, former
research focused on single-threaded concurrency control schemes using a trial and error
approach: The transaction repeats executing the critical section until
no conflict with other transactions was detected.
This thesis proposes the application of helper threads in transactional
memory to achieve a parallelised transaction processing, which is able to
compute the same critical section in respect to different serialisation orders with other transactions. While
traditional concurrency control has to rollback and start another attempt in the
same thread, this approach aims to compute the next attempt in a helper thread
in parallel to the current attempt computed by a leading thread. Due to the
nature of transactions and concurrent shared memory applications in general, the
introduction of helper threads comes with several new aspects to be considered
on the conceptional and the implementation level.
The work presents concepts for helper thread aided concurrency controls
independently executing the same transaction in parallel instead of sharing
information of the leader thread, to lower the contention. For example, the
detection of conflicts is delegated to a helper thread which executes the same
transaction on the same state of shared data in parallel instead of validating
the data read by the leader. In this manner parallelised transaction processing
has been proposed which executes a transaction in parallel with different
validation schemes: lazy and eager validation. Because the reaction time on
conflicts and execution time differ, they drift apart and compute results for different
serialisation orders.
The work also presents several requirements and sub-systems needed to run
parallelised transactions: The use of so-called transactional
wrappers or pure functions to speedup access to thread private data in
transactional sections cannot be granted, because the private data of the
application thread is now concurrently accessed by the helper thread. Also, a
concept has been developed to clone the state of the transaction start and
transfer the state of the helper committed transaction back to the leader. The
existing sandboxing approach of Dalessandro and Scott to suppress and
prevent errors in transactions resulting from lazy validation has been improved
and memory management inside transactions was adapted.
While the developed approaches can compete in some cases and show good
scalability especially in higher concurrency, the evaluation shows
an unexpected large loss of performance, too. An investigation of hardware
characteristics in respect to memory and cache read/write latency revealed
several scalability issues with concurrent access to the same address. These
issues have significant impact on highly concurrent applications,
which seriously affects the use of transactions in general and
parallelised transactions in particular.Transactional Memory zielt darauf ab wechselseitigen Ausschluss in kritischen Abschnitten durch Transaktionen auf gemeinsamen Daten zu ersetzen, um die Skalierbarkeit nebenläufiger Anwendungen zu verbessern und traditionelle Probleme paralleler Programmierung wie Deadlocks/Livelocks zu eliminieren. Eine Schlüsselrolle in der Transaktionsverarbeitung spielt die Nebenläufigkeitskontrolle, die für das Auffinden verzahnter oder überlappender Ablaufpläne für laufende Transaktionen auf gemeinsamen Daten zuständig ist, deren Ergebnis äquivalent zu einer seriellen Ausführung derselben Transaktionen ist. In dieser Hinsicht konzentrierte sich die bisherige Forschung auf Nebenläufigkeitskontrollen für Transaktionen mit nur einem Ausführungsfaden basierend auf einem Trial and Error-Ansatz: Die Transaktion führt den kritischen Abschnitt solange wiederholt aus, bis kein Konflikt mit anderen Transaktionen für einen Durchlauf entstanden ist.
Diese Arbeit unterbreitet den Vorschlag Hilfs-Threads in Transactional Memory einzusetzen, um eine parallelisierte Transaktionsverarbeitung zu erreichen, die eine gleichzeitige Bearbeitung unterschiedlicher Serialisierungsreihenfolgen auf demselben kritischen Abschnitt in Relation zu anderen laufenden Transaktionen erlaubt. Während bisher bekannte Nebenläufigkeitskontrollen die Transaktion zurücksetzen müssen, um mit dem einen verfügbaren Thread der Transaktion einen weiteren Bearbeitungsversuch hinsichtlich einer neuen Serialisierungsordnung zu starten, erlaubt der hier vorgeschlagene Ansatz den nächsten Bearbeitungsversuch bereits zu Beginn des aktuellen Bearbeitungsversuchs an einen Hilfs-Thread zu delegieren. Aufgrund der Besonderheiten von Transaktionen und nebenläufiger Anwendungen auf gemeinsamen Daten im Allgemeinen, geht die Einführung von Hilfs-Threads mit verschiedenen neuen Aspekten einher, die bei Konzeption und Implementierung zu berücksichtigen sind.
Diese Arbeit präsentiert entwickelte Konzepte für Hilfs-Thread-gestützte Nebenläufigkeitskontrollen, welche unabhängig voneinander dieselbe Transaktion parallel ausführen, anstatt information mit dem Haupt-Thread der Transaktion zu teilen, um die Wechselwirkungen gering zu halten. Beispielsweise wird die Entdeckung von Konflikten an einen Hilfs-Thread delegiert, der dieselbe Transaktion auf demselben Prozesszustand parallel Ausführt, anstatt auf die Daten des Haupt-Threads zuzugreifen und jene auf Konfliktfreiheit zu prüfen. Ein weitergehender hier vorgeschlagener Ansatz mit ähnlichem Aufbau, beinhaltet die gleichzeitige Bearbeitung des kritischen Abschnitt mit unterschiedlichen Validierungsmethoden: späte Validierung (lazy) und direkte Validierung (eager). Weil die Verfahren unterschiedliche Reaktionszeiten hinsichtlich auftretender Konflikte haben, driften die beiden Threads zeitlich auseinander und verfolgen als konsequenz tendentiell unterschiedliche Serialisierungsreihenfolgen hinsichtlich konkurrierender Transaktionen. Diese Arbeit präsentiert desweiteren Anforderungen und Subsysteme, die für die Realisierung parallelisierter Transaktionen benötigt werden: Die verwendung sogenannter "Transactional Wrapper" oder "Pure Functions" muss unterbunden werden, weil die Hilfs-Threads nebenläufige Zugriffe auch auf lokalen Variablen einer Funktion erzeugen. Außerdem wurde eine Konzept zum "Clonen" des Zustands einer Transaktion entwickelt, was den Transfer des Kontrollflusses erlaubt, einerseits beim Betreten des kritischen Abschnitts vom Haupt-Thread zum Hilfs-Thread und anderseits bei einem erfolgreichen Commit vom Hilfs-Thread zurück zum Haupt-Thread. Der existierende Sandboxing-Ansatz für Transactional Memory von Dalessandro und Scott zur Unterdrückung und Vermeidung von Fehlern in der Transaktion aufgrund von später Validierung wurde verbessert und die Speicherverwaltung in Transaktionen an die Umstellungen angepasst.
Während die hier entwickelten Ansätze in einigen Fällen durchaus mit konkurrieren konnten und gute Skalierbarkeit in besonderen Fällen hoher Nebenläufigkeit aufwiesen, zeigte die Evaluierung gleichermaßen unerwartet hohe Leistungseinbußen in anderen Fällen. Eine Untersuchung der Hardware-Charakteristiken in Bezug auf die Latenz von Lese und Schreibzugriffen auf Speicher und Caches enthüllte verschiedene Probleme der Skalierbarkeit von gleichzeitigen Zugriffen auf dieselben Speicheradressen. Diese Probleme haben deutlichen Einfluss auf hochgradig nebenläufige Anwendungen, was die Verwendung von Transaktionen im Allgemeinen und die Verwendung parallelisierter Transaktionen im Besonderen stark beeinträchtigt
Modeling and Assessing an Energy-Aware Power-Supply for Wireless Sensor Nodes
Get PDF[EN] Este trabajo presenta el modelado y evaluación de un sistema de alimentación para el sensor de la plataforma Iris[EN] Wireless sensors networks can be deployed in remote locations due to they do not need
a fixed infrastructure. Therefore, energy scavenging systems are really important to
provide the energy necessary to the sensor nodes and thus maximize its lifetime. This
work presents the modeling and assessing of an energy-aware power-supply system for
the Iris platform sensor. Theoretical models have been developed in order to estimate
the energy in the energy storage supercapacitor depending on the incoming and
outgoing energy. These models can be used to verify that the power-supply system
provides enough energy to the sensor node under the most adverse weather conditions,
and thus assuring the perpetual operation of the sensor nodes without human
intervention. Also, these models will be implemented in a software module that makes
possible the estimation of the sensor nodes¿ lifetime in function of their actual state of
energy. The theoretical results given by these models have been compared with the
results obtained with the real circuit. The comparison between both proves that the
theoretical models are valid for the prediction of the future estate of energy based on the
actual estate of energy.Álvarez Álvarez, J. (2009). Modeling and Assessing an Energy-Aware Power-Supply for Wireless Sensor Nodes. https://riunet.upv.es/handle/10251/27229.Archivo delegad
Resource allocation strategies in multi-hop wireless networks for industrial applications
No full text- …
