Neighborhood View Consistency in Wireless Sensor Networks

Wireless sensor networks (WSNs) are characterized by localized interactions, that is, protocols are often based on message exchanges within a node’s direct radio range. We recognize that for these protocols to work effectively, nodes must have consistent information about their shared neighborhoods. Different types of faults, however, can affect this information, severely impacting a protocol’s performance. We factor this problem out of existing WSN protocols and argue that a notion of neighborhood view consistency (NVC) can be embedded within existing designs to improve their performance. To this end, we study the problem from both a theoretical and a system perspective. We prove that the problem cannot be solved in an asynchronous system using any of Chandra and Toueg’s failure detectors. Because of this, we introduce a new software device called pseudocrash failure detector (PCD), study its properties, and identify necessary and sufficient conditions for solving NVC with PCDs. We prove that, in the presence of transient faults, NVC is impossible to solve with any PCDs, thus define two weaker specifications of the problem. We develop a global algorithm that satisfies both specifications in the presence of unidirectional links, and a localized algorithm that solves the weakest specification in networks of bidirectional links. We implement the latter atop two different WSN operating systems, integrate our implementations with four different WSN protocols, and run extensive micro-benchmarks and full-stack experiments on a real 90-node WSN testbed. Our results show that the performance significantly improves for NVC-equipped protocols; for example, the Collection Tree Protocol (CTP) halves energy consumption with higher data delivery.

Related papers:

title: Fidelity and yield in a volcano monitoring sensor network
abstract: We present a science-centric evaluation of a 19-day sensor network deployment at Reventador, an active volcano in Ecuador. Each of the 16 sensors continuously sampled seismic and acoustic data at 100 Hz. Nodes used an event-detection algorithm to trigger on interesting volcanic activity and initiate reliable data transfer to the base station. During the deployment, the network recorded 229 earthquakes, eruptions, and other seismoacoustic events.
 The science requirements of reliable data collection, accurate event detection, and high timing precision drive sensor networks in new directions for geophysical monitoring. The main contribution of this paper is an evaluation of the sensor network as a scientific instrument, holding it to the standards of existing instrumentation in terms of data fidelity (the quality and accuracy of the recorded signals) and yield (the quantity of the captured data). We describe an approach to time rectification of the acquired signals that can recover accurate timing despite failures of the underlying time synchronization protocol. In addition, we perform a detailed study of the sensor network's data using a direct comparison to a standalone data logger, as well as an investigation of seismic and acoustic wave arrival times across the network.

title: Experiences from Two Sensor Network Deployments - Self-monitoring and Self-configuration Keys to Success
abstract: Despite sensor network protocols being self-configuring, sensor network deployments continue to fail. We report our experience from two recently deployed IP-based multi-hop sensor networks: one in-door surveillance network in a factory complex and a combined out-door and in-door surveillance network. Our experiences highlight that adaptive protocols alone are not sufficient, but that an approach to self-monitoring and self-configuration that covers more aspects than protocol adaptation is needed. Based on our experiences, we design and implement an architecture for self-monitoring of sensor nodes. We show that the self-monitoring architecture detects and prevents the problems with false alarms encountered in our deployments. The architecture also detects software bugs by monitoring actual and expected duty-cycle of key components of the sensor node. We show that the energy-monitoring architecture detects bugs that cause the radio chip to be active longer than expected.

title: Real-World Sensor Network for Long-Term Volcano Monitoring: Design and Findings
abstract: This paper presents the design, deployment, and evaluation of a real-world sensor network system in an active volcano - Mount St. Helens. In volcano monitoring, the maintenance is extremely hard and system robustness is one of the biggest concerns. However, most system research to date has focused more on performance improvement and less on system robustness. In our system design, to address this challenge, automatic fault detection and recovery mechanisms were designed to autonomously roll the system back to the initial state if exceptions occur. To enable remote management, we designed a configurable sensing and flexible remote command and control mechanism with the support of a reliable dissemination protocol. To maximize data quality, we designed event detection algorithms to identify volcanic events and prioritize the data, and then deliver higher priority data with higher delivery ratio with an adaptive data transmission protocol. Also, a light-weight adaptive linear predictive compression algorithm and localized TDMA MAC protocol were designed to improve network throughput. With these techniques and other improvements on intelligence and robustness based on a previous trial deployment, we air-dropped 13 stations into the crater and around the flanks of Mount St. Helens in July 2009. During the deployment, the nodes autonomously discovered each other even in-the-sky and formed a smart mesh network for data delivery immediately. We conducted rigorous system evaluations and discovered many interesting findings on data quality, radio connectivity, network performance, as well as the influence of environmental factors.

title: The hitchhiker's guide to successful wireless sensor network deployments
abstract: The successful deployment of a wireless sensor network is a difficult task, littered with traps and pitfalls. Even a functional network does not guarantee gathering meaningful data. In SensorScope, with its multiple campaigns in various environments (e.g., urban, high-mountain), we have acquired much knowledge in planning, conducting, and managing real-world sensor network deployments. In this paper, we share our experience by stepping through the entire process, from the preparatory hard- and software development to the actual field deployment. Illustrated by numerous real-life examples, excerpted from our own experience, we point out many potential problems along this way and their possible solutions. We also indicate the importance of a close interaction with the end-user community in planning and running the network, and finally exploiting the data.

title: Next century challenges: scalable coordination in sensor networks
abstract: Networked sensors-those that coordinate amongst themselves to achieve a larger sensing task-will revolutionize information gathering and processing both in urban environments and in inhospitable terrain. The sheer numbers of these sensors and the expected dynamics in these environments present unique challenges in the design of unattended autonomous sensor networks. These challenges lead us to hypothesize that sensor network coordination applications may need to be structured differently from traditional network applications. In particular, we believe that localized algorithms (in which simple local node behavior achieves a desired global objective) may be necessary for sensor network coordination. In this paper, we describe localized algorithms, and then discuss directed diffusion, a simple communication model for describing localized algorithms.

title: Collection tree protocol
abstract: This paper presents and evaluates two principles for wireless routing protocols. The first is datapath validation: data traffic quickly discovers and fixes routing inconsistencies. The second is adaptive beaconing: extending the Trickle algorithm to routing control traffic reduces route repair latency and sends fewer beacons.
 We evaluate datapath validation and adaptive beaconing in CTP Noe, a sensor network tree collection protocol. We use 12 different testbeds ranging in size from 20--310 nodes, comprising seven platforms, and six different link layers, on both interference-free and interference-prone channels. In all cases, CTP Noe delivers > 90% of packets. Many experiments achieve 99.9%. Compared to standard beaconing, CTP Noe sends 73% fewer beacons while reducing topology repair latency by 99.8%. Finally, when using low-power link layers, CTP Noe has duty cycles of 3% while supporting aggregate loads of 30 packets/minute.

title: PDA: Passive distributed assertions for sensor networks
abstract: Sensor networks are prone to failures and are hard to debug. This is particularely true for failures caused by incorrect interaction of multiple nodes. We propose a mechanism called passive distributed assertions (PDA) that allows developers to detect such failures and provides hints on possible causes. PDA allow a programmer to formulate assertions over distributed node states using a simple declarative language, causing the sensor network to emit information that can be passively collected (e.g., using packet sniffing) and evaluated to verify that assertions hold. This passive approach allows us to minimize the interference between the application and assertion verification. Further, our system provides mechanisms to deal with inaccurate traces that result from message loss and synchronization inaccuracies. We implement PDA on the BTnode platform and evaluate it using an extensive case study.

