The management of positions of mobile objects is an essential prerequisite for many context-aware systems such as advanced traffic management systems or personal assistance systems. In this paper, we present two approaches for the scalable tracking of mobile object trajectories and the efficient processing of continuous spatial range queries, respectively. We show in detail how both approaches utilize the basic concepts of accuracy relaxation and utilization of context information, such as movement predictions, to minimize the number of position updates, the size of trajectory data, and the number of energy-consuming position sensing operations.

Moving objects databases (MOD) manage trajectory information of vehicles, animals, and other mobile objects. A crucial problem is how to efficiently track an object's trajectory in real-time, in particular if the trajectory data is sensed at the mobile object and thus has to be communicated over a wireless network.

We propose a family of tracking protocols that allow trading the communication cost and the amount of trajectory data stored at a MOD off against the spatial accuracy. With each of these protocols, the MOD manages a simplified trajectory that does not deviate by more than a certain accuracy bound from the actual movement. Moreover, the different protocols enable several trade-offs between computational costs, communication cost and the reduction of the trajectory data: Connection-Preserving Dead Reckoning (CDR) minimizes the communication cost using dead reckoning, a technique originally designed for tracking an object's current position. Generic Remote Trajectory Simplification (GRTS) further separates between tracking of the current position and simplification of the past trajectory and can be realized with different line simplification algorithms. For both protocols, we discuss how to bound the space consumption and computing time at the moving object and thereby present an effective compression technique to optimize the reduction performance of real-time line simplification in general.

Our evaluations with hundreds of real GPS traces show that a realization of GRTS with a simple simplification heuristic reaches 85 to 90% of the best possible reduction rate, given by retrospective offline simplification. A realization with the optimal line simplification algorithm by Imai and Iri even reaches more than 97% of the best possible reduction rate.

Scaling heterogeneous information systems (HIS) to thousands of sources poses particular challenges to source discovery. It requires a powerful formalism for describing the contents of the sources in a concise manner and for formulating compatible queries as well as a suitable structure for indexing and retrieving the source descriptions efficiently.

We propose an extended logic-based description formalism for large-scale HIS with structured sources and a shared ontology. The formalism refines existing approaches that describe the sources by constraints on the attribute value ranges in several ways: It allows for complex, nested descriptions based on defined classes. It supports alternative descriptions to express that a source may be discovered by different combinations of constraints. Finally, it allows to adjust between positive matching, similar to keyword-based discovery, and negative matching, as used in existing logic-based approaches.

We further propose the SDC-Tree for indexing such source descriptions. To allow for efficient discovery, the SDC-Tree features multidimensional indexing capabilities for the different attributes and the IS-A hierarchy of the shared ontology, but also incorporates the existence or absence of constraints. For this purpose, it supports three different types of node split operations which exploit the expressiveness of the description formalism. Therefore, we also propose a generic split algorithm which can be used with arbitrary ontologies.

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.

Space-partitioned Moving Objects Databases (SP-MODs) allow for the scalable, distributed management of large sets of mobile objects' trajectories by partitioning the trajectory data to a network of database servers.

Processing a spatio-temporal query q therefore requires efficiently routing q to the servers storing the affected trajectory segments. With a coordinate-based query - like a spatio-temporal range query - the relevant servers are directly determined by the queried range. However, with trajectory-based queries - like retrieving the distance covered by a certain object during a given time interval - the relevant servers depend on actual movement of the queried object. Therefore, efficient routing mechanisms for trajectory-based queries are an important challenge in SP-MODs.

In this paper, we present the Distributed Trajectory Index (DTI) that allows for such efficient query routing by creating an overlay network for each trajectory. We further present an enhanced index called DTI+S. It accelerates the processing of queries on aggregates of dynamic attributes, like the maximum speed during a time interval, by augmenting DTI with summaries of trajectory segments. Our simulations with a network of 1000 database servers show that DTI+S can reduce the overall processing time by more than 98%.

Moving objects databases (MODs) store objects' trajectories by spatiotemporal polylines that approximate the actual movements given by sequences of sensed positions. Determining such a polyline with as few vertices as possible under the constraint that it does not deviate by more than a certain accuracy bound epsilon from the sensed positions is an algorithmic problem known as trajectory reduction.

A specific challenge is online trajectory reduction, i.e. continuous reduction with position sensing in realtime. This particularly is required for moving objects with embedded position sensors whose movements are tracked and stored by a remote MOD.

In this paper, we present Connection-preserving Dead Reckoning (CDR), a new approach for online trajectory reduction. It outperforms the existing approaches by 30 to 50 CDR requires the moving objects to temporally store some of the previously sensed positions. Although the storage consumption of CDR generally is small, it is not bounded. We therefore further present CDRM whose storage allocation and execution time per position fix can be adjusted and limited. Even with very limited storage allocations of less than 1 kB CDRM outperforms the existing approach by 20 to 40

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.

Position information of moving objects plays a vital role in many pervasive applications. Therefore, moving objects databases (MODs), which can manage trajectory data of a number objects, are used in many pervasive systems. A crucial problem with MODs is how to efficiently track a remote object's trajectory in real-time, i.e. how to continuously report the sensed trajectory data to the MOD with minimal effort. For this purpose, we present a prototypical implementation of the Generic Remote Trajectory Simplification (GRTS) protocol, which optimizes storage consumption, processing, and communication costs. Our prototypical system includes a fully functional MOD as well as map-based mobile applications for subnotebooks and smartphones to illustrate the functioning of GRTS.

