UNIVERSIDADE DO VALE DO RIO DOS SINOS — UNISINOSUNIDADE ACADÊMICA DE GRADUAÇÃOCURSO DE CIÊNCIA DA COMPUTAÇÃO

NÍVEL BACHAREL

IURI ANDREAZZA

REDES MESH COGNITIVAS: MANTENDO A QUALIDADE DA TRANSMISSÃOUTILIZANDO ANÁLISE E PREDIÇÃO DE TRÁFEGO COM

REDES NEURAIS ARTIFICIAIS

SÃO LEOPOLDO2012

Iuri Andreazza

REDES MESH COGNITIVAS: MANTENDO A QUALIDADE DA TRANSMISSÃOUTILIZANDO ANÁLISE E PREDIÇÃO DE TRÁFEGO COM

REDES NEURAIS ARTIFICIAIS

Trabalho de conclusão de curso apresentadocomo requisito parcial para a obtenção dotítulo de Bacharel em Ciência da Computação,pelo curso de Ciência da Computação pelaUniversidade do Vale do Rio dos Sinos —UNISINOS

Orientador:Prof. MSc. Mateus Raeder

São Leopoldo2012

Para aqueles que eu amo muito.

The whole of science is nothing more than arefinement of everyday thinking. — ALBERT EINSTEIN

AGRADECIMENTOS

Para todos aqueles que partilharam comigo esta jornada, mesmo que este contato tenha sidobreve ou que tenha se estendido um pouco mais, alguns ficaram e perseveraram nessa luta queé o processo de formação acadêmica. A essas pessoas sou agradecido por fazerem parte naconstrução do acadêmico que sou hoje.

À minha família por todo seu apoio em todos os momentos, sempre incondicional, mesmoescutando bravejos de um estudante estressado sempre estiveram ao meu lado me apoiando eajudando a sobrepujar os obstáculos impostos.

Para meus eternos fiéis amigos, Felipe e Dante, sempre que estivemos juntos instauramosa loucura nas cadeiras com planos faraônicos para os trabalhos ou mesmo as loucas conversasde bar à frente da UNISINOS. Sempre pensando e inventando um dia iremos ainda fazer umtrabalho formal sobre infestação zumbi não?

Devo mencionar também meus grandes amigos Paulo, Wanderson, Roberto e Bryan que,apesar de não sermos colegas de longa data, partilhamos muitas risadas sobre o universo nerdem que vivemos, até mesmo trocando idéias sobre projetos ou ajudando uns aos outros no quefosse necessário!

À minha mãe e pai em especial por todo o apoio dado e pela longas jornadas de pesquisae desenvolvimento intenso e das horas de sono perdidas, no qual ambos ficaram e me acompa-nharam durante o desenvolvimento deste trabalho.

Devo mencionar também ao meu orientador, Mateus Raeder, por suas longas horas de cor-reções e puxões de orelha com o objetivo de manter meu trabalho minucioso, sempre buscandopotencializar minhas qualidades e extrair o melhor no desenvolvimento deste.

Sem mais delongas, agradeço à minha namorada Cecília por estar presente ao meu ladonessa jornada final, por ser prestativa, companheira e compreensiva, sempre disposta a me aju-dar no que fosse possível.

Para todos vocês um muito obrigado!

RESUMO

A necessidade de maior conectividade exige cada vez mais da infraestrutura dos mode-los de redes atuais. Considerando o ritmo de crescimento dos dispositivos requisitando dadosconstantemente da rede, esses modelos logo se tornarão obsoletos, pois não conseguirão proverconstante acesso à rede sem que o usuário precise configurar seus dispositivos cada vez quequiser acessar a web. O modelo da Rede Mesh surge com o intuito de solucionar essa necessi-dade de constante conectividade, porém traz diversos problemas, tal como conseguir manter aqualidade dos serviços provendo links com velocidade e desempenho desejáveis. Este trabalhopropõe uma nova abordagem em relação ao roteamento no modelo da Rede Mesh, tentando aliara flexibilidade das Redes Neurais Artificiais, objetivando manter o desempenho da rede dianteda constante mudança de topologia.

Palavras-chave: Redes Neurais Artificiais. Redes Mesh. Protocolo de Roteamento.

ABSTRACT

The need for greater connectivity requires more of the infrastructure of existing networkmodels. Considering the growth rate of the devices on the network requesting data constantly,these models will soon become obsolete because it will not be able to provide constant accessto the network without requiring the user to configure their device each time you access theWeb. The model comes with the mesh in order to address this need for constant connectivity,but has several problems, as can maintain the quality of services providing links with speed andperformance desired. This paper proposes a new approach to routing in the mesh model, tryingto combine the flexibility of neural networks aiming to maintain network performance in theface of changing topology.

Keywords: Neural Networks. Mesh Networks. Routing Protocol.

LISTA DE FIGURAS

Figura 1: Representação de uma célula neural humana (HAYKIN, 2001). . . . . . . . 27Figura 2: Visão clássica da estrutura de uma Rede Neural Artificial (BRAGA; CAR-

VALHO; LUDEMIR, 2007). . . . . . . . . . . . . . . . . . . . . . . . . . 28Figura 3: Estrutura clássica da organização de uma rede de Hopfield (LOESCH; SARI,

1996). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29Figura 4: Estrutura geral de uma Rede Mesh. . . . . . . . . . . . . . . . . . . . . . . 31Figura 5: Visão da conectividade geral entre client nodes e Mesh Routers. Em verde,

a comunicação entre mesh routers e, em amarelo, a ligação entre client nodes. 32Figura 6: Gráficos apresentando resultados de entrega de pacotes dentro de uma Rede

Mesh (BAUMANN et al., 2007). . . . . . . . . . . . . . . . . . . . . . . . 34Figura 7: Organização da estrutura do NS-3. . . . . . . . . . . . . . . . . . . . . . . 35

Figura 8: Representação da topologia da Rede Mesh mostrando o caminho ótimo dospacotes entre dois mesh clients. . . . . . . . . . . . . . . . . . . . . . . . . 43

Figura 9: Estrutura do Frame de transmissão do protocolo HWMP-ANN. . . . . . . . 44Figura 10: Representação Parcial da topologia da rede. . . . . . . . . . . . . . . . . . . 45Figura 11: Estrutura da RNA utilizada no processo de decisão do roteamento de pacotes. 46

Figura 12: Média fracionária de entrega de pacotes. . . . . . . . . . . . . . . . . . . . 50Figura 13: Comparativo entre alguns algoritmos de roteamento e o HWMP-AN. . . . . 51Figura 14: Gráficos mostrando o comparativo de 25 simulações proeminentes. . . . . . 51Figura 15: Total de Pacotes Perdido durante a simulação. . . . . . . . . . . . . . . . . 52Figura 16: Comparativo entre Total de pacotes entregues sem e com a utilização das

RNAs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52Figura 17: Atraso médio na entrega de pacotes. . . . . . . . . . . . . . . . . . . . . . . 53Figura 18: Comparativo de 12 simulações mostrando o atraso médio utilizando a avali-

ação pela RNA. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53Figura 19: Dispersão da média de atrasos de todas as simulações utilizando a RNA. . . 54Figura 20: Gráficos representando o estado (métricas PDF e Pacotes Perdidos) da rede

comprando 25 fluxos de informação, com RNAs e Sem RNAs. . . . . . . . 54Figura 21: Métricas gerais comprando 12 rodadas de simulações. . . . . . . . . . . . . 55Figura 22: Dispersão da média fracionária em todas as simulações. . . . . . . . . . . . 56Figura 23: Gráficos representando o desempenho geral da simulação da rede. . . . . . . 57

LISTA DE TABELAS

Tabela 1: Cenários gerados para simular a rede em diversas condições. . . . . . . . . 42Tabela 2: Modelos de RNA pesquisados e seus requisitos para uso no roteamento de

pacotes na rede. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46Tabela 3: Amostra da Base de dados construída para treinar a RNA sobre os estados

dos mesh clients. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

Tabela 4: Objetivos alcançados nesta pesquisa. . . . . . . . . . . . . . . . . . . . . . 66

LISTA DE ABREVIATURAS

RNA Redes Neurais Artificiais

APs Access Points

AODV Ad hoc On-Demand Distance Vector

AODV-CGAAd Hoc On Demand Distance Vector Reactive By Hop Routing

AODV-HP Ad Hoc On Demand Distance Vector High Performance

FBR Field Based Routing

FBR-GW Field Based Routing Enhancement for Scalability

GSR Gateway Source Routing

GSR-PN Gateway Source Routing Preferred Neighbor

HWMP Hybrid Wireless Mesh Protocol

P2P Peer To Peer

PLM Peer Link Management

NS-3 Network Simulator 3

API Application Programming Interface

IP Internet Protocol

PDF Packet Delivery Fraction

HWMP-AN Hybrid Wireless Mesh Protocol with Artifical Networks

QoS Quality of Service

MRATP Multipah Routing Algorithm based on Traffic Prediction

STE stochastic traffic engineering

ETX Expected Transmission Count

mETX Modified ETX

ENT Effective Number of Transmissions

SMA Simple Moving Avarege

EWMA Exponetially Weighted Moving Avarege

COMNET Cognite Wireless Mesh Networks

WLAN Wireless Area Network

RRS Redes Recorrentes Simples

RRDD Redes Recorrentes Dinâmicamente Dirigidas

LISTA DE SIGLAS

txPackets Total de Pacotes Transmitidos

rxPackets Pacotes Transmitidos com sucesso

lostPackets Numero de Pacotes perdidos

rxBitrate bits transmitidos com sucesso

txBitrate total de bits transmitidos

tx Pacotes Transmitidos com sucesso

rx bits transmitidos com sucesso

pcap Package Capture (Captura de Pacotes)

LISTA DE SÍMBOLOS

s Segundos

m Minutos

Σ Somatório

α Alpha

exp Exponencial

Tn Taxa de Pacotes em um ponto do tempo

Rn Taxa de Bits em um ponto do Tempo

Spdf Estado do PDF de um node em um ponto do tempo

SdelayEstado do Atraso de um node em um ponto do tempo

SUMÁRIO

1 INTRODUÇÃO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231.1 Motivação e Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241.2 Estrutura do Texto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

2 FUNDAMENTAÇÃO TEÓRICA . . . . . . . . . . . . . . . . . . . . . . . . . . . 272.1 Redes Neurais Artificiais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272.1.1 Modelos de RNAs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282.1.2 Uso temporal no reconhecimento de padrões . . . . . . . . . . . . . . . . . 302.2 Redes Mesh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302.2.1 Estrutura da rede . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322.2.2 Mecanismos de Roteamento . . . . . . . . . . . . . . . . . . . . . . . . . . . 332.3 Simulador NS-3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

3 MÉTODO DE PESQUISA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 373.1 Delineamento da pesquisa . . . . . . . . . . . . . . . . . . . . . . . . . . . . 373.2 Definição do conjunto da unidade análise e da população alvo . . . . . 383.3 Técnica de coleta de dados . . . . . . . . . . . . . . . . . . . . . . . . . . . 383.4 Técnica de análise de dados . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

4 SIMULAÇÕES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 414.1 Cenários de Execução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 414.2 RNA Aplicada ao Roteamento . . . . . . . . . . . . . . . . . . . . . . . . . . 44

5 AVALIAÇÃO DOS RESULTADOS . . . . . . . . . . . . . . . . . . . . . . . . . 495.1 Métricas da simulação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 495.2 Resultados obtidos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

6 TRABALHOS RELACIONADOS . . . . . . . . . . . . . . . . . . . . . . . . . . 596.1 A Multipah Routing Algorithm Based on Traffic Prediction in Wireless

Mesh Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 596.2 Neural network based optimal routing algorithm for communication

networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 596.3 Stochastic Traffic Engineering in Multihop Cognitive Wireless Mesh

Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 606.4 High Performance AODV Routing Protocol for Hybrid Wireless Mesh

Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 606.5 A high-throughput path metric for multi-hop wireless routing . . . . . . 616.6 Quality-Aware Routing Metric for Time-Varying Wireless Mesh Networks 616.7 Bio-inspired Link Quality Estimation for Wireless Mesh Networks . . . . 616.8 Cognitive Wireless Mesh Networks with Dynamic Spectrum Access . . 626.9 Relação com os trabalhos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

7 CONSIDERAÇÕES FINAIS E TRABALHOS FUTUROS . . . . . . . . . . . . 65

REFERÊNCIAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

APÊNDICE A INFORMAÇÕES COMPLEMENTARES . . . . . . . . . . . . . . 71A.1 NS-3 Módulos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71A.1.1 HWMP Mac Header . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71A.1.2 HWMP Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71A.1.3 HWMP Rtable . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72A.1.4 HwmpRtable::updateNodeStats . . . . . . . . . . . . . . . . . . . . . . . . . 72

ANEXO A NS-3 SCRIPTS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73A.1 Cenário Base das Simulações . . . . . . . . . . . . . . . . . . . . . . . . . . 73

23

1 INTRODUÇÃO

Nas últimas décadas, a evolução tecnológica, tanto na área da informação quanto da comu-nicação, popularizou a computação móvel e, consequentemente, as redes de computadores semfio. O uso dessas tecnologias está cada vez mais presente nos ambientes acadêmicos, industriaise residenciais.

A grande quantidade de dispositivos móveis como notebooks, celulares e tables demandamconectividade instantânea com a rede, exigindo infraestrutura para acesso à Internet e forçandoas redes em fio ao limite. Concomitantemente, a migração de serviços para a web e o desenvol-vimento de novas ferramentas onlines requerem qualidade e eficiência da conexão à Internet.

A maioria das redes sem fio operam de modo centralizado, ou seja, sua estrutura prevê quesomente um único ponto de acesso é responsável pela administração e conexão de todos osclientes. Sua principal desvantagem, obviamente, é a dependência da estrutura em relação aesse ponto de acesso. Se ele falhar, toda a rede ficará indisponível.

Na tentativa de solucionar esse problema, o padrão de malha (do inglês mesh) propõe umaabordagem diferenciada para a conexão entre os usuários de uma rede. Nesse padrão, os clien-tes e roteadores se comunicam uns com os outros, utilizando múltiplos saltos para encaminharmensagens ao destino apropriado. Além disso, as Redes Mesh possuem capacidades de au-torreparação, autoconfiguração e auto-organização, permitindo que a rede - com a Internet eentre oustros usuários - continue a funcionar, mesmo que um dos pontos de acesso pare defuncionar (AKYILDIZ; WANG, 2005).

Entretanto, as redes mesh atuais, dada a volatilidade dos clientes - ora presentes na rede,ora ausentes -, não priorizam a qualidade de serviço, ou seja, a transmissão de dados dentroda malha é lenta e, geralmente, ocorrem excessivas retransmissões de dados. Esses fatoresdificultam a manutenção de um fluxo de dados para clientes dentro da malha.

