We investigate the ethical and privacy implications of voice-first ambient interfaces (VFAIs) for aging in place through an in-depth engagement with five older adults. Our participants were in the process of becoming experienced VFAI users, and had used a VFAI-based design probe for health data reporting. We create and iteratively refine an interview protocol using Privacy Cards. We customize Privacy Cards by drawing on participants’ previous interviews and device usage logs. Using Privacy Cards, we conduct interviews to surface their mental models, and explore their privacy concerns. We find insufficient mental models for proper consent. For example, participants did not know who could access their data, and experienced difficulty distinguishing built-in functionality from third-party apps. Participants initially expressed little worry about VFAI-related ethical concerns, but interviews with Privacy Cards revealed nuanced issues, resulting in various implications for future research and design.

From ELIZA to Alexa, Conversational Agents (CAs) have been deliberately designed to elicit or project empathy. Although empathy can help technology better serve human needs, it can also be deceptive and potentially exploitative. In this work, we characterize empathy in interactions with CAs, highlighting the importance of distinguishing evocations of empathy between two humans from ones between a human and a CA. To this end, we systematically prompt CAs backed by large language models (LLMs) to display empathy while conversing with, or about, 65 distinct human identities, and also compare how different LLMs display or model empathy. We find that CAs make value judgments about certain identities, and can be encouraging of identities related to harmful ideologies (e.g., Nazism and xenophobia). Moreover, a computational approach to understanding empathy reveals that despite their ability to display empathy, CAs do poorly when interpreting and exploring a user’s experience, contrasting with their human counterparts.

We focus on the stories of five older adults who became voice assistant users through our study, and with whom we speculated about future interfaces through two design probes, one for health data reporting and one for positive reminiscing. We delivered a voice-first ambient interface (VFAI) to each participant, and closely observed participants’ journeys through periodic themed interviews (16 hours, 21 minutes of transcribed recordings), usage log reviews (4,657 entries), and phone and text support. Participants’ lived experiences impacted their perceptions and interactions with their VFAI, fueling rich insights about how to design for diverse needs. For example, while one participant saw increased potential in the VFAI after interacting with the design probe for health data reporting, another was skeptical of using it to communicate with her doctor. We contribute an in-depth exploration of VFAIs to support aging in place, implications for design, and areas for future work for tailoring VFAIs towards enabling continuity of care in people’s homes.

Older adults around the world lack access to a wide range of potentially life-changing digital applications, services, and information that could be provided by voice assistants (such as Amazon’s Alexa, Google’s Assistant, or Apple’s Siri). However, older adults’ needs are underrepresented in the design of voice assistants. Because of this, we are missing opportunities for digital inclusion, and increasing risks of excluding older adults as these devices permeate public settings. In this work, we video record older adults (n=26) interacting with a multi-modal voice assistants while waiting in line at food pantries, and use Interaction Analysis to draw insights from these recordings. We find that by being agnostic to body language, audio-prosodic features, and other contextual factors, voice assistants fail to capture and react to some important aspects of interactions. We discuss design (e.g, interpreting users’ posture as a cue to wake the device when they are leaning towards the device) and research (e.g., surveillance trade-offs) implications, and argue for the use of multi-modal inputs with attention to privacy. Designing and training voice assistants to take in and appropriately respond to non-verbal cues may increase their inclusivity, helping them fulfill important needs of our aging population.

We design a scalable algorithm to privately generate location heatmaps over decentralized data from millions of user devices. It aims to ensure differential privacy before data becomes visible to a service provider while maintaining high data accuracy and minimizing resource consumption on users’ devices. To achieve this, we revisit distributed differential privacy based on recent results in secure multiparty computation, and we design a scalable and adaptive distributed differential privacy approach for location analytics. Evaluation on public location datasets shows that this approach successfully generates metropolitan-scale heatmaps from millions of user samples with a worstcase client communication overhead that is significantly smaller than existing state-of-the-art private protocols of similar accuracy.

Digital medical records have enabled us to employ clinical data in many new and innovative ways. However, these advances have brought with them a complex set of demands for healthcare institutions regarding data sharing with topics such as data ownership, the loss of privacy, and the protection of the intellectual property. The lack of clear guidance from government entities often creates conflicting messages about data policy, leaving institutions to develop guidelines themselves. Through discussions with multiple stakeholders at various institutions, we have generated a set of guidelines with 10 key principles to guide the responsible and appropriate use and sharing of clinical data for the purposes of care and discovery. Industry, universities, and healthcare institutions can build upon these guidelines toward creating a responsible, ethical, and practical response to data sharing.

Federated models are created by aggregating model updates submittedby participants. To protect confidentiality of the training data,the aggregator by design has no visibility into how these updates aregenerated. We show that this makes federated learning vulnerable to amodel-poisoning attack that is significantly more powerful than poisoningattacks that target only the training data.A single or multiple malicious participants can use modelreplacement to introduce backdoor functionality into the joint model,e.g., modify an image classifier so that it assigns an attacker-chosenlabel to images with certain features, or force a word predictor tocomplete certain sentences with an attacker-chosen word. We evaluatemodel replacement under different assumptions for the standardfederated-learning tasks and show that it greatly outperformstraining-data poisoning.Federated learning employs secure aggregation to protect confidentialityof participants’ local models and thus cannot detect anomalies inparticipants’ contributions to the joint model. To demonstrate thatanomaly detection would not have been effective in any case, we alsodevelop and evaluate a generic constrain-and-scale technique thatincorporates the evasion of defenses into the attacker’s loss functionduring training.

Implicit feedback (e.g., clicks) is widely used in content recommendations. However, clicks only reflect user preferences according to their first impressions. They do not capture the extent to which users continue to engage with the content. Our analysis shows that more than half of the clicks on music and short videos are followed by skips from two real-world datasets. In this paper, we leverage post-click feedback, e.g. skips and completions, to improve the training and evaluation of content recommenders. Specifically, we experiment with existing collaborative filtering algorithms and find that they perform poorly against post-click-aware ranking metrics. Based on these insights, we develop a generic probabilistic framework to fuse click and post-click signals. We show how our framework can be applied to improve pointwise and pairwise recommendation models. Our approach is shown to outperform existing methods by 18.3% and 2.5% respectively in terms of Area Under the Curve (AUC) on the short-video and music dataset. We discuss the effectiveness of our approach across content domains and trade-offs in weighting various user feedback signals.

Recent years have witnessed the flourishing of podcasts, a unique type of audio medium. Prior work on podcast content modeling focused on analyzing Automatic Speech Recognition outputs, which ignored vocal, musical, and conversational properties (e.g., energy, humor, and creativity) that uniquely characterize this medium. In this paper, we present an Adversarial Learning-based Podcast Representation (ALPR) that captures non-textual aspects of podcasts. Through extensive experiments on a large-scale podcast dataset (88,728 episodes from 18,433 channels), we show that (1) ALPR significantly outperforms the state-of-the-art features developed for music and speech in predicting theseriousness andenergy of podcasts, and (2) incorporating ALPR significantly improves the performance of topic-based podcast-popularity prediction. Our experiments also reveal factors that correlate with podcast popularity.

This paper introduces RecBoard, a unified web-based platform that facilitates researchers and practitioners to train, test, deploy, and monitor recommendation systems. RecBoard streamlines the end-to-end process of building recommendation systems by providing a collaborative user interface that automates repetitive tasks related to dataset management, model training, visualization, deployments, and monitoring. Our demo prototype demonstrates how RecBoard can empower common tasks in research and development. RecBoard will be open-sourced and publicly available upon publication.

People's content choices are ideally driven by their intentions, aspirations, and plans. However, in reality, choices may be modulated by recommendation systems which are typically trained to promote popular items and to reinforce users' historical behavior. As a result, the utility and user experience of content consumption can be affected implicitly and undesirably. To study this problem, we conducted a 2 × 2 randomized controlled field experiment (105 urban college students) to compare the effects of intention informed recommendations with classical intention agnostic systems. The study was conducted in the context of spoken word web content (podcasts) which is often consumed through subscription sites or apps. We modified a commercial podcast app to include (1) a recommender that takes into account users' stated intentions at onboarding, and (2) a Collaborative Filtering (CF) recommender during daily use. Our study suggests that: (1) intention-aware recommendations can significantly raise users' interactions (subscriptions and listening) with channels and episodes related to intended topics by over 24%, even if such a recommender is only used during onboarding, and (2) the CF-based recommender doubles users' explorations on episodes from not-subscribed channels and improves satisfaction for users onboarded with the intention-aware recommender.

Digital overuse on mobile devices is a growing problem in everyday life. This paper describes a generalizable mobile intervention that combines nudge theory and negative reinforcement to create a subtle, repeating phone vibration that nudges a user to reduce their digital consumption. For example, if a user has a daily Facebook limit of 30 minutes but opens Facebook past this limit, the user's phone will issue gentle vibrations every five seconds, but the vibration stops once the user navigates away from Facebook. We evaluated the intervention through a three-week controlled experiment with 50 participants on Amazon's Mechanical Turk platform with findings that show daily digital consumption was successfully reduced by over 20%. Although the reduction did not persist after the intervention was removed, insights from qualitative feedback suggest that the intervention made participants more aware of their app usage habits; and we discuss design implications of episodically applying our intervention in specific everyday contexts such as education, sleep, and work. Taken together, our findings advance the HCI community's understanding of how to curb digital overload.

Traditionally, recommendation systems are built on the assumption that each service provider has full access to all user data generated on its platform. However, with increasing data privacy concerns and personal data protection regulation, service providers such as Google, Twitter, and Facebook are enabling their users to revisit, erase, and rectify their historical profiles. Future recommendation systems need to be robust to such profile modifications and user-controlled data filtering. In this paper, we explore how recommendation performance may be affected by time-sensitive user data filtering, that is, users choosing to share only recent "N days" of data. Using the MovieLens dataset as a testbed, we evaluated three widely used collaborative filtering algorithms. Our experiments demonstrate that filtering out historical user data does not significantly affect the overall recommendation performance, but its impact on individual users may vary. These findings challenge the common belief that more data is essential to better performance, and suggest a potential win-win solution for services and end users.

Implicit-feedback Recommenders (ImplicitRec) leverage positive only user-item interactions, such as clicks, to learn personalized user preferences. Recommenders are often evaluated and compared offline using datasets collected from online platforms. These platforms are subject to popularity bias (i.e., popular items are more likely to be presented and interacted with), and therefore logged ground truth data are Missing-Not-At-Random (MNAR). As a result, the widely used Average-Over-All (AOA) evaluator is biased toward accurately recommending trendy items. In this paper, we (a) investigate evaluation bias of AOA and (b) develop an unbiased and practical offline evaluator for implicit MNAR datasets using the Inverse-Propensity-Scoring (IPS) technique. Through extensive experiments using four real-world datasets and four widely used algorithms, we show that (a) popularity bias is widely manifested in item presentation and interaction; (b) evaluation bias due to MNAR data pervasively exists in most cases where AOA is used to evaluate ImplicitRec; and (c) the unbiased estimator significantly reduces the AOA evaluation bias by more than 30% in the Yahoo! music dataset in terms of the Mean Absolute Error (MAE).

Voice interfaces introduced by smart speakers present new opportunities and challenges for podcast content recommendations. Understanding how users interact with voice-based recommendations has the potential to inform better design of vocal recommenders. However, existing knowledge about user behavior is mostly for visual interfaces, such as the web, and is not directly transferable to voice interfaces, which rely on user listening and do not support skimming and browsing. To fill in the gap, we conducted a controlled study to compare user interactions with recommendations delivered visually to those with recommendations delivered vocally. Through an online A/B testing with 100 participants, we found that when recommendations are vocally conveyed, users consume more slowly, explore less, and choose fewer long-tail items. The study also reveals the correlation between user choices and exploration via voice interfaces. Our findings pose challenges to the design of voice interfaces, such as adaptively recommending diverse content and designing better navigation mechanisms.

With the increasing demand for deeper understanding of users» preferences, recommender systems have gone beyond simple user-item filtering and are increasingly sophisticated, comprised of multiple components for analyzing and fusing diverse information. Unfortunately, existing frameworks do not adequately support extensibility and adaptability and consequently pose significant challenges to rapid, iterative, and systematic, experimentation. In this work, we propose OpenRec, an open and modular Python framework that supports extensible and adaptable research in recommender systems. Each recommender is modeled as a computational graph that consists of a structured ensemble of reusable modules connected through a set of well-defined interfaces. We present the architecture of OpenRec and demonstrate that OpenRec provides adaptability, modularity and reusability while maintaining training efficiency and recommendation accuracy. Our case study illustrates how OpenRec can support an efficient design process to prototype and benchmark alternative approaches with inter-changeable modules and enable development and evaluation of new algorithms.

Predicting users’ proficiencies is a critical component of AI-powered personal assistants. This article introduces a novel approach for the prediction based on users’ diverse, noisy, and passively generated application usage histories. We propose a novel bi-directional recurrent neural network with hierarchical attention mechanism to extract sequential patterns and distinguish informative traces from noise. Our model is able to attend to the most discriminative actions and sessions to make more accurate and directly interpretable predictions while requiring 50× less training data than the state-of-the-art sequential learning approach. We evaluate our model with two large scale datasets collected from 68K Photoshop users: a digital design skill dataset where the user skill is determined by the quality of the end products and a software skill dataset where users self-disclose their software usage skill levels. The empirical results demonstrate our model’s superior performance compared to existing user representation learning techniques that leverage action frequencies and sequential patterns. In addition, we qualitatively illustrate the model’s significant interpretative power. The proposed approach is broadly relevant to applications that generate user time-series analytics.

Metric learning algorithms produce distance metrics that capture the important relationships among data. In this work, we study the connection between metric learning and collaborative filtering. We propose Collaborative Metric Learning (CML) which learns a joint metric space to encode not only users' preferences but also the user-user and item-item similarity. The proposed algorithm outperforms state-of-the-art collaborative filtering algorithms on a wide range of recommendation tasks and uncovers the underlying spectrum of users' fine-grained preferences. CML also achieves significant speedup for Top-K recommendation tasks using off-the-shelf, approximate nearest-neighbor search, with negligible accuracy reduction.

