Engineering Papers⌕ Search

SEARCH · Engineering Papers

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 235 records · Page 13

Tusas: A fully implicit parallel approach for coupled phase-field equations

In this study, we develop a fully-coupled, fully-implicit approach for phase-field modeling of solidification in metals and alloys. Predictive simulation of solidification in pure metals and metal alloys remains a significant challenge in the field of materials science, as microstructure formation during the solidification process plays a critical role in the properties and performance of the solid material. Our simulation approach consists of a finite element spatial discretization of the fully-coupled nonlinear system of partial differential equations at the microscale, which is treated implicitly in time with a preconditioned Jacobian-free Newton-Krylov method. The approach is algorithmically scalable as well as efficient due to an effective preconditioning strategy based on algebraic multigrid and block factorization. We implement this approach in the open-source Tusas framework, which is a general, flexible tool developed in C++ for solving coupled systems of nonlinear partial differential equations. The performance of our approach is analyzed in terms of algorithmic scalability and efficiency, while the computational performance of Tusas is presented in terms of parallel scalability and efficiency on emerging heterogeneous architectures. We demonstrate that modern algorithms, discretizations, and computational science, and heterogeneous hardware provide a robust route for predictive phase-field simulation of microstructure evolution during additive manufacturing.

97 MATHEMATICS AND COMPUTING↗

Joint optimization of logistics infrastructure investments and subsidies in a regional logistics network with CO 2 emission reduction targets

This study proposes an optimization model that simultaneously incorporates the selection of logistics infrastructure investments and subsidies for green transport modes to achieve specific CO 2 emission targets in a regional logistics network. The proposed model is formulated as a bi-level formulation, in which the upper level determines the optimal selection of logistics infrastructure investments and subsidies for green transport modes such that the benefit-cost ratio of the entire logistics system is maximized. The lower level describes the selected service routes of logistics users. A genetic and Frank-Wolfe hybrid algorithm is introduced to solve the proposed model. The proposed model is applied to the regional logistics network of Changsha City, China. Findings show that using the joint scheme of the selection of logistics infrastructure investments and green subsidies is more effective than using them solely. In conclusion, carbon emission reduction targets can significantly affect logistics infrastructure investments and subsidy levels.

29 ENERGY PLANNING, POLICY, AND ECONOMY↗

Formal Approach For Resilient Reachability based on End-System Route Agility

The deterministic nature of existing routing protocols has resulted into an ossified Internet with static and predictable network routes. This gives persistent attackers (e.g. eavesdroppers and DDoS attackers) plenty of time to study the network and identify the vulnerable links (critical) to plan a devastating and stealthy attack. Recently, route mutation approaches have been proposed to address such issues. However, these approaches incur significantly high overhead and depend upon the availability of disjoint routes in the network, which inherently limit their use for mission critical services. To cope with these issues, we extend the current routing architecture to consider end-hosts as routing elements, and present a formal method based agile defense mechanism to increase resiliency of the existing cyber infrastructure. The major contributions of this paper include: (1) formalization of efficient and resilient End to End (E2E) reachability problem as a constraint satisfaction problem, which identifies the potential end-hosts to reach a destination while satisfying resilience and QoS constraints, (2) design and implementation of a novel decentralized End Point Route Mutation (EPRM) protocol, and (3) design and implementation of planning algorithm to minimize the overlap between multiple flows, for the sake of maximizing the agility in the system. Our implementation and evaluation validates the correctness, effectiveness and scalability of the proposed approach.

Rauf, Usman↗

Performance Enhancement of APW+lo Calculations by Simplest Separation of Concerns

Full-potential linearized augmented plane wave (LAPW) and APW plus local orbital (APW+lo) codes differ widely in both their user interfaces and in capabilities for calculations and analysis beyond their common central task of all-electron solution of the Kohn–Sham equations. However, that common central task opens a possible route to performance enhancement, namely to offload the basic LAPW/APW+lo algorithms to a library optimized purely for that purpose. To explore that opportunity, we have interfaced the Exciting-Plus (“EP”) LAPW/APW+lo DFT code with the highly optimized SIRIUS multi-functional DFT package. This simplest realization of the separation of concerns approach yields substantial performance over the base EP code via additional task parallelism without significant change in the EP source code or user interface. We provide benchmarks of the interfaced code against the original EP using small bulk systems, and demonstrate performance on a spin-crossover molecule and magnetic molecule that are of size and complexity at the margins of the capability of the EP code itself.