Os padrões de redes contemporâneos suportam uma grande quantidade de usuários e garan-tem a manutenção da qualidade, porém não previram a inclusão de novos tipos de clientes, comodispositivos gerais do cotidiano (impressoras, celulares, geladeiras e demais eletrodomésticos,centrais de informação, carros e casas). A presença maciça de mecanismos computacionaisexaure a capacidade das redes, pois todo o ambiente estará interconectado, gerando um cons-tante e intenso fluxo de dados (AKYILDIZ; WANG, 2005)(ZHU; MUTKA; NI, 2004)

Diante disso, o modelo de redes mesh se mostra cada vez mais atrativo para a implantaçãoem larga escala, pois possibilita a coexistência de todos esses dispositivos e a geração de um"ecossistema"computacional natural. Dada as capacidades de autoconfiguração e autorrepara-ção do modelo mesh, os usuários não precisam nem configurar manualmente seus dispositivose nem se preocupar com a rede caso algum dos dispositivos pare de funcionar.

Porém, nesse ecossistema, um problema se torna evidente. O fluxo de dados entre os dispo-sitivos e com a Internet é um fator determinante na avaliação qualitativa (por parte do usuário)e quantitativa (métricas avaliadas pelos mecanismos da rede) da rede. Para qualquer dispositivo

24

que realizar a requisição de um stream de informação, a rede terá que ser capaz de manter ofluxo, sempre selecionando o melhor caminho, ou seja, o menos sobrecarregado e com menorcusto (BARANSEL; DOBOSIEWICZ; GBURZYNSKI, 1995).

Considerando essa problemática, o desenvolvimento de tecnologias que possibilitem ao mo-delo mesh ter a flexibilidade necessária para suportar aplicações em larga escala deve ser pros-pectado e avaliado, assim como estudos de como manter a eficiência nas Redes Mesh se fazemnecessários.

A eficiência das redes está intrinsecamente ligada à capacidade da rede manter o fluxo dedados. Não transmitir dados de maneira eficaz é um fator determinante para a perda da qua-lidade dos serviços da rede. Assim, o roteamento de pacotes tem papel decisivo, devendo serflexível o suficiente para suportar as constantes mudanças topológicas.

As Redes Neurais Artificiais (RNAs) podem auxiliar no roteamento de pacotes, pois são ca-pazes de calcular as métricas dos clientes das redes de forma eficiente e com baixo custo de pro-cessamento. Esses cálculos acabam por influenciar de forma positiva o roteamento, deixando-omais empírico e capaz de se ajustar a cenários de grande mudança. Além disso, a rede torna-se maleável e a previsão de eventos que podem causar mudanças adquire proatividade. Todosesses fatores acabam por influenciar diretamente a qualidade de serviço das redes.

A ideia principal do roteamento cognitivo em Redes Mesh é prover flexibilidade aos dispo-sitivos presentes no ecossistema, de modo a utilizar eficientemente os recursos disponíveis dasredes e manter a qualidade de conexão a um nível aceitável. Conforme mencionado anterior-mente, a utilização de Redes Neurais Artificiais dentro do roteamento de pacotes é importanteno ganho de desempenho da rede, pois acabando proporcionando agilidade na distribuição dainformação através da topologia. O emprego de engenharia de tráfego no fluxo de informaçãoda rede é de extrema importância, uma vez que a estocasticidade topológica da rede impõegrandes desafios à qualidade da conexão dos dispositivos à rede.

1.1 Motivação e Objetivos

Com o foco desta pesquisa na manutenção da eficiência da rede, a predição de tráfego torna-se uma alternativa atraente para ajustar os mecanismos de roteamento, uma vez que o fluxo deinformações tende a sofrer com a estocasticidade da topologia. Nesse cenário, este trabalhopropõe um ajuste do mecanismo de roteamento que vise manter a conectividade e maximize aqualidade da transmissão, conseguindo se ajustar à constante mudança das redes.

Essa problemática influencia toda a gestão do tráfego, criando a necessidade de um proto-colo capaz de influenciar todo o gerenciamento da transmissçã de dados dentro da rede e, aomesmo tempo, robusto e flexível, ajustando-se aos diversos cenários que os dispositivos compu-tacionais possam residir. Com essa capacidade cognitiva, o protocolo possivelmente irá manterestável a transmissão com qualidade nominal, aumentando a conectividade da rede. Uma abor-dagem a se adotar seria unificar os trabalhos que usam Redes Neurais Artificiais e propor um

25

algoritmo de roteamento robusto, colocando como premissa de que este tenha a flexibilidadesuficiente para manter a conectividade com o máximo de qualidade possível. Considerandoisso, o desenvolvimento das RNAs precisará de um conjunto de métricas de decisão, que serãotreinadas com o objetivo de serem o mecanismo principal na decisão do roteamento de paco-tes. Sendo assim, será possível prever mudanças dentro da rede e, a priori, conseguir evitarcongestionamentos ou outras situações caóticas.

Mantendo a visão do problema sob a gerência de tráfego, a manutenção da qualidade selocaliza na predição do tráfego interno da rede. Essa predição habilita o protocolo de roteamentoa ser flexível perante cenários de caos, portanto este trabalho buscou como objetivo habilitarcognitivamente o mecanismo de roteamento. Nesse cenário, este trabalho objetiva proporum novo mecanismo de roteamento para redes mesh que vise manter a conectividade emaximize a qualidade da transmissão, conseguindo se ajustar à constante mudança datopologia da rede.

O protocolo cognitivo foi desenvolvido para ser utilizado dentro de um ambiente simuladode redes de computadores. Esse ambiente disponibiliza um conjunto de ferramentas para análiseda rede como um todo, possibilitando a construção de uma visão analítica do roteamento dasredes e a execução de uma análise da efetividade do protocolo.

As principais contribuições deste trabalho são listadas abaixo:

• Flexibilizar o protocolo de roteamento;

• Aumentar a qualidade da rede em cenários de caos;

• Melhorar a qualidade da conexão para dispositivos com alta mobilidade;

• Demonstrar o uso efetivo de Redes Neurais Artificiais juntamente com Redes Mesh.

1.2 Estrutura do Texto

O trabalho está organizado em sete capítulos. O Capítulo 2 apresenta a fundamentação doproblema e os pontos críticos para as Redes Mesh. O Capítulo 3 demonstra o método de pes-quisa e a definição dos métodos de análise dos dados extraídos das simulações. O Capítulo 4introduz o ambiente de simulação. O Capítulo 5 expõe os resultados obtidos com as modifica-ções do protocolo de roteamento. O Capítulo 6 explana os trabalhos relacionados com o objetode pesquisa deste trabalho. Por fim, o Capítulo 7 descreve as considerações finais deste trabalhoe quais caminhos podem ser seguidos a partir desta pesquisa.

26

27

2 FUNDAMENTAÇÃO TEÓRICA

Neste capítulo serão abordados os temas relacionados à proposta do roteamento, visandoconceituar e descrever os conteúdos básicos para uma melhor compreensão do problema apre-sentado, como brevemente o simulador utilizado para gerar a rede.

2.1 Redes Neurais Artificiais

Redes Neurais Artificiais, usualmente denominadas "Redes Neurais"ou RNAs, vêm sendodesenvolvidas por causa de um grande motivador, o cérebro humano. Nele, o processamentoda informação ocorre de forma totalmente diferente de um computador digital. A capacidadehumana de processar dados é não-linear e com um grande diferencial, todo o processo é para-lelo. Assim, a mente humana é capaz de processar e classificar dados de forma cognitiva comextrema eficiência, mas, para que isso seja possível, o cérebro se organiza e se conecta comouma grande rede através dos neurônios (Figura 1).

Figura 1: Representação de uma célula neural humana (HAYKIN, 2001).

À semelhança da mente humana, a RNA é capaz de organizar a informação e classificá-la através de suas experiências. Tanto que, para as RNAs, é necessário um treinamento comum conjunto base de cenários e seus respectivos resultados. Essa aprendizagem é chamada detreinamento supervisionado e tem como objetivo preparar as estruturas internas (Pesos) da RNApara responderem com valores esperados sempre que encontrarem um padrão conhecido.

RNAs são construídas como sistemas paralelos distribuídos compostos por pequenas e sim-ples unidades de processamento (neurônios artificiais), as quais calculam determinadas funçõesmatemáticas (normalmente não-lineares). Essas unidades são organizadas em camadas e in-terligadas por um grande número de conexões, na maioria das vezes unidirecionais (Figura 2).Entretanto, existem outros modelos que utilizam conexões de retorno (backpropagation) (HAY-KIN, 2001).

Dentro da RNA, as conexões estão associadas a pesos, onde é armazenado o conhecimento

28

Figura 2: Visão clássica da estrutura de uma Rede Neural Artificial (BRAGA; CARVALHO; LUDE-MIR, 2007).

adquirido pela rede, servindo para ponderar sobre a entrada recebida por cada neurônio. A so-lução de problemas por meio de RNAs é bastante atrativa, pois, devido à forma com que suasestruturas internas são representadas e ao paralelismo natural inerente à sua arquitetura, gerama possibilidade de um desempenho superior aos métodos tradicionais de decisão (VENKATA-RAM; GHOSAL; KUMAR, 2002).

Nas RNAs, o processamento básico de uma solução de problemas passa por uma fase ini-cial de aprendizagem. Alguns modelos necessitam que o desenvolvedor da rede faça ajustesmanuais, ou seja, apresente cenários de aprendizagem exemplos (treinamento supervisionado).Outros modelos, por sua vez, suportam a aprendizagem dinâmica (convergência), ou seja, auto-mática, sem a interferência humana no seu aprendizado. Com base nesse aprendizado, a RNAé capaz de extrair as características básicas para representar a informação do conhecimentodos problemas apresentados a ela. Mais tarde, essas informações serão utilizadas para gerarrespostas automáticas para problemas do mesmo grupo com dados desconhecidos (BRAGA;CARVALHO; LUDEMIR, 2007).

2.1.1 Modelos de RNAs

Um dos modelos mais conhecido dentro das redes autoassociativas é a rede de Hopfield(ou Hopfield/Tank) (LOESCH; SARI, 1996). Sua arquitetura apresenta uma camada de pro-cessamento singular, com a possibilidade de utilizar sua saída para realimentar a camada deprocessamento, fazendo com que a rede seja capaz de ponderar sobre o resultado obtido de suasaída.

A Figura 3 mostra uma rede de Hopfield recorrente de uma só camada. Eventualmente,pode ser anteposta uma camada de entrada à rede com uma função única de distribuir os pesosde entrada. Também pode ser adicionada uma camada de saída com a função de normalizar osresultados da rede (LOESCH; SARI, 1996).

Dentro da Rede Neural de Hopfield, o neurônio é composto de duas funções matemáticas

29

Figura 3: Estrutura clássica da organização de uma rede de Hopfield (LOESCH; SARI, 1996).

nas quais representam o processo de ativação e ponderação dos pesos da entrada dos neurôniosda rede. A função de ativação imita o funcionamento da célula neural biológica na qual requercertas condições para ativar uma descarga elétrica dentro da célula. Quando a descarga ocorre,ela irá ativar as terminações do axônio e transmitir informação de um neurônio para outro.

Dentro do neurônio, antes de passar pela função de transição, é necessário ponderar os sinaisde entrada (S), definidos pela Equação 2.1. Após, o resultado é passado para a transição. Asfunções serão representadas pelas Equações 2.2, 2.3 e 2.4.

S =n∑

i=1

WiXi (2.1)

Abaixo algumas funções de transição comumente usadas:

• Função de Limiar

ϕ(v) =

