A wireless sensor network (WSN) is made of tiny sensor nodes usually deployed in high density within a targeted area to monitor a phenomenon of interest such as temperature, vibration or humidity. The WSNs can be employed in various applications (e.g., Structural monitoring, agriculture, environment monitoring, machine health monitoring, military, and health). For each application area there are different technical issues and remedies. Various challenges need to be considered while setting up a WSN, including limited computing, memory and energy resources, wireless channel errors and network scalability. One way of addressing these problems is by implementing a routing protocol that efficiently uses these limited resources and hence reduces errors, improves scalability and increases the network lifetime. The topology of any network is important and wireless sensor networks (WSNs) are no exception. In order to effectively model an energy-efficient routing algorithm, the topology of the WSN must be factored in. However, little work has been done on routing for WSNs with regular patterned topologies, except for the shortest path first (SPF) routing algorithms. The issue with the SPF algorithm is that it requires global location information of the nodes from the sensor network, which proves to be a drain on the network resources. In this thesis a novel algorithm namely, BRALB (Biased Random Algorithm for Load Balancing) is proposed to overcome the issues faced in routing data within WSNs with regular topologies such as square-base topology and triangle-based topology. It is based on random walk and probability. The proposed algorithm uses probability theory to build a repository of information containing the estimate of energy resources in each node, in order to route packets based on the energy resources in each node and thus does not require any global information from the network. It is shown in this thesis by statistical analysis and simulations that BRALB uses the same energy as the shortest path first routing as long as the data packets are comparable in size to the inquiry packets used between neighbours. It is also shown to balance the load (i.e. the packets to be sent) efficiently among the nodes in the network. In most of the WSN applications the messages sent to the base station are very small in size. Therefore BRALB is viable and can be used in sensor networks employed in such applications. However, one of the constraints of BRALB is that it is not very scalable; this is a genuine concern as most WSNs deployment is large scale. In order to remedy this problem, C-BRALB (Clustered Biased Random Algorithm for Load Balancing) has been proposed as an extension of BRALB with clustering mechanism. The same clustering technique used in Improved Directed Diffusion (IDD) has been adopted for C-BRALB. The routing mechanism in C-BRALB is based on energy biased random walk. This algorithm also does not require any global information apart from the initial flooding initiated by the sink to create the clusters. It uses probability theory to acquire all the information it needs to route packets based on energy resources in each cluster head node. It is shown in this thesis by using both simulations and statistical analysis that C-BRALB is an efficient routing algorithm in applications where the message to be sent is comparable to the inquiry message among the neighbours. It is also shown to balance the load (i.e. the packets to be sent) among the neighbouring cluster head nodes.

O presente trabalho aborda o sistema logístico usualmente denominado Vendor Managed Inventory (VMI), no qual o fornecedor controla e coordena as decisões de reabastecimento, sendo responsável por manter os estoques de seus clientes dentro de limites fixados de antemão. O modelo proposto incorpora ainda as decisões relativas à produção e manutenção de estoque por parte do fornecedor, além da utilização de frota heterogênea na distribuição, e busca a minimização dos custos totais do sistema. Quatro heurísticas de duas etapas são propostas para a resolução do problema abordado. A primeira etapa, comum a todas as heurísticas, baseia-se em uma heurística recentemente publicada na literatura e fornece uma solução inicial viável, utilizada como ponto de partida para a etapa de melhoria subsequente, na qual é utilizada a metaheurística busca tabu ou busca em vizinhança variável. As heurísticas propostas foram avaliadas em um conjunto de teste, sendo obtidos resultados melhores que os reportados na literatura em todas as instâncias testadas. Dentre as estratégias de solução avaliadas, destaca-se a heurística baseada em busca tabu com diversificação, que demonstrou ser superior às demais heurísticas propostas. Os resultados obtidos indicam ainda que, no caso da frota disponível ser heterogênea, é vantajosa a utilização de uma adaptação do procedimento de obtenção da solução inicial, como forma de privilegiar a utilização de veículos de maior eficiência. / This thesis deals with the logistic system usually called Vendor Managed Inventory (VMI). In this system the supplier controls and coordinates the supply decisions and is responsible for keeping the inventory of each of his clients within predetermined minimum and maximum levels. Heterogeneous fleet and production/stocking decisions at the supplier are considered as well, and the proposed model seeks to minimize the total system cost. Four two-stage heuristics are proposed for this problem. The first stage consists in an adaptation of a heuristic found in the bibliography, which provides an initial viable solution that will be improved in the second stage by means of the metaheuristics tabu search or variable neighborhood search. The proposed heuristics were tested on a set of benchmark instances with improvements found on the best known results in all of the tested instances. The obtained results indicate that the tabu search based heuristic with diversification strategy is clearly superior to the other proposed heuristics and that a better fleet utilization can be obtained in the case of heterogeneous fleet by a simple improvement in the first stage, that favors the selection of more efficient vehicles.

