Search

Complex networks are known to be vulnerable to the failure of components in terms of structural robustness. An as yet less researched topic is dynamical robustness, which refers to the ability of a network to maintain its dynamical activity against local disturbances. This paper introduces a new type of attack—the overload attack—to disturb the network’s dynamical activity. The attack is based on the load redistribution model for sequential attacks. The main contribution are heuristics to assess the vulnerability of complex networks with respect to this type of attack. The effectiveness of the heuristics is demonstrated with an application for real power networks.

The paper proposes a demand response scheme controlling many domestic electric water heaters (DEWHs) with a price function to consume electric power according to a target schedule. It discusses at length the design of an algorithm to calculate the price function from a target schedule. The price function is used by the control of each DEWH to automatically and optimally minimize its local heating costs. It is demonstrated that the resulting total power consumption approximates the target schedule. The algorithm was successfully validated by simulation with a realistic set of 50 DEWHs assuming perfect knowledge of parameters and water consumption. It is shown that the algorithm is also applicable to clusters of large numbers of DEWHs with statistical knowledge only. However, this leads to a slightly higher deviation from the target schedule.

Wireless communications techniques are finding their way into industrial applications, but commercial wireless technologies lack the dependability required for critical applications in very large networks. In many wireless-controlled industrial facilities, safety regulations mandate real-time communications for tasks such as emergency shutdowns. This requires a wireless communications architecture that supports the coexistence of non-real-time and real-time tasks. To address this requirement, this paper proposes an architecture that augments a wireless mesh network with a unidirectional long-range communications system. Various configuration parameters of the system, including its security features, are optimized. Additionally, a physical realization of the architecture is evaluated using a series of experiments, including some performed on a real solar tower power plant. The experimental results demonstrate that the extension of a wireless mesh network with a unidirectional long-range communications system provides safety and scalability for industrial applications while promoting cost effectiveness and energy efficiency.

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.

A well-known mechanism for demand response is sending price signals to customers a day ahead. Customers then postpone or advance their usage of electricity to minimize cost. Setting up price functions that adapt the customers’ load to availability is a big challenge. This paper investigates the feasibility of finding day-ahead price functions to induce a desired load profile of domestic electric water heaters (DEWHs) minimizing their electricity cost for demand response. Bilevel optimization is applied for a single DEWH using a simplified linear model and full knowledge. This leads to a solvable bilevel problem and allows understanding optimality of price functions and resulting heating profiles. It is shown that with the resulting price functions the DEWH may select many significantly different heating profiles leading to the same cost. Thus the price does not uniquely induce the desired heating profile. The acquired knowledge forms the basis for a procedure to create price functions for controlling the load profile of many DEWHs.

In 2015, the IEEE 802.15.4 standard was expanded by the Deterministic and Synchronous Multi-Channel Extension (DSME) to increase reliability, scalability and energy-efficiency in industrial applications. The extension offers a TDMA/FDMA-based channel access, where time is divided into two alternating phases, a contention access period (CAP) and a contention free period (CFP). During the CAP, transmission slots can be allocated offering an exclusive access to the shared medium during the CFP. The fraction \(\tau \) of CFP’s time slots in a dataframe is a critical value, because it directly influences agility and throughput. A high throughput demands that the CFP is much longer than the CAP, i.e., a high value of \(\tau \), because application data is only sent during the CFP. High agility is given if the expected waiting time to send a CAP message is short and that the length of the CAPs are long enough to accommodate necessary GTS negotiations, i.e., a low value of \(\tau \). Once DSME is configured according to the needs of an application, \(\tau \) can only assume one of two values and cannot be changed at run-time. In this paper, we propose two extensions of DSME that allow to adopt \(\tau \) to the current traffic pattern. We show theoretically and through simulations that the proposed extensions provide a high degree of responsiveness to traffic fluctuations while keeping the throughput high.

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.

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.