Position information of moving as well as stationary objects is generally subject to uncertainties due to inherent measuring errors of positioning technologies, explicit tolerances of position update protocols, and approximations by interpolation algorithms. There exist a variety of approaches for specifying these uncertainties by mathematical uncertainty models such as tolerance regions or the Dilution of Precision (DOP) values of GPS. In this paper we propose a principled generic uncertainty model that integrates the different approaches and derive a comprehensive query interface for processing spatial queries on uncertain position information of different sources based on this model. Finally, we show how to implement our approach with prevalent existing uncertainty models.

Context-aware applications rely on models of the physical world. Within the Nexus project, we envision a World Wide Space which provides the conceptual and technological framework for integrating and sharing such context models in an open, global platform of context providers. In our ongoing research we tackle important challenges in such a platform including distributed processing of streamed context data, situation recognition by distributed reasoning, efficient management of context data histories, and quality of context information. In this paper we discuss our approach to cope with these challenges and present an extended Nexus architecture.

Dieser Beitrag beschreibt die Verteilung kontextbezogener Informationen mittels eines erweiterten Instant-Messaging-Dienstes. Dieser Dienst ermöglicht das Senden von Nachrichten an alle Teilnehmer, die einen bestimmten Kontext besitzen und sich z.B. an einem bestimmten Ort aufhalten oder bestimmte Interessen besitzen. Als Basis dient das Extensible Messaging and Presence Protokoll (XMPP) sowie ein XMPP-basierter Instant-Messaging-Dienst. Wir beschreiben Protokoll- und Architekturerweiterungen für die Integration von Kontextinformationen in das XMPP-Protokoll und die Server-Infrastruktur. Der erweiterte Dienst unterstützt insbesondere die Server-seitige Filterung von Nachrichten aufgrund von Kontextinformationen und ermöglicht dadurch die effiziente Nachrichtenverteilung.

Context-awareness refers to the idea that applications adapt to their context of use including, for example, location, nearby devices and user habits. In the last years, billions of sensors have been deployed all over the globe, which allow creating comprehensive context models of our physical environment. The availability of such models constitutes a huge potential for context-aware computing as it allows selecting relevant context information from different providers all over the globe. However, such sharing of context information poses a number of challenges. A fundamental problem is how to provide efficient access to the immense amounts of distributed dynamic context information - particularly due to the mobility of devices and other entities.

To enable efficient access to current and past position information about moving objects, we propose a family of trajectory tracking protocols (CDR, GRTS) as well as a distributed indexing scheme (DTI) for trajectories. Given a certain accuracy bound, CDR and GRTS optimize the storage consumption and communication cost for tracking a moving object's trajectory in real-time at some remote database and allow for various trade-offs between computational costs, reduction efficiency, and communication. DTI enables efficient access to trajectory information that is partitioned in space and stored by different servers for scalability reasons. In addition, an extended scheme DTI+S is presented, which optimizes the processing of aggregate queries.

For discovering context information that is relevant for the situation of an application, we propose a powerful formalism for describing context models in a concise manner and a corresponding index structure (SDC-Tree). The formalism considerably extends existing approaches for describing information sources by constraints and permits to adjust between different semantics for matching descriptions against corresponding queries. The SDC-Tree enables to discover relevant context models out of potentially millions of descriptions efficiently using multidimensional indexing capabilities.

For context-aware computing, position is an important aspect. Usually the mobile objects fix position on their own. A central instance called location service manages the position data. Transmitting latest position data to the location service is called position update. The location service uses the position data to answer queries on the positions of mobile objects.

Often this implies that the mobile objects regularly fix and update position. Therefore they spend a lot of energy, which decreased the availability time of mobile devices. Existing approaches to save energy only reduce the number of position updates. In order to minimize the energy consumption the number of position fixes and updates has to be adapted to the actual demand of the queries.

First of all the query interface of the location service is analyzed in this work. The query interface is enhanced so that an inquiring application can specify its actual demand precisely. This implies research on continuous queries as well as on temporal and spatial tolerance.

Afterwards it is shown how the number of position fixes can be minimized for a given query and tolerance. Starting from that, the energy consumption is minimized. Several approaches are developed for processing queries efficiently. Normally the queries have to be processed by the location service and the inquired mobile objects together.

Detailed simulations fortify the theoretical results. An all new approach to process range queries is put to test with promising results.

The final result of this work is that there are a lot of possibilities to save energy in location management, thus increasing the availability time of mobile devices.

In ubiquitous computing - the third era of the electronic data processing - energy efficient algorithms play an important role, since the corresponding computer systems have limited energy supplies. Many tasks are mastered through cooperation in ubiquitous computer systems. The computers communicate via wireless networks with each other. The network interface of such a computer consumes a lot of energy. Energy can be saved by deactivating this interface, but then the computer becomes unreachable for others.

Today there are a lot of energy efficient algorithms for media access control and routing. These algorithms save energy by deactivating the network interface during regular intervals and try to compensate the unreachability.

In this work energy efficient algorithms, which use knowledge on the applications and services of a computer, are examined. Using this knowledge potentially most of all energy can be saved. At the same time negative effects of the deactivation of the network interfaces can be minimized. Here, especially variants or extensions of SANDMAN, an algorithm for energy efficient service discovery, are examined. SANDMAN divides a wireless network in clusters and uses a clusterhead per cluster as service directory. In the approach discussed here, not only the service discovery but also the use of the service occurs via the clusterhead. The real service is hidden behind the clusterhead.

In the first part of this work advantages and disadvantages of this approach are examined. One result among others is how services and computers have to look like to be suitable for this approach. After the discussion of some existing energy efficient algorithms, LATE RISER, a concrete algorithm according to the described approach, is developed and its implementation is described. Data of the analysis of LATE RISER through simulation are presented and discussed.

The conclusion is that using the described approach a lot of energy can be saved, but it can only be used under suitable circumstances.