O projeto ISAM apresenta uma plataforma para o desenvolvimento e a execução de aplicações pervasivas. O ambiente de execução proposto na arquitetura ISAM, denominado ISAMpe (ISAM pervasive environment), foi concebido para ser implantado em escala global, com elevado número de componentes. Esses componentes podem ser móveis ou fixos e podem apresentar limitações em seus recursos computacionais. Muitas das aplicações pervasivas que podem ser executadas no ISAMpe têm necessidade de um serviço de disseminação capaz de distribuir informações de um produtor para um grande número de consumidores. Esta dissertação apresenta um serviço de disseminação de informações para a arquitetura ISAM, denominado DIMI (Disseminador Multicast de Informações). O DIMI apresenta uma arquitetura de multicast no nível de aplicação. O DIMI propõe um algoritmo de formação da topologia de disseminação que tem o objetivo de alcançar maior escalabilidade pelo alívio de sobrecarga em participantes específicos do canal, durante os momentos em que houver um grande número de novos consumidores querendo iniciar o consumo simultaneamente. No seu ambiente-alvo, o ISAMpe, o DIMI também oferece suporte à desconexão planejada, permitindo que dispositivos computacionais com limitações de conectividade participem da disseminação, e ainda oferece suporte à mobilidade de usuários. A topologia de comunicação do DIMI adapta-se às condições da rede física subjacente a ela, de acordo com critérios específicos da aplicação que utilizar o serviço. Os resultados obtidos com a simulação de alguns aspectos do funcionamento do DIMI e com a execução do protótipo do mesmo validam os argumentos usados para justificar a necessidade e a forma de construção do serviço. / The ISAM project presents a platform to the development and to the execution of pervasive applications. The execution environment proposed by the ISAM architecture, named ISAMpe (ISAM pervasive environment) was conceived to be deployed on global scale, having a large number of components. These components may be mobile or static and may present computational resource limitations. Many of the pervasive applications that may be executed on the ISAMpe need a dissemination service capable of distribute information from one producer to many consumers. This dissertation presents a information dissemination service for the ISAM architecture, named DIMI (Multicast Information Disseminator - Disseminador Multicast de Informações). DIMI presents an application-level multicast architecture. DIMI proposes an algorithm to create the dissemination topology which objective is to achieve scalability through the relief of overload on specific participants of the channel, during the moments where many new consumers want to start consumption simultaneously. Inside its target-environment, DIMI also offer support to user mobility and to planned disconnection, allowing resource limited computational devices to be participants of the dissemination. DIMI's dissemination topology adapt itself to the conditions of fabric network, accordingly to applications' criteria. The results obtained with the simulation of some DIMI's characteristics and with prototipation validate the arguments used to justify the necessity and the way of construction of the service.

Nos últimos anos tem sido observado um aumento na utilização de redes sem fio em ambientes industriais, em função de diversas vantagens relacionadas à redução de custos de cabeamento, mobilidade e facilidade de inserção, instalação e configuração de novos dispositivos. Entretanto, a aplicação de redes sem fio em sistemas de automação apresenta requisitos mais rígidos no que diz respeito à confiabilidade, segurança e garantias de entrega de mensagens. O protocolo WirelessHART é um padrão aberto de comunicação sem fio que busca atender a estes requisitos. Neste protocolo, um dispositivo conhecido como gerenciador de rede é responsável pela configuração, definição das rotas e alocação de recursos para a comunicação entre os dispositivos da rede. A definição de rotas consiste em um processo complexo, em função das características das redes sem fio, dos recursos restritos dos dispositivos e dos requisitos da aplicação. O ambiente desenvolvido nesta dissertação tem como objetivo permitir a avaliação das rotas determinadas por diferentes algoritmos de roteamento, auxiliando no desenvolvimento, comparação, ajuste de parâmetros e na identificação de problemas. O ambiente também tem como objetivo permitir a monitoração de redes WirelessHART operacionais, através da captura do tráfego na camada física, obtendo informações sobre as condições reais de operação, onde anomalias e problemas na topologia e nas rotas utilizadas na rede podem ser identificados. A ferramenta proposta foi validada com alguns estudos de estudos de caso, que também são apresentados neste trabalho. Os estudos envolveram a análise e ajuste de parâmetros de um algoritmo de definição de rotas estado da arte modificado, e a obtenção de topologias e rotas utilizadas em uma rede WirelessHART operacional. / In the last years the use of wireless networks in industrial environments has been observed, due to several advantages related to the reduction of cabling costs, mobility and ease of integration, installation and configuration of new devices. However, the implementation of wireless networks in automation systems introduces stringent requirements regarding reliability, security and message delivery guarantees. The WirelessHART protocol is an open standard for wireless communication that aims to meet these requirements. In this protocol, a device known as network manager is responsible for the configuration, routes definition, and resource allocation for communication between network devices. The route definition consists of a complex process, due to the wireless networks characteristics, limited resources of devices and application requirements. The environment developed in this work has as objective to enable the evaluation of the routes determined by different routing algorithms, helping in the development, comparison, tuning of parameters and in the identification of possible design problems. The environment also has as objective to allow the monitoring of operational WirelessHART networks, by capturing packets at the physical layer, obtaining information of operating conditions, where anomalies and problems in network topology and routes can be identified. The developed tool has been experimentally validated via some case studies, which are also described in this work. The study cases involved the analysis and tuning of parameters of a state-of-art modified route definition algorithm, and the capture of the current topology and routes of an operational WirelessHART network.