This paper analyzes the impact of the high dimensional parameter space of domestic electric water heaters (DEWH) for demand response (DR). To quantify the consumer comfort a novel metric is introduced considering a stochastic distribution of different water draw events. Incorporating three control algorithms from literature, it is shown that all considered parameters of a DEWH except the heat conductivity have a significant impact on consumer satisfaction. The effect on DR is mainly influenced by the temperature range and the planning horizon, but also by the heat conductivity and the volume. In contrast, the rated power of the heating element and the nominal temperature have no significant impact on the effect on DR. The impacts are analyzed by varying these parameters in a simulation of 1000 DEWHs considering three different controllers: a common thermostat, an exchange price dependent nominal temperature changing mechanism and an energy scheduling algorithm proposed by Du and Lu.

Wireless mesh networks using IEEE 802.15.4 are getting increasingly popular for industrial applications because of low energy consumption and low maintenance costs. The IEEE 802.15.4 standard introduces DSME (Deterministic and Synchronous Multi-channel Extension). DSME uses time-slotted channel access to guarantee timely data delivery, multi-channel communication, and frequency hopping to mitigate the effects of external interferences. A distinguishing feature of DSME is its flexibility and adaptability to time-varying network traffic and to changes in the network topology. In this paper we evaluate the ability of DSME to adapt to time-varying network traffic. We examine the limits for slot allocation rates for different topologies. The evaluation is performed with openDSME, an open-source implementation of DSME.

Testbeds are a key element in the evaluation of wireless multi-hop networks. In order to relieve researchers from the hassle of deploying their own testbeds, remotely controllable testbeds, such as the FIT/IoT-LAB, are built. However, while the IoT-LAB has a high number of nodes, they are deployed in constraint areas. This, together with the complex nature of radio propagation, makes an ad-hoc construction of multi-hop topologies with a high number of hops difficult. This work presents a strategic approach to solve this problem and proposes algorithms to generate topologies with desired properties. The implementation is evaluated for the IoT-LAB testbeds and is provided as open-source software. The results show that preset topologies of various types can be built even in dense testbeds.

It is known for some time that a random graph G(n, p) contains w.h.p. a Hamiltonian cycle if p is larger than the critical value \(p_{crit}= (\log n + \log \log n + \omega _n)/n\). The determination of a concrete Hamiltonian cycle is even for values much larger than \(p_{crit}\) a nontrivial task. In this paper we consider random graphs G(n, p) with p in \(\tilde{\varOmega }(1/\sqrt{n})\), where \(\tilde{\varOmega }\) hides poly-logarithmic factors in n. For this range of p we present a distributed algorithm \(\mathcal{A}_\mathsf {HC}\) that finds w.h.p. a Hamiltonian cycle in \(O(\log n)\) rounds. The algorithm works in the synchronous model and uses messages of size \(O(\log n)\) and \(O(\log n)\) memory per node.

The paper analyzes the behavior of two demand response algorithms, both claiming to minimize the energy cost regarding time-varying prices in an optimal way by iteratively scheduling heating phases of water heaters considering hot water consumption. Four issues of the well known algorithm by Du and Lu are analyzed, which lead to suboptimal behavior. Proposed enhancements lead to an algorithm similar to the second, recently published, method of Shah et al. The effect of each enhancement and its combinations are analysed simulatively reducing the costs up to 6%.

Self-monitoring is a simple and effective mechanism for surveilling wireless sensor networks, especially to cope against faulty or compromised nodes. A node v can monitor the communication over a link e if both end-nodes of e are neighbors of v. Finding a set of monitoring nodes satisfying all monitoring constraints is called the edge-monitoring problem. The minimum edge-monitoring problem is known to be NP-complete. In this paper, we present a novel self-stabilizing algorithm for computing a minimal edge-monitoring set under the unfair distributed scheduler. For sparse networks the time complexity of this new algorithm is much lower than the currently best known algorithm.

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 constructedforwarding paths with an almost ideal approach. As a resultof independent interest we present a distributed algorithm using messages of size O(logn) for constructing virtual rings of graphs that are on average shorter than rings based on depth first search.

