Wenxuan Xu, Arvind Pillai, Subigya Nepal, Amanda C. Collins, Daniel M Mackin, Michael V. Heinz, Tess Z Griffin, Nicholas C. Jacobson, Andrew Campbell. Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2026.

OBJECTIVE: Semantic coherence in speech is characterized by a logical, connected flow of ideas. A lack of coherence in speech may reflect disorganized thinking, a core feature of psychosis in schizophrenia spectrum disorders (SSDs). Developing tools that could help with automated assessment of semantic coherence in language could facilitate early detection of SSDs and improved monitoring of symptoms, enabling more timely intervention. Large language models (LLMs) have demonstrated strong capabilities on numerous language-centric tasks and have shown promise for analyzing semantic coherence due to the natural fit between their innate measures of language perplexity and the surprising turns that incoherent narrative often takes. This study aims to develop a novel representation and associated measure of semantic coherence using LLM-based perplexity metrics and to compare this measure with traditional vector distance-based coherence metrics. METHOD: We evaluated "bag" and "chain" models based on LLM perplexities as measures of semantic coherence. Regression models were trained using both single and paired combinations of perplexity- and proximity-based features to predict human ratings of semantic coherence using standardized instruments. Performance was evaluated on held-out examples from a training set of speeches from individuals experiencing psychotic symptoms and a test set of clinical interviews with patients diagnosed with SSDs, both with labels from human assessments of disorganized thinking severity. RESULTS: The best performance was achieved using a combination of perplexity and proximity features, yielding a Spearman correlation with human ratings of 0.61 (vs. 0.56 with proximity features alone) on leave-one-out cross-validation in the training set, and 0.54 (vs. 0.52 with proximity features alone) on the test set. CONCLUSION: We developed novel methods for assessing semantic coherence using LLM perplexities and found them complementary to proximity-based methods. Combined, these methods showed improved performance across two datasets, highlighting LLM's potential in enhancing automated diagnosis and monitoring of SSDs.

MoodCapture presents a novel approach that assesses depression based on images automatically captured from the front-facing camera of smartphones as people go about their daily lives. We collect over 125,000 photos in the wild from N=177 participants diagnosed with major depressive disorder for 90 days. Images are captured naturalistically while participants respond to the PHQ-8 depression survey question: “I have felt down, depressed, or hopeless”. Our analysis explores important image attributes, such as angle, dominant colors, location, objects, and lighting. We show that a random forest trained with face landmarks can classify samples as depressed or non-depressed and predict raw PHQ-8 scores effectively. Our post-hoc analysis provides several insights through an ablation study, feature importance analysis, and bias assessment. Importantly, we evaluate user concerns about using MoodCapture to detect depression based on sharing photos, providing critical insights into privacy concerns that inform the future design of in-the-wild image-based mental health assessment tools.

The COVID-19 pandemic continues to affect the daily life of college students, impacting their social life, education, stress levels and overall mental well-being. We study and assess behavioral changes of N=180 undergraduate college students one year prior to the pandemic as a baseline and then during the first year of the pandemic using mobile phone sensing and behavioral inference. We observe that certain groups of students experience the pandemic very differently. Furthermore, we explore the association of self-reported COVID-19 concern with students' behavior and mental health. We find that heightened COVID-19 concern is correlated with increased depression, anxiety and stress. We evaluate the performance of different deep learning models to classify student COVID-19 concerns with an AUROC and F1 score of 0.70 and 0.71, respectively. Our study spans a two-year period and provides a number of important insights into the life of college students during this period.

Impaired social functioning is a symptom of mental illness (e.g., depression, schizophrenia) and a wide range of other conditions (e.g., cognitive decline in the elderly, dementia). Today, assessing social functioning relies on subjective evaluations and self assessments. We propose a different approach and collect detailed social functioning measures and objective mobile sensing data from N=55 outpatients living with schizophrenia to study new methods of passively accessing social functioning. We identify a number of behavioral patterns from sensing data, and discuss important correlations between social function sub-scales and mobile sensing features. We show we can accurately predict the social functioning of outpatients in our study including the following sub-scales: prosocial activities (MAE = 7.79, r = 0.53), which indicates engagement in common social activities; interpersonal behavior (MAE = 3.39, r = 0.57), which represents the number of friends and quality of communications; and employment/occupation (MAE = 2.17, r = 0.62), which relates to engagement in productive employment or a structured program of daily activity. Our work on automatically inferring social functioning opens the way to new forms of assessment and intervention across a number of areas including mental health and aging in place.

Schizophrenia is a severe psychiatric disorder. We use the CrossCheck study dataset to develop methods to predict whether or not a patient with schizophrenia is going to relapse from mobile phone data. Out of 75 patients in the year long randomized controlled trial only 27 relapse episodes occur. We apply various techniques to address predicting rare events in a longitudinal dataset. We apply resampling methods combining oversampling relapse examples and undersampling non-relapse examples and impute missing data. To avoid overfitting, we apply feature selection and transformation (i.e., PCA) to reduce the feature dimensionality. We find the best relapse prediction result using the first 100 principal components from both passive sensing and self-reports with 30-day prediction windows (precision=26.8%, recall=28.4%). If we demand the recall to be greater than 50%, we find the best result using 25 principle components from both passive sensing and self-reports with 30-day prediction windows (precision=15.4%, recall=51.6%).

The ubiquitous use of social media enables researchers to obtain self-recorded longitudinal data of individuals in real-time. Because this data can be collected in an inexpensive and unobtrusive way at scale, social media has been adopted as a “passive sensor” to study human behavior. However, such research is impacted by the lack of homogeneity in the use of social media, and the engineering challenges in obtaining such data. This paper proposes a statistical framework to leverage the potential of social media in sensing studies of human behavior, while navigating the challenges associated with its sparsity. Our framework is situated in a large-scale in-situ study concerning the passive assessment of psychological constructs of 757 information workers wherein of four sensing streams was deployed - bluetooth beacons, wearable, smartphone, and social media. Our framework includes principled feature transformation and machine learning models that predict latent social media features from the other passive sensors. We demonstrate the efficacy of this imputation framework via a high correlation of 0.78 between actual and imputed social media features. With the imputed features we test and validate predictions on psychological constructs like personality traits and affect. We find that adding the social media data streams, in their imputed form, improves the prediction of these measures. We discuss how our framework can be valuable in multimodal sensing studies that aim to gather comprehensive signals about an individual's state or situation.

Early detection of mental health changes in individuals with serious mental illness is critical for effective intervention. CrossCheck is the first step towards the passive monitoring of mental health indicators in patients with schizophrenia and paves the way towards relapse prediction and early intervention. In this paper, we present initial results from an ongoing randomized control trial, where passive smartphone sensor data is collected from 21 outpatients with schizophrenia recently discharged from hospital over a period ranging from 2-8.5 months. Our results indicate that there are statistically significant associations between automatically tracked behavioral features related to sleep, mobility, conversations, smart-phone usage and self-reported indicators of mental health in schizophrenia. Using these features we build inference models capable of accurately predicting aggregated scores of mental health indicators in schizophrenia with a mean error of 7.6% of the score range. Finally, we discuss results on the level of personalization that is needed to account for the known variations within people. We show that by leveraging knowledge from a population with schizophrenia, it is possible to train accurate personalized models that require fewer individual-specific data to quickly adapt to new users.

Pervasive Wi-Fi connectivity is attractive for users in places not covered by cellular services (e.g., when traveling abroad). However, the power drain of frequent Wi-Fi scans undermines the device's battery life, preventing users from staying always connected and fetching synced emails and instant message notifications (e.g., WhatsApp). We study the energy overhead of scan and roaming in detail and refer to it as the scan tax problem. Our findings show that the main processor is the primary culprit of the energy overhead. We propose a simple and effective architectural change of offloading scans to the Wi-Fi radio. We design and build WiScan to fully exploit the gain of scan offloading. Our experiments demonstrate that WiScan achieves 90%+ of the maximal connectivity, while saving 50-62% energy for seeking connectivity.

