Abstract
With the availability and accuracy of satellite-based positioning systems and the growing computational power of mobile devices, recent research and commercial products of navigation systems are focusing on incorporating real-time information for supporting various applications. In addition, for routing purposes, navigation systems implement many algorithms related to path finding (e.g., shortest path search algorithms). This chapter presents the foundation and state-of-the-art development of navigation systems and reviews several spatial query related algorithms.
TopModern Navigation Systems
A navigation system is an integration of position and orientation devices, computation devices, communication hardware and software for guiding the movement of objects (e.g., people, vehicles, etc.) from one location to another. In general, the infrastructure of navigation systems can be classified into two subsystems: positioning signal transmission systems and positioning signal receivers. The positioning signal transmission system allows the signal receiver to determine its location (longitude, latitude, and altitude) using timing signals. Positioning signal receivers range from hand-held devices, cellular phones, to car-based devices. These devices typically include some storage of map data and the computing capabilities of spatial operations, such as calculating directions. Additionally, in some novel geoinformatics applications, the receiver also relies on some server components for various services, such as real-time traffic information. In such a scenario, a server infrastructure is introduced which includes a Web server, a spatial database server, and an application server to provide these services. The signal receiver communicates with the server via wired or wireless networking infrastructures.
Positioning Signal Transmission Systems
Positioning signal transmitters, such as satellites and base stations, broadcast precise timing signals by radio to receivers, allowing them to determine exact geographic locations and then dynamically display and update their current position on digital maps. As of 2006, the Global Positioning System (GPS) is the only fully functional satellite-based positioning signal transmission system.
Key Terms in this Chapter
Trilateration: Computing the relative positions of an object using the geometry of sphere intersections. To accurately determine the relative position of an object in 2D, trilateration uses at least 3 reference points, and the measured distance between the object and each reference point.
GIS: A system for creating, integrating, analyzing and storing managing geographical data and associated features. In general, GIS provides users with an interface to query, retrieve, and edit the spatial data in an efficient way.
Ephemeris: Refers to the relative positions of the planets, or satellites in the sky at a given moment.
Geosynchronous Satellite: A satellite whose orbital track lies over the equator.
Shortest Path Search: Finding the shortest or least cost path through an underlay network.