Nutrient-based meal recommendations have the potential to help individuals prevent or manage conditions such as diabetes and obesity. However, learning people’s food preferences and making recommendations that simultaneously appeal to their palate and satisfy nutritional expectations are challenging. Existing approaches either only learn high-level preferences or require a prolonged learning period. We propose Yum-me , a personalized nutrient-based meal recommender system designed to meet individuals’ nutritional expectations, dietary restrictions, and fine-grained food preferences. Yum-me enables a simple and accurate food preference profiling procedure via a visual quiz-based user interface and projects the learned profile into the domain of nutritionally appropriate food options to find ones that will appeal to the user. We present the design and implementation of Yum-me and further describe and evaluate two innovative contributions. The first contriution is an open source state-of-the-art food image analysis model, named FoodDist . We demonstrate FoodDist’s superior performance through careful benchmarking and discuss its applicability across a wide array of dietary applications. The second contribution is a novel online learning framework that learns food preference from itemwise and pairwise image comparisons. We evaluate the framework in a field study of 227 anonymous users and demonstrate that it outperforms other baselines by a significant margin. We further conducted an end-to-end validation of the feasibility and effectiveness of Yum-me through a 60-person user study, in which Yum-me improves the recommendation acceptance rate by 42.63%.

We propose a new user-centric recommendation model, called Immersive Recommendation, that incorporates cross-platform and diverse personal digital traces into recommendations. Our context-aware topic modeling algorithm systematically profiles users' interests based on their traces from different contexts, and our hybrid recommendation algorithm makes high-quality recommendations by fusing users' personal profiles, item profiles, and existing ratings. Specifically, in this work we target personalized news and local event recommendations for their utility and societal importance. We evaluated the model with a large-scale offline evaluation leveraging users' public Twitter traces. In addition, we conducted a direct evaluation of the model's recommendations in a 33-participant study using Twitter, Facebook and email traces. In the both cases, the proposed model showed significant improvement over the state-of-the-art algorithms, suggesting the value of using this new user-centric recommendation model to improve recommendation quality, including in cold-start situations.

Food preference learning is an important component of wellness applications and restaurant recommender systems as it provides personalized information for effective food targeting and suggestions. However, existing systems require some form of food journaling to create a historical record of an individual's meal selections. In addition, current interfaces for food or restaurant preference elicitation rely extensively on text-based descriptions and rating methods, which can impose high cognitive load, thereby hampering wide adoption.

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.

Participatory sensing (PS) is a distributed data collection and analysis approach where individuals, acting alone or in groups, use their personal mobile devices to systematically explore interesting aspects of their lives and communities [Burke et al. 2006]. These mobile devices can be used to capture diverse spatiotemporal data through both intermittent self-report and continuous recording from on-board sensors and applications. Ohmage (http://ohmage.org) is a modular and extensible open-source, mobile to Web PS platform that records, stores, analyzes, and visualizes data from both prompted self-report and continuous data streams. These data streams are authorable and can dynamically be deployed in diverse settings. Feedback from hundreds of behavioral and technology researchers, focus group participants, and end users has been integrated into ohmage through an iterative participatory design process. Ohmage has been used as an enabling platform in more than 20 independent projects in many disciplines. We summarize the PS requirements, challenges and key design objectives learned through our design process, and ohmage system architecture to achieve those objectives. The flexibility, modularity, and extensibility of ohmage in supporting diverse deployment settings are presented through three distinct case studies in education, health, and clinical research.

Location-Based Mobile Service (LBMS) is one of the most popular smartphone services. LBMS enables people to more easily connect with each other and analyze the aspects of their lives. However, sharing location data can leak people's privacy. We present PDVLoc, a controlled location data-sharing framework based on selectively sharing data through a Personal Data Vault (PDV). A PDV is a privacy architecture in which individuals retain ownership of their data. Data are routinely filtered before being shared with content-service providers, and users or data custodian services can participate in making controlled data-sharing decisions. Introducing PDVLoc gives users flexible and granular access control over their location data. We have implemented a prototype of PDVLoc and evaluated it using real location-sharing social networking applications, Google Latitude and Foursquare. Our user study of 19 participants over 20 days shows that most users find that PDVLoc is useful to manage and control their location data, and are willing to continue using PDVLoc.

Mobile health (mHealth) leverages the power and ubiquity of mobile and cloud technologies to support patients and clinicians in monitoring and understanding symptoms, side effects and treatment outside the clinical setting; thereby closing the feedback loops of self-care, clinical-care, and personal-evidence-creation. However, to realize this promise, we must develop new data capture, processing and modeling techniques to convert the digital exhaust emitted by mobile phone use into behavioral biomarkers. This calls for a modular layered sensemaking framework in which low level state classifications of raw data (e.g., estimated activity states such as sitting, walking, driving from continuous accelerometer and location traces), are used to derive mid-level semantic features (e.g., total number of ambulatory minutes, number of hours spent out of house), that can then be mapped to particular behavioral biomarkers for specific diseases (e.g., chronic pain, GI disfunction, MS, fatigue, depression, etc). The techniques needed to derive these markers will range from simple functions to machine learning classifiers, and will need to fuse diverse data types, but all will need to cope with noisy, erratic data sources. We are working to build an open architecture and community to speed the rate and robustness of innovation in this space, both academic and commercial (http://openmhealth.org).

Smartphones can capture diverse spatio-temporal data about an individual; including both intermittent self-report, and continuous passive data collection from onboard sensors and applications. The resulting personal data streams can support powerful inference about the user's state, behavior, well-being and environment. However making sense and acting on these multi-dimensional, heterogeneous data streams requires iterative and intensive exploration of the datasets, and development of customized analysis techniques that are appropriate for a particular health domain.

Just as coordinate-oriented location-based applications have exploded recently with mapping services, new semantic location services will be critical for the next wave of killer applications. People are going to want everyday applications to have location-awareness that goes beyond simple numerical latitude and longitude. Loci is a new semantic location service layer that employs user feedback to bridge the gap between machine-learned and human-defined places. Advances in place learning techniques have provided us the tools to detect nearly 95% of the visits we make to places and the distances we travel. The difficulty of recovering the remaining 5% comes from designing parameters that work for every user in every place. Based on a user study with 29 participants over three weeks, we show that the level of user feedback required by the service is acceptable and most of the users are willing to provide help to improve their experiences with the service. Our results suggest that user feedback has the potential to significantly improve semantic location services, but requires well-timed prompting mechanisms to improve the quality of the feedback.

Bicycling is an affordable, environmentally friendly alternative transportation mode to motorized travel. A common task performed by bikers is to find good routes in an area, where the quality of a route is based on safety, efficiency, and enjoyment. Finding routes involves trial and error as well as exchanging information between members of a bike community. Biketastic is a platform that enriches this experimentation and route sharing process making it both easier and more effective. Using a mobile phone application and online map visualization, bikers are able to document and share routes, ride statistics, sensed information to infer route roughness and noisiness, and media that documents ride experience. Biketastic was designed to ensure the link between information gathering, visualization, and bicycling practices. In this paper, we present architecture and algorithms for route data inferences and visualization. We evaluate the system based on feedback from bicyclists provided during a two-week pilot.

The increasing ubiquity of the mobile phone is creating many opportunities for personal context sensing, and will result in massive databases of individuals' sensitive information incorporating locations, movements, images, text annotations, and even health data. In existing system architectures, users upload their raw (unprocessed or filtered) data streams directly to content-service providers and have little control over their data once they "opt-in".

We present a background model that differentiates between background motion and foreground objects. Unlike most models that represent the variability of pixel intensity at a particular location in the image, we model the underlying warping of pixel locations arising from background motion. The background is modeled as a set of warping layers, where at any given time, different layers may be visible due to the motion of an occluding layer. Foreground regions are thus defined as those that cannot be modeled by some composition of some warping of these background layers. We illustrate this concept by first reducing the possible warps to those where the pixels are restricted to displacements within a spatial neighborhood, and then learning the appropriate size of that spatial neighborhood. Then, we show how changes in intensity/color histograms of pixel neighborhoods can be used to discriminate foreground and background regions. We find that this approach compares favorably with the state of the art, while requiring less computation.

The rapid adoption of mobile devices that are able to capture and transmit a wide variety of sensing modalities (media and location) has enabled a new data collection paradigm - participatory sensing. Participatory sensing initiatives organize individuals to gather sensed information using mobile devices through cooperative data collection. A major factor in the success of these data collection projects is sustained, high quality participation. However, since data capture requires a time and energy commitment from individuals, incentives are often introduced to motivate participants. In this work, we investigate the use of micro-payments as an incentive model. We define a set of metrics that can be used to evaluate the effectiveness of incentives and report on findings from a pilot study using various micro-payment schemes in a university campus sustainability initiative.

Development of inexpensive, automated ground methods is necessary to advance precision plant phenology monitoring across large spatial extents. We propose the use of free, publicly available, Internet-connected cameras, often associated with nonscientific monitoring, to monitor plant phenology at continental scales. We provide a methodology to detect changes in vegetation greenness and determine timing of spring and fall events from over 1100 public cameras across North America from February 2008 - 2009. Manual image segmentation facilitated spring detection for both deciduous and understory vegetation occurring within a single camera view. Deciduous spring green-up was highly correlated with visual ground truths, despite signal noise introduced by varying image exposure and automatic color correction. Compared to co-occurring satellite remote sensing products, public cameras had an equivalent or higher ability to detect spring with fewer days lost to cloud cover.

Using data from 43 users across two platforms, we present a detailed look at smartphone traffic. We find that browsing contributes over half of the traffic, while each of email, media, and maps contribute roughly 10%. We also find that the overhead of lower layer protocols is high because of small transfer sizes. For half of the transfers that use transport-level security, header bytes correspond to 40% of the total. We show that while packet loss is the main factor that limits the throughput of smartphone traffic, larger send buffers at Internet servers can improve the throughput of a quarter of the transfers. Finally, by studying the interaction between smartphone traffic and the radio power management policy, we find that the power consumption of the radio can be reduced by 35% with minimal impact on the performance of packet exchanges.

Participatory sensing is the process whereby individuals and communities use ever-more-capable mobile phones and cloud services to collect and analyze systematic data for use in discovery. The convergence of technology and analytical innovation with a citizenry that is increasingly comfortable using mobile phones and online social networking sets the stage for this technology to dramatically impact many aspects of our daily lives.

Using detailed traces from 255 users, we conduct a comprehensive study of smartphone use. We characterize intentional user activities -- interactions with the device and the applications used -- and the impact of those activities on network and energy usage. We find immense diversity among users. Along all aspects that we study, users differ by one or more orders of magnitude. For instance, the average number of interactions per day varies from 10 to 200, and the average amount of data received per day varies from 1 to 1000 MB. This level of diversity suggests that mechanisms to improve user experience or energy consumption will be more effective if they learn and adapt to user behavior. We find that qualitative similarities exist among users that facilitate the task of learning user behavior. For instance, the relative application popularity for can be modeled using an exponential distribution, with different distribution parameters for different users. We demonstrate the value of adapting to user behavior in the context of a mechanism to predict future energy drain. The 90th percentile error with adaptation is less than half compared to predictions based on average behavior across users.

Continuously understanding a user's location context in colloquial terms and the paths that connect the locations unlocks many opportunities for emerging applications. While extensive research effort has been made on efficiently tracking a user's raw coordinates, few attempts have been made to efficiently provide everyday contextual information about these locations as places and paths. We introduce SensLoc, a practical location service to provide such contextual information, abstracting location as place visits and path travels from sensor signals. SensLoc comprises of a robust place detection algorithm, a sensitive movement detector, and an on-demand path tracker. Based on a user's mobility, SensLoc proactively controls active cycle of a GPS receiver, a WiFi scanner, and an accelerometer. Pilot studies show that SensLoc can correctly detect 94% of the place visits, track 95% of the total travel distance, and still only consume 13% of energy than algorithms that periodically collect coordinates to provide the same information.

Imaging sensors, or “imagers,” embedded in the natural environment enable remote collection of large quantities of data, thus easing the design and deployment of sensing systems in a variety of application domains. Yet, the data collected from such imagers are difficult to interpret due to a variety of “nuisance factors” in the data formation process, such as illumination, vantage point, partial occlusions, etc. These are especially severe in natural environments, where the objects of interest (e.g., plants, animals) have evolved to blend with their habitat, exhibit complex variability in shape and appearance, and perform rapid motions against dynamic backgrounds with rapid illumination changes. We describe three applications that exemplify these problems and the solutions we developed. First, we show how temporal oversampling can simplify the analysis of a slow process such as the avian nesting cycle. Then, we show how to overcome temporal undersampling in order to detect birds at a feeder station. Finally, we show how to exploit temporal consistency to reliably detect pollinators as they visit flowers in the field.

We present a scalable end-to-end system for vision-based monitoring of natural environments, and illustrate its use for the analysis of avian nesting cycles. Our system enables automated analysis of thousands of images, where manual processing would be infeasible. We automate the analysis of raw imaging data using statistics that are tailored to the task of interest. These “features” are a representation to be fed to classifiers that exploit spatial and temporal consistencies. Our testbed can detect the presence or absence of a bird with an accuracy of 82%, count eggs with an accuracy of 84%, and detect the inception of the nesting stage within a day. Our results demonstrate the challenges and potential benefits of using imagers as biological sensors. An exploration of system performance under varying image resolution and frame rate suggest that an in situ adaptive vision system is technically feasible.

Most sensor network research and software design has been guided by an architectural principle that permits multinode data fusion on small-form-factor, resource-poor nodes, or motes . While we were among the earliest promoters of this approach, through experience we found that this principle leads to fragile and unmanageable systems and explore an alternative. The Tenet architecture is motivated by the observation that future large-scale sensor network deployments will be tiered , consisting of motes in the lower tier and masters , relatively unconstrained 32-bit platform nodes, in the upper tier. Tenet constrains multinode fusion to the master tier while allowing motes to process locally-generated sensor data. This simplifies application development and allows mote-tier software to be reused. Applications running on masters task motes by composing task descriptions from a novel tasklet library. Our Tenet implementation also contains a robust and scalable networking subsystem for disseminating tasks and reliably delivering responses. We show that a Tenet pursuit-evasion application exhibits performance comparable to a mote-native implementation while being considerably more compact. We also present two real-world deployments of Tenet system: a structural vibration monitoring application at Vincent Thomas Bridge and an imaging-based habitat monitoring application at James Reserve, and show that tiered architecture scales network capacity and allows reliable delivery of high rate data. 1

As mobile phones advance in functionality and capability, they are being used for more than just communication. Increasingly, these devices are being employed as instruments for introspection into habits and situations of individuals and communities. Many of the applications enabled by this new use of mobile phones rely on contextual information. The focus of this work is on one dimension of context, the transportation mode of an individual when outside. We create a convenient (no specific position and orientation setting) classification system that uses a mobile phone with a built-in GPS receiver and an accelerometer. The transportation modes identified include whether an individual is stationary, walking, running, biking, or in motorized transport. The overall classification system consists of a decision tree followed by a first-order discrete Hidden Markov Model and achieves an accuracy level of 93.6% when tested on a dataset obtained from sixteen individuals.

Detecting visits to semantically meaningful places is important for many emerging mobile applications. We present PlaceSense, a place discovery algorithm suitable for mobile devices that exploits pervasive RF-beacons. By relying on separate mechanisms to detect entrance to and departure from a place and buffering overlapping data for subsequent visits, it is more robust than the state-of-the-art, especially in detecting short visits, places where people are mobile, or where inconsistent beacons are prevalent due to interference. We experimentally evaluate PlaceSense's effectiveness in discovering semantically meaningful places, and compare with other approaches that use coordinates or RF-beacon fingerprints. Our results demonstrate that PlaceSense correctly discovers 92% (compared to between 28% and 65% for previous work) of the visited places and accurately detects their entrance and departure times from both real-life and scripted data sets.

Cellular and Wi-Fi networks now form a global substrate that provides billions of mobile phone users with consistent, location-aware communication and multimedia data access. On this substrate is emerging a new class of mobile phone applications that use the phones location, image and acoustic sensors, and enable people to choose what to sense and when to share data about themselves and their surroundings. Peoples' natural movement through and among living, work, and ldquothirdrdquo spaces, provides spatial and temporal coverage for these modalities, the character of which is impossible to achieve through embedded instrumentation alone. This paper proposes a network service architecture for participatory sensing, describing challenges in (1) network coordination services enabling applications to efficiently select, incentivize and task mobile users based on measures of coverage, capabilities and interests; (2) attestation mechanisms to enable data consumers to assign trust to the data they access; and (3) participatory privacy regulation mechanisms used by data contributors to control what data they share.

PEIR, the Personal Environmental Impact Report, is a participatory sensing application that uses location data sampled from everyday mobile phones to calculate personalized estimates of environmental impact and exposure. It is an example of an important class of emerging mobile systems that combine the distributed processing capacity of the web with the personal reach of mobile technology. This paper documents and evaluates the running PEIR system, which includes mobile handset based GPS location data collection, and server-side processing stages such as HMM-based activity classification (to determine transportation mode); automatic location data segmentation into "trips''; lookup of traffic, weather, and other context data needed by the models; and environmental impact and exposure calculation using efficient implementations of established models. Additionally, we describe the user interface components of PEIR and present usage statistics from a two month snapshot of system use. The paper also outlines new algorithmic components developed based on experience with the system and undergoing testing for integration into PEIR, including: new map-matching and GSM-augmented activity classification techniques, and a selective hiding mechanism that generates believable proxy traces for times a user does not want their real location revealed.

Soil contains vast ecosystems that play a key role in the Earth's water and nutrient cycles, but scientists cannot currently collect the high-resolution data required to fully understand them. In this paper, we present Suelo, an embedded networked sensing system designed for soil monitoring. An important challenge for Suelo is that many soil sensors are inherently fragile and often produce invalid or uncalibrated data. Therefore Suelo is an assisted sensing system: it actively requests the help of a human when necessary to validate, calibrate, repair, or replace sensors. This approach allows us to use available sensors without sacrificing data integrity, while minimizing the human resources required. We tested our system in multiple real soil monitoring deployments and demonstrate that, using human assistance, Suelo produced 91% fewer false negatives and false positives than common fault detection solutions on these datasets.

One of the most important goals of current and future sensor networks is energy-efficient communication of images. This paper presents a quantitative comparison between the energy costs associated with 1) direct transmission of uncompressed images and 2) sensor platform-based JPEG compression followed by transmission of the compressed image data. JPEG compression computations are mapped onto various resource-constrained platforms using a design environment that allows computation using the minimum integer and fractional bit-widths needed in view of other approximations inherent in the compression process and choice of image quality parameters. Advanced applications of JPEG, such as region of interest coding and successive/progressive transmission, are also examined. Detailed experimental results examining the tradeoffs in processor resources, processing/transmission time, bandwidth utilization, image quality, and overall energy consumption are presented.

