Wi-Fi networks are still stubbornly unicast. By this we mean that networks are still designed under the basic assumption that it is always best for one pair of nodes to be transmitting to each other at any time. For example, on the uplink, the MAC protocol tries to schedule one transmission at a time to the AP. On the downlink, the AP transmits to one client at a time. This is surprising in light of the fact that wireless is a shared broadcast medium, physically multiple nodes can transmit concurrently on the uplink, and transmissions from the AP can reach multiple nodes on the downlink concurrently. There is of course good reason for this unicast design, since concurrent transmission on either the uplink or downlink leads to packet loss. This design ethos is used even in recent work that decodes from collisions, the focus is still to avoid collisions, but when they inevitably happen, figure out how to decode them if possible.

In this paper we question this long-held design principle. We show that with the appropriate design, successful concurrent transmissions can be enabled and exploited on both the uplink and downlink. Multiple clients can concurrently transmit to the AP, and the AP can transmit packets for multiple clients in a single downlink transmission. We show that this counter-intuitive approach can significantly increase network capacity and simplify network design. We design and implement AutoMAC, a novel MAC protocol that exploits recently proposed rateless coding techniques to provide such concurrency. We show via a prototype implementation and experimental evaluation that AutoMAC can provide a 3x increase in network capacity, and simplifies the MAC design since the strenuous effort MAC protocols put in avoiding collisions is no longer needed.

