No description available.

O transporte de cargas desempenha um papel fundamental nos sistemas logísticos uma vez que possibilita o fluxo de produtos entre os elementos dos canais de distribuição, além de representar um elevado percentual de participação nos custos logísticos totais. Desse modo, a eficiência dos serviços de transporte depende diretamente de um adequado processo de planejamento em nível estratégico, tático e operacional. O transporte rodoviário, em particular, apresenta em nível operacional, problemas de elevada complexidade como a roteirização e o carregamento de veículos. Durante os últimos 50 anos estes problemas vêm sendo objeto de intensos estudos e desenvolvimentos, porém de forma separada, conduzindo a resultados difíceis de serem implementados nas situações práticas, devido à grande interdependência existente entre roteirização e carregamento de veículos. A resolução integrada destes dois problemas é recente na literatura, o que abre um campo bastante promissor para novos desenvolvimentos. Assim, esta tese tem como objetivo propor uma abordagem integrada de resolução para o problema de roteirização e carregamento de veículos onde, além das restrições de carregamento tridimensionais, as restrições de tempo de ciclo e distribuição de peso nos eixos são consideradas. Este modelo adota uma abordagem aproximativa que combina o uso de heurísticas para construção dos carregamentos com a metaheurística de Busca Tabu para melhoria dos roteiros de entrega. Para execução dos testes computacionais é proposto um conjunto de 12 instâncias que buscam simular situações práticas encontradas nas operações de entrega feitas por empresas de transporte e prestadores de serviços logísticos. A partir desse conjunto de instâncias são construídos cenários que avaliam o uso de diferentes tipos de veículos e os respectivos custos operacionais. Testes complementares realizados com um conjunto de 27 instâncias disponíveis na literatura, demonstram a capacidade do modelo proposto de atingir boas soluções em um tempo de processamento aceitável. / Freight transportation plays a fundamental role in logistics systems, once it enables the product flow between distribution channels elements, besides to represents a high percentage of participation on the total logistics costs. In this way, transport service efficiency depends directly of a suitable process of planning in strategic, tactical and operational level. The road transportation, in particular, shows in operational level high complexity problems as routing and loading of vehicles. During the last 50 years, these problems has been object of deep studies and developments, but in a separate manner, leading to results that are difficult to implement in practical situation due to the interdependence between routing and loading of vehicles. The integrated resolution of these two problems is recent in the literature, what opens a quite promising field for new developments. Thus, this thesis has as objective to propose an integrated resolution approach for the vehicle routing and loading where, besides the three-dimensional loading constraints, constraints, the time cicle and the distribution load over de axles are considered. This model adopts an approximated approach that combines the use of heuristics for loading construction with Tabu Search metaheuristics to improve the delivery routes. For computational tests execution is proposed a 12 instances set that tries to simulate practical situation found in delivery operations made by freight firms and thirty party logistics. From this instance set, it is built scenarios that evaluate the use of different vehicle types and the respectives operational costs. Complementary tests made with a 27 instances set available in literature show the capacity of proposed model to get good solutions in an acceptable computational time.

