Commercial wearables from Fitbit, Garmin, and Whoop have recently introduced real-time notifications based on detecting changes in physiological responses indicating potential stress. In this paper, we investigate how these new capabilities can be leveraged to improve stress management. We developed a smartwatch app, a smartphone app, and a cloud service, and conducted a 100-day field study with 122 participants who received prompts triggered by physiological responses several times a day. They were asked whether they were stressed, and if so, to log the most likely stressor. Each week, participants received new visualizations of their data to self-reflect on patterns and trends. Participants reported better awareness of their stressors, and self-initiating fourteen kinds of behavioral changes to reduce stress in their daily lives. Repeated self-reports over 14 weeks showed reductions in both stress intensity (in 26,521 momentary ratings) and stress frequency (in 1,057 weekly surveys).

The promise of Mobile Health (mHealth) is the ability to use wearable sensors to monitor participant physiology at high frequencies during daily life to enable temporally-precise health interventions. However, a major challenge is frequent missing data. Despite a rich imputation literature, existing techniques are ineffective for the pulsative signals which comprise many mHealth applications, and a lack of available datasets has stymied progress. We address this gap with PulseImpute, the first large-scale pulsative signal imputation challenge which includes realistic mHealth missingness models, an extensive set of baselines, and clinically-relevant downstream tasks. Our baseline models include a novel transformer-based architecture designed to exploit the structure of pulsative signals. We hope that PulseImpute will enable the ML community to tackle this important and challenging task.

Public release of wrist-worn motion sensor data is growing. They enable and accelerate research in developing new algorithms to passively track daily activities, resulting in improved health and wellness utilities of smartwatches and activity trackers. But, when combined with sensitive attribute inference attack and linkage attack via re-identification of the same user in multiple datasets, undisclosed sensitive attributes can be revealed to unintended organizations with potentially adverse consequences for unsuspecting data contributing users. To guide both users and data collecting researchers, we characterize the re-identification risks inherent in motion sensor data collected from wrist-worn devices in users' natural environment. For this purpose, we use an open-set formulation, train a deep learning architecture with a new loss function, and apply our model to a new data set consisting of 10 weeks of daily sensor wearing by 353 users. We find that re-identification risk increases with an increase in the activity intensity. On average, such risk is 96% for a user when sharing a full day of sensor data.

Smoking is one of the most challenging behavioral health problems. In the past, failed quit attempts have been attributed to factors including stress, presence of smoking cues, and negative affect – most of which were self-reported and prone to recall-bias. The first step in designing effective smoking cessation systems is to objectively identify factors that contribute to lapse. In our research, we collected physiological data utilizing wearable sensors from a four day pre-quit, post-quit study (N=55). We also collected self-report measures (n=3120), which offer rich contextual information about users' social, emotional, geographical, and physiological conditions. Analysis of collected data informed the design of MyQuitPal, a participant-centric cessation support system, which aims to assist individuals to better understand their smoking behavior. The design of MyQuitPal is also grounded on theories of long term health-behavior change. We believe our research advances understanding of complexities and opportunities surrounding the design of smoking cessation systems.

The development and validation studies of new multisensory biomarkers and sensor-triggered interventions requires collecting raw sensor data with associated labels in the natural field environment. Unlike platforms for traditional mHealth apps, a software platform for such studies needs to not only support high-rate data ingestion, but also share raw high-rate sensor data with researchers, while supporting high-rate sense-analyze-act functionality in real-time. We present mCerebrum, a realization of such a platform, which supports high-rate data collections from multiple sensors with realtime assessment of data quality. A scalable storage architecture (with near optimal performance) ensures quick response despite rapidly growing data volume. Micro-batching and efficient sharing of data among multiple source and sink apps allows reuse of computations to enable real-time computation of multiple biomarkers without saturating the CPU or memory. Finally, it has a reconfigurable scheduler which manages all prompts to participants that is burden- and context-aware. With a modular design currently spanning 23+ apps, mCerebrum provides a comprehensive ecosystem of system services and utility apps. The design of mCerebrum has evolved during its concurrent use in scientific field studies at ten sites spanning 106,806 person days. Evaluations show that compared with other platforms, mCerebrum's architecture and design choices support 1.5 times higher data rates and 4.3 times higher storage throughput, while causing 8.4 times lower CPU usage.