Networked embedded acoustic sensors and imagers allow scientists to observe biological and environmental phenomena at high sampling rates and multiple scales. Such sampling can create large data sets that often require some form of automated processing to extract useful information. However, to guarantee the accuracy of the data, the scientist must be included in the processing, rather than treating it as a black box, an approach we call interactive environmental sensing. In this paper we describe the challenges of such an approach and motivate it with several examples from bioacoustics, plant phenology and avian biology.

Distributed acoustic sensing underlies an increasingly important class of sensor network applications, from habitat monitoring and bioacoustic census to security applications and virtual fences. VoxNet is a complete hardware and software platform for distributed acoustic monitoring applications that focuses on three key goals: (1) rapid deployment in realistic environments; (2) a high level programming language that abstracts the user from platform and network details and compiles into a high performance distributed application; and (3) an interactive usage model based on run-time installable programs, with the ability to run the same high level program seamlessly over live or stored data. The VoxNet hardware is self-contained and weather-resistant, and supports a four-channel microphone array with automated time synchronization, localization, and network coordination. Using VoxNet, an investigator can visualize phenomena in real-time, develop and tune online analysis, and record raw data for off-line analysis and archival. This paper describes both the hardware and software elements of the platform, as well as the architecture required to support distributed programs running over a heterogeneous network. We characterize the performance of the platform, using both microbenchmarks that evaluate specific aspects of the platform and a real application running in the field.

Dual-radio, dual-processor nodes are an emerging class of wireless sensor network devices that provide both low-energy operation as well as substantially increased computational performance and communication bandwidth for applications. In such systems, the secondary radio and processor operates with sufficiently low power that it may remain always vigilant, while the main processor and primary, high-bandwidth radio remain off until triggered by the application. By exploiting the high energy efficiency of the main processor and primary radio along with proper usage, net operating energy benefits are enabled for applications. The secondary radio provides a constantly available multi-hop network, while paths in the primary network exist only when required. This paper describes a topology control mechanism for establishing an end-to-end path in a network of dual-radio nodes using the secondary radios as a control channel toselectivelywake up nodes along the required end-to-end path. Using numerical models as well as testbed experimentation, we show that our proposed mechanism provides significant energy savings of more than 60% compared to alternative approaches, and that it incurs only moderately greater application latency.

Energy-efficient image communication is one of the most important goals for a large class of current and future sensor network applications. This paper presents a quantitative comparison between the energy costs associated with 1) direct transmission of uncompressed images and 2) sensor platform-based JPEG compression followed by transmission of the compressed image data. JPEG compression computations are mapped onto various resource-constrained sensor platforms using a design environment that allows computation using the minimum integer and fractional bit-widths needed in view of other approximations inherent in the compression process and choice of image quality parameters. Detailed experimental results examining the tradeoffs in processor resources, processing/transmission time, bandwidth utilization, image quality, and overall energy consumption are presented.

The rapid adoption of mobile phones by society over the last decade and the increasing ability to capture, classifying, and transmit a wide variety of data (image, audio, and location) have enabled a new sensing paradigm - where humans carrying mobile phones can act as sensor systems. Human-in-the-loop sensor systems raise many new challenges in areas of sensor data quality assessment, mobility and sampling coordination, and user interaction procedures.

Recent work in wireless embedded networked systems has followed heterogeneous designs, incorporating a mixture of elements from extremely constrained 8- or 16-bit “Motes” to less resource-constrained 32-bit embedded “Microservers.” Emstar is a software environment for developing and deploying complex applications on such heterogeneous networks. Emstar is designed to leverage the additional resources of Microservers by trading off some performance for system robustness in sensor network applications. It enables fault isolation, fault tolerance, system visiblity, in-field debugging, and resource sharing across multiple applications. In order to accomplish these objectives, Emstar is designed to run as a multiprocess system and consists of libraries that implement message-passing IPC primitives, services that support networking, sensing, and time synchronization, and tools that support simulation, emulation, and visualization of live systems, both real and simulated. We evaluate this work by discussing the Acoustic ENSBox, a platform for distributed acoustic sensing that we built using Emstar. We show that by leveraging existing Emstar services, we are able to significantly reduce development time while achieving a high degree of robustness. We also show that a sample application was developed much more quickly on this platform than it would have been otherwise.

Wireless sensor networks (WSNs) are a relatively new and rapidly developing technology; they have a wide range of applications including environmental monitoring, agriculture, and public health. Shared technology is a common usage model for technology adoption in developing countries. WSNs have great potential to be utilized as a shared resource due to their on-board processing and ad-hoc networking capabilities, however their deployment as a shared resource requires that the technical community first address several challenges. The main challenges include enabling sensor portability: (1) the frequent movement of sensors within and between deployments, and rapidly deployable systems; (2) systems that are quick and simple to deploy. We first discuss the feasibility of using sensor networks as a shared resource, and then describe our research in addressing the various technical challenges that arise in enabling such sensor portability and rapid deployment. We also outline our experiences in developing and deploying water quality monitoring wireless sensor networks in Bangladesh and California

We present the design, implementation, and evaluation of the Acoustic Embedded Networked Sensing Box (ENSBox), a platform for prototyping rapid-deployable distributed acoustic sensing systems, particularly distributed source localization. Each ENSBox integrates an ARM processor running Linux and supports key facilities required for source localization: a sensor array, wireless network services, time synchronization, and precise self-calibration of array position and orientation. The ENSBox's integrated, high precision self-calibration facility sets it apart from other platforms. This self-calibration is precise enough to support acoustic source localization applications in complex, realistic environments: e.g., 5 cm average 2D position error and 1.5 degree average orientation error over a partially obstructed 80x50 m outdoor area. Further, our integration of array orientation into the position estimation algorithm is a novel extension of traditional multilateration techniques. We present the result of several different test deployments, measuring the performance of the system in urban settings, as well as forested, hilly environments with obstructing foliage and 20-30 m distances between neighboring nodes.

We will demonstrate the operation of the Acoustic Embedded Networked Sensing Box (ENSBox), a platform for prototyping rapid-deployable distributed acoustic sensing systems. The ENSBox is a Linux-based acoustic sensing system with and integrated, high precision self-calibration facility sets it apart from other platforms. This selfcalibration is precise enough to support acoustic source localization applications in complex, realistic environments: e.g., 5 cm average 2D position error and 1.5 degree average orientation error over a 80x50 m outdoor area.

Most sensor network research and software design has been guided by an architectural principle that permits multi-node data fusion on small-form-factor, resource-poor nodes, or motes. We argue that this principle leads to fragile and unmanageable systems and explore an alternative. The Tenet architecture is motivated by the observation that future large-scale sensor network deployments will be tiered, consisting of motes in the lower tier and masters, relatively unconstrained 32-bit platform nodes, in the upper tier. Masters provide increased network capacity. Tenet constrains multi-node fusion to the master tier while allowing motes to process locally-generated sensor data. This simplifies application development and allows mote-tier software to be reused. Applications running on masters task motes by composing task descriptions from a novel tasklet library. Our Tenet implementation also contains a robust and scalable networking subsystem for disseminating tasks and reliably delivering responses. We show that a Tenet pursuit-evasion application exhibits performance comparable to a mote-native implementation while being considerably more compact.

Small-form-factor, low-power wireless sensors—motes—are convenient to deploy, but lack the bandwidth to capture and transmit raw high-frequency data, such as human voices or neural signals, in real time. Local filtering can help, but we show that the right filter settings depend on changing ambient conditions and network effects such as congestion, which makes them dynamic and unpredictable. Mote collection systems for high-frequency data must support iteratively-tuned, deployment-specific filter settings as well as fast sampling.VANGO, our software system for high-frequency data collection, achieves these goals via integrated processing across network tiers. Bandwidth-limited sensor nodes reduce data in network but rely on microservers, which have greater computational capabilities and a wider scope of observation, to plan how. VANGO provides a cross-platform library for data transformation, measurement, and classification; a fast and low-jitter data acquisition system for motes; and a mechanism to control mote and microserver signal processing. With VANGO we have developed new applications: the first acoustic collection system for motes responsive to changing environmental conditions and user interests, and the first neural spike acquisition application capable of supporting a network of nodes.

We discuss the use of mobility to enhance network performance for a certain class of applications in sensor networks. A major performance bottleneck in sensor networks is energy since it is impractical to replace the batteries in embedded sensor nodes post-deployment. A significant portion of the energy expenditure is attributed to communications and, in particular, the nodes close to the sensor network gateways used for data collection typically suffer a large overhead as these nodes must relay data from the remaining network. Even with compression and in-network processing to reduce the amount of communicated data, all the processed data must still traverse these nodes to reach the gateway. We discuss a network infrastructure based on the use of controllably mobile elements to reduce the communication energy consumption at the energy constrained nodes and, thus, increase useful network lifetime. In addition, our approach yields advantages in delay-tolerant networks and sparsely deployed networks. We first show how our approach helps reduce energy consumption at battery constrained nodes. Second, we describe our system prototype, which utilizes our proposed approach to improve the energy performance. As part of the prototyping effort, we experienced several interesting design choices and trade-offs that affect system capabilities and performance. We describe many of these design challenges and discuss the algorithms developed for addressing these. In particular, we focus on network protocols and motion control strategies. Our methods are tested using a practical system and do not assume idealistic radio range models or operation in unobstructed environments

Recently, several wireless sensor network studies demonstrated large discrepancies between experimentally observed communication properties and properties produced by widely used simulation models. Our first goal is to provide sound foundations for conclusions drawn from these studies by extracting relationships between location (e.g. distance) and communication properties (e.g. reception rate) using non-parametric statistical techniques. The objective is to provide a probability density function that completely characterizes the relationship. Furthermore, we study individual link properties and their correlation with respect to common transmitters, receivers and geometrical location. The second objective is to develop a series of wireless network models that produce networks of arbitrary sizes with realistic properties. We use an iterative improvement-based optimization procedure to generate network instances that are statistically similar to empirically observed networks. We evaluate the accuracy of our conclusions using our models on a set of standard communication tasks, like connectivity maintenance and routing.

Networked infomechanical systems (NIMS) introduces a new actuation capability for embedded networked sensing. By exploiting a constrained actuation method based on rapidly deployable infrastructure, NIMS suspends a network of wireless mobile and fixed sensor nodes in three-dimensional space. This permits run-time adaptation with variable sensing location, perspective, and even sensor type. Discoveries in NIMS environmental investigations have raised requirements for 1) new embedded platforms integrating many diverse sensors with actuators, and 2) advances for in-network sensor data processing. This is addressed with a new and generally applicable processor-preprocessor architecture described in this paper. Also this paper describes the successful integration of R, a powerful statistical computing environment, into the embedded NIMS node platform.