{1 se v ≥ 00 se v < 0

(2.2)

• Função linear por partes

ϕ(v) =

1 v ≥ +1

2

v +12

> v > -12

0 v ≤ -12

(2.3)

• Função sigmóide

ϕ(v) =1

1 + exp(−av)(2.4)

As funções acima representam a transição do sinal internamente do neurônio. Sempre quefor necessário trabalhar o desempenho do neurônio ou alterar seu comportamento, ajustes nasfuncões de transição deverão serem feitas.

30

Uma das desvantagens das redes de Hopfield de memória associativa e otimização é o re-torno de informações imprecisas e geralmente com falhas em cenários de grande quantidade deinformação, tornando sua aplicação limitada a casos pequenos ou simples.

2.1.2 Uso temporal no reconhecimento de padrões

O tempo constitui parte essencial no processo de aprendizagem de uma RNA. Ele pode sercontínuo ou discreto, representando uma entidade temporal ordenada. Tal processo, é básicopara execução de muitas tarefas cognitivas, tais como: visão, fala, o processamento de sinaise o controle motor. Através da incorporação do tempo na operação de uma RNA, podemoscapacitá-la a seguir variações estatísticas em processos não estacionários, como flutuações dospadrões de roteamento dos client nodes.

O tempo dentro da RNA é representado em uma das seguintes formas:

• Representação implícita: A representação nesta forma é feita sobre o processamento an-terior. Por exemplo, os sinais de entrada contém uma amostragem uniforme e os pesossinápticos de cada neurônio conectados a camada de entrada da rede sofrem sequen-cialmente uma convolação com amostras de entrada diferenciadas. Assim, a estruturatemporal do sinal de entrada é inserida na estrutura espacial da rede.

• Representação explícita: O tempo neste formato tem sua própria representação, ou seja,neurônios específicos para representar o atraso temporal do sinal de entrada em relaçãoao tempo transcorrido pela RNA.

A forma simples de adicionar a dimensão temporal à memória de uma RNA é acrescentaratrasos de tempo implementados a níveis sinápticos ou a nível das entradas da rede. Essesatrasos operam nas entradas sinápticas e habilitam a rede com uma memória de curto prazotemporal, influenciando diretamente o processamento de informações e utilizando a dimensãotemporal dos dados.

2.2 Redes Mesh

Novos dispositivos computacionais estão cada vez mais presentes no cotidiano das pessoas.Esse aumento significativo de usuários dentro do ambiente das redes sem fio (do inglês wireless)força a estrutura atual aos limites, muitas vezes causando uma perda significativa da qualidadedo serviço oferecido. A evolução tecnológica do modelo de rede sem fio (Wireless) gera outrasabordagens para preencher o vácuo da necessidade na manutenção da qualidade do serviço queas redes dispõem.

Na busca de prover conectividade de qualidade de maneira fácil e ampla, entidades acadêmi-cas e grandes corporações investem na pesquisa e aprimoramento do modelo mesh. O modeloprovê características únicas facilitando a aplicação em larga escala e sua rápida implantação.

31

Figura 4: Estrutura geral de uma Rede Mesh.

A estrutura de uma Rede Mesh, representada na Figura 4, funciona em camadas. Percebe-se a separação da camada dos clientes (em amarelo) da camada dos pontos de acesso (Access

Points ou APs, ilustrados em verde), conectados às torres de transmissão (AKYILDIZ; WANG,2005).

A rede é composta de computadores vistos como nós (nodes) da malha, conectados comnodes vizinhos, formando uma topologia multidimensional chamada de mesh. Os nodes darede podem ser separados em três grandes classes: os clientes (mesh clients), os routers (mesh

routers) e a infraestrutura (backbones), que são as torres de transmissão.

Os mesh routers geralmente formam uma camada única, interconectando outros routers eeventualmente conectando-se diretamente com torres de transmissão de dados e à rede global.Os routers são mais flexíveis e versáteis em comparação aos pontos de acesso normais, poisconseguem atingir esta, senão mais, cobertura com muito menos energia. Isso ocorre pois aestrutura da rede é baseada em conexões ponto a ponto, permitindo que ocorram múltiplossaltos durante a comunicação (SONG; ZHANG; FANG, 2010).

Os mesh clients contêm o aparato necessário para se comportarem tanto como um client

quanto um router. Entretanto, deve ser visto que as funções de ponte (bridge) e gateway nãose encontram presentes (AKYILDIZ; WANG, 2005). Apesar dessa pequena desvantagem, osclients podem manter a conectividade com seus vizinhos (ad-hoc) e possuir um hardware maissimples. Consequentemente, o software para eles tendem ser mais simples.

Como aspectos positivos da rede, a conectividade promove a auto-organização, a autoconfi-guração e a autorreparação entre mesh clients e routers. A auto-organização e autoconfiguração

32

permitem que, conforme os nodes vão se conectando, formem-se aglomerados de dispositivosgerando uma rede automática. A autoreparação ocorre quando, caso um client ou um router pa-rar de funcionar, a rede não desaparece, continuando a existir através de um caminho alternativopara o roteamento de pacotes (AKYILDIZ; WANG, 2005).

Outra vantagem das Redes Mesh é a construção de uma infraestrutura de acesso fácil, per-mitindo que clientes que possuam uma placa de rede sem fio conectem-se tanto a um client

como a um router. Também é possível ter um ambiente híbrido, no qual uma Ethernet estejaligada a um router que faça parte do ecossistema de nodes da rede.

2.2.1 Estrutura da rede

A organização das Redes Mesh é automática, ou seja, cada novo membro que se junta aoecossistema faz com que os outros membros existentes ou reconheçam como vizinho (ou umclient node distante presente no caminho de um pacote) (AKYILDIZ; WANG, 2005).

Figura 5: Visão da conectividade geral entre client nodes e Mesh Routers. Em verde, a comunicaçãoentre mesh routers e, em amarelo, a ligação entre client nodes.

A organização da estrutura de ligação vista na Figura 5 é automática, ou seja, os mesh rou-

ters têm alcance maior e estabelecem comunicação entre si. Dentro da infraestrutura, eles sãodistintos e geralmente não tem restrições de energia e outras limitações que os clients geral-mente impõem.

Nesse formato, os mesh routers formam uma ligação entre si e priorizam a retransmissão dospacotes entre seus links, porém os client nodes também podem retransmitir em um raio menor,mas essa retransmissão geralmente tende a ser comprometida e mais lenta do que a dos routers.Não são uma constante dentro da rede, já que existem muitos computadores estacionários quepodem funcionar como mesh router.

33

A auto-organização permite que a rede sempre exista e que haja conexão ativa entre osmesh clients. Caso haja a disponibilidade de uma ligação à rede global, essa mesma ligaçãoserá compartilhada entre todos os seus vizinhos próximos. Isso pode ser extendido tambéma todo um segmento da rede, possibilitando assim que os mesmos tenham acesso à Internet.Outro detalhe deste aspecto da rede é a capacidade de incorporar automaticamente novos mesh

clients conforme surge a necessidade, assim também como mover os mesmos dentro da infra-estrutura, sempre re-estabelecendo as ligações entre os vizinhos e reposicionando o node que semoveu (AKYILDIZ; WANG, 2005).

Caso um ponto da rede fique indisponível, isolando clients ou routers, a infraestrutura con-seguirá restabelecer um link com outra parte da malha, reabilitando a ligação primária e per-mitindo que o fluxo de dados volte a fluir dentro do ecossistema que foi desconectado tempo-rariamente, essa capacidade é chamada de autorreparação (AKYILDIZ; WANG, 2005). Casohaja falhas de conectividade, os mesh clients podem experienciar perda de acesso a serviçosou baixa na qualidade da conexão, porém este aspecto permite que a rede sempre busque viasalternativas e mantenha de alguma forma a ligação ao ecossistema principal.

2.2.2 Mecanismos de Roteamento

A capacidade de auto-organização e de autorreparação são as principais características domodelo mesh, permitindo que a rede seja flexível e quase à prova de falhas, porém geram umproblema no processo de decisão na retransmissão e roteamento de pacotes. Representando oquão estocástica é a topologia da rede, com essa constante mudança topológica (entrada e saídade client nodes e possíveis falhas dos mesh routers), a estrutura da rede não comporta algorit-mos que convergem a estados estáticos e, depois desta convergência, não são mais capazes desuportar grandes mudanças.

Conforme descrito em Baumann et al. (2007) Zhi-yuan, Ru-chuan e Jun-lei (2009) Song,Zhang e Fang (2010), os algoritmos triviais não são capazes de se ajustarem a tempo de com-portar as alterações da rede. O algoritmo tradicional AODV (Ad Hoc On Demand Distance

Vector) (GRANVILLE; CARISSIMI; ROCHOL, 2009) não é capaz de prover um roteamentode qualidade para o modelo, por esse motivo, os autores do trabalho Baumann et al. (2007)demonstram uma versão do AODV-CGA (Ad Hoc On Demand Distance Vector Reactive By

Hop Routing) como alternativa e comparam com outros protocolos propostos por eles, como oFBR (Field Beacon Routing).

O FBR propõe uma alternativa pró-ativa ao roteamento, fazendo com que os client nodes

busquem o que está ao seu redor e consigam usar o ecossistema a seu favor no roteamento dospacotes.

Após análise dos gráficos (Figuras 6(a), 6(b) e 6(c)) apresentados por Baumann et al. (2007),é possível notar que, quanto maior a mobilidade dos client nodes, maior é a quebra na entregade pacotes. Com isso, é possível notar que o throughput cai e a entrega de pacotes fica compro-

34

(a) Média de entrega de pacotes em um cenáriocontendo pedestres conectados ao ecossistema.

(b) Média de entrega de pacotes em um cenáriocontendo carros conectados ao ecossistema.

(c) Média de entrega de pacotes em um cenáriocontendo carros conectados ao ecossistema.

Figura 6: Gráficos apresentando resultados de entrega de pacotes dentro de uma Rede Mesh (BAU-MANN et al., 2007).

metida. O usuário final do ecossistema deve notar uma queda significativa do desempenho darede.

Com base na Figura 6(c), é possível ver que, em cenários onde os client nodes presentes noecossistema são estáticos, o roteamento de pacotes tende a funcionar corretamente mesmo comos protocolos clássicos. Porém, nota-se que, em cenários onde existem client nodes móveis ecom comportamentos aleatórios, a entrega de pacotes tende a ser efetivamente menor.

Para este trabalho, foi escolhido como protocolo de roteamento o HWMP (do inglês Hybrid

Wireless Mesh Protocol) (AKYILDIZ; XUDONG, 2009). O HWMP foi construído sobre oAODV e ajustado para suportar o roteamento em árvore. O protocolo trabalha tanto com oroteamento de pacotes, quanto com a seleção de caminhos dentro da rede. Sua proatividade édestacada por descobrir e manter registros dos mesh clients que estão ao seu alcance, utilizandoo gerenciamento de indivíduos por ligação (do inglês Peer Link Management).

Este protocolo é caracterizado híbrido pelo fato de, caso o mesh client estiver conectado auma rede estática, então, para os computadores desta, ele não precisará utilizar a seleção de ca-minhos na transmissão de pacotes. Porém, se estiver presente em uma rede cuja a infraestruturafunciona como árvores, ele utiliza a seleção de caminhos para direcionar o pacote ao destino.Este trabalho utilizou como base o HWMP e criou uma derivação utilizando RNA no processode roteamento, no qual foi chamado de HWMP-ANN (Hybrid Wireless Mesh Protocol with

35

Artificial Neural Networks).

2.3 Simulador NS-3

O NS-3 é um simulador baseado em eventos discretos destinado para a comunidade depesquisadores e educadores com o objetivo de prover um ambiente para o estudo de redesem escalas micro e macro como, por exemplo, redes locais e a Internet. O simulador tem afinalidade de gerar ambientes controlados, onde é possível realizar análises minuciosas. Pelofato do NS-3 ter seus módulos agrupados em forma de bibliotecas, é possível que os mesmossejam usados dentro de um programa C++ que define e rode a simulação da conFiguraçãode rede montada. Apesar de ser escrito em C++, o NS-3 exporta suas funcionalidades para oambiente python, permitindo que outros programas possam importar seus módulos.

Figura 7: Organização da estrutura do NS-3.

A organização da biblioteca apresentada na Figura 7 mostra que o simulador está divididoem módulos. O core contém todos os componentes que são comuns a todos os protocolos, hard-

ware e modelos de ambiente. O simulador contém todo o modelo de execução das simulações,sendo usada como base genérica para outros módulos (não somente aqueles que são baseadosna internet). Os módulos comuns do NS-3 são livres de arquitetura de hardware e de rede.

Adicionalmente, os programas escritos para o simulador podem usar a vantagem de criarclasses que envolvem as chamadas de baixo nível da rede dentro do simulador, permitindoampliar a capacidade do usuário de extrair informações e acompanhar o estado da rede durantea execução da simulação.

Por ter uma arquitetura modular, o NS-3 se tornou robusto e extensível. A partir de suasprincipais características, apresentadas abaixo, é possível testar novos modelos de redes, es-tudar melhorias nas redes atuais e fazer o ambiente simulado interagir com máquinas reais.Suporta uma gama enorme de tipos de simulações, que podem ir de redes de celulares à novasarquiteturas de rede.

36

• É escrito em C++ com uma interface para Python de maneira opcional;

• Provê integração com softwares padronizados para entrada e saída de informação, habili-tando outras ferramentas a serem utilizadas em conjunto com o simulador;

• A pesquisa, de maneira geral, é validada de duas maneiras: através de simulações e ou-tras é implementações de maneira real. O NS-3 tem uma organização que lembra asimplementações físicas, permitindo assim testar de maneira mais fiel as simulações;

• Contém códigos que permitem integração com os módulos do kernel Linux permitindoassim que o simulador opere juntamente com dados reais. Como seu modelo é relativa-mente perto da implementação real, ele suporta drivers de dispositivos assim como APIs

IP e Sockets (no Linux);

• Facilidade de testar da simulação a ambientes reais de teste, assim como experimentosem tempo real;

• Contém uma rica documentação sobre o funcionamento de suas camadas e classes, infor-mando o que cada parte do código disponível no simulador faz;

• Seu novo modelo de geração de relatórios é compatível com ferramentas externas, comowireshark por exemplo.

37

3 MÉTODO DE PESQUISA

Este capítulo descreverá o processo de análise dos dados obtidos durante as simulações ecomo este foi estruturado.

3.1 Delineamento da pesquisa

O formato da pesquisa é exploratório, visando a busca e expansão do conhecimento dosintermédios da Rede Mesh (AKYILDIZ; XUDONG, 2009). Assim como também foi exploradoo mundo da neurociência em busca de ferramentas de apoio para otimização do problema demanutenção da qualidade da rede. Através do estudo de trabalhos relacionados com a áreade Inteligência Artificial, foi notado que as Redes Neurais Artificiais eram empregadas paraseleção e classificação de conjuntos de dados. Este processo cognitivo pode ser usado dentro domecanismo de roteamento para avaliar o estado de um cliente para a retransmissão de pacotes.

Por esta pesquisa ser de natureza exploratória, este projeto vem aprimorar mecanismos nocampo de redes de computadores aliando a área de Redes Neurais Artificiais ao processo dedecisão. Com isto, a pesquisa é flexível e tem relevância ao objeto de pesquisa (GIL, 2004).Tendo a classificação da natureza da pesquisa como aplicada, houve o desenvolvimento dasimulação e dos ajustes ao protocolo de roteamento para suportar a aplicação das Redes NeuraisArtificiais no processo de decisão (SEVERINO, 2011).

Neste caso, o problema específico é o mecanismo de roteamento dentro de uma Rede Mesh

e quais abordagens devem ser feitas para ampliar a qualidade da conexão para com o usuário,levando em conta que a rede apresenta sempre cenários de caos. Com base nesta premissa, osdados de roteamento de pacotes servirão de conjunto para análise e validação dos estados darede. As métricas utilizadas serão apresentadas posteriormente.

A pesquisa é abordada de forma qualitativa, focando na observação das transmissões depacotes, como também de forma analítica, compondo representações gráficas dos estados darede nos cenários simulados, projetando um meridional comparativo com o algoritmo padrãode roteamento.

A pesquisa sobre o problema foi realizada na forma exploratória, conforme supracitado.Foram estudados artigos e trabalhos que visam o aumento da qualidade de serviço das RedesMesh abordando o problema do roteamento dentro da rede. Alguns trabalhos tratam o problemado ponto de vista cognitivo, utilizando técnicas da natureza, buscando a flexibilidade necessáriaao protocolo. O foco deste foi aplicar a cognição ao processo de decisão de rotear pacotes, detal forma a outorgar o empirismo no protocolo.

O empirismo aplicado ao protocolo possibilita flexibilidade mediante cenários em que omesmo já possa ter convergido, ou seja, a rede estabilizou e não houve mais mudanças dosmesh clients. Caso haja mudanças após a convergência, os algoritmos tradicionais não conse-guirão funcionar de forma eficiente. É nesse ponto em que o protocolo cognitivo irá se destacar,

38

conseguindo prever mudanças e evitando a estagnação.O núcleo no ponto de decisão da transmissão do pacote foi alterado para utilizar a RNA

na avaliação dos estados dos mesh clients. Esta alteração afetou o processo da seguinte forma:antes da transmissão do pacote, a RNA avalia os estados do mesh client e determina se estaráem condições de receber dados. Caso o mesmo não esteja, o protocolo seleciona o próximodisponível, iniciando novamente a busca por um caminho até o endereço de destino.

3.2 Definição do conjunto da unidade análise e da população alvo

O conjunto de análise é formado por coleta de dados estatísticos de redes simuladas. Esteconjunto é composto por dados extraídos dos mesh clients no momento de rotear pacotes narede. Os dados serão produzidos para posterior análise e busca da validação do estado do rotea-mento para um mesh clients específico. Estes dados representarão as estatísticas do roteamentoe os estados da RNA utilizados para validar os pacotes.

A produção dos dados para análise ocorre dentro do simulador, conforme os cenários sãorodados no ambiente. Os conjuntos de dados foram produzidos com estatísticas extraídas dosimulador e compiladas em um banco de dados, permitindo a análise dos dados e avaliação doprotocolo.

3.3 Técnica de coleta de dados

Este trabalho utiliza as seguintes técnicas de coleta de dados:

• Pesquisa bibliográfica: principal fonte de conteúdo a ser tomada como base da pesquisa,através de livros e artigos científicos relacionados com a área. O conteúdo foi crucial paraampliação da base de conhecimento e para o aumento da segurança do conteúdo cientí-fico necessário usado no desenvolvimento da pesquisa. Com isso, foi possível escolhero ambiente de simulação que suportaria a utilização de ambas áreas em uníssono, comotambém extrair as métricas do roteamento da rede e análise dos dados coletados (MAR-CONI; EVA MARIA, 2011);

• Pesquisa Documental: foram realizadas pesquisas com os problemas relacionados ao ro-teamento. Também foram consultados textos sobre análise e fluxo de dados em redese, em momentos, foi necessário buscar material sobre a utilização de Redes Neurais naresolução de problemas relativos a decisões e processos cognitivos em mecanismos dedecisão;

• Observação Sistemática: A observação sistemática (registro das ocorrências em arquivosde texto) gerou dados estatísticos sobre o funcionamento do roteamento entre client no-

des. Esses registros foram gerados conforme o andamento das transmissões de dados emarcados para identificação posterior do fluxo de cada client node passando por aquele

39

ponto específico. Com estes registros foi possível gerar um conjunto de gráficos querepresentam o estado da rede (GIL, 2004);

3.4 Técnica de análise de dados

Foi realizado um exame exaustivo dos dados gerados e também sua tabulação. Os registroscompõem tabelas de fluxos de dados e tabelas comparativas de estados da rede após a simula-ção. Essa tabela contém os dados do roteamento de pacotes dentro da rede, tais informaçõesrepresentam o estado da rede decorrente da simulação e como ocorreu o roteamento de pacotes.Cada tabela de dados é composta por:

• Taxa de Transmissão de pacotes (txPackets);

• Taxa de Transmissão de pacotes entregues (rxPackets);

• Pacotes Perdidos (lostPackets);

• Pacotes Abandonados (droppedPackets);

• Média de Entrega de Pacotes (PDF - Average Packet Delivery Fraction);

• Atraso Médio na entrega de pacotes (delay);

• Média na transmissão de bits (rxBitrate);

• Taxa de transmissão de bits (txBitrate).

A tabela de dados da RNA representa o fluxo de saída da rede e a taxa de convergência emrelação aos dados de entrada (métricas de estado dos nodes que estão sendo encaminhados ospacotes). A tabela é composta por:

• Entrada 1 (PDF);

• Entrada 2 (Delay);

• Saída.

Os dados de saída da RNA representam a convergência do resultado da rede na previsão dosestados dos mesh clients. Esta convergência define se o protocolo deve ou não enviar o pacote.A partir de seu treinamento supervisionado e conforme os dados passam pela RNA, os dadossão agrupados de forma a alinhar os resultados para determinação dos estados.

40

41

4 SIMULAÇÕES

Neste capítulo serão apresentados os cenários em que as simulações ocorreram e a estruturamontada da topologia da rede, suas configurações e parâmetros.

4.1 Cenários de Execução

O cenário base foi criado para ser configurável, permitindo a alteração de seus parâmetrose consequentemente, a partir da mesma construção, gerar resultados alternativos para uma basecomparativa. Seus parâmetros base são:

• x-size: Tamanho em X do grid, padrão 6;

• y-size: Tamanho em Y do grid, padrão 6;

• step: Espaço da borda no grid, padrão 100m;

• step: Tempo de aleatoriedade para início da transmissão de pacotes (0.1 segundo);

• time: Tempo da simulação, padrão 100 segundos;

• packet-interval: Intervalo de transmissão dos pacotes, padrão 0.001 segundo;

• packet-size: Tamanho do pacote, padrão 1024bytes;

• interfaces: Número de interfaces de transmissão (antenas) que o um client node possuirá,padrão 1;

• channels: Número de canais de transmissão de um client node, padrão 1;

• pcap: Habilita PCAP para geração de arquivos de trace, padrão sim;

• stack: Modelo da pilha de rede utilizada, padrão ns3::Dot11sStack;

• root: Endereço MAC do node base do grid.

Os cenários da rede foram criados com a finalidade de propiciar meios de gerar resultadosaleatórios e de testar diversas configurações de rede. Com esses testes, é possível estressaros mecanismos da rede, assim como a capacidade de adaptação da rede neural. O código docenário base é apresentado no anexo A.1. As simulações foram rodadas com valores diferentespara alguns parâmetros, tais como tamanho do grid, quantidade de nodes presentes na rede,tempo da simulação e aleatoriedade da transmissão de pacotes.

Os cenários executados com a finalidade de extração de dados são apresentados na Tabela 1.Nestes cenários, a variação entre eles foi o tamanho do grid (quantidade total de mesh clients),

42

Cenário Tamanho X Tamanho Y Tempo Total (s) Modelos de MobilidadeCenário 1 5 5 240 ConstantPositionMobilityModelCenário 2 5 5 240 RandomWalk2dMobilityModelCenário 3 5 5 240 Random2dMobilityModelCenário 4 50 50 1240 ConstantPositionMobilityModelCenário 6 50 50 1240 RandomWalk2dMobilityModelCenário 7 50 50 1240 RandomCar2dMobilityModelCenário 8 50 50 1240 Random2dMobilityModel

Tabela 1: Cenários gerados para simular a rede em diversas condições.

vistos na tabela como Tamanho em X e Y. Também foi variado o tempo de simulação, com a fi-nalidade de avaliar se, com um tempo maior, o algoritmo de roteamento continuaria convergindocorretamente. Outra variável de simulação do cenário utilizada foi o modelo de mobilidade dosnodes influenciando diretamente a rede. Esses modelos foram os fatores principais de estresseda rede, forçando sempre os limites da simulação e gerando resultados expressivos durante ostestes do algoritmo.

A topologia apresentada (Figura 8) representa de forma simplificada a organização dos no-

des durante o período da simulação. São gerados com espaços iguais entre si e posteriormentea rede é rearranjada de forma aleatória com a finalidade de gerar estruturas com maior nívelde complexidade e estocasticidade, estressando ao máximo o algoritmo de roteamento. Alémdisto, o cenário permite o ajuste no padrão de movimentação dos mesh clients, sendo possívelindicar a organização e também sua movimentação de forma aleatória.

O protocolo de roteamento escolhido foi o HWMP. O HWMP possui propriedades reativase pró-ativas, consoantes com os objetivos da RNA dentro do roteamento. O algoritmo identificao melhor caminho a ser percorrido pelo pacote, visto na Figura 8, sempre buscando validar qualcaminho o mesmo está decorrendo. Assim, o caminho será sempre o ótimo se baseando nasmétricas dos padrões do HWMP, porém, como visto anteriormente, este caminho pode sofrerflutuações caso os mesh clients ficarem indisponíveis ou sobrecarregados.

Como o protocolo funciona com manutenção por link (formato P2P1), periodicamente ocorreuma comunicação entre os mesh clients vizinhos para atualização da tabela de roteamento.Quando ocorre esta comunicação, os mesh clients transmitem pacotes de controle, atualizandoo estado para seus vizinhos.

O pacote administrativo é composto por flags (controles de transmissão base). A estruturado pacote administrativo foi alterada para suportar o envio e o recebimento dos dados quesão usados para compor as métricas avaliadas pela RNA. Os parâmetros são total de pacotestransmitidos, número de pacotes que foram transmitidos com sucesso e a taxa de atraso médiono encaminhamento dos pacotes.

1Descrição em http://en.wikipedia.org/wiki/Peer-to-peer , acessado em 10 abril de 2012

43

Figura 8: Representação da topologia da Rede Mesh mostrando o caminho ótimo dos pacotes entre doismesh clients.

Com a finalidade de transmitir os dados dos seus estados, o protocolo utiliza as mensagensde controle. Para isto foi alterado o pacote de gerenciamento e adicionado ao cabeçalho 25bits que guardam o tx, o rx e o delay. Os parâmetros são mantidos atualizados, possibilitandocom que a RNA avalie o estado do mesh client. A Figura 9 mostra a estrutura do frame e alocalização das informações de estado do node.

Inicialmente, a avaliação não é ativa. A rede deve convergir de forma natural para posteri-ormente ocorrer o preenchimento das tabelas de roteamento. Após essas etapas, o processo deavaliação começa. Uma vez que os pacotes de controle atualizam diversas informações relativasao estados dos nodes, foi decidido utilizá-los para transportar os dados de controle da RNA dosnodes.

Em ordem de habilitar a RNA e conseguir avaliar o mesh client de destino, durante a trocade pacotes de administração, o protocolo foi ajustado para informar os parâmetros adicionais aonode do qual está recebendo as informações de estado, sendo eles Taxa de Transmissão, Taxa deEntrega de Pacotes com Sucesso e Atraso Médio. A Figura 10 representa como o HWMP-ANNfuncionaria em seu estado perfeito, fazendo com que os nodes problemáticos sejam evitados.

44

Figura 9: Estrutura do Frame de transmissão do protocolo HWMP-ANN.

Sendo assim, o caminho principal fica recortado e o pacote viaja paralelamente, sempre evitandoáreas e nodes congestionados.

A Figura 10 representa um modelo topológico da Rede Mesh. É possível notar que osnodes que ficam constantemente conectados são indicados por linhas pontilhadas com setas emambos os lados simbolizando o link entre seus vizinhos. Com o link estabelecido, conforme anecessidade, o node retransmite dados e atualiza seu status. Pode-se separar este processo deroteamento de um pacote nas seguintes etapas: 1) requisitar um caminho, a partir disto a redeconverge a retornar um caminho até o node destino; 2) avaliar este caminho, após isto o pacoteé transmitido para os endereços contidos na sequência de pulos.

