An important aspect of location-aware services is the management of location information. To this end, location information needs to be transferred from a mobile device, which determines this information by means of a local positioning sensor (such as GPS), to a location service, where the location information can be queried by applications. Because bandwidth in wide area mobile communications is still scarce and expensive, it is important to use an update protocol that requires as few messages as possible while still guaranteeing a desired accuracy of the location information. To decrease the number of necessary update messages, so-called dead-reckoning strategies have been proposed. In this paper we give an overview of different variants of dead-reckoning protocols for updating location information and propose a new map-based protocol. While a simple dead-reckoning protocol already reduces the number of update messages by up to 83%, the map-based protocol further reduces their number by again up to 60%.