Loading presentation...
Prezi is an interactive zooming presentation

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

DySPAN 2012

by

Caleb Phillips

on 29 March 2015

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of DySPAN 2012

Practical Radio Environment
Mapping with Geostatistics
Caleb Phillips
Michael Ton
Doug Sicker
Dirk Grunwald
Measure
Model
Interpolate
Map
Grid Sample*
Drive Test
Crowd Sourced
Resampling
Initial Sampling
Null Measurements
Choosing What to Measure
Physical Layer Metrics
Signal to Noise Ratio (SNR)
Carrier to Interference and Noise Ratio (CINR)
Effective Signal to Noise Ratio (SNR)
Subcarrier Flatness
Relative Constellation Error (RCE)
Error Vector Magnitude (EVM)
Application Layer Metrics
TCP/UDP Throughput
Bit Error Rate
Packet Error Rate
Wireless networks are everywhere
yet, we don't have good methods for
saying how well they
work where
Wireless coverage mapping is the process of
making a picture of an invisible thing that is constantly changing.
Why do we care?
Finding and Repairing Holes
Communicating Abilities to Users
Verifying Contractual Requirements
Self Optimizing Networks
Radio Environment Mapping for Spectrum Re-use
Mapping Sources of Interference & Spurious Emissions
How's it done now?
Measurements in straight lines :(
Can we just...guess?
Phillips, Sicker, and Grunwald. Bounding the Practical Error of Path Loss Models. International Journal of Antennas and Propagation. Hindawi Publishing Corporation. Volume 2012.

Phillips, Sicker, and Dirk Grunwald. A Survey of Wireless Path Loss Prediction and Coverage Mapping Methods. IEEE Communications Society Surveys and Tutorials.

Phillips, Sicker, and Grunwald. Bounding the Practical Error of Path Loss Models in Urban Environments. IEEE Dynamic Spectrum Access Networks 2011 (DySPAN 2011)

Phillips, Raynel, Curtis, Bartels, Sicker, Grunwald, and McGregor. The Efficacy of Path Loss Models for Fixed Rural Wireless Links. Passive and Active Measurement Conference 2011 (PAM 2011).
50+ dB RMSE typical
Best case performance ~12 dB RMSE
~9 dB with parameter tuning (or simple fitting)

Bottom line: if some certainty of accuracy is needed, then measurements are necessary.
Optimize
Summary
Put "green"
in the right spots
and red in the
right spots.
A "Krigian" Approach to Wireless
Coverage Mapping
www.nearfield.org/2011/02/wifi-light-painting
www.verizonwireless.com
www.ntia.doc.gov/files/ntia/publications/2003-allochrt.pdf
Harrison, K. How Much White-Space Capacity Is There? IEEE DySPAN 2010.
www.nytimes.com/2012/02/15/business/media/fcc-bars-airwave-use-for-broadband-plan.html
Robinson, Swaminathan, and Knightly. Assessment of Urban-Scale Wireless Networks with a Small Number of Measurements. ACM MobiCom 2008.
www.fiercewireless.com/story/photos-riding-shotgun-verizon-network-tester/2011-06-17
The need for greater
uniformity in
valuation procedures
and for the limitation
as far as possible of the personal element cannot be disputed.

The solution to this problem lies, in my opinion, in the
extensive application of statistics
. I do not wish to imply, however, that statistics is a miracle tool with rigid procedures that can be applied indiscriminately [...] without a proper appreciation of local conditions. On the contrary, a
clear concept of the problems involved
is essential, and this can emanate only from practical experience.

Once the necessary spade work has been done, however, the routine application of statistics [... is]
well within the scope of the average surveyor
This thesis claims that
Domain appropriate geostatistical methods can provide a solution to wireless coverage mapping that (a) is more accurate than is possible with common a priori modeling approaches and (b) requires fewer measurements than explicit, undirected measurement-based approaches.
Core research contributions:
-
Complete
, thoroughly
tested

system
for
coverage mapping
- First practical application of
geostatistics
to
the radio environment
- Greater
accuracy
than is possible with
existing a priori modeling methods or
common data-fitting approaches
-
Richer maps
than heuristic sample-minimizing
approaches w/ same accuracy and efficiency
- First practical investigation of
crowd-sourced
coverage mapping
using real data
- First application of
sample optimization
to radio environment mapping
Why Geostatistics and not X, Y, or Z other approaches?
Embraces rather than ignores spatiotemporal variability by explicitly modeling intrinsic variation in the field.
A robust statistical method where each mapped
point is a distribution with a clear notion of confidence in predictions.
An exact interpolation method where the interpolated point is always true at the measured locations.
1)
2)
3)
www.3ts.it/radioplanning.asp
www.wimaxforumglobalevents.com/americas/exhibition_zone/exhibitors/edx
A random field named 'Z'
Our friend, the semivariogram
Fitting the semivariogram model
Important Extensions:
Resampling
Truncation
Null measurements
Cubic & Gaussian
Automation
Parallelism
Ordinary Kriging is a-OK
en.wikipedia.org/wiki/File:Example_krig.png
www.nae.edu/MembersSection/Directory20412/31144.aspx
Wellens, Riihijarvi, and Mahonen. Spatial statistics and models of spectrum use. Computer Communications. 2009. 32. 1998-2011.
www.bisolutions.us/A-Brief-Introduction-to-Spatial-Interpolation.php
Hybridization: Measurement-corrected modeling
Z'(x) - Model Error
Z(x) - Map
Confidence
CU WiMax "4G"
Verizon LTE "4G"
Urban Mesh WiFi
AT&T GSM "3G"
Case Studies & Performance Evaluation
5 BSs on 4 channels
Portable
Spectum
Analyzer
WiMax @ 2.5 GHz
Clustered
Measurements
Throughput
measurements
~ 4 dB RMSE, 70% hole prediction accuracy
AT&T LTE @ 700 MHz
LG LTE Dongle &
JDSU Software
Clustered
Measurements
Throughput
Measurements
11 BSs with ~3
sectors each
~4-6 dB RMSE depending on metric used
Sample: 100m Equilateral Triangular Lattice
Sample: 100m Equilateral Triangular Lattice
3 WiFi Drive-Test Datasets:
Google Mountain View
Rice/TFA Houston
MetroFi Portland
Several Hundred Unique APs
Resampled at multiple lags
50-100m performs best
Packet-based measurements with
commodity hardware
Overall RMSE 5-10dB depending on site, and resampling density.