O transporte de cargas desempenha um papel fundamental nos sistemas logísticos uma vez que possibilita o fluxo de produtos entre os elementos dos canais de distribuição, além de representar um elevado percentual de participação nos custos logísticos totais. Desse modo, a eficiência dos serviços de transporte depende diretamente de um adequado processo de planejamento em nível estratégico, tático e operacional. O transporte rodoviário, em particular, apresenta em nível operacional, problemas de elevada complexidade como a roteirização e o carregamento de veículos. Durante os últimos 50 anos estes problemas vêm sendo objeto de intensos estudos e desenvolvimentos, porém de forma separada, conduzindo a resultados difíceis de serem implementados nas situações práticas, devido à grande interdependência existente entre roteirização e carregamento de veículos. A resolução integrada destes dois problemas é recente na literatura, o que abre um campo bastante promissor para novos desenvolvimentos. Assim, esta tese tem como objetivo propor uma abordagem integrada de resolução para o problema de roteirização e carregamento de veículos onde, além das restrições de carregamento tridimensionais, as restrições de tempo de ciclo e distribuição de peso nos eixos são consideradas. Este modelo adota uma abordagem aproximativa que combina o uso de heurísticas para construção dos carregamentos com a metaheurística de Busca Tabu para melhoria dos roteiros de entrega. Para execução dos testes computacionais é proposto um conjunto de 12 instâncias que buscam simular situações práticas encontradas nas operações de entrega feitas por empresas de transporte e prestadores de serviços logísticos. A partir desse conjunto de instâncias são construídos cenários que avaliam o uso de diferentes tipos de veículos e os respectivos custos operacionais. Testes complementares realizados com um conjunto de 27 instâncias disponíveis na literatura, demonstram a capacidade do modelo proposto de atingir boas soluções em um tempo de processamento aceitável. / Freight transportation plays a fundamental role in logistics systems, once it enables the product flow between distribution channels elements, besides to represents a high percentage of participation on the total logistics costs. In this way, transport service efficiency depends directly of a suitable process of planning in strategic, tactical and operational level. The road transportation, in particular, shows in operational level high complexity problems as routing and loading of vehicles. During the last 50 years, these problems has been object of deep studies and developments, but in a separate manner, leading to results that are difficult to implement in practical situation due to the interdependence between routing and loading of vehicles. The integrated resolution of these two problems is recent in the literature, what opens a quite promising field for new developments. Thus, this thesis has as objective to propose an integrated resolution approach for the vehicle routing and loading where, besides the three-dimensional loading constraints, constraints, the time cicle and the distribution load over de axles are considered. This model adopts an approximated approach that combines the use of heuristics for loading construction with Tabu Search metaheuristics to improve the delivery routes. For computational tests execution is proposed a 12 instances set that tries to simulate practical situation found in delivery operations made by freight firms and thirty party logistics. From this instance set, it is built scenarios that evaluate the use of different vehicle types and the respectives operational costs. Complementary tests made with a 27 instances set available in literature show the capacity of proposed model to get good solutions in an acceptable computational time.

Uma Rede Móvel Ad Hoc (MANET) consiste em uma coleção de terminais que possuem uma interface de transmissão e recepção sem fio (wireless) e que se movimentam em uma determinada área de abrangência. Geralmente esses terminais fazem uso de freqüências de rádio nas comunicações e configuram uma rede não infraestruturada. As MANETs, também conhecidas como independentes, não necessitam de qualquer infra-estrutura pré-existente para prover comunicação entre os nós, contudo, são utilizadas, principalmente quando integradas à Internet. Essa integração, apesar de possível, normalmente necessita de um gateway que encaminhe os pacotes entre as redes de computadores, respeitando as suas características individuais. Problemas, assim como atrasos e perdas de pacotes, podem ser provocados pelas diferenças intríncias aos protocolos de roteamento. Embora o Internet Engineering Task Force (IETF) proponha diversos protocolos de roteamento para as MANETs, o presente trabalho investiga o protocolo de roteamento Ad hoc On-Demand Distance Vector (AODV), por ser considerado um dos protocolos mais implementados e estudados pelo grupo de trabalho do IETF. O nodo gateway, embora já esteja implementado no protocolo de roteamento AODV (HAMIDIAN, 2003), deve ser capaz de interagir com as funções de roteamento da Internet, trocando tráfego com a mesma, de modo transparente e eficiente. O protocolo AODV, por ser reativo, pode demorar até 0,05 segundos para estabelecer uma rota entre um nodo origem e um nodo destino. Nos padrões atuais esse tempo pode ser considerado exageradamente alto, gerando gargalos entre sub-redes, descarte de pacotes e baixa eficiência. O presente trabalho apresenta uma proposta de customização do protocolo de roteamento AODV com atuação restrita ao nodo gateway. Esta customização consiste na adição de uma métrica de confiabilidade no processo de descoberta e utilização de rotas visando a redução no número de pacotes descartados e um ganho de eficiência no fluxo de dados entre as sub-redes envolvidas. / A Mobile Ad Hoc Network (MANET) consists of a collection of mobile hosts, moving in certain range area, that has a wireless interface for transmission and receiving data. Usually these terminals make use of radio frequencies in communications and configure a non infrastructured network. The MANETs, also known as independent, require no pre-existing infrastructure to provide communication between network mobile nodes, however, are used, preferably when integrated with the Internet. This integration, although possible, usually need a gateway that forwards packets between both computer networks, keeping their individual characteristics. Problems such as delays and packet losses can be caused by differences inherent in the routing protocols. Although the Internet Engineering Task Force (IETF) proposes several routing protocols for MANETs, this paper investigates the Ad hoc On-Demand Distance Vector (AODV) routing protocol, viewed as one of more implemented and studied protocol by the IETF work group. The gateway node, which is already implemented in the AODV routing protocol (Hamidian, 2003), should be able to interact, transparently and efficiently, with the Internet routing functions exchanging traffic between them. The AODV protocol, being reactive, can take up to 0.05 seconds to establish a route between a source node and a destination node. By today's standards this time may be considered excessively high, creating bottlenecks between subnets, packet drop and low efficiency. This paper proposes an AODV routing protocol customization restricted to the gateway node activities. This customization consists of adding reliability metric in the route discovery process and its consequent use in order to reduce the number of dropped packets and get increased efficiency in the data flow between the subnets involved.

