High performance VLSI architecture for dynamic routing in knowledge intensive networks

• Main Author: Quek, Kai Hock.
• Other Authors: Srikanthan, Thambipillai
• Format: Theses and Dissertations
• Published: 2008
• Subjects: DRNTU::Engineering::Computer science and engineering::Computer applications::Physical sciences and engineering
• Online Access: http://hdl.handle.net/10356/2429
• Institution: Nanyang Technological University

Most people consider route determination to transport themselves from one place to another as a trivial task. Research has shown that much time and distances can be saved if the driver is made aware of the optimum path in an interactive manner. This can be achieved with the help of a dynamic route guidance system that identifies the optimum route based on the prevailing traffic conditions. Although two popular routing algorithms, namely the Dijkstra and heuristic A*, have been widely used for computing the optimum route, they are not best suited for complex roadway networks in which the traffic conditions change rapidly. In addition, they do not lend well towards the realisation of a high-speed architecture at low cost. In this project, a novel hierarchical routing algorithm based on the Clustering technique has been proposed as the solution for providing dynamic route guidance along a roadway network. Techniques for the efficient modelling of the roadway network have been devised to ensure that complex manoeuvres can be represented accurately. A multi-level hierarchical map representation has been proposed in order to incorporate the most desirable route planning considerations of humans as well as to better manage the database of a large network (i.e. one with more than 10,000 nodes) during real-time computations. A novel routing strategy was then developed to maximise the probability of identifying the optimum path using the compact representation of the hierarchical mapping process.