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 Reuse
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/wifilightpainting
www.verizonwireless.com
www.ntia.doc.gov/files/ntia/publications/2003allochrt.pdf
Harrison, K. How Much WhiteSpace Capacity Is There? IEEE DySPAN 2010.
www.nytimes.com/2012/02/15/business/media/fccbarsairwaveuseforbroadbandplan.html
Robinson, Swaminathan, and Knightly. Assessment of UrbanScale Wireless Networks with a Small Number of Measurements. ACM MobiCom 2008.
www.fiercewireless.com/story/photosridingshotgunverizonnetworktester/20110617
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 measurementbased 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 datafitting approaches

Richer maps
than heuristic sampleminimizing
approaches w/ same accuracy and efficiency
 First practical investigation of
crowdsourced
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 aOK
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. 19982011.
www.bisolutions.us/ABriefIntroductiontoSpatialInterpolation.php
Hybridization: Measurementcorrected 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
~46 dB RMSE depending on metric used
Sample: 100m Equilateral Triangular Lattice
Sample: 100m Equilateral Triangular Lattice
3 WiFi DriveTest Datasets:
Google Mountain View
Rice/TFA Houston
MetroFi Portland
Several Hundred Unique APs
Resampled at multiple lags
50100m performs best
Packetbased measurements with
commodity hardware
Overall RMSE 510dB depending on site, and resampling density.
Achieves same holeprediction
accuracy as Robinson's method with an the same number of samples.
Open Signal Maps CrowdSourced Data Collection w/Android Phones
www.opensignalmaps.net
587 distinct BSs, 11257
measurements each
190 distinct devices
performing measurement
Datasparse (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 multiphase 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. Secondphase sampling designs for nonstationary spatial variables. Geoderma. Volume 153. 2009. 205216.
Kriging Variance
Roughness
Roughnessweighed 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
12 orders of magnitude
smaller RMSE
than simple data fitting and modeling approaches
Error approaching expected repeated measures variance*
Same
efficiency
as sampleminimizing 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.
PostDefense 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. 183205.
*Rizk, Wagen, and Gardiol. Twodimensional raytracing modeling for propagation prediction in microcellular environments. IEEE Trans. on Vehicular Technology. 1997. Volume 46. 508518.
**J Robinson, R Swaminathan, and E Knightly. Assessment of an Urbanscale 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
10fold 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
Crowdsourced measurements
1.9 GHz
Metric KVar RMSE
Gain
Accuracy
CU WiMax CINR 24 24
918
~70%
ESNR 511 611
2.58
~70%
Verizon LTE SNR 46 45.5
0.42.5
Urban WiFi SNR 46 310
0.52.5
8090%
AT&T GSM SNR 5.5 4
8.8
8590%
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 minevaluation
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", CrowdSourced
Metrics
Physicallayer: CINR, ESNR**
Applicationlayer: TCP/UDP TPut, PER
Ongoing Work & Extensions
Crowd sourced
measurement
Secondphase
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.
?
Present Remotely
Send the link below via email or IM
CopyPresent 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.
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.