The scalability of the IPv6 Routing Protocol for Low-Power and Lossy Networks (RPL) is increasingly attracting the interest of both academia and industry. In light of this, we present experiences from a pilot experimental study conducted over several weeks on the protocol’s state-of-the-art implementation, RPL-Lite, in a large multi-hop IEEE 802.15.4 network of up to 700 nodes dispersed over 3390 m2. Our results show that RPL is capable of reliable and self-managed data collection even in such large-scale deployments, but its performance may drop significantly because of transmission power settings, border router locations, and insufficient load balancing, notably due to a phenomenon that, to the best of our knowledge, has not been reported in literature. We believe that our observations can be of value to designers and administrators of low-power wireless networks as well as to the community developing RPL.

Data arrangement determines the capacity, resilience, and performance of a distributed storage system. A scalable self-managed system must place its data efficiently not only during stable operation but also after an expansion, planned downscaling, or device failures. In this article, we present Derrick, a data balancing algorithm addressing these needs, which has been developed for HYDRAstor, a highly scalable commercial storage system. Derrick makes its decisions quickly in case of failures but takes additional time to find a nearly optimal data arrangement and a plan for reaching it when the device population changes. Compared to balancing algorithms in two other state-of-the-art systems, Derrick provides better capacity utilization, reduced data movement, and improved performance. Moreover, it can be easily adapted to meet custom placement requirements.

The immense popularity of object storage is also affecting the market of backup. Not only have novel backup solutions emerged that utilize cloud-based object storage as backends, but also support for object storage interfaces is increasingly expected from traditional dedicated backup appliances. This latter trend especially concerns systems with data deduplication, as they can offer compelling gains in storage capacity and throughput. However, such systems have been designed for interfaces and workloads that are markedly different from those encountered in object storage. Notably, they expect data to be written in portions that are orders of magnitude longer than those in the novel object-storage-oriented backup applications. In this light, we contribute twofold. First, contrasting the properties of object storage interfaces with usage patterns from 686 commercial deployments of backup appliances, we identify specific issues an implementation of such an interface has to address to offer adequate performance in a backup system with block-level deduplication. In particular, we show that a major challenge is efficient metadata management. Second, we present distributed data structures and algorithms to handle object metadata in backup systems with block-level deduplication. Subsequently, we implement them as an object storage layer for our HYDRAstor backup system. In comparison to object storage without in-line deduplication, our solution achieves 1.8–3.93x higher write throughput. Compared to object storage on top of a state-of-the-art file-based backup system, it processes 5.26–11.34x more object put operations per time unit.

Testbeds remain indispensable instruments for experimentally evaluating IoT-oriented low-power wireless networking solutions. With the evolution of the field, they are increasingly expected to match envisioned deployment conditions of such solutions, notably in terms of scale. However, large-scale testbeds are scarce, likely because they have been believed to be expensive. This paper argues that this belief need no longer be justified by presenting the architecture and basic properties of 1KT, our new smart-building IoT testbed for solutions utilizing IEEE 802.15.4 and Bluetooth Low Energy. It comprises 1000 experimental devices deployed directly in human spaces of 168 rooms on all 5 floors of a sizable building. At the same time, its cost is relatively low considering the scale.

In October 2017, an international crew participated in an emulated Mars colonization mission. For two weeks, they stayed confined in a special complex, a so-called analog habitat, where they were isolated from the outside world, including a lack of natural lighting and exterior noises, and lived on particularly adjusted Martian time. The mission followed a strict schedule, involving actual scientific work and activities envisioned as necessary for survival and exploration of the red planet. The main objective was to study the behavior and group dynamics of the crew in conditions recreating colonization of Mars, albeit under some unique circumstances compared to previous similar experiments. What was also special about the mission was the use of sociometric methods utilizing custom pervasive sensing solutions that we had built and deployed to complement classic methods based on self-reports and interviews. Based on that experiment, in this paper we contribute twofold. First, we share our deployment experiences to highlight the potential of pervasive distributed sensing systems in sociometric studies of habitat-based missions. The examples presented to this end include quantitative results that we obtained, among others, on social interactions between the astronauts, the impact of atypical situations on the crew, and the ergonomics of the habitat. Second, drawing from the experiences, in cooperation with the astronauts we attempt to highlight some unique challenges that space habitats pose for distributed support systems, such as ours. Among others, the challenges pertain to system deployment, autonomy, resilience, and flexibility. We believe that these challenges and, in general, space colonization constitute exciting research opportunities for the distributed systems community.

