Les travaux de recherche menés dans le cadre de cette thèse concernent l'amélioration du débit et de la qualité de service dans les réseaux sans fil basés sur les standards de la famille 802.11. Des simulations exhaustives ont été menées pour l'analyse et l'évaluation des performances des protocoles de routages réactifs AODV, DSR et DYMO ainsi que des protocoles de routage proactifs DSDV, FSR et OLSR. Plusieurs paramètres ont été considérés comme la mobilité des noeuds la charge du réseau et la mise à l'échelle. Nous pouvons observer que la métrique de qualité de lien est un paramètre important dans toute stratégie de routage. L'objectif du présent travail est de proposer une analyse comparative des différents protocoles de routage, basée sur les métriques de qualité de lien et de proposer une nouvelle métrique permettant d'améliorer le routage en termes de routage et de délai bout-en-bout. Dans la disparité des métriques proposées dans la littéraire, la métrique ETX (Expected Transmission Count) a été largement utilisée. Aussi, nous focaliserons, principalement, sur les métriques basées sur ETX. Notre constatation est que les besoins en termes de qualité de service dans les réseaux sans fil multi-saut, sont affecté entre autre par le protocole de routage adopté et la métrique de lien utilisée. Cependant, ceci est aussi strictement lié à la qualité des canaux de communication au niveau physique et l'état des files d'attente au niveau MAC. Aussi, une nouvelle métrique de qualité de lien est proposée, basée sur ETX et appelée IBETX (Interference and Bandwidth Adjusted ETX). Cette nouvelle métrique prend en considération les effets de l'interférence et de l'impact de l'état de la couche MAC sur les performances des liens de communication. Des simulations ont été conduites sous NS-2 afin de montrer l'intérêt de la métrique utilisée. Ainsi IBETX améliore le débit efficace de 19% par rapport à ETX et de 10% par rapport à ETP (Expected Throughput). Par ailleurs, la métrique proposée réduit le délai bout en bout de 16% par rapport à ELP ( Expected Link Performance) et de 24% par à ETX / This dissertation endeavors to contribute enhancements in goodputsof the IEEE 802.11-based Wireless Multi-hop Networks (WMhNs).By performing exhaustive simulations, for the deep analysis and detailed assessment of both reactive (AODV, DSR, DYMO) and proactive (DSDV, FSR, OLSR) protocols for varying mobilities, speeds, network loads and scalabilities, it is observed that a routing link metric is a significant component of a routing protocol. In addition to finding all available paths, the fastest end-to-end route is selected by a link metric for the routing protocol. This study aims the quality routing. In the class of quality link metrics, Expected Transmission Count (ETX) is extensively used. Thus, the most recently proposed ETX-based metrics have been analyzed. Though, newly developed metrics over perform ETX but still they can be improved. By profound analysis and particularized comparison of routing protocols depending upon their classes (reactive and proactive) and ETX-based metrics, we come to realize that users always demand proficient networks. In fact, WMhNs are facing several troubles which they expect to be resolved by the routing protocol operating them. Consequently, the protocol depends upon the link metric for providing quality paths. So, we identify and analyze the requirements to design a new routing link metric for WMhNs. Because, considering these requirements, when a link metric is proposed, then : firstly, both the design and implementation of the link metric with a routing protocol become easy. Secondly, the underlying network issues can easily be tackled. Thirdly, an appreciable performance of the network is guaranteed. Keeping in view the issues of WMhNs, increasing demands of users and capabilities of routing protocols, we propose and implement a new quality link metric, Interference and Bandwidth Adjusted ETX (IBETX). As, MAC layer affects the link performance and consequently the route quality, the metric therefore, tackles the issue by achieving twofold MAC-awareness. Firstly, interference is calculated using cross-layered approach by sending probes to MAC layer. Secondly, the nominal bit rate information is provided to all nodes in the same contention domain by considering the bandwidth sharing mechanism of 802.11. Like ETX, our metric also calculates link delivery ratios that directly affect throughput and selects those routes that bypass dense regions in the network. Simulation results by NS-2 show that IBETX gives 19% higher through put than ETX and 10% higher than Expected Throughput (ETP). Our metric also succeeds to reduce average end-to-end delay up to 16% less than Expected Link Performance (ELP) and 24% less than ETX

