Emergency Medical Services (EMS) are critical to patient survival in emergencies, but first responders often face intense cognitive demands in high-stakes situations. AI cognitive assistants, acting as virtual partners, have the potential to ease this burden by supporting real-time data collection and decision making. In pursuit of this vision, we introduce EgoEMS, the first end-to-end, high-fidelity, multimodal, multiperson dataset capturing over 20 hours of realistic, procedural EMS activities from an egocentric view in 233 simulated emergency scenarios performed by 62 participants, including 46 EMS professionals. Developed in collaboration with EMS experts and aligned with national standards, EgoEMS is captured using an open-source, low-cost, and replicable data collection system and is annotated with keysteps, timestamped audio transcripts with speaker diarization, action quality metrics, and bounding boxes with segmentation masks. Emphasizing realism, the dataset includes responder-patient interactions reflecting real-world emergency dynamics. We also present a suite of benchmarks for real-time multimodal keystep recognition and action quality estimation, essential for developing AI support tools for EMS. We hope EgoEMS inspires the research community to push the boundaries of intelligent EMS systems and ultimately contribute to improved patient outcomes.

Multi-label text classification (MLTC) tasks in the medical domain often face the longtail label distribution problem.Prior works have explored hierarchical label structures to find relevant information for few-shot classes, but mostly neglected to incorporate external knowledge from medical guidelines.This paper presents DKEC, Domain Knowledge Enhanced Classification for diagnosis prediction with two innovations: (1) automated construction of heterogeneous knowledge graphs from external sources to capture semantic relations among diverse medical entities, (2) incorporating the heterogeneous knowledge graphs in few-shot classification using a label-wise attention mechanism.We construct DKEC using three online medical knowledge sources and evaluate it on a real-world Emergency Medical Services (EMS) dataset and a public electronic health record (EHR) dataset.Results show that DKEC outperforms the state-of-the-art labelwise attention networks and transformer models of different sizes, particularly for the fewshot classes.More importantly, it helps the smaller language models achieve comparable performance to large language models.

Monocular depth estimation is an important step in many downstream tasks in machine vision. We address the topic of estimating monocular depth from defocus blur which can yield more accurate results than the semantic based depth estimation methods. The existing monocular depth from defocus techniques are sensitive to the particular camera that the images are taken from. We show how several camera-related parameters affect the defocus blur using optical physics equations and how they make the defocus blur depend on these parameters. The simple correction procedure we propose can alleviate this problem which does not require any retraining of the original model. We created a synthetic dataset which can be used to test the camera independent performance of depth from defocus blur models. We evaluate our model on both synthetic and real datasets (DDFF12 and NYU depth V2) obtained with different cameras and show that our methods are significantly more robust to the changes of cameras. Code: https://github.com/sleekEagle/defocus_camind.git

Emergency Medical Services (EMS) providers use their hands extensively for the rescue operation and providing care to the patients in an EMS scene. Using smartwatch based sensor data, i.e., accelerometer, gyroscope, and magnetometer, we are developing SenseEMS, a system for hand operated EMS intervention detection and real-time monitoring. SenseEMS will use a hybrid deep neural network with appropriate real-time algorithms on the sensor data to detect multiple hand operated activities, i.e. CPR compressions, attaching defibrillation pads and breathing bags, and to provide quality assessment on different metrics of the activity, i.e., the rate and depth of CPR compressions. Our initial results for this ongoing research show promising accuracy. Preliminary survey with 31 anonymous EMS responders suggests that this automated system will be highly beneficial for real-scene application and EMS training.

In smart computing, the labels of training samples for a specific task are not always abundant. However, the labels of samples in a relevant but different dataset are available. As a result, researchers have relied on unsupervised domain adaptation to leverage the labels in a dataset (the source domain) to perform better classification in a different, unlabeled dataset (target domain). Existing non-generative adversarial solutions for UDA aim at achieving domain confusion through adversarial training. The ideal scenario is that perfect domain confusion is achieved, but this is not guaranteed to be true. To further enforce domain confusion on top of the adversarial training, we propose a novel UDA algorithm, E-ADDA, which uses both a novel variation of the Mahalanobis distance loss and an out-of-distribution detection subroutine. The Mahalanobis distance loss minimizes the distribution-wise distance between the encoded target samples and the distribution of the source domain, thus enforcing additional domain confusion on top of adversarial training. Then, the OOD subroutine further eliminates samples on which the domain confusion is unsuccessful. We have performed extensive and comprehensive evaluations of E-ADDA in the acoustic and computer vision modalities. In the acoustic modality, E-ADDA outperforms several state-of-the-art UDA algorithms by up to 29.8%, measured in the f1 score. In the computer vision modality, the evaluation results suggest that we achieve new state-of-the-art performance on popular UDA benchmarks such as Office-31 and Office-Home, outperforming the second best-performing algorithms by up to 17.9%.

Wearable devices like smartwatches and smart wristbands have gained substantial popularity in recent years. However, their small interfaces create inconvenience and limit computing functionality. To fill this gap, we propose ViWatch, which enables robust finger interactions under deployment variations, and relies on a single IMU sensor that is ubiquitous in COTS smartwatches. To this end, we design an unsupervised Siamese adversarial learning method. We built a real-time system on commodity smartwatches and tested it with over one hundred volunteers. Results show that the system accuracy is about 97% over a week. In addition, it is resistant to deployment variations such as different hand shapes, finger activity strengths, and smartwatch positions on the wrist. We also developed a number of mobile applications using our interactive system and conducted a user study where all participants preferred our un-supervised approach to supervised calibration. The demonstration of ViWatch is shown at https://youtu.be/N5-ggvy2qfI.

Electric vehicles (EVs) are being rapidly adopted due to their economic and societal benefits. Autonomous mobility-on-demand (AMoD) systems also embrace this trend. However, the long charging time and high recharging frequency of EVs pose challenges to efficiently managing EV AMoD systems. The complicated dynamic charging and mobility process of EV AMoD systems makes the demand and supply uncertainties significant when designing vehicle balancing algorithms. In this work, we design a data-driven distributionally robust optimization (DRO) approach to balance EVs for both the mobility service and the charging process. The optimization goal is to minimize the worst-case expected cost under both passenger mobility demand uncertainties and EV supply uncertainties. We then propose a novel distributional uncertainty sets construction algorithm that guarantees the produced parameters are contained in desired confidence regions with a given probability. To solve the proposed DRO AMoD EV balancing problem, we derive an equivalent computationally tractable convex optimization problem. Based on real-world EV data of a taxi system, we show that with our solution the average total balancing cost is reduced by 14.49%, and the average mobility fairness and charging fairness are improved by 15.78% and 34.51%, respectively, compared to solutions that do not consider uncertainties.

With the rapid development of cities, heterogeneous urban cyber-physical systems are designed to improve citizens’ experience, e.g., navigation and delivery service. However, the integration of services is not designed for disruptive events, an oversight that has rippling effects on service quality. For example, urban transportation systems consist of multiple transport modes that have complementary characteristics of capacities, speeds, and costs, facilitating smooth passenger transfers by planned schedules. Such integration may experience significantly increased delays during disruptions. Current solutions rely on a substitute service to transport passengers from and to affected areas using ad-hoc schedules and static routes, which are inefficient and do not utilize mobility patterns of mobile systems, e.g., dynamic passenger demand. To coordinate heterogeneous transportation systems under disruptions, we design a service to automatically select and integrate part of three systems (subway, bus, and taxi) using systems’ mobility patterns, e.g., predicted supply and demand. The service is presented in a normal version, eRoute, considering both subway and bus, and in a version taking taxis into account, called enhanced eRoute. We implement and evaluate eRoute with datasets including subway, bus and taxi, and a fare collection system. The data-driven evaluation results show that eRoute improves the ratio of served passengers per time interval by up to 11.5 times and reduces the average traveling time by up to 82.1 percent compared with existing solutions.

An increasing number of monitoring systems have been developed in smart cities to ensure that a city's real-time operations satisfy safety and performance requirements. However, many existing city requirements are written in English with missing, inaccurate, or ambiguous information. There is a high demand for assisting city policy makers in converting human-specified requirements to machine-understandable formal specifications for monitoring systems. To tackle this limitation, we build CitySpec, the first intelligent assistant system for requirement specification in smart cities. To create CitySpec, we first collect over 1,500 real-world city requirements across different domains from over 100 cities and extract city-specific knowledge to generate a dataset of city vocabulary with 3,061 words. We also build a translation model and enhance it through requirement synthesis and develop a novel online learning framework with validation under uncertainty. The evaluation results on real-world city requirements show that CitySpec increases the sentence-level accuracy of requirement specification from 59.02 % to 86.64 %, and has strong adaptability to a new city and a new domain (e.g., F1 score for requirements in Seattle increases from 77.6 % to 93.75% with online learning).

As more and more monitoring systems have been deployed to smart cities, there comes a higher demand for converting new human-specified requirements to machine-understandable formal specifications automatically. However, these human-specific requirements are often written in English and bring missing, inaccurate, or ambiguous information. In this paper, we present City Spec [1], an intelligent assistant system for requirement specification in smart cities. CitySpec not only helps overcome the language differences brought by English requirements and formal specifications, but also offers solutions to those missing, inaccurate, or ambiguous information. The goal of this paper is to demonstrate how CitySpec works. Specifically, we present three demos: (1) interactive completion of requirements in CitySpec; (2) human-in-the-loop correction while CitySepc encounters exceptions; (3) online learning in CitySpec.

The rapid development of machine learning on acoustic signal processing has resulted in many solutions for detecting emotions from speech. Early works were developed for clean and acted speech and for a fixed set of emotions. Importantly, the datasets and solutions assumed that a person only exhibited one of these emotions. More recent work has continually been adding realism to emotion detection by considering issues such as reverberation, de-amplification, and background noise, but often considering one dataset at a time, and also assuming all emotions are accounted for in the model. We significantly improve realistic considerations for emotion detection by (i) more comprehensively assessing different situations by combining the five common publicly available datasets as one and enhancing the new dataset with data augmentation that considers reverberation and de-amplification, (ii) incorporating 11 typical home noises into the acoustics, and (iii) considering that in real situations a person may be exhibiting many emotions that are not currently of interest and they should not have to fit into a pre-fixed category nor be improperly labeled. Our novel solution combines CNN with out-of-data distribution detection. Our solution increases the situations where emotions can be effectively detected and outperforms a state-of-the-art baseline.

As various smart services are increasingly deployed in modern cities, many unexpected conflicts arise due to various physical world couplings. Existing solutions for conflict resolution often rely on centralized control to enforce predetermined and fixed priorities of different services, which is challenging due to the inconsistent and private objectives of the services. Also, the centralized solutions miss opportunities to more effectively resolve conflicts according to their spatiotemporal locality of the conflicts. To address this issue, we design a decentralized negotiation and conflict resolution framework named DeResolver, which allows services to resolve conflicts by communicating and negotiating with each other to reach a Pareto-optimal agreement autonomously and efficiently. Our design features a two-step self-supervised learning-based algorithm to predict acceptable proposals and their rankings of each opponent through the negotiation. Our design is evaluated with a smart city case study of three services: intelligent traffic light control, pedestrian service, and environmental control. In this case study, a data-driven evaluation is conducted using a large dataset consisting of the GPS locations of 246 surveillance cameras and an automatic traffic monitoring system with more than 3 million records per day to extract real-world vehicle routes. The evaluation results show that our solution achieves much more balanced results, i.e., only increasing the average waiting time of vehicles, the measurement metric of intelligent traffic light control service, by 6.8% while reducing the weighted sum of air pollutant emission, measured for environment control service, by 12.1%, and the pedestrian waiting time, the measurement metric of pedestrian service, by 33.1%, compared to priority-based solution.

Data collection is a major hurdle faced by the researchers, particularly in the field of wearable computing, as it requires significant amount of time and manual effort. Although wearable devices such as, smartwatches have sophisticated sensing capabilities today and are being popularly used by CPS researchers, collecting data from the sensors embedded on the smartwatch remains a challenging job. The fundamental limitation of the smartwatches is the small form factor, which makes it difficult for the user to input any data collection preferences or labels for the data collection. The existing apps/systems that takes such inputs manually from the user are therefore ineffective for the smartwatches. In this paper, we present the idea of using voice interaction capabilities of a smartwatch for conveniently collecting and labeling sensor data from the available sensing modalities. We present VoiSense, a voice interactive smartwatch based system which intelligently gathers the user preferences and data labels with voice interaction and facilitates convenient data collection without requiring any expertise or significant manual effort.

With the rapid development of the Internet of Things (IoT), there are billions of interacting devices and applications. With so many devices and applications, one of the most critical challenges is how to provide security. Traditional software-based defenses will not be enough to protect the security of IoT because of the attack surfaces derived from the physical environment. For example, an attacker can physically re-point a surveillance camera, can move a smart device to another location, can send a sound signal to influence an accelerometer, can cause wireless jamming, etc. We propose to create "smart buttons," and collections of them called "smart blankets" as hardware/software (HW/SW) security patches rather than software-only patches. These fixes operate similarly to software patches, but because of the hardware added, these new patches can better support against physical world attacks. While this paper primarily presents a vision for HW/SW patches, solutions are implemented and shown for two classes of attacks involving cameras and robots. Open questions are also discussed.

With the development of the Internet of Things, millions of sensors are being deployed in cities to collect real-time data. This leads to a need for checking city states against city requirements at runtime. In this article, we develop a novel spatial-temporal specification-based monitoring system for smart cities. We first describe a study of over 1000 smart city requirements, some of which cannot be specified using the existing logic, such as the signal temporal logic (STL) and its variants. To tackle this limitation, we develop spatial aggregation STL (SaSTL)-a novel spatial aggregation STL-for the efficient runtime monitoring of safety and performance requirements in smart cities. We develop two new logical operators in SaSTL to augment STL for expressing spatial aggregation and spatial counting characteristics that are commonly found in real city requirements. We define the Boolean and quantitative semantics for SaSTL in support of the analysis of city performance across different periods and locations. We also develop efficient monitoring algorithms that can check the SaSTL requirement in parallel over multiple data streams (e.g., generated by multiple sensors distributed spatially in a city). Additionally, we build an SaSTL-based monitoring tool to support decision making of different stakeholders to specify and runtime monitor their requirements in smart cities. We evaluate our SaSTL monitor by applying it to three case studies with large-scale real city sensing data (e.g., up to 10 000 sensors in one study). The results show that SaSTL has a much higher coverage expressiveness than other spatial-temporal logics, and with a significant reduction of computation time for monitoring requirements. We also demonstrate that the SaSTL monitor improves the safety and performance of smart cities via simulated experiments.

With the transformation to smarter cities and the development of technologies, a large amount of data is collected from sensors in real time. Services provided by ride-sharing systems such as taxis, mobility-on-demand autonomous vehicles, and bike sharing systems are popular. This paradigm provides opportunities for improving transportation systems’ performance by allocating ride-sharing vehicles toward predicted demand proactively. However, how to deal with uncertainties in the predicted demand probability distribution for improving the average system performance is still a challenging and unsolved task. Considering this problem, in this work, we develop a data-driven distributionally robust vehicle balancing method to minimize the worst-case expected cost. We design efficient algorithms for constructing uncertainty sets of demand probability distributions for different prediction methods and leverage a quad-tree dynamic region partition method for better capturing the dynamic spatial-temporal properties of the uncertain demand. We then derive an equivalent computationally tractable form for numerically solving the distributionally robust problem. We evaluate the performance of the data-driven vehicle balancing algorithm under different demand prediction and region partition methods based on four years of taxi trip data for New York City (NYC). We show that the average total idle driving distance is reduced by 30% with the distributionally robust vehicle balancing method using quad-tree dynamic region partitions, compared with vehicle balancing methods based on static region partitions without considering demand uncertainties. This is about a 60-million-mile or a 8-million-dollar cost reduction annually in NYC.

Predictive monitoring—making predictions about future states and monitoring if the predicted states satisfy requirements—offers a promising paradigm in supporting the decision making of Cyber-Physical Systems (CPS). Existing works of predictive monitoring mostly focus on monitoring individual predictions rather than sequential predictions. We develop a novel approach for monitoring sequential predictions generated from Bayesian Recurrent Neural Networks (RNNs) that can capture the inherent uncertainty in CPS, drawing on insights from our study of real-world CPS datasets. We propose a new logic named Signal Temporal Logic with Uncertainty (STL-U) to monitor a flowpipe containing an infinite set of uncertain sequences predicted by Bayesian RNNs. We define STL-U strong and weak satisfaction semantics based on whether all or some sequences contained in a flowpipe satisfy the requirement. We also develop methods to compute the range of confidence levels under which a flowpipe is guaranteed to strongly (weakly) satisfy an STL-U formula. Furthermore, we develop novel criteria that leverage STL-U monitoring results to calibrate the uncertainty estimation in Bayesian RNNs. Finally, we evaluate the proposed approach via experiments with real-world CPS datasets and a simulated smart city case study, which show very encouraging results of STL-U based predictive monitoring approach outperforming baselines.

Recent years have witnessed the design and development of several smart devices that are wireless and battery-less. These devices exploit RFID backscattering-based computation and transmissions. Although singular devices can operate efficiently, their coexistence needs to be controlled, as they have widely varying communication requirements, depending on their interaction with the environment. The design of efficient communication protocols able to dynamically adapt to current device operation is quite a new problem that the existing work cannot solve well. In this article, we propose a new communication protocol, called ReLEDF, that dynamically discovers devices in smart buildings and their active and nonactive status and when active their current communication behavior (through a learning-based mechanism) and schedules transmission slots (through an Earliest Deadline First-- (EDF) based mechanism) adapt to different data transmission requirements. Combining learning and scheduling introduces a tag starvation problem, so we also propose a new mode-change scheduling approach. Extensive simulations clearly show the benefits of using ReLEDF, which successfully delivers over 95% of new data samples in a typical smart home scenario with up to 150 heterogeneous smart devices, outperforming related solutions. Real experiments are also conducted to demonstrate the applicability of ReLEDF and to validate the simulations.

This paper presents a technique for automated curation of a domain-specific knowledge base or lexicon for resource-constrained domains, such as Emergency Medical Services (EMS) and its application to real-time concept extraction and cognitive assistance in emergency response. The EMS responders often verbalize critical information describing the situations at an incident scene, including patients' physical condition and medical history. Automated extraction of EMS protocol-specific concepts from responders' speech data can facilitate cognitive support through the selection and execution of the proper EMS protocols for patient treatment. Although this task is similar to the traditional NLP task of concept extraction, the underlying application domain poses major challenges, including low training resources availability (e.g., no existing EMS ontology, lexicon, or annotated EMS corpus) and domain mismatch. Hence, we develop EMSContExt, a weakly-supervised concept extraction approach for EMS concepts. It utilizes different knowledge bases and a semantic concept model based on a corpus of over 9400 EMS narratives for lexicon expansion. The expanded EMS lexicon is then used to automatically extract critical EMS protocol-specific concepts from real-time EMS speech narratives. Our experimental results show that EMSContExt achieves 0.85 recall and 0.82 F1-score for EMS concept extraction and significantly outperforms MetaMap, a state-of-the-art medical concept extraction tool. We also demonstrate the application of EMSContExt to EMS protocol selection and execution and real-time recommendation of protocol-specific interventions to the EMS responders. Here, EMSContExt outperforms MetaMap with a 6% increase and six times speedup in weighted recall and execution time, respectively.

EMS (emergency medical service) plays an important role in saving lives in emergency and accident situations. When first responders, including EMS providers and firefighters, arrive at an incident, they communicate with the patients (if conscious), family members and other witnesses, other first responders, and the command center. The first responders utilize a microphone and headset to support these communications. After the incident, the first responders are required to document the incident by filling out a form. Today, this is performed manually. Manual documentation of patient summary report is time-consuming, tedious, and error-prone. We have addressed these form filling problems by transcribing the audio from the scene, identifying the relevant information from all the conversations, and automatically filling out the form. Informal survey of first responders indicate that this application would be exceedingly helpful to them. Results show that we can fill out a model summary report form with an F1 score as high as 94%, 78%, 96%, and 83% when the data is noise-free audio, noisy audio, noise-free textual narratives, and noisy textual narratives, respectively.

Hand hygiene is crucial in preventing the spread of infections and diseases. Lack of hand hygiene is one of the major reasons for healthcare associated infections (HAIs) in hospitals. Adherence to hand hygiene compliance by the workers in the food business is very important for preventing food-borne illness. In addition to healthcare settings and food businesses, hand washing is also vital for personal well-being. Despite the importance of hand hygiene, people often do not wash hands when necessary. Automatic detection of hand washing activity can facilitate just-in-time alerts when a person forgets to wash hands. Monitoring hand washing practices is also essential in ensuring accountability and providing personalized feedback, particularly in hospitals and food businesses. Inertial sensors available in smart wrist devices can capture hand movements, and so it is feasible to detect hand washing using these devices. However, it is challenging to detect hand washing using wrist wearable sensors since hand movements are associated with a wide range of activities. In this paper, we present HAWAD, a robust solution for hand washing detection using wrist wearable inertial sensors. We leverage the distribution of penultimate layer output of a neural network to detect hand washing from a wide range of activities. Our method reduces false positives by 77% and improves F1-score by 30% compared to the baseline method.

Stress increases the risk of several mental and physical health problems like anxiety, hypertension, and cardiovascular diseases. Better guidance and interventions towards mitigating the impact of stress can be provided if stress can be monitored continuously. The recent proliferation of wearable devices and their capability in measuring several physiological signals related to stress have created the opportunity to measure stress continuously in the wild. Wearable devices used to measure physiological signals are mostly placed on the wrist and the chest. Though currently chest sensors, with/without wrist sensors, provide better results in detecting stress than using wrist sensors only, chest devices are not as convenient and prevalent as wrist devices, particularly in the free-living context. In this paper, we present a solution to detect stress using wrist sensors that emulate the gold standard chest sensors. Data from wrist sensors are translated into the data from chest sensors, and the translated data is used for stress detection without requiring the users to wear any device on the chest. We evaluated our solution using a public dataset, and results show that our solution detects stress with accuracy comparable to the gold standard chest devices which are impractical for daily use.

Activity recognition using wearable sensors has widespread and important applications in different domains including healthcare, safety and behavior monitoring. Almost all the solutions for gesture and activity recognition are data-driven, and so, understanding the data and their characteristics is fundamental toward developing effective solutions. Visualization is perhaps the most effective approach for getting insight into data as well as communicating the insights with others. A novel visualization method that would provide additional utility to the existing methods is of utmost desire. However, such novel methods for visualization are rarely invented, particularly in the area of wearable and mobile sensing. This paper presents novel methods for visualizing movement and orientation using inertial sensors. we demonstrate the use of the methods for visualizing several activities and gestures. We also developed an efficient method for smoking puff detection leveraging the visualization methods.

This paper presents the design, implementation and evaluation of milliMap, a single-chip millimetre wave (mmWave) radar based indoor mapping system targetted towards low-visibility environments to assist in emergency response. A unique feature of milliMap is that it only leverages a low-cost, off-the-shelf mmWave radar, but can reconstruct a dense grid map with accuracy comparable to lidar, as well as providing semantic annotations of objects on the map. milliMap makes two key technical contributions. First, it autonomously overcomes the sparsity and multi-path noise of mmWave signals by combining cross-modal supervision from a co-located lidar during training and the strong geometric priors of indoor spaces. Second, it takes the spectral response of mmWave reflections as features to robustly identify different types of objects e.g. doors, walls etc. Extensive experiments in different indoor environments show that milliMap can achieve a map reconstruction error less than 0.2m and classify key semantics with an accuracy of ~ 90%, whilst operating through dense smoke.