Apart from being standardized, an important industrial advantage of the IPv6 Routing Protocol for Low-Power and Lossy Networks (RPL) is the possibilities of completely adapting its route formation criteria. Through largely open routing metrics and route selection delegated to so-called objective functions, RPL's adopters are free to customize the protocol to individual applications, even ones with peculiar requirements. However, these possibilities also pose a major reliability risk: it is not clear whether a given combination of routing metrics, objective function, and RPL's remaining configuration parameters ensures that the resulting routes will be formed correctly when the routing metric values change dynamically. We study this problem here to derive conditions for routing metrics and objective functions under which routing path construction and maintenance can be proved correct. We start with a case study, based on an industrial deployment, that motivates the considered problem. We then formally model and analyze the dynamic behavior of RPL's route formation process in abstraction from particular objective functions and routing metrics. We derive conditions under which this process is provably correct. Finally, we attempt to translate these theoretical conditions into practical guidelines that can be utilized by RPL's adopters who aim at reliable systems.

Industrial Internet of Things (IoT) is frequently mentioned as one of the emerging areas in computing that may have a high potential real-world impact in the coming decade. In this paper, we analyze the challenges posed and opportunities offered by industrial IoT solutions from the distributed systems perspective. We focus on the sensing and actuation layer, which results from the the tight coupling of such solutions with the physical objects they monitor and control. We analyze this layer with respect to interoperability, scalability, and dependability, which are key features of many distributed systems.

Switching active memory banks at runtime allows a processor with a narrow address bus to access memory that exceeds ranges normally addressable via the bus. Switching code memory banks is regaining interest in microcontrollers for the Internet of Things (IoT), which have to run continuously growing software, while at the same time consuming ultra-small amounts of energy. To make use of bank switching, such software must be partitioned among the available banks and augmented with bank-switching instructions. In contrast to the augmenting, which is done automatically by a compiler, today the partitioning is normally done manually by programmers. However, since IoT software is cross-compiled on much more powerful machines than its target microcontrollers, it becomes possible to partition it automatically during compilation. In this article, we thus study the problem of partitioning program code among banks such that the resulting runtime performance of the program is maximized. We prove that the problem is NP -hard and propose a heuristic algorithm with a low complexity, so it enables fast compilation and hence interactive software development. The algorithm decomposes the problem into three subproblems and introduces a heuristic for each of them: (1) which pieces of code to partition, (2) which of them to assign to permanently mapped banks, and (3) how to divide the remaining ones among switchable banks. We integrate the algorithm, together with earlier ones, in an open-source compiler and test the resulting solution on synthetic as well as actual commercial IoT software bases, thereby demonstrating its advantages and drawbacks. In particular, the results show that the performance of partitions produced by our algorithm comes close to that of partitions created manually by programmers with expert knowledge on the partitioned code.

The slicing problem is to partition a partially-ordered collection of values into a given number of totally-ordered disjoint sets - slices - so that each slice contains a predefined fraction of values that are greater than those in the previous slice and smaller than those in the next slice. In this paper, we investigate a decentralized variant of the problem, which we encountered in our experiments with wearable low-power wireless devices. In this variant of the problem, each mobile device has a local value and, by opportunistically communicating with other devices, has to autonomously assign itself to an appropriate slice, depending on how its value compares to the values of others. We propose an algorithmic framework for this setting, within which we investigate several techniques that can potentially be employed to solve the slicing problem. We then empirically study the advantages and drawbacks of such solutions in low-level simulations and on a testbed of 80 low-power wireless devices.