Cette thèse traite de l'étude des spanneurs multichemins, comme extension des spanneurs de graphes classiques. Un spanneur H d'un graphe G est un sous-graphe couvrant tel que pour toute paire de sommets du graphe a,b « appartient à » V(G) la distance dans le spanneur dh(a,b) n'est pas trop étirée par rapport à la distance dans le graphe d'origine dg(a,b). Ainsi il existe un facteur d'étirement (alpha, beta) tel que pour tout a,b« appartient à »V(G), dh(a,b)« est inférieur ou égal à » alpha dg(a,b)+beta. Motivés par des considérations de routage à plusieurs chemins et après la remarque que le concept de spanneur peut être étendu à toute métrique « non décroissante », nous introduisons la notion de spanneur multichemins. Après une introduction au domaine, nous parlerons des résultats obtenus concernant d'une part les spanneurs multichemins arêtes disjoints et d'autre part les spanneurs multichemins sommets disjoints. / This thesis deals with multipath spanners, as an extension of classical graph spanners. A spanner H of a graph G is a spanning subgraph such that for any pair of vertices a,b « is an element of » V(G) the distance measured in the spanner dh(a,b) isn't too much stretched compared to the distance measured in the original graph dg(a,b). As such there exists a stretch factor (alpha, beta) such that for all a,b« is an element of »V(G), dh(a,b)«is less than or equal to » alpha dg(a,b)+beta. Motivated by multipath routing and after noting that the concept of spanner can be extended to any “non decreasing” metric, we introduce the notion of multipath spanner. After an introduction to the topic, we will show the results obtained. The first part is devoted to edge-disjoint multipath spanners. The second part id devoted to vertex-disjoint spanners.