4.2 RNA Aplicada ao Roteamento

Durante a fase de pesquisa, o modelo de rede neural escolhido foi o Rede Recorrente Di-namicamente Dirigida (RRDD). Esse modelo tem propriedades de convergência automáticadentro do protocolo da rede, ou seja, não necessita de interferência do usuário em relação aajustes dos seus pesos e na criação de cenários de treinamento. Assim, a rede aprende sozinha,convergindo de forma natural às métricas apresentadas durante o intervalo que o mesh client

estiver ativo.

Foi escolhido este modelo de rede neural por sua capacidade de aprender sozinha com umsupervisor automático, por sua memória matricial com atraso temporal e por sua capacidadede adaptação contínua. O aprendizado supervisionado automatizado ocorre durante a execuçãoda RRDD, ajustando os pesos internos da rede com base em sua saída. O supervisor operana convergência do resultado com a finalidade de manter a rede sempre dentro dos parâmetrosespecificados durante seu projeto. Memória matricial com atraso temporal tem a capacidade deavaliar em um futuro (não somente breve mas também longínquo) os estados dos nodes que opacote deve viajar. A capacidade da adaptação contínua deixa com que a decisão do pacote deir em frente ao caminho previamente selecionado continue flexível, porém, mesmo depois daconvergência da RNA ou algum evento de reorganização da rede acabe por ocorrer, o processode decisão continuará ocorrendo.

A Tabela 2 apresenta os modelos clássicos das RNAs e seus objetivos. Nessa tabela as

45

Figura 10: Representação Parcial da topologia da rede.

colunas representadas como Req. 1, Req. 2 e Req. 3 são os requisitos relacionados comAprendizagem Não Supervisionada, Capacidade de Representação Temporal e Suporte a RetroPropagação.

Os estados dos client nodes podem ser mapeados como séries (Equações 4.1 4.2), ondeé possível mapear a variação das mesmas para a RNA. Considerando esta variação, a redeconsegue convergir e tratar os estados dos mesh clients em um futuro e decidir se o pacote deveou não ser transmitido. Caso seja decidido por não transmitir o pacote, o protocolo foi ajustadopara enviá-lo para o próximo mesh client que esteja disponível.

Spdf =n∑

i=1

(Tn/Rn) (4.1)

Sdelay =n∑

i=1

(Tn − T1+n) (4.2)

46

Modelo de RNA Req. 1 Req. 2 Req. 3Feedforward - - -Perceptron - - -Hopfield/Tank - - -Hopfield com Retropropagação - X XRRDD X X X

Tabela 2: Modelos de RNA pesquisados e seus requisitos para uso no roteamento de pacotes na rede.

Durante a construção dos cenários, foram aplicados ajustes ao algoritmo de roteamentodentro da camada de retransmissão e construção de caminhos pra os pacotes. Foi utilizada aRRDD para a avaliação dos estados dos mesh clients. Porém não foi possível simular os nodes

pois a simulação consumiu muitos recursos de hardware. Assim como qualquer outra RNA, aRRDD demanda enorme recursos computacionais. Esse problema é evidenciado no trabalhode Venkataram, Ghosal e Kumar (2002) no qual demonstra os resultados apresentando o quea sobrecarga da RNA faz com a simulação e propõe uma implementação a nível de hardware.A simulação de todo o protocolo HWMP-ANN (Hybrid Wireless Mesh Protocol with Artificial

Networks) teve que ser feita utilizando uma versão mais simplista de RNA e otimizada parafuncionar na simulação.

Figura 11: Estrutura da RNA utilizada no processo de decisão do roteamento de pacotes.

A utilização da RRDD dentro de cada node simulado demandou um grande consumo derecursos da máquina, fazendo com que a simulação utilizasse mais de 4 Gigabytes de memóriaRAM e ocupando os 8 núcleos do processador. Para simular um ambiente com mais de 100nodes seria necessário rodar em uma grade de processamento ou mesmo utilizar algum cloud

computing. Com esta barreira impossibilitando a simulação de ser executada, foi decidido quea RNA a ser utilizada seria uma rede de Hopfield com retro-propagação (Figura 11). A rede foiconstruída para funcionar de forma assíncrona ao ambiente, tendo seus cenários de treinamentocriados a parte da simulação e tendo sua instância única para todos os mesh clients, diminuindoa necessidade de hardware.

O conjunto de treinamento foi feito precedente à simulação e a convergência da RNA foisalva para uso posterior. A base de dados dos cenários de treinamento foi criada a partir da

47

PDF Atraso Saída esperada0.942602 0.0157996 10.950339 0.043428 10.577982 0.0777419 00.51567 0.0668167 00.884 0.0158224 10.818182 0.0185725 10.533813 0.281112 00.919325 0.0104014 10.578144 0.152738 00.489744 0.0588817 00.501792 0.0469955 00.938449 0.264351 10.362369 1.00000 00.876988 0.0533023 10.388235 0.00797154 00.954128 0.0112579 10.366667 0.153154 0

Tabela 3: Amostra da Base de dados construída para treinar a RNA sobre os estados dos mesh clients.

extração das métricas de roteamento do ambiente simulado e compilado nos treinamentos su-pervisionados. As métricas foram extraídas com a finalidade de avaliar os mesh clients virtuais.Pelo fato de serem simuladas, as métricas reais poderiam representar dados imprecisos para abase de dados avaliativa. Então as métricas dos nodes virtuais foram extraídas com a finali-dade de possibilitar com que os testes avaliativos executados pela RNA dos mesh clients fossemcoerentes com os estados em que se apresentariam.

