The aim of this thesis is to conduct performance investigation of a combined system of Network Coding (NC) technique with Ant-Colony (ACO) routing protocol. This research analyses the impact of several workload characteristics, on system performance. Network coding is a significant key development of information transmission and processing. Network coding enhances the performance of multicast by employing encoding operations at intermediate nodes. Two steps should realize while using network coding in multicast communication: determining appropriate transmission paths from source to multi-receivers and using the suitable coding scheme. Intermediate nodes would combine several packets and relay them as a single packet. Although network coding can make a network achieve the maximum multicast rate, it always brings additional overheads. It is necessary to minimize unneeded overhead by using an optimization technique. On other hand, Ant Colony Optimization can be transformed into useful technique that seeks imitate the ant’s behaviour in finding the shortest path to its destination using quantities of pheromone that is left by former ants as guidance, so by using the same concept of the communication network environment, shorter paths can be formulated. The simulation results show that the resultant system considerably improves the performance of the network, by combining Ant Colony Optimization with network coding. 25% improvement in the bandwidth consumption can be achieved in comparison with conventional routing protocols. Additionally simulation results indicate that the proposed algorithm can decrease the computation time of system by a factor of 20%.

In this thesis, I introduce two new algorithms: Ant Brood Clustering-Intelligent Ants (ABC-INTE) and Ant Brood Clustering-Polymorphic Ants (ABC-POLY) for the graph clustering problem. ABC-INTE uses techniques such as hopping ants, relaxed drop function, ants with memories, stagnation control, and addition of k-means cluster retrieval process, as an improvement of the basic ABC-KLS algorithm. ABC-POLY uses two types of ants, inspired by the division of labour between the major and minor ants in Pheidole genus, as an improvement of ABC-INTE. For comparison purpose, I also implement MMAS, an ACO clustering algorithm. When tested on the benchmark networks, ABC-POLY outperforms or achieves the same modularity values as MMAS and ABC-INTE on 7 out of 10 networks and is robust against different graphs. In practice, the speed of ABC-POLY is at least 10 times faster than MMAS, making it a scalable algorithm compared to MMAS. ABC-POLY also outputs a direct visual representation of the natural clusters on the graph that is appealing to human observation. This thesis opens an interesting research topic to apply polymorphic ants for graph clustering in the ABC-POLY algorithm. The distributive and self-organization nature of ABC-POLY makes it a candidate for analyzing clusters in more complex and dynamic graphs. / May 2016

The Ant Colony Optimization belongs into the metaheuristic methods category and it has been developing quite recently. So far it has shown its capabalities to over-perform other metaheuristic methods in quality of the solutions. This work brings analysis of the possible applications of the method on the classical optimization combinatorial problems -- traveling salesman problem, vehicle routing problem, knapsack problem, generalized assignment problem and maximal clique problem. It also deals with the practical experiments with application on several optimization problems and analysis of the time and memory complexity of such algorithms. The last part of the work is dedicated to the possibility of parallelization of the algorithm, which was result of the application of the ACO method on the traveling salesman problem. It brings analysis of the crucial operations and data synchronization issues, as well as practical example and demonstration of the parallelized version of the algorithm.

