Search NASA⌕ Search

SEARCH · Search NASA

Results for “Routing”

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 91 records · Page 5
All sourcesNASA NTRSDOE OSTI
NASA NTRSDate not supplied

Aerial Vehicle Routing and Scheduling for UAS Traffic Management: A Monte Carlo Tree Search Approach

Numerous unmanned aircraft systems operating at low altitudes to deliver goods and services may one day become ubiquitous in our cities. In the Unmanned Aircraft Systems (UAS) Traffic Management (UTM) framework, such a concept is envisioned, where aerial vehicles operate beyond visual line of sight (BVLOS) within specifically reserved and time stamped “corridors” in the airspace. For example, these corridors or operational intent volumes can connect an aerial vehicle’s origin site to its destination site for package delivery operations. There may also be more than one corridor available for an aerial vehicle to choose from and often different corridors may intersect with one another. Thus, it is imperative to ensure flight trajectories belonging to different aerial vehicles are not in conflict. Per the UTM CONOPs, we assume that a vehicle almost always stays inside its corridor or operational volume. This work provides a framework for strategic deconfliction of UTM or package delivery drones, where we schedule the departure time of all vehicles subject to various temporal constraints (including the corridor deconfliction at the intersections). We present the “multi-route weighted package delivery problem” which serves as an exemplifying model for strategic deconfliction in UTM. In the multi-route weighted package delivery problem, a graph network is given which consists of a set of depots (source) and drop-off (destination) nodes, with multiple routes (defined as a sequence of waypoints) connecting the depots to drop-off nodes. In addition, routes are weighted by the associated ground risk and total travel distance for package delivery. The goal is for a known set of aerial vehicles to depart from the depots, choose a route and take off time, while avoiding conflicts with other aerial vehicles, and minimizing both risk and distance traveled. We provide a mixed integer linear programming (MILP) formulation of the problem, as well as a heuristic solution based on Monte Carlo Tree Search (MCTS) – a method used in game theory and artificial intelligence – to overcome limitations inherent to optimal solvers. Computational results show the advantages of using MCTS over the MILP formulation; the former can provide a sub-optimal solution quickly, and may sometimes even reach an optimal solution, whereas the latter may not even produce a solution in reasonable time. Furthermore, results from both the MILP formulation and MCTS methods were validated using a preliminary agent-based simulator implementing the UTM concept of operations. Thus, the MCTS method can be seen as a scalable solution to the complex multi-route weighted package delivery problem and may possibly be extended to similar complex optimization problems.

Kenny Chour↗
NASA NTRSDate not supplied

Multi-Domain Routing in Delay Tolerant Networks

The goal of Delay Tolerant Networking (DTN) is to provide the missing ingredient for the ever-growing collection of communicating nodes in our solar system to become a Solar System Internet (SSI). Great strides have been made in modeling particular types of DTNs, such as schedule- or discovery-based. Now, analogously to the Internet, these smaller DTNs can be considered routing domains which must be stitched together to form the overall SSI. In this paper, we propose a framework for cross-domain routing in DTNs as well as methodologies for detecting these sub-domains. Example time-varying networks are given to demonstrate the techniques proposed. A basic component is the mathematical theory of sheaves, which unifies the underlying model of DTN routing algorithms, by giving rise to routing sheaves – these can be defined for the dynamic and scheduled networks as noted above, and can also be used to define the interfaces between these domains in order to route across them. An immediate application would be routing across discovery-based networks connected by scheduled networks. These DTN subdomains remain elusive, however, and need to become well-defined and properly sized for tractable computability. In particular, a balance must be determined between areas that are too large (i.e. large matrix computations) versus areas that are too small (i.e. “many” single-noded domains). Moreover, the connections between the domains should, at least locally, be chosen to optimize data flow and connectivity: we address this in three ways. First, tools from persistent homology are given to understand underlying structures, reminiscent of hierarchies in the Internet Protocol (IP) addressing. Second, we construct a notion of temporal graph curvature based on network geometry to analyze flows induced by dynamical processes on these networks. Finally, Schrodinger Bridges, a tool arising from statistical physics, are proposed as a method of constructing flows on time-evolving networks with desirable properties such as speed, robustness, and load sensitivity. We construct an approach to temporal hypergraphs to simultaneously model unicast, multicast, and broadcast, using the language of scheme theory, and then consider DTN network coding as a way to achieve network-level computation and organization. The paper concludes with a discussion and ideas for future work.

