Introduction to Wireless Localization

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