Zhang, Long↗

Data acquisition and path selection decision making for an autonomous roving vehicle

The feasibility of using range/pointing angle data such as might be obtained by a laser rangefinder for the purpose of terrain evaluation in the 10-40 meter range on which to base the guidance of an autonomous rover was investigated. The decision procedure of the rapid estimation scheme for the detection of discrete obstacles has been modified to reinforce the detection ability. With the introduction of the logarithmic scanning scheme and obstacle identification scheme, previously developed algorithms are combined to demonstrate the overall performance of the intergrated route designation system using laser rangefinder. In an attempt to cover a greater range, 30 m to 100 mm, the problem estimating gradients in the presence of positioning angle noise at middle range is investigated.

Shen, C. N.↗

Modeling the weather with a data flow supercomputer

A static concept of data flow architecture is considered for a supercomputer for weather modeling. The machine level instructions are loaded into specific memory locations before computation is initiated, with only one instruction active at a time. The machine would have processing element, functional unit, array memory, memory routing and distribution routing network elements all contained on microprocessors. A value-oriented algorithmic language (VAL) would be employed and would have, as basic operations, simple functions deriving results from operand values. Details of the machine language format, computations with an array and file processing procedures are outlined. A global weather model is discussed in terms of a static architecture and the potential computation rate is analyzed. The results indicate that detailed design studies are warranted to quantify costs and parts fabrication requirements.

Dennis, J. B.↗

Introducing Tropical Geometric Approaches to Delay Tolerant Networking Optimization

Delay Tolerant Networking (DTN) is the standard approach to the networking of space systems with the goal of supporting the Solar System Internet (SSI). Current space networks have a small scale and often depend on rigorously scheduled (pre-determined) contact opportunities; this manual approach inhibits scalability. The goal of this paper is to recast these scheduling problems in order to apply the optimization machinery of tropical geometry. Contact opportunities in space are dependent on such factors as orbital mechanics and asset availability, which induce time-varying connectivity; indeed, end-to-end connectivity might never occur. Routing optimization within this structure is classically difficult and typically utilizes Dijkstra's algorithm as applied to contact graphs. Alternatively, we follow the successes of tropical geometry in train schedule optimization, job assignments, and even traditional networking, by extending this approach to this more general (i.e. disconnected) problem space. These successes imply tropical geometry provides a useful framework in the context of DTNs, starting with applications to queuing theory and long-haul links. Recently, tropical geometry has been applied to parametric path optimization on graphs with variable edge weights. In this work, we extend these advances to account for the problem of routing in a space network, and find that tropical geometry is well-suited to the challenges offered by this new setting, including contact schedules featuring probabilities. Our approach leverages the combinatorial nature of the problem to give feasible shortest path trees in the presence of variable channel conditions and latency, evolving topologies, and uncertainty inherent in space routing. We discuss our tropical approach to DTN for two Python implementations, a Verilog Tropical ALU implementation, tropical frameworks for other parametric graph problems, and solution stability. Lastly, a program for future work is included to illuminate the path ahead.

Delay Tolerant Networking↗

Automated Conflict Resolution For Air Traffic Control

The ability to detect and resolve conflicts automatically is considered to be an essential requirement for the next generation air traffic control system. While systems for automated conflict detection have been used operationally by controllers for more than 20 years, automated resolution systems have so far not reached the level of maturity required for operational deployment. Analytical models and algorithms for automated resolution have been traffic conditions to demonstrate that they can handle the complete spectrum of conflict situations encountered in actual operations. The resolution algorithm described in this paper was formulated to meet the performance requirements of the Automated Airspace Concept (AAC). The AAC, which was described in a recent paper [1], is a candidate for the next generation air traffic control system. The AAC's performance objectives are to increase safety and airspace capacity and to accommodate user preferences in flight operations to the greatest extent possible. In the AAC, resolution trajectories are generated by an automation system on the ground and sent to the aircraft autonomously via data link .The algorithm generating the trajectories must take into account the performance characteristics of the aircraft, the route structure of the airway system, and be capable of resolving all types of conflicts for properly equipped aircraft without requiring supervision and approval by a controller. Furthermore, the resolution trajectories should be compatible with the clearances, vectors and flight plan amendments that controllers customarily issue to pilots in resolving conflicts. The algorithm described herein, although formulated specifically to meet the needs of the AAC, provides a generic engine for resolving conflicts. Thus, it can be incorporated into any operational concept that requires a method for automated resolution, including concepts for autonomous air to air resolution.