While routing protocols for low-power wireless networks, such as CTP or RPL, handle link failures relatively well, node failures have received considerably less research attention. This paper thus studies crash-failures of destination nodes in distance-vector routing, that is, failures of so-called DODAG root nodes. First, it demonstrates empirically that handling root node crashes in existing state-of-the-art routing protocols leaves room for improvement or even fails completely in some cases. Second, based on an analysis of this behavior, the paper proposes RNFD, a new algorithm that explicitly tracks node failures at the routing layer. The algorithm is designed as a framework that complements rather than replaces regular route maintenance algorithms, which facilitates its integration with the existing protocols. Third, the paper evaluates a prototype implementation of RNFD through simulations and testbed experiments. In particular, it demonstrates that, with little information overhead, RNFD can speed up node failure detection by an order of magnitude and considerably reduce the traffic during the process.

Quantified crowd, a vision in which on-body sensors of nearby people collaborate to detect various phenomena within a crowd and produce feedback, is an emerging research area. One of the issues that impedes progress in this new area is a lack of a broadly applicable experimental platform, such as the platforms that enabled research on wireless sensor networks. In this paper, we aim to address this issue by presenting such an experimental hardware-software platform. Not only does the platform introduce custom badge-form low-power devices that feature a number of sensors relevant to quantified crowd, but it also ensures that these devices can interoperate with commercial off-the-shelf smartphones, wristbands, and other devices for self-quantification. In effect, it constitutes a powerful experimental instrument, as we show in a preliminary real-world evaluation.

Recently proposed applications for monitoring the behavior of real-world crowds with wireless sensor nodes rely on decentralized in-network aggregation. Although some of the aggregation algorithms for wireless sensor networks seem appealing for such applications, we are not aware of any deployments of these algorithms in real-world scenarios with crowd mobility. As a step toward filling this gap, we thus discuss our experiences with decentralized in-network aggregation from a few such deployments involving up to 177 nodes. We compare two main classes of algorithms for basic aggregates. We show that algorithms based on probabilistic, order- and duplicate-insensitive sketches outperform algorithms based on gradual variance reduction. To this end, however, they have to be adapted considerably to minimize the traffic, latency, and errors of the aggregation process, and to account for some real-world issues. In short, while the algorithms do have a potential for the envisioned crowd-monitoring applications, deploying them is not trivial.

Unit testing, an important facet of software quality assurance, is underappreciated by wireless sensor network (sensornet) developers. This is likely because our tools lag behind the rest of the computing field. As a remedy, we present a new framework that enables modern unit testing techniques in sensornets. Although the framework takes a holistic approach to unit testing, its novelty lies mainly in two aspects. First, to boost test development, it introduces embedded mock modules that automatically abstract out dependencies of tested code. Second, to automate test assessment, it provides embedded code coverage tools that identify untested control flow paths in the code. We demonstrate that in sensornets these features pose unique problems, solving which requires dedicated support from the compiler and operating system. However, the solutions have the potential to offer substantial benefits. In particular, they reduce the unit test development effort by a few factors compared to existing solutions. At the same time, they facilitate obtaining full code coverage, compared to merely 57--72% that can be achieved with integration tests. They also allow for intercepting and reporting many classes of runtime failures, thereby simplifying the diagnosis of software flaws. Finally, they enable fine-grained management of the quality of sensornet software.

We focus on a popular message dissemination protocol for wireless ad-hoc networks, Gossip3. Our contribution is twofold. First, we perform an extensive experimental evaluation of Gossip3 under fully utilized wireless channel and across diverse node densities. We identify the parameters of Gossip3 that need special configuration for the protocol to operate optimally. Second, we devise a self-configuration algorithm for Gossip3, that allows the protocol to work optimally for any network. We demonstrate through simulations that our protocol significantly outperforms the default configuration of Gossip3.

