Made available in DSpace on 2015-05-14T12:36:54Z (GMT). No. of bitstreams: 1 arquivototal.pdf: 2485062 bytes, checksum: ad2a2349ad56d837e75386f8c9ba1027 (MD5) Previous issue date: 2010-03-27 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / The present dissertation deals with the Routing Circuits for Field Programable Gate Arrays (FPGAs). Due to the combinatorial nature of the problem, heuristics methods are commonly used to generate good quality solutions in an acceptable computationally time. In this context, a procedure based on GRASP (Greedy Randomized Adaptive Search Procedure) with a procedure of local search based on ILS (Iterated Local Search) is proposed. The algorithm has been tested in benchmark problems found in the literature, MCNC, exploring timing-driven and channel-width criteria, being able to improve 55% of the benchmarks on timing drive criteria and improve 5,3% of the benchmarks on channel width criteria. / A presente dissertação trata do problema de roteamento de circuitos para Field Programable Gate Arrays (FPGAs). Em função da natureza combinatória do problema, métodos heurísticos são comumente utilizados para gerar soluções de boa qualidade em um tempo computacionalmente aceitável. Neste contexto, um procedimento baseado na metaheurística GRASP (Greedy Randomized Adaptive Search Procedure) com um procedimento de busca local baseado em ILS (Iterated Local Search) é proposto. O algoritmo foi testado em instâncias encontradas na literatura, benchmark MCNC, explorando os critérios de tempo crítico e números de trilhas, onde mostrou-se capaz de melhorar 55% das instancias no critério de tempo crítico e 5,3% quanto ao número de trilhas.

O comportamento de insetos sociais, em especial de formigas, tem sido muito estudado nos últimos tempos, devido à capacidade destes insetos realizarem tarefas complexas a partir de interações entre indivíduos simples. Ao se moverem sobre um ambiente na busca de alimento, as formigas depositam no solo uma substância química, denominada feromônio, que atrai as formigas que se encontram no ninho e as guia em direção ao alimento encontrado. O processo de construção e seguimento destas trilhas permite que as formigas descubram os menores caminhos e as melhores fontes de alimento no ambiente. Com o objetivo de estudar as características das formigas que contribuem para a sua adaptação a diferentes condições do meio, diversos experimentos vêm sendo realizados com estes insetos. Dentro deste contexto, esta tese apresenta experimentos inéditos realizados com formigas em laboratório, sobre uma rede artificial de túneis, onde diversos caminhos interconectados conduzem a uma fonte de alimento. As decisões das formigas foram analisadas nos níveis individual e coletivo, sob mudanças no meio, compreendendo o bloqueio/desbloqueio de ramos. A medição de diversas características individuais das formigas permitiu desenvolver dois modelos matemáticos sobre o seu comportamento, que foram aplicados à situação em que não se alterou a condição do ambiente com relação ao acesso aos ramos (estática), como também a mudanças no meio (dinâmica). A análise realizada do comportamento coletivo foi utilizada na comparação dos resultados obtidos pelas simulações dos modelos. De forma geral, o segundo modelo proposto foi mais eficiente que o primeiro na situação estática, porém ele ainda necessita de ajustes nas demais situações. O bom desempenho do segundo modelo proposto levou a aplicação de sua principal característica, a função de escolha que considera a concentração de feromônio sobre os ramos do meio e a capacidade de orientação das formigas, a um problema de otimização combinatorial, o roteamento em redes de telecomunicações. O algoritmo de roteamento proposto foi avaliado sob variações no nível de tráfego e topologia da rede, e seu desempenho foi comparado ao de dois algoritmos usados por concessionárias de telecomunicações, considerando diversas medidas de desempenho. O algoritmo desenvolvido obteve resultados encorajadores, sugerindo a aplicabilidade da estrutura do modelo proposto a outros problemas complexos de otimização. / The behavior of social insects, particularly of ants, has been intensively studied in the last years, due to their capacity to perform complex tasks through interactions among simple individuals. When moving in the environment searching for food, ants deposit on the ground a chemical substance, called pheromone, to attract ants in the nest and guide them towards the source of food that was found. The process of laying/following the pheromone trails allows ants to find the shortest paths and best sources of food of the environment. With the aim to study the characteristics of the ants that contribute to their adaptation to different environment conditions, several experiments with ants have been performed and reported in this research. In this context, this thesis presents novel experiments with ants in the laboratory, in an artificial network of tunnels, where several interconnected paths lead the insects from the nest to the food source. Ants\' decision were analyzed according to the individual and collective levels, under changes in the environment, comprising the blockage/release of branches. The measure of several individual characteristics of ants allowed the development of two mathematical models of their behavior, which were applied to the non-changing (static) environment access to all branches and to changing (dynamic) access. The analysis of the collective behavior of ants in the experiments was used to compare the results derived from the simulations of the models. In general, the second proposed model was more accurate than the first one in simulating ants behavior for the static situation, however, it needs some improvements for the other situations. The satisfactory behavior of the second model led to apply its main feature, the choice taking into consideration the pheromone concentration over the branches and the ants ability to orient themselves, to solve an optimization problem, the routing in telecommunications networks. The proposed routing algorithm was evaluated under variations on the traffic level and topology of the network, and its performance was compared with two routing algorithms used by telecommunications companies, considering several performance measures. The developed algorithm produced encouraging results, suggesting the possibility to apply the framework of the proposed model to other optimization problems.