Erzberger, Heinz↗

Cybersecurity Enhancement in Digital Substations: Hidden Markov Model-Based Smart Cyber Switching and Threat Response

The rising incidence of cyber-attacks on critical infrastructure and power grids poses significant threats to the stability and reliability of electrical substations, with potentially devastating consequences such as extended blackouts. This paper introduces an advanced cybersecurity framework aimed at safeguarding IEC 61850-based substations through the integration of software-defined networking (SDN) and digital twin (DT) technologies. The proposed DT-based framework employs smart cyber switching (SCS) for proactive threat mitigation and concurrent intelligent electronic device (CIED) for swift system restoration, thereby maintaining continuous operational integrity and robust cybersecurity defenses. Central to this framework is the adaptive port controller (APC), which enables dynamic port management to adapt to evolving threats, and an intrusion detection system (IDS) designed to detect and neutralize malicious attacks on IEC 61850-based sampled value (SV) and generic object-oriented substation event (GOOSE) messages within the substation’s communication network. Further, novel predictive intrusion detection and response (PIDR) algorithm is implemented on a digital substation (DS) to predict the best route to be taken by the attacker. The efficacy of these comprehensive cybersecurity frameworks is validated through rigorous simulations and a hardware-in-the-loop (HIL) testbed, showcasing the system’s ability to sustain substation operations amidst cyber-attacks.

Digital substation↗

Parallel discrete event simulation: A shared memory approach

With traditional event list techniques, evaluating a detailed discrete event simulation model can often require hours or even days of computation time. Parallel simulation mimics the interacting servers and queues of a real system by assigning each simulated entity to a processor. By eliminating the event list and maintaining only sufficient synchronization to insure causality, parallel simulation can potentially provide speedups that are linear in the number of processors. A set of shared memory experiments is presented using the Chandy-Misra distributed simulation algorithm to simulate networks of queues. Parameters include queueing network topology and routing probabilities, number of processors, and assignment of network nodes to processors. These experiments show that Chandy-Misra distributed simulation is a questionable alternative to sequential simulation of most queueing network models.

Reed, Daniel A.↗

Traffic routing for multicomputer networks with virtual cut-through capability

Consideration is given to the problem of selecting routes for interprocess communication in a network with virtual cut-through capability, while balancing the network load and minimizing the number of times that a message gets buffered. An approach is proposed that formulates the route selection problem as a minimization problem with a link cost function that depends upon the traffic through the link. The form of this cost function is derived using the probability of establishing a virtual cut-through route. The route selection problem is shown to be NP-hard, and an algorithm is developed to incrementally reduce the cost by rerouting the traffic. The performance of this algorithm is exemplified by two network topologies: the hypercube and the C-wrapped hexagonal mesh.

Kandlur, Dilip D.↗

An Elementary Algorithm for Autonomous Air Terminal Merging and Interval Management

A central element of air traffic management is the safe merging and spacing of aircraft during the terminal area flight phase. This paper derives and examines an algorithm for the merging and interval managing problem for Standard Terminal Arrival Routes. It describes a factor analysis for performance based on the distribution of arrivals, the operating period of the terminal, and the topology of the arrival routes; then presents results from a performance analysis and from a safety analysis for a realistic topology based on typical routes for a runway at Phoenix International Airport. The heart of the safety analysis is a statistical derivation on how to conduct a safety analysis for a local simulation when the safety requirement is given for the entire airspace.

White, Allan L.↗

Integrated Routing and Traffic Signal Control for CAVs via Reinforcement Learning Approach

Incorporating Connected and Automated Vehicles (CAVs) into urban traffic networks presents opportunities and challenges for traffic management systems. This paper aims to develop an integrated routing and traffic signal control system designed explicitly for CAVs, utilizing a Reinforcement Learning (RL) approach. The objective is to enhance traffic flow and improve overall transportation efficiency in the controlled areas. We propose an innovative framework that employs the Deep Reinforcement Learning (DRL) algorithm, especially the Deep Q-network (DQN), to dynamically adjust the number of vehicles in the routes and the duration of traffic signals. Our simulation results demonstrate that a DQN agent successfully optimizes the number of vehicles in the routes and traffic signal timings of traffic signal controllers, eventually reducing total travel time. The study illustrates the potential usage of RL-based systems in managing routing and traffic signals for CAVs, offering a promising opportunity for future urban traffic management strategies.

