ARA is an at-scale Platform for Advanced Wireless Research (PAWR), specifically tailored to the unique community, application, and economic context of rural regions. It features the first-of-its-kind real-world implementation of long-distance, high-capacity wireless backhaul and access systems spanning over 30 km in diameter. Leveraging both software-defined radios and programmable Commercial Off-The-Shelf (COTS) systems, ARA orchestrates the wireless resources alongside the networking and compute resources for enabling end-to-end experiments involving user equipment, base stations, edge computing, and cloud infrastructure. Such an integration facilitates the coevolution of rural-focused wireless innovation and applications, while helping to advance the frontiers of advanced Next-G wireless systems such as Open RAN. As of summer 2024, ARA is publicly accessible with 7 base stations (BSes) and over 30 user equipment (UEs). In this demo, we share advanced wireless research experiments enabled by ARA, involving MU-MIMO in TV White Space (TVWS) bands, long-range mmWave and microwave backhaul communications, and open-source 5G NR protocol stacks such as srsRAN and OpenAirInterface (OAI).

Edge deployments perform complex deep learning inference and analysis in the wild in highly resource constrained environment. They are positioned everywhere from our largest cities to the bottom of our oceans, and often necessitate significant financial resources and labor to create and deploy. These properties make correctness of edge deployments simultaneously extremely important and difficult to verify a priori. In the past decade, a series of IoT and cloud testbeds have emerged to facilitate this testing. They provide users with access to resources and, less often, sensors that can be used to emulate workloads before deployment. While developers can use these resources to verify the correctness of their configurations, often users would like to “right-size” their deployments - that is, to find a minimal resource configuration that guarantees correctness - to decrease cost and prevent over-provisioning. The current suite of cloud and IoT testbeds does not provide this capability. We present Righteous, an automatic deployment right-sizing tool for edge deployments. Righteous treats configuration as a hyperparameter optimization problem, testing hyperparameter combinations to find a near-optimal configuration as quickly as possible. Righteous uses a new optimization algorithm, informed Pareto Simulated Annealing (iPSA) to find near-optimal configurations faster than other leading approaches. We use Righteous in conjunction with the PROWESS testbed to optimize a drone swarm deployment workload. Our results demonstrate that Righteous configurations use up to 3.5X less resources than those identified by leading hyperparameter tuning and resource allocation techniques, and does so up to 76.3X faster.

Time synchronization is a critical component in network operation and management, and it is also required by Ultra-Reliable, Low-Latency Communications (URLLC) in next-generation wireless systems such as those of 5G, 6G, and Open RAN. In this context, we design and implement AraSync as an end-to-end time synchronization system in the ARA wireless living lab to enable advanced wireless experiments and applications involving stringent time constraints. We make use of Precision Time Protocol (PTP) at different levels to achieve synchronization accuracy in the order of nanoseconds. Along with fiber networks, AraSync enables time synchronization across the AraHaul wireless x-haul network consisting of long-range, high-capacity mmWave and microwave links. In this paper, we present the detailed design and implementation of AraSync, including its hardware and software components and the PTP network topology. Further, we experimentally characterize the performance of AraSync from spatial and temporal dimensions. Our measurement and analysis of the clock offset and mean path delay show the impact of the wireless channel and weather conditions on the PTP synchronization accuracy.

As the Platform for Advanced Wireless Research (PAWR) in rural broadband, the ARA wireless living lab features the deployment of first-of-its-kind wireless access and backhaul platforms in real-world agriculture and rural settings, and preliminary experiments have demonstrated very promising results, e.g., up to 3.2 Gbps wireless access throughput and more than 10 Gbps throughput across a wireless backhaul link of over 10 km. ARA is expected to be publicly released for broad community use starting in September 2023. Through this demo, we plan to share, for the first time, with the wireless research community the transformative research experiments enabled by ARA. To stimulate discussion and community participation, we will demonstrate a few example experiments ranging from MU-MIMO in TV White Space (TVWS) bands to long-range mmWave and microwave backhaul communications, as well as open-source 5G NR protocol stacks such as srsRAN and OpenAirInterface.

Digital contact tracing offers significant promise to help reduce the spread of SARS-CoV-2 and other viruses. Google and Apple joined together in 2020 to create the Google/Apple Exposure Notification (GAEN) framework to determine encounters with anonymous users later diagnosed COVID-19 positive. However, as GAEN lacks geospatial awareness, it is susceptible to geographically distributed replay attacks. Anonymous, low-cost, crowd-sourced replay attack networks deployed by malicious actors (or far away nation-state attackers) who utilize malicious (or innocent) users’ smartphones to capture and replay GAEN advertisements can drastically increase false-positive rates even in areas that otherwise exhibit low positivity rates. In response to this powerful replay attack, we introduce GAEN+ , a solution that enhances GAEN with geospatial awareness while maintaining user privacy, and demonstrate its ability to effectively prevent geographically distributed replay attacks.

Embedding models that encode semantic information into low-dimensional vector representations are useful in various machine learning tasks with limited training data. However, these models are typically too large to support inference in small edge devices, which motivates training of smaller yet comparably predictive student embedding models through knowledge distillation (KD). While knowledge distillation traditionally uses the teacher’s original training dataset to train the student, we hypothesize that using a dataset similar to the student’s target domain allows for better compression and training efficiency for the said domain, at the cost of reduced generality across other (non-pertinent) domains. Hence, we introduce Specialized Embedding Approximation (SEA) to train a student featurizer to approximate the teacher’s embedding manifold for a given target domain. We demonstrate the feasibility of SEA in the context of acoustic event classification for urban noise monitoring and show that leveraging a dataset related to this target domain not only improves the baseline performance of the original embedding model but also yields competitive students with >1 order of magnitude lesser storage and activation memory. We further investigate the impact of using random and informed sampling techniques for dimensionality reduction in SEA.

Edge sensing with micro-power pulse-Doppler radars is an emergent domain in monitoring and surveillance with several smart city applications. Existing solutions for the clutter versus multi-source radar classification task are limited in terms of either accuracy or efficiency, and in some cases, struggle with a tradeoff between false alarms and recall of sources. We find that this problem can be resolved by learning the classifier across multiple time-scales. We propose a multi-scale, cascaded recurrent neural network architecture, MSC-RNN, composed of an efficient multi-instance learning (MIL) Recurrent Neural Network (RNN) for clutter discrimination at a lower tier and a more complex RNN classifier for source classification at the upper tier. By controlling the invocation of the upper RNN with the help of the lower tier conditionally, MSC-RNN achieves an overall accuracy of 0.972. Our approach holistically improves the accuracy and per-class recalls over machine learning models suitable for radar inferencing. Notably, we outperform cross-domain handcrafted feature engineering with purely time-domain deep feature learning, while also being up to ∼3× more efficient than a competitive solution.

The status quo of limited broadband connectivity in rural areas motivates the need for fielding alternatives such as long-distance wireless mesh networks. A key aspect of fielding wireless meshes cost-effectively is planning how to connect the last-mile networks to the core network service providers (i.e., the network between the edge access terminals and the landline / optical fiber terminals) with minimal infrastructure cost and throughput constraints. This so-called middle-mile network optimization, which includes topology construction, tower height assignment, antenna and orientation selection, as well as transmit power assignment, is known to be a computationally hard problem. In this paper, we provide the first polynomial time approximation solution for a generalized version of the middle-mile network optimization problem, wherein point-to-point (i.e., WiFi p2p) links are deployed to bridge last-mile networks. Our solution has a cost performance ratio of O(ln|A| + |B|/|A| + |A|+|B|/γ), where A and B respectively denote the number of terminals and nonterminals and γ is the ratio of link capacity/terminal demand. Furthermore, our solution extends to hybrid networks, i.e., point-to-multipoint (i.e., WiFi p2mp) or omnidirectional (i.e., TV White Space) can serve as hyperlinks in addition to point-to-point links, to further reduce the cost of wireless links. We provide a complementary heuristic for our middle-mile network optimization solution that adds hyperlinks if and only if they reduce the cost.

A vast literature on secret sharing protocols now exists based on the folk theorem that the wireless channel between communicating parties Alice and Bob cannot be controlled or predicted by a third party in a fine-grain way. We find that the folk theorem unfortunately does not hold. In particular, we show how an adversary, using a customized full-duplex forwarder, can control the channel seen by Alice and Bob in fine granularity without leaving a trace, while predicting with high probability the secrets generated by any channel reciprocity based secret sharing protocol. An implementation of our proposed secret manipulator, called Channel Spoofer, on a software-defined radio platform empirically verifies Channel Spoofer's effectiveness in breaking several representative state-of-the-art secret sharing protocols. To the best of our knowledge, the proposed Channel Spoofer is the first practical attacker against all extant channel reciprocity based secret sharing protocols.