Orientador: Fernando José Von Zuben / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-17T20:59:25Z (GMT). No. of bitstreams: 1 Azuma_ReginaMitsue_M.pdf: 2321816 bytes, checksum: 44c4417bf2a4fad2a8241c7189e4d04a (MD5) Previous issue date: 2011 / Resumo: A classe de problemas de estoque e roteamento está presente em várias áreas, incluindo indústria automobilística e gerência de numerário no reabastecimento de caixas eletrônicos. Supondo que o fornecedor é responsável pela estocagem e distribuição dos produtos, sujeito a um conjunto de restrições, o desafio que se apresenta é a determinação de uma política ótima, mais especificamente quais clientes atender, qual quantidade a ser fornecida a cada cliente e qual rota empregar visando a minimização dos custos. Este trabalho apresenta uma proposta de solução para uma das mais comuns formulações do problema: um produto é distribuído a partir de um fornecedor para vários clientes em um horizonte de tempo definido. O transporte é realizado por um veículo de capacidade limitada. Para produzir a otimização simultânea de ambos os objetivos, minimização dos custos de transporte e estoque, a proposta segue uma abordagem multiobjetivo e se baseia no uso do algoritmo SPEA2 (do inglês, Strength Pareto Evolutionary Algorithm 2), incluindo inovações na representação de soluções-candidatas, nos operadores genéticos e de busca local. A fronteira de Pareto estimada é então composta de múltiplas soluções não-dominadas, representando compromissos distintos entre custos de transporte e estoque. Como casos de estudo, são tomadas instâncias de médio porte extraídas da literatura e são geradas instâncias de grande porte. Para as instâncias de médio porte, as fronteiras de Pareto estimadas em cada caso são comparadas com as respectivas soluções ótimas da versão mono-objetivo de cada problema, pois já existe um algoritmo exato de solução para a formulação mono-objetivo de instâncias de médio porte / Abstract: The class of inventory routing problems (IRP) is present in several areas, including automotive industry and cash management for ATM networks. Given that the supplier is responsible for managing the product inventory and replenishment, subject to a set of restrictions, the challenge here is to determine an optimal policy, more specifically which retailers to serve, the quantity to deliver to each retailer and which routes to employ in order to minimize the cost. This work presents a proposal to solve one version of the IRP usually found in the scientific literature: a product is distributed from a supplier to several retailers in a defined time horizon. Shipment is performed by a vehicle with limited capacity. To perform the simultaneous optimization of both objectives, minimization of transportation and inventory costs, the proposal follows a multi-objective approach based on SPEA2 (Strength Pareto Evolutionary Algorithm 2), including innovative aspects mainly associated with the representation of candidate solutions, genetic operators and local search. The Pareto front is then composed of multiple non-dominated solutions with distinct trade-offs between transportation and inventory costs. As case studies, medium size instances extracted from the literature are considered and large size instances are generated. For the medium size instances, the estimated Pareto fronts are compared, in each case, with the corresponding optimal solutions associated with the single-objective version of each problem, given that there is already an exact algorithm to solve such medium size single-objective instances / Mestrado / Engenharia de Computação / Mestre em Engenharia Elétrica