Park, Jiho [New York University]↗

A sweep algorithm for massively parallel simulation of circuit-switched networks

A new massively parallel algorithm is presented for simulating large asymmetric circuit-switched networks, controlled by a randomized-routing policy that includes trunk-reservation. A single instruction multiple data (SIMD) implementation is described, and corresponding experiments on a 16384 processor MasPar parallel computer are reported. A multiple instruction multiple data (MIMD) implementation is also described, and corresponding experiments on an Intel IPSC/860 parallel computer, using 16 processors, are reported. By exploiting parallelism, our algorithm increases the possible execution rate of such complex simulations by as much as an order of magnitude.

Gaujal, Bruno↗

Flight Deck Surface Trajectory-based Operations (STBO): Results of Piloted Simulations and Implications for Concepts of Operation (ConOps)

The results offour piloted medium-fidelity simulations investigating flight deck surface trajectory-based operations (STBO) will be reviewed. In these flight deck STBO simulations, commercial transport pilots were given taxi clearances with time and/or speed components and required to taxi to the departing runway or an intermediate traffic intersection. Under a variety of concept of operations (ConOps) and flight deck information conditions, pilots' ability to taxi in compliance with the required time of arrival (RTA) at the designated airport location was measured. ConOps and flight deck information conditions explored included: Availability of taxi clearance speed and elapsed time information; Intermediate RTAs at intermediate time constraint points (e.g., intersection traffic flow points); STBO taxi clearances via ATC voice speed commands or datal ink; and, Availability of flight deck display algorithms to reduce STBO RTA error. Flight Deck Implications. Pilot RTA conformance for STBO clearances, in the form of ATC taxi clearances with associated speed requirements, was found to be relatively poor, unless the pilot is required to follow a precise speed and acceleration/deceleration profile. However, following such a precise speed profile results in inordinate head-down tracking of current ground speed, leading to potentially unsafe operations. Mitigating these results, and providing good taxi RTA performance without the associated safety issues, is a flight deck avionics or electronic flight bag (EFB) solution. Such a solution enables pilots to meet the taxi route RTA without moment-by-moment tracking of ground speed. An avionics or EFB "error-nulling" algorithm allows the pilot to view the STBO information when the pilot determines it is necessary and when workload alloys, thus enabling the pilot to spread his/her attention appropriately and strategically on aircraft separation airport navigation, and the many other flight deck tasks concurrently required. Surface Traffic Management (STM) System Implications. The data indicate a number of implications regarding specific parameters for ATC/STM algorithm development. Pilots have a tendency to arrive at RTA points early with slow required speeds, on time for moderate speeds, and late with faster required speeds. This implies that ATC/STM algorithms should operate with middle-range speeds, similar to that of non-STBO taxi performance. Route length has a related effect: Long taxi routes increase the earliness with slow speeds and the lateness with faster speeds. This is likely due to the" open-loop" nature of the task in which the speed error compounds over a longer time with longer routes. Results showed that this may be mitigated by imposing a small number oftime constraint points each with their own RTAs effectively tuming a long route into a series of shorter routes - and thus improving RTA performance. STBO ConOps Implications. Most important is the impact that these data have for NextGen STM system ConOps development. The results of these experiments imply that it is not reasonable to expect pilots to taxi under a "Full STBO" ConOps in which pilots are expected to be at a predictable (x,y) airport location for every time (t). An STBO ConOps with a small number of intermediate time constraint points and the departing runway, however, is feasible, but only with flight deck equipage enabling the use of a display similar to the "error-nulling algorithm/display" tested.

Foyle, David C.↗

TU-CD-304-05: 4Ï€ Non-Coplanar Radiotherapy: From Mathematical Modeling to Clinical Implementation