Target discrimination in wireless sensor networks remains challenging when sensors have structured electronic noise and deployment settings have variable in-situ clutter. Data-driven learning of discrimination functions is especially hard when deployment sites are remote or hazardous, necessitating reliance on surrogate environments for data collection. The challenge is exacerbated if sensors are resource constrained. We present an intruder discrimination system that addresses these challenges in the context of a battery powered radar mote. The system robustly rejects clutter moving in-situ to trigger discrimination of humans versus other targets only when said targets displace across the scene. Its learning uses a new, generic extension to feature selection methods that leverages cross-environmental robustness instead of a random or bounded model of feature noise. We experimentally validate that our scheme improves the cross-environmental performance medians and dispersions of extant methods by up to 70% and 100% respectively. It achieves optimal performance with very few features given a modest number of diverse training environments, allowing for efficient mote-scale implementation. A mote mesh network has been deployed to detect poachers while rejecting cattle and other non-targets at a rhino reserve in South Africa.

Motivated by the need for impromptu or as-you-go deployment of wireless sensor networks in some situations, we study the problem of optimal sequential deployment of wireless sensors and relays along a line (e.g., a forest trail) of unknown length. Starting from the sink node (e.g., a base station), a ”deployment agent„ walks along the line, stops at equally spaced points (”potential„ relay locations), placing relays at some of these points, until he reaches a location at which the source node (i.e., the sensor) needs to be placed, the objective being to create a multihop wireless relay network between the source and the sink. The deployment agent decides whether to place a relay or not at each of the potential locations, depending upon the link quality measurements to the previously placed relays. In this article, we seek to design efficient deployment algorithms for this class of problems, to achieve the objective of 2-connectivity in the deployed network. We ensure multi-connectivity by allowing each node to communicate with more than one neighbouring node. By proposing a network cost objective that is additive over the deployed relays, we formulate the relay placement problem as a Markov decision process. We provide structural results for the optimal policy and evaluate the performance of the optimal policy via numerical exploration. Computation of such an optimal deployment policy requires a statistical model for radio propagation; we extract this model from the raw data collected via measurements in a forestlike environment. To validate the results obtained from the numerical study, we provide an experimental study of algorithms for 2-connected network deployment.

Research in system stabilization has traditionally relied on the availability of a complete system implementation. As such, it would appear that the scalability and reusability of stabilization is limited in practice. To redress this perception, in this paper, we show for the first time that system stabilization may be designed knowing only the system specification but not the system implementation. We refer to stabilization designed thus as specification-based design of stabilization and identify “local everywhere specifications” and “convergence refinements” as being amenable to the specification-based design of stabilization. Using our approach, we present the design of Dijkstra's four-state stabilizing token-ring system starting from an abstract fault-intolerant token-ring system. We also present an illustration of automated design of specification-based stabilization on a three-state token-ring system.

Complex (imaginary) signals arise commonly in the field of communications in the form of time series in the complex space. In this work we propose a symbolic approach for such signals based on string kernels derived from a complex SAX representation and apply it to a challenging counting problem. Our approach, that we call cStrings, is within a Gaussian process regression framework and outperforms established Fourier transforms and complex kernels, achieving a correlation coefficient of 0.985 when predicting the number of targets sensed by a pulsed Doppler radar.

People counting is key to a diverse set of sensing applications. In this paper, we design a mote-scale event-driven solution that uses a low-power pulsed radar to estimate the number of people within the ∼10m radial range of the radar. In contrast to extant solutions, most of which use computer vision, our solution is light-weight and private. It also better tolerates the presence of obstacles that partially or fully impair line of sight; this is achieved by accounting for “small” indirect radio reflections via joint time-frequency domain features. The counter itself is realized using Support Vector Regression; the regression map is learned from a medium sized dataset of 0–∼40 people in various indoor room settings. 10-fold cross validation of our counter yields a mean absolute error of 2.17 between the estimated count and the ground truth and a correlation coefficient of 0.97.We compare the performance of our solution with baseline counters.

We demonstrate a mote-scale, human-animal classifier based on a micropower radar. Our classifier is automatically learned from diverse data, using features in the joint time-frequency domain. It is being used as part of a wireless sensor network in a forest to create a virtual fence for human and wildlife protection.

Metrics that aggregate the state of neighboring nodes are frequently used in wireless sensor networks. In this paper, we present two primitives that exploit simultaneous communications in 802.15.4 radios to enable a polling node to calculate with low power the number (or set) of its neighbors where some state predicate of interest holds. In both primitives, the poller assigns transmission powers and response lengths to its respective neighbors for their simultaneous response to each of its poll requests. The two primitives adopt complementary schemes for power assignment such that the Received Signal Strength Indicator (RSSI) of the respective signal from each neighbor is significantly different from that of all others in one primitive and nearly equivalent to that of the others in the other. The first primitive, LinearPoll, suits sparse networks and consumes energy that is linear in the size of its neighborhood, whereas the second primitive, LogPoll, suits dense networks and consumes constant energy. Compared to the state-of-the-art solutions that use multiple sub-carriers, our primitives are simpler and more compute-efficient while provide estimation with comparable quality. Compared to single-carrier solutions, our primitives achieve comparable quality at less than half the energy cost or richer information at comparable energy cost. They are also compatible with other radio physical layers. Based on our implementation for CC2420 radios on the TelosB platform, we evaluate the primitives in different wireless environments and neighborhood topologies to study their performance, the tradeoff between their estimation accuracy and energy cost, and methods for tuning their critical parameters, and we compare them with baseline counting protocols.

Capacity studies for wireless networks typically focus on scheduling of transmissions but rarely on scheduling of radio sleep-wakeup. We show that in a multi-hop network setting the duty-cycling of radios results in a per-node throughput capacity of Θ(W ψ√log n/√n) as opposed to Θ(W ψ/√ n log n) where ψ is the fraction of time each node radio is active. Likewise, in a single-hop clique network the duty-cycling of radios results in a per-node throughput capacity of Θ (Wψ), as opposed to Θ(Wψ/n). These capacity gains of Θ(log n) and Θ(n) respectively result from spreading interference over time. They emphasizes the importance of efficient co-scheduling of transmissions and sleep-wakeup, which is normally a function of the Medium Access Control (MAC) layer. We also examine how well canonical classes of duty-cycled MAC protocols achieve throughput capacity. In particular, we abstract four schedulers, each of which represents several well-used MAC schedulers, namely sender-centric synchronous (e.g. S-MAC, T-MAC, SCP-MAC), receiver-centric synchronous (e.g. O-MAC), sender-centric asynchronous (e.g. B-MAC, X-MAC, BoX-MAC), and receiver-centric asynchronous (e.g. RI-MAC). We compare the achievable throughput of these schedulers analytically; extensive experiments are then performed to corroborate our MAC analysis. The findings strongly suggest that out of the four classes receiver-centric synchronous scheme yields the smallest gap between existing MACs and the optimal scheduler.

The International Conference on Mobile Ad-hoc and Sensor Networks 2012 (MSN 2012) was held at Yinhe Dynasty Hotel, Chengdu, China. This is the Eighth conference in the series, following the successful MSN 2005 in Wuhan, MSN 2006 in Hong Kong, MSN 2007 in Beijing, MSN2008 in Wuhan, MSN 2009 in Wuyi, MSN 2010 in Hangzhou, and MSN 2011 in Beijing. This year we have received 86 submissions for the conference from different countries. The selected papers address a broad range of research issues and challenges in the field of mobile ad-hoc and sensor networks.

This article develops a shared-secret free wireless security infrastructure that provides confidentiality, identity authentication, message authentication, integrity, sender nonrepudiation, receiver nonrepudiation, and anonymity. Our infrastructure is based on two physical primitives, namely collaborative jamming and spatial signature enforcement, and a zero knowledge alternative for bootstrapping trust. Notably, it eschews the use of shared secrets, while providing a cryptosystem that is no less secure than conventional cryptosystems.

Predicting and bounding performance is a fundamental requirement in wireless sensor network (WSN) protocol development. To support a fast development cycle principled methods are required for experimentation with wireless protocols in testbed environments that can provide repeatable performance guarantees in the target environment. In this paper we propose a method to achieve performance repeatability across test and target environments, that relies on analytical prediction of expected protocol performance as a function of RF environment parameters and forwarding protocol. For the validation of the proposed method, we present analytical, simulation, and experimental results for one-dimensional networks deployed in indoor and outdoor propagation environments, and for two-dimensional networks on four major indoor WSN testbeds to validate the performance of the proposed method on achieving repeatable protocol behavior across diverse set of RF environments.

The energy efficiency of the widely used convergecast pattern depends substantially on the choice of medium access control (MAC) and routing protocol. In this paper, we formalize the maximization of convergecast energy efficiency with respect to its MAC and routing as a resource constrained optimization problem. We then analytically show that this maximization problem is linear in the context of two prototypical MACs - a locally synchronized wakeup (as in S-MAC) and a locally staggered wakeup MAC (as in O-MAC) - assuming low, uniform traffic that is delivered reliably and without interference. With this insight, we present a centralized algorithm, MeeCast, that solves the optimization problem utilizing linear programming techniques. We also design a distributed version of MeeCast, for the case where the traffic is ultra-low, and prove that it achieves optimality as well as fast convergence time. Notably, this version is self-stabilizing, so it autonomically handles changes in traffic load, network topology, loss of coordination and state corruption. In comparison with Dozer, a state-of-the-art convergecast protocol, MeeCast achieves better energy efficiency and application lifetime in the context of S-MAC and identical energy efficiency but better application lifetime in the context of O-MAC.

Using phase information from medium bandwidth Doppler Radars, it is possible to obtain motion information corresponding to changes in target range on the order of a wavelength. Comparable range resolution from ranging radars would require much wider bandwidth. For long-range radars, the power consumption depends mostly on transmitted power levels and only weakly on bandwidth. But for short range radars of the type that are most useful in Wireless Sensor Networks (WSNs), transmitted power is usually negligible compared to processing power (i.e., within the radar), and the power budget depends strongly on the bandwidth. Thus, medium-bandwidth Doppler Radars offer the opportunity to achieve finer resolution of relative range information at much lower power at the expense of absolute range information.

Link estimation is a basic element of routing in low-power wireless networks, and data-driven link estimation using unicast MAC feedback has been shown to outperform broadcast-beacon-based link estimation. Nonetheless, little is known about how different data-driven link estimation methods affect routing behaviors. To address this issue, we classify existing data-driven link estimation methods into two broad categories: L-NT that uses aggregate information about unicast and L-ETX that uses information about the individual unicast-physical-transmissions. Through mathematical analysis and experimental measurement in a testbed of 98 XSM motes (an enhanced version of MICA2 motes), we examine the accuracy and stability of L-NT and L-ETX in estimating the ETX routing metric. We also experimentally study the routing performance of L-NT and L-ETX. We discover that these two representative, seemingly similar methods of data-driven link estimation differ significantly in routing behaviors: L-ETX is much more accurate and stable than L-NT in estimating the ETX metric, and accordingly, L-ETX achieves a higher data delivery reliability and energy efficiency than L-NT (for instance, by 25.18 percent and a factor of 3.75, respectively, in our testbed). These findings provide new insight into the subtle design issues in data-driven link estimation that significantly impact the reliability, stability, and efficiency of wireless routing, thus shedding light on how to design link estimation methods for mission-critical wireless networks which pose stringent requirements on reliability and predictability.

Link asymmetry is one of the unique challenges that wireless sensor networks pose in the design of network protocols. We observe, based on testbed experiments, that a substantial percentage of links are asymmetric, many are even unidirectional. We also find that the reliability of synchronous acknowledgments is considerably higher than that of asynchronous messages. Thus the norm of estimating link quality bidirectionally via asynchronous beacons underestimates the link reliability of asymmetric links. This leads us to investigate how to exploit asymmetric links in order to improve network functions such as convergecast routing in sensor networks via one-way link estimation. We propose a new one-way link metric ETF (for the expected number of transmissions over forward links ) and present a local procedure for its estimation. We use ETF to identify reliable forward links, and we use dynamic retransmission thresholding for error control. Via experiments on testbeds of CC1000 radios and CC2420 radios (an IEEE 802.15.4-compliant radio), we quantify the performance improvement in ETF as compared with ETX. We also study the performance improvement of ETF over ETX when no special mechanism is employed to discover asymmetric links or to control retransmissions.

In this paper, motivated by the goal of modeling the fine-grain capabilities of jammers for the context of security in low-power wireless networks, we experimentally characterize jamming in networks of CC2420 radio motes and CC1000 radio motes. Our findings include that it is easy to locate J (relative to S and R) and choose its power level so that J can corrupt S's messages with high probability as well as corrupt individual S's bits with nontrivial probability. Internal jammers are however limited in at least two ways: One, it is hard for them to prevent R from detecting that it has received an uncorrupted message from S. And two, the outcome of their corruptions are not only not deterministic, even the probabilities of corrupted outcomes are time-varying. We therefore conclude that it is hard to predict the value resulting from colliding S's messages (bits) with J's messages (bits) and, conversely, to deduce the value sent by S's or J's from the corrupted value received by R.

Link estimation is a basic element of routing in low-power wireless networks, and data-driven link estimation using unicast MAC feedback has been shown to outperform broadcast- beacon based link estimation. Nonetheless, little is known about the impact that different data-driven link estimation methods have on routing behaviors. To address this issue, we classify existing data- driven link estimation methods into two broad categories: L-NT that uses aggregate information about unicast and L-ETX that uses information about the individual unicast-physical transmissions. Through mathematical analysis and experimental measurement in a testbed of 98 XSM motes (an enhanced version of MICA2 motes), we examine the accuracy and stability of L-NT and L-ETX in estimating the ETX routing metric. We also experimentally study the routing performance of L-NT and L-ETX. We discover that these two representative, seemingly similar methods of data-driven link estimation differ significantly in routing behaviors: L-ETX is much more accurate and stable than L-NT in estimating the ETX metric, and, accordingly, L-ETX achieves a higher data delivery reliability and energy efficiency than L-NT (for instance, by 25.18% and a factor of 3.75 respectively in our testbed). These findings provide new insight into the subtle design issues in data-driven link estimation that significantly impact the reliability, stability, and efficiency of wireless routing, thus shedding light on how to design link estimation methods for mission-critical wireless networks which pose stringent requirements on reliability and predictability.

Wireless sensor network (WSN) testbeds are useful because they provide a way to test applications in an environment that makes it easy to deploy experiments, configure them statically or dynamically, and gather performance information. However, WSNs are typically composed of low-cost devices and tend to be unreliable, with failures a common phenomenon. Accurate knowledge of network health status, including nodes and links of each type, is critical for correctly configuring applications on WSN testbeds and for interpreting the data collected from them. In this article we present a stabilizing protocol, Chowkidar, that provides accurate and efficient network health monitoring in WSNs. Our approach adapts the well-known problem of message-passing rooted spanning tree construction and its use in propagation of information with feedback (PIF) for the case of a WSN. The Chowkidar protocol is initiated upon demand; that is, it does not involve ongoing maintenance, and it terminates with accurate results, including detection of failure and restart during the monitoring process. Chowkidar is distinguished from others in two important ways. Given the resource constraints of WSNs, it is message-efficient in that it uses only a few messages per node. Also, it tolerates ongoing node and link failure and node restart, in contrast to requiring that faults stop during convergence. We have implemented the Chowkidar protocol as part of enabling a network health status service that is tightly integrated with a remotely accessible wireless sensor network testbed, Kansei, at The Ohio State University. We present experimental results from this testbed that validate the correctness and performance of Chowkidar. We also report on initial experiences and lessons learnt from the integration of Chowkidar with Kansei, including feedback from both testbed users and administrators who have found Chowkidar to be a useful tool for improving the accuracy and efficiency of testbed experimentation and maintenance, and the need for well-defined policies to address issues such as minimizing interference with concurrently running experiments. Finally, we discuss extensions that enhance the functionality and usability of Chowkidar.

The wireless network community has become increasingly aware of the benefits of data-driven link estimation and routing as compared with beacon-based approaches, but the issue of Biased Link Sampling (BLS) estimation has not been well studied even though it affects routing convergence in the presence of network and environment dynamics. Focusing on traffic-induced dynamics, we examine the open, unexplored question of how serious the BLS issue is and how to effectively address it when the routing metric ETX is used. For a wide range of traffic patterns and network topologies and using both node-oriented and network-wide analysis and experimentation, we discover that the optimal routing structure remains quite stable even though the properties of individual links and routes vary significantly as traffic pattern changes. In cases where the optimal routing structure does change, data-driven link estimation and routing is either guaranteed to converge to the optimal structure or empirically shown to converge to a close-to-optimal structure. These findings provide the foundation for addressing the BLS issue in the presence of traffic-induced dynamics and suggest approaches other than existing ones. These findings also demonstrate that it is possible to maintain an optimal, stable routing structure despite the fact that the properties of individual links and paths vary in response to network dynamics.