Orientador: Francisco de Assis Magalhães Gomes Neto / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-12T23:12:18Z (GMT). No. of bitstreams: 1 Vieira_HeloisaPassarelli_M.pdf: 1211437 bytes, checksum: 312aded4a440d526d723ab88a2a23588 (MD5) Previous issue date: 2008 / Resumo: Nos últimos anos, diversas heurísticas e meta-heurísticas foram propostas para o Problema de Roteamento de Veículos com Janela de Tempo (PRVJT), cujo objetivo é determinar a rota a ser seguida por uma frota de veículos para servir um número de clientes em um dado intervalo de tempo, sem violar a capacidade dos veículos. Cada cliente é visitado por exatamente um veículo e somente uma vez. Esta disertação apresenta um estudo das técnicas utilizadas para o PRVJT, dando ênfase para os Algoritmos Genéticos. Diversos tipos de cruzamento e esquemas de mutação, além de outras técnicas avançadas, tal como o Hill-Climbing, são analisados. Para o algoritmo que implementamos, são apresentados vários resultados numéricos baseados em um conjunto de 56 problemas, cada qual com 100 clientes, proposto por Solomon. O desempenho do algoritmo que implementamos também é comparado aos melhores resultados publicados na literatura / Abstract: In recent years, several heuristic and metaheuristic methods were proposed for the Vehicle Routing Problem with Time Windows (VRPTW). The objective of the problem is to serve a set of customers within a given time interval, without violating the capacity of the vehicles. Each customer must be visited once and by only one vehicle. This dissertation presents a survey on the techniques used to solve the VRPTW, with emphasis on the genetic algorithms. Several crossover and mutation schemes, as well as other advanced techniques, such as the Hill-Climbing are analyzed. Numerical results based on Solomon's 56 VRPTW 100-customer instances are presented for the algorithm implemented here. The performance of our algorithm is also compared with the best results published in the specialized literature / Mestrado / Pesquisa Operacional / Mestre em Matemática Aplicada