Monitoring of environmental phenomena with embedded networked sensing confronts the challenges of both unpredictable variability in the spatial distribution of phenomena coupled with the demands for a high spatial sampling rate in three dimensions. For example, low distortion mapping of critical solar radiation properties in forest environments may require two-dimensional spatial sampling rates of greater than 10 samples/m/sup 2/ over transects exceeding 1000 m/sup 2/. Clearly, adequate sampling coverage of such transect requires an impractically large number of sensing nodes. A new approach, networked infomechanical system (NIMS), has been introduced to combine autonomous-articulated and static sensor nodes enabling sufficient spatiotemporal sampling density over large transects to meet a general set of environmental mapping demands. This paper describes our work on the critical parts of NIMS, the task allocation module. We present our methodologies and the two basic greedy task allocation policies - based on time of the task arrival (time policy) and distance from the robot to the task (distance policy). We present results from NIMS deployed in a forest reserve and from a lab testbed. The results show that both policies are adequate for the task of spatiotemporal sampling, but also complement each other. Finally, we suggest the future direction of research that would both help us better quantify the performance of our system and create more complex policies.

Monitoring environmental phenomena by distributed sensor sampling confronts the challenge of unpredictable variability in the spatial distribution of phenomena often coupled with demands for a high spatial sampling rate. The introduction of actuation-enabled robotics sensors permits a system to optimize the sampling distribution through runtime adaptation. However, such systems must efficiently dispense sampling points or otherwise suffer from poor temporal response. In this paper, we propose and characterize an active modeling system. In our approach, as the robotic sensor acquires measurement samples of the environment, it builds a model of the phenomenon. Our algorithm is based on an incremental optimization process where the robot supports a continuous, iterative process of 1) collecting samples with maximal coverage in the design space; 2) building the environmental model; 3) predicting sampling point locations that contribute the greatest certainty regarding the phenomenon; and 4) sampling the environment based on a combined measure of information gain and navigation and sampling cost. This can provide significant reductions in the magnitude of field estimation error with a modest navigational trajectory time. We evaluate our algorithm through a simulation, using a combination of static and mobile sensors sampling light illumination field.

Recently, several studies have analyzed the statistical properties of low power wireless links in real environments, clearly demonstrating the differences between experimentally observed communication properties and widely used simulation models. However, most of these studies have not performed in depth analysis of the temporal properties of wireless links. These properties have high impact on the performance of routing algorithms.Our first goal is to study the statistical temporal properties of links in low power wireless communications. We study short term temporal issues, like lagged autocorrelation of individual links, lagged correlation of reverse links, and consecutive same path links. We also study long term temporal aspects, gaining insight on the length of time the channel needs to be measured and how often we should update our models.Our second objective is to explore how statistical temporal properties impact routing protocols. We studied one-to-one routing schemes and developed new routing algorithms that consider autocorrelation, and reverse link and consecutive same path link lagged correlations. We have developed two new routing algorithms for the cost link model: (i) a generalized Dijkstra algorithm with centralized execution, and (ii)a localized distributed probabilistic algorithm.

Understanding how a sensor network system works requires running the system, extracting log files, and manually interpreting system metrics. When interpreting system metrics, we often try to correlate behavior over multiple modalities. For example, if a node is exhibiting strange behaviors, the cause may be due to weak battery, geographically bad placement, collision, interference, sensor failure, algorithmic faults, or a combination of the above. This approach of interpreting metrics is adequate for closed systems such as the ones run in simulations, with limited duration. However, for complex sensor network systems that have already been deployed for weeks or even months in the fields, this approach is difficult, laborious, and error-prone. Thus, a suite of tools to help analyze complex sensor network system is desirable. We have implemented Deployment Analysis System (DAS), a centralized data mining suite designed to better understand sensor networks. It supports visualization and deployment-related queries that allow the user to inspect historical system metrics, environmental data, geographical placements, and system status.

This paper presents the Simple Packet Combining (SPaC) error-correction scheme for wireless sensor networks. Nodes buffer corrupt packets, and when two or more corrupt versions of a packet have been received, a packet combining procedure attempts to recover the original packet from the corrupt copies. Packet combining exploits the broadcast medium and spatial diversity of a multi-hop wireless network by using packets overheard at any node, in addition to the next-hop destination of the packet itself. Unlike point-to-point forward error correction (FEC), packet combining therefore helps multi-node interactions such as multi-hop routing or broadcasting as well as to hop-by-hop communication. Also, SPaC does not transmit redundant overhead on good links and does not require costly probes to estimate channel conditions.We have implemented SPaC as a link-layer extension on sensor nodes; it is transparent to upper layer protocols and has low memory and CPU footprints. We evaluate performance through a combination of analysis, trace-driven simulation, indoor and outdoor testbed micro-benchmarks, and deployment on a live network. The results show significant performance gains, even when accounting for the energy cost of CPU processing. We also present detailed bit-level link measurements and the design and evaluation of a new preamble detection scheme motivated by these measurements.

Recent technological progress in integrated low power CMOS based imaging devices has led to new type of sensors such as Cyclops. Cyclops is a CMOS image sensor, with reduced complexity and power that allows it to mate with typical sensor network nodes such as Motes. This motivates a new class of sensor networks which exploit vision.In this demonstration we introduce a network of Motes that carry Cyclops sensors. In this network, each individual node can be programmed to perform specific operation on the image. These operations include detecting objects in the scene, detecting edges, reporting histogram of the image, getting the image across the network or getting only particular region of interest.The demonstration showcases the functionality of our network to detect objects. Each node in the network is programmed to detect presence of the objects in its field of view. In addition, users can request the whole image or particular region of interest which the presence of the object has been detected. Performance studies as well as architectural choices will be presented along with outstanding challenges and opportunities.

Despite their increasing sophistication, wireless sensor networks still do not exploit the most powerful of the human senses: vision. Indeed, vision provides humans with unmatched capabilities to distinguish objects and identify their importance. Our work seeks to provide sensor networks with similar capabilities by exploiting emerging, cheap, low-power and small form factor CMOS imaging technology. In fact, we can go beyond the stereo capabilities of human vision, and exploit the large scale of sensor networks to provide multiple, widely different perspectives of the physical phenomena.To this end, we have developed a small camera device called Cyclops that bridges the gap between the computationally constrained wireless sensor nodes such as Motes, and CMOS imagers which, while low power and inexpensive, are nevertheless designed to mate with resource-rich hosts. Cyclops enables development of new class of vision applications that span across wireless sensor network. We describe our hardware and software architecture, its temporal and power characteristics and present some representative applications.

Being embedded in the physical world, sensor networks present a wide range of bugs and misbehavior qualitatively different from those in most distributed systems. Unfortunately, due to resource constraints, programmers must investigate these bugs with only limited visibility into the application. This paper presents the design and evaluation of Sympathy, a tool for detecting and debugging failures in sensor networks. Sympathy has selected metrics that enable efficient failure detection, and includes an algorithm that root-causes failures and localizes their sources in order to reduce overall failure notifications and point the user to a small number of probable causes. We describe Sympathy and evaluate its performance through fault injection and by debugging an active application, ESS, in simulation and deployment. We show that for a broad class of data gathering applications, it is possible to detect and diagnose failures by collecting and analyzing a minimal set of metrics at a centralized sink. We have found that there is a tradeoff between notification latency and detection accuracy; that additional metrics traffic does not always improve notification latency; and that Sympathy's process of failure localization reduces.

Time synchronization is critical to sensor networks at many layers of its design and enables better duty-cycling of the radio, accurate localization, beamforming and other collaborative signal processing. While there has been significant work in sensor network synchronization, measurement based studies have been restricted to very short-term (few minutes) datasets and have focused on obtaining accurate instantaneous synchronization. Long-term synchronization has typically been handled by periodic re-synchronization schemes with beacon intervals of a few minutes based on the assumption that long-term drift is too hard to model and predict. Thus, none of this work exploits the temporally correlated behavior of the clock drift. Yet, there are incredible energy gains to be achieved from better modeling and prediction of long-term drift that can provide bounds on long-term synchronization error across a sensor network. Better synchronization can lead to significantly lower duty-cycles of the radio, simplify signal processing and can enable an order of magnitude greater lifetime than current techniques.We measure, evaluate and analyze in-depth the long-term behavior of synchronization skew and drift on typical Mica sensor nodes and develop an efficient long-term time synchronization protocol. We use four real time data sets gathered over periods of 12-30 hours in different environmental conditions to study the interplay between three key parameters that influence long-term synchronization - synchronization rate, history of past synchronization beacons and the estimation scheme. We use this measurement-based study to design an online adaptive time-synchronization algorithm that can adapt to changing clock drift and environmental conditions while achieving application-specified precision with very high probability. We find that our algorithm achieves between one and two orders of magnitude improvement in energy efficiency over currently available time-synchronization approaches.

Wireless sensor networks enable dense sensing of the environment, offering unprecedented opportunities for observing the physical world. This article addresses two key challenges in wireless sensor networks: in-network storage and distributed search. The need for these techniques arises from the inability to provide persistent, centralized storage and querying in many sensor networks. Centralized storage requires multihop transmission of sensor data to Internet gateways which can quickly drain battery-operated nodes.Constructing a storage and search system that satisfies the requirements of data-rich scientific applications is a daunting task for many reasons: (a) the data requirements may be large compared to available storage and communication capacity of resource-constrained nodes, (b) user requirements are diverse and range from identification and collection of interesting event signatures to obtaining a deeper understanding of long-term trends and anomalies in the sensor events, and (c) many applications are in new domains where a priori information may not be available to reduce these requirements.This article describes a lossy, gracefully degrading storage model . We believe that such a model is necessary and sufficient for many scientific applications since it supports both progressive data collection for interesting events as well as long-term in-network storage for in-network querying and processing. Our system demonstrates the use of in-network wavelet-based summarization and progressive aging of summaries in support of long-term querying in storage and communication-constrained networks. We evaluate the performance of our linux implementation and show that it achieves: (a) low communication overhead for multiresolution summarization, (b) highly efficient drill-down search over such summaries, and (c) efficient use of network storage capacity through load-balancing and progressive aging of summaries.

Localization is a key application for sensor networks. We propose a Bayesian method to analyze the lower bound of localization uncertainty in sensor networks. Given the location and sensing uncertainty of individual sensors, the method computes the minimum-entropy target location distribution estimated by the network of sensors. We define the Bayesian bound (BB) as the covariance of such distribution, which is compared with the Cramer-Rao bound (CRB) through simulations. When the observation uncertainty is Gaussian, the BB equals the CRB. The BB is much simpler to derive than the CRB when sensing models are complex. We also characterize the localization uncertainty attributable to the sensor network topology and the sensor observation type through the analysis of the minimum entropy and the CRB. Given the sensor network topology and the sensor observation type, such characteristics can be used to approximately predict where the target can be relatively accurately located.

The capabilities and distributed nature of networked sensors are uniquely suited to the characterization of distributed phenomena in the natural environment. However, environmental characterization by fixed distributed sensors encounters challenges in complex environments. In this paper we describe Networked Infomechanical Systems (NIMS), a new distributed, robotic sensor methodology developed for applications including characterization of environmental structure and phenomena. NIMS exploits deployed infrastructure that provides the benefits of precise motion, aerial suspension, and low energy sustainable operations in complex environments. NIMS nodes may explore a three-dimensional environment and enable the deployment of sensor nodes at diverse locations and viewing perspectives. NIMS characterization of phenomena in a three dimensional space must now consider the selection of sensor sampling points in both time and space. Thus, we introduce a new approach of mobile node adaptive sampling with the objective of minimizing error between the actual and reconstructed spatiotemporal behavior of environmental variables while minimizing required motion. In this approach, the NIMS node first explores as an agent, gathering a statistical description of phenomena using a nested stratified random sampling approach. By iteratively increasing sampling resolution, guided adaptively by the measurement results themselves, this NIMS sampling enables reconstruction of phenomena with a systematic method for balancing accuracy with sampling resource cost in time and motion. This adaptive sampling method is described analytically and also tested with simulated environmental data. Experimental evaluations of adaptive sampling algorithms have also been completed. Specifically, NIMS experimental systems have been developed for monitoring of spatiotemporal variation of atmospheric climate phenomena. A NIMS system has been deployed at a field biology station to map phenomena in a 50m width and 50m span transect in a forest environment. In addition, deployments have occurred in testbed environments allowing additional detailed characterization of sampling algorithms. Environmental variable mapping of temperature, humidity, and solar illumination have been acquired and used to evaluate the adaptive sampling methods reported here. These new methods have been shown to provide a significant advance for efficient mapping of spatially distributed phenomena by NIMS environmental robotics.

We propose an entropy-based sensor selection heuristic for localization. Given 1) a prior probability distribution of the target location, and 2) the locations and the sensing models of a set of candidate sensors for selection, the heuristic selects an informative sensor such that the fusion of the selected sensor observation with the prior target location distribution would yield on average the greatest or nearly the greatest reduction in the entropy of the target location distribution. The heuristic greedily selects one sensor in each step without retrieving any actual sensor observations. The heuristic is also computationally much simpler than the mutual-information-based approaches. The effectiveness of the heuristic is evaluated using localization simulations in which Gaussian sensing models are assumed for simplicity. The heuristic is more effective when the optimal candidate sensor is more informative.

We study four distributed techniques for computing the area of a region in a sensor network. Area calculation is a fundamental sensor network primitive, and distributed, in-network approaches prove more scalable than centralized collection in terms of energy consumption. The four techniques - Delaunay triangulations, Voronoi diagrams, and two new, simpler algorithms, inverse neighborhood and inverse neighborhood with location - vary in computational complexity, communication cost, and information required from the sensor network. We conclude that when sensors know their physical locations, our simple and efficient inverse-neighborhood approach performs comparably to more systematic, but more expensive, computational geometry algorithms. We also analyze the effects of radio range and deployment density on accuracy, and show that topologies derived from real testbeds behave quite differently from commonly seen random topologies with unit disk connectivity.

This work presents a preliminary design and evaluation of Sympathy, a debugging tool for pre-deployment sensor networks. Sympathy consists of mechanisms for collecting system performance metrics with minimal memory overhead; mechanisms for recognizing events based on these metrics; and a system for collecting events and their spatio-temporal context. Sympathy introduces the idea of correlating seemingly unrelated events, and providing context for these events, in order to track down bugs and find their root causes. Eventually, Sympathy will be part of a system that can aid in debugging sensor networks both pre- and post-deployment.

Since the inception of sensor networks, in-network processing has been touted as the enabling technology for long-lived deployments. Radio communication is the overriding consumer of energy in such networks. Therefore, data reduction before transmission, either by compression or feature extraction, will directly and significantly increase network lifetime. This paper evaluates a simple temporal compression scheme designed specifically to be used by mica motes for the compaction of microclimate data. The algorithm makes use of the observation that over a small enough window of time, samples of microclimate data are linear. It finds such windows and generates a series of line segments that accurately represent the data. It compresses data up to 20-to-1 while introducing errors in the order of the sensor hardware's specified margin of error. Furthermore, it is simple, consumes little CPU and requires very little storage when compared to other compression techniques. This paper describes the technique and results using a dataset from a one-year microclimate deployment.