Alan Hylton↗
DOE OSTI2025

Evaluation of Flow Routing on the Unstructured Voronoi Meshes in Earth System Modeling

Flow routing is a fundamental process of Earth System Models' (ESMs) river component. Traditional flow routing models rely on Cartesian rectangular meshes, which exhibit limitations, particularly when coupled with unstructured mesh-based ocean components. They also lack the support for regionally refined models. While previous studies have highlighted the potential benefits of unstructured meshes for flow routing, their widespread application and comprehensive evaluation within ESMs remain limited. This study extends the river component of the Energy Exascale Earth System Model to unstructured Voronoi meshes. We evaluated the model's performance in simulating river discharge and water depth across three watersheds spanning the Arctic, temperate, and tropical regions. The results show that while providing several benefits, unstructured mesh-based flow routing can achieve comparable performance to structured mesh-based routing, and their difference is often less than 10%. Although the unstructured mesh-based method could address several existing limitations, this research also shows that additional improvements in the numerical method are needed to fully exploit the advantages of unstructured mesh for hydrologic and ESMs.

54 ENVIRONMENTAL SCIENCES↗
DOE OSTI2025

Discrete global grid system-based flow routing datasets in the Amazon and Yukon basins

Abstract. Discrete global grid systems (DGGS) are emerging spatial data structures widely used to organize geospatial datasets across scales. While DGGS have found applications in various scientific disciplines, including atmospheric science and ecology, their integration into physically based hydrological models and Earth system models (ESMs) has been hindered by the lack of flow routing datasets based on DGGS. In response to this gap, this study pioneers the development of new flow routing datasets using icosahedral Snyder equal-area (ISEA) DGGS and a novel mesh-independent flow direction model. We present flow routing datasets for two large basins, the tropical Amazon River basin and the Arctic Yukon River basin. These datasets (1) facilitate the adoption of DGGS for hydrological models and (2) provide flow routing inputs for evaluation of DGGS-based flow routing in the Amazon and Yukon river basins. The data are available at https://doi.org/10.5281/zenodo.8377765 (Liao, 2023).

54 ENVIRONMENTAL SCIENCES↗
NASA NTRS2016

Toward a Unified Routing Framework for Delay-Tolerant Networking

Routing in Delay-/Disruption-Tolerant Networking (DTN) has long been recognized as a challenging research topic. The difficulty lies in the fact that link intermittency and network partitioning, possibly coupled with long delays, prevent the use of Internet solutions based on an up-to-date comprehensive knowledge of network topology, as communicated by routing protocols. In the literature on DTN routing, there is a dichotomy between solutions designed for deterministic (e.g., space flight) networks, such as Contact Graph Routing (CGR), and the wide variety of protocols designed for opportunistic terrestrial networks. After a discussion of the origin and motivations of this duality, the paper presents an opportunistic extension of CGR (OCGR). The aim is to try to resolve the DTN routing dichotomy by providing a unified approach suitable for all DTN environments.

Routing↗
DOE OSTI2024

Enhancing Acute Migraine Treatment: Exploring Solid Lipid Nanoparticles and Nanostructured Lipid Carriers for the Nose-to-Brain Route