Management of daily stress can be greatly improved by delivering sensor-triggered just-in-time interventions (JITIs) on mobile devices. The success of such JITIs critically depends on being able to mine the time series of noisy sensor data to find the most opportune moments. In this paper, we propose a time series pattern mining method to detect significant stress episodes in a time series of discontinuous and rapidly varying stress data. We apply our model to 4 weeks of physiological, GPS, and activity data collected from 38 users in their natural environment to discover patterns of stress in real-life. We find that the duration of a prior stress episode predicts the duration of the next stress episode and stress in mornings and evenings is lower than during the day. We then analyze the relationship between stress and objectively rated disorder in the surrounding neighborhood and develop a model to predict stressful episodes.

Craving usually precedes a lapse for impulsive behaviors such as overeating, drinking, smoking, and drug use. Passive estimation of craving from sensor data in the natural environment can be used to assist users in coping with craving. In this paper, we take the first steps towards developing a computational model to estimate cigarette craving (during smoking abstinence) at the minute-level using mobile sensor data. We use 2,012 hours of sensor data and 1,812 craving self-reports from 61 participants in a smoking cessation study. To estimate craving, we first obtain a continuous measure of stress from sensor data. We find that during hours of day when craving is high, stress associated with self-reported high craving is greater than stress associated with low craving. We use this and other insights to develop feature functions, and encode them as pattern detectors in a Conditional Random Field (CRF) based model to infer craving probabilities.

Differential privacy concepts have been successfully used to protect anonymity of individuals in population-scale analysis. Sharing of mobile sensor data, especially physiological data, raise different privacy challenges, that of protecting private behaviors that can be revealed from time series of sensor data. Existing privacy mechanisms rely on noise addition and data perturbation. But the accuracy requirement on inferences drawn from physiological data, together with well-established limits within which these data values occur, render traditional privacy mechanisms inapplicable. In this work, we define a new behavioral privacy metric based on differential privacy and propose a novel data substitution mechanism to protect behavioral privacy. We evaluate the efficacy of our scheme using 660 hours of ECG, respiration, and activity data collected from 43 participants and demonstrate that it is possible to retain meaningful utility, in terms of inference accuracy (90%), while simultaneously preserving the privacy of sensitive behaviors.

The field of mobile health (mHealth) has the potential to yield new insights into health and behavior through the analysis of continuously recorded data from wearable health and activity sensors. In this paper, we present a hierarchical span-based conditional random field model for the key problem of jointly detecting discrete events in such sensor data streams and segmenting these events into high-level activity sessions. Our model includes higher-order cardinality factors and inter-event duration factors to capture domain-specific structure in the label space. We show that our model supports exact MAP inference in quadratic time via dynamic programming, which we leverage to perform learning in the structured support vector machine framework. We apply the model to the problems of smoking and eating detection using four real data sets. Our results show statistically significant improvements in segmentation performance relative to a hierarchical pairwise CRF.

Recent advances in mobile health have produced several new models for inferring stress from wearable sensors. But, the lack of a gold standard is a major hurdle in making clinical use of continuous stress measurements derived from wearable sensors. In this paper, we present a stress model (called cStress) that has been carefully developed with attention to every step of computational modeling including data collection, screening, cleaning, filtering, feature computation, normalization, and model training. More importantly, cStress was trained using data collected from a rigorous lab study with 21 participants and validated on two independently collected data sets --- in a lab study on 26 participants and in a week-long field study with 20 participants. In testing, the model obtains a recall of 89% and a false positive rate of 5% on lab data. On field data, the model is able to predict each instantaneous self-report with an accuracy of 72%.

Recent researches have demonstrated the feasibility of detecting smoking from wearable sensors, but their performance on real-life smoking lapse detection is unknown. In this paper, we propose a new model and evaluate its performance on 61 newly abstinent smokers for detecting a first lapse. We use two wearable sensors - breathing pattern from respiration and arm movements from 6-axis inertial sensors worn on wrists. In 10-fold cross-validation on 40 hours of training data from 6 daily smokers, our model achieves a recall rate of 96.9%, for a false positive rate of 1.1%. When our model is applied to 3 days of post-quit data from 32 lapsers, it correctly pinpoints the timing of first lapse in 28 participants. Only 2 false episodes are detected on 20 abstinent days of these participants. When tested on 84 abstinent days from 28 abstainers, the false episode per day is limited to 1/6.