O Estado do Rio de Janeiro possui indicadores de produção muito baixos na realização de exames de câncer de mama. Na tentativa de melhorar o acesso aos exames, principalmente em regiões com baixa densidade populacional onde a aquisição de mamógrafos não é custo-efetiva, o uso da mamografia móvel é uma alternativa para aumentar a execução de exames de rastreamento de câncer de mama. O objetivo desta pesquisa é a construção de um modelo computacional para definir a alocação de mamógrafos móveis. O Modelo considera as variáveis associadas com os custos e prazos, indicando quando, onde e por quanto tempo, as unidades móveis de mamografia devem permanecer em cada cidade. O modelo foi construído no software de modelagem e simulação Anylogic, usando técnicas de modelagem baseada em agentes. O principal resultado é determinar o percurso de cada veículo disponível, para oferecer a cobertura desejada em cada cidade. Todas as entradas são parametrizadas, permitindo simular diferentes cenários e fornecer informações importantes para o processo de tomada de decisão. O horizonte de tempo, número de mamógrafos (fixos e móveis), a cobertura desejada da população, a capacidade de produção de cada dispositivo, a adesão da população urbana e rural, entre outras variáveis, foram consideradas no modelo. Os dados da Região Serrana do Rio de Janeiro foram usados nas simulações, onde menos de metade das cidades possuem mamógrafos fixos. Com o modelo proposto foi possível determinar a distribuição de cada dispositivo físico e o número ótimo de unidades móveis de mamografia para oferecer cobertura à totalidade da população no ciclo de dois anos. O número de mamógrafos para oferecer cobertura de toda a população da região poderia ser reduzido pela metade com o modelo de alocação proposto neste trabalho. A utilização de mamografia móvel, em conjunto com a rede existente de mamógrafos fixos, procura maximizar a disponibilização de exames de testes de diagnóstico de câncer de mama no estado do Rio de Janeiro. O desenvolvimento de um modelo de roteamento que aperfeiçoa a cobertura de rastreio do câncer de mama é apresentado como um complemento importante na tentativa de melhorar o acesso à população residente em áreas urbanas e rurais dos municípios. / The Rio de Janeiro State has low indicators in screening exams of breast cancer. As an attempt to improve access to exams, particularly in regions with low population density, where the acquisition of mammography is not cost- effective, the use of mobile mammography is an alternative to increase screening tests for breast cancer. The objective of this research is to build a computer model to define the allocation of mobile mammography. The model considers the variables associated with the costs and deadlines, indicating when, where and how long, the mobile mammography units must remain in each city. The model was built in the modeling and simulation software AnyLogic, using Agent-Based modelling techniques. The main result is to determine the route of each vehicle available, to offer the desired coverage for each city. All inputs are parameterized, enabling simulate different scenarios and providing important information for decision-making. The time horizon, number of mammography devices (fixed and mobile) available, desired coverage of the population, production capacity of each device, adherence of urban and rural population, among others variables, were considered into the model. The tests data came from Mountain Region of the Rio de Janeiro State, where less than half of cities have fixed mammography units. Women need to move to other cities for the examination, which leads to decreased adherence to mammographic screening programs. With the proposed model was possible to determine the distribution of each physical device and the optimum number of mobile mammography units to cover to the entire population in the 2-year cycle. The number of mammography devices to provide coverage to the entire population of the region could be reduced by half with the routing proposed in the model. The use of mobile mammography, together with the existing network of fixed mammography, indicated a possibility to optimize the uptake of breast cancer diagnostic tests in the Rio de Janeiro State. The development of a routing model that optimized the breast cancer screening coverage represent an important complement in an attempt to improve access to mammography exams.

