ITC/USA 2005 Conference Proceedings / The Forty-First Annual International Telemetering Conference and Technical Exhibition / October 24-27, 2005 / Riviera Hotel & Convention Center, Las Vegas, Nevada / An ad hoc network is a group of wireless nodes which do not rely on any fixed infrastructure. Hosts cooperate by forwarding packets for each other to communicate with nodes that are out of the radio transmission range. We propose a new routing algorithm that is based on the concept of multipoint relay nodes (MPR). The main focus of the Trust Level Routing protocol is the reliability and survivability of the network by applying costs to each MPR candidate. The cost calculation is based on the delay incurred, energy available at the MPR node, energy spent during transmission and number of packets sent on each link. We highlight the vulnerabilities in current link state routing algorithms and propose the use of light weight encryption algorithms to achieve a dependable routing algorithm. Network simulator (ns-2) is used to compare the protocol performance to other existing link state routing protocols.

Researchers have been investigating the optimal route query problem for a long time. Optimal route queries are categorized as either unconstrained or constrained queries. Many main memory based algorithms have been developed to deal with the optimal route query problem. Among these, Dijkstra's shortest path algorithm is one of the most popular algorithms for the unconstrained route query problem. The constrained route query problem is more complicated than the unconstrained one, and some constrained route query problems such as the Traveling Salesman Problem and Hamiltonian Path Problem are NP-hard. There are many algorithms dealing with the constrained route query problem, but most of them only solve a specific case. In addition, all of them require that the entire graph resides in the main memory. Recently, due to the need of applications in very large graphs, such as the digital maps managed by Geographic Information Systems (GIS), several disk-based algorithms have been derived by using divide-and-conquer techniques to solve the shortest path problem in a very large graph. However, until now little research has been conducted on the disk-based constrained problem. <br /><br /> This thesis presents two algorithms: 1) a new disk-based shortest path algorithm (DiskSPNN), and 2) a new disk-based optimal path algorithm (DiskOP) that answers an optimal route query without passing a set of forbidden edges in a very large graph. Both algorithms fit within the same divide-and-conquer framework as the existing disk-based shortest path algorithms proposed by Ning Zhang and Heechul Lim. Several techniques, including query super graph, successor fragment and open boundary node pruning are proposed to improve the performance of the previous disk-based shortest path algorithms. Furthermore, these techniques are applied to the DiskOP algorithm with minor changes. The proposed DiskOP algorithm depends on the concept of collecting a set of boundary vertices and simultaneously relaxing their adjacent super edges. Even if the forbidden edges are distributed in all the fragments of a graph, the DiskOP algorithm requires little memory. Our experimental results indicate that the DiskSPNN algorithm performs better than the original ones with respect to the I/O cost as well as the running time, and the DiskOP algorithm successfully solves a specific constrained route query problem in a very large graph.

Researchers have been investigating the optimal route query problem for a long time. Optimal route queries are categorized as either unconstrained or constrained queries. Many main memory based algorithms have been developed to deal with the optimal route query problem. Among these, Dijkstra's shortest path algorithm is one of the most popular algorithms for the unconstrained route query problem. The constrained route query problem is more complicated than the unconstrained one, and some constrained route query problems such as the Traveling Salesman Problem and Hamiltonian Path Problem are NP-hard. There are many algorithms dealing with the constrained route query problem, but most of them only solve a specific case. In addition, all of them require that the entire graph resides in the main memory. Recently, due to the need of applications in very large graphs, such as the digital maps managed by Geographic Information Systems (GIS), several disk-based algorithms have been derived by using divide-and-conquer techniques to solve the shortest path problem in a very large graph. However, until now little research has been conducted on the disk-based constrained problem. <br /><br /> This thesis presents two algorithms: 1) a new disk-based shortest path algorithm (DiskSPNN), and 2) a new disk-based optimal path algorithm (DiskOP) that answers an optimal route query without passing a set of forbidden edges in a very large graph. Both algorithms fit within the same divide-and-conquer framework as the existing disk-based shortest path algorithms proposed by Ning Zhang and Heechul Lim. Several techniques, including query super graph, successor fragment and open boundary node pruning are proposed to improve the performance of the previous disk-based shortest path algorithms. Furthermore, these techniques are applied to the DiskOP algorithm with minor changes. The proposed DiskOP algorithm depends on the concept of collecting a set of boundary vertices and simultaneously relaxing their adjacent super edges. Even if the forbidden edges are distributed in all the fragments of a graph, the DiskOP algorithm requires little memory. Our experimental results indicate that the DiskSPNN algorithm performs better than the original ones with respect to the I/O cost as well as the running time, and the DiskOP algorithm successfully solves a specific constrained route query problem in a very large graph.

