I detta arbete har en trådad simulator tagits fram enligt standarden High Level Architecture (HLA). Simulatorn är kapabel att avgöra den kortaste vägen från alla noder till alla andra noder i ett radionätverk med 200 noder på i genomsnitt 263 millisekunder. Tidigare var det endast möjligt att simulera kommunikation mellan två noder i ett nätverk som hade direkt förbindelse med varandra. I och med detta tillägg kan kommunikationssignalen reläas fram genom nätverket om en direkt förbindelse inte är möjlig. Simulatorn, eller federatet som det kallas i HLA, bygger på en centraliserad routingalgoritm och kan konfigureras till att beräkna specifika vägar på begäran alternativt beräkna alla möjliga vägar genom nätverket utan att någon efterfrågan behövs. Simulatorn använder sig av en A*-algoritm som kan använda en av två heuristiker där den ena heuristiken tar fram den kortaste vägen mellan två noder i nätverket och den andra heuristiken tar fram den väg med bäst signalkvalitet mellan två noder. / This paper presents a threaded simulator designed according to the standard High Level Architecture (HLA). The simulator is capable of determining the shortest path from all nodes to all other nodes in a radio network with 200 nodes in 263 milliseconds on average. It was previously only possible to simulate communication between two nodes which had direct connection. As of this addition, the communication can be relayed through other nodes in the network if direct connection is not possible. The simulator, or federate as it is called in HLA, implements a centralised routing algorithm and can be configured to find specific paths on the basis of requests alternatively find all paths through the network without the need for any request. The simulator uses an A* (A-star) algorithm which can use one of two heuristics, one of which returns the shortest path and the other returns the path with the best signal quality.

Submitted by Fernando Souza (fernandoafsou@gmail.com) on 2017-08-21T13:50:24Z No. of bitstreams: 1 arquivototal.pdf: 2220137 bytes, checksum: 5d830e5d1ba6396c3e9ff56a19b08deb (MD5) / Made available in DSpace on 2017-08-21T13:50:24Z (GMT). No. of bitstreams: 1 arquivototal.pdf: 2220137 bytes, checksum: 5d830e5d1ba6396c3e9ff56a19b08deb (MD5) Previous issue date: 2016-02-26 / Multi-Robot System (MRS) consisting of multiple interacting robots, each running a specific control strategy, which is not driven centrally. Technical challenges arise from the need to develop complex, software-intensive products that take the constraints of the physical world into account. Make tools, methodologies and teams from different fields can work together is not an easy task to accomplish. Co-simulation represents on technique of validation in heterogeneous systems. Its fundamental principle is to provide support to execute different simulators in a cooperative way. A known standard is the High Level Architecture (HLA) that is a pattern described in IEEE 1516 series and has been developed to provide a common architecture to distributed model and simulation. Using HLA, several simulators and real applications could be simulated together. That way, this work presents a project for Multi-Robot Systems (SMR) simulation using ROS co-simulation with a network simulator, the OMNeT++, using HLA. The main goal is make the simulations more realistic, where the data exchange will be performed by using a simulated network, as if we had real robots interacting through a conventional network. To this end, an interface was developed between ROS and OMNeT++ using HLA. Experiments demonstrate that the packet losses were correctly simulated, adding realism to simulations. / Sistemas Multi-Robôs (SMR) consistem em múltiplos robôs interagindo, cada um executando uma estratégia de controle específica, que não é conduzida de forma centralizada. Alguns desafios surgiram da necessidade de desenvolver produtos que levem o mundo real em consideração. Fazer com que ferramentas, metodologias e equipes de diferentes áreas possam trabalhar juntas não é uma tarefa simples de ser realizada. Cossimulação representa uma técnica para validação de sistemas heterogêneos. Seu princípio fundamental é prover suporte à execução de diferentes simuladores de forma cooperativa. Um dos padrões para tal é conhecido como High Level Architecture (HLA), que é um padrão descrito no IEEE 1516 e tem sido desenvolvido para dispor uma arquitetura para modelagem e simulação distribuídos. Utilizando HLA, vários simuladores e aplicações reais podem ser simulados juntos. Sendo assim, este trabalho apresenta um projeto para simulação de Sistemas Multi-Robôs (SMR) utilizando ROS cossimulado com um simulador de redes de computadores, o OMNeT++ através do HLA. Seu principal objetivo é tornar as simulações mais próximas da realidade, onde os dados irão ser trocados através de uma rede simulada, como se tivéssemos robôs reais interagindo através de uma rede convencional. Para tal, foi desenvolvida a interface entre o ambiente ROS e o OMNeT++ com o HLA. Experimentos demonstraram que a perda de pacotes foi simulada corretamente, adicionando ao ambiente mais realismo