Doctor of Philosophy / Economics / Philip G. Gayle / This dissertation consists of three essays on product quality in commercial aviation. Since the mid-1990s, major airlines that serve the U.S. domestic market have increasingly found it appealing to form alliances. Amidst the recent emergence of airline alliance formation, this dissertation has sought to answer questions on the product quality implications of policies regarding cooperation among airlines in the U.S. domestic air travel industry. A challenge that empirical work faces in studying the relationship between airline alliances and product quality is to find reasonable measure(s) of product quality. The first essay sheds light on whether the route network integration that comes with an airline alliance provides sufficient extra incentive to partner carriers to improve their flight routing quality. Evidence suggests that routing quality for Delta/Continental/Northwest's--our alliance of interest--products decreases in markets where pre-alliance competition among alliance partners exists, resulting in substantial negative welfare effects for passengers. In fact, routing quality for Delta/Continental/Northwest products decreased by 0.256% below the mean routing quality of the entire sample's products. More interestingly, the codeshare effects in specific markets where the alliance firms competed prior to the alliance, are also negatively associated with routing quality of the alliance firms' products, resulting in a fall in consumer utility of $0.5 per consumer. The second essay explores the potential relationship between on-time performance and airline code-sharing. Although flight delay has always received much attention, we are unaware of any empirical research that measures the on-time performance effects of airline alliances. We empirically investigate the on-time performance effects of the largest U.S. domestic alliance that began in June 2003--an alliance between Delta Air Lines, Northwest Airlines and Continental Airlines. We find evidence that code-sharing improves alliance partners' on-time performance and that the size of the alliance effect on on-time performance depends on pre-alliance competition in a market, with the effect being larger in markets where the partners competed in prior to the alliance. Using a structural econometric model, the third essay attempts to provide an alternative explanation to a long-standing question: why are airlines late? Airlines usually claim that air travel delays are out of their control, placing the blame on adverse weather or air traffic control as the most common reasons. Despite these claims, data on causes of flight delay reveal that the share of delay caused by weather and air traffic control has been on the decline while the share of delay caused by airlines has been on the rise. This suggests that on-time performance improvement is well within the reach of carriers. We investigate why airlines have little or no incentive to improve on-time performance. We also measure the cost of delay borne by consumers in terms of how much monetary value they are willing to pay to avoid delay. We find that consumers are willing to pay $0.78 for every minute of arrival delay which after extrapolation, amounts to consumer welfare effects of $1.76 billion. Our findings suggest that airlines have little to no incentive because their markups do not increase when they improve on-time performance. In fact, the marginal increase in price resulting from on-time performance improvement is offset by an increase in marginal cost causing a zero net effect on markup.

