RFID tags are popular as they are inexpensive and batteryless. These tags are used for tracking and monitoring of objects within a short-range. According to recent studies, such applications can save billions of dollars in shopping malls, airports, and warehouses. However, the existing works failed to decode a large number of RFID tags due to their poor scalability and accuracy. This poor performance is the result of the estimation technique used by the existing solutions.

Dashboard camera installations are becoming increasingly common due to various Advanced Driver Assistance Systems (ADAS) based services provided by them. Though deployed primarily for crash recordings, calibrating these cameras can allow them to measure real-world distances, which can enable a broad spectrum of ADAS applications such as lane-detection, safe driving distance estimation, collision prediction, and collision prevention. Today, dashboard camera calibration is a tedious manual process that requires a trained professional who needs to use a known pattern (e.g., chessboard-like) at a calibrated distance. In this paper, we propose SmartDashCam, a system for automatic and live calibration of dashboard cameras which always ensures highly accurate calibration values. Smart-DashCam leverages collecting images of a large number of vehicles appearing in front of the camera and using their coarse geometric shapes to derive the calibration parameters. In sharp contrast to the manual process we are proposing the use of a large amount of data and machine learning techniques to arrive at calibration accuracies that are comparable to the manual process. SmartDashCam implemented using commodity dashboard cameras estimates real-world distances with mean errors of 5.7% which closely rivals the 4.1% mean error obtained from traditional manual calibration using known patterns.

In recent years, the volume of uplink traffic in our networks has grown and become increasingly diverse. Typically, concurrent uplink transmissions can be made possible by allowing the APs to collaborate over the wired backbone for control signalling as well as data decoding. In our paper, we remove the dependency over the wired backbone for data decoding without requiring any pre-coding constraints at the clients' end. Our paper contrasts with other existing works which can decode concurrent uplink data-streams without the backbone as they either need multiple antennas at the transmitters/receivers, pre-coding at the transmitters or antennas to be physically moved at the receivers. In our paper, we address the problem space of single antenna transmitters and receivers and enable concurrent uplink transmissions by leveraging the recent developments in full-duplex wireless communication. We make each of our APs act as full-duplex relay nodes. Each AP cancels its own client's signal at the other AP, thus enabling themselves to clearly hear their own clients without requiring any pre-coding at the clients' end. We implemented and evaluated our scheme using USRP N210 software defined radios and achieved upto 1.48x throughput gains over TDMA. The throughput improvement over TDMA is upto 1.7x in our system level simulations with our greedy node selection algorithm.

The cost of energy usage is of significant concern in cloud/data center systems that support a large number of servers. A simple way to reduce energy consumption and the electricity bill is to turn some of the servers off during periods of under utilization. However, turning a server back on typically consumes a lot of energy. Another way to reduce the energy cost is to equip cloud systems with renewable resources and batteries. Most works in the literature have focused on one or the other approach. In this work, we propose a joint server on-off and energy control policy, which determines the servers' on-off status, as well as the energy purchasing behavior, by taking electricity price, renewable resources, possible future tasks and turn-on cost into account. The server on-off control component is proved to be optimal in terms of energy consumption minimization. The joint policy is shown to be arbitrarily close to the optimal solution in terms of electricity bill minimization, in the case where the battery has infinite capacity with stable energy level. Simulation results show that even under reasonable battery size, a significant electricity cost reduction is achieved with the proposed policy.

Reliable and timely delivery of periodic V2V (vehicle-to-vehicle) broadcast messages is essential for realizing the benefits of connected vehicles. Existing MAC protocols for ad hoc networks fall short of meeting these requirements. In this paper, we present, CoReCast, the first collision embracing protocol for vehicular networks. CoReCast provides high reliability and low delay by leveraging two unique opportunities: no strict constraint on energy consumption, and availability of GPS clocks to achieve near-perfect time and frequency synchronization.

Emerging smart cities are typically equipped with thousands of outdoor cameras. However, these cameras are usually not calibrated, i.e., information such as their precise mounting height and orientation is not available. Calibrating these cameras allows measurement of real-world distances from the video, thereby enabling a wide range of novel applications such as identifying speeding vehicles and city road planning . Unfortunately, robust camera calibration is a manual process today and is not scalable. In this article, we propose AutoCalib, a system for scalable, automatic calibration of traffic cameras. AutoCalib exploits deep learning to extract selected key-point features from car images in the video and uses a novel filtering and aggregation algorithm to automatically produce a robust estimate of the camera calibration parameters from just hundreds of samples. We have implemented AutoCalib as a service on Azure that takes in a video segment and computes the camera calibration parameters. Using video from real-world traffic cameras, we show that AutoCalib is able to estimate real-world distances with an error of less than 12%.

Inter-vehicular communication (IVC) can be explored to build a live map of vehicles for enhancing collaborative vehicular applications related to traffic statistics, safety by accident prediction and prevention, and energy efficient route planning. For enhancing the abovementioned applications, a live map of vehicles associated with their communication identities (e.g., IP/MAC addresses) of other collaborating vehicles is needed. This is particularly challenging to achieve in the presence of legacy vehicles which may not have any sensing or IVC capabilities. Additionally, vehicles might have diverse sensing capabilities and can have contradicting opinions of surrounding vehicles. We present RoadView, a system that builds the live map of surrounding vehicles by intelligently fusing the local maps created by individual vehicles. RoadView runs on top of existing local vehicular matching systems (LM) such as Foresight [10] or RoadMap [20]. RoadView is the first work that provides a live map of vehicles by leveraging collaboration across vehicles. Our simulations show that for different adoption rates and traffic densities, RoadView can robustly fuse information from a collection of local maps and enhance vehicles to sense 1.8x (average) number of immediate neighboring vehicles compared to state of art LM algorithms.

The energy consumption of cellular networks has increased dramatically due to high demand for wireless communication. Base-stations (BSs) use about 60% to 80% of the energy consumed by these networks. An attractive way to reduce energy consumption is to turn the BSs off during periods of under-utilization. However, turning a BS back on typically consumes a lot of energy, which has not been considered in previous works, but critical to good energy management strategies. In this work, we dynamically determine the on-off schedule of these base-stations by taking both operation-cost and turn-on-cost into account. We develop the first online algorithm that only uses future information to decide the on-off status of each BS and characterize its performance using competitive ratio analysis. We extend it by utilizing history information which helps improve the competitive ratio. A heuristic adaptive online algorithm is then designed to balance the utilization of history and future information. We then show via simulation results that the adaptive algorithm works well under a wide range of traffic intensities.

To meet the growing demand for wireless data, it is time to move away from the age-old paradigm of prohibiting interfering nodes from transmissions. Instead, through proactive management of interference among multiple colliding packets, we can design high throughput wireless systems. This is well explored in the Information Theory community and there are also a few implementational efforts that have been recently reported. The existing solutions are nontrivial to use in real systems as they require either tight time/frequency synchronization or exchange of data between transmitters prior to the transmissions. These requirements are hard to meet in practice especially for uplink transmissions. This paper proposes BASIC, a lightweight multi-user uplink transmission strategy that does not require tight synchronization or exchange of samples among nodes, which makes it an attractive alternative compared to its counterparts. BASIC exploits receiver diversity by controlling the data rates of the clients. A novel greedy algorithm is proposed for data rate selection. We implement BASIC on a software-defined radio platform. Our experiments on a real testbed show that BASIC outperforms TDMA by 48% in terms of overall throughput. Our trace-driven simulations show up to 4.8x gain in throughput with similar flow fairness.