<p>More and more travellers use navigation-aid software to find the way while driving. Most of todays systems use static maps with little or no information at all about currently yeilding roads conditions and disturbances in the network. It is desirable for such services</p><p>in the future to include information about road works, accidents, surface conditions and other types of events that affects what route is currently the best.</p><p>It is also desirable to notify users about changes in the prerequisites of the chosen route after they have started their trip.</p><p>This thesis investigates methods to include dynamic traffic information in route calculations and notifying users when the characteristics change for their chosen route.</p><p>The thesis utilizes dynamic traffic information from The Swedish Road Agencys (Vägverket) central database for traffic information, TRISS and calculates affected clients with help of positioning through the GSM network.</p>

More and more travellers use navigation-aid software to find the way while driving. Most of todays systems use static maps with little or no information at all about currently yeilding roads conditions and disturbances in the network. It is desirable for such services in the future to include information about road works, accidents, surface conditions and other types of events that affects what route is currently the best. It is also desirable to notify users about changes in the prerequisites of the chosen route after they have started their trip. This thesis investigates methods to include dynamic traffic information in route calculations and notifying users when the characteristics change for their chosen route. The thesis utilizes dynamic traffic information from The Swedish Road Agencys (Vägverket) central database for traffic information, TRISS and calculates affected clients with help of positioning through the GSM network.

The main objective of the diploma thesis is creation of methodology and automatization of calibration process of network graph based on the values of morphometric characteristics and motion vectors. The resulting morphometric values of the terrain have been detected on the basis of mathematical and cartographic methods for line course expression. The most accurate one has been used in GIS network analysis over the road network and digital terrain models, which were chosen as the most appropriate for this purpose. Relationship between morphometric values and values suitable for use in network analysis (speed, time, ...) has been studied using specific examples in appropriately selected territory with using selected vehicle, which was designated as a bicycle. The practical part for the verification of functionality of the suggested methodology has been compared with other models of accessibility, available web-map portals and route planners. The process of transport network evaluation based on selected parameters has been automated in Python programming language as a tool in ArcGIS software, which is attached to the diploma thesis. Powered by TCPDF (www.tcpdf.org)

When a large number of base stations fail due to the breakdown of some transmission circuit in a mobile cellular network, base stations located in neighboring areas may take over those malfunctioned base stations and continue to provide the access service of mobile communications for users in surrounding areas, thereby reducing the area in which mobile communications are out of service. Therefore, if leased circuits in base stations could complete the route distribution configuration prior to the onset of malfunction, it could decrease the impact of circuit breakdown and traffic loss. Also, the efficiency would be improved if the circuit assignment personnel could complete the job when the leased lines are less, while avoiding reassignment in the future and enhancing the mobile communications operations. In this study, we use a graph structure to represent the present mobile cellular network and establish the route-selection strategies. We define the "Optimal Route Assignment" for a newly constructed base station, which refers to the route assignment that causes least impact on disconnection area when any circuit in the network is broken. We also propose to use A* algorithm for optimal route assignment. However, the computation for the optimal route is time consuming. Measures such as computation time and least hops are considered in designing other strategies for route assignment. These strategies are parametric and we carried out experiments by adjusting and controlling parameters using real routing data. The experimental results demonstrate that there is no single winner among the proposed strategies. We identify a number of best strategies for different operating regions.

Approved for public release, distribution is unlimited / The objective of this thesis is to provide an aircraft with an optimal route to its destination that avoids encroaching into surface-to-air weapons killing envelopes in real time. The optimal route computed will be updated dynamically, depending on the location of the vehicle and the location of the Surface to Air Missile (SAM) sites. The problem was solved using heuristic algorithms instead of the conventional Dijkstra's & Bellman Ford algorithms, which are computationally expensive. Data fusion techniques such as spatial correlation and triangulation algorithms are presented in detail. Such techniques are important for situational awareness in a real time combat environment. Important information provided by onboard sensors are merged with the preplanned data to provide the operator with a better integrated picture of the combat environment. / Civilian, Singapore Ministry of Defense

In this work we present algorithms that are capable of calculating paths to destination for electric vehicles. These paths can be based on the simple metrics such as the distance, time or the paths can be based on more advanced metric such as the minimum energy demanding metric. This metric is parameterizable by the physical construction of the electrical vehicle. We also propose a new algorithm that computes energy optimal paths that are more acceptable by the driver, because it also takes into consideration the time metric while computing the path.