We reconsider two well-known distributed randomized algorithms computing a maximal independent set, proposed in the seminal work of Luby (1986). We enhance these algorithms such that they become self-stabilizing without sacrificing their run-time, i.e., both stabilize in O(log⁡n) synchronous rounds with high probability on any n-node graph. The first algorithm gets along with three states, but needs to know an upper bound on the maximum degree. The second does not need any information about the graph, but uses a number of states that is linear in the node degree. Both algorithms use messages of logarithmic size.

We consider self-stabilizing algorithms to compute a Maximal Independent Set (MIS) in the extremely weak beeping communication model. The model consists of an anonymous network with synchronous rounds. In each round, each vertex can optionally transmit a signal to all its neighbors (beep). After the transmission of a signal, each vertex can only differentiate between no signal received, or at least one signal received. We assume that vertices have some knowledge about the topology of the network.

We consider self-stabilizing algorithms to compute a Maximal Independent Set (MIS) in the extremely weak beeping communication model. The model consists of an anonymous network with synchronous rounds. In each round, each vertex can optionally transmit a signal to all its neighbors (beep). After the transmission of a signal, each vertex can only differentiate between no signal received, or at least one signal received. We also consider an extension of this model where vertices can transmit signals through two distinguishable beeping channels. We assume that vertices have some knowledge about the topology of the network. We revisit the not self-stabilizing algorithm proposed by Jeavons, Scott, and Xu (2013), which computes an MIS in the beeping model. We enhance this algorithm to be self-stabilizing, and explore three different variants, which differ in the knowledge about the topology available to the vertices and the number of beeping channels. In the first variant, every vertex knows an upper bound on the maximum degree $Δ$ of the graph. For this case, we prove that the proposed self-stabilizing version maintains the same run-time as the original algorithm, i.e., it stabilizes after $O(\log n)$ rounds w.h.p. on any $n$-vertex graph. In the second variant, each vertex only knows an upper bound on its own degree. For this case, we prove that the algorithm stabilizes after $O(\log n\cdot \log \log n)$ rounds on any $n$-vertex graph, w.h.p. In the third variant, we consider the model with two beeping channels, where every vertex knows an upper bound of the maximum degree of the nodes in the $1$-hop neighborhood. We prove that this variant stabilizes w.h.p. after $O(\log n)$ rounds.

The emerging implementation of urban air mobility (UAM) is in need of a robust low latency communication system. The key priority is to cope with the required high level of safety assurance. 5G communication standards lay the foundation for a promising communication infrastructure, yet there exists the challenge of connectivity and coverage through the base station network. In this paper, we address this aspect and study the realization of a reliable and efficient 5G base station plan and evaluate its influence on the performance of the UAM communication system through simulations. Our findings can assist in real UAM deployment scenarios to search for the most cost effective radio network planning solution. We focus on the 3d-channel model and on the number and placement of base stations. As a use case we consider the Hamburg metropolitan region.

In the Industrial Internet of Things (i.e., IIoT), the standardization of open technologies and protocols has achieved seamless data exchange between machines and other physical systems from different manufacturers. At the MAC sublayer, the industry-standard protocols IEEE 802.15.4 Time Slot Channel Hopping (TSCH) and Deterministic and Synchronous Multi-channel Extension (DSME) show promising properties for high adaptability and dynamically changing traffic. However, performance comparison between these MAC protocols rarely has gone beyond a simulation phase. This work presents the results of such a comparison on physically deployed networks using the facilities of the FIT-IoTLab. The evaluation includes fully implementing an IIoT protocol stack based on MQTT in Contiki-NG. It comprises the integration of DSME as part of Contiki-NG’s software stack through OpenDSME, the only publicly available implementation of DSME. Results show that both protocols suit IIoT applications, particularly for data collection. The comparison between TSCH and DSME also includes an evaluation of distributed schedulers for both MAC modes and one autonomous scheduler for TSCH within a UDP protocol stack.