Recurrent Neural Networks (RNNs) have made great achievements for sequential prediction tasks. In practice, the target sequence often follows certain model properties or patterns (e.g., reasonable ranges, consecutive changes, resource constraint, temporal correlations between multiple variables, existence, unusual cases, etc.). However, RNNs cannot guarantee their learned distributions satisfy these model properties. It is even more challenging for predicting large-scale and complex Cyber-Physical Systems. Failure to produce outcomes that meet these model properties will result in inaccurate and even meaningless results. In this paper, we develop a new temporal logic-based learning framework, STLnet, which guides the RNN learning process with auxiliary knowledge of model properties, and produces a more robust model for improved future predictions. Our framework can be applied to general sequential deep learning models, and trained in an end-to-end manner with back-propagation. We evaluate the performance of STLnet using large-scale real-world city data. The experimental results show STLnet not only improves the accuracy of predictions, but importantly also guarantees the satisfaction of model properties and increases the robustness of RNNs.

Input is a significant problem for wearable devices, particularly for head-mounted virtual and augmented reality systems. Contemporary AR/VR systems use in-air gestures or handheld controllers for interactivity. However, mid-air handwriting provides a natural, subtle, and easy-to-use way to input commands and text. In this demo, we propose and investigate ViFin, a new technique for input commands and text entry which tracks continuous micro finger-level writing with a commodity smartwatch through vibrations. Inspired by the recurrent neural aligner and transfer learning, ViFin recognizes continuous finger writing and works across different users and achieves an accuracy of 90% and 91% for recognizing numbers and letters, respectively. Finally, a real-time writing system with two specific applications using AR smartglasses are implemented.

Smartwatches, which are small and portable, have become dominant devices in the wearable ecosystem. However, due to the limited size of the touch screens, smartwatches typically have a poor interactive experience for users. In our previous work [3, 4], we studied appropriating the human body as a surface to extend the input through tapping-induced vibrations. In this demo, we extend previously published research by presenting a brand-new product: a smartwatch that provides on-body tapping gestures recognition. We design eight tapping gestures for four applications on the new smartwatch: music players, shortcuts, cameras, and phone calls. In 2020, we collaborated with Mad Gaze [1] and launched this smartwatch on a crowdfunding platform. Our smartwatch has exceeded the crowdfunding target amount by 27 times.

Family caregivers often report increased anxiety and depression. In order to improve the interactions between in-home patients and caregivers, and reduce strain on caregivers, we build a monitoring, modeling, and interactive recommendation system for caregivers for in-home dementia patient care. The system includes monitoring for mood by speech, building classifiers that work in realistic home settings, and supporting an adaptive recommendation system to reduce stress of the caregiver. This demo shows how our system supports caregivers in practice through several scenarios.

In order to prevent safety violations, predictive monitoring with uncertainty is crucial for deep learning-enabled services in smart cities. We develop a novel predictive monitoring system for smart city applications, which consists of an RNN-based predictor with uncertainty estimation and a new specification language, named Signal Temporal Logic with Uncertainty. The solution first predicts a sequence of distributions representing city's future states with uncertainty estimation and then checks the predicted results against STL-U specified safety and performance requirements. The system supports decision making by providing a quantitative satisfaction degree with confidence guarantees. We receive promising results from evaluations on two large-scale city datasets, and on a case study on real-time predictive monitoring in a simulated smart city.

IMACS is an intelligent, interactive cognitive assistant dedicated to cardiac arrest cases in Emergency Medical Service (EMS). EMS providers deal with many cardiac cases. IMACS interacts with EMS providers in real-time and collects vital information from the providers' conversation, including names of interventions, timestamps of interventions, and dosage amount. Throughout the process, IMACS provides necessary reminders and creates a summary report afterward. Using the dynamic behavioral model of two different cardiac arrest recovery protocols, we have developed a critical risk-index based approach to provide time-sensitive feedback and suggest alternatives to the providers in real-time. Our experiments reveal an F1-score of 83% with 300 test cases. A qualitative study also reflects that seven out of ten of the EMS providers rate the system as very helpful in correctly executing cardiac arrest EMS protocols.

The COVID-19 pandemic has brought significant changes in daily activities, such as, washing hands and wearing masks regularly. During a pandemic, it is crucial to follow the recommendations from physicians and experts for mental and physical well-being. Also, it is important to know the latest information on the pandemic situation. Although smartwatches are very popular for monitoring and assisting daily life activities, existing systems are not directed towards coping up with the "new normal" life during pandemic. Towards achieving this goal, we present CoPED, a comprehensive voice cognitive assistant on a smartwatch that reminds and assists people for different daily activities during the pandemic and beyond.

Cities are deploying tens of thousands of sensors and actuators and developing a large array of smart services. The smart services use sophisticated models and decision-making policies supported by Cyber Physical Systems and Internet of Things technologies. The increasing number of sensors collects a large amount of city data across multiple domains. The collected data have great potential value, but has not yet been fully exploited. This survey focuses on the domains of transportation, environment, emergency and public safety, energy, and social sensing. This article carefully reviews both the data sets being collected across 14 smart cities and the state-of-the-art work in modeling and decision making methodologies. The article also points out the characteristics, challenges faced today, and those challenges that will be exacerbated in the future. Key data issues addressed include heterogeneity, interdisciplinary, integrity, completeness, real-timeliness, and interdependencies. Key decision making issues include safety and service conflicts, security, uncertainty, humans in the loop, and privacy.

Low-power wireless communication has been widely used in cyber-physical systems that require time-critical data delivery. Achieving this goal is challenging because of link burstiness and interference. Based on significant empirical evidence of 21 days and over 3.6 M packet transmissions per link, we propose both routing and scheduling algorithms that produce latency bounds of the real-time periodic streams and accounts for both link bursts and interference. The solution is achieved through the definition of a new metric B max that characterizes links by their maximum burst length, and by choosing a novel least-burst-route that minimizes the sum of worst-case burst lengths over all links in the route. With extensive data-driven analysis, we show that our algorithms outperform existing solutions by achieving accurate latency bound with much less energy consumption. In addition, a testbed evaluation consisting of 48 nodes spread across a floor of a building shows that we obtain 100% reliable packet delivery within derived latency bounds. We also demonstrate how performance deteriorates and discuss its implications for wireless networks with insufficient high-quality links.

An effective and non-invasive audio monitoring system needs to be capable of simultaneous real-time detection of multiple audio events in many different environments, and locally executable on resource constrained devices, such as, smart microphones. A major challenge in this research domain is having limited available annotated data. This paper presents a novel framework to generate robust detection models of environmental and human audio events with limited available data. The framework presents the generation of a large synthetic dataset using limited data for any audio event, a novel computationally efficient feature modeling technique, named Audio2Vec, that is robust against environmental variations, and identifies and exploits the syntactic relation between audio states represented by the features and the targeted audio events. The presented framework achieves 10.3% higher F-1 scores compared to the best baseline approaches. To demonstrate the effectiveness of the framework we implemented a real-time audio monitoring system that simultaneously detects 10 audio events on a Raspberry Pi 3B and evaluate it in real home and in-car settings, that achieve F-1 scores of 0.96 and 0.956, respectively.

This paper presents a cognitive assistant system for emergency medical services (EMS) that can serve as a rescue robot or virtual assistant, helping with improving situational awareness of the first responders through automated collection and analysis of data from the incident scene and providing suggestions to them. The proposed system relies on a Behavior Tree (BT) framework that combines the knowledge of EMS protocol guidelines with speech recognition, natural language processing, and machine learning methods to (i) extract critical information from responders' conversations and verbalized observations, (ii) infer the incident context, and (iii) decide on safe and effective response interventions to perform. We use a data-set of 8302 real EMS call records from an urban, high volume regional ambulance agency in the U.S. to evaluate the responsiveness and cognitive ability of the system and assess the safety of the suggestions provided to the responders. The experimental results show that the developed cognitive assistant achieves an average top-3 accuracy of 89% in selecting the correct EMS protocols and an average F1-score of 71% in suggesting the protocol specific interventions while providing transparency and evidence for the suggestions.

Facial recognition is a key enabling component for emerging Internet of Things (IoT) services such as smart homes or responsive offices. Through the use of deep neural networks, facial recognition has achieved excellent performance. However, this is only possibly when trained with hundreds of images of each user in different viewing and lighting conditions. Clearly, this level of effort in enrolment and labelling is impossible for wide-spread deployment and adoption. Inspired by the fact that most people carry smart wireless devices with them, e.g. smartphones, we propose to use this wireless identifier as a supervisory label. This allows us to curate a dataset of facial images that are unique to a certain domain e.g. a set of people in a particular office. This custom corpus can then be used to finetune existing pre-trained models e.g. FaceNet. However, due to the vagaries of wireless propagation in buildings, the supervisory labels are noisy and weak. We propose a novel technique, AutoTune, which learns and refines the association between a face and wireless identifier over time, by increasing the inter-cluster separation and minimizing the intra-cluster distance. Through extensive experiments with multiple users on two sites, we demonstrate the ability of AutoTune to design an environment-specific, continually evolving facial recognition system with entirely no user effort.

With the ever-growing usage of batteries in the IoT era, the need for more eco-friendly technologies is clear. RF-powered computing enables the redesign of personal computing devices in a battery-less manner. While there has been substantial work on the underlying methods for RF-powered computing, practical applications of this technology has largely been limited to scenarios that involve simple tasks. This paper demonstrates how RFID technology, typically used to implement object identification and counting, can be exploited to realize a battery-free smart home. In particular, we consider the coexistence of several battery-free devices, with different transmission requirements-periodic, event-based, and real-time-and propose a new adaptive and quick-to-learn MAC protocol, called APT-MAC, which dynamically collects information from devices without requiring any a priori knowledge of the environment. Extensive simulations clearly show the benefits of using APT-MAC, which is able to successfully deliver 97.7% of new data samples in complex scenarios, including several high traffic demanding devices, such as joysticks and cameras.

This poster presents the PreGo system for smart touring services. PreGo is smart in the sense that it enables its users to consider many preferences, (e.g., distance, travel time, services, attractions, safety), in their routing queries. The recommended route is completely personalized based on each user's weights for each of the routing preferences.

In smart cities, commuters have the opportunities for smart routing that may enable selecting a route with less car accidents, or one that is more scenic, or perhaps a straight and flat route. Such smart personalization requires a data management framework that goes beyond a static road network graph. This paper introduces PreGo, a novel system developed to provide real time personalized routing. The recommended routes by PreGo are smart and personalized in the sense of being (1) adjustable to individual users preferences, (2) subjective to the trip start time, and (3) sensitive to changes of the road conditions. Extensive experimental evaluation using real and synthetic data demonstrates the efficiency of the PreGo system.

Smart wrist devices available today like smart watches and fitness trackers are usually enriched with inertial sensors such as accelerometers and gyroscopes that can be used to capture wrist motions. This opens an opportunity to use these devices for user authentication, exploiting an important biometric trait of a user: the wrist gestures during performing a signature in the air. In contrast to traditional authentication methods, the gestures can be captured while signing in the air freely with no need for any input media like keypads and signature capture devices. This paper presents result from a preliminary study that shows the potential of the proposed approach to be used for robust user authentication.

Textual health advice generated from different online sources (e.g., health apps and websites) can be conflicting. Conflicts can occur due to lexical features, (such as, negation, antonyms, or numerical mismatch) or can be conditioned upon time and/or physiological status. Detecting conflicts from textual health advice poses several challenges, including, large structural variation between text and hypothesis pairs, finding conceptual overlap between pairs of advice, and inference of the semantics of an advice (i.e., what to do, why, and how). In this demonstration, we present a semantic rule-based system to detect different types of conflicts in online textual health advice statements in a context-aware and interpretable manner.

Research in the area of internet-of-things, cyberphysical-systems, and smart health often employ sensor systems at residences for continuous monitoring. Such research-oriented residential monitoring systems (RRMSs) usually face two major challenges, long-term reliable operation management and validation of system functionality with minimal human effort. Targeting these two challenges, this paper describes a monitor of monitoring systems with ground-truth validation capabilities, M2G. It consists of two subsystems, the Monitor2system and the Ground-truth validation system. The Monitor2system encapsulates a flexible set of general-purpose components to monitor the operation and connectivity of heterogeneous sensor devices (e.g. smart watches, smart phones, microphones, beacons, etc.), a local base-station, as well as a cloud server. It provides a user-friendly interface and supports different types of RRMSs in various contexts. The system also features a ground truth validation system to support obtaining ground truth in the field. Additionally, customized alerts can be sent to remote administrators and other personnel to report any dysfunction or inaccuracy of the system in real time. M2G is applied to three very different case studies: the M2FED system which monitors family eating dynamics [1], an in-home wireless sensing system for monitoring nighttime agitation [2], and the BESI system which monitors behavioral and environmental parameters to predict health events and to provide interventions [3]. The results indicate that M2G is a comprehensive system that (i) requires small cost in time and effort to adapt to an existing RRMS, (ii) provides reliable data collection and reduction in data loss by detecting faults in real-time, and (iii) provides a convenient and timely ground truth validation facility.

We develop solutions to various challenges in different stages of the processing pipeline of a real time indoor distant speech emotion recognition system to reduce the discrepancy between training and test conditions for distant emotion recognition. We use a novel combination of distorted feature elimination, classifier optimization, several signal cleaning techniques and train classifiers with synthetic reverberation obtained from a room impulse response generator to improve performance in a variety of rooms with various source-to-microphone distances. Our comprehensive evaluation is based on a popular emotional corpus from the literature, two new customized datasets and a dataset made of YouTube videos. The two new datasets are the first ever distance aware emotional corpuses and we created them by 1) injecting room impulse responses collected in a variety of rooms with various source-to-microphone distances into a public emotional corpus; and by 2) re-recording the emotional corpus with microphones placed at different distances. The overall performance results show as much as 15.51% improvement in distant emotion detection over baselines, with a final emotion recognition accuracy ranging between 79.44%-95.89% for different rooms, acoustic configurations and source-to-microphone distances. We experimentally evaluate the CPU time of various system components and demonstrate the real time capability of our system.

With the rapid digitalization of the health sector, people often turn to mobile apps and online health websites for health advice. Health advice generated from different sources can be conflicting as they address different aspects of health (e.g., weight loss, diet, disease) or as they are unaware of the context of a user (e.g., age, gender, physiological condition). Conflicts can occur due to lexical features, (such as, negation, antonyms, or numerical mismatch) or can be conditioned upon time and/or physiological status. We formulate the problem of finding conflicting health advice and develop a comprehensive taxonomy of conflicts. While a similar research area in the natural language processing domain explores the problem of textual contradiction identification, finding conflicts in health advice poses its own unique lexical and semantic challenges. These include large structural variation between text and hypothesis pairs, finding conceptual overlap between pairs of advice, and inference of the semantics of an advice (i.e., what to do, why and how). Hence, we develop Preclude, a novel semantic rule-based solution to detect conflicting health advice derived from heterogeneous sources utilizing linguistic rules and external knowledge bases. As our solution is interpretable and comprehensive, it can guide users towards conflict resolution too. We evaluate Preclude using 1156 real advice statements covering 8 important health topics that are collected from smart phone health apps and popular health websites. Preclude results in 90% accuracy and outperforms the accuracy and F1 score of the baseline approach by about 1.5 times and 3 times, respectively.

As sensor networks are increasingly deployed for critical applications, reliability and latency guarantee become more important than ever to meet industrial requirements. In this paper, we investigated the impact of link burstiness on stream scheduling using a data trace of 3,600,000 packets collected from an indoor testbed. We demonstrate that a good tradeoff between reliability and latency can be achieved by allocating certain time slots on each link for stream transmissions based on its burst length and frequency distributions. With this observation, we design transmission scheduling and routing algorithms for data streams to meet a specified reliability requirement while minimizing end-to- end latency. For the multi-stream scheduling problem, we prove its NP-hardness and design an algorithm that achieves the reliability guarantee and an O(log n) approximation of minimizing the maximum end-to-end latency for any stream. Trace- driven simulations show that our solution meets specified end-to-end reliability requirements with latency up to 9.18 times less than existing solutions.

Investigating passenger demand is essential for the taxicab business. Existing solutions are typically based on offline data collected by manual investigations, which are often dated and inaccurate for real-time analysis. To address this issue, we propose Dmodel, employing roving taxicabs as real-time mobile sensors to (i) infer passenger arriving moments by interactions of vacant taxicabs, and then (ii) infer passenger demand by customized online training with both historical and real-time data. Dmodel utilizes a novel parameter called pickup pattern based on an entropy of pickup events (accounts for various real-world logical information, e.g., bad weather) to reduce the size of big historical taxicab data to be processed. We evaluate Dmodel with a real-world 450 GB dataset of 14,000 taxicabs for a half year, and results show that compared to the ground truth, Dmodel achieves 83 percent accuracy and outperforms a statistical model by 42 percent. We further present an application where Dmodel is used to dispatch vacant taxicabs to achieve an equilibrium between passenger demand and taxicab supply across urban regions.

This paper explores efficient 3G/4G budget utilization in mobile sensing applications. Distinct from previous research work that either relied on limited WiFi access points or assumed the availability of unlimited 3G/4G communication capability, we offer a more practical mobile sensing system that leverages potential 3G/4G budgets that participants contribute at will, and uses it efficiently customized for the needs of multiple mobile sensing applications with heterogeneous sensitivity to environmental changes. We address the challenge that the information of data generation and WiFi encounters is not a priori knowledge, and propose an online decision making algorithm that takes advantage of participants' historical data. Three typical mobile sensing applications, vehicular application, mobile health and video sharing application are explored. Experimental results demonstrate that our proposed algorithms lead to significantly better system performance compared to alternative solutions for both applications.

Internet traffic measurement and analysis have long been used to characterize network usage and user behaviors, but face the problem of scalability under the explosive growth of Internet traffic and high-speed access. In this paper, we present Hobbits, a Hadoop and Hive based traffic analysis system that performs Internet Protocol (IP) and Transport Control Protocol (TCP) analysis of large-sized Internet traffic in a scalable manner. Our experimental evaluation on real datasets confirms that Hobbits outperforms previous solutions in terms of both job completion time and storage efficiency.

A few decades ago, the Internet was created. Since then, searching for information and services has increased exponentially. With the introduction of GPS-enabled devices, a special type of search appeared offering location-aware services. These services customize search results based on users' location. This includes, but not limited to, (1) service finding, e.g., "find the nearest pizza restaurant", (2) routing, e.g., "obtain the shortest path from a user's home to the airport", (3) transportation, e.g., "what are the bus links to get a user from downtown to the mall", and (4) monitoring, e.g., "alert a parent if their child school-bus deviates from its regular route". Though new hardware and software technologies such as smart watches, voice search, and big-data platforms have been introduced and widely used, each single type of the above services has benefited very little from these technologies. On the local level of each service (the micro level), a full-fledged view is still missing. On the global level of all service types (the macro level), all Location-aware services are still acting as isolated islands and a global optimized service is not available. This paper presents our vision of how to provide an integrated macro location-aware service that acts harmoniously, and how each micro service can be further improved by better incorporation of novel technologies. We also overview the key challenges associated with these suggested improvements. Then, we highlight the potential value-added by the application of our vision.

Due to high mobility and intermittent connections in vehicular networks, reliable and efficient Vehicle-to-Vehicle (V2V) communication is a challenging task. The Named Data Networking (NDN) paradigm is recently being applied to achieve efficient V2V communication, however, proactive V2V information diffusion conflicts with the receiver-initiated nature of NDN. This paper bridges this gap by exploiting hierarchical data names to achieve efficient and proactive V2V information diffusion. We first identify a popular subgroup of vehicles, then select them as the diffusion seeds with 3G/4G capability, while others are only equipped with short-range V2V communication. We also design a namespace-based method to optimize data transmission when vehicles are close, in order to maximize the information distribution across geographical space. We evaluate our solution via a real-world taxicab dataset. Experimental results demonstrate that our approach significantly outperforms state-of-the-art solutions in terms of diffusion speed and success rate of data retrieval.

Diaries are used to record aspects of lives --- activities, events, experiences, feelings, thoughts, and physiological measures. Smart diaries can reduce the user's burden by automatically registering some of these aspects. Existing systems have two weaknesses: (a) they are not extensible, and (b) their design is not theory-driven. We introduce LifeMaps, a cloud-based automated, extensible, theory-driven smart diary. Because it is inspired by theory, "The Deep Structures of Lives," it organizes data to conform to the way we experience our lives and may lead a deeper understanding of lives.

The obesity epidemic is the primary cause of recent increases in heart disease, diabetes, cancer, and other diseases that place an untenable strain on healthcare and public health. One of the primary behavioral causes, i.e. dietary intake, is a behavior that science has had little success in understanding, much less affecting. Current behavioral science suggests that family eating dynamics (FED) have high potential to impact child and parent dietary intake and obesity rates. In contrast to traditional obesity related approaches that focus on dietary intakes (e.g., what and how much is being eaten), FED based approaches focus on family mealtime and home food environment (e.g., who is eating, when, where, with whom, interpersonal stress) for modeling behavior and providing feedback that has potential for successful behavior modification. This poster briefly presents M2FED, an integrated system for monitoring and modeling FED. The system is under development, and it consists of in-situ and wearable sensors, and smartphones that collect synchronized real-time FED data used to iteratively develop dynamic, contextualized FED models.

The populations of large cities around the world are growing rapidly. Cities are beginning to address this problem by implementing significant sensing and actuation infrastructure and building services on this infrastructure. However, as the density of sensing and actuation increases and as the complexities of services grow there is an increasing potential for conflicts across Smart City services. These conflicts can cause unsafe situations and disrupt the benefits that the services were originally intended to provide. Although some of the conflicts can be detected and avoided during designing the services, many can still occur unpredictably during runtime. This paper carefully defines and enumerates the main issues regarding the detection and resolution of runtime conflicts in smart cities. In particular, it focuses on conflicts that arise across services. This issue is becoming more and more important as Smart City designs attempt to integrate services from different domains (transportation, energy, public safety, emergency, medical, and many others). Research challenges are identified and then addressed that deal with uncertainty, dynamism, real-time, mobility and spatio-temporal availability, duration and scale of effect, efficiency, and ownership. A watchdog architecture is also described that oversees the services operating in a Smart City. This watchdog solution detects and resolves conflicts, it learns and adapts, and it provides additional inputs to decision making aspects of services. Using data from a Smart City dataset, an emulated set of services and activities using those services are created to perform a conflict analysis. A second analysis hypothesizes 41 future services across 5 domains. Both of these evaluations demonstrate the high probability of conflicts in smart cities of the future.

Traditional taxi systems in metropolitan areas often suffer from inefficiencies due to uncoordinated actions as system capacity and customer demand change. With the pervasive deployment of networked sensors in modern vehicles, large amounts of information regarding customer demand and system status can be collected in real time. This information provides opportunities to perform various types of control and coordination for large-scale intelligent transportation systems. In this paper, we present a receding horizon control (RHC) framework to dispatch taxis, which incorporates highly spatiotemporally correlated demand/supply models and real-time Global Positioning System (GPS) location and occupancy information. The objectives include matching spatiotemporal ratio between demand and supply for service quality with minimum current and anticipated future taxi idle driving distance. Extensive trace-driven analysis with a data set containing taxi operational records in San Francisco, CA, USA, shows that our solution reduces the average total idle distance by 52%, and reduces the supply demand ratio error across the city during one experimental time slot by 45%. Moreover, our RHC framework is compatible with a wide variety of predictive models and optimization problem formulations. This compatibility property allows us to solve robust optimization problems with corresponding demand uncertainty models that provide disruptive event information.