As redes de sensores sem fio estão presentes nos mais diversos setores, formando um conjunto de elementos colaborativos que realizam o transporte da informação em cenários urbanos, agricultura de precisão, saúde e automação industrial. Sua utilização enfrenta desafios como necessidade constante de adaptações a alterações de topologia, baixas taxas de comunicação e uso eficiente de energia. Dessa forma, as aplicações dessas redes precisam suportar estas características dinamicamente. Esta tese propõe, então, um novo protocolo de roteamento: o HOFACO (Hybrid Objective Function based on Ant Colony Optimization), com base no funcionamento do padrão RPL (Routing Protocol for Low Power and Lossy Networks) aplicado à eficiência energética. Este protocolo proposto preserva as interfaces já consolidadas de roteamento e faz uso de uma informação heurística baseada em swarm intelligence (inteligência de enxames), por meio do uso de agentes - colônia de formigas -, para a composição híbrida de métricas utilizadas na avaliação do rank durante a construção de topologias. Esta proposta foi validada por meio de implementações em simulações e dispositivos reais em duas plataformas distintas: o Contiki e o OpenWSN. O processo de validação utilizou parâmetros como número de mensagens de controle, alterações de configurações topológicas, latência da rede e taxa de entrega de pacotes comparando-se a proposta a soluções tradicionais. Os resultados obtidos demonstraram um funcionamento compatível com estes parâmetros e uma melhoria em torno de 7,6% no sentido de redução do tempo de estabilização da rede. Adicionalmente, foi feito um teste comparativo de consumo de energia, evidenciando uma melhoria em termos de eficiência enérgica de até 20,9% da proposta com relação a protocolos tradicionais. / The wireless sensor networks are present in the most diverse sectors, forming a set of collaborative elements that perform the transport of information in urban scenarios, precision agriculture, health and industrial automation. Its use faces challenges as a constant need for adaptations to topology changes, low communication rates and efficient energy use. In this way, the applications of these networks must support these characteristics dynamically. This thesis proposes, therefore, a new routing protocol: the HOFACO (Hybrid Objective Function based on Ant Colony Optimization), based on the RPL (Routing Protocol for Low Power and Lossy Networks) applied to energy efficiency. This proposed protocol preserves the already consolidated routing interfaces and makes use of heuristic information based on swarm intelligence, using ant colony agents for the hybrid composition of metrics used in rank evaluation during the construction of topologies. This proposal was validated through implementations in simulations and real devices in two different platforms: Contiki and OpenWSN. The validation process used parameters such as number of control messages, changes of topological configurations, network latency and packet delivery rate, comparing the proposal to traditional solutions. The results showed a functioning compatible with these parameters and an improvement around 7.6% in the sense of reducing the time of stabilization of the network. In addition, a comparative test of energy consumption was made, evidencing an improvement in terms of energetic efficiency up to 20.9% of the proposal with respect to traditional protocols.

NASA's current plans for human spaceflight include an evolutionary series of missions based on a steady increase in capability to explore cis-lunar space, the Moon, near-Earth asteroids, and eventually Mars. Although the system architecture definition has the greatest impact on the eventual performance and cost of an exploration program, selecting an optimal architecture is a difficult task due to the lack of methods to adequately explore the architecture design space and the resource-intensive nature of architecture analysis. This research presents a modeling framework to mathematically represent and analyze the space system architecture design space using graph theory. The framework enables rapid exploration of the design space without the need to limit trade options or the need for user interaction during the exploration process. The architecture design space for three missions in a notional evolutionary exploration program, which includes staging locations, vehicle implementation, and system functionality, for each mission destination is explored. Using relative net present value of various system architecture options, the design space exploration reveals that the launch vehicle selection is the primary driver in reducing cost, and other options, such as propellant type, staging location, and aggregation strategy, provide less impact.

Vehicular Ad hoc Networks (VANET) exhibit highly dynamic behavior with high mobility and random network topologies. The performance of Transmission Control Protocols in such wireless ad hoc networks is plagued by a number of problems: frequent link failures, scalability, multi-hop data transmission and data loss. To address these VANET routing issues, I have used the ideas from swarm intelligence. The Ant Colony Optimization (ACO), which is a branch of swarm intelligence, is the main source of my inspiration. I have designed an ant-based routing algorithm which addresses routing issues prevalent in VANETs: adaptivity, robustness and scalability. One attractive feature of ACO is that they provide multiple routes from source to destination, resulting in more robust network. In this work, together with ACO, I have used the ideas from zone routing protocols to develop my algorithm: Mobility Aware Zone based Ant Colony Optimization Routing for VANET that exhibits locality and scalability.

