Provisionamento de QoS Em Redes Ad Hoc Sem Fio Utilizando Medição de Retardo de Enlace TCC Weverton

UNIVERSIDADE FEDERAL DO PARCENTRO DE CINCIAS EXATAS E NATURAIS

COLEGIADO DO CURSO DE CINCIA DA COMPUTAO

Weverton Luis da Costa Cordeiro

Provisionamento de Qualidade de Servio em Redes Ad Hoc Sem Fio Utilizando Medio de

Retardo de Enlace

Belm

2007

UNIVERSIDADE FEDERAL DO PARCENTRO DE CINCIAS EXATAS E NATURAIS




Retardo de Enlace

Trabalho de Concluso de Curso

apresentado para obteno do grau

de Bacharel em Cincia da

Computao.

Orientador: Prof. Dr. Antnio Jorge

Gomes Abelm

Belm

2007

2UNIVERSIDADE FEDERAL DO PARCENTRO DE CINCIAS EXATAS E NATURAIS




Retardo de Enlace

Trabalho de Concluso de Curso apresentado para obteno

do grau de Bacharel em Cincia da Computao.

Data da defesa: 23/02 /2007

Conceito: ExcelenteBanca Examinadora

Prof. Dr. Antnio Jorge Gomes AbelmDepartamento de Informtica/UFPA - Orientador

Prof. Dr. Kelvin Lopes Dias

Departamento de Engenharia Eltrica e Computao /UFPA - Membro

Prof. Msc. Elisngela Santana AguiarUniversidade da Amaznia - Membro

3Aos meus pais, Weliton de Lima

Cordeiro e Ana Margarete da

Costa Cordeiro, meus irmos

Werley da Costa Cordeiro e Lis

Marina da Costa Cordeiro. Minha

tia Marins Vieira da Costa e

Aldete das Graas Serra da Costa

e Ladislau Cavalheiro da Costa.

4AGRADECIMENTOS

Agradeo primeiramente a Deus por todas as oportunidades que Ele me

ofereceu, desde o incio em Itaituba, Par, at o presente momento. Bem sei que

tudo o que consegui em toda a minha vida foi com a ajuda dEle, e que Ele sempre esteve e sempre estar comigo durante toda a minha vida. Toda a honra e toda a

glria seja dada ao Nosso Senhor Jesus Cristo.

Agradeo aos meus pais, Weliton e Ana Margarete, e meus irmos Werley e

Lis Marina, pelo apoio incondicional que sempre tive em todos os momentos da

minha vida. Quero que vocs saibam que eles so muito especiais para mim.

Agradeo minha tia Marins Vieira da Costa, a qual foi a primeira pessoa

a me apoiar aqui em Belm, tanto materialmente quanto espiritualmente.

Agradeo a Deus por ter colocado a senhora no meu caminho.

Agradeo tambm Aldete das Graas e ao Ladislau Cavalheiro da Costa,

os quais me adotaram como um filho durante a minha estadia em Belm. Meus

especiais agradecimentos tambm Ana Carolina Serra da Costa, Anderson Jorge

Serra da Costa e Maria Auxiliadora da Silva Tavares.

Aos professores Antnio Jorge Gomes Abelm, Carla Alessandra Lima Reis

e Rodrigo Quites Reis, pela grande e valorosa amizade e pelo apoio prestado durante todo o curso.

Por fim, agradeo a todos que sempre estiveram comigo durante esses

cinco anos, especialmente aos meus grandes amigos do GERCOM e do LABES.

Tambm aos meus amigos e colegas da universidade, pessoas com quem

compartilhei inesquecveis momentos . Muito obrigado a todos.

5I haven't failed. I've just found 10,000 ways that don't work.

Thomas Alva Edison

You'll never get to heaven if

you're scared of gettin' high...

Kylie Minogue

The important thing is not to

stop questioning.

Albert Einstein

With men this is impossible: but

with God all things are possible.

Matthew 19:26

6SUMRIO

LISTA DE TABELAS......................................................................................................................8LISTA DE FIGURAS......................................................................................................................9LISTA DE SIGLAS......................................................................................................................11RESUMO..................................................................................................................................13ABSTRACT...............................................................................................................................14

1. INTRODUO .......................................................................................................................15

1.1. MOTIVAO......................................................................................................................161.2. OBJETIVOS........................................................................................................................18

1.3. ORGANIZAO...................................................................................................................18

2. PROTOCOLOS DE ROTEAMENTO PARA REDES AD HOC SEM FIO..................................................202.1. TIPOS DE PROTOCOLOS DE ROTEAMENTO PARA REDES AD HOC...............................................21

2.1.1. Protocolos Pr- Ativos ..........................................................................................21

2.1.2. Protocolos Reativos ...............................................................................................22

2.1.3. Protocolos Hbridos ..............................................................................................23

2.2. ANLISE COMPARATIVA......................................................................................................24

2.3. CONSIDERAES FINAIS DO CAPTULO...................................................................................27

3. ESTIMATIVA DE CAPACIDADE DE ENLACE................................................................................283.1. TCNICAS ATIVAS..............................................................................................................30

3.1.1. CapProbe ..................................................................................................................31

3.1.2. AdHoc Probe ...........................................................................................................32

3.1.2.1. Problema de Sincronizao do Relgio do Sistema ...............................33

3.2. TCNICAS PASSIVAS............................................................................................................34

3.2.1. TFRC Probe ..............................................................................................................353.2.2. TCP Probe ................................................................................................................36

3.3. ANLISE COMPARATIVA......................................................................................................37

3.4. CONSIDERAES FINAIS DO CAPTULO...................................................................................38

4. O PROTOCOLO DE ROTEAMENTO OLSR................................................................................39

74.1. EXTENSES PARA O PROTOCOLO OLSR................................................................................43

4.1.1. Alteraes no Algoritmo de Seleo de MPRs...............................................44

4.1.2. QOLSR.......................................................................................................................454.1.3. OLSR- ETX................................................................................................................48

4.1.3.1. A Mtrica ETX..................................................................................................48

4.1.3.2. O Protocolo OLSR- ETX..................................................................................52

4.1.4. OLSR- ML..................................................................................................................544.2. CONSIDERAES FINAIS DO CAPTULO...................................................................................57

5. UMA EXTENSO PARA O PROTOCOLO OLSR BASEADO NA MTRICA DE RETARDO DE TRANSMISSO DO ENLACE.........................................................................................................58

5.1. EXTENSO PROPOSTA.........................................................................................................595.2. CONSIDERAES FINAIS DO CAPTULO...................................................................................64

6. ESTUDO DE CASO................................................................................................................656.1. O PROJETO REMESH..........................................................................................................656.2. O CENRIO ESTUDADO E CONFIGURAES DA SIMULAO......................................................666.3. METODOLOGIA EMPREGADA.................................................................................................696.4. ANLISE DOS RESULTADOS..................................................................................................70

6.4.1. Avaliao do Atraso Mdio .................................................................................736.4.2. Avaliao do Jitter Mdio ....................................................................................766.4.3. Avaliao da Vazo Mdia ...................................................................................806.4.3. Avaliao da Probabilidade Mdia de Bloqueio .............................................84

6.5. CONSIDERAES FINAIS DO CAPTULO...................................................................................877. CONCLUSES.......................................................................................................................88

7.1. RESUMO DAS CONTRIBUIES..............................................................................................88

7.2. ANLISE CRTICA DO MODELO............................................................................................897.3. QUESTES ABERTAS E TRABALHOS FUTUROS.........................................................................907.4. CONSIDERAES FINAIS.......................................................................................................91

REFERNCIAS BIBLIOGRFICAS....................................................................................................93

8LISTA DE TABELAS

TABELA 2.1: PROTOCOLOS DE ROTEAMENTO PR- ATIVOS.............................................................25

TABELA 2.2: PROTOCOLOS DE ROTEAMENTO REATIVOS.................................................................26TABELA 2.3: PROTOCOLOS DE ROTEAMENTO PR- ATIVOS.............................................................27TABELA 3.1: ALGORITMOS DE ESTIMATIVA DE CAPACIDADE DE ENLACE...........................................38TABELA 6.1: PARMETROS UTILIZADOS NA SIMULAO...............................................................67TABELA 6.2: CONFIGURAO DAS CHAMADAS VOIP..................................................................69TABELA 6.3: CONFIGURAO DOS TRFEGOS DE SEGUNDO PLANO................................................70

9LISTA DE FIGURAS

FIGURA 1.1: EXEMPLO DE REDE AD HOC. AS ARESTAS INDICAM A CONECTIVIDADE BIDIRECIONAL ENTRE

OS COMPUTADORES DA REDE.......................................................................................................16FIGURA 4.1: FORMATO BSICO DE UM PACOTE DE CONTROLE DO OLSR (CLAUSEN, 2003) ............39FIGURA 4.2: ALGORITMO DE SELEO DE MPRS DO PROTOCOLO OLSR TRADICIONAL (LEGUAY, 2006) ...................................................................................................................................41FIGURA 4.3: MENSAGEM HELLO (A) CAMPO DIVULGANDO INFORMAES SOBRE GRUPO DE VIZINHOS DO N ATUAL. (B) FORMATO DO CAMPO DE CDIGO DO ENLACE, CONTIDO NA MENSAGEM HELLO, INFORMANDO QUAL O TIPO DE COMUNICAO QUE EXISTE ENTRE O N ATUAL E O GRUPO DE VIZINHOS