Orientador: Flávio Keidi Miyazawa / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-16T14:13:04Z (GMT). No. of bitstreams: 1 Azevedo_BrunoLuisPiresde_M.pdf: 1384772 bytes, checksum: 48aa7ca2380aaa03fd6375cb9b35aebc (MD5) Previous issue date: 2009 / Resumo: Nesta dissertação apresentamos um algoritmo exato para o Problema de Roteamento de Veículos Capacitados com Restrições Bidimensionais. Este combina o problema de carregar um conjunto de itens bidimensionais em veículos com o problema de minimizar o custo total de transporte. Existem várias aplicações práticas para este problema, dado que em muitas situações os itens não podem ser empilhados por diversas razões. Propomos um algoritmo exato baseado em uma abordagem branch-and-cut. Sete desigualdades válidas para o Problema de Roteamento de Veículos Capacitados foram adaptadas e utilizadas. As restrições de empacotamento são garantidas através de um algoritmo exato. Também apresentamos uma nova heurística de empacotamento bidimensional. Exploramos duas variantes do problema, as versões seqüencial e irrestrita. Para ambos os casos, consideramos os itens possuirem orientação fixa. Efetuamos testes computacionais e comparamos os resultados obtidos com a abordagem exata, para o caso seqüencial, apresentada por Iori, Salazar-González e Vigo. Observamos resultados satisfatórios e nove instâncias da literatura foram resolvidas à otimalidade pela primeira vez. Como o caso irrestrito ainda não havia sido abordado de modo exato, apresentamos também as soluções de cinqüenta instâncias nunca resolvidas à otimalidade / Abstract: We present an exact algorithm for the Vehicle Routing Problem with Two-dimensional Loading Constraints. This problem combines the problems of loading vehicles with two-dimensional items and minimizing transportation costs. It has many practical applications, since in many cases items can not be stacked on top of each other. We propose an exact algorithmbased on a branch-and-cut approach. Seven valid inequalities for the the Capacitated Vehicle Routing Problems were modified and used. The packing constraints are imposed by an exact algorithm. We also present a new heuristic for two-dimensional packing. We explored two variants of the problem, the sequential and the unrestricted cases. For both variants we assume the items to have fixed orientation. We performed computational tests and compared the results with the exact approach by Iori, Salazar-González and Vigo for the sequential case. We found the results to be satisfactory and nine instances from the literature were solved to optimality for the first time. Since the unrestricted case haven't been tested so far by an exact algorithm, we also present the solutions for fifty instances never solved to optimality before / Mestrado / Teoria da Computação / Mestre em Ciência da Computação

Orientador: Vinicius Amaral Armentano / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-06T12:38:24Z (GMT). No. of bitstreams: 1 Goraieb_Elias_M.pdf: 21259035 bytes, checksum: 5e5d4e69c800350a20727695a2f33647 (MD5) Previous issue date: 2005 / Resumo: Este trabalho aborda o problema de roteamento de veículos com coleta e entrega, visando à minimização do número de veículos utilizado e a distância total percorrida. O pedido de serviço é atendido por um veículo na janela de tempo imposta pelo cliente, e envolve uma coleta na origem que precede a entrega no destino. A capacidade dos veículos é limitada e uma rota tem duração máxima. Um algoritmo de busca tabu é proposto para a resolução deste problema. Diversas estratégias avançadas são incorporadas ao algoritmo, tais como redução de vizinhança, diversificação da busca, e utilização da metodologia path relinking / Abstract: This work considers the vehicle routing problem with pickup and delivery with the objectives of minimizing the fleet size and the total traveI distance. Each service request is served by a vehicle within time windows imposed by the clients, and involves a pickup origin that precedes a delivery destination. The capacity of the vehicle and the total route duration are limited. A tabu search algorithm is proposed to solve this problem. Several advanced strategies are incorporated in the algorithm, such as neighborhood reduction, search diversification, and path relinking / Mestrado / Engenharia de Sistemas / Mestre em Engenharia Elétrica