In the context of IEEE 802.11b network testbeds, we examine the differences between unicast and broadcast link properties, and we show the inherent difficulties in precisely estimating unicast link properties via those of broadcast beacons even if we make the length and transmission rate of beacons be the same as those of data packets. To circumvent the difficulties in link estimation, we propose to estimate unicast link properties directly via data traffic itself without using periodic beacons. To this end, we design a data-driven routing protocol Learn-on-the-Fly (LOF). LOF chooses routes based on ETX/ETT-type metrics, but the metrics are estimated via MAC feedback for unicast data transmission instead of broadcast beacons. Using a realistic sensor network traffic trace and an 802.11b testbed of ~195 Stargates, we experimentally compare the performance of LOF with that of beacon-based protocols, represented by the geography-unaware ETX and the geography-based PRD. We find that LOF reduces end-to-end MAC latency by a factor of 3, enhances energy efficiency by a factor up to 2.37, and improves network throughput by a factor up to 7.78, which demonstrate the feasibility and the potential benefits of data-driven link estimation and routing.

Distributed observation and control of mobile objects via static wireless sensors demands timely information in a distance-sensitive manner: Information about closer objects is required more often and more quickly than that of farther objects. In this article, we present a wireless sensor network protocol, Trail, that supports distance-sensitive tracking of mobile objects for in-network subscribers upon demand. Trail achieves a find time that is linear in the distance from a subscriber to an object, via a distributed data structure that is updated only locally when the object moves. Notably, Trail does not partition the network into a hierarchy of clusters and clusterheads, and as a result Trail has lower maintenance costs, is more locally fault tolerant, and it better utilizes the network in terms of load balancing and minimizing the size of the data structure needed for tracking. Moreover, Trail is reliable and energy efficient, despite the network dynamics that are typical of wireless sensor networks. Trail can be refined by tuning certain parameters, thereby yielding a family of protocols that are suited for different application settings such as rate of queries, rate of updates, and network size. We evaluate the performance of Trail by analysis, simulations in a 90 × 90 sensor network, and experiments on 105 Mica2 nodes in the context of a pursuer-evader control application.

We focus on decomposition of hard-masking real-time fault-tolerant programs (where safety, timing constraints, and liveness are preserved in the presence of faults) that are designed from their fault-intolerant versions. Towards this end, motivated by the concepts of state predicate detection and state predicate correction, we identify three types of fault-tolerance components, namely, detectors, weak S-correctors, and strong S-correctors. We show that any hard-masking program can be decomposed into its fault-intolerant version plus a collection of detectors, and, weak and strong S-correctors. We argue that such decomposition assists in providing assurance about dependability and time-predictability of embedded systems.

We present DESALalpha, a realization of the dynamic embedded sensor-actuator language for Telos-based devices. The platform provides native support for: (i) rule-based programming; (ii) synchronized action scheduling; (iii) neighborhood management; and (iv) distributed state sharing. We describe the design and implementation of DESALalpha, present examples that illustrate its use, and summarize the resource requirements of compiled applications. Finally, we present lessons learned based on our use of DESALalphaduring the past year.

This paper experimentally investigates the feasibility of crypto-free communications in resource-constrained wireless sensor networks. We exploit the spatial signature induced by the radio communications of a node on its neighboring nodes. We design a primitive that robustly and efficiently realizes this concept, even at the level of individual packets and when the network is relatively sparse. Using this primitive, we design a protocol that robustly and efficiently validates the authenticity of the source of messages: authentic messages incur no communication overhead whereas masqueraded communications are detected cooperatively by the neighboring nodes. The protocol enables lightweight collusion-resistant methods for broadcast authentication, unicast authentication, non-repudiation and integrity of communication. We have implemented our primitive and protocol, and quantified the high-level of accuracy of the protocol via testbed experiments withCC1000radio-enabled motes.

Despite recent theory development, methods of calibration that accurately recover signals from biased sensor readings remain limited in their applicability. Acoustic sensors, for instance, which have been popular in low power wireless sensor networks, are difficult to calibrate in this manner, given their significant hardware variability, large dynamic range, sensitivity to battery power level, and complex spatial/temporal environmental variations. In this paper, we submit that the applicability of calibration is broadened by lifting the calibration problem from the level of sensors to that of sensing applications. We show feasibility of adaptive, easy, and accurate calibration at the level of application-specific features, via an example of recovering the feature of acoustic signal-to-noise ratio (SNR) that is useful in event-detection applications. By easy, we mean there is an efficient, purely local, and stimulus-free procedure for recovering SNR (that compares measured variances for multiple randomly chosen sensitivities, effected via acoustic sensor hardware support); unlike extant calibration methods, the procedure does not need to rely on any synchronization among nodes, long-term correlation between their respective environments, or assumptions about training events. And by accurate, we mean the procedure yields low error in SNR estimation. We provide experimental validation of the difficulty of directly calibrating acoustic signals and the accuracy of our SNR calibration procedure.

Surveillance systems based on wireless sensor network technology have been shown to successfully detect, classify and track evaders over a large area. State information collected via the sensor network also enables these systems to actuate mobile agents so as to achieve surveillance goals, such as target capture and asset protection. But satisfying these goals is complicated by the fact that the track information in a sensor network is routed to mobile agents through multihop wireless communication links and is thus subject to message delays and losses. Stabilization must also be considered in designing pursuer strategies so as to deal with state corruption as well as suboptimal evader strategies. In this article, we formulate optimal pursuit control strategies in the presence of network effects, assuming that target track information has been established locally in the sensor network. We adapt ideas from the theory of differential games to networked games—including ones involving nonperiodic track updates, message losses and message delays—to derive optimal strategies, bounds on the information requirements, and scaling properties of these bounds. We show the inherent stabilization features of our pursuit strategies, both in terms of implementation as well as the strategies themselves.

A substantial percentage of links in wireless networks, especially low-power ones, is asymmetric. For the low-quality direction of asymmetric links, we observe based on testbed experiments that the reliability of synchronous acknowledgments is considerably higher than that of asynchronous messages. Thus the norm of estimating link quality in both directions via asynchronous beacons such as in ETX-based routing potentially underestimates the link reliability of asymmetric links. This leads us to investigate how to exploit asymmetric links in order to improve network functions such as convergecast routing in sensor networks via one-way link estimation. We propose a new one-way link metric ETF (for the expected number of transmissions over forward links) and present a local procedure for its estimation. We use ETF to identify high reliability forward links and use dynamic retransmission thresholding for error control and observe an improvement inconvergecast routing over ETX. This is quantified with experimental testbed results with respect to reliability, number of transmissions per packet, latency, duplicates and average hops. We also study the comparative performance improvement of ETF over ETX when no special mechanism is employed to discover asymmetric links.

We present Sprinkler, a reliable data dissemination service for wireless embedded devices which are constrained in energy, processing speed, and memory. Sprinkler embeds a virtual grid over the network whereby it can locally compute a connected dominating set of the devices to avoid redundant transmissions and a transmission schedule to avoid collisions. Sprinkler transmits O(1) times the optimum number of packets in O(1) of the optimum latency; its time complexity is O(1). Sprinkler is tolerant to fail-stop and state corruption faults. Thus, Sprinkler is suitable for resource-constrained wireless embedded devices. We evaluate the performance of Sprinkler in terms of the number of packet transmissions and the latency, both in an outdoor and indoor environment. The outdoor evaluation is based on data from project ExScal, which deployed 203 extreme scale stargazer (XSS). Our indoor evaluation is based on an implementation in the Kansei testbed, which houses 210 XSSs whose transmission power is controllable to even low ranges. We compare Sprinkler with the existing reliable data dissemination services, analytically or using simulations also. Our evaluations show that Sprinkler is not only energy efficient as compared to existing schemes, but also has less latency. Further, the energy consumption of nodes and the latency grows linearly as a function of newly added nodes as the network grows larger.

Energy efficiency is widely understood to be one of the dominant considerations for wireless sensor networks. Based on historical data and technology trends, the receiver energy consumption will dominate all energy, to the point that for the majority of applications, power management research must focus on receiver efficiency. By modeling several popular MAC layer protocols, we derive bounds on performance for receiver efficiency. In particular, we analyze four abstract models, synchronous blinking (e.g. T- MAC, S-MAC), Long Preamble (e.g. B-MAC), structured time-spreading (also called asynchronous wake-up), and random time spreading. These results strongly suggest that scheduling the receiver so as to minimize (or eliminate) the potential for interference (or collisions) could be from 10 fold to 100 fold more efficient than current practice. We provide two new receiver scheduling methods, staggered on and pseudorandom staggered on, both of which are designed to exploit the untapped opportunity for greater receiver efficiency. Compared with the centralized deterministic scheduling in staggering on, the decentralized scheduling in pseudorandom staggered on achieves only slightly lower energy efficiency. In addition, we design a new MAC protocol, called O-MAC, based upon pseudorandom staggered on that achieves near optimal energy efficiency. Finally, we describe two variations of our O-MAC protocol-with local broadcast channel and preamble-sized slots.