Many cognitive, behavioral, and environmental factors impact student learning during college. The SmartGPA study uses passive sensing data and self-reports from students' smartphones to understand individual behavioral differences between high and low performers during a single 10-week term. We propose new methods for better understanding study (e.g., study duration) and social (e.g., partying) behavior of a group of undergraduates. We show that there are a number of important behavioral factors automatically inferred from smartphones that significantly correlate with term and cumulative GPA, including time series analysis of activity, conversational interaction, mobility, class attendance, studying, and partying. We propose a simple model based on linear regression with lasso regularization that can accurately predict cumulative GPA. The predicted GPA strongly correlates with the ground truth from students' transcripts (r = 0:81 and p < 0:001) and predicts GPA within ±0:179 of the reported grades. Our results open the way for novel interventions to improve academic performance.

We present LiSense, the first-of-its-kind system that enables both data communication and fine-grained, real-time human skeleton reconstruction using Visible Light Communication (VLC). LiSense uses shadows created by the human body from blocked light and reconstructs 3D human skeleton postures in real time. We overcome two key challenges to realize shadow-based human sensing. First, multiple lights on the ceiling lead to diminished and complex shadow patterns on the floor. We design light beacons enabled by VLC to separate light rays from different light sources and recover the shadow pattern cast by each individual light. Second, we design an efficient inference algorithm to reconstruct user postures using 2D shadow information with a limited resolution collected by photodiodes embedded in the floor. We build a 3 m x 3 m LiSense testbed using off-the-shelf LEDs and photodiodes. Experiments show that LiSense reconstructs the 3D user skeleton at 60 Hz in real time with 10 degrees mean angular error for five body joints.

We present a new visible light communication (VLC) primitive: VLC in the dark, where the communication sustains even when the LED light appears dark. We achieve the goal by reducing the duty cycle of the light source to an extremely low level (0.0019%) such that the illuminance is imperceptible to human eyes and yet can still be sensed by photodiodes to decode data. VLC in the dark consumes much lower energy than the conventional VLC links and thus is appealing for enabling VLC uplink or communication among Internet-of-Things devices with tight energy budget. We build a preliminary prototype to demonstrate its feasibility. Our current single link achieves 190.7 bps data rate with 46.8 microwatts power consumption at the LED.

We present HiLight, a new form of real-time screen-camera communication without showing any coded images (e.g., barcodes) for off-the-shelf smart devices. HiLight encodes data into pixel translucency change atop any screen content, so that camera-equipped devices can fetch the data by turning their cameras to the screen. HiLight leverages the alpha channel, a well-known concept in computer graphics, to encode bits into the pixel translucency change. By removing the need to directly modify pixel RGB values, HiLight overcomes the key bottleneck of existing designs and enables real-time unobtrusive communication while supporting any screen content. We build a HiLight prototype using off-the-shelf smart devices and demonstrate its efficacy and robustness in practical settings. By offering an unobtrusive, flexible, and lightweight communication channel between screens and cameras, HiLight opens up opportunities for new HCI and context-aware applications, e.g., smart glasses communicating with screens to realize augmented reality.

No abstract available.

Much of the stress and strain of student life remains hidden. The StudentLife continuous sensing app assesses the day-to-day and week-by-week impact of workload on stress, sleep, activity, mood, sociability, mental well-being and academic performance of a single class of 48 students across a 10 week term at Dartmouth College using Android phones. Results from the StudentLife study show a number of significant correlations between the automatic objective sensor data from smartphones and mental health and educational outcomes of the student body. We also identify a Dartmouth term lifecycle in the data that shows students start the term with high positive affect and conversation levels, low stress, and healthy sleep and daily activity patterns. As the term progresses and the workload increases, stress appreciably rises while positive affect, sleep, conversation and activity drops off. The StudentLife dataset is publicly available on the web.

We present HiLight, a new form of screen-camera communication without the need of any coded images (e.g. barcodes) for off-the-shelf smart devices. HiLight hides information underlying any images shown on a LED or an OLED screen, so that camera-equipped smart devices can fetch the information by turning their cameras to the screen. HiLight achieves this by leveraging the orthogonal transparency (alpha) channel, a well-known concept in computer graphics, to embed bits into pixel translucency changes without the need of modifying pixel color values. We demonstrated HiLight's feasibility using smartphones. By offering an unobtrusive, flexible, and lightweight communication channel between screens and cameras, HiLight opens up opportunities for new HCI and context-aware applications to emerge, e.g. smart glass communicates with screens for additional personalized information to realize augmented reality.

We present CarSafe, a new driver safety app for Android phones that detects and alerts drivers to dangerous driving conditions and behavior. It uses computer vision and machine learning algorithms on the phone to monitor and detect whether the driver is tired or distracted using the front-facing camera while at the same time tracking road conditions using the rear-facing camera. Today's smartphones do not, however, have the capability to process video streams from both the front and rear cameras simultaneously. In response, CarSafe uses acontext-aware algorithm that switches between the two cameras while processing the data in real-time with the goal of minimizing missed events inside (e.g., drowsy driving) and outside of the car (e.g., tailgating). Camera switching means that CarSafe technically has a "blind spot" in the front or rear at any given time. To address this, CarSafe uses other embedded sensors on the phone (i.e., inertial sensors) to generate soft hints regarding potential blind spot dangers. We present the design and implementation of CarSafe and discuss its evaluation using results from a 12-driver field trial. Results from the CarSafe deployment are promising -- CarSafe can infer a common set of dangerous driving behaviors and road conditions with an overall precision and recall of 83% and 75%, respectively. CarSafe is the first dual-camera sensing app for smartphones and represents a new disruptive technology because it provides similar advanced safety features otherwise only found in expensive top-end cars.

We present CarSafe, the first driver safety application that uses dual cameras on smartphones to detect and alert drivers to dangerous driving conditions. CarSafe fuses events detected from cameras and readings from embedded sensors on the phone -- such as the GPS, accelerometer and gyroscope -- to detect and alert the driver of dangerous driving behavior in and outside of the car. Results from a 12-driver field trial show CarSafe can infer five of the most commonly occurring dangerous driving conditions with an overall precision and recall of 83% and 75%, respectively.

Stress can have long term adverse effects on individuals' physical and mental well-being. Changes in the speech production process is one of many physiological changes that happen during stress. Microphones, embedded in mobile phones and carried ubiquitously by people, provide the opportunity to continuously and non-invasively monitor stress in real-life situations. We propose StressSense for unobtrusively recognizing stress from human voice using smartphones. We investigate methods for adapting a one-size-fits-all stress model to individual speakers and scenarios. We demonstrate that the StressSense classifier can robustly identify stress across multiple individuals in diverse acoustic environments: using model adaptation StressSense achieves 81% and 76% accuracy for indoor and outdoor environments, respectively. We show that StressSense can be implemented on commodity Android phones and run in real-time. To the best of our knowledge, StressSense represents the first system to consider voice based stress detection and model adaptation in diverse real-life conversational situations using smartphones.

We propose MobileQueue, a mobile queue-card management system that offers more freedom to customers by enabling image-based queue-card retrieving and service-information querying actions using mobile phones. MobileQueue interacts with cloud services allowing customers to query summary description and availability (e.g., available seats) of services provided by stores. MobileQueue also offers suggestions to waiting customers such as potentially interesting substitute activities and stores.

We demonstrate CarSafe, a driver safety application for Android phones that fuses information from both front and back cameras and others embedded sensors on the phone to detect and alert drivers to dangerous driving conditions in and outside of the car. In this demonstration, we set up an emulated driving environment to show how CarSafe works.

Driving while being tired or distracted is dangerous. We are developing the CafeSafe app for Android phones, which fuses information from both front and back cameras and others embedded sensors on the phone to detect and alert drivers to dangerous driving conditions in and outside of the car. CarSafe uses computer vision and machine learning algorithms on the phone to monitor and detect whether the driver is tired or distracted using the front camera while at the same time tracking road conditions using the back camera. CarSafe is the first dual-camera application for smart-phones.