title: How was your journey?: uncovering routing dynamics in deployed sensor networks with multi-hop network tomography
abstract: In the context of wireless data collection, a common application class in wireless sensor networks, this paper presents a novel, non-intrusive algorithm for the precise reconstruction of the packet path, the per-hop arrival order and the per-hop arrival times of individual packets from partial in-band information at runtime. Information is reconstructed outside the network immediately after a packet is received at the sink. After establishing the correctness of our proposed algorithm, we evaluate its performance in testbed experiments using CTP and Dozer, two well-known data collection protocols. Foremost interested in obtaining a better understanding of the performance of long-term real-world deployments, Multi-hop Network Tomography (MNT) is applied to in total more than 140 million packets that have been obtained from three multi-year WSN deployments of the PermaSense project. The capabilities of the performance analysis of deployed systems using the proposed algorithm and methodology are demonstrated in a case study.

title: Real-Time Scheduling for WirelessHART Networks
abstract: TDMA transmission, redundant routes, and avoidance of spatial reuse of channels for enhanced reliability and real-time performance. This paper makes several key contributions to real-time transmission scheduling in WirelessHART networks: (1) formulation of the end-to-end real-time transmission scheduling problem based on the characteristics of WirelessHART, (2) proof of NP-hardness of the problem, (3) an optimal branch-and-bound scheduling algorithm based on a necessary condition for schedulability, and (4) an efficient and practical heuristic-based scheduling algorithm called Conflict-aware Least Laxity First (C-LLF). Extensive simulations based on both random topologies and real network topologies of a physical testbed demonstrate that C-LLF is highly effective in meeting end-to-end deadlines in WirelessHART networks, and significantly outperforms common real-time scheduling policies.

title: Z-MAC: a hybrid MAC for wireless sensor networks
abstract: This paper presents the design, implementation and performance evaluation of a hybrid MAC protocol, called Z-MAC, for wireless sensor networks that combines the strengths of TDMA and CSMA while offsetting their weaknesses. Like CSMA, ZMAC achieves high channel utilization and low latency under low contention and like TDMA, achieves high channel utilization under high contention and reduces collision among two-hop neighbors at a low cost. A distinctive feature of Z-MAC is that its performance is robust to synchronization errors, slot assignment failures, and time-varying channel conditions; in the worst case, its performance always falls back to that of CSMA. Z-MAC is implemented in TinyOS.

title: Adaptive and Decentralized Operator Placement for In-Network Query Processing
abstract: In-network query processing is critical for reducing network traffic when accessing and manipulating sensor data. It requires placing a tree of query operators such as filters and aggregations but also correlations onto sensor nodes in order to minimize the amount of data transmitted in the network. In this paper, we show that this problem is a variant of the task assignment problem for which polynomial algorithms have been developed. These algorithms are however centralized and cannot be used in a sensor network. We describe an adaptive and decentralized algorithm that progressively refines the placement of operators by walking through neighbor nodes. Simulation results illustrate the potential benefits of our approach. They also show that our placement strategy can achieve near optimal placement onto various graph topologies despite the risks of local minima.

title: Distributed localization in wireless sensor networks: a quantitative compariso
abstract: This paper studies the problem of determining the node locations in ad-hoc sensor networks. We compare three distributed localization algorithms (Ad-hoc positioning, Robust positioning, and N-hop multilateration) on a single simulation platform. The algorithms share a common, three-phase structure: (1) determine node-anchor distances, (2) compute node positions, and (3) optionally refine the positions through an iterative procedure. We present a detailed analysis comparing the various alternatives for each phase, as well as a head-to-head comparison of the complete algorithms. The main conclusion is that no single algorithm performs best; which algorithm is to be preferred depends on the conditions (range errors, connectivity, anchor fraction, etc.). In each case, however, there is significant room for improving accuracy and/or increasing coverage.

title: Unified broadcast in sensor networks
abstract: Complex sensor network applications include multiple services such as collection, dissemination, time synchronization, and failure detection protocols. Many of these protocols require local state maintenance through periodic broadcasts which leads to high control overhead. Recent attempts to consolidate these broadcasts focus on piggybacking information into existing services but such tight coupling between protocols limits code reuse and interoperability of applications. We present Unified Broadcast (UB) which combines broadcasts from multiple protocols while maintaining a modular architecture of the network stack. UB is implemented as a transparent layer between the link and network layers, where it delays, schedules, and combines broadcasts from upper layer protocols before transmission on the wireless channel. Our empirical results in simulation and on a testbed show that UB can decrease the overall packet transmissions in the network by more than 60%, corresponding to more than 40% energy savings, without requiring new interfaces or affecting the correctness of the upper layer protocols.

title: Trickle: A Self-Regulating Algorithm for Code Propagation and Maintenance in Wireless Sensor Networks (Awarded Best Paper!)
abstract: We present Trickle, an algorithm for propagating and maintaining code updates in wireless sensor networks. Borrowing techniques from the epidemic/gossip, scalable multicast, and wireless broadcast literature, Trickle uses a "polite gossip" policy, where motes periodically broadcast a code summary to local neighbors but stay quiet if they have recently heard a summary identical to theirs. When a mote hears an older summary than its own, it broadcasts an update. Instead of flooding a network with packets, the algorithm controls the send rate so each mote hears a small trickle of packets, just enough to stay up to date. We show that with this simple mechanism, Trickle can scale to thousand-fold changes in network density, propagate new code in the order of seconds, and impose a maintenance cost on the order of a few sends an hour.

title: Unreliable failure detectors for reliable distributed systems
abstract: We introduce the concept of unreliable failure detectors and study how they can be used to solve Consensus in asynchronous systems with crash failures. We characterise unreliable failure detectors in terms of two properties—completeness and accuracy. We show that Consensus can be solved even with unreliable failure detectors that make an infinite number of mistakes, and determine which ones can be used to solve Consensus despite any number of crashes, and which ones require a majority of correct processes. We prove that Consensus and Atomic Broadcast are reducible to each other in asynchronous systems with crash failures; thus, the above results also apply to Atomic Broadcast. A companion paper shows that one of the failure detectors introduced here is the weakest failure detector for solving Consensus [Chandra et al. 1992].

title: Flush: a reliable bulk transport protocol for multihop wireless networks
abstract: We present Flush, a reliable, high goodput bulk data transport protocol for wireless sensor networks. Flush provides end-to-end reliability, reduces transfer time, and adapts to time-varying network conditions. It achieves these properties using end-to-end acknowledgments, implicit snooping of control information, and a rate-control algorithm that operates at each hop along a flow. Using several real network topologies, we show that Flush closely tracks or exceeds the maximum goodput achievable by a hand-tuned but fixed rate for each hop over a wide range of path lengths and varying network conditions. Flush is scalable; its effective bandwidth over a 48-hop wireless network is approximately one-third of the rate achievable over one hop. The design of Flush is simplified by assuming that different flows do not interfere with each other, a reasonable restriction for many sensornet applications that collect bulk data in a coordinated fashion, like structural health monitoring, volcanic activity monitoring, or protocol evaluation. We collected all of the performance data presented in this paper using Flush itself.

title: MUSTER: Adaptive Energy-Aware Multisink Routing in Wireless Sensor Networks
abstract: Wireless sensor networks (WSNs) are increasingly proposed for applications characterized by many-to-many communication, where multiple sources report their data to multiple sinks. Unfortunately, mainstream WSN collection protocols are generally designed to account for a single sink and, dually, WSN multicast protocols optimize communication from a single source. In this paper, we present MUSTER, a routing protocol expressly designed for many-to-many communication. First, we devise an analytical model to compute, in a centralized manner, the optimal solution to the problem of simultaneously routing from multiple sources to multiple sinks. Next, we illustrate heuristics approximating the optimal solution in a distributed setting, and their implementation in MUSTER. To increase network lifetime, MUSTER minimizes the number of nodes involved in many-to-many routing and balances their forwarding load. We evaluate MUSTER in emulation and in a real WSN testbed. Results indicate that our protocol builds near-optimal routing paths, doubles the WSN lifetime, and overall delivers to the user 2.5 times the amount of raw data w.r.t. mainstream protocols. Moreover, MUSTER is intrinsically amenable to in-network aggregation, pushing the improvements up to a 180 percent increase in lifetime and a four-time increase in data yield.