In the context of IEEE 802.11b network testbeds, we examine the differences between unicast and broadcast link properties, and we show the inherent difficulties in precisely estimating unicast link properties via those of broadcast beacons even if we make the length and transmission rate of beacons be the same as those of data packets. To circumvent the difficulties in link estimation, we propose to estimate unicast link properties directly via data traffic itself without using periodic beacons. To this end, we design a data-driven routing protocol Learn on the Fly (LOF). LOF estimates link quality based on data traffic, and it chooses routes by way of a locally measurable metric ELD, the expected MAC latency per unit-distance to the destination. Using a realistic sensor network traffic trace and an 802.11b testbed of 195 Stargates, we experimentally compare the performance of LOF with that of existing protocols, represented by the geography-unaware ETX and the geography-based PRD. We find that LOF reduces endto-end MAC latency by a factor of 3, enhances energy efficiency by a factor up to 2.37, improves route stability by 2 orders of magnitude, and improves network throughput by a factor up to 7.78. The results demonstrate the feasibility as well as potential benefits of data-driven link estimation and routing. Keywords—sensor network, beacon-free geographic routing, data-driven link quality estimation, MAC latency, IEEE 802.11b, real time, energy, reliability

Surveillance systems based on sensor network technology have been shown to successfully detect, classify and track targets of interest over a large area. State information collected via the sensor network also enables these systems to actuate mobile agents so as to achieve surveillance goals such as target capture and asset protection. But satisfying these goals is complicated by the fact that track information in a sensor network is routed to mobile agents through multi-hop communication links and is thus subject to delays and losses. In addition, as the sensor network is scaled in size, high throughput rates for all pursuers cannot be sustained at all times, which necessitates a network communication strategy that adapts to pursuer information requirements.In this paper, we concentrate on the formulation of optimal pursuit control strategies in the presence of network effects, assuming that target track information has been established locally in the sensor network. We adapt ideas from the theory of differential games to networked games --including ones involving non-periodic track updates, message losses and message delays-- to derive optimal strategies, bounds on the information requirements, and scaling properties of these bounds. Moreover, we present a specific network communication protocol which has the required scalable information characteristics and conclude with the results of experimental studies.

Ultrawideband radar-enabled wireless sensor networks have the potential to address key detection and classification requirements common to many surveillance and tracking applications. However, traditional radar signal processing techniques are mismatched with the limited computational and storage resources available on typical sensor nodes. The mismatch is exacerbated in noisy, cluttered environments or when the signals have corrupted spectra. To explore the compatibility of ultrawideband radar and mote-class sensor nodes, we designed and built a new platform called the Radar Mote. An early prototype of this platform was used to detect, classify, and track people and vehicles moving through an outdoor sensor network deployment. This paper describes the sensor's theory of operation, discusses the design and implementation of the Radar Mote, and presents sample signal waveforms of people, vehicles, noise, and clutter. We demonstrate that radar sensors can be successfully integrated with mote-class devices and imbue them with an extraordinarily useful sensing modality.

The Kansei testbed at the Ohio State University is designed to facilitate research on networked sensing applications at scale. Kansei embodies a unique combination of characteristics as a result of its design focus on sensing and scaling: (i) Heterogeneous hardware infrastructure with dedicated node resources for local computation, storage, data exfiltration and back-channel communication, to support complex experimentation, (ii) Time accurate hybrid simulation engine for simulating substantially larger arrays using testbed hardware resources, (iii) High fidelity sensor data generation and real-time data and event injection, (iv) Software components and associated job control language to support complex multi-tier experiments utilizing real hardware resources and data generation and simulation engines. In this paper, we present the elements of Kansei testbed architecture, including its hardware and software platforms as well as its hybrid simulation and sensor data generation engines.

Recents experiments have evaluated the ability of heterogeneous, hierarchical wireless sensor networks to scale to large node numbers and coverage areas. An exemplar is Project ExScal, where we designed and deployed a network of 1000+ sensor nodes and 200+ 802.11b backbone nodes for a 1.3km by 300m remote, open area. In this talk, we overview key issues in the scaling of wireless sensor network operations and applications, based on lessons derived from ExScal and other related experiments. We discuss at some length the impact of the network characteristics on a number of data management problems related to convergecast, broadcast, and in-network data flows. Finally, we identify challenges for future work in this area.

Research in sensor networks has begun to address the use of mobility to improve the reachability of the network, but a number of network principles and application patterns remain to be explored in this context. We propose here a network architecture that uses energy constrained devices for enabling new campus wide applications. Specifically, our demonstration illustrates a new network stack and application framework for a class of locality specific applications. The locality specific nature favors exploiting the limited, slow and regional mobility pattern present in large campuses, as opposed to exclusively exploiting the Internet or the cellular network.

We present a fast, local clustering service, FLOC, that partitions a multihop wireless network into nonoverlapping and approximately equal-sized clusters. Each cluster has a clusterhead such that all nodes within unit distance and some nodes within distance m of the clusterhead belong to the cluster. We show that, by asserting a stretch factor m ges 2, FLOC achieves locality of clustering and fault-local self-stabilization: the effects of cluster formation and faults/changes at any part of the network are contained within at most m + 1 units. Through simulations and experiments with actual deployments, we analyze the trade-offs between clustering time and the quality of clustering and suggest suitable parameters for FLOC to achieve a fast completion time without compromising the quality of the resulting clustering

Recent experiments have taken steps towards realizing the vision of extremely large wireless sensor networks, the largest of these being ExScal, in which we deployed about 1200 nodes over a 1.3 km by 300 m open area. Such experiments remain especially challenging because of: (a) prior observations of failure of sensor network protocols to scale, due to network faults and their spatial and temporal variability, (b) complexity of protocol interaction, (c) lack of sufficient data about faults and variability, even at smaller scales, and (d) current inadequacy of simulation and analytical tools to predict sensor network protocol behavior. In this paper, we present detailed data about faults, both anticipated and unanticipated, in ExScal. We also evaluate the impact of these faults on ExScal as well as the design principles that enabled it to satisfy its application requirements despite these faults. We describe the important lessons learnt from the ExScal experiment and suggest services and tools as a further aid to future large scale network deployments.

We present the design of the extreme scale mote, a new sensor network platform for reliably detecting and classifying, and quickly reporting, rare, random, and ephemeral events in a large-scale, long-lived, and ret askable manner. This new mote was designed for the ExScal project which seeks to demonstrate a 10,000 node network capable of discriminating civilians, soldiers and vehicles, spread out over a 10 km/sup 2/ area, with node lifetimes approaching 1,000 hours of continuous operation on two AA alkaline batteries. This application posed unique functional, usability, scalability, and robustness requirements which could not be met with existing hardware, and therefore motivated the design of a new platform. The detection and classification requirements are met using infrared, magnetic, and acoustic sensors. The infrared and acoustic sensors are designed for low-power continuous operation and include asynchronous processor wakeup circuitry. The usability and scalability requirements are met by minimizing the frequency and cost of human-in-the-loop operations during node deployment, activation, and verification through improvements in the user interface, packaging, and configurability of the platform. Recoverable retasking is addressed by using a grenade timer that periodically forces a system reset. The key contributions of this work are a specific design point and general design methods for building sensor network platforms to detect exceptional events.

Majority of papers in the area of wireless sensor networks (WSNs) have an element of energy-efficiency and associated with it an analysis of network lifetime. Yet, there is no agreement on how to analyze the lifetime of a WSN. As a result, errors are frequently made on both sides. Some underestimate the network lifetime by an order of magnitude, while others end up overestimating the lifetime by a significant factor. This paper presents a first step towards standardizing the lifetime analysis of WSNs. We focus on WSNs deployed for always-on applications, where the problem of power management is most severe because the environment needs to be monitored continuously. Underestimation of network lifetime is common when proposing sleep-wakeup schemes, where it is frequently assumed that in the absence of a sleep-wakeup scheme, a sensor node from the Mica family lasts 3-5 days on a pair of AA batteries. We show that the same sensor node can be made to last more than 36 days, even if it is continuously monitoring the environment. Overestimation typically occurs when proposing non-sleep-wake up power management schemes such as in-network data aggregation. Overestimation occurs because several network activities (e.g periodic routing messages) are assumed to have negligible effect on the network lifetime and therefore are ignored in the lifetime analysis. We use our recent experience in deploying ExScal (a large-scale WSN for intrusion detection) to identify major components in the network lifetime analysis. We then present a careful lifetime analysis of ExScal and show how to analyze the effects of using various non-sleep-wake up power management schemes such as hierarchical sensing, low-power listening, and in-network data aggregation on the network lifetime. Our lifetime analysis will be useful as a template in analyzing the lifetime of other WSNs deployed for always-on applications