We investigate needs, challenges, and opportunities in visualizing time-series sensor data on stress to inform the design of just-in-time adaptive interventions (JITAIs). We identify seven key challenges: massive volume and variety of data, complexity in identifying stressors, scalability of space, multifaceted relationship between stress and time, a need for representation at multiple granularities, interperson variability, and limited understanding of JITAI design requirements due to its novelty. We propose four new visualizations based on one million minutes of sensor data (n=70). We evaluate our visualizations with stress researchers (n=6) to gain first insights into its usability and usefulness in JITAI design. Our results indicate that spatio-temporal visualizations help identify and explain between- and within-person variability in stress patterns and contextual visualizations enable decisions regarding the timing, content, and modality of intervention. Interestingly, a granular representation is considered informative but noise-prone; an abstract representation is the preferred starting point for designing JITAIs.

Mobile sensor data-to-knowledge (MD2K) was chosen as one of 11 Big Data Centers of Excellence by the National Institutes of Health, as part of its Big Data-to-Knowledge initiative. MD2K is developing innovative tools to streamline the collection, integration, management, visualization, analysis, and interpretation of health data generated by mobile and wearable sensors. The goal of the big data solutions being developed by MD2K is to reliably quantify physical, biological, behavioral, social, and environmental factors that contribute to health and disease risk. The research conducted by MD2K is targeted at improving health through early detection of adverse health events and by facilitating prevention. MD2K will make its tools, software, and training materials widely available and will also organize workshops and seminars to encourage their use by researchers and clinicians.

With increasing popularity of media-enabled handhelds and their integration with the in-vehicle entertainment systems, the need for high-data-rate services for mobile users on the go is evident. This ever-increasing demand of data is constantly surpassing what cellular networks can economically support. Large-scale wireless local area networks (WLANs) can provide such a service, but they are expensive to deploy and maintain. Open WLAN access points, on the other hand, need no new deployments, but can offer only opportunistic services, lacking any performance guarantees. In contrast, a carefully planned sparse deployment of roadside WiFi provides an economically scalable infrastructure with quality-of-service assurance to mobile users. In this paper, we present a new metric, called Contact Opportunity, to closely model the quality of data service that a mobile user might experience when driving through the system. We then present efficient deployment algorithms for minimizing the cost for ensuring a required level of contact opportunity. We further extend this concept and the deployment techniques to a more intuitive metric-the average throughput-by taking various dynamic elements into account. Simulations over a real road network and experimental results show that our approach achieves significantly better cost versus throughput tradeoff in both the worst case and average case compared to some commonly used deployment algorithms.

Driving is known to be a daily stressor. Measurement of driver's stress in real-time can enable better stress management by increasing self-awareness. Recent advances in sensing technology has made it feasible to continuously assess driver's stress in real-time, but it requires equipping the driver with these sensors and/or instrumenting the car. In this paper, we present "GStress", a model to estimate driver's stress using only smartphone GPS traces. The GStress model is developed and evaluated from data collected in a mobile health user study where 10 participants wore physiological sensors for 7 days ( for an average of 10.45 hours/day) in their natural environment. Each participant engaged in 10 or more driving episodes, resulting in a total of 37 hours of driving data. We find that major driving events such as stops, turns, and braking increase stress of the driver. We quantify their impact on stress and thus construct our GStress model by training a Generalized Linear Mixed Model (GLMM) on our data. We evaluate the applicability of GStress in predicting stress from GPS traces, and obtain a correlation of 0.72. By obviating any burden on the driver or the car, we believe, GStress can make driver's stress assessment ubiquitous.

Wearable wireless sensors for health monitoring are enabling the design and delivery of just-in-time interventions (JITI). Critical to the success of JITI is to time its delivery so that the user is available to be engaged. We take a first step in modeling users' availability by analyzing 2,064 hours of physiological sensor data and 2,717 self-reports collected from 30 participants in a week-long field study. We use delay in responding to a prompt to objectively measure availability. We compute 99 features and identify 30 as most discriminating to train a machine learning model for predicting availability. We find that location, affect, activity type, stress, time, and day of the week, play significant roles in predicting availability. We find that users are least available at work and during driving, and most available when walking outside. Our model finally achieves an accuracy of 74.7% in 10-fold cross-validation and 77.9% with leave-one-subject-out.