Purpose: To develop and clinically implement 4π radiotherapy, an inverse optimization platform that maximally utilizes non-coplanar intensity modulated radiotherapy (IMRT) beams to significantly improve critical organ sparing. Methods: A 3D scanner was used to digitize the human and phantom subject surfaces, which were positioned in the computer assisted design (CAD) model of a TrueBeam machine to create a virtual geometrical model, based on which, the feasible beam space was calculated for different tumor locations. Beamlets were computed for all feasible beams using convolution/superposition. A column generation algorithm was employed to optimize patient specific beam orientations and fluence maps. Optimal routing through all selected beams were calculated by a level set method. The resultant plans were converted to XML files and delivered to phantoms in the TrueBeam developer mode. Finally, 4π plans were recomputed in Eclipse and manually delivered to recurrent GBM patients. Results: Compared to IMRT utilizing manually selected beams and volumetric modulated arc therapy plans, markedly improved dosimetry was observed using 4π for the brain, head and neck, liver, lung, and prostate patients. The improvements were due to significantly improved conformality and reduced high dose spillage to organs mediolateral to the PTV. The virtual geometrical model was experimentally validated. Safety margins with 99.9% confidence in collision avoidance were included to the model based model accuracy estimates determined via 300 physical machine to phantom distance measurements. Automated delivery in the developer mode was completed in 10 minutes and collision free. Manual 4 π treatment on the GBM cases resulted in significant brainstem sparing and took 35–45 minutes including multiple images, which showed submillimeter cranial intrafractional motion. Conclusion: The mathematical modeling utilized in 4π is accurate to create and guide highly complex non-coplanar IMRT treatments that consistently and significantly outperform human-operator-created plans. Deliverability of such plans is clinically demonstrated. This work is funded by Varian Medical Systems and the NSF Graduate Research Fellowship DGE-1144087.

60 APPLIED LIFE SCIENCES↗

Real-time processing of radar return on a parallel computer

NASA is working with the FAA to demonstrate the feasibility of pulse Doppler radar as a candidate airborne sensor to detect low altitude windshears. The need to provide the pilot with timely information about possible hazards has motivated a demand for real-time processing of a radar return. Investigated here is parallel processing as a means of accommodating the high data rates required. A PC based parallel computer, called the transputer, is used to investigate issues in real time concurrent processing of radar signals. A transputer network is made up of an array of single instruction stream processors that can be networked in a variety of ways. They are easily reconfigured and software development is largely independent of the particular network topology. The performance of the transputer is evaluated in light of the computational requirements. A number of algorithms have been implemented on the transputers in OCCAM, a language specially designed for parallel processing. These include signal processing algorithms such as the Fast Fourier Transform (FFT), pulse-pair, and autoregressive modelling, as well as routing software to support concurrency. The most computationally intensive task is estimating the spectrum. Two approaches have been taken on this problem, the first and most conventional of which is to use the FFT. By using table look-ups for the basis function and other optimizing techniques, an algorithm has been developed that is sufficient for real time. The other approach is to model the signal as an autoregressive process and estimate the spectrum based on the model coefficients. This technique is attractive because it does not suffer from the spectral leakage problem inherent in the FFT. Benchmark tests indicate that autoregressive modeling is feasible in real time.

Aalfs, David D.↗

Transport spatial model for the definition of green routes for city logistics centers

This paper presents a transport spatial decision support model (TSDSM) for carrying out the optimization of green routes for city logistics centers. The TSDSM model is based on the integration of the multi-criteria method of Weighted Linear Combination (WLC) and the modified Dijkstra algorithm within a geographic information system (GIS). The GIS is used for processing spatial data. The proposed model makes it possible to plan routes for green vehicles and maximize the positive effects on the environment, which can be seen in the reduction of harmful gas emissions and an increase in the air quality in highly populated areas. The scheduling of delivery vehicles is given as a problem of optimization in terms of the parameters of: the environment, health, use of space and logistics operating costs. Each of these input parameters was thoroughly examined and broken down in the GIS into criteria which further describe them. The model presented here takes into account the fact that logistics operators have a limited number of environmentally friendly (green) vehicles available. The TSDSM was tested on a network of roads with 127 links for the delivery of goods from the city logistics center to the user. The model supports any number of available environmentally friendly or environmentally unfriendly vehicles consistent with the size of the network and the transportation requirements. - Highlights: • Model for routing light delivery vehicles in urban areas. • Optimization of green routes for city logistics centers. • The proposed model maximizes the positive effects on the environment. • The model was tested on a real network.

54 ENVIRONMENTAL SCIENCES↗