Many interactive applications running in data centers such as web search, social networks, online gaming, and financial services are delay-sensitive, and often have a deadline. These deadlines vary across users and applications, which makes the job scheduling problem very challenging when the overall system performance needs to be optimized. In this paper, the performance of interest is the total utility gain of multiple interactive jobs, and our objective is to maximize the total utility gain. The interactive jobs arrive to the system over time, and are allowed to be partially executed before their deadlines. We focus on the preemptive scenario, where a job in service can be interrupted by other jobs, and its service can be resumed later. We propose a deadline agnostic scheduler, called ISPEED (Interactive Services with Partial Execution and Deadlines). Being deadline agnostic is an attractive property of ISPEED because data center schedulers are often not privy to individual job deadlines, and thus schedulers that are deadline dependent may not be amenable to implementation. We first prove that ISPEED achieves the maximum total utility when jobs have homogeneous deadlines and their utility functions are non-decreasing and concave. Then, in the case of heterogeneous job deadlines we prove that ISPEED achieves a competitive ratio of 2 + α, where α is a shape parameter for a large class of non-decreasing utility functions. In the special case of α = 0, i.e., The utility functions are concave, ISPEED has a competitive ratio of 2, while no causal scheduler can achieve a competitive ratio smaller than ½5+1/2. Finally, we show through trace-driven simulations that ISPEED outperforms the state-of-the-art schedulers in a wide range of scenarios.

The number and size of data centers has seen a rapid growth in the last few years. It is no longer uncommon to see large data centers with thousands or even tens of thousands of machines. Hence, it is critical to develop scalable scheduling mechanisms for processing the enormous number of jobs handled by popular paradigms such as the MapReduce framework. This work explores the possibility of simplifying the scheduling procedure by exploiting the “largeness” of the data center system. Specifically, we consider the problem of minimizing the total flow time of a sequence of jobs under the MapReduce framework, where the jobs arrive over time and need to be processed through both Map and Reduce procedures before leaving the system. We show that any work-conserving scheduler is asymptotically optimal under a wide range of traffic loads, including the heavy traffic limit. Our results are shown for scenarios in which the tasks can be preempted and served in parallel over different machines, as well as scenarios when each task has to be served only on one machine and cannot be preempted. This result implies, somewhat surprisingly, that when we have a large number of machines, there is little to be gained by optimizing beyond ensuring that a scheduler should be work-conserving. For long running applications, we also study the relationship between the number of machines and total running time, and show sufficient conditions to guarantee the asymptotic optimality of work-conserving schedulers. Further, we run extensive simulations, that indeed verify that when the total number of machines is large, state-of-the-art work-conserving schedulers have similar and close-to-optimal delay performance.

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

Sensing white space channels to detect whether a particular channel is free or not is very crucial to the operation of Cognitive Radio Networks (CRNs). Cooperative sensing has been shown to improve the performance of channel sensing. However, cooperative sensing is susceptible to malicious users that may not faithfully follow sensing instructions to save energy and/or time, or to launch denial of service attacks against the network. In this paper, we propose a novel active transmissions based algorithm, FastProbe for detecting malicious users. FastProbe proactively detects malicious users before the CRN causes any interference to the Primary Users. Further, using active transmissions, FastProbe achieves higher detection accuracy while maintaining lower overheads when compared with existing algorithms. Simulations and experiments show that in the presence of malicious nodes operating under 2 different attack models, FastProbe reduces the throughput loss due to sensing by as much as 65% compared to existing algorithms.

Device-to-device (D2D) communications is being pursued as an important feature in next generation cellular networks. D2D can improve resource utilization in two ways: Offloading cellular traffic to D2D, and Reuse of resources used by conventional cellular transmissions for D2D communication. In this paper, we show that in multi-cell environments that employ FFR (Fractional Frequency Reuse), the benefits from D2D toward reuse are limited. We then propose R2D2- a holistic approach to efficient offloading with D2D traffic. R2D2 leverages the flexible nature of D2D traffic (in using downlink/uplink resources) to cater effectively to the spatial and temporal asymmetry in traffic load both across and within cells. R2D2 incorporates a two time-scale solution: a coarse time-scale dynamic FFR scheme that leverages D2D traffic to determine the FFR patterns for downlink and uplink jointly among interfering sectors; and a fine time-scale scheduling solution that intelligently schedules cellular and D2D traffic jointly across DL (Downlink) and UL (Uplink) resources. We establish the hardness of the scheduling problem and present efficient and low complexity algorithms with approximation guarantees. Through extensive evaluations, we confirm that R2D2 delivers the offloading benefits of D2D, with its proposed algorithms performing very close to the optimal.

Storage clouds, such as Amazon S3, are being widely used for web services and Internet applications. It has been observed that the delay for retrieving data from and placing data into the clouds is quite random, and exhibits weak correlations between different read/write requests. This inspires us to investigate a key problem: can we reduce the delay by transmitting data replications in parallel or using powerful erasure codes? In this paper, we study the problem of reducing the delay of downloading data from cloud storage systems by leveraging multiple parallel threads, assuming that the data has been encoded and stored in the clouds using fixed rate forward error correction (FEC) codes with parameters (n, k). That is., each file is divided into k equal-sized chunks, which are then expanded into n chunks such that any k chunks out of the n are sufficient to successfully restore the original file. The model can be depicted as a multiple-server queue with arrivals of data retrieving requests and a server corresponding to a thread. However, this is not a typical queueing model because a server can terminate its operation, depending on when other servers complete their service (due to the redundancy that is spread across the threads). Hence, to the best of our knowledge, the analysis of this queueing model remains quite uncharted. Real traces from Amazon S3 show that the time to retrieve a fixed size chunk is random and can be accurately approximated as an i.i.d. exponentially distributed random variable. We show that any work-conserving scheme is delay-optimal when k = 1. When k > 1, we find that a simple greedy scheme, which allocates all available threads to the head of line request, is delay optimal, which appears surprising.

Using broadcast in vehicular applications such as autonomous cruise control and collaborative driving can disturb unrelated drivers and fail to convey the message due to unspecified receiver, resulting in increased risk of accidents. For supporting the unicast communication primitive, it is important to know the electronic identities (EIDs), e.g., the IP addresses and the relative positions of the nearby vehicles. We show that the estimated GPS coordinates alone are not accurate enough to uniquely identify the intended vehicle. On the other hand, there is an increasing array of devices, such as on-board camera, RADAR, and DSRC radio that are becoming available in newer vehicles. These heterogeneously deployed devices provide information sources that have varying levels of accuracy and potentially different coverage regions, making it challenging to accurately identify the vehicle. As a first step, we design ForeSight, a system that dynamically integrates the information observed in the visual domain (e.g., from camera) and the electronic domain (e.g., WiFi radio) to match the vehicles observed in these two domains with high accuracy. The experiment and simulation results show that ForeSight is able to significantly improve the vehicle identification accuracy compared to using GPS or other algorithms. In our case study, ForeSight reduces disturbing messages by 14 × as compared to the number of a GPS-based communication method.

Data offloading is an increasingly popular mechanism for meeting the rising demands of cellular users. In order to enable the small players, such as businesses and individual owners to make their services available to the bigger wireless service providers (WSPs) to help offload data, a simple, practical and easy-to-use payment machinery needs to be devised. Existing auction mechanisms usually assume that bidders can precisely estimate their true valuations, and they ignore the significant overhead to sellers incurred for obtaining a precise estimation. Such assumption is unrealistic in femtocell networks. To allow imprecise valuations, we introduce the novel concept of perceived valuation, which is a value that can be acquired by the seller at little or no cost. We further propose two novel metrics: partial truthfulness, and imprecision loss, to measure the quality of a truthful auction that accepts perceived valuations. Based on this, we propose EasyBid, a new auction model that provides guarantees for truthfulness even when considering a system with imprecise valuations. Finally, we design a dynamic programming based algorithm which aims to maximize the WSP's utility while satisfying any given constraints on partial truthfulness and imprecision loss. Through simulations, we show that the utility achieved by EasyBid with imprecise valuations can be close to the optimal solution that assumes precise valuations.

