A backscatter tag-to-tag network enables battery-less communication by harvesting energy and reflecting wireless signals between tags, making it ideal for energy-efficient IoT applications such as asset tracking, structural health monitoring, and environmental sensing. Accurate localization is crucial for these applications. While RSSI-based (Received Signal Strength Indicator) localization is the most common method for RF localization—estimating distance based on the received signal strength—it is often dependent on the position and power of the excitation source. We present a novel distance estimation method based on the estimation of the channel path loss and phase between tags, which is independent of the excitation source’s position and power. The experimental results demonstrate millimeter-level accuracy in 67% of cases and 99% accuracy within 17 cm for tag-to-tag distances up to 2.4 meters at 915 MHz.

Millions of video cameras are deployed globally across major cities for learning-based video analytic (VA) applications, such as object detection. Video streams from the cameras are either sent over the wide-area network to be processed by the cloud or are (at least partially) processed in a local edge workstation, incurring significant latency and elevated financial costs. In this paper, to minimize reliance on the cloud and overcome the unavailability of high-compute workstations on edge, we investigate the use of heterogeneous and distributed embedded devices as edge nodes shared by multiple cameras to fully serve the video processing needs of a VA application (without requiring cloud support). We present OVIDA, an edge-only orchestrator to deploy VA application(s) on a distributed edge environment to maximize accuracy. Given the resource-constrained nature of edge nodes, OVIDA disaggregates the VA application pipeline into multiple modules. OVIDA's core functionality and contributions are: (i) optimizing the placement and replication of the VA application modules across the edge nodes to maximize the throughput, and in turn, accuracy; and (ii) an adaptive model selection algorithm for VA modules based on accuracy-throughput tradeoff to maximize accuracy in response to varying load conditions. To further improve performance, OVIDA employs a central-queue-based design (instead of the usual push-based design), which also obviates the need for complex load balancing algorithms. We implement OVIDA on top of Kubernetes and evaluate its performance for three VA applications, supported over a heterogeneous edge cluster under varying network conditions. When compared against several baselines in our evaluation, we achieve throughput and accuracy gains of at least 51% and 28%.

Edge computing has emerged as an alternative to reduce transmission and processing delay and preserve privacy of the video streams. However, the ever-increasing complexity of Deep Neural Networks (DNNs) used in video-based applications (e.g. object detection) exerts pressure on memory-constrained edge devices. Model merging is proposed to reduce the DNNs' memory footprint by keeping only one copy of merged layers' weights in memory. In existing model merging techniques, (i) only architecturally identical layers can be shared; (ii) requires computationally expensive retraining in the cloud; (iii) assumes the availability of ground truth for retraining. The re-evaluation of a merged model's performance, however, requires a validation dataset with ground truth, typically runs at the cloud. Common metrics to guide the selection of shared layers include the size or computational cost of shared layers or representation size. We propose a new model merging scheme by sharing representations (i.e., outputs of layers) at the edge, guided by representation similarity S. We show that S is extremely highly correlated with merged model's accuracy with Pearson Correlation Coefficient |r| > 0.94 than other metrics, demonstrating that representation similarity can serve as a strong validation accuracy indicator without ground truth. We present our preliminary results of the newly proposed model merging scheme with identified challenges, demonstrating a promising research future direction.

The emergence of immersive multimedia content over mobile devices introduces applications that demand superior data bandwidth and low delay in network connections. Especially, the required network bandwidth and delays in 360-degree video streaming make it hard to achieve high QoE using TCP over inherently variable wireless networks. To overcome such limi-tations, this paper explores the use of QUIC and its multipath extension (Multipath QUIC or MPQUIC) for 360-degree video streaming. We also present a Cross-Layer Scheduling mechanism (CLS) for QUIC and MPQUIC to address further the lack of prioritization in QUIC's stream multiplexing. CLS uses appli-cation layer information, such as object sizes and priorities, and network layer information, such as network delays and bandwidth. It uses a variation of a job scheduling algorithm to schedule segments for QUIC streams. We implement CLS in the application layer without modifying QUIC/MPQUIC and follow the MPEG-DASH standard for video streaming. Our evaluation demonstrates significant improvement in user's QOE including rebuffering over baseline QUIC or TCP.

Large scale networks of intelligent sensors that can function without any batteries will have enormous implications in applications that range from smart spaces to structural and environmental monitoring. RF tags present an amenable platform for sensor integration as the backscatter communication offers low energy cost of communication. Current RF tags either use extremely low-power sensors or perform tasks of tag localization and identification based on the strength of the backscatter signal. We present a technique for estimation of amplitude and phase of the tag-to-tag channel that can be performed with very limited computational and energy resources. This enables monitoring of the interactions between tagged objects and activities around tags, as well as assessment of a variety of engineering structures. Experimental results demonstrate high resolution in the amplitude and phase channel measurement at a distances ranging from 22 cm to 1.34 m.

We address the problem of localizing an (unauthorized) transmitter using a distributed set of sensors. Our focus is on developing techniques that perform the transmitter localization in an efficient manner, wherein the efficiency is defined in terms of the number of sensors used to localize. Localization of unauthorized transmitters is an important problem which arises in many important applications, e.g., in patrolling of shared spectrum systems for any unauthorized users. Localization of transmitters is generally done based on observations from a deployed set of sensors with limited resources, thus it is imperative to design techniques that minimize the sensors’ energy resources. In this paper, we design greedy approximation algorithms for the optimization problem of selecting a given number of sensors in order to maximize an appropriately defined objective function of localization accuracy. The obvious greedy algorithm delivers a constant-factor approximation only for the special case of two hypotheses (potential locations). For the general case of multiple hypotheses, we design a greedy algorithm based on an appropriate auxiliary objective function—and show that it delivers a provably approximate solution for the general case. We develop techniques to significantly reduce the time complexity of the designed algorithms by incorporating certain observations and reasonable assumptions. We evaluate our techniques over multiple simulation platforms, including an indoor as well as an outdoor testbed, and demonstrate the effectiveness of our designed techniques—our techniques easily outperform prior and other approaches by up to 50-60% in large-scale simulations and up to 16% in small-scale testbeds.

With the next generation immersive video applications, network capacity is becoming a growing bottleneck to deliver a high quality video to end-users. Recent advances to tackle this challenge introduced super-resolution (SR) for video quality enhancement through neural computations by leveraging client-side compute capacity. However, the existing SR models are bulky, compute-, and memory-expensive, which makes it difficult to deploy them in practice. In this work, we present dcSR, a lightweight data-centric SR approach that enables a practical neural quality enhancement for videos. On the server-side, dcSR constructs micro SR models trained on a few selected frames from each video through a data-centric paradigm by employing a long term video scene understanding mechanism. On the client-side, dcSR integrates the micro SR models into the regular video decoder and enhances the video quality in real-time without compromising on quality enhancement. We evaluate dcSR and show its benefits by comparing it with previous methods.

We present RF energy harvester and management strategy tailored for the passive near-zero power devices. Radio- less RF-powered backscattering tags that have the ability to recognize and localize activities in the surrounding environment are example of such devices. We propose a management strategy that determines the operation regime of the harvester based on the input power level at which harvester provides the instantaneous supply voltage for device operation. As the input power exceeds this level, the storage of the excess energy is managed by an adaptive capacitor charging circuit that keeps the voltage at the input of voltage regulator constant. We demonstrate that backscatter-based RF tag in the listening mode of operation can instantaneously operate with an input power of -34.4 dBm. Due to the adaptive capacitor charging circuit, the power efficiency of the energy harvester is higher than 50% over a range of input powers from -25 dBm up to -5 dBm.

Backscattering tags transmit passively without an on-board active radio transmitter. Almost all present-day backscatter systems, however, rely on active radio receivers. This presents a significant scalability, power and cost challenge for backscatter systems. To overcome this barrier, recent research has empowered these passive tags with the ability to reliably receive backscatter signals from other tags. This forms the building block of passive networks wherein tags talk to each other without an active radio on either the transmit or receive side. For wider functionality, accurate localization of such tags is critical. All known backscatter tag localization techniques rely on active receivers for measuring and characterizing the received signal. As a result, they cannot be directly applied to passive tag-to-tag networks. This paper overcomes the gap by developing a localization technique for such passive networks based on a novel method for phase-based ranging in passive receivers. This method allows pairs of passive tags to collaboratively determine the inter-tag channel phase while effectively minimizing the effects of multipath and noise in the surrounding environment. Building on this, we develop a localization technique that benefits from large link diversity uniquely available in a passive tag-to-tag network. We evaluate the performance of our techniques with extensive micro-benchmarking experiments in an indoor environment using fabricated prototypes of tag hardware. We show that our phase-based ranging performs similar to active receivers, providing median 1D ranging error <1 cm and median localization error also <1 cm. Benefiting from the large-scale link diversity our localization technique outperforms several state-of-the-art techniques that use active receivers.

For bandwidth-efficient streaming of 360-degree videos, the streaming technique must adapt both to the changing viewport of the user and variations of the available network bandwidth. The state-of-the-art streaming techniques for this problem attempt to solve an optimization using simplified rules that do not adapt very well to the uncertainties related to the viewport or network. We adopt a 3D-Convolutional Neural Networks (3DCNN) model to extract spatio-temporal features of videos and predict the viewport. Given the sequential decision-making nature of such streaming technique, we then apply a Reinforcement Learning (RL) based adaptive streaming approach. We address the challenges of using RL in this scenario, such as large action space and delayed reward evaluation. Comprehensive evaluations with real network traces show that the proposed method outperforms three tile-based streaming techniques for 360-degree videos. Compared to the tile-based streaming techniques, the average user-perceived bitrate of the proposed method is 1.3-1.7 times higher and the average quality of experience of the proposed method is also 1.6-3.4 times higher. Subjective user studies further confirm the superiority of the proposed approach.

Conventional streaming solutions for streaming 360-degree panoramic videos are inefficient in that they download the entire 360-degree panoramic scene, while the user views only a small sub-part of the scene called the viewport. This can waste over 80% of the network bandwidth. We develop a comprehensive approach called Mosaic that combines a powerful neural network-based viewport prediction with a rate control mechanism that assigns rates to different tiles in the 360-degree frame such that the video quality of experience is optimized subject to a given network capacity. We model the optimization as a multi-choice knapsack problem and solve it using a greedy approach. We also develop an end-to-end testbed using standards-compliant components and provide a comprehensive performance evaluation of Mosaic along with five other streaming techniques - two for conventional adaptive video streaming and three for 360-degree tile-based video streaming. Mosaic outperforms the best of the competitions by as much as 47-191% in terms of average video quality of experience. Simulation-based evaluation as well as subjective user studies further confirm the superiority of the proposed approach.