Wireless sensor networks are characterized by collections of small, low-power nodes that collect information about the physical world. Concurrent transmissions caused by the well-known hidden terminal problem result in collisions and packet corruption. Since corrupted packets must be retransmitted, collisions add an additional burden to the already energy constrained system. We present an application-based approach to collision avoidance. We propose two specific algorithms; the first one follows TCP's congestion avoidance algorithm and adjusts the transmission rate when a collision occurs, while the second one shifts packet transmission times to minimize collisions. We evaluated both algorithms through simulations and our results show that our approach can reduce the number of collision-induced retransmissions by a factor of 8 and the energy consumption by up to 50%.

Due to lack of experimental data and sophisticated models derived from such data, most data processing algorithms from the sensor network literature are evaluated with data generated from simple parametric models. Unfortunately, the type of data input used in the evaluation often significantly affects the algorithm performance. Our case studies of a few widely-studied sensor network data processing algorithms demonstrated the need to evaluate algorithms with data across a range of parameters. In conclusion, we propose our synthetic data generation framework.

We propose Voronoi scoping, a distributed algorithm to constrain the dissemination of messages from different sinks. It has the property that a query originated by a given sink is forwarded only to the nodes for which that sink is the closest (under the chosen metric). Thus each query is forwarded to the smallest possible number of nodes, and per-node dissemination overhead does not grow with network size or with number of sinks. The algorithm has a simple distributed implementation and requires only a few bytes of state at each node. Experiments over a network of 54 motes confirm the algorithm's effectiveness.

Computer networks have historically considered support for mobile devices as an extra overhead to be borne by the system. Recently however, researchers have proposed methods by which the network can take advantage of mobile components. We exploit mobility to develop a fluid infrastructure: mobile components are deliberately built into the system infrastructure for enabling specific functionality that is very hard to achieve using other methods. Built-in intelligence helps our system adapt to run time dynamics when pursuing pre-defined performance objectives. Our approach yields significant advantages for energy constrained systems, sparsely deployed networks, delay tolerant networks, and in security sensitive situations. We first show why our approach is advantageous in terms of network lifetime and data fidelity. Second, we present adaptive algorithms that are used to control mobility. Third, we design the communication protocol supporting a fluid infrastructure and long sleep durations on energy-constrained devices. Our algorithms are not based on abstract radio range models or idealized unobstructed environments but founded on real world behavior of wireless devices. We implement a prototype system in which infrastructure components move autonomously to carry out important networking tasks. The prototype is used to validate and evaluate our suggested mobility control methods.

With the advent of tiny networked devices, Mark Weiser's vision of a world embedded with invisible computers is coming to age. Due to their small size and relative ease of deployment, sensor networks have been utilized by zoologists, seismologists and military personnel. In this paper, we investigate the application of sensor networks to the film industry. In particular, we are interested in augmenting film and video footage with sensor data. Unobtrusive sensors are deployed on a film set or in a television studio and on performers. During a filming of a scene, sensor data such as light intensity, color temperature and location are collected and synchronized with each film or video frame. Later, editors, graphics artists and programmers can view this data in synchronization with film and video playback. For example, such data can help define a new level of seamless integration between computer graphics and real world photography. A real-time version of our system would allow sensor data to trigger camera movement and cue special effects. In this paper, we discuss the design and implementation of the first part of our embedded film set environment, the augmented recording system. Augmented recording is a foundational component for the UCLA Hypermedia Studio's research into the use of sensor networks in film and video production. In addition, we have evaluated our system in a television studio.

A key challenge in sensor networks is ensuring the sustainability of the system at the required performance level, in an autonomous manner. Sustainability is a major concern because of severe resource constraints in terms of energy, bandwidth and sensing capabilities in the system. In this paper, we envision the use of a new design dimension to enhance sustainability in sensor networks - the use of controlled mobility. We argue that this capability can alleviate resource limitations and improve system performance by adapting to deployment demands. While opportunistic use of external mobility has been considered before, the use of controlled mobility is largely unexplored. We also outline the research issues associated with effectively utilizing this new design dimension. Two system prototypes are described to present first steps towards realizing the proposed vision.

Monitoring of environmental phenomena with embedded networked sensing confronts the challenges of both unpredictable variability in the spatial distribution of phenomena, coupled with demands for a high spatial sampling rate in three dimensions. For example, low distortion mapping of critical solar radiation properties in forest environments may require two-dimensional spatial sampling rates of greater than 10 samples/m2 over transects exceeding 1000 m2. Clearly, adequate sampling coverage of such a transect requires an impractically large number of sensing nodes. This paper describes a new approach where the deployment of a combination of autonomous-articulated and static sensor nodes enables sufficient spatiotemporal sampling densityo ver large transects to meet a general set of environmental mapping demands.To achieve this we have developed an embedded networked sensor architecture that merges sensing and articulation with adaptive algorithms that are responsive to both variabilityin environmental phenomena discovered bythe mobile sensors and to discrete events discovered byst atic sensors. We begin byde scribing the class of important driving applications, the statistical foundations for this new approach, and task allocation. We then describe our experimental implementation of adaptive, event aware, exploration algorithms, which exploit our wireless, articulated sensors operating with deterministic motion over large areas. Results of experimental measurements and the relationship among sampling methods, event arrival rate, and sampling performance are presented.

Recently deployed Wireless Sensor Network systems (WSNs) are increasingly following heterogeneous designs, incorporating a mixture of elements with widely varying capabilities. The development and deployment of WSNs rides heavily on the availability of simulation, emulation, visualization and analysis support. In this work, we develop tools specifically to support heterogeneous systems, as well as to support the measurement and visualization of operational systems that is critical to addressing the inevitable problems that crop up in deployment. Our system differs from related systems in three key ways: in its ability to simulate and emulate heterogeneous systems in their entirety, in its extensive support for integration and interoperability between motes and microservers, and in its unified set of tools that capture, view, and analyze real time debugging information from simulations, emulations, and deployments.

We propose a new configuration language, component and service library, and compiler that make it easier to develop efficient sensor network applications. Our goal is the construction of smart application service libraries: high-level libraries that implement concepts like routing trees and periodic sensing, and that combine automatically into efficient programs. Important language features include flexible control over component sharing and transitive arrow connections, which let independently-implemented services knit themselves into integrated control flow paths. Our language, library, and compiler are collectively called SNACK (Sensor Network Application Construction Kit). We describe them, and present and evaluate a simple SNACK-based multihop data collection application. This application uses SNACK language features to provide both simplicity (excluding reusable service definitions, its description is three lines long) and efficiency (it performs comparably to the well-known Surge application).

No abstract available.

Technological progress in integrated, low power CMOS imaging [1] and maturing low power wireless sensor network platforms, motivate a new and rich design space exploiting in network dense imaging. In particular, by combining comparably low power CMOS cameras and low power wireless sensor nodes, and implementing on board compression and image analysis techniques, we can greatly enhance the application of dense wireless sensor networks to phenomena that are most readily observed in the optical domain.

Structural monitoring---the collection and analysis of structural response to ambient or forced excitation--is an important application of networked embedded sensing with significant commercial potential. The first generation of sensor networks for structural monitoring are likely to be data acquisition systems that collect data at a single node for centralized processing. In this paper, we discuss the design and evaluation of a wireless sensor network system (called Wisden for structural data acquisition. Wisden incorporates two novel mechanisms, reliable data transport using a hybrid of end-to-end and hop-by-hop recovery, and low-overhead data time-stamping that does not require global clock synchronization. We also study the applicability of wavelet-based compression techniques to overcome the bandwidth limitations imposed by low-power wireless radios. We describe our implementation of these mechanisms on the Mica-2 motes and evaluate the performance of our implementation. We also report experiences from deploying Wisden on a large structure.

Embedded networked sensors promise to revolutionize the way we interact with our physical environment and require scalable, ad hoc deployable and energy-efficient node localization/positioning.This paper describes the motivation, design, implementation, and experimental evaluation (on sharply resource-constrained devices) of a self-configuring localization system using radio beacons. We identify beacon density as an important parameter in determining localization quality, which saturates at a transition density. We develop algorithms to improve localization quality by (i) automating placement of new beacons at low densities (HEAP) and (ii) rotating functionality among redundant beacons while increasing system lifetime at high densities (STROBE).

Wireless sensor networks have been attracting increasing research interest given the recent advances in microelectronics, array processing, and wireless networking. Consisting of a large collection of small, wireless, low-cost, integrated sensing, computing and communicating nodes capable of performing various demanding collaborative space-time processing tasks, wireless sensor network technology poses various unique design challenges, particularly for real-time operation. We review the approximate maximum-likelihood (AML) method for source localization and direction-of-arrival (DOA) estimation. Then, we consider the use of least-squares method (LS) method applied to DOA bearing crossings to perform source localization. A novel virtual array model applicable to the AML-DOA estimation method is proposed for reverberant scenarios. Details on the wireless acoustical testbed are given. We consider the use of Compaq iPAQ 3760s, which are handheld, battery-powered device normally meant to be used as personal organizers (PDAs), as sensor nodes. The iPAQ provide a reasonable balance of cost, availability, and functionality. It has a build in StrongARM processor, microphone, codec for acoustic acquisition and processing, and a PCMCIA bus for external IEEE 802.11b wireless cards for radio communication. The iPAQs form a distributed sensor network to perform real-time acoustical beamforming. Computational times and associated real-time processing tasks are described. Field measured results for linear, triangular, and square subarrays in free-space and reverberant scenarios are presented. These results show the effective and robust operation of the proposed algorithms and their implementations on a real-time acoustical wireless testbed.

Advances in microsensor and radio technology enable small but smart sensors to be deployed for a wide range of environmental monitoring applications. The low-per node cost allows these wireless networks of sensors and actuators to be densely distributed. The nodes in these dense networks coordinate to perform the distributed sensing and actuation tasks. Moreover, as described in this paper, the nodes can also coordinate to exploit the redundancy provided by high density so as to extend overall system lifetime. The large number of nodes deployed in this systems preclude manual configuration, and the environmental dynamics precludes design-time preconfiguration. Therefore, nodes have to self-configure to establish a topology that provides communication under stringent energy constraints. ASCENT builds on the notion that, as density increases, only a subset of the nodes is necessary to establish a routing forwarding backbone. In ASCENT, each node assesses its connectivity and adapts its participation in the multihop network topology based on the measured operating region. This paper motivates and describes the ASCENT algorithm and presents analysis, simulation, and experimental measurements. We show that the system achieves linear increase in energy savings as a function of the density and the convergence time required in case of node failures while still providing adequate connectivity.

The advent of multicast and the growth and complexity of the Internet has complicated network protocol design and evaluation. Evaluation of Internet protocols usually uses random scenarios or scenarios based on designers' intuition. Such an approach may be useful for average case analysis but does not cover boundary-point (worst or best case) scenarios. To synthesize boundary-point scenarios, a more systematic approach is needed. In this paper, we present a method for automatic synthesis of worst and best case scenarios for protocol boundary-point evaluation. Our method uses a fault-oriented test generation (FOTG) algorithm for searching the protocol and system state space to synthesize these scenarios. The algorithm is based on a global finite state machine (FSM) model. We extend the algorithm with timing semantics to handle end-to-end delays and address performance criteria. We introduce the notion of a virtual LAN to represent delays of the underlying multicast distribution tree. Our algorithms utilize implicit backward search using branch and bound techniques and start from given target events. As a case study, we use our method to evaluate variants of the timer suppression mechanism, used in various multicast protocols, with respect to two performance criteria: overhead of response messages and response time. Simulation results for reliable multicast protocols show that our method provides a scalable way for synthesizing worst case scenarios automatically. Results obtained using stress scenarios differ dramatically from those obtained through average case analyses. We hope for our method to serve as a model for applying systematic evaluation to other multicast protocols.

This paper proposes S-MAC, a medium access control (MAC) protocol designed for wireless sensor networks. Wireless sensor networks use battery-operated computing and sensing devices. A network of these devices will collaborate for a common application such as environmental monitoring. We expect sensor networks to be deployed in an ad hoc fashion, with nodes remaining largely inactive for long time, but becoming suddenly active when something is detected. These characteristics of sensor networks and applications motivate a MAC that is different from traditional wireless MACs such as IEEE 802.11 in several ways: energy conservation and self-configuration are primary goals, while per-node fairness and latency are less important. S-MAC uses a few novel techniques to reduce energy consumption and support self-configuration. It enables low-duty-cycle operation in a multihop network. Nodes form virtual clusters based on common sleep schedules to reduce control overhead and enable traffic-adaptive wake-up. S-MAC uses in-channel signaling to avoid overhearing unnecessary traffic. Finally, S-MAC applies message passing to reduce contention latency for applications that require in-network data processing. The paper presents measurement results of S-MAC performance on a sample sensor node, the UC Berkeley Mote, and reveals fundamental tradeoffs on energy, latency and throughput. Results show that S-MAC obtains significant energy savings compared with an 802.11-like MAC without sleeping.

In this paper, we consider the use of a Compaq iPAQ 3760s, equipped with a built-in microphone and an external wireless card, for acoustic acquisition and processing to perform a distributed acoustical beamforming. Time synchronization among the microphones is achieved by the reference-broadcast synchronization method. Two beamforming algorithms, based on the time difference of arrivals (TDOA) among the microphones followed by a least-squares estimation, and the maximum-likelihood (ML) parameter estimation method, are used to perform source detection, enhancement, localization, delay-steered beamforming, and direction-of-arrival estimation. Experimental beamforming results using the iPAQs and the wireless network are reported.

We are developing an acoustic habitat-monitoring sensor network that recognizes and locates specific animal calls in real time. We investigate the system requirements of such a real-time acoustic monitoring network. We propose a system architecture and a set of lightweight collaborative signal processing algorithms that achieve real-time behavior while minimizing inter-node communication to extend the system lifetime. In particular, the target classification is based on spectrogram pattern matching while the target localization is based on beamforming using time difference of arrival (TDOA). We describe our preliminary implementation on a commercial off the shelf (COTS) testbed and present its performance based on testbed measurements.

We study the feasibility of extending the lifetime of a wireless sensor network by exploiting mobility. In our system, a small percentage of network nodes are autonomously mobile, allowing them to move in search of energy, recharge, and delivery energy to immobile, energy-depleted nodes. We term this approach energy harvesting. We characterize the problem of uneven energy consumption, suggest energy harvesting as a possible solution, and provide a simple analytical framework to evaluate energy consumption and our scheme. Data from initial feasibility experiments using energy harvesting show promising results.

Wireless sensor networks enable dense sensing of the environment, offering unprecedented opportunities for observing the physical world. Centralized data collection and analysis adversely impact sensor node lifetime. Previous sensor network research has, therefore, focused on in network aggregation and query processing, but has done so for applications where the features of interest are known a priori. When features are not known a priori, as is the case with many scientific applications in dense sensor arrays, efficient support for multi-resolution storage and iterative, drill-down queries is essential.Our system demonstrates the use of in-network wavelet-based summarization and progressive aging of summaries in support of long-term querying in storage and communication-constrained networks. We evaluate the performance of our linux implementation and show that it achieves: (a) low communication overhead for multi-resolution summarization, (b) highly efficient drill-down search over such summaries, and (c) efficient use of network storage capacity through load-balancing and progressive aging of summaries.

A distinguishing characteristic of wireless sensor networks is the opportunity to exploit characteristics of the application at lower layers. This approach is encouraged by device resource constraints, and acceptable because devices are inexpensive and numerous enough that they can be dedicated to specific applications. Many data dissemination protocols have been proposed for multi-hop communication in sensor networks, each evaluated in some scenario. The premise of this paper is that, if protocols are designed to exploit application requirements, then no one protocol can be optimized for all applications.Instead, a family of protocols are needed, with guidance to match protocol to application. We show through field experiments with two tracking applications that choice of diffusion algorithm can affect application performance by 40--60%. These applications motivate the design of two new diffusion algorithms: push and one-phase pull diffusion. We describe these algorithms in comparison to previous algorithms, then systematically explore their performance as the number of sinks and sources, the traffic rate and node placement varies, and with and without geographic proximity in node placement and with and without geographically scoped communication. We characterize algorithm performance and highlight the effect of the choice of algorithm parameters. The end result of this work are guidelines to help application developers to match dissemination algorithms to application performance requirements.

We propose a novel entropy-based sensor selection heuristic for localization. Given 1) a prior probability distribution of the target location, and 2) the locations and the sensing characteristics of a set of additional sensors, we would like to select an optimal additional sensor such that fusion of its measurements with existing information would yield the greatest entropy reduction of the target location distribution. The heuristic can select a sub-optimal additional sensor without retrieving the measurements of candidate sensors. The heuristic is computationally much simpler than the mutual information based sensor selection approaches for localization and tracking [1, 2]. Just as those existing approaches do, the heuristic greedily selects one sensor in each step.