Network resiliency pertains to the vulnerability of telecommunication networks in the case of failures and malicious attacks. With the increasing capacity catering of network for the booming multi-services in Next Generation Networks (NGNs), reducing recovery time and improving capacity efficiency while providing high quality and resiliency of services has become increasingly important for the future network development. Providing network resiliency means to rapidly and accurately reroute the traffic via diversely routed spare capacity in the network when a failure takes down links or nodes in the working path. Planning and optimization for NGNs require an efficient algorithm for spare capacity allocation (SCA) that assures restorability with a minimum of total capacity. This dissertation aims to understand and advance the state of knowledge on spare capacity allocation in network resiliency for telecommunication core networks. Optimal network resiliency design for restorability requires considering: network topology, working and protection paths routing and spare capacity allocation. Restorable networks should be highly efficient in terms of total capacity required for restorability and be able to support any target level of restorability. The SCA strategy is to decide how much spare capacity should be reserved on links and to pre-plan protection paths to protect traffic from a set of failures. This optimal capacity allocation problem for survivable routing is known as NP-complete. To expose the problem structure, we propose a model of the SCA problem using a matrix-based framework, named Distributed Resilience Matrix (DRM) to identify the dependencies between the working and protection capacities associated with each pair of links and also to capture the local capacity usage information in a distributed control environment. In addition, we introduce a novel ant-based heuristic algorithm, called Friend-or-Foe Resilient (FoF-R) ant-based routing algorithm to find the optimal protection cycle (i.e., two node-disjoint paths between a source-destination node pair) and explore the sharing ability among protection paths using a capacity headroom-dependent attraction and repulsion function. Simulation results based on the OMNeT++ and AMPL/CPLEX tools show that the FoF-R scheme with the DRM structure is a promising approach to solving the SCA problem for survivable routing and it gives a good trade off between solution optimality and computation speed. Furthermore, for the SCA studies of survivable networks, it is also important to be able to differentiate between network topologies by means of a robust numerical measure that indicates the level of immunity of these topologies to failures of their nodes and links. Ideally, such a measure should be sensitive to the existence of nodes or links, which are more important than others, for example, if their failure causes the network’s disintegration. Another contribution in this dissertation is to introduce an algebraic connectivity metric, adopted from the spectral graph theory, namely the 2nd smallest eigenvalue of the Laplacian matrix of the network topology, instead of the average nodal degree, to characterize network robustness in studies of the SCA problem. Extensive simulation studies confirm that this metric is a more informative parameter than the average nodal degree for characterizing network topologies in network resiliency studies.

Vehicular Ad hoc Networks (VANET) exhibit highly dynamic behavior with high mobility and random network topologies. The performance of Transmission Control Protocols in such wireless ad hoc networks is plagued by a number of problems: frequent link failures, scalability, multi-hop data transmission and data loss. To address these VANET routing issues, I have used the ideas from swarm intelligence. The Ant Colony Optimization (ACO), which is a branch of swarm intelligence, is the main source of my inspiration. I have designed an ant-based routing algorithm which addresses routing issues prevalent in VANETs: adaptivity, robustness and scalability. One attractive feature of ACO is that they provide multiple routes from source to destination, resulting in more robust network. In this work, together with ACO, I have used the ideas from zone routing protocols to develop my algorithm: Mobility Aware Zone based Ant Colony Optimization Routing for VANET that exhibits locality and scalability.