Sensor-enabled smartphones are opening a new frontier in the development of mobile sensing applications. The recognition of human activities and context from sensor-data using classification models underpins these emerging applications. However, conventional approaches to training classifiers struggle to cope with the diverse user populations routinely found in large-scale popular mobile applications. Differences between users (e.g., age, sex, behavioral patterns, lifestyle) confuse classifiers, which assume everyone is the same. To address this, we propose Community Similarity Networks (CSN), which incorporates inter-person similarity measurements into the classifier training process. Under CSN every user has a unique classifier that is tuned to their own characteristics. CSN exploits crowd-sourced sensor-data to personalize classifiers with data contributed from other similar users. This process is guided by similarity networks that measure different dimensions of inter-person similarity. Our experiments show CSN outperforms existing approaches to classifier training under the presence of population diversity.

Multi-instance learning, like other machine learning and data mining tasks, requires distance metrics. Although metric learning methods have been studied for many years, metric learners for multi-instance learning remain almost untouched. In this paper, we propose a framework called Multi-Instance MEtric Learning (MIMEL) to learn an appropriate distance under the multi-instance setting. The distance metric between two bags is defined using the Mahalanobis distance function. The problem is formulated by minimizing the KL divergence between two multivariate Gaussians under the constraints of maximizing the between-class bag distance and minimizing the within-class bag distance. To exploit the mechanism of how instances determine bag labels in multi-instance learning, we design a nonparametric density-estimation-based weighting scheme to assign higher "weights" to the instances that are more likely to be positive in positive bags. The weighting scheme itself has a small workload, which adds little extra computing costs to the proposed framework. Moreover, to further boost the classification accuracy, a kernel version of MIMEL is presented. We evaluate MIMEL, using not only several typical multi-instance tasks, but also two activity recognition datasets. The experimental results demonstrate that MIMEL achieves better classification accuracy than many state-of-the-art distance based algorithms or kernel methods for multi-instance learning.

Event-driven sensor networks operate under an idle or light load and then suddenly become active in response to a detected or monitored event. The transport of event impulses is likely to lead to varying degrees of congestion in the network depending on the distribution and rate of packet sources in the network. It is during these periods of event impulses that the likelihood of congestion is greatest and the information in transit of most importance to users. To address this challenge we propose an energy-efficient congestion control scheme for sensor networks called CODA (COngestion Detection and Avoidance) that comprises three mechanisms: (i) receiver-based congestion detection; (ii) open-loop hop-by-hop backpressure; and (iii) closed-loop multisource regulation. We present the detailed design, implementation, and evaluation of CODA using simulation and experimentation. We define three important performance metrics (i.e., energy tax, fidelity penalty, and power) to evaluate the impact of CODA on the performance of sensing applications. We discuss the performance benefits and practical engineering challenges of implementing CODA in an experimental sensor network testbed based on Berkeley motes using CSMA. Simulation results indicate that CODA significantly improves the performance of data dissemination applications such as directed diffusion by mitigating hotspots, and reducing the energy tax and fidelity penalty on sensing applications. We also demonstrate that CODA is capable of responding to a number of congestion scenarios that we believe will be prevalent as the deployment of these networks accelerates.

Modeling human behavior requires vast quantities of accurately labeled training data, but for ubiquitous people-aware applications such data is rarely attainable. Even researchers make mistakes when labeling data, and consistent, reliable labels from low-commitment users are rare. In particular, users may give identical labels to activities with characteristically different signatures (e.g., labeling eating at home or at a restaurant as "dinner") or may give different labels to the same context (e.g., "work" vs. "office"). In this scenario, labels are unreliable but nonetheless contain valuable information for classification. To facilitate learning in such unconstrained labeling scenarios, we propose Community-Guided Learning (CGL), a framework that allows existing classifiers to learn robustly from unreliably-labeled user-submitted data. CGL exploits the underlying structure in the data and the unconstrained labels to intelligently group crowd-sourced data. We demonstrate how to use similarity measures to determine when and how to split and merge contributions from different labeled categories and present experimental results that demonstrate the effectiveness of our framework.

Local search engines are very popular but limited. We present Hapori, a next-generation local search technology for mobile phones that not only takes into account location in the search query but richer context such as the time, weather and the activity of the user. Hapori also builds behavioral models of users and exploits the similarity between users to tailor search results to personal tastes rather than provide static geo-driven points of interest. We discuss the design, implementation and evaluation of the Hapori framework which combines data mining, information preserving embedding and distance metric learning to address the challenge of creating efficient multidimensional models from context-rich local search logs. Our experimental results using 80,000 queries extracted from search logs show that contextual and behavioral similarity information can improve the relevance of local search results by up to ten times when compared to the results currently provided by commercially available search engine technology.

We present Darwin, an enabling technology for mobile phone sensing that combines collaborative sensing and classification techniques to reason about human behavior and context on mobile phones. Darwin advances mobile phone sensing through the deployment of efficient but sophisticated machine learning techniques specifically designed to run directly on sensor-enabled mobile phones (i.e., smartphones). Darwin tackles three key sensing and inference challenges that are barriers to mass-scale adoption of mobile phone sensing applications: (i) the human-burden of training classifiers, (ii) the ability to perform reliably in different environments (e.g., indoor, outdoor) and (iii) the ability to scale to a large number of phones without jeopardizing the "phone experience" (e.g., usability and battery lifetime). Darwin is a collaborative reasoning framework built on three concepts: classifier/model evolution, model pooling, and collaborative inference. To the best of our knowledge Darwin is the first system that applies distributed machine learning techniques and collaborative inference concepts to mobile phones. We implement the Darwin system on the Nokia N97 and Apple iPhone. While Darwin represents a general framework applicable to a wide variety of emerging mobile sensing applications, we implement a speaker recognition application and an augmented reality application to evaluate the benefits of Darwin. We show experimental results from eight individuals carrying Nokia N97s and demonstrate that Darwin improves the reliability and scalability of the proof-of-concept speaker recognition application without additional burden to users.

Supporting continuous sensing applications on mobile phones is challenging because of the resource demands of long-term sensing, inference and communication algorithms. We present the design, implementation and evaluation of the Jigsaw continuous sensing engine, which balances the performance needs of the application and the resource demands of continuous sensing on the phone. Jigsaw comprises a set of sensing pipelines for the accelerometer, microphone and GPS sensors, which are built in a plug and play manner to support: i) resilient accelerometer data processing, which allows inferences to be robust to different phone hardware, orientation and body positions; ii) smart admission control and on-demand processing for the microphone and accelerometer data, which adaptively throttles the depth and sophistication of sensing pipelines when the input data is low quality or uninformative; and iii) adaptive pipeline processing, which judiciously triggers power hungry pipeline stages (e.g., sampling the GPS) taking into account the mobility and behavioral patterns of the user to drive down energy costs. We implement and evaluate Jigsaw on the Nokia N95 and the Apple iPhone, two popular smartphone platforms, to demonstrate its capability to recognize user activities and perform long term GPS tracking in an energy-efficient manner.

Top end mobile phones include a number of specialized (e.g., accelerometer, compass, GPS) and general purpose sensors (e.g., microphone, camera) that enable new people-centric sensing applications. Perhaps the most ubiquitous and unexploited sensor on mobile phones is the microphone - a powerful sensor that is capable of making sophisticated inferences about human activity, location, and social events from sound. In this paper, we exploit this untapped sensor not in the context of human communications but as an enabler of new sensing applications. We propose SoundSense, a scalable framework for modeling sound events on mobile phones. SoundSense is implemented on the Apple iPhone and represents the first general purpose sound sensing system specifically designed to work on resource limited phones. The architecture and algorithms are designed for scalability and Soundsense uses a combination of supervised and unsupervised learning techniques to classify both general sound types (e.g., music, voice) and discover novel sound events specific to individual users. The system runs solely on the mobile phone with no back-end interactions. Through implementation and evaluation of two proof of concept people-centric sensing applications, we demostrate that SoundSense is capable of recognizing meaningful sound events that occur in users' everyday lives.

Technological advances in sensing, computation, storage, and communications will turn the ubiquitous mobile phone into a global mobile sensing device carried by billions of people world-wide. Sensing will be people- centric, enabling a different way to sense, learn, visualize, and share information about ourselves, friends, communities, the way we live, and the world we live in. People-centric sensing juxtaposes the traditional view of small-scale, mote-based sensor networks with one in which people, carrying sensor-enabled mobile phones, enable opportunistic sensing coverage - ultimately, leading to the dawn of a global mobile sensor network. In the MetroSense Project's vision of people-centric sensing, users are the key architectural system component, enabling a host of new application areas such as personal, public, and social sensing.