Today's Enterprise Wireless LANs are comprised of densely deployed access points. This paper proposes BBN, an interference nulling scheme that leverages the high density of access points to enable multiple mobile devices to transmit simultaneously to multiple access points (APs), all within a single collision domain. BBN also leverages the capability of the APs to communicate with each other on the wired backbone to migrate most of the decoding complexity to the APs, while keeping the design at the mobile clients simple. Finally, we leverage the static nature of the access points to make BBN more practical in networks where the mobility of clients inhibit the use of traditional interference alignment schemes. We implement a prototype of BBN on USRP testbed showing its feasibility. The experiment results show that BBN provides a throughput gain of 1.48X over omniscient TDMA. Results from our trace-driven simulations show that BBN obtains a throughput of up to 5.6X over omniscient TDMA.

Licensed white space channels can now be used opportunistically by unlicensed users, provided the channels are relinquished when needed by the primary users. In order to maximize their potential, these channels need to be assigned to the secondary users in an efficient manner. The protocols to enable such an assignment need to simultaneously aim for fairness, high throughput, low overhead, and low rate of channel reconfigurations. One way of channel assignment is to allow neighboring access points (APs) to operate on the same channel. However, if not done properly, this may increase the number of collisions resulting in lower throughput. In this paper, we present a new channel assignment algorithm that performs controlled channel sharing among neighboring APs that increases not only the fairness but also the total throughput of the APs. Controlled sharing and assignment of channels leads to a new problem that we call as the Shared Coloring Problem. We design a protocol based on a centralized algorithm, called Share, and its localized version, lShare that work together to meet the objectives. The algorithm has tight bounds on fairness and it provides high system throughput. We also show how the 802.22 MAC layer protocol for wireless regional area networks (WRANs) can be modified considering the typical case of low degree of interference resulting from the operations of Share and lShare. Results from extensive ns-3 simulations based on data traces show that our protocol increases the minimum throughput among all APs by at least 58 percent when compared to the baseline algorithms.

With increasing prevalence of mobile wireless devices with WiFi and Bluetooth capability, new applications that can make use of limited contact opportunities when the devices are physically close are emerging. Proximity-based social networking, and location specific dissemination of advertisements and events, are some such applications. Discovering such services is a challenging problem due to energy budget limitations, user mobility, and nonuniformity and the time-varying nature of energy budgets across users. It is important to rapidly discover such mobile services to make use of limited contact opportunities. To support such applications, we seek to design a localized discovery scheme that can minimize the expected contact latency between mobile phones with limited energy budgets. All the existing neighbor discovery schemes assume lack of any time synchronization. However, in practice sufficiently accurate time synchronization can be achieved with existing time synchronization techniques. We propose Recursive Binary Time Partitioning (RBTP), a scheme that determines how the devices should wake up and sleep to achieve minimal contact latency with other nearby devices. RBTP achieves provable performance bound and outperforms state-of-the-art asynchronous protocols for smartphones. When compared with the optimum scheme, the contact latency is shown to be within a factor of (9/8) in the expected case and 2 in the worst case.

In this paper, we investigate the utility maximization problem for a sensor network with energy replenishment. Each sensor node consumes energy in its battery to generate and deliver data to its destination via multihop communications. Although the battery can be replenished from renewable energy sources, the energy allocation should be carefully designed in order to maximize system performance, especially when the replenishment profile is unknown in advance. In this paper, we address the joint problem of energy allocation and routing to maximize the total system utility, without prior knowledge of the replenishment profile. We first characterize optimal throughput of a single node under general replenishment profile and extend our idea to the multihop network case. After characterizing the optimal network utility with an upper bound, we develop a low-complexity online solution that achieves asymptotic optimality. Focusing on long-term system performance, we can greatly simplify computational complexity while maintaining high performance. We also show that our solution can be approximated by a distributed algorithm using standard optimization techniques. In addition, we show that the required battery size is O(ln(1/ξ)) to constrain the performance of our scheme within ξ-neighborhood of the optimum. Through simulations with replenishment profile traces for solar and wind energy, we numerically evaluate our solution, which outperforms a state-of-the-art scheme that is developed based on the Lyapunov optimization technique.

Large-scale Enterprise WLANs are amenable to centralized control and coordination through the wired backbone for improved performance. Distributed scheduling algorithms either fail to achieve high performance in real deployments due to their myopic view of interference characteristics, or take significant time to converge to a globally optimal solution. Thus, they are not reactive to current network conditions. Centralized packet scheduling algorithms do not suffer from the performance limitations of distributed approaches, but are non-trivial to implement. Tight time synchronization requirements make proposed centralized schemes difficult to use in practice. This paper proposes Relative Scheduling: a technique for triggering wireless transmissions through other wireless transmissions in a domino-like fashion, thus making tight time synchronization unnecessary. Through USRP experiments and trace-driven simulations, we show that our approach can achieve up to 1.96× the throughput of Distributed Coordination Function (DCF).

With recent advances in wireless systems, wireless in-band full duplex is proven possible. Prior work primarily allows a full duplex receiver to either send back a packet (bi-directional mode) or to forward another packet to its neighbor (secondary transmission). In our work, we look beyond a node pair and explore how a network can best utilize the full duplex capability. When a full duplex receiver does not have any packets to send back, concurrent transmissions (exposed transmissions) can be initiated. In a distributed channel access protocol, rapid signaling is crucial to identify the best mode for a given pair of transmitter and receiver, and to inform potential exposed terminals of transmission opportunities. In this paper, we present, RCTC, a fast and low overhead signaling mechanism based on Pseudo-random Noise (PN) sequences to enable multi-modal operation of wireless links in a distributed channel access setting to support concurrent transmissions in the neighborhood. Our prototype with USRPs shows up to 78% throughput gain. Extensive simulations over larger networks show a throughput gain of up to 131% for RCTC over the native full duplex scheme and up to 111% over a scheme that enables secondary transmission.

Cognitive radio devices opportunistically operate on whitespace channels, provided those channels are not in use by the primary users. This opportunistic reusing of channels requires secondary users to perform fast and efficient sensing to determine the unused channels. Although individual secondary clients may be unwilling to frequently sense all the channels, their density could be exploited for tasking the individual devices to collaboratively extract useful information on spectrum usage. It is critical to determine how the sensing tasks should be assigned to different secondary users. This is particularly challenging in practical networks due to the variability in the sensing accuracy of different users that may arise because of multipath effects on the signal and varying distances from the primary transmitters. Further, presence of multiple Primary Users on the same channel makes it challenging to select the best users for sensing. Finally, to reduce the sensing overhead, it is beneficial to limit the number of channel sensing tasks that can be performed within a given time period. We propose a novel metric that captures the sensing accuracy of a given sensing assignment. Using our metric, we design an algorithm DISCERN for computing the sensing assignment that maximizes the sensing accuracy. Our algorithm is the first to take into account the limitations in practical networks. Our work is motivated by experimental measurements. Tracedriven simulations show that DISCERN increases the sensing accuracy by at least 30%. Theoretical analysis shows that the sensing assignment computed by DISCERN performs within 63% of the exponential-time optimal solution.

With the rapid increase in size and number of jobs that are being processed in the MapReduce framework, efficiently scheduling jobs under this framework is becoming increasingly important. We consider the problem of minimizing the total flowtime of a sequence of jobs in the MapReduce framework, where the jobs arrive over time and need to be processed through both Map and Reduce procedures before leaving the system. We show that for this problem for non-preemptive tasks, no on-line algorithm can achieve a constant competitive ratio (defined as the ratio between the completion time of the online algorithm to the completion time of the optimal non-causal off-line algorithm). We then construct a slightly weaker metric of performance called the efficiency ratio. An online algorithm is said to achieve an efficiency ratio of γ when the flow-time incurred by that scheduler divided by the minimum flow-time achieved over all possible schedulers is almost surely less than or equal to γ. Under some weak assumptions, we then show a surprising property that, for the flow-time problem, any work-conserving scheduler has a constant efficiency ratio in both preemptive and nonpreemptive scenarios. More importantly, we are able to develop an online scheduler with a very small efficiency ratio (2), and through simulations we show that it outperforms the state-of-the-art schedulers.