Achieves same hole-prediction
accuracy as Robinson's method with an the same number of samples.
Open Signal Maps Crowd-Sourced Data Collection w/Android Phones
www.opensignalmaps.net
587 distinct BSs, 1-1257
measurements each
190 distinct devices
performing measurement
Data-sparse (only 13 unique
devices mapping central
Boulder)
~4dB RMSE, but too
little data for strong
cross validation
Modeling CU campus: 4.2% of students participating could exhaustively map the campus in 24 hours.
Experiments in Simulated Mobility using SLAW
1
2
3
4
Iterative multi-phase optimized sampling
Problem: Want to choose N additional points that will most improve the existing map.

Has seen some application in soil sciences

Complexity is N choose M, where N is the number of possible locations and M is the sample size.
e.g., 1.27956169 × 10^160 options for one CU WiMax node using a sample size of 50.
Delmelle and Goovaerts. Second-phase sampling designs for non-stationary spatial variables. Geoderma. Volume 153. 2009. 205-216.
Kriging Variance
Roughness
Roughness-weighed Kriging Variance
Tractable solutions to an intractable problem
Greedy
Serial Spatial
Simulated Annealing
Parallel Spatial Simulated Annealing
A momentary digression on how friggin' amazing computers are
1,040,000 compute hours
118 years, 255 days
15.47 seconds
26,975 KWh
5.41 times
Case Study - Geni WiMax Node at CU Boulder
Modest ~0.5 dB RMSE Gain
3 phases w/ N = 10,25, & 50 points
Complete
, statistically robust coverage mapping
method
1-2 orders of magnitude
smaller RMSE
than simple data fitting and modeling approaches
Error approaching expected repeated measures variance*
Same
efficiency
as sample-minimizing heuristic approaches**
First application of
geostatistics
to real coverage mapping
New
visualization
schemes adapted from medical imaging, and new map combining and tiling mechanisms
But wait...there's more
What's Next?
Under review at Science :)
Submissions in progress to IEEE INFOCOM 2013,
IEEE TMC, and IEEE DySPAN 2013 on the work
described here.
Many open doors in the realm of wireless
coverage mapping
Visualization, better measurement tools, and sample optimization most are most opportune
Seeking postdoc funding for work on sustainable
food distribution and waste reduction networks
Apply optimization and statistical modeling skills to new and important problems.
Thanks
Wonderfully supportive friends and family, advisors and collaborators, former teachers, people who hired me in spite of inflated resumes, those who gave me opportunities and mentored me. My bike, the Colorado mountains, good beer. And, oddly, the Radiolab radio program.
Post-Defense Beers at the Southern Sun at high noon
*Yfantis, Flatman, and Behar. Efficiency of Kriging Estimation for Square, Triangular, and Hexagonal Grids. Mathematical Geology. 1987. Volume 19. 183-205.
*Rizk, Wagen, and Gardiol. Two-dimensional ray-tracing modeling for propagation prediction in microcellular environments. IEEE Trans. on Vehicular Technology. 1997. Volume 46. 508-518.
**J Robinson, R Swaminathan, and E Knightly. Assessment of an Urban-scale Wireless Network with a Small Number of Measurements. ACM MobiCom. 2008.
P(x) = alpha*10*log10(d) + 20log10(f) + 32.45 + epsilon
they're revolutionary, amazing and
empowering
Oslo, Norway
"
"
Other Contributions to
Wireless Systems Research
Geostatistical Interpolation (Kriging) requires we first fit a semivariogram model for the data.
Investigated greedy and metaheuristic algorithms (parallel and serial)