title: Murphy loves potatoes: experiences from a pilot sensor network deployment in precision agriculture
abstract: We report on preliminary experiences with deploying a large-scale sensor network (about 100 nodes) for a pilot in precision agriculture. The pilot did not answer the initial research questions, but instead revealed many engineering problems typically overlooked by (computer) scientists evaluating their work by means of simulation. The deployment prompted us to rethink our development process and includes important lessons for the WSN research community as a whole

title: A line in the sand: a wireless sensor network for target detection, classification, and tracking
abstract: Intrusion detection is a surveillance problem of practical import that is well suited to wireless sensor networks. In this paper, we study the application of sensor networks to the intrusion detection problem and the related problems of classifying and tracking targets. Our approach is based on a dense, distributed, wireless network of multi-modal resource-poor sensors combined into loosely coherent sensor arrays that perform in situ detection, estimation, compression, and exfiltration. We ground our study in the context of a security scenario called "A Line in the Sand" and accordingly define the target, system, environment, and fault models. Based on the performance requirements of the scenario and the sensing, communication, energy, and computation ability of the sensor network, we explore the design space of sensors, signal processing algorithms, communications, networking, and middleware services. We introduce the influence field, which can be estimated from a network of binary sensors, as the basis for a novel classifier. A contribution of our work is that we do not assume a reliable network; on the contrary, we quantitatively analyze the effects of network unreliability on application performance. Our work includes multiple experimental deployments of over 90 sensor nodes at MacDill Air Force Base in Tampa, FL, as well as other field experiments of comparable scale. Based on these experiences, we identify a set of key lessons and articulate a few of the challenges facing extreme scaling to tens or hundreds of thousands of sensor nodes.

title: Not all wireless sensor networks are created equal: A comparative study on tunnels
abstract: Wireless sensor networks (WSNs) are envisioned for a number of application scenarios. Nevertheless, the few in-the-field experiences typically focus on the features of a specific system, and rarely report about the characteristics of the target environment, especially with respect to the behavior and performance of low-power wireless communication. The TRITon project, funded by our local administration, aims to improve safety and reduce maintenance costs of road tunnels, using a WSN-based control infrastructure. The access to real tunnels within TRITon gives us the opportunity to experimentally assess the peculiarities of this environment, hitherto not investigated in the WSN field. We report about three deployments: (i) an operational road tunnel, enabling us to assess the impact of vehicular traffic; (ii) a nonoperational tunnel, providing insights into analogous scenarios (e.g., underground mines) without vehicles; (iii) a vineyard, serving as a baseline representative of the existing literature. Our setup, replicated in each deployment, uses mainstream WSN hardware, and popular MAC and routing protocols. We analyze and compare the deployments with respect to reliability, stability, and asymmetry of links, the accuracy of link quality estimators, and the impact of these aspects on MAC and routing layers. Our analysis shows that a number of criteria commonly used in the design of WSN protocols do not hold in tunnels. Therefore, our results are useful for designing networking solutions operating efficiently in similar environments.

title: Is there light at the ends of the tunnel? Wireless sensor networks for adaptive lighting in road tunnels
abstract: Existing deployments of wireless sensor networks (WSNs) are often conceived as stand-alone monitoring tools. In this paper, we report instead on a deployment where the WSN is a key component of a closed-loop control system for adaptive lighting in operational road tunnels. WSN nodes along the tunnel walls report light readings to a control station, which closes the loop by setting the intensity of lamps to match a legislated curve. The ability to match dynamically the lighting levels to the actual environmental conditions improves the tunnel safety and reduces its power consumption. The use of WSNs in a closed-loop system, combined with the real-world, harsh setting of operational road tunnels, induces tighter requirements on the quality and timeliness of sensed data, as well as on the reliability and lifetime of the network. In this work, we test to what extent mainstream WSN technology meets these challenges, using a dedicated design that however relies on well-established techniques. The paper describes the hw/sw architecture we devised by focusing on the WSN component, and analyzes its performance through experiments in a real, operational tunnel.

title: Efficient State Retention for Transiently-powered Embedded Sensing
abstract: We present state retention techniques to support embedded sensing applications on 32-bit microcontrollers whose energy provisioning is assisted through ambient harvesting or wireless energy transfer. As energy availability is likely erratic in these settings, applications may be unpredictably interrupted. To behave dependably, applications should resume from where they left as soon as energy is newly available. We investigate the fundamental building block necessary to this end, and conceive three mechanisms to checkpoint and restore a device's state on stable storage quickly and in an energy-efficient manner. The problem is unique in many regards; for example, because of the distinctive performance vs. energy trade-offs of modern 32-bit microcontrollers and the peculiar characteristics of current flash chips. Our results, obtained from real experiments using two different platforms, crucially indicate that there is no ``one-size-fits-all'' solution. The performance depends on factors such as the amount of data to handle, how in memory the data is laid out, as well as an application's read/write patterns.

title: Energy Harvesting Sensor Nodes: Survey and Implications
abstract: Sensor networks with battery-powered nodes can seldom simultaneously meet the design goals of lifetime, cost, sensing reliability and sensing and transmission coverage. Energy-harvesting, converting ambient energy to electrical energy, has emerged as an alternative to power sensor nodes. By exploiting recharge opportunities and tuning performance parameters based on current and expected energy levels, energy harvesting sensor nodes have the potential to address the conflicting design goals of lifetime and performance. This paper surveys various aspects of energy harvesting sensor systems- architecture, energy sources and storage technologies and examples of harvesting-based nodes and applications. The study also discusses the implications of recharge opportunities on sensor node operation and design of sensor network solutions.

title: Mementos: system support for long-running computation on RFID-scale devices
abstract: Transiently powered computing devices such as RFID tags, kinetic energy harvesters, and smart cards typically rely on programs that complete a task under tight time constraints before energy starvation leads to complete loss of volatile memory. Mementos is a software system that transforms general-purpose programs into interruptible computations that are protected from frequent power losses by automatic, energy-aware state checkpointing. Mementos comprises a collection of optimization passes for the LLVM compiler infrastructure and a linkable library that exercises hardware support for energy measurement while managing state checkpoints stored in nonvolatile memory. We evaluate Mementos against diverse test cases in a trace-driven simulator of transiently powered RFID-scale devices. Although Mementos's energy checks increase run time when energy is plentiful, they allow Mementos to safely suspend execution when energy dwindles, effectively spreading computation across zero or more power failures. This paper's contributions are: a study of the runtime environment for programs on RFID-scale devices; an energy-aware state checkpointing system for these devices that is implemented for the MSP430 family of microcontrollers; and a trace-driven simulator of transiently powered RFID-scale devices.

title: A networked embedded system platform for the post-mote era
abstract: For the last fifteen years, research explored the hardware, software, sensing, communication abstractions, languages, and protocols that could make networks of small, embedded devices---motes---sample and report data for long periods of time unattended. Today, the application and technological landscapes have shifted, introducing new requirements and new capabilities. Hardware has evolved past 8 and 16 bit microcontrollers: there are now 32 bit processors with lower energy budgets and greater computing capability. New wireless link layers have emerged, creating protocols that support rapid and efficient setup and teardown but introduce novel limitations that systems must consider. The time has come to look beyond optimizing networks of motes. We look towards new technologies such as Bluetooth Low Energy, Cortex M processors, and capable energy harvesting, with new application spaces such as personal area networks, and new capabilities and requirements in security and privacy to inform contemporary hardware and software platforms. It is time for a new, open experimental platform in this post-mote era.