Smoking has been conclusively proved to be the leading cause of mortality that accounts for one in five deaths in the United States. Extensive research is conducted on developing effective smoking cessation programs. Most smoking cessation programs achieve low success rate because they are unable to intervene at the right moment. Identification of high-risk situations that may lead an abstinent smoker to relapse involve discovering the associations among various contexts that precede a smoking session or a smoking lapse. In the absence of an automated method, detection of smoking events still relies on subject self-report that is prone to failure to report and involves subject burden. Automated detection of smoking events in the natural environment can revolutionize smoking research and lead to effective intervention.

Vehicular Internet access via open WiFi access points (APs) has been demonstrated to be a feasible solution to provide opportunistic data service to moving vehicles. Using an in situ deployment, however, such a solution does not provide performance guarantees due to unpredictable intermittent connectivity. On the other hand, a solution that tries to cover every point in an entire road network with APs (a full coverage) is not very practical due to prohibitive deployment and operational costs. In this paper, we introduce a new notion of intermittent coverage for mobile users, called Alpha Coverage, which provides worst-case guarantees on the interconnection gap, i.e., the distance or expected delay between two consecutive mobile-AP contacts for a vehicle, while using significantly fewer APs than needed for full coverage. We propose efficient algorithms to verify whether a given deployment provides Alpha Coverage. The problem of finding an economic deployment that provides α -coverage turns out to be NP-hard. We hence provide both approximation algorithms that have provable guarantees on the performance as well as efficient heuristics that perform well in practice. The efficiency of our algorithms is demonstrated via simulations using data from real-world road networks.

We present AutoWitness, a system to deter, detect, and track personal property theft, improve historically dismal stolen property recovery rates, and disrupt stolen property distribution networks. A property owner embeds a small tag inside the asset to be protected, where the tag lies dormant until it detects vehicular movement. Once moved, the tag uses inertial sensor-based dead reckoning to estimate position changes, but to reduce integration errors, the relative position is reset whenever the sensors indicate the vehicle has stopped. The sequence of movements, stops, and turns are logged in compact form and eventually transferred to a server using a cellular modem after both sufficient time has passed (to avoid detection) and RF power is detectable (hinting cellular access may be available). Eventually, the trajectory data are sent to a server which attempts to match a path to the observations. The algorithm uses a Hidden Markov Model of city streets and Viterbi decoding to estimate the most likely path. The proposed design leverages low-power radios and inertial sensors, is immune to intransit cloaking, and supports post hoc path reconstruction. Our prototype demonstrates technical viability of the design; the volume market forces driving machine-to-machine communications will soon make the design economically viable.

Wearable sensors are revolutionizing healthcare and science by enabling capture of physiological, psychological, and behavioral measurements in natural environments. However, these seemingly innocuous measurements can be used to infer potentially private behaviors such as stress, conversation, smoking, drinking, illicit drug usage, and others. We conducted a study to assess how concerned people are about disclosure of a variety of behaviors and contexts that are embedded in wearable sensor data. Our results show participants are most concerned about disclosures of conversation episodes and stress - inferences that are not yet widely publicized. These concerns are mediated by temporal and physical context associated with the data and the participant's personal stake in the data. Our results provide key guidance on the extent to which people understand the potential for harm and data characteristics researchers should focus on to reduce the perceived harm from such datasets.

Micro-incentives represent a new but little-studied trend in participant compensation for user studies. In this paper, we use a combination of statistical analysis and models from labor economics to evaluate three canonical micro-payment schemes in the context of high-burden user studies, where participants wear sensors for extended durations. We look at how these strategies affect compliance, data quality, and retention, and show that when used carefully, micro-payments can be highly beneficial. We find that data quality is different across the micro-incentive schemes we experimented with, and therefore the incentive strategy should be chosen with care. We think that adaptive micro-payment based incentives can be used to successfully incentivize future studies at much lower cost to the study designer, while ensuring high compliance, good data quality, and lower retention issues.

Effect of psychosocial stress on health has been a central focus area of public health research. This demonstration features a wireless sensor suite called AutoSense that collects and processes cardiovascular, respiratory, and thermoregularity measurements that can inform about the general stress state of test subjects in their natural environment.