Dynamic balancing of computation and communication load is vital for the execution stability and performance of distributed, parallel simulations deployed on shared, unreliable resources of large-scale environments. High Level Architecture (HLA) based simulations can experience a decrease in performance due to imbalances that are produced initially and/or during run-time. These imbalances are generated by the dynamic load changes of distributed simulations or by unknown, non-managed background processes resulting from the non-dedication of shared resources. Due to the dynamic execution characteristics of elements that compose distributed simulation applications, the computational load and interaction dependencies of each simulation entity change during run-time. These dynamic changes lead to an irregular load and communication distribution, which increases overhead of resources and execution delays. A static partitioning of load is limited to deterministic applications and is incapable of predicting the dynamic changes caused by distributed applications or by external background processes. Due to the relevance in dynamically balancing load for distributed simulations, many balancing approaches have been proposed in order to offer a sub-optimal balancing solution, but they are limited to certain simulation aspects, specific to determined applications, or unaware of HLA-based simulation characteristics. Therefore, schemes for balancing the communication and computational load during the execution of distributed simulations are devised, adopting a hierarchical architecture. First, in order to enable the development of such balancing schemes, a migration technique is also employed to perform reliable and low-latency simulation load transfers. Then, a centralized balancing scheme is designed; this scheme employs local and cluster monitoring mechanisms in order to observe the distributed load changes and identify imbalances, and it uses load reallocation policies to determine a distribution of load and minimize imbalances. As a measure to overcome the drawbacks of this scheme, such as bottlenecks, overheads, global synchronization, and single point of failure, a distributed redistribution algorithm is designed. Extensions of the distributed balancing scheme are also developed to improve the detection of and the reaction to load imbalances. These extensions introduce communication delay detection, migration latency awareness, self-adaptation, and load oscillation prediction in the load redistribution algorithm. Such developed balancing systems successfully improved the use of shared resources and increased distributed simulations' performance.

The allocation of resources over time, referred to as resource scheduling, in large-scale construction environments is a challenging problem. Although traditional network scheduling techniques are the most popular scheduling techniques in the construction industry, they are ineffective in modeling the dynamic nature and resource interactions of large projects. Simulation based modeling or optimization techniques are also time-consuming, complicated and costly to be implemented in large-scale projects. This research is focused on developing a new framework to insert artificial intelligence inside construction simulations for facilitating the resource allocation process. The first stage in this study was developing a framework to solve resource scheduling problems in large scale construction projects. This framework, called the Simulation Based Auction Protocol (SBAP), integrates Multi-Agent Resource Allocation (MARA) in a simulation environment. This hybrid framework deploys centralized MARA (i.e., auction protocols) whereby agents bid on different combinations of resources at the start of a simulation cycle. Agents attempt to improve their individual welfare by acquiring a combination of resources. An auctioneer is designed to allocate resources to the agents by maximizing the overall welfare of the society. Simulation is also employed to track the availability of resources, and manage resource oriented activities. This framework is implemented in two large construction applications of scheduling module assembly yard and multiple heavy lift planning in modular construction. The second objective of this project is to develop a generic resource allocation component for addressing optimized resource allocation in various construction projects. This component is developed in a large scale model using High Level Architecture (HLA), instead of traditional simulation environments. HLA allows splitting a large scale model, known as a federation, into a number of manageable components (i.e., federates), while maintaining interoperability between them. A generic Resource Allocation (RA) federate is designed to act as an auctioneer for federates developed based on the SBAP. Another generic federate is also built to automate the communication with the RA federate. These two generic federates can be reused in various construction federations. This framework is successfully implemented in an industrial construction process that involves different supply chains including spool fabrication, module assembly and heavy crane lifts in site construction. / Construction Engineering and Management

