Next Generation Navigation Systems
Shashi Shekhar, Xiaobin Ma, Jin Soung Yoo and Changqing Zhou
Navigation systems that guide objects moving from one place to another have progressed recently with the rapid advances in positioning, communication, and spatial data storage and processing technologies. The easy availability of satellite based global positioning systems has revolutionized all forms of automated navigation. Other positioning technologies such as handsets using user input and networks using one of many location-determining methods are also showing continued advances. The proliferation of such location-aware devices provides us opportunities to develop a diverse range of location-based applications, many of which will use user location-specific information.
Location-based service, or LBS, is the ability to find the geographical location of a positioning device and provide services based on that location [OpenLS]. LBS can enhance a range of personal, governmental, industrial and emergency mobile applications. These capabilities will contribute to revolutionize many areas of life in the near future. Many of the functions, applications, and services typically found in GIS systems are applicable to LBS. Open GIS (OGC) is an international consortium for developing publicly available geoprocessing specifications. OGC recently initiated the OpenLS standard, which address the technical specifications for LBS. OpenLS is focused on defining the interface specifications for interoperable location application services that integrate users’ geographical location and other spatial information in the wireless Internet environment.
Architecture: The general architecture of a modern navigation system based on OpenLS is shown in Figure 1. The components can be broadly classified into four sub-systems, namely the spatial database server, the GeoMobility server, communication systems, and the location aware clients. Client side components include position aware devices that range from personal digital assistants (PDAs), laptops, cars, ships, and airborne vehicles, and cellular phones. The client and server interact through wireless communications. Client side devices use various visual interfaces (e.g., GUI, voice recognition) to interact (query and presentation) with the server.
Spatial Database Server: A spatial database [Guting, 94; Shekhar, 01; Shekhar, 02; Rigaux, 02] management system aims at the effective and efficient management of data related to a space in the physical world. Spatial database systems serve various spatial data (e.g., digital road maps) and nonspatial information (e.g., route guidance instruction) on request to the client. A spatial database server is an essential component for building efficient navigation system applications. It provides conceptual, logical, and physical data modeling facilities to build and manage spatial databases. It also provides various geospatial query-processing capabilities such as, find the nearest neighbor (e.g., restaurant) to a given location; find the shortest route between two points, etc. It acts as a backend spatial database server to the GeoMobililty server. Commercial examples of spatial database management systems include Oracle Spatial [OSpatial], DB2 Spatial Extender [DB2Spatial]), and ESRI’s Spatial Database Engine [SDE].
GeoMobility server: The GeoMobility server is an OpenLS platform through which content/service providers can deliver and service the location based applications. The core services are Location Utilities service, Directory Service, Presentation Service, Gateway Service and the Route Determination Service.
(1)Gateway Service: This service enables obtaining the position of a mobile terminal from the network.
(2)Location Utilities Service: The OpenLS utilities specification provides two services, geocoder and the reverse geocoder, and an abstract data type name Address. The geocoder service is a network-accessible service that transforms a description of a location into a normalized description of the location with point geometry. On the other hand, reverse geocoder service maps a given position into a normalized description of a feature location.
(3)Directory Service: The directory service provides a search capability for one or more points of interest (e.g., a place, product or service with a fixed position), or area of interest (e.g., a polygon or a bounding box). An example query is “Where is the nearest Thai restaurant to the EE/CS department?”
(4)Route Determination Service: This service provides the ability to find a best route between two points that satisfies user constraints.
(5)Presentation Service: This service deals with visualization of the spatial information as a map, route, and/or textual information (e.g., route description)
Communication Systems: The most recent advancement in telecommunications is wireless telephony, commonly known as “cell phones”. Wireless communication plays an important role in modern navigation systems. It makes user mobility over large geographic areas possible. Both analog and digital wireless systems are used in current communication systems. The first issue in wireless communication systems is the channel access techniques that define the basic framework for the system. There are three major channel access methods: Frequency-Division Multiple Access (FDMA), Time-Division Multiple Access (TDMA) and Code-Division Multiple Access (CDMA). In [Zhao, 97], land mobile radio is classified into two groups: public service and private service. Public services include paging, cellular telephony, and personal communication services. Categories of private services include conventional, trunked, and specialized mobile radio. Specific examples include EDACS, iDEN, and MCA.
Location Aware Clients:Client side devices in the architecture of a modern navigation system consist of three basic components, namely, a position and orientation module, a computing module consisting of display and storage, and a communication module. Each client side module may not necessarily be equipped with all three modules but still can be part of a location based application. For example, a personal digital assistant (PDA) without a positioning module can utilize the “gateway” service to obtain its current location. Client side devices vary widely in nature and function. Example devices include PDAs, cell phones, laptops, and land, sea, and airborne vehicles. Client devices may additionally be equipped with visual display units (e.g., touch screens), and voice recognition systems. Standalone (or thick) clients can store spatial databases locally, either on CD-ROM, DVDs, or hard disks.
Challenges: There are many technological challenges posed the next generation navigation system. Examples include map matching, nearest neighbor queries and personal gazetteer constructions, etc.
An application example of map matching is an automatic road user charge system. In the automatic charge system, a GPS receiver is installed on road users’ vehicles and records the road segments that the users have traveled. Then these users will be charged for using roads according to the types of roads. This gives rise to the need to automatically identify what roads were used by these road users. Traditionally this problem may be solved by map matching algorithms that match user GPS signals to specific road segments. However, in the automatic user charge system, the GPS signals need to be classified according to the road types. This problem brings a good opportunity to design a more efficient and accurate map matching algorithm.
Location-based services provide a search capacity for points of interest. One important service is the nearest neighbor search. For example, a commuter may request the identification of the nearest gas station on the way of his/her destination. Figure 2 shows the predefined route and the current location of a user and nearby gas stations. The nearest neighbor can be different by its search criteria.Euclidean distance based nearest gas station is ‘BP’.Road-distance based nearest gas station is‘SA’.The gas station through with smallest travel distance to the destination from the current location can be‘Amoco’.However, a commuter may prefer agas station (i.e., ‘Esso’) via which the detour from his/heroriginal route on the way to the destination is smallest. This in-route nearest neighbor search using road-distance metric is computationally expensive thus requiresefficient query processing algorithms[Yoo, 03].
In wireless mobile environment, personal gazetteers record individuals’ most important places, such as home, work, grocery store, etc. Using personal gazetteers in location-aware applications offers additional functionality and improves the user experience. An interesting challenge is to design a smart system which can automatically learn favorite places and routes for each user via a privacy-preserving manner[CQ, 04].
The present portable personal digital assistants have limited memories and display units. These limitations dictate the need for efficient main memory spatial processing algorithms, and intelligent user interfaces. Emergency applications, which require real-time dynamic spatial data from remote spatial database servers, are limited by the limited bandwidth provided by present wireless communication devices. In order to reduce the amount of information transferred over networks, we need efficient compression techniques. Additional research is needed to progressively transmit the data based on importance. Overall research needs are summarized in Table 1.
Navigation System Component / Research NeedsServer / Gateway /
- Indoor location sensing
- 100% coverage of location sensing despite GPS shadows
Location Utility /
- Improving map accuracy
- Improving effectiveness of map matching using additional information such as long-term and short-term histories
Directory /
- Nearest neighbor to a route
Route Determination /
- Alternate paths
Presentation /
- Safe visual and audio interfaces
- Cartographic generalization
Client / PDAs /
- Improving memories, display sizes, processing power
- Efficient in-memory algorithms
- Intelligent interfaces
Communications /
- Improving bandwidths
- Efficient map compression algorithms
- Progressive transmissions
Table 1. Research needs for new generation navigation systems
References
[OpenLS] OGC, “Open Location Services Initiative (OpenLS)”,
[Elmasri, 01] Ramez Elmasri and S. B. Navathe, “Fundamentals of Database Systems, with E-book”, 3rd edition, Addison-Wesley, 2001.
[Shekhar, 99] Shashi Shekhar, Ranga Raju Vatsavai, Sanjay Chawla, and Thomas E. Burk. "Spatial Pictogram Enhanced Conceptual Data Models and Their Translation to Logical Data Models". Integrated Spatial Databases, Digital Imagesand GIS, Lecture Notes in Computer Science, Vol 1737. 1999, Springer Verlag.
[OGC, 98] OGC, “Simple Features Specification (for OLE/COM, CORBA, SQL)”,
[SDC], Oracle, “Oracle Spatial”,
[Shekhar,97] S. Shekhar and D. R. Liu, CCAM: A Connectivity-Clustered Access Method for Networks and Network Computations, IEEE Trans. on Knowledge and Data Engineering, 9(1), Jan. 1997.
[Jing, 94] Ning Jing, Yun-Wu Huang, Elke Rundensteiner : A semimaterialized view appraoch for Route Maintenance in Intelligent Vehicle Highway systems. Proc Second ACM workshop on Geographic Information Systems, Nov 1994
[Jing, 98] Ning Jing, Yun-Wu Huang, Elke Rundensteiner : Hierarchical encoded Path views for path query processing: An optimal model and its performance evaluation. IEEE Transactions on Knowledge and Data Engineering, Vol 10 No:3 May/June 1998
[Jing, 95] Ning Jing, Yun-Wu Huang, Elke Rundensteiner : Hierarchical Path Views: A model based on Fragmentation and Transportation Road types. Third ACM Workshop on Geographic Ingormation Systems Nov 1995
[Huang, 96] Yun-Wu Huang, Ning Jing, Elke Rundensteiner : Effective Graph Clustering for path queries in Digital Map Databases. Proc Fifth Int’l Conference on Information and Knowledge management, 1996
[Jung, 02] Sungwon Jung, Sakti Pramanik : An efficient Path Computation Model for Hierarchically Structured Topological Road Maps. IEEE Transactions on Knowledge and data Engineering Vol 14 No:5 Sept/Oct 2002
[Jung, 96] Sungwon Jung, Sakti Pramanik : HiTi Graph Model of Topological Road Maps in navigation Systems. Proc 12th International Conference on Data Engineering 1996
[Bonsiepe, 93] Bonsiepe, Gui. Interpretations of Human User Interface. Visible Language. Vol. 24. No. 3. pp262-285,1993.
[Zhao, 97] Yilin Zhao. Vehicle Location and Navigation System. 1997
[FGDC] Fedaral Geographic Data Committee Digital Deospatial Metadata Standard Version 2,
[ASPRS] American Sociaty for Phtogrammetry and Remote Sensing Standard, American Sociaty for Phtogrammetry and Remote Sensing,
[NMAS] National Map Accuracy Standard,
[NMEA] National Marine Electronics Association 0183 standard,
[MNDOT] Minnesota Department Of Transportation Basemap,
[TIGER] Topologically Integrated Geographic Encoding and Referencing system
[Gm, 01] Fedaral Geographic Data Committee, Geospatial Metadata, 2001, April
[ETAK] Tele Atlas Products and Services,
[Navtech] Navigation Technologies Data,
[GDT] Geographic Data Technology product catalog,
[Feng, 02] Jun Feng and Toyohide Watanbe, “Fast Search of Nearest Target Object in Urban District Road Networks”, PYIWIT(2002)
[Tao, 02] Yufei Tao, Dimitris Papdias, Qiongmao Shen, “Continuous Nearest Neighbor Search”, Proceeding of the 28th the Very Large Data Bases Conference(VLDB Conference) , Hong Kong, China, 2002
[Bespamyatnikh, 99]Bespamyatnikh, S., Snoeyink, J., “ Queries with Segments in Voronoi Diagrams”, SODA, 1999
[Corral, 00] Corral, A., Manolopoulos, Y., Theodoridis, Y., Vassilakopoulos, M., “Closes Pair Queries in Spatial Databases”, ACM SIGMOND, 2000.
[Hjaltason, 99] Hjaltason , G and Samet, H, “Distance Browsing in Spatial Databases”, ACM TODS, 24(2), pp.265-31.1999
[Hjaltason, 992] Gisli R. Hjaltason and Hanan Samet, Distance browsing in spatial databases, In ACM Transactions on Database Systems, volumn 24, pages 254-318, 1999.
[Song, 01] Zhexuan Song and Nick Roussopoulos. K-Nearest Neighbor Search for Moving Query Point. In SSTD, Redondo Beach, USA, July 12-15th, 2001
[Ishikawa, 02] Yoshiharu Ishikawa, Hiroyuki Kitagawa and Tooru Kawashima, “Continual Neighborhood Tracking for Moving Objects Using Adaptive Distances”, IDEAS,2002.
[Shekhar, 97] S.Shekhar and D.-R. Liu, “CCAM: A Connectivity-Clustered Access Method for Networks and Network Computations”, IEEE TKDE, 9(1):102-119,1997.
[Zhang, 02] Jun Zhang, Nikos Mamoulis, Dimitris Papadias, Yufei Tao, All-Nearest-Neighbors Queries in Spatial Databses,2002
[Gaede, 98] V. Gaede and O.Gunther, “Multidimensional Access Methods. ACM Computing Surveys”, 30(2):170-231.1998
[Shahabi] Cyrus Shahabi, Mohammad R. Kolahdouzan, Mehdi Sharifzadeh, “A Road Network Embedding Technique for K-Nearest Neighbor Search in Moving Object Databaes”,
[Hakimi, 92]S. Louis Hakimi, Martine Labbe, and Edward Schmeichel. The voronoi partition of a network and its implications I location theory. In ORSA Journal on Computing, volume 4, 1992
[Roussopoulos, 95] Nick Roussopoulos, Stephen Kelleym and Fredeic Vincent. Nearest Neighbor Queries. In proceedings of the 1995 ACM SIGMOD International Conference on Management of Data, San Hose, California, May 22-25, 11995, pages 71-79, ACM Press, 1995
[Ferhatosmanoglu, 01] Hakan Ferhatosmanoglu, Ioana Stanoi, Divyakant Agrawal, and Amr El Abbadi. Constrained nearest neighbor queries. In SSTD, Redondo Beach, USA, July 12-15th, 2001, pages 257-278
[Yu, 01] Cui Yu, Beng Chin Ooi, Kian-Lee Tan, and H.V. Jagadish. Indexing the distance: An efficient methods to KNN processing. In The VLDB Journal, pages 421-430,2001.
[Berchtold, 97] Stefan Berchtold, Christian Bohm, Daniel A. Keim, and Hans-Peter Kriegel. A cost model for nearest neighbor search in high-dimensional data space. In Proceedings of the Sixteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 12-14, 1997, Tucson, Arizona, pages 78-86. ACM Press, 1997.
[berchtold, 98] Stefan berchtold, Bernhard Ertl, Daniel A. Keim, Hans-Peter Kriegel, and Thomas Seidl. Fast nearest neighbor search in high-dimensional spaces. In Proc. 14th IEEE Conf. Data Engineering, ICDE, 23-27 1998
[Tao, 02] Tao, Y., Papadias, D. Time-Parameterized Queries in Spatio-Temporal Databases. ACM SIGMON, 2002
[Zheng, 01] Baihua Zheng, Dik Lun Lee, Semantic Caching in Location-Dependent Query Processing, SSTD, 2001.