In this paper, we present a technique whereby passive tags can track each other in a backscattering tag-to-tag network (BTTN). In such a network, passive tags without any on-board radio transceivers communicate directly with each other by backscattering an external excitation signal. First, we explain how the tags determine their distances to other communicating tags in their proximity and then how they can track nearby tags. Our technique is based on multiphase backscattering, more specifically, on the ability of backscattering tags to systematically change the phase offset of the signal that is being backscattered. A passive receiving tag with an envelope detector can then examine the received signal amplitude over the multiple backscattering phases and can draw inferences about the inter-tag distance. We demonstrate our method and show its accuracy on tags that we have built in our lab. Experiments show that our passive tags can measure Doppler shifts with approximately the same accuracy as that achieved by active conventional RFID readers. Our median tracking error based on data from two tags is only about 2.5 cm.

We address the problem of localizing an (illegal) transmitter using a distributed set of sensors. Our focus is on developing techniques that perform the transmitter localization in an efficient manner, wherein the efficiency is defined in terms of the number of sensors used to localize. Localization of illegal transmitters is an important problem which arises in many important applications, e.g., in patrolling of shared spectrum systems for any unauthorized users. Localization of transmitters is generally done based on observations from a deployed set of sensors with limited resources, thus it is imperative to design techniques that minimize the sensors' energy resources. In this paper, we design greedy approximation algorithms for the optimization problem of selecting a given number of sensors in order to maximize an appropriately defined objective function of localization accuracy. The obvious greedy algorithm delivers a constant-factor approximation only for the special case of two hypotheses (potential locations). For the general case of multiple hypotheses, we design a greedy algorithm based on an appropriate auxiliary objective function - and show that it delivers a provably approximate solution for the general case. We develop techniques to significantly reduce the time complexity of the designed algorithms, by incorporating certain observations and reasonable assumptions. We evaluate our techniques over multiple simulation platforms, including an indoor as well as an outdoor testbed, and demonstrate the effectiveness of our designed techniques - our techniques easily outperform prior and other approaches by up to 50-60% in large-scale simulations.

360° videos provide an immersive experience to users, but require considerably more bandwidth to stream compared to regular videos. State-of-the-art 360° video streaming systems use viewport prediction to reduce bandwidth requirement, that involves predicting which part of the video the user will view and only fetching that content. However, viewport prediction is error prone resulting in poor user Quality of Experience (QoE). We design PARSEC, a 360° video streaming system that reduces bandwidth requirement while improving video quality. PARSEC trades off bandwidth for additional client-side computation to achieve its goals. PARSEC uses an approach based on super-resolution, where the video is significantly compressed at the server and the client runs a deep learning model to enhance the video to a much higher quality. PARSEC addresses a set of challenges associated with using super-resolution for 360° video streaming: large deep learning models, slow inference rate, and variance in the quality of the enhanced videos. To this end, PAR-SEC trains small micro-models over shorter video segments, and then combines traditional video encoding with super-resolution techniques to overcome the challenges. We evaluate PARSEC on a real WiFi network, over a broadband network trace released by FCC, and over a 4G/LTE network trace. PARSEC significantly outperforms the state-of-art 360° video streaming systems while reducing the bandwidth requirement.

Free floating sub-mm and mm sized brain implants can communicate through a backscatter-based link in a presence of the EM field generated by the external coil. This link reduces the bandwidth requirement in the uplink communication of these implants to the external coil and enables a close-loop operation of the distributed implant system through reduced latency. The critical challenge in the link design stems from the low modulation index in the incident signal at the receiving coil. This calls for the design of the ASK demodulator that can resolve signals with low modulation index. We propose a demodulator design comprising a self-biased common-source based envelope detector that provides sufficient conversion gain and at the same time operates with a low power consumption. With 90 MHz carrier frequency and 50-kbps data rate, the ASK demodulator, implemented in 65 nm CMOS technology, resolves input RF signal with 1% modulation index consuming less than 100 nW when amplitude of the input RF signal is 200 mV.

Page Load Time (PLT) is critical in measuring web page load performance. However, the existing PLT metrics are designed to measure the Web page load performance on desktops/laptops and do not consider user interactions on mobile browsers. As a result, they are ill-suited to measure mobile page load performance from the perspective of the user. In this work, we present the Mobile User-Centered Page Load Time Estimator (muPLTest), a model that estimates the PLT of users on Web pages for mobile browsers. We show that traditional methods to measure user PLT for desktops are unsuited to mobiles because they only consider the initial viewport, which is the part of the screen that is in the user’s view when they first begin to load the page. However, mobile users view multiple viewports during the page load process since they start to scroll even before the page is loaded. We thus construct the muPLTest to account for page load activities across viewports. We train our model with crowdsourced scrolling behavior from live users. We show that muPLTest predicts ground truth user-centered PLT, or the muPLT, obtained from live users with an error of 10-15% across 50 Web pages. Comparatively, traditional PLT metrics perform within 44-90% of the muPLT. Finally, we show how developers can use the muPLTest to scalably estimate changes in user experience when applying different Web optimizations.

Consumer IoT networks are characterized by heterogeneous devices with diverse functionality and programming interfaces. This lack of homogeneity makes the integration and secure management of IoT infrastructures a daunting task for users and administrators. In this paper, we introduce VISCR, a Vendor-Independent policy Specification and Conflict Resolution engine that enables intent-based conflict-free policy specification and enforcement in IoT environments. VISCR converts the topology of the IoT infrastructure into a tree-based abstraction and translates existing policies from heterogeneous vendor-specific programming languages, such as Groovy-based SmartThings, OpenHAB, IFTTT-based templates, and MUD-based profiles, into a vendor-independent graph-based specification. These are then used to automatically detect rogue policies, policy conflicts, and automation bugs. We evaluated VISCR using a dataset of 907 IoT apps, programmed using heterogeneous automation specifications, in a simulated smart-building IoT infrastructure. In our experiments, among 907 IoT apps, VISCR exposed 342 of IoT apps as exhibiting one or more violations, while also running 14.2x faster than the state-of-the-art tool (Soteria). VISCR detected 100% of violations reported by Soteria while also detecting new types of violations in 266 additional apps.

The Science DMZ (SDMZ) is a special purpose network architecture proposed by ESnet (Energy Sciences Network) to facilitate distributed science experimentation on terabyte- (or petabyte-) scale data, exchanged over ultra-high bandwidth WAN links. Critical security challenges faced by these networks include: (i) network monitoring at high bandwidths, (ii) reconciling site-specific policies with project-level policies for conflict-free policy enforcement, (iii) dealing with geographically-distributed datasets with varying levels of sensitivity, and (iv) dynamically enforcing appropriate security rules. To address these challenges, we develop a fine-grained dataflow-based security enforcement system, called CoordiNetZ (CNZ), that provides coordinated situational awareness, i.e., the use of context-aware tagging for policy enforcement using the dynamic contextual information derived from hosts and network elements. We also developed tag and IP-based security microservices that incur minimal overheads in enforcing security to data flows exchanged across geographically-distributed SDMZ sites. We evaluate our prototype implementation across two geographically distributed SDMZ sites with SDN-based case studies, and present performance measurements that respectively highlight the utility of our framework and demonstrate efficient implementation of security policies across distributed SDMZ networks.

Observable reading behavior, the act of moving the eyes over lines of text, is highly stereotyped among the users of a language, and this has led to the development of reading detectors-methods that input windows of sequential fixations and output predictions of the fixation behavior during those windows being reading or skimming. The present study introduces a new method for reading detection using Region Ranking SVM (RRSVM). An SVM-based classifier learns the local oculomotor features that are important for real-time reading detection while it is optimizing for the global reading/skimming classification, making it unnecessary to hand-label local fixation windows for model training. This RRSVM reading detector was trained and evaluated using eye movement data collected in a laboratory context, where participants viewed modified web news articles and had to either read them carefully for comprehension or skim them quickly for the selection of keywords (separate groups). Ground truth labels were known at the global level (the instructed reading or skimming task), and obtained at the local level in a separate rating task. The RRSVM reading detector accurately predicted 82.5% of the global (article-level) reading/skimming behavior, with accuracy in predicting local window labels ranging from 72-95%, depending on how tuned the RRSVM was for local and global weights. With this RRSVM reading detector, a method now exists for near real-time reading detection without the need for hand-labeling of local fixation windows. With real-time reading detection capability comes the potential for applications ranging from education and training to intelligent interfaces that learn what a user is likely to know based on previous detection of their reading behavior.

We have developed a type of RFID tags that can communicate with each other directly if there is an RF signal in their environment to support backscattering. These tags are passive and they can form a tag-to-tag network. Our tags communicate by what we refer to as multiphase probing. With this technique, we basically explore the backscatter channel by reflecting the incident RF signal with different changes in the phase. We define a measure of the backscatter channel, which we call backscatter channel state information (BCSI). The BCSI is composed of backscatter channel phase, backscatter amplitude, and change in baseline excitation level. When acquired over time, this measure provides rich RF analytics that can be used to extract various types of information from the environment of the tags by signal processing/machine learning methods. We show in the paper that this analytics is invariant w.r.t. to some variables including the deployment environment. We provide results from experiments with our tags that demonstrate the invariance of the BCSI.

We envision a future where every object in our living and working environment will carry one or more RF tags. Based on the backscattering tag-to-tag communication link, these RF tags will be connected in a network without the need for the central interrogating device. We present a novel tag architecture that enables estimation of the parameters of wireless tag-to-tag channel by a passive receiver. Sampling the received baseband signal at different reflecting phases at the backscattering tag enables estimation of amplitude and phase of the tag-to-tag channel. The low-power implementation of the channel estimator, after envelope detection, integrates amplification and filtering of the baseband signal that is followed by analog-to-digital conversion. The channel estimator, implemented in 65 nm CMOS technology, has sensitivity of -45 dBm at 2.5% modulation index and consumes 122 nW.

Conventional streaming solutions for streaming 360-degree panoramic videos are inefficient in that they download the entire 360-degree panoramic scene, while the user views only a small sub-part of the scene called the viewport. This can waste over 80% of the network bandwidth. We develop a comprehensive approach called Mosaic that combines a powerful neural network-based viewport prediction with a rate control mechanism that assigns rates to different tiles in the 360-degree frame such that the video quality of experience is optimized subject to a given network capacity. We model the optimization as a multi-choice knapsack problem and solve it using a greedy approach. We also develop an end-to-end testbed using standards-compliant components and provide a comprehensive performance evaluation of Mosaic along with four other streaming techniques - two for conventional adaptive video streaming and two for 360-degree tile-based video streaming. Mosaic outperforms the best of the competition by as much as 50% in terms of median video quality.