Dynamic balancing of computation and communication load is vital for the execution stability and performance of distributed, parallel simulations deployed on shared, unreliable resources of large-scale environments. High Level Architecture (HLA) based simulations can experience a decrease in performance due to imbalances that are produced initially and/or during run-time. These imbalances are generated by the dynamic load changes of distributed simulations or by unknown, non-managed background processes resulting from the non-dedication of shared resources. Due to the dynamic execution characteristics of elements that compose distributed simulation applications, the computational load and interaction dependencies of each simulation entity change during run-time. These dynamic changes lead to an irregular load and communication distribution, which increases overhead of resources and execution delays. A static partitioning of load is limited to deterministic applications and is incapable of predicting the dynamic changes caused by distributed applications or by external background processes. Due to the relevance in dynamically balancing load for distributed simulations, many balancing approaches have been proposed in order to offer a sub-optimal balancing solution, but they are limited to certain simulation aspects, specific to determined applications, or unaware of HLA-based simulation characteristics. Therefore, schemes for balancing the communication and computational load during the execution of distributed simulations are devised, adopting a hierarchical architecture. First, in order to enable the development of such balancing schemes, a migration technique is also employed to perform reliable and low-latency simulation load transfers. Then, a centralized balancing scheme is designed; this scheme employs local and cluster monitoring mechanisms in order to observe the distributed load changes and identify imbalances, and it uses load reallocation policies to determine a distribution of load and minimize imbalances. As a measure to overcome the drawbacks of this scheme, such as bottlenecks, overheads, global synchronization, and single point of failure, a distributed redistribution algorithm is designed. Extensions of the distributed balancing scheme are also developed to improve the detection of and the reaction to load imbalances. These extensions introduce communication delay detection, migration latency awareness, self-adaptation, and load oscillation prediction in the load redistribution algorithm. Such developed balancing systems successfully improved the use of shared resources and increased distributed simulations' performance.

This thesis puts forth a process for ontology driven distributed simulation through a case study. Ontology is regarded as a domain model, including objects, attributes, methods and object relations. The case study involves trajectory simulation. A trajectory simulation is a piece of software that calculates the flight path and other parameters of a munition, such as its orientation and angular rates, from launch to impact. Formal specification of trajectory simulation domain is available as a domain model in the form of an ontology, called Trajectory Simulation ONTology (TSONT). Ontology driven federation development process proposed in this thesis is executed in three steps. The first step is to analyze the TSONT and to create instances of individuals guided by the requirements of the targeted simulation application, called Puma Trajectory Simulation. Puma is the simulation of a ficticious air-to-ground guided bomb. The second step is to create the High Level Architecture(HLA) Federation Object Model (FOM) using Puma Simulation individuals. FOM will include the required object and interaction definitions to enable information exchange among federation members, including the Puma federate and the Exercise Manager federate. Transformation from the ontology to FOM is realized in two ways: manually, and by using a tool called OWL2OMT. The third step is to implement the Trajectory Simulation federation based on the constructed FOM. Thus, the applicability of developing HLA federates and the federation under the guidance of ontology is demonstrated.

No description available.

As computer systems become increasingly complex and diverse, so too do the architectures they implement. This leads to an increase in complexity in the tools used to design new hardware and software. One particularly important tool in hardware and software design is the Instruction Set Simulator, which is used to prototype new architectures and hardware features, verify hardware, and test and debug software. Many Architecture Description Languages exist which facilitate the description of new architectural or hardware features, and generate a tools such as simulators. However, these typically suffer from poor performance, are difficult to test effectively, and may be limited in functionality. This thesis considers three objectives when developing Instruction Set Simulators: performance, correctness, and completeness, and presents techniques which contribute to each of these. Performance is obtained by combining Dynamic Binary Translation techniques with a novel analysis of high level architecture descriptions. This makes use of partial evaluation techniques in order to both improve the translation system, and to improve the quality of the translated code, leading a performance improvement of over 2.5x compared to a naïve implementation. This thesis also presents techniques which contribute to the correctness objective. Each possible behaviour of each described instruction is used to guide the generation of a test case. Constraint satisfaction techniques are used to determine the necessary instruction encoding and context for each behaviour to be produced. It is shown that this is a significant improvement over benchmark-driven testing, and this technique has led to the discovery of several bugs and inconsistencies in multiple state of the art instruction set simulators. Finally, several challenges in ‘Full System’ simulation are addressed, contributing to both the performance and completeness objectives. Full System simulation generally carries significant performance costs compared with other simulation strategies. Crucially, instructions which access memory require virtual to physical address translation and can now cause exceptions. Both of these processes must be correctly and efficiently handled by the simulator. This thesis presents novel techniques to address this issue which provide up to a 1.65x speedup over a state of the art solution.

