MATEUS, Bruno Góis. Análise sobre o impacto da densidade veicular, da carga da rede e da mobilidade no desempenho de protocolos de roteamento para redes veiculares. 2010. 136 f. Dissertação (Mestrado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2010. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-07-08T19:49:39Z No. of bitstreams: 1 2010_dis_bgmateus.pdf: 3335220 bytes, checksum: 4b0144b0ee1b7f925c7bb9fe44a92e9c (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-07-14T15:18:09Z (GMT) No. of bitstreams: 1 2010_dis_bgmateus.pdf: 3335220 bytes, checksum: 4b0144b0ee1b7f925c7bb9fe44a92e9c (MD5) / Made available in DSpace on 2016-07-14T15:18:09Z (GMT). No. of bitstreams: 1 2010_dis_bgmateus.pdf: 3335220 bytes, checksum: 4b0144b0ee1b7f925c7bb9fe44a92e9c (MD5) Previous issue date: 2010 / Advances in mobile computing and wireless communications have made possible the development of the Intelligent Transportation System, which contain the vehi- cular networks. There, routing is a challenging task due to the high node mobility, the instability of wireless links and the diversity of scenarios. For this reason, several routing protocols have been designed with the goal of solving one or more speci c problems of each scenario. However, although there are several proposed solutions to the routing problem in vehicular networks, none of them has achieved a satisfac- tory performance in more than one scenario, such as urban and highway. Thus, in this work, we rst analyze with simulations the impact of density, the network load and the mobility pattern in the performance of routing protocols for these networks. Then, we provide new directions for designing e cient vehicular network routing protocols, able to adapt to urban and highway scenarios. To achieve this goal, four existing protocols were evaluated in urban and highway scenarios. / Os avanços alcançados na computação móvel e na comunicação sem o levaram ao desenvolvimento do Sistema Inteligente de Transporte, onde se pode destacar as redes veiculares. Nelas, o roteamento é uma tarefa desa adora devido à alta mobi- lidade dos nós, à instabilidade dos enlaces sem- o e a diversidade de cenários. Por essa razão, diversos protocolos de roteamento foram projetados com o objetivo de solucionar um ou mais problemas especí cos de cada cenário. Entretanto, apesar de existirem várias soluções propostas para o problema do roteamento em redes veicu- lares, nenhuma delas alcançou um desempenho satisfatório em mais de um cenário, como urbano e rodovia. Sendo assim, nesta dissertação, analisamos através de si- mulações o impacto da densidade, da carga da rede e da mobilidade no desempenho de um protocolo de roteamento para fornecer diretrizes para os projetistas de redes veiculares desenvolverem protocolos de roteamento e cientes, capazes de se adaptar aos cenários urbano e de rodovia. Para alcançar esse objetivo, quatro protocolos existentes na literatura foram avaliados nos cenários urbano e de rodovia, dois deles voltados diretamente para redes veiculares e os outro dois tradicionais de redes —d ho™.

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.

Orientador: Prof. Dr. João Henrique Kleinschmidt / Dissertação (mestrado) - Universidade Federal do ABC, Programa de Pós-Graduação em Engenharia da Informação, 2017. / O interesse pela Internet das Coisas cresceu nos últimos anos e alavancou o estudo das tecnologias necessárias para o perfeito funcionamento desse novo paradigma. As mais diversas áreas do conhecimento tem influência sobre a IoT, desde as áreas ligadas a engenharia, preocupadas com a criação de padrões, dispositivos e aplicações, à áreas ligadas a legislação, comunicação, marketing, etc. Dentro do estudo da engenharia, o campo das padronizações tem trazido muitas oportunidades. A demanda por desenvolvimento de padrões que possibilitem a interoperabilidade de dispositivos aumenta a cada ano. Organizações, como IETF, já disponibilizaram uma série de protocolos dedicados à IoT, dentre eles o protocolo de roteamento RPL, que foi desenvolvido para redes de baixa potência com perdas. O trabalho apresentado a seguir faz o estudo do protocolo RPL em cenários híbridos, ou seja, onde os nós são móveis ou estáticos. Esse trabalho é necessário pois grande parte das aplicações de IoT serão utilizadas por dispositivos móveis e a especificação do RPL não contempla a mobilidade dos nós. O objetivo deste trabalho é entender como o protocolo se comporta nestes cenários cenários híbridos. A mobilidade dos nós é definida por modelos de mobilidade consagrados, como o Manhattan e o Random Waypoint. Notou-se que a mobilidade dos nós elevou a perda de pacotes da rede bem como o atraso. Além disso foi possível verificar com base no ETX que houve alteração da topologia da rede. Essas mudanças causada pela presença de nós móveis ocasionaram a elevação do consumo de energia dos nós. Verificou-se também que o ciclo de trabalho dos nós tem influência direta no desempenho do protocolo. / The interest in the Internet of Things has grown in recent years and has leveraged the study of the technologies necessary for the functioning of this new paradigm. The most different areas of knowledge have an influence on the IoT, since areas related to engineering, concerned about standards, development, devices and applications, until areas related to legislation, ncommunication, marketing, etc. In the engineering study, the standardization area has brought many opportunities. The demand for standards development that enables device interoperability increases every year. Organizations such as IETF already provided a series of protocols dedicated to IoT, including the RPL routing protocol, which was developed for lowpower lossy networks. The work presented here makes a study of the RPL protocol in hybrid scenarios, in other words, where the nodes are mobile or static. This work is necessary because most of the IoT applications will be used by mobile devices and the RPL specification does not include nodes mobility. The objective of this work is to understand the behavior of the protocol in hybrid scenarios. Nodes mobility is defined by well know mobility models, such as Manhattan and Random Waypoint. In this work was possible to verify the increase of latency and packet loss because of the nodes mobility. In addition, it was possible to verify, based on the ETX, that there was a change in the network topology. These changes caused by mobile nodes increase the power consumption. It was also verified that the duty cycle of the nodes has a direct influence in the protocol performance.

[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.

Made available in DSpace on 2016-06-02T19:05:27Z (GMT). No. of bitstreams: 1 1656.pdf: 2804908 bytes, checksum: c4d85936e5766095625c6510da07116b (MD5) Previous issue date: 2007-06-21 / Universidade Federal de Sao Carlos / Wireless sensor networks are increasingly being deployed for fine-grain monitoring of physical environments subjected to critical conditions such as fire, leaking of toxic gases and explosions. A great challenge to these networks is to provide channels that satisfy the necessities of the applications for events propagation, even in the presence of emergency conditions that can lead to node failures and path disruption to the sink that receives those events. Quality of Service (QoS) mechanisms can be applied that meet application requirements such as: low latency and packet delivery reliability, fast path repair in the presence of faults and network longevity with uniform energy dissipation. This work presents QoS-based routing solutions, which aims to meet, simultaneously, the main requirements mentioned above. The proposed solutions were implemented and simulated in the NS-2 simulator. Important metrics, such as end-to-end delay, packet loss rate, control messages overhead and energy consumption, were evaluated. The results show that the proposed solutions can be a potential alternative to the supervision and control of physical environments subject to emergency situations / As redes de sensores sem fio estão cada vez mais sendo utilizadas para o monitoramento preciso de ambientes físicos sujeitos a situações de emergência, tais como: incêndio, vazamento de gases tóxicos e explosões. Um grande desafio dessas redes é garantir a entrega de dados coletados, mesmo na presença de situações de emergência que possam vir a causar falhas nos nós sensores e interrupções de caminhos de entrega de dados. Mecanismos de Qualidade de Serviço (QoS) visam atender requisitos de aplicações, tais como: baixa latência e confiabilidade na entrega de pacotes, reparo rápido de caminhos na presença de falhas, e longevidade da rede com dissipação uniforme de energia. Este trabalho apresenta soluções de roteamento baseadas em QoS que visam atender, simultaneamente, os principais requisitos mencionados acima. As soluções propostas como parte deste trabalho foram implementadas e simuladas no simulador de redes ns-2 e comparadas a outras soluções existentes. Métricas importantes, tais como: atraso fim-a-fim, taxa de perda de pacotes, custo de mensagens de controle, bem como gasto de energia na disseminação de dados, foram avaliadas. Os resultados mostram que a solução proposta pode ser uma alternativa em potencial para a supervisão e controle de ambientes físicos sujeitos a situações de emergência

Made available in DSpace on 2014-06-11T19:24:00Z (GMT). No. of bitstreams: 0 Previous issue date: 2011-11-07Bitstream added on 2014-06-13T20:11:43Z : No. of bitstreams: 1 alexandre_la_me_sjrp.pdf: 320692 bytes, checksum: 6eed9e28aa2bc1202427d3e419739bc5 (MD5) / Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) / A utilização de computadores portáteis trouxe a necessidade de criação de redes de acesso sem fio. Mesmo com o padrão 802.11, um dos protocolos responsáveis por gerir os sistemas wireless, a mobilidade desejada não era alcançada. Diversas regiões de difícil acesso eram isoladas das redes de comunicação por não existir uma forma eficiente de levar os dados até estas. Pensando nisso, foram criadas as redes sem fio de múltiplos saltos, conhecidas por wireless mesh ou ad-hoc. Uma rede de múltiplos saltos é composta por diversos dispositivos que se interconectam por meio de conexão sem fio, levando assim a informação para regiões distantes. No entanto, há sérios problemas de segurança que atingem ambas as soluções: redes sem fio ou múltiplos saltos. Baseado no aspecto de segurança da informação, este trabalho apresenta soluções que podem ser utilizadas para fazer roteamento seguro de informações em redes de múltiplos saltos / The use of laptops brought the need for network wireless access creation. Even with the creation of 802.11 standard, which is one of the responsible for managing the wireless systems, the mobility desired was not enough. Many areas of difficult access were isolated from network communication because they din't have an efficient way to bring data to these areas. To address this, they created the wireless multi-hop, also know as wireless mesh or ad hoc. A wireless multi-hop network is composed of several devices that are interconnected by wireless connection, so they can bring information to distant areas. However, there are serious security issues that affect both solutions: wireless networks or multi-hop. Based on the aspect of information security, this paper presents solutions that can be used to secure routing information in multi-hop networks

Resumo: MANETs (Mobile Ad Hoc Networks) são redes sem fio e sem infra-estrutura estabelecidas dinamicamente, sem a necessidade de uma administração centralizada. Devido ao roteamento distribuído nessas redes e ao meio de comunicação sem fio redes Ad Hoc podem apresentar todos os problemas de segurança existentes em redes convencionais e ainda novos desafios. O uso de criptografia é a principal técnica para garantir a transferência de dados em uma rede de forma segura. Nos sistemas criptográficos assimétricos, os nós utilizam uma chave para cifrar uma mensagem e outra chave para decifrar a mesma. A tarefa de administrar essas chaves é realizada por um Sistema de Gerenciamento de Chaves, que define a emissão, o armazenamento, a distribuição, a proteção e a revogação das mesmas. Esse trabalho apresenta um novo Sistema de Gerenciamento de chaves baseado em Virtualização. Nesse sistema, chamado de Virtual Key Management (VKM), ´e utilizado uma estrutura virtual, sem qualquer relação com as coordenadas físicas dos nós da rede, para estabelecer a confiança entre os mesmos. Dessa forma, os nós seguem as regras estabelecidas por essa estrutura para realizar a emissão, o armazenamento, a distribuição, a proteção e a revogação de chaves públicas e de chaves privadas na rede. O VKM é 100% resistente a ataques de Criação de Identidades Falsas. Quando comparado com o Sistema de Gerenciamento de Chaves Públicas Auto-organizado (PGP-Like), o VKM mostra maior resistência contra ataques de Personificação e a mesma resistência contra ataques de Falta de Cooperação. Quando comparado com o Group-based Key Management (GKM), o VKM mostra maior resistência contra ataques de Criação de Identidades Falsas por ser 100% resistente ao mesmo. O Virtual Routing Protocol (VRP) e o Virtual Distance Vector (VDV) são dois protocolos de roteamento híbridos que utilizam uma estrutura virtual para definir a parte pró-ativa do protocolo. Esse trabalho também mostra que o impacto no roteamento causado pela incorporação do VKM nesses protocolos de roteamento causa queda na taxa de entrega de dados, aumento do atraso no envio de mensagens e aumento da sobrecarga gerada na rede.

Submitted by Automa??o e Estat?stica (sst@bczm.ufrn.br) on 2016-07-06T19:34:30Z No. of bitstreams: 1 MarceloHenriqueRamalhoNobre_TESE.pdf: 4355071 bytes, checksum: 05cf1b490e598685ec4e7b682423a8d9 (MD5) / Approved for entry into archive by Arlan Eloi Leite Silva (eloihistoriador@yahoo.com.br) on 2016-07-06T22:04:01Z (GMT) No. of bitstreams: 1 MarceloHenriqueRamalhoNobre_TESE.pdf: 4355071 bytes, checksum: 05cf1b490e598685ec4e7b682423a8d9 (MD5) / Made available in DSpace on 2016-07-06T22:04:01Z (GMT). No. of bitstreams: 1 MarceloHenriqueRamalhoNobre_TESE.pdf: 4355071 bytes, checksum: 05cf1b490e598685ec4e7b682423a8d9 (MD5) Previous issue date: 2015-11-23 / Coordena??o de Aperfei?oamento de Pessoal de N?vel Superior (CAPES) / A comunica??o sem fios ? uma tend?ncia no ambiente industrial atualmente e nessa tend?ncia temos o WirelessHART como uma das principais tecnologias. Com essa situa??o, ? natural que melhorias no desempenho sejam buscadas e um dos principais caminhos para isso passa pelo desenvolvimento de algoritmos de escalonamento e roteamento. Nesta tese ? apresentado uma revis?o da literatura sobre as principais solu??es em escalonamento e roteamento desenvolvidas especificamente para a tecnologia WirelessHART. Al?m disso prop?e um novo Algoritmo de escalonamento chamando Escalonamento Flow que visa melhorar aspectos de flexibilidade e de utiliza??o do superframe. Para prop?sitos de valida??o, ? desenvolvido e utilizado um m?dulo de simula??o para o Network Simulator 3 (NS-3) que modela aspectos como posicionamento, atenua??o de sinal e consumo de energia al?m de prover simula??es mais exatas por meio de configura??es de erro individuais para cada link. Este m?dulo tamb?m possibilita a gera??o do superframe de escalonamento a partir do grafo de roteamento utilizando os algoritmos Flow e Han. Para a valida??o do novo algoritmo s?o realizados experimentos comparativos entre o algoritmo Han e algoritmo Flow, avaliando crit?rios de aloca??o de links, delay e taxa de ocupa??o de superframe. Para valida??o da camada f?sica do m?dulo de simula??o, o escalonamento e o roteamento s?o configurados estaticamente e s?o desenvolvidos experimentos de confiabilidade e consumo de energia com topologias validadas na literatura e com varia??es de probabilidades de erro. / Wireless Communication is a trend in the industrial environment nowadays and on this trend, we can highlight the WirelessHART technology. In this situation, it is natural the search for new improvements in the technology and such improvements can be related directly to the routing and scheduling algorithms. In the present thesis, we present a literature review about the main specific solutions for Routing and scheduling for WirelessHART. The thesis also proposes a new scheduling algorithm called Flow Scheduling that intends to improve superframe utilization and flexibility aspects. For validation purposes, we develop a simulation module for the Network Simulator 3 (NS-3) that models aspects like positioning, signal attenuation and energy consumption and provides an link individual error configuration. The module also allows the creation of the scheduling superframe using the Flow and Han Algorithms. In order to validate the new algorithms, we execute a series of comparative tests and evaluate the algorithms performance for link allocation, delay and superframe occupation. In order to validate the physical layer of the simulation module, we statically configure the routing and scheduling aspects and perform reliability and energy consumption tests using various literature topologies and error probabilities.

Made available in DSpace on 2013-08-07T18:43:32Z (GMT). No. of bitstreams: 1 000426257-Texto+Completo-0.pdf: 1755625 bytes, checksum: 752156f9068dd50cc9bde67b5e57153f (MD5) Previous issue date: 2010 / Delay Tolerant Network (DTN) are networks in which frequent interruptions, high delay, and high error rates may occur. In these networks the nodes are mobile and play the role of routers, storing and transferring messages that need to be delivered. This thesis consider the stochastic DTN, where the topological changes are not known in advance and techniques are proposed that try to increase the probability of success in the routing, using, for instance, historical knowledge of network behavior in the routing decision. DTN has some similarities to ad hoc networks, but due to frequent disruptions that occur in DTN, the routing problem is handled differently. In sparse scenarios, due to lack of connectivity of nodes, DTN has higher percentage of delivered messages, at the price of higher delays. A study comparing these two kinds of networks is carried out by this thesis, providing quantitative information about this aspect. This work proposes three variations of a routing protocol for stochastic DTN based on a metric called “delivery potential”, which is used while deciding how messages are forwarded. The delivery potential is a historical measure that indicates the number of meetings in which the nodes are involved in a period of time. In order to increase the probability to find the destination, the strategy gives priority to routing nodes that have a high number of meetings. The initial protocol is called ARPR (Adaptive Potential Routing Protocol) and, in comparison with other protocols for the same type of network, presents a percentage of delivered messages equivalent to these protocols, with a very low overhead, especially for sparse networks (important in DTN).An APRP variation uses an acknowledgement mechanism for messages already delivered in order to release space in buffer for new messages. This variation is called APRP-Ack and has better performance than ARPR, despite causing an increase in the average delay in the delivery of messages. Finally, the APRP-Group is proposed, in order to reduce the delay generated by APRP-Ack. The APRP-Group seeks to identify groups of nodes with similar delivery potential and decide on the forwarding of messages based on these groups. This protocol provides a significant reduction in the delivery delay, compared to APRP and APRP-Ack, maintaining low costs of communication and maintaining or improving levels of delivery. The above mentioned proposed protocols where evaluated using a DTN specific simulation environment specific and compared to analogous protocols from the literature, specially with the Spray and Wait due to its high performance reported in the literature. / Redes Tolerantes a Atrasos (Delay Tolerant Network - DTN) são redes sujeitas a interrupções frequentes, altos atrasos e elevadas taxas de erro. Nessas redes os nodos são móveis e fazem o papel de roteadores, armazenando e fazendo o repasse das mensagens que precisam ser entregues. O foco deste trabalho está nas redes DTN estocásticas, nas quais as mudanças topológicas não são conhecidas e surgem técnicas para tentar aumentar a probabilidade de sucesso no roteamento, utilizando conhecimento histórico do comportamento da rede na tomada da decisão. As redes DTN possuem algumas semelhanças com as redes ad hoc, mas devido às constantes disrupções que ocorrem nas redes DTN, o problema do roteamento é tratado de forma diferente. Em cenários esparsos, devido à falta de conectividade dos nodos, as redes DTN apresentam maior percentual de mensagens entregues, a custo de maiores atrasos. Um estudo comparando esses dois tipos de redes é realizado por este trabalho, comprovando esse aspecto. Este trabalho propõe três variações de um protocolo de roteamento para redes DTN estocásticas que utiliza uma métrica chamada de “potencial de entrega” usada na decisão do repasse das mensagens. O potencial de entrega é uma medida histórica que indica o número de encontros em que os nodos estão envolvidos em um período de tempo. No intuito de aumentar a probabilidade de encontrar o destinatário, a estratégia prioriza o roteamento a nodos que tenham um número alto de encontros. O protocolo inicial é chamado de APRP (Adaptive Potential Routing Protocol ) e, em comparação com outros protocolos para o mesmo tipo de rede, apresenta um percentual de mensagens entregues equivalente a esses protocolos, com um overhead bastante reduzido, especialmente para redes esparsas (importantes em DTN).Uma variação do APRP utiliza um mecanismo de confirmação de mensagens já entregues com o intuito de liberar espaço em buffer para mensagens novas. Tal variação é chamada de APRP-Ack e apresenta desempenho superior ao APRP, ao custo de um aumento no atraso médio na entrega das mensagens. Por fim, é proposto o APRP-Group, com o objetivo de reduzir o atraso gerado pelo APRP e APRP-Ack. O APRP-Group busca identificar grupos de nodos com potenciais de entrega similares e decidir sobre o repasse das mensagens com base em tais grupos. Este protocolo apresenta uma redução significativa no atraso de entrega, se comparado ao APRP e APRP-Ack, mantendo baixos os custos de comunicação e mantendo ou melhorando níveis de entrega. Os diferentes protocolos foram simulados em um ambiente específico para DTN e comparados com protocolos da literatura, especialmente com o Spray and Wait devido ao seu alto desempenho reportado na literatura.

Made available in DSpace on 2013-08-07T18:43:38Z (GMT). No. of bitstreams: 1 000425006-Texto+Completo-0.pdf: 2030732 bytes, checksum: af723abcff811e622f9a8f3c907145a0 (MD5) Previous issue date: 2009 / The performance evaluation of routing protocols for Ad hoc networks is usually made through simulation techniques and tools. The use of Stochastic Automata Networks is a new alternative to evaluate such protocols, since this formalism can handle very large spaces of states, which it was one of the major problems of other analytical formalisms. The routing protocols for Ad hoc networks are a key factor in the success of the data transmissions task between the nodes, so the DSR - Dynamic Source Routing, protocol was evaluated at this work. DSR protocol main characteristics are the techniques of discovery and maintenance of routes, in order to assure the smaller - or better - route inside a network. The first contribution of this work is the straight evaluation of route discovery process, as well as the possibility of transmission failures and the need of route maintenance. These results are directly connected with the workload of the network, which is directly related to route utilization results. The second contribution is the analysis of networks with a DSR protocol with promiscuous listening in order to evaluate if the use of such characteristic helps the networks behavior. Are also presented evaluation results of metrics like throughput with different packets sizes and nodes pause time during the transmission inside a network that uses the DSR protocol to information routing. Additionally, this work demonstrate the efficiency of the Stochastic Automata Networks formalism to obtain these metrics as an alternative to evaluate this type of environment while similar results were obtained in literature. / A avaliação de desempenho dos protocolos de roteamento de redes Ad hoc é realizada, em sua maioria, através do uso de técnicas e ferramentas de simulação. Através do uso das Redes de Autômatos Estocásticos, surge uma nova alternativa para realizar esta avaliação, já que este formalismo provê grande quantidade de espaços de estados, que era um dos grandes problemas de outros formalismos analíticos. Os protocolos de roteamento para redes sem fio Ad hoc são um fator determinante no sucesso da tarefa de transmissão de dados entre os nodos. Sendo assim, foi avaliado neste trabalho o protocolo DSR - Dynamic Source Routing, que tem como características principais as técnicas de descoberta e manutenção de rota, a fim de garantir a menor - ou melhor - rota dentro de uma rede. A primeira contribuição presente neste trabalho trata diretamente da avaliação deste processo de descoberta de rota, bem como da possibilidade de falhas de transmissão ocorrerem e o processo de manutenção de rota se fazer necessário. Estes resultados estão diretamente ligados aos resultados obtidos avaliando-se o workload dos nodos da rede, que reflete diretamente na utilização das rotas.A segunda contribuição é a análise do comportamento de redes quando estas utilizam uma particularidade do protocolo DSR que é a escuta promíscua (promiscuous listening). Busca-se avaliar se o uso de tal característica auxilia no funcionamento da rede. São apresentados também resultados de avaliação de métricas como vazão com diferentes tamanhos de pacotes e tempos de pausa dos nodos durante a transmissão dentro de uma rede que utiliza o protocolo DSR para o roteamento das informações. Adicionalmente busca-se demonstrar a eficiência das Redes de Autômatos Estocásticos na obtenção destas métricas e assim apresentar este formalismo como uma alternativa para avaliação deste tipo de ambiente, dada a similaridade dos resultados obtidos, se comparados àqueles apresentados na literatura.