Black box optimization (BBO) focuses on optimizing unknown functions in high-dimensional spaces. In many applications, sampling the unknown function is expensive, imposing a tight sample budget.Ongoing work is making progress on reducing the sample budget by learning the shape/structure of the function, known as kernel learning. We propose a new method to learn the kernel of a Gaussian Process. Our idea is to create a continuous kernel space in the latent space of a variational autoencoder, and run an auxiliary optimization to identify the best kernel. Results show that the proposed method, Kernel Optimized Blackbox Optimization (KOBO), outperforms state of the art by estimating the optimal at considerably lower sample budgets. Results hold not only across synthetic benchmark functions but also in real applications. We show that a hearing aid may be personalized with fewer audio queries to the user, or a generative model could converge to desirable images from limited user ratings.

This paper considers the problem of estimating chirp parameters from a noisy mixture of chirps. While a rich body of work exists in this area, challenges remain when extending these techniques to chirps of higher order polynomials. We formulate this as a non-convex optimization problem and propose a modified Langevin Monte Carlo (LMC) sampler that exploits the average curvature of the objective function to reliably find the minimizer. Results show that our Curvature-guided LMC (CG-LMC) algorithm is robust and succeeds even in low SNR regimes, making it viable for practical applications.

Blind Speech Separation (BSS) aims to separate multiple speech sources from audio mixtures recorded by a microphone array. The problem is challenging because it is a blind inverse problem, i.e., the microphone array geometry, the room impulse response (RIR), and the speech sources, are all unknown. We propose ArrayDPS to solve the BSS problem in an unsupervised, array-agnostic, and generative manner. The core idea builds on diffusion posterior sampling (DPS), but unlike DPS where the likelihood is tractable, ArrayDPS must approximate the likelihood by formulating a separate optimization problem. The solution to the optimization approximates room acoustics and the relative transfer functions between microphones. These approximations, along with the diffusion priors, iterate through the ArrayDPS sampling process and ultimately yield separated voice sources. We only need a simple single-speaker speech diffusion model as a prior, along with the mixtures recorded at the microphones; no microphone array information is necessary. Evaluation results show that ArrayDPS outperforms all baseline unsupervised methods while being comparable to supervised methods in terms of SDR. Audio demos and codes are provided at: https://arraydps.github.io/ArrayDPSDemo/ and https://github.com/ArrayDPS/ArrayDPS.

Neural Radiance Fields (NeRFs) have been remarkably successful at synthesizing novel views of 3D scenes by optimizing a volumetric scene function. This scene function models how optical rays bring color information from a 3D object to the camera pixels. Radio frequency (RF) or audio signals can also be viewed as a vehicle for delivering information about the environment to a sensor. However, unlike camera pixels, an RF/audio sensor receives a mixture of signals that contain many environmental reflections (also called “multipath”). Is it still possible to infer the environment using such multipath signals? We show that with redesign, NeRFs can be taught to learn from multipath signals, and thereby “see” the environment. As a grounding application, we aim to infer the indoor floorplan of a home from sparse WiFi measurements made at multiple locations inside the home. Although a difficult inverse problem, our implicitly learnt floorplans look promising, and enables forward applications, such as indoor signal prediction and basic ray tracing.

We consider the problem of personalizing audio to maximize user experience. Briefly, we aim to find a filter h*, which applied to any music or speech, will maximize the user’s satisfaction. This is a black-box optimization problem since the user’s satisfaction function is unknown. Substantive work has been done on this topic where the key idea is to play audio samples to the user, each shaped by a different filter hi, and query the user for their satisfaction scores f(hi). A family of “surrogate” functions is then designed to fit these scores and the optimization method gradually refines these functions to arrive at the filter ˆh* that maximizes satisfaction. In certain applications, we observe that a second type of querying is possible where users can tell us the individual elements h*[j] of the optimal filter h*. Consider an analogy from cooking where the goal is to cook a recipe that maximizes user satisfaction. A user can be asked to score various cooked recipes (e.g., tofu fried rice) or to score individual ingredients (say, salt, sugar, rice, chicken, etc.). Given a budget of B queries, where a query can be of either type, our goal is to find the recipe that will maximize this user’s satisfaction. Our proposal builds on Sparse Gaussian Process Regression (GPR) and shows how a hybrid approach can outperform any one type of querying. Our results are validated through simulations and real world experiments, where volunteers gave feedback on music/speech audio and were able to achieve high satisfaction levels. We believe this idea of hybrid querying opens new problems in black-box optimization and solutions can benefit other applications beyond audio personalization.