In this paper, we propose Symphony, a packet recovery architecture that encourages collisions among transmitters, and utilizes the unused capacity in the backbone to transmit recovered data packets and coordinate the efficient recovery of collided packets. Symphony improves the wireless throughput while incurring a low overhead on the typically under-utilized wired backbone. In Symphony, upon receiving the collided transmissions, the APs carefully suppress a subset of the transmissions. Realizing this idea in practice entails several challenges including identification of clients that have data to transmit and ensuring that the algorithm works despite imperfect time-synchronization and non-zero latency among APs. We present Symphony that addresses these challenges and show how it leverages Successive Interference Cancellation (SIC) to further increase the network throughput. Experiments performed on an USRP testbed shows that on an average, Symphony provides 43% and 187% higher throughput over Omniscient TDMA and IEEE 802.11, respectively. ns-3 based simulation results show that on an average, Symphony provides a throughput of up to 1.63x compared to omniscient TDMA and 5.6x compared to IEEE 802.11.

The smart grid is the new generation of electricity grid that can efficiently utilize new distributed sources of energy (e.g., harvested renewable energy), and allow for dynamic electricity price. In this paper, we investigate the cost minimization problem for an end-user, such as a home, community, or a business, which is equipped with renewable energy devices when electrical appliances allow different levels of delay tolerance. The varying price of electricity presents an opportunity to reduce the electricity bill from an end-user's point of view by leveraging the flexibility to schedule operations of various appliances and HVAC systems. We assume that the end user has an energy storage battery as well as an energy harvesting device so that harvested renewable energy can be stored and later used when the price is high. The energy storage battery can also draw energy from the external grid. The problem we formulate here is to minimize the cost of the energy drawn from the external grid while usage of appliances are subject to individual delay constraints and a long-term average delay constraint. The resulting algorithm requires some future information regarding electricity prices, but it achieves provable performance without requiring future knowledge of either the power demands or the task arrival process. Moreover, we analyze the influence of the assumption that energy can be sold from the battery to the grid. An alternative algorithm is proposed to take advantage of the ability to sell energy. The performance gap between our proposed algorithm and the optimum is shown to diminish as energy selling price approaches the electricity price.

Femtocell-based architectures have the potential to position the cellular service providers to compete head-on with the WiFi market. However, significant interference can happen due to unplanned deployments. Current use of hard partitioning approaches for resource allocation, and lack of guidelines for configuring the femtocells, makes it difficult to obtain significant performance gains over traditional cellular networks. In this paper, we study the dynamic OFDMA subchannel assignment problem while jointly considering power assignment and association control to provide maxmin fairness. Toward this objective, we first consider a noninterfering model (NINT model), which disallows interfering femtocells in the solution. A more general interfering model (INT model) is then considered under which the problem is transformed into the partition coloring problem. We then show the NP-hardness of the problems and design centralized approximation algorithms with provable bounds and distributed solutions. Through extensive simulations in realistic settings we show that, compared to previous work, our solutions under the NINT model can achieve two times the minimum throughput, and under the INT model the minimum throughput can be up to three times the baseline algorithms.

The papers in this special issue focus on quality of service in the network and services management sectors.

In this paper, we investigate the utility maximization problem for a sensor network with energy replenishment. Each sensor node consumes energy in its battery to generate and deliver data to its destination via multi-hop communications. Although the battery can be replenished from renewable energy sources, the energy allocation should be carefully designed in order to maximize system performance, especially when the replenishment profile is unknown in advance. In this paper, we address the joint problem of energy allocation and routing to maximize the total system utility, without prior knowledge of the replenishment profile. We first characterize optimal throughput of a single node under general replenishment profile, and extend our idea to the multi-hop network case. After characterizing the optimal network utility with an upper bound, we develop a low-complexity online solution that achieves asymptotic optimality. Focusing on long-term system performance, we can greatly simplify computational complexity while maintaining high performance. We also show that our solution can be approximated by a distributed algorithm using standard optimization techniques. Through simulations with replenishment profile traces for solar and wind energy, we numerically evaluate our solution, which outperforms a state-of-the-art scheme that is developed based on the Lyapunov optimization technique.

Access to relative location of nearby vehicles on the local roads or on the freeways is useful for providing critical alerts to the drivers, thereby enhancing their driving experience as well as reducing the chances of accidents. The problem of determining the relative location of two vehicles can be broken into two smaller subproblems: (i) Relative lane localization, where a vehicle determines if the other vehicle is in left lane, same lane or right lane with respect to it, and (ii) Relative front-rear localization where it needs to be determined which of the two vehicles is ahead of the other on the road. In this paper, we propose a novel antenna diversity based solution, MARVEL, that solves the two problems of determining the relative location of two vehicles. MARVEL has two components: (i) a smartphone; and (ii) four wireless radios. Unlike exisiting technologies, MARVEL can also determine relative location of vehicles that are not in the immediate neighborhood, thereby providing the driver with more time to react. Further, due to minimal hardware requirements, the deployment cost of MARVEL is low and it can be easily installed on newer as well as existing vehicles. Using results from our real driving tests, we show that MARVEL is able to determine the relative lane location of two vehicles with 96.8% accuracy. Through trace-driven simulations, we also show that by aggregating information across different vehicles, MARVEL is able to increase the localization accuracy to 98%.

Access to relative location of nearby vehicles on the local roads or on the freeways is useful for providing critical alerts to the drivers, thereby enhancing their driving experience as well as reducing the chances of accidents. The problem of determining the relative location of two vehicles can be broken into two smaller subproblems: (i) Relative lane localization, where a vehicle determines if the other vehicle is in left lane, same lane or right lane with respect to it, and (ii) Relative front-rear localization where it needs to be determined which of the two vehicles is ahead of the other on the road. In this demo, we show a novel antenna diversity based solution, MARVEL, that solves the problem of relative lane localization.

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

In this paper, we investigate the problem of maximizing the throughput over a finite-horizon time period for a sensor network with energy replenishment. The finite-horizon problem is important and challenging because it necessitates optimizing metrics over the short term rather than metrics that are averaged over a long period of time. Unlike the infinite-horizon problem, the fact that inefficiencies cannot be made to vanish to infinitesimally small values, means that the finite-horizon problem requires more delicate control. The finite-horizon throughput optimization problem can be formulated as a convex optimization problem, but turns out to be highly complex. The complexity is brought about by the “time coupling property,” which implies that current decisions can influence future performance. To address this problem, we employ a three-step approach. First, we focus on the throughput maximization problem for a single node with renewable energy assuming that the replenishment rate profile for the entire finite-horizon period is known in advance. An energy allocation scheme that is equivalent to computing a shortest path in a simply-connected space is developed and proven to be optimal. We then relax the assumption that the future replenishment profile is known and develop an online algorithm. The online algorithm guarantees a fraction of the optimal throughput. Motivated by these results, we propose a low-complexity heuristic distributed scheme, called NetOnline, in a rechargeable sensor network. We prove that this heuristic scheme is optimal under homogeneous replenishment profiles. Further, in more general settings, we show via simulations that NetOnline significantly outperforms a state-of-the-art infinite-horizon based scheme, and for certain configurations using data collected from a testbed sensor network, it achieves empirical performance close to optimal.

This paper presents a full duplex radio design using signal inversion and adaptive cancellation. Signal inversion uses a simple design based on a balanced/unbalanced (Balun) transformer. This new design, unlike prior work, supports wideband and high power systems. In theory, this new design has no limitation on bandwidth or power. In practice, we find that the signal inversion technique alone can cancel at least 45dB across a 40MHz bandwidth. Further, combining signal inversion cancellation with cancellation in the digital domain can reduce self-interference by up to 73dB for a 10MHz OFDM signal. This paper also presents a full duplex medium access control (MAC) design and evaluates it using a testbed of 5 prototype full duplex nodes. Full duplex reduces packet losses due to hidden terminals by up to 88%. Full duplex also mitigates unfair channel allocation in AP-based networks, increasing fairness from 0.85 to 0.98 while improving downlink throughput by 110% and uplink throughput by 15%. These experimental results show that a re- design of the wireless network stack to exploit full duplex capability can result in significant improvements in network performance.

