Search NASA⌕ Search

SEARCH · Search NASA

Results for “Routing algorithm”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 19 records
All sourcesNASA NTRSDOE OSTI
NASA NTRS2004

Routing Algorithm Exploits Spatial Relations

A recently developed routing algorithm for broadcasting in an ad hoc wireless communication network takes account of, and exploits, the spatial relationships among the locations of nodes, in addition to transmission power levels and distances between the nodes. In contrast, most prior algorithms for discovering routes through ad hoc networks rely heavily on transmission power levels and utilize limited graph-topology techniques that do not involve consideration of the aforesaid spatial relationships. The present algorithm extracts the relevant spatial-relationship information by use of a construct denoted the relative-neighborhood graph (RNG).

Okino, Clayton↗
NASA NTRS2016

Transmission Scheduling and Routing Algorithms for Delay Tolerant Networks

The challenges of data processing, transmission scheduling and routing within a space network present a multi-criteria optimization problem. Long delays, intermittent connectivity, asymmetric data rates and potentially high error rates make traditional networking approaches unsuitable. The delay tolerant networking architecture and protocols attempt to mitigate many of these issues, yet transmission scheduling is largely manually configured and routes are determined by a static contact routing graph. A high level of variability exists among the requirements and environmental characteristics of different missions, some of which may allow for the use of more opportunistic routing methods. In all cases, resource allocation and constraints must be balanced with the optimization of data throughput and quality of service. Much work has been done researching routing techniques for terrestrial-based challenged networks in an attempt to optimize contact opportunities and resource usage. This paper examines several popular methods to determine their potential applicability to space networks.

Space Networking↗
NASA NTRS2010

Design and Evaluation of a Dynamic Programming Flight Routing Algorithm Using the Convective Weather Avoidance Model

The optimization of traffic flows in congested airspace with varying convective weather is a challenging problem. One approach is to generate shortest routes between origins and destinations while meeting airspace capacity constraint in the presence of uncertainties, such as weather and airspace demand. This study focuses on development of an optimal flight path search algorithm that optimizes national airspace system throughput and efficiency in the presence of uncertainties. The algorithm is based on dynamic programming and utilizes the predicted probability that an aircraft will deviate around convective weather. It is shown that the running time of the algorithm increases linearly with the total number of links between all stages. The optimal routes minimize a combination of fuel cost and expected cost of route deviation due to convective weather. They are considered as alternatives to the set of coded departure routes which are predefined by FAA to reroute pre-departure flights around weather or air traffic constraints. A formula, which calculates predicted probability of deviation from a given flight path, is also derived. The predicted probability of deviation is calculated for all path candidates. Routes with the best probability are selected as optimal. The predicted probability of deviation serves as a computable measure of reliability in pre-departure rerouting. The algorithm can also be extended to automatically adjust its design parameters to satisfy the desired level of reliability.

Ng, Hok K.↗
DOE OSTI2017

A multi criteria analog model for assessing the vulnerability of rural catchments to road spills of hazardous substances

Road spills of hazardous substances are common in developing countries due to increasing industrialization and traffic accidents, and represent a serious threat to soils and water in catchments. There is abundant literature on equations describing the wash-off of pollutants from roads during a storm event and there are a number of watershed models incorporating those equations in storm water quality algorithms that route runoff and pollution yields through a drainage system towards the catchment outlet. However, methods describing catchment vulnerability to contamination by road spills based solely on biophysical parameters are scarce. These methods could be particularly attractive to managers because they can operate with a limited amount of easily collectable data, while still being able to provide important insights on the areas more prone to contamination within the studied watershed. The purpose of this paper was then to contribute with a new vulnerability model. To accomplish the goal, a selection of medium properties appearing in wash-off equations and routing algorithms were assembled and processed in a parametric framework based on multi criteria analysis to define the watershed vulnerability. However, parameters had to be adapted because wash-off equations and water quality models have been developed to operate primarily in the urban environment while the vulnerability model is meant to run in rural watersheds. The selected parameters were hillside slope, ground roughness (depending on land use), soil permeability (depending on soil type), distance to water courses and stream density. The vulnerability model is a spatially distributed algorithm that was prepared to run under the IDRISI Selva software, a GIS platform capable of handling spatial and alphanumeric data and execute the necessary terrain model, hydrographic and thematic analyses. For illustrative purposes, the vulnerability model was applied to the legally protected Environmental Protection Area (APA), located in the Uberaba region, state of Minas Gerais, Brazil. In this region, the risk of accidents causing chemical spills is preoccupying because large quantities of dangerous materials are transported in two important distribution highways while the APA is fundamental for the protection of water resources, the riverine ecosystems and remnants of native vegetation. In some tested scenarios, model results show 60% of vulnerable areas within the studied area. The most sensitive parameter to vulnerability is soil type. To prevent soils from contamination, specific measures were proposed involving minimization of land use conflicts that would presumably raise the soil's organic matter and in the sequel restore the soil's structural functions. Additionally, the present study proposed the preservation and reinforcement of riparian forests as one measure to protect the quality of surface water. - Highlights: • A multi criteria analog model was developed to assess rural catchment vulnerability along roads. • Model parameters were defined by analogy with urban wash-off equations and routing algorithms. • The model mixes up various biophysical and socio-economic parameters. • Model application was based on a scenario analysis. • The study is focused on the Environmental Protection Area of Uberaba River, Brazil.