This paper considers the problem of audio source separation, where the goal is to isolate a target audio signal (say Alice's speech) from a mixture of multiple interfering signals (e.g., when many people are talking). This problem has gained renewed interest mainly due to the significant growth in voice-controlled devices, including robots in homes, offices, and other public facilities. Although a rich body of work exists on the core topic of source separation, we find that rotational motion of the microphones (e.g., a swiveling robot-head) offers complementary gains. We show that rotating the microphone array to the optimal orientation can produce desirable “delay aliasing” between two interferers, causing the two interferers to appear as one. In general, a mixture of K signals becomes a mixture of (K - 1) signals, a mathematically concrete gain. We show that the gain translates well to practice, provided two rotation-related challenges can be mitigated. This paper is focused on mitigating these challenges and demonstrating the end-to-end performance on a fully functional prototype. We believe that our Rotational Source Separation (RoSS) module could be plugged into actual robot heads or into other devices (like Amazon Show) that are also capable of rotation.

We consider the problem of audio voice separation for binaural applications, such as earphones and hearing aids. While today’s neural networks perform remarkably well (separating 4+ sources with 2 microphones) they assume a known or fixed maximum number of sources, K. Moreover, today’s models are trained in a supervised manner, using training data synthesized from generic sources, environments, and human head shapes. This paper intends to relax both these constraints at the expense of a slight alteration in the problem definition. We observe that, when a received mixture contains too many sources, it is still helpful to separate them by region, i.e., isolating signal mixtures from each conical sector around the user’s head. This requires learning the fine-grained spatial properties of each region, including the signal distortions imposed by a person’s head. We propose a two-stage self-supervised framework in which overheard voices from earphones are pre-processed to extract relatively clean personalized signals, which are then used to train a region-wise separation model. Results show promising performance, underscoring the importance of personalization over a generic supervised approach. (audio samples available at our project website: https://uiuc-earable-computing.github.io/binaural). We believe this result could help real-world applications in selective hearing, noise cancellation, and audio augmented reality.

This paper considers the problem of estimating K angle of arrivals (AoA) using an array of M > K microphones. We assume the source signal is human voice, hence unknown to the receiver. Moreover, the signal components that arrive over K spatial paths are strongly correlated since they are delayed copies of the same source signal. Past works have successfully extracted the AoA of the direct path, or have assumed specific types of signals/channels to derive the subsequent (multipath) AoAs. Our method builds on the core observation that signals from multiple AoAs embed predictable delay-structures in them, which can be factorized through iterative alignment and cancellation. Simulation results show median AoA errors of < 4° for the first 3 AoAs. Real-world measurements, from a circular microphone array similar to Amazon Echo, show modest degradations. We believe the ability to infer even K = 3 AoAs can be helpful to various sensing and localization applications.

Head related transfer functions (HRTF) describe how sound signals bounce, scatter, and diffract when they arrive at the head, and travel towards the ears. HRTFs produce distinct sound patterns that ultimately help the brain infer the spatial properties of the sound, such as its direction of arrival, 𝜃. If an earphone can learn the HRTF, it could apply the HRTF to any sound and make that sound appear directional to the user. For instance, a directional voice guide could help a tourist navigate a new city. While past works have estimated human HRTFs, an important gap lies in personalization. Today's HRTFs are global templates that are used in all products; since human HRTFs are unique, a global HRTF only offers a coarse-grained experience. This paper shows that by moving a smartphone around the head, combined with mobile acoustic communications between the phone and the earbuds, it is possible to estimate a user's personal HRTF. Our personalization system, UNIQ, combines techniques from channel estimation, motion tracking, and signal processing, with a focus on modeling signal diffraction on the curvature of the face. The results are promising and could open new doors into the rapidly growing space of immersive AR/VR, earables, smart hearing aids, etc.

This paper finds that actions of the teeth, namely tapping and sliding, produce vibrations in the jaw and skull. These vibrations are strong enough to propagate to the edge of the face and produce vibratory signals at an earphone. By re-tasking the earphone speaker as an input transducer - a software modification in the sound card - we are able to sense teeth-related gestures across various models of ear/headphones. In fact, by analyzing the signals at the two earphones, we show the feasibility of also localizing teeth gestures, resulting in a human-to-machine interface. Challenges range from coping with weak signals, distortions due to different teeth compositions, lack of timing resolution, spectral dispersion, etc. We address these problems with a sequence of sensing techniques, resulting in the ability to detect 6 distinct gestures in real-time. Results from 18 volunteers exhibit robustness, even though our system - EarSense - does not depend on per-user training. Importantly, EarSense also remains robust in the presence of concurrent user activities, like walking, nodding, cooking and cycling. Our ongoing work is focused on detecting teeth gestures even while music is being played in the earphone; once that problem is solved, we believe EarSense could be even more compelling.

Voice assistants such as Amazon Echo (Alexa) and Google Home use microphone arrays to estimate the angle of arrival (AoA) of the human voice. This paper focuses on adding user localization as a new capability to voice assistants. For any voice command, we desire Alexa to be able to localize the user inside the home. The core challenge is two-fold: (1) accurately estimating the AoAs of multipath echoes without the knowledge of the source signal, and (2) tracing back these AoAs to reverse triangulate the user's location.

This paper aims to use modern earphones as a platform for acoustic augmented reality (AAR). We intend to play 3D audio-annotations in the user's ears as she moves and looks at AAR objects in the environment. While companies like Bose and Microsoft are beginning to release such capabilities, they are intended for outdoor environments. Our system aims to explore the challenges indoors, without requiring any infrastructure deployment. Our core idea is two-fold. (1) We jointly use the inertial sensors (IMUs) in earphones and smartphones to estimate a user's indoor location and gazing orientation. (2) We play 3D sounds in the earphones and exploit the human's responses to (re)calibrate errors in location and orientation. We believe this fusion of IMU and acoustics is novel, and could be an important step towards indoor AAR. Our system, Ear-AR, is tested on 7 volunteers invited to an AAR exhibition - like a museum - that we set up in our building's lobby and lab. Across 60 different test sessions, the volunteers browsed different subsets of 24 annotated objects as they walked around. Results show that Ear-AR plays the correct audio-annotations with good accuracy. The user-feedback is encouraging and points to further areas of research and applications.

This paper explores the possibility of detecting the hidden presence of wireless eavesdroppers. Such eavesdroppers employ passive receivers that only listen and never transmit any signals making them very hard to detect. In this paper, we show that even passive receivers leak RF signals on the wireless medium. This RF leakage, however, is extremely weak and buried under noise and other transmitted signals that can be 3-5 orders of magnitude larger. Hence, it is missed by today's radios. We design and build Ghostbuster, the first device that can reliably extract this leakage, even when it is buried under ongoing transmissions, in order to detect the hidden presence of eavesdroppers. Ghostbuster does not require any modifications to current transmitters and receivers and can accurately detect the eavesdropper in the presence of ongoing transmissions. Empirical results show that Ghostbuster can detect eavesdroppers with more than 95% accuracy up to 5 meters away.

A rich body of work has focused on motion tracking techniques using inertial sensors, namely accelerometers, gyroscopes, and magnetometers. Applications of these techniques are in indoor localization, gesture recognition, inventory tracking, vehicular motion, and many others. This paper identifies room for improvement over today's motion tracking techniques. The core observation is that conventional systems have trusted gravity more than the magnetic North to infer the 3D orientation of the object. We find that the reverse is more effective, especially when the object is in continuous fast motion. We leverage this opportunity to design MUSE, a magnetometer-centric sensor fusion algorithm for orientation tracking. Moreover, when the object's motion is somewhat restricted (e.g., human-arm motion restricted by elbow and shoulder joints), we find new methods of sensor fusion to fully leverage the restrictions. Real experiments across a wide range of uncontrolled scenarios show consistent improvement in orientation and location accuracy, without requiring any training or machine learning. We believe this is an important progress in the otherwise mature field of IMU-based motion tracking.

Ear devices, such as noise-canceling headphones and hearing aids, have dramatically changed the way we listen to the outside world. We re-envision this area by combining wireless communication with acoustics. The core idea is to scatter IoT devices in the environment that listen to ambient sound and forward it over their wireless radio. Since wireless signals travel much faster than sound, the ear-device receives the sound much earlier than its actual arrival. This "glimpse" into the future allows sufficient time for acoustic digital processing, serving as a valuable opportunity for various signal processing and machine learning applications. We believe this will enable a digital app store around human ears.

This paper shows the feasibility of identifying liquids by shining ultra-wideband (UWB) wireless signals through them. The core opportunity arises from the fact that wireless signals experience distinct slow-down and attenuation when passing through a liquid, manifesting in the phase, strength, and propagation delay of the outgoing signal. While this intuition is simple, building a robust system entails numerous challenges, including (1) pico-second scale time of flight estimation, (2) coping with integer ambiguity due to phase wraps, (3) pollution from hardware noise and multipath, and (4) compensating for the liquid-container's impact on the measurements. We address these challenges through multiple stages of signal processing without relying on any feature extraction or machine learning. Instead, we model the behavior of radio signals inside liquids (using principles of physics), and estimate the liquid's permittivity, which in turn identifies the liquid. Experiments across 33 different liquids (spread over the whole permittivity spectrum) show median permittivity error of 9%. This implies that coke can be discriminated from diet coke or pepsi, whole milk from 2% milk, and distilled water from saline water. Our end system, LiquID, is cheap, non-invasive, and amenable to real-world applications.

Active Noise Cancellation (ANC) is a classical area where noise in the environment is canceled by producing anti-noise signals near the human ears (e.g., in Bose's noise cancellation headphones). This paper brings IoT to active noise cancellation by combining wireless communication with acoustics. The core idea is to place an IoT device in the environment that listens to ambient sounds and forwards the sound over its wireless radio. Since wireless signals travel much faster than sound, our ear-device receives the sound in advance of its actual arrival. This serves as a glimpse into the future, that we call lookahead, and proves crucial for real-time noise cancellation, especially for unpredictable, wide-band sounds like music and speech. Using custom IoT hardware, as well as lookahead-aware cancellation algorithms, we demonstrate MUTE, a fully functional noise cancellation prototype that outperforms Bose's latest ANC headphone. Importantly, our design does not need to block the ear - the ear canal remains open, making it comfortable (and healthier) for continuous use.

This paper explores the possibility of injecting mobility into wireless network infrastructure. We envision WiFi APs on wheels that move to optimize user performance. Movements need not be all around the floor, neither do they have to operate on batteries. As a first step, WiFi APs at home could remain tethered to power and Ethernet outlets while moving in small areas (perhaps under the couch). If such systems prove successful, perhaps future buildings could offer explicit support for network infrastructure mobility. This paper begins with a higher level discussion of robotic wireless networks-the opportunities and the hurdles-and then pivots by developing a smaller slice of the vision through a system called iMob. With iMob, a WiFi AP is mounted on a Roomba robot and made to periodically move within a 2x2 sqft region. The core questions pertain to finding the best location to move to, such that the SNRs from its clients are strong, and the interferences from other APs are weak. Our measurements show that the richness of wireless multipath offers significant opportunities-even within a 2x2 sqft region, locations exist that are 1:7x better than the average location in terms of throughput. When multiple APs in a neighborhood coordinate, the gains can be even higher. In sum, although infrastructure mobility has been discussed in the context of Google Balloons, ad hoc networks, and delay tolerant networks, we believe that the possibility of moving our personal devices in homes and offices is relatively unexplored, and could open doors to new kinds of innovation.

Consider sounds, say at 40kHz, that are completely outside the human's audible range (20kHz), as well as a microphone's recordable range (24kHz). We show that these high frequency sounds can be designed to become recordable by unmodified microphones, while remaining inaudible to humans. The core idea lies in exploiting non-linearities in microphone hardware. Briefly, we design the sound and play it on a speaker such that, after passing through the microphone's non-linear diaphragm and power-amplifier, the signal creates a "shadow" in the audible frequency range. The shadow can be regulated to carry data bits, thereby enabling an acoustic (but inaudible) communication channel to today's microphones. Other applications include jamming spy microphones in the environment, live watermarking of music in a concert, and even acoustic denial-of-service (DoS) attacks. This paper presents BackDoor, a system that develops the technical building blocks for harnessing this opportunity. Reported results achieve upwards of 4kbps for proximate data communication, as well as room-level privacy protection against electronic eavesdropping.

We demonstrate that high frequency ultrasonic sounds can be designed to become recordable by unmodified smartphone microphones, while remaining inaudible to humans. The core idea lies in exploiting nonlinearities in microphone hardware with a combination of ultrasound frequencies. These frequencies can be regulated to carry data bits, thereby enabling an acoustic (but inaudible) communication channel to today's microphones. Other applications include jamming spy microphones in the environment, live watermarking of music in a concert, and even acoustic Denial-of-Service (DoS) attacks.

Environmental fingerprinting has been proposed as a key enabler to immersive, highly contextualized mobile computing applications, especially augmented reality. While fingerprints can be constructed in many domains (e.g., wireless RF, magnetic field, and motion patterns), visual fingerprinting is especially appealing due to the inherent heterogeneity in many indoor spaces. This visual diversity, however, is also its Achilles' heel -- matching a unique visual signature against a database of millions requires either impractical computation for a mobile device, or to upload large quantities of visual data for cloud offload. Further, most visual "features" tend to be low entropy -- e.g., homogeneous repetitions of floor and ceiling tiles. Our system VisualPrint, proposes a means to offload only the most distinctive visual data, that is, only those visual signatures which stand a good chance to yield a unique match. VisualPrint enables cloud-offloaded visual fingerprinting with efficacy comparable to using whole images, but with an order reduction in network transfer.

Most location based services require semantic place names such as Staples, rather than physical coordinates. Past work has mostly focussed on achieving localization accuracy, while assuming that the translation of physical coordinates to semantic names will be done manually. This paper makes an effort to automate this step, by leveraging the presence of a website corresponding to each store and the availability of a repository of WiFi-tagged pictures from different stores. By correlating the text inside the pictures, against the text extracted from store websites, our proposed system, called AutoLabel, can automatically label clusters of pictures, and the corresponding WiFi APs, with store names. Later, when a user enters a store, her mobile device scans the WiFi APs and consults a lookup table to recognize the store she is in. Experiment results from 40 different stores show recognition accuracy upwards of 87%, even with as few as 10 pictures from a store, offering hope that automatic large-scale semantic labeling may indeed be possible from pictures and websites of stores.

Randomized backoff is a well-established approach for avoiding collisions in CSMA networks. Today's backoff operation, such as in WiFi, attempts to create a total ordering among all the nodes contending for the channel. Total ordering requires assigning a unique backoff to each node, which is achieved by having nodes choose their back-offs from a large range, ultimately leading to channel wastage. This paper observes that total ordering can be achieved more efficiently. We propose “hierarchical backoff” in which nodes pick random numbers from a smaller range, resulting in groups of nodes picking the same number (i.e., partial order). Now, the group of nodes that picks the smallest number is advanced to a second round, where they again perform the same operation. This results in more efficient backoff because the time for partially ordering all nodes plus totally ordering each small groups is actually less than the time needed to totally order all nodes. Realizing the above intuition requires addressing new protocol challenges in group signaling, the feasibility of which is demonstrated on a USRP/GNUradio prototype. Large scale simulations also show consistent throughput gains by incorporating the proposed backoff approach into two CSMA protocols - WiFi and oCSMA. We also show that the proposed approach can be complementary to and even outperform existing backoff optimization schemes.

Internet connectivity on mobile devices is an essential commodity in today's world. While outdoors, most people connect through cellphone towers on 3G or 4G. However, cellphone tower coverage is not uniform and is affected by electromagnetic shadows cast by large structures, multipath, and absorption by various surfaces. Users with high data needs suffer in such locations due to insufficient network bandwidth. A similar insufficiency can also be felt by flash crowds in locations with otherwise moderate signal strength due to division of the available bandwidth.

Inertial sensors continuously track the 3D orientation of a flying drone, serving as the bedrock for maneuvers and stabilization. However, even the best inertial measurement units (IMU) are prone to various types of correlated failures. We consider using multiple GPS receivers on the drone as a fail-safe mechanism for IMU failures. The core challenge is in accurately computing the relative locations between each receiver pair, and translating these measurements into the drone's 3D orientation. Achieving IMU-like orientation requires the relative GPS distances to be accurate to a few centimeters -- a difficult task given that GPS today is only accurate to around 1-4 meters. Moreover, GPS-based orientation needs to be precise even under sharp drone maneuvers, GPS signal blockage, and sudden bouts of missing data. This paper designs SafetyNet, an off-the-shelf GPS-only system that addresses these challenges through a series of techniques, culminating in a novel particle filter framework running over multi-GNSS systems (GPS, GLONASS, and SBAS). Results from 11 sessions of 5-7 minute flights report median orientation accuracies of 2° even under overcast weather conditions. Of course, these improvements arise from an increase in cost due to the multiple GPS receivers, however, when safety is of interest, we believe that tradeoff is worthwhile.

This paper demonstrates the feasibility of using the vibration motor in mobile devices as a sound sensor, almost like a microphone. We show that the vibrating mass inside the motor -- designed to oscillate to changing magnetic fields -- also responds to air vibrations from nearby sounds. With appropriate processing, the responses become intelligible, to the extent that humans can understand the vibra-motor recorded words with greater than 80% average accuracy. Even off-the-shelf speech recognition softwares are able to decode at 60% accuracy, without any training or machine learning. We present our overall techniques and results through a system called VibraPhone, and discuss implications to both sensing and security.

This paper aims to track the 3D posture of the entire arm - both wrist and elbow - using the motion and magnetic sensors on smartwatches. We do not intend to employ machine learning to train the system on a specific set of gestures. Instead, we aim to trace the geometric motion of the arm, which can then be used as a generic platform for gesture-based applications. The problem is challenging because the arm posture is a function of both elbow and shoulder motions, whereas the watch is only a single point of (noisy) measurement from the wrist. Moreover, while other tracking systems (like indoor/outdoor localization) often benefit from maps or landmarks to occasionally reset their estimates, such opportunities are almost absent here.

This paper explores the possibility of injecting mobility into wireless network infrastructure. We envision WiFi access points on wheels that move to optimize user performance. Movements need not be all around the floor, neither do they have to operate on batteries. As a first step, WiFi APs at home could remain tethered to power and Ethernet outlets while moving in small areas (perhaps under the couch). If such systems prove successful, perhaps future buildings and cities could offer explicit support for network infrastructure mobility. This paper begins with a higher level discussion of robotic wireless networks -- the opportunities and the hurdles -- and then pivots by developing a smaller slice of the vision through a system called iMob. With iMob, a WiFi AP is mounted on a Roomba robot and made to periodically move within a 2x2 sqft region. The core research questions pertain to finding the best location to move to, such that the SNRs from its clients are strong, and the interferences from other APs are weak. Our measurements show that the richness of wireless multipath offers significant opportunities -- even within a 2x2 sqft region, locations exist that are 1.7x better than the average location in terms of throughput. When multiple APs in a neighborhood coordinate, the gains can be even higher. In sum, although infrastructure mobility has been discussed in the context of Google Balloons, ad hoc networks, and delay tolerant networks, we believe that the possibility of moving our personal devices in homes and offices is relatively unexplored, and could open doors to new kinds of innovation.

Indoor localization using mobile sensors has gained momentum lately. Most of the current systems rely on an extensive calibration step to achieve high accuracy. We propose SemanticSLAM, a novel unsupervised indoor localization scheme that bypasses the need for war-driving. SemanticSLAM leverages the idea that certain locations in an indoor environment have a unique signature on one or more phone sensors. Climbing stairs, for example, has a distinct pattern on the phone's accelerometer; a specific spot may experience an unusual magnetic interference while another may have a unique set of Wi-Fi access points covering it. SemanticSLAM uses these unique points in the environment as landmarks and combines them with dead-reckoning in a new Simultaneous Localization And Mapping (SLAM) framework to reduce both the localization error and convergence time. In particular, the phone inertial sensors are used to keep track of the user's path, while the observed landmarks are used to compensate for the accumulation of error in a unified probabilistic framework. Evaluation in two testbeds on Android phones shows that the system can achieve 0.53 meters human median localization errors. In addition, the system can detect the location of landmarks with 0.83 meters median error. This is 62 percent better than a system that does not use SLAM. Moreover, SemanticSLAM has a 33 percent lower convergence time compared to the same systems. This highlights the promise of SemanticSLAM as an unconventional approach for indoor localization.

This paper explores the feasibility of automatically extracting passwords from a user's daily activity logs, such as her Facebook activity, phone activity etc. As an example, a smartphone might ask the user: "Today morning from whom did you receive an SMS?" In this paper, we observe that infrequent activities (i.e., outliers) can be memorable and unpredictable. Building on this observation, we have developed an end to end system ActivPass and experimented with 70 users. With activity logs from Facebook, browsing history, call logs, and SMSs, the system achieves 95% success (authenticates legitimate users) and is compromised in 5.5% cases (authenticates impostors). While this level of security is obviously inadequate for serious authentication systems, certain practices such as password sharing can immediately be thwarted from the dynamic nature of passwords. With security improvements in the future, activity-based authentication could fill in for the inadequacies in today's password-based systems.

This paper presents experiences with eNav, a smartphone-based vehicular GPS navigation system that has an energy-saving location sensing mode capable of drastically reducing navigation energy needs. Traditional navigation systems sample the phone's GPS at a fixed rate (usually around 1Hz), regardless of factors such as current vehicle speed and distance from the next navigation waypoint. This practice results in a large energy consumption and unnecessarily reduces the attainable length of a navigation session, if the phone is left unplugged. The paper investigates two questions. First, would drivers be willing to sacrifice some of the affordances of modern navigation systems in order to prolong battery life? Second, how much energy could be saved using straightforward alternative localization mechanisms, applied to complement GPS for vehicular navigation? According to a survey we conducted of 500 drivers, as much as 91% of drivers said they would like to have a vehicular navigation application with an energy saving mode. To meet this need, eNav exploits on-board accelerometers for approximate location sensing when the vehicle is sufficiently far from the next navigation waypoint (or is stopped). A user test-study of eNav shows that it results in roughly the same user experience as standard GPS navigation systems, while reducing navigation energy consumption by almost 80%. We conclude that drivers find an energy-saving mode on phone-based vehicular navigation applications desirable, even at the expense of some loss of functionality, and that significant savings can be achieved using straightforward location sensing mechanisms that avoid frequent GPS sampling.

We present the results, experiences and lessons learned from comparing a diverse set of technical approaches to indoor localization during the 2014 Microsoft Indoor Localization Competition. 22 different solutions to indoor localization from different teams around the world were put to test in the same unfamiliar space over the course of 2 days, allowing us to directly compare the accuracy and overhead of various technologies. In this paper, we provide a detailed analysis of the evaluation study's results, discuss the current state-of-the-art in indoor localization, and highlight the areas that, based on our experience from organizing this event, need to be improved to enable the adoption of indoor location services.

Many emerging mobile computing applications are continuous vision based. The primary challenge these applications face is computation partitioning between the phone and cloud. The indoor location information is one metadata that can help these applications in making this decision. In this extended-abstract, we propose a vision based scheme to uniquely fingerprint an environment which can in turn be used to identify user's location from the uploaded visual features. Our approach takes into account that the opportunity to identify location is fleeting and the phones are resource constrained -- therefore minimal yet sufficient computation needs to be performed to make the offloading decision. Our work aims to achieve near real-time performance while scaling to buildings of arbitrary sizes. The current work is in preliminary stages but holds promise for the future -- may apply to many applications in this area.

Imagine a user typing on a laptop keyboard while wearing a smart watch. This paper asks whether motion sensors from the watch can leak information about what the user is typing. While its not surprising that some information will be leaked, the question is how much? We find that when motion signal processing is combined with patterns in English language, the leakage is substantial. Reported results show that when a user types a word $W$, it is possible to shortlist a median of 24 words, such that $W$ is in this shortlist. When the word is longer than $6$ characters, the median shortlist drops to $10$. Of course, such leaks happen without requiring any training from the user, and also under the (obvious) condition that the watch is only on the left hand. We believe this is surprising and merits awareness, especially in light of various continuous sensing apps that are emerging in the app market. Moreover, we discover additional "leaks" that can further reduce the shortlist -- we leave these exploitations to future work.

The idea of augmented reality - the ability to look at a physical object through a camera and view annotations about the object - is certainly not new. Yet, this apparently feasible vision has not yet materialized into a precise, fast, and comprehensively usable system. This paper asks: What does it take to enable augmented reality (AR) on smartphones today? To build a ready-to-use mobile AR system, we adopt a top-down approach cutting across smartphone sensing, computer vision, cloud offloading, and linear optimization. Our core contribution is in a novel location-free geometric representation of the environment - from smartphone sensors - and using this geometry to prune down the visual search space. Metrics of success include both accuracy and latency of object identification, coupled with the ease of use and scalability in uncontrolled environments. Our converged system, OverLay, is currently deployed in the engineering building and open for use to regular public; ongoing work is focussed on campus-wide deployment to serve as a "historical tour guide" of UIUC. Performance results and user responses thus far have been promising, to say the least.

This paper develops techniques using which humans can be visually recognized. While face recognition would be one approach to this problem, we believe that it may not be always possible to see a person?s face. Our technique is complementary to face recognition, and exploits the intuition that human motion patterns and clothing colors can together encode several bits of information. Treating this information as a "temporary fingerprint", it may be feasible to recognize an individual with reasonable consistency, while allowing her to turn off the fingerprint at will.

Mobile computing has traditionally implied mobile clients connected to a static infrastructure. This paper breaks away from this point of view and envisions the possibility of injecting mobility into infrastructure. We envision a WiFi access point on wheels, that moves to optimize desired performance metrics. Movements need not necessarily be all around the floor of a home or office, neither do they have to operate on batteries, or connect wirelessly to the Internet. At homes, they could remain tethered to power and Ethernet outlets while moving in small areas (perhaps under the study table). In offices of the future, perhaps APs could move on tracks installed on top of false ceilings.

We propose an augmented reality system on off-the-shelves smartphones which allows random physical object tagging. At later times, such tags could be retrieved from different locations and orientations. Our approach does not require any additional infrastructure support, localization scheme, specialized camera, or modification to smartphone's operating system. Designed and developed for current generation smartphones, our application shows promising initial results with retrieval accuracy of 82% in indoor environment without noticeable impact on the user experience.

This paper describes WalkCompass, a system that exploits smartphone sensors to estimate the direction in which a user is walking. We find that several smartphone localization systems in the recent past, including our own, make a simplifying assumption that the user's walking direction is known. In trying to relax this assumption, we were not able to find a generic solution from past work. While intuition suggests that the walking direction should be detectable through the accelerometer, in reality this direction gets blended into various other motion patterns during the act of walking, including up and down bounce, side-to-side sway, swing of arms or legs, etc. Moreover, the walking direction is in the phone's local coordinate system (e.g., along Y axis), and translation to global directions, such as 45 degree North, can be challenging when the compass is itself erroneous. WalkCompass copes with these challenges and develops a stable technique to estimate the user's walking direction within a few steps. Results drawn from 15 different environments demonstrate median error of less than 8 degrees, across 6 different users, 3 surfaces, and 3 holding positions. While there is room for improvement, we believe our current system can be immediately useful to various applications centered around localization and human activity recognition.

We present a demonstration of WalkCompass, a system to appear in the MobiSys 2014 main conference. WalkCompass exploits smartphone sensors to estimate the direction in which a user is walking. We find that several smartphone localization systems in the recent past, including our own, make a simplifying assumption that the user's walking direction is known. In trying to relax this assumption, we were not able to find a generic solution from past work. While intuition suggests that the walking direction should be detectable through the accelerometer, in reality this direction gets blended into various other motion patterns during the act of walking, including up and down bounce, side-to-side sway, swing of arms or legs, etc. WalkCompass analyzes the human walking dynamics to estimate the dominating forces and uses this knowledge to find the heading direction of the pedestrian. In the demonstration we will show the performance of this system when the user holds the smartphone on the palm. A collection of YouTube videos of the demo is posted at http://synrg.csl.illinois.edu/projects/ localization/walkcompass.

No abstract available.

This video presents a demo of indoor localization in multiple settings. In the demo, a user walks with a smartphone and the user's location is shown on the phone's screen in real time. Our system, called Unsupervised Indoor Localization (UnLoc) utilizes the sensor data from smartphones to learn "invisible landmarks" in the environment. Example landmarks could be a unique magnetic fluctuation experienced when the phone is near a water-cooler, or a distinct gyroscope rotation when the user turns a corner. We use these indoor "landmarks" to periodically reset the user's location. To track the user between these landmarks, we use an optimized variant of dead reckoning, ultimately leading to a robust location tracking system. We call our system UnLoc, since the landmarks are generated in an unsupervised manner, requiring no manual effort or floorplan of the building. The demo describes the high level intuitions, shows UnLoc in operation, and shares experiences from running UnLoc in various real-world environments.

Mobile phones are becoming the convergent platform for personal sensing, computing, and communication. This paper attempts to exploit this convergence toward the problem of automatic image tagging. We envision TagSense, a mobile phone-based collaborative system that senses the people, activity, and context in a picture, and merges them carefully to create tags on-the-fly. The main challenge pertains to discriminating phone users that are in the picture from those that are not. We deploy a prototype of TagSense on eight Android phones, and demonstrate its effectiveness through 200 pictures, taken in various social settings. While research in face recognition continues to improve image tagging, TagSense is an attempt to embrace additional dimensions of sensing toward this end goal. Performance comparison with Apple iPhoto and Google Picasa shows that such an out-of-band approach is valuable, especially with increasing device density and greater sophistication in sensing and learning algorithms.

This paper describes a system for automatically rating content - mainly movies and videos - at multiple granularities. Our key observation is that the rich set of sensors available on today's smartphones and tablets could be used to capture a wide spectrum of user reactions while users are watching movies on these devices. Examples range from acoustic signatures of laughter to detect which scenes were funny, to the stillness of the tablet indicating intense drama. Moreover, unlike in most conventional systems, these ratings need not result in just one numeric score, but could be expanded to capture the user's experience. We combine these ideas into an Android based prototype called Pulse, and test it with 11 users each of whom watched 4 to 6 movies on Samsung tablets. Encouraging results show consistent correlation between the user's actual ratings and those generated by the system. With more rigorous testing and optimization, Pulse could be a candidate for real-world adoption.

This paper presents iSee, a crowdsourced approach to detecting and localizing events in outdoor environments. Upon spotting an event, an iSee user only needs to swipe on her smartphone's touchscreen in the direction of the event. These swiping directions are often inaccurate and so are the compass measurements. Moreover, the swipes do not encode any notion of how far the event is located from the user, neither is the GPS location of the user accurate. Furthermore, multiple events may occur simultaneously and users do not explicitly indicate which events they are swiping towards. Nonetheless, as more users start contributing data, we show that our proposed system is able to quickly detect and estimate the locations of the events. We have implemented iSee on Android phones and have experimented in real-world settings by planting virtual "events" in our campus and asking volunteers to swipe on seeing one. Results show that iSee performs appreciably better than established triangulation and clustering-based approaches, in terms of localization accuracy, detection coverage, and robustness to sensor noise.

The proliferation of pictures and videos in the Internet is imposing heavy demands on mobile data networks. Though emerging wireless technologies will provide more bandwidth, the increase in demand will easily consume the additional capacity. To alleviate this problem, we explore the possibility of serving user requests from other mobile devices located geographically close to the user. For instance, when Alice reaches areas with high device density - Data Spots - the cellular operator learns Alice's content request, and guides her device to nearby devices that have the requested content. Importantly, communication between the nearby devices can be mediated by servers, avoiding many of the known problems of pure ad hoc communication. This paper argues this viability through systematic prototyping, measurements, and measurement-driven analysis.

Cooperative packet recovery has been widely investigated in wireless networks, where corrupt copies of a packet are combined to recover the original packet. While previous work such as MRD (Multi Radio Diversity) and Soft apply combining to bits and bit-confidences, combining at the symbol level has been avoided. The reason is rooted in the prohibitive overhead of sharing raw symbol information between different APs of an enterprise WLAN. We present Epicenter that overcomes this constraint, and combines multiple copies of incorrectly received “symbols” to infer the actual transmitted symbol. Our core finding is that symbols need not be represented in full fidelity - coarse representation of symbols can preserve most of their diversity, while substantially lowering the overhead. We then develop a rate estimation algorithm that actually exploits symbol level combining. Our USRP/GNURadio testbed confirms the viability of our ideas, yielding 40% throughput gain over Soft, and 25-90% over 802.11. While the gains are modest, we believe that they are realistic, and available with minimal modifications to today's EWLAN systems.

Today's smartphones provide a variety of sensors, enabling high-resolution measurements of user behavior. We envision that many services can benefit from short-term predictions of complex human behavioral patterns. While enablement of behavior awareness through sensing is a broad research theme, one possibility is in predicting how quickly a person will move through a space. Such a prediction service could have numerous applications. For one example, we imagine shop owners predicting how long a particular customer is likely to browse merchandise, and issue targeted mobile coupons accordingly - customers in a hurry can be encouraged to stay and consider discounts. Within a space of moderate size, WiFi access points are uniquely positioned to track a statistical framework for user length of stay, passively recording metrics such as WiFI signal strength (RSSI) and potentially receiving client-uploaded sensor data. In this work, we attempt to quantity this opportunity, and show that human dwell time can be predicted with reasonable accuracy, even when restricted to passively observed WiFi RSSI.

Spectrum sensing, the task of discovering spectrum usage at a given location, is a fundamental problem in dynamic spectrum access networks. While sensing in narrow spectrum bands is well studied in previous work, wideband spectrum sensing is challenging since a wideband radio is generally too expensive and power consuming for mobile devices. Sequential scan, on the other hand, can be very slow if the wide spectrum band contains many narrow channels. In this paper, we propose an analog-filter based spectrum sensing technique, which is much faster than sequential scan and much cheaper than using a wideband radio. The key insight is that, if the sum of energy on a contiguous band is low, we can conclude that all channels in this band are clear with just one measurement. Based on this insight, we design an intelligent search algorithm to minimize the number of total measurements. We prove that the algorithm has the same asymptotic complexity as compressed sensing while our design is much simpler and easily implementable in the real hardware. We show the availability of our technique using hardware devices that include analog filters and analog energy detectors. Our extensive evaluation using real TV “white space” signals shows the effectiveness of our technique.

Successive interference cancellation (SIC) is a PHY capability that allows a receiver to decode packets that arrive simultaneously. While the technique is well known in communications literature, emerging software radio platforms are making practical experimentation feasible. This motivates us to study the extent of throughput gains possible with SIC from a MAC layer perspective and scenarios where such gains are worth pursuing. We find that contrary to our initial expectation, the gains are not high when the bits of interfering signals are not known a priori to the receiver. Moreover, we observe that the scope for SIC gets squeezed by the advances in bitrate adaptation. In particular, our analysis shows that interfering one-to-one transmissions benefit less from SIC than scenarios with many-to-one transmissions (such as when clients upload data to a common access point). In view of this, we develop an SIC-aware scheduling algorithm that employs client pairing and power reduction to extract the most gains from SIC. We believe that our findings will be useful guidelines for moving forward with SIC-aware protocol research.

A growing number of mobile apps are exploiting smartphone sensors to infer user behavior, activity, or context. Inference requires training using labeled ground truth data. Obtaining labeled data for new apps is a "chicken-egg" problem. Without a reasonable amount of labeled data, apps cannot provide any service. But until an app provides useful service it is not worth installing and has no opportunity to collect user data. This paper aims to address this problem. Our intuition is that even though users are different, they exhibit similar patterns on certain sensing dimensions. For instance, different users may walk and drive at different speeds, but certain speeds will indicate driving for all users. These common patterns could be used as "seeds" to model new users through semi-supervised learning. We prototype a technique to automatically extract the commonalities to seed personalized inference models for new users. We evaluate the proposed technique through example apps and real world data.

Deploying home access points (AP) is hard. Untrained users typically purchase, install, and configure a home AP with very little awareness of wireless signal coverage and complex interference conditions. We envision a future of autonomous wireless network management that uses the Internet as an enabling technology. By leveraging a P2P architecture over wired Internet connections, nearby APs can coordinate to manage their shared wireless spectrum, especially in the face of network-crippling faults. As a specific instance of this architecture, we build RxIP, a network diagnostic and recovery tool, initially targeted towards hidden terminal mitigation. Our stable, in-kernel implementation demonstrates that APs in real home settings can detect hidden interferers, and agree on a mutually beneficial channel access strategy. Consistent throughput and fairness gains with TCP traffic and in-home micro-mobility confirm the viability of the system. We believe that using RxIP to address other network deficiencies opens a rich area for further research, helping to ensure that smarter homes of the future embed smarter networks. In the near term, with the wireless and entertainment industries poised for home-centric wireless gadgets, RxIP-type home management systems will become increasingly relevant.

Motor vehicle accidents are one of the leading causes of death. While lane departure warning, blind spot warning, and driver attention monitoring systems for avoiding collisions have been in development for quite sometime, to date mostly luxury cars are only equipped with these safety features. As a cheaper and ubiquitous alternative, we explore how a smartphone can assist an inattentive driver by leveraging its front and back cameras apart from other sensors. The challenge, however, is given the resource constraints of a smartphone, how quickly and accurately can it detect an unintended maneuver and alert the driver. In this paper, we describe our on-going attempt to address this challenge.

Many context aware applications can benefit from using high-level sensing results with semantic meanings (e.g, busy/idle). This paper proposes a platform design that provides high-level "virtual sensor" abstractions and enables new virtual sensors to be bootstrapped from existing ones.

The Wi-Fi interface is one of the major energy consuming components in smart phones. Wi-Fi scanning process contributes significantly to this. We present a solution based on partial scan, which produces full scan results, by performing only incomplete scan process. Using a decision tree algorithm, we propose such a prediction scheme, with the help of cached scan results.

This paper attempts to solve the following problem: can a distant object be localized by looking at it through a smartphone. As an example use-case, while driving on a highway entering New York, we want to look at one of the skyscrapers through the smartphone camera, and compute its GPS location. While the problem would have been far more difficult five years back, the growing number of sensors on smartphones, combined with advances in computer vision, have opened up important opportunities. We harness these opportunities through a system called Object Positioning System (OPS) that achieves reasonable localization accuracy. Our core technique uses computer vision to create an approximate 3D structure of the object and camera, and applies mobile phone sensors to scale and rotate the structure to its absolute configuration. Then, by solving (nonlinear) optimizations on the residual (scaling and rotation) error, we ultimately estimate the object's GPS position.

We attempt to localize a distant object by looking at it through a smartphone. As an example use-case, while driving on a highway entering New York, we want to look at one of the skyscrapers through the smartphone camera, and compute its GPS location. While the problem would have been far more difficult five years back, the growing number of sensors on smartphones, combined with advances in computer vision, have opened up important opportunities. We harness these opportunities through a system called Object Positioning System (OPS) [1] that achieves reasonable localization accuracy. Our core technique uses computer vision to create an approximate 3D structure of the object and camera, and applies mobile phone sensors to scale and rotate the structure to its absolute configuration. Then, by solving (nonlinear) optimizations on the residual (scaling and rotation) error, we ultimately estimate the object's GPS position.

This paper shows that the location of screen taps on modern smartphones and tablets can be identified from accelerometer and gyroscope readings. Our findings have serious implications, as we demonstrate that an attacker can launch a background process on commodity smartphones and tablets, and silently monitor the user's inputs, such as keyboard presses and icon taps. While precise tap detection is nontrivial, requiring machine learning algorithms to identify fingerprints of closely spaced keys, sensitive sensors on modern devices aid the process. We present TapPrints, a framework for inferring the location of taps on mobile device touch-screens using motion sensor data combined with machine learning analysis. By running tests on two different off-the-shelf smartphones and a tablet computer we show that identifying tap locations on the screen and inferring English letters could be done with up to 90% and 80% accuracy, respectively. By optimizing the core tap detection capability with additional information, such as contextual priors, we are able to further magnify the core threat.

This paper explores the viability of precise indoor localization using physical layer information in WiFi systems. We find evidence that channel responses from multiple OFDM subcarriers can be a promising location signature. While these signatures certainly vary over time and environmental mobility, we notice that their core structure preserves certain properties that are amenable to localization. We attempt to harness these opportunities through a functional system called PinLoc, implemented on off-the-shelf Intel 5300 cards. We evaluate the system in a busy engineering building, a crowded student center, a cafeteria, and at the Duke University museum, and demonstrate localization accuracies in the granularity of 1m x 1m boxes, called "spots". Results from 100 spots show that PinLoc is able to localize users to the correct spot with 89% mean accuracy, while incurring less than 6% false positives. We believe this is an important step forward, compared to the best indoor localization schemes of today, such as Horus.

We propose UnLoc, an unsupervised indoor localization scheme that bypasses the need for war-driving. Our key observation is that certain locations in an indoor environment present identifiable signatures on one or more sensing dimensions. An elevator, for instance, imposes a distinct pattern on a smartphone's accelerometer; a corridor-corner may overhear a unique set of WiFi access points; a specific spot may experience an unusual magnetic fluctuation. We hypothesize that these kind of signatures naturally exist in the environment, and can be envisioned as internal landmarks of a building. Mobile devices that "sense" these landmarks can recalibrate their locations, while dead-reckoning schemes can track them between landmarks. Results from 3 different indoor settings, including a shopping mall, demonstrate median location errors of 1:69m. War-driving is not necessary, neither are floorplans the system simultaneously computes the locations of users and landmarks, in a manner that they converge reasonably quickly. We believe this is an unconventional approach to indoor localization, holding promise for real-world deployment.

We propose UnLoc [1], an unsupervised indoor localization scheme that bypasses the need for war-driving. Our key observation is that certain locations in an indoor environment present an identifiable signature on one or more sensing dimensions. An elevator, for instance, imposes a distinct pattern on a smartphone's accelerometer; a specific spot may experience an unusual magnetic fluctuation. This form of urban sensing and activity recognition has already been demonstrated in literature [2, 3], but not yet applied in pure localization applications. We hypothesize that these kind of signatures naturally exist in the environment and can be envisioned as internal landmarks of a building. Mobile devices that "sense" these landmarks can recalibrate their locations, while dead-reckoning schemes can track them between landmarks. Neither war-driving nor floorplans are necessary - the system simultaneously computes the locations of users and landmarks, in a manner so that they converge reasonably quickly. We believe this is an unconventional approach to indoor localization, holding promise for real-world deployment.

We propose a content distribution strategy over municipal WiFi networks where Access Points (APs) collaboratively cache popular multimedia content, and disseminate them in a manner that each mobile device has the portion of the content just-in-time for playback. If successful, we envision that a child will be able to seamlessly watch a movie in a car, as her tablet downloads different parts of the movie over different WiFi APs at different times.

WiFi continues to be a prime source of energy consumption in mobile devices. This paper observes that, despite a rich body of research in WiFi energy management, there is room for improvement. Our key finding is that WiFi energy optimizations have conventionally been designed with a single AP in mind. However, network contention among different APs can dramatically increase a client's energy consumption. Each client may have to keep awake for long durations before its own AP gets a chance to send it packets to it. As AP density increases, the waiting time inflates, resulting in a proportional decrease in battery life. We design SleepWell, a system that achieves energy efficiency by evading network contention. The APs regulate the sleeping window of their clients in a way that different APs are active/inactive during nonoverlapping time windows. The solution is analogous to the common wisdom of going late to office and coming back late, thereby avoiding the rush hours. We implement SleepWell on a testbed of eight Laptops and nine Android phones, and evaluate it over a wide variety of scenarios and traffic patterns. Results show a median gain of up to 2x when WiFi links are strong; when links are weak and the network density is high, the gains can be even more.

WiFi clients must associate to a specific Access Point (AP) to communicate over the Internet. Current association methods are based on maximum Received Signal Strength Index (RSSI) implying that a client associates to the strongest AP around it. This is a simple scheme that has performed well in purely distributed settings. Modern wireless networks, however, are increasingly being connected by a wired backbone. The backbone allows for out-of-band communication among APs, opening up opportunities for improved protocol design. This paper takes advantage of this opportunity through a coordinated client association scheme where APs consider a global view of the network, and decide on the optimal client-AP association. We show that such an association outperforms RSSI based schemes in several scenarios, while remaining practical and scalable for wide-scale deployment. We also show that optimal association is a NP-Hard problem and our max-flow based heuristic is a promising solution.

Modern wireless interfaces support a physical-layer capability called Message in Message (MIM). Briefly, MIM allows a receiver to disengage from an ongoing reception and engage onto a stronger incoming signal. Links that otherwise conflict with each other can be made concurrent with MIM. However, the concurrency is not immediate and can be achieved only if conflicting links begin transmission in a specific order. The importance of link order is new in wireless research, motivating MIM-aware revisions to link-scheduling protocols. This paper identifies the opportunity in MIM-aware reordering, characterizes the optimal improvement in throughput, and designs a link-layer protocol for enterprise wireless LANs to achieve it. Testbed and simulation results confirm the performance gains of the proposed system.

A wireless transmitter learns of a packet loss and infers collision only after completing the entire transmission. If the transmitter could detect the collision early [such as with carrier sense multiple access with collision detection (CSMA/CD) in wired networks], it could immediately abort its transmission, freeing the channel for useful communication. There are two main hurdles to realize CSMA/CD in wireless networks. First, a wireless transmitter cannot simultaneously transmit and listen for a collision. Second, any channel activity around the transmitter may not be an indicator of collision at the receiver. This paper attempts to approximate CSMA/CD in wireless networks with a novel scheme called CSMA/CN (collision notification). Under CSMA/CN, the receiver uses PHY-layer information to detect a collision and immediately notifies the transmitter. The collision notification consists of a unique signature, sent on the same channel as the data. The transmitter employs a listener antenna and performs signature correlation to discern this notification. Once discerned, the transmitter immediately aborts the transmission. We show that the notification signature can be reliably detected at the listener antenna, even in the presence of a strong self-interference from the transmit antenna. A prototype testbed of 10 USRP/GNU Radios demonstrates the feasibility and effectiveness of CSMA/CN.

This paper shows the viability of precise indoor localization using physical layer information in WiFi systems. We find that channel frequency responses across multiple OFDM sub-carriers can be suitably aggregated into a location fingerprint. While these fingerprints vary over time and environmental mobility, we notice that their core structure preserves certain properties that are amenable to localization. We demonstrate these ideas through a functional prototype, implemented on off-the-shelf Intel 5300 cards (that export per-subcarrier information to the driver). We evaluate the prototype using the existing APs inside a busy building, a cafeteria, and a museum, and demonstrate localization accuracies in the granularity of 1m × 1m boxes, called spots. Results show that our system, PinLoc, is able to localize users to a spot with 90% mean accuracy, while incurring less than 6% false positives. We believe this holds promise towards an important development in indoor localization.

Wireless multicast applications, such as MobiTV, web telecast, and multimedia classrooms, are gaining rapid popularity. The broadcast nature of the wireless channel is amenable to such multicasts because a single packet transmission can be received by all clients. Unfortunately, the rate of this transmission is bottlenecked by data rate of the weakest client, degrading system performance. Attempts to increase the data rate results in lower reliability and higher unfairness. This paper presents PeerCast, a wireless multicast protocol that engages clients in cooperative relaying. The main idea is simple. Instead of multicasting at the bottleneck rate, the access point transmits at a high rate and suitably chooses a few stronger clients to relay the packet to the weaker ones. Multiple transmissions of the same packet, each at higher rate, can achieve better throughput than one transmission at the low, bottleneck rate. We propose a new simultaneous reply-back scheme for clients and detect the power level to estimate the AP's transmission strategy. PeerCast translates these ideas into a functional system using off-the-shelf hardware. Performance evaluation on a 9 node testbed demonstrates consistent throughput and reliability improvements over 802.11. Simulations in QualNet indicate similar trends in large-scale networks.

Conventional WiFi networks perform channel contention in time domain. This is known to be wasteful because the channel is forced to remain idle while all contending nodes are backing off for multiple time slots. This paper proposes to break away from convention and recreate the backing off operation in the frequency domain. Our basic idea leverages the observation that OFDM subcarriers can be treated as integer numbers. Thus, instead of picking a random backoff duration in time, a contending node can signal on a randomly chosen subcarrier. By employing a second antenna to listen to all the subcarriers, each node can determine whether its chosen integer (or subcarrier) is the smallest among all others. In fact, each node can even determine the rank of its chosen subcarrier, enabling the feasibility of scheduled transmissions after every round of contention. We develop these ideas into a Back2F protocol that migrates WiFi backoff to the frequency domain. Experiments on a prototype of 10 USRPs confirm feasibility, along with consistent throughput gains over 802.11. at high bit rates. Trace based simulations affirm scalability to larger, real-world network topologies.

Numerous sensors in modern mobile phones enable a range of people-centric applications. This paper envisions a system called PhonePoint Pen that uses the in-built accelerometer in mobile phones to recognize human writing. By holding the phone like a pen, a user should be able to write short messages or draw simple diagrams in the air. The acceleration due to hand gestures can be translated into geometric strokes, and recognized as characters. We prototype the PhonePoint Pen on the Nokia N95 platform, and evaluate it through real users. Results show that English characters can be identified with an average accuracy of 91.9%, if the users conform to a few reasonable constraints. Future work is focused on refining the prototype, with the goal of offering a new user-experience that complements keyboards and touch-screens.

No abstract available.

Supporting interactive, multiplayer games on mobile phones over cellular networks is a difficult problem. It is particularly relevant now with the explosion of mostly single-player or turn-based games on mobile phones. The challenges stem from the highly variable performance of cellular networks and the need for scalability (not burdening the cellular infrastructure, nor any server resources that a game developer deploys). We have built a service for matchmaking in mobile games -- assigning players to games such that game settings are satisfied as well as latency requirements for an enjoyable game. This requires solving two problems. First, the service needs to know the cellular network latency between game players. Second, the service needs to quickly group players into viable game sessions. In this paper, we present the design of our service, results from our experiments on predicting cellular latency, and results from efficiently grouping players into games.

WiFi continues to be a prime source of energy consumption in mobile devices. This paper observes that, despite a rich body of research in WiFi energy management, there is room for improvement. Our key finding is that WiFi energy optimizations have conventionally been designed with a single AP in mind. However, network contention among different APs can dramatically increase a client's energy consumption. Each client may have to keep awake for long durations before its own AP gets a chance to send packets to it. As the AP density increases in the vicinity, the waiting time inflates, resulting in a proportional decrease in battery life.We design SleepWell, a system that achieves energy efficiency by evading network contention. The APs regulate the sleeping window of their clients in a way that different APs are active/inactive during non-overlapping time windows. The solution is analogous to the common wisdom of going late to office and coming back late, thereby avoiding the rush hours. We implement SleepWell on a testbed of 8 Laptops and 9 Android phones, and evaluate it over a wide variety of scenarios and traffic patterns (YouTube, Pandora, FTP, Internet radio, and mixed). Results show a median gain of up to 2x when WiFi links are strong; when links are weak and the network density is high, the gains can be even more. We believe SleepWell is a desirable upgrade to WiFi systems, especially in light of increasing WiFi density.

WiFi continues to be a prime source of energy consumption in mobile devices. We observe that, despite a rich body of research in WiFi energy management, there is room for improvement. Our key finding is that WiFi energy optimizations have conventionally been designed with a single AP in mind. However, network contention among different APs can dramatically increase a client's energy consumption. Each client may have to keep awake for long durations before its own AP gets a chance to send packets to it. As the AP density increases in the vicinity, the waiting time inflates, resulting in a proportional decrease in battery life.

Mobile phones are becoming the convergent platform for personal sensing, computing, and communication. This paper attempts to exploit this convergence towards the problem of automatic image tagging. We envision TagSense, a mobile phone based collaborative system that senses the people, activity, and context in a picture, and merges them carefully to create tags on-the-fly. The main challenge pertains to discriminating phone users that are in the picture from those that are not. We deploy a prototype of TagSense on 8 Android phones, and demonstrate its effectiveness through 200 pictures, taken in various social settings. While research in face recognition continues to improve image tagging, TagSense is an attempt to embrace additional dimensions of sensing towards this end goal. Performance comparison with Apple iPhoto and Google Picasa shows that such an out-of-band approach is valuable, especially with increasing device density and greater sophistication in sensing/learning algorithms.

Smartphones are becoming the convergent platform for personal sensing, computing, and communication. Our work attempts to exploit this convergence towards the problem of automatic image tagging. We envision TagSense, a smartphone based collaborative system that senses the people/activity/context in a picture, and merges them carefully to create tags on-the-fly. The main challenge pertains to discriminating phone users that are in the picture, from those that are not. Our demonstration system consists of 8 Android phones and a laptop. Phones -- with the TagSense application running -- will be randomly distributed to participants. Once a picture is taken by a participant with the phone, tags generated by TagSense will be shown on the phone screen.

This poster shows the viability of precise indoor localization using physical layer information in WiFi systems. We find that channel frequency responses across multiple OFDM subcarriers can be suitably aggregated into a location signature. While these signatures vary over time and environmental mobility, we notice that their core structure preserves certain properties that are amenable to localization. We demonstrate these ideas through a functional system, implemented on off-the-shelf Intel 5300 cards (that are designed to export per-subcarrier information to the driver). We evaluate the system in a busy engineering building, a cafeteria, and the university museum, and demonstrate localization accuracies in the granularity of 1m x 1m boxes, called spots. Results show that our system, PinLoc, is able to localize users to a spot with 90% mean accuracy, while incurring less than 6% false positives. We believe this is an important step forward, compared to the best indoor localization schemes of today.

Vehicular ad hoc networks (VANETs) are being increasingly advocated for traffic control, accident avoidance, and management of parking lots and public areas. Security and privacy are two major concerns in VANETs. Unfortunately, in VANETs, most privacy-preserving schemes are vulnerable to Sybil attacks, whereby a malicious user can pretend to be multiple (other) vehicles. In this paper, we present a lightweight and scalable protocol to detect Sybil attacks. In this protocol, a malicious user pretending to be multiple (other) vehicles can be detected in a distributed manner through passive overhearing by s set of fixed nodes called road-side boxes (RSBs). The detection of Sybil attacks in this manner does not require any vehicle in the network to disclose its identity; hence privacy is preserved at all times. Simulation results are presented for a realistic test case to highlight the overhead for a centralized authority such as the DMV, the false alarm rate, and the detection latency. The results also quantify the inherent trade-off between security, i.e., the detection of Sybil attacks and detection latency, and the privacy provided to the vehicles in the network. From the results, we see our scheme being able to detect Sybil attacks at low overhead and delay, while preserving privacy of vehicles.

Wireless clients must associate to a specific Access Point (AP) to communicate over the Internet. Current association methods are based on maximum Received Signal Strength Index (RSSI) implying that a client associates to the strongest AP around it. This is a simple scheme that has performed well in purely distributed settings. Modern wireless networks, however, are increasingly being connected by a wired backbone. The backbone allows for out-of-band communication among APs, opening up opportunities for improved protocol design. This paper takes advantage of this opportunity through a coordinated client association scheme where APs consider a global view of the network, and decides on the optimal client-AP association. We show that such an association outperforms RSSI based schemes in several scenarios, while remaining practical and scalable for wide-scale deployment. Although an early work in this direction, our basic analytical framework (based on a max-flow formulation) can be extended to sophisticated channel and traffic models. Our future work is focussed towards designing and evaluating these extensions.

Conventional WiFi networks perform channel contention in time domain. This is known to be wasteful because the channel is forced to remain idle, while all contending nodes are backing off for multiple time slots. This paper proposes to break away from convention and recreate the backing off operation in the frequency domain. Our basic idea is to pretend that OFDM subcarriers are integer numbers, and thereby, view today's random backoff process as equivalent to transmitting on a randomly chosen subcarrier. By employing a second antenna to listen to all the subcarriers, each node can determine whether its chosen integer (or subcarrier) is the smallest among all others. In fact, each node can even determine the rank of its chosen integer, enabling the feasibility of a TDMA-like schedule from every round of contention. We develop these ideas into a Time to Frequency (T2F) protocol and prototype it on a small testbed of 8 USRPs. Experiments confirm its feasibility, along with promising throughput gains of more than 35% at high bit rates. A fuller design and thorough evaluation of T2F is a topic of ongoing work.

Successive interference cancellation (SIC) is a physical layer capability that allows a receiver to decode packets that arrive simultaneously. While the technique is well known in communications literature, emerging software radios are making practical experimentation feasible. This motivates us to study the extent of throughput gains possible with SIC from a MAC layer perspective. Contrary to our initial expectation, we find that the gains from SIC are not easily available in many realistic situations. Moreover, we observe that the scope for SIC gets squeezed by the advances in bitrate adaptation, casting doubt on the future of SIC based protocols.

This paper identifies the possibility of using electronic compasses and accelerometers in mobile phones, as a simple and scalable method of localization without war-driving. The idea is not fundamentally different from ship or air navigation systems, known for centuries. Nonetheless, directly applying the idea to human-scale environments is non-trivial. Noisy phone sensors and complicated human movements present practical research challenges. We cope with these challenges by recording a person's walking patterns, and matching it against possible path signatures generated from a local electronic map. Electronic maps enable greater coverage, while eliminating the reliance on WiFi infrastructure and expensive war-driving. Measurements on Nokia phones and evaluation with real users confirm the anticipated benefits. Results show a location accuracy of less than 11m in regions where today's localization services are unsatisfactory or unavailable.

The nature of human mobility demands that mobile devices become agile to diverse operating environments. Coping with such diversity requires the device to assess its environment, and trigger appropriate responses to each of them. While existing communication subsystems rely on in-band wireless signals for context-assessment and response, we explore a lateral approach of using out-of-band sensor information. We propose a relatively novel framework that synthesizes in-band and out-of-band information, facilitating more informed communication decisions. We believe that further research in this direction could enable a new kind of device agility, deficient in today's communication systems. Since such a framework is located at the boundaries of mobile sensing and wireless communication, we call it sensor assisted wireless communication.

Finding a person in a public place, such as in a library, conference hotel, or shopping mall, can be difficult. The difficulty arises from not knowing where the person may be at that time; even if known, navigating through an unfamiliar place may be frustrating. Maps and floor plans help in some occasions, but such maps may not be always handy. In a small scale poll, 80% of users responded that the ideal solution would be "to have an escort walk me to the desired person".

A wireless transmitter learns of a packet loss, infers collision, only after completing the entire transmission. If the transmitter could detect the collision early (such as with CSMA/CD in wired networks), it could immediately abort its transmission, freeing the channel for useful communication. There are two main hurdles to realize CSMA/CD in wireless networks. First, a wireless transmitter cannot simultaneously transmit and listen for a collision. Second, any channel activity around the transmitter may not be an indicator of collision at the receiver. This paper attempts to approximate CSMA/CD in wireless networks with a scheme called CSMA/CN (collision notification). Under CSMA/CN, the receiver uses PHY layer information to detect a collision and immediately notifies the transmitter. The collision notification consists of a unique signature, sent on the same channel as the data. The transmitter employs a listener antenna and performs signature correlation to discern this notification. Once discerned, the transmitter immediately aborts transmission. We show that the notification signature can be reliably detected at the listener antenna, even in the presence of a strong self-interference from the transmit antenna. A prototype testbed of 10 USRP/GNURadios demonstrates the feasibility and effectiveness of CSMA/CN

Sensor networks have been conventionally defined as a network of sensor motes that collaboratively detect events and report them to a remote monitoring station. This paper makes an attempt to extend this notion to the social context by using mobile phones as replacement of motes. We envision a social application where mobile phones collaboratively sense their ambience and recognize socially "interesting" events. The phone with a good view of the event triggers a video recording, and later, the video-clips from different phones are "stitched" into a video highlights of the occasion. We observe that such a video highlights is akin to the notion of event coverage in conventional sensor networks, only the notion of "event" has changed from physical to social. We have built a Mobile Phone based Video Highlights system (MoVi) using Nokia phones and iPod Nanos, and have experimented in real-life social gatherings. Results show that MoVi-generated video highlights (created offline) are quite similar to those created manually, (i.e., by painstakingly editing the entire video of the occasion). In that sense, MoVi can be viewed as a collaborative information distillation tool capable of filtering events of social relevance.

This paper proposes a fair association scheme between clients and APs in WiFi network, exploiting the hybrid nature of the recent WLAN architecture. We show that such an association outperforms RSSI based schemes in several scenarios, while remaining practical and scalable for wide-scale deployment.

We study broadcasting of information in a system of moving agents equipped with omnidirectional as well as directional antenna. The agent communication protocol is inspired by the classical SIRS epidemics dynamics. We assume that the antennas of all agents have a fixed transmitting power, while signal reception only occurs when the receivers sense signals with power exceeding a certain threshold. Thus, information exchange is a local phenomenon which depends on the relative distance and antenna orientation between the transmitting and the receiving agent. We derive an expression for the mean broadcasting time and study the information dissemination robustness of the system using elements of classical epidemiology and physics. In particular, we show that the mean broadcasting time depends upon ¿ which quantifies the area the radiation pattern of the antenna sweeps as it moves. We report three important observations (a) directional antennas perform better than omnidirectional antennas, (b) directional antennas whose beam-width is narrower perform even better, and (c) the performance enhances a lot if directional antennas rotate. These behaviors can be understood in the light of the reported analytical findings.

A growing number of mobile phone applications utilize physical location to express the context of information. Most of these location-based applications assume GPS capabilities. Unfortunately, GPS incurs an unacceptable energy cost that can reduce the phone's battery life to less than nine hours. Alternate localization technologies, based on WiFi or GSM, improve battery life at the expense of localization accuracy. This paper quantifies this important tradeoff that underlies a range of emerging services. Driven by measurements from Nokia N95 phones, we develop an energy-efficient localization framework called EnLoc. The framework characterizes the optimal localization accuracy for a given energy budget, and develops prediction- based heuristics for real-time use. Evaluation on traces from real users demonstrates the possibility of achieving good localization accuracy for a realistic energy budget.

A growing number of mobile computing applications are centered around the user's location. The notion of location is broad, ranging from physical coordinates (latitude/longitude) to logical labels (like Starbucks, McDonalds). While extensive research has been performed in physical localization, there have been few attempts in recognizing logical locations. This paper argues that the increasing number of sensors on mobile phones presents new opportunities for logical localization. We postulate that ambient sound, light, and color in a place convey a photo-acoustic signature that can be sensed by the phone's camera and microphone. In-built accelerometers in some phones may also be useful in inferring broad classes of user-motion, often dictated by the nature of the place. By combining these optical, acoustic, and motion attributes, it may be feasible to construct an identifiable fingerprint for logical localization. Hence, users in adjacent stores can be separated logically, even when their physical positions are extremely close. We propose SurroundSense, a mobile phone based system that explores logical localization via ambience fingerprinting. Evaluation results from 51 different stores show that SurroundSense can achieve an average accuracy of 87% when all sensing modalities are employed. We believe this is an encouraging result, opening new possibilities in indoor localization.

Modern wireless interfaces support a physical layer capability called Message in Message (MIM). Briefly, MIM allows a receiver to disengage from an ongoing reception, and engage onto a stronger incoming signal. Links that otherwise conflict with each other, can be made concurrent with MIM. However, the concurrency is not immediate, and can be achieved only if conflicting links begin transmission in a specific order. The importance of link order is new in wireless research, motivating MIM-aware revisions to link scheduling protocols. This paper identifies the opportunity in MIM-aware reordering, characterizes the optimal improvement in throughput, and designs a link layer protocol to achieve it. Testbed results confirm the performance gains of the proposed system.

Individuals face privacy risks when providing personal location data to potentially untrusted location based services (LBSs). We develop and demonstrate CacheCloak, a system that enables realtime anonymization of location data. In CacheCloak, a trusted anonymizing server generates mobility predictions from historical data and submits intersecting predicted paths simultaneously to the LBS. Each new predicted path is made to intersect with other users' paths, ensuring that no individual user's path can be reliably tracked over time. Mobile users retrieve cached query responses for successive new locations from the trusted server, triggering new prediction only when no cached response is available for their current locations. A simulated hostile LBS with detailed mobility pattern data attempts to track users of CacheCloak, generating a quantitative measure of location privacy over time. GPS data from a GIS-based traffic simulation in an urban environment shows that CacheCloak can achieve realtime location privacy without loss of location accuracy or availability.

Wireless link layer multicast is an important service primitive for emerging applications, such as live video, streaming audio, and other content telecasts. The broadcast nature of the wireless channel is amenable to multicast because a single packet transmission may be received by all clients in the multicast group. However, in view of diverse channel conditions at different clients, the rate of such a transmission is bottlenecked by the rate of the weakest client. Multicast throughput degrades severely. Attempts to increase the data rate result in lower reliability and higher unfairness. This paper utilizes smart beamforming antennas to improve multicast performance in wireless LANs. The main idea is to satisfy the stronger clients with a high-rate omnidirectional transmission, followed by high-rate directional transmission(s) to cover the weaker ones. By selecting an optimal transmission strategy (using dynamic programming), we show that the multicast throughput can be maximized while achieving a desired delivery ratio at all the clients. We use testbed measurements to verify our main assumptions. We simulate our protocol in Qualnet, and observe consistent performance improvements over a range of client topologies and time-varying channel conditions.

Recent years have witnessed the impacts of distributed content sharing (Wikipedia, Blogger), social networks (Facebook, MySpace), sensor networks, and pervasive computing. We believe that significant more impact is latent in the convergence of these ideas on the mobile phone platform. Phones can be envisioned as people-centric sensors capable of aggregating participatory as well as sensory inputs from local surroundings. The inputs can be visualized in different dimensions, such as space and time. When plugged into the Internet, the collaborative inputs from phones may enable a high resolution view of the world. This paper presents the architecture and implementation of one such system, called Micro-Blog. New kinds of application-driven challenges are identified and addressed in the context of this system. Implemented on Nokia N95 mobile phones, Micro-Blog was distributed to volunteers for real life use. Promising feedback suggests that Micro-Blog can be a deployable tool for sharing, browsing, and querying global information.

Neighbors of both the transmitter and the receiver must keep quiet in a 802.11 wireless network as it requires bidirectional exchange, i.e., nodes reverse their roles as transmitters and receivers, for transmitting a single DATA frame. To reduce role reversals and to improve spatial reuse, a piggybacked acknowledgment based approach has been proposed to enable concurrent transmissions. Recent findings on physical layer capture show that it is possible to capture a frame of interest in the presence of concurrent interference and that the SINR threshold is dependent on the relative order in which the frame and the interference arrive at the receiver. In this paper, we show that it is possible to exploit capture and increase concurrent transmissions in wireless adhoc networks. We develop a distributed channel access scheme and demonstrate that it offers significant throughput gain particularly at lower data rates.

A large majority of the Internet traffic relies on TCP as its transport protocol. In future, as the edge of the Internet continues to extend over the wireless medium, TCP (or its close variants) may not prove to be appropriate. The key reason is in TCP’s inability to discriminate congestion losses from transmission losses. Since transmission losses are frequent in wireless networks, the penalty from loss misclassification can become high, leading to performance degradation. This paper presents an eXtended Rate-based Transport Protocol (XRTP), designed to support communication over lossy wireless media. We depart from the ack-based rate control paradigm. Instead, we try to estimate the network conditions by injecting probe packets at the sender, and then observing the spacing between packets that arrive at the receiver. We show that these observations can be useful indicators of available bandwidth, network congestion, and even the cause of packet loss. The inferences from the observations are utilized to regulate the transmission rate at the sender, leading to desirable properties of congestion control and loss discrimination. Simulation results show the efficacy of our proposed rate-based protocol in lossy wireless environments.

802.11 requires bidirectional exchange (i.e., nodes reverse their roles as transmitters and receivers) and hence neighbors of both the transmitter and receiver must keep quiet for the entire duration of communication. This degrades spatial reuse, leading to low network throughput. To address this problem, power control, rate control, and carrier-sense adaptations have successfully identified possibilities of concurrency in the spatial domain. In the temporal domain, optimizations such as piggybacked Acks [1] have reduced role reversals, also enabling concurrency. Though beneficial, these improvements are bounded by the SINR requirement. Recent studies found that the SINR threshold is a dynamic value, dependent on the relative order in which the signal and the interference arrive at the receiver. This implies that under certain conditions, it might be feasible to capture a data frame in the presence of concurrent interference. If harnessed carefully, this can help improve the spatial reuse of wireless networks.

Vehicular ad hoc networks (VANETs) are being advocated for traffic control, accident avoidance, and a variety of other applications. Security is an important concern in VANETs because a malicious user may deliberately mislead other vehicles and vehicular agencies. One type of malicious behavior is called a Sybil attack, wherein a malicious vehicle pretends to be multiple other vehicles. Reported data from a Sybil attacker will appear to arrive from a large number of distinct vehicles, and hence will be credible. This paper proposes a light-weight and scalable framework to detect Sybil attacks. Importantly, the proposed scheme does not require any vehicle in the network to disclose its identity, hence privacy is preserved at all times. Simulation results demonstrate the efficacy of our protocol.

The synergy of phone sensors (microphone, camera, GPS, etc.), wireless capability, and ever-increasing device density can lead to novel people-centric applications. Unlike traditional sensor networks, the next generation networks may be participatory, interactive, and in the scale of human users. Millions of global data points can be organized on a visual platform, queried, and sophistically answered through human participation. Recent years have witnessed the isolated impacts of distributed knowledge sharing (Wikipedia), social networks, sensor networks, and mobile communication. We believe that significant more impact is latent in their convergence, that can to be drawn out through innovations in applications. This demonstration, called Micro-Blog, is a first step towards this goal.

The 802.11e amendment to IEEE 802.11 standard defines a block acknowledgement (ACK) mechanism to reduce the overhead required by a station to acknowledge the receipt of multiple frames. This paper presents an analytic model for estimating the overhead required to selectively retransmit data frames when using the block ACK mechanism in a noisy channel. This model is applicable both to the present block ACK mechanism and further refinements that could be proposed in a future standards amendment, such as the 802.11n high throughput task group.

A network-wide broadcast service is often used for information dissemination in sensor networks. Sensor networks are typically energy-constrained and prone to failures. In view of these constraints, the broadcast service should minimize energy consumption by reducing redundant transmissions, and be tolerant to frequent node and link failures. We propose "smart gossip", a probabilistic protocol that offers a broadcast service with low overheads. Smart gossip automatically and dynamically adapts transmission probabilities based on the underlying network topology. The protocol is capable of coping with wireless losses and unpredictable node failures that affect network connectivity over time. The resulting protocol is completely decentralized. We present thorough experimental results to evaluate our "smart gossip" proposal, and demonstrate its benefits over existing protocols

We investigate the possibility of using directional antennas for medium access control in wireless ad hoc networks. Previous research in ad hoc networks typically assumes the use of omnidirectional antennas at all nodes. With omnidirectional antennas, while two nodes are communicating using a given channel, MAC protocols such as IEEE 802.11 require all other nodes in the vicinity to remain silent. With directional antennas, two pairs of nodes located in each other's vicinity may potentially communicate simultaneously, increasing spatial reuse of the wireless channel. Range extension due to higher gain of directional antennas can also be useful in discovering fewer hop routes. However, new problems arise when using directional beams that simple modifications to 802.11 may not be able to mitigate. This paper identifies these problems and evaluates the tradeoffs associated with them. We also design a directional MAC protocol (MMAC) that uses multihop RTSs to establish links between distant nodes and then transmits CTS, DATA, and ACK over a single hop. While MMAC does not address all the problems identified with directional communication, it is an attempt to exploit the primary benefits of beamforming in the presence of some of these problems. Results show that MMAC can perform better than IEEE 802.11, although we find that the performance is dependent on the topology and flow patterns in the system.

Several network services, including routing, resource-discovery, etc., require the knowledge of a node's location, before invoking their respective algorithms. Locating a node is a challenging problem in large-scale ad hoc networks, especially when the nodes are mobile. Initial approaches to learn a node's location relied on flooding a query in the network. In view of the large overheads of flooding, gossiping was later proposed as a scalable alternative. With gossiping, each node probabilistically forwards the query. Research findings show that for carefully chosen gossip probabilities, the query is very likely to reach the destination. While gossiping is a random propagation of a specific information, a similar effect might be achieved if nodes move randomly carrying the same information in their local caches. Thus, a node's location information can diffuse into the network via node mobility, as opposed to wireless transmissions that incur bandwidth. If these mobile nodes lend their caches to be queried by its neighborhood, a distributed location estimation service can be envisioned. Clearly, wireless transmission and physical mobility appear to be two modes of information transportation. While each have been studied individually, there has been little work on the possibility of combining them. For example, mobile nodes that gossip with each other periodically, may achieve percolation at significantly lower overheads. This paper investigates the combined potential of gossip and random (Brownian) node mobility. We argue that using such a combined strategy, it might be possible to design a scalable location service for mobile networks, over which several other applications can be developed, including geographic routing, resource discovery, etc

This work addresses deafness - a problem that appears when MAC protocols are designed using directional antennas. Briefly, deafness is caused when a transmitter fails to communicate to its intended receiver, because the receiver is beamformed towards a direction away from the transmitter. Existing CSMA/CA protocols rely on the assumption that congestion is the predominant cause of communication failure, and adopt backoff schemes to handle congestion. While this may be appropriate for omnidirectional antennas, for directional antennas, both deafness and congestion can be the reason for communication failures. An appropriate directional MAC protocol needs to classify the actual cause of failure, and react accordingly. This paper quantifies the impact of deafness on directional medium access control, and proposes a tone-based mechanism as one way of addressing deafness. The tone-based mechanism, ToneDMAC, assumes congestion as the default reason for communication failures, and applies a corrective measure whenever the cause is deafness. Simulation results indicate that ToneDMAC can alleviate deafness, and perform better than existing directional MAC protocols.

Previous research in wireless ad hoc networks typically assumes the use of omnidirectional antennas at all nodes. With omnidirectional antennas, while two nodes are communicating using a given channel, MAC protocols such as IEEE 802.11 require all other nodes in the vicinity to stay silent. With directional antennas, two pairs of nodes located in each other's vicinity may potentially communicate simultaneously, depending on the directions of transmission. This can increase spatial reuse of the wireless channel. In addition, the higher gain of directional antennas allows a node to communicate with other nodes located far away, implying that messages could be delivered to the destination in fewer hops. In this paper, we propose a MAC protocol that exploits the characteristics of directional antennas. Our design focuses on using multi-hop RTSs to establish links between distant nodes, and then transmit CTS, DATA and ACK over a single hop. Results show that our directional MAC protocol can perform better than IEEE 802.11, although we find that the performance is dependent on the topology configuration and the flow patterns in the system.

Realizing high volume real time communication in a highly dynamic architecture like Mobile Ad hoc Networks (MANET) still remains a major point of research. In this paper, we have attempted to address the issue of maintaining an uninterrupted session between a source and a destination through multiple paths in a temporal domain. We have tried to develop an agentcentric protocol that would accomplish multimedia communication over adaptively selected routes. The protocol ensures minimal consumption of network resources. We have organized this work in two logical steps. In the first part, we have devised an agent-based framework with its associated protocols and mechanisms. The agents in the framework move from one node to another in the MANET architecture. The primary objective of this mobile multi-agent framework is to asynchronously collect network topology information (like node velocity, node location etc.) and distribute them into the information cache of all other nodes. This is accomplished proactively with the aim of making all nodes in the system topology-aware. The second part of the work attempts to make use of this topology awareness in the context of establishing and maintaining a communication link between two nodes. The agentenabled proactive replenishment of fresh topology information enables the node to constantly evaluate network conditions.

Summary form only given. We have discussed a mobile multi-agent based framework to address the aspect of topology discovery in ad hoc wireless network environment. In other words, we have designed a multi-agent based protocol to make the nodes in the network topology aware. Our primary aim is to collect all topology-related information from each node in the network and distribute them periodically (as updates) to other nodes through mobile agents. The notion of stigmergic communication has been used through the implementation of a shared information cache in each node. Moreover, we have used a concept of link stability and information aging based on which a predictive algorithm running on each node can predict the current network topology based on the current network information stored at that node. We have demonstrated through performance evaluation of a simulated system that the use of mobile multi-agent framework would be able to make each node in the network topology aware without consuming large portion of network capacity. This would eventually help us to implement a proactive routing protocol without much overhead. Moreover, as a direct outcome of infiltrating topology information into the nodes, the foundations for designing distributed network management and implementing communication awareness get automatically laid.