Shared spectrum systems is an emerging paradigm to improve spectrum utilization and thus address the unabated increase in mobile data consumption. The paradigm allows the “unused” spectrum bands of licensed Primary Users (PUs) to be shared with Secondary Users (SUs), without causing any harmful interference to the PUs. Allocation of spectrum to the SUs is done based on spectrum availability at the SUs' locations; such allocation of spectrum is greatly facilitated by spectrum occupancy maps. In this work, we address the problem of creating spectrum occupancy maps from spectrum occupancy data over a large number of instants, in the challenging scenario of dynamically (temporally) changing spectrum occupancy due to intermittent transmission of primary users. The problem is particularly challenging when the available occupancy data is very sparse spatially, i.e., only very few locations report sensing data at any particular instant. We design various techniques to create spectrum maps in the above context, including a promising correlation-based merging method that merges observation vectors iteratively in conjunction with careful interpolation. Using extensive simulation over data including real data from cellular and deployed WiFi settings, we show that the correlation-based method is very effective in generating high-accuracy spatiotemporal spectrum maps even with very sparse observation vectors (as long as the number of such vectors is large enough).

A novel framework and related methodologies are described to leverage RF power for building intelligent and battery-free devices with communication and computation capabilities. These passive devices are envisioned to make significant impact for the popular vision of smart dust due to extreme low power operation. The communication framework relies on tag-to-tag backscattering with very limited energy resources. The computing framework relies on a novel AC computing methodology that facilitates local data processing with an order of magnitude less power consumption. These enabling technologies, as described in this paper, revitalize the concept of smart dust with significant impact on various application domains such as smart spaces, implantable devices, and environmental/structural monitoring.

We use a crowdsourcing approach for RF spectrum patrolling, where heterogeneous, low-cost spectrum sensors are deployed widely and are tasked with detecting unauthorized transmissions in a collaborative fashion while consuming only a limited amount of resources. We pose this as a collaborative signal detection problem where the individual sensor's detection performance may vary widely based on their respective hardware or software configurations, but are hard to model using traditional approaches. Still an optimal subset of sensors and their configurations must be chosen to maximize the overall detection performance subject to given resource (cost) limitations. We present the challenges of this problem in crowdsourced settings and present a set of methods to address them. The proposed methods use data-driven approaches to model individual sensors and develops mechanisms for sensor selection and fusion while accounting for their correlated nature. We present performance results using examples of commodity-based spectrum sensors and show significant improvements relative to baseline approaches.

Mobile video traffic is dominant in cellular and enterprise wireless networks. With the advent of myriads of applications from video telephony and streaming to virtual reality, network administrators face the challenge to provide high quality of experience (QoE) in the face of diverse wireless conditions and application contents. Yet, state-of-the-art networks lack analytics for QoE, as this requires support from the application or user feedback. While there are existing techniques to map quality of service (QoS) to QoE by training machine learning (ML) models without requiring user feedback, these techniques are limited to only few applications (e.g., Skype), due to insufficient QoE ground-truth annotation for ML. To address these limitations, we focus on video telephony applications and model key artefacts of spatial and temporal video QoE. Our key contribution is designing content- and device-independent metrics and training across diverse WiFi conditions. We show that our metrics achieve a median 90% accuracy by comparing with mean-opinion-score (MOS) from more than 200 users and 800 video samples. Our content-independent metrics significantly reduce the MOS prediction error of previous works and are validated over three popular video telephony applications - Skype, FaceTime and Google Hangouts.

We present the vision of BARNET (Backscattering Activity Recognition NEtwork of Tags), a network of passive RF tags that use RF backscatter for tag-to-tag communication. BARNET not only provides identification of tagged objects but also can serve as a 'device-free' activity recognition system. BARNET's key innovation is the concept of backscatter channel state information (BCSI) which can be measured via systematic multiphase probing of the backscatter tag-to-tag channel using innovative processing on the passive tags. So far such measurements were only possible using active radio receivers that consume much higher power. Changes in BCSI provide signatures for different activities in the environment that can be learned using suitable machine learning tools. We develop the BARNET tag architecture which shows that an ASIC implementation can run on harvested RF power. We develop a printed circuit board (PCB) prototype using discrete components to evaluate activity recognition performance. We show that the prototype can recognize human daily activities with an average error around 6%. Overall, BARNET uses passive tags to achieve the same level of performance as systems that use powered, active radios.

Radio frequency (RF)-powered backscatter communication between passive tags holds tremendous potential as an enabling technology for a ubiquitous “Internet of Things.” We develop a backscattering tag-to-tag network (BTTN), comprised of passive tags capable of large-scale, passive, and multihop communication with each other via backscatter modulation of an external RF excitation signal. The low sensitivity and lack of active demodulator on passive tags present significant challenges to the communication, including a unique phase cancellation problem, which significantly affects the range and robustness of a passive tag-to-tag link. We overcome these challenges using innovative tag architecture and also develop a novel multiphase backscatter modulation technique with a learning mechanism that overcomes the phase cancellation problem. This improves the link performance bringing passive tag-to-tag communication closer to practical use. The additional hardware compared to the conventional radio frequency identification tag architecture includes one more terminating impedance in the modulator. The data rate is reduced due to backscatter at two different phases while the increase in the power consumption is negligible. We develop prototype BTTN tag hardware and firmware and evaluate its performance. The prototype achieves link ranges of up to 3 m at 5 kb/s with an excitation power level of only -20 dBm while successfully overcoming phase cancellation. We further extend BTTN operation to a multihop network where we demonstrate a four hop link capable of communicating over 12 m under similar conditions.

We describe an end-to-end platform called SpecSense to support large scale spectrum monitoring. SpecSense crowdsources spectrum monitoring to low-cost, low-power commodity SDR/embedded platforms and provides necessary analytics support in a central spectrum server. In this work, we describe SpecSense and address specific challenges related to accurately estimate spectrum occupancy on demand with low overhead. To address the accuracy question, we augment state-of-the-art spatial interpolation techniques to accommodate scenarios where RF propagation characteristics change across space. To address the overhead question, we solve the sensor selection problem to select the minimum number of spectrum sensors that can best estimate the spectrum at the requested locations.

Expected increase in cellular demand has pushed recent interest in picocell networks which have reduced cell sizes (100-200m or less). For ease of deployment of such networks, a wireless backhaul network is highly desired. Since RF-based technologies are unlikely to provide the desired multi-gigabit data rates, we motivate and explore use of free space optics (FSO) for picocell backhaul. In particular, we present a novel network architecture based on steerable links and sufficiently many robust short-range links, to help circumvent the key challenge of outdoor effects in reliable operation of outdoor FSO links. Our architecture is motivated by the fact that, due to the high density of picocells, many short-range links will occur naturally in a picocell backhaul. Moreover, use of steerable FSO links facilitates networks with sufficient redundancy while using only a small number of interfaces per node. We address the key problems that arise in the context of such a backhaul architecture, viz., an FSO link design with desired characteristics, and related network design and management problems. We develop and evaluate a robust 100m FSO link prototype, and simulate the proposed architecture in many metro US cities while show its viability via evaluation of key performance metrics.

Enterprise wireless networks face significant challenges to deliver Quality-of-Experience (QoE) with the variety of mobile applications. One of the fundamental challenges is that the traditional definition of network capacity (often defined as throughput capacity) is not sufficient to reflect applications' requirements in wireless networks. In this paper, we propose to rethink the network capacity of wireless networks to better incorporate QoE. Specifically, we first propose a novel concept of an Experiential Capacity Region (ExCR) for wireless networks. ExCR is defined as a set of simultaneous application flows whose QoE requirements can be satisfied by the network. Next, we present the infrastructure based ExBox system that measures per-application QoE metrics and determines the ExCR for wireless networks to better serve a set of mobile application flows. In its core, ExBox employs light-weight machine learning techniques that are tailored for dynamic wireless environments. Through both large-scale simulations and extensive real-life experiments on WiFi and LTE networks, we show that ExBox delivers QoE in admission control decision with a precision of ≈ 0.8 - 0.9, even when clients experience diverse channel quality. Moreover, ExBox quickly adapts to changing network environments without much overhead.

We argue that spectrum sensing on mobile clients will be both necessary and feasible if we wish to manage the white space spectrum optimally in indoor spaces. We demonstrate the necessity with a set of empirical measurements showing the need for fine grained sensing. We demonstrate the feasibility by building a spectrum sensing infrastructure that collects measurements from sensing devices to analyze and better use spectrum resources. The infrastructure consists of mobile spectrum sensors that are built using DTV receiver dongles interfaced with Android-based mobile devices and a cloud-based central server to manage such sensing devices. We also show results about resource consumption (energy, network overhead) involved in operating such sensors. The vision is ultimately creating a system where mobile devices perform part-time spectrum sensing in a coordinated fashion under the control of a central spectrum manager. We lay out the research challenges based on our initial prototyping and benchmarking experience.

Backscatter-based tag-to-tag communication (BBTT) is a paradigm wherein radio-less devices communicate with each other by using purely passive backscatter modulation. This allows for highly inexpensive and low power devices. Traditional backscattering devices like RFID tags are designed to communicate directly with an active reader leading to a centralized framework centered on the reader. Under a BBTT network, the tags talk to each other using backscattering in the presence of an external excitation signal, which can come from multiple sources (e.g., dedicated exciters, WiFi access points, TV towers, or cell phone towers). The two main components that determine the range and robustness of a passive tag-to-tag link are the power harvesting and demodulation circuit blocks in the analog front end (AFE). In this paper, we investigate the design constraints, optimization goals, and tradeoffs in the design of the AFE for BBTT tags. We first analyze the BBTT link theoretically and then verify the predicted optimal AFE parameters by simulations.

Humans see only a tiny region at the center of their visual field with the highest visual acuity, a behavior known as foveation. Visual acuity reduces drastically towards the visual periphery. 'Foveated' video coding/compression techniques exploit this non-uniformity to gain significant efficiency by compressing more in the periphery and less in the center. We propose a practical and scalable method to use such a technique for video streaming service over the Internet. The essential idea is to use a commodity webcam on the user side to provide real-time gaze feedback to the server with the server sending appropriately coded video to the client player. We develop a multi-resolution video coding approach that is scalable in that it is possible to pre-code the video in a small number of copies for a given set of resolutions. The coding approach is designed to match the error performance of an eye tracker built using commodity webcams. We demonstrate that the technique is energy efficient and thus usable in mobile devices. We develop a methodology for performance evaluation of such a system when network budgets may vary and video quality may fluctuate. Finally, we present a comprehensive user study that demonstrates a bandwidth reduction of a factor of 2 for the same user satisfaction.