Migraine has a high prevalence worldwide and is one of the main disabling neurological diseases in individuals under the age of 50. In general, treatment includes the use of oral analgesics or non-steroidal anti-inflammatory drugs (NSAIDs) for mild attacks, and, for moderate or severe attacks, triptans or 5-HT1B/1D receptor agonists. However, the administration of antimigraine drugs in conventional oral pharmaceutical dosage forms is a challenge, since many molecules have difficulty crossing the blood-brain barrier (BBB) to reach the brain, which leads to bioavailability problems. Efforts have been made to find alternative delivery systems and/or routes for antimigraine drugs. In vivo studies have shown that it is possible to administer drugs directly into the brain via the intranasal (IN) or the nose-to-brain route, thus avoiding the need for the molecules to cross the BBB. In this field, the use of lipid nanoparticles, in particular solid lipid nanoparticles (SLN) and nanostructured lipid carriers (NLC), has shown promising results, since they have several advantages for drugs administered via the IN route, including increased absorption and reduced enzymatic degradation, improving bioavailability. Furthermore, SLN and NLC are capable of co-encapsulating drugs, promoting their simultaneous delivery to the site of therapeutic action, which can be a promising approach for the acute migraine treatment. This review highlights the potential of using SLN and NLC to improve the treatment of acute migraine via the nose-to-brain route. First sections describe the pathophysiology and the currently available pharmacological treatment for acute migraine, followed by an outline of the mechanisms underlying the nose-to-brain route. Afterwards, the main features of SLN and NLC and the most recent in vivo studies investigating the use of these nanoparticles for the treatment of acute migraine are presented.

Torres, Joana (ORCID:0000000327276229)↗
NASA NTRS1987

Automatic routing module

Automatic Routing Module (ARM) is a tool to partially automate Air Launched Cruise Missile (ALCM) routing. For any accessible launch point or target pair, ARM creates flyable routes that, within the fidelity of the models, are optimal in terms of threat avoidance, clobber avoidance, and adherence to vehicle and planning constraints. Although highly algorithmic, ARM is an expert system. Because of the heuristics applied, ARM generated routes closely resemble manually generated routes in routine cases. In more complex cases, ARM's ability to accumulate and assess threat danger in three dimensions and trade that danger off with the probability of ground clobber results in the safest path around or through difficult areas. The tools available prior to ARM did not provide the planner with enough information or present it in such a way that ensured he would select the safest path.

Malin, Janice A.↗
NASA NTRS1987

Route planning in a four-dimensional environment

Robots must be able to function in the real world. The real world involves processes and agents that move independently of the actions of the robot, sometimes in an unpredictable manner. A real-time integrated route planning and spatial representation system for planning routes through dynamic domains is presented. The system will find the safest most efficient route through space-time as described by a set of user defined evaluation functions. Because the route planning algorthims is highly parallel and can run on an SIMD machine in O(p) time (p is the length of a path), the system will find real-time paths through unpredictable domains when used in an incremental mode. Spatial representation, an SIMD algorithm for route planning in a dynamic domain, and results from an implementation on a traditional computer architecture are discussed.

Slack, M. G.↗
NASA NTRS1990

Depth-first search approach for fault-tolerant routing in hypercube multicomputers

Using depth-first search, the authors develop and analyze the performance of a routing scheme for hypercube multicomputers in the presence of an arbitrary number of faulty components. They derive an exact expression for the probability of routing messages by way of optimal paths (of length equal to the Hamming distance between the corresponding pair of nodes) from the source node to an obstructed node. The obstructed node is defined as the first node encountered by the message that finds no optimal path to the destination node. It is noted that the probability of routing messages over an optimal path between any two nodes is a special case of the present results and can be obtained by replacing the obstructed node with the destination node. Numerical examples are given to illustrate the results, and they show that, in the presence of component failures, depth-first search routing can route a message to its destination by means of an optimal path with a very high probability.

Chen, Ming-Syan↗
NASA NTRS1992

Optimal routing and buffer allocation for a class of finite capacity queueing systems

The problem of routing jobs to K parallel queues with identical exponential servers and unequal finite buffer capacities is considered. Routing decisions are taken by a controller which has buffering space available to it and may delay routing of a customer to a queue. Using ideas from weak majorization, it is shown that the shorter nonfull queue delayed (SNQD) policy minimizes both the total number of customers in the system at any time and the number of customers that are rejected by that time. The SNQD policy always delays routing decisions as long as all servers are busy. Only when all the buffers at the controller are occupied is a customer routed to the queue with the shortest queue length that is not at capacity. Moreover, it is shown that, if a fixed number of buffers is to be distributed among the K queues, then the optimal allocation scheme is the one in which the difference between the maximum and minimum queue capacities is minimized, i.e., becomes either 0 or 1.