SUBSEQUENTES (CLAUSEN, 2003) ..............................................................................................42FIGURA 4.4: FORMATO DA MENSAGEM DE CONTROLE DE TOPOLOGIA (TC) DEFINIDA PELO PROTOCOLO OLSR (CLAUSEN, 2003) ........................................................................................................42FIGURA 4.5: ALGORITMO DE SELEO DE MPRS DO PROTOCOLO QOLSR (LEGUAY, 2006) ........46FIGURA 4.6: REDE AD HOC SIMPLES FORMADA POR 4 ESTAES....................................................51FIGURA 4.7: NOVO FORMATO DA MENSAGEM HELLO, LQ_HELLO...........................................53FIGURA 4.8: NOVO FORMATO DA MENSAGEM TC, LQ_TC.........................................................54FIGURA 4.9: REDE AD HOC COMPOSTA POR QUATRO ESTAES......................................................55FIGURA 5.1: PACOTE OLSR COM INFORMAES GERADAS PELO ALGORITMO ADHOC PROBE...........61FIGURA 5.2: MENSAGEM OLSR HELLO COM INFORMAES SOBRE RETARDO DE TRANSMISSO.......62FIGURA 5.3: MENSAGEM OLSR TC COM INFORMAES SOBRE RETARDO DE TRANSMISSO..............62FIGURA 6.1: CENRIO UTILIZADO PARA EXPERIMENTAO (AGUIAR, 2006) ................................68FIGURA 6.2: VISO GERAL DO DESEMPENHO DOS PROTOCOLOS.......................................................71FIGURA 6.3: PROBABILIDADE DE BLOQUEIO MEDIDA EM CADA UM DOS PROTOCOLOS..........................72FIGURA 6.4: ATRASO MDIO DAS CHAMADAS VOIP NO PROTOCOLO OLSR...................................73FIGURA 6.5: ATRASO MDIO DAS CHAMADAS VOIP NO PROTOCOLO OLSR- ETX.........................73FIGURA 6.6: ATRASO MDIO DAS CHAMADAS VOIP NO PROTOCOLO OLSR- ML...........................74FIGURA 6.7: ATRASO MDIO DAS CHAMADAS VOIP NO PROTOCOLO OLSR- LD...........................74FIGURA 6.8: GRFICO DE TENDNCIA DE ATRASO PARA CADA UM DOS FLUXOS DE CHAMADA VOIP...75

10

FIGURA 6.9: JITTER MDIO DAS CHAMADAS VOIP NO PROTOCOLO OLSR.....................................77FIGURA 6.10: JITTER MDIO DAS CHAMADAS VOIP NO PROTOCOLO OLSR- ETX.........................77FIGURA 6.11: JITTER MDIO DAS CHAMADAS VOIP NO PROTOCOLO OLSR- ML...........................78FIGURA 6.12: JITTER MDIO DAS CHAMADAS VOIP NO PROTOCOLO OLSR- LD...........................78FIGURA 6.13: GRFICO DE TENDNCIA DE JITTER PARA CADA UM DOS FLUXOS DE CHAMADA VOIP...79FIGURA 6.14: VAZO MDIA DAS CHAMADAS VOIP NO PROTOCOLO OLSR..................................81FIGURA 6.15: VAZO MDIA DAS CHAMADAS VOIP NO PROTOCOLO OLSR- ETX........................81FIGURA 6.16: VAZO MDIA DAS CHAMADAS VOIP NO PROTOCOLO OLSR- ML..........................82FIGURA 6.17: VAZO MDIA DAS CHAMADAS VOIP NO PROTOCOLO OLSR- LD..........................82FIGURA 6.18: GRFICO DE TENDNCIA DE VAZO PARA CADA UM DOS FLUXOS DE CHAMADA VOIP. .83FIGURA 6.19: PROBABILIDADE MDIA DE BLOQUEIO NO PROTOCOLO OLSR....................................84FIGURA 6.20: PROBABILIDADE MDIA DE BLOQUEIO PROTOCOLO OLSR- ETX...............................85FIGURA 6.21: PROBABILIDADE MDIA DE BLOQUEIO NO PROTOCOLO OLSR- ML............................85FIGURA 6.22: PROBABILIDADE MDIA DE BLOQUEIO NO PROTOCOLO OLSR- LD............................86FIGURA 6.23: GRFICO DE TENDNCIA DE PROBABILIDADE DE BLOQUEIO PARA CADA UM DOS FLUXOS DE CHAMADA VOIP......................................................................................................................86

11

LISTA DE SIGLAS

ACK AcknowlegdementADR Average Dispersion Rate

AODV Ad Hoc On Demand Distance VectorAP Access Point

CGSR Clusterhead Gateway Switch RoutingDARPA Defense Advanced Research Projects AgencyDSDV Destination Sequenced Distance VectorDSR Dynamic Source RoutingETX Estimated Transmission Count

IEEE Institute of Electrical and Electronics Engineers

IETF Internet Engineerig Task Force

IP Interet Protocol

LANMAR LandMark AdHoc Routing

LQ Link QualityMAC Media Access ControlML Minimum Losses

MPR MultiPoint Relay

MTU Maximum Transfer Unit

NLQ Neighbor Link QualityPSH PushOLSR Optimized Link State RoutingOWD One Way delayQoS Quality of ServiceQOLSR QoS- enhanced OLSRRDMAR Relative Distance Microdiversity Routing

RFC Request for CommentsRNP Rede Nacional de Ensino e Pesquisa

12

RTS Retardo de Transmisso SuavizadoRTT Round Trip Time

SHARP Sharp Hybrid Adaptive Routing ProtocolSSNR Smoothed Signal to Noise RatioSSR Signal Stability RoutingSTAR Source Tree Adaptive RoutingTC Topology ControlTCP Transmission Control ProtocolTFRC TCP- Friendly Rate ControlTORA Temporary Ordered Routing AlgorithmTTL Time to Live

UDP User Datagram Protocol

UFF Universidade Federal Fluminense

UFPA Universidade Federal do Par

VoIP Voice Over IP

WLAN Wireless Local Area Network

WRP Wireless Routing Protocol

ZRP Zone Routing Protocol

13

RESUMO

Redes ad hoc sem fio so redes formadas espontaneamente e que no

possuem uma infra- estrutura central de acesso, por exemplo um ponto de acesso

(do ingls Access Point, AP). Existem diversas propostas de protocolos de roteamento na literatura especficos para este tipo de redes. Entretanto, no

existe atualmente um protocolo de roteamento perfeitamente adequado aos

diferentes cenrios de aplicao.

Um dos principais problemas existentes neste tipo de rede prover

garantias de qualidade de servios especficas para aplicaes multimdia,

principalmente devido a fatores como o desvanecimento do sinal de rdio entre

os ns da rede e a mobilidade dos mesmos.

Uma idia para melhorar a qualidade de servio em redes ad hoc prover

ao algoritmo de roteamento mtricas que indiquem o retardo de transmisso, de

modo que enlaces com menor retardo sejam utilizados na composio de rotas.Neste trabalho apresentada uma modificao ao protocolo Optimized

Link State Routing (OLSR), um dos principais protocolos de roteamento para redes ad hoc , baseada em um algoritmo para o clculo do retardo de transmisso

entre ns participantes da rede. Simulaes da proposta realizadas com o

objetivo de validar a proposta feita neste trabalho mostraram que protocolo OLSR- Link Delay, a proposta de extenso ao OLSR deste trabalho, teve um

desempenho consideravelmente superior em relao ao OLSR original em termos

de vazo, atraso, variao de atraso e probabilidade de bloqueio.

PALAVRAS- CHAVE : Redes Ad Hoc Mveis Sem Fio, OLSR, Qualidade de Servio, Retardo de Transmisso do Enlace.

14

ABSTRACT

Wireless ad hoc network is a temporally and self- organized network

without the aid of any established infrastructure or centralized administration,

for example an Access Point (AP). There are several proposals of routing protocols tailored to the requirements of this kind of networks. Nevertheless,

there is not a routing protocol that performs well in different scenarios.

One of the main issues in ad hoc networks is the provisioning of quality of

service that meets the requirements of multimedia application's traffics, mainly

due to the radio signal vanishing among nodes and the high degree of mobility.

An idea to improve quality of service provided by this protocol is enabling

the routing algorithm calculate the routing table using the estimated link delay

metric, thus allowing that short delay links have better chances of being selected

over longer delay ones.

In this work it is presented an extension to the Optimized Link State

Routing (OLSR) protocol, one of the major protocols for ad hoc networks, based on an algorithm for link delay calculation. Simulations performed aiming to

validade this proposal have shown that OLSR- Link Delay protocol, the proposed

extension to OLSR, performed considerably better in comparison to original OLSR

in terms of throughput, delay, jitter and loss probability.

KEYWORDS : Mobile Ad Hoc Networks, OLSR, Quality of Service, Link Delay.

15

1. INTRODUORedes sem fio podem proporcionar aos usurios de dispositivos mveis a

capacidade de comunicao ubqua e fcil acesso informao, independente da

localizao. Segundo Royer & Toh (1999), existem atualmente duas variaes das redes sem fio. A primeira conhecida como rede sem fio infra- estruturada, isto

, aquelas redes com gateways fixos e cabeados, a partir dos quais os dispositivos

que fazem parte da rede sem fio ganham acesso a outras redes. Aplicaes tpicas

para este tipo de rede incluem redes locais sem fio (do ingls Wireless Local Area Network, WLAN ) e redes celulares.

O segundo tipo de redes mveis sem fio so as redes que no possuem

qualquer infra- estrutura de acesso central. Segundo Corson & Macker (1999), esse tipo de redes so geralmente conhecidas como redes auto- organizveis, redes ad

hoc mveis, redes sem fio mveis de mltiplos saltos, redes mveis de pacotes de

rdio e redes mesh mveis.

Atualmente, em funo do crescimento do segmento de computadores

pessoais portteis e da conseqente diminuio dos custos de produo desses