title: A case against routing-integrated time synchronization
abstract: To achieve more accurate global time synchronization, this paper argues for decoupling the clock distribution network from the routing tree in a multihop wireless network. We find that both flooding and routing-integrated time synchronization rapidly propagate node-level errors (typically due to temperature fluctuations) across the network. Therefore, we propose that a node chooses synchronization neighbors that offer the greatest frequency stability. We propose two methods to estimate a neighbor's stability. The first approach selects the neighbor whose Frequency Error Variance, or simply FEV, is smallest with respect to the local clock. The second approach selects the neighbor that reports the lowest FEV relative to its synchronization parent. We also propose the node-level time-variance FEV as an additive metric for selecting more stable clock trees than either naïve flooding or routing-integrated time synchronization can provide. We incorporate these techniques into FTSP, a widely-used time synchronization protocol, and show that the mean error in global time significantly improved (by a factor of five) when some nodes are warmed and others are not.

title: Let the tree Bloom: scalable opportunistic routing with ORPL
abstract: Routing in battery-operated wireless networks is challenging, posing a tradeoff between energy and latency. Previous work has shown that opportunistic routing can achieve low-latency data collection in duty-cycled networks. However, applications are now considered where nodes are not only periodic data sources, but rather addressable end points generating traffic with arbitrary patterns.
 We present ORPL, an opportunistic routing protocol that supports any-to-any, on-demand traffic. ORPL builds upon RPL, the standard protocol for low-power IPv6 networks. By combining RPL's tree-like topology with opportunistic routing, ORPL forwards data to any destination based on the mere knowledge of the nodes' sub-tree. We use bitmaps and Bloom filters to represent and propagate this information in a space-efficient way, making ORPL scale to large networks of addressable nodes. Our results in a 135-node testbed show that ORPL outperforms a number of state-of-the-art solutions including RPL and CTP, conciliating a sub-second latency and a sub-percent duty cycle. ORPL also increases robustness and scalability, addressing the whole network reliably through a 64-byte Bloom filter, where RPL needs kilobytes of routing tables for the same task.

title: Broadcast-free collection protocol
abstract: Asynchronous low-power listening techniques reduce the energy footprint of radio communication by enforcing link layer duty cycling. At the same time, these techniques make broadcast traffic significantly more expensive than unicast traffic. Because broadcast is a key network primitive and is widely used in various protocols, recently several techniques have been proposed to reduce the amount of broadcast activity by merging broadcasts from different protocols. In this paper we focus on collection protocols and investigate the more extreme approach of eliminating broadcast completely. To this end, we design, implement and, evaluate a Broadcast-Free Collection Protocol, BFC. We derive first-order models to quantify the costs of broadcasts, and evaluate the performance of BFC on a public testbed. Compared to the Collection Tree Protocol, the de facto standard for data collection, BFC achieves double-digit percentage improvements on the duty cycles. The specific benefits to individual nodes depend on the relative cost of unicast activity; we show that the nodes that benefit the most are the sink's neighbors, which are crucial for network lifetime extension. Eliminating broadcast also brings several other advantages, including extra flexibility with link layer calibrations and energy savings in the presence of poor connectivity.

title: Low-power wireless bus
abstract: We present the Low-Power Wireless Bus (LWB), a communication protocol that supports several traffic patterns and mobile nodes immersed in static infrastructures. LWB turns a multi-hop low-power wireless network into an infrastructure similar to a shared bus, where all nodes are potential receivers of all data. It achieves this by mapping all traffic demands on fast network floods, and by globally scheduling every flood. As a result, LWB inherently supports one-to-many, many-to-one, and many-to-many traffic. LWB also keeps no topology-dependent state, making it more resilient to link changes due to interference, node failures, and mobility than prior approaches. We compare the same LWB prototype on four testbeds with seven state-of-the-art protocols and show that: (i) LWB performs comparably or significantly better in many-to-one scenarios, and adapts efficiently to varying traffic loads; (ii) LWB outperforms our baselines in many-to-many scenarios, at times by orders of magnitude; (iii) external interference and node failures affect LWB's performance only marginally; (iv) LWB supports mobile nodes acting as sources, sinks, or both without performance loss.

title: Hood: a neighborhood abstraction for sensor networks
abstract: This paper proposes a neighborhood programming abstraction for sensor networks, wherein a node can identify a subset of nodes around it by a variety of criteria and share state with those nodes. This abstraction allows developers to design distributed algorithms in terms of the neighborhood abstraction itself, instead of decomposing them into component parts such as messaging protocols, data caches, and neighbor lists. In those applications that are already neighborhood-based, this abstraction is shown to facilitate good application design and to reduce algorithmic complexity, inter-component coupling, and total lines of code. The abstraction as defined here has been successfully used to implement several complex applications and is shown to capture the essence of many more existing distributed sensor network algorithms.

title: Lightweight neighborhood cardinality estimation in dynamic wireless networks
abstract: We address the problem of estimating the neighborhood cardinality of nodes in dynamic wireless networks. Different from previous studies, we consider networks with high densities (a hundred neighbors per node) and where all nodes estimate cardinality concurrently. Performing concurrent estimations on dense mobile networks is hard; we need estimators that are not only accurate, but also fast, asynchronous (due to mobility) and lightweight (due to concurrency and high density). To cope with these requirements, we propose Estreme, a neighborhood cardinality estimator with extremely low overhead that leverages the rendezvous time of low-power medium access control (MAC) protocols. We implemented Estreme on the Contiki OS and show a significant improvement over the state-of-the-art. With Estreme, 100 nodes can concurrently estimate their neighborhood cardinality with an error of ≈10%. State-of-the-art solutions provide a similar accuracy, but on networks consisting of a few tens of nodes and where only a fraction of nodes estimate the cardinality concurrently.

title: Selective Reprogramming of Mobile Sensor Networks through Social Community Detection
abstract: We target application domains where the behavior of animals or humans is monitored using wireless sensor network (WSN) devices. The code on these devices is updated frequently, as scientists acquire in-field data and refine their hypotheses. Wireless reprogramming is therefore fundamental to avoid the (expensive) re-collection of the devices. Moreover, the code carried by the monitored individuals often depends on their characteristics, e.g., the behavior or preferred habitat. We propose a selective reprogramming approach that simplifies and automates the process of delivering a code update to a target subset of nodes. Target selection is expressed through constraints injected in the WSN, triggering automatic dissemination of code updates whenever verified. Update dissemination relies on a novel protocol exploiting the social behavior of the monitored individuals. We evaluate our approach through simulation, using real-world animal and human traces. The results shows that our protocol is able to capture the social network structure in a way comparable to existing offline algorithms with global knowledge while allowing runtime adaptation to community structure changes, and that existing dissemination approaches based on gossip generate up to three times more network overhead than our socially-aware dissemination.

title: Practical asynchronous neighbor discovery and rendezvous for mobile sensing applications
abstract: We present Disco, an asynchronous neighbor discovery and rendezvous protocol that allows two or more nodes to operate their radios at low duty cycles (e.g. 1%) and yet still discover and communicate with one another during infrequent, opportunistic encounters without requiring any prior synchronization information. The key challenge is to operate the radio at a low duty cycle but still ensure that discovery is fast, reliable, and predictable over a range of operating conditions. Disco nodes pick a pair of prime numbers such that the sum of their reciprocals is equal to the desired radio duty cycle. Each node increments a local counter with a globallyfixed period. If a node's local counter value is divisible by either of its primes, then the node turns on its radio for one period. This protocol ensures that two nodes will have some overlapping radio on-time within a bounded number of periods, even if nodes independently set their own duty cycle. Once a neighbor is discovered, and its wakeup schedule known, rendezvous is just a matter of being awake during the neighbor's next wakeup period,for synchronous rendezvous, or during an overlapping wake period, for asynchronous rendezvous.