Orientadores: Edson Moschim, Felipe Rudge Barbosa / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-07T06:09:06Z (GMT). No. of bitstreams: 1 Nascimento_LuizHenriqueBonanido_D.pdf: 2297657 bytes, checksum: b04918af9ef98f4cae4bd6c3d6d4c0ca (MD5) Previous issue date: 2006 / Resumo: Hoje em dia, como uma multiplicidade muito grande de tecnologias converge para as redes fotônicas, a demanda por vazão cresce. Os protocolos para acesso múltiplo e simultâneo às portas de entrada da rede, bem como a abordagem do formato dos pacotes fotônicos e a arquitetura das redes, são considerados como alternativas tecnológicas para a melhora do desempenho das redes fotônicas. Deste modo, apresenta-se aqui uma proposta para a arquitetura de redes fotônicas,utilizando topologias em malha otimizadas para que os pacotes atinjam seus respectivos nós de destino no menor número de hops possível, com nós de rede 2x2. Além disso, utiliza-se o roteamento por deflexão para a resolução de contenda entre pacotes ópticos, bem como buffers eletrônicos na entrada da rede óptica para evitar problemas de perdas de inserção. Além disso, a estrutura de rede permite hierarquização e também se propõe um modelo para o funcionamento do nó que faz a ligação entre hierarquias diferentes dentro da rede óptica. Esta arquitetura de rede é então avaliada quanto à sua capacidade de prover requisitos para QoS em termos de perdas de pacotes, atrasos e inversão de ordem de pacotes, para a qual é proposta uma heurística para uma avaliação quantitativa. Os resultados mostram que uma arquitetura nos moldes apresentados é capaz de prover ganhos de desempenho, oferecendo condições para a garantia de QoS, provida por protocolos de rede em nível superior, até cerca de 70% de carga / Abstract: Nowadays, as a multiplicity of technologies converges upon the optical network, the demand for throughput increases. The protocols for multiple and simultaneous access to network ports, as well as the optical packet approach should be considered as technological alternatives to optical network performance upgrade. Thus, we present here a new proposal to the architecture of optical packet networks, using mesh topologies optimized in such a way that the packets reach their respective destination nodes with the smaller possible number of hops, and using 2x2 network nodes. Besides, we use deflection routing to solve the contention between optical packets, as well as electronical buffers at the optical network input to prevent problems with insertion losses. The structure of the network also allows hierarchization, performing the link between different hierarchies on the optical network. The performance of the proposed architecture is evaluated by the capacity of providing requirements of QoS, in terms of packet losses, delays and the amount of out of order packets, for which is presented a heuristic to get a quantitative estimation. The results show that the proposed architecture is able to provide performance gains, giving conditions to guarantee some levels of QoS, which is done by the specific protocols of superior network layers, up to 70% of network load / Doutorado / Telecomunicações e Telemática / Doutor em Engenharia Elétrica

Orientador: Helio Waldman / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-07T07:45:28Z (GMT). No. of bitstreams: 1 Pavani_GustavoSousa_D.pdf: 2684581 bytes, checksum: 17646b6816963a02bde2ea189d451458 (MD5) Previous issue date: 2006 / Resumo: Este trabalho aborda o uso de otimização por colônia de formigas (ACO) em redes ápticas. Como essa técnica exibe naturalmente capacidade de balanceamento de carga e auto-organização, além de prover controle distribuído na rede, apresentamos um algoritmo de roteamento baseado em formigas artificiais integrado a um plano de controle GMPLS, propondo seu uso nas seguintes aplicações: engenharia de tráfego e restauração em redes comutadas por caminhos ápticos e por pacotes ápticos, roteamento na presença de degenerações na camada física e gerenciamento integrado de caminhos ápticos e de recursos de processamento em arquiteturas de grid. O algoritmo proposto é comparado com técnicas tradicionais de roteamento baseado em topologia, como o roteamento por caminho mais curto. Apresentamos as vantagens e as limitações do algoritmo proposto em relação a essas técnicas para diferentes cenários, sendo que os resultados indicam que o algoritmo proposto neste trabalho é um excelente candidato para o controle de redes ápticas em substituição aos métodos tradicionais / Abstract: This work discusses the usage of Ant Colony Optimization (ACO) in optical networking. Since this technique exhibits naturally the capacity of network load-balancing and self-organization, besides it provides a distributed control of the network, we present a routing algorith:Q1 based on artificial ants, which is integrated with a GMPLS control plane. We propose the following applications for it: traffic engineering and restoration for wavelength-routed and optical packet switched networks, routing aware of physical-Iayer impairments, and integrated management of processing resources and lightpaths in grid architectures. The proposed algorithm is compared to conventional routing techniques based on topology, such as shortest-path routing. We present the advantages and limitations of the proposed algorithm when compared to those techniques considering different scenarios. The results indicate that the proposed algorithm is an excellent candidate to manage and control optical networks in lieu of the conventional methods / Doutorado / Telecomunicações e Telemática / Doutor em Engenharia Elétrica e de Computação

