TL;DR
This paper proposes a vision for a ubiquitous indoor positioning system (IPS) that leverages crowd-sourced data from smartphone sensors to automatically build a worldwide floor plan database. The core contribution is demonstrating the feasibility of this approach, particularly in automatically constructing floor plans and identifying areas of interest with high accuracy, paving the way for seamless indoor-outdoor navigation and location-aware applications.
What Problem Does This Paper Address?
While GPS is ubiquitous for outdoor localization, a comparable, seamless indoor localization system is still missing. Existing indoor localization technologies are often isolated, require specialized infrastructure, or are limited to specific areas with pre-existing floor plans. The authors aim to bridge this gap by creating a system that works globally, with minimal overhead, across diverse devices, and allows users to transition smoothly between indoor and outdoor environments. A key challenge identified is the lack of comprehensive, automatically generated indoor floor plans, which hinders the widespread adoption of technologies like WiFi localization.
Methods
The proposed IPS architecture is built around a crowd-sourcing approach, utilizing the embedded sensors in smartphones (accelerometers, compasses, cameras, WiFi, GSM). The system comprises several modules:
- Signal Collection Module: Gathers raw sensor data with timestamps.
- Floor Plan Construction Module: This is the focus of the paper. It includes:
- User Trace Construction Module: Processes raw sensor data to estimate user velocity and displacement, combining it with compass data to create user traces within a building. This module employs a dead reckoning approach, using accelerometer data for displacement and magnetometer for direction. To combat error accumulation, it leverages a zero velocity update (ZVU) technique, essentially using the accelerometer as a pedometer. A finite state machine (FSM) is introduced for robust step counting, outperforming a variance-based method.
- Area of Interest Detection Module: Classifies blocks within the floor plan into categories like offices, corridors, elevators, and stairs. This module uses features derived from user traces, such as average time spent in a block, average and variance of acceleration, correlation between accelerometer axes, number of turns, and WiFi/GSM signal strength. A C4.5 decision tree classifier is used for this task.
- Location Information Database Builder Module: Constructs a fingerprint database for localization.
- Location Determination Engine: Estimates user location based on collected signals and the fingerprint database.
- User Interface Module: Handles user queries for location and floor plans.
The system leverages cloud computing for data processing and storage.
Datasets
The paper describes an experimental testbed in a single building floor plan covering 448m². Three users with Android phones (two Nexus One, one Samsung Galaxy S) were used. The experiments involved collecting sensor data (accelerometer, magnetometer, WiFi, GSM, GPS for synchronization) as users moved through the building. No specific public datasets were used; rather, the authors generated their own data through these controlled experiments.
Key Insights and Ideas
- Crowd-sourcing as the key to ubiquitous indoor mapping: The paper strongly advocates for leveraging the vast number of smartphone users to automatically build a global floor plan database, overcoming the manual effort and cost associated with traditional methods.
- Smartphone sensors are powerful enough for floor plan construction: The research demonstrates that raw sensor data, particularly from accelerometers and compasses, can be effectively processed to reconstruct user movement and identify distinct areas within a building.
- Robust step counting is crucial for accurate dead reckoning: The development of a finite state machine-based step detection method significantly improves accuracy compared to simpler integration methods, mitigating error accumulation in dead reckoning.
- Feature engineering is vital for area classification: Identifying relevant features from user traces (e.g., time spent, acceleration patterns, turns) allows for accurate classification of different indoor spaces.
- Elevators and corridors are good synchronization points: The results highlight that these areas can be identified with high accuracy and can serve as reliable reference points for correcting local traces.
Key Results
- User Trace Construction: Achieved a displacement error of less than 0.9m and an average error of less than 2.3% in estimating the number of steps.
- Area of Interest Identification: Demonstrated up to 90% accuracy in correctly identifying areas of interest (offices, corridors, elevators, stairs).
- Classifier Performance: Elevators and corridors were detected with zero false negative rates, and elevators and offices had zero false positive rates.
- Block Size Impact: A block size of 0.7m was found to yield the best classification accuracy (90%).
Limitations and Future Work
Limitations:
- Single Building Testbed: The experiments were conducted in a single building, and scalability to a worldwide, heterogeneous environment requires further validation.
- Limited Sensor Usage: While phones have cameras and microphones, these were not utilized in the current testbed for area of interest detection.
- Privacy Concerns: The paper acknowledges that user privacy is a significant concern for a 24/7 tracking system.
- Hardware Variations: Dealing with the heterogeneity of smartphone sensors and their varying quality is a major challenge.
- Robustness to Attacks: The system's vulnerability to data poisoning attacks needs to be addressed.
- Energy Efficiency: Balancing accuracy with the energy consumption of continuous sensor data collection is critical.
- Incentive Models: Encouraging users to contribute data for new buildings requires well-designed incentive mechanisms.
- Phone Orientation: The impact of phone orientation on sensor readings needs to be fully compensated for.
- Scalability: Handling the massive amount of data generated by a global system is a significant challenge.
- Integration of Multiple Technologies: Seamlessly integrating various indoor and outdoor localization technologies is complex.
Future Work:
The authors identify several research directions:
- Automating floor plan construction and fingerprint generation.
- Seamless roaming between indoor and outdoor environments.
- Addressing user privacy concerns through anonymization and user control.
- Developing techniques to handle hardware variations and sensor fusion.
- Improving system performance and energy efficiency.
- Designing effective incentive models for crowd-sourcing.
- Developing orientation-independent algorithms.
- Investigating techniques for data reduction and search space pruning for scalability.
- Integrating a wider range of localization technologies.
- Exploring specific applications like enhancing first responder safety and location-aware social networking.
Summary updated