title: U-connect: a low-latency energy-efficient asynchronous neighbor discovery protocol
abstract: Mobile sensor nodes can be used for a wide variety of applications such as social networks and location tracking. An important requirement for all such applications is that the mobile nodes need to actively discover their neighbors with minimal energy and latency. Nodes in mobile networks are not necessarily synchronized with each other, making the neighbor discovery problem all the more challenging. In this paper, we propose a neighbor discovery protocol called U-Connect, which achieves neighbor discovery at minimal and predictable energy costs while allowing nodes to pick dissimilar duty-cycles. We provide a theoretical formulation of this asynchronous neighbor discovery problem, and evaluate it using the power-latency product metric. We analytically establish that U-Connect is an 1.5-approximation algorithm for the symmetric asynchronous neighbor discovery problem, whereas existing protocols like Quorum and Disco are 2-approximation algorithms. We evaluate the performance of U-Connect and compare the performance of U-Connect with that of existing neighbor discovery protocols. We have implemented U-Connect on our custom portable FireFly Badge hardware platform. A key aspect of our implementation is that it uses a slot duration of only 250μs, and achieves orders of magnitude lower latency for a given duty cycle compared to existing schemes for wireless sensor networks. We provide experimental results from our implementation on a network of around 20 sensor nodes. Finally, we also describe a Friend-Finder application that uses the neighbor discovery service provided by U-Connect.

title: Acc: generic on-demand accelerations for neighbor discovery in mobile applications
abstract: As a supporting primitive of many mobile device applications, neighbor discovery identifies nearby devices so that they can exchange information and collaborate in a peer-to-peer manner. To date, discovery schemes trade a long latency for energy efficiency and require a collaborative duty cycle pattern, and thus they are not suitable for interactive mobile applications where a user is unable to configure others' devices. In this paper, we propose Acc, which serves as an on-demand generic discovery accelerating middleware for many existing neighbor discovery schemes. Acc leverages the discovery capabilities of neighbor devices, supporting both direct and indirect neighbor discoveries. Our evaluations show that Acc-assisted discovery schemes reduce latency by a maximum of 51.8%, compared with the schemes consuming the same amount of energy. We further present and evaluate a Crowd-Alert application where Acc can be employed by taxi drivers to accelerate selection of a direction with fewer competing taxis and more potential passengers, based on a 10 GB dataset of more than 15,000 taxis in a metropolitan area.

title: Programming Wireless Sensor Networks with the TeenyLimeMiddleware
abstract: Wireless sensor networks (WSNs) are evolving to support sense-and-react applications, where actuators are physically interspersed with the sensors that trigger them. This solution maximizes localized interactions, improving resource utilization and reducing latency w.r.t. solutions with a centralized sink. Nevertheless, application development becomes more complex: the control logic must be embedded in the network, and coordination among multiple tasks is needed to achieve the application goals. 
 
This paper presents TeenyLime, a WSN middleware designed to address the above challenges. TeenyLime provides programmers with the high-level abstraction of a tuple space, enabling data sharing among neighboring devices. These and other WSN-specific constructs simplify the development of a wide range of applications, including sense-and-react ones. TeenyLime yields simpler, cleaner, and more reusable implementations, at the cost of only a very limited decrease in performance. We support these claims through a source-level, quantitative comparison between implementations based on TeenyLime and on mainstream approaches, and by analyzing measures of processing overhead and power consumption obtained through cycle-accurate emulation.

title: NetDetect: Neighborhood Discovery in Wireless Networks Using Adaptive Beacons
abstract: It is generally foreseen that the number of wirelessly connected networking devices will increase in the next decades, leading to a rise in the number of applications involving large-scale networks. A major building block for enabling self-* system properties in ad-hoc scenarios is the run-time discovery of neighboring devices and somewhat equivalently, the estimation of the local node density. This problem has been studied extensively before, mainly in the context of fully-connected, synchronized networks. In this paper, we propose a novel adaptive and decentralized solution, the NetDetect algorithm, to the problem of discovering neighbors in a dynamic wireless network. The main difference with existing state of the art is that we target dynamic scenarios, i.e., multihop mesh networks involving mobile devices. The algorithm exploits the beaconing communication mechanism, dynamically adapting the beacon rate of the devices in the network based on local estimates of neighbor densities. We evaluate NetDetect on a variety of networks with increasing levels of dynamics: fully-connected networks, static and mobile multi-hop mesh networks. Results show that NetDetect performs well in all considered scenarios, maintaining a high rate of neighbor discoveries and good estimate of the neighborhood density even in very dynamic situations. More importantly, the proposed solution is adaptive, tracking changes in the local environment of the nodes without any additional algorithmic reconfiguration. Comparison with existing approaches shows that the proposed scheme is efficient from both convergence time and energy perspectives.

title: Self-stabilizing systems in spite of distributed control
abstract: The synchronization task between loosely coupled cyclic sequential processes (as can be distinguished in, for instance, operating systems) can be viewed as keeping the relation “the system is in a legitimate state” invariant. As a result, each individual process step that could possibly cause violation of that relation has to be preceded by a test deciding whether the process in question is allowed to proceed or has to be delayed. The resulting design is readily—and quite systematically—implemented if the different processes can be granted mutually exclusive access to a common store in which “the current system state” is recorded.

title: Self Stabilization
abstract: AULT tolerance and reliability are important issues for flight vehicles such as aircraft, space-shuttles, and satellites. A self-stabilizing system recovers automatically following disturbances that force the system to an arbitrary state. The self-stabilization concept is an essential property of any autonomous control/computing system. Important branches of distributed computing theory were initiated because of the need for fault-tolerance of aircraft computing devices. The Byzantine fault model, for example, was a creation of the NASA SIFT project of more than a couple of decades ago. The Byzantine fault model is an elegant abstraction of faults where it is assumed that faulty parts behave as adversaries. The idea is to use redundancy—for instance, in the number of processors—in order to overcome the behavior of faulty processors. This line of thinking fits the common practice in engineering in which the design of critical parts is done independently by several design teams to make sure that there is no mistake in the calculations. Analogously, in the Byzantine fault model, some processors are simultaneously computing the same calculations for implementing a robust flight controller; thus the flight controller can function well in spite of the faulty behavior of several of the processors. Faulty behavior cannot be anticipated, the most severe behavior is therefore assumed—one that is reminiscent of the behavior of an adversary in the Byzantine court, in which backstabbing was common. A formal impossibility proof shows that, in order to ensure the correct behavior of the system, less than one-third of the processors may be of the Byzantine type. The task examined is the agreement, or consensus, for which processors need to decide on the same output, which is the input of one of the processors. The decision can be viewed as choosing the common result among the results of the design teams in the engineering example. The intuition behind the impossibility result is as follows: assume you have met two persons, Alice and Bob, one of which is honest while the other is not. You may try to decide what to do by speaking with each of them. Because you do not know which of the two is honest, you have to find this out. You may try a direct question to Alice asking who among them is not honest; Alice will answer Bob, and Bob, if asked, will obviously answer Alice. Each of them may also describe the conversations he/she had with the other, knowing that no one listened to the communication between them. This symmetry in the weights of the answers of Alice and Bob make it impossible to decide. It is possible to formally prove that agreement can be achieved if, and only if, less than one-third of the processors are Byzantine (e.g. Ref. 7). Systems that tolerate Byzantine faults are designed for flight devices, which need to be extremely robust. In such a device, the assumptions made for reaching agreement can be violated: Is it reasonable to assume that, during any period of the execution, less than one-third of the processors are faulty? What happens if, for a short period, more than a third are faulty, or perhaps experience a weaker fault than a Byzantine fault (say, caused by a transient electric spark)? What happens if messages sent by non-faulty processors are lost in one instant of time? Seven years prior to the introduction of the Byzantine fault model, Edsger W. Dijkstra suggested an important fundamental fault tolerance property called self-stabilization; 3 that is, to design the system as if there were no (yesterday) past history—a system that can be started in any possible state of its state space. It would therefore not be assumed that consistency was maintained from the fixed initial state by always executing steps according to the program of the processors. Self-stabilizing systems thus overcome transient faults. Temporary violations of the assumptions made by the algorithm designer can be viewed as leaving the system in an arbitrary initial state from which the system resumes. Self-stabilizing systems work correctly when started in any initial system state. Thus, even if the system loses its consistency due to an unexpected temporary violation of the assumptions made, it converges to legal behavior once the assumptions start to hold again. Self-stabilization is a strong fault tolerance property for systems; it ensures automatic recovery once faults stop occurring. A self-stabilizing system is designed to start in any possible state where its components—e.g., processors, processes, communication links, communication buffers—are in an arbitrary state; i.e., arbitrary variable values,