Orientador: Edmundo Roberto Mauro Madeira / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-11T08:18:18Z (GMT). No. of bitstreams: 1 Paschoalino_RacheldeCarvalho_M.pdf: 2064052 bytes, checksum: e9b127c3cba93b04b66044600728e3a9 (MD5) Previous issue date: 2008 / Resumo: Devido à facilidade de implantação e gerência, as redes mesh sem fio constituem uma escolha natural para atender a crescente demanda por acesso sem fio com cobertura em larga escala. Formadas por roteadores mesh interligados através de enlaces sem fio, as WMNs (Wireless Mesh Networks) fornecem um backbone flexível para diversas aplicações e serviços. Entretanto, os protocolos de roteamento existentes aplicados às WMNs não provêem escalabilidade, reduzindo a vazão conforme o tamanho da rede aumenta. Esta dissertação apresenta um protocolo de roteamento escalável com QoS para WMNs multirádio. Incorporamos uma métrica local de qualidade do enlace e suporte a múltiplos rádios ao protocolo OLSR (Optimized Link State Routing). A métrica de qualidade é usada na seleção de nós especiais de relay, que irão compor as rotas. Variações na métrica de qualidade são tratadas na vizinhança de 1 salto, preservando estabilidade no roteamento. Por sua vez, o uso de múltiplos rádios por nó provê um melhor aproveitamento do espectro sem fio, minimizando a contenção. Essa abordagem simples e escalável permite distribuir o tráfego na rede por caminhos com enlaces de melhor qualidade. Através das simulações realizadas, demonstramos que o protocolo proposto, chamado LQ-OLSR (Link Quality OLSR), traz melhorias expressivas na vazão, atraso e perda de pacotes em relação ao OLSR original, com um aumento mínimo do overhead / Abstract: Due to their deployment and management simplicity, Wireless Mesh Networks (WMNs) have become a natural way to fulfill the increasing demand for large area wireless coverage. Formed by mesh routers connected by wireless links, WMNs provide a flexible backbone for various applications and services. Nevertheless, the available routing protocols applied to WMNs suffer from scalability, where throughput decreases as the number of nodes grows. In this thesis, a scalable QoS routing protocol for multi-radio WMNs is proposed. We incorporate a locallink quality metric and multi-radio support in the OLSR (Optimized Link State Routing) protocol. The quality metric is used in the selection of relay nodes which will form the routes. Significant changes to link quality metric are treated in l-hop neighborhood, preserving route stability. Using multiple radios in each node allows a better utilization of the wireless spectrum, minimizing contention. This simple and scalable approach permits traffic distribution among better quality links. Simulations were conducted and the results showed expressive performance improvements .concerning throughput, delay and packet loss of the proposed protocol LQ-OLSR (Link Quality OLSR) over the original OLSR, with a minimum overhead increase / Mestrado / Redes de Computadores / Mestre em Ciência da Computação