Renewable energy enables sensor networks with the capability to recharge and provide perpetual data services. Due to low recharging rates and the dynamics of renewable energy such as solar and wind power, providing services without interruptions caused by battery runouts is nontrivial. Most environment monitoring applications require data collection from all nodes at a steady rate. The objective of this paper is to design a solution for fair and high throughput data extraction from all nodes in the presence of renewable energy sources. Specifically, we seek to compute the lexicographically maximum data collection rate and routing paths for each node such that no node will ever run out of energy. We propose a centralized algorithm and two distributed algorithms. The centralized algorithm jointly computes the optimal data collection rate for all nodes along with the flows on each link, the first distributed algorithm computes the optimal rate when the routing structure is a given tree, and the second distributed algorithm, although heuristic, jointly computes a routing structure and a high lexicographic rate assignment that is nearly optimum. We prove the optimality for the centralized and the first distributed algorithm, and use real test-bed experiments and extensive simulations to evaluate both of the distributed algorithms.

Energy harvesting sensor platforms have opened up a new dimension to the design of network protocols. In order to sustain the network operation, the energy consumption rate cannot be higher than the energy harvesting rate, otherwise, sensor nodes will eventually deplete their batteries. In contrast to traditional network resource allocation problems where the resources are static, the time-varying recharging rate presents a new challenge. In this paper, We first explore the performance of an efficient dual decomposition and subgradient method based algorithm, called QuickFix, for computing the data sampling rate and routes. However, fluctuations in recharging can happen at a faster time-scale than the convergence time of the traditional approach. This leads to battery outage and overflow scenarios, that are both undesirable due to missed samples and lost energy harvesting opportunities respectively. To address such dynamics, a local algorithm, called SnapIt, is designed to adapt the sampling rate with the objective of maintaining the battery at a target level. Our evaluations using the TOSSIM simulator show that QuickFix and SnapIt working in tandem can track the instantaneous optimum network utility while maintaining the battery at a target level. When compared with IFRC, a backpressure-based approach, our solution improves the total data rate by 42% on the average while significantly improving the network utility.

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

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

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

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

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

In the context of IEEE 802.11b network testbeds, we examine the differences between unicast and broadcast link properties, and we show the inherent difficulties in precisely estimating unicast link properties via those of broadcast beacons even if we make the length and transmission rate of beacons be the same as those of data packets. To circumvent the difficulties in link estimation, we propose to estimate unicast link properties directly via data traffic itself without using periodic beacons. To this end, we design a data-driven routing protocol Learn-on-the-Fly (LOF). LOF chooses routes based on ETX/ETT-type metrics, but the metrics are estimated via MAC feedback for unicast data transmission instead of broadcast beacons. Using a realistic sensor network traffic trace and an 802.11b testbed of ~195 Stargates, we experimentally compare the performance of LOF with that of beacon-based protocols, represented by the geography-unaware ETX and the geography-based PRD. We find that LOF reduces end-to-end MAC latency by a factor of 3, enhances energy efficiency by a factor up to 2.37, and improves network throughput by a factor up to 7.78, which demonstrate the feasibility and the potential benefits of data-driven link estimation and routing.

Low duty cycle operation is critical to conserve energy in wireless sensor networks. Traditional wake-up scheduling approaches either require periodic synchronization messages or incur high packet delivery latency due to the lack of any synchronization. To simultaneously achieve the seemingly contradictory goals of energy efficiency and low latency, the design of a new low duty-cycle MAC layer protocol called Convergent MAC (CMAC) is presented. CMAC avoids synchronization overhead while supporting low latency. By using zero communication when there is no traffic, CMAC allows sensor nodes to operate at very low duty cycles. When carrying traffic, CMAC first uses anycast to wake up forwarding nodes, and then converges gradually from route-suboptimal anycast with unsynchronized duty cycling to route-optimal unicast with synchronized scheduling. To validate our design and provide a usable module for the research community, CMAC has been implemented in TinyOS and evaluated on the Kansei testbed consisting of 105 XSM nodes. The results show that CMAC at 1% duty cycle significantly outperforms BMAC at 1% in terms of latency, throughput and energy efficiency. The performance of CMAC is also compared with other protocols using simulations, in which the results show for 1% and lower duty cycles, CMAC exhibits similar throughput and latency as CSMA/CA using much less energy, and outperforms SMAC, DMAC and GeRaF in almost all aspects.

In recent years, numerous large-scale Wireless LANs (WLAN) have been deployed all over the world. However, the shortage of non-interfering channels makes it a challenge for WLANs to efficiently support real-time multicast services. We study the problem of efficient scheduling ofreal-timemulticastflows. For mitigating interferences, we allow access-points (APs) to transmit simultaneously only if they are mutually non-interfering and our objective is minimizing the fraction of time used by the APs for servicing the multicast flows. We introduce two multicast strategies, theassociationstrategyfor which each user is restricted to receive flows only from its associated AP and thenon-associationstrategy for which a user may also decode transmissions from other APs in its vicinity. Under both strategies, the scheduling problem of minimizing the multicast service time is NP-hard and we propose simple approximation algorithms with provable performance bounds. Our simulations clearly demonstrate that the proposed algorithms yield efficient multicast scheduling.

Sleep-wake scheduling is an effective mechanism to prolong the lifetime of energy-constrained wireless sensor networks. However, it incurs an additional delay for packet delivery when each node needs to wait for its next-hop relay node to wake up, which could be unacceptable for delay-sensitive applications. Prior work in the literature has proposed to reduce this delay using anycast, where each node opportunistically selects the first neighboring node that wakes up among multiple candidate nodes. In this paper, we study the joint control problem of how to optimally control the sleep-wake schedule, the anycast candidate set of next-hop neighbors, and anycast priorities, to maximize the network lifetime subject to a constraint on the expected end-to-end delay. We provide an efficient solution to this joint control problem. Our numerical results indicate that the proposed solution can substantially outperform prior heuristic solutions in the literature, especially under the practical scenarios where there are obstructions in the coverage area of the wireless sensor network.

In sensor networks, application layer QoS requirements are critical to meet while conserving energy. One of the leading factors for energy wastage is failed transmission attempts due to channel dynamics and interference. Existing techniques are unaware of the channel dynamics and lead to suboptimal channel access patterns. We propose a MAC layer solution called pushback, that appropriately delays packet transmissions to overcome periods of poor channel quality and high interference, while ensuring that the throughput requirement of the node is met. It uses a hidden Markov model (HMM) based channel model that is maintained without any additional signaling overhead. The pushback algorithm is shown to improve the packet success rate by up to 71% and reduce the number of transmissions needed by up to 38% while ensuring the same throughput.

To benefit from data aggregation in large scale sensor networks, an aggregation point, i.e. the place where data are aggregated, must be close to sources. In event triggered sensor networks, this can be achieved by dynamically constructing a tree connecting the sources rooted at a nearby node. However, this incurs high control and maintenance overhead. With static trees, the distance (Delta) between sources and the aggregation point can be as high as O(n) where n is the number of nodes in the network. This diminishes the benefit of data aggregation, thereby limiting the scalability of static trees. In this paper we propose AFT (alternative forwarding tree), a structure with multi-level overlapping clusters. Packet forwarding decisions on AFT are made on the fly when packets are being forwarded and it bounds the distance between the aggregation point and sources by O(delta) irrespective of network size, where delta is the diameter of the event. This guarantees that packets can be aggregated near sources without the overhead of constructing a dynamic structure and therefore is scalable. We prove that in the worst case, AFT guarantees aggregation at a node that is at most 2(1 + radic13)delta away from the sources.

Communication between arbitrary pairs of nodes has become critical to support in emerging sensor networking applications. Traditional routing techniques for multi-hop wireless networks either require high control overhead in computing and maintaining routes, or may lead to unbounded route-stretch. In order to bound the route-stretch, we propose a distributed shortest-path roadmap based routing paradigm that embodies two ideas: routing hole approximation that summaries the critical information about hole boundaries and controlled advertisement that advertises the boundary information of each hole within limited neighborhoods. We show that our approach makes a desired tradeoff between the worst case route-stretch and the message overhead through both analysis and simulations.