54 ENVIRONMENTAL SCIENCES↗
NASA NTRS2010

Route Generation for a Synthetic Character (BOT) Using a Partial or Incomplete Knowledge Route Generation Algorithm in UT2004 Virtual Environment

This paper presents a new Route Generation Algorithm that accurately and realistically represents human route planning and navigation for Military Operations in Urban Terrain (MOUT). The accuracy of this algorithm in representing human behavior is measured using the Unreal Tournament(Trademark) 2004 (UT2004) Game Engine to provide the simulation environment in which the differences between the routes taken by the human player and those of a Synthetic Agent (BOT) executing the A-star algorithm and the new Route Generation Algorithm can be compared. The new Route Generation Algorithm computes the BOT route based on partial or incomplete knowledge received from the UT2004 game engine during game play. To allow BOT navigation to occur continuously throughout the game play with incomplete knowledge of the terrain, a spatial network model of the UT2004 MOUT terrain is captured and stored in an Oracle 11 9 Spatial Data Object (SOO). The SOO allows a partial data query to be executed to generate continuous route updates based on the terrain knowledge, and stored dynamic BOT, Player and environmental parameters returned by the query. The partial data query permits the dynamic adjustment of the planned routes by the Route Generation Algorithm based on the current state of the environment during a simulation. The dynamic nature of this algorithm more accurately allows the BOT to mimic the routes taken by the human executing under the same conditions thereby improving the realism of the BOT in a MOUT simulation environment.

Hanold, Gregg T.↗
NASA NTRS1996

A Formal Algorithm for Routing Traces on a Printed Circuit Board

This paper addresses the classical problem of printed circuit board routing: that is, the problem of automatic routing by a computer other than by brute force that causes the execution time to grow exponentially as a function of the complexity. Most of the present solutions are either inexpensive but not efficient and fast, or efficient and fast but very costly. Many solutions are proprietary, so not much is written or known about the actual algorithms upon which these solutions are based. This paper presents a formal algorithm for routing traces on a print- ed circuit board. The solution presented is very fast and efficient and for the first time speaks to the question eloquently by way of symbolic statements.

Hedgley, David R., Jr.↗
NASA NTRS2018

Evaluation of Opportunistic Contact Graph Routing in Random Mobility Environments

Routing in networks where nodes move randomly is particularly challenging due their potentially unpredictable, and rapidly changing topology. Several routing algorithms have been presented in the literature to address the needs of such networks, most of them implementing variants of controlled network flooding in the hope of successful data delivery. In this note, we compare the results of previous routing algorithms with Opportunistic Contact Graph Routing (OCGR), an enhanced version of Contact Graph Routing (CGR) that is suitable for networks where contacts cannot always be scheduled ahead of time. To perform the benchmark, we simulate a network of nodes moving in a certain space according to the Random Waypoint Mobility Model, and then take measurements of bundle delivery probabilty and overhead ratio as metrics of performance and cost respectively. Through this exercise, we demonstrate that the performance of OCGR is highly dependent on the type of network under consideration (e.g. very sparse vs. densely connected) and the assumed mobility model.

Burleigh, Scott↗
DOE OSTI2022

Controller-Based Energy-Aware Wireless Sensor Network Routing Using Quantum Algorithms