Este trabalho apresenta uma variação do problema de roteamento de veículos que permite o uso de veículos com múltiplos compartimentos. A necessidade de veículos com múltiplos compartimentos surge com frequência em aplicações práticas quando uma série de produtos, que possuem diferentes qualidades ou tipo, precisam ser transportados mas não podem ser misturados. Este problema é chamado na literatura de roteamento de veículos com múltiplos compartimentos (PRVMC). Nós propomos uma heurística busca tabu implementada em uma busca local iterada para resolver este problema. Experimentos foram feitos para avaliar a performance da busca tabu iterada e os resultados obtidos foram comparados com os resultados disponíveis na literatura. O algoritimo proposto é capaz de encontrar soluções melhores e em menos tempo de processamento que as heurísticas existentes. / We study a variant of the vehicle routing problem that allows vehicles with multiple compartments. The need for multiple compartments frequently arises in practical applications when there are several products of different quality or type, that must be kept or handled separately. The resulting problem is called the multi-compartment vehicle routing problem (MCVRP). We propose a tabu search heuristic and embed it into an iterated local search to solve the MCVRP. In several experiments we analyze the performance of the iterated tabu search and compare it with results from the literature. We find that it consistently produces solutions that are better than existing heuristic algorithms.

O Roteamento Global é responsável pelo planejamento da distribuição dos meios de interconexão dentro da área do circuito. Dentro da fase do projeto de circuitos conhecida como Síntese Física, essa fase situa-se após a etapa de posicionamento, que define uma posição exata para cada célula do circuito, e antes da etapa de roteamento detalhado que irá definir uma posição para cada meio de interconexão. Os roteadores globais utilizam uma versão abstrata e simplificada do circuito, que agrega uma região e toda a capacidade de fios que esta região comporta, trabalhando com o planejamento dessas capacidades em relação a demanda de interconexão entre as células do circuito. Este trabalho, apresenta um conjunto de técnicas para delimitação e tratamento de áreas que possuem alta demanda por meios de interconexão em circuitos VLSI. As técnicas são aplicadas em duas fases do fluxo de rotamento global: a primeira é executada na fase de pré-roteamento, onde são identificadas as regiões que possuem alta demanda por interconexão, isto é, são destino ou origem de um número elevado fios em relação a sua capacidade de alocar meios de interconexão; a segunda etapa ocorre dentro da fase de roteamento iterativo, identificando e protegendo aquelas que regiões que possuem os níveis mais elevados de congestionamento. Para avaliar os impactos da aplicação das técnicas propostas, foi feita a implementação em um fluxo de roteamento global existente. A avaliação foi partir da extração de quatro métricas de roteamento global comumente utilizadas na literatura de síntese física, para análise de roteamento global: comprimento dos fios, valor total de congestionamento, máximo congestionamento de aresta e tempo de execução. A partir da execução de experimentos utilizando as técnicas, foi possível verificar ganhos de até 11% em redução do congestionamento total no circuito, em benchmarks para os quais ainda não se tem soluções válidas na literatura. Os tempos de execução obtiveram um redução de até 35%, quando comparados com a implementação usada como referência para aplicação das técnicas, o roteador GR-WL. Um dos efeitos colaterais da aplicação de técnicas de calibração de custos é o aumento do comprimento médio dos fios. Os resultados dos experimentos mostram que as técnicas propostas conseguem reduzir este efeito colateral para, no máximo, 1.39% de acordo com os benchmarks executados. / Global routing phase is responsible for the interconnect planning and distribution across the circuit area. During the integrated circuit project flow, the global routing is contained in the Physical Synthesis, after the placement, that is when the position of all circuit cells are defined, and before the detailed routing, when the position of all interonnection wires is realized. A simplified and abstrate version of the circuit routing area is used by the global router, that will agregate in a single vertex, an specific region of the circuit, that represents a bunch of interconnection with their total capacity. This work presents a set of techniques to delimit and threat areas that have high interconnection demand in VLSI circuits. These techniques are applied in two steps of the global routing flow: the first is executed during the initial routing, where the high interconnection demanding regions are identified. the second step is executed during the iterative routing, where the top offender regions are identified and heva their costs pre-allocated. In order to evaluate the impact of the proposed techniques, they are implemented in an existing global routing flow, and four metrics are collected: total wirelenght, execution time, total overflow and maximum overflow. Tha last two metrics will be different from zero just for the circuits that not have a valid solution. After the execution of the experiments it was possible to verify a reduction up to 11% in wirelenght, in some benchmarks that the literature do no have a valid solution. Furthermore, it was possible to verify a reduction up to 35% in the execution time, when compared to the reference implementation. Once we are including constraints in form of cost pre-allocation, it is possible to verify an wirelength increase in some cases. In this work, it was possible to observe a small presence of these side-effects, up to 1.39%, according to the executed benchmarks.