[pt] Os problemas advindos da área de logística de transportes, em especial no que diz respeito ao uso racional de frotas de veículos, são amplamente estudados na área de otimização combinatória. A natureza intrinsicamente combinatorial desses problemas sugere que boa parte deles pode ser formulada e resolvida como um problema de programação linear inteira. Contudo, a maioria dos algoritmos atualmente disponíveis não consegue encontrar, em tempos computacionais aceitáveis, a solução ótima para instâncias de porte razoável. O sucesso desses algoritmos tem sido limitado, em parte devido ao fato dos mesmos não explorarem avanços recentes na área de programação linear inteira. Algumas dessas novas técnicas e suas aplicações a problemas de roteamento de veículos são o objeto de estudo desta dissertação. Primeiro são apresentadas as técnicas básicas de decomposição de problemas de programação linear e linear inteira e de geração de colunas. A resolução de problemas de programação linear inteira neste contexto é tratada em seguida, com a descrição do algoritmo branch-and-bound e das variações branch-and-cut, branch-and-price e branch-and- cut-and-price. Em seguida são descritos problemas de roteamento onde essa metodologia foi aplicada. Inicialmente, é apresentado o problema de roteamente do veículos com restrição de capacidade, o PRVC. Em seguida são apresentados problemas de roteamento de veículos com janela de tempo e frota heterogenea. Para cada problema, descrevemos como as técnicas descritas acima foram aplicadas e os resultados computacionais para um grande número de instâncias. Finalmente, no último capítulo, mostramos um caso real da aplicação do problema de roteamento de veículos com janela de tempo e frota heterogênea, que é o caso do problema de distribuição de jornais numa grande empresa de comunicação do Rio de Janeiro. / [en] Optimization techniques have an important role in Transportation Logistics. The combinatorial nature of several problems related to this area seggests integer programming as a natural approach to solve them. Nevertheless, there are many cases in which instances of reasonable size are still beyond the resolution capability of the algotithms presented in the literature. The sucess of the known algotithms have therefore been limited partly to the fact that most of them have not incorporated any recent relevant advances in the combinatorial optimization field. Some of these new techniques and their applications are the main subject of this dissertation. Firstly, basic decomposition techniques for linear and integer programming problems, as well as the relates column generation approach are addressed. This is followed by the presentation of a reformulation technique for linear and integer programming, which is alternative to the well known Dantzig-Wolfe master program. The new possibilities arousing from this approach are explored and the resulting consequences to the standard branch-and-bound algotithm and its variations branch-and- cut, branch-and-prince and branch-and-cut-and-price are presented. Later, routing problems where this methodology was applied were addressed with the capacitated vehicle routing problems - CVRP and followed by vehicle routing problems with time windows and heterogeneous fleet. For each problem, it is described how the techniques mentioned above were reported. Finally, in the last time windows and heterogeneous fleet, which is the case of a newspaper distribution in a major communication company in Rio de Janeiro.

Due to the high availability of cheap hardware, wireless multi-hop networks and in particular Wireless Mesh Networks (WMNs) are becoming popular in more and more contexts. For instance, IEEE 802.11 based WMNs have already started to be deployed as means to provide Internet access to rural areas in the developing world. To lower the cost and increase the coverage in such deployments, the wired network is extended with a wireless backbone of fixed mesh routers. With advances in technology and reduction in price comes also the possibility for more powerful wireless nodes, having multiple radios that allow transmitting on different channels in parallel. To be a successful platform for providing general Internet access, wireless multi-hop networks must provide support for common Internet applications. As most of the applications in the Internet today use the Transmission Control Protocol (TCP), TCP performance is crucial. Unfortunately, the design of TCP’s congestion control that made it successful in today’s Internet makes it perform less than optimal in wireless multi-hop networks. This is due to, among others, TCP’s inability to distinguish wireless losses from congestion losses. The current trend for operating system designers is also to focus TCP development on high-speed fixed networks, rather than on wireless multi-hop networks. To enable wireless multi hop networks as a successful platform there is therefore a need to provide good performance using TCP variants commonly deployed in the Internet. In this thesis, we develop novel proposals for the network layer in wireless multi-hop networks to support TCP traffic more efficiently. As an initial study, we experimentally evaluate different TCP variants, with and without mobile nodes, in a MANET context. Our results show that TCP Vegas, which does not provoke packet loss to determine available bandwidth, reduces the stress on the network while still providing the same or slightly increased performance, compared to TCP Newreno. We further propose and evaluate packet aggregation combined with aggregation aware multi-path forwarding to better utilize the available bandwidth. IP layer packet aggregation, where small packets are combined to larger ones before sent to the link layer, has been shown to improve the performance in wireless multi-hop networks for UDP and small packet transfers. Only few studies have been made on the impact of packet aggregation on TCP traffic, despite the fact that TCP traffic constitutes the majority of the Internet traffic. We propose a novel aggregation algorithm that is specifically addressing TCP relevant issues like packet reordering, fairness and TCP timeouts. In a typical WMN scenario, the aggregation algorithm increases TCP performance by up to 70 % and decreases round trip time (RTT) by up to 40 %. A detailed evaluation of packet aggregation in a multi radio setting has shown that a naive combination of multi path routing and packet aggregation can cause valuable aggregation opportunities to be lost. Therefore, we propose a novel combined packet aggregation and aggregation aware forwarding strategy that can reduce delay, packet loss and increase TCP performance by around 30 %.

