Introduction to Wireless Localization: With iPhone SDK Examples

Eddie C. L. Chan, Hong Kong University of Science and Technology, Hong Kong Eddie C. L. Chan received the B.Sc. degree, the M.Sc. degree and the Ph.D. degree, all in computer science from The Hong Kong Polytechnic University. He has won numerous awards during his postgraduate study, including the Best Student Paper Award in International Conference on Fuzzy Computation, Madeira, Portugal in 2009, Best Presentation Award of Research Project and Alan Turing scholarship from Poly U in 2007 and 2008, and the 2nd-Class Group Award from The 9th Philip Challenge Cup in China in 2005. His research interests include wireless communication, localization, fuzzy logic, 3D visualization of tracking system, agent technology and data mining. George Baciu, The Hong Kong Polytechnic University, Hong Kong George Baciu holds a PhD and a MSc degree in Systems Engineering and a B.Math degree in Computer Science and Applied Mathematics from the University of Waterloo. He has been a member of the Computer Graphics Laboratory and the Pattern Analysis and Machine Intelligence Laboratory at the University of Waterloo and subsequently Director of the Graphics And Music Experimentation Laboratory at The Hong Kong University of Science and Technology in Hong Kong. Currently, Dr. Baciu is Professor and Associate Head in the Department of Computing and the founding director of the Graphics And Multimedia Applications (GAMA) Laboratory at The Hong Kong Polytechnic University. His research interests are primarily in mobile augmented reality systems, user interfaces, physically-based illumination, rendering, image processing, motion tracking and synthesis for both outdoor and indoor location aware systems.

