AutoMAC: Rateless Wireless Concurrent Medium Access,
Stephanie Pereira, and
Sachin Katti (Stanford University, USA)
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.
No Symbol Left Behind: A Link-layer Protocol for Rateless Codes,
Hari Balakrishnan, and
Devavrat Shah (Massachusetts Institute of Technology, USA)
Recently, rateless codes like Raptor [25, 22], Strider , and Spinal codes  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.
Rate Adaptation for 802.11 Multiuser MIMO Networks,
Kuang-Che Lee, and
Kate Ching-Ju Lin (Academia Sinica, Taiwan);
Shyamnath Gollakota (University of Washington);
Dina Katabi (Massachusetts Institute of Technology, USA); and
Ming-Syan Chen (Academia Sinica, Taiwan)
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.
Achieving High Data Rates in Distributed MIMO Systems,
Horia Vlad Balan,
Konstantinos Psounis, and
Giuseppe Caire (University of Southern California, USA)
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.
Argos: Practical Base Stations with Large-scale Multi-user Beamforming,
Hang Yu, and
Narendra Anand (Rice University, USA);
Li Erran Li and
Tom Marzetta (Bell Labs, USA);
Yang Richard Yang (Yale University, USA); and
Lin Zhong (Rice University, USA)
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.
802.11ec: Collision Avoidance without Control Messages,
Eugenio Magistretti (Rice University, USA);
Omer Gurewitz (Ben Gurion University, Israel); and
Edward W. Knightly (Rice University, USA)
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
SimpleMAC: A Jamming-Resilient MAC-Layer Protocol for Wireless Channel Coordination,
Sang-Yoon Chang and
Yih-Chun Hu (University of Illinois, Urbana-Champaign, USA); and
Nicola Laurenti (University of Padova, Italy)
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).
Frame Retransmission Considered Harmful: Improve Spectrum Efficiency Using uACKs,
Haichen Shen, and
Kun Tan (Microsoft Research Asia, China);
Ranveer Chandra (Microsoft Research, USA);
Yongguang Zhang (Microsoft Research Asia, China); and
Qian Zhang (Hong Kong University of Science and Technology, China)
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.
Radio-Jockey: Mining Program Execution to Optimize Cellular Radio Usage,
Pavan K. Athivarapu,
Vishnu Navda, and
Ramachandran Ramjee (Microsoft Research India);
Dushyant Arora (Princeton University, USA);
Venkata N. Padmanabhan (Microsoft Research India); and
George Varghese (University of California, San Diego, USA)
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.
Can We Pay for What We Get in 3G Data Access?
Chiyu Li, and
Songwu Lu (University of California, Los Angeles, USA)
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.
CloudIQ: A Framework for Processing Base Stations in a Data Center,
Shoban Preeth Chandrabose, and
Manjunath Kashyap Jataprolu (Alcatel-Lucent Bell Labs);
Gautam Kumar (University of California, Berkeley, USA);
Vikram Srinivasan, and
Thomas Woo (Alcatel-Lucent Bell Labs)
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.
ProfileDroid: Multi-layer Profiling of Android Applications,
Iulian Neamtiu, and
Michalis Faloutsos (University of California, Riverside, USA)
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.
Building Efficient Spectrum-Agile Devices for Dummies,
Eugene Chai and
Kang G. Shin (University of Michigan-Ann Arbor, USA);
Sung-Ju Lee, and
Raul Etkin (HP Labs, USA)
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.
Asymmetric Caching: Improved Network Deduplication for Mobile Devices,
Shruti Sanadhya and
Raghupathy Sivakumar (Georgia Institute of Technology, USA);
Kyu-Han Kim and
Paul T. Congdon (HP Labs, USA);
Sriram Lakshmanan (Georgia Institute of Technology, USA); and
Jatinder Pal Singh (Xerox PARC, USA)
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.
Crowdsourcing to Smartphones: Incentive Mechanism Design for Mobile Phone Sensing,
Guoliang Xue, and
Xi Fang (Arizona State University, USA); and
Jian Tang (Syracuse University, USA)
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.
Searchlight: Won't You Be My Neighbor?
Matt Trower, and
Robin Kravets (University of Illinois, Urbana-Champaign, USA)
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
Distinguishing Users with Capacitative Touch Communication,
Predrag Spasojevic, and
Jeffrey Walling (Rutgers University, USA)
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
MuVi: A Multicast Video Delivery Scheme for 4G Cellular Networks,
Jongwon Yoon (University of Wisconsin-Madison, USA);
Honghai Zhang (NEC Laboratories America, USA)
Suman Banerjee (University of Wisconsin-Madison, USA); and
Sampath Rangarajan (NEC Laboratories America, USA)
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.
Temporal Quality Assessment for Mobile Videos,
An Jack Chan,
Eilwoo Baik, and
Prasant Mohapatra (University of California, Davis, USA)
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.
Soft video delivery in MIMO WLANs,
Xiao Lin Liu (University of Science and Technology of China);
Feng Wu, and
Yongguang Zhang (Microsoft Research Asia, China)
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.
MARVEL: Multiple Antenna based Relative Vehicle Localizer,
Zhixue Lu, and
Prasun Sinha (Ohio State University, USA)
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%.
MIDU: Enabling MIMO Full Duplex,
Ehsan Aryafar(Princeton University, USA);
Mohammad A. Khojastepour,
Karthikeyan Sundaresan, and
Sampath Rangarajan (NEC Laboratories America, USA)
Mung Chiang (Princeton University, USA)
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
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.
Locating in Fingerprint Space: Wireless Indoor Localization with Little Human Intervention,
Chenshu Wu, and
Yunhao Liu (Tsinghua University, China)
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 1600m2, 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
Centaur: Locating Devices in an Office Environment,
Krishna Chintalapudi, and
Venkata N. Padmanabhan (Microsoft Research India)
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.
Zee: Zero-Effort Crowdsourcing for Indoor Localization,
Krishna Chintalapudi, and
Venkata N. Padmanabhan (Microsoft Research India); and
Rijurekha Sen (Indian Institute of Technology, Bombay, India)
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.
Push the Limit of WiFi based Localization for Smartphones,
Simon Sidhom, and
Yingying Chen (Stevens Institute of Technology, USA); and
Fan Ye (IBM Research, USA)
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.
Empowering Developers to Estimate App Energy Consumption,
Radhika Mittal (Indian Institute of Technology, Kharapur, India);
Aman Kansal and
Ranveer Chandra (Microsoft Research, USA)
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.
FLIGHT: Clock Calibration Using Fluorescent Lighting,
Cheng Li, and
Mo Li (Nanyang Technological University, Singapore);
Xiang-Yang Li (Illinois Institute of Technology, USA); and
Yunhao Liu (Tsinghua University, China)
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.
Energy-based Rate Adaptation for 802.11n,
Chunyi Peng, and
Songwu Lu (University of California, Los Angeles, USA); and
Xinbing Wang (Shanghai JiaoTong University, China)
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.
Faster GPS Via the Sparse Fourier Transform,
Dina Katabi, and
Piotr Indyk (Massachusetts Institute of Technology, USA)
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
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.
Every Bit Counts - Fast and Scalable RFID Estimation,
Muhammad Shahzad and
Alex X. Liu (Michigan State University, USA)
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.
Temporal Reachability Graphs,
John Whitbeck and
Marcelo Dias de Amorim (LIP6 Laboratory, France);
Vania Conan (Thales Communications and Security, France); and
Jean-Loup Guillaume (LIP6 Laboratory, France)
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.
Copyright © 2012, ACM Annual
International Conference on Mobile Computing and Networking
(Banner photograph by Stephan
Ramon Garcia, used with his kind permission.)