Wireless and mobile healthcare systems are proliferating. Many of these systems are Cyber Physical Systems (CPS). However, the complexities involved in building healthcare systems often go beyond those CPS systems that are constructed using principles from physics and other natural physical sciences. In healthcare CPSs, complex human physiology and free will, both of which are person dependent, are paramount. These complexities give rise to many new research problems for CPS. This article highlights some of the major new research questions and promising directions for wireless and mobile healthcare CPSs of the future.

This paper explores direct phone-to-phone communication (via WiFi interface) among vehicles to support participatory sensing applications. Sensing data usually contains location, speed, and fuel consumption of the car, and has a long time delay between collected and transferred to the server. Direct communication among phones aboard is important in reducing data transfer delay time and sharing participatory sensing information in an inexpensive manner. We design a practical and optimized communication mechanism for direct phone-to-phone data transfer among phones aboard that strategically enables phone-to-phone and/or phone-to-WiFiAP communications by optimally toggling the phones between the normal client and the hotspot modes. We take advantage of the WiFi hotspot functionality on smartphones, and hence require neither involvement of participants nor changes to existing wireless infrastructure and protocols. An analytical model is established to optimize toggling between client and hotspot modes for optimal system efficiency. We fully implement this system on off-the-shelf Google Galaxy Nexus and Nexus S phones. Through a 35-vehicle two-month deployment study, as well as simulation experiments using the real-world T-drive 9,211-taxicab dataset, we show that our solution significantly reduces data transfer delay time and maintains over 80 percent system efficiency under varying system parameters.

Extensive empirical studies presented in this article confirm that the quality of radio communication between low-power sensor devices varies significantly with time and environment. This phenomenon indicates that the previous topology control solutions, which use static transmission power, transmission range, and link quality, might not be effective in the physical world. To address this issue, online transmission power control that adapts to external changes is necessary. This article presents ATPC, a lightweight algorithm for Adaptive Transmission Power Control in wireless sensor networks. In ATPC, each node builds a model for each of its neighbors, describing the correlation between transmission power and link quality. With this model, we employ a feedback-based transmission power control algorithm to dynamically maintain individual link quality over time. The intellectual contribution of this work lies in a novel pairwise transmission power control, which is significantly different from existing node-level or network-level power control methods. Also different from most existing simulation work, the ATPC design is guided by extensive field experiments of link quality dynamics at various locations over a long period of time. The results from the real-world experiments demonstrate that (1) with pairwise adjustment, ATPC achieves more energy savings with a finer tuning capability, and (2) with online control, ATPC is robust even with environmental changes over time.

This article demonstrates how to use multiple channels to improve communication performance in Wireless Sensor Networks (WSNs). We first investigate multichannel realities in WSNs through intensive empirical experiments with Micaz motes. Our study shows that current multichannel protocols are not suitable for WSNs because of the small number of available channels and unavoidable time errors found in real networks. With these observations, we propose a novel tree-based, multichannel scheme for data collection applications, which allocates channels to disjoint trees and exploits parallel transmissions among trees. In order to minimize interference within trees, we define a new channel assignment problem that is proven NP-complete. Then, we propose a greedy channel allocation algorithm that outperforms other schemes in dense networks with a small number of channels. We implement our protocol, called the Tree-based, Multichannel Protocol (TMCP), in a real testbed. To adjust to networks with link quality heterogeneity, an extension of TMCP is also proposed. Through both simulation and real experiments, we show that TMCP can significantly improve network throughput and reduce packet losses. More important, evaluation results show that TMCP better accommodates multichannel realities found in WSNs than other multichannel protocols.

The primary objective of this research is to develop a simple and interpretable predictive framework to perform temporal modeling of individual user's behavior traits based on each person's past observed traits/behavior. Individual-level human behavior patterns are possibly influenced by various temporal features (e.g., lag, cycle) and vary across temporal scales (e.g., hour of the day, day of the week). Most of the existing forecasting models do not capture such multi-scale adaptive regularity of human behavior or lack interpretability due to relying on hidden variables. Hence, we build a multi-scale adaptive personalized (MAPer) model that quantifies the effect of both lag and behavior cycle for predicting future behavior. MAper includes a novel basis vector to adaptively learn behavior patterns and capture the variation of lag and cycle across multi-scale temporal contexts. We also extend MAPer to capture the interaction among multiple behaviors to improve the prediction performance.

Advances in wireless sensor networks have enabled the monitoring of daily activities of elderly people. The goal of these monitoring applications is to learn normal behavior in terms of daily activities and look for any deviation, i.e., Anomalies, so that alerts can be sent to relatives or caregivers. However, human behavior is very complex, and many existing anomaly detection systems are too simplistic which cause many false alarms, resulting in unreliable systems. We present Holmes, a comprehensive anomaly detection system for daily in-home activities. Holmes accurately learns a resident's normal behavior by considering variability in daily activities based not only on a per day basis, but also considering specific days of the week, different time periods such as per week and per month, and collective, temporal, and correlation based features. This approach of learning complicated normal behaviors reduces false alarms. Also, based on resident and expert feedback, Holmes learns semantic rules that explain specific variations of activities in specific scenarios to further reduce false alarms. We evaluate Holmes using data collected from our own deployed system, public data sets, and data collected by a senior safety system provider company from an elderly resident's home. Our evaluation shows that compared to state of the art systems, Holmes reduces false positives and false negatives by at least 46% and 27%, respectively.

AsthmaGuide is a smartphone and cloud based asthma system in which a smart phone is used as a hub for collecting a comprehensive collection of information. The data, including data over time, is then displayed in a cloud web application for both patients and healthcare providers to view. AsthmaGuide also provides an advice and alarm infrastructure based on the collected data and parameters set by healthcare providers. With these components, AsthmaGuide provides a comprehensive ecosystem that allows patients to be involved in their own health and also allows doctors to provide more effective day to day care. Using real asthma patient wheezing sounds we develop a new combination of classifiers that is 96% accurate at automatically detecting wheezing. This abstract provides an overview of the design and implementation of AsthmaGuide and provides empirical evidence that AsthmaGuide is 3% - 11% more accurate in detecting wheezing sounds than standard techniques.

Many elderly who are suffering from dementia are also suffering from agitation. While most assisted living facilities and home health care situations rely upon caregivers to monitor and record agitation of their patients, the accuracy is limited because the caregiver must be present during the agitation and must record the event properly. Accurate 24-7 data would help physicians with improved diagnoses and care. To solve this problem we developed KinVocal, a system that continuously monitors and detects agitated vocal events and can be used for the elderly population suffering from dementia. KinVocal, using a novel combination of acoustic signal processing and multiple text mining techniques, automatically detects and records the 8 major vocal agitations for dementia patients as defined by the medical community. This includes: constant unwarranted request for attention or help, making verbal sexual advances, crying, screaming, laughing, cursing, speaking in repetitive sentences, and negativism. The novelty of KinVocal includes the comprehensiveness of addressing all 8 vocal events, using the text of the vocalizations only when accurate, combining text and acoustic features when necessary, and employing text mining and feature identification. A comprehensive performance evaluation includes using data from Youtube and movies, controlled experiments, and real in-home deployments. The results show high accuracy for all 8 vocal events.

Many applications in wireless sensor networks require communication performance that is both consistent and of high quality. Unfortunately, performance of current network protocols can vary significantly because of various interferences and environmental changes. Current protocols estimate link quality based on the reception of probe packets over a short time period. This method is neither efficient nor accurate enough to capture the dramatic variations of link quality. Therefore, we propose a link metric called competence that characterizes links over a longer period of time. We combine competence with current short-term estimations in routing algorithm designs. To further improve network performance, we have designed a distributed route maintenance framework based on feedback control solutions. This framework allows every link along an end-to-end (E2E) path to adjust its link protocol parameters, such as transmission power and number of retransmissions, to ensure specified E2E reliability and latency under dynamic link qualities. Our solutions are evaluated in both extensive simulations and real system experiments. In real system evaluations with 48 T-Motes, our overall solution improves E2E packet delivery ratio over existing solutions by up to 40% while reducing transmission energy consumption by up to 22%. Importantly, our solution also achieves more stable and better transient performance than current approaches.

In the taxicab industry, a long-standing challenge is how to reduce taxicabs' miles spent without fares, i.e., cruising miles. The current solutions for this challenge usually depend on passengers to actively provide their locations in advance for pickups. To address this challenge without the burden on passengers, in this paper, we propose a cruising system, pCruise, for taxicab drivers to find efficient routes to pick up passengers to reduce cruising miles. According to the real-time pick-up events from nearby taxicabs, pCruise characterizes a cruising process with a cruising graph, and assigns weights on edges of the cruising graph to indicate the utility of cruising corresponding road segments. Our weighting process considers the number of nearby passengers and taxicabs together in real-time, aiming at two scenarios where taxicabs are explicitly or implicitly coordinated with each other. Based on a weighted cruising graph, when a taxicab becomes vacant, pCruise provides a distributed online scheduling strategy to obtain and update an efficient cruising route with the minimum length and at least one arriving passenger. We evaluate pCruise based on a real-world GPS dataset from a Chinese city Shenzhen with 14;000 taxicabs. The evaluation results show that pCruise assists taxicab drivers to reduce cruising miles by 42 percent on average.

This paper explores direct phone-to-phone communication (via WiFi interface) among vehicles to support mobile sensing applications. Direct communication among drivers' phones is important in improving data collection efficiency and sharing participatory sensing information in an inexpensive manner. We design a practical and optimized communication mechanism for direct phone-to-phone data transfer among drivers' phones that strategically enables phone-to-phone and/or phone-to-WiFiAP communications by optimally toggles the phone between the normal client and the hotspot modes. We take advantage of the WiFi hotspot functionality on smartphones, and hence require neither involvement of participants nor changes to existing wireless infrastructure and protocols. An analytical model is established to optimize toggling between client and hotspot modes for optimal system efficiency. We fully implement this system on off-the-shelf Google Galaxy Nexus and Nexus S phones. Through a 35-vehicle 2-month deployment study, as well as simulation experiments using the real-world T-drive 9,211-taxicab dataset, we show that our solution significantly reduces data transfer delay time and maintains over 80% efficiency under varying system parameters. We even achieve 90% for parameter settings of the latest smartphones.

With the proliferation of inexpensive sensors, sensors are increasingly being used in smart homes. Recent experience on long term sensor deployment in residential homes has identified the potential risk of various types of sensor failure. Motivated by real examples, we develop new schemes to detect not only fail-stop failure, but obstructed-view and moved-location failures that are not the traditional fault detection foci. Our proposed solution, FailureSense, uses a novel idea of using electrical appliances to detect sensor failure at home. We learn the regular patterns of sensor firing with respect to appliance activation events and report a failure when we observe a significant deviation from the regularity. By using data from three real home deployments of over 71 days and 2818 recorded turn on and off events of 19 monitored appliances, we observe that FailureSense can detect obstructed-view, moved-location, and fail-stop failures with 82.84%, 90.53%, and 86.87% precision, respectively, with an average of 88.81% recall.

Kintense is a robust, accurate, real-time, and evolving system for detecting aggressive actions such as hitting, kicking, pushing, and throwing from streaming 3D skeleton joint coordinates obtained from Kinect sensors. Kintense uses a combination of: (1) an array of supervised learners to recognize a predefined set of aggressive actions, (2) an unsupervised learner to discover new aggressive actions or refine existing actions, and (3) human feedback to reduce false alarms and to label potential aggressive actions. This paper describes the design and implementation of Kintense and provides empirical evidence that the system is 11% - 16% more accurate and 10% - 54% more robust to changes in distance, body orientation, speed, and person when compared to standard techniques such as dynamic time warping (DTW) and posture based gesture recognizers. We deploy Kintense in two multi-person households and demonstrate how it evolves to discover and learn unseen actions, achieves up to 90% accuracy, runs in real-time, and reduces false alarms with up to 13 times fewer user interactions than a typical system.

Many technical communities are vigorously pursuing research topics that contribute to the Internet of Things (IoT). Nowadays, as sensing, actuation, communication, and control become even more sophisticated and ubiquitous, there is a significant overlap in these communities, sometimes from slightly different perspectives. More cooperation between communities is encouraged. To provide a basis for discussing open research problems in IoT, a vision for how IoT could change the world in the distant future is first presented. Then, eight key research topics are enumerated and research problems within these topics are discussed.

The primary goal of breadcrumb trail sensor networks is to transmit in real-time users' physiological parameters that measure life-critical functions to an incident commander through reliable multihop communication. In applications using breadcrumb solutions, there are often many users working together, and this creates a well-known body shadowing effect (BSE). In this article, we first measure the characteristics of body shadowing for 2.4GHz sensor nodes. Our empirical results show that the body shadowing effect leads to severe packet loss and consequently very poor real-time performance. Then we develop a novel Intentional Forwarding solution. This solution accurately detects the shadowing mode and enables selected neighbors to forward data packets. Experimental results from a fully implemented testbed demonstrate that Intentional Forwarding is able to improve the end-to-end average packet delivery ratio (PDR) from 58% to 93% and worst-case PDR from 45% to 85%, and is able to meet soft real-time requirements even under severe body shadowing problems.

MultiNets is a system supporting seamless switch-over between wireless interfaces on mobile devices in real-time. MultiNets is configurable to run in three different modes: (i) Energy Saving mode --for choosing the interface that saves the most energy based on the condition of the device, (ii) Offload mode --for offloading data traffic from the cellular to WiFi network, and (iii) Performance mode --for selecting the network for the fastest data connectivity. MultiNets also provides a powerful API that gives the application developers: (i) the choice to select a network interface to communicate with a specific server, and (ii) the ability to simultaneously transfer data over multiple network interfaces. MultiNets is modular, easily integrable, lightweight, and applicable to various mobile operating systems. We implement MultiNets on Android devices as a show case. MultiNets does not require any extra support from the network infrastructure and runs existing applications transparently. To evaluate MultiNets, we first collect data traces from 13 actual Android smartphone users over three months. We then use the collected traces to show that, by automatically switching to WiFi whenever it is available, MultiNets can offload on average 79.82% of the data traffic. We also illustrate that, by optimally switching between the interfaces, MultiNets can save on average 21.14 KJ of energy per day, which is equivalent to 27.4% of the daily energy usage. Using our API, we demonstrate that a video streaming application achieves 43--271% higher streaming rate when concurrently using WiFi and 3G interfaces. We deploy MultiNets in a real-world scenario and our experimental results show that depending on the user requirements, it outperforms the state-of-the-art Android system either by saving up to 33.75% energy, achieving near-optimal offloading, or achieving near-optimal throughput while substantially reducing TCP interruptions due to switching.

Breadcrumb systems (BCS) aid first responders by communicating their physiological parameters to remotely located base stations. In this paper, we describe the design, implementation, and evaluation of an automatic and robust multi-user breadcrumb system for indoor first response applications. Our solution includes a breadcrumb dispenser with a link estimator that is used to decide when to deploy breadcrumbs to maintain reliable wireless connectivity. The solution includes accounting for realities of buildings and dispensing such as the height difference between where the dispenser is worn and the floor where the dispensed nodes are found. We also include adaptive power management to maintain link quality over time. Moreover, we propose UF, a distributed cooperative deployment algorithm, to achieve longer breadcrumb chain lengths while maintaining fairness and high system reliability via selecting appropriate benefit and cost functions. We deployed and evaluated our system in real buildings with several different first responder mobility patterns. Experimental results from our study show that compared to the state of the art solution , our breadcrumb system achieves 200 percent link redundancy with only 23 percent additional deployed nodes. Our deployed breadcrumb chain can achieve 90 percent PRR when one node fails in the chain. In addition, by applying the UF coordination algorithm, the system can maintain connectivity for up to 87 percent longer distances than baseline greedy coordination approach while maintaining 96 percent packet delivery ratio.

Carpooling taxicab services hold the promise of providing additional transportation supply, especially in extreme weather or rush hour when regular taxicab services are insufficient. Although many recommendation systems about regular taxicab services have been proposed recently, little research, if any, has been done to assist passengers to find a successful taxicab ride with carpooling. In this paper, we present the first systematic work to design a unified recommendation system for both regular and carpooling services, called CallCab, based on a data driven approach. In response to a passenger's request, CallCab aims to recommend either (i) a vacant taxicab for a regular service with no detour, or (ii) an occupied taxicab heading to the similar direction for a carpooling service with less detour, yet without assuming any knowledge of destinations of passengers already on occupied taxicabs. To analyze these unknown destinations of occupied taxicabs, CallCab generates and refines taxicab trip distributions based on GPS datasets and context information collected in the existing taxicab infrastructure. To improve CallCab's efficiency to process such a big dataset, we augment the efficient MapReduce model with a Measure phase tailored for our application. We evaluate CallCab with a real world dataset of 14,000 taxicabs, and results show that compared to ground truth, CallCab can reduce 64% of the total mileage to deliver all passengers and 63% of passenger's waiting time.

Various sensing systems have been exploited to monitor in-person interactions, one of the most important indicators of mental health. However, existing solutions either require deploying in-situ infrastructure or fail to provide detailed information about a person's involvement during interactions. In this paper, we use smartphones and on-body sensors to monitor in-person interactions without relying on any in-situ infrastructure. By using state-of-art smartphones and on-body sensors, we implement a multi-modal system that collects a battery of features to better monitor in-person interactions. In addition, unlike existing work that monitors interactions only based on data collected from one person, we emphasize that in-person interactions intrinsically involve multiple participants, and thus we aggregate information from nearby people to identify more interaction details. Evaluation shows our solution accurately detects various in-person interactions and provides insights absent in existing systems.

Wireless Sensor Networks (WSNs) are being developed and deployed in a wide range of Cyber-Physical systems, some of which must be dependable, e.g. in assisted living facilities where their failure could lead to an accident. In this paper, it is shown that the state of the art approaches do not meet the needs of dependability that these applications require. The main reason is an issue is the unpredictable physical environment in which they operate. Currently there is little emphasis on how these systems behave when failures occur, instead authors emphasise average case performance. Consequently there is little understanding of how and why systems fail and the possible consequences e.g. a system hazard. In this paper simulated tests are used at run-time to check key dependability properties of the system. The results of these tests are used to plan maintenance, thus ensuring available and reliable operation, and determining when the system is at risk of subjecting people to unacceptable hazards such that appropriate steps can be taken. Our approach has been show to perform with 15% less time at risk than the current state-of-the art.

There is a growing number of examples that use the microphones in phone for various acoustic processing tasks as mobile phones become increasingly computationally powerful. However, there is no general physiological acoustic anomaly detection service on smartphones. To this end, we propose a physiological acoustic anomaly detection service which contains classifiers that can be used to detect irregularity and anomalies in lung sounds and notifies the user. We also present and discuss on some preliminary results.

The monitoring of electrical and water fixtures in the home is being applied for a variety of "smart home" applications, such as recognizing activities of daily living (ADLs) or conserving energy or water usage. Fixture monitoring techniques generally fall into two categories: fixture recognition and fixture disaggregation. However, existing techniques require users to explicitly identify each individual fixture, either by placing a sensor on it or by manually creating training data for it. In this paper, we present a new fixture discovery system that automatically infers the existence of electrical and water fixtures in the home. We call the system FixtureFinder. The basic idea is to use data fusion between the smart meters and other sensors or infrastructure already in the home, such as the home security or automation system, and to find repeating patterns in the fused data stream. To evaluate FixtureFinder, we deployed the system into 4 different homes for 7-10 days of data collection. Our results show that FixtureFinder is able to identify and differentiate major light and water fixtures in less than 10 days, including multiple copies of light bulbs and sinks that have identical power/water profiles.

Auditeur is a general-purpose, energy-efficient, and context-aware acoustic event detection platform for smartphones. It enables app developers to have their app register for and get notified on a wide variety of acoustic events. Auditeur is backed by a cloud service to store user contributed sound clips and to generate an energy-efficient and context-aware classification plan for the phone. When an acoustic event type has been registered, the smartphone instantiates the necessary acoustic processing modules and wires them together to execute the plan. The phone then captures, processes, and classifies acoustic events locally and efficiently. Our analysis on user-contributed empirical data shows that Auditeur's energy-aware acoustic feature selection algorithm is capable of increasing the device lifetime by 33.4%, sacrificing less than 2% of the maximum achievable accuracy. We implement seven apps with Auditeur, and deploy them in real-world scenarios to demonstrate that Auditeur is versatile, 11.04% - 441.42% less power hungry, and 10.71% - 13.86% more accurate in detecting acoustic events, compared to state-of-the-art techniques. We present a user study to demonstrate that novice programmers can implement the core logic of interesting apps with Auditeur in less than 30 minutes, using only 15 - 20 lines of Java code.

Modeling and simulation play important roles in engineering research and design. These techniques are especially helpful in the early phases where limited detail is available about the design and where design changes are less costly. In addition, high-fidelity models can be employed at the later stages to complement testing. Models are also important research tools for understanding complex phenomena.

Falls are a significant problem for the elderly living independently in the home. Many falls occur due to household objects left in open spaces. We present KinSpace, a system that uses real-time depth data and human-in-the-loop feedback to adjust its understanding of the open space of an environment. We present results showing the effectiveness of our underlying technical solutions in identifying open spaces and obstacles. The results for both lab testing and a small deployment in an actual home show over 80% accuracy for open space detection and 70% accuracy in obstacle detection even in the presence of many real world issues.

Kintense is a robust, accurate, real-time, and evolving system for detecting aggressive actions such as hitting, kicking, pushing, and throwing from streaming 3D skeleton joint coordinates obtained from Kinect sensors. Kintense uses a combination of: (1) an array of supervised learners to recognize a predefined set of aggressive actions, (2) an unsupervised learner to discover new aggressive actions or refine existing actions, and (3) human feedback to reduce false alarms and to label potential aggressive actions. This abstract provides an overview of the design and implementation of Kintense and provides empirical evidence that Kintense is 11% -- 16% more accurate when compared to standard techniques such as dynamic time warping (DTW) and posture based gesture recognizers.

We solve the problem of localizing and tracking household objects using a depth-camera sensor network. We design and implement Kin sight that tracks household objects indirectly -- by tracking human figures, and detecting and recognizing objects from human-object interactions. We devise two novel algorithms: (1) Depth Sweep -- that uses depth information to efficiently extract objects from an image, and (2) Context Oriented Object Recognition -- that uses location history and activity context along with an RGB image to recognize object sat home. We thoroughly evaluate Kinsight's performance with a rich set of controlled experiments. We also deploy Kinsightin real-world scenarios and show that it achieves an average localization error of about 13 cm.

We monitor activities of daily living of smart home residents to detect anomalies in their behavior. Unlike traditional anomaly detection systems, we aim to reduce false positives in anomaly detection with the help of semantic rules. Some of these rules are predefined based on expert knowledge and the rest are learned by the system with the help of resident/expert feedback. We also correlate trend of change in different activities to improve anomaly detection. In addition to monitor statistical deviation from regular behavior, we also detect deviation from healthy and social norms (defined by experts) as anomalies.

Inexpensive wireless sensing products are dramatically reducing the cost of in-home sensing. However, these sensors have been found to fail often and prohibitive maintenance costs may negate the cost benefits of inexpensive hardware and do-it-yourself installation. In this paper, we describe a new technique called SMART that uses application-level semantics to detect, assess, and adapt to sensor failures. SMART detects sensor failures at run-time by analyzing the relative behavior of multiple classifier instances trained to recognize the same set of activities based on different subsets of sensors. Once a failure is detected, SMART assesses its importance and adapts the classifier ensemble in attempt to avoid maintenance dispatch. Evaluation on three homes from two public datasets shows that SMART decreases the number of maintenance dispatches by 55% on average, identifies non-fail-stop failures at run-time with more than 85% accuracy, and improves the activity recognition accuracy under sensor failures by 15% on average.

