Send the link below via email or IMCopy
Present to your audienceStart 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
Transcript of DySPAN 2012
Mapping with Geostatistics
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)
Relative Constellation Error (RCE)
Error Vector Magnitude (EVM)
Application Layer Metrics
Bit Error Rate
Packet Error Rate
Wireless networks are everywhere
yet, we don't have good methods for
saying how well they
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.
in the right spots
and red in the
A "Krigian" Approach to Wireless
Harrison, K. How Much White-Space Capacity Is There? IEEE DySPAN 2010.
Robinson, Swaminathan, and Knightly. Assessment of Urban-Scale Wireless Networks with a Small Number of Measurements. ACM MobiCom 2008.
The need for greater
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:
- First practical application of
the radio environment
than is possible with
existing a priori modeling methods or
common data-fitting approaches
than heuristic sample-minimizing
approaches w/ same accuracy and efficiency
- First practical investigation of
using real data
- First application of
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.
A random field named 'Z'
Our friend, the semivariogram
Fitting the semivariogram model
Cubic & Gaussian
Ordinary Kriging is a-OK
Wellens, Riihijarvi, and Mahonen. Spatial statistics and models of spectrum use. Computer Communications. 2009. 32. 1998-2011.
Hybridization: Measurement-corrected modeling
Z'(x) - Model Error
Z(x) - Map
CU WiMax "4G"
Verizon LTE "4G"
Urban Mesh WiFi
AT&T GSM "3G"
Case Studies & Performance Evaluation
5 BSs on 4 channels
WiMax @ 2.5 GHz
~ 4 dB RMSE, 70% hole prediction accuracy
AT&T LTE @ 700 MHz
LG LTE Dongle &
11 BSs with ~3
~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
Several Hundred Unique APs
Resampled at multiple lags
50-100m performs best
Packet-based measurements with
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
587 distinct BSs, 1-1257
190 distinct devices
Data-sparse (only 13 unique
devices mapping central
~4dB RMSE, but too
little data for strong
Modeling CU campus: 4.2% of students participating could exhaustively map the campus in 24 hours.
Experiments in Simulated Mobility using SLAW
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.
Roughness-weighed Kriging Variance
Tractable solutions to an intractable problem
Parallel Spatial Simulated Annealing
A momentary digression on how friggin' amazing computers are
1,040,000 compute hours
118 years, 255 days
Case Study - Geni WiMax Node at CU Boulder
Modest ~0.5 dB RMSE Gain
3 phases w/ N = 10,25, & 50 points
, statistically robust coverage mapping
1-2 orders of magnitude
than simple data fitting and modeling approaches
Error approaching expected repeated measures variance*
as sample-minimizing heuristic approaches**
First application of
to real coverage mapping
schemes adapted from medical imaging, and new map combining and tiling mechanisms
But wait...there's more
Under review at Science :)
Submissions in progress to IEEE INFOCOM 2013,
IEEE TMC, and IEEE DySPAN 2013 on the work
Many open doors in the realm of wireless
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.
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
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
Metric K-Var RMSE
CU WiMax CINR 2-4 2-4
ESNR 5-11 6-11
Verizon LTE SNR 4-6 4-5.5
Urban WiFi SNR 4-6 3-10
AT&T GSM SNR 5.5 4
Frame & Figure Graveyard
As with mining, intuition doesn't always work
Correlations between Metrics
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.
Bidirectional 1minute TCP throughput test.
UE Tx Power, Path Loss, CQI
Downstream measurements noisy.
6 Public Data Sets
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"
Y Value Distribution
X Value Distribution
Friday, October 19th, 2012
Grid*, "In Lines", Crowd-Sourced
Physical-layer: CINR, ESNR**
Application-layer: TCP/UDP T-Put, PER
Ongoing Work & Extensions
* 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.