Tais conjuntos foram normalizados entre o intervalo 0 e 1, fazendo com que a convergênciada RNA demonstrasse o estado futuro do mesh client e que sua saída indicasse se o node estarásobrecarregado. A base de dados compilada é demonstrada (parcialmente) na Tabela 3. Comesses dados, a saída da RNA sempre estará no intervalo de 0 a 1 e os nodes com saídas maioresque 0.5 indicam que estão estáveis para encaminhamento dos pacotes. Tais atributos variamdurante o tempo de execução, sempre tendendo para menos, conforme a quantidade de pacotespara ser encaminhados aumenta.

Por fim, a RNA ficou com a estrutura de duas entradas, três neurônios na camada oculta eum na saída. O layout ficou com o padrão de 3 camadas, como visto na Figura 11. A utilizaçãosimples e direta da estrutura foi efetiva e de maneira geral conseguiu representar os estadosdos mesh clients durante toda a execução das simulações e, com o uso da retropropagação, ospesos acabaram se ajustando para suportar as alterações dos estados dos nodes fazendo com quea RNA conseguisse convergir e identificar um mesh client com métricas ruins.

48

49

5 AVALIAÇÃO DOS RESULTADOS

Neste capítulo, serão descritos os resultados das simulações da Rede Mesh com a utiliza-ção da RNA. Conforme apresentado no capítulo 4, as simulações foram desenvolvidas paraserem totalmente aleatórias, produzindo cenários caóticos. Os parâmetros gerais da rede e osresultados de um total de 250 simulações foram armazenados em um banco de dados.

O objetivo desta avaliação é verificar se o uso de caminhos alternativos determinados deforma empírica pela RNA é eficiente e aplicável ao problema. As pesquisas de Venkataram,Ghosal e Kumar (2002) e Zhi-yuan, Ru-chuan e Jun-lei (2009) buscam evitar a sobrecargado caminho principal e determinar caminhos alternativos. Já o objetivo deste trabalho vem ahabilitar a resolução de caminhos alternativos de forma cognitiva. Cabe à RNA a decisão dequal o caminho o pacote deve seguir.

5.1 Métricas da simulação

Os parâmetros extraídos possibilitaram a análise minunciosa do funcionamento da rede,assim como a efetividade do protocolo de roteamento modificado. As métricas para avaliaçãoforam selecionadas a partir de trabalhos que serão apresentados no capítulo 6. O conjunto demétricas é constituído por:

• Throughput;

• A média fracionária de entrega de pacotes, do inglês Average Packet Delivery Fraction

(PDF), vista na equação 5.1, aonde Rx significa a quantidade de pacotes transmitidoscom sucesso e Tx significa a quantidade total de pacotes que foram enviados;

• Taxa de Transmissão de Pacotes;

• Média de delay entre o pacote sendo enviado e seu tempo de chegada ao destino;

• Pacotes que chegaram ao destino;

As avalições foram construídas utilizando como base os autores Venkataram, Ghosal e Ku-mar (2002) Zhi-yuan, Ru-chuan e Jun-lei (2009) Song, Zhang e Fang (2010) Baumann et al.(2007) e Paul et al. (2010). As informações sobre a transmissão foram extraídas utilizando omecanismo de rastreamento fornecido pelo NS-3 e por modificações internas para o simuladorsuportar a saída da RNA.

PDF = (Rx/Tx) (5.1)

A simulação gerou arquivos contêndo informações relevantes sobre os estados que um mesh

client assumiu durante o período da execução da simulação. A partir de tais informações, foram

50

produzidos gráficos traçando um comparativo entre as métricas da simulação utilizando RNAs eas que não utilizam. As métricas básicas levantadas até o presente momento foram apresentadasno início deste capítulo.

5.2 Resultados obtidos

Com a finalidade de criar uma base comparativa, a rede foi simulada cerca de 250 vezes uti-lizando o padrão HWMP. Tais simulações geraram o conjunto base de métricas de roteamento.Essas métricas foram usadas para delimitar as análises dos resultados posteriores e criar umparâmetro comparativo do protocolo alterado com as execuções sem a utilização das RNAs. Osgráficos apresentados nas Figuras 12, 14(a), 14(b) e 15 demonstram a qualidade da rede e seuspadrões de entrega de pacotes. Estes gráficos foram gerados com uma amostra de 25 fluxos darede, contendo entre os mais e menos efetivos casos no processo de roteamento.

Figura 12: Média fracionária de entrega de pacotes.

O gráfico da Figura 12 representa a fração de pacotes que chegaram com sucesso ao seudestino, isto demonstra de maneira efetiva como o protocolo de roteamento está funcionando ese os caminhos selecionados são estáveis e confiáveis. Porém, como toda a Rede Mesh é sujeitaa alterações, é possível notar que, em alguns casos, esta média fica abaixo da linha dos sessentapor cento de entrega. Tal limiar foi traçado com a finalidade de identificar mesh clients que temresidem em ambiente mais estocásticos.

Foi traçado um comparativo de alguns algoritmos de roteamento propostos nos trabalhosrelacionados. Esse foi feito com o propósito de demonstrar o resultado geral da efetividade doroteamento na rede. Os dados de roteamento dos trabalhos foram extraídos e compilados em 3cenários. Estes cenários foram baseados no trabalho de Baumann et al. (2007) e o HWMP-ANfoi simulado com parâmetros de mobilidade para ser incluído no comparativo.

O gráfico na Figura 13 apresenta alguns algoritmos e projeta um comparativo do HWMP-

51

Figura 13: Comparativo entre alguns algoritmos de roteamento e o HWMP-AN.

AN demonstrando sua efetividade em 3 cenários distintos. É possível notar que conforme amobilidade aumenta (representado pelos pedestres e carros no gráfico) a tendência da efetivi-dade dos protocolos abaixa. É possível notar que apesar da mobilidade aumentar alguns delesmantém sua efetividade porém levemente diminuta. O HWMP-AN apresentou vantagens emcenários caóticos. Nos cenários apresentados, onde foi buscada a flexibilidade, e, apesar do al-goritmo não ser totalmente otimizado, o HWMP-AN desempenhou formidavelmente seu papel,mantendo a conectividade da rede.

(a) Taxa de Transmissão de Pacotes. (b) Total de pacotes entregues com sucesso.

Figura 14: Gráficos mostrando o comparativo de 25 simulações proeminentes.

Nota-se na (Figura 14(a)) que a taxa de transmissão de pacotes tende a variar também con-forme o mesh client é selecionado para rotear pacotes. Os nodes mais exteriores tendem a nãoserem selecionados para a retransmissão por ter métricas ruins. Porém, traçando um paralelocomparativo entre a Figura 12, é possível notar que mesmo estes nodes podem ter taxas de

52

entrega aceitáveis.

Os mesh clients com métricas ruins podem ter pontos positivos no processo de roteamento,funcionando como pontos temporários de apoio em relação aos mesh clients estáticos. Nográfico da Figura 14(b), comparando com o da Figura 12, assim como o da Figura 15, é possívelnotar que mesmo aqueles mesh clients não são selecionados possuem grandes taxas de entrega.

Figura 15: Total de Pacotes Perdido durante a simulação.

Porém, a tendência é dos pacotes sempre trafegarem por caminhos estáveis. Em face acongestionamentos ou mesmo uma mudança brusca na topologia, os caminhos alternativos setornam viáveis à curto prazo, com a finalidade de dispersar o fluxo de informação e manter aconectividade da rede, assim o fluxo é sustentado mesmo em cenários de caos. Foi selecio-nada uma amostra de 25 fluxos de dados do conjunto de avaliação e apresentado no gráfico daFigura 16. O gráfico apresenta a média de entrega de pacotes comparando uma execução daversão do protocolo sem a RNA e outras com a utilização da RNA. É visto que, em comparaçãoao roteamento trivial, a RNA consegue aumentar as taxas de entrega e diminuir os atrasos emalguns nodes.

Conforme os usuários presentes dentro da rede requisitam mais dados, nota-se que os mesh

clients estáticos tendem a se sobrecarregar, aumentando significativamente o atraso na entregade pacotes. Isto também é influenciado diretamente pela distância do caminho selecionado paraos pacotes. Porém, utilizando a dispersão dos fluxos de dados conforme a RNA avalia os saltosfuturos, o atraso tende a diminuir consideravelmente.

Foi apresentado nos gráficos das figuras 17, 18 e 19 que o atraso médio geral utilizandoRNA tende a ser menor, já que a mesma consegue de maneira efetiva prever os estados dosnodes e conseguir evitar a sobrecarga eminente.

A dispersão média dos atrasos das entregas de pacotes tende a ficar baixa (Figura 19). Adispersão do fluxo tem impactos positivos em toda a infraestrutura, além de evitar que caminhosestáveis se congestionem. A preempção dos estados evita que pacotes avancem por lugares ondeirão se tornar instáveis ou gerar atrasos em sua entrega.

53

Figura 16: Comparativo entre Total de pacotes entregues sem e com a utilização das RNAs.

Figura 17: Atraso médio na entrega de pacotes.

Figura 18: Comparativo de 12 simulações mostrando o atraso médio utilizando a avaliação pela RNA.

Durante as simulações, foi possível notar que houve um aumento nas taxas de entrega depacotes utilizando as RNAs, Figura 20(a). Em muitos casos a rede consegue garantir que o

54

Figura 19: Dispersão da média de atrasos de todas as simulações utilizando a RNA.

pacote trafegue por vias alternativas com estabilidade suficiente para chegar ao seu destino.

(a) Média fracionária de entrega de pacotes utilizandoRNA.

(b) Comparativo de pacotes perdidos.

Figura 20: Gráficos representando o estado (métricas PDF e Pacotes Perdidos) da rede comprando 25fluxos de informação, com RNAs e Sem RNAs.

No entanto, esta rede somente avalia um salto a frente, deixando abertura para que o pacoteentre em um caminho onde não conseguirá atingir seu destino. Conforme apresentado no gráficoda Figura 20(b), a perda de pacotes apresenta uma pequena elevação em alguns fluxos. Porém,essa porcentagem é baixa quando a rede seleciona um caminho alternativo perto do ótimo.

O throughput da rede representa quantos pacotes foram entregues passando pelo caminhoprincipal, isto demonstra o uso eficiente da banda de transmissão. O throughput teórico condizcom a entrega média de pacotes com sucesso sobre um canal de transmissão. Porém, no trabalhodesenvolvido, esta métrica apresenta distorções. Estas distorções são citadas por Venkataram,Ghosal e Kumar (2002), uma vez que a rede neural tende a forçar os limites das simulações.

Foi montada uma amostra de doze itens a partir das 250 simulações. Este comparativo faza indicação de que o throughput da rede se mantém estável com a utilização das RNA. Nestaanálise foi identificado que o throughput da rede nunca conseguirá exibir a total efetividade do

55

(a) Média fracionária de entrega de pacotes utilizando RNA comparando as simulações.

(b) Delay médio na entrega de pacotes das si-mulações.

(c) Comparativo do throughput da rede.

Figura 21: Métricas gerais comprando 12 rodadas de simulações.

protocolo modificado, pois onera, a nível de software, o custo da execução das RNAs, fazendocom que a simulação roteie pacotes de maneira menos efetiva.

Fazendo o comparativo entre os gráficos nas figuras 21(c), 21(a) e 21(b), os delays são bai-xos e o PDF é alto. Isto demonstra que a rede está funcionando, porém o cálculo do throughput

considera o tempo e o caminho que o pacote levou. Nisto, o throughput do protocolo modifi-cado não representa efetivamente a eficiência da rede, já que os pacotes não necessariamentefazem o mesmo caminho até seu destino.

Já na dispersão do PDF (Figura 22) é possível notar que, durante todas as simulações,mesmo com a aleatoriedade dos mesh clients, as taxas de entrega de pacotes se mantêm es-táveis e perto dos 80%. Durante o período de simulação, algumas saídas se mantiveram pertodo 0%. Estas saídas foram consideradas como pontos de anomalias, uma vez que estavam rela-tivamente afastados de outros mesh clients, tendo perda considerável de pacotes, níveis de PDFmuito baixo e com sinal de conexão muito fraco, ou seja, este mesh client estava presente emuma parte do ecossistema distante dos outros.

56

Figura 22: Dispersão da média fracionária em todas as simulações.

Para representação geral dos resultados foram geradas dez médias ponderadas com as trêsmétricas mais proeminentes: o atraso média na entrega de pacotes (Figura 23(a)), a média depacotes perdidos (Figura 23(b)) e o PDF(Figura 23(c)). Foi possível notar que as simulaçõesnão atingiram todo seu potencial devido a sobrecarga da própria simulação. Também podemosverificar na Figura 23(c) que o PDF utilizando as redes neurais ficou com uma média aceitável.

Podemos identificar que o delay médio de todas as simulações ficou abaixo do 0.035 milis-segundos, nunca ultrapassando este limite. Isto demonstra que a rede sempre converge e queas entregas de pacotes são sempre bem sucedidas. A média de perda de pacotes ficou extrema-mente baixa (Figura 23(b)), considerando que durante as simulações trafegaram mais de doismil e quinhentos pacotes. Em face aos problemas já elencados da sobrecarga da simulação devários nodes, todo o hardware de rede e também os meios de transmissão, os resultados trans-parecem, em muitos dos casos que a RNA representou um fator determinante no contorno docaos imposto à rede.

57

(a) Delay Médio de todas as simulações. (b) Média de pacotes perdidos em todas as si-mulações.

(c) PDF Médiano de todas as simulações utilizando RNA.

Figura 23: Gráficos representando o desempenho geral da simulação da rede.

58

59

6 TRABALHOS RELACIONADOS

Neste capítulo serão descritos alguns trabalhos que possuem características comuns ou se-melhantes a este trabalho.

6.1 A Multipah Routing Algorithm Based on Traffic Prediction in Wireless MeshNetworks

A predição de tráfego é a base do trabalho de Zhi-yuan, Ru-chuan e Jun-lei (2009). Os auto-res colocam como destaque a predição de tráfego na manutenção da qualidade do serviço (QoS,

quality of service). A proposta do trabalho inclui a construção de séries temporais, métodos deregressão e redes neurais, considerando-os parte importante na resolução da tarefa de predizero tráfego.

As Redes Mesh tendem a ser caóticas e com modelos matemáticos diminutos. Por causadisso, os métodos de predição tradicionais não são efetivos, de maneira que métodos não li-neares são baseados na capacidade da rede neural de conseguir organizar os dados do tráfegoda rede. Tal modelagem ocorre com a análise minuniosa da rede observando as característicasdo tráfego de pacotes. O MRATP foi construído com a finalidade de trabalhar na predição detráfego para aumentar a qualidade do serviço no processo de entrega de pacotes.