A mobile phone, as a pervasive device, has great potential in human wellness monitoring. In this demo, we first present the design and implementation of our hardware - SEPTIMU. SEPTIMU consists of a small baseboard and a pair of tiny sensor boards embedded inside conventional earphones. The baseboard provides power conversion and data communication through the normal audio jack interface. The embedded sensor board is 1×1cm2 and integrates 3-axis accelerometer, gyroscope, thermometer, photodiode and microphone. Secondly, we evaluate SEPTIMU using a mobile application that continuously monitors body posture and provides feedback to the user.

The primary goal of breadcrumb trail sensor networks is to transmit in real-time users' physiological parameters that measure life critical functions to an incident commander through reliable multihop communication. In applications using breadcrumb solutions, there are often many users working together, and this creates a well-known body shadowing effect (BSE). In this paper, we first measure the characteristics of body shadowing for 2.4 GHz sensor nodes. Our empirical results show that the body shadowing effect leads to severe packet loss, and consequently very poor real-time performance. Then we develop a novel Intentional Forwarding solution. This solution accurately detects the shadowing mode and enables selected neighbors to forward data packets. Experimental results from a fully implemented testbed demonstrate that Intentional Forwarding is able to improve the end-to-end average packet delivery ratio (PDR) from 58% to 93% and worst-case PDR from 45% to 85%, and meet soft real-time requirements even under severe body shadowing problems.

In this paper we present Multi Nets, a system which is capable of switching between wireless network interfaces on mobile devices in real-time. Multi Nets is motivated by the need of smart phone platforms to save energy, offload data traffic, and achieve higher throughput. We describe the architecture of Multi Nets and demonstrate the methodology to perform switching in Linux based mobile OSes such as Android. Our analysis on mobile data traces collected from real users shows that with real-time switching we can save 27.4% of the energy, offload 79.82% of the data traffic, or achieve 7 times more throughput on average. We deploy Multi Nets in a real world scenario and our experimental results show that depending on the user requirements, it outperforms the state-of-the-art Android system either by saving up to 33.75% energy, or achieving near-optimal offloading, or achieving near-optimal throughput while substantially reducing TCP interruptions due to switching.

Mobile phones have become an ideal platform for physiological and environmental sensing. A number of research and commercial smartphone "accessories" have emerged in recent years that try to extend the sensing capabilities of a mobile phone. However, the major drawback of these devices is that they either require the user to act in some specific way or change their lifestyle and habit to some extent. In this demo, we present Septimu V2 (Septimu2) -- a novel non-intrusive physiological and environmental sensing platform which is fully embedded in a conventional earphone, works with existing smartphones, and does not require the user to change habits in any way. Septimu2 is a continuation of [1], and integrates a suite of new sensors. In addition to 3-axis accelerometer and gyroscope, Septimu2 incorporates remote IR temperature sensor, IR LED, IR photodiode and two additional microphones. The baseboard performs signal condition and sends the data to cellphone via Bluetooth. Septimu2 enables a number of applications, including heart-rate monitoring, fine grained posture detection, and external sound source localization and classification.

MusicalHeart is a biofeedback-based, context-aware, automated music recommendation system for smartphones. We introduce a new wearable sensing platform, Septimu, which consists of a pair of sensor-equipped earphones that communicate to the smartphone via the audio jack. The Septimu platform enables the MusicalHeart application to continuously monitor the heart rate and activity level of the user while listening to music. The physiological information and contextual information are then sent to a remote server, which provides dynamic music suggestions to help the user maintain a target heart rate. We provide empirical evidence that the measured heart rate is 75% -- 85% correlated to the ground truth with an average error of 7.5 BPM. The accuracy of the person-specific, 3-class activity level detector is on average 96.8%, where these activity levels are separated based on their differing impacts on heart rate. We demonstrate the practicality of MusicalHeart by deploying it in two real world scenarios and show that MusicalHeart helps the user achieve a desired heart rate intensity with an average error of less than 12.2%, and its quality of recommendation improves over time.

Body sensor networks (BSNs) are emerging cyber–physical systems that promise to improve quality of life through improved healthcare, augmented sensing and actuation for the disabled, independent living for the elderly, and reduced healthcare costs. However, the physical nature of BSNs introduces new challenges. The human body is a highly dynamic physical environment that creates constantly changing demands on sensing, actuation, and quality of service (QoS). Movement between indoor and outdoor environments and physical movements constantly change the wireless channel characteristics. These dynamic application contexts can also have a dramatic impact on data and resource prioritization. Thus, BSNs must simultaneously deal with rapid changes to both top–down application requirements and bottom–up resource availability. This is made all the more challenging by the wearable nature of BSN devices, which necessitates a vanishingly small size and, therefore, extremely limited hardware resources and power budget. Current research is being performed to develop new principles and techniques for adaptive operation in highly dynamic physical environments, using miniaturized, energy-constrained devices. This paper describes a holistic cross-layer approach that addresses all aspects of the system, from low-level hardware design to higher level communication and data fusion algorithms, to top-level applications.

Quality-aware realtime Embedded DataBase (QeDB) is a database for data-intensive real-time applications running on embedded devices. Currently, databases for embedded systems are best effort, providing no guarantees on their timeliness and data freshness. Existing real-time database (RTDB) technology cannot be applied to these embedded databases since it hypothesizes that the main memory of a system is large enough to hold the entire database. This, however, might not be true in data-intensive real-time applications. QeDB uses a novel feedback control scheme to support QoS in such embedded systems without requiring all data to reside in main memory. In particular, our approach is based on simultaneous control of both I/O and CPU resources to guarantee the desired timeliness. Unlike existing work on feedback control of RTDB performance, we implement and evaluate the proposed scheme on a modern embedded device. The experimental results show that our approach supports the desired timeliness of transactions while still maintaining high data freshness compared to baseline approaches.

This paper describes a novel group-based programming abstraction called a “Bundle” for cyber-physical systems (CPS). Similar to other programming abstractions, a Bundle creates logical collections of sensing devices. However, previous abstractions were focused on wireless sensor networks (WSNs) and did not address key aspects of CPS. Bundles elevate the programming domain from a single WSN to complex systems of systems by allowing the programming of applications involving multiple CPSs that are controlled by different administrative domains and support mobility both within and across CPSs. Bundles can seamlessly group not only sensors, but also actuators which constitute an important part of CPS. They enable programming in a multiuser environment with fine grained access right control and conflict resolution mechanism. Bundles support heterogeneous devices, such as motes, PDAs, laptops, and actuators according to the applications' requirements. They allow different applications to simultaneously use the same sensors and actuators. Bundles facilitate feedback control mechanisms by dynamic membership update and requirements reconfiguration based on feedback from the current members. The Bundle abstraction is implemented in Java which ensures ease and conciseness of programming. We present the design and implementation details of Bundles as well as a performance evaluation using 32 applications written with Bundles. This set includes across-network applications that have sophisticated sensing and actuation logic, mobile nodes that are heterogeneous, and feedback control mechanisms. Each of these applications is programmed in less than 60 lines of code.

Localization of wireless sensor nodes has long been regarded as a problem that is difficult to solve, especially when considering characteristics of real-world environments. This paper formally describes, designs, implements, and evaluates a novel localization system called Spotlight. The system uses spatiotemporal properties of well-controlled events in the network, light in this case, to obtain locations of sensor nodes. Performance of the system is evaluated through deployments of Mica2 and XSM motes in an outdoor environment, where 20 cm localization error is achieved. A sensor network consisting of any number of nodes deployed in a 2,500 m2area can be localized in under 10 minutes. Submeter localization error in an outdoor environment is made possible without equipping the wireless sensor nodes with specialized ranging hardware.

Previous localization solutions in wireless sensor networks mainly focus on using various techniques to estimate node positions. In this paper, we argue that quantifying the uncertainty of these estimates is equally important in practice. By using the quantitative uncertainty of measurements and estimates, we can derive more accurate estimates by better fusing the measurements, provide confidence information for confidence-based applications, and know how to select the best anchor nodes so as to minimize the total mean square errors of the whole network. This paper quantifies the estimation uncertainty as an error covariance matrix, and presents an efficient incremental centralized algorithm---INOVA and a decentralized algorithm---OSE-COV for calculating the error covariance matrix. Furthermore, we present how to use the error covariance matrix to infer the confidence region of each node's estimate, and provide an optimal strategy for the anchor selection problem. Extensive simulation results show that INOVA significantly improves the computation efficiency when the network changes dynamically; the confidence region inference is accurate when the measurement number to node number ratio is more than 2; and the optimal anchor selection strategy reduces the total mean square error by four times as much as the variation-based algorithm in best case.

Breadcrumb systems (BCS) aid first responders by communicating their physiological parameters to remotely located base stations. However, state-of-the-art research only focuses on deploying breadcrumb systems on the assumption of uncoordinated users, which is inefficient. In this paper, we present the first design, implementation, and evaluation of reliable multiuser breadcrumb systems (MUBCS) which exploits efficient and automatic coordination among system users to achieve better utilization of limited breadcrumbs. We propose UF, a distributed cooperative deployment algorithm, to achieve longer breadcrumb chain length while maintaining fairness and high system reliability via selecting appropriate benefit and cost functions. UF also requires no prior assumptions about users' mobility models, making the design practical for real applications. We deployed and evaluated our system in real buildings with several different first responder mobility patterns. Experimental results indicate that this approach can maintain connectivity for up to 87% longer distances than baseline greedy coordination approach while maintaining 96% packet delivery ratio.

Homes are rich with information about people's energy consumption, medical health, and personal or family functions. In this paper, we present our experiences deploying large-scale residential sensing systems in over 20 homes. Deploying small-scale systems in homes can be deceptively easy, but in our deployments we encountered a phase transition in which deployment effort increases dramatically as residential deployments scale up in terms of 1) the number of nodes, 2) the length of time, and 3) the number of houses. In this paper, we distill our experiences down to a set of guidelines and design principles to help future deployments avoid the potential pitfalls of large-scale sensing in homes.

As wireless devices and sensors are increasingly deployed on people, researchers have begun to focus on wireless body-area networks. Applications of wireless body sensor networks include healthcare, entertainment, and personal assistance, in which sensors collect physiological and activity data from people and their environments. In these body sensor networks, quality of service is needed to provide reliable data communication over prioritized data streams. This article proposes BodyQoS, the first running QoS system demonstrated on an emulated body sensor network. BodyQoS adopts an asymmetric architecture, in which most processing is done on a resource-rich aggregator, minimizing the load on resource-limited sensor nodes. A virtual MAC is developed in BodyQoS to make it radio-agnostic, allowing a BodyQoS to schedule wireless resources without knowing the implementation details of the underlying MAC protocols. Another unique property of BodyQoS is its ability to provide adaptive resource scheduling. When the effective bandwidth of the channel degrades due to RF interference or body fading effect, BodyQoS adaptively schedules remaining bandwidth to meet QoS requirements. We have implemented BodyQoS in NesC on top of TinyOS, and evaluated its performance on MicaZ devices. Our system performance study shows that BodyQoS delivers significantly improved performance over conventional solutions in combating channel impairment.

With the emergence of high data rate sensor network applications, there is an increasing demand for high-performance query services. To meet this challenge, we propose Dynamic Conflict-free Query Scheduling (DCQS), a novel scheduling technique for queries in wireless sensor networks. In contrast to earlier TDMA protocols designed for general-purpose workloads, DCQS is specifically designed for query services in wireless sensor networks. DCQS has several unique features. First, it optimizes the query performance through conflict-free transmission scheduling based on the temporal properties of queries in wireless sensor networks. Second, it can adapt to workload changes without explicitly reconstructing the transmission schedule. Furthermore, DCQS also provides predictable performance in terms of the maximum achievable query rate. We provide an analytical capacity bound for DCQS that enables DCQS to handle overload through rate control. NS2 simulations demonstrate that DCQS significantly outperforms a representative TDMA protocol (DRAND) and 802.11b in terms of query latency and throughput.

Cyber-physical systems (CPS) are physical and engineered systems whose operations are monitored, coordinated, controlled and integrated by a computing and communication core. Just as the internet transformed how humans interact with one another, cyber-physical systems will transform how we interact with the physical world around us. Many grand challenges await in the economically vital domains of transportation, health-care, manufacturing, agriculture, energy, defense, aerospace and buildings. The design, construction and verification of cyber-physical systems pose a multitude of technical challenges that must be addressed by a cross-disciplinary community of researchers and educators.

Packet collision causes packet loss and wastes resources in wireless networks. It becomes even worse in dense WSNs, due to burst-traffic and congestion around sinks. In this paper, we propose a novel protocol to recover collided packets. Our experiments on a testbed reveal that collisions between long packets and short packets cause a partial error pattern on collided packets, which can be used for efficient recovery. We give a theoretical analysis that demonstrates that combining such collision recovery with CSMA protocols achieves a significant performance improvement. Then, we design ACR, an Active Collision Recovery protocol, which actively converts most potential collisions into LS-collisions, and then applies a lightweight FEC scheme to recover collided packets with such partial error patterns. We implement ACR on a Tmote testbed, and compare its performance with other packet recovery schemes. Results show that ACR significantly reduces the number of retransmissions, and achieves around 25% improvement on transmission efficiency over other schemes.

It is very important to monitor quantity and quality of sleeping of elderly people. This paper presents a novel sleeping monitoring system based on RFID-based sensors called WISPs (Wireless identification and Sensing Platform). Main advantages of our system are that these WISP devices are noninvasive, inexpensive and do not require batteries. Our system provides feedback to the users/doctors about irregularity in sleeping. Results from our initial experiments show that our system can successfully detect sleeping periods and movements during sleeping.

As wireless sensor networks mature, they are increasingly being used in real-time applications. Many of these applications require reliable transmission within latency bounds. Achieving this goal is very difficult because of link burstiness and interference. Based on significant empirical evidence of 21 days and over 3,600,000 packets transmission per link, we propose a scheduling algorithm that produces latency bounds of the real-time periodic streams and accounts for both link bursts and interference. The solution is achieved through the definition of a new metric Bmax that characterizes links by their maximum burst length, and by choosing a novel least-burst-route that minimizes the sum of worst case burst lengths over all links in the route. A testbed evaluation consisting of 48 nodes spread across a floor of a building shows that we obtain 100% reliable packet delivery within derived latency bounds. We also demonstrate how performance deteriorates and discuss its implications for wireless networks with insufficient high quality links.

Continuous and reliable operation of WSNs is notoriously difficult to guarantee due to hardware degradation and environmental changes. In this paper, we propose and demonstrate a methodology for run-time assurance (RTA), in which we validate at run time that a WSN will function correctly, despite any changes to the operating conditions since it was originally designed and deployed. We use program analysis and compiler techniques to facilitate automated testing of a WSN at run time. As a proof of concept, we implemented a framework for designing and automatically testing WSN applications. We evaluate our implementation on a network of 21 TelosB nodes, and compare performance with an existing network health monitoring solution. Our results indicate that in addition to providing the application-level verification function, RTA misses 75% fewer system failures, produces 70% fewer maintenance dispatches, and incurs 33% less messaging overhead than network health monitoring.

Breadcrumb systems (BCS) have been proposed to aid firefighters inside buildings by communicating their physiological parameters to base stations outside the buildings. In this paper, we describe the design, implementation and evaluation of an automatic and robust breadcrumb system for firefighter applications. Our solution includes a breadcrumb dispenser with an optimized link estimator that is used to decide when to deploy breadcrumbs to maintain reliable wireless connectivity. The solution includes accounting for realities of buildings and dispensing such as the height difference between where the dispenser is worn and the floor where the dispensed nodes are found. We also include adaptive power management to maintain link quality over time.

This paper describes the design and implementation of a pervasive computing framework, named Physicalnet. Essentially, Physicalnet is a generic paradigm for managing and programming world-wide distributed heterogeneous sensor and actuator resources in a multi-user and multi-network environment. Using a four-tier light-weight service oriented architecture, Physicalnet enables global uniform access to heterogeneous resources and decouples applications from particular resources, locations and networks. Through a negotiator module, it allows a large number of applications to concurrently execute on the same resources and to span multiple physical networks and logical administrative domains. By providing a fine-grained use-based access rights control and conflict resolution mechanism, Physicalnet not only ensures owners having total control of sharing and protecting their resources, but also dramatically increases the number of applications that can concurrently execute on the devices. Furthermore, Physicalnet supports resource dynamic location-aware mobility, application run-time reconfigurability and on-the-fly access rights specification. To quantify the performance, we evaluate Physicalnet based on memory usage, the number of concurrent applications, and dynamic responsiveness. The results show Physicalnet has excellent performance, but low overheads.

Heating, ventilation and cooling (HVAC) is the largest source of residential energy consumption. In this paper, we demonstrate how to use cheap and simple sensing technology to automatically sense occupancy and sleep patterns in a home, and how to use these patterns to save energy by automatically turning off the home's HVAC system. We call this approach the smart thermostat. We evaluate this approach by deploying sensors in 8 homes and comparing the expected energy usage of our algorithm against existing approaches. We demonstrate that our approach will achieve a 28% energy saving on average, at a cost of approximately $25 in sensors. In comparison, a commercially-available baseline approach that uses similar sensors saves only 6.8% energy on average, and actually increases energy consumption in 4 of the 8 households.

In many applications of wireless sensor networks, sensor nodes are manually deployed in hostile environments where an attacker can disrupt the localization service and tamper with legitimate in-network communication. In this paper, we introduce Secure Walking GPS, a secure localization and key distribution solution for manual deployments of WSNs. Using the location information provided by the GPS and inertial guidance modules on a special master node, Secure Walking GPS achieves accurate node localization and location-based key distribution at the same time. Our analysis and simulation results indicate that the Secure Walking GPS scheme makes a deployed WSN resistant to the Dolev-Yao, the wormhole, and the GPS-denial attacks, has good localization and key distribution performance, and is practical for large-scale WSN deployments.

Driven by the confluence between the need to collect data about people's physical, physiological, psychological, cognitive, and behavioral processes in spaces ranging from personal to urban and the recent availability of the technologies that enable this data collection, wireless sensor networks for healthcare have emerged in the recent years. In this review, we present some representative applications in the healthcare domain and describe the challenges they introduce to wireless sensor networks due to the required level of trustworthiness and the need to ensure the privacy and security of medical data. These challenges are exacerbated by the resource scarcity that is inherent with wireless sensor network platforms. We outline prototype systems spanning application domains from physiological and activity monitoring to large-scale physiological and behavioral studies and emphasize ongoing research challenges.

Multifrequency media access control has been well understood in general wireless ad hoc networks, while in wireless sensor networks, researchers still focus on single frequency solutions. In wireless sensor networks, each device is typically equipped with a single radio transceiver and applications adopt much smaller packet sizes compared to those in general wireless ad hoc networks. Hence, the multifrequency MAC protocols proposed for general wireless ad hoc networks are not suitable for wireless sensor network applications, which we further demonstrate through our simulation experiments. In this article, we propose MMSN, which takes advantage of multifrequency availability while, at the same time, takes into consideration the restrictions of wireless sensor networks. In MMSN, four frequency assignment options are provided to meet different application requirements. A scalable media access is designed with efficient broadcast support. Also, an optimal nonuniform back-off algorithm is derived and its lightweight approximation is implemented in MMSN, which significantly reduces congestion in the time synchronized media access design. Through extensive experiments, MMSN exhibits the prominent ability to utilize parallel transmissions among neighboring nodes. When multiple physical frequencies are available, it also achieves increased energy efficiency, demonstrating the ability to work against radio interference and the tolerance to a wide range of measured time synchronization errors.

QeDB is a database for data-intensive real-time applications running on flash memory-based embedded systems.Currently, databases for embedded systems are best effort,providing no guarantees on its timeliness and data freshness. Moreover, the existing real-time database (RTDB) technology can not be applied to these embedded databases since they hypothesize that the main memory of a system is large enough to hold all database, which can not be true in data-intensive real-time applications. QeDB uses a novel feedback control scheme to support QoS in such embedded systems without requiring all data to reside in main memory.In particular, our approach is based on simultaneous control of both I/O and CPU resource to guarantee the desired timeliness. Unlike existing work on feedback control of RTDB performance, we actually implement and evaluate the proposed scheme in a modern embedded system.The experimental results show that our approach supports the desired timeliness of transactions while still maintaining high data freshness compared to baseline approaches.

Many applications in wireless sensor networks require communication performance that is both consistent and high quality. Unfortunately, performance of current network protocols can vary significantly because of various interferences and environmental changes. Current protocols estimate link quality based on the reception of probe packets over a short time period. This method is neither efficient nor accurate enough to capture the dramatic variations of link quality. Therefore, we propose a link metric called competence that characterizes links over a longer period of time. We combine competence with current short term estimations in routing algorithm designs. To further improve network performance we have designed a distributed route maintenance framework based on feedback control solutions. In real system evaluations with 48 T-Motes, our overall solution improves end-to-end packet delivery ratio over existing solutions by up to 40%, while reducing energy consumption by up to 22%. Importantly, our solution also achieves more stable and better transient performance than current approaches.

It is a challenging task to provide timely access to global data from sensors in large-scale sensor network applications. Current data storage architectures for sensor networks have to make trade-offs between timeliness and scalability. PRIDE is a data abstraction layer for 2-tier sensor networks, which enables timely access to global data from the sensor tier to all participating nodes in the upper storage tier. The design of PRIDE is heavily influenced by collaborative real-time applications such as search-and-rescue tasks for high-rise building fires, in which multiple devices have to collect and manage data streams from massive sensors in cooperation. PRIDE achieves scalability, timeliness, and flexibility simultaneously for such applications by combining a model-driven full replication scheme and adaptive data quality control mechanism in the storage-tier. We show the viability of the proposed solution by implementing and evaluating it on a large-scale 2-tier sensor network testbed. The experiment results show that the model-driven replication provides the benefit of full replication in a scalable and controlled manner.

The current rapid development and deployment of wireless sensor networks (WSNs) and their application in mission critical systems are exacerbating the need for high confidence WSNs. Achieving high confidence WSNs will require new assurance technologies. Most current solutions deal with faults and reliability and not with application level semantics and associated assurances. We propose the use of a novel WSN design and assurance mechanism, run time assurance (RTA), to guarantee that important application-level requirements are met in mission critical applications.

Simultaneous transmissions in the same radio range of a wireless sensor network causes interference and packets are lost. Knowing the interference pattern in advance, the transmission links can be scheduled so that no packet is lost due to interference and all streams meet their deadlines. This problem is NP-hard in general and therefore we resort to heuristics. In this paper, we present a set of heuristics for scheduling periodic, real-time data streams over a wireless sensor network. Simulation results show that our heuristics produce feasible schedules in almost all cases.

Physicalnet is a fully implemented middleware for wireless networks of sensors and actuators (WNSAs). Based on a lightweight service oriented architecture (SOA), Physicalnet allows the users to create administrative domains, in which owners of the nodes can share and protect their resources so that multiple applications can simultaneously use the same sensors and actuators with conflict resolution mechanisms. By using a general programming abstraction, named bundle, Physicalnet allows programming across networks and administrative domains, and has a good support for node mobility. Other features of Physicalnet include using the Java language, supporting heterogeneous devices, and providing a chain of user tools.

This article presents the design, implementation, and evaluation of EnviroMic , a low-cost experimental prototype of a novel distributed acoustic monitoring, storage, and trace retrieval system designed for disconnected operation. Our intended use of acoustic monitoring is to study animal populations in the wild. Since a permanent connection to the outside world is not assumed and due to the relatively large size of audio traces, the system must optimally exploit available resources such as energy and network storage capacity. Towards that end, we design, prototype, and evaluate distributed algorithms for coordinating acoustic recording tasks, reducing redundancy of data stored by nearby sensors, filtering out silence, and balancing storage utilization in the network. For experimentation purposes, we implement EnviroMic on a TinyOS-based platform and systematically evaluate its performance through both indoor testbed experiments and an outdoor deployment. Results demonstrate up to a four-fold improvement in effective storage capacity of the network compared to uncoordinated recording.