The MAC protocol IEEE 802.15.4 DSME has features for WSNs to support exigent requirements such as high reliability and adaptability to dynamic traffic. This work introduces the concept of a virtual sink, which comprises the sink and its 1-hop neighbors, a.k.a. satellites, as the core of a strategy to alleviate the burden caused by the funneling effect in data collection scenarios. Our strategy enables the coexistence of a centralized scheduling algorithm at the virtual sink and a decentralized scheduling algorithm for the remaining nodes of the network. Through a simulative assessment, we compare the performance of the virtual sink-based strategy with the status quo of DSME via a decentralized slot scheduler TPS. Results show an improvement of the network throughput of up to 38% and a reduction of the energy consumption of about 30% at satellites.

Many MAC protocols for the Industrial Internet of Things, such as IEEE 802.15.4 and its extensions, require contention-based channel access for management traffic, e.g., for slot (de)allocations and broadcasts. In many cases, subtle but hidden patterns characterize this secondary traffic, but present contention-based protocols are unaware of these patterns and therefore cannot exploit them. Especially in dense networks, these protocols often do not provide sufficient throughput and reliability for primary traffic, i.e., they cannot allocate transmission slots in time. In this paper, we propose QMA, a contention-based multiple access scheme based on Q-learning. It dynamically adjusts transmission times to avoid collisions by learning patterns in contention-based traffic. We show that QMA solves the hidden node problem without the overhead for RTS/CTS messages and, for example, increases throughput from 10 packets/s to 50 packets/s in a hidden three-node scenario without sacrificing reliability. Additionally, QMA's scalability is evaluated in a realistic scenario for slot (de)allocation in IEEE 802.15.4 DSME, where it achieves up to twice more slot (de)allocations per second.

The Deterministic and Synchronous Multi-Channel Extension (DSME) protocol is a recent amendment to the IEEE 802.15.4 standard. It combines contention-based and time-division medium access, offers channel diversity, and is aimed to support IIoT applications with stringent requirements in terms of timeliness and reliability. In this paper, we show how to configure DSME for a given data collection task. This includes the definition of the slot and frame length and the slot and channel schedule. We formulate different scheduling strategies as linear programs minimizing latency and energy. We verify our results through theoretical analysis and simulations and compare them with state-of-the-art scheduling algorithms. The results indicate a reduced delay of up to 80% for deep networks while also increasing reliability. Additionally, the proposed scheduling strategies significantly reduce the required buffer size.

This article presents a middleware that provides a communication and data dissemination infrastructure suitable for the operation environment of the Internet of Things (IoT). The middleware realizes the channel-based publish/subscribe paradigm that has been identified as a valid means to asynchronously disseminate data in IoT applications. The novelty lies in the routing algorithm PSVR that greatly reduces the path lengths to deliver publications and its suitability for scenarios with a high subfluctuation rate. The middleware is self-stabilizing and eventually provides safety and liveness properties such as the guaranteed delivery of all published messages to all subscribers and the correct handling of subscriptions and unsubscriptions, while no error occurs. The evaluation of the middleware, based on simulations and a real deployment, shows that it has a low memory footprint and scales well with the number of nodes.

The loose coupling and the inherent scalability make publish/subscribe systems an ideal candidate for event-driven services for wireless networks using low power protocols such as IEEE 802.15.4. This work introduces a distributed algorithm to build and maintain a routing structure for such networks. The algorithm dynamically maintains a multicast tree for each node. While previous work focused on minimizing these trees we aim to keep the effort to maintain them in case of fluctuations of subscribers low. The multicast trees are implicitly defined by a novel structure called augmented virtual ring. The main contribution is a distributed algorithm to build and maintain this augmented virtual ring. Maintenance operations after sub-and unsubscriptions require message exchange in a limited region only. We compare the average lengths of the constructed forwarding paths with an almost ideal approach. As a result of independent interest we present a distributed algorithm using messages of size O(log n) for constructing virtual rings of graphs that are on average shorter than rings based on depth first search.

Self-stabilizing systems have in theory the unique and provable ability, to always return to a valid system state even in the face of failures. These properties are certainly desirable for domains like wireless ad-hoc networks with numerous unpredictable faults. Unfortunately, the time in which the system returns to a valid state is not predictable and potentially unbound. The failure rate typically depends on physical phenomena and in self-stabilizing systems each node tries to react to failures in an inherently adaptive fashion by the cyclic observation of the states of its neighbors. When state changes are either too quick or too slow the system might never reach a state that is sufficiently stable for a specific task. In this paper, we investigate the influences of the error rate on the (stability) convergence time on the basis of topology information acquired in real network experiments. This allows us to asses the asymptotic behavior of relevant self-stabilizing algorithms in typical wireless networks.