In old times, castles were surrounded by moats (deep trenches filled with water, and even alligators) to thwart or discourage intrusion attempts. One can now replace such barriers with stealthy and wireless sensors. In this paper, we develop theoretical foundations for laying barriers of wireless sensors. We define the notion of k-barrier coverage of a belt region using wireless sensors. We propose efficient algorithms using which one can quickly determine, after deploying the sensors, whether a region is k-barrier covered. Next, we establish the optimal deployment pattern to achieve k-barrier coverage when deploying sensors deterministically. Finally, we consider barrier coverage with high probability when sensors are deployed randomly. We introduce two notions of probabilistic barrier coverage in a belt region -- weak and strong barrier coverage. While weak barrier-coverage with high probability guarantees the detection of intruders as they cross a barrier of stealthy sensors, a sensor network providing strong barrier-coverage with high probability (at the expense of more sensors) guarantees the detection of all intruders crossing a barrier of sensors, even when the sensors are not stealthy. Both types of barrier coverage require significantly less number of sensors than full-coverage, where every point in the region needs to be covered. We derive critical conditions for weak k-barrier coverage, using which one can compute the minimum number of sensors needed to provide weak k-barrier coverage with high probability in a given belt region. Deriving critical conditions for strong k-barrier coverage for a belt region is still an open problem.

We address the challenges of bursty convergecast in multi-hop wireless sensor networks, where a large burst of packets from different locations needs to be transported reliably and in real-time to a base station. Via experiments on a 49 MICA2 mote sensor network using a realistic traffic trace, we determine the primary issues in bursty convergecast, and accordingly design a protocol, RBC (for Reliable Bursty Convergecast), to address these issues: To improve channel utilization and to reduce ack-loss, we design a window-less block acknowledgment scheme that guarantees continuous packet forwarding and replicates the acknowledgment for a packet; to alleviate retransmission-incurred channel contention, we introduce differentiated contention control. Moreover, we design mechanisms to handle varying ack-delay and to reduce delay in timer-based re-transmissions. We evaluate RBC, again via experiments, and show that compared to a commonly used implicit-ack scheme, RBC doubles packet delivery ratio and reduces end-to-end delay by an order of magnitude, as a result of which RBC achieves a close-to-optimal goodput.

No abstract available.

Project ExScal (for extreme scale) fielded a 1000+ node wireless sensor network and a 200+ node peer-to-peer ad hoc network of 802.11 devices in a 13km by 300m remote area in Florida, USA during December 2004. In comparison with previous deployments, the ExScal application is relatively complex and its networks are the largest ones of either type fielded to date. In this paper, we overview the key requirements of ExScal, the corresponding design of the hardware/software platform and application, and some results of our experiments.

We present Sprinkler, a reliable data dissemination service for wireless embedded devices which are constrained in energy, processing speed, and memory. Sprinkler embeds a virtual grid over the network whereby it can locally compute a connected dominating set of the devices to avoid redundant transmissions, and a transmission schedule to avoid collisions. Sprinkler transmits O(1) times the optimum number of packets in O(1) of the optimum latency; its time complexity is O(1). Thus, Sprinkler is suitable for resource-constrained wireless embedded devices. We evaluate the performance of Sprinkler in terms of the number of packet transmissions and the latency, both in an outdoor and an indoor environment. Our indoor evaluation is based on an implementation in the Kansei testbed that houses 210 XSSs whose transmission power is controllable to even low ranges. We compare Sprinkler with the existing reliable data dissemination services, analytically or using simulations also. Our evaluations show that Sprinkler is not only energy efficient as compared to existing schemes but also have less latency. Further, the energy consumption of nodes and the latency grows linearly as a function of newly added nodes as network grows larger

The influence field of an object, a commonly exploited feature in science and engineering applications, is the region where the object is detectable by a given sensing modality. Being spatially distributed, this feature allows us to tradeoff nodal computation with network communication. By the same token, not only is its calculation subject to nodal failures and false detections, but also to channel fading and channel contention. In this paper, we study how to accurately and efficiently estimate the influence fields of objects in such an unreliable setting and how this reliable estimation of influence fields can be used to classify and track different types of objects. We derive, for node and network fault models, the necessary nodal density for reliably estimating the influence fields so that objects can be classified and tracked. We present four algorithmic techniques: temporal aggregation, probabilistic reporting, temporal segregation and spatial reconstruction, to deal with cases where the effective network density differs from this minimum. We provide corroboration of our analysis through field experiments with Mica2 sensor nodes wherever appropriate. Finally, we demonstrate how these results and techniques were applied to achieve reliable and efficient classification and tracking in a fielded system of 90 Mica2 sensor nodes that we called "A Line In The Sand'.

We present a fast local clustering service, FLOC, that partitions a multi-hop wireless network into nonoverlapping and approximately equal-sited clusters. Each cluster has a clusterhead such that all nodes within unit distance of the clusterhead belong to the cluster but no node beyond distance m from the clusterhead belongs to the cluster. By asserting m /spl ges/ 2, FLOC achieves locality: effects of cluster formation and faults/changes at any part of the network are contained within most m units. By taking unit distance to be the reliable communication radius and m to be the maximum communication radius, FLOC exploits the double-band nature of wireless radio-model and achieves clustering in constant time regardless of the network size. Through simulations and experiments with actual deployments, we analyze the tradeoffs between clustering time and the quality of clustering, and suggest suitable parameters for FLOC to achieve a fast completion time without compromising the quality of the resulting clustering.

Objections to the practical use of stabilization have centered around problems of scale. Because of potential interferences between actions, global reasoning over the entire system is in general necessary. The complexity of this task increases dramatically as systems grow in size. Alternatives to dealing with this complexity focus on reset and composition. For reset, the problem is that any fault, no matter how minor, will cause a complete system reset with potentially significant lack of availability. For existing compositional alternatives, including compositional reset, severe restrictions on candidate systems are imposed. To address these issues, we give a framework for composition in which global reasoning and detailed system knowledge are not necessary, and which apply to a significantly wider range of systems than has hitherto been possible. We explicitly identify for each component which other components it can corrupt. Additionally, the correction of one component often depends on the prior correction of one or more other components, constraining the order in which correction can take place. Given appropriate component stabilizers such as detectors and correctors, we offer several ways to coordinate system correction, depending on what is actually known about the corruption and correction relations. By reducing the design of and reasoning about stabilization to local activities involving each component and the neighbors with which it interacts, the framework is scalable. Reset is generally avoided by using the correction relation to check and correct only where necessary. By including both correction and corruption relations, the framework subsumes and extends other compositional approaches. Though not directly a part of this work, we mention tools and techniques that can be used to help calculate the dependency and corruption relations and to help create the necessary stabilizers. To illustrate the theory, we show how this framework has been applied in our work in sensor networks.

No abstract available.

This paper shows that the elimination of fault-agnostic instability, the instability caused by fault-agnostic distributed control, substantially improves BGP convergence speed. To this end, we first classify BGP convergence instability into two categories: fault-agnostic instability and distribution-inherent instability; secondly, we prove the impossibility of eliminating all distribution-inherent instability in distributed routing protocols; thirdly, we design the grapevine border gateway protocol (G-BGP) to show that all fault-agnostic instability can be eliminated. G-BGP eliminates all fault-agnostic instability under different fault and routing policy scenarios by (i) piggybacking onto BGP UPDATE messages fine-grained information about faults to the nodes affected by the faults, (ii) quickly resolving the uncertainty between link and node failure as well as the uncertainty of whether a node has changed route, and (iii) rejecting obsolete fault information. We have evaluated G-BGP by both analysis and simulation. Analytically, we prove that, by eliminating fault-agnostic instability, G-BGP achieves optimal convergence speed in several scenarios where BGP convergence is severely delayed (e.g., when a node or a link fail-stops), and when the shortest-path-first policy is used, G-BGP asymptotically improves BGP convergence speed except in scenarios where BGP convergence speed is already optimal (e.g., when a node or a link joins). By simulating networks with up to 115 autonomous systems, we observe that G-BGP improves BGP convergence stability and speed by an order of magnitude.