Spatial Simulated Annealing (SSA) performs best
How is validation done
10-fold 20%-withheld cross validation
Mean RMSE, Kriging Variance
Independent random sample
RMSE, "hole" prediction accuracy
Summary of Key Performance Results
State of the Art "4G" technology
Operates in "clean" educational band
Representative of current & future tech.
The favorite 4G Technology
700 MHz may present unique/different mapping challenges
How it's done now
Drive test data
Three Complex urban environments
Directly comparable to prior work
Current cell infrastruture
Crowd-sourced measurements
1.9 GHz

Metric K-Var RMSE
Gain
Accuracy
CU WiMax CINR 2-4 2-4
9-18
~70%
ESNR 5-11 6-11
2.5-8
~70%
Verizon LTE SNR 4-6 4-5.5
0.4-2.5
Urban WiFi SNR 4-6 3-10
0.5-2.5
80-90%
AT&T GSM SNR 5.5 4
8.8
85-90%
Frame & Figure Graveyard
As with mining, intuition doesn't always work
Correlations between Metrics
WiMax
Up/downstream UDP "saturation" throughput tests to ASN gateway. Random sample and specific areas of interest. ~16 MB, ramped packet sizes.
AWB USB Dongle, simultaneous measurements with spectrum analyzer.
ESNR (upstream) and CINR (downstream) best correlation. CINR > 40 dB is a reasonable threshold.
LTE
Bidirectional 1minute TCP throughput test.
UE Tx Power, Path Loss, CQI
Downstream measurements noisy.
6 Public Data Sets
on
cu/antenna
cu/wart
cu/lte
cu/wimax
pdx/vwave
pdx/metrofi
Geostatistics developed for mine-valuation
Key observation: RF mapping not wholly dissimilar from mine valuation
Marriage of practical experience with robust statistical techniques
Removes guesswork, makes problem approachable by "average surveyor"
Measurements
Y Value Distribution
X Value Distribution
Overall Distribution
Friday, October 19th, 2012
IEEE DySPAN
Sampling
Grid*, "In Lines", Crowd-Sourced
Metrics
Physical-layer: CINR, ESNR**
Application-layer: TCP/UDP T-Put, PER
Ongoing Work & Extensions
Crowd sourced
measurement
Second-phase
sample (re)optimization
Questions?
caleb.phillips@colorado.edu
smallwhitecube.com/doku.php?id=thesis
Measure
Model
Interpolate
Map
Optimize
* EA Yfantis, GT Flatman, JV Behar. Efficiency of kriging estimation for square, triangular, and hexagonal grids. Mathematical Geology. 1987.
** D Halperin, W Hu, A Sheth, D Wetherall. Predictable 802.11 packet delivery from wireless channel measurements. ACM SigComm 2010.
?
Full transcript