Advances in microelectronics, array processing, and wireless networking have motivated the analysis and design of low-cost integrated sensing, computing, and communicating nodes capable of performing various demanding collaborative space-time processing tasks. In this paper, we consider the problem of coherent acoustic sensor array processing and localization on distributed wireless sensor networks. We first introduce some basic concepts of beamforming and localization for wide-band acoustic sources. A review of various known localization algorithms based on time-delay followed by least-squares estimations as well as the maximum-likelihood method is given. Issues related to practical implementation of coherent array processing, including the need for fine-grain time synchronization, are discussed. Then we describe the implementation of a Linux-based wireless networked acoustic sensor array testbed, utilizing commercially available iPAQs with built-in microphones, codecs, and microprocessors, plus wireless Ethernet cards, to perform acoustic source localization. Various field-measured results using two localization algorithms show the effectiveness of the proposed testbed. An extensive list of references related to this work is also included.

Advances in processor, memory, and radio technology enable small and cheap nodes capable of sensing, communication, and computation. Networks of such nodes can coordinate to perform distributed sensing of environmental phenomena. We explore the directed diffusion paradigm for such coordination. Directed diffusion is data-centric in that all communication is for named data. All nodes in a directed-diffusion-based network are application aware. This enables diffusion to achieve energy savings by selecting empirically good paths and by caching and processing data in-network (e.g., data aggregation). We explore and evaluate the use of directed diffusion for a simple remote-surveillance sensor network analytically and experimentally. Our evaluation indicates that directed diffusion can achieve significant energy savings and can outperform idealized traditional schemes (e.g., omniscient multicast) under the investigated scenarios.

As the cost of embedded sensors and actuators drops, new applications will arise that exploit high density networks of small devices capable of a variety of sensing tasks. Although individual devices may have limited functionality, the true value of the system comes from the emergent behavior that arises when data from many places in the system is combined. This type of data fusion has a number of requirements, but two of the most important are: 1) synchronized time, precise enough to resolve movement in the sensed phenomenon (e.g., sound); and 2) known geographic locations, on a similar scale to the sensors' size and deployment density. However, the installation cost of a localization system with sufficient granularity is considerable, because of the large amount of effort required to deploy such a system and make all the measurements required to tune it. In this paper, we describe a system based on COTS components that incorporates our novel time synchronization and acoustic ranging techniques. The result is a low-cost, readily available platform for distributed, coherent signal processing.

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

Advances in micro-sensor and radio technology will enable small but smart sensors to be deployed for a wide range of environmental monitoring applications. The low per-node cost will allow these wireless networks of sensors and actuators to be densely distributed. The nodes in these dense networks will coordinate to perform the distributed sensing tasks. Moreover, as described in this paper, the nodes can also coordinate to exploit the redundancy provided by high density, so as to extend overall system lifetime. The large number of nodes deployed in these systems will preclude manual configuration, and the environmental dynamics will preclude design-time pre-configuration. Therefore, nodes will have to self-configure to establish a topology that provides communication and sensing coverage under stringent energy constraints. In ASCENT, each node assesses its connectivity and adapts its participation in the multi-hop network topology based on the measured operating region. This paper motivates and describes the ASCENT algorithm and presents simulation and experimental measurements.

This paper proposes S-MAC, a medium-access control (MAC) protocol designed for wireless sensor networks. Wireless sensor networks use battery-operated computing and sensing devices. A network of these devices will collaborate for a common application such as environmental monitoring. We expect sensor networks to be deployed in an ad hoc fashion, with individual nodes remaining largely inactive for long periods of time, but then becoming suddenly active when something is detected. These characteristics of sensor networks and applications motivate a MAC that is different from traditional wireless MACs such as IEEE 802.11 in almost every way: energy conservation and self-configuration are primary goals, while per-node fairness and latency are less important. S-MAC uses three novel techniques to reduce energy consumption and support self-configuration. To reduce energy consumption in listening to an idle channel, nodes periodically sleep. Neighboring nodes form virtual clusters to auto-synchronize on sleep schedules. Inspired by PAMAS, S-MAC also sets the radio to sleep during transmissions of other nodes. Unlike PAMAS, it only uses in-channel signaling. Finally, S-MAC applies message passing to reduce contention latency for sensor-network applications that require store-and-forward processing as data move through the network. We evaluate our implementation of S-MAC over a sample sensor node, the Mote, developed at University of California, Berkeley. The experiment results show that, on a source node, an 802.11-like MAC consumes 2-6 times more energy than S-MAC for traffic load with messages sent every 1-10 s.

It is important to have continuously updated information about network resources and application activities in a wireless sensor network after it is deployed in an unpredictable environment. Such information can help notify users of resource depletion or abnormal activities. However, constrained by the low user-to-node ratio, limited energy and bandwidth resources, it is infeasible to extract the state of each individual node. In this paper, we propose an approach to constructing abstracted scans of sensor network health by applying in-network aggregation of network state. Specifically, we design a residual energy scan which approximately depicts the remaining energy distribution within a sensor network. Simulations show that our approach has good scalability and energy-efficiency characteristics, compared to continuously extracting the residual energy level individually from each node.

Pervasive micro-sensing and actuation may revolutionize the way in which we understand and manage complex physical systems: from airplane wings to complex ecosystems. The capabilities for detailed physical monitoring and manipulation offer enormous opportunities for almost every scientific discipline, and it will alter the feasible granularity of engineering. We identify opportunities and challenges for distributed signal processing in networks of these sensing elements and investigate some of the architectural challenges posed by systems that are massively distributed, physically-coupled, wirelessly networked, and energy limited.

Beacon placement strongly affects the quality of spatial localization, a critical service for context-aware applications in wireless sensor networks; yet this aspect of localization has received little attention. Fixed beacon placement approaches such as uniform and very dense placement are not always viable and will be inadequate in very noisy environments in which sensor networks may be expected to operate (with high terrain and propagation uncertainties). We motivate the need for empirically adaptive beacon placement and outline a general approach based on exploration and instrumentation of the terrain conditions by a mobile human or robot agent. We design, evaluate and analyze three novel adaptive beacon placement algorithms using this approach for localization based on RF-proximity. In our evaluation, we find that beacon density rather than noise level has a more significant impact on beacon placement algorithms. Our beacon placement algorithms are applicable to a low (beacon) density regime of operation. Noise makes moderate density regimes more improvable.

Recent advances in miniaturization and low-cost, low-power design have led to active research in large-scale, highly distributed systems of small, wireless, low-power unattended sensors and actuators. We explore the use of Random, Ephemeral TRansaction Identifiers (RETRI) in such systems, and contrast it with the typical design philosophy of using static identifiers in roles such as node addressing or efficient data naming. Instead of using statically assigned identifiers that are guaranteed to be unique, nodes randomly select probabilistically unique identifiers for each new transaction. We show how this randomized scheme can significantly improve the system's energy efficiency in contexts where that efficiency is paramount, such as energy-constrained wireless sensor networks. Benefits are realized if the typical data size is small compared to the size of an identifier, and the number of transactions seen by an individual node is small compared to the number of nodes that exist in the entire system. Our scheme is designed to scale well: identifier sizes grow with a system's density not its overall size. We quantify these benefits using an analytic model that predicts our scheme's efficiency. We also describe an implementation as applied to packet fragmentation and an experiment that validates our model.

One approach to achieving scalability in reliable multicast is to use a hierarchy. A hierarchy can be established at the application level, or by using router-assist. With router-assist we have more fine-grain control over the placement of error-recovery functionality, therefore, a hierarchy produced by assistance from the routers is expected to have better performance. In this paper, we test this hypothesis by comparing two schemes, one that uses an application-level hierarchy (ALH) and another that uses router-assisted hierarchy (RAH). Contrary to our expectations, we find that the qualitative performance of ALH is comparable to RAH. We do not model the overhead of creating the hierarchy nor the cost of adding router-assist to the network. Therefore, our conclusions inform rather than close the debate of which approach is better.

The impact of routing policy on Internet paths is poorly understood. In theory, the policy can inflate shortest-router-hop paths. To our knowledge, the extent of this inflation has not been previously examined. Using a simplified model of the routing policy in the Internet, we obtain approximate indications of the impact of policy routing on Internet paths. Our findings suggest that the routing policy does impact the length of Internet paths significantly. For instance, in our model of the routing policy, some 20% of Internet paths are inflated by more than five router-level hops.

If one assumes I have not gone insane, credit for this may go to my family, who have provided endless emotional support.In particular, I'd like to thank my parents Norton and Sandy, and siblings Franny and David, for tirelessly being there through success and failure.I must thank Dana for giving me a great reason to be in Santa Monica by 6:17 every Friday, while having patience and understanding during the times that I can't make it.These people are so close to my heart, and have given me such strength and encouragement, that "thank" seems too cold and empty of a word.I'd also like to thank Gary Klapow-his patient instruction has made Michael Althsuler's words (Chapter 10) a literal reality for me.At a time when I felt that my life had been consumed by digital work, he helped me enjoy an old hobby in analog rather than digital form.Finally, I should of course thank Reza, without whom I might have gone down a completely different path.This one has worked out pretty well.

Many applications of robotics and embedded sensor technology can benefit from fine-grained localization. Fine-grained localization can simplify multi-robot collaboration, enable energy efficient multi-hop routing for low-power radio networks, and enable automatic calibration of distributed sensing systems. We focus on range estimation, a critical prerequisite for fine-grained localization. While many mechanisms for range estimation exist, any individual mode of sensing can be blocked or confused by the environment. We present and analyze an acoustic ranging system that performs well in the presence of many types of interference, but can return incorrect measurements in non-line-of-sight conditions. We then suggest how evidence from an orthogonal sensory channel might be used to detect and eliminate these measurements. The work illustrates the more general research theme of combining multiple modalities to obtain robust results.

No abstract available.

We introduce a geographical adaptive fidelity (GAF) algorithm that reduces energy consumption in ad hoc wireless networks. GAF conserves energy by identifying nodes that are equivalent from a routing perspective and then turning off unnecessary nodes, keeping a constant level of routing fidelity. GAF moderates this policy using application- and system-level information; nodes that source or sink data remain on and intermediate nodes monitor and balance energy use. GAF is independent of the underlying ad hoc routing protocol; we simulate GAF over unmodified AODV and DSR. Analysis and simulation studies of GAF show that it can consume 40% to 60% less energy than an unmodified ad hoc routing protocol. Moreover, simulations of GAP suggest that network lifetime increases proportionally to node density; in one example, a four-fold increase in node density leads to network lifetime increase for 3 to 6 times (depending on the mobility pattern). More generally, GAF is an example of adaptive fidelity, a technique proposed for extending the lifetime of self-configuring systems by exploiting redundancy to conserve energy while maintaining application fidelity.

Previously proposed sensor network data dissemination schemes require periodic low-rate flooding of data in order to allow recovery from failure. We consider constructing two kinds of multipaths to enable energy efficient recovery from failure of the shortest path between source and sink. Disjoint multipath has been studied in the liteature. w propose a model braided multipath scheme, which results in several partially disjoint multipath schemes. We find that braided multipaths are a viable alternative for energy-efficient recovery from isolated and patterned failures

In most distributed systems, naming of nodes for low-level communication leverages topological location (such as node addresses) and is independent of any application. In this paper, we investigate an emerging class of distributed systems where low-level communication does not rely on network topological location. Rather, low-level communication is based on attributes that are external to the network topology and relevant to the application. When combined with dense deployment of nodes, this kind of named data enables in-network processing for data aggregation, collaborative signal processing, and similar problems. These approaches are essential for emerging applications such as sensor networks where resources such as bandwidth and energy are limited. This paper is the first description of the software architecture that supports named data and in-network processing in an operational, multi-application sensor-network. We show that approaches such as in-network aggregation and nested queries can significantly affect network traffic. In one experiment aggregation reduces traffic by up to 42% and nested queries reduce loss rates by 30%. Although aggregation has been previously studied in simulation, this paper demonstrates nested queries as another form of in-network processing, and it presents the first evaluation of these approaches over an operational testbed.