Energy-efficient routing in wireless sensor networks has attracted attention from researchers in both academia and industry, most recently motivated by the opportunity to use software-defined network-inspired approaches. These problems are NP-hard, with algorithms needing computation time that scales faster than polynomials in the problem size. Consequently, heuristic algorithms are used in practice, which are unable to guarantee optimally. In this article, we show proof-of-principle for the use of a quantum annealing processor instead of a classical processor, to find optimal or nearly optimal solutions very quickly. Our preliminary results for small networks show that this approach using quantum computing has great promise and may open the door for other significant improvements in the efficacy of network algorithms.

42 ENGINEERING↗
NASA NTRS1993

Adaptive laser link reconfiguration using constraint propagation

This paper describes Harris AI research performed on the Adaptive Link Reconfiguration (ALR) study for Rome Lab, and focuses on the application of constraint propagation to the problem of link reconfiguration for the proposed space based Strategic Defense System (SDS) Brilliant Pebbles (BP) communications system. According to the concept of operations at the time of the study, laser communications will exist between BP's and to ground entry points. Long-term links typical of RF transmission will not exist. This study addressed an initial implementation of BP's based on the Global Protection Against Limited Strikes (GPALS) SDI mission. The number of satellites and rings studied was representative of this problem. An orbital dynamics program was used to generate line-of-site data for the modeled architecture. This was input into a discrete event simulation implemented in the Harris developed COnstraint Propagation Expert System (COPES) Shell, developed initially on the Rome Lab BM/C3 study. Using a model of the network and several heuristics, the COPES shell was used to develop the Heuristic Adaptive Link Ordering (HALO) Algorithm to rank and order potential laser links according to probability of communication. A reduced set of links based on this ranking would then be used by a routing algorithm to select the next hop. This paper includes an overview of Constraint Propagation as an Artificial Intelligence technique and its embodiment in the COPES shell. It describes the design and implementation of both the simulation of the GPALS BP network and the HALO algorithm in COPES. This is described using a 59 Data Flow Diagram, State Transition Diagrams, and Structured English PDL. It describes a laser communications model and the heuristics involved in rank-ordering the potential communication links. The generation of simulation data is described along with its interface via COPES to the Harris developed View Net graphical tool for visual analysis of communications networks. Conclusions are presented, including a graphical analysis of results depicting the ordered set of links versus the set of all possible links based on the computed Bit Error Rate (BER). Finally, future research is discussed which includes enhancements to the HALO algorithm, network simulation, and the addition of an intelligent routing algorithm for BP.

Crone, M. S.↗
NASA NTRS1990

A parallel algorithm for global routing

A Parallel Hierarchical algorithm for Global Routing (PHIGURE) is presented. The router is based on the work of Burstein and Pelavin, but has many extensions for general global routing and parallel execution. Main features of the algorithm include structured hierarchical decomposition into separate independent tasks which are suitable for parallel execution and adaptive simplex solution for adding feedthroughs and adjusting channel heights for row-based layout. Alternative decomposition methods and the various levels of parallelism available in the algorithm are examined closely. The algorithm is described and results are presented for a shared-memory multiprocessor implementation.

Brouwer, Randall J.↗
NASA NTRS1992

Multicast Routing of Hierarchical Data

The issue of multicast of broadband, real-time data in a heterogeneous environment, in which the data recipients differ in their reception abilities, is considered. Traditional multicast schemes, which are designed to deliver all the source data to all recipients, offer limited performance in such an environment, since they must either force the source to overcompress its signal or restrict the destination population to those who can receive the full signal. We present an approach for resolving this issue by combining hierarchical source coding techniques, which allow recipients to trade off reception bandwidth for signal quality, and sophisticated routing algorithms that deliver to each destination the maximum possible signal quality. The field of hierarchical coding is briefly surveyed and new multicast routing algorithms are presented. The algorithms are compared in terms of network utilization efficiency, lengths of paths, and the required mechanisms for forwarding packets on the resulting paths.

Shacham, Nachum↗
NASA NTRS2016

A Mathematical Model and Algorithm for Routing Air Traffic Under Weather Uncertainty

