Human Activity Detection using Smartphones and Maps BY LEON O. STENNETH B.Sc (University of Technology, Jamaica) 2003 M.Sc (University of Westminster, London, UK) 2004 THESIS Submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy in Computer Science in the Graduate College of the University of Illinois at Chicago, 2013 Chicago, Illinois Defense Committee: Professor Ouri Wolfson, Computer Science, Chair and Advisor Professor Philip Yu, Computer Science, Co-advisor Professor Prasad Sistla, Computer Science Professor Jane Lin, Civil and Materials Engineering Dr. Dr. Bo Xu, Argonne National Laboratory This thesis is dedicated to my family without whom it would have never been accomplished. ii ACKNOWLEDGEMENTS My first debt of gratitude goes to my advisers Professor Ouri Wolfson and Professor Philip Yu. They have provided skillful guidance that helped me accomplish my research goals. They have been very supportive since I commenced the PhD program. I cannot thank them enough for their hard work, fruitful comments, and diligence. Thank you Professor Wolfson and Professor Yu. I would like to give wholehearted thanks to my examination committee inclusive of Professor Jane Lin, Professor Prasad Sistla, and Dr. Dr. Bo Xu. I am honored to have such dynamic committee who provides significant comments and suggestions that improve the research. I would also like to thank my family, coworkers, friends, and everyone who supported me through this dissertation. Without their support this dissertation would not exist. Finally, I would like to thank the National Science Foundation (NSF) and Fulbright for their generous funding support. LS iii iv TABLE OF CONTENTS 1. INTRODUCTION ........................................................................................................................ 1 1.2 Background and Scope .............................................................................................................. 2 1.3 Technical challenges ................................................................................................................. 4 1.3.1 Energy and memory constraints on mobile phones: ......................................................... 4 1.3.2 Transportation mode activity detection: ............................................................................ 5 1.3.3 Parking status detection .................................................................................................... 5 1.3.4 Parking availability estimation: ........................................................................................ 7 1.3.5 Privacy aware mobile sensing: .......................................................................................... 7 1.4 Methodology ............................................................................................................................. 8 1.5 Contributions of work ............................................................................................................... 9 1.5.1 Outdoor mobile sensing .................................................................................................. 10 1.5.2 Indoor and outdoor mobile sensing ................................................................................. 11 1.5.3 Parking status detection .................................................................................................. 11 1.5.4 Street parking availability estimation.............................................................................. 13 1.5.5 Privacy-aware mobile sensing ........................................................................................ 13 1.6 Applications ............................................................................................................................ 14 2. LITERATURE REVIEW ........................................................................................................... 19 2.2 Activity detection .................................................................................................................... 19 2.2.1 Commercial devices ........................................................................................................ 19 2.2.2 Custom hardware ............................................................................................................ 20 2.2.3 Mobile phones ................................................................................................................. 21 2.3 Street parking status detection and availability estimation ..................................................... 24 2.4 Privacy aware mobile sensing ................................................................................................. 26 2.4.1 Snapshot queries ............................................................................................................. 26 2.4.2 Continuous query ............................................................................................................ 29 3. METHODOLOGY ..................................................................................................................... 31 3.2 Summary of general model ..................................................................................................... 31 3.3 Smartphone sensors................................................................................................................. 32 3.3.1 Accelerometer sensor ...................................................................................................... 33 3.3.2 GPS sensor ...................................................................................................................... 33 3.3.3 Bluetooth Sensor ............................................................................................................. 33 3.3.4 Smartphone sensor reports .............................................................................................. 34 3.4 Geospatial data (transportation network) ................................................................................ 35 3.4.1 Real time bus location ..................................................................................................... 35 3.4.2 Bus Stops ........................................................................................................................ 36 3.4.3 Rail Lines ........................................................................................................................ 36 3.5 Supervised machine learning model for activity detection ..................................................... 37 3.6 Street parking .......................................................................................................................... 38 4. OUTDOOR ACTIVITY DETECTION ...................................................................................... 40 4.2 The GPS and GIS model for outdoor activity detection ......................................................... 41 4.3 Classification features for outdoor transportation mode sensing ............................................ 42 4.3.1 Average accuracy of GPS coordinates ............................................................................ 43 v TABLE OF CONTENTS (continued) 4.3.2 Average speed ................................................................................................................. 43 4.3.3 Average heading change ................................................................................................. 44 4.3.4 Average acceleration ....................................................................................................... 44 4.3.5 Bus location closeness .................................................................................................... 45 4.3.6 Average bus closeness (ABC) ......................................................................................... 45 4.3.7 Candidate bus closeness (CBC) ...................................................................................... 46 4.3.8 Rail line trajectory closeness ........................................................................................... 46 4.3.9 Bus stop closeness rate .................................................................................................... 47 4.4 The application environment .................................................................................................. 48 4.5 GPS data preprocessing .......................................................................................................... 50 4.6 Spatial indexing....................................................................................................................... 50 4.6.1 Spatial index performance evaluation ............................................................................. 51 4.7 Evaluation of GPS and GIS model.......................................................................................... 53 4.7.1 Classification without transportation network ................................................................ 53 4.7.2 Classification with Transportation network .................................................................... 55 4.7.3 Extended real world evaluation of the deployed system ................................................. 57 4.7.4 Discussion ....................................................................................................................... 59 4.7.5 Relevant work ................................................................................................................. 60 5. INDOOR AND OUTDOOR ACTIVITY DETECTION ............................................................ 63 5.2 Sensor selection and transportation network ........................................................................... 65 5.2.1 Sensors ............................................................................................................................ 65 5.2.2 Transportation Network .................................................................................................. 67 5.3 General algorithm ................................................................................................................... 67 5.4 Classification feature extraction .............................................................................................. 68 5.5 Architecture for indoor and outdoor transportation mode detection ....................................... 72 5.6 Mobile device position ............................................................................................................ 73 5.7 Evaluation by experiments ...................................................................................................... 78 5.7.1 Experimental setup and sensor data collection ............................................................... 78 5.7.2 Classifier Selection ......................................................................................................... 80 5.8 Results ..................................................................................................................................... 82 5.8.1 Indoor transportation mode detection ............................................................................. 83 5.8.2 Outdoor transportation mode detection ........................................................................... 87 5.8.3 Indoor and outdoor transportation mode detection ......................................................... 89 5.8.4 Mobile phones with GPS or accelerometer turned off .................................................... 91 5.8.5 Battery power consumption ............................................................................................ 93 5.9 Limitations of study ................................................................................................................ 95 5.10 Discussion ........................................................................................................................... 95 5.11 Relevant work ..................................................................................................................... 97 6. PARKING STATUS DETECTION (PSD) .............................................................................. 100 6.2 Parking status detection ........................................................................................................ 100 6.2.1 Connection to in-vehicle Bluetooth .............................................................................. 101 6.2.2 Transportation mode monitoring .................................................................................. 102 vi TABLE OF CONTENTS (continued) 6.2.3 Pay-by-phone Piggyback .............................................................................................. 105 6.3 Energy conservation study .................................................................................................... 106 6.4 Parking and deparking detection accuracy ............................................................................ 107 6.4.1 Automated parking detection accuracy ......................................................................... 107 6.4.2 Unparking or deparking detection accuracy ................................................................. 108 6.5 Relevant work ....................................................................................................................... 111 7. PARKING AVAILABILITY ESTIMATION (PAE) ............................................................... 113 7.2 Overview of parking availability estimation ......................................................................... 114 7.3 Constructing Historical Profiles ............................................................................................ 117 7.3.1 Historical Availability Profile ....................................................................................... 117 7.3.2 HAP Construction Algorithm ....................................................................................... 118 7.3.3 Computation of Confidence .......................................................................................... 119 7.3.4 Assumptions .................................................................................................................. 120 7.4 Parking Availability Estimation algorithms .......................................................................... 123 7.4.1 Historical Statistics (HS) ............................................................................................... 124 7.4.2 Scaled PhonePark (SPP) ............................................................................................... 124 7.4.3 Weighted Average (WA) .............................................................................................. 124 7.4.4 Kalman Filter (KF)........................................................................................................ 125 7.5 Evaluation by Simulations .................................................................................................... 126 7.6 Evaluation of HAP ................................................................................................................ 129 7.6.1 Tuning-up Weighted-Average (WA) ............................................................................ 132 7.7 Comparison of HS, SPP, WA, and KF ................................................................................. 133 7.8 Comparison of RMSE ........................................................................................................... 135 7.9 Comparison on Boolean availability accuracy ...................................................................... 136 7.10 Relevant work ................................................................................................................... 138 7.11 Discussion ......................................................................................................................... 140 8. PRIVACY AWARE MOBILE SENSING ............................................................................... 142 8.2 Preliminaries ......................................................................................................................... 145 8.2.1 Formal definitions ......................................................................................................... 145 8.3 Requirements ........................................................................................................................ 146 8.4 System architecture ............................................................................................................... 148 8.4.1 Mobile device (clients) .................................................................................................. 148 8.4.2 Anonymization server (AS) .......................................................................................... 148 8.4.3 Secure communication service ...................................................................................... 149 8.4.4 Service provider (LBS) ................................................................................................. 149 8.4.5 Operation flow .............................................................................................................. 149 8.5 Threat model and adversary’s knowledge ............................................................................. 150 8.5.1 Count (R) ...................................................................................................................... 151 8.5.2 Lookup (lat, lon) ........................................................................................................... 151 8.5.3 Intersect (R , R , R , R … R , R ).............................................................................. 151 1 2 3 4 n-1 n 8.6 Dummy requests ................................................................................................................... 151 8.6.1 Dummy profile .............................................................................................................. 152 vii TABLE OF CONTENTS (continued) 8.6.2 Dummy diversity........................................................................................................... 156 8.7 Query privacy in MobiPriv implies location privacy ............................................................ 157 8.7.1 Proof that query privacy implies location privacy for type 1 queries ........................... 158 8.8 MobiPriv: System overview .................................................................................................. 159 8.8.1 Mobile request............................................................................................................... 161 8.8.2 Transformation and mapping function .......................................................................... 162 8.9 Algorithms ............................................................................................................................ 162 8.9.1 CloakLessK ................................................................................................................... 163 8.9.2 CloakedK ...................................................................................................................... 164 8.10 Complexity analysis discussion ........................................................................................ 165 8.11 Proof of correctness for MobiPriv in snapshot queries ..................................................... 166 8.12 Evaluation ......................................................................................................................... 167 8.12.1 Evaluation criteria ..................................................................................................... 168 8.13 Experimental setup and road network ............................................................................... 170 8.14 Experimental results .......................................................................................................... 172 8.14.1 High privacy requirement and high spatial tolerance................................................ 172 8.14.2 Lower privacy requirement and high spatial tolerance ............................................. 175 8.14.3 Lower privacy requirement and low spatial tolerance .............................................. 177 8.14.4 Privacy and Quality of Service (spatial tolerance) .................................................... 181 8.15 Continuous queries ............................................................................................................ 183 8.15.1 Query linking in continuous queries ......................................................................... 183 8.15.2 Discussion on K and K ................................................................................... 185 global local 8.15.3 MobiPriv prevents corollary history attacks ............................................................. 185 8.15.4 Proof of correctness for continuous queries .............................................................. 187 8.15.5 Resilience in continuous queries ............................................................................... 188 8.15.6 Resilience across snapshots....................................................................................... 189 8.15.7 Resilience and Quality of Service (spatial tolerance) ............................................... 190 8.15.8 Resilience and global privacy requirement ............................................................... 191 8.16 CloakLessK and CloakedK ............................................................................................... 192 8.17 Discussion ......................................................................................................................... 193 9. CONCLUSION AND FUTURE WORK.................................................................................. 195 10. CITED LITERATURE ............................................................................................................. 199 CURICULUM VITAE ....................................................................................................................... 206 viii LIST OF FIGURES Figure 1-Central server model for activity detection .............................................................................. 4 Figure 2- Fine granularity of bus mode detection ................................................................................ 16 Figure 3- Map of street parking availability ......................................................................................... 17 Figure 4-Map of street parking availability .......................................................................................... 18 Figure 5 – Classification examples ....................................................................................................... 38 Figure 6-Components of the PhonePark system................................................................................... 39 Figure 7 - GPS/GIS activity detection model ....................................................................................... 42 Figure 9-Spatial index performance ..................................................................................................... 52 Figure 10-Transportation network features not considered. ................................................................. 54 Figure 12-Deployed classification system ............................................................................................ 57 Figure 14- Classification examples ...................................................................................................... 68 Figure 15- Accelerometer raw data sampled at 50 times/second. Vertical dimension is y. ................. 69 Figure 16- System architecture (centralized model) ............................................................................. 72 Figure 17- mobile device in bag (x axis readings) ............................................................................... 74 Figure 18 - mobile device in bag (y axis readings) .............................................................................. 75 Figure 19-mobile device in bag (z axis readings) ................................................................................. 75 Figure 20-mobile device in front pocket (x axis readings) ................................................................... 76 Figure 21-mobile device in front pocket (y axis readings) ................................................................... 76 Figure 22-mobile device in front pocket (z axis readings) ................................................................... 77 Figure 23-mobile device on waist (x axis readings) ............................................................................. 77 Figure 24-mobile device on waist (y axis readings) ............................................................................. 78 Figure 25 – mobile device on waist (z axis readings) .......................................................................... 78 ix LIST OF FIGURES (continued) Figure 26-Data distribution .................................................................................................................. 80 Figure 27- Battery power consumption and sensor usage (Apple’s IPhone 3G) ................................. 94 Figure 28- Parking detection using Bluetooth connection between phone and car ............................ 101 Figure 29-Parking finite state machine ............................................................................................... 103 Figure 30-Simplified parking/deparking detection based on transportation mode transitions ........... 105 Figure 31-Parking status detection by pay by phone piggyback ........................................................ 106 Figure 31- Parking detection accuracy ............................................................................................... 107 Figure 32-unparking or deparking detection accuracy ....................................................................... 109 Figure 33- PSD generates spatial and temporal parking and deparking reports ................................. 110 Figure 34-PSD generates spatial and temporal parking and deparking reports .................................. 110 Figure 35-Components of the PhonePark estimation system ............................................................. 115 Figure 36-Street blocks considered for PAE evaluation .................................................................... 127 Figure 37-RMSE of HAP, b=1%, Polk St. ......................................................................................... 130 Figure 38-RMSE of HAP, b=50%, Polk St. ....................................................................................... 131 Figure 39-RMSE of HAP, b=1%, Chestnut St. .................................................................................. 131 Figure 40-RMSE of HAP, b=50%, Chestnut St. ................................................................................ 132 Figure 41-Determining weight (WHS) for WA ................................................................................. 133 Figure 42-RMSE of PAE algorithms, b=1%, Polk St. ....................................................................... 134 Figure 43-RMSE of PAE algorithms, b=50%, Polk St. ..................................................................... 134 Figure 44-RMSE of PAE algorithms, b=1%, Chestnut St. ................................................................ 135 Figure 45 - RMSE of PAE algorithms, b=50%, Chestnut St. ............................................................ 135 Figure 46-Boolean availability accuracy, b=1%, Polk St. .................................................................. 137 x