Providing dependability is still a major issue for wireless mesh networks, which restrains their application in industrial contexts. The widespread CSMA/CA medium access can provide high throughput and low latency, but can not prevent packet loss due to collisions, especially in very large and dense networks. Time slotted medium access techniques together with a distributed slot management, as proposed by the Distributed Synchronous Multi-channel Extension (DSME) of the IEEE 802.15.4 standard, are promising to provide low packet loss, high scalability and bounded end-to-end delays. However, our implementation, openDSME, exposed some weaknesses. While the allocated slots allow for reliable data transmission, the slot management itself is conducted via CSMA/CA and is thus vulnerable to packet loss, eventually leading to an inconsistent slot allocation.

The erratic behavior of wireless channels is still a major hurdle in the implementation of robust applications in wireless networks. In the past it has been argued that self-stabilization is a remedy to provide the needed robustness. This assumption has not been verified to the extent necessary to convince engineers implementing such applications. A major reason is that the time in which a self-stabilizing system returns to a valid state is unpredictable and potentially unbound. Failure rates typically depend on physical phenomena and in self-stabilizing systems each node tries to react to failures in an inherently adaptive fashion by the cyclic observation of its neighbors' states. When the frequency of state changes is too high, the system may never reach a state sufficiently stable for a specific task. In this paper we substantiate the conditions under which self-stabilization leads to fault tolerance in wireless networks and look at the myths about the power of self-stabilization as a particular instance of self-organization. We investigate the influences of the error rate and the neighbor state exchange rate on the stability and the convergence time on topology information acquired in real network experiments.

Self-stabilizing systems tolerate transient faults by always returning to a legitimate system state within a finite time. This goal is challenged by several system features such as arbitrary system states after faults, various process execution models, and constrained process communication means. This work designs self-stabilizing distributed algorithms from the perspective of game theory, achieving an intended system goal through private goals of processes. We propose a generic game design for identifying a maximal independent set (MIS) or a maximal weighted independent set (MWIS) among all processes in a distributed system. From the generic game several specific games can be defined which differ in whether and how neighboring players influence each other. Turning the game designs into self-stabilizing algorithms, we obtain the first algorithms for the MWIS problem and also the first self-stabilizing MIS algorithm that considers node degree (including an analysis of its performance ratio). We also show how to handle simultaneous moves of processes in some process execution models. Simulation results indicate that, for various representative network topologies, the new algorithm outperforms existing methods in terms of MIS size and convergence rate. For the MWIS problem, the new algorithms performed only slightly worse than centralized greedy counterparts.

A sustainable, uniform, and utility-maximizing operation of energy-harvesting sensor networks requires methods for aligning consumption with harvest. This article presents a lightweight algorithm for online load adaptation of energy-harvesting sensor nodes using supercapacitors as energy buffers. The algorithm capitalizes on the elementary relationship between state of charge and voltage that is characteristic for supercapacitors. It is particularly designed to handle the nonlinear system model, and it is lightweight enough to run on low-power sensor node hardware. We define two energy policies, evaluate their performance using real-world solar-harvesting traces, and analyze the influence of the supercapacitor’s capacity and imprecisions in harvest forecasts. To show the practical merit of our algorithm, we devise a load adaptation scheme for multihop data collection sensor networks and run a 4-week field test. The results show that (i) choosing a duty cycle a priori is infeasible, (ii) our algorithm increases the achievable work load of a node when using forecasts, (iii) uniform and steady operation is achieved, and (iv) depletion can be prevented in most cases.

This paper presents a new transformation which adds fault-containment properties to any silent self-stabilizing protocol. The transformation features a constant slow-down factor and the fault-gap – that is the minimal time between two containable faults – is constant. The transformation scales well to arbitrarily large systems and avoids global synchronization.