Preface xiii About the Authors xvii 1 Introduction toWireless Localization 1 1.1 Open Problems in Positioning Technologies 3 1.1.1 Inaccurate Positioning Algorithms 3 1.1.2 Unstable Wireless Signal Transmission 4 1.1.3 Unstructured WLAN Infrastructure 4 1.1.4 Lack of Signal Analytical Models 5 1.2 Factors Leading to Effective Positioning Systems 5 1.2.1 An Accurate Positioning Algorithm/Approach 6 1.2.2 A Stable WLAN Signal Transmission 6 1.2.3 A Structural WLAN Infrastructure 7 1.2.4 A Graphical Fuzzy Signal Visualization Model 7 1.2.5 A Location-aware Information Retrieval System 7 References 9 Part I: Wi-Fi Positioning Systems 2 Installation of Wi-Fi Infrastructure 13 2.1 What is the IEEE 802.11 Family? 14 2.2 Properties of Wi-Fi Signal Strength 15 2.2.1 Distribution of Wi-Fi Signal Strength 15 2.2.2 Large Value of Path Loss 17 2.2.3 Small Value of Path Loss 17 2.2.4 Behavior Study on the Human s Presence 18 2.3 Optimal Channel Allocation for Wi-Fi Positioning 19 2.3.1 Overlapping Channel Interference 20 2.3.2 Distribution of Channel Interference 21 2.3.3 Channel Assignment Schemes 23 2.4 Determining Number of APs to be Installed 24 2.4.1 Square Tessellation Installation 24 2.4.2 Z Factor 24 2.4.3 Environmental Factors 24 2.4.4 Number of Access Points Needed 25 2.5 Other Tessellation Installations 27 2.5.1 X and Y Factors 27 2.5.2 Environmental Factors 30 2.5.3 Determining Number of APs to be Installed 30 2.5.4 Summary of AP Deployment Approach 31 Reference 33 3 Algorithms Used in Wi-Fi Positioning Systems 35 3.1 Taxonomy of Indoor Positioning Techniques 36 3.2 Propagation-based Algorithms 37 3.2.1 Angle of Arrival (AOA) 38 3.2.2 Time of Arrival (TOA) 40 3.2.3 Phase of Arrival (POA) 42 3.2.4 Time Difference of Arrival (TDOA) 43 3.2.5 Roundtrip Time of Flight (RTOF) 46 3.3 Location-fingerprinting-based Algorithms 47 3.3.1 K-Nearest Neighbor Algorithms 47 3.3.2 Smallest M-vertex Polygon (SMP) 50 3.3.3 Neural Network 50 3.3.4 Support Vector Machine (SVM) 53 3.3.5 Probabilistic Algorithms 57 3.4 Evaluation of Positioning Techniques 58 3.4.1 Mean Square Error (MSE) 58 3.4.2 Cumulative Distribution Function (CDF) 59 3.4.3 Cram'er-Rao Lower Bound (CRLB) 59 3.4.4 Circular Error of Probable (CEP) 63 3.4.5 Geometric Dilution of Precision (GDOP) 65 3.5 Comparison of Indoor Positioning System 66 References 68 4 Implementation of Wi-Fi Positioning in iPhone 71 4.1 Site-surveying of Wi-Fi Signals Using iPhone 73 4.2 Implementing Location Fingerprinting Algorithm in iPhone 83 4.3 Orientation Filter 86 4.4 Newton Trust-Region Method 88 4.4.1 TR Subproblem 89 4.4.2 TR Fidelity 89 4.4.3 TR Radius 89 References 95 5 Positioning across Different Mobile Platform 97 5.1 Signal Strength Value Ratio Approach 98 5.1.1 Signal Strength Ratio 98 5.1.2 Log-normalized Signal Strength Ratio 99 5.1.3 K-NN Hyperbolic Location Fingerprinting 99 5.1.4 Probabilistic Hyperbolic Location Fingerprinting 100 5.2 Signal Strength Value Difference Approach 100 5.2.1 Signal Strength Value Difference 100 5.2.2 K-NN DIFF Location Fingerprinting 100 5.2.3 Probabilistic DIFF Location Fingerprinting 100 5.3 Fourier Descriptors Approach 101 5.3.1 Fourier Location Fingerprint 101 5.3.2 Example of Fourier Location Fingerprint 103 5.3.3 K-NN Fourier Location Fingerprinting 103 5.3.4 Probabilistic Fourier Location Fingerprinting 104 References 105 6 Wi-Fi Signal Visualization 107 6.1 Why Do We Need a Wi-Fi Visualization Tool? 107 6.2 Fuzzy Color Map 108 6.2.1 Fuzzy Membership Function 108 6.2.2 Fuzzy Spatio-temporal Cluster 109 6.3 Topographic Map 110 6.3.1 Topographic Node 110 6.3.2 Nelder-Mead Method 110 6.3.3 Topographic Model Generation 112 6.4 Signal Visualization Experiments and Results 113 6.4.1 Experimental Setup 113 6.4.2 Visualization Results 115 6.5 Refinement of Positioning Systems Based on Wi-Fi Visualization Result 118 References 120 Part II: Outdoor Positioning Systems 7 Introduction of Global Positioning System 123 7.1 History of GPS 124 7.2 Functions of GPS 125 7.3 Components of GPS 125 7.3.1 Space Segment 125 7.3.2 Control Segment 126 7.3.3 User Segment 127 7.3.4 Ground Segment 127 7.4 Types of GPS Receivers 127 7.5 Sources of Errors in GPS 128 7.5.1 Ephemeris Errors 128 7.5.2 Satellite Clock Errors 129 7.5.3 Receiver Errors 129 7.5.4 Atmospheric Errors 129 7.5.5 Multipath Interference 130 7.6 Precision of the GPS 131 7.6.1 Geometric Dilution of Precision (GDOP) 131 7.6.2 User Equivalent Range Error (UERE) 133 7.7 Coordinate Systems on the Earth 133 8 Study of GPS Signal and Algorithms 137 8.1 GPS Signals 137 8.1.1 Coarse Acquisition Code 138 8.1.2 Precision Code 138 8.1.3 Navigation Message 138 8.1.4 Navigation Message Format 139 8.2 Modernized GPS Signals 141 8.2.1 L2 Civil Signal (L2C) 142 8.2.2 L5 Signal 142 8.2.3 M Code 143 8.2.4 L1 Civil Signal (L1C) 143 8.3 GPS Absolute Point Determination 143 8.3.1 Trilateration Algorithm 143 8.3.2 What is Pseudorange? 146 8.3.3 Determining the Location 147 8.3.4 Determining the Location Using Linearization 148 8.4 Calculating User Velocity 153 9 Differential GPS and Assisted GPS 157 9.1 Types of DGPS 158 9.2 How DGPS Works 158 9.2.1 Real-time DGPS 158 9.2.2 Post-process DGPS 161 9.3 DGPS Navigation Message Format 161 9.3.1 RTCM SC-104 Version 2.3 162 9.3.2 RTCM SC-104 Version 3.0 164 9.4 Assisted GPS 166 9.5 AGPS in iPhone 167 9.5.1 Core Location Framework 168 9.5.2 Core Location 171 9.5.3 GPS Program in iPhone 173 9.5.4 Core Location Heading 176 9.5.5 Compass in iPhone 179 9.5.6 MapKit framework 180 10 Other Existing Positioning Systems 185 10.1 Acoustic-based Positioning 186 10.1.1 Active Acoustic Positioning 187 10.1.2 Passive Acoustic Positioning 187 10.1.3 What is Beamforming? 187 10.1.4 Applications of Acoustic Positioning 188 10.2 Vision-based Positioning 188 10.2.1 Camera-based Positioning 188 10.2.2 Landmark-based Positioning 190 10.2.3 Applications of Vision-based Positioning 192 10.3 What is RFID Technology and Its Components? 192 10.3.1 RFID Reader 193 10.3.2 RFID Tag 193 10.3.3 RFID Positioning 195 10.3.4 Applications of RFID Positioning 196 Part III: Applications in Wireless Localization 11 AI for Location-aware Applications 201 11.1 What is Location-aware Application? 202 11.2 What are AI Techniques? 204 11.2.1 Fuzzy Logic 205 11.2.2 Natural Language Processing 207 11.3 Example of the Tourist Guide Application 209 11.3.1 System Overview of the Tourist Guide Application 209 11.3.2 Applying Fuzzy Logic in the Tourist Guide Application 210 11.3.3 Building the Database Structure 211 11.3.4 Setting Up the Server Side in PHP 212 11.3.5 Setting Up the Client-side in iPhone 213 12 Beyond Positioning: Video Streaming and Conferencing 223 12.1 What is Video Streaming? 224 12.1.1 Point-to-point Video Streaming 224 12.1.2 Multicast Video Streaming 225 12.1.3 Broadcast Video Streaming 225 12.2 Networks and Formats in Video Streaming 225 12.3 How Does Video Streaming Work? 227 12.3.1 Traditional Video Streaming 228 12.3.2 Adaptive Video Streaming 228 12.4 Location-aware Video Streaming 229 12.4.1 Building the Location-Based Bandwidth Lookup Database 230 12.4.2 Location-based Bit-rate and Quality Monitoring 231 12.5 What is Video Conferencing? 231 12.6 Implementation of Video Streaming in iPhone 233 12.7 Implementation of Video Conferencing in iPhone 241 Appendix A Starting the iOS SDK 245 A.1 Getting the iOS SDK 246 A.2 What Can You Create Using iOS SDK? 248 A.2.1 What Tools Are in the iOS SDK? 248 A.2.2 Apple Developer Center 249 A.3 Limitations of iPhone Environment 250 A.4 Introduction to Xcode 251 A.4.1 Xcode Project Template 253 A.4.2 Xcode Project Summary 253 A.5 Xcode Project Interface 254 A.5.1 Toolbar 255 A.5.2 Navigation Area 256 A.5.3 Editor Area 257 A.5.4 Debug Area 257 A.5.5 Utility Area 258 Appendix B Introduction to Objective-C Programming in iPhone 261 B.1 Objective-C Program, HelloWorld 262 B.1.1 Using Xcode to Code and Compile Programs 263 B.1.2 What is #import? 265 B.1.3 What is Main? 266 B.1.4 Automatic Reference Counting (ARC) 266 B.1.5 What is NSLog()? 266 B.2 Object-Oriented Programming (OOP) 266 B.2.1 Infix Notation 268 B.2.2 The @Interface Section 269 B.2.3 The @Implementation Section 270 B.2.4 The Program Section 271 B.2.5 @property, @synthesize and @dynamic 272 B.2.6 @property in the @interface Section 273 B.2.7 @synthesize in the @implementation Section 274 B.2.8 @dynamic in the @implementation Section 275 B.2.9 Dot Notation 275 B.2.10 Category 275 B.3 HelloWorld iPhone Application 278 B.3.1 Using Interface Builder 279 B.3.2 Creating User Interface by Click-dragging Processes 281 B.4 Creating Your Web Browser in iPhone 282 B.5 Creating a Simple Map Application 287 B.5.1 Map Function from MapKit Frameworks 289 B.5.2 Locate Yourself and Shift Center View in the Map 291 B.5.3 Translate and Zoom by MKCoordinateRegion Class 291 B.5.4 Switch from Satellite Map to Standard Street Map 292 B.5.5 UISlider Item Handles Zoom Events 294 B.5.6 Switches Web Browser and Simple Map Application 298 Index 305