We present a new methodology for developing systematic and automatic test generation algorithms for multipoint protocols. These algorithms attempt to synthesize network topologies and sequences of events that stress the protocol's correctness or performance. This problem can be viewed as a domain-specific search problem that suffers from the state space explosion problem. One goal of this work is to circumvent the state space explosion problem utilizing knowledge of network and fault modeling, and multipoint protocols. The two approaches investigated are based on forward and backward search techniques. We use an extended finite state machine (FSM) model of the protocol. The first algorithm uses forward search to perform reduced reachability analysis. Using domain-specific information for multicast routing over LAN, the algorithm complexity is reduced from exponential to polynomial in the number of routers. This approach, however, does not fully automate topology synthesis. The second algorithm, the fault-oriented test generation, uses backward search for topology synthesis and uses backtracking to generate event sequences instead of searching forward from initial states. Using these algorithms, we have conducted studies for correctness of the multicast routing protocol PIM.

A scalable object location service can enable users to search for various objects in an environment where many small, networked devices are attached to objects. We investigate two hierarchical, self-configuring or unattended approaches for an efficient object location service. Each approach has its advantages and disadvantages based on the anticipated load. The first approach, SCOUT-AGG, is based on aggregation of object names. The second approach, SCOUT-MAP, is based on indirection, where information about an object is stored at the locator sensor for the object. The relative efficiency of SCOUT-AGG and SCOUT-MAP can be characterized by the query to mobility, update rate of the system. SCOUT-AGG performs better for low query to update rate but its performance deteriorates in general relative to SCOUT-MAP as the queries to update rate increases. The rate of performance deterioration depends on query specificity (i.e., queries for a specific object or for any object of a particular type). SCOUT-MAP generally exhibits better load balancing than SCOUT-AGG for various scenarios. We support the above results through simple analytical modeling and simulation.

The Internet has witnessed a rapid growth in deployment of Web-based streaming applications during recent years. In these applications, the server should be able to perform end-to-end congestion control and quality adaptation to match the delivered stream quality to the average available bandwidth. Thus the delivered quality is limited by the bottleneck bandwidth on the path to the client. This paper proposes a proxy caching mechanism for layered-encoded multimedia streams in the Internet to maximize the delivered quality of popular streams to interested clients. The main challenge is to replay a quality-variable cached stream while performing quality adaptation effectively in response to the variations in available bandwidth. We present a prefetching mechanism to support higher quality cached streams during subsequent playbacks and improve the quality of the cached stream with its popularity. We exploit inherent properties of multimedia streams to extend the semantics of popularity and capture both level of interest among clients and usefulness of a layer in the cache. We devise a fine-grain replacement algorithm suited for layered-encoded streams. Our simulation results show that the interaction between the replacement algorithm and prefetching mechanism causes the state of the cache to converge to an efficient state such that the quality of a cached stream is proportional to its popularity, and the variations in quality of a cached stream are inversely proportional to its popularity. This implies that after serving several requests for a stream, the proxy can effectively hide low bandwidth paths to the original server from interested clients.

Advances in processor, memory and radio technology will enable small and cheap nodes capable of sensing, communication and computation. Networks of such nodes can coordinate to perform distributed sensing of environmental phenomena. In this paper, we explore the directed diffusion paradigm for such coordination. Directed diffusion is datacentric in that all communication is for named data. All nodes in a directed diffusion-based network are application-aware. This enables diffusion to achieve energy savings by selecting empirically good paths and by caching and processing data in-network. We explore and evaluate the use of directed diffusion for a simple remote-surveillance sensor network.

Fault isolation has received little attention in the Internet research literature. We take a step towards addressing this deficiency, exploring robust and scalable techniques by which multicast receivers can (in some cases, approximately) locate the on-tree router responsible for a route change, or the link responsible for significant packet loss. A common property of our techniques is that receivers with overlapped paths coordinate to share the responsibility of monitoring paths to the source. Our techniques assume no additional path monitoring capability other than that provided by multicast traceroute (mtrace).

Of the many distributed applications designed for the Internet, the successful ones are those that have paid careful attention to scale and robustness. These applications share several design principles. In this paper, we illustrate the application of these principles to common network monitoring tasks. Specifically, we describe and evaluate 1) a robust distributed topology discovery mechanism and 2) a mechanism for scalable fault isolation in multicast distribution trees. Our mechanisms reveal a different design methodology for network monitoring-one that carefully trades off monitoring fidelity (where necessary) for more graceful degradation in the presence of different kinds of network dynamics.

Streaming audio and video applications are becoming increasingly popular on the Internet, and the lack of effective congestion control in such applications is now a cause for significant concern. The problem is one of adapting the compression without requiring video servers to reencode the data, and fitting the resulting stream into the rapidly varying available bandwidth. At the same time, rapid fluctuations in quality will be disturbing to the users and should be avoided. We present a mechanism for using layered video in the context of unicast congestion control. This quality adaptation mechanism adds and drops layers of the video stream to perform long-term coarse-grain adaptation, while using a TCP-friendly congestion control mechanism to react to congestion on very short timescales. The mismatches between the two timescales are absorbed using buffering at the receiver. We present an efficient scheme for the distribution of available bandwidth among the active layers. Our scheme allows the server to trade short-term improvement for long-term smoothing of quality. We discuss the issues involved in implementing and tuning such a mechanism, and present our simulation results.

Current multicast routing protocols can be classified into three types according to how the multicast tree is established: broadcast and prune (e.g., DVMRP, PIM-DM), membership advertisement (e.g., MO-SPF), and rendezvous-based (e.g., CBT, PIM-SM). Rendezvous-based protocols associate with each logical multicast group address, a physical unicast address, referred to as the 'core' or 'rendezvous point' (RP). Members first join a multicast tree rooted at this rendezvous point in order to receive data packets sent to the group. Rendezvous mechanisms are well suited to large wide-area networks because they distribute group-specific data and membership information only to those routers that are on the multicast distribution tree. However, rendezvous protocols require a bootstrap mechanism to map each logical multicast address to its current physical rendezvous point address. The bootstrap mechanism must adapt to network and router failures but should minimize unnecessary changes in the group-to-RP mapping. In addition, the bootstrap mechanism should be transparent to the hosts. This paper describes and analyzes the bootstrap mechanism developed for PIM-SM. The mechanism employs an algorithmic mapping of multicast group to rendezvous point address, based on a set of available RPs distributed throughout a multicast domain. The primary evaluation measures are convergence time, message distribution overhead, balanced assignment of groups to RPs, and host impact. The mechanism as a whole, and the design lessons in particular, are applicable to other rendezvous-based multicast routing protocols as well.

End-to-end congestion control mechanisms have been critical to the robustness and stability of the Internet. Most of today's Internet traffic is TCP, and we expect this to remain so in the future. Thus, having "TCP-friendly" behavior is crucial for new applications. However, the emergence of non-congestion-controlled realtime applications threatens unfairness to competing TCP traffic and possible congestion collapse. We present an end-to-end TCP-friendly rate adaptation protocol (RAP), which employs an additive-increase, multiplicative-decrease (AIMD) algorithm. It is well suited for unicast playback of realtime streams and other semi-reliable rate-based applications. Its primary goal is to be fair and TCP-friendly while separating network congestion control from application-level reliability. We evaluate RAP through extensive simulation, and conclude that bandwidth is usually evenly shared between TCP and RAP traffic. Unfairness to TCP traffic is directly determined by how TCP diverges from the AIMD algorithm. Basic RAP behaves in a TCP-friendly fashion in a wide range of likely conditions, but we also devised a fine-grain rate adaptation mechanism to extend this range further. Finally, we show that deploying RED queue management can result in an ideal fairness between TCP and RAP traffic.

Article Free Access Share on Next century challenges: scalable coordination in sensor networks Authors: Deborah Estrin USC/Information Sciences Institute, 4676 Admiralty Way, Marina del Rey, CA USC/Information Sciences Institute, 4676 Admiralty Way, Marina del Rey, CAView Profile , Ramesh Govindan USC/Information Sciences Institute, 4676 Admiralty Way, Marina del Rey, CA USC/Information Sciences Institute, 4676 Admiralty Way, Marina del Rey, CAView Profile , John Heidemann USC/Information Sciences Institute, 4676 Admiralty Way, Marina del Rey, CA USC/Information Sciences Institute, 4676 Admiralty Way, Marina del Rey, CAView Profile , Satish Kumar USC/Information Sciences Institute, 4676 Admiralty Way, Marina del Rey, CA USC/Information Sciences Institute, 4676 Admiralty Way, Marina del Rey, CAView Profile Authors Info & Claims MobiCom '99: Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networkingAugust 1999 Pages 263–270https://doi.org/10.1145/313451.313556Published:01 August 1999Publication History 1,787citation7,746DownloadsMetricsTotal Citations1,787Total Downloads7,746Last 12 Months255Last 6 weeks29 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Streaming audio and video applications are becoming increasingly popular on the Internet, and the lack of effective congestion control in such applications is now a cause for significant concern. The problem is one of adapting the compression without requiring video-servers to re-encode the data, and fitting the resulting stream into the rapidly varying available bandwidth. At the same time, rapid fluctuations in quality will be disturbing to the users and should be avoided.In this paper we present a mechanism for using layered video in the context of unicast congestion control. This quality adaptation mechanism adds and drops layers of the video stream to perform long-term coarse-grain adaptation, while using a TCP-friendly congestion control mechanism to react to congestion on very short timescales. The mismatches between the two timescales are absorbed using buffering at the receiver. We present an efficient-scheme for the distribution of buffering among the active layers. Our scheme allows the server to trade short-term improvement for long-term smoothing of quality. We discuss the issues involved in implementing and tuning such a mechanism, and present our simulation results.

End-to-end protocols measure network characteristics and react based on their estimates of network performance. Network dynamics can alter the topology significantly, and thereby affect protocol operation. Topology changes may result in routing pathologies (such as route loops, packet interleaving), changes to the end-to-end path characteristics, network partition etc., that then impact the performance of end-to-end protocols. This paper presents methodologies to evaluate an end-to-end protocol in the presence of network dynamics using a simulator. We evaluate a reliable multicast transport protocol over dynamic topologies and study its adaptivity to topology change. We present a systematic evaluation of the adaptive timer mechanisms in scalable reliable multicast (SRM). The timer mechanisms are evaluated under simple topology changes, as well as under network partition conditions. The paper concludes by posing a number of open research questions about the behaviour of different reliable multicast mechanisms when operating over dynamic topologies.

We propose a method for using simulation to analyze the robustness of multiparty (multicast-based) protocols in a systematic fashion. We call our method Systematic Testing of Robustness by Examination of Selected Scenarios (STRESS). STRESS aims to cut the time and effort needed to explore pathological cases of a protocol during its design. This paper has two goals: (1) to describe the method, and (2) to serve as a case study of robustness analysis of multicast routing protocols. We aim to offer design tools similar to those used in CAD and VLSI design, and demonstrate how effective systematic simulation can be in studying protocol robustness.

Due to the complexity and scale of the current Internet, large scale simulation is an increasingly important tool to evaluate network protocol design. Parallel and distributed simulation is one appropriate approach to the simulation scalability problem, but it can require expensive hardware and have high overhead. We investigate a complementary solution-simulation abstraction. Just as a custom simulator includes only details necessary for the task at hand, a general simulator can support configurable levels of detail for different simulations. We demonstrate two abstraction techniques in multicast simulations and show that they each help to gain one order of magnitude in performance. Although abstraction simulations are not identical to more detailed simulations, in many cases these differences are small and result in minimal changes in the conclusions drawn from simulations.

Multicast routing enables efficient data distribution to multiple recipients. However, existing work has concentrated on extending single-domain techniques to wide-area networks, rather than providing mechanisms to realize inter-domain multicast on a global scale in the Internet. We describe an architecture for inter-domain multicast routing that consists of two complementary protocols. The Multicast Address-Set Claim (MASC) protocol forms the basis for a hierarchical address allocation architecture. It dynamically allocates to domains multicast address ranges from which groups initiated in the domain get their multicast addresses. The Border-Gateway Multicast Protocol (BGMP), run by the border routers of a domain, constructs inter-domain bidirectional shared trees, while allowing any existing multicast routing protocol to be used within individual domains. The resulting shared tree for a group is rooted at the domain whose address range covers the group's address; this domain is typically the group initiator's domain. We demonstrate the feasibility and performance of these complementary protocols through simulation. This architecture, together with existing protocols operating within each domain, is intended as a framework in which to solve the problems facing the current multicast addressing and routing infrastructure.

Scalable reliable multicast (SRM) is a framework for reliable multicast delivery. In order to maximize the collaboration among the group members in error recovery, both retransmission requests and replies are multicast to the entire group. While SRM effectively uses random timers to suppress duplicate requests and replies, the global nature of the request and replies means that every packet loss results in at least one request and reply message sent to the entire group. To further improve the scalability of SRM, one must localize the scope of error recovery traffic. In this paper, we present two approaches to local recovery: hop-based scope control and use of local recovery groups. The first approach uses hop count to limit the distribution of requests and replies whereas the second approach confines error recovery traffic using separately addressed local recovery groups. The local recovery groups and hop count settings are automatically created and dynamically adjusted based on observed loss patterns. The use simulation experiments to examine the performance of both approaches.

Soft state protocols use periodic refresh messages to keep the network state alive while adapting to changing network conditions; this has raised concerns regarding the scalability of protocols that use the soft state approach. In existing soft state protocols, the values of the timers that control the sending of these messages, and the timers for aging out state, are chosen by matching empirical observations with desired recovery and response times. These fixed timer-values fail because they use time as a metric for bandwidth; they adapt neither to (1) the wide range of link speeds that exist in most wide-area internets, nor to (2) fluctuations in the amount of network state over time. We propose and evaluate a new approach in which timer-values adapt dynamically to the volume of control traffic and available bandwidth on the link. The essential mechanisms required to realize this scalable timers approach are: (1) dynamic adjustment of the senders' refresh rate so that the bandwidth allocated for control traffic is not exceeded, and (2) estimation of the senders' refresh rate at the receiver in order to determine when the state can be timed-out and deleted. The refresh messages are sent in a round robin manner not exceeding the bandwidth allocated to the control traffic, and taking into account the message priorities. We evaluate two receiver estimation methods for dynamically adjusting network state timeout values: (1) counting of the rounds and (2) exponential weighted moving average.

Given the need to provide users with reasonable feedback about the "costs" their network usage incurs and the increasingly commercial nature of the Internet, we believe that the allocation of cost among users will play an important role in future networks. This paper discusses cost allocation in the context of multicast flows. The question we discuss is this. When a single data flow is shared among many receivers, how does one split the cost of that flow among the receivers? Multicast routing increases network efficiency by using a single shared delivery tree. We address the issue of how these savings are allocated among the various members of the multicast group. We first consider an axiomatic approach to the problem, analyzing the implications of different distributive notions on the resulting allocations. We then consider a "one-pass" mechanism to implement such allocation schemes and investigate the family of allocation schemes such mechanisms can support.