Towsley, Don↗
NASA NTRS1993

Strategic planning for aircraft noise route impact analysis: A three dimensional approach

The strategic routing of aircraft through navigable and controlled airspace to minimize adverse noise impact over sensitive areas is critical in the proper management and planning of the U.S. based airport system. A major objective of this phase of research is to identify, inventory, characterize, and analyze the various environmental, land planning, and regulatory data bases, along with potential three dimensional software and hardware systems that can be potentially applied for an impact assessment of any existing or planned air route. There are eight data bases that have to be assembled and developed in order to develop three dimensional aircraft route impact methodology. These data bases which cover geographical information systems, sound metrics, land use, airspace operational control measures, federal regulations and advisories, census data, and environmental attributes have been examined and aggregated. A three dimensional format is necessary for planning, analyzing space and possible noise impact, and formulating potential resolutions. The need to develop this three dimensional approach is essential due to the finite capacity of airspace for managing and planning a route system, including airport facilities. It appears that these data bases can be integrated effectively into a strategic aircraft noise routing system which should be developed as soon as possible, as part of a proactive plan applied to our FAA controlled navigable airspace for the United States.

Bragdon, C. R.↗
NASA NTRS2004

Adaptive Bio-Inspired Wireless Network Routing for Planetary Surface Exploration

Wireless mobile networks suffer connectivity loss when used in a terrain that has hills, and valleys when line of sight is interrupted or range is exceeded. To resolve this problem and achieve acceptable network performance, we have designed an adaptive, configurable, hybrid system to automatically route network packets along the best path between multiple geographically dispersed modules. This is very useful in planetary surface exploration, especially for ad-hoc mobile networks, where computational devices take an active part in creating a network infrastructure, and can actually be used to route data dynamically and even store data for later transmission between networks. Using inspiration from biological systems, this research proposes to use ant trail algorithms with multi-layered information maps (topographic maps, RF coverage maps) to determine the best route through ad-hoc network at real time. The determination of best route is a complex one, and requires research into the appropriate metrics, best method to identify the best path, optimizing traffic capacity, network performance, reliability, processing capabilities and cost. Real ants are capable of finding the shortest path from their nest to a food source without visual sensing through the use of pheromones. They are also able to adapt to changes in the environment using subtle clues. To use ant trail algorithms, we need to define the probability function. The artificial ant is, in this case, a software agent that moves from node to node on a network graph. The function to calculate the fitness (evaluate the better path) includes: length of the network edge, the coverage index, topology graph index, and pheromone trail left behind by other ant agents. Each agent modifies the environment in two different ways: 1) Local trail updating: As the ant moves between nodes it updates the amount of pheromone on the edge; and 2) Global trail updating: When all ants have completed a tour the ant that found the shortest route updates the edges in its path.

Alena, Richard I.↗
NASA NTRS1999

En route Spacing Tool: Efficient Conflict-free Spacing to Flow-Restricted Airspace

This paper describes the Air Traffic Management (ATM) problem within the U.S. of flow-restricted en route airspace, an assessment of its impact on airspace users, and a set of near-term tools and procedures to resolve the problem. The FAA is committed, over the next few years, to deploy the first generation of modem ATM decision support tool (DST) technology under the Free-Flight Phase-1 (FFp1) program. The associated en route tools include the User Request Evaluation Tool (URET) and the Traffic Management Advisor (TMA). URET is an initial conflict probe (ICP) capability that assists controllers with the detection and resolution of conflicts in en route airspace. TMA orchestrates arrivals transitioning into high-density terminal airspace by providing controllers with scheduled times of arrival (STA) and delay feedback advisories to assist with STA conformance. However, these FFPl capabilities do not mitigate the en route Miles-In-Trail (MIT) restrictions that are dynamically applied to mitigate airspace congestion. National statistics indicate that en route facilities (Centers) apply Miles-In-Trail (MIT) restrictions for approximately 5000 hours per month. Based on results from this study, an estimated 45,000 flights are impacted by these restrictions each month. Current-day practices for implementing these restrictions result in additional controller workload and an economic impact of which the fuel penalty alone may approach several hundred dollars per flight. To mitigate much of the impact of these restrictions on users and controller workload, a DST and procedures are presented. The DST is based on a simple derivative of FFP1 technology that is designed to introduce a set of simple tools for flow-rate (spacing) conformance and integrate them with conflict-probe capabilities. The tool and associated algorithms are described based on a concept prototype implemented within the CTAS baseline in 1995. A traffic scenario is used to illustrate the controller's use of the tool, and potential display options are presented for future controller evaluation.