The effect of psychosocial stress on health has been a central focus area of public health research. However, progress has been limited due a to lack of wearable sensors that can provide robust measures of stress in the field. In this paper, we present a wireless sensor suite called AutoSense that collects and processes cardiovascular, respiratory, and thermoregularity measurements that can inform about the general stress state of test subjects in their natural environment. AutoSense overcomes several challenges in the design of wearable sensor systems for use in the field. First, it is unobtrusively wearable because it integrates six sensors in a small form factor. Second, it demonstrates a low power design; with a lifetime exceeding ten days while continuously sampling and transmitting sensor measurements. Third, sensor measurements are robust to several sources of errors and confounds inherent in field usage. Fourth, it integrates an ANT radio for low power and integrated quality of service guarantees, even in crowded environments. The AutoSense suite is complemented with a software framework on a smart phone that processes sensor measurements received from AutoSense to infer stress and other rich human behaviors. AutoSense was used in a 20+ subject real-life scientific study on stress in both the lab and field, which resulted in the first model of stress that provides 90% accuracy.

With increasing popularity of media enabled hand-helds, the need for high data-rate services for mobile users is evident. Large-scale Wireless LANs (WLANs) can provide such a service, but they are expensive to deploy and maintain. Open WLAN access-points (APs), on the other hand, need no new deployments, but can offer only opportunistic services with no guarantees on short term throughput. In contrast, a carefully planned sparse deployment of roadside WiFi provides an economically scalable infrastructure with quality of service assurance to mobile users. In this paper, we propose to study the deployment techniques with respect to roadside WiFi. In particular, we present a new metric, called Contact Opportunity, as a characterization of a roadside WiFi network. Informally, the contact opportunity for a given deployment measures the fraction of distance or time that a mobile user is in contact with some AP when moving through a certain path. Such a metric is closely related to the quality of data service that a mobile user might experience while driving through the system. We then present an efficient deployment method that maximizes the worst case contact opportunity under a budget constraint. We further show how to extend this concept and the deployment techniques to a more intuitive metric -- the average throughput -- by taking various dynamic elements into account. Simulations over a real road network and experimental results show that our approach achieves more than 200% higher minimum contact opportunity, 30%-100% higher average contact opportunity and a significantly improved distribution of average throughput compared with two commonly used baseline algorithms.

We present AutoWitness, a system to deter, detect, and track personal property theft, improve historically dismal stolen property recovery rates, and disrupt stolen property distribution networks. A property owner embeds a small tag inside the asset to be protected, where the tag lies dormant until it detects vehicular movement. Once moved, the tag uses inertial sensor-based dead reckoning to estimate position changes, but to reduce integration errors, the relative position is reset whenever the sensors indicate the vehicle has stopped. The sequence of movements, stops, and turns are logged in compact form and eventually transferred to a server using a cellular modem after both sufficient time has passed (to avoid detection) and RF power is detectable (hinting cellular access may be available). Eventually, the trajectory data are sent to a server which attempts to match a path to the observations. The algorithm uses a Hidden Markov Model of city streets and Viterbi decoding to estimate the most likely path. The proposed design leverages low-power radios and inertial sensors, is immune to intransit cloaking, and supports post hoc path reconstruction. Our prototype demonstrates technical viability of the design; the volume market forces driving machine-to-machine communications will soon make the design economically viable.

Global barrier coverage, which requires much fewer sensors than full coverage, is known to be an appropriate model of coverage for movement detection applications such as intrusion detection. However, it has been proved that given a sensor deployment, sensors can not locally determine whether the deployment provides global barrier coverage, making it impossible to develop localized algorithms, thus limiting its use in practice. In this paper, we introduce the concept of local barrier coverage to address this limitation. Motivated by the observation that movements are likely to follow a shorter path in crossing a belt region, local barrier coverage guarantees the detection of all movements whose trajectory is confined to a slice of the belt region of deployment. We prove that it is possible for individual sensors to locally determine the existence of local barrier coverage, even when the region of deployment is arbitrarily curved. Although local barrier coverage does not deterministically guarantee global barrier coverage, we show that for thin belt regions, local barrier coverage almost always provides global barrier coverage. To demonstrate that local barrier coverage can be used to design localized algorithms, we develop a novel sleep-wakeup algorithm for maximizing the network lifetime, called localized barrier coverage protocol (LBCP). We prove that LBCP guarantees local barrier coverage and show that LBCP provides close to optimal enhancement in the network lifetime, while providing global barrier coverage most of the time. They outperform an existing algorithm called randomized independent sleeping (RIS) by up to six times.