Esta dissertação trata do problema do agrupamento de cargas fracionadas na distribuição de cimento ensacado partindo de um depósito central. O problema consiste em definir quais entregas de cimento serão carregadas juntas em um determinado veículo, de modo a aproveitar ao máximo sua capacidade e ao mesmo tempo reduzir o custo com o frete pago aos transportadores que farão sua distribuição. Em especial, o método de resolução proposto pode ser dividido em três fases. Na primeira fase, as entregas pertencentes a um mesmo cliente são agrupadas prioritariamente. Na segunda fase, são agrupadas as entregas de clientes dentro de uma mesma cidade. Neste caso, uma simplificação necessária é considerar que todas as entregas de uma mesma cidade estão localizadas em um único ponto. Com isso, a distância entre os clientes se torna irrelevante e é proposto um método baseado em um algoritmo genético para resolução de problemas de bin-packing (BPP). Para a terceira fase, é considerado o agrupamento para pontos de entrega pertencentes a cidades diferentes, onde as distâncias rodoviárias são consideradas. Nesta etapa, é proposta uma variação do método anterior, incorporando ao modelo algumas heurísticas para resolução de problemas de roteirização de veículos, como o algoritmo de Clarke & Wright e o algoritmo do Vizinho Mais Próximo. / This thesis deals with the problem of merging less-than-truckload deliveries in bagged cement distribution from a central depot. The problem consists in defining which cement deliveries shall be loaded in each given vehicle, in order to maximize the vehicle full capacity as well as reduce carriers freights. Particularly, the solution method can be divided hierarchically in three stages. In the first stage, the deliveries from the same client are merged with priority. In the second stage, the deliveries from the same city are merged. In this case, a necessary assumption is to consider the deliveries from the same city as located in a single destination point. Consequently, the distances among deliveries can be assumed as irrelevant and a heuristic method is proposed, which relies on a genetic algorithm for the bin-packing problem (BPP). In the third stage, merging of different delivery points that are apart from each other is considered. For this step, a variation of the previous method is proposed, incorporating some heuristics to solve the vehicle routing problem, like the Clarke & Wrights savings algorithm and the Nearest Neighbor algorithm.

Orientador: Cid Carvalho de Souza / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-19T00:16:31Z (GMT). No. of bitstreams: 1 Zilli_PetersonKatagiri_M.pdf: 1307926 bytes, checksum: 5fe0ddfca7cce84d9e26b66106d61e8b (MD5) Previous issue date: 2011 / Resumo: O Problema de Roteamento de Veículos (VRP, em inglês) foi proposto por Dantzig e Ramser em 1959 e, desde então, um grande número de artigos foi dedicado à solução de suas variantes. O problema original consiste em determinar rotas otimais que serão usadas por veículos de capacidade limitada para servirem a um conjunto de clientes. Neste trabalho focamos o estudo e a implementação dos modelos chamados de "ricos" na literatura, os quais englobam variantes complexas do VRP e conseguem representar situações mais próximas dos problemas logísticos encontrados em sistemas de distribuição reais. A principal motivação para esta pesquisa é uma aplicação prática referente ao problema de roteamento dos ônibus fretados pela UNICAMP para o transporte de seus funcionários, que se caracteriza como um modelo rico. O objetivo final é a otimização de tal processo através da minimização da distância total percorrida ou do número de veículos empregados, com a consequente redução dos gastos incorridos pela Universidade. Portanto, além do seu aspecto científico, esta dissertação produz resultados com chances reais de trazer benefícios à administração de uma instituição pública de ensino. Para que isto venha a ocorrer, as heurísticas desenvolvidas foram inseridas em um sistema de informações geográficas, que será usado pela universidade no processo de criação e otimização das rotas a serem licitadas publicamente / Abstract: The Vehicle Routing Problem (VRP) was first proposed by Dantzig and Ramser in 1959 and, since then, a large number of papers has been devoted to the solution of its variants. The original problem consists in determining an optimal set of routes to be used by vehicles of limited capacity that serve a set of customers. In this paper we focus on the study and implementation of models called "rich" in the literature, which include complex variants of the VRP that represent situations closer to the logistical problems encountered in real distribution systems. The main motivation for this research is a practical problem concerning the routing of buses chartered by UNICAMP for transporting a part of its employees, which is characterized as a rich model. The goal is to optimize this process by minimizing the total travel distance or the number of vehicles used, with a consequent reduction of the expenses incurred by the University. Therefore, in addition to its scientific aspect, this dissertation gives results with real chances to benefit the administration of a public university. For this to happen, the heuristics developed were entered into a geographic information system, which will be used by the university in the process of creation and optimization of routes to be publicly auctioned / Mestrado / Pesquisa Operacional / Mestre em Ciência da Computação

Orientador: Vinicius Amaral Armentano / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-03T23:44:20Z (GMT). No. of bitstreams: 1 Shiguemoto_AndreLuis_M.pdf: 3046317 bytes, checksum: c423cde2a2fa6c3581d15058afec5085 (MD5) Previous issue date: 2004 / Mestrado / Engenharia Eletrica / Mestre em Engenharia Elétrica