L'Internet est organisé sous la forme d'une multitude de réseaux appelés Systèmes Autonomes (AS). Le Border Gateway Protocol (BGP) est le langage commun qui permet à ces domaines administratifs de s'interconnecter. Grâce à BGP, deux utilisateurs situés n'importe où dans le monde peuvent communiquer, car ce protocole est responsable de la propagation des messages de routage entre tous les réseaux voisins. Afin de répondre aux nouvelles exigences, BGP a dû s'améliorer et évoluer à travers des extensions fréquentes et de nouvelles architectures. Dans la version d'origine, il était indispensable que chaque routeur maintienne une session avec tous les autres routeurs du réseau. Cette contrainte a soulevé des problèmes de scalabilité, puisque le maillage complet des sessions BGP internes (iBGP) était devenu difficile à réaliser dans les grands réseaux. Pour couvrir ce besoin de connectivité, les opérateurs de réseaux font appel à la réflection de routes (RR) et aux confédérations. Mais si elles résolvent un problème de scalabilité, ces deux solutions ont soulevé des nouveaux défis car elles sont accompagnées de multiples défauts; la perte de diversité des routes candidates au processus de sélection BGP ou des anomalies comme par exemple des oscillations de routage, des déflections et des boucles en font partie. Les travaux menés dans cette thèse se concentrent sur oBGP, une nouvelle architecture pour redistribuer les routes externes à l'intérieur d'un AS. `A la place des classiques sessions iBGP, un réseau de type overlay est responsable (I) de l'´echange d'informations de routage avec les autres AS, (II) du stockage distribué des routes internes et externes, (III) de l'application de la politique de routage au niveau de l'AS et (IV) du calcul et de la redistribution des meilleures routes vers les destinations de l'Internet pour tous les routeurs clients présents dans l'AS / The Internet is organized as a collection of networks called Autonomous Systems (ASes). The Border Gateway Protocol (BGP) is the glue that connects these administrative domains. Communication is thus possible between users worldwide and each network is responsible of sharing reachability information to peers through BGP. Protocol extensions are periodically added because the intended use and design of BGP no longer fit the current demands. Scalability concerns make the required internal BGP (iBGP) full mesh difficult to achieve in today's large networks and therefore network operators resort to confederations or Route Reflectors (RRs) to achieve full connectivity. These two options come with a set of flaws of their own such as route diversity loss, persistent routing oscillations, deflections, forwarding loops etc. In this dissertation we present oBGP, a new architecture for the redistribution of external routes inside an AS. Instead of relying on the usual statically configured set of iBGP sessions, we propose to use an overlay of routing instances that are collectively responsible for (I) the exchange of routes with other ASes, (II) the storage of internal and external routes, (III) the storage of the entire routing policy configuration of the AS and (IV) the computation and redistribution of the best routes towards Internet destinations to each client router in the AS

Examensarbetet handlar om att minimera en total servicekostnad för företaget Chargestorm då de skall utföra service på sina laddningscentraler för elbilar. En ruttoptimering har gjorts som resulterar i ett antal rutter som är tänka att användas av en servicetekniker när denne åker runt och utför service på laddningscentralerna. En simulering har också gjorts för att påvisa de bästa tidsintervallen då olika typer av service kan ske, med målet att minimera den totala servicekostnaden.

A mobile wireless ad hoc network (MANET) consists of a group of mobile nodes communicating wirelessly with no fixed infrastructure. Each node acts as source or receiver, and all play a role in path discovery and packet routing. MANETs are growing in popularity due to multiple usage models, ease of deployment and recent advances in hardware with which to implement them. MANETs are a natural environment for multicasting, or group communication, where one source transmits data packets through the network to multiple receivers. Proposed applications for MANET group communication ranges from personal network apps, impromptu small scale business meetings and gatherings, to conference, academic or sports complex presentations for large crowds reflect the wide range of conditions such a protocol must handle. Other applications such as covert military operations, search and rescue, disaster recovery and emergency response operations reflect the "mission critical" nature of many ad hoc applications. Reliable data delivery is important for all categories, but vital for this last one. It is a feature that a MANET group communication protocol must provide. Routing protocols for MANETs are challenged with establishing and maintaining data routes through the network in the face of mobility, bandwidth constraints and power limitations. Multicast communication presents additional challenges to protocols. In this dissertation we study reliability in multicast MANET routing protocols. Several on-demand multicast protocols are discussed and their performance compared. Then a new reliability protocol, R-ODMRP is presented that runs on top of ODMRP, a well documented "best effort" protocol with high reliability. This protocol is evaluated against ODMRP in a standard network simulator, ns-2. Next, reliable multicast MANET protocols are discussed and compared. We then present a second new protocol, Reyes, also a reliable on-demand multicast communication protocol. Reyes is implemented in the ns-2 simulator and compared against the current standards for reliability, flooding and ODMRP. R-ODMRP is used as a comparison point as well. Performance results are comprehensively described for latency, bandwidth and reliable data delivery. The simulations show Reyes to greatly outperform the other protocols in terms of reliability, while also outperforming R-ODMRP in terms of latency and bandwidth overhead.

As mobility and computing becomes ever more pervasive in society and business, the non-optimal use of radio resources has created many new challenges for telecommunication operators. Usage patterns of modern wireless handheld devices, such as smartphones and surfboards, have indicated that the signaling traffic generated is many times larger than at a traditional laptop. Furthermore, in spite of approaching theoretical limits by, e.g., the spectral efficiency improvements brought by 4G, this is still not sufficient for many practical applications demanded by end users. Essentially, users located at the edge of a cell cannot achieve the high data throughputs promised by 4G specifications. Worst yet, the Quality of Service bottlenecks in 4G networks are expected to become a major issue over the next years given the rapid growth of mobile devices. The main problems are because of rigid mobile systems architectures with limited possibilities to reconfigure terminals and base stations depending on spectrum availability. Consequently, new solutions must be developed that coexist with legacy infrastructures and more importantly improve upon them to enable flexibility in the modes of operation. To control the intelligence required for such modes of operation, cognitive radio technology is a key concept suggested to be part of the so-called beyond 4th generation mobile networks. The basic idea is to allow unlicensed users access to licensed spectrum, under the condition that the interference perceived by the licensed users is minimal. This can be achieved with the help of devices capable of accurately sensing the spectrum occupancy, learning about temporarily unused frequency bands and able to reconfigure their transmission parameters in such a way that the spectral opportunities can be effectively exploited. Accordingly, this indicates the need for a more flexible and dynamic allocation of the spectrum resources, which requires a new approach to cognitive radio network management. Subsequently, a novel architecture designed at the application layer is suggested to manage communication in cognitive radio networks. The goal is to improve the performance in a cognitive radio network by sensing, learning, optimization and adaptation.

This thesis deals with solving a real case from one specific part of Operations Research -- Discrete Models. The case can be classified as Vehicle Routing Problem (VRP) which is a subset of classical Travelling Salesman Problem (TSP). The VRP is modified TSP when requirements of customers and capacities of trucks play role. The data needed for calculations were taken from the real situation of Pivovar Svijany a.s. The problem can be defined as VRP with cars with different capacities and split delivery. Even though the mathematic model of the problem is known and described in the thesis, the size of the problem is too big to be optimized. Therefore heuristic was used to solve it. Because of the good computational results in the past the savings algorithm was chosen. Its model was set using Visual Basic for Applications (VBA). The thesis (among others) analyses the sensitivity of the output on the values of the factors that can be chosen by the analyst. At the end of the thesis the best found solution is presented and the initial and the new scheme of the circles are compared.

No description available.

[pt] Um avanço importante gerado pela tecnologia de TV digital é a possibilidade de interatividade com os usuários, realizada por meio do assim chamado canal de retorno. As redes ad hoc têm um grande potencial para atender esse tipo de serviço, pois podem ser empregadas em diversas áreas geográficas e idealmente de forma independente de infra- estrutura. Isso diminui o seu custo e propícia o aumento da velocidade de implantação deste tipo de rede. Uma das principais questões técnicas a serem resolvidas no contexto das redes móveis ad hoc é a necessidade de algoritmos eficientes para a realização do roteamento dos pacotes. O projeto Terminodes, desenvolvido pelo Instituto Federal de Tecnologia da Suíça, desenvolveu um protocolo de roteamento que utiliza a informação de localização. Este método de roteamento é freqüentemente proposto como um meio para prover escalabilidade em redes ad hoc distribuídas sobre áreas geográficas extensas. O roteamento baseado em localização é difícil quando há áreas de exclusão na topologia da rede e os nós são móveis ou freqüentemente desconectados para fins de economia de bateria. Portanto, a investigação da robustez do protocolo para esses casos é fundamental para avaliar seu uso em redes que podem servir como canal de retorno de TV digital. / [en] An important advance generated by the technology of digital TV is the possibility of interactivity with the users, what is done by means of the return channel. The mobile ad hoc networks have a great potential to provide this type of service, because it can ideally be used in diverse geographic areas and independent of any infrastructure. This minimizes the costs and the time needed to implement the network for this canal. One of the main questions techniques in the context of the mobile ad hoc networks is the necessity of efficient routing algorithms. The Terminodes project, developed by the Federal Institute of Technology of Switzerland, developed a routing protocol that is based in location information. This routing method frequently is a way to provide scalability in large ad hoc networks. The routing based on location is difficult when it has areas of exclusion in the topology of the network and the nodes are mobile or they are frequently disconnected to save battery. Therefore, assess the robustness of the protocol for these cases is basic to evaluate its use in networks for the digital TV return channel.

[pt] Com a era da globalização e a introdução da filosofia de Gestão da Cadeia de Suprimentos, os clientes têm se tornado cada vez mais exigentes no que diz respeito à qualidade e prazos de entrega, gerando uma competitividade crescente e uma busca por serviços cada vez mais customizados que, para as empresas de distribuição de produtos, tem se tornado um fator cada vez mais importante na obtenção de vantagem competitiva e conquista de fatias cada vez maiores do mercado. Nesse sentido, muitas empresas de transporte têm tentado dar maior confiabilidade, mais velocidade e flexibilidade, buscando obter maior eficiência e pontualidade nas tarefas de entrega e/ou coleta; um melhor aproveitamento da frota e dos motoristas; menores tempos de ciclo; melhor planejamento das rotas, gerando assim sensíveis reduções de custos operacionais, melhoria da imagem da empresa no mercado e, em função disso, uma conquista cada vez maior de mercado. Nesse sentido, de modo a obter excelência nos processos de distribuição física, muitas empresas têm adquirido os chamados sistemas de roteirizarão e programação de veículos ou, simplesmente, roteirizadores. Dado o crescimento na utilização de roteirizadores para redução de custos operacionais e a possibilidade por parte do autor de participar da implementação dessa tecnologia em uma empresa, os objetivos dessa dissertação são: Descrever a operação da Empresa Alfa onde foi realizada a implementação do roteirizador de veículos e a apresentação do processo de implementação do roteirizador na operação. Como o autor fez parte da implementação do roteirizador na Empresa Alfa, a metodologia utilizada para a elaboração desse trabalho incluiu: pesquisa bibliográfica, visitas in loco e entrevistas não estruturadas junto aos envolvidos na operação. O resultado desta dissertação é uma análise da operação da Empresa Alfa durante a implementação do roteirizador, mostrando seus pontos positivos e suas dificuldades extraídos apos finalizado o processo de implementação. / [en] Nowadays with the globalization and the introduction of the Supply chain management philosophy, the customers become more demanding in order to get better quality in delivery time, increasing competitiveness and a search for customized services that, for distribution companies, it has become the most important factor in order to get competitive advantage and to increase the market share. In accordance with these ideas, many distribution companies have tried to improve the reliability, speed and flexibility, in order to get higher efficiency and punctuality in the deliveries; better fleet and drivers utilization; lower time to planning routes, generating cost reduction, improvements of the company`s image in the market, and higher market share. Trying to get excellence in distribution process, many companies have acquired the routing and scheduling systems. Due to the growth of routing systems use and the possibility for the author to participate in an implementation of this technology in a company, the objectives of this work are: to describe the operation of the Alpha Company`s where the implementation has been done; and present the routing system implementation process. Since the author was part of the team in the implementation of routing system in the Alpha Company, the methodology used for the elaboration of this work included: bibliographical research, visits in loco to the Alpha Company`s operations and non structuralized interviews with the involved parts in the operation. As a result of this work, we have an analysis of the operation during the implementation of the Routing System in line with the main results getting after finished the implementation process.