Renewable energy enables sensor networks with the capability to recharge and provide perpetual data services. Due to low recharging rates and the dynamics of renewable energy such as solar and wind power, providing services without interruptions caused by battery runouts is non-trivial. Most environment monitoring applications require data collection from all nodes at a steady rate. The objective of this paper is to design a solution for fair and high throughput data extraction from all nodes in presence of renewable energy sources. Specifically, we seek to compute the lexicographically maximum data collection rate for each node, such that no node will ever run out of energy. We propose a centralized algorithm and an asynchronous distributed algorithm that can compute the optimal lexicographic rate assignment for all nodes. The centralized algorithm jointly computes the optimal data collection rate for all nodes along with the flows on each link, while the distributed algorithm computes the optimal rate when the routes are pre-determined. We prove the optimality for both the centralized and the distributed algorithms, and use a testbed with 155 sensor nodes to validate the distributed algorithm.

In wireless sensor networks, the many-to-one data communication pattern induces high collision losses as multiple transmissions cause contention and interference along the paths from sources to the sink. This paper proposes a low-overhead MAC layer solution to address the high contention problem to improve system throughput and reduce energy consumption. Periods of bursty transmissions with reduced contention from neighboring nodes are exploited to efficiently clear up back- logged queues and improve the performance of CSMA. Through analytical modeling we characterize the expected performance improvement and show that it conforms to the simulation results. Using extensive simulations onns-2and experiments on the 49 node sensor network testbed (Kansei) running TinyOS, we evaluate the performance of our solution.

Computing and maintaining network structures for efficient data aggregation incurs high overhead for dynamic events where the set of nodes sensing an event changes with time. Moreover, structured approaches are sensitive to the waiting time that is used by nodes to wait for packets from their children before forwarding the packet to the sink. Although structureless approaches can address these issues, the performance does not scale well with the network size. We propose tree on DAG (ToD), a semistructured approach that uses dynamic forwarding on an implicitly constructed structure composed of multiple shortest path trees to support network scalability. The key principle behind ToD is that adjacent nodes in a graph will have low stretch in one of these trees in ToD, thus resulting in early aggregation of packets. Based on simulations on a 2,000-node network and real experiments on a 105-node Mica2-based network, we conclude that efficient aggregation in large-scale networks can be achieved by our semistructured approach.

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

In-network caching is a useful technique for reducing latency and retransmission overhead of lost packets for reliable data delivery in wireless networks. However, in-network caching is challenging to implement in memory constrained devices such as RFIDs and sensors, and also in Wireless LAN (WLAN) gateways for large-scale deployments. In this paper we propose a novel technique for management of in-network caches using XOR coding for optimizing the use of limited buffer space in presence of random and burst packet losses. We identify two critical parameters, coding degree and coding distance for the coding scheme. As a case-study we implement our approach over Snoop and evaluate its performance for a WLAN. Using simulations in ns-2, we observe that when the size of the retransmission buffer on the gateway is less than 16 packets per TCP flow, the throughput can be enhanced by up to 30% for random losses and up to 20% for burst losses.

Support for efficient multicasting in WLANs can enable new services such as streaming TV channels, radio channels, and visitor's information. With increasing deployments of large-scale WLANs, such services can have a significant impact. However, for a solution to be viable, the mutlicast services must minimally impact the existing unicast services which are currently the core services offered by most WLANs. This paper focuses on three objective functions motivated by different revenue functions and network scenarios: maximizing the number of users (MNU), balancing the load among APs (BLA), and minimizing the load of APs (MLA). We show that these problems are NP-hard and present centralized approximation algorithms and distributed approaches to solve them. Using simulations we evaluate the performance of these algorithms. We observe that the number of users can be increased by up to 36.9%, and the maximum AP load and the total load can be reduced by up to 52.9% and 31.1%, respectively.

In-network data storage techniques can provide robustness against failure of dedicated sink nodes in sensor networks. For storing data in the network it is critical to ensure that the data can be accessed from other nodes for a long period of time. As replicating the data will increase consumption of resources, we propose a technique for data relocation that optimizes the accessibility of the data in the network. The two challenging constraints for solving this problem are "limited sensor lifetime" and "cost of data relocation". We study both centralized and distributed approaches for computing accessibility of each node. Using extensive simulations, we evaluate the performance of our techniques.

Data aggregation protocols can reduce the communication cost, thereby extending the lifetime of sensor networks. Prior works on data aggregation protocols have focused on tree-based or cluster-based structured approaches. Although structured approaches are suited for data gathering applications, they incur high maintenance overhead in dynamic scenarios for event-based applications. The goal of our work is to design techniques and protocols that lead to efficient data aggregation without explicit maintenance of a structure. As packets need to converge spatially and temporally for data aggregation, we propose two corresponding mechanisms–Data-Aware Anycastat the MAC layer andRandomized Waitingat the application layer. We model the performance of the combined protocol that uses both the approaches and show that our analysis matches with the simulations. Using extensive simulations and experiments on a testbed with implementation in TinyOS, we study the performance and potential of structure-free data aggregation.

In third-generation (3G) wireless data networks, providing service to low data-rate users is required for maintaining fairness, but at the cost of reducing the cell's aggregate throughput. In this paper, we propose the unified cellular and ad hoc network (UCAN) architecture for enhancing cell throughput while maintaining fairness. In UCAN, a mobile client has both 3G interface and IEEE 802.11 -based peer-to-peer links. The 3G base station forwards packets for destination clients with poor channel quality to proxy clients with better channel quality. The proxy clients then use an ad hoc network composed of other mobile clients and IEEE 802.11 wireless links to forward the packets to the appropriate destinations, thereby improving cell throughput. We refine the 3G base station scheduling algorithm so that the throughput gains are distributed in proportion to users' average channel rates, thereby maintaining fairness. With the UCAN architecture in place, we propose novel greedy and on-demand protocols for proxy discovery and ad hoc routing that explicitly leverage the existence of the 3G infrastructure to reduce complexity and improve reliability. We further propose secure crediting mechanisms to motivate users that are not actively receiving to participate in relaying packets for others. Through both analysis and extensive simulations with HDR and IEEE 802.11b, we show that the UCAN architecture can increase individual user's throughput by more than 100 percent and the aggregate throughput of the HDR downlink by up to 50 percent.

We present Sprinkler, a reliable data dissemination service for wireless embedded devices which are constrained in energy, processing speed, and memory. Sprinkler embeds a virtual grid over the network whereby it can locally compute a connected dominating set of the devices to avoid redundant transmissions and a transmission schedule to avoid collisions. Sprinkler transmits O(1) times the optimum number of packets in O(1) of the optimum latency; its time complexity is O(1). Sprinkler is tolerant to fail-stop and state corruption faults. Thus, Sprinkler is suitable for resource-constrained wireless embedded devices. We evaluate the performance of Sprinkler in terms of the number of packet transmissions and the latency, both in an outdoor and indoor environment. The outdoor evaluation is based on data from project ExScal, which deployed 203 extreme scale stargazer (XSS). Our indoor evaluation is based on an implementation in the Kansei testbed, which houses 210 XSSs whose transmission power is controllable to even low ranges. We compare Sprinkler with the existing reliable data dissemination services, analytically or using simulations also. Our evaluations show that Sprinkler is not only energy efficient as compared to existing schemes, but also has less latency. Further, the energy consumption of nodes and the latency grows linearly as a function of newly added nodes as the network grows larger.

Data aggregation protocols can reduce the cost of communication, thereby extending the lifetime of sensor networks. Prior work on data aggregation protocols has focused on tree-based or cluster-based structured approaches. Although structured approaches are suited for data gathering applications, they incur high maintenance overhead in dynamic scenarios for event-based applications. The goal of our work is to design techniques and protocols that lead to efficient data aggregation without explicit maintenance of a structure. As packets need to converge spatially and temporally for data aggregation, we propose two corresponding mechanisms- Data-Aware Anycast at the MAC layer and Randomized Waiting at the application layer. We model the performance of the combined protocol that uses both the approaches and show that our analysis matches with the simulations. Using extensive simulations and experiments on a testbed with implementation in TinyOS, we study the performance and potential of structure-free data aggregation.