Hierarchical routing has often been mentioned as an appealing point-to-point routing technique for wireless sensor networks (sensornets). While there is a volume of analytical and high-level simulation results demonstrating its merits, there has been little work evaluating it in actual sensornet settings. This article bridges the gap between theory and practice. Having analyzed a number of proposed hierarchical routing protocols, we have developed a framework that captures the common characteristics of the protocols and identifies design points at which the protocols differ. We use a sensornet implementation of the framework in TOSSIM and on a 60-node testbed to study various trade-offs that hierarchical routing introduces, as well as to compare the performance of hierarchical routing with the performance of other routing techniques, namely shortest-path routing, compact routing, and beacon vector routing. The results show that hierarchical routing is a compelling routing technique also in practice. In particular, despite only logarithmic routing state, it can offer small routing stretch: an average of ∼ 1.25 and a 99th percentile of 2. It can also be robust, minimizing the maintenance traffic or the latency of reacting to changes in the network. Moreover, the trade-offs offered by hierarchical routing are attractive for many sensornet applications when compared to the other routing techniques. For example, in terms of routing state, hierarchical routing can offer scalability at least an order of magnitude better than compact routing, and at the same time, in terms of routing stretch, its performance is within 10--15% of that of compact routing; in addition, this performance can further be tuned to a particular application. Finally, we also identify a number of practical issues and limitations of which we believe sensornet developers adopting hierarchical routing should be aware.

A recursive multihop area hierarchy has a number of applications in wireless sensor networks, the most common being scalable point-to-point routing, so-called hierarchical routing. In this paper, we consider the problem of maintaining a recursive multihop area hierarchy in large sensor networks. We present a gossip-based protocol, dubbed PL-Gossip, in which nodes, by using local-only operations and by periodically gossiping with their neighbors, collaboratively maintain such a hierarchy. Since the hierarchy is a complex distributed structure, PL-Gossip introduces special mechanisms for internode coordination and consistency enforcement. Yet, these mechanisms are seamlessly integrated within the basic gossiping framework. Through simulations and experiments with an actual embedded protocol implementation, we demonstrate that PL-Gossip maintains the hierarchy in a manner that addresses all the peculiarities of sensor networks. More specifically, it offers excellent opportunities for aggressive energy saving and facilitates provisioning energy harvesting infrastructure. In addition, it bootstraps and recovers the hierarchy after failures relatively fast while also being robust to message loss. Finally, it can seamlessly operate on real sensor node hardware in realistic deployment scenarios and can outperform existing state-of-the-art hierarchy maintenance protocols.

We consider multi-resolution storage, a technique for providing scalable adaptive data fidelity, necessary for many applications of large wireless sensor networks (WSNs). Although the previously proposed design of multi-resolution storage, based on quad trees and geographic routing, is conceptually simple, it exhibits inherent problems if applied to real-world WSNs. To address these problems, we revisit some of the networking assumptions and propose an alternative design that employs an overlay combining area and landmark hierarchies. Simulations and initial experiments with a prototype embedded implementation indicate that our solution can be scalable and can work on real hardware, which motivates further research.

PL-Gossip is evaluated using packet-level event-driven simulator. Experiments are conducted with varying network sizes, densities, message loss rates, and node arrival and departure schemes . The experimental results verified that a node's state, as maintained by the protocol (i.e., the label and the routing table), grows logarithmically with the network size, which ensures scalability and small bandwidth requirements. In addition, the hierarchical network organization offers efficient routing: the average hop stretch does not exceed 25%. Moreover, the hierarchy is quickly bootstrapped or restored, also under significant node population changes, which minimizes disruptions caused to the applications. Finally, the experiments confirmed what the authors proved analytically, that is, the protocol recovers the network from any massive node failure or network partitioning, even when such incidents happen continuously and concurrently. PL-Gossip is also implemented in TinyOS. The implementation is subject to real-world tests while at the same time being integrated into a large-scale real-world system.

Abstract Much research on content‐based P2P searching for file‐sharing applications has focused on exploiting semantic relations between peers to facilitate searching. Current methods suggest reactive ways to manage semantic relations: they rely on the usage of the underlying search mechanism, and infer semantic relationships based on the queries placed and the corresponding replies received. In this paper we follow a different approach, proposing a proactive method to build a semantic overlay. Our method is based on an epidemic protocol that clusters peers with similar content. Peer clustering is done in a completely implicit way, that is, without requiring the user to specify preferences or to characterize the content of files being shared. In our approach, each node maintains a small list of semantically optimal peers. Our simulation studies show that such a list is highly effective when searching files. The construction of this list through gossiping is efficient and robust, even in the presence of changes in the network. Copyright © 2007 John Wiley & Sons, Ltd.