In cyber-physical systems, such as modern industrial plants, complex software is an essential part that enables cost-effective and flexible operation. However, this complexity increases the probability of problems that only reveal themselves after the deployment. This is even more important if security aspects are involved. Therefore, providing the possibility for software updates is an important building block in the design of industrial plants. This paper presents a holistic concept for software updates in an industrial plant with thousands of wirelessly connected embedded devices. Using wireless technology imposes additional difficulties in terms of data rate, packet size and reliability that have to be addressed in particular. The contribution also includes an analytical model to estimate the time until a new firmware is distributed. Evaluations carried out on hardware as well as in the OMNeT++ simulator demonstrate the applicability and scalability of the proposed approach.

The triangle partition problem is a generalization of the well-known graph matching problem consisting of finding the maximum number of independent edges in a given graph, i.e., edges with no common node. Triangle partition instead aims to find the maximum number of disjoint triangles. The triangle partition problem is known to be NP-complete. Thus, in this paper, the focus is on the local maximization variant, called maximal triangle partition (MTP). Thus, paper presents a new self-stabilizing algorithm for MTP that converges in O(m) moves under the unfair distributed daemon.

The analysis of self-stabilizing algorithms is in the vast majority of all cases limited to the worst case stabilization time starting from an arbitrary configuration. Considering the fact that these algorithms are intended to provide fault tolerance in the long run this is not the most relevant metric. From a practical point of view the worst case time to recover in case of a single fault is much more crucial. This paper presents techniques to derive upper bounds for the mean time to recover from a single fault for self-stabilizing algorithms Markov chains in combination with lumping. To illustrate the applicability of the techniques they are applied to a self-stabilizing coloring algorithm.

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. This paper uses the UPPAAL framework for formal analysis and verification of the slot management process. The analysis identifies weaknesses of the slot allocation process under communication and node failures. However, it is shown that inconsistencies are eventually resolved and improvements to the procedure are proposed that reduce the negative impact of failed slot allocation procedures significantly.

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 have in theory the uniqueand provable ability, to always return to a valid system stateeven in the face of failures. These properties are certainly desirablefor domains like wireless ad-hoc networks with numerousunpredictable faults. Unfortunately, the time in which the systemreturns to a valid state is not predictable and potentially unbound. The failure rate typically depends on physical phenomena andin self-stabilizing systems each node tries to react to failuresin an inherently adaptive fashion by the cyclic observation ofthe states of its neighbors. When state changes are either tooquick or too slow the system might never reach a state that issufficiently stable for a specific task. In this paper, we investigatethe influences of the error rate on the (stability) convergence timeon the basis of topology information acquired in real networkexperiments. This allows us to asses the asymptotic behavior ofrelevant self-stabilizing algorithms in typical wireless networks.

The analysis of self-stabilizing algorithms is often limited to the worst case stabilization time starting from an arbitrary state, i.e., a state resulting from a sequence of faults. Considering the fact that these algorithms are intended to provide fault tolerance in the long run, this is not the most relevant metric. A common situation is that a running system is an a legitimate state when hit by a single fault. This event has a much higher probability than multiple concurrent faults. Therefore, the worst case time to recover from a single fault is more relevant than the recovery time from a large number of faults. This paper presents techniques to derive upper bounds for the mean time to recover from a single fault for self-stabilizing algorithms based on Markov chains in combination with lumping. To illustrate the applicability of the techniques they are applied to a new self-stabilizing coloring algorithm.

This paper quantitatively compares five demand response (DR) approaches for waterbeds using simulation. The approaches enable privacy by design with a local control and contribute to the planning phase of the electricity network's balancing process. Approaches are assessed by their energy consumption, their ability to shift power consumption to times of high availability, and the effort of realization and configuration. Load steps were identified as a risk for power network stability. A classification of DR methods, based on the position of their contribution within the electricity network's balancing process, is used to distinguish our approach from the DR approaches found in the literature.

A p-star is a complete bipartite graph K 1,p with one center node and p leaf nodes. In this paper we propose the first distributed self-stabilizing algorithm for graph decomposition into p-stars. For a graph G and an integer p ≤ 1, this decomposition provides disjoint components of G where each component forms a p-star. We prove convergence and correctness of the algorithm under an unfair distributed daemon. The stabilization time is $2\lfloor \frac{n}{p+1}\rfloor +2$ rounds.