Recently, rateless codes like Raptor [25, 22], Strider [9], and Spinal codes [23] have introduced a promising approach to obtaining higher wireless throughput than fixed-rate codes, especially over time-varying channels. Rateless codes naturally process all the information available at the receiver corresponding to a packet, across different frame transmis- sions. Profitably using rateless codes in a wireless network, however, requires a link-layer protocol to coordinate between sender and receiver. This protocol needs to determine how much coded data should be sent before the sender pauses for feedback from the receiver. Without such feedback, an “open-loop” sender would not know when the packet has been decoded, but sending this feedback is not free and consumes a significant fraction of the packet transmission time. This paper develops RLP, a protocol that learns the probability distribution of the number of symbols required to decode a packet (the decoding CDF, and uses the learned distribution in a dynamic programming strategy to produce an optimal transmission schedule. Our experiments show that RLP reduces overhead by between 2.6x and 3.9x compared to 802.11-style ARQ and between 2.8x and 5.4x compared to 3GPP-style “Try-after-n” H-ARQ.

In multiuser MIMO (MU-MIMO) networks, the optimal bit rate of a user is highly dynamic and changes from one packet to the next. This breaks traditional bit rate adaptation algorithms, which rely on recent history to predict the best bit rate for the next packet. To address this problem, we introduce TurboRate, a rate adaptation scheme for MU-MIMO LANs. TurboRate shows that clients in a MU-MIMO LAN can adapt their bit rate on a per-packet basis if each client learns two variables: its SNR when it transmits alone to the access point, and the direction along which its signal is received at the AP. TurboRate also shows that each client can compute these two variables passively without exchanging control frames with the access point. A TurboRate client then annotates its packets with these variables to enable other clients to pick the optimal bit rate and transmit concurrently to the AP. A prototype implementation in USRP-N200 shows that traditional rate adaptation does not deliver the gains of MU-MIMO WLANs, and can interact negatively with MU-MIMO, leading to low throughput. In contrast, enabling MUMIMO with TurboRate provides a mean throughput gain of 1.7x and 2.3x, for 2-antenna and 3-antenna APs respectively.

A distributed MIMO system consists of several access points connected to a central server and operating as a large distributed multi-antenna access point. In theory, such a system enjoys all the significant performance gains of a traditional MIMO system, and it may be deployed in an enterprise WiFi like setup. In this paper, we investigate the efficiency of such a system in practice. Specifically, we build upon our prior work on developing a distributed MIMO testbed, and study the performance of such a system when both full channel state information is available to the transmitters and when no channel state information is available. In the full channel state information scenario, we implement Zero-Forcing Beamforming (ZFBF) and Tomlinson-Harashima Precoding (THP) which is provably near-optimal in high SNR conditions. In the scenario where no channel information is available, we implement Blind Interference Alignment (BIA), which achieves a higher multiplexing gain (degrees of freedom) than conventional TDMA. Our experimental results show that the performance of our implementation is very close to the theoretically predicted performance and offers significant gains over optimal TDMA. We also discuss medium access layer issues in detail for both scenarios. To the best of our knowledge, this is the first time that the theoretical high data rates of multiuser MIMO systems have been showcased in a real world distributed MIMO testbed.

Multi-user multiple-input multiple-output theory predicts manyfold capacity gains by leveraging many antennas on wireless base stations to serve multiple clients simultaneously through multi-user beamforming (MUBF). However, realizing a base station with a large number antennas is nontrivial, and has yet to be achieved in the real-world.

We present the design, realization, and evaluation of Argos, the first reported base station architecture that is capable of serving many terminals simultaneously through MUBF with a large number of antennas (M >> 10). Designed for extreme flexibility and scalability, Argos exploits hierarchical and modular design principles, properly partitions baseband processing, and holistically considers realtime requirements of MUBF. Argos employs a novel, completely distributed, beamforming technique, as well as an internal calibration procedure to enable implicit beamforming with channel estimation cost independent of the number of base station antennas. We report an Argos prototype with 64 antennas and capable of serving 15 clients simultaneously. We experimentally demonstrate that by scaling from 1 to 64 antennas the prototype can achieve up to 6.7 fold capacity gains while using a mere 1/64th of the transmission power.

In this paper, we design, implement and evaluate 802.11ec (Encoded Control), an 802.11-based protocol without control messages: instead, 802.11ec employs correlatable symbol sequences, which together with the timing the codes are transmitted, encode all control information and change the fundamental design properties of the MAC. The use of correlatable symbol sequences provides two key advantages: (i) efficiency, as it permits a near order of magnitude reduction of the control time; (ii) robustness, because codes are short and easily detectable even at low SINR and even while a neighbor is transmitting data. We implement 802.11ec on an FPGA-based software defined radio. We perform a large number of experiments and show that, compared to 802.11 (with and without RTS/CTS), 802.11ec achieves a vast efficiency gain in conveying control information and resolves key throughput and fairness problems in the presence of hidden terminals, asymmetric topologies, and general multi-hop topologies.

In wireless networks, users share a transmission medium. To increase the efficiency of the channel, wireless systems often use a medium access control (MAC) protocol perform channel coordination by having each node announce its usage intentions to minimize interference from other nodes in the same network. Traditionally, in a multi-channel environment, such announcements are made on a common control channel. However, such a channel is vulnerable to jamming because its location is pre-assigned and known to attackers. Furthermore, the announcements themselves provide information useful for jamming. In this paper, we focus on a situation where multiple wireless transmitters share spectrum in the presence of intelligent and possibly insider jammers capable of dynamically and adaptively changing their jamming patterns.

We develop a framework for effectively countering MAC-aware jamming attacks and then propose two schemes (Simple Transmitter Strategy and Simple Signaling Scheme) that are easily analyzed using game theory and show how they restrict optimal adversarial behavior. We evaluate our schemes three ways: mathematically, through Monte Carlo simulations, and by implementation on the WARP software-defined radio platform. Our schemes provides very rapid improvement over the alternative of not using any MAC protocol, and eventually converges to optimal performance (over fifteen-fold improvement in SINR and 50% gains in Shannon capacity in a realistic mobile scenario).

Retransmissions reduce the efficiency of data communication in wireless networks because of: (i) per-retransmission packet headers, (ii) contention overhead on every retransmission, and (iii) redundant bits in every retransmission. In fact, every retransmission more than doubles the time to successfully deliver the packet. To improve spectrum efficiency in a lossy environment, we propose a new in-frame retransmission scheme using uACKs. Instead of waiting for the entire transmission to end before sending the ACK, the receiver sends smaller uACKs on every few symbols, on a separated narrow feedback channel. Based on these uACKs, the sender only retransmits the lost symbols after the last data symbol in the frame, thereby adaptively changing the frame size to ensure it is successfully delivered. We have implemented uACKs on the Sora platform. Experiments with our prototype validate the feasibility of symbol-level uACKs. By significantly reducing the retransmistion overhead, the sender is able to aggressively use higher data rate for a lossy link. Both improve the overall network efficiency. Our experimental results from a controlled environment and an 9-node software radio testbed show that uACKs can have up to 240% throughput gain over 802.11g and up to 60% gain compared to the best known retransmission scheme.

Many networked applications that run in the background on a mobile device incur significant energy drains when using the cellular radio interface for communication. This is mainly due to the radiotail, where the cellular radio remains in a high energy state for up to 20s after each communication spurt. In order to cut down energy consumption, many recent devices employ fast dormancy, a feature that forces the client radio to quickly go into a low energy state after a fixed short idle period. However, aggressive idle timer values for fast dormancy can increase signaling overhead due to frequent state transitions, which negatively impacts the network. In this work, we have designed and implemented RadioJockey, a system that uses program execution traces to predict the end of communication spurts, thereby accurately invoking fast dormancy without increasing network signaling load. We evaluate RadioJockey on a broad range of background applications and show that it achieves 20-40% energy savings with negligible increase in signaling overhead compared to fixed idle timer-based approaches.

In 3G/4G cellular networks, data-plan subscribers are charged based on the used traffic volume. In this work, we conduct experiments to assess both this usage-based accounting architecture and application-specific charging policies by operators. Our evaluation basis is the user-centric tenet: We pay for what we get. The results show that both domains may go wrong. In various scenarios, we are charged for what we never get, and we can get what we want for free. In one case, we are charged for 450MB or more data despite receiving no single bit. In another case, we demonstrate that we are able to transfer 100MB or any amount we specify for free. The root causes lie in both the element-based (rather than end-to-end) accounting architecture and less prudent policy enforcement by operators. We make recommendations to remedy these unintended accounting actions.

The cellular industry is evaluating architectures to distribute the signal processing in radio access networks. One of the options is to carry out the processing of all base stations on a shared pool of compute resources in a central location. In this centralized architecture, the existing base stations will be replaced with just the antennas and a few other active RF components, and the remainder of the digital processing including the physical layer will be carried out in a central location. This model has potential benefits that include a reduction in the cost of operating the network due to fewer site visits, easy upgrades, and lower site lease costs, and an improvement in the network performance with joint signal processing techniques that span multiple base stations. Further there is a potential to reduce the number of hardware resources required to process the base stations by exploiting the variations in the processing load across base stations, which is the focus of this paper.

Specifically, we make the following contributions in the paper. Based on real-world data, we characterise the potential savings if shared homogeneous compute resources are used to process the signals from multiple base stations in the centralized architecture. We show that the centralized architecture can potentially result in savings of at least 22 % in compute resources by exploiting the variations in the processing load across base stations. These savings are achievable with statistical guarantees on successfully processing the base station's signals. We also design a framework that has two objectives: (i) partitioning the set of base stations into groups that are simultaneously processed on a shared homogeneous compute platform for a given statistical guarantee, and (ii) scheduling the set of base stations allocated to a platform in order to meet their real-time processing requirements. This partitioning and scheduling framework saves up to 19 % of the compute resources for a probability of failure of one in 10 billion. We refer to this solution as CloudIQ. Finally we implement and extensively evaluate the CloudIQ framework with a 3GPP compliant implementation of 5 MHz LTE.

The Android platform lacks tools for assessing and monitoring apps in a systematic way. This lack of tools is particularly problematic when combined with the open nature of Google Play, the main app distribution channel. As our key contribution, we design and implement ProfileDroid, a comprehensive, multi-layer system for monitoring and proling apps. Our approach is arguably the first to profile apps at four layers: (a) static, or app specication, (b) user interaction, (c) operating system, and (d) network. We evaluate 27 free and paid Android apps and make several observations: (a) we identify discrepancies between the app specication and app execution, (b) free versions of apps could end up costing more than their paid counterparts, due to an order of magnitude increase in traffic, (c) most network traffic is not encrypted, (d) apps communicate with many more sources than users might expect|as many as 13, and (e) we find that 22 out of 27 apps communicate with Google during execution. ProfileDroid is the first step towards a systematic approach for (a) generating cost-effective but comprehensive app profiles, and (b) identifying inconsistencies and surprising behaviors.

Spectrum management and device coordination for Dynamic Spectrum Access (DSA) networks have received significant research attention. However, current wireless devices have yet to fully embrace DSA networks due to the difficulties in realizing spectrum- agile communications. We address the practical hurdles and present solutions towards implementing DSA devices, answering an important question "what is a simple practical extension to current wireless devices that makes them spectrum-agile?" To this end, we propose RODIN, a general per-frame spectrum-shaping protocol that has the following features to support DSA in commercial off-the-shelf (COTS) wireless devices: (a) direct manipulation of passband signals from COTS devices, (b) fast FPGA-based spectrum shaping, and (c) a novel preamble design for spectrum agreement. RODIN uses an FPGA-based spectrum shaper together with a preamble I-FOP to achieve per-frame spectrum shaping with a delay of under 10μs.

Network deduplication (dedup) is an attractive approach to improve network performance for mobile devices. With traditional deduplication, the dedup source uses only the portion of the cache at the dedup destination that it is aware of. We argue in this work that in a mobile environment, the dedup destination (say the mobile) could have accumulated a much larger cache than what the current dedup source is aware of. This can occur because of several reasons ranging from the mobile consuming content through heterogeneous wireless technologies, to the mobile moving across different wireless networks. In this context, we propose asymmetric caching, a solution that is overlaid on baseline network deduplication, but which allows the dedup destination to selectively feedback appropriate portions of its cache to the dedup source with the intent of improving the redundancy elimination efficiency. We show using traffic traces collected from $30$ mobile users, that with asymmetric caching, over 89% of the achievable redundancy can be identified and eliminated even when the dedup source has less than one hundredth of the cache size as the dedup destination. Further, we show that the ratio of bytes saved from transmission at the dedup source because of asymmetric caching is over 6x that of the number of bytes sent as feedback. Finally, with a prototype implementation of asymmetric caching on both a Linux laptop and an Android smartphone, we demonstrate that the solution is deployable with reasonable CPU and memory overheads.

Mobile phone sensing is a new paradigm which takes advantage of the pervasive smartphones to collect and analyze data beyond the scale of what was previously possible. In a mobile phone sensing system, the platform recruits smartphone users to provide sensing service. Existing mobile phone sensing applications and systems lack good incentive mechanisms that can attract more user participation. To address this issue, we design incentive mechanisms for mobile phone sensing. We consider two system models: the platform-centric model where the platform provides a reward shared by participating users, and the user-centric model where users have more control over the payment they will receive. For the platform-centric model, we design an incentive mechanism using a Stackelberg game, where the platform is the leader while the users are the followers. We show how to compute the unique Stackelberg Equilibrium, at which the utility of the platform is maximized, and none of the users can improve its utility by unilaterally deviating from its current strategy. For the user-centric model, we design an auction-based incentive mechanism, which is computationally efficient, individually rational, profitable, and truthful. Through extensive simulations, we evaluate the performance and validate the theoretical properties of our incentive mechanisms.

The rapid deployment of millions of mobile sensors and smartphones has resulted in a demand for opportunistic encounter-based networking to support mobile social networking applications and proximity-based gaming. However, the success of these emerging networks is limited by the lack of effective and energy efficient neighbor discovery protocols. While probabilistic approaches perform well for the average case, they exhibit long tails resulting in high upper bounds on neighbor discovery time. Recent deterministic protocols, which allow nodes to wake up at specific timeslots according to a particular pattern, improve on the worst case bound, but do so by sacrificing average case performance. In response to these limitations, we have designed Searchlight, a highly effective asynchronous discovery protocol that is built on three basic ideas. First, it leverages the constant offset between periodic awake slots to design a simple probing-based approach to ensure discovery. Second, it allows awake slots to cover larger sections of time, which ultimately reduces total awake time drastically. Finally, Searchlight has the option to employ probabilistic techniques with its deterministic approach that can considerably improve its performance in the average case when all nodes have the same duty cycle. We validate Searchlight through analysis and real-world experiments on smartphones that show considerable improvement (up to 50%) in worst-case discovery latency over existing approaches in almost all cases, irrespective of duty cycle symmetry.

As we are surrounded by an ever-larger variety of post-PC devices, the traditional methods for identifying and authenticating users have become cumbersome and time-consuming. In this paper, we present a capacitive communication method through which a device can recognize who is interacting with it. This method exploits the capacitive touchscreens, which are now used in laptops, phones, and tablets, as a signal receiver. The signal that identifies the user can be generated by a small transmitter embedded into a ring, watch, or other artifact carried on the human body. We explore two example system designs with a low-power continuous transmitter that communicates through the skin and a signet ring that needs to be touched to the screen. Experiments with our prototype transmitter and tablet receiver show that capacitive communication through a touchscreen is possible, even without hardware or firmware modifications on a receiver. This latter approach imposes severe limits on the data rate, but the rate is sufficient for differentiating users in multiplayer tablet games or parental control applications. Controlled experiments with a signal generator also indicate that future designs may be able to achieve datarates that are useful for providing less obtrusive authentication with similar assurance as PIN codes or swipe patterns commonly used on smartphones today.

Although wireless broadband technologies have evolved significantly over the past decade, they are still insufficient to support the fast-growing mobile traffic, especially due to the increasing popularity of mobile video applications. Wireless multicast, aiming to exploit the wireless broadcast advantage, is a viable approach to bridge the gap between the limited wireless networking capacity and the ever-increasing mobile video traffic demand. In this work, we propose MuVi, a Multicast Video delivery scheme in OFDMA-based 4G wireless networks, to optimize multicast video traffic. MuVi differentiates video frames based on their importance in reconstructing the video and incorporates an efficient radio resource allocation algorithm to optimize the overall video quality across all users in the multicast group. MuVi is a lightweight solution with most of the implementation in the gateway, slight modification in the base station, and no modification at the clients. We implement MuVi on a WiMAX testbed and compare its performance to a Naive wireless multicast scheme that employs the most robust MCS (Modulation and Coding Scheme), and an Adaptive scheme that employs the highest MCS supportable by all clients. Experimental results show that MuVi improves the average video PSNR (Peak Signal-to-Noise Ratio) by up to 13 and 7 dB compared to the Naive and the Adaptive schemes, respectively. MuVi does not require modification to the video encoding scheme or the air interface. Thus it allows speedy deployment in existing systems.

Video quality assessment in mobile devices, for instances smart phones and tablets, raises unique challenges such as unavailability of original videos, the limited computation power of mobile devices and inherent characteristics of wireless networks (packet loss and delay). In this paper, we present a metric, Temporal Variation Metric (TVM), to measure the temporal information of videos. Despite its simplicity, it shows a high correlation coefficient of 0.875 to optical flow which captures all motion information in a video. We use the TVM values to derive a reduced-reference temporal quality assessment metric, Temporal Variation Index (TVI), which quantifies the quality degradation incurred in network transmission. Subjective assessments demonstrate that TVI is a very good predictor of users’ Quality of Experience (QoE). Its prediction shows a 92.5% of correlation to subjective Mean Opinion Score (MOS) ratings. Through video streaming experiments, we show that TVI can also estimate the network conditions such as packet loss and delay. It depicts an accuracy of almost 95% in extensive tests on 183 video traces.

We observe two trends, growing wireless capability at the physical layer powered by MIMO-OFDM, and growing video traffic as the dominant application traffic. We observe non-uniform energy distribution of both the source and MIMO-OFDM channel components. This motivates us to leverage the source data redundancy at the channel to achieve high video reconstruction performance. We propose SMARTCAST that first separates the source and channel into independent components, matches the more important source components with higher-gain channel components, and allocates power weights with joint consideration to the source and the channel. Such a scheme achieves fine-grained unequal error protection across source components. We implemented SMARTCAST in Matlab and on Sora. Extensive evaluation shows that our scheme outperforms competitive schemes by notable margins, sometimes up to 7~dB in PSNR for challenging scenarios.

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-back 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% 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%.

Given that full duplex andMIMO both employ multiple antenna resources, an important question that arises is how to make the choice between MIMO and FD?. Interestingly, we show that optimal performance requires a combination of both to be used. Hence, we present the design and implementation of MIDU, the first MIMO Full-Duplex system for wireless networks. MIDU employs antenna cancellation with symmetric placement of transmit and receive antennas as its primary RF cancellation technique. We show that MIDU’s design provides large amounts of self-interference cancellation with several key advantages: (i) It allows for two stage of additive antenna cancellation in tandem, to yield as high as 45 dB self-interference suppression; (ii) It can potentially eliminate the need for other forms of analog cancellation, thereby avoiding the need for variable attenuator and delays; (iii) It easily scales to MIMO systems, thereby enabling the coexistence of MIMO and Full Duplex.

We implementedMIDU on theWARP FPGA platform, and evaluated its performance against Half Duplex (HD)-MIMO. Our results reveal that with the same number of RF chains, MIDU can potentially double the throughput achieved by Half Duplex MIMO in a single link; and provide median gains of at least 30% even in single cell scenarios, where Full Duplex encounters inter-client interference. Based on key insights from our results, we also highlight how to efficiently enable scheduling for a MIDU node.

Indoor localization is of great importance for a range of pervasive applications, attracting many research efforts in the past decades. Most radio-based solutions require a process of site survey, in which radio signatures of an interested area are annotated with their real recorded locations. Site survey involves intensive costs on manpower and time, limiting the applicable buildings of wireless localization worldwide. In this study, we investigate novel sensors integrated in modern mobile phones and leverage user motions to construct the radio map of a floor plan, which is previously obtained only by site survey. On this basis, we design LiFS, an indoor localization system based on off-the-shelf WiFi infrastructure and mobile phones. LiFS is deployed in an office building covering over 1600m², and its deployment is easy and rapid since little human intervention is needed. In LiFS, the calibration of fingerprints is crowdsourced and automatic. Experiment results show that LiFS achieves comparable location accuracy to previous approaches even without site survey.

We consider the problem of locating devices such as laptops, desktops, smartphones etc. within an office environment, without requiring any special hardware or infrastructure. We consider two widely-studied approaches to indoor localization: (a) those based on Radio Frequency (RF) measurements made by devices withWiFi or cellular interfaces, and (b) those based on Acoustic Ranging (AR) measurements made by devices equipped with a speaker and a microphone. A typical office environment today comprises devices that are amenable to either one or both these approaches to localization. In this paper we ask the question, "How can we combine RF and AR based approaches in synergy to locate a wide range of devices, leveraging the benefits of both approaches?" The key contribution of this paper is Centaur, a system that fuses RF and AR based localization techniques into a single systematic framework that is based on Bayesian inference. Centaur is agnostic to the specific RF or AR technique used, giving users the flexibility of choosing their preferred RF or AR schemes. We also make two additional contributions: making AR more robust in non-line-of-sight settings (EchoBeep) and adapting AR to localize speaker-only devices (DeafBeep). We evaluate the performance of our AR enhancements and that of the Centaur framework through microbenchmarks and deployment in an office environment.

Radio Frequency (RF) fingerprinting, based onWiFi or cellular signals, has been a popular approach to indoor localization. However, its adoption in the real world has been stymied by the need for site-specific calibration, i.e., the creation of a training data set comprising WiFi measurements at known locations in the space of interest. While efforts have been made to reduce this calibration effort using modeling, the need for measurements from known locations still remains a bottleneck. In this paper, we present Zee – a system that makes the calibration zero-effort, by enabling training data to be crowdsourced without any explicit effort on the part of users.

Zee leverages the inertial sensors (e.g., accelerometer, compass, gyroscope) present in the mobile devices such as smartphones carried by users, to track them as they traverse an indoor environment, while simultaneously performing WiFi scans. Zee is designed to run in the background on a device without requiring any explicit user participation. The only site-specific input that Zee depends on is a map showing the pathways (e.g., hallways) and barriers (e.g., walls). A significant challenge that Zee surmounts is to track users without any a priori, user-specific knowledge such as the user’s initial location, stride-length, or phone placement. Zee employs a suite of novel techniques to infer location over time: (a) placement-independent step counting and orientation estimation, (b) augmented particle filtering to simultaneously estimate location and user-specific walk characteristics such as the stride length, (c) back propagation to go back and improve the accuracy of localization in the past, and (d) WiFi-based particle initialization to enable faster convergence. We present an evaluation of Zee in a large office building.

Highly accurate indoor localization of smartphones is critical to enable novel location based features for users and businesses. In this paper, we first conduct an empirical investigation of the suitability of WiFi localization for this purpose. We find that although reasonable accuracy can be achieved, significant errors (e.g., 6 ~ 8m) always exist. The root cause is the existence of distinct locations with similar signatures, which is a fundamental limit of pure WiFibased methods. Inspired by high densities of smartphones in public spaces, we propose a peer assisted localization approach to eliminate such large errors. It obtains accurate acoustic ranging estimates among peer phones, then maps their locations jointly against WiFi signature map subjecting to ranging constraints. We devise techniques for fast acoustic ranging among multiple phones and build a prototype. Experiments show that it can reduce the maximum and 80-percentile errors to as small as 2m and 1m, in time no longer than the original WiFi scanning, with negligible impact on battery lifetime.

Battery life is a critical performance and user experience metric on mobile devices. However, it is difficult for app developers to measure the energy used by their apps, and to explore how energy use might change with conditions that vary outside of the developer’s control such as network congestion, choice of mobile operator, and user settings for screen brightness. We present an energy emulation tool that allows developers to estimate the energy use for their mobile apps on their development workstation itself. The proposed techniques scale the emulated resources including the processing speed and network characteristics to match the app behavior to that on a real mobile device. We also enable exploring multiple operating conditions that the developers cannot easily reproduce in their lab. The estimation of energy relies on power models for various components, and we also add new power models for components not modeled in prior works such as AMOLED displays. We also present a prototype implementation of this tool and evaluate it through comparisons with real device energy measurements.

In this paper, we propose a novel clock calibration approach called FLIGHT, which leverages the fact that the fluorescent light intensity changes with a stable period that equals half of the alternating current’s. By tuning to the light emitted from indoor fluorescent lamps, FLIGHT can intelligently extract the light period information and achieve network wide time calibration by referring to such a common time reference. We address a series of practical challenges and implement FLIGHT in TelosB motes. We conduct comprehensive experiments using a 12-node test-bed in both static and mobile environments. Over one-week measurement suggests that compared with existing technologies, FLIGHT can achieve tightly synchronized time with low energy consumption.

Rate adaptation in 802.11n is more complex than in its legacy systems. In addition to MCS rates, it has to select configurations along more dimensions spanning transmit/receive antennas and the number of spatial streams. In this work, we show that current MIMO RA algorithms are not energy efficient despite achieving high throughput. The fundamental problem is that, the high-throughput setting is not equivalent to the energy-efficient one. Marginal throughput gain may be realized at high energy cost. We then proposed EERA, an energy-efficient solution that uses tree-based ternary search with simultaneous branch pruning. The resulting algorithm has both low complexity and high energy savings. Our experiments have confirmed its effectiveness.

GPS is one of the most widely used wireless systems. A GPS receiver has to lock on the satellite signals to calculate its position. The process of locking on the satellites is quite costly and requires hundreds of millions of hardware multiplications, leading to high power consumption. The fastest known algorithm for this problem is based on the Fourier transform and has a complexity of O(n log n), where n is the number of signal samples.

This paper presents the fastest GPS locking algorithm to date. The algorithm reduces the locking complexity to O(n (log n)^0.5). Further, if the SNR is above a threshold, the algorithm becomes linear, i.e., O(n). Our algorithm builds on recent developments in the growing area of sparse recovery. It exploits the sparse nature of the synchronization problem, where only the correct alignment between the received GPS signal and the satellite code causes their cross-correlation to spike.

We further show that the theoretical gain translates into empirical gains for GPS receivers. Specifically, we built a prototype of the design using software radios and tested it on two GPS datasets collected in the US and Europe. The results show that the new algorithm reduces the median number of multiplications by 2.2× in comparison to the state of the art design, for real GPS signals.

Radio Frequency Identification (RFID) systems have been widely deployed for various applications. This paper concerns the fundamental problem of estimating tag population size, which is needed in many applications such as tag identification and warehouse monitoring. In this paper, we propose a new scheme called Average Run based Tag estimation (ART). ART is significantly faster than prior schemes because its estimator has much smaller variance. For example, given a confidence interval of 0.1% and the required reliability of 99.9%, ART is consistently 7 times faster than the fastest existing schemes (UPE and EZB) for any tag population size. Furthermore, ART's estimation time is observably independent of population sizes. ART is easy to deploy because it neither requires modification to tags nor to the communication protocol between tags and readers. ART only needs to be implemented on readers as a software module. ART works with multiple readers with overlapping regions.

While a natural fit for modeling and understanding mobile networks, time-varying graphs remain poorly understood. Indeed, many of the usual concepts of static graphs have no obvious counterpart in time-varying ones. In this paper, we introduce the notion of temporal reachability graphs. A (tau,delta)-reachability graph is a time-varying directed graph derived from an existing connectivity graph. An edge exists from one node to another in the reachability graph at time t if there exists a journey (i.e., a spatiotemporal path) in the connectivity graph from the first node to the second, leaving after t, with a positive edge traversal time tau, and arriving within a maximum delay delta. We make three contributions. First, we develop the theoretical framework around temporal reachability graphs. Second, we harness our theoretical findings to propose an algorithm for their efficient computation. Finally, we demonstrate the analytic power of the temporal reachability graph concept by applying it to synthetic and real-life datasets. On top of defining clear upper bounds on communication capabilities, reachability graphs highlight asymmetric communication opportunities and offloading potential.