Continuous queries are often employed to monitor the locations of mobile objects (MOs), which are determined by sensing devices like GPS receivers. In this paper, we tackle two challenges in processing continuous range queries (CRQs): coping with data uncertainty inherently associated with location data, and reducing the energy consumption of battery-powered MOs. We propose the concept of spatiotemporal tolerance for CRQ to relax a query's accuracy requirements in terms of a maximal acceptable error. Unlike previous works, our definition considers tolerance in both the spatial and temporal dimensions, which offers applications more flexibility in specifying their individual accuracy requirements. As we will show, these tolerance bounds can provide well-defined query semantics in spite of different sources of data uncertainty. In addition, we present efficient algorithms that carefully control when an MO should sense or report a location, while satisfying these tolerances. Thereby, we particularly reduce the number of position sensing operations substantially, which constitute a considerable source of energy consumption. Extensive simulations confirm that the proposed algorithms result in large energy savings compared to nontolerant query processing.

Moving objects databases (MODs) have been proposed for managing trajectory data, an important kind of information for pervasive applications. To save storage capacity, a MOD generally stores simplified trajectories only. A simplified trajectory approximates the actual trajectory of the mobile object according to a certain accuracy bound. In order to minimize the costs of communicating position information between mobile object and MOD, the trajectory simplification should be performed by the mobile object. To assure that the MOD always has a valid simplified trajectory of the remote object, we propose the generic remote trajectory simplification protocol (GRTS) allowing for computing and managing a simplified trajectory in such a system in real-time. We show how to combine GRTS with existing line simplification algorithms for computing the simplified trajectory and analyze trade-offs between the different algorithms. Our evaluations show that GRTS outperforms the two existing approaches by a factor of two and more in terms of reduction efficiency. Moreover, on average, the reduction efficiency of GRTS is only 12% worse compared to optimal offline simplification.

In location-based services, continuous queries are often employed to monitor the locations of mobile objects that are determined by sensing devices like GPS receivers. Due to limited battery resources, it is important for these objects to acquire and report location data only if necessary. We study how these energy- consuming operations can be reduced with a controlled impact on query accuracy of continuous range queries (CRQs). Specifically, we develop uncertainty- aware tolerances, which are user-defined error bounds that provide correctness guarantees, with consideration of different sources of data uncertainty: sensing uncertainty, sampling uncertainty, and communication delay. Novel algorithms are developed to control carefully when an object should acquire and update a location, while satisfying these tolerances. Extensive simulations validate the effectiveness of our methods.

Many location-based systems rely on fine-grained tracking of mobile objects that determine their own locations with sensing devices like GPS receivers. For these objects, energy is a very valuable and limited resource. A distance-based reporting protocol can be employed to reduce the energy they consume by sending position updates. However, the energy required for position sensing has not been considered in the past. In this paper, we study how the resulting energy consumption from both sensing and update operations can be reduced for distance-based reporting. We show that significant savings are achieved by sending position updates earlier than actually required. For uniform movement, we derive the minimal power consumption analytically. Subsequently, two novel online heuristics are proposed that control the sending of position updates at runtime. Their effectiveness is validated by extensive simulations.