We address the problem of network-side localization where cellular operators are interested in localizing cellular devices by means of signal strength measurements alone. While fingerprinting-based approaches have been used recently to address this problem, they require significant amount of geo-tagged (`labeled') measurement data that is expensive for the operator to collect. Our goal is to use semi-supervised and unsupervised machine learning techniques to reduce or eliminate this effort without compromising the accuracy of localization. Our experimental results in a university campus (6 sq. km) demonstrate that sub-100m median localization accuracy is achievable with very little or no labeled data so long as enough training is possible with `unlabeled' measurements. This provides an opportunity for the operator to improve the model with time. We present extensive analysis of the error characteristics to gain insight and improve performance, including understanding spatial properties and developing confidence measures.

In this work, we investigate the problem of localizing RFID tags using a ranging method used in frequency-modulated radars. The idea is to exploit the phase change of the tag response due to frequency changes that normally happen as the RFID reader frequency hops. We demonstrate the general feasibility of this technique in ranging standard RFID tags using commodity readers. We then use it for a localization application - localizing shopping carts in supermarket aisles. We show that the ranging and localization accuracies are very good (median errors 5cm and 10cm respectively) even at distances over 4m making the technique competitive with existing techniques that require more complex set up.

Spectrum databases used to estimate TV white space availability often provide inaccurate and largely conservative estimates as they are primarily based on empirical propagation models. This leads to 'loss' of white space spectrum that is critical in urban areas with large spectrum demand. While alternatives are possible in terms of incorporating direct spectrum measurements, the measurement locations must be judiciously chosen so that measurement effort is not prohibitive. Fundamentally, this boils down to addressing the estimation accuracy vs measurement effort question. We present a rigorous data driven analysis to address this using measurement data collected in parts of New York City metro area. We show that it is possible to develop models that estimate whether the current database estimates are reliable in a given location. Following this, we provide a recipe for developing a `measurement-augmented' spectrum database that takes the help of measurements where needed and falls back on the current propagation model-based database technique in the rest of the areas. The final takeaway is that it is possible to improve database accuracy significantly with only modest amount of measurements.

Recent industry trends suggest a new phenomenon in the mobile market: mobile virtual network operators or MVNOs that operate on top of existing cellular infrastructures. While MVNOs have shown significant growth in the US and elsewhere in the past two years and have been successful in attracting customers, there is anecdotal evidence that users are concerned about cellular performance when choosing MVNOs over traditional cellular operators. In this paper, we present the first systematic measurement study to shed light on this emerging phenomenon. We study the performance of 3 key applications: web access, video streaming and voice, in 2 popular MVNO families (a total of 8 carriers) in the US, where each MVNO family consists of a major base carrier and 3 MVNOs running on top of it. We observe that some MVNOs do indeed exhibit significant performance degradation and that there are key differences between the two MVNO families.

Conventional static datacenter (DC) network designs offer extreme cost vs. performance tradeoffs---simple leaf-spine networks are cost-effective but oversubscribed, while "fat tree"-like solutions offer good worst-case performance but are expensive. Recent results make a promising case for augmenting an oversubscribed network with reconfigurable inter-rack wireless or optical links. Inspired by the promise of reconfigurability, this paper presents FireFly, an inter-rack network solution that pushes DC network design to the extreme on three key fronts: (1) all links are reconfigurable; (2) all links are wireless; and (3) non top-of-rack switches are eliminated altogether. This vision, if realized, can offer significant benefits in terms of increased flexibility, reduced equipment cost, and minimal cabling complexity. In order to achieve this vision, we need to look beyond traditional RF wireless solutions due to their interference footprint which limits range and data rates. Thus, we make the case for using free-space optics (FSO). We demonstrate the viability of this architecture by (a) building a proof-of-concept prototype of a steerable small form factor FSO device using commodity components and (b) developing practical heuristics to address algorithmic and system-level challenges in network design and management.

We explore the vision of an all-wireless inter-rack datacenter fabric. Such a fabric, if realized, can offer operator the ability to dynamically reconfigure the network topology to adapt to future traffic demands while eliminating concerns related to cabling complexity. A key enabler for our vision is the use of free space optical (FSO) technology which, in contrast to traditional wireless/RF technologies, has lower interference footprint, can support longer range, and offers higher bandwidths. While FSO is an enabler, there are several significant practical challenges that need to be addressed before this vision turns into reality. We demonstrate the early promise of addressing these challenges and the potential benefits that this offers in comparison to state-of-the-art datacenter architectures.

In this paper, we envision a scenario where mobile devices perform at least part-time spectrum sensing in a collaborative fashion under the control of a central server. The goal is to create an adequate `radio environment map' for the `white spaces' that will be useful for spectrum management decisions. We lay out the research challenges, describe a prototype implementation using a DTV receiver dongle interfaced with an Android-based mobile device, and present preliminary performance measurements.

The volume of data in broadband cellular network is growing exponentially. However, studies have indicated the traffic load on the cellular base stations varies significantly over time. This gives an opportunity to accommodate additional traffic with the same network capacity if some of the traffic (e.g., p2p, cloud sync) can be amenable to `delayed scheduling' without hurting the user experience any significantly. In this paper, we study various algorithmic problems that can arise in this context. Using a model where all flows can have certain flexibility in scheduling (via use of a `deadline'), we develop optimal or near-optimal algorithms to determine the minimum network capacity for two different models. We also develop various semi-online and online algorithms for online scheduling of flows, and analyze their performance. In particular, even though the online scheduling problem is shown to be intractable, our proposed semi-online algorithm can schedule flows optimally if aided by historical data and slightly additional network capacity over the optimal. Finally, using flow level traffic traces collected at the core of a commercially operated cellular network, we evaluate the effectiveness of our techniques. Evaluations show that delayed scheduling, when done efficiently (using an offline optimal algorithm), can accommodate the same traffic with much lower network capacity (up to 50% less) with only modest delays. While such an optimal solution needs an offline approach, we demonstrate that online scheduling can be almost equally effective when historical traffic data can be exploited for estimation purposes.

We present a tool to estimate the interference between nodes and links in a live wireless network by passive monitoring of wireless traffic. This tool does not require any controlled experiments, injection of probe traffic in the network, or even access to the network nodes. Our approach requires deploying multiple sniffers across the network to capture wireless traffic traces. These traces are then analyzed using a machine learning approach to infer the carrier-sense relationship between network nodes. This coupled with an estimation of collision probabilities helps us to deduce the interference relationships. We also demonstrate an important application of this tool-detection of selfish carrier-sense behavior. This is based on identifying any asymmetry in carrier-sense behavior between node pairs and finding multiple witnesses to raise confidence. We evaluate the effectiveness of the tool for both the applications using extensive experiments and simulation. Experimental and simulation results demonstrate that the proposed approach of estimating interference relations is significantly more accurate than simpler heuristics and quite competitive with active measurements. We also validate the approach in a real Wireless LAN environment. Evaluations using a real testbed as well as ns2 simulation studies demonstrate excellent detection ability of the selfish behavior. On the other hand, the metric of selfishness used to estimate selfish behavior matches closely with actual degree of selfishness observed.

In this paper we develop a new MAC protocol for improving network throughput and hence, channel utilization in wireless LANs that can support very high PHY layer data rates (>; 1Gbps). We call our new MAC protocol Busy Tone Assisted Fine-Grained Channel Access (btFICA). btFICA is based upon the framework of a prominent state-of-the-art PHY/MAC scheme for high data rate WLANs, called Fine-Grained Channel Access (FICA). While the rationale behind the FICA scheme appears effective for enhancing channel utilization in high data rate WLANs, a recent study shows that problems, such as deafness, muteness and a form of hidden terminal problem, can easily arise with the FICA MAC protocol. These problems can degrade the network performance, if left unaddressed. This motivates us to develop our btFICA MAC protocol that uses an additional busy tone antenna. btFICA comprehensively solves all of the three problems faced by the FICA MAC protocol, while maintaining the beneficial aspects of the original FICA scheme. Finally, we show via extensive simulations, that btFICA significantly outperforms the original FICA scheme and 802.11 DCF, in different network topologies and traffic scenarios, in terms of channel utilization, per-user-throughput and fairness.

Recently wireless radios and hardware technologies have been developed that allow operation on very wide channels and that can support very high physical layer data rates (1Gbps and up). However, it is proven that the conventional 802.11 CSMA/CA MAC protocol causes a drastic under-utilization of such high-speed channels. In order to improve channel utilization, a new scheme, called, Fine-Grained Channel Access (FICA), has been recently put forward. While the FICA approach appears more promising than the other proposed schemes for high data rate WLANs, it has not been studied extensively before. Hence, in this paper, we focus on the FICA MAC protocol, and we study this protocol thoroughly in different traffic scenarios and network topologies. We identify, for the first time, some of the serious problems that can arise with the FICA MAC protocol. We call these problems deafness, muteness and a form of hidden terminal problem. We quantify the impact of these problems on the performance of FICA via extensive simulations. Our results show that under some typical scenarios, FICA can perform even worse than the conventional 802.11 DCF, in terms of channel utilization, per-user-throughput or fairness. The insights obtained in this paper motivates the need for addressing FICA's problems and paves the path for future development of better new MAC protocols for high data rate WLANs.

Location-based services (LBSs) are often based on an area or place as opposed to an accurate determination of the precise location. However, current mobile software frameworks are geared towards using specific hardware devices (e.g., GPS or 3G or WiFi interfaces) for as precise localization as possible using that device, often at the cost of a significant energy drain. Further, often the location information is not returned promptly enough. To address this problem, we design a framework for mobile devices, called Geo-fencing. The proposed framework is based on the observation that users move from one place to another and then stay at that place for a while. These places can be, for example, airports, shopping centers, home, offices and so on. Geo-fencing defines such places as geographic areas bounded by polygons. It assumes people simply move from fence to fence and stay inside fences for a while. The framework is coordinated with available communication chips and sensors based on their energy usage and accuracy provided. The essential goal is to determine when users check in or out of fences in an energy effiecient fashion so that appropriate LBS can be triggered. Windows based smartphones are used to prototype Geo-fencing. Validations are conducted with the resulting traces of outdoor and indoor activities of several users for several months. The results show that Geo-fencing provides an effective framework for use with LBSs with a significant energy saving for mobile devices.

We consider the problem of localizing a wireless client in an indoor environment based on the signal strength of its transmitted packets as received on stationary sniffers or access points. Several state-of-the-art indoor localization techniques have the drawback that they rely extensively on a labor-intensive 'training' phase that does not scale well. Use of unmodeled hardware with heterogeneous power levels further reduces the accuracy of these techniques.

We investigate a transport layer protocol design that integrates 3G and WiFi networks, specifically targeting vehicular mobility. The goal is to move load from the expensive 3G network to the less expensive WiFi network without hurting the user experience. As the test platform we choose a nationwide 3G network and a commercially operated metro-scale WiFi network. We exploit the often complementary characteristics of these networks for a hybrid design at the transport layer. To this end, we modify the stock Linux SCTP implementation to support `striping' across multiple interfaces and the ability to handle frequent path failures and recovery in a seamless fashion. Instead of simply striping data over two network connections, we develop a utility and cost-based formulation that decides the right amount of load that can be put on the 3G network to maximize the user's benefit. We develop and experiment with a transport level scheduler to do this. We call the new SCTP design as oSCTP, meaning `SCTP to be used for offloading.' We demonstrate the effectiveness of oSCTP and show that it is able to deliver superior network throughput and user experience, while significantly reducing the load on the 3G network.

We conduct the first detailed measurement analysis of network resource usage and subscriber behavior using a large-scale data set collected inside a nationwide 3G cellular data network. The data set tracks close to a million subscribers over thousands of base stations. We analyze individual subscriber behaviors and observe a significant variation in network usage among subscribers. We characterize subscriber mobility and temporal activity patterns and identify their relation to traffic volume. We then investigate how efficiently radio resources are used by different subscribers as well as by different applications. We also analyze the network traffic from the point of view of the base stations and find significant temporal and spatial variations in different parts of the network, while the aggregated behavior appears predictable. Broadly, our observations deliver important insights into network-wide resource usage. We describe implications in pricing, protocol design and resource and spectrum management.

With the advent of programmability in radios, it is becoming easier for wireless network nodes to cheat to obtain an unfair share of the bandwidth. In this work we study the widely used 802.11 protocol and present a solution to detect selfish carrier-sensing behavior where a node raises the CCA (clear channel assessment) threshold for carrier-sensing, or simply does not sense carrier (possibly randomly to avoid detection). Our approach is based on detecting any asymmetry in carrier-sense behavior between node pairs and finding multiple such witnesses to raise confidence. The approach is completely passive. It requires deploying multiple sniffers across the network to capture wireless traffic traces. These traces are then analyzed by using a machine learning approach to infer carrier-sense relationships between network nodes. Evaluations using a real testbed as well as ns2 simulation studies demonstrate excellent detection ability. The metric of selfishness used to estimate selfish behavior matches closely with actual degree of selfishness observed.

The IEEE 802.11 standard statically channelizes the wide spectrum into smaller channels of equal width, and classically, each access point is assigned one of these channels to operate on. While an intelligent channel assignment for interfering APs can provide better network performance than just any arbitrary channel assignment, still recent work shows that even far better performance can be achieved if the fixed 802.11 channels are not used and instead the channel width and central frequency for each AP is adapted, based upon the traffic load at each AP in the network. However, the existing work for dynamic distribution of spectrum amongst APs, provides non-overlapping channels to interfering APs, which can cause loss of spectral reuse opportunities. In this paper, we propose a new dynamic spectrum distribution technique in infrastructured wireless LANs, that exploits spectrum reuse opportunities and allows overlap between channels provided to interfering APs. Our technique achieves two goals: 1) max-min fairness amongst flows in the network and 2) high network throughput. Finally, we evaluate the performance of our technique, via simulations, and present its superiority when compared to single-channel 802.11-like DCF, classic fixed channelization and the state-of-the-art dynamic spectrum distribution technique for WLANs.