Orientador: Cid Carvalho de Souza / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-15T11:41:44Z (GMT). No. of bitstreams: 1 Hoshino_EdnaAyako_D.pdf: 1434503 bytes, checksum: c1b32d8a6dc810d6d7ff6100d1a77c79 (MD5) Previous issue date: 2009 / Resumo: Nesta tese,dois problemas de otimização combinatória em grafos são modelados por programação linear inteira e resolvidos através de técnicas de geração de colunas. Os dois casos correspondem a generalizações de problemas clássicos em grafos e que ocorrem em muitas situações práticas. O primeiro, chamado problema dos anéis-estrelas capacitados, é uma generalização do problema de roteamento de veículos e modela situações reais encontradas nas áreas de logística de distribuição e de transporte. O segundo, conhecido por problema da coloração particionada, generaliza o problema da coloração de vértices em grafos e ocorre em aplicações no projeto de redes ópticas. As formulações de programação linear inteira desenvolvidas neste trabalho para modelar ambos os problemas estão relacionadas 'a técnica da decomposição de Dantzig-Wolfe e usam uma quantidade exponencialmente grande de variáveis de decisão . Nestas formulações, cada uma das variáveis representa uma estrutura específica do problema sendo estudado. No problema dos anéis-estrelas capacitados, cada variável está associada a um anel-estrela e, no problema da coloração particionada, a um conjunto independente. As relaxações lineares destes tipos de modelos, em geral, apresentam limitantes duais mais apertados que outros modelos compactos, isto é, definidos para um número polinomial de variáveis. Nesta tese, nós avaliamos estas novas formulações, comparando-as com outros modelos conhecidos para os problemas estudados. Além disso, nos dois casos, projetamos e implementamos algoritmos exatos do tipo branch-and-price e/ou branch-and-cut-and-price capazes de computar os modelos propostos. Experimentos computacionais foram realizados com estes algoritmos que confirmaram a adequação das técnicas aqui empregadas. Tanto para o problema dos anéis-estrelas capacitados quanto para o problema da coloração particionada, os resultados alcançados por nós foram comparados com aqueles reportados na literatura e mostraram que os algoritmos baseados em geração de colunas tiveram desempenho melhor que os algoritmos propostos anteriormente / Abstract: In this thesis, two combinatorial optimization problems are modeled by integer linear programming and solved using the column generation technique. Both cases correspond to generalizations of classical problems in graphs that occur in many practical situations. The first, called capacitated ring-star problem is a generalization of the vehicle routing problem and models real situations found in logistics and transportation. The second, known as the partition coloring problem, generalizes the vertex coloring problem in graphs and arises in design of fiber optics networks. The integer linear programming formulations developed in this work to model both problems are related to the Dantzing-Wolfe decomposition and use exponential number of decision variables. In these formulations, each decision variable represents a specific structure of the problem under study. For the capacitated ring-star problem, each variable is assigned to a ring-star and, for the partition coloring problem, to an independent set. The linear relaxation of this kind of model in general leads to tighter dual bounds than the ones obtained from compact models, i.e., defined over a polynomial number of variables. In this thesis, we evaluated both new formulations, comparing them to other known models for the respective problems. Moreover, in both cases, we designed and implemented exact branch-and-price and/or branch-and-cut-and-price algorithms that are able to solve the proposed models. Computational experiments were performed with these algorithms and showed that the used techniques were adequate. Both for the capacitated ring-star problem and for the partition coloring problem, we compared our results with those reported in the literature and showed that the algorithms based on column generation outperformed the previous ones / Doutorado / Otimização Combinatoria / Doutor em Ciência da Computação