We present BikeNet, a mobile sensing system for mapping the cyclist experience. Built leveraging the MetroSense architecture to provide insight into the real-world challenges of people-centric sensing, BikeNet uses a number of sensors embedded into a cyclist's bicycle to gather quantitative data about the cyclist's rides. BikeNet uses a dual-mode operation for data collection, using opportunistically encountered wireless access points in a delay-tolerant fashion by default, and leveraging the cellular data channel of the cyclist's mobile phone for real-time communication as required. BikeNet also provides a Web-based portal for each cyclist to access various representations of her data, and to allow for the sharing of cycling-related data (for example, favorite cycling routes) within cycling interest groups, and data of more general interest (for example, pollution data) with the broader community. We present: a description and prototype implementation of the system architecture based on customized Moteiv Tmote Invent motes and sensor-enabled Nokia N80 mobile phones; an evaluation of sensing and inference that quantifies cyclist performance and the cyclist environment; a report on networking performance in an environment characterized by bicycle mobility and human unpredictability; and a description of BikeNet system user interfaces.

MAC addresses can be easily spoofed in 802.11 wireless LANs. An adversary can exploit this vulnerability to launch a large number of attacks. For example, an attacker may masquerade as a legitimate access point to disrupt network services or to advertise false services, tricking nearby wireless stations. On the other hand, the received signal strength (RSS) is a measurement that is hard to forge arbitrarily and it is highly correlated to the transmitter's location. Assuming the attacker and the victim are separated by a reasonable distance, RSS can be used to differentiate them to detect MAC spoofing, as recently proposed by several researchers. By analyzing the RSS pattern of typical 802.11 transmitters in a 3-floor building covered by 20 air monitors, we observed that the RSS readings followed a mixture of multiple Gaussian distributions. We discovered that this phenomenon was mainly due to antenna diversity, a widely-adopted technique to improve the stability and robustness of wireless connectivity. This observation renders existing approaches ineffective because they assume a single RSS source. We propose an approach based on Gaussian mixture models, building RSS profiles for spoofing detection. Experiments on the same testbed show that our method is robust against antenna diversity and significantly outperforms existing approaches. At a 3% false positive rate, we detect 73.4%, 89.6% and 97.8% of attacks using the three proposed algorithms, based on local statistics of a single AM, combining local results from AMs, and global multi-AM detection, respectively.

Knowledge of the network path properties such as latency, hop count, loss and bandwidth is key to the performance of overlay networks, grids and P2P applications. Network operators also use these metrics for managing and diagnosing problems in their networks. However, the size of the Internet makes the task of measuring these metrics immensely difficult. A more scalable approach of inference and estimation of these metrics based on partial measurements has been recently adopted. Current inference approaches do not adapt to different network topologies and the evolution of the network over time. In this paper, we propose a novel learning based approach, called Minerva, for the inferencing of inter-node properties. Minerva uses partial measurements to create signature-like profiles for the participating nodes. These signatures are later used as input to a trained Bayesian network module to estimate the different network properties. We have built a system based on our approach and present performance results from real network measurements obtained from the Planet-Lab testbed. The sensitivity of the system to different parameters including training set, measurement overhead, and size of network have also been studied in this paper.

Sensor networks are characterized by limited energy, processing power, and bandwidth capabilities. These limitations become particularly critical in the case of event-based sensor networks where multiple collocated nodes are likely to notify the sink about the same event, at almost the same time. The propagation of redundant highly correlated data is costly in terms of system performance, and results in energy depletion, network overloading, and congestion. Data aggregation is regarded as an effective technique to reduce energy consumption and prevent congestion. In this paper, we derive a number of significant insights concerning the data aggregation process, which have not been discussed in the literature so far. We first estimate the conditions under which aggregation is a costly process as compared to a no-aggregation approach, by considering a realistic scenario where processing costs related to aggregation of data are not neglected. We also consider that aggregation should preserve the integrity of data, and therefore, the entropy of the correlated data sent by sources can be considered in order to both decrease the amount of redundant data forwarded to the sink and perform an overall lossless process. Our framework can be used to investigate the tradeoff between the increase in data aggregation required to reduce energy consumption, and the need to maximize information integrity.

We present the design, implementation, evaluation, and user ex periences of theCenceMe application, which represents the first system that combines the inference of the presence of individuals using off-the-shelf, sensor-enabled mobile phones with sharing of this information through social networking applications such as Facebook and MySpace. We discuss the system challenges for the development of software on the Nokia N95 mobile phone. We present the design and tradeoffs of split-level classification, whereby personal sensing presence (e.g., walking, in conversation, at the gym) is derived from classifiers which execute in part on the phones and in part on the backend servers to achieve scalable inference. We report performance measurements that characterize the computational requirements of the software and the energy consumption of the CenceMe phone client. We validate the system through a user study where twenty two people, including undergraduates, graduates and faculty, used CenceMe continuously over a three week period in a campus town. From this user study we learn how the system performs in a production environment and what uses people find for a personal sensing system.

No abstract available.

A transmitter in a wireless network that uses CSMA, a simple carrier sensing-based MAC protocol, to determine the likelihood of successful packet reception at the intended receiver can easily be misled. At the same time, CSMA variants and hybrid MAC protocols based at least in part on carrier sensing have become the de facto standard in wireless sensor networks, underscoring a need to improve its performance. We propose to enhance the de facto state of carrier sensing-based MACs in wireless sensor networks by using low cost channel feedback combined with a learning approach to try to better predict the probability of a successful reception, on a per-receiver basis. We show results from an experimental wireless sensor network testbed, where our proposal E-CSMA (Enhanced CSMA) provides up to a 55% improvement in network performance.

We describe our experiences deploying BikeNet, an extensible mobile sensing system for cyclist experience mapping leveraging opportunistic sensor networking principles and techniques. BikeNet represents a multifaceted sensing system and explores personal, bicycle, and environmental sensing using dynamically role-assigned bike area networking based on customized Moteiv Tmote Invent motes and sensor-enabled Nokia N80 mobile phones. We investigate real-time and delay-tolerant uploading of data via a number of sensor access points (SAPs) to a networked repository. Among bicycles that rendezvous en route we explore inter-bicycle networking via data muling. The repository provides a cyclist with data archival, retrieval, and visualization services. BikeNet promotes the social networking of the cycling community through the provision of a web portal that facilitates back end sharing of real-time and archived cycling-related data from the repository. We present: a description and prototype implementation of the system architecture, an evaluation of sensing and inference that quantifies cyclist performance and the cyclist environment; a report on networking performance in an environment characterized by bicycle mobility and human unpredictability; and a description of BikeNet system user interfaces. Visit [4] to see how the BikeNet system visualizes a user's rides.

In this paper, we investigate the impact of variable-range transmission power control on the physical and network connectivity, on network capacity, and on power savings in wireless multihop networks. First, using previous work by Steele (1988), we show that, for a path attenuation factor a = 2, the average range of links in a planar random network of A m2having n nodes is ~aradicA/n1. We show that this average range is approximately half the range obtained when common-range transmission control is used. Combining this result and previous work by Gupta and Kumar (2000), we derive an expression for the average traffic carrying capacity of variable-range-based multihop networks. For a = 2, we show that this capacity remains constant even when more nodes are added to the network. Second, we derive a model that approximates the signaling overhead of a routing protocol as a function of the transmission range and node mobility for both route discovery and route maintenance. We show that there is an optimum setting for the transmission range, not necessarily the minimum, which maximizes the capacity available to nodes in the presence of node mobility. The results presented in this paper highlight the need to design future MAC and routing protocols for wireless ad hoc and sensor networks based, not on common-range which is prevalent today, but on variable-range power control