We perform a head-to-head comparison of the performance characteristics of a 3G network operated by a nation-wide provider and a metro-scale WiFi network operated by a commercial ISP, from the perspective of vehicular network access. Our experience shows that over a wide geographic region and under vehicular mobility, these networks exhibit very different throughput and coverage characteristics. WiFi has frequent disconnections even in a commercially operated, metro-scale deployment; but when connected, indeed delivers high throughputs even in a mobile scenario. The 3G network offers similar or lower throughputs in general, but provides excellent coverage and less throughput variability. The two network characteristics are often complementary. It is conceivable that these properties can be judiciously exploited for a hybrid network design where 3G data can be offloaded to WiFi for better performance and to reduce 3G network congestion and to lower costs.

Wireless interference is the major cause of degradation of capacity in 802.11 wireless networks. We present an approach to estimate the interference between nodes and links in a live wireless network by passive monitoring of wireless traffic. This does not require any controlled experiments, injection of probe traffic in the network, or even access to the network nodes. Our approach requires deploying multiple sniffers across the network to capture wireless traffic traces. These traces are then analyzed to infer the interference relations between nodes and links. We model the 802.11 MAC as a Hidden Markov Model (HMM), and use a machine learning approach to learn the state transition probabilities in this model using the observed trace. This coupled with an estimation of collision probabilities helps us to deduce the interference relationships. We show the effectiveness of this method against simpler heuristics, and also a profiling-based method that requires active measurements. Experimental results demonstrate that the proposed approach is significantly more accurate than heuristics and quite competitive with active measurements. We also validate the approach in a real WLAN environment.

The demand for capacity in WiFi networks is driving a new look at transmission scheduling-based link layers. One basic issue here is the use of accurate interference models to drive transmission scheduling algorithms. However, experimental work in this space has been limited. In this work, we use commodity WiFi hardware (specifically, 802.11a) for a comprehensive study of interference modeling for transmission scheduling on a mesh network setup. We focus on the well-known physical interference model for its realism. We propose use of the "graded" version of the model where feasibility of a link is probabilistic, as opposed to using the more traditional "thresholded" version, where feasibility is binary. We show experimentally that the graded model is significantly more accurate (80 percentile error 0.2 vs. 0.55 for thresholded model). We develop transmission scheduling experiments using greedy scheduling algorithms for the evacuation model for both interference models. We also develop similar experiments for optimal scheduling performance for the simplified one-shot scheduling. The scheduling experiments demonstrate clearly superior performance for the graded model, often by a factor of 2. We conclude by promoting use of this model for scheduling studies.

With the proliferation of WiFi technology, many WiFi networks are accessible from vehicles on the road making vehicular WiFi access realistic. However, several challenges exist: long latency to establish connection to a WiFi access point (AP), lossy link performance, and frequent disconnections due to mobility. We argue that people drive on familiar routes frequently, and thus the mobility and connectivity related information along their drives can be predicted with good accuracy using historical information – such as GPS tracks with timestamps, RF fingerprints, and link and network-layer addresses of visible APs. We exploit such information to develop new handoff and data transfer strategies. The handoff strategy reduces the connection establishment latency and also uses pre-scripted handoffs triggered by change in vehicle location. The data transfer strategy speeds up download performance by using prefetching on the APs yet to be encountered. Experimental performance evaluation reveals that the predictability of mobility and connectivity is high enough to be useful in such protocols. In our experiments with a vehicular client accessing road-side APs, the handoff strategy improves download performance by roughly a factor of 2 relative to the state-of-the-art. The data transfer strategy further improves this performance by another factor of 2.5.

One of the useful approaches to exploit redundancy in a sensor network is to keep active only a small subset of sensors that are sufficient to cover the region required to be monitored. The set of active sensors should also form a connected communication graph, so that they can autonomously respond to application queries and/or tasks. Such a set of active sensors is known as a connected sensor cover, and the problem of selecting a minimum connected sensor cover has been well studied when the transmission radius and sensing radius of each sensor is fixed. In this article, we address the problem of selecting a minimum energy-cost connected sensor cover, when each sensor node can vary its sensing and transmission radius; larger sensing or transmission radius entails higher energy cost. For the aforesaid problem, we design various centralized and distributed algorithms, and compare their performance through extensive experiments. One of the designed centralized algorithms (called CGA) is shown to perform within an O (log n ) factor of the optimal solution, where n is the size of the network. We have also designed a localized algorithm based on Voronoi diagrams which is empirically shown to perform very close to CGA and, due to its communication-efficiency, results in significantly prolonging the network lifetime. We also extend the aforementioned algorithms to incorporate fault tolerance. In particular, we show how to extend the algorithms to address the minimum energy-cost connected sensor k -cover problem, in which every point in the query region needs to be covered by at least k distinct active sensors. The CGA preserves the approximation bound in this case. We also propose a localized topology control scheme to preserve k -connectivity, and use it to extend the Voronoi-based approach to computing a minimum energy-cost k 1 -connected k 2 -cover. We study the performance of our proposed algorithms through extensive simulations.

We use a steerable beam directional antenna mounted on a moving vehicle to localize roadside WiFi access points (APs), located outdoors or inside buildings. Localizing APs is an important step towards understanding the topologies and network characteristics of large scale WiFi networks that are deployed in a chaotic fashion in urban areas. The idea is to estimate the angle of arrival of frames transmitted from the AP using signal strength information on different directional beams of the antenna - as the beam continuously rotates while the vehicle is moving. This information together with the GPS locations of the vehicle are used in a triangulation approach to localize the APs. We show how this method must be extended using a clustering approach to account for multi-path reflections in cluttered environments. Our technique is completely passive requiring minimum effort beyond driving the vehicle around in the neighborhood where the APs need to be localized, and is able to improve the localization accuracy by an order of magnitude compared with trilateration approaches using omnidirectional antennas, and by a factor of two relative to other known techniques using directional antennas.

In this work, we address the issue of unrealistic simulations of wireless networks using a measurement-based approach. The idea is to use empirical modeling using measurement data as a mechanism to model physical layer behavior. We demonstrate the power of this approach for 802.11-based networks using ns2, a packet-level network simulator. Specifically, we develop two versions of the ns2 simulator that model the wireless physical layer with different levels of fidelity. In both versions, the deferral and reception model are built using measurements. For propagation modeling, one version uses direct measurements and the other uses an empirically derived model. In validation experiments with a 12-node mesh testbed, both these versions were found to be reasonably accurate (85 percentile errors within about 10% of the capacity) relative to regular simulations (85 percentile errors within 50% of capacity).

Accurate interference models are important for use in transmission scheduling algorithms in wireless networks. In this work, we perform extensive modeling and experimentation on two 20-node TelosB motes testbeds – one indoor and the other outdoor – to compare a suite of interference models for their modeling accuracies. We first empirically build and validate the physical interference model via a packet reception rate vs. SINR relationship using a measurement driven method. We then similarly instantiate other simpler models, such as hop-based, range-based, protocol model, etc. The modeling accuracies are then evaluated on the two testbeds using transmission scheduling experiments. We observe that while the physical interference model is the most accurate, it is still far from perfect, providing a 90-percentile error about 20-25 % (and 80 percentile error 7-12%), depending on the scenario. The accuracy of the other models is worse and scenario-specific. The second best model trails the physical model by roughly 12-18 percentile points for similar accuracy targets. Somewhat similar throughput performance differential between models is also observed when used with greedy scheduling algorithms. Carrying on further, we look closely into the the two incarnations of the physical model – ‘thresholded ’ (conservative, but typically considered in literature) and ‘graded ’ (more realistic). We show via solving the one shot scheduling problem, that the graded version can improve ‘expected throughput ’ over the thresholded version by scheduling imperfect links. Categories and Subject Descriptors C.2.1 [Network architecture and design]: Wireless communication;