Essa abordagem é uma nova tentativa de prover flexibilidade no roteamento de pacotes pararedes mesh, aumentando a qualidade. Esse método usa primariamente caminhos alternativosao principal para transmitir dados mais leves que não necessitam de desempenho na entrega,deixando assim os caminhos principais para os fluxos mais custosos como stream de vídeo ouprotocolos TCP, que necessitam de confiabilidade na transmissão de pacotes.

Os parâmetros de avaliação dos caminhos alternativos são a distância XOR entre nodes,espaço de banda para transmissão e energia residual dos nodes. Conforme as transmissõesocorrem, a rede, avalia em tempo real constantemente se ocorrerá congestionamento. Casonecessário utilizará os caminhos alternativos para rotear os pacotes.

6.2 Neural network based optimal routing algorithm for communication networks

O trabalho Venkataram, Ghosal e Kumar (2002) seleciona como fator impactante o rotea-mento de pacotes dentro da infraestrutura de rede, tendo como foco principal a descoberta decaminhos eficientes para transmissão de dados. Esse caminho ótimo deve ser descoberto como desperdício mínimo de tempo, satisfazendo as demandas do usuário. Em termos de definiçãode rede para o melhor desempenho, ou seja, ter o throughput alto ou atraso médio de entregade pacotes baixo é preciso que tal processamento seja feito em tempo real. Isto faz com que aRNA seja uma perfeita candidata para tal objetivo.

A utilização da RNA é indicada por ter uma grande capacidade de processamento paralelo

60

e assim aumentar o ganho de tempo no período de processamento de pacotes. Os algoritmos deroteamento usados atualmente utilizam de alguma foram os cálculos de menor caminho. Porém,o trabalho busca fazer estes cálculos em tempo real, eliminando a sobrecarga necessária dentroda camada de rede.

Assim, os autores demonstram a utilização de RNAs na busca de caminhos dentro da rede,achando a melhor via entre dois mesh clients. O modelo de RNA selecionado foi o de rede re-corrente de hopfield. Foi também descrito como implementá-lo a nível de hardware. O trabalhoapresenta resultados promissores na resolução da busca do melhor caminho, porém utiliza umatopologia estática da rede, não tendo flexibilidade suficiente para uma rede estocástica.

6.3 Stochastic Traffic Engineering in Multihop Cognitive Wireless Mesh Networks

O trabalho de Song, Zhang e Fang (2010) é focado em uma área pouco explorada em RedesMesh cognitivas, nomeada de engenharia estocástica de tráfego, do inglês stochastic traffic

engineering (STE). O objeto de pesquisa foi o funcionamento do tráfego dentro da rede, oscomportamentos dos usuários e como estes afetam os seus vizinhos.

A partir da análise dos usuários presentes na rede, o trabalho apresenta mecanismos possí-veis para aumentar a qualidade. O trabalho faz a análise de frequências utilizadas para transmis-são dos dados buscando aumentar consideravelmente a utilização eficiente das mesmas. No de-senvolvimento tecnológico propõe técnicas avançadas para trabalhar na camada física da rede,removendo os limites de frequência das transmissões e permitindo com que os nodes transmi-tam nas bandas restritas (bandas especiais, de uso restrito ao governo e licenciadas). Sem estarestrição, o trabalho apresenta a possibilidade de aumentar a eficiência da rede ao conseguirtransmitir mais pacotes em um ambiente com índices menores de colisão.

Como resultado final, além da proposta de alteração de frequências de transmissão, o traba-lho indica que os mecanismos de roteamento se tornem proativos e consigam evitar áreas que setornem ruins para tráfego da rede, enviando os pacotes por caminhos que sejam estáveis e quesofram menos interferências dos usuários, como movimentação, nodes que tendem a ser desli-gados. Por fim acabam por unir o modelo matemático da engenharia de tráfego ao algoritmo deroteamento, evitando de forma efetiva as áreas de transmissão problemáticas.

6.4 High Performance AODV Routing Protocol for Hybrid Wireless Mesh Networks

O trabalho apresenta uma nova abordagem ao roteamento das redes mesh híbridas utilizandoo AODV. Os autores demonstraram uma nova métrica no protocolo na tentativa de solucionaro problema de rotear pacotes com mesh clients altamente móveis. Foram exploradas as capa-cidades do AODV e criada uma extensão chamada de AODV-HP (PIRZADA; PORTMANN,2007).

A métrica desenvolvida para o AODV-HP foi a de sempre priorizar os mesh routers durante o

61

processo de transmissão dos pacotes. Com isso, o protocolo conseguiu aperfeiçoar o roteamentoem cenários de grande mobilidade.

6.5 A high-throughput path metric for multi-hop wireless routing

A solução proposta em De Couto et al. (2005) é trabalhar na métrica ETX, ou seja, contagemde transmissões esperada (do inglês expected transmission count). O ETX encontra caminhoscom o mínimo de saltos possíveis (incluindo as retransmissões). Essa métrica calcula quan-tos saltos o pacote dará para chegar ao destino e usa as taxas de perdas e o uso da banda detransmissão nos nodes, assim como as taxas de envio e recebimento dos nodes. Como principalobjetivo o ETX acha caminhos com grandes taxas de throughput e minimiza o valor de perdade pacotes.

O ETX trabalha bem com caminhos que tenham dois ou mais saltos. Entretanto, seu de-sempenho tende a variar quando enfrenta cenários de caos, onde as ações dos usuários afetamdiretamente os links de transmissões. O trabalho apresenta modificações dentro do DSDV eDSR em ordem a suportar o ETX ajustado e demonstra que há um aumento significativo natransmissão de pacotes. Por fim, explica o ganho de desempenho que a rede tem ao utilizar asmétricas modificadas.

6.6 Quality-Aware Routing Metric for Time-Varying Wireless Mesh Networks

No trabalho Koksal e Balakrishnan (2006) foi desenvolvido também uma versão modificadado ETX, chamado mETX (Modified ETX). A pesquisa teve como objeto a busca pelo melhorcaminho de roteamento, através das camadas superiores da rede, sempre utilizando baixas taxasde perdas de pacotes. Com isso o trabalho desenvolveu outra métrica chamada ENT (Effective

Number of Transmissions) que mantém o mETX sob controle, impedindo que a primeira métricaenvie pacotes por caminhos que apresentem índices significativos de perca de pacotes.

Ambos mETX e ENT capturam as características temporais dos canais com o objetivo detraduzir o estado físico para as camadas superioras da rede e determinar como enviar dadosde maneira eficiente. Com o tempo, se somente for utilizada uma das métricas propostas notrabalho, o roteamento tende a não manter todos os parâmetros em vista. Logo, se ambos foremusados, então a tendência demonstrada é que a banda da transmissão seja usada eficientemente.Com essa avaliação física, o impacto do desempenho à nível da rede é visível. Os autoresindicaram que com esse método é possível atingir 50% de redução da perda de pacotes.

6.7 Bio-inspired Link Quality Estimation for Wireless Mesh Networks

O trabalho de Caleffi e Paura (2009) traz como foco da pesquisa a busca por melhores avali-ações das métricas, como ETX, SMA (Simple Moving Avarege) e EWMA (Exponetially Weigh-

62

ted Moving Avarege). Essas métricas podem ser encaixadas como séries temporais, habilitandocom que a RNA proposta consiga derivar em um futuro breve seus possíveis valores.

O paradigma de estimativa biológica, ou seja, empírica, é demonstrada durante a pesquisados autores. A efetividade do uso do RNA na construção de métricas de métricas eficiêntesse dá pelo fato que as RNAs possuírem, em muitos casos, a habilidade de aprender através daaprendizagem não supervisionada. A implementação em dispositivos de baixa memória fica nomesmo nível dos algoritmos tradicionais. Em ambas implementações, por estarem presentesem ambientes diversificados, o algoritmo de estimativa é igualmente eficiente. O trabalho apre-senta uma comparação numérica com duas estimativas normais e representa a efetividade daestimativa utilizando RNA para ambientes mesh e ad hocs.

6.8 Cognitive Wireless Mesh Networks with Dynamic Spectrum Access

O trabalho dos autores Chowdhury e Akyildiz (2008) apresenta uma abordagem, com afinalidade de reduzir colisões de transmissão, nova em cenários de grande quantidade de mesh

clients presentes. A abordagem repousa sobre o uso de antenas configuráveis presentes emdispositivos conectados a malha. Essas antenas podem ajustar o espectro de transmissão dodispositivo, assim deixando com que consiga enviar dados através de bandas prioritárias, paraseus vizinhos, e bandas licenciadas para transmissões de longa distância.

Todo o estudo foi conduzido sob o preceito de evitar o congestionamento do meio de trans-missão, logo o trabalho apresenta resultados indicando que com o aumento de dispositivospresentes nas redes, acabam interferindo no meio causando colisões das ondas de rádio. Outrosfatores são considerados, como a presenta de micro-ondas, dispositivos bluetooth1 entre outrasfontes de intefêrencia. Nisso os autores buscam a redução significativa da aplicação em largaescala do modelo da rede, flexibilizando a rede a conseguir pró-ativamente evitar os congestio-namentos dos canais usados.

A proposa do trabalho COMNET(COgnitive wireless Mesh NETwork) foi feita com base nacriação da sensibilidade cognitiva da leitura do espectro de transmissão. Nisso foi desenvol-vido técnicas de compartilhamento de banda, assim como serão os primeiros passos para extra-ção dos beneficios do uso de transmissão cognitiva na área da Redes Mesh (CHOWDHURY;AKYILDIZ, 2008).

6.9 Relação com os trabalhos

A descrição e aplicação do trabalho de Zhi-yuan, Ru-chuan e Jun-lei (2009) são semelhantesas deste trabalho. A pesquisa supracitada trabalha com caminhos previamente selecionadosde maneira pró-ativa. Ambos trabalhos utilizam a ideia de avaliar os caminhos, porém estapesquisa utiliza uma abordagem mais empírica da rede, deixando totalmente à rede a decisão

1Descrição em http://en.wikipedia.org/wiki/Bluetooth, acessado em 10/06/2012

63

de para qual node o pacote deve ir, ao invés de selecionar caminhos inteiros como alternativos.O trabalho de Venkataram, Ghosal e Kumar (2002) traz a implementação de uma RNA

dentro do roteamento de pacotes, e por isso, está diretamente relacionado com este trabalho.Assim como os autores, foi possível notar que a falta de uma RNA em tempo real implementadaa nível de hardware influencia diretamente no desempenho da rede, porém a diferença entre osestudos está que este trabalho emprega a RNA na decisão de encaminhar o pacote e o mesmobusca achar o melhor caminho. Como resultado seria possível unificar ambos os trabalhos egerar um algoritmo de roteamento utilizando RNA de maneira extensiva.

Já o trabalho de Song, Zhang e Fang (2010) trabalha o modelo de engenharia de tráfegopara possibilitar a busca de nodes com deficiências técnicas e evitar que o tráfego circule pelaárea em que o mesmo se encontra, assim habilitando que o objeto de pesquisa deste trabalhobusque com eficiência encontrar nodes que venham a apresentar. Considerando que na pesquisade De Couto et al. (2005) é demonstrado que, mesmo com grandes perdas, os nodes podemtransmitir com efetividade os pacotes, entretanto o mesmo não suporta cenários muitos caóticos.Neste quesito, esta pesquisa difere, pois sempre procura sempre flexibilização do roteamentonos piores cenários. O objeto utilizado do trabalho Pirzada e Portmann (2007) foi a priorizaçãodos nodes com estabilidade.

A pesquisa realizada em Koksal e Balakrishnan (2006) concentrou-se no roteamento depacotes, porém fica focado no uso eficiente da banda de transmissão, assim provendo ao rotea-mento boas métricas representando o estado real do lado físico da rede. A pesquisa influencioudiretamente na avaliação das métricas e no levantamento dos parâmetros de entrega de pacotes.O trabalho de Caleffi e Paura (2009) influênciou esta pesquisa com a ideia de estimar as métricasdos nodes utilizando RNA, tratando-as como séries temporais. Essa capacidade representativatrouxe benefícios na estimativa futura dos estados da rede. Com isso é possível trabalhar oroteamento sempre prevendo as condições em que os estados possam assumir.

64

65

7 CONSIDERAÇÕES FINAIS E TRABALHOS FUTUROS

Este trabalho apresentou uma nova abordagem do mecanismo de decisão no roteamento depacotes dentro das Redes Mesh utilizando o protocolo HWMP. O uso da capacidade cognitivano protocolo habilitou o processo de um nível empírico necessário para flexibilizar os caminhosem que o pacote deve percorrer, assim como o fluxo de carros nas cidades congestionadas, buscasempre formas alternativas de chegar ao destino evitando vias sobrecarregadas e lentas.

A flexibilização torna-se o foco principal quando é buscado o aumento significativo da qua-lidade da rede. Mesmo em casos que os dispositivos tenham alta mobilidade a rede deveráconseguir fornecer uma conexão de qualidade e evitar sobrecargas nas vias principais de co-municação, aumentando significativamente a qualidade da experiência do usuário no uso darede.

Essa abordagem foi fruto de uma pesquisa sobre neurociência, utilizando RNAs e conheci-mentos sobre o modelo de Rede Mesh. Essa pesquisa rendeu uma primeira aplicação da RNAdentro do processo de decisão e criou o norte para trabalhos futuros utilizando a capacidadecognitiva para aumentar a qualidade das Redes Mesh.

A pesquisa foi avalidada através de dados extraídos dos ajustes feitos ao mecanismo de ro-teamento. Foram analisados todos os dados gerados e construídos gráficos representando osresultados, apresentados no Capítulo 5. Esses resultados apresentaram números interessantessobre o roteamento cognitivo. A simulação foi feita utilizando o NS-3, apresentado no Capí-tulo 2.

Durante as simulações, observou-se que os fluxos de informação, ao sobrecarregarem osmesh clients envolvidos acabavam afetando diretamente as métricas de avaliação do desem-penho da rede. Assim, os resultados finais da rede podem ser observados nos gráficos da Fi-gura 23(c), Figura 23(a) e Figura 23(b), representando efetivamente o aumento significativo daqualidade em cenários de constante alteração.

O aumento da qualidade dentro da rede é uma projeção da capacidade da RNA de identificare dispersar os pacotes de suas rotas principais, evitando possíveis congestionamentos e dirigindoo fluxo por caminhos alternativos. Esses caminhos servem como pontes de apoio aos caminhosprincipais dos fluxos, tentando evitar que congestionem ou inibindo a transmissão para umpossível mesh client que deixou de existir na rede.

Este resultado demonstra que as decisões da RNA ajudam, em muitos casos, a rede a mantera coesão e as taxas de entregas, diminuindo consideravelmente o tempo de espera na entrega depacotes (Figura 23(a)) e a quantidade de pacotes perdidos (Figura 23(b)). O resultado global darede, demonstrado no gráfico da Figura 23(c), é de que é possível utilizar as RNAs dentro doroteamento de pacotes ampliando o desempenho.