dispositivos, a rea de redes ad hoc sem fio tem recebido ateno especial por

parte da comunidade cientfica.

Liu (2005) define redes mveis ad hoc como sendo redes mveis sem fio formadas espontaneamente, nas quais a comunicao entre os dispositivos

envolve tipicamente o estabelecimento de rotas multihop (i.e., rotas contendo mltiplos saltos) temporrias, com cada um dos dispositivos presente na rede utilizando um ao outro como roteadores, e sem fazer uso de qualquer infra-

estrutura fixa, por exemplo um AP.

Este tipo de rede bastante flexvel, sendo largamente empregadas para

compartilhamento temporrio de informaes em conferncias, aes militares e

em aes de resgate em locais onde ocorreram desastres. Alm desses usos, as

redes ad hoc experimentam um significativo aumento de uso de cunho comercial

(Pereira, 2006).

16

Uma rede ad hoc sem fio composta por uma coleo de dispositivos

mveis (ou terminais) com a habilidade de comunicar - se entre si. Os terminais da rede so responsveis pelo estabelecimento de comunicao entre todos os

outros dispositivos que fazem parte da rede, isto , atuam como roteadores da

rede, ao mesmo tempo em que executam aplicaes para o usurio do

dispositivo, atuando tambm como estaes de trabalho.

1.1. MOTIVAOEm redes ad hoc sem fio, dada a limitao da modalidade de comunicao

via rdio, freqente a ocorrncia de situaes em que uma estao A no tenha

comunicao via rdio direta com outra estao B, dentro de uma mesma rede ad

hoc sem fio, conforme pode ser ilustrado na Figura 1.1. Neste caso, os outros

dispositivos da rede atuaro como roteadores temporrios, de modo que uma

comunicao entre o dispositivo A e o dispositivo B seja estabelecida. Nesse contexto, a tarefa dos dispositivos que fazem parte da rede encontrar a melhor

rota entre os dispositivos A e B, bem como identificar formas de manter os canais

de comuni cao j estabelecidos.

Figura 1.1: Exemplo de rede ad hoc . As arestas indicam a conectividade

bidirecional entre os computadores da rede

Entretanto, o roteamento multihop , a constante mobilidade dos dispositivos

que fazem parte da rede ad hoc e outras caractersticas inerentes a redes ad hoc

17

implicam em um grande overhead no processo de descoberta e manuteno de

rotas entre os dispositivos (Gerasimov, 2002). Este problema agravado pela limitao dos recursos disponveis, por exemplo energia, poder computacional

dos dispositivos e largura de banda, o que dificulta o provisionamento de

Qualidade de Servio (do ingls Quality of Service, QoS) nestas redes.Os protocolos de roteamento existentes na literatura de redes ad hoc

podem ser divididos em trs categorias principais: pr- ativos, reativos e hbridos.

Os protocolos pr- ativos mantm para cada dispositivo presente na rede uma

viso atualizada da topologia da mesma, de modo que a melhor rota entre dois

dispositivos quaisquer pode ser estabelecida de forma rpida, entretanto ao custo

da excessiva troca de mensagens de controle entre os dispositivos participantes

da rede. Considerando a limitao de recursos mencionada anteriormente, essa

soluo pode se tornar invivel em certos contextos, por exemplo em redes de

sensores sem fio.

Os protocolos reativos, ao contrrio, requerem um nmero muito menor de

troca de mensagens de controle entre os dispositivos, uma vez que as rotas so

estabelecidas por demanda, entretanto ao custo do aumento no tempo necessrio

para o estabelecimento da rota entre dois dispositivos quaisquer da rede. Em

ambos os casos, o provisionamento de QoS severamente prejudicado pela mobilidade dos dispositivos nestas redes, o que torna a busca por solues no

sentido de prover QoS que satisfaam os requisitos de aplicaes multimdia um dos principais temas de pesquisa em redes ad hoc .

Os protocolos hbridos so aqueles que renem as principais caractersticas

dos protocolos pr- ativos e reativos.

Segundo Albuquerque (2005), o desenvolvimento de um protocolo de roteamento que fornea garantias de QoS deve ser baseado em um conjunto de princpios bsicos. Esse conjunto de princpios inclui a transparncia, de tal forma que as aplicaes possam ser isoladas da complexidade das especificaes

e gerenciamento de QoS, a integrao entre as diversas camadas de protocolo, de forma que a QoS seja configurvel e previsvel fim- a- fim, e a separao de

18

funes, ou seja, a transferncia, o controle e o gerenciamento devem ser vistos como atividades distintas do ponto de vista da arquitetura. Entretanto, as

condies mencionadas anteriormente inerente s redes ad hoc tornam

extremamente complicada a busca por um mecanismo que satisfaa os requisitos

mencionados anteriormente.

1.2. OBJETIVOSConsiderando o empenho da comunidade cientfica na busca por uma

soluo para o provisionamento de QoS em redes ad hoc , este trabalho visa apresentar uma contribuio para rea, ao investigar uma extenso para o

protocolo OLSR (Clausen, 2003). A principal direo a ser tomada no processo de desenvolvimento da extenso o uso de estimativas de retardo de transmisso

do enlace entre pares de ns participantes da rede. Essas estimativas sero

obtidas a partir de variaes de tcnicas de medio de capacidade de enlace

baseadas em pares de pacotes presentes na literatura.

A estimativa de capacidade de enlace tem sido amplamente investigada

pela comunidade cientfica (Kapoor et al., 2004; Chen et al., 2004; Persson et al., 2005 ). Em adio a esse fato, h um considervel nmero de propostas que visam integrao de mtricas de capacidade de enlace ao funcionamento dos

protocolos de roteamento para redes ad hoc mais conhecidos. Entretanto, a

maioria das propostas utilizam mtricas obtidas a partir da camada fsica, o que

especialmente difcil quando utilizada a camada MAC (Media Access Control) do IEEE (Institute of Electrical and Electronics Engineers) 802.11 (Leguay, 2006). Este trabalho adota como diretriz, portanto, uma variao da proposta de estimativa

de capacidade de enlace proposto em (Chen et al., 2005a).

1.3. ORGANIZAOO trabalho est organizado como segue. O Captulo 2 apresenta uma

discusso sobre os tipos e os principais exemplos de protocolos de roteamento

19

para redes ad hoc existentes. O Captulo 3 apresenta um conjunto de propostas existentes na literatura para a medio da capacidade de enlaces de comunicao.

O Captulo 4 discute com um maior grau de detalhamento o protocolo OLSR e as

principais variaes do protocolo listadas na literatura. O Captulo 5 apresenta uma extenso ao protocolo OLSR a partir do uso de uma tcnica de medio de

retardo de transmisso entre pares de ns, adequada para o cenrio de redes ad

hoc . O Captulo 6 apresenta simulaes realizadas para validar a proposta. Como fechamento, o Captulo 7 apresenta as concluses observadas a partir das

simulaes realizadas, bem como propostas de trabalhos futuros.

20

2. PROTOCOLOS DE ROTEAMENTO PARA REDES AD HOC SEM FIOOs protocolos de roteamento existentes para redes cabeadas no so

adequados para o cenrio de redes ad hoc , uma vez que redes ad hoc so

formadas espontaneamente, no possuem qualquer infra - estrutura fixa de

comunicao e a topologia da rede pode mudar constantemente devido a

mobilidade dos dispositivos que fazem parte da rede (principalmente com respeito entrada e sada de dispositivos na rede).

De acordo com Corson & Macker (1999), outros fatores que tornam as propostas de protocolos de roteamento para redes cabeadas no adequadas para

redes ad hoc so: a instabilidade do canal de comunicao (ocasionada por interferncia e atenuao do sinal de rdio), limitao de recursos (por exemplo, energia e poder computacional do dispositivo), falta de escalabilidade da rede e de uma entidade central, entre outros problemas que no so comuns em redes

cabeadas.

Os protocolos de roteamento para redes ad hoc devem prover, portanto,

uma srie de caractersticas de modo a tornar funcional a rede ad hoc na qual o

mesmo empregado. Entre as funcionalidades necessrias cabe destacar (i) a deteco e resposta a mudanas na topologia da rede e servios, (ii) a disseminao de informao a respeito dessas mudanas para uso na construo

de rotas, (iii) o gerenciamento de mobilidade, (iv) a construo e seleo de rotas e (v ) o encaminhamento de trfego de acordo com as rotas selecionadas. Aliado a essas caractersticas, o protocolo deve ser capaz de maximizar a capacidade da

rede para o encaminhamento de trfego dos usurios e minimizar o atraso de

encaminhamento de pacotes.

Desde o advento das redes baseadas em pacotes de rdio desenvolvido pela

DARPA (Defense Advanced Research Projects Agency), vrias propostas de protocolos de roteamento para redes ad hoc foram apresentadas, cada uma

baseada em diferentes aspectos de otimizao e situaes (Chen, 1998). Algumas das propostas apresentadas so adaptaes de algoritmos tradicionais utilizados

21

no roteamento em redes cabeadas, por exemplo as baseadas nos algoritmos de

estado de enlace e vetor de distncia. No entanto, as propostas visam resolver

problemas especficos de redes ad hoc .

2.1. TIPOS DE PROTOCOLOS DE ROTEAMENTO PARA REDES A D HOCOs protocolos de roteamento para redes ad hoc podem ser classificados de

acordo com a abordagem utilizada para a descoberta de rotas. As categorias em

que os mesmos podem ser classificados so protocolos pr- ativos (ou orientados a tabela de roteamento), protocolos reativos (ou orientados demanda de rotas) e protocolos hbridos (renem caractersticas dos protocolos das duas classes anteriores).