Energy efficiency is a fundamental issue for outdoor sensor network systems. This article presents the design and implementation of multidimensional power management strategies in VigilNet, a major recent effort to support long-term surveillance using power-constrained sensor devices. A novel tripwire service is integrated with an effective sentry and duty cycle scheduling in order to increase the system lifetime, collaboratively. The tripwire service partitions a network into distinct, nonoverlapping sections and allows each section to be scheduled independently. Sentry scheduling selects a subset of nodes, the sentries, which are turned on while the remaining nodes save energy. Duty cycle scheduling allows the active sentries themselves to be turned on and off, further lowering the average power draw. The multidimensional power management strategies proposed in this article were fully implemented within a real sensor network system using the XSM platform. We evaluate key system parameters using a network of 200 XSM nodes in an outdoor environment, and an analytical probabilistic model. We evaluate network lifetime using a simulation of a 10,000-node network that uses measured XSM power values. These evaluations demonstrate the effectiveness of our integrated approach and identify a set of lessons and guidelines, useful for the future development of energy-efficient sensor systems. One of the key results indicates that the combination of the three presented power management techniques is able to increase the lifetime of a realistic network from 4 days to 200 days.

In this paper, we first present a new privacy leak in residential wireless ubiquitous computing systems, and then we propose guidelines for designing future systems to prevent this problem. We show that we can observe private activities in the home such as cooking, showering, toileting, and sleeping by eavesdropping on the wireless transmissions of sensors in a home, even when all of the transmissions are encrypted. We call this the Fingerprint and Timing-based Snooping (FATS) attack. This attack can already be carried out on millions of homes today, and may become more important as ubiquitous computing environments such as smart homes and assisted living facilities become more prevalent. In this paper, we demonstrate and evaluate the FATS attack on eight different homes containing wireless sensors. We also propose and evaluate a set of privacy preserving design guidelines for future wireless ubiquitous systems and show how these guidelines can be used in a hybrid fashion to prevent against the FATS attack with low implementation costs.

In this paper, we analyze the performance of group based detection in sparse sensor networks, when the system level detection decision is made based on the detection reports generated from multiple sensing periods. Sparse deployment is essential for reducing cost of large scale sensor networks, which cover thousands of square miles. In a sparse deployment, the sensor field is only partially covered by sensorspsila sensing ranges, resulting in void sensing areas in the region, but all nodes are connected through multi-hop networking. Further, due to the unavoidable false alarms generated by a single sensor in a network, many deployed systems use group based detection to reduce system level false alarms. Despite the popularity of group based detection, few analysis works in the literature deal with group based detection. In this paper, we propose a novel approach called Markov chain based Spatial approach (MS-approach) to model group based detection in sensor networks. The M-S-approach successfully overcomes the complicated conditional detection probability of a target in each sensing period, and reduces the execution time of the analysis from many days to 1 minute. The analytical model is validated through extensive simulations. This analytical work is important because it provides an easy way to understand the performance of a system that uses group based detection without running countless simulations or deploying real systems.

In this paper, we advocate asymmetric function placement as one of guiding principles to architect sensor network systems. We demonstrate its generic applicability and effectiveness by applying this principle to three typical sensor network technologies, namely, localization (Spotlight), sensing (uSense) and communication (mNets). These technologies have very dissimilar features, representing a wide spectrum of system design requirements. We have invested significant effort to design, implement and evaluate our techniques on TinyOS/Mote testbeds. The results from several running systems indicate that asymmetric function placement is a powerful guiding principle to achieveefficiencyandhigh-performancesimultaneously in wireless sensor networks. At the end, we exam the system features that discourage the use of asymmetric function placement and approaches to address them.

This paper demonstrates how to use multiple channels to improve communication performance in Wireless Sensor Networks (WSNs). We first investigate multi-channel realities in WSNs through intensive empirical experiments with Micaz motes. Our study shows that current multi-channel protocols are not suitable for WSNs, because of the small number of available channels and unavoidable time errors found in real networks. With these observations, we propose a novel tree-based multichannel scheme for data collection applications, which allocates channels to disjoint trees and exploits parallel transmissions among trees. In order to minimize interference within trees, we define a new channel assignment problem which is proven NP- complete. Then we propose a greedy channel allocation algorithm which outperforms other schemes in dense networks with a small number of channels.We implement our protocol, called TMCP, in a real testbed. Through both simulation and real experiments, we show that TMCP can significantly improve network throughput and reduce packet losses. More importantly, evaluation results show that TMCP better accommodates multi-channel realities found in WSNs than other multi-channel protocols.

As wireless devices and sensors are increasingly deployed on people, researchers have begun to focus on wireless body-area networks. Applications of wireless body sensor networks include healthcare, entertainment, and personal assistance, in which sensors collect physiological and activity data from people and their environments. In these body sensor networks, quality of service is needed to provide reliable data communication over prioritized data streams. This paper proposes BodyQoS, the first running QoS system demonstrated on an emulated body sensor network. BodyQoS adopts an asymmetric architecture, in which most processing is done on a resource rich aggregator, minimizing the load on resource limited sensor nodes. A virtual MAC is developed in BodyQoS to make it radio-agnostic, allowing a BodyQoS to schedule wireless resources without knowing the implementation details of the underlying MAC protocols. Another unique property of BodyQoS is its ability to provide adaptive resource scheduling. When the effective bandwidth of the channel degrades due to RF interference or body fading effect, BodyQoS adaptively schedules remaining bandwidth to meet QoS requirements. We have implemented BodyQoS in NesC on top of TinyOS, and evaluated its performance on MicaZ devices. Our system performance study shows that BodyQoS delivers significantly improved performance over conventional solutions in combating channel impairment.

This paper presents LiteOS, a multi-threaded operating system that provides Unix-like abstractions for wireless sensor networks. Aiming to be an easy-to-use platform, LiteOS offers a number of novel features, including: (1) a hierarchical file system and a wireless shell interface for user interaction using UNIX-like commands; (2) kernel support for dynamic loading and native execution of multithreaded applications; and (3) online debugging, dynamic memory, and file system assisted communication stacks. LiteOS also supports software updates through a separation between the kernel and user applications, which are bridged through a suite of system calls. Besides the features that have been implemented, we also describe our perspective on LiteOS as an enabling platform. We evaluate the platform experimentally by measuring the performance of common tasks, and demonstrate its programmability through twenty-one example applications.

We demonstrate MetroNet, which is an application that illustrates collaborative data sharing on the Wide Wide Web. MetroNet has two parts. First, our sensors gather data about pedestrian foot traffic in front of and into stores, which is made available online to shopkeepers. Second, this sensor data can be made public, at the discretion of the shopkeeper, for use by city planners, other shopkeepers, or residents of the city. MetroNet is an application through which we study fundamental problems of sharing data on the Web, such as search, data fusion, and privacy.

Sensor networks have been used in many surveillance systems, providing statistical information about monitored areas. Accurate counting information (e.g., the distribution of the total number of targets) is often important for decision making. As a complementary solution to double-counting in communication, this paper presents the first work that deals with double-counting in sensing for wireless sensor networks. The probability mass function (pmf) of target counts is derived first. This, however, is shown to be computationally prohibitive when a network becomes large. A partitioning algorithm is then designed to significantly reduce computation complexity with a certain loss in counting accuracy. Finally, two methods are proposed to compensate for the loss. To evaluate the design, we compare the derived probability mass function with ground truth obtained through exhaustive enumeration in small-scale networks. In large-scale networks, where pmf ground truth is not available, we compare the expected count with true target counts. We demonstrate that accurate counting within 1 ∼ 3% relative error can be achieved with orders of magnitude reduction in computation, compared with an exhaustive enumeration-based approach.

The demand for real-time data services in embedded systems is increasing. In these new computing platforms, using traditional buffer management schemes, whose goal is to minimize the number of I/O operations, is problematic since they do not consider the constraints of those platforms such as limited energy and distinctive underlying storage. In particular, due to asymmetric read/write characteristic of flash memory, minimum buffer misses neither coincide with minimum power consumption nor minimum I/O deadline miss ratio. In this paper we propose a power-aware buffer cache management scheme for real-time databases whose secondary storage is a flash memory. We focus on the problem of guaranteeing the performance goal in terms of both I/O power consumption and I/O deadline miss ratio. To address this problem, we propose logical partitioning of the global buffer pool into read and write buffer pools, and dynamic feedback control of read/write buffer pool sizes to satisfy both performance goals. We have shown through an extensive evaluation that our approach satisfies both performance goals in a variety of workloads and access patterns with considerably smaller size of buffer pools compared to baseline approaches.

Effective debugging usually involves watching program state to diagnose bugs. When debugging sensor network applications, this approach is often time-consuming and errorprone, not only because of the lack of visibility into system state, but also because of the difficulty to watch the right variables at the right time. In this paper, we present declarative tracepoints, a debugging system that allows the user to insert a group of action-associated checkpoints, or tracepoints, to applications being debugged at runtime. Tracepoints do not require modifying application source code. Instead, they are written in a declarative, SQL-like language called TraceSQL independently. By triggering the associated actions when these checkpoints are reached, this system automates the debugging process by removing the human from the loop. We show that declarative tracepoints are able to express the core functionality of a range of previously isolated debugging techniques, such as EnviroLog, NodeMD, Sympathy, and StackGuard. We describe the design and implementation of the declarative tracepoints system, evaluate its overhead in terms of CPU slowdown, illustrate its expressiveness through the aforementioned debugging techniques, and finally demonstrate that it can be used to detect real bugs using case studies of three bugs based on the development of the LiteOS operating system.

Traditional fall detection is only based on acceleration analysis. In this work we present a novel fall detection method that also utilizes posture and context information. This information can help reduce both false positives and negatives. Our solution also strives for low computational cost and fast response.

Extensive empirical results reveal that interference can cause link qualities to change quickly and dramatically. For such highly dynamic links, the short term link quality estimations widely used in existing protocols require frequent measurements and may not be accurate. As a result, when these links are selected, end-to-end communication quality varies significantly. Also, route changes occur frequently, introducing traffic oscillation and excessive overhead in network protocols. To achieve good and stable network performance, it is not enough to use short term link estimation. It is essential to characterize a link's capacity to perform well at a desired level in the presence of interference and environmental changes. Therefore, we propose a performance metric called competence. We have incorporated the competence metric into routing algorithm designs. We have also designed and implemented a maintenance framework that stabilizes performance at both link and network layers. This framework allocates the desired performance level among multiple links along an active route by using an end-to-end feedback loop, and enforces the performance level of each link through adaptive transmission power control and retransmission control. In real system evaluations with 48 TMotes, our solution outperforms previous protocols significantly and achieves end-to-end stable performance for more than 99% of the time over 24 hours.

No abstract available.

For many sensor network applications, such as military surveillance, it is necessary to provide full sensing coverage to a security-sensitive area while, at the same time, minimizing energy consumption and extending system lifetime by leveraging the redundant deployment of sensor nodes. In this paper, we propose a surveillance service for sensor networks based on a distributed energy-efficient sensing coverage protocol. In the protocol, each node is able to dynamically decide a schedule for itself to guarantee a certain degree-of-coverage (DOC) with average energy consumption inversely proportional to the node density. Several optimizations and extensions are proposed to enhance the basic design with a better load-balance feature and a longer network lifetime. We consider and address the impact of the target size and the unbalanced initial energy capacity of individual nodes to the network lifetime. Several practical issues such as the localization error, irregular sensing range, and unreliable communication links are addressed as well. Simulation shows that our protocol extends system lift-time significantly with low energy consumption. It outperforms other state-of-the-art schemes by as much as 50% reduction in energy consumption and as much as 130% increase in the half-life of the network.

In this paper, we examine at-home activity rhythms and present a dozen of behavioral patterns obtained from an activity monitoring pilot study of 22 residents in an assisted living setting with four case studies. Established behavioral patterns have been captured using custom software based on a statistical predictive algorithm that models circadian activity rhythms (CARs) and their deviations. The CAR was statistically estimated based on the average amount of time a resident spent in each room within their assisted living apartment, and also on the activity level given by the average number of motion events per room. A validated in-home monitoring system (IMS) recorded the monitored resident's movement data and established the occupancy period and activity level for each room. Using these data, residents' circadian behaviors were extracted, deviations indicating anomalies were detected, and the latter were correlated to activity reports generated by the IMS as well as notes of the facility's professional caregivers on the monitored residents. The system could be used to detect deviations in activity patterns and to warn caregivers of such deviations, which could reflect changes in health status, thus providing caregivers with the opportunity to apply standard of care diagnostics and to intervene in a timely manner.

This work presents a TDMA based multi-channel MAC protocol called TMMAC for Ad Hoc Networks. TMMAC requires only a single half-duplex radio transceiver on each node. In addition to explicit frequency negotiation which is adopted by conventional multi-channel MAC protocols, TMMAC introduces lightweight explicit time negotiation. This two-dimensional negotiation enables TMMAC to exploit the advantage of both multiple channels and TDMA, and achieve aggressive power savings by allowing nodes that are not involved in communication to go into doze mode. Moreover, TMMAC dynamically adjusts its negotiation window size based on different traffic patterns, which further improves communication throughput and energy savings. In this paper, the performance of TMMAC is analyzed and evaluated. The evaluations show that TMMAC achieves up to 113% higher communication throughput while consuming 74% less per packet energy over the state-of-the-art multi-channel MAC protocols for single-transceiver wireless devices.

This paper presents EnviroMic, a novel distributed acoustic monitoring, storage, and trace retrieval system. Audio represents one of the least exploited modalities in sensor networks to date. The relatively high frequency and large size of audio traces motivate distributed algorithms for coordinating recording tasks, reducing redundancy of data stored by nearby sensors, filtering out silence, and balancing storage utilization in the network. Applications of acoustic monitoring with EnviroMic range from the study of mating rituals and social behavior of animals in the wild to audio surveillance of military targets. EnviroMic is designed for disconnected operation, where the luxury of having a basestation cannot be assumed. We implement the system on a Tiny OS-based platform and systematically evaluate its performance through both indoor testbed experiments and a preliminary outdoor deployment. Results demonstrate up to a 4-fold improvement in effective storage capacity of the network compared to uncoordinated recording.

This paper presents a new cooperative storage system for sensor networks geared for disconnected operation (where sensor nodes do not have a connected path to a basestation). The goal of the system is to maximize its data storage capacity by appropriately distributing storage utilization and opportunistically offloading data to external devices when possible. The system is motivated by the observation that a large category of sensor network applications, such as environmental data logging, does not require real-time data access. Such networks generally operate in a disconnected mode. Rather than focusing on multihop routing to a basestation, an important concern becomes (i) to maximize the effective storage capacity of the disconnected sensor network such that it accommodates the most data, and (ii) to take the best advantage of data upload opportunities when they become available to relieve network storage. The storage system described in this paper achieves the above goals, leading to significant improvements in the amount of data collected compared to non-cooperative storage. It is implemented in nesC for TinyOS and evaluated in TOSSIM through various application scenarios.

No abstract available.

Recently, cheap and large capacity non-volatile memory such as flash memory is rapidly replacing disks in embedded systems. While the access time of flash memory is highly predictable, deadline misses may occur if data objects in flash memory are not properly managed in real-time embedded databases. Buffer cache can be used to mitigate this problem. However, since the workload of a real-time database cannot be precisely predicted, it may not be feasible to provide enough buffer space to satisfy all timing constraints. Several deadline miss ratio management schemes have been proposed, but they do not consider I/O activities. In this paper, we present an I/O-aware deadline miss ratio management scheme in real-time embedded databases whose secondary storage is flash memory. We propose an adaptive I/O deadline assignment scheme, in which I/O deadlines are derived from up-to-date system status. We also present a deadline miss ratio management architecture where a control theory-based feedback control loop prevents resource overload both in I/O and CPU. A simulation study shows that our approach can effectively cope with both I/O and CPU overload to achieve the desired deadline miss ratio.

We have developed an analysis-based design tool, ANDES, for modeling a wireless sensor network system and analyzing its performance before deployment ANDES enables designers to systematically develop a model for the system, refine it iteratively by tuning the system parameters based on existing analysis techniques, and resolve key design decisions according to the required system performance. We also present a real-time communication schedulability analysis for sensor networks based on exact characterization which utilizes information regarding network topology and workload characteristics to analyze the schedulability of a set of periodic streams with real-time constraints. We further demonstrate the use of ANDES for the designers through detailed case studies where we design wireless sensor network applications (for target detection and environmental monitoring) using ANDES and validate the results through simulations. Currently, ANDES supports communication schedulability analysis, target tracking analysis and real-time capacity analysis which work on system models with differing levels of detail. ANDES has been developed by extending the AADL/OSATE framework which has been used extensively for real-time and embedded systems. Based on key insights gained from the development of this analysis tool, we address issues in AADL for its use in the field of wireless sensor networks. We have developed a plug-in for ANDES, called ModelGeneration, which bridges the gap between the semantics needed for sensor networks and the syntax supported by AADL. This makes it easy for sensor network designers to build system models that are intuitive to them. Furthermore, ANDES is extensible and new analysis techniques can be easily incorporated into the toolset.

This demonstration highlights an interactive Unix-like shell for operating wireless sensor networks, where the user uses familiar Unix commands to complete tasks ranging from wireless installation of user applications to retrieval of data reports with the help of a built-in Unix-like file system.

Environmental wireless sensor network (EWSN) systems are deployed in potentially harsh and remote environments where inevitable node and communication failures must be tolerated. LUSTER---Light Under Shrub Thicket for Environmental Research---is a system that meets the challenges of EWSNs using a hierarchical architecture that includes distributed reliable storage, delay-tolerant networking, and deployment time validation techniques.

In this paper we address three challenges that are present when building and analyzing wireless sensor networks (WSN) as part of ubiquitous computing environment: the need for an in-situ user interface, a data logger, and a power consumption meter. Solutions for the above have been presented using laptops, personal digital assistants (PDA), onboard flash memory chips of limited size (usually 1MB), and laboratory test equipment. All of them have a good utility for the right applications. However, considering a certain variety of WSNs, where size, battery life, and cost are crucial, none of the above solutions is satisfactory. In this paper we present a compact, lightweight, low power, and low cost multimodal sensor module SeeMote that meets the stated challenges, and is compatible with the popular MICAz mote. Our module has the following components: (1) a graphical user interface component that combines a color liquid crystal display (LCD) and 5-way buttons, (2) a power meter component that is reconfigurable for attaching various low-power devices, and (3) a data logger component that is interfaced to a removable secure digital (SD) or multimedia memory card (MMC). The module dimensions are 34times58times12 mm. This paper describes the hardware and software design and experiences while developing and using the device. The device is evaluated by comparing its parameters and functionality to laptop and PDA solutions. We conclude that SeeMote is preferred for certain WSNs, such as very large scale, difficult to reach, and wearable WSNs. We also present several applications that use the LCD module, such as the portable frequency spectrum analyzer and remote sensory data display device.

With the emergence of high data rate sensor net-work applications, there is an increasing demand for high-performance query services in such networks. To meet this challenge, we propose Dynamic Conflict-free Query Scheduling (DCQS), a novel scheduling technique for queries in wireless sensor networks. In contrast to earlier TDMA protocols designed for general-purpose networks and workloads, DCQS is specifically designed for query services supporting in-network data aggregation. DCQS has several important features. First, it optimizes the query performance and energy efficiency by exploiting the temporal properties and precedence constraints introduced by data aggregation. Second, it can efficiently adapt to dynamic workloads and rate changes without explicitly reconstructing the transmission schedule. In addition, we provide an analytical capacity bound for DCQS in terms of query completion rate. This bound enables DCQS to handle overload through rate control. NS2 simulation results demonstrate that DCQS significantly outperforms a representative TDMA protocol (DRAND) and the 802.11 protocol in terms of query latency, throughput, and energy efficiency.

Recent studies on radio reality provided strong evidence that radio links between low-power sensor devices are extremely unreliable. In this paper, we study how to improve energy efficiency for reliable communication using such unreliable links. We identify an optimal bound on energy efficiency for reliable communication, and propose a new communication model in the link layer that asymptotically approaches this bound. This new model indicates a better path metric compared to previous path metrics, and we validate this by establishing a routing infrastructure based on this metric, which indeed achieves a higher energy efficiency compared to other stateof -the-art approaches. We present results from a systematic analysis, simulations and prototype experiments based on the MicaZ platform. The results give us fundamental insights on communication efficiency over unreliable links.

Abstract — Energy efficiency is a fundamental issue for out-door sensor network systems. This paper presents the design and implementation of multi-dimensional power management strategies in VigilNet, a major recent effort to support long-term surveillance using power-constrained sensor devices. We integrate a novel tripwire service with an effective sentry and duty cycle scheduling in order to increase the system lifetime, collaboratively. Through extensive system implementation, we demonstrate the feasibility to achieve high surveillance perfor-mance and energy efficiency, simultaneously. We invest a fair amount of effort to evaluate our architecture with a network of 200 XSM motes in an outdoor environment, an extensive simulation with 10,000 nodes, as well as an analytical probabilistic model. These evaluations demonstrate the effectiveness of our integrated approach and identify many interesting lessons and guidelines, useful for the future development of energy-efficient sensor systems. I.

Abstract — Sensing events from dynamic environments are normally asynchronous and non-repeatable. This lack of repeatability makes it particularly difficult to statistically evaluate the performance of sensor network applications. Hence, it is essential to have the capability to capture and replay sensing events, providing a basis not only for system evaluation, but also for realistic protocol comparison and parameter tuning. To achieve that, we design and implement EnviroLog, a distributed service that improves repeatability of experimental testing of sensor networks via asynchronous event recording and replay. To use EnviroLog, an application programmer needs only to specify two types of simple annotations to the source code. Automatically, the preprocessor embeds EnviroLog into any desired level of an event-driven architecture. It records all events generated by lower layers and can replay them later to upper layers on demand. We validate the accuracy and performance of recording and replay through a set of microbenchmarks, using the latest XSM platforms. We further demonstrate the strength of EnviroLog in system tuning and performance evaluation for sensor network applications in an outdoor environment with 37 XSMs. I.

Abstract — Multi-frequency media access control has been well understood in general wireless ad hoc networks, while in wireless sensor networks, researchers still focus on single frequency solutions. In wireless sensor networks, hardware devices are equipped with very limited communication ability and applications adopt much smaller packet sizes compared to those in general wireless ad hoc networks. Hence, the multi-frequency MAC protocols proposed for general wireless ad hoc networks are not suitable for wireless sensor network applications, which we further demonstrate through our simulation experiments. In this paper, we propose MMSN, the first multi-frequency MAC protocol for wireless sensor networks. In the MMSN protocol, four frequency assignment options are provided to meet different application requirements. A scalable media access is designed with efficient broadcast support. Also, an optimal non-uniform backoff algorithm is derived and its lightweight approximation is implemented in MMSN, which significantly reduces congestion in the time synchronized media access design. Through extensive experiments, MMSN exhibits prominent ability to utilize parallel transmission among neighboring nodes. It also achieves increased energy efficiency when multiple physical frequencies are available. I.

Since sensor nodes normally have limited resources in terms of energy, bandwidth and computation capability, efficiency is a key design goal in sensor network research. As one of techniques to achieve efficiency, data aggregation has been extensively investigated in recent literature. Previous research on data aggregation has demonstrated its effectiveness in reducing traffic, easing congestion and decreasing the energy consumption. However few are actually designed for a real-world application and implemented in a running system. This paper describes our design and implementation of a physical tracking system, using an aggressive data aggregation architecture as one of building blocks. This architecture can be generally applied to other sensor systems, where communication efficiency is a paramount concern and networking resources are limited.