In this paper, we consider multihop wireless mesh networks, where each router node is equipped with multiple radio interfaces, and multiple channels are available for communication. We address the problem of assigning channels to communication links in the network with the objective of minimizing the overall network interference. Since the number of radios on any node can be less than the number of available channels, the channel assignment must obey the constraint that the number of different channels assigned to the links incident on any node is at most the number of radio interfaces on that node. The above optimization problem is known to be NP-hard. We design centralized and distributed algorithms for the above channel assignment problem. To evaluate the quality of the solutions obtained by our algorithms, we develop a semidefinite program and a linear program formulation of our optimization problem to obtain lower bounds on overall network interference. Empirical evaluations on randomly generated network graphs show that our algorithms perform close to the above established lower bounds, with the difference diminishing rapidly with increase in number of radios. Also, ns-2 simulations, as well as experimental studies on testbed, demonstrate the performance potential of our channel assignment algorithms in 802.11-based multiradio mesh networks.

Data caching can significantly improve the efficiency of information access in a wireless ad hoc network by reducing the access latency and bandwidth usage. However, designing efficient distributed caching algorithms is nontrivial when network nodes have limited memory. In this article, we consider the cache placement problem of minimizing total data access cost in ad hoc networks with multiple data items and nodes with limited memory capacity. The above optimization problem is known to be NP-hard. Defining benefit as the reduction in total access cost, we present a polynomial-time centralized approximation algorithm that provably delivers a solution whose benefit is at least 1/4 (1/2 for uniform-size data items) of the optimal benefit. The approximation algorithm is amenable to localized distributed implementation, which is shown via simulations to perform close to the approximation algorithm. Our distributed algorithm naturally extends to networks with mobile nodes. We simulate our distributed algorithm using a network simulator (ns2) and demonstrate that it significantly outperforms another existing caching technique (by Yin and Cao [33]) in all important performance metrics. The performance differential is particularly large in more challenging scenarios such as higher access frequency and smaller memory.

In this article, we design techniques that exploit data correlations in sensor data to minimize communication costs (and hence, energy costs) incurred during data gathering in a sensor network. Our proposed approach is to select a small subset of sensor nodes that may be sufficient to reconstruct data for the entire sensor network. Then, during data gathering only the selected sensors need to be involved in communication. The selected set of sensors must also be connected, since they need to relay data to the data-gathering node. We define the problem of selecting such a set of sensors as the connected correlation-dominating set problem, and formulate it in terms of an appropriately defined correlation structure that captures general data correlations in a sensor network. We develop a set of energy-efficient distributed algorithms and competitive centralized heuristics to select a connected correlation-dominating set of small size. The designed distributed algorithms can be implemented in an asynchronous communication model, and can tolerate message losses. We also design an exponential (but nonexhaustive) centralized approximation algorithm that returns a solution within O (log n ) of the optimal size. Based on the approximation algorithm, we design a class of centralized heuristics that are empirically shown to return near-optimal solutions. Simulation results over randomly generated sensor networks with both artificially and naturally generated data sets demonstrate the efficiency of the designed algorithms and the viability of our technique—even in dynamic conditions.

Radio frequency identification (RFID) is a technology where a reader device can "sense" the presence of a close-by object by reading a tag device attached to the object. To improve coverage, multiple RFID readers can be deployed in the given region. In this paper, we consider the problem of slotted scheduled access of RFID tags in a multiple reader environment. In particular, we develop centralized algorithms in a slotted time model to read all the tags using near-optimal number of time slots. We consider two scenarios -one wherein the tag distribution in the physical space is unknown, and the other where tag distribution is known or can be estimated a priori. For each of these scenarios, we consider two cases depending on whether a single channel or multiple channels are available. All the above version of the problem are NP-hard. We design approximation algorithms for the single channel and heuristic algorithms for the multiple channel cases. Through extensive simulations, we show that for the single channel case, our heuristics perform close to the approximation algorithms. In general, our simulations show that our algorithms significantly outperform colorwave, an existing algorithm for similar problems.

We study the problem of supporting VoIP calls in a wireless mesh network. Specifically, we propose solutions for call admission control (CAC) and route selection for VoIP calls. Call admission decisions must evaluate how the capacity of the mesh network is utilized by the existing calls. We address this issue via a measurement-based modeling effort to model mutual interference between wireless links. The modeling approach evaluates whether capacity constraints (or, required QoS metrics) will be satisfied if a new call is admitted with a given route. Evaluations with a 6-node 802.11a testbed demonstrate excellent accuracy of the model and thus also the CAC performance. We address the issue of route selection by also using a modeling approach that considers models of transmission and interference ranges to develop a polynomial-time algorithm to search for feasible routes. This problem takes exponential time for wireless networks without such modeling. In addition to studying feasibility, we study several routing metrics such as shortest feasible path and maximum residual feasible path. Finally, we develop a new method for routing using call statistics that uses prior calling patterns to avoid potentially critical links. We evaluate the performance of these route selection techniques via extensive simulations and demonstrate the superiority of using max residual feasible path over simply shortest feasible path, and routing using call statistics over max residual feasible path.

We propose a novel algorithm for detecting worm-hole attacks in wireless multi-hop networks. The algorithm uses only connectivity information to look for forbidden substructures in the connectivity graph. The proposed approach is completely localized and, unlike many techniques proposed in literature, does not use any special hardware artifact or location information, making the technique universally applicable. The algorithm is independent of wireless communication models. However, knowledge of the model and node distribution helps estimate a parameter used in the algorithm. We present simulation results for three different communication models and two different node distributions, and show that the algorithm is able to detect wormhole attacks with a 100% detection and 0% false alarm probabilities whenever the network is connected with high probability. Even for very low density networks where chances of disconnection is very high, the detection probability remains very high.

We present a practical, measurement-based model that captures the effect of interference in 802.11-based wireless LAN or mesh networks. The goal is to model capacity of any given link in the presence of any given number of interferers in a deployed network, carrying any specified amount of offered load. Central to our modeling approach is a MAC-layer model for 802.11 that is fed by PHY-layer models for deferral and packet capture behaviors, which in turn are profiled based on measurements. The target network to be evaluated needs only O(N) measurement steps to gather metrics for individual links that seed the models. We provide two solution approaches - one based on direct simulation (slow, but accurate) and the other based on analytical methods (faster, but approximate). We present elaborate validation results for a 12 node 802.11b mesh network using upto 5 interfering transmissions. We demonstrate, using as comparison points three simpler modeling approaches, that the accuracy of our approach is much better, predicting link capacities with errors within 10% of the base channel datarate for about 90% of the cases.

In this work, we investigate the use of directional antennas and beam steering techniques to improve performance of 802.11 links in the context of communication between amoving vehicle and roadside APs. To this end, we develop a framework called MobiSteer that provides practical approaches to perform beam steering. MobiSteer can operate in two modes - cached mode - where it uses prior radiosurvey data collected during "idle" drives, and online mode, where it uses probing. The goal is to select the best AP and beam combination at each point along the drive given the available information, so that the throughput can be maximized. For the cached mode, an optimal algorithm for AP and beam selection is developed that factors in all overheads.

This paper presents first results of experiments in vehicular-to-roadside communication using directional antennas. With directional antennas on one side, the duration of connection to a fixed access point or a road side communication unit can be extended and on the other side the interference caused to others can be reduced. In this work results of experiments with electronical steerable directional antennas mounted on a car communicating with stationary access points are presented. The measurements show the benefit of using directional antennas in different environments typical for vehicular communications. The duration of potential 802.11b connections have been compared using directional and omnidirectional antenna patterns when driving through suburban environment. This comparison is based on passive scanning for access points in order to validate the approach in realistic scenarios. The results clearly prove a substantial potential improvement when using directional antennas.

The goal in this paper is to develop comprehensive protocol support in all layers to provide max-min fairness for multihop flows in a wireless mesh network. Our approach has three parts. First, we estimate the max-min fair rate of all multihop flows in the network using a distributed protocol. This estimation uses the knowledge of the flow contention graph that the network nodes learn by exchanging local information. Second, the nodes enforce this rate by controlling the rate at which a flow is scheduled to the link layer. Third, a back pressure flow control is used to reduce the transmission rate of a flow if it has been exceeding its fair rate. Finally, we argue that the fair rate estimation can at best be approximated in an 802.11 based MAC protocol. Thus, to complement our fair rate estimation and scheduling procedures, we develop a virtual time based MAC protocol. We demonstrate via extensive simulations the benefit of all these approaches for ensuring fairness relative to the base case that uses 802.11 MAC and FIFO scheduling.

Directional antennas in wireless mesh networks can improve spatial reuse. However, using them effectively needs specialized protocol support at the MAC layer, which is always not practical. In this work, we present a topology control approach to effectively using directional antennas with legacy MAC layer protocols such as IEEE 802.11. The idea is to use multiple directional antennas on each node and orient them appropriately to create low interference topologies while maintatining network connectivity. Our approach is based on a well-known approximation algorithm to compute minimum degree spanning trees. We show via empirical studies that this approach can reduce interference significantly without increasing stretch factors to any appreciable extent. Detailed wireless network simulations also show that this approach improves end-to-end throughput of multihop flows relative to using omni-directional antennas. Three or four directional antennas per network node with only moderate beamwidths are sufficient to improve the saturation throughput of multihop flows by a factor of 3-4.

Data caching can significantly improve the efficiency of information access in a wireless ad hoc network by reducing the access latency and bandwidth usage. However, designing efficient distributed caching algorithms is non-trivial when network nodes have limited memory. In this article, we consider the cache placement problem of minimizing total data access cost in ad hoc networks with multiple data items and nodes with limited memory capacity. The above optimization problem is known to be NP-hard. Defining benefit as the reduction in total access cost, we present a polynomial-time centralized approximation algorithm that provably delivers a solution whose benefit is at least one-fourth (one-half for uniform-size data items) of the optimal benefit. The approximation algorithm is amenable to localized distributed implementation, which is shown via simulations to perform close to the approximation algorithm. Our distributed algorithm naturally extends to networks with mobile nodes. We simulate our distributed algorithm using a network simulator (ns2), and demonstrate that it significantly outperforms another existing caching technique (by Yin and Cao [30]) in all important performance metrics. The performance differential is particularly large in more challenging scenarios, such as higher access frequency and smaller memory.

In this paper, we propose two new MAC protocols for multichannel operation in wireless ad hoc and mesh networks. The first protocol, extended receiver directed transmission protocol (xRDT) is based on a previously known multichannel solution called receiver directed transmission (RDT) that uses a notion of quiescent channel. xRDT solves the problems faced by RDT, such as multichannel hidden terminal and deafness, by using an additional busy tone interface and few additional protocol operations. We also develop a novel single interface solution, called local coordination-based multichannel MAC (LCM MAC). LCM MAC performs coordinated channel negotiations and channel switching to provide multichannel support. We demonstrate the effectiveness of these two protocols over two other well-known multichannel protocols - MMAC and DCA - via extensive ns2 simulations