Como visto anteriormente, os resultados do roteamento de pacotes utilizando RNAs comomecanismo de decisão foram positivos. Os objetivos deste trabalho, representados na Tabela 4,foram atingidos parcialmente.

66

Objetivo AtendidoEstruturar Algoritmo de Roteamento XDefinir RNA XGerar Cenários NS3 XImplantar RNA dentro do NS3 XTestar RRDD na simulação XUtilizar RNA RRDD dentro do NS3 -Utilizar RNA Hopfield dentro do NS3 XSimular rede mesh XGerar saídas das métricas de roteamento XAvaliar resultados X

Tabela 4: Objetivos alcançados nesta pesquisa.

Com o resultado do processo de avaliação da simulação do protocolo modificado foi possívelvislumbrar um ganho de qualidade significativo para a conectividade da rede. Foi notável que oprocesso cognitivo de decisão pode auxiliar o roteamento, habilitando todo o mecanismo a serflexível o suficiente para suportar alterações bruscas e constantes dentro da topologia da rede.Flexibilidade esta tornada empírica já que as decisões são tomadas sem ter todo o conhecimentodo estado da rede.

A partir deste trabalho, é possível desenvolver outros estudos que acabem por complementarou mesmo estendê-lo, tais como:

• Habilitar a RNA a avaliar não somente um salto do pacote, mas sim habilitar os seis grausde separação e deixar com que a rede seja capaz de avaliar os seis saltos. Tal avaliaçãopode dar uma noção mais ampla do estado do caminho em que o pacote irá tomar;

• Alterar a RNA para não ter treinamento supervisionado e construir seu conhecimento apartir dos dados que trafegam no mesh client;

• Substituir a tabela de roteamento do protocolo HWMP por um estudo em que a RNApossa efetivamente funcionar como memória matricial, assim funcionando como a tabelade roteamento, aonde se apresenta o endereço de destino e a rede responde com os dadospara encaminhar o pacote;

• Estudar a viabilidade de testar o roteamento em um ambiente real, buscando avaliar comusuários a qualidade da rede, com isto será melhor avaliado a aplicação em escala real daRNA dentro de uma Rede Mesh;

• Propor uma implementação a nível de hardware da RNA para aumentar consideravel-mente o desempenho da execução da rede neural, tal implementação serve para retirar asobrecarga que ocorre ao executar a rede em nível de software, assim deixando o rotea-mento ainda mais rápido;

67

• Avaliar outras métricas que possam ser usadas como entradas da rede neural, assim comotambém o estado do espectro de transmissão, o tamanho do pacote a ser retransmitido, aquantidade de saltos que o mesmo precisa dar para chegar ao destino;

• Habilitar a RNA para avaliar também o nível de utilização do espectro de transmissão,com a finalidade de ampliar a visão da rede neural do ambiente em que o mesh client estápresente;

• Determinar a sobrecarga que a simulação causa, como também a execução da RNA coma rede. Verificar o impacto direto que ocorre e quanto difere a simulação de uma imple-mentação real.

68

69

REFERÊNCIAS

AKYILDIZ, I. F.; XUDONG, W. Wireless Mesh Networks. 2th. ed. [S.l.]: Willey, 2009.

AKYILDIZ, I.; WANG, X. A survey on wireless mesh networks. CommunicationsMagazine, IEEE, [S.l.], v. 43, n. 9, p. S23 – S30, sept. 2005.

BARANSEL, C.; DOBOSIEWICZ, W.; GBURZYNSKI, P. Routing in multihop packetswitching networks: gb/s challenge. Network, IEEE, [S.l.], v. 9, n. 3, p. 38 –61,may/jun 1995.

BAUMANN, R.; HEIMLICHER, S.; LENDERS, V.; MAY, M. Routing Packets into WirelessMesh Networks. In: WIRELESS AND MOBILE COMPUTING, NETWORKING ANDCOMMUNICATIONS, 2007. WIMOB 2007. THIRD IEEE INTERNATIONALCONFERENCE ON, 2007, White Plains, NY, USA. Anais. . . [S.l.: s.n.], 2007. p. 38.(WIMOB ’07).

BRAGA, A.; CARVALHO, A.; LUDEMIR, T. Redes Neurais Artificiais - Teorias eAplicações. 1th. ed. [S.l.]: LTC, 2007.

CALEFFI, M.; PAURA, L. Bio-inspired link quality estimation for wireless mesh networks.In: WOWMOM, 2009. Anais. . . IEEE, 2009. p. 1–6.

CHOWDHURY, K.; AKYILDIZ, I. Cognitive Wireless Mesh Networks with DynamicSpectrum Access. Selected Areas in Communications, IEEE Journal on, Edmonton, AB,Canadá, v. 26, n. 1, p. 168 –181, jan. 2008.

DE COUTO, D. S. J.; AGUAYO, D.; BICKET, J.; MORRIS, R. A high-throughput pathmetric for multi-hop wireless routing. Wirel. Netw., Hingham, MA, USA, v. 11, n. 4,p. 419–434, July 2005.

GIL, A. C. Como elaborar projetos de pesquisa. 3th. ed. [S.l.]: ATLAS, 2004.

GRANVILLE, L. Z.; CARISSIMI, A. D. S.; ROCHOL, J. Redes de Computadores. 20th. ed.[S.l.]: BOOKMAN COMPANHIA ED, 2009.

HAYKIN, S. Redes Neurais - Princípios e Prática. 2th. ed. [S.l.]: Bookman, 2001.

KOKSAL, C. E.; BALAKRISHNAN, H. Quality-aware routing metrics for time-varyingwireless mesh networks. IEEE JSAC, [S.l.], v. 24, p. 1984–1994, 2006.

LOESCH, C.; SARI, S. T. Redes Neurais Artificiais - Fundamentos e Modelos. 1th. ed.[S.l.]: FURB, 1996.

MARCONI, M. d. A.; EVA MARIA, L. Metodologia do Trabalho Científico. 7th. ed. [S.l.]:ATLAS, 2011.

PAUL, A.; KONWAR, S.; GOGOI, U.; CHAKRABORTY, A.; YESHMIN, N.; NANDI, S.Implementation and performance evaluation of AODV in Wireless Mesh Networks usingNS-3. In: EDUCATION TECHNOLOGY AND COMPUTER (ICETC), 2010 2NDINTERNATIONAL CONFERENCE ON, 2010. Anais. . . [S.l.: s.n.], 2010. v. 5, p. V5–298–V5–303.

70

PIRZADA, A. A.; PORTMANN, M. High Performance AODV Routing Protocol for HybridWireless Mesh Networks. In: FOURTH ANNUAL INTERNATIONAL CONFERENCE ONMOBILE AND UBIQUITOUS SYSTEMS: NETWORKING&SERVICES(MOBIQUITOUS), 2007., 2007, Washington, DC, USA. Proceedings. . . IEEE ComputerSociety, 2007. p. 1–5. (MOBIQUITOUS ’07).

SEVERINO, A. J. Metodologia do Trabalho Científico. 23th. ed. [S.l.]: Cortez Editora,2011.

SONG, Y.; ZHANG, C.; FANG, Y. Stochastic Traffic Engineering in Multihop CognitiveWireless Mesh Networks. Mobile Computing, IEEE Transactions on, [S.l.], v. 9, n. 3,p. 305 –316, march 2010.

VENKATARAM, P.; GHOSAL, S.; KUMAR, B. P. V. Neural network based optimal routingalgorithm for communication networks. Neural Netw., Oxford, UK, UK, v. 15, p. 1289–1298,December 2002.

ZHI-YUAN, L.; RU-CHUAN, W.; JUN-LEI, B. A Multipath Routing Algorithm Based onTraffic Prediction in Wireless Mesh Networks. In: NATURAL COMPUTATION, 2009. ICNC’09. FIFTH INTERNATIONAL CONFERENCE ON, 2009. Anais. . . [S.l.: s.n.], 2009. v. 6,p. 115 –119.

ZHU, F.; MUTKA, M.; NI, L. PrudentExposure: a private and user-centric service discoveryprotocol. In: PERVASIVE COMPUTING AND COMMUNICATIONS, 2004. PERCOM2004. PROCEEDINGS OF THE SECOND IEEE ANNUAL CONFERENCE ON, 2004.Anais. . . [S.l.: s.n.], 2004. p. 329 – 338.

71

APÊNDICE A INFORMAÇÕES COMPLEMENTARES

A.1 NS-3 Módulos

Os módulos abaixo apresentados foram utilizados em ordem para desenvolver e avaliar aaplicação da RNA no roteamento de pacotes.

A.1.1 HWMP Mac Header

A.1.1.1 MeshHeader::Serialize

Esta função serializa os dados de transmissão do frame da rede mesh. Foram adicionadosos parâmetros de estado do mesh client.

Retorno: void

Parâmetro: Buffer::Iterator start

A.1.1.2 MeshHeader::Deserialize

Lê a partir do dos dados transmitidos e codificados no cabeçalho do pacote.Retorno: uint32_t

Parâmetro: Buffer::Iterator start

A.1.2 HWMP Protocol

A.1.2.1 HwmpProtocol::fann_vld_dst

Este método foi desenvolvido com a finalidade de rodar a RNA e avaliar o estado do node.Retorno: bool

Parâmetro: Mac48Address node

Código:

// Caso a RNA apresentar resultados incoerents ao

//destino deve selecionar outro destio

HwmpRtable::LookupResult adr = m_rtable->GetResult(node);

//m_stats.totalQueued;

//Durante a primeira transmissão nao validar os nodes pois

//os mesmos não trocaram informações

if(adr.PDF == 0 && adr.TxDelay == 0){

return true;

}else{

72

fann_type addr_data[2];

addr_data[0] = adr.PDF;

addr_data[1] = adr.TxDelay;

fann_type *result = fann_run(ann, addr_data);

fann_abs(result[0] - addr_data[0]));

return (result[0] >= 0.5); //Sainda da RNA, se caso maior

// que 0.5 deixa enviar para o mesmo.

A.1.2.2 HwmpProtocol::RequestRoute

Este método possui a chamada para avaliar o node. Quando o mesmo requer uma rota paratransmitir o pacote, ela avalia cada um deles para saber se o mesmo está apto a encaminhar comsegurança. Caso o mesh client não seja válido, o algoritmo continua a procurar alternativas.

Retorno: bool

Parâmetros: uint32_t sourceIface, const Mac48Address source, const Mac48Address desti-

nation, Ptr<const Packet> constPacket, uint16_t protocolType, MeshL2RoutingProtocol::RouteReplyCallback

routeReply

A.1.3 HWMP Rtable

A.1.3.1 HwmpRtable::GetResult

Esta função retorna a busca por uma entrada específica, conforme o parâmetro a partir doMacAddress.

Retorno: HwmpRtable::LookupResult

Parâmetro: Mac48Address addr

A.1.4 HwmpRtable::updateNodeStats

Este método é executado cada vez que o mesh client se comunica com seus vizinhos. Oestado de cada vizinho é atualizado.

Retorno: void

Parâmetros: Mac48Address adr, uint16_t tx, uint16_t rx, uint8_t delay

73

ANEXO A NS-3 SCRIPTS

A.1 Cenário Base das Simulações

//#include "ns3/simulator-module.h"

//#include "ns3/node-module.h"

//#include "ns3/helper-module.h"

//#include "ns3/global-routing-module.h"

#include "ns3/wifi-module.h"

#include "ns3/mesh-module.h"

#include "ns3/mobility-module.h"

#include "ns3/mesh-helper.h"

#include "ns3/mesh-module.h"

#include "ns3/wifi-phy.h"

#include "ns3/flow-monitor.h"

#include "ns3/flow-monitor-helper.h"

#include "ns3/ipv4-flow-classifier.h"

#include "ns3/random-variable.h"

#include <iostream>

#include <sstream>

#include <fstream>

#include <vector>

#include "ns3/core-module.h"

#include "ns3/internet-module.h"

#include "ns3/network-module.h"

#include "ns3/applications-module.h"

#include "ns3/wifi-module.h"

#include "ns3/mesh-module.h"

#include "ns3/mobility-module.h"

#include "ns3/mesh-helper.h"

#include "tcc_cenario_simples.h"

#include <iostream>

#include <sstream>

#include <fstream>

#include <vector>

74

using namespace ns3;

class MeshTest

{

public:

// Init test

MeshTest ();

// Configure test from command line arguments

void Configure (int argc, char ** argv);

// Run test

int Run ();

private:

int m_xSize; //x size of the grid

int m_ySize; //y size of the grid

double m_step; //separation between nodes

double m_randomStart;

double m_totalTime;

uint16_t m_packetSize;

uint32_t m_nIfaces;

bool m_chan;

bool m_pcap;

std::string m_stack;

std::string m_txrate;

//to calculate the lenght of the simulation

float m_timeTotal, m_timeStart, m_timeEnd;

// List of network nodes

NodeContainer nodes;

// List of all mesh point devices

NetDeviceContainer meshDevices;

// Addresses of interfaces:

Ipv4InterfaceContainer interfaces;

// MeshHelper. Report is not static methods

MeshHelper mesh;

private:

// Create nodes and setup their mobility

void CreateNodes ();

// Install internet m_stack on nodes

void InstallInternetStack ();

// Install applications randomly

void InstallApplicationRandom ();

75

// Print mesh devices diagnostics

void Report ();

};

MeshTest::MeshTest () :

m_xSize (5),

m_ySize (5),

m_step (170),

//m_randomStart (0.1),

m_randomStart (100),

m_totalTime (240),

m_packetSize (1024),

m_nIfaces (1),

m_chan (false),

m_pcap (false),

m_stack ("ns3::Dot11sStack"),

m_txrate ("200kbps")

{ }

void

MeshTest::Configure (int argc, char *argv[])

{

CommandLine cmd;

cmd.AddValue ("m_xSize", "m_xSize", m_xSize);

cmd.AddValue ("m_ySize", "m_ySize", m_ySize);

cmd.AddValue ("m_txrate", "m_txrate", m_txrate);

cmd.Parse (argc, argv);

}

void MeshTest::CreateNodes ()