Many real-time applications, such as traffic control systems, surveillance systems and health monitoring systems, need to operate on continuous unbounded streams of data. These applications also have inherent real-time performance requirements that have to be met under high-volume, time-varying incoming data streams. In this paper, we present a real-time data stream query model named PQuery, which provides periodic real-time queries on data streams for the aforementioned real-time applications. To support the PQuery model, a real-time data stream management prototype system named RTSTREAM is developed to provide deadline miss ratio guarantees for periodic queries over continuous and unbounded data streams. We describe the periodic query semantics and discuss why the periodic query model is appropriate for real-time applications. To handle irregular data arrival patterns and query workloads, we propose data admission as an overload protection mechanism. We conduct performance studies with synthetic workloads as well as real workloads from network traffic monitoring applications. The experimental results show that the proposed periodic query model suits the need of the real-time applications and the data admission overload protection approach is effective in managing the workload fluctuations.

Many wireless sensor network applications must resolve the inherent conflict between energy efficient communication and the need to achieve desired quality of service such as end-to-end communication delay. To address this challenge, we propose the Real-time Power-Aware Routing (RPAR) protocol, which achieves application-specified communication delays at low energy cost by dynamically adapting transmission power and routing decisions. RPAR features a power-aware forwarding policy and an efficient neighborhood manager that are optimized for resource-constrained wireless sensors. Moreover, RPAR addresses important practical issues in wireless sensor networks, including lossy links, scalability, and severe memory and bandwidth constraints. Simulations based on a realistic radio model of MICA2 motes show that RPAR significantly reduces the number of deadlines missed and energy consumption compared to existing real-time and energy-efficient routing protocols.

Wireless sensor networks (WSN) composed of large numbers of small devices that self-organize are being investigated for a wide variety of applications. Two key advantages of these networks over more traditional sensor networks are that they can be dynamically and quickly deployed, and that they can provide fine-grained sensing. Applications, such as emergency response to natural or manmade disasters, detection and tracking, and fine grained sensing of the environment are key examples of applications that can benefit from these types of WSN. Current research for these systems is widespread. However, many of the proposed solutions are developed with simplifying assumptions about wireless communication and the environment, even though the realities of wireless communication and environmental sensing are well known. Many of the solutions are evaluated only by simulation. In this talk I describe a fully implemented system consisting of a suite of more than 30 synthesized protocols. The system supports a power aware surveillance, tracking and classification application running on 203 XSM motes and evaluated in a realistic, large-area environment. Technical details and evaluations are presented. I end with a discussion of opportunities and problems for data mining related to WSN.

Personal instrumentation and monitoring services that collect and archive the physical activities of a user have recently been introduced for various medical, personal, safety, and entertainment purposes. A general software architecture is needed to support different categories of such monitoring services. This paper presents a software architecture, implementation, and preliminary evaluation of SATIRE, a wearable personal monitoring service transparently embedded in user garments. SATIRE records the owner's activity and location for subsequent automated uploading and archiving. The personal archive can later be searched for particular events to answer questions regarding past and present user activity, location, and behavior patterns. A short feasibility and usage study of a prototype based on MicaZ motes provides a proof of concept for the SATIRE architecture.

With the emergence of large wired and wireless sensor networks, many real-time applications need to operate on continuous unbounded data streams. At the same time, many of these systems have inherent timing constraints. Providing deadline guarantees for queries over dynamic data streams is a challenging problem due to bursty data stream arrival rates and time-varying stream contents. In this paper, we propose a prediction-based quality-of-service (QoS) management scheme for periodic queries over dynamic data streams. Our QoS management scheme features novel query workload estimators, which predict the query workload using execution time profiling and input data sampling, and adjusts the query QoS levels based on online query execution time prediction. We implement our QoS management algorithm on a real-time data stream query system prototype called RTStream. Our experimental evaluation of the scheme shows that our query workload estimator performs very well even with workload fluctuations and our QoS management scheme yields better overall system utility than the existing approaches for QoS management

The development of a reliable large-scale wireless sensor network (WSN) is very difficult because of resource constraints, energy budget, and demanding application requirements. Three OS features-OS protection, virtual memory, and preemptive scheduling-can significantly improve the reliability of WSN systems and facilitate developing complex WSN software. However, due to the lack of hardware support for privileged execution and address translation, it is impossible to implement these features with traditional OS design techniques. To solve this problem, we design a new OS kernel, the t-kernel, to perform extensive code modification at load time. The modified code and the OS work in a collaborative way supporting the aforementioned features. Having implemented the t-kernel on MICA2 motes, we evaluate its performance by measuring the overhead and execution speed. We analyze the CPU utilization of sensor network applications, and verify that, though CPU-bound tasks execute 1.5-3 times as long as in native mode, application performance under typical workloads does not noticeably degrade. The t-kernel significantly enhances developers' ability to design reliable and sophisticated sensor networks, and includes several new design techniques, such as efficient binary translation on highly constrained sensor nodes, differentiated virtual memory without repeatedly writable swapping devices, and the protection of the OS from application errors without privileged execution hardware.

No abstract available.

Extensive empirical studies presented in this paper confirm that the quality of radio communication between low power sensor devices varies significantly with time and environment. This phenomenon indicates that the previous topology control solutions, which use static transmission power, transmission range, and link quality, might not be effective in the physical world. To address this issue, online transmission power control that adapts to external changes is necessary. This paper presents ATPC, a lightweight algorithm of Adaptive Transmission Power Control for wireless sensor networks. In ATPC, each node builds a model for each of its neighbors, describing the correlation between transmission power and link quality. With this model, we employ a feedback-based transmission power control algorithm to dynamically maintain individual link quality over time. The intellectual contribution of this work lies in a novel pairwise transmission power control, which is significantly different from existing node-level or network-level power control methods. Also different from most existing simulation work, the ATPC design is guided by extensive field experiments of link quality dynamics at various locations and over a long period of time. The results from the real-world experiments demonstrate that 1) with pairwise adjustment, ATPC achieves more energy savings with a finer tuning capability and 2) with online control, ATPC is robust even with environmental changes over time.

The problem of localization in wireless sensor networks where nodes do not use ranging hardware, remains a challenging problem, when considering the required location accuracy, energy expenditure and the duration of the localization phase. In this paper we propose a framework, called StarDust, for wireless sensor network localization based on passive optical components. In the StarDust framework, sensor nodes are equipped with optical retro-reflectors. An aerial device projects light towards the deployed sensor network, and records an image of the reflected light. An image processing algorithmis developed for obtaining the locations of sensor nodes. For matching a node ID to a location we propose a constraint-based label relaxation algorithm. We propose and develop localization techniques based on four types of constraints: node color, neighbor information, deployment time for a node and deployment location for a node. We evaluate the performance of a localization system based on our framework by localizing a network of 26 sensor nodes deployed in a 120-60ft2 area. The localization accuracy ranges from 2 ft to 5 ft while the localization time ranges from 10 milliseconds to 2 minutes.

No abstract available.

Sensor networks open a new frontier for embedded-distributed computing. Paradigms for sensor network programming-in-the-large have been identified as a significant challenge toward developing large-scale applications. Classical programming languages are too low-level. This paper presents the design, implementation, and evaluation of EnviroSuite , a programming framework that introduces a new paradigm, called environmentally immersive programming , to abstract distributed interactions with the environment. Environmentally immersive programming refers to an object-based programming model in which individual objects represent physical elements in the external environment. It allows the programmer to think directly in terms of environmental abstractions. EnviroSuite provides language primitives for environmentally immersive programming that map transparently into a support library of distributed algorithms for tracking and environmental monitoring. We show how nesC code of realistic applications is significantly simplified using EnviroSuite and demonstrate the resulting system performance on Mica2 and XSM platforms.

This article describes one of the major efforts in the sensor network community to build an integrated sensor network system for surveillance missions. The focus of this effort is to acquire and verify information about enemy capabilities and positions of hostile targets. Such missions often involve a high element of risk for human personnel and require a high degree of stealthiness. Hence, the ability to deploy unmanned surveillance missions, by using wireless sensor networks, is of great practical importance for the military. Because of the energy constraints of sensor devices, such systems necessitate an energy-aware design to ensure the longevity of surveillance missions. Solutions proposed recently for this type of system show promising results through simulations. However, the simplified assumptions they make about the system in the simulator often do not hold well in practice, and energy consumption is narrowly accounted for within a single protocol. In this article, we describe the design and implementation of a complete running system, called VigilNet, for energy-efficient surveillance. The VigilNet allows a group of cooperating sensor devices to detect and track the positions of moving vehicles in an energy-efficient and stealthy manner. We evaluate VigilNet middleware components and integrated system extensively on a network of 70 MICA2 motes. Our results show that our surveillance strategy is adaptable and achieves a significant extension of network lifetime. Finally, we share lessons learned in building such an integrated sensor system.

In this article, we investigate the impact of radio irregularity on wireless sensor networks. Radio irregularity is a common phenomenon that arises from multiple factors, such as variance in RF sending power and different path losses, depending on the direction of propagation. From our experiments, we discover that the variance in received signal strength is largely random; however, it exhibits a continuous change with incremental changes in direction. With empirical data obtained from the MICA2 and MICAZ platforms, we establish a radio model for simulation, called the Radio Irregularity Model (RIM). This model is the first to bridge the discrepancy between the spherical radio models used by simulators and the physical reality of radio signals. With this model, we investigate the impact of radio irregularity on several upper layer protocols, including MAC, routing, localization and topology control. Our results show that radio irregularity has a relatively larger impact on the routing layer than the MAC layer. It also shows that radio irregularity leads to larger localization errors and makes it harder to maintain communication connectivity in topology control. To deal with these issues, we present eight solutions to deal with radio irregularity. We evaluate three of them in detail. The results obtained from both the simulations and a running testbed demonstrate that our solutions greatly improve system performance in the presence of radio irregularity.

This paper presents the design and implementation of an adaptive Web server architecture to provide relative and absolute connection delay guarantees for different service classes. The first contribution of this paper is an adaptive architecture based on feedback control loops that enforce desired connection delays via dynamic connection scheduling and process reallocation. The second contribution is the use of control theoretic techniques to model and design the feedback loops with desired dynamic performance. In contrast to heuristics-based approaches that rely on laborious hand-tuning and testing iteration, the control theoretic approach enables systematic design of an adaptive Web server with established analytical methods. The adaptive architecture has been implemented by modifying an Apache server. Experimental results demonstrate that the adaptive server provides robust delay guarantees even when workload varies significantly.

Tasks in many real-time applications can be scheduled by variations of rate monotonic or earliest deadline first algorithms. When this is possible, it is satisfying to have formal analysis and performance bounds underlying the use of these algorithms. However, in many applications the simultaneous set of constraints that must be satisfied makes these traditional solutions unsuitable. Practical solutions for these more complicated applications are important. In this paper we develop a novel integrated scheduling and allocation heuristic for a dual face phased array radar system. The realistic features of the radar system that must be simultaneously addressed include timeliness (worst case execution time, period, deadline), semantic importance, and physical constraints such as beam selection and frequency harmonics. The heuristic function we develop provides a very flexible way to incorporate these requirements into one single equation. Since scheduling high semantic importance tasks is paramount, we use the highest semantic importance tasks' success ratio as the major performance metric. Based on simulation results, we show that our static heuristic algorithm can schedule more than 91% of the highest semantic importance tasks at high frequency conflict degree even at heavy workloads. The result is 50% better than EDF and 31% better than an importance (IMP) based static priority scheduling algorithm where IMP is similar to various current approaches. For the online scheduling algorithm, our heuristic algorithm is 30% better than EDF and 20% better than IMP in terms of highest semantic importance tasks' success ratio at heavy workloads.

In wireless sensor networks, many protocols assume that if node A is able to interfere with node B's packet reception, node B is within node A's communication range. It is also assumed that if node B is within node A's communication range, node A is able to interfere with node B's packet reception from any transmitter. While these assumptions may be useful in protocol design, they are not valid, according to the real experiments we conducted in MICA2 platform. For a strong link that has a high packet delivery ratio, the interference range is observed smaller than the communication range, while for a weak link that has a low packet delivery ratio, the interference range is larger than the communication range. So using communication range information alone is not enough to design real collision-free media access control protocols. This paper presents a radio interference detection protocol (RID) and its variation (RID-B) to detect run-time radio interference relations among nodes. The interference detection results are used to design real collision-free TDMA protocols. With extensive simulations in GlomoSim, and with sensor network application scenarios, we observe that the TDMA which uses the interference detection results has 100% packet delivery ratio, while the traditional TDMA has packet loss up to 60%, in heavy load. In addition to the scheduling-based TDMA protocols, we also explore the application of interference detection on contention-based MAC protocols.

Lifetime maximization is one key element in the design of sensor-network-based surveillance applications. We propose a protocol for node sleep scheduling that guarantees a bounded-delay sensing coverage while maximizing network lifetime. Our sleep scheduling ensures that coverage rotates such that each point in the environment is sensed within some finite interval of time, called the detection delay. The framework is optimized for rare event detection and allows favorable compromises to be achieved between event detection delay and lifetime without sacrificing (eventual) coverage for each point. We compare different sleep scheduling policies in terms of average detection delay, and show that ours is closest to the detection delay lower bound for stationary event surveillance. We also explain the inherent relationship between detection delay, which applies to persistent events, and detection probability, which applies to temporary events. Finally, a connectivity maintenance protocol is proposed to minimize the delay of multi-hop delivery to a base-station. The resulting sleep schedule achieves the lowest overall target surveillance delay given constraints on energy consumption.

Battlefield surveillance often involves a high element of risk for military operators. Hence, it is very important for the military to execute unmanned surveillance by using large-scale wireless sensor systems. This invited paper summarizes the architecture of the VigilNet system - a long-term real-time networked sensor system for military surveillance. Specifically, we review the design of several major subsystems within VigilNet including sensing and classification, localization, tracking, networking, power management, reconfiguration, graphic user interface, and the debugging subsystem. High-level programming abstractions are also presented. This is a balanced design to achieve realtime response, high confidence detection, accurate tracking and energy efficiency simultaneously.

In this paper we present a balanced data replication scheme that provides real-time latency bounds on content retrieval in content distribution networks. Many network applications have ever-increasing requirements on latency sensitive data services. Data replication services have been widely used as an important performance enhancement mechanism to reduce data access latency and throughput. We investigate the problem of provisioning an underlying balanced data replication service to provide a global latency bound on data retrieval in content distribution networks. The solution involves constructing an overlay network based on the given latency bound, and a mechanism to assign content objects to the network nodes so that the workload of all the network nodes is balanced. Our evaluation results drawn from detailed simulations show the efficacy of our load-balancing scheme in meeting the latency bound requirements with high confidence under heavy load.

A wide variety of sensors have been incorporated into a spectrum of wireless sensor network (WSN) platforms, providing flexible sensing capability over a large number of low-power and inexpensive nodes. Traditional signal processing algorithms, however, often prove too complex for energy-and-cost-effective WSN nodes. This study explores how to design efficient sensing and classification algorithms that achieve reliable sensing performance on energy-and-cost effective hardware without special powerful nodes in a continuously changing physical environment. We present the detection and classification system in a cutting-edge surveillance sensor network, which classifies vehicles, persons, and persons carrying ferrous objects, and tracks these targets with a maximum error in velocity of 15%. Considering the demanding requirements and strict resource constraints, we design a hierarchical classification architecture that naturally distributes sensing and computation tasks at different levels of the system. Such a distribution allows multiple sensors to collaborate on a sensor node, and the detection and classification results to be continuously refined at different levels of the WSN. This design enables reliable detection and classification without involving high-complexity computation, reduces network traffic, and emphasizes resilience and adaptation to the realistic environment. We evaluate the system with performance data collected from outdoor experiments and field assessments. Based on the experience acquired and lessons learned when developing this system, we abstract common issues and introduce several guidelines which can direct future development of detection and classification solutions based on WSNs.

No abstract available.

The problem of localization of wireless sensor nodes has long been regarded as very difficult to solve, when considering the realities of real world environments. In this paper, we formally describe, design, implement and evaluate a novel localization system, called Spotlight. Our system uses the spatio-temporal properties of well controlled events in the network (e.g., light), to obtain the locations of sensor nodes. We demonstrate that a high accuracy in localization can be achieved without the aid of expensive hardware on the sensor nodes, as required by other localization systems. We evaluate the performance of our system in deployments of Mica2 and XSM motes. Through performance evaluations of a real system deployed outdoors, we obtain a 20cm localization error. A sensor network, with any number of nodes, deployed in a 2500m2 area, can be localized in under 10 minutes, using a device that costs less than $1000. To the best of our knowledge, this is the first report of a sub-meter localization error, obtained in an outdoor environment, without equipping the wireless sensor nodes with specialized ranging hardware.

Low-power embedded systems traditionally employ a "thin" OS because of resource constraints, hardware variety, and cost efficiency. This results in two problems - First, the embedded system programmers are limited to professionals with sufficient knowledge on hardware; Second, it is much slower for progress in programming languages and software engineering to find their ways to the systems with embedded microcontrollers, which is 98% of the microprocessors market. When low-power embedded processors are used in wireless sensor networks (WSNs), the thin OS approach, if followed, leads to another serious problem - The OS services cannot meet applications' ever-growing requirements. If these three problems are not solved, the transformation of the prosperous research on WSNs into a technology and market success has to be slow.

With the proliferation of location dependent applications in sensor networks, location awareness becomes an essential capability of sensor nodes. Because coarse accuracy is sufficient for most sensor network applications, solutions in range-free localization are being pursued as a cost-effective alternative to more expensive range-based approaches. In this paper, we present APIT, a novel localization algorithm that is range-free. We show that our APIT scheme performs best when an irregular radio pattern and random node placement are considered, and low communication overhead is desired. We compare our work, via extensive simulation, with three state-of-the-art range-free localization schemes to identify the preferable system configurations of each. In addition, we provide insight into the impact of localization accuracy on various location dependent applications and suggestions on improving their performance in the presence of such inaccuracy.

In this paper, we present a spatiotemporal communication protocol for sensor networks, called SPEED. SPEED is specifically tailored to be a localized algorithm with minimal control overhead. End-to-end soft real-time communication is achieved by maintaining a desired delivery speed across the sensor network through a novel combination of feedback control and nondeterministic geographic forwarding. SPEED is a highly efficient and scalable protocol for sensor networks where the resources of each node are scarce. Theoretical analysis, simulation experiments, and a real implementation on Berkeley motes are provided to validate the claims.

Aspect oriented programming (AOP), when used well, has many advantages. Aspects are however, programming-time constructs, i.e., they relate to source code. Previously, we developed a tool called VEST that extended aspects to design time for embedded systems. Two types of design time aspects were identified which we labeled aspect checks and prescriptive aspects. In the original VEST tool several keys aspect checks and a simple form of prescriptive aspects were implemented. Prescriptive aspects are extremely powerful and result in many design time advantages and uses. This paper enhances and exploits the concept of prescriptive aspects well beyond its original purpose and results. A new prescriptive language is developed and implemented in the VEST tool. We also use prescriptive aspects in a case study for an avionics application and evaluate its benefits. The result is a tool with significant and new features for building distributed real-time embedded systems. It is shown in the case study that design time is shortened by 69%.

Distributed sensor networks are quickly gaining recognition as viable embedded computing platforms. Current techniques for programming sensor networks are cumbersome, inflexible, and low-level. We introduce EnviroTrack, an object-based distributed middleware system that raises the level of programming abstraction by providing a convenient and powerful interface to the application developer geared towards tracking the physical environment. EnviroTrack is novel in its seamless integration of objects that live in physical time and space into the computational environment of the application. Performance results demonstrate the ability of the middleware to track realistic targets.

Web clusters continue to be widely used by large enterprises and organizations to host online services. Providing services without interruption is critical to the revenue and perceived image of both hosts and content providers. Therefore, server node failure and recovery should be invisible to the clients. Most of the existing fault-tolerance schemes simply stop dispatching future client requests to the failed server. They do not recover those connections handled by the node at the time of failure, which makes the failure visible to some clients. Making the failure transparent requires both application-layer and transport-layer mechanisms. While atomic application-layer primary-backup failover schemes have been addressed at length in previous literature, a transport-layer scheme is necessary in order to make them invisible to the clients. We describe a transparent TCP connection failover mechanism. Besides transparency, our solution is also highly efficient, and does not need any dedicated hardware support.

We present the design, implementation and evaluation of a simple, practical and cost effective localization solution, called walking GPS, that can be used in real, manual deployments of wireless sensor networks. We evaluate our localization solution exclusively in real deployments of MICA2 and XSM motes. Our experiments show that 100% of the deployed motes localize (i.e,. have a location position) and that the average localization errors are within 1 to 2 meters, due mainly to the limitations of the existing commercial GPS devices.

The focus of surveillance missions is to acquire and verify information about enemy capabilities and positions of hostile targets. Such missions often involve a high element of risk for human personnel and require a high degree of stealthiness. Hence, the ability to deploy unmanned surveillance missions, by using wireless sensor networks, is of great practical importance for the military. Because of the energy constraints of sensor devices, such systems necessitate an energy-aware design to ensure the longevity of surveillance missions. Solutions proposed recently for this type of system show promising results through simulations. However, the simplified assumptions they make about the system in the simulator often do not hold well in practice and energy consumption is narrowly accounted for within a single protocol. In this paper, we describe the design and implementation of a running system for energy-efficient surveillance. The system allows a group of cooperating sensor devices to detect and track the positions of moving vehicles in an energy-efficient and stealthy manner. We can trade off energy-awareness and surveillance performance by adaptively adjusting the sensitivity of the system. We evaluate the performance on a network of 70 MICA2 motes equipped with dual-axis magnetometers. Our results show that our surveillance strategy is adaptable and achieves a significant extension of network lifetime. Finally, we share lessons learned in building such a complete running system.

In this paper, we investigate the impact of radio irregularity on the communication performance in wireless sensor networks. Radio irregularity is a common phenomenon which arises from multiple factors, such as variance in RF sending power and different path losses depending on the direction of propagation. From our experiments, we discover that the variance in received signal strength is largely random; however, it exhibits a continuous change with incremental changes in direction. With empirical data obtained from the MICA2 platform, we establish a radio model for simulation, called the Radio Irregularity Model (RIM). This model is the first to bridge the discrepancy between spherical radio models used by simulators and the physical reality of radio signals. With this model, we are able to analyze the impact of radio irregularity on some of the well-known MAC and routing protocols. Our results show that radio irregularity has a significant impact on routing protocols, but a relatively small impact on MAC protocols. Finally, we propose six solutions to deal with radio irregularity. We evaluate two of them in detail. The results obtained from both the simulation and a running testbed demonstrate that our solutions greatly improve communication performance in the presence of radio irregularity.

Power management is an important technique to prolong the lifespan of sensor networks. Many power-management protocols employ wake-up/sleep schedules, which are often complicated and inefficient. We present power management schemes that eliminate such wake-up periods unless the node indeed needs to wake up. This type of wake-up capability is enabled by a new radio-triggered hardware component. We evaluate the potential power saving in terms of the lifespan of a sensor network application, using experiment data and SPICE circuit simulations. Comparing the result with always-on and rotation-based power management schemes, we find the radio-triggered scheme saves 98% of the energy used in the always-on scheme, and saves over 70% of the energy used in the rotation-based scheme. Consequently, the lifespan increases from 3.3 days (always-on) or 49.5 days (rotation-based) to 178 days (radio-triggered). Furthermore, a store-energy technique can extend operating distance from 10 feet to 22 feet, or even longer if longer latency is acceptable. We also present amplification and radio-triggered IDs which can further enhance performance.