Abstract A novel beacon‐less algorithm called Blind Geographic Routing (BGR) is presented, which comes with an effective and robust recovery strategy to circumvent voids, and a new technique to avoid simultaneous forwarding by more than one node, features not included in other beacon‐less algorithms. BGR is the first beacon‐less algorithm that also works in 3D topologies. Additionally, BGR supports different delivery semantics, which specify how close a node must be to the destination location in order to receive the message, and how many nodes shall receive it. These semantics allow for routing not only to designated nodes with network‐wide known locations such as sinks, but to arbitrary destinations within the network area. It is shown through extensive simulation that BGR performs well even in the case of mobility, radio irregularity, and location errors, while GPSR as a beacon‐based algorithm suffers from severe problems in realistic scenarios that do not follow the unit disk graph model, even with recent enhancements of the original GPSR algorithm. Copyright © 2009 John Wiley & Sons, Ltd.

A particular class of data intensive wireless sensor networks are those networks where sensors periodically measure data with high rates. The focus of this work is on the efficient transport of high volumes of sampled data through a multi-hop network with limited resources using a routing tree. This paper analyzes TDMA schemes for this purpose with respect to buffer usage and energy consumption. In particular, it is shown, that classical TDMA schemes are not optimal for tree-routing in data-intensive sensor networks.

Sensor networks are increasingly used in applications where sensors periodically measure data with high rates. The reliable transport of high volumes of sampled data through a multi-hop network with limited resources requires sophisticated protocols. This paper presents a novel protocol for this task that uses minimal energy, provides high throughput, and requires only small amounts of additional buffer. The protocol is based on a dynamic TDMA scheme and is robust against omission failures.

P2P data stores excel if availability of inserted data items must be guaranteed. Their inherent mechanisms to counter peer population dynamics make them suitable for a wide range of application domains. This paper presents and analyzes the fusion maintenance operation. It aims at reorganizing parts of our P2P data store in case the peer population shrinks so much that data availability is threatened. To this end, we present a formal cost model that peers use to estimate the optimal invocation point of a fusion. Finally, we present experimental results that validate our cost model by simulating various network conditions

This paper presents HTTPExplorer, an interactive tool to explore the Hypertext Transfer Protocol. The intention is to use the tool in a course on web-based applications to support the learning of HTTP, the most significant protocol used on the internet today. A web-based user-interface allows students to contact any HTTP-Server connected to the internet, to issue a request and to make the data flow between a client and the server completely visible. The tool can be used by novices to get first experience with HTTP and by advanced users to experiment with more complex features. We also report about some initial experience gained in the usage of HTTPExplorer in a real course.

Regular trees are a natural extension of finite trees, which have many applications. The path-embedding problem is to determine whether a regular tree S can be obtained from another regular tree T by deleting (probably infinitely many) subtrees of T. This paper explores efficient algorithms for the path-embedding problem in ordered and unordered trees. Given two regular trees S and T represented by rational graphs, our algorithms solve the ordered version of path-embedding problem in O(|E_S||E_T|) time and the unordered version in O(|E S ||E T |D S D T ) time. Here |E S | denotes the number of edges in the rational graph for S, and D S denotes the maximum outdegree of a vertex inS. We also demonstrate that our approach can be applied to pattern matching problems for regular trees recently studied by Fu J. Algorithms, 22 (1997), pp. 372--391].

Active networks allow protocol processing code to be loaded dynamically into network nodes at run-time. This code can perform tasks specific to a stream of packets or even a single packet. In this paper we compare two active network architectures: the active node transfer system (ANTS) and the messenger system (M0). We have implemented a robust audio multicast protocol and a layered video multicast protocol with both active network systems. We discuss the differences of the two systems, evaluate architectural strengths and weaknesses, compare the runtime performance, and report practical experience and lessons learned.

In an object-oriented database system (OODBS), objects exist persistently and object I/O is transparent to the programmer. Therefore, some mechanism in the system must initiate I/O as the program runs. In this paper we present an approach based on pattern matching and dynamic programming that allows a program to interact efficiently with the runtime storage layer. We are interested in allowing programs to manipulate very large objects without necessarily reading them entirely. If a program touches only a small part of a large object, the problem is how to determine the part of the object needed. In this paper, we present an approach based on pattern matching and dynamic programming to resolve this problem.