O desenvolvimento e aperfeiçoamento de métodos de otimização são pontos de profundo interesse em todas as áreas de pesquisa. Tais técnicas muitas vezes envolvem a aquisição de métodos de controle novos ou melhores, o que está diretamente ligado a duas tarefas importantes: a escolha de formas eficientes de monitoramento do processo e a obtenção de modelos confiáveis para a variável de interesse a partir de dados experimentais. Graças às suas diversas vantagens, os sensores óticos vêm sendo amplamente aplicados na primeira tarefa. Uma vez que é possível a utilização de vários tipos de espectroscopia através deste tipo de sensor, modelos capazes de lidar com dados espectrais estão se tornando cada vez mais atraentes. A segunda tarefa, por sua vez, depende não só de quais preditores são utilizados na construção do modelo, mas também de quantos. Como a qualidade do modelo depende também do número de variáveis selecionadas, é importante desenvolver métodos que identifiquem aqueles que explicam o máximo possível da variabilidade dos dados. O método de otimização Colônia de Formigas (ACO) aparece como uma ferramenta bastante útil na seleção de variáveis, podendo-se encontrar muitas variações desse algoritmo na literatura. O propósito deste trabalho é desenvolver métodos de seleção de variáveis com base no algoritmo ACO, conceitos estatísticos e testes de hipóteses. Para isso, diversos critérios de decisão foram implementados nas etapas do algoritmo referentes à atualização de trilha de feromônios (C1) e à seleção de modelos (C2). A fim de estudar estas modificações, foram realizados dois estudos de caso: o primeiro na área de bioprocessos e o segundo na área de caracterização de alimentos. Ambos os estudos mostraram que, em geral, os modelos com menores erros são obtidos utilizando-se métricas dos componentes do modelo, tal como o tamanho do intervalo de confiança de cada parâmetro e o teste-t de hipóteses. Além disso, a modificação do critério de seleção de modelos parece não interferir significativamente no resultado final do algoritmo. Por último, foi feito um estudo da aplicação dessas versões do ACO no campo de caracterização de combustíveis, mais especificamente diesel, associando-se duas análises espectroscópicas para predição do conteúdo de enxofre. Algumas das versões desenvolvidas mostraram-se superior ao algoritmo ACO utilizado como base para este trabalho, proposto por Ranzan (2014), e todas os versões forneceram melhores resultados na quantificação de enxofre que aqueles obtidos por PCR. Dessa forma, comprova-se a potencialidade de métricas implementadas no algoritmo ACO, associadas à espectroscopia, na seleção de preditores significativos. / The development and improvement of optimization methods are points of deep interest in all areas of research. These techniques are often related to the acquisition of new or better control methods, which are directly attached to two importante tasks: choosing efficient forms of process monitoring and obtaining reliable models for the monitored variable from experimental data. Due to their several advantagens, optical sensors are being widely applied in the first task. Since several types of spectroscopy are possible through this type of sensor, models capable of dealing with spectral data are becoming increasingly attractive. The second task depends not only on which predictors are used in the model, but also on how many. Since the quality of the model depends on the number of selected variables, it is important to develop methods that identify those that explain the greater amount of data variability as possible, without compromising the reliability of the model. The Ant Colony Optimization is an important tool for variable selection, being possible to find a lot of variations of this method in literature. The purpose of this work is to develop a method of variable selection based on the Ant Colony Optimization (ACO) algorithm, statistical concepts and hypothesis testing. For this purpose, several decision criteria for trail update (C1) and model selection (C2) were implemented within the routine. In order to study these modifications, two case study was conducted: one related to bioprocess monitoring and another one envolving the characterization of food products. Both studies showed that, in general, the models with the lowest errors were obtained through the use of model component metrics, such as the length of the confidence interval associated with each parameter and the t hypothesis test. Besides, the modification of the model selection criterion doesn’t seem to affect the algorithm final result. Finally, the aplicattion of these methods in the field of fuels characterization, specifically diesel fuel, was studied, associating two spectroscopical analyses in order to predict the sulfur content. Some of the new developed methods appeared to be better than the ACO algorithm used as basis in this work, proposed by Ranzan (2014), and all methods showed better results than those from the models constructed by PCR. Thus, it is proved the high potencial of using different metrics within ACO algorithm, associated with spectroscopy, in order to select significative predictors.

No description available.