2.1.1. Protocolos Pr- AtivosOs protocolos desta classe mantm sempre uma viso atualizada sobre a

topologia da rede, atravs do envio e recebimento de mensagens de controle.

Essas mensagens de controle informam, entre outros, quais so os ns

atualmente ativos na rede, e ns que podem ser utilizados para alcanar outros

ns na rede.

Um n pode, neste tipo de protocolo, enviar mensagens de controle

informando que o mesmo est ativo na rede (geralmente estas mensagens tem TTL (Time to Live) igual a 1, de modo a no congestionar a rede) e enviar mensagens de controle divulgando os ns com os quais ele tem alcanabilidade

(este tipo de mensagem geralmente possui TTL maior que 1, de modo que a mensagem possa chegar a ns que estejam mais distantes). A partir das informaes de controle recebidas da rede, cada n pode ento calcular a sua

tabela de roteamento interna, utilizando como parmetro mtricas pr-

determinadas pelo prprio protocolo.

A principal vantagem deste tipo de protocolo que rotas para diversos ns

que fazem parte da rede esto sempre disponveis, e o mesmo extremamente

22

sensvel a mudanas na topologia na rede. Essa caracterstica evita a quebra de

comunicao entre dois ns devido a sada ou mesmo a perda de comunicao

com ns intermedirios que faziam parte da rota utilizada.

As desvantagens deste tipo de protocolo so (i) a necessidade de troca de mensagens de controle, que impem um overhead adicional rede, (ii) o fato de que muitas das rotas calculadas pelo protocolo no so efetivamente utilizadas

para fins de roteamento de dados de aplicaes, e (iii) restries de poder computacional do n e mesmo de energia podem tornar essa soluo de

roteamento extremamente cara para a rede que a utiliza.

Os protocolos de roteamento pr- ativos tm sido largamente utilizados

como solues para redes mesh , como pode ser verificado em (Bruno, 2005), (Santivanez, 2003) e (Tsarmpopoulos, 2005). Um dos principais motivos o fato de que os roteadores mesh so estacionrios, alm de no apresentarem

restries quanto ao consumo de energia.

Entre as principais propostas de protocolos de roteamento pro - ativos

esto o Destination Sequenced Distance Vector (DSDV) (Perkins, 1994), Wireless Routing Protocol (WRP) (Murthy, 1996), Clusterhead Gateway Switch Routing (CGSR) (Chiang, 1997), Source Tree Adaptive Routing (STAR) (Garcia- Luna-Aceves, 1999) e o Optimized Link State Routing Protocol (OLSR) (Clausen, 2003).

2.1.2. Protocolos Reativos

Os protocolos desta classe apenas criam rotas para um destino quando elas

so necessrias para que o n atual possa iniciar um fluxo de comunicao com

um destino arbitrrio na rede. O n atual, nesse caso, inicia um processo de

descoberta de rota na rede. Esse processo apenas termina quando uma rota

encontrada ou quando todas as permutaes possveis de rotas so avaliadas

(com o objetivo de encontrar a melhor rota dentre todas as rotas identificadas).Uma vez que uma rota descoberta e estabelecida, ela mantida pelo

mecanismo de manuteno de rotas at que a rota no seja mais necessria ou ento at que todas as possibilidades de rotas entre o n atual e os ns de

23

destino sejam avaliadas (caso em que o n de destino passa a ser considerado inacessvel).

Os protocolos dessa classe so especialmente interessantes em cenrios em

que h limitao de recursos (por exemplo, energia, poder de processamento ou capacidade de comunicao), uma vez que a rede no inundada com mensagens de controle e nem os ns que fazem parte dessa rede tm a obrigao de enviar

constantemente mensagens de difuso para informar que os mesmos esto ativos

na rede.

A principal desvantagem dos protocolos desta classe, no entanto, que a

comunicao entre os ns na rede apenas pode ser iniciada quando uma rota

estiver disponvel, o que ocasiona um determinado atraso para a aplicao que

far uso da rota.

Entre as principais propostas de protocolos de roteamento reativos esto o

Signal Stability Routing (SSR) (Dube, 1997), Dynamic Source Routing (DSR) (Johnson, 2007), Temporary Ordered Routing Algorithm (TORA) (Park, 1997) e Ad Hoc on Demand Distance Vector Routing (AODV) (Perkins, 2003).

2.1.3. Protocolos HbridosOs protocolos desta classe renem as principais caractersticas encontradas

nos protocolos pr- ativos e reativos. Esses protocolos so especialmente

interessantes em redes ad hoc cujo comportamento varia com o passar do tempo.Por exemplo, uma rede, em um determinado momento, pode possuir todos

os ns igualmente ativos, o que requer que a tabela de roteamento seja constantemente atualizada. Entretanto, com o passar do tempo, a maioria dos ns

da rede podem tornar - se menos ativos ou at mesmo no ativos, fazendo assim

com que uma abordagem reativa seja mais adequada nesse novo contexto.Outra questo em relao aos protocolos das classes anteriores est na

escalabilidade. medida que aumentam o nmero de ns da rede, os protocolos pr- ativos tendem a tornar no escalveis, devido ao grande nmero de

mensagens de controle propagadas utilizando pacotes de difuso . Entretanto, em

24

grandes redes a latncia para a descoberta e manuteno de uma rota passa a se

tornar um estrangulador da rede.

Entre as principais propostas existentes nessa classe de protocolos esto os

protocolos adaptativos, por exemplo, o Sharp Hybrid Adaptive Routing Protocol

(SHARP) (Ramasubramanian, 2003), e protocolos que utilizam roteamento baseado em zonas, como por exemplo o Zone Routing Protocol (ZRP) (Haas, 1997).

O SHARP um protocolo que identifica o comportamento que a rede possui

no momento e automaticamente muda a abordagem de funcionamento, ora

agindo como um protocolo prativo, ora funcionando como um protocolo

reativo.

O ZRP um protocolo que divide os ns em zonas de roteamento, e que

utiliza uma abordagem pr- ativa para o roteamento intra- zona e uma abordagem

reativa para o roteamento inter - zonas.

2.2. ANLISE COMPARATIVAA escolha do melhor protocolo de roteamento est inerentemente ligada ao

cenrio e ao tipo de aplicao que ser feito da rede ad hoc em questo. As

tabelas a seguir tem o objetivo de apresentar um resumo das caractersticas dos protocolos de roteamento para redes ad hoc discutidos neste captulo. A Tabela

2.1 rene os protocolos pr- ativos; a Tabela 2.2 rene os protocolos reativos e a

Tabela 2.3 rene os protocolos hbridos. Em cada uma das tabelas so

enumeradas as principais caractersticas de cada um dos protocolos.

25

Tabela 2.1: Protocolos de roteamento pr- ativos

Protocolo Classificao FuncionamentoBsico Principaiscaractersticas

CGSR Prativo

Baseadonoprotocolo

DSDV.Nsso

organizadosem

clusters.

Mensagensdecontrole

utilizadasparadivulgao

dosmembrosdeclusters.

DSDV Prativo

Baseadonoalgoritmo

deroteamentode

BellmanFord.

Mensagensdecontrole

utilizadaspara

comunicaodatabelade

roteamento.

OLSR Prativo

Baseadonoalgoritmo

deestadodeenlaces

enoconceitode

MultipointRelays.

Usodemensagensde

controleparaoprocesso

dedescobertadevizinhos

edivulgaode

informaesdetopologia.

STAR Prativo

Duasabordagenspara

clculodatabelade

roteamento:

priorizandooclculo

derotastimasoua

diminuiono

overheaddetrocade

mensagensde

controle.

Nsenviammensagens

informandoarvorede

caminhosutilizadospor

elesmesmosparaalcanar

determinadosdestinos.

26

Tabela 2.2: Protocolos de roteamento reativos


AODV Reativo

Baseadonoprotocolo

DSDV,pormapenas

estabelecendorotas

sobdemanda.

Mensagensderequisiode

rotassoenviadasatodos

osnsdarede.Utiliza

apenasenlacessimtricos.

DSR Reativo

Usodemensagens

RouteRequeste

RouteReplyparao

estabelecimentode

rotas.

Naoutilizamensagens

HELLO,diferentementede

outrosprotocoloson

demand.Nsmantmcache

derotasdescobertas.

SSR Reativo

Protocolode

roteamentosob

demandabaseadonos

algoritmosDynamic

RoutingProtocole

StaticRouting

Protocol.

Seleoderotasfeita

deacordocoma

intensidadedosinalentre

nseaestabilidadedo

mesmo.

TORA Reativo

Protocolode

roteamentoadaptativo

eescalvelbaseado

noconceitode

reversodeenlace.

baseadoemtrsfunes

bsicas:criao,

manutenoeexclusode

rotas.Acriaoderotas

realizadasobdemandae

utilizandopacotesQRYe

UPD.

27

Tabela 2.3: Protocolos de roteamento hbridos


SHARP Hbrido

Baseadoemabordagens

prativasextradas

dosprotocolosDSDVe

TORAeemabordagens

reativasextradasdo

protocoloAODV.

Procuraumpontode

balanceamentonarede

entreumaabordagempr

ativaereativa,apartir

docomportamentodosns

quefazempartedarede.

ZRP Hbrido

Utilizaumaabordagem

prativaemuma

vizinhanadeatn

saltoseuma

abordagemreativa

paransdedestino

foradessa

vizinhana.

Casoondedestino

estejadentroda

vizinhanaatnsaltos,o

nenviaopacote

diretamente.Caso

contrrio,ummecanismode

RouteRequestdisparado.

2.3. CONSIDERAES FINAIS DO CAPTULONeste captulo foram discutidas as principais abordagens utilizadas pelos