Green, S.↗
NASA NTRS2006

Central East Pacific Flight Routing

With the introduction of the Federal Aviation Administration s Advanced Technology and Oceanic Procedures system at the Oakland Oceanic Center, a level of automation now exists in the oceanic environment to potentially begin accommodating increased user preferred routing requests. This paper presents the results of an initial feasibility assessment which examines the potential benefits of transitioning from the fixed Central East Pacific routes to user preferred routes. As a surrogate for the actual user-provided routing requests, a minimum-travel-time, wind-optimal dynamic programming algorithm was developed and utilized in this paper. After first describing the characteristics (e.g., origin airport, destination airport, vertical distribution and temporal distribution) of the westbound flights utilizing the Central East Pacific routes on Dec. 14-16 and 19-20, the results of both a flight-plan-based simulation and a wind-optimal-based simulation are presented. Whereas the lateral and longitudinal distribution of the aircraft trajectories in these two simulations varied dramatically, the number of simulated first-loss-of-separation events remained relatively constant. One area of concern that was uncovered in this initial analysis was a potential workload issue associated with the redistribution of traffic in the oceanic sectors due to thc prevailing wind patterns.

Grabbe, Shon↗
NASA NTRS2010

Interface Supports Lightweight Subsystem Routing for Flight Applications

A wireless avionics interface exploits the constrained nature of data networks in flight systems to use a lightweight routing method. This simplified routing means that a processor is not required, and the logic can be implemented as an intellectual property (IP) core in a field-programmable gate array (FPGA). The FPGA can be shared with the flight subsystem application. In addition, the router is aware of redundant subsystems, and can be configured to provide hot standby support as part of the interface. This simplifies implementation of flight applications requiring hot stand - by support. When a valid inbound packet is received from the network, the destination node address is inspected to determine whether the packet is to be processed by this node. Each node has routing tables for the next neighbor node to guide the packet to the destination node. If it is to be processed, the final packet destination is inspected to determine whether the packet is to be forwarded to another node, or routed locally. If the packet is local, it is sent to an Applications Data Interface (ADI), which is attached to a local flight application. Under this scheme, an interface can support many applications in a subsystem supporting a high level of subsystem integration. If the packet is to be forwarded to another node, it is sent to the outbound packet router. The outbound packet router receives packets from an ADI or a packet to be forwarded. It then uses a lookup table to determine the next destination for the packet. Upon detecting a remote subsystem failure, the routing table can be updated to autonomously bypass the failed subsystem.

Lux, James P.↗
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.↗
NASA NTRS2012

Near real-time traffic routing

A near real-time physical transportation network routing system comprising: a traffic simulation computing grid and a dynamic traffic routing service computing grid. The traffic simulator produces traffic network travel time predictions for a physical transportation network using a traffic simulation model and common input data. The physical transportation network is divided into a multiple sections. Each section has a primary zone and a buffer zone. The traffic simulation computing grid includes multiple of traffic simulation computing nodes. The common input data includes static network characteristics, an origin-destination data table, dynamic traffic information data and historical traffic data. The dynamic traffic routing service computing grid includes multiple dynamic traffic routing computing nodes and generates traffic route(s) using the traffic network travel time predictions.

Yang, Chaowei↗
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↗