Orientadores: Antonio Carlos Moretti, Margarida Pinheiro Mello / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-11T15:01:14Z (GMT). No. of bitstreams: 1 Oliveira_WashingtonAlvesde_M.pdf: 1986709 bytes, checksum: fa0dfb8c33d0fe5dd13eeced37d3b4ee (MD5) Previous issue date: 2008 / Resumo: Nesta dissertação estudamos um aspecto do problema de planejamento do pratulhamento urbano preventivo: a construção de rotas a serem percorridas pelos veículos da força policial no patrulhamento preventivo. De modo geral, a elaboração de rotas visa garantir uma boa visibilidade para o patrulhamento, de modo a proporcionar sensação de segurança para a população, permitir o atendimento rápido em caso de ocorrências, fazer vigilância de determinados estabelecimentos (hospitais, escolas, etc.). O planejamento deve levar em conta os recursos disponíveis, normalmente o número de veículos, visar agilidade e uma distribuição equânime de trabalho. O produto final é um módulo computacional capaz de automaticamente gerar rotas atendendo um dado conjunto de especificações, que possa ser utilizado pelos departamentos responsáveis pela segurança pública. Para tanto, fizemos uma adaptação do modelo para o Problema de Rotas de Cobertura multi-veículo (m-PRC). Este modelo consiste em um programa linear inteiro cujo tamanho e complexidade torna inviável a aplicação de métodos exatos para sua solução. Soluções subótimas são obtidas aplicando-se as heurísticas propostas por M. Hachicha et. al. (2000), e outras contribuídas por nós. Neste modelo alguns pontos geográficos devem ser obrigatoriamente visitados, enquanto outros devem ficar suficientemente próximos das rotas traçadas. Procuramos gerar rotas de tamanho menor possível, para que cada circuito seja percorrido um maior número de vezes durante o turno de serviço. As heurísticas foram implementadas em MATLAB e sua validação, assim como a do modelo, foi feita através da resolução de problemas gerados aleatoriamente. Além disso, obtivemos dados relativos à cidade de Vinhedo, S.P., e formulamos rotas para patrulhamento preventivo pela Guarda Civil Municipal. Os resultados são promissores, e a análise das soluções obtidas será utilizada para aprimorar o modelo / Abstract: In this text we study one aspect of the urban community policing: routine patrol route planning. We seek routes that guarantee visibility, as this has a sizable impact on the community's perceived safety and allows for quick emergency responses, and that provide surveillance of public buildings (e.g., hospitals, schools). The planning is restricted to the availability of vehides and strives to achieve balanced and short routes. We construct a computerized module, capable of automatic generation of routes for a given vehide fieet and lists of sites that must be visited. Such a module could be of interest to Police, Public Safety Departments, Municipal Service Agencies. The module implements an adaptation of the model for the multi-vehicle covering tour problem. It constitutes an integer program whose size and complexity makes the use of an exact method impractical. Suboptimal solutions are obtained with several heuristics, some by M. Hachicha et. al. (2000), and others of our own devising. In this model a set of locations must be visited, whereas another subset must be close enough to the planned routes. The heuristics aim to construct short routes so that one could make several rounds during a work shift. The implementation was done in MATLAB and its validation, as well as the model's, was based on the solution of randomly generated problems. Furthermore, data from the city of Vinhedo, SP, was obtained and tentative routes planned for the patroling of a choice of locations by the Municipal Guard. Their appraisal by the personnel in charge of the route planning will, without a doubt, help us improve the model and heuristics / Mestrado / Pesquisa Operacional / Mestre em Matemática Aplicada