protocolos de roteamento para redes ad hoc sem fio, as abordagens pr- ativas,

reativas e hbridas. Exemplos de protocolos que utilizam cada uma das

abordagens mencionadas foram apresentados para completar a discusso sobre

cada uma das classes.

28

3. ESTIMATIVA DE CAPACIDADE DE ENLACEO conhecimento da capacidade do enlace uma caracterstica

especialmente til em diversos cenrios.

Uma aplicao multimdia, baseada em informaes das camadas mais

baixas a respeito da capacidade atual do enlace utilizado para o trfego de

informao multimdia, pode adaptar a taxa de transmisso de quadros de modo

a fazer o melhor uso da banda disponvel.

Um servidor de fluxo de dados contnuo, por outro lado, pode identificar

qual a melhor taxa de dados a ser utilizada para cada um dos seus clientes,

baseado na capacidade do enlace mais estreito existente no caminho entre o

cliente e o servidor. Um terceiro exemplo pode ser relacionado transmisso de

um jogo de futebol pela Internet utilizando multicast . Atravs do conhecimento da capacidade do caminho entre o servidor e cada um dos assinantes, o servidor

poder identificar quais os formatos de dados que devem ser enviados na rede

para aquele evento, e as direes em que os mesmos devem ser enviados.

Mais ainda, tendo conhecimento a respeito da capacidade de um caminho

fim- a- fim, protocolos que utilizam controle de congestionamento

nomeadamente o protocolo TCP (Transmission Control Protocol) podem prover um melhor controle de congestionamento, ao passo que promovem uma melhor

utilizao dos recursos de banda disponveis para o fluxo.

Segundo Persson et al. (2005), a capacidade de um caminho da Internet refere- se a menor capacidade fsica de um enlace dentre todos os enlaces que

fazem parte desse caminho (isto , a capacidade do enlace de gargalo do caminho).

Ainda de acordo com Persson, uma observao importante que essa

informao diferente da informao sobre banda disponvel, que o mnimo de

banda no utilizada ao longo do caminho, e que, portanto, um valor que varia

ao longo do tempo, conforme o uso que est sendo feito da rede.

Existem alguns requisitos que devem ser atendidos pelas tcnicas de

29

medio de capacidade de enlace. Alm de possuir uma baixa complexidade, o

processo de estimativa deve (i) ser independente de trfego cruzado (isto , o fato de pares de pacotes de amostra ficarem separados, na fila de roteadores

intermedirios, por pacotes pertencentes ao trfego do usurio, no deve afetar

no resultado obtido pela tcnica); (ii) ser adequada para a medio de capacidade de trfego de caminhos que misturem enlaces cabeados e sem fio; e (iii) a aplicao deve ser no- intrusiva, ao ponto de no perturbar o trfego de

aplicaes do usurio que estejam fluindo pela rede.A estimao de capacidade de enlace tem sido extensivamente estudada em

redes cabeadas. As primeiras pesquisas no estudo de capacidade de enlace

utilizavam essencialmente a variao do atraso entre pacotes (Jacobson, 2006) ou disperso entre os pacotes (Dovrolis, 2001) (Lai, 1999).

Paxson (1997) mostrou que a distribuio de disperso pode ser multi -modal (por exemplo, em enlaces multi - canais), e props o uso de Packet Bunch Modes , uma tcnica que envolve o uso de trens de pacotes de diferentes

comprimentos.

Dovrolis (2001) mostrou que as distribuies de disperses podem certamente ser multi - modal sem multi - canais, e que o modo mais representativo

na distribuio multi - modal da disperso pode corresponder ou (1) a capacidade do enlace, (2) a uma disperso "comprimida", superestimando a capacidade do enlace, ou (3) numa Taxa de Disperso Mdia (do ingls Average Dispersion Rate, ADR ), que corresponde a um valor menor que a capacidade real. Kapoor et al. (2004) props uma abordagem baseada em pares de pacotes chamada CapProbe , a qual combina atrasos e medidas de disperses para estimar a capacidade do

enlace.

Devido rpida variao das condies dos canais em redes ad hoc sem fio,

mobilidade dos ns, e caminhos de mltiplos saltos formados essencialmente por

enlaces sem fio, as propostas utilizadas em redes cabeadas no se mostraram

adequadas para o cenrio de redes ad hoc sem fio. Chen et al. (2005a) endereou esse problema ao propor o AdHoc Probe , uma tcnica baseada nos mesmos

30

princpios do CapProbe para a estimao de capacidade de enlaces em redes ad

hoc de mltiplos saltos.

3.1. TCNICAS ATIVASAs tcnicas ativas de medio de capacidade de enlace injetam pacotes

extras na rede de modo a obter amostras para poder calcular a capacidade do

enlace estudado. Entre os conceitos geralmente utilizados pelas tcnicas ativas

esto o "par de pacotes" e o "trem de pacotes". Embora intrusivas, elas

apresentam um baixo tempo de convergncia e medies mais precisas sobre a

capacidade real do enlace analisado.

As tcnicas baseadas em pares de pacotes so tcnicas que dependem do

envio simultneo de dois pacotes de mesmo tamanho em um nico sentido do

enlace. O objetivo medir a diferena de tempo com que o par de pacotes chega ao dispositivo de destino (outra ponta do enlace). A partir dessa informao a capacidade do enlace ser calculada.

As tcnicas baseadas em trens de pacotes, por outro lado, tem como

objetivo inundar o enlace com pacotes UDP (User Datagram Protocol) e verificar, na outra ponta do enlace, qual a maior vazo obtida. O maior valor medido

corresponder capacidade do enlace analisado.

Pathrate e CapProbe so as duas tcnicas ativas mais representativas. A

principal diferena entre as tcnicas que Pathrate utiliza o conceito de "trem de

pacotes" para estimar a capacidade de um enlace, enquanto que o CapProbe

utiliza a tcnica de "pares de pacotes". Kapoor et al. (2004) mostrou que a tcnica CapProbe menos intrusiva, possui um menor tempo de convergncia, e menos

complexa que Pathrate , enquanto que mantm o mesmo grau de preciso que a

segunda tcnica. Outra proposta ativa de estimativa de capacidade de enlace o

AdHoc Probe (Chen et al., 2005a), especialmente desenvolvida para os propsitos e peculiaridades das redes ad hoc sem fio.

31

3.1.1. CapProbeO CapProbe (Kapoor et al., 2004) uma tcnica para a estimao da

capacidade do enlace de gargalo em um caminho formado por mltiplos saltos.

Essa tcnica fundamenta - se no fato de que quando dois pacotes so enviados na

rede em modo de ida e volta (round- trip ), eles so sempre separados no enlace de gargalo por um intervalo relacionado capacidade de gargalo. Se tal intervalo

mantido at o destino final do pacote, ele ir permitir calcular a capacidade do

enlace que gerou esse intervalo.

Segundo Dovrolis (2001), um dos principais problemas que podem ocorrer nesses tipos de amostras a interferncia causada pelo enfileiramento de pacotes

em enlaces congestionados. Tal interferncia pode fazer com que a capacidade do

enlace calculada pelo algoritmo seja superestimada ou subestimada.Para filtrar amostras que tenham sofrido perturbaes causadas por

trfego cruzado, o CapProbe combina o uso de medidas de intervalo de tempo e

medidas de atraso fim- a- fim.

Dovrolis (2001) define que um valor incorreto da estimao de capacidade apenas pode ocorrer se trfego cruzado interferir no caminho do pacote. Neste

caso, atrasos causados por enfileiramento e atrasos de um ou ambos os pacotes

sero maiores que o mnimo observado na ausncia de trfego cruzado. A soma

dos atrasos dos pacotes no par de pacotes definida como soma de atraso. Uma

soma de atraso, que no inclui quaisquer atrasos de enfileiramento induzidos por

trfego cruzado, referenciado como soma de atraso mnimo. Portanto,

quaisquer somas de atrasos que sejam maiores que o mnimo calculado devem ter sofrido perturbaes ocasionadas por trfego cruzado e devem ser

descartadas.

Calculado a soma de atraso mnimo, a capacidade pode ser calculada

utilizando a frmula apresentada no Quadro 3.1, onde P o tamanho do pacote de amostra e T o intervalo entre pacotes com soma de atraso mnimo.

32

C = P/TQuadro 3.1 frmula de clculo de capacidade de enlace

3.1.2. AdHoc ProbeEmbora exista considervel nmero de estudos sobre estimativa de

capacidade de enlace listadas na literatura especializada, a maioria

essencialmente orientada ao estudo de estimativa de capacidade em enlaces

cabeados ou redes com ultimo salto composto por enlaces sem fio.

Segundo (Chen et al., 2005a), as propostas de estimativa de capacidade de enlace mencionadas anteriormente no podem ser diretamente aplicadas na

estimativa de capacidade de caminhos em redes ad hoc de mltiplos saltos,

devido s caractersticas intrnsecas deste ltimo tipo de rede.

Primeiro, a capacidade do enlace pode variar dinmica e rapidamente

devido a uma srie de fatores, como interferncia, mobilidade ou mudana nas

polticas de economia de energia adotadas pelos ns da rede. Em adio a esse

fato, somam - se a alta complexidade das principais propostas existentes, o alto

tempo requerido para convergncia, e o fato de que as abordagens que trabalham

com round- trip no so adequadas para o cenrio de redes ad hoc .

Ainda segundo (Chen et al., 2005a), embora simulaes e experimentos tenham mostrado que o CapProbe seja uma proposta adequada para a estimao de capacidade em redes cabeadas, o fato de ser geralmente utilizado em modo

round- trip para estimar a capacidade do enlace nas duas direes o torna

inadequado para redes ad hoc . O modo round- trip inadequado para redes ad

