Energy-Efficient Collaborative Outdoor Localization for Participatory Sensing

Wendong Wang, Teng Xi, Edith C. H. Ngai, Zheng Song

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

Abstract

Location information is a key element of participatory sensing. Many mobile and sensing applications require location information to provide better recommendations, object search and trip planning. However, continuous GPS positioning consumes much energy, which may drain the battery of mobile devices quickly. Although WiFi and cell tower positioning are alternatives, they provide lower accuracy compared to GPS. This paper solves the above problem by proposing a novel localization scheme through the collaboration of multiple mobile devices to reduce energy consumption and provide accurate positioning. Under our scheme, the mobile devices are divided into three groups, namely the broadcaster group, the location information receiver group and the normal participant group. Only the broadcaster group and the normal participant group use their GPS. The location information receiver group, on the other hand, makes use of the locations broadcast by the broadcaster group to estimate their locations. We formulate the broadcaster set selection problem and propose two novel algorithms to minimize the energy consumption in collaborative localization. Simulations with real traces show that our proposed solution can save up to 68% of the energy of all of the participants and provide more accurate locations than WiFi and cellular network positioning.
BibTeX
@inproceedings{wang2016energy,
  author = {Wendong Wang and Teng Xi and Edith C. H. Ngai and Zheng Song},
  title = {{Energy-Efficient Collaborative Outdoor Localization for Participatory Sensing}},
  booktitle = {Sensors},
  year = {2016},
  url = {https://openreview.net/forum?id=pWmv5QaZbHH},
}
Figure