abstract: The increasingly recurrent extraordinary flood events in the metropolitan area of Monterrey, Mexico have led to significant stakeholder interest in understanding the hydrologic response of the Santa Catarina watershed to extreme events. This study analyzes a flood mitigation strategy proposed by stakeholders through a participatory workshop and are assessed using two hydrological models: The Hydrological Modeling System (HEC-HMS) and the Triangulated Irregular Network (TIN)-based Real-time Integrated Basin Simulator (tRIBS). The stakeholder-derived flood mitigation strategy consists of placing new hydraulic infrastructure in addition to the current flood controls in the basin. This is done by simulating three scenarios: (1) evaluate the impact of the current structure, (2) implementing a large dam similar to the Rompepicos dam and (3) the inclusion of three small detention dams. These mitigation strategies are assessed in the context of a major flood event caused by the landfall of Hurricane Alex in July 2010 through a consistent application of the two modeling tools. To do so, spatial information on topography, soil, land cover and meteorological forcing were assembled, quality-controlled and input into each model. Calibration was performed for each model based on streamflow observations and maximum observed reservoir levels from the National Water Commission in Mexico. Simulation analyses focuses on the differential capability of the two models in capturing the spatial variability in rainfall, topographic conditions, soil hydraulic properties and its effect on the flood response in the presence of the different flood mitigation structures. The implementation of new hydraulic infrastructure is shown to have a positive impact on mitigating the flood peak with a more favorable reduction in the peak at the outlet from the larger dam (16.5% in tRIBS and 23% in HEC-HMS) than the collective effect from the small structures (12% in tRIBS and 10% in HEC-HMS). Furthermore, flood peak mitigation depends strongly on the number and locations of the new dam sites in relation to the spatial distribution of rainfall and flood generation. Comparison of the two modeling approaches complements the analysis of available observations for the flood event and provides a framework within which to derive a multi-model approach for stakeholder-driven solutions. / Dissertation/Thesis / Masters Thesis Civil and Environmental Engineering 2016