Since this is the 25 anniversary of RTSS, I begin this Keynote presentation by highlighting, with a critical eye, a number of key technical successes from the past 25 years. While it is satisfying that our field has been very successful and productive, I prefer to emphasize the future. Consequently, a large part of the presentation focuses on multiple technical ideas and research directions for the future of real-time computing. One theme for the proposed future directions is “We need to get the real into real-time computing.” If I am feeling brave I will conclude with several things we should not be pursuing.

Location information is of paramount importance for wireless sensor networks (WSN). The accuracy of the collected data can significantly be affected by an imprecise positioning of the event of interest. Despite the importance of location information, real system implementations that do not use specialized hardware for localization purposes have not been successful. In this paper, we propose a location estimation scheme that uses a probabilistic approach for estimating the location of a node in a sensor network. Our localization scheme makes use of additional knowledge of topology deployment. We assume a sensor network is deployed in a controlled manner, where the goal of the deployment is to form a grid topology. We evaluate our localization scheme through simulations, showing localization errors as low as 3% of radio range. We outperform similar localization schemes by obtaining 50% less error in localization. We also evaluate our localization solution and the DV-hop scheme in a real implementation, obtaining an average error in location of 79% of radio range, outperforming DV-hop by approximately 40%. We analyze the significant differences in performance between simulations and a real implementation and stress the importance of further evaluations of real implementations. The result is an effective and realistic protocol that works in an actual implementation, under certain assumptions, because it exploits deployment information.

No abstract available.

Real-time databases (RTDBs) are increasingly being used as an integral part of many computer systems. During normal operation, transactions in RTDBs must be executed in such a way that transaction timing and data time validity constraints can be met. RTDBs must also prepare for possible failures and provide fault tolerance capability. Principles for fault tolerance in RTDBs must take timing requirements into consideration and are distinct from those for conventional databases. We discuss these issues in this paper and describe a logging and recovery technique that is time-cognizant and is suitable for an important class of RTDB applications. The technique minimizes normal runtime overhead caused by logging and has a predictable impact on transaction timing constraints. Upon a failure, the system can recover critical data to a consistent and temporally valid state within predictable time bounds. The system can then resume its major functioning while non-critical data are being recovered in the background. As a result, the recovery time is bounded and shortened. In short, we are providing a bounded and predictable logging and recovery technique for critical transactions accessing critical variant and invariant data, while the database may consist of all kinds of data. Our performance evaluation via simulation shows that logging overhead has a small effect on missing transaction deadlines while adding recovery capability. In addition, our algorithm scales well with respect to large I/O page sizes, indicating that it can be adapted to future generations of storage devices with larger I/O page sizes. We compare our algorithm with another approach that does more frequent checkpointing for data with certain special characteristics. Simulation results disclose conditions under which each approach performs better than the other. Experiments also show that recovery using our approach is 3–6 times faster than traditional recovery.

Sensor networks, a novel paradigm in distributed wireless communication technology, have been proposed for various applications including military surveillance and environmental monitoring. These systems deploy heterogeneous collections of sensors capable of observing and reporting on various dynamic properties of their surroundings in a time sensitive manner. Such systems suffer bandwidth, energy, and throughput constraints that limit the quantity of information transferred from end-to-end. These factors coupled with unpredictable traffic patterns and dynamic network topologies make the task of designing optimal protocols for such networks difficult. Mechanisms to perform data-centric aggregation utilizing application-specific knowledge provide a means to augmenting throughput, but have limitations due to their lack of adaptation and reliance on application-specific decisions. We, therefore, propose a novel aggregation scheme that adaptively performs application-independent data aggregation in a time sensitive manner. Our work isolates aggregation decisions into a module that resides between the network and the data-link layer and does not require any modifications to the currently existing MAC and network layer protocols. We take advantage of queuing delay and the broadcast nature of wireless communication to concatenate network units into an aggregate using a novel adaptive feedback scheme to schedule the delivery of this aggregate to the MAC layer for transmission. In our evaluation we show that end-to-end transmission delay is reduced by as much as 80% under heavy traffic loads. Additionally, we show as much as a 50% reduction in transmission energy consumption with an overall reduction in header overhead. Theoretical analysis, simulation, and a test-bed implementation on Berkeley's MICA motes are provided to validate our claims.

The demand for real-time data services is increasing in many applications including e-commerce, agile manufacturing, and telecommunications network management. In these applications, it is desirable to execute transactions within their deadlines, i.e., before the real-world status changes, using fresh (temporally consistent) data. However, meeting these fundamental requirements is challenging due to dynamic workloads and data access patterns in these applications. Further, transaction timeliness and data freshness requirements may conflict. We define average/transient deadline miss ratio and new data freshness metrics to let a database administrator specify the desired quality of real-time data services for a specific application. We also present a novel QoS management architecture for real-time databases to support the desired QoS even in the presence of unpredictable workloads and access patterns. To prevent overload and support the desired QoS, the presented architecture applies feedback control, admission control, and flexible freshness management schemes. A simulation study shows that our QoS-aware approach can achieve a near zero miss ratio and perfect freshness, meeting basic requirements for real-time transaction processing. In contrast, baseline approaches fail to support the desired miss ratio and/or freshness in the presence of unpredictable workloads and data access patterns.

In this paper, we present a real-time communication protocol for sensor networks, called SPEED. The protocol provides three types of real-time communication services, namely, real-time unicast, real-time area-multicast and real-time area-anycast. SPEED is specifically tailored to be a stateless, localized algorithm with minimal control overhead End-to-end soft real-time communication is achieved by maintaining a desired delivery speed across the sensor network through a novel combination of feedback control and non-deterministic geographic forwarding. SPEED is a highly efficient and scalable protocol for sensor networks where the resources of each node are scarce. Theoretical analysis, simulation experiments and a real implementation on Berkeley motes are provided to validate our claims.

Wireless Sensor Networks have been proposed for a multitude of location-dependent applications. For such systems, the cost and limitations of hardware on sensing nodes prevent the use of range-based localization schemes that depend on absolute point-to-point distance estimates. Because coarse accuracy is sufficient for most sensor network applications, solutions in range-free localization are being pursued as a cost-effective alternative to more expensive range-based approaches. In this paper, we present APIT, a novel localization algorithm that is range-free. We show that our APIT scheme performs best when an irregular radio pattern and random node placement are considered, and low communication overhead is desired. We compare our work via extensive simulation, with three state-of-the-art range-free localization schemes to identify the preferable system configurations of each. In addition, we study the effect of location error on routing and tracking performance. We show that routing performance and tracking accuracy are not significantly affected by localization error when the error is less than 0.4 times the communication radio radius. 1.

