Location, Localization, and Localizability (eBook)

Yunhao Liu received his BS degree in Automation Department from Tsinghua University, China, in 1995, and an MA degree in Beijing Foreign Studies University, China, in 1997, and an MS and a Ph.D. degree in Computer Science and Engineering at Michigan State University in 2003 and 2004, respectively. He is a member of Tsinghua National Lab for Information Science and Technology, and the Director of Tsinghua MOE Key Lab for Information Security. He is also a faculty at the Department of Computer Science and Engineering, the Hong Kong University of Science and Technology. He serves as Associate Editor of IEEE Transactions on Parallel and Distributed Systems and IEEE Transactions on Mobile Computing. He also serves as General Vice Chair of WWW 2008, area chair of ICDCS 2010, and PC member of a lot of top conferences such as MobiCom, INFOCOM, MOBIHOC, etc. Yunhao and his research group are awarded Best Paper Award or Best Paper Candidate in many conferences like PerCom 2007, MobiCom 2008, ICPADS 2009, and etc. He and his Phd student Li Mo won the Grand Prize of Hong Kong Best Innovation and Research Award in 2008. He is also the Vice Chair of ACM China Council. Zheng Yang received a Bachelor of Engineering degree in computer science from Tsinghua University in 2006 and a Ph.D. degree from Hong Kong University of Science and Technology (HKUST) in 2010. His main research interests include wireless ad-hoc/sensor networks and pervasive computing. He has worked on location-based services for over 4 years and published a number of research papers in prestigious journals and conferences, including IEEE/ACM Transactions on Networking (ToN), IEEE Transactions on Parallel and Distributed Systems (TPDS), IEEE INFOCOM, IEEE ICDCS, IEEE RTSS, ACM SenSys, etc. He is a member of the IEEE and the ACM.

Preface 7
Contents 11
Chapter 1: Introduction 15
1.1 Location-Based Services 15
1.1.1 Location-Based Applications 15
1.1.1.1 Motivating Example: GreenOrbs 16
1.1.2 Location-Aided Network Functions 18
1.1.2.1 Routing 18
1.1.2.2 Topology Control 18
1.1.2.3 Coverage 18
1.1.2.4 Boundary Detection 18
1.1.2.5 Clustering 19
1.2 Introduction to Localization 19
1.3 Book Organization 20
Chapter 2: Physical Measurements 23
2.1 Distance Measurements 23
2.1.1 Radio Signal Strength 23
2.1.2 Time of Arrival (ToA) 25
2.1.2.1 Symmetric Double Sided Two-Way Ranging (SDS-TWR) 27
2.1.2.2 BeepBeep 28
2.1.3 Time Difference of Arrival (TDoA) 32
2.2 Angle Measurement 33
2.3 Area Measurement 34
2.3.1 Single Reference Area Estimation 34
2.3.2 Multireference Area Estimation 35
2.4 Hop Count Measurements 36
2.5 Neighborhood Measurement 37
2.6 Summary 37
Chapter 3: One-Hop Location Estimation 40
3.1 Distance-Based Positioning Techniques 40
3.2 TDoA-Based Positioning Techniques 42
3.3 AoA-Based Positioning Techniques 44
3.4 RSS-Profiling-Based Positioning Techniques 46
3.4.1 Off-line Profiling Scheme 47
3.4.2 Online Profiling Scheme 47
Chapter 4: Range-Based Network localization 50
4.1 Computation Organization 50
4.2 Centralized Localization Approaches 51
4.2.1 Multidimensional Scaling (MDS) 51
4.2.2 Semidefinite Programming (SDP) 53
4.3 Distributed Localization Approaches 55
4.3.1 Beacon-based Localization 55
4.3.1.1 Iterative Trilateration 55
4.3.1.2 Finite Localization by Bilateration 56
4.3.2 Coordinate System Stitching 59
4.3.2.1 Local Map Stitching 59
4.3.2.2 Component Stitching 61
4.4 Summary 64
4.4.1 Beacon Nodes 64
4.4.2 Node Density 65
4.4.3 Accuracy 65
4.4.4 Cost 65
Chapter 5: Range-Free Network Localization 68
5.1 Basic Hop-Based Algorithms 68
5.1.1 DV-Hop 68
5.1.2 Amorphous 69
5.2 Improved Hop-Based Algorithms for Anisotropic Networks 69
5.2.1 PDM-Based Localization in Anisotropic Networks 69
5.2.2 Rendered Path in Networks with Holes 71
5.2.3 Delaunay-Complex-Based Localization 75
5.2.3.1 Basic Delaunay-Complex-Based Algorithm 77
5.2.3.2 Incremental Landmark Selection Scheme 78
5.3 Proximity-Based Algorithms 80
5.3.1 Point-in-Triangulation Test 80
5.3.2 Perpendicular Intersection 81
5.4 Relative Distance Estimation 83
5.5 Summary 86
Chapter6: Error Control 88
6.1 Measurement Errors 88
6.1.1 Errors in Distance Measurements 88
6.1.2 Negative Impact of Noisy Ranging Results 89
6.2 Error Characteristics 90
6.2.1 What is CRLB 90
6.2.2 CRLB for Multihop Localization 90
6.2.3 CRLB for One-Hop Localization 91
6.3 Localization 92
6.4 Location Refinement 95
6.4.1 A Framework of Location Refinement 96
6.4.2 Metrics for Location Refinement 96
6.5 Outlier-Resistant Localization 100
6.5.1 Explicitly Sifting 101
6.5.2 Implicitly De-emphasizing 105
6.6 Summary 109
Chapter 7: Localization for Mobile Networks 110
7.1 Overview 110
7.2 Monte Carlo Localization 111
7.2.1 Particle Filtering 111
7.2.2 Sequential Monte Carlo Localization 113
7.3 Convex Approximation Localization 115
7.4 Moving-Baseline Localization 118
7.4.1 Techniques for Universal Localization 122
Chapter 8: Localizability 123
8.1 Network Localizability 123
8.2 Graph Rigidity 124
8.2.1 Globally Rigid Graphs 124
8.2.2 Conditions for Network Localizability 126
8.3 Inductive Construction of Globally Rigid Graphs 127
8.3.1 Trilateration 127
8.3.2 Wheel 128
8.4 Node Localizability 133
8.5 Summary 141
Chapter 9: Location Privacy 142
9.1 Introduction 142
9.2 Threats 143
9.2.1 How Can the Adversary Obtain Location Information of Others? 143
9.2.2 What Is the Negative Consequence of a Location Leak? 143
9.3 Protection Strategies 144
9.3.1 Regulatory Approaches 144
9.3.2 Privacy Policies 145
9.3.3 Anonymity 146
9.3.4 Obfuscation 146
9.4 Anonymity-Based Approaches 147
9.4.1 k-Anonymity 148
9.4.2 Mix Zone 149
9.4.3 Using Dummies 151
9.4.4 Path Confusion 152
9.4.5 Comparison 154
9.5 Summary 155
References 157
Index 163