Submitted by Geyciane Santos (geyciane_thamires@hotmail.com) on 2015-12-09T20:33:22Z No. of bitstreams: 1 Dissertação - Moysés Mendes de Lima.pdf: 1622069 bytes, checksum: 337a5becc26e67c107efbaeff8a9c441 (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2016-01-19T20:45:40Z (GMT) No. of bitstreams: 1 Dissertação - Moysés Mendes de Lima.pdf: 1622069 bytes, checksum: 337a5becc26e67c107efbaeff8a9c441 (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2016-01-19T20:47:25Z (GMT) No. of bitstreams: 1 Dissertação - Moysés Mendes de Lima.pdf: 1622069 bytes, checksum: 337a5becc26e67c107efbaeff8a9c441 (MD5) / Made available in DSpace on 2016-01-19T20:47:25Z (GMT). No. of bitstreams: 1 Dissertação - Moysés Mendes de Lima.pdf: 1622069 bytes, checksum: 337a5becc26e67c107efbaeff8a9c441 (MD5) Previous issue date: 2015-04-19 / Não informada / AWireless Sensor Network (WSN) consists of a set of sensors arranged in a sensor field in contact or near an event or phenomenon to be monitored. Such networks have amajor impact on applications involving the monitoring of environmental conditions such as temperature, light, motion and presence of certain types of objects. Accordingly in most other applications, the sensor nodes have limited power and bandwidth. Thus, techniques for reducing power consumption and communication are required in many settings. One of the main objectives in the design of a WSN is to provide data communication between the sensor nodes and the node textit sink.The challenge is to extend the network lifetime while maintaining a quality communication and data delivery. One of the key points observed in several studies is that routing protocols for WSNs will differ depending on the application and network architecture. Recently, algorithms that exploit information geographic, called Geographic Routing Algorithms, been considered as one of the most viable solution for routing in Wireless Sensor Networks (WSNs) due to their high scalability, dynamism, and high data delivery rate. These algorithms refer to nodes by position rather than address and use these coordinates to discover routes to the sink node.The main drawback of these algorithms is the need for position information of the nodes, which can be expensive in several ways. In this paper, we go further and propose two new routing algorithms that does not require position information while also adds data aggregation functionality to the network. Our proposal takes advantage of the grater communication range of the sink node as well as the Received Signal Strength Indicator (RSSI) of the sensor nodes to configure routing paths and aggregation times back to the sink node. Our results indicate clearly that the proposed algorithm reduces the amount of redundant data and the number of transmissions in the network while maintaining all advantages of these kind of algorithms. / Uma Rede de Sensores Sem Fio (RSSF) consiste em um conjunto de sensores, dispostos em um campo de sensoreamento em contato ou próximos a um evento ou fenômeno a ser sensoreado. Estas redes têm um grande impacto em aplicações de monitoramento ambiental tais como medição de temperatura, luminosidade, movimento e presença de certos tipos de objetos. Na maioria das aplicações para RSSF, os nós sensores possuem limitações de energia e largura de banda. Desta forma, técnicas de redução do consumo de energia e comunicação são necessárias, afim de otimizar o tempo de vida de uma RSSF. Um dos objetivos principais no projeto de uma RSSF é prover a comunicação de dados entre os nós sensores e o nó sink. O desafio é prolongar a vida útil da redemantendo uma qualidade na comunicação e na entrega dos dados. Um dos pontos chaves observados em diversos estudos é que os protocolos de roteamento em RSSFs irão diferir de acordo com a aplicação e a arquitetura da rede. Recentemente, algoritmos que exploram informações geográficas, chamados Algoritmos de Roteamento Geográfico, têm sido propostos para o transporte de dados nas RSSFs por serem escaláveis, dinâmicos e possuírem uma alta taxa de entrega de dados. Estes algoritmos se baseiam na posição física dos nós da rede ao invés de seus endereços para criar rotas em direção ao nó sink. A principal desvantagem destes algoritmos é a necessidade de localização, que pode ser custoso em diversos aspectos. Neste trabalho, propomos dois novos algoritmos de roteamento geográfico que não necessitam das informações de posição dos nós enquanto ainda proveem a funcionalidade de agregação de dados na rede. Nossa proposta tira vantagem da possibilidade de maior alcance de comunicação do nó sink, bem como do indicador de potência do sinal recebido (RSSI) dos nós sensores para configurar rotas e tempos de agregação de dados em direção ao nó sink. Os resultados obtidos mostram que os algoritmos propostos reduzem a quantidade de dados redundantes e o número de transmissões na rede, enquanto mantém todas as vantagens deste tipo de algoritmo.

Made available in DSpace on 2015-04-11T14:02:50Z (GMT). No. of bitstreams: 1 ricardo.pdf: 1126811 bytes, checksum: 85736cdaf1e7cf53e93c63df8abb6b16 (MD5) Previous issue date: 2013-07-29 / CNPq - Conselho Nacional de Desenvolvimento Científico e Tecnológico / The Internet is organized on network groups managed by administrative domains known as Autonomous Systems (ASes). Each AS employs its own routing policies and has autonomy in comparison to other ASes. The comunication and coordination between these ASes is made possible by the interdomain routing protocol. The Border Gateway Protocol (BGP)is the interdomain routing protocol currently used on Internet. However, the Internet s interdomain routing architecture has undergone only minor changes since its inception. It presents issues difficult to solve, because of the barrier to deploy new features, the hardness to understand its behavior and dynamics, and complexity to identify and correct faults. The deployment on Internet architecture is a tough task, because the need to deploy it directly on routers. Besides that, there is a requirement of global acceptance of new protocols and modifications. We observed that Software Defined Networking (SDN) could be used to provide innovation on interdomain routing, but it lacked mechanisms support this approach. SDN is an emerging paradigm composed by a data plane, a control plane, and an open protocol. On this work we present a mechanism able to perform interdomain routing with domains that deploys SDN paradigm, called Inter-SDN Routing Component. We point out the main issues on current interdomain routing, describes the Inter-SDN component, its behavior, and its experimental evaluation. Besides that, we show how prototyping and building of an interdomain mechanism on SDN are tasks relatively simple, and explain how our solution takes advantage of the SDN features to address the issues of the interdomain routing. / A Internet está organizada em grupos de redes que são gerenciados por domínios ad- ministrativos conhecidos como Sistemas Autônomos (ASes Autonomous Systems). Cada AS emprega suas próprias políticas de roteamento e tem autonomia em relação a outros ASes. A comunicação e coordenação entre estes ASes acontece por meio do protocolo de roteamento interdomínio. O Protocolo de Roteamento de Borda (BGP Border Gateway Protocol) é o protocolo de roteamento interdomínio atualmente utilizado na Internet. Entretanto, a arquitetura do roteamento interdomínio da Internet tem sofrido poucas mudanças desde sua criação. Ela apresenta problemas complexos de serem resolvidos, devido à dificuldade para a implantação de novas soluções, à dificuldade de entender seu comportamento e dinâmica, e à complexidade de identificar e corrigir falhas. A implantação de novas funcionalidades na arquitetura da Internet é uma tarefa difícil, devido à necessidade de manipular diretamente todos os roteadores. Além disso, é necessário aceitação global de novos protocolos e modificações nos existentes. Nós observamos que a abordagem Redes Definidas por Software (SDN Software-Defined Networking) poderia ser usada para prover inovação no roteamento interdomínio, mas que faltavam mecanismos para suportar esse tipo de roteamento. Neste trabalho, nós apresentamos um mecanismo capaz de realizar o roteamento interdomínio entre domínios que utilizam o paradigma SDN, chamado Inter-SDN. Nós ressaltamos os principais problemas no modelo atual de roteamento interdomínio, descrevemos o componente Inter-SDN, seu comportamento, e apresentamos uma análise experimental. Além disso, nós mostramos como o projeto e a construção de um mecanismo de roteamento interdomínio em SDN são tarefas relativamente simples, e explicamos como nossa solução utiliza as vantagens do SDN para resolver problemas do roteamento interdomínio.

FundaÃÃo Cearense de Apoio ao Desenvolvimento Cientifico e TecnolÃgico / Os avanÃos alcanÃados na computaÃÃo mÃvel e na comunicaÃÃo sem o levaram ao desenvolvimento do Sistema Inteligente de Transporte, onde se pode destacar as redes veiculares. Nelas, o roteamento à uma tarefa desaadora devido à alta mobi- lidade dos nÃs, à instabilidade dos enlaces sem-o e a diversidade de cenÃrios. Por essa razÃo, diversos protocolos de roteamento foram projetados com o objetivo de solucionar um ou mais problemas especÃcos de cada cenÃrio. Entretanto, apesar de existirem vÃrias soluÃÃes propostas para o problema do roteamento em redes veicu- lares, nenhuma delas alcanÃou um desempenho satisfatÃrio em mais de um cenÃrio, como urbano e rodovia. Sendo assim, nesta dissertaÃÃo, analisamos atravÃs de si- mulaÃÃes o impacto da densidade, da carga da rede e da mobilidade no desempenho de um protocolo de roteamento para fornecer diretrizes para os projetistas de redes veiculares desenvolverem protocolos de roteamento ecientes, capazes de se adaptar aos cenÃrios urbano e de rodovia. Para alcanÃar esse objetivo, quatro protocolos existentes na literatura foram avaliados nos cenÃrios urbano e de rodovia, dois deles voltados diretamente para redes veiculares e os outro dois tradicionais de redes âd hoâ. / Advances in mobile computing and wireless communications have made possible the development of the Intelligent Transportation System, which contain the vehi- cular networks. There, routing is a challenging task due to the high node mobility, the instability of wireless links and the diversity of scenarios. For this reason, several routing protocols have been designed with the goal of solving one or more specic problems of each scenario. However, although there are several proposed solutions to the routing problem in vehicular networks, none of them has achieved a satisfac- tory performance in more than one scenario, such as urban and highway. Thus, in this work, we rst analyze with simulations the impact of density, the network load and the mobility pattern in the performance of routing protocols for these networks. Then, we provide new directions for designing ecient vehicular network routing protocols, able to adapt to urban and highway scenarios. To achieve this goal, four existing protocols were evaluated in urban and highway scenarios.

Submitted by Renata Lopes (renatasil82@gmail.com) on 2018-11-19T12:44:23Z No. of bitstreams: 1 luizeduardomendesmatheus.pdf: 1606990 bytes, checksum: 2736fa2230ff16ef4aaa41155178b616 (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2018-11-23T13:06:46Z (GMT) No. of bitstreams: 1 luizeduardomendesmatheus.pdf: 1606990 bytes, checksum: 2736fa2230ff16ef4aaa41155178b616 (MD5) / Made available in DSpace on 2018-11-23T13:06:46Z (GMT). No. of bitstreams: 1 luizeduardomendesmatheus.pdf: 1606990 bytes, checksum: 2736fa2230ff16ef4aaa41155178b616 (MD5) Previous issue date: 2018-09-03 / Na última década, o interesse (acadêmico e comercial) em torno da Comunicação por Luz Visível (VLC) aumentou consideravelmente, devido a fatores como a crescente demanda por recursos sem fio na Internet e às vantagens oferecidas pela transmissão de dados através da luz visível. Entretanto, a utilização da luz como meio de comunicação, principalmente em ambientes internos, oferece diversos desafios, como interferência e bloqueios criados por obstáculos. Ao mesmo tempo, este tipo de ambiente oferece uma rica infraestrutura de fontes de luz, que podem ser utilizadas para auxiliar na comunicação através de mecanismos multi-hop. A maioria dos trabalhos presentes na literatura adotam técnicas simples para construção de mecanismos multi-hop em redes VLC, focando principalmente em aumento de distância. Neste trabalho, foi desenvolvido um protocolo de roteamento dinâmico, DYRP-VLC (DynamicRoutingProtocolforVisibleLightCommunication),quetemcomoobjetivo aumentar o desempenho de sistemas VLC em ambientes dinâmicos, enquanto reage à obstáculos construindo rotas alternativas na rede. A avaliação do protocolo foi realizada em um ambiente real, utilizando a plataforma embarcada OpenVLC 1.0 e métricas adotadas para problemas de roteamento. Os resultados obtidos mostram que, usando o DYRP-VLC, a rede foi capaz de se adaptar a mudanças dinâmicas na comunicação, como sombras e obstáculos, com pouca sobrecarga. / In the last decade, the interest in Visible Light Communication (VLC) has increased considerably, from both academic and commercial perspectives, due to factors such as the growing demand for wireless resources and the advantages offered by the transmission of data through visible light. However, the use of light as a communication medium, especially in indoor environments, offers several challenges, which includes shadowing and interference caused by obstacles. At the same time, this type of environment offers a rich infrastructure of light sources, which can be used to aid communication through multi-hop mechanisms. Most of the works present in the literature adopt simple techniques to construct multi-hop mechanisms in VLC networks, focusing mainly on increasing distance. Inthisthesis,wedevelopedDYRP-VLC(DynamicRoutingProtocolforVisibleLight Communication), a reactive routing protocol which aims to increase the performance ofVLCsystemsindynamicenvironments,whilereactingtoobstaclesbyconstructing alternative routes in the network. The evaluation of the protocol was performed in a real environment, using OpenVLC 1.0 embedded platform and adopting metrics for routing problems. The results show that, by using DYRP-VLC, the network was able to adapt to dynamic changes in communication, such as shadows and obstacles, with low overhead.