Este trabalho apresenta a implementação de um roteador global de circuitos integrados capaz de tratar os problemas de roteamento atuais, utilizando como referência para avaliação os circuitos de benchmark publicados durante as competições de roteamento global realizadas no ACM International Symposium on Physical Design 2007 e 2008. O roteador global desenvolvido utiliza como ferramenta principal a técnica de ripup and reroute associada às técnicas de roteamento monotônico e maze routing, ambas com grande histórico de uso nas ferramentas acadêmicas descritas também neste trabalho. O desenvolvimento da ferramenta também possui características diferenciadas e únicas, com um novo método de ordenamento das redes durante a fase de rip-up and reroute. Para a geração dos resultados foram definidas duas versões diferentes da ferramenta, sendo estas duas versões analisadas com duas diferentes técnicas de construção das árvores de roteamento, gerando no total quatro configurações da ferramenta. Como decisão de projeto, a versão principal utilizada no desenvolvimento e discussão dos resultados é a versão que prioriza a qualidade do roteamento, utilizando MSTs para construção das árvores de roteamento. Os resultados mostram que o roteador global desenvolvido é capaz de gerar resultados com boa qualidade mesmo sem fazer uso de técnicas de identificação de áreas de congestionamento, sem otimizações pós-roteamento e sem nenhuma forma de ajuste (tuning) para os diferentes circuitos de benchmark, apesar de ainda ter tempo de execução acima dos apresentados por outras ferramentas acadêmicas. O foco durante o processo de desenvolvimento e implementação da ferramenta foram os circuitos mais recentes, entretanto a ferramenta obteve ótimos resultados também para os circuitos publicados no ISPD 1998, gerando soluções com qualidade similar ou melhor que as reportadas na literatura. A diferença dos resultados deste trabalho em relação aos melhores resultados dos roteadores globais com código disponível, para circuitos 3D lançados no ISPD 2008 é de, em média, 1,78%1 na métrica de comprimento de fio sem considerar o custo das vias e de 15,56% considerando o custo da via como uma unidade de comprimento de fio (ISPD 2008), para a versão voltada a qualidade de roteamento. Já para a versão da ferramenta que busca a convergência o mais rápido possível a diferença foi de 3,39% e 16,32%, respectivamente. As maiores diferenças são encontradas nos circuitos mais difíceis de gerar uma solução sem violações. Isso mostra como as técnicas de identificação de região podem contribuir tanto para uma convergência mais rápida quanto para evitar que fios passem por rotas desnecessárias durante a fase de negociação. Na métrica que avalia as vias como custo de uma unidade de comprimento, os resultados obtidos apresentam em média 18,67% maior comprimento de fio que os melhores resultados da literatura, sendo que dois circuitos com solução sem violações2 apresentam resultado com violações utilizando a ferramenta desenvolvida neste trabalho. / This work describes the implementation of an integrated circuit global router capable of handling the current routing problems, using as a reference the evaluation of benchmark circuits from the two global routing contests held in ISPD 2007 and 2008. The developed global router uses rip-up and reroute as the main technique associated with monotonic and maze routing techniques, both with large history of use in academic tools, also described in this work. The tool also has distinctive and unique characteristics, with a new method of net ordering during the rip-up and reroute stage. In order to generate the results were defined two different versions of the tool analyzed with two different techniques of routing tree construction, generating a total of four configurations. As a design decision, the major version used in the development and discussion of results is the version that prioritizes the routing quality, using MSTs for tree construction. The results show that the global router developed is able to generate good results even without making use of techniques to identify congestion areas, without post-routing optimizations and without any form of tuning for the different benchmark circuits, despite having run time above other academic tools. The focus during the development and implementation of the tool were the newer circuits, however the tool also obtained excellent results for the circuits released in ISPD 1998, generating solutions with similar quality or better than those reported in the literature. The difference in the results of this work over the best results generated with the available code global routers for 3D circuits released in ISPD 2008 is, on average, 2.53% in wirelength metric without considering the cost of vias and 18.34% considering the cost of the vias as one wirelength unit (ISPD 2008), for the best routing quality version. As for the version of the tool that seeks convergence as soon as possible the difference was 3.82% and 17.03%, respectively. The largest differences were found in the most difficult circuits to generate a solution without violations. This shows how the techniques of congested region identification can contribute to both a faster convergence and to avoid unnecessary wire detours during the negotiation phase. In the metric that evaluates the cost of vias as one wirelength unit, the results show an average of 22.5% greater wirelength than the best results found in literature. Also, the developed global router was unable to find a violation free solution for two circuits that are known to have a violation free solution3.

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.