Dynamic balancing of computation and communication load is vital for the execution stability and performance of distributed, parallel simulations deployed on shared, unreliable resources of large-scale environments. High Level Architecture (HLA) based simulations can experience a decrease in performance due to imbalances that are produced initially and/or during run-time. These imbalances are generated by the dynamic load changes of distributed simulations or by unknown, non-managed background processes resulting from the non-dedication of shared resources. Due to the dynamic execution characteristics of elements that compose distributed simulation applications, the computational load and interaction dependencies of each simulation entity change during run-time. These dynamic changes lead to an irregular load and communication distribution, which increases overhead of resources and execution delays. A static partitioning of load is limited to deterministic applications and is incapable of predicting the dynamic changes caused by distributed applications or by external background processes. Due to the relevance in dynamically balancing load for distributed simulations, many balancing approaches have been proposed in order to offer a sub-optimal balancing solution, but they are limited to certain simulation aspects, specific to determined applications, or unaware of HLA-based simulation characteristics. Therefore, schemes for balancing the communication and computational load during the execution of distributed simulations are devised, adopting a hierarchical architecture. First, in order to enable the development of such balancing schemes, a migration technique is also employed to perform reliable and low-latency simulation load transfers. Then, a centralized balancing scheme is designed; this scheme employs local and cluster monitoring mechanisms in order to observe the distributed load changes and identify imbalances, and it uses load reallocation policies to determine a distribution of load and minimize imbalances. As a measure to overcome the drawbacks of this scheme, such as bottlenecks, overheads, global synchronization, and single point of failure, a distributed redistribution algorithm is designed. Extensions of the distributed balancing scheme are also developed to improve the detection of and the reaction to load imbalances. These extensions introduce communication delay detection, migration latency awareness, self-adaptation, and load oscillation prediction in the load redistribution algorithm. Such developed balancing systems successfully improved the use of shared resources and increased distributed simulations' performance.

In this dissertation, we present an efficient algorithm, called P-Pruning algorithm, for data distribution management problem in High Level Architecture. High Level Architecture (HLA) presents a framework for modeling and simulation within the Department of Defense (DoD) and forms the basis of IEEE 1516 standard. The goal of this architecture is to interoperate multiple simulations and facilitate the reuse of simulation components. Data Distribution Management (DDM) is one of the six components in HLA that is responsible for limiting and controlling the data exchanged in a simulation and reducing the processing requirements of federates. DDM is also an important problem in the parallel and distributed computing domain, especially in large-scale distributed modeling and simulation applications, where control on data exchange among the simulated entities is required. We present a performance-evaluation simulation study of the P-Pruning algorithm against three techniques: region-matching, fixed-grid, and dynamic-grid DDM algorithms. The P-Pruning algorithm is faster than region-matching, fixed-grid, and dynamic-grid DDM algorithms as it avoid the quadratic computation step involved in other algorithms. The simulation results show that the P-Pruning DDM algorithm uses memory at run-time more efficiently and requires less number of multicast groups as compared to the three algorithms. To increase the scalability of P-Pruning algorithm, we develop a resource-efficient enhancement for the P-Pruning algorithm. We also present a performance evaluation study of this resource-efficient algorithm in a memory-constraint environment. The Memory-Constraint P-Pruning algorithm deploys I/O efficient data-structures for optimized memory access at run-time. The simulation results show that the Memory-Constraint P-Pruning DDM algorithm is faster than the P-Pruning algorithm and utilizes memory at run-time more efficiently. It is suitable for high performance distributed simulation applications as it improves the scalability of the P-Pruning algorithm by several order in terms of number of federates. We analyze the computation complexity of the P-Pruning algorithm using average-case analysis. We have also extended the P-Pruning algorithm to three-dimensional routing space. In addition, we present the P-Pruning algorithm for dynamic conditions where the distribution of federated is changing at run-time. The dynamic P-Pruning algorithm investigates the changes among federates regions and rebuilds all the affected multicast groups. We have also integrated the P-Pruning algorithm with FDK, an implementation of the HLA architecture. The integration involves the design and implementation of the communicator module for mapping federate interest regions. We provide a modular overview of P-Pruning algorithm components and describe the functional flow for creating multicast groups during simulation. We investigate the deficiencies in DDM implementation under FDK and suggest an approach to overcome them using P-Pruning algorithm. We have enhanced FDK from its existing HLA 1.3 specification by using IEEE 1516 standard for DDM implementation. We provide the system setup instructions and communication routines for running the integrated on a network of machines. We also describe implementation details involved in integration of P-Pruning algorithm with FDK and provide results of our experiences.