To make a network last beyond the lifetime of an individual sensor node, redundant nodes must be deployed. What sleep-wake-up schedule can then be used for individual nodes so that the redundancy is appropriately exploited to maximize the network lifetime? We develop optimal solutions to both problems for the case when wireless sensor nodes are deployed to form an impenetrable barrier for detecting movements. In addition to being provably optimal, our algorithms work for nondisk sensing regions and heterogeneous sensing regions. Further, we provide an optimal solution for the more difficult case when the lifetimes of individual nodes are not equal. Developing optimal algorithms for both homogeneous and heterogeneous lifetimes allows us to obtain, by simulation, several interesting results. We show that even when an optimal number of sensor nodes has been deployed randomly, statistical redundancy can be exploited to extend the network lifetime by up to seven times. We also use simulation to show that the assumption of homogeneous lifetime can result in severe loss (two-thirds) of the network lifetime. Although these results are specifically for barrier coverage, they provide an indication of behavior for other coverage models.

Although random deployment is widely used in theoretical analysis of coverage and connectivity, and evaluation of various algorithms (e.g., sleep-wakeup), it has often been considered too expensive as compared to optimal deterministic deployment patterns when deploying sensors in real-life. Roughly speaking, a factor of log n additional sensors are needed in random deployment as compared to optimal deterministic deployment if n sensors are needed in a random deployment. This may be an illusion however, since all real-life large-scale deployments strategies result in some randomness, two prime sources being placement errors and sensor failures, either at the time of deployment or afterwards. In this paper, we consider the effects of placement errors and random failures on the density needed to achieve full coverage when sensors are deployed randomly versus deterministically. We compare three popular strategies for deployment. In the first strategy, sensors are deployed in an optimal lattice but enough sensors are colocated at each lattice point to compensate for failure and placement errors. In the second, only one sensor is deployed at each lattice point but lattice spacing is sufficiently shrunk to achieve a desired quality of coverage in the presence of failure and placement errors. In the third, a random deployment is used with appropriate density. We derive explicit expressions for the density needed for each of the three strategies to achieve a given quality of coverage, which are of independent interest. In comparing the three deployments, we find that if errors in placement are half the sensing range and failure probability is 50%, random deployment needs only around 10% higher density to provide a similar quality of coverage as the other two. We provide a comprehensive comparison to help a practitioner decide the lowest cost deployment strategy in real-life.

Tracking of movements such as that of people, animals, vehicles, or of phenomena such as fire, can be achieved by deploying a wireless sensor network. So far only prototype systems have been deployed and hence the issue of scale has not become critical. Real-life deployments, however, will be at large scale and achieving this scale will become prohibitively expensive if we require every point in the region to be covered (i.e., full coverage), as has been the case in prototype deployments. In this paper we therefore propose a new model of coverage, called trap coverage, that scales well with large deployment regions. A sensor network providing trap coverage guarantees that any moving object or phenomena can move at most a (known) displacement before it is guaranteed to be detected by the network, for any trajectory and speed. Applications aside, trap coverage generalizes the de-facto model of full coverage by allowing holes of a given maximum diameter. From a probabilistic analysis perspective, the trap coverage model explains the continuum between percolation (when coverage holes become finite) and full coverage (when coverage holes cease to exist). We take first steps toward establishing a strong foundation for this new model of coverage. We derive reliable, explicit estimates for the density needed to achieve trap coverage with a given diameter when sensors are deployed randomly. Our density estimates are more accurate than those obtained using asymptotic critical conditions. We show by simulation that our analytical predictions of density are quite accurate even for small networks. We then propose polynomial-time algorithms to determine the level of trap coverage achieved once sensors are deployed on the ground. Finally, we point out several new research problems that arise by the introduction of the trap coverage model.

Vehicular Internet access via open WLAN access points (APs) has been demonstrated to be a feasible solution to provide opportunistic data service to moving vehicles. Using an in situ deployment, however, such a solution does not provide worst-case performance guarantees due to unpredictable intermittent connectivity. On the other hand, a solution that tries to cover every point in an entire road network with APs (full coverage) is not very practical due to the prohibitive deployment and operational cost. In this paper, we introduce a new notion of intermittent coverage for mobile users, called a-coverage, which provides worst-case guarantees on the interconnection gap while using significantly fewer APs than needed for full coverage. We propose efficient algorithms to verify whether a given deployment provides alpha-coverage and approximation algorithms for determining a deployment of APs that will provide alpha-coverage. We compare alpha-coverage with opportunistic access of open WLAN APs (modeled as a random deployment) via simulations over a real-world road network and show that using the same number of APs as random deployment, alpha-coverage bounds the interconnection gap to a much smaller distance than that in a random deployment.