A aplicação de redes sem fio vem crescendo consideravelmente nos últimos anos. Protocolos baseados nesta tecnologia estão sendo desenvolvidos para uma grande variedade de aplicações. A confiabilidade é um dos principais requisitos dos protocolos de comunicação nos ambientes industriais. Interferências, ambiente ruidoso e o grande risco das aplicações industriais que são monitoradas são fatores que elevam os níveis de exigência no que se refere à confiabilidade, redundância e segurança do protocolo. O protocolo WirelessHART é um padrão de comunicação sem fio desenvolvido especificamente para monitoramento e controle de processos com os requisitos necessários para ser utilizado em ambientes industriais. A norma do WirelessHART define diversos aspectos técnicos a serem utilizados no desenvolvimento de algoritmos. Os algoritmos de roteamento e escalonamento de mensagens são de grande relevância para o cumprimento dos requisitos temporais, de confiabilidade e segurança. Requisitos de roteamento e escalonamento são especificados, porém, os algoritmos a serem utilizados não são definidos. O objetivo nessa dissertação é analisar alguns dos principais algoritmos que tem sido propostos especificamente para o protocolo WirelessHART e apresentar um conjunto capaz de ser aplicado nesse protocolo. Análises e comparações entre os algoritmos são realizadas proporcionando um estudo aprofundado sobre seus impactos no desempenho do protocolo. / The application of wireless networks has grown considerably in recent years. Protocols based on this technology are being developed for a great variety of applications. Reliability is one of the main requirements for communication protocols in industrial environments. Interferences, noisy environment and high risk processes that are monitored are factors that increase the levels of requirements in terms of reliability, redundancy and security of the protocol. The WirelessHART protocol is a wireless communication standard specifically designed for process monitoring and control applications with the necessary requirements for to be used in industrial environments. The WirelessHART standard defines several technical aspects to be used in the development of the algorithms. The algorithms of routing and scheduling messages are highly relevant to meeting the timing requirements of reliability and safety. Routing and scheduling strategies are specified, however, the routing and scheduling algorithms are not defined for use. The goal of this dissertation is to analyze some of the main algorithms that have been proposed specifically for the WirelessHART protocol and to present a set able to be applied in this protocol. Analyzes and comparisons between algorithms are realized by providing a detailed study of their impacts on the protocol performance.

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.

Les théâtres d’opérations militaires s’organisent aujourd’hui sous la forme de coalitions. Les forces armées qui sont déployées possèdent des moyens technologiques (communication, routage) et créent des réseaux sans fil. Le mouvement de ces forces sur le terrain donne au réseau une topologie fortement dynamique. Il se caractérise comme un réseau sans fil mobile, plus communément appelé MANET (Mobile Ad hoc NETwork). Pour l’efficacité de la mission et des communications, il est intéressant d’interconnecter facilement les différents groupes participant à la coalition. Cependant, chaque membre de la coalition possède sa propre architecture et souhaite rester autonome, sans s’adapter aux autres. Comme les opérateurs ont pu le faire lors de la création de l’Internet avec le protocole BGP (Border Gateway Protocol), il est nécessaire de créer un protocole qui connecte tous ces groupes participant à la coalition. Ce protocole doit permettre de créer des connexions inter-groupes, supporter facilement les changements de topologies et appliquer des politiques de routage qui permettent d’indiquer des préférences de groupes à emprunter, par exemple. Dans cette thèse, nous allons dans un premier temps étudier la non-adaptabilité de BGP sur les réseaux MANET. Puis, nous étudierons les différentes propositions de la littérature. Ensuite, nous présenterons notre solution ITMAN (Inter Tactical Mobile Ad hoc Network) dans sa première version et les améliorations que nous avons pu y apporter. Enfin, nous terminerons ce manuscrit par les perspectives qui peuvent être menées suite à cette thèse. / Nowadays, military operations are organized as coalitions. The armed forces that are deployed have technological features (communication, routing) that create wireless networks. The mobility of these forces on the ground means that the network has a highly dynamic topology. This is a mobile wireless network, more commonly called MANET (Mobile Ad hoc NETwork). For mission and communication efficencies, interconnection between the various groups participating in the coalition is necessary. However, each member of the coalition has its own architecture and wants to keep independancy from the other groups technologies. This situation is similar as the Internet construction, where operators were able to interconnect their infrastructures with BGP (Border Gateway Protocol). It is important to create a protocol that can connect all the groups involved in the coalition. This protocol should allow inter-group connections, easily support topology changes and apply routing policies that specifies groups on the route preferences, for example. In this thesis, we first study the adaptability issues of BGP on MANET. Then, we study the proposals that have been made in the literature. Next, we present ITMAN (Inter Tactical Mobile Ad Hoc Network) in its first version and the improvements that have been made. Finally, we will conclude this manuscript with the perspectives that can be highlighted following this thesis.