In the recent past, there has been a tremendous increase in the popularity of VoIP services as a result of huge growth in broadband access. The same voice-over-Internet protocol (VoIP) service poses new challenges when deployed over a wireless mesh network, while enabling users to make voice calls using WiFi phones. Packet losses and delay due to interference in a multiple-hop mesh network with limited capacity can significantly degrade the end-to-end VoIP call quality. In this work, we discuss the basic requirements for efficient deployment of VoIP services over a mesh network. We present and evaluate practical optimizing techniques that can enhance the network capacity, maintain the VoIP quality and handle user mobility efficiently. Extensive experiments conducted on a real testbed and ns-2 provide insights into the performance issues and demonstrate the level of improvement that can be obtained by the proposed techniques. Specifically, we find that packet aggregation along with header compression can increase the number of supported VoIP calls in a multihop network by 2-3 times. The proposed fast path switching is highly effective in maintaining the VoIP quality. Our fast handoff scheme achieves almost negligible disruption during calls to roaming clients

Abstract We develop an on‐demand, multipath distance vector routing protocol for mobile ad hoc networks. Specifically, we propose multipath extensions to a well‐studied single path routing protocol known as ad hoc on‐demand distance vector (AODV). The resulting protocol is referred to as ad hoc on‐demand multipath distance vector (AOMDV). The protocol guarantees loop freedom and disjointness of alternate paths. Performance comparison of AOMDV with AODV using ns‐2 simulations shows that AOMDV is able to effectively cope with mobility‐induced route failures. In particular, it reduces the packet loss by up to 40% and achieves a remarkable improvement in the end‐to‐end delay (often more than a factor of two). AOMDV also reduces routing overhead by about 30% by reducing the frequency of route discovery operations. Copyright © 2006 John Wiley & Sons, Ltd.

We consider the channel assignment problem in a multi-radio wireless mesh network that involves assigning channels to radio interfaces for achieving efficient channel utilization. We propose the notion of a traffic-independent base channel assignment to ease coordination and enable dynamic, efficient and flexible channel assignment. We present a novel formulation of the base channel assignment as a topology control problem, and show that the resulting optimization problem is NP-complete. We then develop a new greedy heuristic channel assignment algorithm (termed CLICA) for finding connected, low interference topologies by utilizing multiple channels. Our extensive simulation studies show that the proposed CLICA algorithm can provide large reduction in interference (even with a small number of radios per node), which in turn leads to significant gains in both link layer and multihop performance in 802.11-based multi-radio mesh networks.

In this paper, we design techniques that exploit data correlations in sensor data to minimize communication costs (and hence, energy costs) incurred during data gathering in a sensor network. Our proposed approach is to select a small subset of sensor nodes that may be sufficient to reconstruct data for the entire sensor network. Then, during data gathering only the selected sensors need to be involved in communication. The selected set of sensors must also be connected, since they need to relay data to the data-gathering node. We define the problem of selecting such a set of sensors as the connected correlation-dominating set problem, and formulate it in terms of an appropriately defined correlation structure that captures general data correlations in a sensor network.We develop a set of energy-efficient distributed algorithms and competitive centralized heuristics to select a connected correlation-dominating set of small size. The designed distributed algorithms can be implemented in an asynchronous communication model, and can tolerate message losses. We also design an exponential (but non-exhaustive) centralized approximation algorithm that returns a solution within O(log n) of the optimal size. Based on the approximation algorithm, we design a class of efficient centralized heuristics that are empirically shown to return near-optimal solutions. Simulation results over randomly generated sensor networks with both artificially and naturally generated data sets demonstrate the efficiency of the designed algorithms and the viability of our technique -- even in dynamic conditions.

Abstract — Sensor networks are often deployed in a redundant fashion. In order to prolong the network lifetime, it is desired to choose only a subset of sensors to keep active and put the rest to sleep. In order to provide fault tolerance, this small subset of active sensors should also provide some degree of redundancy. In this paper, we consider the problem of choosing a minimum subset of sensors such that they maintain a required degree of coverage and also form a connected network with a required degree of fault tolerance. In addition, we consider a more general, variable radii sensor model, wherein every sensor can adjust both its sensing and transmission ranges to minimize overall energy consumption in the network. We call this thevariableradiik1-Connected, k2-Cover problem. To address this problem, we propose a distributed and localized Voronoibased algorithm. The approach extends the relative neighborhood graph (RNG) structure to preserve k-connectivity in a graph, and design a distributed technique to inactivate desirable nodes while preserving k-connectivity of the remaining active nodes. We show through extensive simulations that our proposed techniques result in overall energy savings in random sensor networks over a wide range of experimental parameters. I.

We develop an anycast mechanism at the link layer for wireless ad hoc networks. The goal is to exploit path diversity in the link layer by choosing the best next hop to forward packets when multiple next hop choices are available. Such choices can come from a multipath routing protocol, for example. This technique can reduce transmission retries and packet drop probabilities in the face of channel fading. We develop an anycast extension of the IEEE 802.11 MAC layer based on this idea. We implement the protocol in an experimental proof-of-concept testbed using the Berkeley motes platform and S-MAC protocol stack. We also implement it in the popular ns-2 simulator and experiment with the AOMDV multipath routing protocol and Rician fading channels. We show that anycast performs significantly better than 802.11 in terms of packet delivery, particularly when the path length is large or fading is substantial.

We have designed and evaluated iMesh, an infrastructure-mode 802.11-based mesh network. IEEE 802.11 access points double as routers making the network architecture completely transparent to mobile clients, who view the network as a conventional wireless LAN. Layer-2 handoffs between access points trigger routing activities inside the network, which can be thought of as layer-3 handoffs. We describe the design rationale and a testbed implementation of iMesh. We present results related to the handoff performance. The results demonstrate excellent handoff performance, the overall latency varying between 50-100 ms, depending on different layer-2 techniques, even when a five-hop long route update is needed. Various performance measurements also demonstrate the clear superiority of a flat routing scheme relative to a more traditional, Mobile IP-like scheme to handle layer-3 handoff.

In overdeployed sensor networks, one approach to conserve energy is to keep only a small subset of sensors active at any instant. We consider the problem of selecting a minimum size connected K-cover, which is defined as a set of sensors M such that each point in the sensor network is "covered" by at least K different sensors in M, and the communication graph induced by M is connected. For the above optimization problem, we design a centralized approximation algorithm that delivers a near-optimal (within a factor of O(lg n)) solution, and present a distributed version of the algorithm. We also present a communication-efficient localized distributed algorithm which is empirically shown to perform well.

This paper considers serial fusion as a mechanism for collaborative signal detection. The advantage of this technique is that it can use only the sensor observations that are really necessary for signal detection and thus can be very communication efficient. We develop the signal processing mechanisms for serial fusion based on simple models. We also develop a space-filling curve-based routing mechanism for message routing to implement serial fusion. We demonstrate via simulations that serial fusion with curve-based routing performs better, both in terms of detection errors and message cost, relative to commonly used mechanisms such as parallel fusion with a tree-based aggregation scheme.

One of the useful approaches to exploit redundancy in a sensor network is to actively keep only a small subset of sensors that are sufficient to cover the region required to be monitored. The set of active sensors should also form a connected communication graph, so that they can autonomously respond to application queries and/or tasks. Such a set of active sensors is known as a connected sensor cover, and the problem of selecting a minimum connected sensor cover has been well studied when the transmission radius and sensing radius of each sensor is fixed. In this article, we address the problem of selecting a minimum energy-cost connected sensor cover, when each sensor node can vary its sensing and transmission radius; larger sensing or transmission radius entails higher energy cost. For the above problem, we design various centralized and distributed algorithms, and compare their performance through extensive experiments. One of the designed centralized algorithms (called CGA) is shown to perform within an O(log n) factor of the optimal solution, where n is the size of the network. We have also designed a localized algorithm based on Voronoi diagrams which is empirically shown to perform very close to CGA, and due to its communication-efficiency, results in significantly prolonging the network lifetime.

Abstract A predictive model‐based mobility tracking method, called dead reckoning, is developed for mobile ad hoc networks. It disseminates both location and movement models of mobile nodes in the network so that every node is able to predict or track the movement of every other node with a very low overhead. The basic technique is optimized to use ‘distance effect’, where distant nodes maintain less accurate tracking information to save overheads. The dead reckoning‐based location service mechanism is evaluated against three known location dissemination service protocols: simple, distance routing effect algorithm for mobility (DREAM) and geographic region summary service (GRSS). The evaluation is done with geographic routing as an application. It is observed that dead reckoning significantly outperforms the other protocols in terms of packet delivery fraction. It also maintains low‐control overhead. Its packet delivery performance is only marginally impacted by increasing speed or noise in the mobility model, that affects its predictive ability. Copyright © 2004 John Wiley & Sons, Ltd.

Spatial query execution is an essential functionality of a sensor network, where a query gathers sensor data within a specific geographic region. Redundancy within a sensor network can be exploited to reduce the communication cost incurred in execution of such queries. Any reduction in communication cost would result in an efficient use of the battery energy, which is very limited in sensors. One approach to reduce the communication cost of a query is to self-organize the network, in response to a query, into a topology that involves only a small subset of the sensors sufficient to process the query. The query is then executed using only the sensors in the constructed topology.In this article, we design and analyze algorithms for such self-organization of a sensor network to reduce energy consumption. In particular, we develop the notion of a connected sensor cover and design a centralized approximation algorithm that constructs a topology involving a near-optimal connected sensor cover. We prove that the size of the constructed topology is within an log n factor of the optimal size, where n is the network size. We also develop a distributed self-organization version of our algorithm, and propose several optimizations to reduce the communication overhead of the algorithm. Finally, we evaluate the distributed algorithm using simulations and show that our approach results in significant communication cost reduction.

Many applications require that sensor observations in a given geographic region be aggregated or fused in a serial fashion. This requires a routing path to be constructed through all sensors in that region. This paper investigates efficient network traversal techniques to construct such path using the novel concept of space-filling curves.

A predictive model-based mobility tracking method, called dead reckoning, is proposed for mobile ad hoc networks. It disseminates both location and movement models of mobile nodes in the network so that every node is able to predict or track the movement of every other node with a very low overhead. This technique is applied to solve the unicast routing problem by modeling link costs using both link lifetime and geographic distance from the destination to the link egress point. This method presents a much superior routing performance compared to either DSR or AODV, two other popular routing protocols, particularly in terms of delivery fraction and routing load.