A central challenge in managing today's commercial en route air traffic is the task of routing the aircraft in the presence of adverse weather. Such weather can make regions of the airspace unusable, so all affected flights must be re-routed. Today this task is carried out by conference and negotiation between human air traffic controllers (ATC) responsible for the involved sectors of the airspace. One can argue that, in so doing, ATC try to solve an optimization problem without giving it a precise quantitative formulation. Such a formulation gives the mathematical machinery for constructing and verifying algorithms that are aimed at solving the problem. This paper contributes one such formulation and a corresponding algorithm. The algorithm addresses weather uncertainty and has closed form, which allows transparent analysis of correctness, realism, and computational costs.

uncertainty↗
NASA NTRS1988

Experiences with serial and parallel algorithms for channel routing using simulated annealing

Two algorithms for channel routing using simulated annealing are presented. Simulated annealing is an optimization methodology which allows the solution process to back up out of local minima that may be encountered by inappropriate selections. By properly controlling the annealing process, it is very likely that the optimal solution to an NP-complete problem such as channel routing may be found. The algorithm presented proposes very relaxed restrictions on the types of allowable transformations, including overlapping nets. By freeing that restriction and controlling overlap situations with an appropriate cost function, the algorithm becomes very flexible and can be applied to many extensions of channel routing. The selection of the transformation utilizes a number of heuristics, still retaining the pseudorandom nature of simulated annealing. The algorithm was implemented as a serial program for a workstation, and a parallel program designed for a hypercube computer. The details of the serial implementation are presented, including many of the heuristics used and some of the resulting solutions.

Brouwer, Randall Jay↗
DOE OSTI2018

Mass imbalances in EPANET water-quality simulations

EPANET is widely employed to simulate water quality in water distribution systems. However, in general, the time-driven simulation approach used to determine concentrations of water-quality constituents provides accurate results only for short water-quality time steps. Overly long time steps can yield errors in concentration estimates and can result in situations in which constituent mass is not conserved. The use of a time step that is sufficiently short to avoid these problems may not always be feasible. The absence of EPANET errors or warnings does not ensure conservation of mass. This paper provides examples illustrating mass imbalances and explains how such imbalances can occur because of fundamental limitations in the water-quality routing algorithm used in EPANET. In general, these limitations cannot be overcome by the use of improved water-quality modeling practices. This paper also presents a preliminary event-driven approach that conserves mass with a water-quality time step that is as long as the hydraulic time step. Results obtained using the current approach converge, or tend to converge, toward those obtained using the preliminary event-driven approach as the water-quality time step decreases. Improving the water-quality routing algorithm used in EPANET could eliminate mass imbalances and related errors in estimated concentrations. Furthermore, the results presented in this paper should be of value to those who perform water-quality simulations using EPANET or use the results of such simulations, including utility managers and engineers.

54 ENVIRONMENTAL SCIENCES↗
NASA NTRSDate not supplied

Contact Multigraph Routing: Overview and Implementation

In Delay Tolerant Networking (DTN), the standard routing algorithm used to navigate time-varying networks has been Contact Graph Routing (CGR). In CGR, a globally distributed list of contacts, periods during which two DTN nodes may communicate, is used to construct a contact graph, in which contacts are vertices. A version of Dijkstra’s algorithm can then be used to find paths through this model of the timevarying network. However, since contact graphs may be large compared to the network, potentially growing with the square of the number of network nodes and linearly with the time interval represented, the resulting algorithm does not scale well with the size of the network or time. Any improvement to the routing algorithm will bring significant returns to scale. In a previous paper, we briefly introduced an alternative to the contact graph model for routing. This alternative model is based on a multigraph (a graph in which there may be multiple edges between a pair of vertices) where vertices represent network nodes instead of contacts. A version of Dijkstra’s algorithm in these multigraph models reduces the time needed to perform the same routing computations done in the existing CGR algorithm. Moreover, a modified version of Yen’s algorithm for multigraphs is included. Our variation of CGR, which we call Contact Multigraph Routing (CMR), provides an in-line replacement for the previously used pathfinding algorithms. This paper describes an implementation created based on the CMR approach, and experimental comparisons to traditional CGR are given. In addition, we explore some additional modifications to the routing pipeline traditionally assumed in CGR. These modifications range from the theoretical to the practical in terms of size and scope. We step forward our understanding of sheaftheoretic networking and describe how to model the routing pipeline using sheaves. We detail some enhanced route selection criteria that addresses some of the added complexity of DTNbased systems. We also include a future works section on future improvements and implementations that would be of service to the broader DTN community.

contact graph routing↗