Cette thèse démontre la pertinence de l’utilisation du Courant Porteur en Ligne (CPL) pour des applications de réseaux de capteurs. Nous nous focalisons sur la technologie basse consomma- tion et bas débit "WPC" développée par la société Watteco et nous montrons que son utilisation est justifiée pour des applications de réseaux de capteurs. Nous situons la solution WPC dans le paysage du CPL et déterminons les protocoles compatibles. Nous décrivons ensuite l’implé- mentation du module WPC et du média CPL dans le simulateur de réseau COOJA afin de proposer une solution réseau reposant sur l’adaptation du standard 802.15.4 sur la technologie WPC. Nous démontrons ensuite l’intérêt de la convergence des médias au niveau réseau par l’utilisation du standard IPv6, que nous adaptons sur notre solution CPL grâce au protocole 6LoWPAN. Nous justifions l’utilisation des protocoles standards de l’IETF sur notre solution CPL et nous montrons qu’une solution de routage sur CPL doit être développée. Nous montrons par des expérimentations que notre solution CPL correspond aux critères des réseaux basse puis- sance et supportant les pertes de transmissions (LLNs) pour lesquels le protocole standard RPL a été conçu. Nous justifions l’utilisation de ce protocole sur CPL, et validons son implémenta- tion dans le cadre de 2 expérimentations. Formées respectivement de 7 puis 26 noeuds CPL, les résultats montrent que le routage créé par RPL permet de couvrir un étage d’un bâtiment avec une topologie de type arbre et une profondeur de 3 sauts maximum. Nous montrons également que la technologie WPC permet une connectivité importante entre les noeuds du réseau et que la qualité des liens est fortement dynamique, mais que le routage permet de s’adapter à ces variations. Nous pointons également les limites de notre solution CPL qui présente des délais importants et des débits faibles, générant de contraintes fortes sur les applications. Notre solu- tion de réseau de capteur sur CPL repose sur le standard IP, permettant des échanges de paquets avec d’autres technologies. Nous étudions ainsi la possibilité de créer des réseaux hétérogènes mélangeant la technologie WPC et radio 802.15.4. Nous montrons que notre pile protocolaire permet la création de ce type de réseau, afin de profiter du meilleur des 2 mondes. Nous décri- vons ainsi l’architecture d’un noeud hybride Radio Fréquence (RF) / CPL permettant de faire transiter les paquets entre ces 2 médias. Nous montrons ensuite que l’utilisation combinée de ces 2 médias augmente le nombre de chemins disponibles et permet de faciliter le routage, en diminuant le nombre de sauts et le risque que certains noeuds du réseau soient inaccessibles. Nous démontrons ensuite que l’injection de noeuds CPL et RF/CPL dans un réseau formé de noeuds RF sur batterie permet de les délester de leur charge de routage afin de prolonger leur durée de vie. Nous présentons ensuite une optimisation énergétique matérielle et logicielle d’un noeud radio. Nous déterminons les paramètres des protocoles et les optimisations logicielles per- mettant de tirer au mieux partie de cette architecture et nous réalisons l’étude énergétique de la sonde embarquée sur le noeud. Au final, notre architecture présente une consommation totale inférieure à 17 μW. Nous indiquons dans les annexes nos implications dans les organismes de standardisation qui ont permis de valider l’implémentation. / This thesis demonstrate the relevance of Powerline Communication (PLC) usage for sensor networks applications. We focus in particular on the low power and low data rate PLC technol- ogy "Watt Pulse Communication" (WPC) developed by the Watteco company and justify its usage for sensor network applications. We situate the WPC technology in the PLC landscape and define compatible protocols. We then describe the WPC module and the PLC media im- plementation in the COOJA network simulator. This allows us to propose a network solution over this technology, leveraging on the adaptation of the 802.15.4 standard over the WPC tech- nology. We then demonstrate the benefit of media convergence at the network layer level, with the use of the IPv6 standard that we adapted over our PLC solution thanks to the 6LoWPAN protocol. We justify the usage of standards protocols over our PLC solution and show that a routing solutions must be developed over WPC. We show through experiments that our PLC solution match low power and lossy network (LLNs) criterions for which the RPL standard pro- tocol has been designed. We justify the usage of this routing protocol over our PLC solution, and validate its implementation through 2 experiments conducted in tertiary types buildings. Respectively composed of 7 and 26 PLC nodes, results show that the routing topology created by RPL enable the coverage an entire floor of a tertiary building with a tree based topology and 3 hops maximum path length. We also show that the WPC technology exhibits a high connectivity between nodes and that the link quality is highly dynamic. Though, we observed that the routing topology was able to handle these variations. We point out the limitations of our PLC solution, which presents high delays and low throughput, creating high constraints on applications. Our sensor network solution over PLC relies on the IP standard, enabling packets exchanges with other technologies using the same protocol. In particular, we study the possi- bility to create heterogeneous networks mixing the WPC technology with 802.15.4 radio. We show that our protocol stack used over PLC enable to create this type of network, in order to benefit from the best of these 2 worlds. We purpose an architecture of a hybrid Radio / PLC node enabling to transfer packets between these 2 media. Then, we show that the combined usage of these 2 media increase the number of available paths and facilitate the routing, while diminishing the number of hops and possible unreachability of nodes. We then demonstrate that the addition of PLC and Radio/PLC nodes in a RF based battery powered sensor network enable to relieve their routing charge in order to expand their lifetime. We then continue the energy study with a power consumption optimization of a wireless sensor network platform from the hardware and software standpoint. We first determine the operating frequency, the wake up frequency and the mode of operation of the micro controller offering the lowest power consump- tion. We then conduct an energy study of 4 different radio transceivers using the 2.4 GHz and 868 MHz frequency band, in order to determine the most efficient architecture. We determine the protocols parameters and the software optimization to reach the lower power consumption of this architecture. Finally, we realize the energy study of several probes than can be embedded on the node, according to their nature and functioning mode. Our final architecture exhibits a total power consumption that is lower than 17 μW, with an applicative reporting each 10 minutes and the maintenance of the reachability with the network. We also mention in annex parts our implication in standards developments organizations such as the IETF a the IPSO alliance, that allow us to validate the implementation of our solution through interoperability events.