Methods for mechanically synthesizing concurrent programs from temporal logic specifications obviate the need to manually construct a program and compose a proof of its correctness. A serious drawback of extant synthesis methods, however, is that they produce concurrent programs for models of computation that are often unrealistic. In particular, these methods assume completely fault-free operation, that is, the programs they produce are fault-intolerant. In this paper, we show how to mechanically synthesize fault-tolerant concurrent programs for various fault classes. We illustrate our method by synthesizing fault-tolerant solutions to the mutual exclusion and barrier synchronization problems.

We formulate a notion of local stabilization, by which a system self-stabilizes in time proportional to the size of any perturbation that changes the network topology or the state of nodes. The notion implies that the part of the network involved in the includes at most the nodes whose distance from the perturbed nodes is proportional to the perturbation size. Also, we present LSRP, a protocol for local in shortest path routing. LSRP achieves local via two techniques. First, it layers system computation into three diffusing waves each having a different propagation speed, i.e., stabilization with the lowest speed, with intermediate speed, and with the highest speed. The containment wave contains the mistakenly initiated wave, the super-containment wave contains the mistakenly initiated containment wave, and the super-containment wave self-stabilizes itself locally. Second, LSRP avoids forming loops during stabilization, and it removes all transient loops within small constant time. To the best of our knowledge, LSRP is the first protocol that achieves local in shortest path routing.

An attractive architecture for sensor networks is to have the sensing devices mounted on small computers, called motes. Motes are battery-powered, and can communicate in a wireless fashion by broadcasting messages over radio frequency. In mote networks, the connectivity of a mote u can be defined by those motes that can receive messages from u with high probability and those motes from which u can receive messages with high probability. In this paper, we describe a protocol that can be triggered by any mote in a mote network in order that each mote in the network computes its connectivity. The protocol is simple and has several energy saving features. We implemented this protocol over TinyOS and discuss the results of some execution runs of this implementation.

Bluetooth is a radio interface standard used to build a personal area ad-hoc network(PAN) by interconnecting mobile electronics devices. In PAN, different applications and protocols place different QoS demands on the link. To meet these requirements properly, Bluetooth specification provides quality of service(QoS) configuration. In particular, Bluetooth LMP commands are used to configure the poll interval to provide QoS service to the higher layer. However, a method to provide QoS in scatternet is absent in the specification. Moreover, in scatternet, the schedule exerts a direct influence on the basic QoS properties like bandwidth, delay and jitter. We present two versions of QoS-aware scheduling algorithms: a perfect assignment algorithm for bipartite scatternet and a distributed, local algorithm. Also, both algorithms are shown to be perfect over tree scatternet. Finally, we present the performance and QoS evaluation. It is shown that the delay and jitter of the schedule generated by the algorithms have tight bounds.

Abstract Multicast/broadcast is an important service primitive in networks. It is supported by all IEEE 802.x standards, including 802.11. The IEEE 802.11 multicast/broadcast protocol is based on the basic access procedure of Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA). This protocol does not provide any media access control (MAC) layer recovery on multicast/broadcast frames. As a result, the reliability of the multicast/broadcast service is reduced owing to the increased probability of lost frames resulting from interference or collisions. Recently, a few MAC protocols have been proposed to enhance the reliability and the efficiency of the 802.11 multicast/broadcast protocol. In this paper, we observe that these protocols are still unreliable or inefficient. To redress the problems of reliability and efficiency, we propose a reliable Batch Mode Multicast MAC protocol (BMMM), which in most cases reduces the number of contention phases fromnto 1, wherenis the number of intended receivers in the multicast/broadcast. This considerably reduces the time required for a multicast/broadcast. We then propose a Location Aware Multicast MAC protocol (LAMM), which uses station location information to further improve upon BMMM. Extensive analysis and simulation results validate the reliability and efficiency of our multicast MAC protocols. Copyright © 2003 John Wiley & Sons, Ltd.

Refinement tools such as compilers do not necessarily preserve fault-tolerance. That is, given a fault-tolerant program in a high-level language as input, the output of a compiler in a lower-level language will not necessarily be fault-tolerant. We identify a type of refinement, namely "convergence refinement", that preserves the fault-tolerance property of stabilization. We illustrate the use of convergence refinement by presenting the first formal design of Dijkstra's little-understood 3-state stabilizing token-ring system. Our designs begin with simple, abstract token-ring systems that are not stabilizing, and then add an abstract "wrapper" to the systems so as to achieve stabilization. The system and the wrapper are then refined to obtain a concrete token-ring system, while preserving stabilization. In fact, the two are refined independently, which demonstrates that convergence refinement is amenable for "graybox" design of stabilizing implementations, i.e., design of system stabilization based solely on system specification and without knowledge of system implementation details.

We present a solution to the problem of dining philosophers. Our solution tolerates malicious crashes. In a malicious crash the failed process behaves arbitrarily for a finite time and then ceases all operation undetectably to other processes. The tolerance of our solution is achieved by the combination of stabilization and crash failure locality. Stabilization allows our program to recover from an arbitrary state. Crash failure locality ensures that only a limited number of processes are affected by a process crash. The crash failure locality of our solution is optimal. Finally, we argue that the malicious crash fault model and its extensions are worthy of further study as they admit tolerances that are not achieved under stronger fault models and are unnecessary under weaker fault models.

Multicast/broadcast is an important service primitive in networks. The IEEE 802.11 multicast/broadcast protocol is based on the basic access procedure of Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA). This protocol does not provide any media access control (MAC) layer recovery on multicast/broadcast frames. As a result, the reliability of the multicast/broadcast service is reduced due to the increased probability of lost frames resulting from interference or collisions. In this paper, we propose a reliable Batch Mode Multicast MAC protocol, BMMM, which substentially reduces the number of contention phases, thus considerably reduces the time required for a multicast/broadcast. We then propose a Location Aware Multicast MAC protocol, LAMM, that uses station location information to further improve upon BMMM. Extensive analysis and simulation results validate the reliability and efficiency of our multicast MAC protocols. 1

We present GS3, a distributed, scalable, self-configuration and self-healing algorithm for multi-hop wireless networks. The algorithm enables network nodes in a 2D plane to configure themselves into a cellular hexagonal structure such that cells have tightly bounded geographic radius and low overlap between neighboring cells. The structure is self-healing under various perturbations, such as node joins, leaves, deaths, movements, and state corruptions. For instance, it slides as a whole if nodes in many cells die at the same rate. Moreover, its configuration and healing are scalable in three respects: first, local knowledge enables each node to maintain only limited information with respect to a constant number of nearby nodes; second, local healing guarantees that all perturbations are contained within a tightly bounded region with respect to the perturbed area and dealt with in a one-way message diffusion time across the region; third, only local coordination is needed in both configuration and self-healing.

An ideal approach to deal with faults in large-scale distributed systems is to contain the effects of faults as locally as possible and, additionally, to ensure some type of tolerance within each fault-affected locality. Existing results using this approach accommodate only limited faults (such as crashes) or assume that fault occurrence is bounded in space and/or time. In this paper, we define and explore possibility/impossibility of local tolerance with respect to arbitrary faults (such as Byzantine faults) whose occurrence may be unbounded in space and in time. Our positive results include programs for graph coloring and dining philosophers, with proofs that the size of their tolerance locality is optimal. The type of tolerance achieved within fault-affected localities is self-stabilization. That is, starting from an arbitrary state of the distributed system, each non-faulty process eventually reaches a state from where it behaves correctly as long as the only faults that occur henceforth (regardless of their number) are outside the locality of this process.

Research in system stabilization has traditionally relied on the availability of a complete system implementation. As such, it would appear that the scalability and reusability of stabilization is limited in practice. Towards redressing this perception, the authors show for the first time that system stabilization may be designed knowing only the system specification but not the system implementation. We refer to stabilization designed thus as being "graybox" and identify "local everywhere-eventually specifications" as being amenable to design of graybox stabilization. We illustrate the design of graybox stabilization using timestamp-based distributed mutual exclusion as our example.

We dispel the myth that it is impossible for any stabilizing message passing program to be terminating. We identify fixpoint-symmetry as a necessary condition for a message passing stabilizing program to be terminating. Our results do confirm that a number of well-known input-output problems (e.g., leader election and consensus) do not admit a terminating and stabilizing solution. On the flip side, they show that reactive problems such as mutual exclusion and reliable-transmission do admit such solutions. We go on to present stabilizing and terminating programs for both problems. Also, we describe a way to add termination to a stabilizing program, and demonstrate it in the context of our design of a solution to the reliable-transmission problem.