The AutoWitness project aims to deter, detect, and track theft of everyday objects using a combination of ultra low-power mobile tags and a wide-area network of static anchors. Key research challenges include dramatically driving down the cost and size of tags and increasing their lifetime, discriminating between normal activities and theft using motion detection and classification algorithms, reconstructing getaway trajectories from sparse anchor rendezvous, and ensuring sufficient coverage and connectivity in a sparse, wide-area network of anchors. The demonstration will show AutoWitness in operation including motion detection, classifying theft signatures, and tracking the trajectories of "stolen" objects near the conference venue.

The problem of sleep wakeup has been extensively studied for the full coverage model, where every point in the deployment region is covered by some sensor. Since the sleep-wakeup problem is NP-Hard for this model, several heuristics exist. For the model of barrier coverage, however, where sensors are deployed to form an impenetrable barrier for detecting moving objects (a flagship application of wireless sensor networks), design of an optimal sleep-wakeup algorithm is open. In this paper, we solve this open problem by proposing optimal algorithms not only for the often-used case of equal lifetime but also for the much harder case when sensor lifetimes are different. We prove the optimality of both algorithms. Our algorithms can be used to maintain not just barrier coverage but fault tolerant connectivity, as well, while maximizing the network lifetime. We use simulation to show that for random deployments, even when a minimal number of sensors have been deployed, our optimal algorithms can increase the network lifetime by 500% (from 10 weeks to more than a year). Finally, we show that using our optimal algorithms increases the network lifetime six times longer than that achievable using an existing sleep wake-up algorithm called Randomized Independent Sleeping (RIS).

Deriving the critical density (which is equivalent to deriving the critical radius or power) to achieve coverage and/or connectivity for random deployments is a fundamental problem in the area of wireless networks. The probabilistic conditions normally derived, however, have limited appeal among practitioners because they areoften asymptotic, i.e., they only make high probability guarantees in the limit of large system sizes. Such conditions are not very useful in practice since deployment regions are always finite. Another major limitation of most existing work on coverage and connectivity is their focus on thick deployment regions (such as a square or a disk). There is no existing work (including traditional percolation theory) that derives critical densities for thin strips (or annuli).

Global barrier coverage that requires much fewer sensors than full coverage, is known to be an appropriate model of coverage for movement detection applications such as intrusion detection. However, it has been proved that given a sensor deployment, sensors can not locally determine whether the deployment provides global barrier coverage, making it impossible to develop localized algorithms, thus limiting its use in practice.

It is well-known that placing disks in the triangular lattice pattern is optimal for achieving full coverage on a plane. With the emergence of wireless sensor networks, however, it is now no longer enough to consider coverage alone when deploying a wireless sensor network; connectivity must also be con-sidered. While moderate loss in coverage can be tolerated by applications of wireless sensor networks, loss in connectivity can be fatal. Moreover, since sensors are subject to unanticipated failures after deployment, it is not enough to have a wireless sensor network just connected, it should be k-connected (for k > 1 ). In this paper, we propose an optimal deployment pattern to achieve both full coverage and 2-connectivity, and prove its optimality for all values of rc/rs, where rc is the communication radius, and rs is the sensing radius. We also prove the optimality of a previously proposed deployment pattern for achieving both full coverage and 1-connectivity, when rc/rs < √3 .Finally, we compare the efficiency of some popular regular deployment patterns such as the square grid and triangular lattice, in terms of the number of sensors needed to provide coverage and connectivity.

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

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

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

Sensor networks are often desired to last many times longer than the active lifetime of individual sensors. This is usually achieved by putting sensors to sleep for most of their lifetime. On the other hand, surveillance kind of applications require guaranteed k-coverage of the protected region at all times. As a result, determining the appropriate number of sensors to deploy that achieves both goals simultaneously becomes a challenging problem. In this paper, we consider three kinds of deployments for a sensor network on a unit square - a √n x √n grid, random uniform (for all n points), and Poisson (with density n). In all three deployments, each sensor is active with probability p, independently from the others. Then, we claim that the critical value of the function npπr2/log(np) is 1 for the event of k-coverage of every point. We also provide an upper bound on the window of this phase transition. Although the conditions for the three deployments are similar, we obtain sharper bounds for the random deployments than the grid deployment, which occurs due to the boundary condition. In this paper, we also provide corrections to previously published results for the grid deployment model. Finally, we use simulation to show the usefulness of our analysis in real deployment scenarios.