Dans cette thèse, nous nous intéressons à plusieurs méthodes pour améliorer la sécurité des réseaux sans fil ad-hoc. Ces réseaux, ainsi que la sous-famille des réseaux de capteurs sans fil, sont une des solutions les plus intéressantes pour de nombreux problèmes, comme par exemple la collecte de données dans une large zone, ou bien la création d'infrastructure de communication après une catastrophe. Ces réseaux sont par nature collaboratifs, ce qui les rend très vulnérables à d'éventuels attaquants. Pour les protéger, nous étudions la sécurité des protocoles conçus pour ces réseaux. Premièrement, nous proposons SR3 (pour Secure and Resilient Reputation-based Routing), un algorithme de routage sécurisé et résilient pour le routage convergent (tous-vers-un) dans les réseaux de capteurs sans fil. SR3 route ses messages selon une mesure de réputation qui est bâtie sur des informations fiables. Ce protocole garantit la confidentialité de ses données, et l'inforgeabilité de ses paquets. Nous avons prouvé formellement ces propriétés avec deux outils de vérification : Scyther et CryptoVerif. Nous avons montré expérimentalement la résilience de SR3 quand confronté à divers scénarios d'attaque, et nous avons comparé nos résultats à plusieurs algorithmes de routage de la litérature. L'évaluation a montré que la résilience et l'équité fournies par SR3 sont meilleures que celles des autres protocoles, et cette distinction est accentuée si le réseau est peu dense. De plus, et contrairement aux autres protocoles, SR3 est capable de s'auto-adapter aux changements de comportement des attaquants afin d'assurer une qualité de service satisfaisante. Les analyses de la sécurité des protocoles de routage reposent presque toujourssur des simulations, qui évaluent la capacité du protocole à délivrer ses messages aux bons noeuds. Il existe plusieurs définitions différentes pour concevoir la sécurité du routage, mais à notre connaissance, elles considèrent seulement les protocoles de source routing, où les routes sont déterminées avant que le message ne soit envoyé. Nous proposons la notion de corruptibilité, une définition calculatoire et quantitative pour la sécurité du routage basée sur la capacité d'un attaquant à altérer les routes empruntées par un message. Nous illustrons ensuite ces définitions par plusieurs analyses de protocoles. Enfin, nous étudions les systèmes de détection d'intrusions (IDS) pour réseaux sans fil ad-hoc, et plus spécifiquement les sources de données utilisées pour leurs mécanismes de décision. Nous classifions celles-ci en fonction du niveau de coopération qu'elles requièrent, et en fonction de l'origine de leurs données. Nous proposons ensuite InDICE, un outil d'aide à la décision qui étant donné un IDS, permet de découvrir automatiquement quelles attaques seront indétectables par les sources de données qu'utilise cet IDS. Enfin, nous utilisons cet outil pour découvrir deux vulnérabilités dans des IDS de la littérature. / In this document, we focus on ways of increasing the security of wireless ad-hoc networks. These networks, and more specifically wireless sensor networks, look increasingly like the right answer to a lot of problem, such as data collection over a large area, or providing emergency network infrastructure after a disaster. They are also inherently exposed to malicious intents due to their collaborative nature. In order to protect them, we focus on the security aspects of the protocols built for these networks. We first propose a Secure and Resilient Reputation-based Routing protocol, called SR3. This protocol routes messages according to a reputation metric built using only trusted information. This protocol achieves data confidentiality and data packet unforgeability, which we prove formally using two verification tools: CryptoVerif and Scyther. We experimentally show the resiliency of SR3 against various attack scenarios, and we compared our results to several routing algorithms of the literature. This evaluation shows that both the resiliency and fairness accomplished by SR3 are better than for those others protocols, especially when the network is sparse. Moreover, and unlike previous solutions, if the compromised nodes behavior changes, then SR3 will self-adapt in order to ensure an acceptable quality of service. Analyses of routing protocols security are nearly always supported by simulations, which often evaluate the ability to deliver messages to a given destination. Several competing definitions for secure routing exist, but to our knowledge, they only address source routing protocols. We propose the notion of incorruptibility, a quantitative computational definition for routing security based on the attacker's ability to alter the routes used by messages. These definitions are then illustrated with several routing algorithms. Finally, we study Intrusion Detection Systems (IDS) for WANET, and more specifically their inputs. These systems provide a supplementary layer of defenses for WANETs, and they are able to easily detect attacks who are complicated for the network protocols. We classify the different inputs used by the decision process of these IDS, according to their level of required cooperation, and the source of their data. We then propose the InDICE tool, a decision aid which, given an IDS, allows automated discovery of undetectable attacks according to the inputs used by that IDS. In the end, we apply our framework to discover weaknesses in two existing IDS.