hoc pelo fato de que o primeiro pacote enviado pelo n de origem pode colidir

com o segundo pacote originado pelo n de destino do primeiro pacote.

O AdHoc Probe uma proposta para estimar capacidade de enlaces em

redes ad hoc de mltiplos saltos, que utiliza a mesma abordagem de par de

pacotes utilizada pelo CapProbe (Kapoor et al., 2004). A proposta capaz de identificar a variao da capacidade de um enlace levando em considerao as

principais caractersticas de uma rede ad hoc , sendo, de acordo com Chen et al.

33

(2005a), uma proposta com complexidade e tempo de convergncia menor que as demais propostas relacionadas existentes na literatura.

Diferentemente do CapProbe , que baseado no modo round- trip , o AdHoc

Probe apenas utiliza pares de pacotes enviados em um nico sentido. Outra

diferena que o AdHoc Probe mede a capacidade mxima de transferncia de

dados que pode ser alcanada em um enlace no utilizado, isto um enlace que

no est sendo disputado com trfego cruzado, durante a realizao das

medies. Tal mtrica especialmente interessante em situaes em que polticas

de qualidade de servio devem ser adotadas.

No AdHoc Probe , pares de pacotes de tamanho fixo so enviados em uma

direo nica, com o tempo de envio registrado em cada pacote transmitido. Com

a informao sobre o momento em que o pacote foi enviado, o destino pode

ento calcular o atraso de via nica (do ingls One Way Delay, OWD), e por conseqncia a capacidade do enlace em um sentido.

O receptor do pacote mede o OWD de cada pacote como a diferena entre o

tempo em que o pacote foi recebido (identificado no receptor do pacote) e o tempo em que o mesmo foi enviado (o qual registrado no pacote pelo emissor do mesmo). Com isso, a soma de OWD calculada. Da mesma forma que a soma de atraso no CapProbe , somas de OWD podem ser descartadas no AdHoc Probe ,

caso as mesmas sejam maiores que a soma de OWD mnimo calculada. Por fim, a capacidade dada pela frmula apresentada no Quadro 3.1.

3.1.2.1. Problema de Sincronizao do Relgio do Sistema

A medida do OWD problemtica em um testbed real. Diferentemente da

sincronizao perfeita de relgios dos diferentes ns participantes da rede

existente no ambiente de simulao, no existem meios de garantir que os

relgios de diferentes ns pertencentes a uma rede ad hoc estejam sempre sincronizados. Como resultado, o OWD medido ser diferente do OWD real.

Para lidar com diferenas de sincronizao de relgio, o algoritmo AdHoc

Probe utiliza clculos matemticos para absorver do valor de OWD a constante de

34

deslocamento de tempo entre o emissor e receptor de pacotes. Como essa

constante no varia para todos os pares de pacotes enviados do emissor ao

receptor, Chen et al. (2005a) mostra que a presena da constante para todos os pares de pacotes no interfere no resultado final da estimativa.

Suponha que seja a constante de deslocamento de tempo entre o emissor e o receptor de uma rede ad hoc . Para o ensimo par de pacotes de amostra o