{

int i, j;

double m_txpower = 18.0; // dbm

// Calculate m_ySize*m_xSize stations grid topology

double position_x = 0;

double position_y = 0;

ListPositionAllocator myListPositionAllocator;

for (i = 1; i <= m_xSize; i++){

for (j = 1; j <= m_ySize; j++){

std::cout << "Node at x = " << position_x << ", y = "

<< position_y << "\n";

76

Vector3D n_pos (position_x, position_y, 0.0);

myListPositionAllocator.Add(n_pos);

position_y += m_step;

}

position_y = 0;

position_x += m_step;

}

// Create the nodes

nodes.Create (m_xSize*m_ySize);

// Configure YansWifiChannel

YansWifiPhyHelper WifiPhy = YansWifiPhyHelper::Default ();

WifiPhy.Set ("EnergyDetectionThreshold", DoubleValue (-89.0) );

WifiPhy.Set ("CcaMode1Threshold", DoubleValue (-62.0) );

WifiPhy.Set ("TxGain", DoubleValue (1.0) );

WifiPhy.Set ("RxGain", DoubleValue (1.0) );

WifiPhy.Set ("TxPowerLevels", UintegerValue (1) );

WifiPhy.Set ("TxPowerEnd", DoubleValue (m_txpower) );

WifiPhy.Set ("TxPowerStart", DoubleValue (m_txpower) );

WifiPhy.Set ("RxNoiseFigure", DoubleValue (7.0) );

YansWifiChannelHelper WifiChannel;

WifiChannel.SetPropagationDelay

("ns3::ConstantSpeedPropagationDelayModel");

WifiChannel.AddPropagationLoss

("ns3::LogDistancePropagationLossModel","Exponent",

StringValue ("2.7"));

WifiPhy.SetChannel (WifiChannel.Create ());

// Configure the parameters of the Peer Link

Config::SetDefault ("ns3::dot11s::PeerLink::MaxBeaconLoss",

UintegerValue (20));

Config::SetDefault ("ns3::dot11s::PeerLink::MaxRetries",

UintegerValue (4));

Config::SetDefault ("ns3::dot11s::PeerLink::MaxPacketFailure",

UintegerValue (5));

// Configure the parameters of the Peer Management Protocol

//Config::SetDefault ("ns3::dot11s::PeerManagementProtocol::

EnableBeaconCollision-Avoidance",BooleanValue (false));

Config::SetDefault ("ns3::dot11s::PeerManagementProtocol::

EnableBeaconCollisionAvoidance",BooleanValue (false));

77

// Configure the parameters of the HWMP

Config::SetDefault ("ns3::dot11s::HwmpProtocol::

Dot11MeshHWMPactivePathTimeout",

TimeValue (Seconds (100)));

Config::SetDefault ("ns3::dot11s::HwmpProtocol::

Dot11MeshHWMPactiveRootTimeout",

TimeValue (Seconds (100)));

Config::SetDefault ("ns3::dot11s::HwmpProtocol::

Dot11MeshHWMPmaxPREQretries",

UintegerValue (5));

Config::SetDefault ("ns3::dot11s::HwmpProtocol::

UnicastPreqThreshold",

UintegerValue (10));

Config::SetDefault ("ns3::dot11s::HwmpProtocol::

UnicastDataThreshold",

UintegerValue (5));

Config::SetDefault("ns3::dot11s::HwmpProtocol::DoFlag",

BooleanValue (true));

Config::SetDefault ("ns3::dot11s::HwmpProtocol::RfFlag",

BooleanValue (false));

// Stack installer creates all protocols and install them to mesh point device

mesh = MeshHelper::Default ();

mesh.SetStandard (WIFI_PHY_STANDARD_80211a);

mesh.SetMacType ("RandomStart",

TimeValue (Seconds(m_randomStart)));

mesh.SetRemoteStationManager("ns3::ConstantRateWifiManager",

"DataMode", StringValue ("OfdmRate6Mbps"),

"RtsCtsThreshold", UintegerValue (2500));

// Set number of interfaces - default is

//single-interface mesh point

mesh.SetNumberOfInterfaces (m_nIfaces);

mesh.SetStackInstaller (m_stack);

//If multiple channels is activated

if (m_chan) {

mesh.SetSpreadInterfaceChannels

(MeshHelper::SPREAD_CHANNELS);

}

else {

mesh.SetSpreadInterfaceChannels

78

(MeshHelper::ZERO_CHANNEL);

}

// Install protocols and return container if MeshPointDevices

meshDevices = mesh.Install (WifiPhy, nodes);

// Place the protocols in the positions calculated before

MobilityHelper mobility;

mobility.SetPositionAllocator(&myListPositionAllocator);

mobility.SetMobilityModel

("ns3::ConstantPositionMobilityModel");

mobility.Install (nodes);

}

void MeshTest::InstallInternetStack ()

{

//Install the internet protocol stack on all nodes

InternetStackHelper internetStack;

internetStack.Install (nodes);

//Assign IP addresses to the devices interfaces

Ipv4AddressHelper address;

address.SetBase ("192.168.1.0", "255.255.255.0");

interfaces = address.Assign (meshDevices);

}

void MeshTest::InstallApplicationRandom ()

{

// Create as many connections as nodes has the grid

int m_nconn = m_xSize * m_ySize;

int i=0;

int m_source, m_dest, m_dest_port;

char num [2];

char onoff [7];

char sink [6];

double start_time, stop_time, duration;

// Set the parameters of the onoff application

Config::SetDefault ("ns3::OnOffApplication::PacketSize",

UintegerValue

(m_packetSize));

79

Config::SetDefault ("ns3::OnOffApplication::DataRate",

StringValue (m_txrate));

ApplicationContainer apps [m_nconn];

UniformVariable rand_nodes (0,m_ySize*m_xSize-1);

UniformVariable rand_port (49000,49100);

// 50 seconds for transitori are left at the beginning.

UniformVariable a(50,m_totalTime-15);

for (i = 0; i < m_nconn; i++){

start_time = a.GetValue();

ExponentialVariable b(30);

duration = b.GetValue()+1;

// If the exponential variable gives us a value

//that added to the start time

// is greater than the maximum permitted, this

//is changed for the maximum

// 10 seconds are left at the end to calculate

//well the statistics of each flow

if ( (start_time + duration) > (m_totalTime - 10)){

stop_time = m_totalTime-10;

}else{

stop_time = start_time + duration;

}

// Create different names for the connections

// (we can not use vectors for OnOffHelper)

strcpy(onoff,"onoff");

strcpy(sink,"sink");

sprintf(num,"%d",i);

strcat(onoff,num);

strcat(sink,num);

// Set random variables of the destination

//(server) and destination port.

m_dest = rand_nodes.GetInteger (0,m_ySize*m_xSize-1);

m_dest_port = rand_port.GetInteger (49000,49100);

// Set random variables of the source (client)

m_source = rand_nodes.GetInteger (0,m_ySize*m_xSize-1);

// Client and server can not be the same node.

80

while (m_source == m_dest){

m_source = rand_nodes.GetInteger (0,m_ySize*m_xSize-1);

}

// Plot the connection values

std::cout << "\n\t Node "<< m_source << " to " << m_dest;

std::cout << "\n Start_time: " << start_time << "s";

std::cout << "\n Stop_time: " << stop_time << "s\n";

// Define UDP traffic for the onoff application

OnOffHelper onoff ("ns3::UdpSocketFactory",

Address (InetSocketAddress

(interfaces.GetAddress (m_dest), m_dest_port)));

onoff.SetAttribute ("OnTime",

RandomVariableValue (ConstantVariable (1)));

onoff.SetAttribute ("OffTime",

RandomVariableValue (ConstantVariable (0)));

apps[i] = onoff.Install (nodes.Get(m_source));

apps[i].Start (Seconds (start_time));

apps[i].Stop (Seconds (stop_time));

// Create a packet sink to receive the packets

PacketSinkHelper sink ("ns3::UdpSocketFactory",

InetSocketAddress

(interfaces.GetAddress (m_dest), 49001));

apps[i] = sink.Install (nodes.Get (m_dest));

apps[i].Start (Seconds (1.0));

}

}

int MeshTest::Run ()

{

CreateNodes ();

InstallInternetStack ();

InstallApplicationRandom ();

// Install FlowMonitor on all nodes

FlowMonitorHelper flowmon;

Ptr<FlowMonitor> monitor = flowmon.InstallAll();

m_timeStart=clock();

Simulator::Schedule (Seconds(m_totalTime),

& MeshTest::Report, this);

Simulator::Stop (Seconds (m_totalTime));

81

Simulator::Run ();

// Define variables to calculate the metrics

int k=0;

int totaltxPackets = 0;

int totalrxPackets = 0;

double totaltxbytes = 0;

double totalrxbytes = 0;

double totaldelay = 0;

double totalrxbitrate = 0;

double difftx, diffrx;

double pdf_value, rxbitrate_value,

txbitrate_value,

delay_value;

double pdf_total, rxbitrate_total, delay_total;

//Print per flow statistics

monitor->CheckForLostPackets ();

Ptr<Ipv4FlowClassifier> classifier =

DynamicCast<Ipv4FlowClassifier>

(flowmon.GetClassifier ());

std::map<FlowId, FlowMonitor::FlowStats> stats =

monitor->GetFlowStats ();

std::ostringstream osFlow;

osFlow << "TCC_FLOW_TABLE.txt";

std::ofstream ofFlow (osFlow.str().c_str(),

ios::out | ios::app);

ofFlow << "IPs;";

ofFlow << "FLOW;";

ofFlow << "txPackets;";

ofFlow << "rxPackets;";

ofFlow << "lostPackets;";

ofFlow << "DropedPackets;";

ofFlow << "PDF;";

ofFlow << "Delay;";

ofFlow << "rxBitrate;";

ofFlow << "txBitrate;\n";

82

for (std::map<FlowId, FlowMonitor::FlowStats>::const_iterator i = stats.begin ();

i != stats.end (); ++i)

{

Ipv4FlowClassifier::FiveTuple t = classifier->FindFlow (i->first);

difftx = i->second.timeLastTxPacket.GetSeconds() -

i->second.timeFirstTxPacket.GetSeconds();

diffrx = i->second.timeLastRxPacket.GetSeconds() -

i->second.timeFirstRxPacket.GetSeconds();

pdf_value = (double) i->second.rxPackets /

(double) i->second.txPackets * 100;

txbitrate_value = (double) i->second.txBytes

* 8 / 1024 / difftx;

if (i->second.rxPackets != 0){

rxbitrate_value = (double)i->second.rxPackets

* m_packetSize * 8 /

1024 / diffrx;

delay_value = (double) i->second.delaySum.GetSeconds() /

(double) i->second.rxPackets;

} else{

rxbitrate_value = 0;

delay_value = 0;

}

// We are only interested in the metrics of the data flows

if ((!t.destinationAddress.

IsSubnetDirectedBroadcast("255.255.255.0")))

{

k++;

ofFlow << t.sourceAddress << " -> "

<< t.destinationAddress << ";";

ofFlow << k << ";";

ofFlow << i->second.txPackets << ";";

ofFlow << i->second.rxPackets << ";";

ofFlow << i->second.lostPackets << ";";

ofFlow << i->second.packetsDropped.size() << ";";

ofFlow << pdf_value << ";";

ofFlow << delay_value << ";";

ofFlow << rxbitrate_value << ";";

ofFlow << txbitrate_value << ";\n";

83

// Plot the statistics for each data flow

std::cout << "\nFlow " << k << " ("

<< t.sourceAddress << " -> "

<< t.destinationAddress << ")\n";

//

/*std::cout << "tx Preq Packets: "

<< i->second.txPreq << "\n";

std::cout << "rx Preq Packets: "

<< i->second.rxPreq << "\n";

std::cout << "tx Mgt Packets: " <

< i->second.txMgt << "\n";

std::cout << "tx Mgt Bytes Packets: "

<< i->second.txMgtBytes << "\n";

std::cout << "rx Mgt Packets: "

<< i->second.rxMgt << "\n";

std::cout << "rx Mgt Bytes Packets: "

<< i->second.rxMgtBytes << "\n";*/

std::cout << "Tx Packets: "

<< i->second.txPackets << "\n";

std::cout << "Rx Packets: "

<< i->second.rxPackets << "\n";

std::cout << "Lost Packets: "

<< i->second.lostPackets << "\n";

std::cout << "Dropped Packets: "

<< i->second.packetsDropped.size() << "\n";

std::cout << "PDF: "

<< pdf_value << " %\n";

std::cout << "Average delay: "

<< delay_value << "s\n";

std::cout << "Rx bitrate: "

<< rxbitrate_value << " kbps\n";

std::cout << "Tx bitrate: "

<< txbitrate_value << " kbps\n\n";

84

// Acumulate for average statistics

totaltxPackets += i->second.txPackets;

totaltxbytes += i->second.txBytes;

totalrxPackets += i->second.rxPackets;

totaldelay += i->second.delaySum.GetSeconds();

totalrxbitrate += rxbitrate_value;

totalrxbytes += i->second.rxBytes;

} }

// Average all nodes statistics

if (totaltxPackets != 0){

pdf_total = (double) totalrxPackets

/ (double) totaltxPackets * 100;

}

else{

pdf_total = 0;

}

if (totalrxPackets != 0){

rxbitrate_total = totalrxbitrate;

delay_total = (double) totaldelay

/ (double) totalrxPackets;

} else{

rxbitrate_total = 0;

delay_total = 0;

}

//print all nodes statistics

ofFlow << "\nTotal PDF: "

<< pdf_total << " %\n";

ofFlow << "Total Rx bitrate: "

<< rxbitrate_total << " kbps\n";

ofFlow << "Total Delay: "

<< delay_total << " s\n";

ofFlow << "\nTotal PDF: "

<< pdf_total << " %\n";

ofFlow << "Total Rx bitrate: "

<< rxbitrate_total << " kbps\n";

ofFlow << "Total Delay: "

<< delay_total << " s\n";

85

ofFlow.close ();

//print all nodes statistics in files

std::ostringstream os;

os << "1_HWMP_PDF.txt";

std::ofstream of (os.str().c_str(),

ios::out | ios::app);

of << pdf_total << "\n";

of.close ();

std::ostringstream os2;

os2 << "1_HWMP_Delay.txt";

std::ofstream of2 (os2.str().c_str(),

ios::out | ios::app);

of2 << delay_total << "\n";

of2.close ();

std::ostringstream os3;

os3 << "1_HWMP_Throu.txt";

std::ofstream of3 (os3.str().c_str(),

ios::out | ios::app);

of3 << rxbitrate_total << "\n";

of3.close ();

Simulator::Destroy ();

m_timeEnd=clock();

m_timeTotal=(m_timeEnd - m_timeStart)

/(double) CLOCKS_PER_SEC;

std::cout << "\n*** Simulation time: "

<< m_timeTotal << "s\n\n";

return 0;

}

void MeshTest::Report ()

{

// Using this function we print detailed

86

//statistics of each mesh point device

// These statistics are used later with

//an AWK files to extract routing metrics

unsigned n (0);

for (NetDeviceContainer::Iterator i = meshDevices.Begin ();

i != meshDevices.End (); ++i, ++n)

{

std::ostringstream os;

//os << "mp-report1-" << n << ".xml";

os << "mp-report.xml";

std::ofstream of;

of.open (os.str().c_str(),

ios::out | ios::app);

if (! of.is_open ())

{

std::cerr << "Error: Can’t open file "

<< os.str() << "\n";

return;

}

mesh.Report (*i, of);

of.close ();

}

n = 0;

}

int main (int argc, char *argv[])

{

MeshTest t;

t.Configure (argc, argv);

return t.Run();

}