title: Abstractions for safe concurrent programming in networked embedded systems
abstract: Over the last several years, large-scale wireless mote networks have made possible the exploration of a new class of highly-concurrent and highly-distributed applications. As the horizon of what kinds of applications can be built on these networked embedded systems keeps expanding, there is a need to keep the activity of programming such systems easy, efficient, and scalable. We make three major contributions in this paper. First, we present a library for TinyOS and nesC that enables true multi-threading on a mote. This library includes support for all mote platforms in use currently (AVR, MSP). Second, we present a tool that can effectively and accurately compute stack requirements for multithreaded programs. Such analysis ensures that the stacks allocated to individual threads are correctly sized. Finally, we present a collection of programming abstractions that simplifies the construction of concurrent systems for the mote platform. We also present experimental results obtained from several example systems built using our concurrent programming abstractions and the underlying thread library.

title: Failure Detection Sequencers: Necessary and Sufficient Information about Failures to Solve Predicate Detection
abstract: This paper investigates the amount of information about failures needed to solve the predicate detection problem in asynchronous systems with crash failures. In particular, we show that predicate detection cannot be solved with traditional failure detectors, which are only functions of failures. In analogy to the definition of failure detectors, we define a failure detection sequencer, which can be regarded as a generalization of a failure detector. More specifically, our failure detection sequencer ? outputs information about failures and about the final state of the crashed process. We show that ? is necessary and sufficient to solve predicate detection. Moreover, ? can be implemented in synchronous systems. Finally, we relate sequencers to perfect failure detectors and characterize the amount of knowledge about failures they additionally offer.

title: Detectors and correctors: a theory of fault-tolerance components
abstract: Two primitive components, namely detectors and correctors, provide a basis for achieving the different types of fault tolerance properties required in computing systems. We develop the theory of these primitive tolerance components, characterizing precisely their role in achieving the different types of fault tolerance. Also, we illustrate how they can be used to formulate extant design methods and argue that they sometimes offer the potential for better designs than those obtained from extant methods.

title: The flooding time synchronization protocol
abstract: Wireless sensor network applications, similarly to other distributed systems, often require a scalable time synchronization service enabling data consistency and coordination. This paper describes the Flooding Time Synchronization Protocol (FTSP), especially tailored for applications requiring stringent precision on resource limited wireless platforms. The proposed time synchronization protocol uses low communication bandwidth and it is robust against node and link failures. The FTSP achieves its robustness by utilizing periodic flooding of synchronization messages, and implicit dynamic topology update. The unique high precision performance is reached by utilizing MAC-layer time-stamping and comprehensive error compensation including clock skew estimation. The sources of delays and uncertainties in message transmission are analyzed in detail and techniques are presented to mitigate their effects. The FTSP was implemented on the Berkeley Mica2 platform and evaluated in a 60-node, multi-hop setup. The average per-hop synchronization error was in the one microsecond range, which is markedly better than that of the existing RBS and TPSN algorithms.

title: Efficient network flooding and time synchronization with Glossy
abstract: This paper presents Glossy, a novel flooding architecture for wireless sensor networks. Glossy exploits constructive interference of IEEE 802.15.4 symbols for fast network flooding and implicit time synchronization. We derive a timing requirement to make concurrent transmissions of the same packet interfere constructively, allowing a receiver to decode the packet even in the absence of capture effects. To satisfy this requirement, our design temporally decouples flooding from other network activities. We analyze Glossy using a mixture of statistical and worst-case models, and evaluate it through experiments under controlled settings and on three wireless sensor testbeds. Our results show that Glossy floods packets within a few milliseconds and achieves an average time synchronization error below one microsecond. In most cases, a node receives the flooding packet with a probability higher than 99.99 %, while having its radio turned on for only a few milliseconds during a flood. Moreover, unlike existing flooding schemes, Glossy's performance exhibits no noticeable dependency on node density, which facilitates its application in diverse real-world settings.

title: A unifying link abstraction for wireless sensor networks
abstract: Recent technological advances and the continuing quest for greater efficiency have led to an explosion of link and network protocols for wireless sensor networks. These protocols embody very different assumptions about network stack composition and, as such, have limited interoperability. It has been suggested  that, in principle, wireless sensor networks would benefit from a unifying abstraction (or "narrow waist" in architectural terms), and that this abstraction should be closer to the link level than the network level. This paper takes that vague principle and turns it into practice, by proposing a specific unifying sensornet protocol (SP) that provides shared neighbor management and a message pool.The two goals of a unifying abstraction are generality and efficiency: it should be capable of running over a broad range of link-layer technologies and supporting a wide variety of network protocols, and doing so should not lead to a significant loss of efficiency. To investigate the extent to which SP meets these goals, we implemented SP (in TinyOS) on top of two very different radio technologies: B-MAC on mica2 and IEEE 802.15.4 on Telos. We also built a variety of network protocols on SP, including examples of collection routing [53], dissemination [26], and aggregation . Measurements show that these protocols do not sacrifice performance through the use of our SP abstraction.

title: uCast: Unified Connectionless Multicast for Energy Efficient Content Distribution in Sensor Networks
abstract: In this paper, we present uCast, a novel multicast protocol for energy efficient content distribution in sensor networks. We design uCast to support a large number of multicast sessions, especially when the number of destinations in a session is small. In uCast, we do not keep any state information relevant to ongoing multicast deliveries at intermediate nodes. Rather, we directly encode the multicast information in the packet headers and parse these headers at intermediate nodes using a scoreboard algorithm proposed in this paper. We demonstrate that 1) uCast is powerful enough to support multiple addressing and unicast routing schemes and 2) uCast is robust, efficient, and scalable in the face of changes in network topology, such as those introduced by energy conservation protocols. We systematically evaluate the performance of uCast through simulations, compare it with other state-of-the-art protocols, and collect preliminary data from a running system based on the Berkeley motes platform