There is a critical need for new thinking regarding overload traffic management in sensor networks. It has now become clear that experimental sensor networks (e.g., mote networks) and their applications commonly experience periods of persistent congestion and high packet loss, and in some cases even congestion collapse. This significantly impacts application fidelity measured at the physical sinks, even under light to moderate traffic loads, and is a direct product of the funneling effect ; that is, the many-to-one multihop traffic pattern that characterizes sensor network communications. Existing congestion control schemes are effective at mitigating congestion through rate control and packet drop mechanisms, but do so at the cost of significantly reducing application fidelity measured at the sinks. To address this problem we propose to exploit the availability of a small number of all wireless, multiradio virtual sinks that can be randomly distributed or selectively placed across the sensor field. Virtual sinks are capable of siphoning off data events from regions of the sensor field that are beginning to show signs of high traffic load. In this paper, we present the design, implementation, and evaluation of Siphon , a set of fully distributed algorithms that support virtual sink discovery and selection, congestion detection, and traffic redirection in sensor networks. Siphon is based on a Stargate implementation of virtual sinks that uses a separate longer range radio network (based on IEEE 802.11) to siphon events to one or more physical sinks, and a short-range mote radio to interact with the sensor field at siphon points. Results from analysis, simulation and an experimental 48 Mica2 mote testbed show that virtual sinks can scale mote networks by effectively managing growing traffic demands while minimizing any negative impact on application fidelity. Additionally, we show the scheme is competitive with respect to energy consumption compared to a network composed of only motes.

In a wireless network using CSMA for MAC, packet collisions can result either because of the vulnerability stemming from the idle channel detection delay of the radio device or because of the hidden terminal problem. Both of these collision scenarios can be addressed by applying some additional structure to carrier sense-based channel access, sacrificing throughput to improve collision protection. Specifically, we assign a unique time slice to each contending transmitter that is designed to allow collision-free access to each data slot while still using carrier sense as the mechanism to determine channel state. The width of each time slice is equal to the idle channel detection delay of the radio. We prepend a fixed-length time interval to each transmitted packet whose length is proportional to the idle channel detection delay of the radio device and the node density. We discuss this method of channel access including tradeoffs and requirements, and analyze the performance in comparison with existing MAC strategies.

Delivering sufficient fidelity to sensor network applications is challenging because unpredictable wireless links, network dynamics, and the presence of transitional regions in sensor networks impact the delivery of packets (i.e., fidelity) to the sink. One of the major reasons for this problem is due to the non-responsive nature of forwarding mechanisms commonly implemented in experimental sensor networks. Existing routing protocols implemented in these networks typically base their forwarding decision-making on some form of statistical observations regarding past communications or the quality of past beacon signals received by communicating nodes. This approach fails, however, to capture the link conditions at the exact time of forwarding packets across the wireless link, limiting the aggregate forwarding capability of the network. In this paper, we argue that the forwarding decision of a sensor device should be based not on historical information but on the instantaneous link conditions at the exact time of packet communications, and propose, solicitation-based forwarding (SOFA), a highly-responsive hop-by-hop routing protocol that results in increased application fidelity. SOFA represents a cost-effective, on-demand scheme that makes use of simple solicitation-based handshakes between a sender and multiple potential receivers at each wireless hop to negotiate the best forwarding path to a target destination (i.e., sink) when events occur in the sensor field. We present the detailed design, implementation, and experimental evaluation of SOFA in a 36-node Mica2 testbed using TinyOS, and discuss its measured performance benefits in comparison to the TinyOS standard routing protocol widely used by the experimental sensor network community

Sensor networks exhibit a unique funneling effect which is a product of the distinctive many-to-one, hop-by-hop traffic pattern found in sensor networks, and results in a significant increase in transit traffic intensity, collision, congestion, packet loss, and energy drain as events move closer toward the sink. While network (e.g., congestion control) and application techniques (e.g., aggregation) can help counter this problem they cannot fully alleviate it. We take a different but complementary approach to solving this problem than found in the literature and present the design, implementation, and evaluation of a localized, sink-oriented, funneling-MAC capable of mitigating the funneling effect and boosting application fidelity in sensor networks. The funneling-MAC is based on a CSMA/CA being implemented network-wide, with a localized TDMA algorithm overlaid in the funneling region (i.e., within a small number of hops from the sink). In this sense, the funneling-MAC represents a hybrid MAC approach but does not have the scalability problems associated with the network-wide deployment of TDMA. The funneling-MAC is 'sink-oriented' because the burden of managing the TDMA scheduling of sensor events in the funneling region falls on the sink node, and not on resource limited sensor nodes; and it is 'localized' because TDMA only operates locally in the funneling region close to the sink and not across the complete sensor field. We show through experimental results from a 45 mica-2 testbed that the funneling-MAC mitigates the funneling effect, improves throughput, loss, and energy efficiency, and importantly, significantly outperforms other representative protocols such as B-MAC, and more recent hybrid TDMA/CSMA MAC protocols such as Z-MAC.

No abstract available.

No abstract available.

No abstract available.

There is a critical need for new thinking regarding overload traffic management in sensor networks. It has now become clear that experimental sensor networks (e.g., mote networks) and their applications commonly experience periods of persistent congestion and high packet loss, and in some cases even congestion collapse. This significantly impacts application fidelity measured at the physical sinks, even under light to moderate traffic loads, and is a direct product of the funneling effect; that is, the many-to-one multi-hop traffic pattern that characterizes sensor network communications. Existing congestion control schemes are effective at mitigating congestion through rate control and packet drop mechanisms, but do so at the cost of significantly reducing application fidelity measured at the sinks. To address this problem we propose to exploit the availability of a small number of all wireless, multi-radio virtual sinks that can be randomly distributed or selectively placed across the sensor field. Virtual sinks are capable of siphoning off data events from regions of the sensor field that are beginning to show signs of high traffic load. In this paper, we present the design, implementation, and evaluation of Siphon, a set of fully distributed algorithms that support virtual sink discovery and selection, congestion detection, and traffic redirection in sensor networks. Siphon is based on a Stargate implementation of virtual sinks that uses a separate longer-range radio network (based on IEEE 802.11) to siphon events to one or more physical sinks, and a short-range mote radio to interact with the sensor field at siphon points. Results from analysis, simulation and an experimental 48 Mica2 mote testbed show that virtual sinks can scale mote networks by effectively managing growing traffic demands while minimizing the impact on application fidelity.

There is a growing need to support reliable data communications in sensor networks that are capable of supporting new applications, such as, assured delivery of high-priority events to sinks, reliable control and management of sensor networks, and remotely programming/retasking sensor nodes over-the-air. We present the design, implementation, and evaluation of pump slowly, fetch quickly (PSFQ), a simple, scalable, and robust transport protocol that is customizable to meet the needs of emerging reliable data applications in sensor networks. PSFQ represents a simple approach because it makes minimum assumptions about the underlying routing infrastructure, it is scalable and energy- efficient because it supports minimum signaling, thereby reducing the communication cost for data reliability, and importantly, it is robust because it is responsive to a wide range of operational error conditions found in sensor network, allowing for the successful operation of the protocol even under highly error-prone conditions. The key idea that underpins the design of PSFQ is to distribute data from a source node by pacing data at a relatively slow speed ("pump slowly"), but allowing nodes that experience data loss to fetch (i.e., recover) any missing segments from their local immediate neighbors aggressively ("fetch quickly"). We present the design and implementation of PSFQ, and evaluate the protocol using the ns-2 simulator and an experimental wireless sensor testbed based on Berkeley motes and the TinyOS operating system. We show that PSFQ can outperform existing related techniques and is highly responsive to the various error conditions experienced in sensor networks. The source code for PSFQ is freely available for experimentation.