In the context of IEEE 802.11b network testbeds, we examine the differences between unicast and broadcast link properties, and we show the inherent difficulties in precisely estimating unicast link properties via those of broadcast beacons even if we make the length and transmission rate of beacons be the same as those of data packets. To circumvent the difficulties in link estimation, we propose to estimate unicast link properties directly via data traffic itself without using periodic beacons. To this end, we design a data-driven routing protocol Learn on the Fly (LOF). LOF estimates link quality based on data traffic, and it chooses routes by way of a locally measurable metric ELD, the expected MAC latency per unit-distance to the destination. Using a realistic sensor network traffic trace and an 802.11b testbed of 195 Stargates, we experimentally compare the performance of LOF with that of existing protocols, represented by the geography-unaware ETX and the geography-based PRD. We find that LOF reduces endto-end MAC latency by a factor of 3, enhances energy efficiency by a factor up to 2.37, improves route stability by 2 orders of magnitude, and improves network throughput by a factor up to 7.78. The results demonstrate the feasibility as well as potential benefits of data-driven link estimation and routing. Keywords—sensor network, beacon-free geographic routing, data-driven link quality estimation, MAC latency, IEEE 802.11b, real time, energy, reliability

Efficient, scalable and robust multicasting support from the MAC layer is needed for meeting the demands of multicast based applications over WiFi and mesh networks. However, the IEEE 802.11 protocol has no specific mechanism for multicasting. It implements multicasting using broadcasting at the base transmission rate. We identify two fundamental reasons for performance limitations of this approach: (a) Channel-state indifference: irrespective of the current quality of the channel to the receivers, the transmission always uses the base transmission rate; (b) Demand ignorance: packets are transmitted by a node even if children in the multicast tree have received those packets by virtue of overhearing. We propose a solution for MAC layer multicasting called HIMAC that uses the following two mechanisms: unary channel feedback (UCF) and unary negative feedback (UNF) to respectively address the shortcomings of 802.11. Our study is supported by measurements in a testbed, and simulations. We observe that the end-to-end throughput of multicast sessions using MAODV can be increased by up to 74% while reducing the end-to-end latency by up to a factor of 56

Computing and maintaining network structures for efficient data aggregation incurs high overhead for dynamic events where the set of nodes sensing an event changes with time. Moreover, structured approaches are sensitive to the waiting-time which is used by nodes to wait for packets from their children before forwarding the packet to the sink. Although structureless approaches can address these issues, the performance does not scale well with the network size. We propose a semi-structured approach that uses a structureless technique locally followed by Dynamic Forwarding on an implicitly constructed packet forwarding structure to support network scalability. The structure, ToD, is composed of multiple shortest path trees. After performing local aggregation, nodes dynamically decide the forwarding tree based on the location of the sources. The key principle behind ToD is that adjacent nodes in a graph will have low stretch in one of these trees in ToD, thus resulting in early aggregation of packets. Based on simulations on a 2000 nodes network and real experiments on a 105 nodes Mica2-based network, we conclude that efficient aggregation in large scale networks can be achieved by our semi-structured approach.

We identify two typical problems in WLAN hotspots that result in unbounded unfairness between upstream and downstream flows. The first unfairness problem arises due to the uniformity of the MAC layer protocol at the access point (AP) and user nodes that result in equal share to the AP and the user nodes but not to the individual flows. The second unfairness problem arises due to the inability of the physical layer to distinguish frame errors due to hidden terminal based collisions and frame errors due to poor signal strength. We present FairMAC, a deployable solution that addresses these unfairness problems without requiring a change to the 802.11 protocol. Thus, our solution is immediately deployable in the millions of currently operational hotspots. We evaluate the performance of our protocol using simulations and a prototype implementation. We show that FairMAC provides fair access to all the flows regardless whether they are originating at the AP or a host.

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

We present Sprinkler, a reliable data dissemination service for wireless embedded devices which are constrained in energy, processing speed, and memory. Sprinkler embeds a virtual grid over the network whereby it can locally compute a connected dominating set of the devices to avoid redundant transmissions, and a transmission schedule to avoid collisions. Sprinkler transmits O(1) times the optimum number of packets in O(1) of the optimum latency; its time complexity is O(1). Thus, Sprinkler is suitable for resource-constrained wireless embedded devices. We evaluate the performance of Sprinkler in terms of the number of packet transmissions and the latency, both in an outdoor and an indoor environment. Our indoor evaluation is based on an implementation in the Kansei testbed that houses 210 XSSs whose transmission power is controllable to even low ranges. We compare Sprinkler with the existing reliable data dissemination services, analytically or using simulations also. Our evaluations show that Sprinkler is not only energy efficient as compared to existing schemes but also have less latency. Further, the energy consumption of nodes and the latency grows linearly as a function of newly added nodes as network grows larger

We focus on self-contention: contention between packets of the same transport layer connection along the path from source to destination. We observe that self-contention plays an important role in degrading TCP performance in multi-hop wireless networks and that the use of the popular IEEE 802.11 MAC protocol exacerbates self-contention. We propose and study two MAC-layer approaches to alleviate self-contention. The first approach, called quick-exchange (QE), is designed with the intent of reducing the effects of inter-flow self-contention (e.g. between packets of the same connection traveling in opposite directions). The design of our second mechanism, called fast-forward (FF), is geared towards decreasing intra-flow self-contention (e.g. between packets of the same connection traveling in the same direction). We simulate and study our proposed schemes and observe that quick-exchange consistently improves net-work aggregate goodput (by as much as 20% in string topologies, 15% in random static scenarios, and 10% in random mobile scenarios). In contrast to our expectations, fast-forward causes sporadic and often negative effects on goodput for TCP connections. Upon investigation we find that while the MAC is, in some respect, operating more efficiently, as demonstrated by improved UDP throughput; interactions with TCPs congestion control mechanism cause the goodput to degrade. We analyze various effects that cause the respective behaviors with QE and FF in detail.

As local area wireless networks based on the IEEE 802.11 standard see increasing public deployment, it is important to ensure that access to the network by different users remains fair. While fairness issues in 802.11 networks have been studied before, this paper is the first to focus on TCP fairness in 802.11 networks in the presence of both mobile senders and receivers. In this paper, we evaluate extensively through analysis, simulation, and experimentation the interaction between the 802.11 MAC protocol and TCP. We identify four different regions of TCP unfairness that depend on the buffer availability at the base station, with some regions exhibiting significant unfairness of over 10 in terms of throughput ratio between upstream and downstream TCP flows. We also propose a simple solution that can be implemented at the base station above the MAC layer that ensures that different TCP flows share the 802.11 bandwidth equitably irrespective of the buffer availability at the base station.

In third-generation (3G) wireless data networks, mobile users experiencing poor channel quality usually have low data-rate connections with the base-station. Providing service to low data-rate users is required for maintaining fairness, but at the cost of reducing the cell's aggregate throughput. In this paper, we propose the Unified Cellular and Ad-Hoc Network (UCAN) architecture for enhancing cell throughput, while maintaining fairness. In UCAN, a mobile client has both 3G cellular link and IEEE 802.11-based peer-to-peer links. The 3G base station forwards packets for destination clients with poor channel quality to proxy clients with better channel quality. The proxy clients then use an ad-hoc network composed of other mobile clients and IEEE 802.11 wireless links to forward the packets to the appropriate destinations, thereby improving cell throughput. We refine the 3G base station scheduling algorithm so that the throughput gains of active clients are distributed proportional to their average channel rate, thereby maintaining fairness. With the UCAN architecture in place, we propose novel greedy and on-demand protocols for proxy discovery and ad-hoc routing that explicitly leverage the existence of the 3G infrastructure to reduce complexity and improve reliability. We further propose a secure crediting mechanism to motivate users to participate in relaying packets for others. Through extensive simulations with HDR and IEEE 802.11b, we show that the UCAN architecture can improve individual user's throughput by up to 310% and the aggregate throughput of the HDR downlink by up to 60%.