Most studies on TCP over multi-hop wireless ad hoc networks have only addressed the issue of performance degradation due to temporarily broken routes, which results in TCP inability to distinguish between losses due to link failures or congestion. This problem tends to become more serious as network mobility increases. We tackle the equally important capture problem to which there has been little or no solution, and is present mostly in static and low mobility multihop wireless networks. This is a result of the interplay between the MAC layer and TCP backoff policies, which causes nodes to unfairly capture the wireless shared medium, hence preventing neighboring nodes to access the channel. This has been shown to have major negative effects on TCP performance comparable to the impact of mobility. We propose a novel algorithm, called COPAS (COntention-based PAth Selection), which incorporates two mechanisms to enhance TCP performance by avoiding capture conditions. First, it uses disjoint forward (sender to receiver for TCP data) and reverse (receiver to sender for TCP ACKs) paths in order to minimize the conflicts of TCP data and ACK packets. Second, COPAS employs a dynamic contention-balancing scheme where it continuously monitors and changes forward and reverse paths according to the level of MAC layer contention, hence minimizing the likelihood of capture. Through extensive simulation, COPAS is shown to improve TCP throughput by up to 90% while keeping routing overhead low.

We examine two aspects concerning the influence of unidirectional links on routing performance in multihop wireless networks. In the first part of the paper we evaluate the benefit from utilizing unidirectional links for routing as opposed to using only bidirectional links. Our evaluations are based on three transmit power assignment models that reflect some realistic network scenarios with unidirectional links. Our results indicate that the marginal benefit of using a high-overhead routing protocol to utilize unidirectional links is questionable.Most common routing protocols however simply assume that all network links are bidirectional and thus may need additional protocol actions to remove unidirectional links from route computations. In the second part of the paper we investigate this issue using a well known on-demand routing protocol Ad hoc On-demand Distance Vector (AODV) as a case study. We study the performance of three techniques for AODV for efficient operation in presence of unidirectional links viz. BlackListing Hello and ReversePathSearch. While BlackListing and Hello techniques explicitly eliminate unidirectional links the ReversePathSearch technique exploits the greater network connectivity offered by the existence of multiple paths between nodes. Performance results using ns-2 simulations under varying number of unidirectional links and node speeds show that all three techniques improve performance by avoiding unidirectional links the ReversePathSearch technique being the most effective.

We propose a CSMA-based medium access control protocol for multihop wireless networks that uses multiple channels and a dynamic channel selection method. The proposed protocol uses one control channel and N data channels, where N is independent of the number of nodes in the network. The source uses an exchange of control packets on the control channel to decide on the best channel to send the data packet on. Channel selection is based on maximizing the signal-to-interference plus noise ratio at the receiver. We present performance evaluations obtained from simulations that demonstrate the effectiveness of the proposed protocol.

We develop an empirical technique to determine the capacity of a mobile ad hoc network. We assume that the network runs on-demand routing and carrier sense-based medium access protocols. The technique, however, is general and should apply to other types of protocols. We develop a tool that determines the network capacity given session-level traffic and node mobility traces. We compare the network capacity so determined with the actual network utilization from output statistics generated by a comprehensive simulator. It is observed that network capacity increases with node mobility; but the routing and medium access protocols fail to take advantage of the increased capacity. Even with high loads, a significant portion of the network capacity is not utilized, while the routing performance remains poor. This study indicates that there is a significant scope for designing aggressive routing protocols that utilize the network capacity better to improve routing performance.

We experimentally evaluate the performance of a wireless ad hoc network from the point of view of both the routing and transport layers. The experiments are done on a testbed with desktop PCs and laptops using wireless radio LAN interfaces. For these experiments an on-demand routing protocol called AODV (ad hoc on-demand distance vector) has been implemented as a part of the operating system protocol stack. We describe our design choices and the experimental setup. The performance evaluation reveals that the performance is poor beyond two hops at moderate to high loads.

Ad hoc networks are characterized by multi-hop wireless connectivity, frequently changing network topology and the need for efficient dynamic routing protocols. We compare the performance of two prominent on-demand routing protocols for mobile ad hoc networks - dynamic source routing (DSR) and ad hoc on-demand distance vector routing (AODV). A detailed simulation model with MAC and physical layer models is used to study inter-layer interactions and their performance implications. We demonstrate that even though DSR and AODV share a similar on-demand behavior the differences in the protocol mechanics can lead to significant performance differentials. The performance differentials are analyzed using varying network load, mobility and network size. Based on the observations, we make recommendations about how the performance of either protocol can be improved.

Mobile ad hoc networks are characterized by multi-hop wireless links, absence of any cellular infrastructure, and frequent host mobility. Design of efficient routing protocols in such networks is a challenging issue. A class of routing protocols called on-demand protocols has recently attracted attention because of their low routing overhead. The on-demand protocols depend on query floods to discover routes whenever a new route is needed. Such floods take up a substantial portion of network bandwidth. We focus on a particular on-demand protocol, called dynamic source routing, and show how intelligent use of multipath techniques can reduce the frequency of query floods. We develop an analytic modeling framework to determine the relative frequency of query floods for various techniques. Results show that while multipath routing is significantly better than single path routing, the performance advantage is small beyond a few paths and for long path lengths. It also shows that providing all intermediate nodes in the primary (shortest) route with alternative paths has a significantly better performance than providing only the source with alternate paths.

Mobile ad hoc networks are characterized by multi-hop wireless links, absence of any cellular infrastructure, and frequent host mobility.Design of efficient routing protocols in such networks is a challenging issue.A class of routing protocols called on-demand protocols has recently found attention because of their low routing overhead.We propose a technique that can reduce the routing overhead even further.The on-demand protocols depend on query floods to discover routes whenever a new route is needed.Our technique utilizes prior routing histories to localize the query flood to a limited region of the network.Simulation results demonstrate excellent reduction of routing overheads with this mechanism.This also contributes to a reduced level of network congestion and better end-to-end delay performance of data packets.

We describe a new carrier-sense multiple access (CSMA) protocol for multihop wireless networks, sometimes also called ad hoc networks. The CSMA protocol divides the available bandwidth into several channels and selects an idle channel randomly for packet transmission. It also employs a notion of "soft" channel reservation as it gives preference to the channel that was used for the last successful transmission. We show via simulations that this multichannel CSMA protocol provides a higher throughput compared to its single channel counterpart by reducing the packet loss due to collisions. We also show that the use of channel reservation provides better performance than multichannel CSMA with purely random idle channel selection.

We evaluate several routing protocols for mobile, wireless, ad hoc networks via packet level simulations. The protocol suite includes routing protocols specifically designed for ad hoc routing, as well as more traditional protocols, such as link state and distance vector used for dynamic networks. Performance is evaluated with respect to fraction of packets delivered, end-to-end delay and routing load for a given traffic and mobility model. It is observed that the new generation of on-demand routing protocols use a much lower routing load. However the traditional link state and distance vector protocols provide, in general, better packet delivery and delay performance.

Wireless links are often subject to burst errors leading to consecutive packet losses, which could be buffered and transmitted later, giving priority to packets on stronger links. This improves overall bandwidth utilization. A channel state dependent scheduling protocol based on the above idea is developed and implemented in a wireless LAN. A commercial wireless LAN, Lucent Technology's Wavelan, is used with Pentium based laptops and PCs. The protocol is implemented as a part of the device driver in the Linux operating system. The protocol includes a channel sensing mechanism to help determine when a wireless link comes out of the error state. Experimental performance evaluation with UDP streams and FTP sessions demonstrates the significant performance benefits of channel state dependent scheduling. The performance evaluation includes a novel channel modulation technique based on previously collected traces for reproducibility of experiments.

The performance of the Time Warp mechanism is experimentally evaluated when only a limited amount of memory is available to the parallel computation. An implementation of the cancelback protocol is used for memory management on a shared memory architecture, viz., KSR to evaluate the performance vs. memory tradeoff. The implementation of the cancelback protocol supports canceling back more than one memory object when memory has been exhausted (the precise number is referred to as the salvage parameter) and incorporates a non-work-conserving processor scheduling technique to prevent starvation. Several synthetic and benchmark programs are used that provide interesting stress cases for evaluating the limited memory behavior. The experiments are extensively monitored to determine the extent to which various factors may affect performance. Several observations are made by analyzing the behavior of Time Warp under limited memory: (1) Depending on the available memory and asymmetry in the workload, canceling back several memory objects at one time (i.e. a salvage parameter value of more than one) improves performance significantly, by reducing certain overheads. However, performance is relatively insensitive to the salvage parameter except at extreme values. (2) The speedup vs. memory curve for Time Warp programs has a well-defined knee before which speedup increases very rapidly with memory and beyond which there is little performance gain with increased memory. (3) A performance nearly equivalent to that with large amounts of memory can be achieved with only a modest amount of additional memory beyond that required for sequential execution, if memory management overheads are small compared to the event granularity. These results indicate that contrary to the common belief, memory usage by Time Warp can be controlled within reasonable limits without any significant loss of performance.

It is widely believed that Time Warp is prone to two potential problems: an excessive amount of wasted, rolled back computation resulting from “rollback thrashing” behaviors, and inefficient use of memory, leading to poor performance of virtual memory and/or multiprocessor cache systems. An adaptive mechanism is proposed based on the Cancelback memory management protocol that dynamically controls the amount of memory used in the simulation in order to maximize performance. The proposed mechanism is adaptive in the sense that it monitors the execution of the Time Warp program, automatically adjusts the amount of memory used to reduce Time Warp overheads (fossil collection, Cancelback, the amount of rolled back computation, etc.) to a manageable level. The mechanism is based on a model that characterizes the behavior of Time Warp programs in terms of the flow of memory buffers among different buffer pools. We demonstrate that an implementation of the adaptive mechanism on a Kendall Square Research KSR-1 multiprocessor is effective in automatically maximizing performance while minimizing memory utilization of Time Warp programs, even for dynamically changing simulation models.

The behavior of n interacting processes synchronized by the “Time Warp” rollback mechanism is analyzed under the constraint that the total amount of memory to execute the program is limited. In Time Warp, a protocol called “cancelback” has been proposed to reclaim storage when the system runs out of memory. A discrete state, continuous time Markov chain model for Time Warp augmented with the cancelback protocol is developed for a shared memory system with n homogeneous processors and homogeneous workload. The model allows one to predict speedup as the amount of available memory is varied. To our knowledge, this is the first model to achieve this result. The performance predicted by the model is validated through direct performance measurements on an operational Time Warp system executing on a shared-memory multiprocessor using a workload similar to that in the model. It is observed that Time Warp with only a few additional message buffers per processor over that required in the corresponding sequential execution can achieve approximately the same or even greater performance than Time Warp with unlimited memory, if GVT computation and fossil collection can be efficiently implemented.

A synthesis technique for a class of nonlinear neural networks that subsumes J.J. Hopfield's network with graded response (1984) is presented. The network is synthesized by designing its energy function E such that the function has local minima at the prescribed attractor points. Implementation of the synthesis technique as a nonlinear programming problem is also suggested.>