There is growing interest in network processor technologies capable of processing packets at line rates. Network processors are likely to be an integral part of next generation high-speed router and switch architectures, replacing the application-specific integrated circuits (ASICs) that are used in routers today. In this paper, we present the design, implementation and evaluation of NetBind, a high-performance, flexible and scalable binding tool for dynamically constructing data paths in network processor-based routers. The methodology that underpins NetBind balances the flexibility of network programmability against the need to process and forward packets at line speeds. To support the dynamic binding of components with the minimum addition of instructions in the critical path, NetBind modifies the machine language code of components at run time. To support fast data path composition, NetBind reduces the number of binding operations required for constructing data paths to a minimum set so that binding latencies are comparable with packet forwarding times. Data paths constructed using NetBind seamlessly share the resources of the same network processor. Resources are assigned during the binding process. We compare the performance of NetBind to the MicroACE system developed by Intel and show that NetBind provides better performance in comparison to MicroACE with smaller binding overhead. The NetBind source code described and evaluated in this paper is freely available on the Web (http://www.comet.columbia.edu/genesis/netbind) for experimentation. Copyright © 2005 John Wiley & Sons, Ltd.

We study the impact of individual variable-range transmission power control on the physical and network connectivity, network capacity and power savings of wireless multihop networks such as ad hoc and sensor networks. First, using previous work by Steele (1988) and Gupta (2000) we derive an asymptotic expression for the average traffic carrying capacity of nodes in a multihop network where nodes can individually control the transmission range they use. For the case of a path attenuation factor /spl alpha/ = 2 we show that this capacity remains constant even when more nodes are added to the network. Second, we show that the ratio between the minimum transmission range levels obtained using common-range and variable-range based routing protocols is approximately 2. This is an important result because it suggests that traditional routing protocols based on common-range transmission can only achieve about half the traffic carrying capacity of variable-range power control approaches. In addition, common-range approaches consume /spl sim/ (1 $2/(2/sup /spl alpha//)) % more transmission power. Second, we derive a model that approximates the signaling overhead of a routing protocol as a function of the transmission range and node mobility for both route discovery and route maintenance. We show how routing protocols based on common-range transmission power limit the capacity available to mobile nodes. The results presented in the paper highlight the need to design future wireless network protocols (e.g., routing protocols) for wireless ad hoc and sensor networks based, not on common-range which is prevalent today, but on variable-range power control.

Peer-to-peer networks are mainly unstructured, where no specific topology is imposed on the network during its operations. These networks offer a high degree of resilience against network dynamics disrupting the network's operation. Unstructured networks, based on random connections are limited, however, in the performance and node reachability they can offer to applications. In contrast, structured networks impose predetermined connectivity relationships between nodes in order to offer a guarantee on the diameter between requesting nodes and the requested objects. We observe that neither structured nor unstructured networks can simultaneously offer both good performance and resilience in a single algorithm. To address this challenge, we propose Phenix, a peer-to-peer algorithm that can construct low-diameter resilient topologies. Phenix supports low diameter operations by creating a topology of nodes whose degree distribution follows a power-law, while the implementation of the underlying algorithm is fully distributed requiring no central server, thus, eliminating the possibility of a single point of failure in the system. We present the design and evaluation of the algorithm and show through analysis, simulation, and experimental results obtained from an implementation on the PlanetLab testbed that Phenix is robust to network dynamics such as joins/leaves, node failure and large-scale network attacks, while maintaining low overhead when implemented in an experimental network.

No abstract available.

No abstract available.

Efficient network provisioning mechanisms that support service differentiation are essential to the realization of the Differentiated Services (DiffServ) Internet. Building on our prior work on edge provisioning, we propose a set of efficient dynamic node and core provisioning algorithms for interior nodes and core networks, respectively. The node provisioning algorithm prevents transient violations of service level agreements (SLA) by predicting the onset of service level violations based on a multiclass virtual queue measurement technique, and by automatically adjusting the service weights of weighted fair queueing schedulers at core routers. Persistent service level violations are reported to the core provisioning algorithm, which dimensions traffic aggregates at the network ingress edge. The core provisioning algorithm is designed to address the difficult problem of provisioning DiffServ traffic aggregates (i.e., rate-control can only be exerted at the root of any traffic distribution tree) by taking into account fairness issues not only across different traffic aggregates but also within the same aggregate whose packets take different routes through a core IP network. We demonstrate through analysis and simulation that the proposed dynamic provisioning model is superior to static provisioning for DiffServ in providing quantitative delay bounds with differentiated loss across per-aggregate service classes under persistent congestion and device failure conditions when observed in core networks.

Event-driven sensor networks operate under an idle or light load and then suddenly become active in response to a detected or monitored event. The transport of event impulses is likely to lead to varying degrees of congestion in the network depending on the sensing application. It is during these periods of event impulses that the likelihood of congestion is greatest and the information in transit of most importance to users. To address this challenge we propose an energy efficient congestion control scheme for sensor networks called CODA (COngestion Detection and Avoidance) that comprises three mechanisms: (i) receiver-based congestion detection; (ii) open-loop hop-by-hop backpressure; and (iii) closed-loop multi-source regulation. We present the detailed design, implementation, and evaluation of CODA using simulation and experimentation. We define two important performance metrics (i.e., energy tax and fidelity penalty) to evaluate the impact of CODA on the performance of sensing applications. We discuss the performance benefits and practical engineering challenges of implementing CODA in an experimental sensor network testbed based on Berkeley motes using CSMA. Simulation results indicate that CODA significantly improves the performance of data dissemination applications such as directed diffusion by mitigating hotspots, and reducing the energy tax with low fidelity penalty on sensing applications. We also demonstrate that CODA is capable of responding to a number of congestion scenarios that we believe will be prevalent as the deployment of these networks accelerates.

The successful operation of emerging public wireless local-area networks requires flexible network mechanisms that can support differentiated or tiered services for a variety of applications such as bursty transactional Web applications, as well as reservation demanding voice and video applications. Congestion pricing has been proposed as one promising solution to traffic control because it accurately models the cost that each user's traffic imposes on network congestion points. The underlying assumption of congestion pricing is that users will respond to a monetary-based price signal to maximize their own utility. We observe, however, that monetary service charge is largely a business concern and not a traffic control concern because operators and users prefer simple, predictable, and stable service charges such as flat-rate or block-rate charging. Therefore, we argue, that traffic control techniques such as congestion pricing should be decoupled from monetary service charges. Under such a new regime, however, a user's response to a nonmonetary price signal would be quite different from utility maximization, and without the appropriate incentives for users to cooperate such a regime would lead to the "tragedy of the commons" phenomenon, undermining any future differentiated service offerings by wireless Internet service providers. To address this problem, we propose wireless incentive engineering mechanisms for mobile devices (MDs) and access points (APs) that provide incentives for mobile users to cooperatively use different classes of services without relying on monetary service charging. Wireless incentive engineering possesses a number of beneficial properties including minimizing the algorithmic and protocol overhead on MDs and APs, Nash bargaining fairness, and incentive compatibility for mobile users promoting the truthful selection of service class and bandwidth declaration. We use analysis, simulation, and experimental results from a wireless testbed to demonstrate the effectiveness of wireless incentive engineering.

Traffic regulation in public and private wireless LANs face a number of significant challenges, particularly in commercial networks where there is a need for efficient regulation of bursty transactional applications, support for bandwidth reservation services while inhibiting bandwidth hogging by mobile devices, and providing incentives for user cooperation. We take a new approach to solving these problems by applying incentive engineering techniques to wireless access networks. We design two incentive-based allocation service classes: an instantaneous allocation (IA) class, which provides better throughput, and a stable allocation (SA) class, which provides better allocation stability. Our approach possesses a number of beneficial properties including minimizing the algorithmic and protocol overhead on mobile devices, Nash bargaining fairness for the IA service, and incentive compatibility for mobile users promoting the truthful selection of service class and bandwidth declaration. We use analysis, simulation and experimental results from a wireless testbed to demonstrate the effectiveness of wireless incentive engineering.

We propose SWAN, a stateless network model which uses distributed control algorithms to deliver service differentiation in mobile wireless ad hoc networks in a simple, scalable and robust manner. We use rate control for UDP and TCP best-effort traffic, and sender-based admission control for UDP real-time traffic. SWAN uses explicit congestion notification (ECN) to dynamically regulate admitted real-time traffic in the face of network dynamics brought on by mobility or traffic overload conditions. We use the term "soft" real-time services to indicate that real-time sessions could be regulated or dropped due to mobility or excessive traffic overloading at mobile wireless routers. SWAN is designed to limit such conditions, however. A novel aspect of SWAN is that it does not require the support of a QOS-capable MAC. Rather, soft real-time services are built using existing best effort wireless MAC technology. Simulation, analysis, and results from an experimental wireless testbed show that real-time applications experience low and stable delays under various multi-hop, traffic and mobility conditions. The wireless testbed and ns-2 simulator source code are available from the Web (comet.columbia.edu/swan).

We propose SWAN, a stateless network model which uses distributed control algorithms to deliver service differentiation in mobile wireless ad hoc networks in a simple, scalable and robust manner. The proposed architecture is designed to handle both real-time UDP traffic, and best effort UDP and TCP traffic without the need for the introduction and management of per-flow state information in the network. SWAN supports per-hop and end-to-end control algorithms that primarily rely on the efficient operation of TC/IP protocols. In particular, SWAN uses local rate control for best-effort traffic, and sender-based admission control for real-time UDP traffic. Explicit congestion notification (ECN) is used to dynamically regulate admitted real-time sessions in the face of network dynamics brought on by mobility or traffic overload conditions. SWAN does not require the support of a QoS-capable MAC to deliver service differentiation. Rather, real-time services are built using existing best effort wireless MAC technology. Simulation, analysis, and results from an experimental wireless testbed show that real-time applications experience low and stable delays under various multihop, traffic, and mobility conditions.

This paper introduces PARO, a power-aware routing optimization that helps to minimize the transmission power needed to forward packets between wireless devices in ad hoc networks. Using PARO, one or more intermediate nodes called "redirectors" elects to forward packets on behalf of source-destination pairs thus reducing the aggregate transmission power consumed by wireless devices. PARO is applicable to a number of networking environments including sensor networks, home networks and mobile ad hoc networks. In this paper, we present the detailed design of PARO and evaluate the protocol using simulation and experimentation. We show through simulation that PARO is capable of outperforming traditional broadcast-based routing protocols (e.g., MANET routing protocols) due to its power conserving point-to-point on-demand design. We discuss some initial experiences from an early implementation of the protocol in an experimental wireless testbed using off-the-shelf radio technology.

This paper investigates differentiated services in wireless packet networks using a fully distributed approach that supports service differentiation, radio monitoring and admission control. Service differentiation is based on the IEEE 802.11 distributed coordination function (DCF) originally designed to support best-effort data services. We extend the distributed coordination function to provide service differentiation for delay sensitive and best-effort traffic. Two distributed estimation algorithms are proposed and analyzed. A virtual MAC (VMAC) algorithm passively monitors the radio channel and estimates locally achievable service levels. The virtual MAC estimates key MAC level statistics related to service quality such as delay, delay variation, packet collision and packet loss. We show the efficiency of the virtual MAC algorithm and consider significantly overlapping cells and highly bursty traffic mixes. A virtual source (VS) algorithm utilizes the virtual MAC to estimate application level service quality. The virtual source allows application parameters to be tuned in response to dynamic channel conditions based on "virtual delay curves". We demonstrate through simulation that when these distributed virtual algorithms are applied to the admission control of the radio channel then a globally stable state can be maintained without the need for complex centralized radio resource management. Finally, we discuss a distributed service level management scheme that builds on the proposed algorithms to offer continuous service with handoff.

Currently, the design, deployment, and refinement of new network architectures is a manual, ad hoc, and time-consuming process. We present the design, implementation, and evaluation of the Genesis Kernel, a programming system that automates the life cycle process for the creation, deployment, management, and architecting of network architectures. We discuss our experiences in building a spawning network that is capable of creating distinct virtual network architectures on-demand. The Genesis Kernel is based on a methodology that allows a child virtual network to operate on top of a subset of its parent's network resources and in isolation from other spawned virtual networks. We show through experimentation how a number of diverse network architectures can be spawned and architecturally refined. These spawned network architectures include a parent network that supports IP forwarding, and interior and exterior routing. We discuss how two child networks based on Cellular IP and Mobiware architectures can be spawned on the parent network to support wireless access to data and continuous media services, respectively.

This paper investigates differentiated services in wireless packet networks using a fully distributed approach that supports service differentiation, radio monitoring, and admission control. While our proposal is generally applicable to distributed wireless access schemes, we design, implement, and evaluate our framework within the context of existing wireless technology. Service differentiation is based on the IEEE 802.11 distributed coordination function (DCF) originally designed to support best-effort data services. We analyze the delay experienced by a mobile host implementing the IEEE 802.11 DCF and derive a closed-form formula. We then extend the DCF to provide service differentiation for delay-sensitive and best-effort traffic based on the results from the analysis. Two distributed estimation algorithms are proposed. These algorithms are evaluated using simulation, analysis, and experimentation. A virtual MAC (VMAC) algorithm passively monitors the radio channel and estimates locally achievable service levels. The VMAC estimates key MAC level statistics related to service quality such as delay, delay variation, packet collision, and packet loss. We show the efficiency of the VMAC algorithm through simulation and consider significantly overlapping cells and highly bursty traffic mixes. In addition, we implement and evaluate the VMAC in an experimental differentiated services wireless testbed. A virtual source (VS) algorithm utilizes the VMAC to estimate application-level service quality. The VS allows application parameters to be tuned in response to dynamic channel conditions based on "virtual delay curves." We demonstrate through simulation that when these distributed victual algorithms are applied to the admission control of the radio channel then a globally stable state can be maintained without the need for complex centralized radio resource management.

A key consideration in building differentiated network services is the feasibility of maintaining stable and consistent service level agreements across multiple networks where allocations are made only on the edges. To investigate this, we consider a game theoretic model of capacity provisioning in a differentiated services Internet. The players are one raw-capacity seller per network, one broker per service per network, and users, to play the roles of wholesellers, retailers and end users respectively in a two-tier wholeseller/retailer market. Based on this model, we are able to construct an explicit necessary and sufficient condition for the stability of the game, which determines the sustainability of a given set of SLA configurations among peering ISP. The analytical results are validated with simulations of user and broker dynamics, using distributed progressive second price auctions as the spot market mechanism in a scenario with three interconnected networks, and two services.

We present the design, implementation, and evaluation of INSIGNIA, an IP-based quality of service framework that supports adaptive services in mobile ad hoc networks. The framework is based on an in-band signaling and soft-state resource management approach that is well suited to supporting mobility and end-to-end quality of service in highly dynamic environments where the network topology, node connectivity, and end-to-end quality of service are time varying. Architecturally INSIGNIA is designed to support fast reservation, restoration, and end-to-end adaptation based on the inherent flexibility and robustness and scalability found in IP networks. We evaluate the framework, paying particular attention to the performance of the in-band signaling system, which helps counter time-varying network dynamics in support of the delivery of adaptive services. Our results show the benefit of our framework under diverse mobility, traffic, and channel conditions.

We describe the design and evaluation of a programmable medium access control framework which is based on a hybrid centralized/distributed data link controller. The programmable framework and its associated algorithms are capable of supporting adaptive real-time applications over time-varying and bandwidth limited networks (e.g., wireless networks) in a fair and efficient manner taking into account application-specific adaptation needs. The framework is flexible, extensible and supports the dynamic introduction of new adaptive services on-demand. As part of the service creation process, applications interact with a set of distributed adaptation handlers to program services without the need to upgrade the centralized adaptation controller. This approach is in contrast to existing techniques that offer a fixed set of "hard-wired" services at the data link from which applications select. We present a framework where a centralized adaptation controller responsible for the fair allocation of available bandwidth among adaptive applications is driven by application specific bandwidth utility curves. A set of distributed adaptation handlers execute at edge devices interacting with a central controller allowing applications to program their adaptation needs in terms of utility curves, adaptation time scales and adaptation policy. The central controller offers a set of simple meta-services called "profiles" that distributed handlers use to build sophisticated adaptive real-time services.

This paper presents a decentralized auction-based approach to pricing of edge-allocated bandwidth in a differentiated services Internet. The players in our network economy model are one raw-capacity seller per network, one broker per service per network, and users, to play the roles of whole-sellers, retailers, and end-buyers, respectively, in a two-tier wholeseller/retailer market, which is best interpreted as a "sender-pay" model. With the progressive second price auction mechanism as the basic building block, we conduct a game theoretic analysis, deriving optimal strategies for buyers and brokers, and show the existence of networkwide market equilibria. In addition to pricing, another key consideration in building differentiated network services is the feasibility of maintaining stable and consistent service level agreements across multiple networks where demand-driven dynamic allocations are made only at the edges. Based on the proposed game-theoretic model, we are able to construct an explicit necessary and sufficient condition for the stability of the game, which determines the sustainability of any set of service level agreement configurations between Internet service providers. These analytical results are validated with simulations of user and broker dynamics, using the distributed progressive second price auction as the spot market mechanism in a scenario with three interconnected networks, and two services based on the proposed standard expedited forwarding and assured forwarding per-hop behavior.

For wireless channels, interference mitigation techniques are typically applied at the packet transmission level. In this paper, we present the Havana Framework for supporting integrated adaptive-QOS that also responds to impairments over multiple time scales that are present at the flow/session level. Our framework is based on three different mechanisms that operate over distinct adaptation time scales. At the packet transmission time scale, a channel predictor determines whether to transmit a packet or not depending on the state of the wireless channel. At the packet scheduling time scale, a compensator credits and compensates flows that experience bad link quality. Over even longer time scales an adaptor regulates flows taking into account the ability of wireless applications to adapt to changes in available bandwidth and channel conditions.

A number of initiatives to add mobility to the Internet and packet data services to third generation cellular systems are being considered by emerging mobile service providers as possible candidate solutions for the delivery of IP data to mobile users. Both of these two candidates have a number of shortcomings, however. Mobile IP represents a simple and scalable global mobility solution but is not appropriate in support of fast and seamless handoff control. In contrast, third generation cellular systems offer smooth mobility support but are built on complex networking infrastructure that lacks the flexibility offered by IP-based solutions. In this paper we present an overview of cellular IP which represents a 'third way' combining the strengths of bath approaches without inheriting their weaknesses. Cellular IP combines the capability of cellular networks to provide smooth fast handoff and efficient location management of active and idle mobile users with the inherent flexibility, robustness and scalability found in IP networks.

Existing mobile systems (e.g., mobile IP, mobile ATM and third generation cellular systems) lack the intrinsic architectural flexibility to deal with the complexity of supporting adaptive mobile applications in wireless and mobile environments. We believe that there is a need to develop alternative network architectures from the existing ones to deal with the demands placed on underlying mobile signalling, adaptation management and wireless transport systems in support of new mobile services, e.g. interactive multimedia and web access. In this paper we present the design, implementation and evaluation of mobiware, a middleware technology that enables the introduction of new services in mobile networks. Mobiware provides a toolkit that service providers can utilize to build services that can dynamically exploit the intrinsic scalable properties of mobile multimedia applications in response to time-varying mobile network conditions. Based on an open programmable networking paradigm, mobiware runs on mobile devices, wireless access points and mobile-capable switch/routers providing a set of open programmable interfaces and distributed objects for adaptive mobile networking. Mobiware is software-intensive and is built on CORBA and Java distributed object technologies. The source code for mobiware v1.0 is freely available (comet.columbia.edu/mobiware) for experimentation.

In th ~ paper we introduce uniuergal mobile channel, a new mobde communications abstraction that enables users and service providers to program apphcation-specific adaptive mobde services into a ce~ular Internet. Universal mobde channels are capable of supporting distinct adaptive qurdity of service control and mobfity management services over the same ce~ular access network infrastructure. Buflt on a split-leuel adaptation control scheme that operates at the ap pfication and network Ieveh, universal mobde channek offer a set of we ~ defined open programmable interfaces to actively exploit the intrinsic scdabfity of adaptive mobfle ap phcations in ce~dar 1P networks. Universal mobde channeb can be programmed and expose interfaces that include: G) utility curves, which capture the adaptive nature of mobde applications in terms of the range of bandwidth over which they can successftiy operate; (ii) adaptation policy, which enables adaptive mobde apphcations to program per-session adaptation time-scales and bandwidth gramdarities rerdizing novel apphcation-specific adaptive servic ~ and (iii) session policy, which enables users to specify the relative importance of flows/sessions within the same universfl mobde channel. To maintain adaptive services, universal mobde channek periodically probe the ce~tiar access network using a distributed network dgonthm achieving utility-based max-min jairness. 1

Recent advances in distributed systems and transportable software and increasing demand for better quality-of-service (QOS) control in multiservice networks are driving a re-examination of network software architectures. We established the COMET Group (Control Management and Telemedia) at Columbia University's Center for Telecommunications Research to provide a comprehensive understanding of network software architecture of the 1990s and beyond. In this paper, we present an overview of our activities, focusing on new research initiatives, international forum participation and on-going research projects. Collectively, these activities shape our vision of a new era driven by open programmable networking.

This paper presents a distributed power control scheme for next-generation multiservices CDMA systems. CDMA has inherent capability to control the quality-of-service (QoS) requirements by assigning different power levels to each traffic type. Toward this, optimum power control schemes have been investigated. The main drawback of the previously proposed algorithms is that they would require all users' transmission state necessitating a complicated control process or peak-rate bandwidth allocation. To overcome this, we exploit the Markovian property to obtain the statistics of the traffic. The statistical formulation is presented for allocating power distributedly so as to keep the "collision" probability below a predefined probability. Numerical examples show that the distributed power control scheme allows better utilization of wireless resources through statistical multiplexing than peak-rate bandwidth assignment, and it does not require a complicated control process while keeping total transmitted power at slightly greater than optimum power control.

Distributed audio and video applications need to adapt to fluctuations in delivered quality of service (QoS).By trading off temporal and spatial quality to available bandwidth, or manipulating the playout time of continuous media in response to variation in delay, audio and video flows can be made to adapt to fluctuating QoS with minimal perceptual distortion.In this paper we describe the implementation of a QoS adaptive transport system that incorporates a QoS oriented API and a range of mechanisms to assist applications in exploiting QoS and adapting to fluctuations in QoS.The system, which is an instantiation of the QoS Architecture (QoS-A), is implemented in a multi ATM switch network environment with Linux based PC end systems and continuous media file servers.A performance evaluation of the system configured to support Video-on-Demand application scenario is presented and discussed.'ACM Multimcdia 96, Boston MA USA

We describe the design of an application platform able to run distributed real-time and multimedia applications alongside conventional UNIX programs. The platform is embedded in a microkernel/PC environment and supported by an ATM-based, QoS-driven communications stack. In particular, we focus on resource-management aspects of the design and deal with CPU scheduling, network resource-management and memory-management issues. An architecture is presented that guarantees QoS levels of both communications and processing with varying degrees of commitment as specified by user-level QoS parameters. The architecture uses admission tests to determine whether or not new activities can be accepted and includes modules to translate user-level QoS parameters into representations usable by the scheduling, network, and memory-management subsystems.>

The integration of distributed multimedia systems around the unifying theme of quality of service (QOS) is addressed. A set of key QOS requirements is presented and mapped onto a provisional QOS architecture (QOS-A) that has emerged from a experimental system designed and implemented at Lancaster. The scope of the discussion is limited to aspects of a QOS-A for the support of continuous media communications. Also, the focus is on asynchronous transfer mode (ATM) at the network layer rather than the full range of multiservice networks. Functions and mechanisms for QOS support are examined and placed within the evolving QOS-A.>

The combination of high-speed multiservice networks and multimedia workstations offers considerable potential for the development of distributed multimedia applications. A key problem is how to integrate continuous-media types such as audio and video into a distributed workstation environment. An experimental system architecture based on a specialized multimedia network interface that attempts to provide this integration is described. The design and implementation of this system are discussed in depth in terms of workstation enhancement and distributed system support. A new approach to the problem of media synchronization is introduced, and the importance of quality of service in the architecture is highlighted. Experiences encountered during this work are described, comparison with other approaches is made, and likely future developments in multimedia network interfacing are discussed.>

The desire to transfer continuous media such as digital audio and video across packet switched networks imposes a number of new requirements on transport level communication services. This paper identifies a number of these requirements in the context of an experimental distributed multimedia infrastructure, and reports on research which addresses some of the associated issues. Particular attention is paid to two areas: (i) extended Quality of Service (QoS) provision; and (ii) support for the co-ordination of multiple related connections. We then describe an application level service, known as an orchestrator, which performs synchronisation functions over multiple related transport connections. We also outline the design and implementation of a continuous media transport service which meets the identified requirements. Finally, we outline the way in which the orchestrator and transport services are integrated into an object-based distributed multimedia application platform.