Several routing algorithms for mobile ad hoc networks (MANETs) have been proposed previously. With the exception of a few, these protocols (i) involve all nodes in the route management process, (ii) rely on the use of broadcast relays for route computation, and (iii) are primarily reactive in nature. Related work has shown that the capacity utilization in ad hoc networks decreases significantly when broadcast relays or "broadcast storms" are performed frequently. This effect is compounded when all nodes in the network take part in the route computation. We propose and study an approach based on overlaying a virtual infrastructure adaptation of the core, proposed by Sivakumar, Sinha and Bharghavan (see IEEE Journal on Selected Areas in Communications, vol.17, no.8, p.1454-65, 1999) on an ad hoc network and operating routing protocols over the infrastructure. The core enables routing protocols to use only a subset of nodes in the network for route management and avoid the use of broadcast relays. Using the ns-2 simulator we evaluate the performance of two ad hoc routing protocols, dynamic source routing (DSR) and ad hoc on demand distance vector (AODV), when they are operated over the core and compare their performance against those of their basic versions.

Ad-hoc networks consist of peer-to-peer communicating nodes that are highly mobile. As such, an ad-hoc network lacks infrastructure and the topology of the network changes dynamically. The task of routing data from a source to a destination in such a network is challenging. Several routing protocols have been proposed for wireless ad-hoc networks. Most of these protocols, however, pre-suppose the presence of bi-directional links between the nodes in the network. In reality the ad-hoc network may consist of heterogeneous nodes with different power capabilities and hence, different transmission ranges. When this is the case, a given node might be able to receive the transmission of another given node but might not be able to successfully transmit to the latter. Thus, unidirectional links are formed. Most of the current routing protocols are unsuitable for deployment when such unidirectional links are present. We consider a routing protocol called the zone routing protocol (ZRP) that has been proposed for wireless ad-hoc networks with bi-directional links. The zone routing protocol employs a hybrid proactive (table driven) and reactive (on-demand) methodology to provide scalable routing in the ad-hoc network. However, in the presence of unidirectional links some routes remain undiscovered if ZRP is used. We propose extensions to ZRP to support its deployment when unidirectional links are present. In particular, we propose a query enhancement mechanism that recursively builds partial routes to a destination. Simulation results show that even at a high mobility of 20 m/s, the queries resulting due to the enhancement mechanism result in the computation of valid routes more than 80% of the time. These results are valid even when a large number (40% of nodes have half the transmission range as that of the remaining nodes) of unidirectional links are present in the network.

CEDAR is an algorithm for QoS routing in ad hoc network environments. It has three key components: (a) the establishment and maintenance of a self-organizing routing infrastructure called the core for performing route computations, (b) the propagation of the link-state of stable high-bandwidth links in the core through increase/decrease waves, and (c) a QoS route computation algorithm that is executed at the core nodes using only locally available state. But preliminary performance evaluation shows that CEDAR is a robust and adaptive QoS routing algorithm that reacts effectively to the dynamics of the network while still approximating link-state performance for stable networks.

Most current wireless wide area packet data networks (WWANs) are characterized by low and variable bandwidths, high and variable delays, significant non-congestion related loss, asymmetric uplink and downlink channels, and occasional blackouts.Additionally, the majority of the latency in a WWAN connection is incurred over the wireless link.Under such operating conditions, most contemporary wireless TCP algorithms do not perform very well.In this paper, we present WTCP, a reliable transport protocol that is designed to operate efficiently over commercial WWAN networks such as CDPD.WTCP is rate-based, uses only end-to-end mechanisms, performs rate control at the receiver, and uses the ratio of sending rate to receiving rate as the primary metric for rate control.We have implemented and evaluated WTCP over the CDPD network, and also simulated it in the ns-2 simulator.Our initial results indicate the WTCP can improve on the performance of comparable algorithms such as TCP-NewReno, TCP-Vegas, and Snoop-TCP by between 20% to 200% for typical operating conditions.'Most of the current deployment uses the proxy model for three reasons: (a) the connection quality of the WWAN network is too poor to sustain typical client-server applications, (b) the amount of data transfered to the mobile host must be filtered because of the orders of magnitude difference in bandwidth between the wired and WWAN connections, and (c) many portable computing devices have display and processing limitations that must be addressed by the proxy before sending the processed/filtered response to the mobile user.Permission to make digital or hard copies of all or part of this work tw personal or classroom use is gxnted without fee provided that coPi= are oat ma& or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first Page.To COPY othenvise, to rqublish, to post on servers or to redistribute to lists, reqllires prior specific permissioll and/or a fee.

In this paper, we present the MCEDAR (multicast core extraction distributed ad hoc routing) multicast routing algorithm for ad hoc networks. MCEDAR is an extension to the CEDAR architecture and provides the robustness of mesh based routing protocols and the approximates the efficiency of tree based forwarding protocols. It decouples the control infrastructure from the actual data forwarding infrastructure. The decoupling allows for a very minimalistic and low overhead control infrastructure while still enabling very efficient data forwarding.

Many current wireless wide area packet data networks are characterized by very low and variable bandwidths, very high and variable delays, significant non-congestion related loss, asymmetric uplink and downlink channels, and occasional blackouts. Additionally, the majority of the latency in a WWAN connection is incurred over the wireless link. Under such operating conditions, most contemporary wireless TCP algorithms do not perform very well. Sinha, Venkitaraman, Sivakumar and Bharghavan (see Proc. of ACM Mobicom '99, 1999) we presented WTCP, a reliable transport protocol that is designed to operate efficiently and fairly over wireless wide area networks. WTCP is rate-based, uses only end-to-end mechanisms, performs rate control at the receiver, and uses the ratio of sending rate to receiving rate as as the primary metric for rate control. In this paper, we evaluate the performance of WTCP over CDPD networks. We have implemented and evaluated WTCP over the CDPD network, and also simulated it in the ns-2 simulator. Our performance results indicate that WTCP can improve on the performance of comparable algorithms such as TCP-NewReno and TCP-Vegas by between 20% to 200% for typical operating conditions.

We present CEDAR, a core-extraction distributed ad hoc routing algorithm for quality-of-service (QoS) routing in ad hoc network environments, CEDAR has three key components: (a) the establishment and maintenance of a self-organizing routing infrastructure called the core for performing route computations; (b) the propagation of the link-state of high bandwidth and stable links in the core through increase/decrease waves; and (c) a QoS-route computation algorithm that is executed at the core nodes using only locally available state. The performance evaluations show that CEDAR is a robust and adaptive QoS routing algorithm that reacts quickly and effectively to the dynamics of the network while still approximating the performance of link-state routing for stable networks.

This paper presents a cursive handwritten address recognition system, which consists of four main modules; 1) over-segmentor, 2) dynamic zip locator, 3) zip candidates generator, and 4) city-state-zip verifier. The dynamic zip locator and city-state-zip verifier are based on a flexible matcher for matching a sequence of graphemes with a list of generalized strings. The dynamic zip locator is able to locate zip without knowing exactly where the zip starts. The zip candidates generator uses a hidden Markov model with position-dependent state transition probabilities. A scheme for utilizing prefixes is designed to reduce computation and memory requirement. Finally, the system employs a mechanism for rejection based on rank features extracted from the matching. The overall system achieves an acceptance rate of 83.5% with 3.6% error for 5-digit encoding on 805 USPS cursive address images.

We present a method of combining multiple classifiers for optimizing word recognition. The proposed method combines the results of individual classifiers in such a way that the correct word is more likely to be hypothesized. This method provides a solution to the crucial issue of assigning reliable cost to the edges of the segmentation graph in the popular over-segmentation followed by dynamic programming approach for word recognition. Three combination functions are proposed and implemented. Experiments show that proposed method has a significant improvement on the word recognition accuracy.