Jacey-Lynn Minoi
Universiti Malaysia Sarawak,
94300 Kota Samarahan, Malaysia
[email protected]
Dr Peter Green
The University of Manchester
Institute of Science and Technology, United Kingdom
[email protected]
Sylvester Arnab
Universiti Malaysia Sarawak, Malaysia
[email protected]
In the age of information explosion and technological advancement, ubiquitous location-awareness is becoming a significant feature in the era of telecommunication [1]. The ubiquitous location-awareness is a requirement for certain telecommunication or mobile applications that uses location information. This development is linked to the tremendous growth in the number and the sophistication of mobile phone and mobile technology. And the trend continues stealthily invading mobile domains especially of those that utilise geographical positions or location information of the mobile devices or that of the mobile user [1]. Various ubiquitous location-awareness applications that are available in the market are normally tailored to a specific technology. Most of these applications require support from a combination of a number of technologies such as location sensor technologies (GPS, MSR RADAR, etc), service providers, and the Internet [1].
Geographical Information Systems (GIS) is an important element in any the ubiquitous location-awareness applications since it contains all the geographical information of the cities, roads, streets [1]. This information is obtained from sources such as topographic maps and satellite images, which are then filtered and delivered to the applications.
Nevertheless visualisation plays an important role especially in displaying spatial data in an image format. This image format is useful in aiding the user’s understanding of the meaning of the data displayed [1]. Presently, there are very few mobile mapping applications that are available in the market that display the spatial data in an image format.
This paper will introduce a prototype of mobile shortest path navigation application that concentrates on roads or streets in urban areas such as in Manchester City. The application prototype aims to provide mobile phone users with a wider and immediate accessibility to the road information to enable them to navigate visually around the city and to display the shortest path or route between two different locations in a map format.
The application should be user-friendly, as the services provided are deemed to be more comprehensive and innovative in the future. It has to be highly usable and accessible to all targeted groups of mobile phone users anywhere around the world.
Mobile Mapping
The use of a portable and wireless device such as Personal Digital Assistance (PDA) and mobile phone is becoming popular and significant. Recent studies [3,4] stated that more than 50% of the world population is reported to have a ratio of at least one mobile phone to a person. It is also stated that the percentage is expected to increase, as the product range in mobile telephony is made more available at reduced prices and equipped with advanced function [3]. The studies also state that by the year 2003, 50% of the 1 billion wireless devices that are available will be connected to the Internet [3]. This emerging and widespread Internet technology has dramatically changed the technology of mobile computing and mobile mapping [4].
The technology of mobile mapping is expanding significantly due also to the rising exceptions of the consumers [4]. The mobile mapping technology incorporates ubiquitous location-awareness and GIS features. This is to ensure that the final products will stay buoyant in the competitive telecommunication market.
Geographical Information Systems
GIS has been in existence for over twenty-five years in one form or another [23]. GIS is, accordingly, whole subject matters and processing contexts that involve a spatial component in the natural world. A GIS may thus be described as:
“… a set of tools for collecting, storing, retrieving at will, transforming and displaying spatial data from the real world for a particular set of purposes.” [24]
The term spatial data is characterised by information of positions (such as latitude and longitude), connection with other features (e.g. the path between two points) and details of non-spatial characteristics (examples details of temperature, rainfall, road traffic and etc.) [24].
Routing GIS-based solution based on spatial data is becoming very popular and is useful in mobile mapping [4]. The users provide input for the start and the destination point into the mapping mobile system. The system will next display a highlighted route in an image, text or voice format.
The navigation application prototype is regarded as a GIS-based routing solution; collecting, storing, searching and retrieving roads and street information, manipulating and calculating the shortest path from one location to another by using a programming language Avenue scripting as the programming language.
The Existing Online Road Navigation Applications
At present, there is a number of existing online road navigation applications available on CD-ROMs and also on the Internet but not a single one yet available on a mobile phone [22]. Examples of such online road applications available on the Internet include www.MapQuest.com [18] and www.multiMap.com [19]. However, there are few limitations to these web-based navigation applications, such as it is not portable and poor visualisation designs (such as vague image, text-based).
Another example of an online road navigation application is the road navigation system that is installed in cars e.g. Honda Navigation System [26]. The constraints of this system are that it is limited in numbers and are only useable in the United States, Japan and selected European countries such as Italy and Paris. Besides, the system is costly and physically bulky.
A Location based Mapping System (MapMe.com)
The shortest path navigation application is an extension of a larger system known as the ‘Location based mapping system’ or MapMe.com [5]. The aim of the ‘Location based mapping system’ was to develop a prototype mobile mapping system that would serve maps of a requested location to a WAP phone [5]. Figure 1 shows the conceptual diagram of the overall MapMe.com system.
Figure 1: The Conceptual Infrastructure of the MapMe.com system [5]
There are three major parts of the MapMe.com system, which are the WAP phone, the Web server and the GIS server. The WAP phone communicates with the Web server using WML/WMLScripts and these WML pages on the web server communicate with the GIS server using the Internet Map Server (IMS). Any search that is carried out on the GIS server will return the results to the Web server and WAP phone in WML pages.
Figure 2 shows the screen sample of the map image generated by the ‘Location based mapping system’ on a typical WAP phone (the WAP phone interface is taken from the Openwave Software Development Kit).
Figure 2: The WAP phone (Openwave SDK) Screen Sample [5] The Shortest Path Navigation Prototype Application
The shortest path navigation application prototype aims to produce an application that calculates the shortest path or route between two different locations and return a map with the shortest route being highlighted to a WAP phone. The final product of the navigation application will then be added to the MapMe.com system [5] as an independent function.
The term shortest path refers to the process of calculating the shortest path (route) between two points of the journey based on the distance of the road. Hence, the application prototype will only concentrate on the distance information that is the length of the road.
One of the fundamental requirements of the navigation application is the type of maps that will be used. This prototype manipulates on digitised road maps as shown below.
Figure 3: Example of procured digitised road map (extracted from [25])
In finding the shortest path, the second important aspect of the application is the calculation of shortest path/route. The application accepts two input locations (i.e. the start address and the destination address) and then calculates the shortest path. In order to get a more accurate and precise calculation, two points are needed instead of just the road or street name(s). The shortest route will be illustrated and explained below.
Figure 4: Case A (map not to scale)
In Figure 4, there are two highlighted streets i.e. Oxford Street and Canal Street. The start address will be from Oxford Street to the destination address at Canal Street. The numbers written in italic represents the distance (in kilometers) between two distinct junctions on the street.
From the previous diagram (Case A), it is not feasible to get the shortest path between Oxford Street and Canal Street. The reason is there are various options of paths that can be taken to move from Oxford Street to Canal Street and moreover, the achievement of the shortest path depends on the exact start and destination locations. For instance, the shortest path navigation application might compute ‘Milan Road’ as the shortest path since this is the shortest distance between the two streets. And, this is inaccurate as the exact location of the user is being neglected.
Due to the location sensor technology constraints in the project, another solution is implemented that is to include another parameter which the intersection of the roads (streets) also known as the junction. A point represents the junction. Two junctions will be needed which will define the two points namely, the start and destination points. Figure 5 shows an example of the implementation of the two points in terms of where the user is (near or at a junction) instead of merely using the road names. The location of the user are marked as ‘ ‘.
Figure 5: Case B (map not to scale)
In this case, the shortest path can be best attained (as shown in Figure 5) and the result is better compared to the first case example.
Lastly, the final displayed map will show the start and destination addresses and the highlighted shortest path. This map will be converted and saved in a format that is viewable on mobile phones.
The next section addresses the algorithm employed to calculate the shortest path.
The Shortest Path Algorithm
The start and destination points can be represented as nodes as used in graphs. Therefore, a map can be considered as a graph with many nodes as shown in Figure 6.
Figure 6: Graphical representation
By representing the map in a graphical format, the shortest path between two locations can be easily obtained, as there are various shortest path algorithms available such as Floyd’s algorithm [10], Bellman Ford algorithm [11], Topological Ordering algorithm [12], [21], A-Star algorithm [11] and Dijkstra’s algorithm [14]. As Dijkstra’s algorithm is the most commonly used and fast in terms of computation [14] therefore, the shortest path algorithm that is used to get the shortest path between two locations is the Dijkstra’s algorithm (as below).
Diagram 1: Dijkstra’s Algorithm
Implementation of the Shortest Path Navigation Application
The navigation application is divided into two modules, that is the ‘Shortest Path Calculation’ module, which is the core part of the study, and the ‘Display’ module that shows mainly the user interface design according to the functionality of the application on WAP phones.
The ‘Shortest Path Calculation’ module is executed in the GIS server, while the ‘Display’ module is executed on the Web server. The process of the ‘Shortest Path Calculation’ module includes the inputs and validation of the roads and the intersections (refer to Figure 7), and calculation of the shortest path between the two locations. The final product from this module is a map in a wireless bitmap format displaying the highlighted shortest path. The map is then sent to the ‘Display’ module for display purposes. Figure 8 illustrates the final map displayed on the WAP phone simulator (Openwave SDK [16]).
Discussion
Testing of the shortest path navigation system is performed on two modules, namely the ‘Shortest Path’ module and the ‘Display’ module. Each module is independent of each other and they are tested separately.
The training samples which has been used to test the system are as described below:
- Smaller graphs
A simple map with small number of nodes. The example of the map is as shown in Figure 4. - Larger graphs
A real digitised map as shown in Figure 3.
The testing was primarily done manually in order to validate the result attained from the system. Based on the observation made from testing, the shortest path calculation was confirmed to work in various graphs.
The user interface on the WAP phone is critical to the success of the application [13]. Despite the limitations of the mobile phones, particularly the small display screens and limited graphic capabilities, the user interface was worked on to produce the best possible interface. Moreover, the displays were designed and tested according to the user interface design principles as stated in the Openwave User Interface guidelines [41,50]. In addition, the ‘Display’ module also works across multiple browsers without much display problems.
Conclusion
This paper documents on the shortest path navigation application prototype suited for mobile phone aiming to be of benefit to mobile users navigating streets around urban areas.
GIS is used as the backbone, as it is the most powerful and expandable approach in creating the application. Besides, GIS as a visualisation tool is used to display the spatial data in an image format.
Even though the system has limited functionality, it is still powerful as proven by the testing done and it could be expanded further to produce a more commercially viable system.
References
- Hightower J. and Borriello G. (August 2001), “Location Systems for Ubiquitous Computing”, IEEE Computer Society, Vol. 34 Num. 8, pp. 57-66
- Buckingham S.(Jan 2000), An Introduction to the WAP, (viewed on the 10th March 2000).
- UltiVerse Technologies (2000), Wireless Internet Messaging Solutions: Architecture, https://www.ultiverse.com/solutions/index.html (viewed on the 1st December 2000).
- U. Srinivas, S. M. C. Chagla, Dr. V. N. Sharma (2000), Mobile Mapping: Challenges and Limitation, /application/lbs/lbs001.htm (viewed on the 4th April 2001).
- Brown J. (2001), A location based mapping system for WAP mobile phones, Final year project, U.M.I.S.T.
- Marble F.M and Peuquet D.J. (1990), Introductory reading in Geographic Information Systems, Taylor & Francis.
- Anonymous, Warterfall Model, (viewed on the 16th April 2001)
- Eberts, Ray E., User Interface Design, Prentice-Hall International, Inc., New Jersey, 1994.
- Horowitz E. et. al. (1996), Computer Algorithms C++, W.H. Freeman and Company, New York.
- Freeland Steve (April 1997), Graph Algorithm, (viewed on the 27th June 2001).
- Dijkstra E. (1997), Edsger Wybe Dijkstra, (viewed on the 27th June 2001).
- Dijkstra E. (1959), A note on two problems in connection with graphs, Numerische Mathematik 1, pg 269-271.
- Openwave (2001), Top 10 Usability Guidelines for WAP Applications, (viewed on the 27th June 2001).
- Morris J.(1998), Dijkstra’s Algorithm – Data Structures and Algorithms, https://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/dijkstra.html (viewed on the 27th June 2001).
- Morris J. (1998), Operation of Dijkstra’s Algorithm – Data Structures and Algorithms, https://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/dij-op.html (viewed on the 27th June 2001).
- Openwave (2001), Openwave,https://developer.phone.com/resources/uiguide.html (viewed on the 7th June 2001).
- Wireless Application Protocol Architecture Specification (1998), WAP Forum, Version 30 April 1998, https://www.wapforum.org/(viewed on the 1st December 2000).
- MapQuest (1999-2001), MapQuest, MapQuest.com, Inc, https://www.mapquest.com , (viewed on the 25th August 2001).
- MultiMap.com (1996-2001), multiMap.com, London UK, https://www.multiMap.com (viewed on the 25th August 2001).
- OpenwaveTM (2001), Openwave Developer Program, Openwave System Inc, , (viewed on the 10th March 2001)
- Tettoni L. (Feb 1997), Topological Ordering, , (viewed on the 22nd September 2001).
- Jacey-Lynn Minoi (Sep 2001), “Navigation and Orientation with Mobile Telephony”, unpublished dissertation, Department of Computation, UMIST, UK.
- Editors of ESRI Press (1998), Understanding GIS: The Arc Info Method Version 7.2 for Unix and Windows NT, Environmental Systems Research.
- Dale, P.F. & McLaughlin, J.D. (1998), Land Information Management, Clarendon Press Oxford.
- Burrough, P.A. (1986), Principles of GIS for Land Resources Assessment, Clarendon Press Oxford.
- Honda Satellite-link Navigation System, https://www.hondacars.com/news/press.html (viewed on the 21/6/2002)
Acknowledgement
We would like to place on record of my appreciation to Jeremy Brown for providing us with invaluable information on his project (Location Based Mapping System), and George Constantinou for all his guidance and help.