The integrated services packet network (ISPN) architecture proposed within the Internet community incorporates a resource reservation mechanism for those applications requiring quality of service (QoS) guarantees. Resource reservation introduces a new form of resource contention that can lead to reduced network throughput and thrashing. We establish several necessary conditions to induce thrashing. We also look at the effects several different reservation models and user behavior can have on network stability. Our work is unique from previous network resource reservation investigations in that we consider the effects of reservations for multipoint-to-multipoint applications. We conclude with examples of how simple modifications to user behavior can result in significant increases in system stability.

The purpose of multicast routing is to reduce the communication costs for applications that send the same data to multiple recipients. Existing multicast routing mechanisms were intended for use within regions where a group is widely represented or bandwidth is universally plentiful. When group members, and senders to those group members, are distributed sparsely across a wide area, these schemes are not efficient; data packets or membership report information are occasionally sent over many links that do not lead to receivers or senders, respectively. We have developed a multicast routing architecture that efficiently establishes distribution trees across wide area internets, where many groups will be sparsely represented. Efficiency is measured in terms of the router state, control message processing, and data packet processing, required across the entire network in order to deliver data packets to the members of the group. Our protocol independent multicast (PIM) architecture: (a) maintains the traditional IP multicast service model of receiver-initiated membership, (b) supports both shared and source-specific (shortest-path) distribution trees, (c) is not dependent on a specific unicast routing protocol, and (d) uses soft-state mechanisms to adapt to underlying network conditions and group dynamics. The robustness, flexibility, and scaling properties of this architecture make it well-suited to large heterogeneous internetworks.

PIM (protocol independent multicast) is capable of supporting sparse mode (SM) and dense mode (DM) operations. In sparse mode, PIM can use shared trees (RPT) or shortest path trees (SPT) to deliver data packets. The availability of these various modes opens questions regarding when each should be used, and the consequences of switching among them dynamically. This paper reports on two specific issues: (1) the overhead tradeoffs between dense mode operations and sparse mode operations, (2) the behaviors of PIM when receivers transition from RPT to SPT. Our results illustrate the cross-over point of sparse mode and dense mode overheads, which gives a hint for selecting protocol modes according to the group density metric. We also show that the conditions under which packet losses occur due to SPT switch are rare.

Given the need to provide users with reasonable feedback about the "costs" their network usage incurs, and the increasingly commercial nature of the Internet, we believe that the allocation of cost among users will play an important role in future networks. This paper discusses cost allocation in the context of multicast flows. The question we discuss is this: when a single data flow is shared among many receivers, how does one split the cost of that flow among the receivers? Multicast routing increases network efficiency by using a single shared delivery tree. We address the issue of how these savings are allocated among the various members of the multicast group. We first consider an axiomatic approach to the problem, analyzing the implications of different distributive notions on the resulting allocations. We then consider a one-pass mechanism to implement such allocation schemes and investigate the family of allocation schemes such mechanisms can support.

This paper presents a comparative analysis of two resource reservation protocols, ST-II proposed by Topolcic (1990) and resource reservation protocol (RSVP) proposed by Zhang, Braden, Estrin, Herzog and Jamin (1994) in support of an integrated services packet network (ISPN). The authors use simulations to examine the network-wide resource requirements for each protocol to support a number of application communication styles, across a range of group sizes and membership distributions. They also present a comparison of the protocol features to accommodate network and group membership dynamics.>

Existing multicast routing mechanisms were intended for use within regions where a group is widely represented or bandwidth is universally plentiful. When group members, and senders to those group members, are distributed sparsely across a wide area, these schemes are not efficient; data packets or membership report information are occasionally sent over many links that do not lead to receivers or senders, respectively. We have developed a multicast routing architecture that efficiently establishes distribution trees across wide area internets, where many groups will be sparsely represented. Efficiency is measured in terms of the state, control message processing, and data packet processing, required across the entire network in order to deliver data packets to the members of the group.

Researchers evaluate and contrast new network routing, admission control, congestion control and flow control algorithms through simulation. Analytically de-rived arguments justifiably lack credibility because, in the attempt to model the underlying physical system, the analyst is forced to make compromising approximations. However, unlike analytical techniques like Jackson Queueing Networks, simulations require significant computation and a simulation's state can consume a great deal of memory.This paper describes a technique that we developed to reduce the memory consumption of communication network simulators. Reduced memory makes simulations of larger and higher bandwidth-delay networks possible, but introduces an adjustable degree of approximation in the simulation. The higher the memory savings, the less accurate the computed measures. We call our technique Flowsim. The paper motivates the need to simulate computer networks rather than model them analytically, motivates why a simulator's state can grow quickly, and explains why analytical techniques have failed to model modern communication networks.

The role of pricing policies in multiple service class networks is studied. An abstract formulation of service disciplines and pricing policies that allows the interplay between service disciplines and pricing policies in determining overall network performance to be described more clearly is presented. Effective multiclass service disciplines allow networks to focus resources on performance-sensitive applications, while effective pricing policies allows the benefits of multiple service classes to be spread around to all users. Furthermore, the incentives formed by service disciplines and pricing policies must be carefully tuned so that user self-interest leads to optimal overall network performance. These concepts are illustrated through simulation of several simple example networks. It is found that it is possible to set the prices so that users of every application type are more satisfied with the combined cost and performance of a network with service-class-sensitive prices.>

Internetworks that are global in scale, contain multiple administrative domains, and support a range of services present special requirements for routing. Multiple administrative domains introduce the need for policy-sensitive routing. Service heterogeneity intensifies the requirement for type of service (TOS) routing, as well as other protocol support for handling a range of services, from datagrams to multimedia streams. Key concepts and protocols developed as part of the interdomain policy routing (IDPR) architecture are summarized. Emphasis is placed on the route installation and packet forwarding mechanisms because they are critical to protocol performance and differ significantly from current practice in datagram wide area networks.>

The current internet is based on a stateless (datagram) architecture. However, many recent proposals rely on the maintenance of state information within network routers, leading to the authors' interest in the implications of a stateful network layer. They collected internetwork traffic traces at the border routers of stub and transit networks, and used these data to evaluate, or predict, the effects of design alternatives for stateful architectures. They present an estimate of the number of active conversations at a router, and from this derive the storage requirements for the associated conversation state table. The analysis shows that, at the network periphery, fine-grain control over the traffic may be possible. However, deeper within the network, it may be more efficient to manage the conversations at a coarser level. The network traffic traces are used to perform trace driven simulations of an LRU cache, for different conversation granularities. Results show that locality exists for each of the conversation types investigated.>

In recent years, the number of organizations connected to thie Internet has grown, resulting in an increasingly diverse set of connected users. As a result, network managers have growing concerns about the security and control of network resources. This concern has led protocol engineers to design routing protocols, such as Inter-Domain Policy Routing (IDPR), that include policy restrictions. The introduction of these protocols present a number of new problems to network administrators as they may not be able to easily understand how the policies of different networks interact. A network manager would like to create policies that prevent unauthorized traffic, without impeding legitimate traffic: flows. In the presence of charging mechanisms, a manager may wish to use policy terms to assist in minimizing costs by avoiding the use of commercial networks whenever possible. In this paper we describe a route synthesis simulation tool (IISST) which we have implemented to examine some of these network management issues. We show how it is used to explore some hypothetical situations that a network administrator would face in managing policy routing.

As internets grow, both in size and in the diversity of routing requirements, providing interdomain routing that can accommodate both of these factors becomes increasingly crucial. The combinatorial explosion of mixing and matching different routing criteria weighs heavily on the mechanisms provided by conventional hop-by-hop routing architectures. We expect that over the next 5 to 10 years, the types of services available will continue to evolve and that specialized facilities will be employed to provide new services. While the number and variety of routes provided by hopby -hop routing architectures with type of service support (i.e., multiple, tagged routes) may be sufficient for a large percentage of traffic, it is important that mechanisms be in place to support efficient routing of specialized traffic types via special routes. Our desire to support special routes efficiently led us to investigate the dynamic installation of routes ([Breslau-Estrin 91, Clark 90, IDPR90]). In a pre...

Policy routing protocols incorporate policy related constraints into the route computation and packet forwarding functions for inter-administrative domain (AD) communication. However, this functionally exacerbates the already critical problem of routing information distribution and storage overhead in very large internets (e.g., 100000 ADs). The authors investigate the scalability of the inter-domain policy routing (IDPR) architecture. In particular, they present an informal analysis of connectivity database and update overhead. A model of the IDPR architecture is defined and tested by varying several parameters. The results obtained illustrate the scaling properties of the IDPR architecture and their dependencies upon internet configuration, connectivity among ADs, and number of policies. It is found that, under certain reasonable assumptions, global information for an internet of 5000 transit ADs (and 50000 stub ADs) will occupy on the order of 2.5 MB of storage in the route server.>

We study the role of pricing policies in multiple service class networks. We argue that some form of graduated prices are required in order for any multiclass service discipline to have the desired effect. Moreover, we demonstrate through simulation that it is possible to set the prices so that every user is more satisfied with the combined cost and performance of a network with graduated prices. For some users the performance penalty received for requesting a less-than-optimal service class is offset by the reduced price of the service. For the other users the monetary penalty incurred by using the more expensive, higher quality service classes is offset by the improved performance they receive. Thus, prices allow us to spread the benefits of multiple service classes around to all users, rather than just having these benefits remain exclusively with users who are performance sensitive. 1 Introduction Recent research on computer networks has been concerned almost exclusively with the...

article Free Access Share on Inter-organization networks, computer integration, and shifts in interdependence: the case of the semiconductor industry Authors: Paul Hart Florida Atlantic Univ., Boca Raton Florida Atlantic Univ., Boca RatonView Profile , Deborah Estrin Univ. of Southern California, Los Angeles Univ. of Southern California, Los AngelesView Profile Authors Info & Claims ACM Transactions on Information SystemsVolume 9Issue 4pp 370–398https://doi.org/10.1145/119311.119314Published:01 October 1991Publication History 63citation1,052DownloadsMetricsTotal Citations63Total Downloads1,052Last 12 Months33Last 6 weeks3 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Inter-organization computer networks (IONS) provide significant opportunities for improving coordination between firms engaged in mutually dependent activities. This research paper focuses on how IONS affect information processing requirements, and production and transaction costs when they interconnect firms with internally integrated computer systems and when they are used only as substitutes for conventional media. We conclude that significant improvements in inter- organization coordination result when IONS support exchanges between internally integrated firms. However, while IONS reduce production costs, they can simultaneously increase transaction costs including those associated with penetration into another firm's computing resources, and segmentation in the marketplace.

Policy Routing (PR) is a new area of development that attempts to incorporate policy related constraints on inter-Administrative Domain (AD) communication into the route computation and forwarding of inter-AD packets.

Most routing protocols, including proposed policy routing protocols, focus on environments where detection of an attack after it has taken place is sufficient. The authors explore the design of policy routing mechanisms for sensitive environments where more aggressive preventative measures are mandated. In particular, they detail the design of four secure protocol versions that prevent abuse by cryptographic checks of data integrity. They analyze and compare these schemes in terms of their prepacket processing overhead. It is concluded that preventative security is feasible, although the overhead cost is quite high. Consequently, it is critical that prevention-based schemes coexist with detection-based schemes.>

The increasing use of internetworking protocols to connect administratively heterogeneous networks has raised the question of how an organization can control the flow of information across its network boundaries. One method for doing so is the use of visas, a cryptographic technique for authenticating and authorizing a flow of datagrams. Two visa protocols are presented and evaluated: one that requires distributed state information in gateways and one that uses additional encryptions instead of distributed state. Applications for such visa protocols include access control, accounting and billing for packet transit, and network resource management.>

In this paper we describe a visa scheme for implementing access control in Inter-Organization Network (ION) gateways. The purpose of the scheme is to allow an organization to modify and trust only them internal system that require ION access all other internal system can not communicate with the outside. Control is distributed among the ION participants so that each may make its own design tradeoffs between performance and trust.

This paper analyzes the technical implications of interconnecting networks across organization boundaries. Such Interorganizational Networks (ION's) are used increasingly to support exchange of CAD/CAM data between manufacturers and subcontractors, software distribution from vendors to users, customer input to suppliers' orderentry systems, and the shared use of expensive computational resources by research laboratories, as examples. We begin by demonstrating that interorganization connections are not satisfied by traditional network design criteria of connectivity and transparency. A primary high-level requirement is access control, and therefore, participating organizations must be able to limit connectivity and make network boundaries visible. We summarize an approach to access control in ION's, based on nondiscretionary control, that allows interconnecting organizations to combine gateway, network, and system-level mechanisms to enforce cross-boundary control over invocation and information flow while minimizing interference with internal operations [6], [4]. The focus of this paper is on the underlying interconnection protocols that are needed to support these access control mechanisms. We describe in detail a particular protocol, called a visa scheme [7]. The visa scheme uses access control servers to authorize a session request and visas to authenticate that successive packets belong to the authorized connection. Control is distributed among the ION participants and each may make its own design tradeoffs between performance and trust. In order to support interorganization communication two (or more) organizations must be able to communicate with one another's access control servers and their respective packet-level gateways and nodes (source/destination) must implement the visa scheme. The security of the proposed mechanism varies according to the security of an organization's components (access control server, gateway, and select hosts) and the encryption function used. The visa scheme's purpose is to allow an organization to modify and trust only those internal systems that require ION access; all other internal systems are inaccessible from and to the ION gateway. We conclude by comparing and contrasting the visa approach to the use of higher level gateways.

Interorganization computer networks support person-to-person communication via electronic mail; exchange of cad/cam data, software modules, or documents via file transfer; input to an order-entry or accounting system via a database query and update protocol; and use of shared computational resources via an asynchronous message protocol or remote login. In most such interorganization arrangements, the set of resources that an organization wants to make accessible to outsiders is significantly smaller than the set of resources that it wants to remain strictly-internal (i.e., accessible to employees of the organization only). In addition, because the potential user is a person (or machine) outside the boundaries of the organization, the damage associated with undesired use can be high. Because of these characteristics, Interorganization Networks (ION's) have unique usage-control requirements.

When two or more distinct organizations interconnect their internal computer networks they form an Inter-Organization Network(ION). IONs support the exchange of cad/cam data between manufacturers and subcontractors, software distribution from vendors to users, customer input to suppliers' order-entry systems, and the shared use of expensive computational resources by research laboratories, as examples. This paper analyzes the technical implications of interconnecting networks across organization boundaries.

This paper describes a conceptual model for implementing usage controls in Inter-Organization Networks (IONs). After describing security requirements in networks that cross organization boundries, I suggest how traditional, non-discretionary controls can be adapted to support usage control in IONs.