title: Routing, Anycast, and Multicast for Mesh and Sensor Networks
abstract: This paper studies routing schemes and their distributed construction in limited wireless networks, such as sensor or mesh networks. We argue that the connectivity of such networks is well captured by a constant doubling metric and present a constant stretch multicast algorithm through which any network node u can send messages to an arbitrary receiver set U. In other words, we describe a distributed approximation algorithm which is only a constant factor off the NP-hard minimum Steiner tree on u cupU. As a building block for the multicasting, we construct a 1 + epsiv stretch labeled routing scheme with label size O(log ominus) and storage overhead O(1/epsiv)alpha(log ominus)(O(alpha) + log Delta), where ominus is the diameter of the network, Delta the maximum degree of any network node, and alpha a constant representing the doubling dimension of the network. In addition to unicast and multicast, we present a constant approximation for anycasting on the basis of radic(6)-approximate distance queries. We provide a distributed algorithm to construct the required labeling and routing tables.

title: On Consistent Neighborhood Views in Wireless Sensor Networks
abstract: Wireless sensor networks (WSNs) are characterized by localized interactions. Indeed, several WSN algorithms and protocols work in a decentralized fashion by coordinating nodes within the wireless communication range, e.g., localization algorithms and MAC protocols. Nevertheless, most often these mechanisms do not address faults that may affect the way wireless neighborhoods are recognized by nodes, e.g., as in the case of data corruption. As the operation of these mechanisms is rooted in the use of topology information, these faults may be a significant detriment to correct and efficient system operation.In this paper, we argue that the above issues are particular instances of a general problem of consistent neighborhood view. We present three increasingly weaker specifications of the problem. Next, we prove the impossibility of solving the two stronger specifications, and provide an algorithm to solve the weakest specification. In addition, we implement our algorithm in a commonly used WSN network stack, and assess its performance both in simulation and in a real-world testbed. The results show that, when possible, our mechanisms efficiently solve the problem of consistent neighborhood view, providing higher-level mechanisms with a re-usable building block to leverage off.

title: Impact of network density on data aggregation in wireless sensor networks
abstract: In-network data aggregation is essential for wireless sensor networks where energy resources are limited. In a previously proposed data dissemination scheme (directed diffusion with opportunistic aggregation), data is opportunistically aggregated at intermediate nodes on a low-latency tree. In this paper, we explore and evaluate greedy aggregation, a novel approach that adjusts aggregation points to increase the amount of path sharing, reducing energy consumption. Our preliminary results suggest that, under investigated scenarios, greedy aggregation can achieve up to 45% energy savings over opportunistic aggregation in high-density networks without adversely impacting latency or robustness.

title: TWIST: a scalable and reconfigurable testbed for wireless indoor experiments with sensor networks
abstract: We present TWIST, a scalable and exible testbed architecture for indoor deployment of wireless sensor networks. The design of TWIST is based on an analysis of typical and desirable use-cases. It provides basic services like node configuration, network-wide programming, out-of-band extraction of debug data and gathering of application data, and also introduces several novel features.Firstly, TWIST supports experiments with heterogeneous node platforms. Secondly, it supports active power supply control of the nodes. This enables easy transition between USB-powered and battery-powered experiments, dynamic selection of topologies as well as controlled injection of node failures into the system. Thirdly, TWIST supports creation of both at and hierarchical sensor networks. For this we introduce a layer of "super nodes" that on one hand form a part of the testbed infrastructure but can also play a role as elements of the sensor network.The self-configuration capability, the use of hardware with standardized interfaces and open-source software makes the TWIST architecture scalable, affordable, and easily repli-cable. To demonstrate its usefulness, we present our experiences with building and using a specific realization of TWIST that spans three floors of our office building and supports over one hundred sensor nodes.

title: A Survey of Fault Management in Wireless Sensor Networks
abstract: Wireless sensor networks are resource-constrained self-organizing systems that are often deployed in inaccessible and inhospitable environments in order to collect data about some outside world phenomenon. For most sensor network applications, point-to-point reliability is not the main objective; instead, reliable event-of-interest delivery to the server needs to be guaranteed (possibly with a certain probability). The nature of communication in sensor networks is unpredictable and failure-prone, even more so than in regular wireless ad hoc networks. Therefore, it is essential to provide fault tolerant techniques for distributed sensor applications. Many recent studies in this area take drastically different approaches to addressing the fault tolerance issue in routing, transport and/or application layers. In this paper, we summarize and compare existing fault tolerant techniques to support sensor applications. We also discuss several interesting open research directions.

title: Fault Diagnosis in Wireless Sensor Networks: A Survey
abstract: The sensor nodes in wireless sensor networks may be deployed in unattended and possibly hostile environments. The ill-disposed environment affects the monitoring infrastructure that includes the sensor nodes and the network. In addition, node failures and environmental hazards cause frequent topology changes, communication failures, and network partitioning. This in turn adds a new dimension to the fragility of the network topology. Such perturbations are far more common than those found in conventional wireless networks thus, demand efficient techniques for discovering disruptive behavior in such networks. Traditional fault diagnosis techniques devised for multiprocessor systems are not directly applicable to wireless sensor networks due to their specific requirements and limitations. This survey integrates research efforts that have been produced in fault diagnosis specifically for wireless sensor networks. The survey aims at clarifying and uncovering the potential of this technology by providing the technique-based taxonomy. The fault diagnosis techniques are classified based on the nature of the tests, correlation between sensor readings and characteristics of sensor nodes and the network.

title: A Survey on Fault Tolerant Routing Techniques in Wireless Sensor Networks
abstract: Wireless Sensor Networks are without a doubt one of the central issues in current research topics due to the harsh environmental conditions in which such networks can be deployed and their unique sensor network characteristics,specifically limited power supply, sensing, processing and communication capabilities. Presented with many challenges and design issues that affect the data routing, a need for a fault tolerant routing protocol becomes essential. In this paper, we summarize and highlight the key ideas of existing fault tolerant techniques of routing protocols, survey existing routing protocols proposed to support fault tolerance. Finally, we provide some future research directions in the area of fault tolerance in wireless sensor networks routing.

title: A survey on resiliency assessment techniques for wireless sensor networks
abstract: Resiliency is becoming one of the most important non functional properties of Wireless Sensor Networks (WSNs), as their adoption is more and more hypothesized in critical application scenarios. Hence, assessing the resiliency of WSN applications, protocols, and platforms is starting to be an import concern for WSN designers and developers. This paper presents the techniques that are currently used in the field of WSN resiliency assessment, categorized as experimental, simulative, analytical and formal techniques. After reporting the state-of-art according to the four categories, the paper discusses research trends, strengths and weaknesses of existing approaches, and concludes with open issues and ongoing challenges.

title: Modeling and Analysis of Fault Detection and Fault Tolerance in Wireless Sensor Networks
abstract: Technological advancements in communications and embedded systems have led to the proliferation of Wireless Sensor Networks (WSNs) in a wide variety of application domains. These application domains include but are not limited to mission-critical (e.g., security, defense, space, satellite) or safety-related (e.g., health care, active volcano monitoring) systems. One commonality across all WSN application domains is the need to meet application requirements (e.g., lifetime, reliability). Many application domains require that sensor nodes be deployed in harsh environments, such as on the ocean floor or in an active volcano, making these nodes more prone to failures. Sensor node failures can be catastrophic for critical or safety-related systems. This article models and analyzes fault detection and fault tolerance in WSNs. To determine the effectiveness and accuracy of fault detection algorithms, we simulate these algorithms using ns-2. We investigate the synergy between fault detection and fault tolerance and use the fault detection algorithms’ accuracies in our modeling of Fault-Tolerant (FT) WSNs. We develop Markov models for characterizing WSN reliability and Mean Time to Failure (MTTF) to facilitate WSN application-specific design. Results obtained from our FT modeling reveal that an FT WSN composed of duplex sensor nodes can result in as high as a 100% MTTF increase and approximately a 350% improvement in reliability over a Non-Fault-Tolerant (NFT) WSN. The article also highlights future research directions for the design and deployment of reliable and trustworthy WSNs.

