Navigation Application with Mobile Telephony: Shortest-path


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:
  1. Smaller graphs
    A simple map with small number of nodes. The example of the map is as shown in Figure 4.

  2. 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
  1. Hightower J. and Borriello G. (August 2001), “Location Systems for Ubiquitous Computing”, IEEE Computer Society, Vol. 34 Num. 8, pp. 57-66

  2. Buckingham S.(Jan 2000), An Introduction to the WAP, http://www.gsmworld.com/technology/yes2wap.html#1 (viewed on the 10th March 2000).

  3. UltiVerse Technologies (2000), Wireless Internet Messaging Solutions: Architecture, http://www.ultiverse.com/solutions/index.html (viewed on the 1st December 2000).

  4. 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).

  5. Brown J. (2001), A location based mapping system for WAP mobile phones, Final year project, U.M.I.S.T.

  6. Marble F.M and Peuquet D.J. (1990), Introductory reading in Geographic Information Systems, Taylor & Francis.

  7. Anonymous, Warterfall Model, http://home.apu.edu/~jcox/cs524/notes/models/SoftwareModels2.htm (viewed on the 16th April 2001)

  8. Eberts, Ray E., User Interface Design, Prentice-Hall International, Inc., New Jersey, 1994.

  9. Horowitz E. et. al. (1996), Computer Algorithms C++, W.H. Freeman and Company, New York.

  10. Freeland Steve (April 1997), Graph Algorithm, http://home.apu.edu/~jcox/cs524/notes/models/SoftwareModels2.htm (viewed on the 27th June 2001).

  11. Dijkstra E. (1997), Edsger Wybe Dijkstra, http://www.uwec.edu.jolhm/335-00/Group9/bAbstract.html (viewed on the 27th June 2001).

  12. Dijkstra E. (1959), A note on two problems in connection with graphs, Numerische Mathematik 1, pg 269-271.

  13. Openwave (2001), Top 10 Usability Guidelines for WAP Applications, http://developer.phone.com/resources/uiguide.html (viewed on the 27th June 2001).

  14. Morris J.(1998), Dijkstra’s Algorithm – Data Structures and Algorithms, http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/dijkstra.html (viewed on the 27th June 2001).

  15. Morris J. (1998), Operation of Dijkstra’s Algorithm – Data Structures and Algorithms, http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/dij-op.html (viewed on the 27th June 2001).

  16. Openwave (2001), Openwave,http://developer.phone.com/resources/uiguide.html (viewed on the 7th June 2001).

  17. Wireless Application Protocol Architecture Specification (1998), WAP Forum, Version 30 April 1998, http://www.wapforum.org/ (viewed on the 1st December 2000).

  18. MapQuest (1999-2001), MapQuest, MapQuest.com, Inc, http://www.mapquest.com , (viewed on the 25th August 2001).

  19. MultiMap.com (1996-2001), multiMap.com, London UK, http://www.multiMap.com (viewed on the 25th August 2001).

  20. OpenwaveTM (2001), Openwave Developer Program, Openwave System Inc, http://updev.phone.com/ , (viewed on the 10th March 2001)

  21. Tettoni L. (Feb 1997), Topological Ordering, http://www-bcm.unil.ch/staff/tettoni/maxsim/order.html , (viewed on the 22nd September 2001).

  22. Jacey-Lynn Minoi (Sep 2001), “Navigation and Orientation with Mobile Telephony”, unpublished dissertation, Department of Computation, UMIST, UK.

  23. Editors of ESRI Press (1998), Understanding GIS: The Arc Info Method Version 7.2 for Unix and Windows NT, Environmental Systems Research.

  24. Dale, P.F. & McLaughlin, J.D. (1998), Land Information Management, Clarendon Press Oxford.

  25. Burrough, P.A. (1986), Principles of GIS for Land Resources Assessment, Clarendon Press Oxford.

  26. Honda Satellite-link Navigation System, http://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.


Page 3 of 3
| Previous |