TL;DR
This paper introduces a novel collaborative localization system for participatory sensing that significantly reduces energy consumption by intelligently distributing roles among mobile devices. By having a subset of devices ("broadcasters") use GPS and share their locations, other devices ("LIRs") can estimate their positions without relying on power-hungry GPS, achieving up to 68% energy savings while maintaining competitive accuracy.
What Problem Does This Paper Address?
Participatory sensing applications, which rely on mobile users to collect and share environmental data, often require accurate location information. However, continuously using GPS for localization drains mobile device batteries rapidly, limiting the feasibility of such applications. While alternatives like Wi-Fi and cellular triangulation exist, they offer lower accuracy. This paper tackles the challenge of providing accurate location information for participatory sensing while drastically minimizing energy consumption, a critical factor for widespread adoption.
Methods
The core of the proposed solution is a collaborative localization architecture that divides mobile participants into three roles:
- Broadcasters: These devices use GPS to determine their location and periodically broadcast this information, along with movement data, to nearby devices.
- Location Information Receivers (LIRs): These devices do not use GPS. Instead, they leverage the broadcasted location and movement data from broadcasters to estimate their own positions using a device-to-device localization method.
- Normal Participants: These devices function similarly to traditional approaches, using GPS to determine their location and label their sensor data.
The system dynamically assigns these roles to participants based on their current locations and the task requirements. A key contribution is the formulation of the Broadcaster Set Selection Problem (BSSP), aiming to minimize the total energy consumption of all participants by optimally selecting broadcasters and determining the duration of their roles. Two heuristic algorithms, Greedy-Based Broadcaster Selection (GBS) and Simulated Annealing-Based Broadcaster Selection (SABS), are proposed to solve the BSSP.
Datasets
The authors evaluated their proposed solution using the GeoLife (Microsoft Research Asia) dataset. This dataset contains real GPS trajectories of 182 volunteers in Beijing, collected from April 2007 to August 2012. For their experiments, they focused on a specific 200 x 500 m² region with high movement density and selected trajectories longer than 20 minutes, resulting in a dataset of 178 participants.
Key Insights and Ideas
- Role-Based Collaboration is Key: The fundamental insight is that not all devices need to use power-hungry GPS simultaneously. By strategically designating some devices as broadcasters, others can achieve localization with significantly less energy.
- Device-to-Device Localization is Viable: The paper demonstrates that LIRs can accurately estimate their locations by leveraging signals from nearby broadcasters, moving beyond server-centric localization.
- Energy-Accuracy Trade-off Management: The BSSP formulation and the proposed algorithms allow for flexible adjustment of localization accuracy based on application requirements, directly impacting the number of broadcasters and thus energy consumption.
- Dynamic Role Assignment: The system's ability to dynamically reassign roles ensures adaptability to changing user mobility patterns and task demands.
Key Results
- Significant Energy Savings: The proposed collaborative localization scheme can save up to 68% of the total energy consumption compared to traditional GPS-based localization.
- Competitive Accuracy: The system provides more accurate locations than Wi-Fi and cellular network positioning.
- Impact of Broadcaster Count: The study shows that there's an optimal number of broadcasters; too few lead to insufficient coverage, while too many increase overall energy consumption due to redundant GPS usage and broadcasting.
- Algorithm Performance: The GBS and SABS algorithms effectively find near-optimal solutions for the BSSP, with SABS showing better performance with more iterations.
Limitations and Future Work
- Participant Density: While the proposed method performs better with higher participant density, performance might degrade in sparse environments.
- Algorithm Iterations: The performance of SABS is sensitive to the number of iterations; a higher number of iterations leads to better results but increases computation time.
- Future Work: The authors suggest extending the system to include vehicle participants to enhance stability and further reduce energy consumption.
Summary updated