title: Fault detection of wireless sensor networks
abstract: This paper presents a distributed fault detection algorithm for wireless sensor networks. Faulty sensor nodes are identified based on comparisons between neighboring nodes and dissemination of the decision made at each node. Time redundancy is used to tolerate transient faults in sensing and communication. To eliminate delay involved in time redundancy scheme a sliding window is employed with some storage for previous comparison results. Simulation results show that sensor nodes with permanent faults are identified with high accuracy for a wide range of fault rates, while most of the transient faults are tolerated with negligible performance degradation.

title: Blind Calibration of Sensor Networks
abstract: This paper considers the problem of blindly calibrating sensor response using routine sensor network measurements. We show that as long as the sensors slightly oversample the signals of interest, then unknown sensor gains can be perfectly recovered. Remarkably, neither a controlled stimulus nor a dense deployment is required. We also characterize necessary and sufficient conditions for the identification of unknown sensor offsets. Our results exploit incoherence conditions between the basis for the signals and the canonical or natural basis for the sensor measurements. Practical algorithms for gain and offset identification are proposed based on the singular value decomposition and standard least squares techniques. We investigate the robustness of the proposed algorithms to model mismatch and noise on both simulated data and on data from current sensor network deployments.

title: Sensor faults: Detection methods and prevalence in real-world datasets
abstract: Various sensor network measurement studies have reported instances of transient faults in sensor readings. In this work, we seek to answer a simple question: How often are such faults observed in real deployments? We focus on three types of transient faults, caused by faulty sensor readings that appear abnormal. To understand the prevalence of such faults, we first explore and characterize four qualitatively different classes of fault detection methods. Rule-based methods leverage domain knowledge to develop heuristic rules for detecting and identifying faults. Estimation methods predict “normal” sensor behavior by leveraging sensor correlations, flagging anomalous sensor readings as faults. Time-series-analysis-based methods start with an a priori model for sensor readings. A sensor measurement is compared against its predicted value computed using time series forecasting to determine if it is faulty. Learning-based methods infer a model for the “normal” sensor readings using training data, and then statistically detect and identify classes of faults.
 We find that these four classes of methods sit at different points on the accuracy/robustness spectrum. Rule-based methods can be highly accurate, but their accuracy depends critically on the choice of parameters. Learning methods can be cumbersome to train, but can accurately detect and classify faults. Estimation methods are accurate, but cannot classify faults. Time-series-analysis-based methods are more effective for detecting short duration faults than long duration ones, and incur more false positives than the other methods. We apply these techniques to four real-world sensor datasets and find that the prevalence of faults as well as their type varies with datasets. All four methods are qualitatively consistent in identifying sensor faults, lending credence to our observations. Our work is a first step towards automated online fault detection and classification.

title: Detecting Faulty Nodes with Data Errors for Wireless Sensor Networks
abstract: Wireless Sensor Networks (WSN) promise researchers a powerful instrument for observing sizable phenomena with fine granularity over long periods. Since the accuracy of data is important to the whole system's performance, detecting nodes with faulty readings is an essential issue in network management. As a complementary solution to detecting nodes with functional faults, this article, proposes FIND, a novel method to detect nodes with data faults that neither assumes a particular sensing model nor requires costly event injections. After the nodes in a network detect a natural event, FIND ranks the nodes based on their sensing readings as well as their physical distances from the event. FIND works for systems where the measured signal attenuates with distance. A node is considered faulty if there is a significant mismatch between the sensor data rank and the distance rank. Theoretically, we show that average ranking difference is a provable indicator of possible data faults. FIND is extensively evaluated in simulations and two test bed experiments with up to 25 MicaZ nodes. Evaluation shows that FIND has a less than 5% miss detection rate and false alarm rate in most noisy environments.

title: A Taxonomic Approach to Topology Control in Ad Hoc and Wireless Networks
abstract: Topology control (TC) aims at tuning the topology of highly dynamic networks to provide better control over network resources and to increase the efficiency of communication. Recently, many TC protocols have been proposed. The protocols are designed for preserving connectivity, minimizing energy consumption, maximizing the overall network coverage or network capacity. Each TC protocol makes different assumptions about the network topology, environment detection resources, and control capacities. This circumstance makes it extremely difficult to comprehend the role and purpose of each protocol. To tackle this situation, a taxonomy for TC protocols is presented throughout this paper. Additionally, some TC protocols are classified based upon this taxonomy.

title: On FTSS-solvable distributed problems
abstract: We investigate which distributed problems can be solved with so-called k-ftss protocols that combine two types of failure resilience: k-jardttolerance (k-ft ) and selfstabi~ization (ss). In fault-tolerance, one sssumes that up to k processes may operate incorrectly; we consider only crash faults where a process abruptly terminates all activity. In self-stabilization, one assumes that all processes operate correctly while the configuration (states of memories and communication finks) can be corrupted arbitrarily. Ft protocofs suspect all incoming information and guarantee legaf behavior of correct processes by preceding each step with a sufficient number of checks. Ss protocols allow processes to behave inconsistently but guarantee an automatic return to legaf behavior from any arbitrary configuration after all corruption ceases. A k-ftss protocol (1) brings correct processes to legal behavior from any configuration despite the presence of up to k crashes, and (2) once established, it guarantees continued legal behavior despite up to k crsshes. Generalizing from [AH93], we give a sufficient condition for identifying cases where ftss solutions are impossible: if a problem is k-fault-sensitive on an asynchronous (j, k)restrictable network then it cannot be k-ftss solved on that network. In a (j, k)-restrictable network of size n, there are j z k processes s.t. if they are extremely slow, then the n – j

title: Transient Fault Detectors
abstract: We present fault detectors for transient faults, (i.e., corruptions of the memory of the processors, but not of the code of the processors). We distinguish fault detectors for tasks (i.e., the problem to be solved) from failure detectors for implementations (i.e., the algorithm that solves the problem). The aim of our fault detectors is to detect a memory corruption as soon as possible. We study the amount of memory needed by the fault detectors for some specific tasks, and give bounds for each task. The amount of memory is related to the size and the number of views that a processor has to maintain to ensure a quick detection. This work may give the implementation designer hints concerning the techniques and resources that are required for implementing a task.

title: Revisiting Failure Detection and Consensus in Omission Failure Environments
abstract: It has recently been shown that fair exchange, a security problem in distributed systems, can be reduced to a fault tolerance problem, namely a special form of distributed consensus. The reduction uses the concept of security modules which reduce the type and nature of adversarial behavior to two standard fault-assumptions: message omission and process crash. In this paper, we investigate the feasibility of solving consensus in asynchronous systems in which crash and message omission faults may occur. Due to the impossibility result of consensus in such systems, following the lines of unreliable failure detectors of Chandra and Toueg, we add to the system a distributed device that gives information about the failure of other processes. Then we give an algorithm using this device to solve the consensus problem. Finally, we show how to implement such a device in an asynchronous system using some weak timing assumptions.

title: Failure detection and consensus in the crash-recovery model
abstract: We study the problems of failure detection and consensus in asynchronous systems in which processes may crash and recover, and links may lose messages. We first propose new failure detectors that are particularly suitable to the crash-recovery model. We next determine under what conditions stable storage is necessary to solve consensus in this model. Using the new failure detectors, we give two consensus algorithms that match these conditions: one requires stable storage and the other does not. Both algorithms tolerate link failures and are particularly efficient in the runs that are most likely in practice – those with no failures or failure detector mistakes. In such runs, consensus is achieved within $3 \delta$ time and with 4 n messages, where $\delta$ is the maximum message delay and n is the number of processes in the system.