Introduction to Wireless Localization

Eddie C. L. Chan, Hong Kong University of Science and Technology, Hong KongEddie 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 KongGeorge 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 xvii1 Introduction toWireless Localization 11.1 Open Problems in Positioning Technologies 31.1.1 Inaccurate Positioning Algorithms 31.1.2 Unstable Wireless Signal Transmission 41.1.3 Unstructured WLAN Infrastructure 41.1.4 Lack of Signal Analytical Models 51.2 Factors Leading to Effective Positioning Systems 51.2.1 An Accurate Positioning Algorithm/Approach 61.2.2 A Stable WLAN Signal Transmission 61.2.3 A Structural WLAN Infrastructure 71.2.4 A Graphical Fuzzy Signal Visualization Model 71.2.5 A Location-aware Information Retrieval System 7References 9Part I: Wi-Fi Positioning Systems2 Installation of Wi-Fi Infrastructure 132.1 What is the IEEE 802.11 Family? 142.2 Properties of Wi-Fi Signal Strength 152.2.1 Distribution of Wi-Fi Signal Strength 152.2.2 Large Value of Path Loss 172.2.3 Small Value of Path Loss 172.2.4 Behavior Study on the Human’s Presence 182.3 Optimal Channel Allocation for Wi-Fi Positioning 192.3.1 Overlapping Channel Interference 202.3.2 Distribution of Channel Interference 212.3.3 Channel Assignment Schemes 232.4 Determining Number of APs to be Installed 242.4.1 Square Tessellation Installation 242.4.2 Z Factor 242.4.3 Environmental Factors 242.4.4 Number of Access Points Needed 252.5 Other Tessellation Installations 272.5.1 X and Y Factors 272.5.2 Environmental Factors 302.5.3 Determining Number of APs to be Installed 302.5.4 Summary of AP Deployment Approach 31Reference 333 Algorithms Used in Wi-Fi Positioning Systems 353.1 Taxonomy of Indoor Positioning Techniques 363.2 Propagation-based Algorithms 373.2.1 Angle of Arrival (AOA) 383.2.2 Time of Arrival (TOA) 403.2.3 Phase of Arrival (POA) 423.2.4 Time Difference of Arrival (TDOA) 433.2.5 Roundtrip Time of Flight (RTOF) 463.3 Location-fingerprinting-based Algorithms 473.3.1 K-Nearest Neighbor Algorithms 473.3.2 Smallest M-vertex Polygon (SMP) 503.3.3 Neural Network 503.3.4 Support Vector Machine (SVM) 533.3.5 Probabilistic Algorithms 573.4 Evaluation of Positioning Techniques 583.4.1 Mean Square Error (MSE) 583.4.2 Cumulative Distribution Function (CDF) 593.4.3 Cram`er-Rao Lower Bound (CRLB) 593.4.4 Circular Error of Probable (CEP) 633.4.5 Geometric Dilution of Precision (GDOP) 653.5 Comparison of Indoor Positioning System 66References 684 Implementation of Wi-Fi Positioning in iPhone 714.1 Site-surveying of Wi-Fi Signals Using iPhone 734.2 Implementing Location Fingerprinting Algorithm in iPhone 834.3 Orientation Filter 864.4 Newton Trust-Region Method 884.4.1 TR Subproblem 894.4.2 TR Fidelity 894.4.3 TR Radius 89References 955 Positioning across Different Mobile Platform 975.1 Signal Strength Value Ratio Approach 985.1.1 Signal Strength Ratio 985.1.2 Log-normalized Signal Strength Ratio 995.1.3 K-NN Hyperbolic Location Fingerprinting 995.1.4 Probabilistic Hyperbolic Location Fingerprinting 1005.2 Signal Strength Value Difference Approach 1005.2.1 Signal Strength Value Difference 1005.2.2 K-NN DIFF Location Fingerprinting 1005.2.3 Probabilistic DIFF Location Fingerprinting 1005.3 Fourier Descriptors Approach 1015.3.1 Fourier Location Fingerprint 1015.3.2 Example of Fourier Location Fingerprint 1035.3.3 K-NN Fourier Location Fingerprinting 1035.3.4 Probabilistic Fourier Location Fingerprinting 104References 1056 Wi-Fi Signal Visualization 1076.1 Why Do We Need a Wi-Fi Visualization Tool? 1076.2 Fuzzy Color Map 1086.2.1 Fuzzy Membership Function 1086.2.2 Fuzzy Spatio-temporal Cluster 1096.3 Topographic Map 1106.3.1 Topographic Node 1106.3.2 Nelder-Mead Method 1106.3.3 Topographic Model Generation 1126.4 Signal Visualization Experiments and Results 1136.4.1 Experimental Setup 1136.4.2 Visualization Results 1156.5 Refinement of Positioning Systems Based on Wi-Fi Visualization Result 118References 120Part II: Outdoor Positioning Systems7 Introduction of Global Positioning System 1237.1 History of GPS 1247.2 Functions of GPS 1257.3 Components of GPS 1257.3.1 Space Segment 1257.3.2 Control Segment 1267.3.3 User Segment 1277.3.4 Ground Segment 1277.4 Types of GPS Receivers 1277.5 Sources of Errors in GPS 1287.5.1 Ephemeris Errors 1287.5.2 Satellite Clock Errors 1297.5.3 Receiver Errors 1297.5.4 Atmospheric Errors 1297.5.5 Multipath Interference 1307.6 Precision of the GPS 1317.6.1 Geometric Dilution of Precision (GDOP) 1317.6.2 User Equivalent Range Error (UERE) 1337.7 Coordinate Systems on the Earth 1338 Study of GPS Signal and Algorithms 1378.1 GPS Signals 1378.1.1 Coarse Acquisition Code 1388.1.2 Precision Code 1388.1.3 Navigation Message 1388.1.4 Navigation Message Format 1398.2 Modernized GPS Signals 1418.2.1 L2 Civil Signal (L2C) 1428.2.2 L5 Signal 1428.2.3 M Code 1438.2.4 L1 Civil Signal (L1C) 1438.3 GPS Absolute Point Determination 1438.3.1 Trilateration Algorithm 1438.3.2 What is Pseudorange? 1468.3.3 Determining the Location 1478.3.4 Determining the Location Using Linearization 1488.4 Calculating User Velocity 1539 Differential GPS and Assisted GPS 1579.1 Types of DGPS 1589.2 How DGPS Works 1589.2.1 Real-time DGPS 1589.2.2 Post-process DGPS 1619.3 DGPS Navigation Message Format 1619.3.1 RTCM SC-104 Version 2.3 1629.3.2 RTCM SC-104 Version 3.0 1649.4 Assisted GPS 1669.5 AGPS in iPhone 1679.5.1 Core Location Framework 1689.5.2 Core Location 1719.5.3 GPS Program in iPhone 1739.5.4 Core Location Heading 1769.5.5 Compass in iPhone 1799.5.6 MapKit framework 18010 Other Existing Positioning Systems 18510.1 Acoustic-based Positioning 18610.1.1 Active Acoustic Positioning 18710.1.2 Passive Acoustic Positioning 18710.1.3 What is Beamforming? 18710.1.4 Applications of Acoustic Positioning 18810.2 Vision-based Positioning 18810.2.1 Camera-based Positioning 18810.2.2 Landmark-based Positioning 19010.2.3 Applications of Vision-based Positioning 19210.3 What is RFID Technology and Its Components? 19210.3.1 RFID Reader 19310.3.2 RFID Tag 19310.3.3 RFID Positioning 19510.3.4 Applications of RFID Positioning 196Part III: Applications in Wireless Localization11 AI for Location-aware Applications 20111.1 What is Location-aware Application? 20211.2 What are AI Techniques? 20411.2.1 Fuzzy Logic 20511.2.2 Natural Language Processing 20711.3 Example of the Tourist Guide Application 20911.3.1 System Overview of the Tourist Guide Application 20911.3.2 Applying Fuzzy Logic in the Tourist Guide Application 21011.3.3 Building the Database Structure 21111.3.4 Setting Up the Server Side in PHP 21211.3.5 Setting Up the Client-side in iPhone 21312 Beyond Positioning: Video Streaming and Conferencing 22312.1 What is Video Streaming? 22412.1.1 Point-to-point Video Streaming 22412.1.2 Multicast Video Streaming 22512.1.3 Broadcast Video Streaming 22512.2 Networks and Formats in Video Streaming 22512.3 How Does Video Streaming Work? 22712.3.1 Traditional Video Streaming 22812.3.2 Adaptive Video Streaming 22812.4 Location-aware Video Streaming 22912.4.1 Building the Location-Based Bandwidth Lookup Database 23012.4.2 Location-based Bit-rate and Quality Monitoring 23112.5 What is Video Conferencing? 23112.6 Implementation of Video Streaming in iPhone 23312.7 Implementation of Video Conferencing in iPhone 241Appendix A Starting the iOS SDK 245A.1 Getting the iOS SDK 246A.2 What Can You Create Using iOS SDK? 248A.2.1 What Tools Are in the iOS SDK? 248A.2.2 Apple Developer Center 249A.3 Limitations of iPhone Environment 250A.4 Introduction to Xcode 251A.4.1 Xcode Project Template 253A.4.2 Xcode Project Summary 253A.5 Xcode Project Interface 254A.5.1 Toolbar 255A.5.2 Navigation Area 256A.5.3 Editor Area 257A.5.4 Debug Area 257A.5.5 Utility Area 258Appendix B Introduction to Objective-C Programming in iPhone 261B.1 Objective-C Program, HelloWorld 262B.1.1 Using Xcode to Code and Compile Programs 263B.1.2 What is #import? 265B.1.3 What is Main? 266B.1.4 Automatic Reference Counting (ARC) 266B.1.5 What is NSLog()? 266B.2 Object-Oriented Programming (OOP) 266B.2.1 Infix Notation 268B.2.2 The @Interface Section 269B.2.3 The @Implementation Section 270B.2.4 The Program Section 271B.2.5 @property, @synthesize and @dynamic 272B.2.6 @property in the @interface Section 273B.2.7 @synthesize in the @implementation Section 274B.2.8 @dynamic in the @implementation Section 275B.2.9 Dot Notation 275B.2.10 Category 275B.3 HelloWorld iPhone Application 278B.3.1 Using Interface Builder 279B.3.2 Creating User Interface by Click-dragging Processes 281B.4 Creating Your Web Browser in iPhone 282B.5 Creating a Simple Map Application 287B.5.1 Map Function from MapKit Frameworks 289B.5.2 Locate Yourself and Shift Center View in the Map 291B.5.3 Translate and Zoom by MKCoordinateRegion Class 291B.5.4 Switch from Satellite Map to Standard Street Map 292B.5.5 UISlider Item Handles Zoom Events 294B.5.6 Switches Web Browser and Simple Map Application 298Index 305