tempo de envio estampado como Tsend,i, e o tempo de recepo dos pacotes (no receptor) estampado como Trecv1,i para o primeiro pacote e Trecv2,i para o segundo pacote, respectivamente. Portanto, a soma do OWD medida pelo algoritmo (S') e a soma do OWD real (S) para o ensimo par de pacotes apresentado nos Quadros 3.2 e 3.3, respectivamente.

S'i = (Trecv1,i - T send,i) + (Trecv2,i - T send,i)Quadro 3.2 soma OWD medida pelo algoritmo AdHoc Probe

Si = (Trecv1,i - T send,i - ) + (Trecv2,i - T send,i - ) = S'i - 2 Quadro 3.3 soma OWD real

Portanto a diferena entre Si e S'i uma constante 2 para todos os pares

de pacotes. Se Sk = min i= 1..nSi para k [1..n], ento S'k = min i= 1..nS'i, e vice versa. Ao filtrar as amostras que no sejam um valor mnimo de S', fcil identificar as boas amostras que possuam valores mnimos para S' e S, e a capacidade do

enlace calculada utilizando o intervalo de tempo entre o par de pacotes.

3.2. TCNICAS PASSIVASA principal desvantagem das tcnicas ativas de estimao de capacidade de

enlace o fato de o trfego extra inserido na rede para a estimao da capacidade

poder perturbar no trfego de aplicaes que esto concorrendo para o uso do

35

meio de transmisso.

De acordo com Chen et al. (2004), essa desvantagem mostra que as tcnicas de estimao de capacidade de enlace, alm de fornecerem estimativas corretas

sobre a capacidade do enlace, devem tambm ser capazes de trabalhar

passivamente sem adicionar overhead excessivo na rede, identificar mudanas na

rede em tempo real, e gerar resultados que possuam uma semntica fim- a- fim.

As tcnicas passivas de medio de capacidade de enlace procuram tirar

vantagens do prprio trfego de aplicaes que flui pela rede. Apesar de ser

baseadas nas mesmas teorias que as tcnicas ativas (disperso de pacotes e atraso fim- a- fim), as tcnicas passivas no impem overhead adicional rede. Entretanto, elas apresentam um maior tempo de convergncia que as tcnicas

ativas, e um menor grau de preciso sobre a capacidade real do enlace analisado.

Entre as tcnicas passivas de estimao de capacidade de enlace listadas na

literatura existem as baseadas no CapProbe , como por exemplo o TFRC Probe

(Chen et al., 2004) e o TCP Probe (Persson et al., 2005).O TFRC Probe uma proposta de protocolo que estima passivamente a

capacidade do enlace, resultando da combinao do TFRC (Floyd, 2000), um protocolo de stream unicast baseado no UDP, com o CapProbe .

O TCP Probe , por sua vez, uma extenso do protocolo TCP facilmente

adaptvel s variantes do TCP existentes na literatura, e que utiliza o par de

pacotes que possuem as indicaes PSH (Push) e ACK (Acknowledgement) para estimar passivamente a capacidade do caminho fim a fim, de modo a melhorar o

controle de congestionamento do TCP.

3.2.1. TFRC ProbeO TFRC Probe (Chen et al., 2004) uma tcnica de monitorao de

capacidade de enlace em tempo real resultante da integrao do algoritmo

CapProbe (Kapoor et al., 2004) no protocolo TFRC (Floyd, 2000). O TFRC um protocolo para fluxos unicast que utiliza um mecanismo prprio para o controle

de congestionamento, de modo a permitir o uso eficiente de banda em um

36

ambiente da Internet baseado em protocolos de melhor esforo.

O TFRC razoavelmente justo quando compete por banda com outros trfegos TCP na rede, entretanto apresenta uma variao menor na taxa de

transmisso ao longo do tempo quando comparado com o TCP, o que o torna

uma alternativa adequada para aplicaes tais como telefonia ou streaming de

mdias.

Diferentemente da natureza do algoritmo CapProbe , o TFRC Probe

projetado para monitorar a capacidade do enlace apenas no sentido de ida, uma vez que apenas essa informao necessria para que o servidor de stream possa

ajustar a sua taxa de envio de dados e qualidade de mdia enviada.Para estimar a capacidade do enlace no sentido de ida, a cada n pacotes

enviados pelo protocolo TFRC, um par de pacotes de amostra criado.

Adicionalmente, com o objetivo de alcanar o valor estimado da capacidade do enlace no sentido de ida, os pacotes de amostra so marcados com a estampa de

tempo de envio. A partir da aplicao da tcnica do CapProbe , a capacidade

estimada pode ento ser enviada para o servidor, ou utilizando um pacote ACK

enviado pelo prprio protocolo, ou ento enviado um pacote extra.

3.2.2. TCP ProbeO TCP Probe (Persson, 2005) uma extenso para todas as variantes

existentes do TCP para o monitoramento da capacidade do enlace, de modo a

melhorar o mecanismo de controle de congestionamento. Conhecendo a

capacidade do enlace, o controle de congestionamento pode utiliz - lo como um

parmetro para ajustar a janela de conteno, de modo a aproveitar melhor a capacidade mxima de transmisso que pode ser alcanada no caminho.

O TCP Probe estima a capacidade do enlace utilizando uma variao do

algoritmo CapProbe , e como pacotes de amostra so utilizados os prprios

pacotes enviados pelo protocolo TCP, o que torna o TCP Probe uma tcnica

passiva de estimao de capacidade de enlace. As medidas sobre capacidade de

enlace calculado pelo TCP Probe possuem uma semntica fim- a- fim, o que

37

permite que os valores estimados sobre a capacidade do enlace possam ser

efetivamente utilizados.

Alguns problemas precisam ser resolvidos para que o algoritmo CapProbe

possa ser efetivamente utilizado no TCP. O Primeiro o mecanismo de Delayed

ACK utilizado pelo TCP, que permite que maiores taxas de transmisso possam

ser alcanadas, a partir do envio de um nico pacote ACK para um conjunto de pacotes de dados enviados pela fonte. Isso resolvido invertendo a ordem dos

pacotes na origem. Desta forma, o destino ir utilizar um ACK separado para

cada pacote, como uma resposta do protocolo a uma possvel perda que tenha

ocorrido na rede.

Outro problema quanto ao tamanho dos pacotes. O pacote enviado pela

origem tem tamanho varivel, enquanto que o tamanho do pacote de ACK tem

um tamanho geralmente fixo e inferior ao tamanho do pacote de dados enviado.

Para contornar essa caracterstica, empregado o mecanismo de calculo de

capacidade em enlaces assimtricos proposto em (Chen et al., 2005b). Desta forma, os resultados obtidos pelo TCP Probe sero correspondentes capacidade

de um enlace assimtrico.

3.3. ANLISE COMPARATIVAEmbora as tcnicas de estimativa de capacidade de enlace geralmente

apresentem vantagens em relao uma outra, o que define a melhor tcnica de

estimativa de capacidade de enlace o cenrio de aplicao e as possibilidades de

obteno de amostras para o clculo das estimativas, e considerando tambm o

cenrio de aplicao e as restries operacionais. A Tabela 3.1 rene as tcnicas

de estimativa de capacidade de enlace mencionadas no decorrer deste captulo,

realando as suas principais caractersticas.

38

Tabela 3.1: Algoritmos de estimativa de capacidade de enlace

Algoritmo Classificao Caractersticasbsicas

AdHocProbe TcnicaAtiva

BaseadonoalgoritmoCapProbe,entretanto

adaptadoparaocenrioderedesadhoc.

Medeacapacidadeociosadeumenlaceem

apenasumsentidodomesmo.

CapProbe TcnicaAtiva

Estimaacapacidadedeidaevoltado

enlacedegargalodeumcaminhobaseadona

tcnicadedispersodeparesdepacotes.

TCPProbe TcnicaPassiva

Estimaacapacidadedeidaevoltado

enlacedegargalodeumcaminho,utilizando

comobaseoalgoritmoCapProbeeuma

alteraonoprotocoloTCP.

TFRCProbe TcnicaPassiva

Resultantedaintegraodoalgoritmo

CapProbenoprotocoloTFRC.Acapacidadedo

enlacedegargalomedidaemapenasuma

via,ecomunicadofontededados

utilizandopacotesTFRCACK.

3.4. CONSIDERAES FINAIS DO CAPTULONeste captulo foi discutida a importncia do conhecimento da capacidade

de um enlace e algumas das principais tcnicas listadas na literatura para a

estimao de capacidade de enlace.

O principal foco da discusso foi o algoritmo proposto por Kapoor et al.

(2004) e suas variaes presentes na literatura, entre as quais o AdHoc Probe , a tcnica de estimao de capacidade de enlace que ser empregada para os fins

deste trabalho.

39

4. O PROTOCOLO DE ROTEAMENTO OLSRO protocolo OLSR (Clausen, 2003) uma adaptao do algoritmo de estado

de enlace tradicional para os fins de redes mveis ad hoc sem fio. Ele age como

um protocolo prativo, orientado tabela de roteamento, por meio da troca de

mensagens sobre informao da topologia da rede com outros ns que tambm

fazem parte da rede. O formato bsico de qualquer mensagem de controle do

OLSR, omitindo informaes sobre o cabealho IP e UDP, mostrado na Figura

4.1.

Figura 4.1: Formato bsico de um pacote de controle do OLSR (Clausen, 2003)

Um nico pacote bsico do OLSR capaz de transportar vrias mensagens

definidas pelo protocolo OLSR at que o tamanho mximo de pacote permitido

pela rede seja alcanado, o qual definido pela unidade mxima de transferncia (do ingls Maximum Transfer Unit, MTU) da interface de rede. Isso permite um

40

menor overhead para o envio de diferentes mensagens por um mesmo n da rede

em um determinado momento. Maiores informaes sobre cada campo do

formato bsico de mensagem do OLSR podem ser obtidas em (Clausen, 2003).O conceito chave do protocolo OLSR que o torna adequado para redes ad

hoc o nmero limitado de pacotes de difuso de controle enviado pelo

protocolo. Essa otimizao alcanada a partir do conceito de MultiPoint Relays

(MPRs). Cada n na rede seleciona ns pertencentes na rede para fazerem parte de seu conjunto de MPRs (MPR set) entre os seus vizinhos de 1 salto que possuem comunicao simtrica (isto , possuem comunicao bidirecional). A seleo de MPRs ajuda a evitar que a rede seja inundada por mensagens de controle geradas pelo protocolo.

No protocolo OLSR, os vizinhos de um n N que no esto em seu conjunto de MPRs podem receber e processar mensagens de difuso de controle enviadas

pelo n N, entretanto eles no retransmitem essas mensagens.

O conjunto de MPRs selecionado de forma que ele possa cobrir todos os ns que estejam a dois saltos de distncia do n atual, que tenham comunicao simtrica com cada um dos ns que esto a um n de distncia do n atual, e que

estejam dispostos a encaminhar pacotes em benefcio da rede (parmetro willigness diferente de WILL_NEVER).

O mecanismo de seleo de MPRs reduz substancialmente as mensagens de

controle e de difuso utilizadas para manter informaes de topologia da rede

em comparao com as propostas tradicionais de protocolos baseados no

algoritmo de estado de enlace. O algoritmo de seleo de MPRs do protocolo

OLSR apresentado na Figura 4.2.

41

Figura 4.2: Algoritmo de seleo de MPRs do protocolo OLSR tradicional (Leguay, 2006)

Em adio ao conjunto de MPRs, cada n mantm um outro conjunto, o conjunto de ns que selecionaram o n atual como MPR (MPR selector set ). A informao sobre quais ns atualmente selecionaram o n atual como MPR pode

ser obtida a partir das mensagens HELLO enviadas periodicamente na rede. Os

ns que foram selecionados como MPR por outros ns da rede divulgaro essa

mensagem nas mensagens TC, mensagens utilizadas para a divulgao de

informaes sobre a topologia da rede. O formato bsico da mensagem HELLO

apresentado na Figura 4.3, enquanto que o formato bsico da mensagem TC

aprese ntado na Figura 4.4.

42

Figura 4.3: Mensagem HELLO (a) Campo divulgando informaes sobre grupo de vizinhos do n atual. (b) Formato do campo de cdigo do enlace, contido na

mensagem HELLO, informando qual o tipo de comunicao que existe entre o n

atual e o grupo de vizinhos subsequentes (Clausen, 2003)

Figura 4.4: Formato da mensagem de controle de topologia (TC) definida pelo protocolo OLSR (Clausen, 2003)

43

Existe ainda outro tipo de mensagem de controle do protocolo OLSR, as

mensagens de declarao de interface, que serve para associar vrios endereos a

um endereo principal. Ela especialmente utilizada em ocasies em que um

nico n possui mais de uma interface sem fio participando da rede ad hoc

utilizando o protocolo OLSR.

A proposta do OLSR tradicional utiliza o nmero de saltos como critrio

para otimizao do roteamento de pacotes. O nmero de saltos utilizado para

computar a menor distncia (e, portanto, a melhor rota) para um destino arbitrrio, utilizando mapas de topologia que consistem de todos os seus

vizinhos e MPRs para todos os outros ns que no forem vizinhos diretos (1 hop neighbor ).

Segundo Leguay (2006), uma vantagem do protocolo OLSR do ponto de vista de QoS que a sua natureza pr - ativa permite que rotas estejam disponveis antes mesmo que a fonte precise iniciar um fluxo de pacotes para um

n de destino arbitrrio. Essa caracterstica especialmente interessante em

redes ad hoc que precisam oferecer suporte a aplicaes multimdia, por exemplo

voz sobre IP (do ingls Voice over IP, VoIP), uma vez que a latncia para o estabelecimento de uma comunicao relativamente baixo.

Ainda de acordo com Leguay (2006), outra vantagem do OLSR, enquanto protocolo que utiliza o algoritmo de estado de enlace, que a computao das

rotas realizada utilizando o conhecimento sobre a topologia de toda a rede.

Essa caracterstica permite que o OLSR proporcione um melhor suporte a QoS que as propostas de protocolos de roteamento baseados no algoritmo de vetor de

distncia.

4.1. EXTENSES PARA O PROTOCOLO OLSRDe acordo com Aslam (2004), o critrio de nmero de saltos definido na

proposta original do OLSR no capaz de fornecer suporte a QoS, uma vez que um caminho selecionado baseado no menor nmero de saltos pode no satisfazer

44

aos requisitos de QoS determinados pela aplicao que far uso da rede. Restries quanto a taxa de perdas de pacotes, atrasos, variao de atraso e

banda mnima no so possveis de serem garantidas selecionando rotas que,

apesar de se mostrarem menores em termos de nmero de saltos, podem ser

extremamente instveis.

Existem um nmero de propostas na literatura que visam resolver o

problema de QoS em redes ad hoc que utilizam o protocolo OLSR. As propostas que apresentam solues para o roteamento com provisionamento de QoS fazem uso de duas estratgias diferentes: modificaes internas no protocolo, de modo

que a compatibilidade com verses do protocolo que sigam estritamente o OLSR

padronizado pelo Internet Engineering Task Force (IETF) no seja quebrada, e modificaes internas e externas no protocolo (como por exemplo modificaes nas mensagens de controle), o que torna as propostas resultantes incompatveis com o OLSR padronizado pelo IETF.

4.1.1. Alteraes no Algoritmo de Seleo de MPRsA heurstica de seleo de MPRs do protocolo OLSR original visa selecionar

um conjunto mnimo de vizinhos diretos (1 hop neighbor ) que podem ser utilizados para alcanar todos os vizinhos que esto a dois saltos de distncia.

Badis et al. (2004) mostrou que essa heurstica pode fazer com que ns com baixa capacidade de comunicao sejam selecionados ao invs de ns que possuam melhores condies de comunicao com outros ns da rede (por exemplo, uma maior banda).

De acordo com Badis et al. (2004), existe uma correspondncia direta entre o conjunto de MPRs selecionados por um n e o conjunto de enlaces anunciados na rede. Apenas os enlaces anunciados na rede so utilizados para o clculo da

tabela de roteamento. A estratgia , portanto, selecionar MPRs de modo que

enlaces de alta capacidade sejam anunciados na rede, ao invs dos enlaces de baixa capacidade.

Ge (2003) prope uma heurstica alternativa para a seleo de MPRs, de

45

modo que o protocolo OLSR possa encontrar caminhos que possuam a maior

banda disponvel. A idia bsica que, quando h mais de um vizinho direto que

possui visibilidade para os mesmos vizinhos distantes dois saltos, o vizinho que

tiver um enlace com o n atual de maior capacidade ser selecionado.

Esta estratgia apresenta algumas vantagens. A primeira que a

modificao na heurstica de seleo de MPRs no quebra compatibilidade com

verses padro do OLSR e com verses do OLSR que utilizem outras heursticas

para a seleo de MPRs. Outra vantagem que essa proposta no requer que

informaes adicionais sejam trocadas entre os ns que fazem parte da rede.Entre as desvantagens da proposta est o fato de que apenas uma mtrica

(ou uma combinao especifica de mtricas) pode ser levada em considerao. A proposta, portanto, no permite que o protocolo possa atender a diversas classes

de servio. E mesmo considerando a mtrica, o algoritmo continua preocupado

em selecionar as rotas que possuam um menor nmero de saltos e que so

melhores em relao mtrica informada, e no as melhores rotas em um

contexto mais amplo. Outra desvantagem que a heurstica de seleo de MPRs

desconsidera a assimetria existente na comunicao entre os ns que fazem parte

da rede.

4.1.2. QOLSRBadis et al. (2004) propuseram o QoS- enhanced OLSR (QOLSR), uma

extenso do OLSR com provisionamento de QoS. Alm de ser baseado em uma nova heurstica para a seleo de MPRs, a proposta utiliza uma variao da

mensagem de TC, a mensagem utilizada para divulgar informaes sobre a

topologia da rede, de modo a divulgar para outros ns da rede a qualidade do

enlace de comunicao que o n atual tem com os seus vizinhos diretos.

Para a seleo de MPRs, a estratgia encontrar MPRs que maximizem a

banda disponvel e minimizem o atraso fim- a- fim entre vizinhos separados por

dois saltos (2 hop neighbor ). Desta forma, o algoritmo para clculo da tabela de roteamento trabalha utilizando um conjunto melhor de enlaces que o OLSR

46

tradicional.

Para aplicar esta heurstica de seleo de MPRs, os ns precisam de

algumas informaes extras sobre os vizinhos a dois saltos de distncia. As

mensagens de HELLO so modificadas para suportar a troca de informaes de

QoS entre vizinhos imediatos (1 hop neighbor ).Cada n anuncia a banda disponvel e o atraso para cada um dos seus

vizinhos imediatos. Os ns podem, opcionalmente, anunciar outras mtricas de

QoS, utilizando um campo de QoS extensvel. Tendo recebido as mensagens de HELLO estendidas, os ns podem selecionar os seus MPRs utilizando a heurstica

apresentada no algoritmo ilustrado na Figura 4.5.

Figura 4.5: Algoritmo de seleo de MPRs do protocolo QOLSR (Leguay, 2006)

No QOLSR, as mensagens TC so similares s mensagens TC do OLSR tradicional. A diferena que mtricas de QoS, no caso a banda disponvel e atraso fim- a- fim, so informadas para os enlaces anunciados, e o algoritmo de

computao da tabela de roteamento leva essas informaes em considerao

para calcular a tabela de roteamento.

47

Outras mtricas de QoS anunciadas nas mensagens de HELLO tambm podem ser divulgadas utilizando as mensagens TC, e o algoritmo de calculo da

tabela de roteamento tambm pode levar em considerao essas informaes

extras.

Para o clculo da tabela de roteamento proposta uma variao do

algoritmo de Dijkstra, de modo que as rotas calculadas possam maximizar a banda disponvel (mtrica considerada cncava) e minimizar o atraso total do caminho (mtrica considerada aditiva). Entretanto, a proposta do protocolo QOLSR no define com mais detalhes como o algoritmo de Dijkstra deve ser efetivamente modificado para o clculo da tabela de roteamento.

Qayyum (2002) demonstrou que o problema de selecionar MPRs baseado em mltiplas mtricas de QoS NP- completo. Para diminuir a complexidade, o QOLSR prope utilizar a idia apresentada por Wang (1996), que consiste em selecionar rotas com o maior comprimento de banda no gargalo; em caso de

empate, rotas com o menor atraso de propagao so selecionadas. Esses tipos de

caminhos so conhecidos na literatura como shortest- widest paths (caminhos mais curtos - maior alcance).

Uma das vantagens do QOLSR que o protocolo capaz de manipular vrias mtricas de QoS. Embora apenas rotas do tipo shortest- widest paths sejam calculadas por padro, outras mtricas tambm podem ser utilizadas.

Outra vantagem que o QOLSR encontra rotas que realmente so caracterizadas como tendo maior comprimento de banda e menor atraso,

diferente da proposta do OLSR com mudana na heurstica de seleo de MPRs,

em que a rota escolhida a melhor rota das que possui o menor nmero de

saltos, e no a melhor rota em um contexto mais amplo.

Uma das desvantagens do QOLSR a incompatibilidade com as verses padro do OLSR, devido modificao nas mensagens de controle do protocolo.

Outra desvantagem do QOLSR, de acordo com Leguay (2006) que as mtricas de largura de banda e atraso, mtricas bsicas nesta variao do OLSR, so difceis

de medir quando utilizando a camada MAC IEEE 802.11.

48

Embora tcnicas para estimar a capacidade de um enlace IEEE 802.11

tenham sido propostas (Deziel, 2005), Leguay (2006) considera que tais propostas so pouco confiveis em um contexto de redes ad hoc , principalmente devido a

heterogeneidade dos dispositivos que fazem parte da rede . Alm disso, o

algoritmo permite pouca flexibilidade quanto ao uso de outras mtricas, uma vez

que largura de banda e atraso so mtricas bsicas.

4.1.3. OLSR- ETXO menor nmero de saltos a mtrica mais comumente utilizada pelos

protocolos de roteamento ad hoc existentes para calcular rotas timas, tal como

feito pelo OLSR padronizado pelo IETF.

Considerando a instabilidade inerente a um ambiente sem fio, em muitas

situaes o menor nmero de saltos no uma boa escolha. Em situaes em que

a rede sem fio densa, pode haver um grande nmero de rotas com o mesmo

nmero de saltos, entretanto com diferentes qualidades de enlace. Podem

inclusive ocorrer situaes em que uma rota com um nmero maior de saltos

apresente uma qualidade maior que uma rota com um nmero menor de saltos.

Uma extenso ao protocolo OLSR proposta pelo projeto OLSR.ORG utiliza uma nova mtrica, o nmero esperado de transmisses (ETX) (De Couto et al., 2003) para selecionar as melhores rotas. Esta extenso visa encontrar rotas com o menor nmero esperado de transmisses requeridas para que um pacote possa

ser entregue e seu recebimento possa ser confirmado pelo destino final. Em caso

de empate entre um nmero de rotas, a rota com o menor nmero de saltos

escolhida, de modo a manter conformidade com a RFC (Request for Comments) 3626.

4.1.3.1. A Mtrica ETX

A mtrica Expected Transmission Count (ETX) foi proposta por De Couto et al. (2003) e indica o nmero esperado de transmisses, incluindo retransmisses, necessrias para enviar um pacote atravs de um enlace. O clculo do valor ETX

49

feito primeiramente a partir da avaliao da probabilidade de perda de pacotes

em ambos os sentidos de ida e volta do enlace, denotados por p i e p v; a partir do

clculo desses valores o valor ETX do enlace calculado.

Primeiramente calculada a probabilidade da transmisso de um pacote

no ocorrer com sucesso. O protocolo 802.11 requer que, para que uma

transmisso possa ocorrer com sucesso, o pacote deve ser confirmado por meio

do envio de um pacote ACK. Considere, portanto, p como sendo a probabilidade

de uma transmisso entre os ns A e B no ocorrer com sucesso. A frmula para

o clculo desta probabilidade apresentada no Quadro 4.1.

p = 1 - (1 - p i) * (1 - p v)Quadro 4.1 probabilidade de uma transmisso no ocorrer com sucesso

O protocolo IEEE 802.11 ir retransmitir um pacote cuja transmisso no ocorreu com sucesso. Supondo que s(k) a probabilidade de uma transmisso ocorrer com sucesso entre os ns A e B aps k tentativas, temos a frmula

apresentada no Quadro 4.2.

s(k) = p k- 1 * (1 - p)Quadro 4.2 probabilidade de uma transmisso ocorrer com sucesso aps k

tentativas

Finalmente, o nmero esperado de transmisses requerido para que a

transmisso de um pacote possa ocorrer com sucesso entre dois ns A e B,

denotado por ETX, apresentado no Quadro 4.3.

ETX = k*s(k)=1 /(1 - p) k=1

Quadro 4.3 nmero esperado de transmisses em um enlace

50

Para calcular a mtrica ETX, primeiramente avaliado o nmero de

seqncia dos pacotes de controles do OLSR gerados pelos vizinhos para a

deteco de perdas. A partir dessa avaliao calculada a taxa de perda de

pacotes enviados pelos ns vizinhos. O valor calculado indica a taxa de perda de

pacotes em uma direo do enlace, isto , do n vizinho ao n atual, e

conhecida como Qualidade do Enlace (Link Quality, LQ).No entanto, necessrio conhecer a qualidade do enlace na direo oposta,

isto , quantos pacotes enviados pelo n atual so atualmente recebidos pelos

Documents

Provisionamento de QoS Em Redes Ad Hoc Sem Fio Utilizando Medição de Retardo de Enlace TCC Weverton