We present a polynomial time algorithm for automatic synthesis of fault-tolerant distributed programs, starting from fault-intolerant versions of those programs. Since this synthesis problem is known to be NP-hard, our algorithm relies on heuristics to reduce the complexity. We demonstrate that our algorithm is able to synthesize an agreement program that tolerates a Byzantine fault.

As the success of the Web increasingly brings us towards a fully connected world, home networking systems that connect and manage home appliances become the natural next step to complete the connectivity. Although there has been fast-growing interest in the design of smart appliances and environments, there has been little study on the dependability issues, which is essential to making home networking part of our daily lives. The heterogeneity of various in-home networks, the undependable nature of consumer devices, and the lack of knowledgeable system administrators in the home environment introduce both opportunities and challenges for dependability research. We report the dependability problems we encountered and the solutions we adopted in the deployment of the Aladdin home networking system. We propose the use of a soft-state store as a shared heartbeat infrastructure for monitoring the health of diverse hardware and software entities. We also describe a system architecture for connecting powerline devices to enhance dependability, and a monitoring tool for detecting unusual powerline activities potentially generated by intruders, interferences, or ill-behaved devices.

Vector clocks (VC) are an inherent component of a rich class of distributed applications. In this paper, we consider the problem of realistic —more specifically, bounded-space and fault-tolerant— implementation of these client applications. To this end, we generalize the notion of VC to resettable vector clocks (RVC), and provide a realistic implementation of RVC. Further, we identify an interface contract under which our RVC implementation can be substituted for VC in client applications, without affecting the client's correctness. Based on such substitution, we show how to transform the client so that it is itself realistically implemented; we demonstrate our method in the context of Ricart-Agrawala's mutual exclusion program.

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.

We show how fault-tolerance can be effectively added to several types of faults in program computations that use barrier synchronization. We divide the faults that occur in practice into two classes, detectable and undetectable, and design a fully distributed program that tolerates the faults in both classes. Our program guarantees that every barrier is executed correctly even if detectable faults occur, and that eventually every barrier is executed correctly even if undetectable faults occur. Via analytical as well as simulation results we show that the cost of adding fault-tolerance is low, in part by comparing the times required by our program with that required by the corresponding fault-intolerant counterpart.

Methods for mechanically synthesizing concurrent programs from temporal logic specificationsobviate the need to manually construct a program and compose a proof of its correctness. A seriousdrawback of extant synthesis methods, however, is that they produce concurrent programs formodels of computation that are often unrealistic. In particular, these methods assume completelyfault-free operation, that is, the programs they produce are fault-intolerant. In this paper, we showhow to mechanically synthesize fault-tolerant concurrent programs for various fault classes. Weillustrate our method by synthesizing fault-tolerant solutions to the mutual exclusion and barriersynchronization problems.Categories and Subject Descriptors: C.2.4 [

The concept of multitolerance abstracts problems in system dependability and provides a basis for improved design of dependable systems. In the abstraction, each source of undependability in the system is represented as a class of faults, and the corresponding ability of the system to deal with that undependability source is represented as a type of tolerance. Multitolerance thus refers to the ability of the system to tolerate multiple fault classes, each in a possibly different way. We present a component based method for designing multitolerance. Two types of components are employed by the method, namely detectors and correctors. A theory of detectors, correctors, and their interference free composition with intolerant programs is developed, which enables stepwise addition of components to provide tolerance to a new fault class while preserving the tolerances to the previously added fault classes. We illustrate the method by designing a fully distributed multitolerant program for a token ring.

Masking fault-tolerance guarantees that programs continually satisfy their specification in the presence of faults. By way of contrast, nonmasking fault-tolerance does not guarantee as much: it merely guarantees that when faults stop occurring, program executions converge to states from where programs continually (re)satisfy their specification. We present in this paper a component based method for the design of masking fault-tolerant programs. In this method, components are added to a fault-intolerant program in a stepwise manner, first, to transform the fault-intolerant program into a nonmasking fault-tolerant one and, then, to enhance the fault-tolerance from nonmasking to masking. We illustrate the method by designing programs for agreement in the presence of Byzantine faults, data transfer in the presence of message loss, triple modular redundancy in the presence of input corruption, and mutual exclusion in the presence of process fail-stops. These examples also serve to demonstrate that the method accommodates a variety of fault-classes. It provides alternative designs for programs usually designed with extant design methods, and it offers the potential for improved masking fault-tolerant programs.

OFMP is a hierarchical, network management protocol that enables group operations to be executed on the management information bases of all nodes in the group. As long as no faults occur, OFMP ensures that all nodes execute their local operation exactly once in each group operation. If "immediately-detectable" faults occur, it ensures masking fault-tolerance; i.e., all non-failed nodes execute their local operation exactly once in each group operation. And, if "eventually-detectable" faults occur, it ensures stabilizing fault-tolerance; i.e., it eventually converges to a state from where all non-failed nodes execute their local operation exactly once in each subsequent group operation. Of special note is the ability of OFMP to detect using only a bounded amount of memory whether nodes have executed in same group operation, in a manner that masks immediately-detectable faults and stabilizes from eventually-detectable faults.

The paradigm of information exchange provides a basis for nodes in a network to stay up-to-date with the recent information in the network. In this paradigm, nodes cooperate with each other to share their current information. We present a simple and uniform schema for building information exchange protocols that are stabilizing, in the following strong sense. Starting from arbitrary state, the protocols reach within bounded real-time a state from where all nodes remain up-to-date with recent information in the network. The ability to stabilize in bounded time is achieved by using timing-based actions. The timing constraints on these actions can be systematically adapted to suit a variety of network loads, delay requirements, and scheduling restrictions and to tolerate out-of-phase and drift-prone node clocks. Our schema also tolerates any number of topological changes in the network. Moreover, it accommodates information that is time-varying as well as it does information that is fixed. It is thus well-suited to dynamic high speed networks.

Masking fault-tolerance guarantees that programs continually satisfy their specification in the presence of faults. By way of contrast, nonmasking fault-tolerance does not guarantee as much: it merely guarantees that when faults stop occurring, program executions converge to states from where programs continually (re)satisfy their specification. In this paper, we show that a practical method to design masking fault-tolerance is to first design nonmasking fault-tolerance and to then transform the nonmasking fault-tolerant program minimally so as to achieve masking fault-tolerance. We demonstrate this method by designing novel fully distributed programs for termination detection, mutual exclusion, and leader election, that are masking tolerant of any finite number of process fail-stops and/or repairs.

We present a method for the design of nonmasking fault-tolerant programs. In our method, a set of constraints is associated with each program. Each of these constraints is continually satisfied under the execution of program actions, as long as faults do not occur. Whenever some of the constraints are violated, due to certain faults, all constraints are eventually reestablished by subsequent execution of the program actions. To design programs thus, two types of program actions are distinguished: "closure" actions and "convergence" actions. Closure actions are the actions that perform the intended computation of the program when all of the constraints are satisfied. Convergence actions are the actions that reestablish the constraints when they have been violated. Sufficient conditions for the validation of closure and convergence actions are formalized in terms of a "constraint graph". These conditions are illustrated by designing nonmasking fault-tolerant programs for diffusing computations, atomic actions, and token rings.>

We design two protocols that maintain the nodes of any computer network in a rooted spanning tree and in a unidirectional ring, respectively, in the presence of any finite number of fail-stop failures and repairs of network nodes and communication channels. Our protocols are fully distributed, have optimal time and space complexity, and illustrate two different methods for the design of nonmasking fault-tolerant protocols.>

A reset subsystem is designed that can be embedded in an arbitrary distributed system in order to allow the system processes to reset the system when necessary. Our design is layered, and comprises three main components: a leader election, a spanning tree construction, and a diffusing computation. Each of these components is self-stabilizing in the following sense: if the coordination between the up-processes in the system is ever lost (due to failures or repairs of processes and channels), then each component eventually reaches a state where coordination is regained. This capability makes our reset subsystem very robust: it can tolerate fail-stop failures and repairs of processes and channels, even when a reset is in progress.>

The authors formally define what it means for a system to tolerate a class of faults. The definition consists of two conditions. The first is that if a fault occurs when the system state is within the set of legal states, the resulting state is within some larger set and, if faults continue to occur, the system state remains within that larger set (closure). The second is that if faults stop occurring, the system eventually reaches a state within the legal set (convergence). The applicability of the definition for specifying and verifying the fault-tolerance properties of a variety of digital and computer systems is demonstrated. Using the definition, the authors obtain a simple classification of fault-tolerant systems. Methods for the systematic design of such systems are discussed.>