In this paper, we present a middleware architecture for coordination services in sensor networks that facilitates interaction between groups of sensors which monitor different environmental events. It sits on top of the native routing infrastructure and exports the abstraction of mobile communication endpoints maintained at the locations of such events. A single logical destination is created and maintained for every environmental event of interest. Such destinations are uniquely labeled and can be used for communication by application-level algorithms for coordination and sensory data management between the different event locales. For example, they may facilitate coordination, in a distributed intrusion scenario, among nodes in the vicinity of the intruders.We evaluate our middleware architecture using GloMoSim, a wireless network simulator. Our results illustrate the success of our architecture in maintaining event-related communication endpoints. We provide an analysis of how architectural and network dependent parameters affect our performance. Additionally we provide a proof of concept implementation on a real sensor network testbed (Berkeley's MICA Motes).

Providing quality of service guarantees for data services in a distributed environment is a challenging task. The presence of multiple sites in distributed environment raises issues that are not present in centralized systems. The transaction workloads in distributed real-time databases may not be balanced and the transaction access patterns may be time-varying and skewed. Data replication is an effective method to help database systems meet the stringent temporal requirements of real-time applications. We have designed an algorithm that provides quality of service guarantees for data services in distributed real-time databases with full replication of temporal data. The algorithm consists of heuristic feedback-based local controllers and global load balancers (GLB) working at each sites. The local controller controls the admission process of incoming transactions. The global load balancers collect the performance data from other nodes and balance the system-wide workload. The simulation results show that the new algorithm successfully balances the workloads in distributed real-time databases and provides tight transaction miss ratio guarantees under various transaction workloads.

Preventing denial-of-service attacks in wireless sensor networks is difficult primarily because of the limited resources available to network nodes and the ease with which attacks are perpetrated. Rather than jeopardize design requirements which call for simple, inexpensive, mass-producible devices, we propose a coping strategy that detects and maps jammed regions. We describe a mapping protocol for nodes that surround a jammer which allows network applications to reason about the region as an entity, rather than as a collection of broken links and congested nodes. This solution is enabled by a set of design principles: loose group semantics, eager eavesdropping, supremacy of local information, robustness to packet loss and failure, and early use of results. Performance results show that regions can be mapped in 1-5 seconds, fast enough for real-time response. With a moderately connected network, the protocol is robust to failure rates as high as 25 percent.

For many sensor network applications such as military surveillance, it is necessary to provide full sensing coverage to a security-sensitive area while at the same time minimizing energy consumption and extending system lifetime by leveraging the redundant deployment of sensor nodes. It is also preferable for the sensor network to provide differentiated surveillance service for various target areas with different degrees of security requirements. In this paper, we propose a differentiated surveillance service for sensor networks based on an adaptable energy-efficient sensing coverage protocol. In the protocol, each node is able to dynamically decide a schedule for itself to guarantee a certain degree of coverage (DOC) with average energy consumption inversely proportional to the node density. Several optimizations and extensions are proposed to provide even better performance. Simulation shows that our protocol accomplishes differentiated surveillance with low energy consumption. It outperforms other state-of-the-art schemes by as much as 50% reduction in energy consumption and as much as 130% increase in the half-life of the network.

Sensor networks can be considered distributed computing platforms with many severe constraints, including limited CPU speed, memory size, power, and bandwidth. Individual nodes in sensor networks are typically unreliable and the network topology dynamically changes, possibly frequently. Sensor networks also differ because of their tight interaction with the physical environment via sensors and actuators. Because of this interaction, we find that sensor networks are very data-centric. Due to all of these differences, many solutions developed for general distributed computing platforms and for ad-hoc networks cannot be applied to sensor networks. After discussing several motivating applications, this paper first discusses the state of the art with respect to general research challenges, then focuses on more specific research challenges that appear in the networking, operating system, and middleware layers. For some of the research challenges, initial solutions or approaches are identified.

The demand for real-time database services has been increasing recently. Examples include sensor data fusion, decision support, Web information services, and online trading. In these applications, it is desirable to execute transactions within their deadlines using temporally consistent data. Due to the high service demand, real-time databases can be overloaded. As a result, many transactions may miss their deadlines, or data temporal consistency constraints can be violated. To address these problems, we present a QoS management scheme to support guarantees on deadline miss ratio and data freshness (temporal consistency) even in the presence of unpredictable workloads and data access patterns. Using our approach, admitted user transactions can be processed in time using fresh data. A simulation study shows that our QoS-sensitive approach can achieve a significant performance improvement, in terms of deadline miss ratio and data freshness, compared to several baseline approaches. Furthermore, our approach shows a comparable performance to the theoretical oracle that is privileged by a complete future knowledge of data accesses.

Attainment of software performance assurances in open, largely unpredictable environments has recently become an important focus for real-time research. Unlike closed embedded systems, many contemporary distributed real-time applications operate in environments where offered load and available resources suffer considerable random fluctuations, thereby complicating the performance assurance problem. Feedback control theory has recently been identified as a promising analytic foundation for controlling performance of such unpredictable, poorly modeled software systems, the same way other engineering disciplines have used this theory for physical process control. In this paper we describe the design and implementation of ControlWare, a middleware QoS-control architecture based on control theory, motivated by the needs of performance-assured Internet services. It offers a new type of guarantees we call convergence guarantees that lie between hard and probabilistic guarantees. The efficacy of the architecture in achieving its QoS goals under realistic load conditions is demonstrated in the context of web server and proxy QoS management.

Real-time databases are needed in security-critical applications, e.g., e-commerce, agile manufacturing, and military applications. In these applications, transactions and data items can be classified into several security levels according to their clearance and sensitivity levels. It is essential for real-time databases to prevent illegal direct/indirect transfer of sensitive data, e.g., trade secret, manufacturing, or operational data, between transactions belonging to different security levels. Further transactions should be committed within their deadlines, i.e., before the market, manufacturing, or battlefield status changes. In this paper we present a novel real-time database architecture, in which illegal direct/indirect inter-level information flows are prevented while controlling the deadline miss ratio for admitted transactions to remain below a certain threshold. In our approach, mandatory access control mechanisms are applied for security purposes. QoS management, admission control, and feedback control schemes are applied to support certain guarantees on the miss ratio against potential overload and data conflicts. A detailed simulation study shows that our approach can support the specified miss ratio preventing illegal information flows even in the presence of unpredictable workloads and varying degrees of data contention, whereas baseline approaches fail.

In this paper, issues involved in the design of a real-time database which maintains data temporal consistency are discussed. The concept of data-deadline is introduced and time cognizant transaction scheduling policies are proposed. Informally, data-deadline is a deadline assigned to a transaction due to the temporal constraints of the data accessed by the transaction. Further, two time cognizant forced wait policies which improve performance significantly by forcing a transaction to delay further execution until a new version of sensor data becomes available are proposed. A way to exploit temporal data similarity to improve performance is also proposed. Finally, these policies are evaluated through detailed simulation experiments. The simulation results show that taking advantage of temporal data semantics in transaction scheduling can significantly improve the performance of user transactions in realtime database systems. In particular, it is demonstrated that under the forced wait policy, the performance can be improved significantly. Further improvements result by exploiting data similarity.

Hierarchical CPU scheduling has emerged as a way to (1) support applications with diverse scheduling requirements in open systems, and (2) provide load isolation between applications, users, and other resource principals. Most existing work on hierarchical scheduling has focused on systems that provide a fixed scheduling model: the schedulers in part or all of the hierarchy are specified in advance. In this paper we describe a system of guarantees that permits a general hierarchy of soft real-time schedulers one that contains arbitrary scheduling algorithms at all points within the hierarchy - to be analyzed. This analysis results in deterministic guarantees for threads at the leaves of the hierarchy. We also describe the design, implementation, and performance evaluation of a system for supporting such a hierarchy in the Windows 2000 kernel. Finally, we show that complex scheduling behaviors can be created using small schedulers as components and describe the HLS programming environment.

Distributed soft real-time systems are becoming increasingly unpredictable due to several important factors such as the increasing use of commercial-off-the-shelf components, the trend towards open systems, and the proliferation of data-driven applications whose execution parameters vary significantly with input data. Such systems are less amenable to traditional worst-case real-time analysis. Instead, system-wide feedback control is needed to meet performance requirements. In this paper, we extend our previous work on developing software control algorithms based on a theory of feedback control to distributed systems. Our approach makes three important contributions. First, it allows the designer for a distributed real-time application to specify the desired temporal behavior of system adaptation, such as the speed of convergence to desired performance upon load or resource changes. This is in contrast to specifying only steady-state metrics, e.g., deadline miss ratio. Second, unlike QoS optimization approaches, our solution meets performance guarantees without accurate knowledge of task execution parameters-a key advantage in an unpredictable environment. Third, in contrast to ad hoc algorithms based on intuition and testing, our solution has a basis in the theory and practice of feedback control scheduling. Performance evaluation reveals that the solution not only has excellent steady state behavior, but also meets stability, overshoot, and settling time requirements. We also show that the solution outperforms several other algorithms available in the literature.

While early research on real-time computing was concerned with guaranteeing avoidance of undesirable effects, such as overload and deadline misses, adaptive real-time systems are designed to handle such effects dynamically. Various research efforts have addressed the characterization and improvement of the dynamic behavior of real-time systems. However, to the authors' knowledge, no unified framework exists for designing adaptive, real-time software systems based on specifications of desired dynamic behavior. We propose such a framework based on control theory. Using control theory, a designer can (i) specify the desired behavior in terms of a set of performance metrics that can be mapped to a dynamic response of the control system, (ii) establish an underlying control model of the real-time systems, and (iii) design a resource scheduler using feedback control design methods to guarantee runtime satisfaction of the specifications. This is in contrast to more ad-hoc techniques. We also show that simply using long-term average performance metrics is not sufficient in designing controllers. We then develop a new algorithm based on two PID controllers that meet both the transient and steady-state performance requirements.

The problem of scheduling real-time tasks with minimum jitter is particularly important in many control applications; nevertheless, it has rarely been studied in the scientific literature. This paper presents an unconventional scheduling approach for distributed static systems where tasks are periodic and have arbitrary deadlines, precedence, and exclusion constraints. The solution presented in this work not only creates feasible schedules, but also minimizes jitter for periodic tasks. We present a general framework consisting of an abstract architecture model and a general programming model. We show how to design a surprisingly simple and flexible scheduling method based on simulated annealing. Experimental results demonstrate the significant improvement of our algorithm over earliest deadline first and rate monotonic algorithms.

Despite the significant body of results in real-time scheduling, many real world problems are not easily supported. While algorithms such as Earliest Deadline First, Rate Monotonic, and the Spring scheduling algorithm can support sophisticated task set characteristics (such as deadlines, precedence constraints, shared resources, jitter, etc.), they are all "open loop" scheduling algorithms. Open loop refers to the fact that once schedules are created they are not "adjusted" based on continuous feedback. While open-loop scheduling algorithms can perform well in static or dynamic systems in which the workloads can be accurately modeled, they can perform poorly in unpredictable dynamic systems. In this paper, we present a new scheduling paradigm, which we call feedback control real-time scheduling. Feedback control real-time scheduling defines error terms for schedules, monitors the error, and continuously adjusts the schedules to maintain stable performance. This paper also presents a practical feedback control real-time scheduling algorithm, FC-EDF, which is a starting point in the long-term endeavor of creating a theory and practice of feedback control scheduling.

Despite the significant body of results in real-time scheduling, many real world problems are not easily supported. While algorithms such as Earliest Deadline First, Rate Monotonic, and the Spring scheduling algorithm can support sophisticated task set characteristics (such as deadlines, precedence constraints, shared resources, jitter etc.), they are all "open loop" scheduling algorithms. Open loop refers to the fact that once schedules are created they are not "adjusted" based on continuous feedback. While open-loop scheduling algorithms can perform well in static or dynamic systems in which the workloads can be accurately modeled, they can perform poorly in unpredictable dynamic systems. In this paper, we present a feedback control real-time scheduling algorithm and its evaluation. Performance results demonstrate the effectiveness of the algorithm when execution times vary from the worst case and when there are major shifts of total load in the system. A key part of this feedback solution is its explicit use of deadline based metrics.

Next-generation, hard real-time systems will require new, flexible functionality and guaranteed, predictable performance. This paper describes the UMass Spring threads package, designed specifically for multiprocessing in dynamic, hard real-time environments. This package is unique because of its support for new thread semantics for real-time processing. Predictable creation and execution of threads is achieved because of an underlying predictable kernel, the UMass Spring kernel. Design decisions and lessons learned while implementing the threads package are presented. Measurements affirm the predictability of this implementation on a representative multiprocessor platform. The adoption of the threads package in the UMass Spring kernel results in additional performance improvements, which include reduced context switching overhead and reduced average-case memory access durations.

The spring scheduling coprocessor is a novel very large scale integration (VLSI) accelerator for multiprocessor real-time systems. The coprocessor can be used for static as well as online scheduling. Many different policies and their combinations can be used (e.g., earliest deadline first, highest value first, or resource-oriented policies such as earliest available time first). In this paper, we describe a coprocessor architecture, a CMOS implementation, an implementation of the host/coprocessor interface and a study of the overall performance improvement. We show that the current VLSI chip speeds up the main portion of the scheduling operation by over three orders of magnitude. We also present an overall system improvement analysis by accounting for the operating system overheads and identify the next set of bottlenecks to improve. The scheduling coprocessor includes several novel VLSI features. It is implemented as a parallel architecture for scheduling that is parameterized for different numbers of tasks, numbers of resources, and internal wordlengths. The architecture was implemented using a single-phase clocking style in several novel ways. The 328 000 transistor custom 2-/spl mu/m VLSI accelerator running with a 100-MHz clock, combined with careful hardware/software co-design results in a considerable performance improvement, thus removing a major bottleneck in real-time systems.

The confluence of computers, communications, and databases is quickly creating a global virtual database where many applications require real time access to both temporally accurate and multimedia data. This is particularly true in military and intelligence applications, but these required features are needed in many commercial applications as well. We are developing a distributed database, called BeeHive, which could offer features along different types of requirements: real time, fault tolerance, security, and quality of service for audio and video. Support of these features and potential trade offs between them could provide a significant improvement in performance and functionality over current distributed database and object management systems. We present a high level design for BeeHive architecture and sketch the design of the BeeHive Object Model (BOM) which extends object oriented data models by incorporating time and other features into objects.

Static redundancy allocation is inappropriate in hard real-time systems that operate in variable and dynamic environments, (e.g., radar tracking, avionics). Adaptive fault tolerance (AFT) can assure adequate reliability of critical modules, under temporal and resource constraints, by allocating just as much redundancy to less critical modules as can be afforded thus gracefully reducing their resource requirement. We propose a mechanism for supporting adaptive fault tolerance in a real-time system. Adaptation is achieved by choosing a suitable redundancy strategy for a dynamically arriving computation to assure required reliability and to maximize the potential for fault tolerance while ensuring that deadlines are met. The proposed approach is evaluated using a real-life workload simulating radar tracking software in AWACS early warning aircraft. The results demonstrate that our technique outperforms static fault tolerance strategies in terms of tasks meeting their timing constraints. Further, we show that the gain in this timing-centric performance metric does not reduce the fault tolerance of the executing task below a predefined minimum level. Overall, the evaluation indicates that the proposed ideas result in a system that dynamically provides QoS guarantees along the fault-tolerance dimension.

An integrated platform which is capable of meeting the requirements of both traditional real-time control processing and multimedia processing has enormous potential for accommodating various kinds of new applications. However, except for the simplest of situations, few, if any, research or commercial systems successfully provide architectural and OS mechanisms which can efficiently support both hard real-time computation and multimedia soft real-time computation. The authors propose a multimedia server execution on multiprocessor real-time operating systems to provide different classes of guarantee to support both types of processing. The multimedia server supports multiple periodic multimedia streams with a capability for graceful QoS degradation during system overload. They (i) develop several multimedia server scheduling algorithms, (ii) evaluate the performance of these algorithms, and (iii) discuss realistic system implementation issues on the SGI IRIX/REACT/PRO operating system.

In this paper, issues involved in the design of a real-time database which maintains data temporal consistency are discussed. The concept of data-deadline is introduced and time cognizant non-waiting transaction scheduling policies are proposed. Further, two time cognizant forced wait policies which improve performance significantly by forcing a transaction to delay further execution until a new version of sensor data becomes available are proposed. A way to exploit temporal data similarity to improve performance is also proposed. Finally, these policies are evaluated through detailed simulation experiments. The simulation results show that taking advantage of temporal data semantics in transaction scheduling can significantly improve the performance of user transactions in real-time database systems. In particular, it is demonstrated that under the forced wait policy, the performance can be improved significantly. Further improvements result by exploiting data similarity.

Integrating multimedia into real-time control applications requires careful consideration. The impact of the system support needed to meet the soft real-time constraints of multimedia on meeting the hard deadlines of the control application is of paramount concern. We propose that integrated resource models and reflective real-time kernels can provide the basis for the needed solutions. Features such as quality of service and call admission would then span a spectrum of requirements from the soft real-time requirements of multimedia to the hard real-time constraints of the control application. The confluence of multimedia, real-time control and real-time active databases is also discussed.

This paper describes a tool called the Real-Time Scheduling Assistant (RTSA) that provides automated assistance in the areas of selection, evaluation, and implementation of scheduling algorithms for complex real-time systems. In RTSA, design elements relevant to real-time scheduling, including task set and processor characteristics, are specified using a graphical user interface. The tool's quantitative evaluation component provides a range of algorithms for analysis of the performance characteristics of systems and scheduling policies under consideration. The RTSA knowledge base contains real-time scheduling expertise that is encoded in the form of production rules, and applied using a forward chaining inference engine. Advice on multiple scheduling algorithms is offered at three levels: conceptual, analysis, and implementation.

The design of a kernel-level thread package for dynamic, hard real-time environments is presented. A highly integrated design is used to ensure predictability. A system description language and real-time programming language are used to specify key properties of threads and thread groups. For a thread, this includes whether or not the thread spawns other threads at run-time, the type of performance guarantee the thread requires, how the thread interacts with other threads, and what processors the thread may execute on. A predictable kernel uses this information along with on-line dynamic guarantees to ensure predictable execution of threads. The first phase of the thread package has been implemented and performance measurements have indicated a 66% improvement in context switching costs.

This paper presents a non-conventional scheduling approach for distributed static systems where tasks are periodic and have arbitrary deadlines, precedence, and exclusion constraints. The solution presented in this work not only creates feasible schedules, but also minimizes jitter for periodic tasks. The problem of scheduling real-time tasks with minimum jitter is particularly important in many control applications, nevertheless, it has been rarely studied in the scientific literature. We present a general framework consisting of an abstract architecture model and a general programming model. We show how to design a surprisingly simple and flexible scheduling method based on simulated annealing and present some experimental results.

Many real-time systems have both performance requirements and reliability requirements. Performance is usually measured in terms of the value in completing tasks on time. Reliability is evaluated by hardware and software failure models. In many situations, there are trade-offs between task performance and task reliability. Thus, a mathematical assessment of performance-reliability trade-offs is necessary to evaluate the performance of real-time fault-tolerance systems. Assuming that the reliability of task execution is achieved through task replication, we present an approach that mathematically determines the replication factor for tasks. Our approach is novel in that it is a task schedule based analysis rather than a state based analysis as found in other models. Because we use a task schedule based analysis, we can provide a fast method to determine optimal redundancy levels, we are not limited to hardware reliability given by constant failure rate functions as in most other models, and we hypothesize that we can more naturally integrate with online real-time scheduling than when state based techniques are used. In this work, the goal is to maximize the total performance index, which is a performance-related reliability measurement. We present a technique based on a continuous task model and show how it very closely approximates discrete models and tasks with varying characteristics.>

Many distributed real-time applications are structured as a set of processes communicating through synchronous channels. Unfortunately, process interactions and especially synchronous communications make the problem of predictably scheduling the tasks more complex. In distributed systems the local and remote tasks as well as the messages over the network must be properly scheduled and synchronized to meet the deadlines of the application. To find such a, schedule is not an easy task, in fact, this problem is NP complete even if one has complete knowledge of the future arrival times for all the processes in the system. The objective of this paper is to develop a scheme that allows for the dynamic scheduling and guaranteeing of distributed processes communicating via synchronous primitives. For efficiency reasons a combination of off-line and on-line scheduling is performed. Precedence and communication constraints are converted off-line into pseudo-deadlines for each task, enabling efficient on-line processing. The on-line scheduling operates in parallel at the sites involved in the distributed computation, further obtaining efficiency. The overall end-to-end scheduling includes the joint and coordinated scheduling of tasks and messages in a reflective memory distributed architecture.>

This paper summarizes the state of the real-time field in the areas of scheduling and operating system kernels. Given the vast amount of work that has been done by both the operations research and computer science communities in the scheduling area, we discuss four paradigms underlying the scheduling approaches and present several exemplars of each. The four paradigms are: static table-driven scheduling, static priority preemptive scheduling, dynamic planning-based scheduling, and dynamic best effort scheduling. In the operating system context, we argue that most of the proprietary commercial kernels as well as real-time extensions to time-sharing operating system kernels do not fit the needs of predictable realtime systems. We discuss several research kernels that are currently being built to explicitly meet the needs of real-time applications.>

Formal results for precedence constrained, real-time scheduling of unit time tasks are extended to arbitrary timed tasks with preemption. An exact characterisation of the EDF-like schedulers that can be used to transparently enforce precedence constraints among tasks is shown. These extended results are then integrated with a well-known protocol that handles real-time scheduling of tasks with shared resources, but does not consider precedence constraints. This results in schedulability formulas for task sets which allow preemption, shared resources, and precedence constraints, and a practical algorithm for many real-time uniprocessor systems.>

We present a novel co-processor for multiprocessor scheduling in the Spring real-time operating system. Since most dynamic scheduling problems are NP-complete, we use a heuristic algorithm which uses a smart searching scheme to find a feasible schedule for a set of specified tasks and hard deadlines. A parallel VLSI architecture for scheduling is developed that can be scaled for different numbers of tasks, numbers of resources, internal wordlengths, and future IC technologies. The scheduling architecture is implemented in a 0.8/spl mu/ CMOS technology and uses an advanced clocking scheme to allow further scaling to future technologies. With an internal clock rate of 100 MHz, a speed increase of two orders of magnitude is expected for scheduling tasks, thus removing a major bottleneck in real-time systems.>

We present a novel VLSI co-processor for real-time multiprocessor scheduling. The co-processor can be used for sophisticated static scheduling as well as for online scheduling using many different algorithms such as earliest deadline first, highest value first, or the Spring scheduling algorithm. When such an algorithm is used online it is important to assess the performance impact of the interface of the co-processor to the host system, in this case, the Spring kernel. We focus on the interface and its implications for overall scheduling performance. We show that the current VLSI chip speeds up the main portion of the scheduling operation by over three orders of magnitude and speeds up the overall scheduling operation 30 fold. The parallel VLSI architecture for scheduling is briefly presented. This architecture can be scaled for different numbers of tasks, resources, and internal word lengths. The implementation uses an advanced clocking scheme to allow further scaling using future IC technologies.>

Most real-time scheduling algorithms schedule tasks with regard to their worst case computation times. Resources reclaiming refers to the problem of utilizing the resources left unused by a task when it executes in less than its worst case computation time, or when a task is deleted from the current schedule. Dynamic resource reclaiming algorithms that are effective, avoid any run time anomalies, and have bounded overhead costs that are independent of the number of tasks in the schedule are presented. Each task is assumed to have a worst case computation time, a deadline, and a set of resource requirements. The algorithms utilize the information given in a multiprocessor task schedule and perform online local optimization. The effectiveness of the algorithms is demonstrated through simulation studies.>

The authors analyze the performance of a heuristic algorithm, H/sub k/, which tries to keep at least k processors busy, if possible. H/sub k/ combines the features of two known heuristic scheduling algorithms: list scheduling and the H scheduling algorithm. The authors analyze its schedule length bound for both uniform tasks, i.e. tasks with the same computation time, and nonuniform tasks, i.e. tasks with arbitrary computation times. When k=2, the time complexity of H is the same as the complexity of the H scheduling algorithm and list scheduling, which is O(n/sup 2/r), where n is the number of tasks and r is the number of resources. Whereas the H scheduling algorithm has a poor schedule length bound but performs very well in finding feasible schedules, and list scheduling does not perform well in finding feasible schedules but has a good bound, the results show that H/sub 2/ has both a good schedule length bound and performs well in finding feasible schedules.>

The authors investigate solutions to the priority inversion problem in a real-time database where two-phase locking is employed for concurrency control. They examine two basic schemes for addressing the priority inversion problem, one based on priority inheritance and the other based on priority abort. The authors also study a new scheme, called conditional priority inheritance, which attempts to capitalize on the advantage of each of the two basic schemes. The performance studies, conducted on a real-time database testbed, indicated that the basic priority inheritance protocol is inappropriate for solving the priority inversion problem in real-time database systems. The authors also show that the conditional priority inheritance scheme and the priority abort scheme perform well for a wide range of system workloads.>

Resource reclaiming refers to the problem of utilizing the resources left unused by a task when it executes in less than its worst-case computation time, or when a task is deleted from the current schedule. In dynamic real-time multiprocessor environments, resource reclaiming can be used to improve the average performance. Dynamic resource reclaiming algorithms must be effective in reclaiming unused time and also avoiding any anomalies. The authors present resource reclaiming algorithms with these properties. These algorithms are designed to have time complexity independent of the number of tasks in a schedule. The effectiveness of the algorithms is demonstrated through simulation studies. The algorithms have also been implemented in the Spring Kernel.>

In this paper, we study the performance characteristics of simple load sharing algorithms for heterogeneous distributed systems. We assume that nonnegligible delays are encountered in transferring jobs from one node to another. We analyze the effects of these delays on the performance of two threshold-based algorithms called Forward and Reverse. We formulate queuing theoretic models for each of the algorithms operating in heterogeneous systems under the assumption that the job arrival process at each node in Poisson and the service times and job transfer times are exponentially distributed. The models are solved using the Matrix-Geometric solution technique. These models are used to study the effects of different parameters and algorithm variations on the mean job response time: e.g., the effects of varying the thresholds, the impact of changing the probe limit, the impact of biasing the probing, and the optimal response times over a large range of loads and delays. Wherever relevant, the results of the models are compared with the M/M/ 1 model, representing no load balancing (hereafter referred to as NLB), and the M/M/K model, which is an achievable lower bound (hereafter referred to as LB).

The authors propose and study a window protocol suitable for transmitting time-constrained messages in a multiaccess network. The protocol differs from traditional window protocols in that it explicitly takes time constraints into account. The window is formed on the basis of the latest time to send a message (LS). A major advantage of the window protocol is that a newly arriving message is immediately considered for transmission if its LS is less than that of all pending messages in the system. As a result, the protocol closely approximates the optimal minimum-laxity-first policy. A performance evaluation through simulation shows that the protocol performs well in a wide range of environments, including under overloaded conditions.>

Efficient scheduling algorithms based on heuristic functions are developed for scheduling a set of tasks on a multiprocessor system. The tasks are characterized by worst-case computation times, deadlines, and resources requirements. Starting with an empty partial schedule, each step of the search extends the current partial schedule by including one of the tasks yet to be scheduled. The heuristic functions used in the algorithm actively direct the search for a feasible schedule, i.e. they help choose the task that extends the current partial schedule. Two scheduling algorithms are evaluated by simulation. To extend the current partial schedule, one of the algorithms considers, at each step of the search, all the tasks that are yet to be scheduled as candidates. The second focuses its attention on a small subset of tasks with the shortest deadlines. The second algorithm is shown to be very effective when the maximum allowable scheduling overhead is fixed. This algorithm is hence appropriate for dynamic scheduling in real-time systems.>

Models for two processor sharing policies called task scheduling processor sharing and job scheduling processor sharing are developed and analyzed. The first policy schedules each task independently and allows parallel execution of an individual program, whereas the second policy schedules each job as a unit, thereby not allowing parallel execution of an individual program. It is found that task scheduling performs better than job scheduling for most system parameter values. The performance of the task scheduling processor sharing is compared to a first come first serve policy. First come first serve performs better than processor sharing over a wide range of system parameters. Processor sharing performs best when the task service time variability is high. The performance of processor sharing and first come first serve is studied with two classes of jobs, and for when a specific number of processors is statically assigned to each of the classes.>

The performance characteristics of simple load-sharing algorithms are studied for heterogeneous distributed systems. It is assumed that non-negligible delays are encountered in transforming jobs from one node to another and in gathering remote state information. The effects of these delays on the performance of two algorithms called Forward and Reverse are analyzed. Queuing theoretic models are formulated for each of the algorithms operating in heterogeneous systems under the assumption that the job arrival process at each node is Poisson and the service times and job transfer time are exponentially distributed. The models are solved using the matrix-geometric solution technique. The models are tested with regard to the effects of varying thresholds, the impact of changing the probe limit, and the determination of the optimal response times over a large range of loads and delays. Wherever relevant, the results of the models are compared with M/M/1, random assignment, and the M/M/K models.>

Results are presented of empirical evaluations carried out on the RT-CARAT testbed. This testbed was used evaluating a set of integrated protocols that support real-time transactions. A basic locking scheme for concurrency control was used to develop and evaluate several algorithms for handling CPU scheduling, data-conflict resolution, deadlock resolution, transaction wakeup, and transaction restart. The performance data indicate that the CPU scheduling algorithm is the most significant of all the algorithms in improving the performance of real-time transactions, conflict-resolution protocols which directly address deadlines and criticality can have a substantial impact on performance compared to protocols that ignore such information, both criticality and deadline distributions strongly affect transaction performance, and overheads such as locking and message communication are nonnegligible and cannot be ignored in real-time transaction analysis. It is believed that these empirical results represent the first experimental results for real-time transactions on a testbed system.>

A study is made of the performance of FCFS (first-come, first-served) and improved FCFS scheduling algorithms for dynamic real-time computer systems in which tasks arrive as a random process and each task has a laxity specifying the maximum time a task can wait for the service. The general solution for M/M/1 systems in which the FCFS or an improved FCFS scheduling algorithm is used is obtained. In particular, explicit expressions for the unfinished work distribution, the task loss ratio, and the CPU utilization for M/M/1+M systems are derived. The last M in M/M/1+M means that the task laxity is exponentially distributed. The steady-state performance of those systems depends not only on the offered load rho (as in the non-real-time arena), but also on the normalized mean laxity, which is equal to the mean laxity divided by the mean service time. An analysis also shows that using the improved FCFS scheduling algorithm results in significant improvement over using the original FCFS algorithm. In many circumstances, the improved FCFS has almost identical or very similar performance to that of the minimum-laxity-first (MLF) algorithm, which has been shown to be optimal. The advantage of the improved FCFS algorithm is that it takes O(1) time while the MLF algorithm needs O(log n) time.>

The authors study the performance characteristics of simple load-sharing algorithms for distributed systems. In the systems under consideration, it is assumed that nonnegligible delays are encountered in transferring tasks from one node to another and in gathering remote state information. Because of these delays, the state information gathered by the load-sharing algorithms is out of date by the time the load-sharing decisions are taken. The authors analyze the effects of these delays on the performance of three algorithms, called forward, reverse, and symmetric. They formulate queueing-theoretic models for each of the algorithms operating in a homogeneous system under the assumption that the task arrival process at each node is Poisson and the service times and task transfer times are exponentially distributed. Each of the models is solved using the matrix-geometric solution technique, and the important performance metrics are derived and studied.>

A set of four heuristic algorithms is presented to schedule tasks that have headlines and resource requirements in a distributed system. When a task arrives at a node, the local scheduler at that node attempts to guarantee that the task will complete execution on that node before its deadline. If the attempt fails, the scheduling components on individual nodes cooperate to determine which other node in the system has sufficient resource surplus to guarantee the task. Simulation studies are performed to compare the performance of these algorithms with respect to each other as well to two baselines. The first baseline is the noncooperative algorithm where a task that cannot be guaranteed locally is not sent to any other node. The second is an (ideal) algorithm that behaves exactly like the bidding algorithm but incurs no communication overheads. The simulation studies examine how communication delay, task laxity, load differences on the nodes, and task computation times affect the performance of the algorithms. The results show that distributed scheduling is effective even in a hard real-time environment and that the relative performance of these algorithms is a function of the system state.>

A decentralized task reallocation algorithm for hard real-time systems is developed and analyzed. The algorithm, which is fast and reliable, specifically considers deadlines of tasks, attempts to utilize all the nodes of a distributed system to achieve its objective, handles tasks in priority order, and separates policy and mechanism. An extensive performance analysis of the algorithm by means of simulation shows that it is quite effective in performing reallocations and that it is significantly better than a centralized approach.>

A modified, priority-based probe algorithm for deadlock detection and resolution in distributed database system is presented. Various examples are used to show that the original priority-based algorithm, presented by M.K. Sinha and N. Natarajan (1985), either fails to detect deadlocks or reports deadlocks that do not exist in many situations. A modified algorithm that eliminates these problems is proposed. The algorithm has been tested through simulation and appears to be errorfree. The performance of the modified algorithm is briefly discussed.>

A line inadvertently omitted from a section of the pseudocode in the above paper (see ibid., vol.15, no.1, p.10-17, 1989) is provided. The correct reading of the section is given in full.>

The problem of efficiently determining the optimum threshold parameter values for a decentralized load balancing algorithm is investigated. Simulation is used to study the behavior of a gradient-based decentralized optimization algorithm for obtaining good values. The algorithm computes the incremental job delay as a function of changes in both the local and remote job arrival rate. Estimators for these two quantities that are embedded in the optimization algorithm are described. Several experiments designed to evaluate the performance of the algorithm in a stationary environment and in an environment where there are changes in the workload are presented. The results indicate that the estimators are accurate, the algorithm chooses good thresholds, and the resultant response time of jobs is near optimal.>

A novel window protocol for transmitting time-constrained messages in a multiaccess network is proposed that explicitly takes time constraints into account. The window is formed on the basis of latest time to send a message (LS). A newly arriving message is immediately considered for transmission if its LS is less than those of the all pending messages in the system. As a result, the protocol closely approximates the optimal minimum-laxity-first policy. A performance evaluation by simulation shows that the protocol performs well in a wide range of environments, even under overloaded conditions.>

Two task-scheduling algorithms for distributed hard real-time computer systems are presented. Both algorithms are based on a heuristic approach and explicitly account for both the deadlines and criticality of tasks when making scheduling decisions. In analyzing the algorithms, a performance metric called the weighted guarantee ratio is defined. It reflects both the percentage of tasks that make their deadlines and their relative worth to the system. The performance is analyzed by simulating the behavior of the algorithms as well as that of several other pertinent baseline algorithms under a wide range of system conditions including a nonhomogeneous task arrival rate. The results show that the algorithms outperform all the baseline algorithms except for the ideal but impractical centralized baseline and in many cases perform close to the ideal.>

We consider the problem of scheduling a set of n preemptable tasks in a system having r resources. Each task has an arbitrary, but known, worst case processing time and a deadline, and may request simultaneous use of a number of resources. A resource can be used either in shared mode or exclusive mode. In this paper, we develop and evaluate algorithms for determining whether or not a set of preemptive tasks is schedulable in such a real-time system, and if so, determining a schedule for it. This scheduling problem is known to be computationally intensive. In many real-time application environments, tasks are scheduled dynamically, and hence the scheduling algorithms used must have low run-time costs. To keep run-time costs low, we propose the use of suboptimal but practical algorithms that employ computationally simple heuristics. The computational complexity of our algorithms for scheduling n tasks in a system having r resources is O(rn2), which is very much lower than that of known optimal algorithms. We report on the results of simulation studies performed on such heuristic preemptive scheduling algorithms and the sensitivity of the performance of the algorithms with respect to various scheduling parameters. These studies show that due to the complexity of the problem, straightforward heuristics do not perform satisfactorily. However, an algorithm that uses combinations of such heuristics in conjunction with limited backtracks works very well.

This paper describes a heuristic approach for solving the problem of dynamically scheduling tasks in a real-time system where tasks have deadlines and general resource requirements. The crux of our approach lies in the heuristic function used to select the task to be scheduled next. The heuristic function is composed of three weighted factors. These factors explicitly consider information about real-time constraints of tasks and their utilization of resources. Simulation studies show that the weights for the various factors in the heuristic function have to be fine-tuned in order to obtain a degree of success in the range of 75-88 percent of that obtained via exhaustive search. However, modifying the approach to use limited backtracking improves the degree of success substantially to as high as 99.5 percent. This improvement is observed even when the initial set of weights are not tailored for a particular set of tasks. Simulation studies also show that in most cases the schedule determined by the heuristic algorithm is optimal or close to optimal.

There is a wide spectrum of techniques that can be aptly named decentralized control. However, certain functions in distributed operating systems, e.g., scheduling, operate under such demanding requirements that no known optimal control solutions exist. It has been shown that heuristics are necessary. This paper presents a heuristic for the effective cooperation of multiple decentralized components of a job scheduling function. An especially useful feature of the heuristic is that it can dynamically adapt to the quality of the state information being processed. Extensive simulation results show the utility of this heuristic. The simulation results are compared to several analytical models and a baseline simulation model. The heuristic itself is based on the application of Bayesian decision theory. Bayesian decision theory was used because its principles can be applied as a systematic approach to complex decision making under conditions of imperfect knowledge, and it can run relatively cheaply in real time.

Most systems which are required to operate under severe real-time constraints assume that all tasks and their characteristics are known a priori. Scheduling of such tasks can be done statistically. Further, scheduling algorithms operating under such conditions are usually limited to multiprocessor configurations. The authors present a scheduling algorithm which works dynamically and on loosely coupled distributed systems for tasks with hard real-time constraints; i.e., the tasks must meet their deadlines. It uses a scheduling component local to every node and a distributed scheduling scheme which is specifically suited to hard real-time constraints and other timing considerations. Periodic tasks, nonperiodic tasks, scheduling overheads, communication overheads due to scheduling and preemption are all accounted for in the algorithm. Simulation studies are used to evaluate the performance of the algorithm.

Many distributed scheduling algorithms have been developed and reported in the current literature. However, very few of them explicitly treat stability issues. This paper first discusses stability issues for distributed scheduling algorithms in general terms. Two very different distributed scheduling algorithms which contain explicit mechanisms for stability are then presented and evaluated with respect to individual specific stability issues. One of the agorithms is based on stochastic learning automata and the other on bidding. The results indicate how very specific the treatment of stability is to the algorithm and environnent under consideration.

Distributed computer systems have been the subject of a vast amount of research. Many prototype distributed computer systems have been built at university, industrial, commercial, and government research laboratories, and production systems of all sizes and types have proliferated. It is impossible to survey all distributed computing system research. Instead, this paper identifies six fundamental distributed computer system research issues, points out open research problems in these areas, and describes how these six issues and solutions to problems associated with them transect the communications subnet, the distributed operating system, and the distributed database areas. It is intended that this perspective on distributed computer system research serve as a form of survey, but more importantly to illustrate and encourage a better integration and exchange of ideas from various subareas of distributed computer system research.

Multiuser transaction processing and database systems commonly use well-formed, two-phase locking to maintain data consistency. The preliminary results presented here represent the first step of an experimental investigation of the impact of different locking schemes on transaction performance. Tests were performed using a simplified but functionally complete testbed system. The transaction throughput rates for three different locking policies (file level locking, page level locking, and mixed level locking) are compared as a function of the lock mode (exclusive or share) and the file size for a small centralized database application. The experimental results for this environment show that the choice of locking policy and lock mode can have a significant impact on transaction throughput performance. The tests also demonstrate the sensitivity of the conclusions to the choice of workload and system characteristics.

This paper describes a multistep technique that can be applied to improve system structure and to improve performance when necessary. The technique begins with the analysis of system structure via the structured design guidelines of coupling and cohesion. Next, manual system structure improvement transformations are applied. The effect of the transformations on execution time is then determined. Finally, vertical migration is used on the restructured system to improve its performance. Using the results of this paper, system programmers can identify specific cases where both good system structure and good performance are attainable, and others where tradeoffs must be made. The technique is most applicable during the maintenance phase of the software life cycle.

A successful technique for improving system performance has been to migrate often used software functions into firmware. An extension of this technique, called vertical migration, has been developed that deals with migrations of functions between any two levels in a multilevel interpretive hierarchy. In both of these approaches the effect of multiple migrations on system performance is not fully understood and has not been formally analyzed. In this paper the effects of multiple migrations on system performance are formally described. Three distinct types of migration are identified and formulas for the execution time savings of each type are derived.