A Comparison of Protocols for Updating Location Information

Leonhardi, A. and Rothermel, K. 2001. A Comparison of Protocols for Updating Location Information. Cluster Computing 4, 4 (Oct. 2001), 355-367.

The location of information may be acquired by different types of sensor systems and therefore has different degree of accuracy. The transmission of location information can use different update protocols:

In case of a querying protocol the information is pulled by the receiver, while with a reporting protocol it is pushed by the sender. A combined protocol is also possible, where an optimal ratio between the number of updates and the number of queries has to be found.

The different types of querying protocols are:
Simple: the location information is queried from the source each time it is queried by the an application
Cached: the server stores a cached copy of the last transmitted location information
Periodic: the server queries the location information periodically from the source with a certain time interval D

The different types of reporting protocols are (the initiative is on the side of the source):
Simple: the source sends the location information each time the value has changed
Time-based: The location information is transmitted periodically after a certain interval of time T has elapsed
Distance-based: sends an update of the location information whenever the geographic distance between the current location and the last reported location becomes greater than a given threshold D.

Location and uncertainty model

A location sighting can have a temporal as well as a spatial accuracy. The temporal accuracy is given by the time that has elapsed since the location sighting has been acquired, while the spatial accuracy is de ned by the maximum distance between the position reported by the sighting and the actual position of the mobile object. For many location-aware applications the spatial accuracy of a sighting is more important, because the applications are concerned with the spatial relationship between (mobile) objects. The uncertainty ul(t) of a certain location sighting l describes the spatial accuracy at a given time t > tl.

At the time of the sighting the uncertainty is determined by the accuracy up of the sensor system. The uncertainty at a later time t can be estimated by the distance the mobile object may have traveled during the time t – tl. If a maximum bound for the velocity of the mobile object (vmax) exists, the maximum uncertainty of the location sighting can be calculated by adding the distance the object can have traveled to the uncertainty of the sensor system (see Figure 4). This is described by the following equation:

Tracking systems vs. positioning systems

The location information for a mobile object can be determined through various types of positioning systems. A basic distinction can be made between tracking systems, where a system of stationary sensors determines the location of a mobile object, and positioning systems, where the location information is determined by a sensor on the mobile object itself.

Disconnection and uncertainty

A common characteristic of these wireless networks is that a connection can be temporarily lost while the device is at an unfavorable location (e.g., inside of a tunnel), a state which is called a disconnection. In most cases a wireless network can also not o er as good a bandwidth and latency as a fixed networks (see [Sat96]).

In the following paragraphs we discuss the properties of the basic protocols with regard to disconnections, namely how long it takes to detect a disconnection and the maximum uncertainty of the location information returned during that time.

Location service functionalities

The location service shall provide the following functionality: It will support range queries, that is finding all mobile objects inside a given area, as well as position queries, which request the current location of a certain mobile object.

Relation to my thesis: Update protocols for location information can be used to reduce (or at least scope) uncertainty on the location timeliness. Catchbob! uses a time-based reporting protocol. On idea is to mix this protocols with others and have an adaptive approach depending on the connectivity and the stage of the game. I could also let the users choose their update algorithms and see their needs to change them. My try to contextualize update protocols in spatial uncertainty: