Este trabalho apresenta uma nova estrutura matemática para a álgebra de caminhos, que permite analisar a convergência dos algoritmos de roteamento multi-restritivos hop-by-hop e, sob o ponto de vista da engenharia de tráfego e da Qualidade de Serviço (QoS) na arquitetura Generalized Multiprotocol Label Switching (GMPLS), garantir de maneira confiável a incorporação de novas métricas de roteamento aos algoritmos de roteamento baseados em múltiplas restrições. Baseando-se nessa nova álgebra de caminhos, são analisadas as propriedades de monotonicidade, isotonicidade e liberdade, conhecidas por garantir a convergência dos algoritmos de roteamento e, ao contrário do indicado na literatura até o momento, verifica-se que a propriedade de monotonicidade não e condição necessária e nem suficiente para garantir a convergência dos algoritmos de roteamento multi-restritivos hop-by-hop. Sendo assim, este trabalho propõe uma nova propriedade, denominada coerência, para a garantia da convergência do roteamento hop-by-hop e um novo algoritmo de roteamento hop-by-hop com convergência garantida. Para avaliar os resultados teóricos obtidos, s~ao analisados dois estudos de casos de aplicação do roteamento multi-restritivos hop-by-hop com o uso de uma ferramenta de simulação desenvolvida em MATLAB e baseada no algoritmo Eliminação de Loop pelo Nó de Destino (ELND) também proposto. Como resultado das simulações desses estudos de casos, verifica-se que as diferentes estratégias de otimização, necessárias as redes (GMPLS), impõem a necessidade de trabalhar com algoritmos de roteamento que permitam a definição de mais de duas métricas de roteamento com diferentes critérios de otimização para cada uma delas, comprovando, portanto, a necessidade do desenvolvimento e da continuação deste trabalho. / This work presents a new mathematical structure for paths algebra that allows the convergence analysis of hop-by-hop multi-constrained routing algorithms and, under the traffic engineering and quality of service perspectives in the Generalized Multiprotocol Label Switching (GMPLS) architecture, trustily ensures the aggregation of new routing metrics in a constrained-based routing. Based on this new paths algebra, we analyze the monotonicity, isotonicity and freeness properties, known as ensuring routing algorithms convergence, and despite of what has been indicated in the literature, we verified that the monotonicity property is not sufficient to ensure the hop-by-hop routing convergence. Therefore, this work proposes a new property, called coherence, as a necessary and sufficient condition to ensure it, as well as, a new multi-constrained hop-by-hop routing algorithm with ensured convergence. In order to evaluate the theoretical results obtained, two study cases of the hop-by-hop multi-constrained routing applications are analyzed in the present thesis by using the Eliminação de Loop pelo Nó de Destino (ELND) simulation tool, developed in MATLAB and also presented as a product of this work. As result of these study cases simulations, we verified that different optimization strategies, requested by the (GMPLS) networks, compel the use of routing algorithms that allow the specification of more than two routing metrics with different optimization criteria for each one of them, thus proving the necessity of this work and its continuation.

Este trabalho apresenta uma nova estrutura matemática para a álgebra de caminhos, que permite analisar a convergência dos algoritmos de roteamento multi-restritivos hop-by-hop e, sob o ponto de vista da engenharia de tráfego e da Qualidade de Serviço (QoS) na arquitetura Generalized Multiprotocol Label Switching (GMPLS), garantir de maneira confiável a incorporação de novas métricas de roteamento aos algoritmos de roteamento baseados em múltiplas restrições. Baseando-se nessa nova álgebra de caminhos, são analisadas as propriedades de monotonicidade, isotonicidade e liberdade, conhecidas por garantir a convergência dos algoritmos de roteamento e, ao contrário do indicado na literatura até o momento, verifica-se que a propriedade de monotonicidade não e condição necessária e nem suficiente para garantir a convergência dos algoritmos de roteamento multi-restritivos hop-by-hop. Sendo assim, este trabalho propõe uma nova propriedade, denominada coerência, para a garantia da convergência do roteamento hop-by-hop e um novo algoritmo de roteamento hop-by-hop com convergência garantida. Para avaliar os resultados teóricos obtidos, s~ao analisados dois estudos de casos de aplicação do roteamento multi-restritivos hop-by-hop com o uso de uma ferramenta de simulação desenvolvida em MATLAB e baseada no algoritmo Eliminação de Loop pelo Nó de Destino (ELND) também proposto. Como resultado das simulações desses estudos de casos, verifica-se que as diferentes estratégias de otimização, necessárias as redes (GMPLS), impõem a necessidade de trabalhar com algoritmos de roteamento que permitam a definição de mais de duas métricas de roteamento com diferentes critérios de otimização para cada uma delas, comprovando, portanto, a necessidade do desenvolvimento e da continuação deste trabalho. / This work presents a new mathematical structure for paths algebra that allows the convergence analysis of hop-by-hop multi-constrained routing algorithms and, under the traffic engineering and quality of service perspectives in the Generalized Multiprotocol Label Switching (GMPLS) architecture, trustily ensures the aggregation of new routing metrics in a constrained-based routing. Based on this new paths algebra, we analyze the monotonicity, isotonicity and freeness properties, known as ensuring routing algorithms convergence, and despite of what has been indicated in the literature, we verified that the monotonicity property is not sufficient to ensure the hop-by-hop routing convergence. Therefore, this work proposes a new property, called coherence, as a necessary and sufficient condition to ensure it, as well as, a new multi-constrained hop-by-hop routing algorithm with ensured convergence. In order to evaluate the theoretical results obtained, two study cases of the hop-by-hop multi-constrained routing applications are analyzed in the present thesis by using the Eliminação de Loop pelo Nó de Destino (ELND) simulation tool, developed in MATLAB and also presented as a product of this work. As result of these study cases simulations, we verified that different optimization strategies, requested by the (GMPLS) networks, compel the use of routing algorithms that allow the specification of more than two routing metrics with different optimization criteria for each one of them, thus proving the necessity of this work and its continuation.

This thesis proposes a new algorithm for multi-constrained Quality of Service Optimal Path Routing in the context of military applications. The objective of our routing algorithm is to manage network traffic according to quality of service requirements of connection requests using military metrics. The algorithm is mainly based on communication priority. The QoS metrics such as bandwidth, delay and packet loss ratio are considered as basic metrics on path finding. If there is no suitable path for the request, some existing connections with lower priorities may be broken to make space for a higher priority level connection request. In this case, priority and bandwidth are used as decisive metrics in cost computation

The automobile industry is constantly evolving and adapting to consumer demands. Automakers are constantly shaping their manufacturing and business processes to more accurately fit the market as well as reduce costs and maximize profits. Along with it, the customer expectations of vehicle quality, reliability, safety, and utility are also at an all-time high. After development, testing the developed system with various evaluation methods is important for the validation and verification of automotive systems. One of the most important evaluation methods for testing automotive systems from the automotive divisions like the power-train systems and ADAS is conducting test drives. Currently, the automotive divisions at Bosch have fixed routes that were planned manually. There is no routing solution, with updated map information and visualization of the route based on some automotive parameters, that can help them with planning the test drives for verifying their automotive systems. This thesis is based on providing a routing solution to engineers which will help them in planning routes based on the required determinants. This thesis report gives an analysis of the whole hypothesis of routing in the initial two chapters. Some fundamentally distinct routing methods and algorithms were examined. Research on some existing open source routing engines and complicated routing scenarios was also done. The outcome of this thesis is a 'TestRide planner' which provides basic routing solution with some extra route visualization functionality. Algorithms for two complex routing functions of distance-constrained routing and RDE-constraint routing were also composed.

Le thème général du sujet tourne autour de l'optimisation inter-couche des réseaux de capteurs basés sur la technologie ultra large bande ULB (UWB, Ultra Wide Band) moyennant des solutions protocolaires permettant d'un côté de répondre au besoin de qualité de service QdS à critères multiples dans les réseaux de capteurs sans fil et d'autre côté d'assurer le partage et l'allocation efficace les ressources disponibles (spectrale et temporelle) ainsi que l'optimisation de la consommation d'énergie dans des tels réseaux. Le domaine d'application cible choisi dans le présent travail est les systèmes de suivi des patients au sein d'un réseau de capteurs déployé en hôpital intelligent (WHSN, Large-scale Wireless Hospital Sensor Network). Dans ce contexte, nous avons proposé le modèle UWBCAS pour assurer le partage des ressources spectrales entre les PANs. Puis, nous avons conçu et implémenté un protocole MAC multi-canal multi-créneau de temps avec support de qualité de service, PMCMTP, pour assurer une allocation conjointe des canaux de fréquence et des créneaux de temps au sein de chaque réseau PAN. Enfin nous avons proposé l'algorithme JSAR qui traite à la fois les problèmes d'ordonnancement des cycles d'activités des membres du réseau dans le but d'optimiser la consommation d'énergie, d'allocation efficace des canaux de fréquence et des créneaux de temps afin d'améliorer le taux d'utilisation des ressources et les performances du réseau et de routage avec support de QdS à critères multiples afin de répondre aux besoins des applications supportées / The general context of the present memory is about the cross-layer optimization of wireless sensors networks based on ultra wide band technology UWB. The proposed solutions ensure the share and the efficient allocation of spectral and temporal resources, the optimization of the energy consumption and the support of multi-constraints quality of services QoS. The most challenging issue is providing a tradeoff between the resource efficiency and the multiconstrained QoS support. For this purpose, we proposed a new Wireless Hospital Sensor Network (WHSN) three-tiered architecture in order to support large-scale deployment and to improve the network performance. Then we designed a channel allocation scheme (UWBCAS,)and a prioritized multi-channel multi-time slot MAC protocol (PMCMTP) to enhance network performance and maximize the resource utilization. Finally, we proposed a joint duty cycle scheduling, resource allocation and multi-constrained QoS routing algorithm (JSAR) which simultaneously combines, a duty cycle scheduling scheme for energy saving, a resource allocation scheme for efficient use of frequency channels and time slots, and an heuristic for multi-constrained routing protocol

QoS routing is one of the major building blocks for supporting QoS in communication networks and, hence, a necessary component of future communication networks. Bandwidth- Constrained Routing Algorithm (BCRA) may help to satisfy QoS requirements such as end-to-end delay, delay-jitter etc when WFQ-like (Weighted Fair Queuing) scheduling mechanisms are deployed. The existing algorithms for bandwidth constrained routing suffer from high message overhead and have a high computational and space complexity. The work presented in the thesis, therefore, focuses on the different techniques that an be used to reserve bandwidth for a unicast connection with low protocol overhead in terms of number of messages. We have compared the performance of the proposed routing algorithms using simulation studies with other bandwidth constrained routing algorithms. The call blocking ratio and message overhead have been used as the performance metric to compare the proposed algorithm with the existing ones. We present three source routing algorithms for unicast connections satisfying the band- width requirement. The first two routing algorithms are based on the partitioning of the network. The link-state broadcasts are limited to the partition. In the first algorithm, the source node queries the other partitions for the state information on a connection request and computes the path based on the information received from the other partitions. The second algorithm is based on state aggregation. The aggregated state of other partitions is maintained at every node. The source node finds a feasible path based on the aggregated information. The path is expanded in every partition, if required, at the time of resource reservation. The third QoS routing algorithm uses the Distance Vector Tables to find a route for a connection. If the shortest path satisfies the bandwidth requirement, then it is selected; otherwise a random deviation is taken at the point where bandwidth requirement is not satisfied and shortest path algorithm is again followed. In all the three algorithms presented, the packets carry the entire path information to the destination node. Therefore, no per connection information is required to be maintained at the intermediate nodes. Simulation results indicate that the proposed algorithms indeed help educing the protocol overhead considerably, and at the same time they give comparable or better performance in terms of resource utilization across a wide range of workloads.

Submitted by Aelson Maciera (aelsoncm@terra.com.br) on 2017-05-22T20:04:01Z No. of bitstreams: 1 TeseALS.pdf: 2588373 bytes, checksum: 85ce391accc868c711a33c83006ee738 (MD5) / Approved for entry into archive by Ronildo Prado (ronisp@ufscar.br) on 2017-05-31T13:43:27Z (GMT) No. of bitstreams: 1 TeseALS.pdf: 2588373 bytes, checksum: 85ce391accc868c711a33c83006ee738 (MD5) / Approved for entry into archive by Ronildo Prado (ronisp@ufscar.br) on 2017-05-31T13:43:34Z (GMT) No. of bitstreams: 1 TeseALS.pdf: 2588373 bytes, checksum: 85ce391accc868c711a33c83006ee738 (MD5) / Made available in DSpace on 2017-05-31T13:52:08Z (GMT). No. of bitstreams: 1 TeseALS.pdf: 2588373 bytes, checksum: 85ce391accc868c711a33c83006ee738 (MD5) Previous issue date: 2017-03-07 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Vehicle routing problems occur in many practical situations where the distribution of goods and / or services to different demand points is necessary. In this context, this research aims to study a ship routing and scheduling problem that arises at the collection and delivery operations of different types of crude oil from offshore platforms to coastal terminals. In the paradigm adopted for the representation of the problem, the transportation is largely the result of the need to maintain inventories at each supply point (platforms) between minimum and maximum levels, considering production rates on these operating points and the demand attendance of each product in the coastal terminals. The routing and scheduling of the fleet aims to achieve minimum variable cost solutions, and considers various operational constraints, such as the maximum cargo volume transported on each ship, the ships mooring in the operational points ports, the simultaneous unloading of the ships in terminals with more than one berth, among many others. In this research, Inventory Constrained Routing Problem (ICRP) models in the maritime context have been modified and extended for appropriately representating and solving real problems based on data collected in a case study performed on a Brazilian oil company, involving relatively short distances and time horizons. Small sized instances are solved by a mathematical programming software. Given the difficulties of solving larger examples, this study proposes a multistart heuristic method that includes a metaheuristic GRASP and improvement procedures, and also a rolling horizon heuristic. Both methods provide feasible good quality solutions in reasonable computing times. In order to improve the quality of the solutions found by these constructive methods, it is also discussed a procedure that combines the mathematical programming software and local search heuristic methods (matheuristic). The results show the potential of the proposed models and solution methods to tackle the problem and produce competitive solutions. / Problemas de roteirização de veículos ocorrem em diversas situações práticas onde se faz necessária a distribuição de bens e/ou serviços a pontos dispersos de demanda. Nesse contexto, a presente pesquisa visa o estudo de um problema de roteirização e programação de navios presente em operações de coleta e entrega de diferentes tipos de óleo cru de diversas plataformas offshore para vários terminais costeiros. No paradigma adotado para representação do problema, o transporte dos produtos é em grande parte o resultado da necessidade de manutenção dos estoques em cada ponto de suprimento (plataformas) entre níveis mínimos e máximos, considerando-se as taxas de produção nesses pontos operacionais, assim como o atendimento da demanda de cada produto nos terminais costeiros para abastecer as refinarias. A roteirização e programação da frota visa a obtenção de soluções de mínimo custo variável e considera várias restrições operacionais, tais como o volume máximo de carga transportada em cada navio, a viabilidade de atracação de navios em portos dos pontos operacionais, os descarregamentos simultâneos de navios em terminais com mais de um berço, dentre várias outras. Nesse sentido, modelos de otimização da literatura de roteirização veículos com restrições de estoque (Inventory Constrained Routing Problem – ICRP) no contexto marítimo foram modificados e estendidos para representação do problema e resolução de exemplares de uma situação real, definidos a partir de dados coletados em um estudo de caso realizado em uma empresa petrolífera nacional, envolvendo distâncias relativamente curtas e com horizontes de planejamento de curto prazo (poucas semanas). Exemplares de pequeno porte são resolvidos por meio da utilização de um software de programação matemática. Dada a dificuldade de resolução dos exemplos de maior porte, é proposto um método heurístico de múltiplos reinícios composto por uma metaheurística GRASP e procedimentos de melhoria, além de uma heurística de horizonte rolante, que proporcionaram a obtenção de soluções factíveis de boa qualidade em tempos computacionais aceitáveis. Com intuito de melhorar a qualidade das soluções encontradas pelos métodos construtivos, é também discutido um procedimento que combina o software de programação matemática e métodos heurísticos com busca local (mateheurística). Os resultados mostram o potencial dos modelos e métodos de solução aqui desenvolvidos e propostos para abordar o problema e produzir soluções competitivas em relação às soluções da empresa.