Uso de small worlds no roteamento em redes de sensores sem fio · Palavras-chave: Redes de Sensores Sem Fio, Roteamento, RSSF, Small Worlds, Overlay. iii. iv. Abstract ... hoc ´e

Uso de small worlds

no roteamento emredes de sensores sem fio

Giulian Dalton Luz

Dissertacao/Tese apresentadaao

Instituto de Matematica e Estatısticada

Universidade de Sao Paulopara

obtencao do tıtulode

Mestre em Ciencias

Area de Concentracao: Ciencia da Computacao

Orientador: Prof. Dr. Alfredo Goldman

Sao Paulo, fevereiro de 2008

Uso de small worlds

no roteamento emredes de sensores sem fio

Este exemplar corresponde a redacaofinal da dissertacao devidamente corrigida

e defendida por Giulian Dalton Luze aprovada pela Comissao Julgadora.

Banca Examinadora:

• Prof. Dr. Alfredo Goldman - IME-USP (orientador).

• Prof. Dr. Jose Augusto Ramos Soares - IME-USP.

• Prof. Dr. Sergio Takeo Kofuji - POLI-USP.

Agradecimentos

Meus sinceros agradecimentos a minha famılia que sempre me apoiou, aos meus amigos e colegas quede perto ou de longe me acompanharam nesta jornada, aos funcionarios e professores do IME-USP,que direta ou indiretamente tornaram esta realizacao possıvel e, em especial, a minha noiva por todocarinho e compreensao e ao meu orientador por toda atencao e apoio.

i

ii

Resumo

Neste trabalho foi realizado um estudo sobre o uso e influencias do efeito small world, ou seis graus deseparacao, no roteamento de redes de sensores sem fio (RSSFs). Para esse objetivo, foram analisadasas caracterısticas das RSSFs que influenciam no roteamento e os diferentes tipos de protocolos. Alemdisso, foram estudadas as caracterısticas do efeito small world e suas propriedades, de um modogeral, em redes de larga escala e com alta densidade de nos, incluindo o modelo de small world parao estudo de redes ad hoc. Realizou-se um breve estudo sobre redes overlay, redes logicas criadassobre a rede fısica com o proposito de melhorar suas qualidades e seu desempenho. A conclusaoneste trabalho e que small worlds pode ser empregado para melhorar o funcionamento de protocolosde roteamento em RSSFs.

Palavras-chave: Redes de Sensores Sem Fio, Roteamento, RSSF, Small Worlds, Overlay.

iii

iv

Abstract

In this work, has made an study about the use and influences of the small world effect, or six degrees ofseparation, in routing of wireless sensors network (WSNs). For this objective, was analyzed the cha-racteristics of WSNs that influence in the routing and the different types of protocols. Moreover, wasstudied the characteristics of small world effect and it properties, generically, in large scale networkswith a high node density, including the small world model for the study of ad hoc networks. Wasaccomplished a brief study about overlay networks, logical network created over physical networkwith the purpose of improve qualities and performance. The conclusion in this work is that smallworlds can be applied to improve the operation of WSNs routing protocols.

Keywords: Wireless Sensor Networks, Routing, WSN, Small Worlds, Overlay.

v

vi

Sumario

Lista de Figuras xi

Lista de Tabelas xiii

1 Introducao 1

1.1 Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.2 Contribuicoes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.3 Organizacao do Trabalho . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2 Conceitos 5

2.1 Redes de sensores sem fio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2.2 Small worlds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2.3 Small worlds em RSSFs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2.4 Redes overlay . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

3 Redes de sensores sem fio 9

3.1 Introducao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

3.2 Caracterısticas das redes de sensores . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

3.2.1 Caracterısticas segundo a configuracao . . . . . . . . . . . . . . . . . . . . . . . 10

3.2.2 Caracterısticas segundo o sensoriamento . . . . . . . . . . . . . . . . . . . . . . 12

vii

viii SUMARIO

3.2.3 Caracterısticas segundo a comunicacao . . . . . . . . . . . . . . . . . . . . . . . 12

3.2.4 Caracterısticas segundo o processamento . . . . . . . . . . . . . . . . . . . . . . 17

4 Protocolos de roteamento 19

4.1 Introducao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

4.2 Protocolos de roteamento ad hoc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

4.3 Protocolos de roteamento plano . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

4.3.1 Protocolo Difusao Direcionada . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

4.3.2 Protocolo SPIN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

4.3.3 Protocolo SAR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

4.3.4 Protocolo Adaptive Local Routing Cooperative Signal Processing . . . . . . . . 27

4.3.5 Protocolo Multi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

4.3.6 Protocolo STORM/AD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

4.4 Protocolos de roteamento hierarquico . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

4.4.1 Protocolo PROC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

4.4.2 Protocolo LEACH . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

4.4.3 Protocolo TEEN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

4.4.4 Protocolo APTEEN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

4.4.5 Protocolo SHARP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

4.4.6 Protocolo PEGASIS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

4.5 Protocolos de roteamento geografico . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

4.5.1 Protocolo LEACH-C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

4.5.2 Protocolo ICA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

4.5.3 Protocolo Geographic Routing without Location Information . . . . . . . . . . 39

4.5.4 Protocolo GeoMote . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

SUMARIO ix

4.5.5 Protocolo GEAR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

4.5.6 Protocolo GPSR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

4.6 Estudo comparativo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

5 Small worlds 49

5.1 O fenomeno small world . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

5.2 Propriedades de redes small world . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

5.3 Small worlds no mundo real . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

5.4 Formalizando o fenomeno small world . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

5.5 Uma modelagem para small worlds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

5.6 Grafos aleatorios geometricos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

5.6.1 Modelando redes ad hoc sem fio com grafos aleatorios geometricos . . . . . . . 63

6 Small worlds em RSSFs 67

6.1 Uso de small worlds em RSSFs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

7 Redes overlay 75

7.1 Uso de redes overlay . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

7.2 Redes overlay em redes de sensores sem fio . . . . . . . . . . . . . . . . . . . . . . . . 76

8 Conclusao 79

8.1 Consideracoes Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

8.2 Trabalhos futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

Referencias Bibliograficas 83

x SUMARIO

Lista de Figuras

3.1 Exemplo de rede com organizacao plana. As arestas indicam conectividade. . . . . . . 10

3.2 Exemplo de rede com organizacao hierarquica . . . . . . . . . . . . . . . . . . . . . . . 11

3.3 Fluxo de inundacao. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

3.4 Fluxo multicast. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

3.5 Fluxo unicast. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

3.6 Fluxo gossiping. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

3.7 Fluxo bargaining. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

4.1 Protocolo difusao direcionada, gradiente. . . . . . . . . . . . . . . . . . . . . . . . . . . 22

4.2 Protocolo difusao direcionada, propagacao de interesse . . . . . . . . . . . . . . . . . . 23

4.3 Protocolo difusao direcionada, estabelecimento de rota . . . . . . . . . . . . . . . . . . 23

4.4 Interacao entre auto-organizacao e roteamento. . . . . . . . . . . . . . . . . . . . . . . 30

4.5 Diagrama esquematico do protocolo STORM/AD. . . . . . . . . . . . . . . . . . . . . 31

4.6 Funcionamento do protocolo SHARP. . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

4.7 Funcionamento do protocolo PEGASIS. . . . . . . . . . . . . . . . . . . . . . . . . . . 36

4.8 Envio de dados no GeoMote. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

4.9 Roteamento de perımetro no GPSR. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

xi

xii LISTA DE FIGURAS

5.1 Exemplo de Watts e Strogatz onde k = 2. As arestas aleatorias estao destacadas (maisclaras). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

5.2 Esquema de uma construcao caveman conexa. . . . . . . . . . . . . . . . . . . . . . . 60

5.3 Exemplo de rede unidimensional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

6.1 Reducao do comprimento dos caminhos e da aglomeracao por probabilidade de reco-nexao. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

6.2 Reducao do comprimento dos caminhos por distancia maxima de contato r. . . . . . . 71

6.3 Contatos a r saltos, reducao maxima do comprimento dos caminhos e em r/d ∼25%− 40%. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

Lista de Tabelas

4.1 A - Classificacao e comparacao de protocolos de roteamento para RSSFs. . . . . . . . 45

4.2 B - Classificacao e comparacao de protocolos de roteamento para RSSFs. . . . . . . . 46

4.3 C - Classificacao e comparacao de protocolos de roteamento para RSSFs. . . . . . . . 47

6.1 Topologias simuladas por Helmy. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

6.2 Aglomeracao, comprimento dos caminhos e comprimento maximo para as redes originais. 69

xiii

xiv LISTA DE TABELAS

Capıtulo 1

Introducao

Redes ad hoc sao utilizadas em muitos tipos de aplicacoes. Dentre os mais comuns temos:

• redes de sensores sem fio;

• aplicacoes militares que necessitam de uma rede descentralizada;

• operacoes de busca, resgate, desastres e combates a incendio que necessitam de uma redeformada rapidamente;

• redes de acesso publico em areas urbanas que necessitam de facil implantacao e coberturaestendida, como por exemplo em shoppings, hoteis, universidades, dentre outros;

• convencoes cujos participantes necessitem transmitir ou compartilhar informacoes;

• redes de taxis;

• redes de comunicacao de veıculos (sistemas de alerta para prevenir acidentes, distancia segurapara controle de direcao, trens, aeroportos, etc.).

Uma rede ad hoc permite que os elementos da rede estabelecam comunicacao a qualquer momentoe em qualquer lugar (ubiquidade) sem a necessidade do apoio de uma infra-estrutura. Uma rede adhoc e estabelecida por seus participantes de modo dinamico. Uma nocao para uma rede movel adhoc e dada por Frodigh et. al em [FJL00]: uma rede movel ad hoc e uma rede formada sem umaadministracao central composta de nos moveis que utilizam uma interface sem fio (Bluetooth, 802.11,

1

2 CAPITULO 1. INTRODUCAO

HiperLAN2, UWB, etc.) para enviar pacotes de dados. Os nos desta rede podem servir como ro-teadores ou servidores e podem repassar pacotes de outros nos, alem de executar aplicacoes de usuario.

As redes moveis ad hoc (MANET - Mobile Ad hoc Network) se destacam por serem de facil im-plementacao, uteis quando ha ausencia ou impossibilidade do uso de uma infra-estrutura, pois naonecessitam de nenhuma estrutura fixa. Alem disso, nem sempre e possıvel ter uma estrutura fixa ea comunicacao pode ser de curto alcance. As redes ad hoc tambem se destacam em redes de curtoalcance, pois utilizam uma estrategia multi-saltos (multi-hop) para permitir a comunicacao entreelementos distantes.

RSSFs podem ser vistas como um tipo especial de rede movel ad hoc [LNR+03]. Estas redes, emgeral, sao compostas por um grande numero de nos chamados sensores. Os nos sensores podem serlancados sobre areas remotas (reservas ambientais, oceanos, vulcoes, rios, florestas, etc.) formando,sem intervencao, uma rede sem fio ad hoc que coleta dados sobre os fenomenos de interesse daaplicacao (temperatura, mobilidade, pluviometria, etc.).

1.1 Objetivos

Neste trabalho realizou-se um estudo sobre as caracterısticas das RSSFs e seus protocolos de rote-amento com o proposito de analisar o uso do efeito small world para melhorar a eficiencia destesprotocolos, pois uma de suas caracterısticas e a existencia de poucos intermediarios entre dois nosquaisquer em uma rede sob este efeito. Alem disso, tambem foi abordado o modelo de grafos aleatoriosgeometricos, reforcando o modelo small world e seus resultados.

O estudo sobre redes overlay, por sua vez, visou encontrar uma forma de implantar as caracterısticasdo efeito small world de forma transparente para a rede fısica atraves da criacao de uma rede logicasobre sua infra-estrutura.

1.2. CONTRIBUICOES 3

1.2 Contribuicoes

Ate o momento, este e o primeiro trabalho que combina o uso de duas tecnicas muito pesquisadasna area de ciencia da computacao, small worlds e redes overlay.

1.3 Organizacao do Trabalho

O capıtulo 1 fornece uma introducao para o trabalho e apresenta alguns conceitos basicos sobre osassuntos estudados. No capıtulo 3 ha uma abordagem sobre as caracterısticas de redes de sensoressem fio. O capıtulo 4 aborda os protocolos de roteamento para estas redes, divididos em quatrocategorias: ad hoc, plano, hierarquico e geografico. Posteriormente, no capıtulo 5, ha um estudosobre o fenomeno small world onde sao apresentadas suas caracterısticas e modelos matematicos.No capıtulo 6 ha um estudo sobre small worlds em RSSFs, sao apresentadas algumas formas de usoe alguns protocolos para este contexto. Na sequencia, e apresentado no capıtulo 7 o conceito de redesoverlay, suas caracterısticas e algumas de suas aplicacoes, inclusive em RSSFs. Por fim, a conclusaono capıtulo 8 mostra a aplicabilidade do efeito small world em redes de sensores efetuando-se umaanalise detalhada em diversas abordagens existentes, incluindo o uso de overlay para criar uma redelogica contemplando small worlds.

4 CAPITULO 1. INTRODUCAO

Capıtulo 2

Conceitos

Este capıtulo fornece uma breve descricao sobre os principais conceitos abordados neste trabalho.

2.1 Redes de sensores sem fio

Um dos maiores desafios de uma RSSF esta relacionado com o consumo de energia dos nos sensores.Como o radio e o equipamento com maior consumo de energia, o protocolo de roteamento deve garan-tir que nao haja comunicacoes desnecessarias de modo a economizar energia na rede. Os protocolosde roteamento existentes para as redes convencionais ou para as redes moveis ad hoc, originalmente,nao se aplicam a esse contexto, pois nao consideram as limitacoes e caracterısticas de uma RSSF eportanto necessitam de adaptacoes para se tornarem factıveis a este tipo de rede.

No mundo cientıfico existem inumeras pesquisas em RSSF e, em especial, sobre protocolos de rotea-mento para as mais variadas arquiteturas de RSSF como em [AKK04], [LNR+03], [DEA05] e [AY05].Recentemente, ha uma preocupacao em relacao a seguranca e ataques na elaboracao dos algoritmosde roteamento para RSSFs como em [KW03], [NSSP04], [S+04] e [WS02].

Os requisitos de um protocolo de roteamento para RSSFs diferem de acordo com as caracterısticasde cada tipo de RSSF descritos na secao 3.2 a seguir. Estas caracterısticas determinam possıveisdificuldades na comunicacao entre os nos da rede e permitem que, em cada caso, diferentes tecnicasde roteamento possam ser empregadas.

5

6 CAPITULO 2. CONCEITOS

Os objetivos principais de um protocolo de roteamento sao: considerar a limitacao de uma RSSF,minimizar as dificuldades relativas as caracterısticas da rede e empregar tecnicas com base nestascaracterısticas para melhorar o roteamento. As principais melhorias em um protocolo de roteamentosao:

• Minimizar o consumo de energia;

• Maximizar o tempo de vida util dos nos;

• Ser tolerante a falhas;

• Garantir eficiencia na comunicacao;

• Garantir eficiencia na disseminacao de dados.

2.2 Small worlds

O termo small world vem da observacao que dois indivıduos distintos estao frequentemente ligadospor uma pequena cadeia de conhecidos comuns. O fenomeno small world [Mil67] e [PK78] e umobjeto de fascinacao popular e anedotas. A experiencia de encontrar uma pessoa completamenteestranha com quem nao se tem nada em comum e descobrir que existe uma lista de conhecidos quee familiar para ambos e um small world.

De um modo mais generico, a ideia de que dois indivıduos quaisquer, selecionados aleatoriamentede algum lugar qualquer do planeta, estejam conectados por uma cadeia de nao mais do que seisconhecidos intermediarios define small worlds. Este fenomeno tambem e conhecido como seis grausde separacao [Gua90].

Uma rede small world pode ser definida como um grupo de small worlds altamente aglomerados quenao estao altamente conectados uns aos outros [KB05]. Uma rede small world e um modelo entreuma rede regular e um grafo aleatorio [New03]. Em uma rede regular os nos vizinhos possuem umgrande numero de interconexoes, mas nos distantes possuem poucas. Redes regulares sao altamenteaglomeradas, em outras palavras, existe uma alta densidade de conexoes entre os nos vizinhos, maspossuem caminhos de comprimento longo, ou seja, entre dois nos distantes entre si existem muitosnos intermediarios. Em um grafo aleatorio os nos sao conectados aleatoriamente. Redes aleatorias

2.3. SMALL WORLDS EM RSSFS 7

sao altamente nao aglomeradas mas possuem caminhos de comprimento pequeno. Devido a aleatori-edade e pouco provavel que os nos vizinhos possuam muitas conexoes, porem, existem mais conexoesque interligam uma parte da rede a outra.

O fenomeno small world pode ser utilizado como um arcabouco para examinar as propriedades deredes compostas por um numero muito grande de nos. Uma rede small world pode atuar comomodelo para uma rede complexa, ou seja, um modelo entre um grafo regular e um grafo aleatorio.

Outro modelo complementar ao small worlds e o modelo de grafo aleatorio geometrico. Os grafosaleatorios geometricos [NV03] diferem de um grafo aleatorio pois suas conexoes sao limitadas peladistancia geometrica dos nos. Como as conexoes de uma rede ad hoc sao limitadas pelo alcance doradio, os grafos aleatorios geometricos sao bons modelos para o estudo de redes ad hoc, alem disso,como ocorre com small worlds, e possıvel determinar caminhos com poucos intermediarios e uma altaconectividade na rede e garantida. Assim como o small world, tambem e um modelo entre um graforegular e um grafo aleatorio. Na literatura, varios autores abordam seu uso em redes ad hoc, comoem [Hek05], [NV03], [Pen99], [Bet02], [DPS98] e [HM04].

2.3 Small worlds em RSSFs

A aplicacao de small worlds em protocolos de roteamento e algo muito interessante, pois uma desuas principais atividades e encontrar de forma eficiente um caminho entre dois nos e em uma redesob este efeito o numero de nos intermediarios entre dois nos quaisquer e aproximadamente seis.Esta caracterıstica ja foi comprovada para redes sociais, inclusive para redes de larga escala e altadensidade [Wat99b]. Destas consideracoes, deriva uma questao interessante: qual a influencia doefeito small world em uma RSSF? Este trabalho analisou o uso de small worlds nos protocolos deroteamento para redes de sensores sem fio.

2.4 Redes overlay

Redes overlay sao redes logicas construıdas sobre redes fısicas. Atraves da monitoracao da rede,pode-se determinar qual e o melhor caminho entre dois nos, com base nos atributos de cada no e deseus vizinhos. Alem disso, permitem aumentar a conectividade de uma rede sem perda de desempe-

8 CAPITULO 2. CONCEITOS

nho. Uma caracterıstica muito interessante, que e a principal razao de seu estudo neste trabalho, ea possibilidade de implantar overlay de forma transparente a rede fısica, isso traz a possibilidade deaplicar overlay em diversos tipos de redes e aplicacoes.

Overlay nao e um conceito novo, atualmente existem muitos trabalhos para diversos tipos de redecomo em: [MOL03], [Fre], [Gnu], [ST02], [Pen03], [ABKM01], [ZK], [KB96], [GM03], [AAG+05],[DO03] e [AR06].

Capıtulo 3

Redes de sensores sem fio

Este capıtulo apresenta um resumo das principais caracterısticas de uma RSSF. Nele ha uma seriede abordagens que classificam as redes de sensores segundo sua configuracao, sensoriamento, comu-nicacao e processamento [Rui03].

3.1 Introducao

RSSFs em geral, sao compostas por uma alta densidade nos, ou seja, os elementos da rede sao emgrande quantidade. Uma RSSF pode ser usada para monitorar e, eventualmente, controlar um ambi-ente. Este tipo de rede e formado geralmente por centenas ou milhares de dispositivos autonomos quetendem a ser projetados com pequenas dimensoes (cm3 ou mm3) chamados nos sensores [RCV+04].Os principais componentes de um no sensor sao radio para comunicacao sem fio, fonte de energia,unidade de sensoriamento, memoria e processador [RCV+04]. Existem casos em que uma RSSFtambem pode ser composta de dispositivos chamados atuadores que permitem ao sistema controlarparametros do ambiente monitorado.

Os nos sensores de uma RSSF formam uma rede ad hoc sem fio para coletar dados do ambienteno qual eles foram implantados, realizam algum processamento local e disseminam as informacoespara o ponto de acesso em um esquema de comunicacao multi-saltos [RCV+04]. O ponto de acessoe o elemento atraves do qual a rede comunica-se com outras redes ou com um ou mais observado-res [RNL03]. O ponto de acesso pode ser implementado em um no sensor que sera chamado de nosorvedouro (sink node) ou em uma estacao base (BS - Base Station). Em geral, as redes ( ad hoc)

9

10 CAPITULO 3. REDES DE SENSORES SEM FIO

que necessitam de integracao com outras redes, como por exemplo redes LAN (Local Area Network)ou acesso a Internet, sao formadas por pontos de acesso sem fio, que podem ser fixos ou moveis.

3.2 Caracterısticas das redes de sensores

Cada tipo de RSSF e classificada conforme os ıtens que serao descritos a seguir e tais caracterısticasinfluenciam diretamente nas caracterısticas de um protocolo de roteamento ideal.

3.2.1 Caracterısticas segundo a configuracao

Composicao

• Homogenea - Composta por nos que apresentam mesma capacidade fısica. Eventualmente osnos podem executar softwares diferentes;

• Heterogenea - Composta por nos com diferentes capacidades fısicas.

Organizacao

• Plana - Nos nao sao organizados em aglomerados e portanto nao ha hierarquia entre eles. Osnos possuem funcoes equivalentes;

Figura 3.1: Exemplo de rede com organizacao plana. As arestas indicam conectividade.

3.2. CARACTERISTICAS DAS REDES DE SENSORES 11

• Hierarquica - Nos estao organizados em aglomerados (clusters). Cada aglomerado possui umlıder (cluster-head) que pode ser eleito pelos nos comuns. Ha nos com diferentes funcoes. Osaglomerados podem organizar hierarquias entre si.

Figura 3.2: Exemplo de rede com organizacao hierarquica

Mobilidade

• Estacionaria - Todos os nos permanecem no local onde foram depositados durante todo otempo de vida da rede;

• Movel - Os nos sensores podem ser deslocados do local onde foram inicialmente depositados.

Densidade

• Densa - Alta concentracao de nos por unidade de area;

• Esparsa - Baixa concentracao de nos por unidade de area;

• Balanceada - Concentracao de nos por unidade de area e ideal, sendo que a concentracao e amesma por toda a area de monitoracao.

Distribuicao

• Irregular - Distribuicao nao uniforme dos nos em uma area de monitoracao;

• Regular - Distribuicao uniforme dos nos em uma area de monitoracao.


3.2.2 Caracterısticas segundo o sensoriamento

Coleta

• Periodica - Os nos sensores coletam dados sobre o(s) fenomeno(s) em intervalos regulares.Como exemplo temos as aplicacoes que monitoram o canto dos passaros. Os sensores efetuama coleta durante o dia e permanecem desligados durante a noite;

• Contınua - Os nos sensores permanecem ligados para coletar os dados de forma ininterrupta.Como exemplo temos as aplicacoes de exploracao interplanetaria que coletam dados continua-mente para a formacao de base de dados para pesquisa;

• Reativa - Os nos sensores coletam dados quando ocorrem eventos de interesse ou quandosolicitado pelo observador. Como exemplo temos as aplicacoes que detectam a presenca deobjetos em areas monitoradas;

• Tempo real - Os nos sensores coletam a maior quantidade de dados possıvel no menor intervalode tempo. Como exemplo temos aplicacoes que envolvem risco para vidas humanas, tais comoaplicacoes em escombros ou areas de desastres. Um outro exemplo sao as aplicacoes militares,cujos dados coletados sao importantes na tomada de decisoes e definicao de estrategias.

3.2.3 Caracterısticas segundo a comunicacao

Disseminacao

Disseminacao e o ato de um no enviar para outros nos da rede informacoes sobre os dados coletadospor seu sensor. Para a disseminacao temos as seguintes caracterısticas:

• Programada - Os nos disseminam dados em intervalos regulares;

• Contınua - Os nos disseminam dados continuamente;

• Sob demanda - Os nos disseminam dados em resposta a consulta do observador e na ocorrenciade eventos.

Tipo de Conexao


• Simetrica - Todas as conexoes existentes entre os nos sensores, com excecao do no sorvedouro,possuem o mesmo alcance;

• Assimetrica - As conexoes entre os nos comuns possuem alcances diferentes.

Transmissao

• Simplex - Os nos sensores possuem radio que permite apenas o envio de dados;

• Half-duplex - Os nos sensores possuem radio que permite transmitir ou receber dados em umdeterminado instante;

• Full-duplex - Os nos sensores possuem radio que permite transmitir e receber dados simulta-neamente.

Alocacao de Canal

• Estatica - Neste tipo de rede, considerando n nos, temos as seguintes estrategias de alocacaode canal [Sch03]:

– FDMA - Frequency Division Multiple Access - A largura de banda e dividida emn partes iguais na frequencia;

– TDMA - Time Division Multiple Access - A largura de banda e dividida em n partesiguais no tempo;

– CDMA - Code Division Multiple Access - A largura de banda e dividida em n partesiguais pelo codigo;

– SDMA - Space Division Multiple Access - A largura de banda e dividida em n partesiguais no espaco.

A cada no e atribuıda uma parte privada da comunicacao, minimizando interferencias;

• Dinamica - Neste tipo de rede nao existe atribuicao fixa de largura de banda. E um processoautomatico para atribuicao de canais em um sistema sem fio de reuso de frequencia, cujos osnos disputam o canal para comunicacao de dados. A estacao base monitora continuamentea interferencia em todos os canais desocupados e efetua as atribuicoes de canais usando umalgoritmo que determina o canal que ira produzir a menor quantidade de interferencia adicional.


Fluxo de Informacao

• Inundacao (Flooding) - Os nos sensores fazem difusao (broadcast) de suas informacoes paratodos os seus vizinhos que por sua vez fazem difusao desses dados para outros e assim sucessiva-mente ate alcancar o ponto de acesso. Essa abordagem promove um alto sobrecusto (overhead)mas esta imune as mudancas dinamicas de topologia e a alguns ataques de impedimento deservico (Dos - Denial of Service) [WS02]. Veja a figura 3.3, na qual e mostrada a propagacaode uma unica informacao por um no;

Figura 3.3: Fluxo de inundacao.

• Multicast - Os nos formam grupos e utilizam o multicast para comunicacao entre os mem-bros do grupo. Os dados sao enviados da origem para muitos nos. Veja a figura 3.4, na qual emostrada a propagacao de uma unica informacao por um no, observe que as comunicacoes saoem menor quantidade em relacao a inundacao;


Figura 3.4: Fluxo multicast.

• Unicast - Os nos sensores podem se comunicar diretamente com o ponto de acesso utilizandoprotocolos de roteamento multi-saltos. Os dados sao enviados da origem para apenas um no.Veja a figura 3.5, na qual e mostrada a propagacao de uma unica informacao por um no, observeque cada no envia a informacao para apenas um vizinho;

Figura 3.5: Fluxo unicast.

• Gossiping [HHL06] - Os nos sensores encaminham dados com uma certa probabilidade,assumindo que qualquer no da rede pode enviar um dado para outro no, ou atraves de uma


conexao direta ou por uma rota conhecida para o no destino. Veja a figura 3.6;

Figura 3.6: Fluxo gossiping.

• Bargaining [KHB02] - Os nos enviam dados somente se o no destino manifestar interesse,pois existe um processo de negociacao. Este processo ocorre em tres fases, primeiro um nopergunta a outro se ele deseja receber um dado, se o no receptor ja o possui ele recusa, casocontrario ele aceita a conexao e o dado e transmitido. Na figura 3.7 as setas simples indicam ointeresse manifestado e as setas em destaque indicam o envio dos dados para o no interessado.

Figura 3.7: Fluxo bargaining.


3.2.4 Caracterısticas segundo o processamento

Cooperacao

• Infra-estrutura - Os nos sensores executam procedimentos relacionados a infra-estrutura darede como, por exemplo, algoritmos de controle de acesso ao meio, roteamento, eleicao delıderes, descoberta de localizacao e criptografia;

• Localizada - Os nos sensores executam, alem dos procedimentos de infra-estrutura, algumtipo de processamento local basico como, por exemplo, a traducao dos dados coletados pelossensores baseado em sua calibracao;

• Correlacao - Capacidade de uma RSSF de agregar ou sumarizar dados coletados pelos sensores,cujo objetivo e reduzir o numero de mensagens transmitidas pela rede. Algumas tecnicas quepodem ser empregadas sao: agregacao, fusao, supressao seletiva, contagem, compressao e multi-resolucao.


Capıtulo 4

Protocolos de roteamento

Neste capıtulo serao apresentados alguns dos protocolos de roteamento existentes, divididos em 4categorias: protocolos de roteamento ad hoc, protocolos de roteamento plano, protocolos de rotea-mento hierarquico e protocolos de roteamento geografico.

4.1 Introducao

As RSSFs diferem das redes tradicionais em diversos aspectos. Um no de uma RSSF possui recursoslimitados, tais como: restricoes de energia, pouco poder de processamento e pouca capacidade arma-zenamento. Estas limitacoes interferem diretamente nas caracterısticas dos protocolos de roteamento.

Cada no de uma RSSF, em geral, possui pouca capacidade de armazenamento, processamento eenergia e, por esse motivo, para realizarmos tarefas nesta rede e necessaria a colaboracao entre seusnos sensores. Nesta colaboracao os nos precisam trocar informacoes entre si e, para isso, e necessarioo uso de um protocolo de roteamento que utilize os recursos da rede de uma forma eficiente. Aprincipal atividade de um protocolo de roteamento e garantir que as mensagens de um no sejamentregues ao ponto de acesso e, para isso, e fundamental que o protocolo encontre uma rota eficienteentre a origem e o destino.

Os principais aspectos a serem considerados em um protocolo de roteamento sao:

1. Recursos limitados - A quantidade de energia, a capacidade de processamento e o alcance

19

20 CAPITULO 4. PROTOCOLOS DE ROTEAMENTO

de comunicacao dos sensores de uma RSSF sao limitados;

2. Topologia dinamica - Os protocolos devem considerar a mobilidade dos sensores e isto implicaem mudancas na topologia da rede. Em redes de sensores este nao e o unico fator que podecausar mudancas na topologia, devemos considerar tambem mudancas ocasionadas quando nosdeixam de operar por falta de energia, problemas na disposicao, ameacas e ataques a seguranca,falhas nos componentes e falha de comunicacao [Rui03] ou ate mesmo quando sao destruıdosou desligam o radio para economizar energia. Por haver falha de nos deve-se considerar aredundancia de informacoes para garantir o bom funcionamento da rede;

3. Tempo de vida de rede - O tempo de vida de uma RSSF deve ser o maior possıvel paraminimizar o custo de manutencao da rede. Deve-se considerar tambem o problema da existenciade areas isoladas, pois quando um no esgota sua energia ele deixa de participar da rede e havendoum numero elevado de nos ausentes algumas regioes podem ficar isoladas. Isolamentos ocorremdevido a inexistencia de nos intermediarios e pela limitacao do alcance do radio, que permitiriamalcancar outras regioes na rede.

O processamento local dos dados atraves de correlacao (fusao, contagem, agregacao, compressao,etc.) tambem sao requisitos a serem considerados no projeto dos protocolos para disseminacao econsulta aos nos sensores, assim como os requisitos de seguranca em cada uma das camadas da pilhade protocolos [RCV+04].

Quanto a classificacao usada neste capıtulo os protocolos ad hoc sao aqueles que consideram umarede que nao depende de infra-estrutura previa, na qual todos os recursos sao alocados pelos par-ticipantes da rede e nao por uma estacao base e os servicos disponıveis dependem unicamente dosparticipantes. Os protocolos planos consideram igualmente todos os nos da rede, nao havendo nosespeciais. Ja os protocolos hierarquicos consideram a existencia de nos lıderes, fixos ou dinamicos,que possuem uma participacao especial no roteamento. Por fim, os protocolos geograficos sao aquelesque consideram o posicionamento, real ou virtual, dos nos da rede para a determinacao de rotas.

Neste trabalho nao serao abordados os protocolos de acesso ao meio (MAC).

4.2. PROTOCOLOS DE ROTEAMENTO AD HOC 21

4.2 Protocolos de roteamento ad hoc

Os protocolos de roteamento ad hoc devem lidar com limitacoes tıpicas desses tipos de rede, taiscomo: consumo de energia dos nos moveis, banda passante limitada e altas taxas de erro. A bandapassante de um meio fısico analogico e a faixa de frequencia onde o meio fısico e capaz de preservar osinal e a banda passante de um meio fısico digital e a quantidade de dados que pode ser transmitidapor um no em um dado momento. Quanto maior a banda passante, maior a quantidade de trafegoque o no pode tratar a cada momento.

Basicamente, ha tres grupos de protocolos de roteamento ad hoc: reativos, pro-ativos e hıbridos. Osprotocolos reativos utilizam, em geral, algoritmos do tipo table-driven, aqueles que possuem tabelasde roteamento para manter a consistencia das informacoes de roteamento em todos os nos. Ja ospro-ativos utilizam algoritmos do tipo on-demand, aqueles que criam rotas somente quando desejadopor um no fonte. Por fim, os protocolos hıbridos utilizam os dois tipos de algoritmos, se adaptandode acordo com a necessidade da rede de ser mais reativa ou pro-ativa.

Dentre os protocolos table-driven destacam-se: DSDV (Destination-Sequenced Distance-Vector Rou-ting) [PB94], WRP (Wireless Routing Protocol) [MGLA95] e CGSR (Cluster-head Gateway SwitchRouting) [MGLA96]. Dentre os protocolos on-demand destacam-se: AODV (Ad Hoc On-DemandDistance Vector Routing) [Per97], DSR (Dynamic Source Routing) [JMH96], LMR (LightweightMobile Routing), TORA (Temporally Ordered Routing Algorithm), ABR (Associativity-Based Rou-ting) [CE95] e SSR (Signal Stability Routing) [PC01].

4.3 Protocolos de roteamento plano

No roteamento plano todos os nos sao considerados iguais do ponto de vista funcional, ou seja, aatividade de roteamento e tratada de forma identica por todos os nos da rede. Alguns representantesimportantes desta classe de algoritmos sao representados a seguir.


4.3.1 Protocolo Difusao Direcionada

O protocolo Difusao Direcionada [IGE00] tem como meta estabelecer canais de comunicacao eficien-tes entre os nos sensores e a estacao base. Este algoritmo efetua um roteamento baseado nos dados.O roteamento baseado nos dados ocorre atraves do pedido de informacao de interesse. Quando algumno possui alguma informacao que e de interesse de outro no ele envia esta informacao ao no que apediu.

Figura 4.1: Protocolo difusao direcionada, gradiente.

O modo de funcionamento basico da difusao direcionada pode ser descrito da seguinte maneira: umpedido de sensoriamento e disseminado pela rede na forma de um interesse e os nos que possuem talinformacao a transmitem ao no interessado.

Este protocolo e centrado em dados, cujos nos nao sao enderecados por seus enderecos fısicos na rede,mas sim pelos dados que monitoram. Os dados sao nomeados por pares de atributo/valor.

No protocolo difusao direcionada o interesse e expresso pelos nos observadores em termos de umaconsulta que se difunde pela rede usando interacoes locais. Tais interesses estabelecem gradientes de

4.3. PROTOCOLOS DE ROTEAMENTO PLANO 23

dados para o no que expressou o interesse, veja a figura 4.1. Uma vez que um no sensor que satisfaza consulta (no fonte) e alcancado ele comeca a transmitir dados para o no que solicitou a consulta,novamente utilizando interacoes locais. A ausencia de uma identificacao global (por exemplo umendereco IP) torna a difusao direcionada eficiente para redes com mobilidade. Veja um exemplonas figuras abaixo. Na figura 4.2 o no z propaga um interesse para toda a rede. Este interesse ereencaminhado ate alcancar o no x, que possui os dados solicitados. Neste momento, como podemosobservar na figura 4.3, uma rota para z, incluindo o no intermediario y, e estabelecida no caminhocontrario a propagacao do interesse (gradiente). A partir daı, z transmite os dados para y que, porsua vez, os reencaminha para z.

Figura 4.2: Protocolo difusao direcionada, propagacao de interesse

Figura 4.3: Protocolo difusao direcionada, estabelecimento de rota

Este protocolo e aplicavel para redes orientadas a eventos e orientadas a consulta. As interacoeslocalizadas permitem ao protocolo ser escalavel para redes grandes. O protocolo difusao direcionadaescala em funcao do numero de interesses ativos presentes na rede.


4.3.2 Protocolo SPIN

O SPIN (Sensor Protocols for Information via Negotiation) [HKB99] e um conjunto de protocolos deroteamento que incorpora duas ideias principais: negociacao e adaptacao de recursos. Para evitaro problema da implosao e do overlap, os nos SPIN negociam com os outros nos antes de transmitirdados. O processo de negociacao ajuda a garantir que somente os dados uteis serao transferidos. Paranegociar com sucesso os nos devem descrever ou nomear os dados que eles observam. Os descritoresutilizados nas negociacoes do SPIN sao referidos como meta-dados.

No SPIN os nos apuram seus dados antes da transmissao de dados. Cada no sensor possui seuproprio gerenciador de recursos que mantem um historico do consumo de recursos. As aplicacoesexaminam o gerenciador antes de transmitir ou processar dados. Isto permite que os nos reduzamsuas atividades, sendo mais prudentes ao encaminhar dados de terceiros, quando a energia estiverabaixo de um limite pre-estabelecido.

Juntas, estas caracterısticas superam as deficiencias da inundacao tradicional. O processo de nego-ciacao que precede a transmissao de dados elimina a implosao pois elimina a transmissao de mensagensde dados redundantes. O uso de descritores de meta-dados eliminam a possibilidade de sobreposicao,pois eles permitem que os nos nomeiem o conjunto de dados que eles estao interessados em obter. Tero conhecimento dos recursos de energia local permite que os nos diminuam suas atividades quandoa energia estiver baixa, estendendo a longevidade da rede.

A famılia de protocolos SPIN tem como objetivos principais operar eficientemente e conservar ener-gia. Para operar eficientemente e economizar energia, os sensores precisam comunicar com outrossensores a respeito dos dados que eles ja possuem e dos dados que eles necessitam. A troca de dadosentre os sensores pode ser uma operacao de rede muito custosa, mas trocar dados sobre os dados desensores (meta-dados) nao precisa ser. Alem disso, os nos da rede devem monitorar e se adaptar amudancas de seus recursos de energia de modo a extender a tempo de vida da rede.

No SPIN os nos utilizam tres tipos de mensagens: ADVertise, REQuest e DATA.


O protocolo e iniciado quando um no obtem novos dados que ele deseja disseminar. Quando o nopossui dados para compartilhar, ele pode comunicar este fato transmitindo uma mensagem ADVcontendo meta-dados (estagio ADV) para seus vizinhos. O meta-dado pode ser o id de cada sensor,uma regiao, etc.

Ao receber uma mensagem ADV, os vizinhos do no verificam se possuem os dados solicitados ouse ja solicitaram tais dados. Se nao possuem, eles enviam ao no que disseminou a informacao umamensagem de pedido de dados (estagio REQ). O no nao e obrigado a enviar uma mensagem REQem resposta a uma mensagem ADV e isso pode ser utilizado para melhorar a eficiencia da duracaoda rede.

O no que possui o dado a ser transmitido responde ao pedido com uma mensagem de dados (estagioDATA). Apos receber o dado, o no vizinho envia uma mensagem ADV a todos os seus vizinhosinformando que ele possui um dado novo e que ele quer repassa-lo. Assim o ciclo se reinicia. Osprincipais protocolos SPIN sao:

• Melhores para redes ponto-a-ponto:

– SPIN-PP;

– SPIN-EC.

• Melhores para redes de difusao:

– SPIN-BC;

– SPIN-RL.

O protocolo SPIN-PP trata a transmissao de dados assumindo condicoes ideais, nas quais a energiae plena e nao ha perda de pacotes. Neste protocolo, cada no conhece apenas seus vizinhos diretos,o que traz algumas vantagens, como o baixo custo e simplicidade do estabelecimento da rede poiscada no precisa determinar apenas seus vizinhos proximos, isso permite ainda que o protocolo seadapte com facilidade a mudancas frequentes de topologia. Este protocolo e valioso em relacao asua simplicidade pois ao receber um novo dado realiza decisoes simples (baixo custo de energia comprocessamento) e transmite dados apenas para seus vizinhos proximos (baixo custo de energia com


comunicacao).

Ja o protocolo SPIN-EC considera o fator energia, porem quando a energia esta chegando ao fim emdeterminado no o funcionamento e igual ao SPIN-PP de modo a poupar este no de pouca energiaminimizando sua participacao no protocolo e para isso este no nao envia mensagens REQ para asmensagens ADV que recebe.

O SPIN-BC tem como caracterıstica a utilizacao de um unico canal de comunicacao compartilhadoe dessa forma evita gasto de energia na recepcao de dados inuteis e, uma outra caracterıstica deextrema importancia, uma unica transmissao alcanca todos os nos vizinhos. Ao receber uma mensa-gem ADV, o no aguarda um tempo antes de enviar uma mensagem REQ e fica escutando o meio, seoutro no enviar os dados que sao de interesse deste no os dados sao recebidos e a mensagem REQ ecancelada, pois os dados ja foram recebidos.

O SPIN-RL e similar ao SPIN-BC, mas nao reenvia um REQ se nao receber uma mensagem DATAem um intervalo de tempo e um no fornecedor de dados, apos enviar um DATA aguarda um tempoantes de atender a um outro REQ do mesmo dado.

4.3.3 Protocolo SAR

O protocolo SAR (Sequential Assignment Routing) [SGAP00] visa facilitar o roteamento multi-saltos.

O objetivo e minimizar a media ponderada de metricas de qualidade de servico (QoS - Quality ofService) atraves do tempo de vida da rede. Ele leva em consideracao os recursos de energia e asmetricas de QoS de cada caminho e a prioridade dos pacotes para determinar o roteamento.

A selecao do caminho e feita pelo no que gera o pacote a nao ser que a topologia mude o caminhofazendo com que o pacote tenha que ser desviado. Tal selecao e baseada em tabelas de roteamentoe e necessario enviar um sobrecusto (overhead) em caso de falhas. Para cada pacote roteado pelarede e computado um peso de medida de QoS como o produto da metrica de QoS e a media da prio-ridade dos pacotes. A ideia e prover cada pacote com um coeficiente de QoS relativo a sua prioridade.


Ate o momento nao foram encontradas referencias com mais detalhes sobre este protocolo.

4.3.4 Protocolo Adaptive Local Routing Cooperative Signal Processing

O roteamento do protocolo Adaptive Local Routing Cooperative Signal Processing [SGAP00] temcomo principal objetivo estabelecer e manter a conectividade em uma RSSF. Neste protocolo, assume-se que um algoritmo da aplicacao ou um agente externo determina qual funcao cooperativa e ne-cessaria e dispara o processo de formacao da rede. Neste protocolo, o termo rede refere-se especifi-camente a um conjunto de sensores que detectam um alvo comum. Como a eficiencia de energia eo objetivo principal, diferentes abordagens podem ser usadas dependendo do tipo de funcoes coope-rativas. Este protocolo utiliza os algoritmos ”Single Winner Election” (SWE) e ”Multiple WinnerElection” (MWE) [Soh00] e [Gao00], alem do algoritmo ”Spanning Tree” (ST) [MGW04] e [PR02].Este protocolo possui duas tecnicas de processamento de sinal cooperativo:

1. ”Non-coherent Processing”Os dados coletados dos sensores sao pre-processados em cada no para que somente algunsparametros sejam enviados ao no central. Tem como caracterıstica pouco trafego de rede.E composto de tres fases:

• FASE I: descoberta do alvo, coleta de dados e pre-processamento;

• FASE II: declaracao de adesao;

• FASE III: escolha do no central.

Para a escolha do no central sao utilizados dois algoritmos: SWE e ST.

2. ”Coherent Processing”Apos um pre-processamento mınimo os dados sao etiquetados com um timestamp e sao envi-ados ao no central para uma computacao mais intensa. Portanto, o tamanho das mensagens egrande, o que necessita de maior consumo de energia na rede, exigindo uma estrategia eficientepara reduzir o gasto de energia.


Diferente do anterior utiliza um algoritmo MWE, no qual cada no possui ate n candidatos e onumero de fontes enviando dados sofre uma limitacao.

4.3.5 Protocolo Multi

O Multi [FNL04] e um protocolo adaptativo hıbrido para disseminacao de dados em RSSFs que reuneas caracterısticas de outros dois protocolos, tambem definidos em [FNL04]: o SID (Source-InitiatedDissemination), um algoritmo reativo, cujo processo de disseminacao e iniciado a partir da origemdos dados, e o EF-Tree (Earliest-First Tree), um algoritmo que constroi e mantem pro-ativamenteuma arvore para a disseminacao de dados para toda a rede

A ideia basica do Multi e explorar os cenarios onde o comportamento da rede possa variar muito.Por exemplo, uma aplicacao orientada a eventos pode ter intervalos de tempo longos com baixa ounenhuma incidencia de eventos, mas em determinado instante pode ocorrer uma avalanche de even-tos, provocando um alto trafego de dados. Nesse caso, pode-se ter um algoritmo mais adequado paracada instante da rede, podendo ser inviavel, ou ate mesmo impossıvel, uma entidade externa agirdinamicamente nesta rede modificando seu comportamento. Assim, a proposta do Multi consiste emadaptar seu funcionamento de forma autonoma e adotando o comportamento de um dos algoritmosque o compoe quando for mais interessante sob a otica do consumo de recursos da rede, principal-mente energia.

Para realizar a adaptacao conforme a variacao de trafego na rede, o Multi estabelece um limiar apartir do qual, observada a elevacao do trafego em determinado intervalo de tempo, o esquema dedisseminacao e alternado.

Inicialmente o Multi adota o comportamento do SID, que mostrou ser mais adequado ao trafegoeventual e restrito a poucas fontes de dados, devido a seu comportamento reativo. Esse algoritmofunciona enviando dados por difusao na rede ate que um caminho seja estabelecido pelo no sorvedouroatraves do envio de mensagens de pedido a vizinhos especıficos, no caso os que levam a entrega dedados de forma mais rapida, formando um caminho reverso a fonte de dados pelo qual novos dadospassarao a ser entregues.


Caso o trafego causado pela elevacao do numero de fontes ultrapasse o limiar pre-determinado ocomportamento do EF-Tree e assumido, no qual o no sorvedouro passa a agir pro-ativamente cons-truindo e mantendo uma arvore de disseminacao para toda a rede. A arvore e construıda a partirda difusao de mensagens de controle pelo no sorvedouro e o ancestral de um no e tomado quando aprimeira mensagem de controle e recebida. Essa adaptacao mostrou-se vantajosa, pois ao verificar-sea tendencia no aumento do numero de fontes, uma infra-estrutura de disseminacao e criada anteci-padamente, evitando as difusoes individuais provenientes do esquema SID.

Ao se ter o trafego reduzido abaixo do limiar, observa-se uma tendencia de diminuicao do numero defontes, assim o Multi adapta-se novamente retornando a funcionar como SID.

4.3.6 Protocolo STORM/AD

O protocolo STORM/AD [NFL04] considera auto-organizacao e roteamento como duas tarefas distin-tas. O roteamento, denominado plano de superimposicao, e realizado pelo algoritmo AD (AdaptiveDiffusion) que opera sobre a topologia criada e mantida por um algoritmo de auto-organizacao.A auto-organizacao, denominada plano de substrato, e executada continuamente pelo algoritmoSTORM (Self-organizing TOpology discoveRy and Maintenance) enquanto o algoritmo de rotea-mento opera utilizando a infra-estrutura disponıvel.


Figura 4.4: Interacao entre auto-organizacao e roteamento.

O STORM e um algoritmo distribuıdo para descoberta e manutencao de topologia para RSSFs queprove a infra-estrutura necessaria para a atividade de disseminacao de dados. A topologia resultantedeste algoritmo e um grafo acıclico direcionado (com multiplos caminhos entre cada no fonte e osorvedouro), no qual o fluxo de dados segue dos nos fonte para o no sorvedouro.

Como a topologia disponibilizada pelo STORM e um grafo acıclico direcionado, o AD pode escolherqualquer caminho sem se preocupar com a deteccao de ciclos. Assim, quando um no precisa enviardados, ele avalia seus ancestrais (levando em conta metricas como: menor caminho e caminho demaior energia) escolhendo para qual deles sera enviado o pacote de dados.

O diagrama esquematico do algoritmo e mostrado na figura 4.5. Primeiro, o no calcula um coeficientede adaptacao para cada um de seus pais. A seguir, todos os coeficientes sao avaliados e o pai que(supostamente) levar para o melhor caminho em direcao ao sorvedouro (aquele com melhor coeficientede adaptacao) e escolhido. Os parametros adequados para o calculo do coeficiente de adaptacao e afuncao de avaliacao devem ser escolhidos de acordo com os requisitos de cada aplicacao considerandometricas como: menor caminho, caminho de maior energia, maior economia (agregacao), melhorrelacao sinal/ruıdo e/ou melhor distribuicao de consumo.

4.4. PROTOCOLOS DE ROTEAMENTO HIERARQUICO 31

Figura 4.5: Diagrama esquematico do protocolo STORM/AD.

4.4 Protocolos de roteamento hierarquico

No roteamento hierarquico sao estabelecidas duas classes distintas de nos: nos fontes e nos lıderesde grupo (cluster-heads). Os nos fontes simplesmente coletam dados e os enviam para o lıder de seugrupo que, por sua vez, pode executar uma fusao/agregacao destes dados antes de envia-los para oponto de acesso, e este envio pode ser feito diretamente ou atraves de uma rota. Todos os nos saoconsiderados iguais do ponto de vista funcional. Alguns algoritmos desta classe de protocolos seraoapresentados a seguir.

4.4.1 Protocolo PROC

O PROC (Proactive ROuting with Coordination) [MCLN04] e um protocolo de roteamento desenvol-vido para redes de sensores homogeneas e estacionarias, cujos nos enviam dados periodicamente paraum estacao base. O protocolo considera que os nos possuem capacidade restrita de processamento ecomunicacao, sendo projetados visando uma implementacao compacta.


Este protocolo utiliza o conceito de coordenadores para construir uma infra-estrutura fısica (back-bone) de roteamento, que e uma arvore com raiz na estacao base. Os nos que nao pertencem aobackbone conectam-se diretamente a um no coordenador. O backbone e reconstruıdo periodica-mente para que o consumo de energia pelos nos seja balanceado. O processo de definicao dos nos queirao compor o backbone e composto por duas partes. Na primeira parte os nos utilizam heurısticaspara determinar se serao ou nao coordenadores. Na segunda parte, e feita a complementacao dobackbone caso este nao tenha sido completamente formado.

4.4.2 Protocolo LEACH

O protocolo LEACH (Low-Energy Adaptive Clustering Hierarchy) [HCB00] tem por objetivo reduziro consumo de energia e e apropriado para redes pro-ativas.

LEACH e um protocolo eficiente em energia para redes de sensores que foi projetado com mecanismode envio de dados contınuo e sem mobilidade. Foi desenvolvido para redes homogeneas e utiliza ciclosdurante os quais sao formados aglomerados (clusters) de nos, nos quais um no e escolhido como lıderou base local (cluster-head) e cada no decide qual sera seu lıder, atingindo assim um menor custo decomunicacao.

No LEACH todos os nos da rede iniciam um ciclo ao mesmo tempo, mas nao e especificado comoobter este grau de sincronizacao na rede. Para uma rede que esta em atividade durante um longoperıodo, a dessincronizacao dos relogios pode fazer com que os nos entrem no perıodo de eleicao delıderes em momentos inoportunos.

O LEACH utiliza uma arquitetura de aglomeracao (clustering) onde os nos membros enviam seusdados para seu lıder. Os lıderes agregam os dados de cada sensor e enviam esta informacao para o nosorvedouro. Este protocolo utiliza ainda um revezamento de lıderes para distribuir a carga de energia.Uma vez que os aglomerados sao formados, seus membros utilizam TDMA para se comunicar comseu lıder.

O lıder e responsavel por repassar os dados do seu aglomerado para o ponto de acesso (estacao base


ou no sorvedouro) com um unico salto, o que limita o tamanho da rede em funcao do alcance do radio.

Entretanto, LEACH e portavel para redes onde todo no tem dado para enviar em intervalos regulares,em outras palavras, a coleta de dados e feita periodicamente. Esta coleta e centralizada nos lıderes.

4.4.3 Protocolo TEEN

O TEEN (Threshold sensitive Energy Efficient sensor Network) [MA01] e um protocolo de rotea-mento hierarquico similar ao LEACH [HCB00] exceto pelo fato de que os nos sensores podem naopossuir dados a serem transmitidos em intervalos regulares.

Uma das ideias deste protocolo e classificar as redes de sensores em redes pro-ativas e redes reati-vas. Este protocolo e mais adequado para redes reativas. Uma rede pro-ativa monitora o ambientecontinuamente e possui dados a serem enviados a uma taxa constante. Em uma rede reativa os nosenviam dados apenas quando um certo parametro ultrapassa seu limite.

O protocolo TEEN utiliza a mesma estrategia de formacao de aglomerados do LEACH, mas adotauma estrategia diferente na fase de transmissao de dados.

Ele faz uso de dois parametros, trocados durante a mudanca de lıder:

• ”Hard Threshold” (HT) - Limiar no qual o valor continuamente coletado deve ser trans-mitido;

• ”Soft Threshold” (ST) - Variacao mınima que justifique o valor ser transmitido apos aprimeira vez.

Se o valor exceder HT pela primeira vez, ele e armazenado em uma variavel e transmitido durante ointervalo de tempo alocado para a transmissao do no. Em seguida, se o valor monitorado exceder ovalor armazenado por uma magnitude de ST o no transmite o dado imediatamente. O valor enviadoe armazenado para comparacoes futuras. Como a transmissao consome bem mais energia do queo sensoriamento esta caracterıstica reduz o consumo de energia da rede. Uma desvantagem que ha


neste protocolo e que se o HT nao e alcancado o no jamais transmitira.

Neste protocolo pode-se utilizar escalonamento TDMA ou CDMA para que nao ocorram colisoesentre as comunicacoes dos nos de um aglomerado.

4.4.4 Protocolo APTEEN

O protocolo APTEEN (AdaPtive TEEN) [MA02] e baseado no protocolo TEEN e introduz algumasnovas caracterısticas.

Neste protocolo, no momento da troca de lıder, o procedimento e similar ao TEEN acrescendo-se osseguintes parametros:

• Agendamento - Atribuindo um canal TDMA para cada no;

• ”Counting Time” (CT) - O tempo maximo entre duas comunicacoes sucessivas.

O APTEEN tenta reunir o melhor das redes pro-ativas e das redes reativas. Com o controle de CT edos limiares, este protocolo oferece flexibilidade ao usuario tanto no sentido do controle do consumode energia, quanto na escolha da tendencia mais pro-ativa ou mais reativa da rede. No entanto, umadesvantagem e sua complexidade. E utilizado escalonamento TDMA para que nao ocorram colisoes.

4.4.5 Protocolo SHARP

O protocolo SHARP (SHARP Hybrid Adaptive Routing Protocol) [RHS03] encontra um ponto deequilıbrio entre protocolos reativos e pro-ativos ajustando o grau com que as informacoes de rotea-mento sao propagadas na rede.

Neste protocolo sao criadas zonas pro-ativas tais que os nos a um certo raio do no definido como pro-ativo sao definidos como pertencentes a zona pro-ativa. Tais zonas sao definidas automaticamentepelo protocolo. Veja a figura 4.6.


Os nos que estiverem fora desta zona pro-ativa podem utilizar um protocolo reativo.

Desta forma o SHARP e mais adequado a redes de sensores que possuem caracterısticas muitodinamicas em relacao a comunicacao, nas quais certas regioes da rede possuem um trafego muitointenso e em outras possuem pouco ou nenhum trafego. O protocolo entao se adapta a heterogenei-dade do trafego da rede adaptando-se as regioes pro-ativas e reativas sob demanda.

Figura 4.6: Funcionamento do protocolo SHARP.

4.4.6 Protocolo PEGASIS

O PEGASIS (Power-Efficient Gathering in Sensor Information Systems) [LR02] e um protocolopara RSSF baseado no conceito de correntes. As correntes sao formadas por um algoritmo guloso,no qual cada no troca informacoes apenas com os vizinhos mais proximos formando uma correnteentre nos e apenas um no e escolhido como lıder a cada ciclo para transferir as informacoes coletadasao no gateway (estacao base). Veja a figura 4.7.


Figura 4.7: Funcionamento do protocolo PEGASIS.

Neste protocolo o numero de trocas de mensagens e baixo e a comunicacao e realizada entre os nosmais proximos entre si. Com isso a energia gasta e reduzida comparando-se a outros protocolos quenecessitam de muitas trocas de mensagens para eleger lıderes e formar aglomerados ou se comparadoa protocolos em que os nos constantemente trocam mensagens de forma direta com o no gateway queem geral situa-se distante dos nos.

Estas caracterısticas do PEGASIS implicam em um tempo de vida maior para cada no e menorlargura de banda da rede. O PEGASIS assume o seguinte:

• O no gateway situa-se a uma distancia fixa da rede;

• Cada no da rede e capaz de transmitir dados diretamente para o no gateway e para qualqueroutro no, porem, para reduzir o consumo de energia os nos apenas se comunicam com seusvizinhos mais proximos ou, quando escolhido como a lıder, o no se comunica diretamente como gateway ;

• Cada no possui informacao global da rede;

• Sempre que um no recebe um dado ele faz uma fusao com os seus dados antes de enviar umamensagem ao proximo no e um no lıder aguarda todos os seus vizinhos enviarem dados para

4.5. PROTOCOLOS DE ROTEAMENTO GEOGRAFICO 37

fazer uma fusao antes de enviar uma mensagem ao no gateway ;

• Os nos sao homogeneos e com nıvel de energia uniforme;

• Os nos nao sao moveis e a cada ciclo um novo no escolhido para transmitir a informacao aogateway. Em uma rede de n nos a cada n ciclos cada no e lıder uma vez.

4.5 Protocolos de roteamento geografico

O roteamento geografico utiliza informacoes geograficas para transmitir seus dados. Estas informacoesgeograficas costumam incluir a localizacao dos nos vizinhos. Os dados de localizacao podem ser de-finidos a partir de um sistema de coordenadas globais (GPS - Global Position System [Riz99]) oumesmo de um sistema local valido somente para os nos da rede ou ainda valido para subconjuntos denos vizinhos. Alguns dos principais algoritmos geograficos utilizados em RSSFs serao apresentadosa seguir.

4.5.1 Protocolo LEACH-C

O protocolo LEACH-C (LEACH Centralized) [Hei00] e [LRS02] e uma variacao do LEACH [HCB00]que centraliza as decisoes de formacao dos aglomerados na estacao base.

A maior vantagem desta abordagem centralizada e a criacao e distribuicao mais eficiente dos aglo-merados na rede.

Neste protocolo, cada no, durante o inıcio de cada ciclo da rede, envia sua posicao geografica e energiadisponıvel para a estacao base. A posicao geografica e obtida utilizando-se um sistema de coorde-nadas globais (GPS) que e ativado pelo no no inıcio de cada ciclo. Baseando-se nesta informacao,a estacao base executa um algoritmo de otimizacao para determinar os aglomerados para este ciclo.Os aglomerados formados na estacao base sao, em geral, melhores que aqueles formados utilizandoum algoritmo distribuıdo.

Determinar os aglomerados otimos para os nos e um problema NP-Difıcil e para isso podem serutilizados algoritmos de aproximacao como busca tabu [GL93] ou ”simulated annealing” [KGV83].


Uma vez que os aglomerados e seus lıderes foram determinados a estacao base envia para cada noda rede uma mensagem que contem o identificador do lıder. Apos esta fase, os nos agem como noLEACH original comunicando-se apenas com seu lıder.

4.5.2 Protocolo ICA

O protocolo ICA (Inter Cluster Routing Algorithm) [MCL04] e baseado no LEACH, sendo idealizadopara aumentar o tempo de vida e o numero de pacotes enviados na rede. O ICA inicia com a estacaobase enviando uma difusao para todos os nos informando sua posicao geografica. Apos esta fase,os nos sabem a posicao geografica da estacao base e e suposto que tambem conhecem suas propriasposicoes.

No ICA os nos sao agrupados em aglomerados que seguem a mesma regra de formacao do LEACH,a nao ser pela decisao de qual aglomerado os nos vao participar. Esta informacao e dada pela pro-ximidade dos nos em relacao aos lıderes (bases locais). O no pertence sempre ao aglomerado cujolıder esta mais proximo. O processo de formacao dissemina a informacao de aglomerados para osaglomerados vizinhos.

No ICA, ao contrario do LEACH, os lıderes tentam nao enviar mensagens diretamente para a estacaobase. Ao inves disso eles, em uma abordagem gulosa, enviam as mensagens para o lıder mais proximona direcao da estacao base. O objetivo e economizar energia enviando mensagens ponto a ponto paranos que estao a uma distancia menor da estacao base em relacao ao no que deseja efetuar a trans-missao.

Desta forma a quantidade de energia consumida por cada no da rede diminui e a quantidade deenergia total da rede se mantem por um tempo maior.

Para evitar o problema da morte prematura de nos mais proximos da estacao base, os lıderes (baseslocais) no ICA podem se recusar a retransmitir mensagens de outros aglomerados para a estacaobase. Isto ocorre quando o lıder percebe que esta ficando sem energia e, para evitar que ele nao possa


enviar as mensagens do seu proprio aglomerado, ele para de rotear mensagens de outros aglomeradospara a estacao base. Quando ocorre uma recusa na transmissao de dados por um lıder intermediario,o lıder que solicitou o servico de roteamento envia a mensagem diretamente a estacao base, da mesmaforma como ocorre no LEACH.

Esta abordagem tenta impedir o aparecimento de areas descobertas perto da estacao base. Isto de-veria ocorrer rapidamente uma vez que todas as mensagens da rede teriam que passar por estes nosantes de chegar a estacao base.

4.5.3 Protocolo Geographic Routing without Location Information

O Geographic Routing without Location Information [RRP+03] e um protocolo que visa atribuircoordenadas virtuais aos nos. Assim, os nos nao precisam necessariamente saber a sua coordenadareal. Apesar de assumir que os nos sensores sabem onde estao, a localizacao dos nos nao e condicaonecessaria para o funcionamento do protocolo. Neste protocolo temos tres cenarios nos quais os nospodem assumir coordenadas virtuais:

1. Os nos da borda da rede sabem a sua localizacao. E possıvel determinar a coordenada dos nosrestantes a partir da posicao dos nos de borda;

2. Os nos da borda da rede sabem que estao na borda da rede, mas nao sabem sua localizacao.Os nos da borda enviam para toda a rede uma mensagem HELLO, desta forma os nos da bordapodem determinar a sua distancia em relacao aos outros nos que estao na borda e todos os nosda borda descobrem, alem da propria localizacao, as coordenadas de todos os outros nos daborda utilizando triangulacao. Em seguida, os nos que nao estao na borda utilizam o metododescrito no primeiro cenario para descobrir suas coordenadas;

3. Os nos nao sabem se estao na borda nem sua localizacao. Neste caso e adicionado um passoinicial ao cenario anterior e para determinar quais sao os nos da borda sao necessarios dois nosfixos de referencia (bootstrap beacon nodes). Uma mensagem HELLO e enviada para toda a redepelos nos de referencia, com o intuito de identificar os nos que estao na borda da rede. Casoum no esteja a uma distancia maior do no de referencia em relacao a todos os nos que estao auma distancia de ate dois saltos do no entao este no e um no da borda. Apos isso e utilizado o


metodo descrito no cenario anterior para determinar as coordenadas dos nos restantes.

Apos determinar a sua coordenada virtual, os nos de borda realizam o roteamento segundo as se-guintes regras:

• O pacote e roteado para o no mais proximo em direcao ao destino;

• Se nao existe nenhum no mais proximo do destino do que o no atual, e verificado se o pacotee destinado a este no. Caso seja, o pacote chegou a seu destino. Caso nao seja, nao e possıvelentregar o pacote.

4.5.4 Protocolo GeoMote

O GeoMote (Geographic Multicast for Networked Sensors) [BPR01] e baseado no GeoCast [NI97](protocolo desenvolvido para redes ”Internet-like”). Os destinatarios das mensagens sao enderecadosatraves de polıgonos. Desta forma e possıvel realizar comunicacoes multicast localizadas. NoGeoMote, cada no possui uma funcao especıfica durante todo o tempo de vida da rede, definidano momento da sua programacao. Existem tres categorias de nos sensores: GeoHosts (que produzemdados), GeoRouters (que repassam dados produzidos pelos GeoHosts) e os GeoGateways (que atuamcomo pontos de entrada e saıda de dados).

Para transmitir seus dados o GeoHost que deseja comunicar com outro no da rede repassa pacotespara um GeoGateway na sua vizinhanca. O GeoGateway ira repassar os dados para um GeoRouter,que por sua vez encaminha os dados ate o GeoGateway mais proximo do no (ou regiao) alvo dacomunicacao atraves de um caminho multi-saltos (figura 4.8).

O caminho de propagacao das mensagens e definido por um algoritmo guloso. Neste algoritmo, osGeoRouters repassam os pacotes para o GeoRouter mais proximo dos destinatarios da mensagem.

Por definir funcoes estaticamente aos nos, o protocolo e inadequado para redes cujos nos sao lancadosde forma arbitraria. Os GeoHosts, por exemplo, devem possuir pelo menos um GeoGateway ao al-cance do seu radio, o que pode nao ocorrer caso os nos sejam posicionados arbitrariamente.


Figura 4.8: Envio de dados no GeoMote.

4.5.5 Protocolo GEAR

O GEAR (Geographical and Energy Aware Routing) [YGE01] e um protocolo de roteamento geo-grafico que procura minimizar o consumo de energia da rede. Como no GeoMote, sao enderecadasregioes da rede atraves de retangulos.

O repasse de dados utiliza um algoritmo guloso, no qual o no que ira repassar os dados e aquele quepossui o menor custo de envio ate a regiao desejada. O custo de envio e calculado em funcao dadistancia e energia residual dos nos que compoe a menor rota ate a regiao especificada. Inicialmente,


a funcao custo e aproximada. A cada pacote enviado para a regiao a funcao custo e recalculada, deforma a melhorar o caminho de repasse dos dados.

Ao encontrar a regiao destinataria dos dados o protocolo envia os pacotes atraves de uma particaorecursiva da regiao em quatro secoes e o algoritmo e aplicado recursivamente, ate que as subsecoessejam vazias. Em regioes onde a densidade dos nos e pequena a transmissao dos dados e feita viadifusao.

O Protocolo GEAR destaca-se dos demais algoritmos geograficos por utilizar informacoes de todaa rota ate o destinatario. O uso de informacoes de nos distantes permite uma rota mais eficiente,ao custo de um maior tempo de convergencia. Em redes onde ha mobilidade de nos, o protocoloira prover rotas menos eficientes que aquelas encontradas em cenarios fixos. Alem disto, existemvarios casos crıticos que necessitam de mecanismos especıficos para seu tratamento, o que aumentaa complexidade do protocolo.

4.5.6 Protocolo GPSR

Ao contrario dos protocolos anteriores o GPSR (Greedy Perimeter Stateless Routing) [KK00] permiteenderecar apenas um no.

O GPSR utiliza dois algoritmos para rotear dados. Quando um no identifica um vizinho que estamais proximo do destino o no repassa os dados para este vizinho. Se nao existe um vizinho maisproximo, o pacote deve ser repassado para um no mais distante, para evitar uma regiao onde a co-bertura de nos e baixa. Nestas situacoes, o protocolo utiliza o algoritmo de roteamento de perımetro(Perimeter Routing) que constroi um grafo planar para identificar para qual vizinho repassar os dados.

Uma vez montado o grafo, a regra da mao direita determina o proximo salto da comunicacao conformemostrado na figura 4.9, na qual o no x repassa o pacote para seu vizinho a direita da semi-reta xD,ate encontrar um no que esteja mais proximo de D em relacao a x. Ao determinar que a distanciado pacote ate o seu destinatario volta a diminuir o protocolo volta a rotear os dados utilizando aestrategia gulosa.

4.6. ESTUDO COMPARATIVO 43

Figura 4.9: Roteamento de perımetro no GPSR.

Como vantagens do protocolo pode-se destacar o uso de informacoes locais da vizinhanca para rote-amento e uso de algoritmos geometricos simples, que possibilitam a implementacao do protocolo emnos sensores com poucos recursos de memoria e processamento.

O protocolo assume que e possıvel identificar todos os nos da rede eficientemente via informacoesgeograficas. Para facilitar a construcao desta tabela, os nos da rede operam em modo promıscuo,armazenando as informacoes de localizacao contidas nos pacotes interceptados.

Com esta abordagem a atualizacao dos dados geograficos e facilitada. Em contrapartida, o radiodeve permanecer sempre ligado, o que consome mais energia.

4.6 Estudo comparativo

Nas tabelas abaixo pode-se observar um resumo de pesquisas recentes sobre protocolos de roteamento.Esta tabela e baseada parcialmente em [AKK04] e nas referencias dos protocolos abordados nestetrabalho. Tais tabelas comparam os protocolos sob diversos aspectos, dentre eles:

• Classificacao - plano, geografico ou hierarquico;


• Mobilidade - grau de mobilidade dos nos possıvel no protocolo;

• Uso de energia - grau no qual o protocolo economiza energia;

• Baseado em localizacao - se o roteamento e orientado pela posicao do no;

• Centrado em dados - se o roteamento e baseado no tipo do dado;

• Baseado em endereco - se o protocolo utiliza algum esquema de enderecamento dos nos;

• Qualidade de servico - se o protocolo possui avaliacao de metricas de QoS;

• Agregacao de dados - se os nos efetuam algum processamento local para agregar dados antesde repassar um pacote;

• Baseado em negociacao - se os nos trocam informacoes de negociacao para decidir o envio dosdados da aplicacao;

• Complexidade - grau de complexidade do algoritmo de roteamento (baixa/moderada/alta indicafacilidade de implementacao e lıderes indica uma complexidade alta que se concentra apenasnos nos escolhidos como lıder);

• Escalabilidade - grau no qual o protocolo esta preparado para um aumento no espaco ou numerode nos da rede (boa indica que a escalabilidade e suportada e limitada indica que ha perda dedesempenho);

• Multi-caminhos - se entre dois nos ha mais de uma rota para o envio de dados;

• Caracterıstica - reativo ou pro-ativo.


Classificacao Mobilidade Uso de Baseado em CentradoEnergia Localizacao em Dados

Dif. Direc plano pouca medio nao simSPIN plano sim medio nao simSAR plano pouca medio nao nao

ALRCSP plano pouca medio nao naoMulti plano sim bom nao sim

Storm/AD plano sim bom nao naoPROC hierarquico sim medio nao naoLEACH hierarquico sim bom nao naoTEEN hierarquico sim bom nao sim

APTEEN hierarquico sim bom nao simSHARP hierarquico sim bom nao sim

PEGASIS hierarquico sim bom nao naoLEACH-C geografico sim bom nao sim

ICA geografico sim bom nao simGRWLI geografico sim bom alguns nos naoGeoMote geografico nao bom sim naoGEAR geografico pouca medio nao naoGPSR geografico sim medio sim nao

Tabela 4.1: A - Classificacao e comparacao de protocolos de roteamento para RSSFs.


Baseado em Qualidade Agregacao Baseado emEndereco de Servico de Dados Negociacao

Dif. Direc sim possıvel sim simSPIN nao nao sim simSAR nao sim nao nao

ALRCSP nao sim nao naoMulti nao sim sim nao

Storm/AD nao sim sim naoPROC nao nao nao naoLEACH sim nao sim naoTEEN sim nao sim nao

APTEEN sim nao sim naoSHARP nao sim sim nao

PEGASIS sim nao nao naoLEACH-C sim nao sim nao

ICA sim nao sim naoGRWLI nao nao nao naoGeoMote sim nao nao naoGEAR nao nao nao naoGPSR nao nao nao nao

Tabela 4.2: B - Classificacao e comparacao de protocolos de roteamento para RSSFs.


Complexidade Escalabilidade Multi CaracterısticaCaminhos

Dif. Direc baixa limitada sim pro-ativoSPIN baixa limitada sim reativoSAR moderada limitada sim pro-ativo

ALRCSP moderada limitada sim pro-ativoMulti moderada boa sim hıbrido

Storm/AD moderada boa sim reativoPROC moderada boa sim pro-ativoLEACH lıderes boa nao pro-ativoTEEN lıderes boa nao pro-ativo

APTEEN lıderes boa nao pro-ativoSHARP moderada boa sim hıbrido

PEGASIS baixa boa nao pro-ativoLEACH-C lıderes boa nao pro-ativo

ICA lıderes boa nao pro-ativoGRWLI moderada boa sim pro-ativoGeoMote moderada boa sim pro-ativoGEAR baixa limitada nao pro-ativoGPSR baixa boa nao reativo

Tabela 4.3: C - Classificacao e comparacao de protocolos de roteamento para RSSFs.

Conforme a pesquisa realizada neste trabalho e os resultados de alguns autores como [FNL04]e [RHS03] observou-se que ha um consenso no meio cientıfico de que os protocolos para redes desensores sao dependentes de aplicacao e, portanto, nao existe um protocolo de roteamento que sejaotimo para todas os tipos de redes. Para se decidir em cada caso qual o melhor protocolo e necessarioconhecer os cenarios da rede onde a aplicacao ira executar. Para cenarios cujas mudancas de topo-logia sao frequentes alguns protocolos assumem uma abordagem hıbrida, se adaptando conforme atopologia da rede. Este tipo de protocolo pode ser utilizado tambem quando o projetista da redenao pode determinar o tipo de rede no momento da criacao da aplicacao.


Capıtulo 5

Small worlds

O conteudo deste capıtulo apresenta uma descricao sobre o que e o fenomeno small world, ou seis grausde separacao, como e conhecido, bem como suas propriedades e caracterısticas, exibindo tambem aspropriedades matematicas do modelo small world.

5.1 O fenomeno small world

Inicialmente, este fenomeno foi estudado por Stanley Milgram em 1967 [Mil67]. Resultados do ex-perimento de Milgram indicaram uma cadeia de tamanho medio igual a seis, foi daı que derivou anocao de seis graus de separacao. Em 2003 foi publicado um estudo realizado por Duncan Watts et.al [DMW03] que comprovou que os seis graus de separacao e igualmente valido em ambito global.Mais sobre este estudo sera abordado na secao 5.3.

Watts e Strogatz [WS98] conduziram uma serie de experimentos em grafos e observaram que religando-se aleatoriamente um pequeno conjunto de arestas a media do comprimento dos caminhos do graforeduziu drasticamente (aproximando-se a grafos aleatorios [Bol85], enquanto o coeficiente de aglo-meracao, que basicamente captura a fracao de nos vizinhos que tambem sao vizinhos entre si, per-manece quase constante (similar a grafos regulares). Esta classe de grafos foi denominada grafossmall world e ela enfatiza a importancia de arestas aleatorias atuando como atalhos que diminuema media do comprimento dos caminhos do grafo.

O modelo elaborado por Watts e Strogatz define um conjunto V de n nos em uma rede circular,

49

50 CAPITULO 5. SMALL WORLDS

entao conecta os k nos mais proximos. Para k = 1 um ciclo e formado, no qual cada no podese comunicar diretamente com seus dois nos vizinhos mais proximos, estando um de cada lado.Entao sao adicionadas algumas conexoes em V aleatoriamente. Estas arestas servem para adicionaraleatoriedade a estrutura da rede. Este modelo cria redes com diametro pequeno como em redesaleatorias e os nos permanecem aglomerados. Cada no em V possui contatos locais, por exemplo umvizinho, e algumas conexoes fracas de longa distancia, como por exemplo um amigo que viajou paraoutro paıs. Veja na figura 5.1 abaixo um exemplo de uma rede criada por Watts e Strogatz.

Figura 5.1: Exemplo de Watts e Strogatz onde k = 2. As arestas aleatorias estao destacadas (mais claras).

5.2. PROPRIEDADES DE REDES SMALL WORLD 51

Rede social empırica e uma rede do mundo real formada por pessoas cujas conexoes na rede saodeterminadas pelas amizades. Em termos matematicos, apesar de redes sociais empıricas possuiremdensidade local muito maior do que em grafos aleatorios, a distancia media entre dois nos escolhidosaleatoriamente em uma rede social empırica nao e muito maior do que em grafos aleatorios com amesma densidade de rede [Wat99a].

Portanto, a comunicacao indireta entre duas pessoas quaisquer e, em geral, quase tao eficiente quantoem grafos aleatorios, ou seja, o numero de nos intermediarios entre dois nos quaisquer de uma redesocial empırica e pequeno. Contudo, e importante identificar a propriedade de nao aleatoriedade deuma rede small world.

5.2 Propriedades de redes small world

Uma rede small world pode ser criada a partir de uma rede regular, cujas conexoes entre os nos saorefeitas. Isto e, deixando cada aresta conectando um par de nos sem modificacoes ou reconectandoum dos nos a um no diferente escolhido de forma aleatoria, alternativamente novas conexoes podemser adicionadas, tambem de forma aleatoria. Esta decisao e feita aleatoriamente e com probabilidadep para cada aresta. Portanto se p = 0 a rede regular original nao sofrera modificacoes, mas se p = 1a rede resultante e completamente aleatoria.

Este modelo consiste de uma rede unidimensional com uma baixa densidade de atalhos adicionadaentre um par de nos selecionado aleatoriamente. Estes atalhos reduzem consideravelmente o compri-mento do caminho caracterıstico entre dois nos da rede.

Considerando um numero n de nos formando uma rede regular. Com probabilidade p de que cadaaresta sera reconectada aleatoriamente uma rede small world e caracterizada pelas seguintes propri-edades:

• A vizinhanca local e preservada, como em uma rede regular;

• O diametro da rede aumenta de forma logarıtmica em relacao ao numero de nos n.

Uma conexao entre dois nos quaisquer em uma rede desta natureza pode ser alcancada com apenas


alguns nos intermediarios, pois existem nos que relacionam muitos small worlds [WS98]. Sociedadesde atores de filmes, grades de energia no Oeste dos EUA e redes neurais de transmissao tambemforam considerados redes small world por Watts [Wat99a].

Para small words Watts em [Wat99b] enumera as seguintes propriedades:

1. A rede e numericamente grande: n� 1;

2. A rede e esparsa, de modo que cada vertice esta conectado a no maximo kmax outros vertices;

3. A rede e descentralizada, de forma que nao existe um vertice central dominante no qual a mai-oria dos outros vertices estariam conectados. Isto implica uma forte condicao de esparsidade:nao somente o grau medio k e muito menor que n, mas o grau maximo kmax sobre todos osvertices deve ser tambem muito menor do que n;

4. A rede e altamente aglomerada, no qual espera-se que muitos dos vertices conectados a umcerto no estejam conectados entre si.

Todos os quatro criterios sao necessarios para que o fenomeno small world seja percebido.

Se uma rede e altamente centralizada, como em uma rede estrela, entao um caminho curto obviodeve existir atraves do centro da estrela entre dois pares de vertices. Finalmente, se a rede nao eaglomerada, entao esta rede e caracterizada pela teoria de grafos aleatorios [Bol85], onde a maioriados vertices deve estar somente a poucos graus de separacao mesmo para um n grande. De fato,um grafo aleatorio e uma aproximacao para o menor grafo possıvel para qualquer n e k, tal quekmax � n e a variancia em k nao e tao grande. Um grafo aleatorio e um grafo cujas propriedades,tais como numero de vertices, arestas e as conexoes entre estes elementos sao definidos de um modoaleatorio, no qual qualquer par de nos da rede possui uma probabilidade q, no intervalo [0, 1], deestar interligado por uma aresta.

5.3 Small worlds no mundo real

Considerando as propriedades da secao anterior para o mundo real temos que n e da ordem de bilhoese k e no maximo da ordem de milhares [Koc89], ou seja, centenas de milhares de vezes menor do que

5.3. SMALL WORLDS NO MUNDO REAL 53

a populacao do planeta, nao havendo assim uma pessoa que conheca a maioria das pessoas que hano mundo e, alem disso, espera-se que muitos de nossos amigos sejam amigos entre si.

Se o mundo nao contivesse muitas pessoas entao nao seria surpresa se todas as pessoas estivessemproximamente conectadas entre si (como em uma pequena cidade). Se a maioria das pessoas conhe-cem a maioria das demais pessoas entao, mais uma vez, nao seria surpresa encontrar dois estranhosque possuem um conhecido em comum.

Estes criterios sao satisfatorios para o mundo real? Dado que a populacao do planeta e da ordemde muitos bilhoes e que a estimativa mais generosa de quantos conhecidos uma pessoa possui emmedia e somente de alguns milhares [Koc89], entao os primeiros dois criterios das propriedades deredes small world sao facilmente satisfeitos. As duas ultimas condicoes sao difıceis de se ter certezae certamente sao difıceis de medir, mas elas parecem ser razoaveis conforme a experiencia do dia a dia.

Algumas pessoas sao claramente mais participativas que outras, mas mesmos os indivıduos maissociaveis estao restritos ao tempo e energia para conhecer somente uma fracao muito pequena dapopulacao total. Finalmente, enquanto deve ser difıcil determinar na pratica quantos dos amigosde uma determinada pessoa sao inclusive amigos entre si e ainda mais difıcil medir isso para umapopulacao grande e seja qual for esta fracao, ela e muito maior do que em redes conectadas aleatori-amente, nas quais uma pessoa escolhe seus amigos independentemente da escolha de seus amigos.

Explicitamente, se o mundo estivesse conectado aleatoriamente entao um conhecido de alguem seriasimplesmente alguem vindo de qualquer pais, com qualquer ocupacao e classe socio-economica assimcomo esta propria pessoa. Claramente este nao e o caso do mundo real.

A primeira evidencia de que o mundo deve ser realmente pequeno, um small world, foi apresentadaha quase 40 anos pelo psicologo Stanley Milgram [Mil67]. Milgram iniciou uma cadeia de cartas comorigens no Kansas e Nebraska para serem enviadas para dois destinatarios em Boston. Para cadaorigem foi dado o nome do destinatario e alguma informacao demografica sobre eles, mas foi instruıdoque eles somente poderiam enviar a carta para alguem que eles conhecessem pelo primeiro nome.Se eles nao conhecessem o destinatario diretamente (uma possibilidade remota), a ideia era enviar a


carta para quaisquer um de seus amigos que eles considerassem conhecer ou estar mais proximo dequem conheca o destinatario.

Este procedimento foi entao repetido, gerando uma cadeia de receptores e, por fim, ou as cartaschegaram no destinatario desejado ou falharam por desanimo. Nas cadeias que foram completadas,Milgram descobriu que o numero de conexoes nas cadeias era na maioria das vezes seis, daı surgiua famosa frase ”seis graus de separacao”. Um trabalho posterior de Milgram [KM70] encontrou re-sultados similares para remetentes e destinatarios em diferentes grupos raciais, assim reforcando apretensao de que o mundo nao era pequeno em uma categoria socio-economica particular mas era,talvez, pequeno universalmente.

Embora o primeiro exame teorico do fenomeno small world, por Pool e Kochen [PK78], nao tenhamaparecido na forma de publicacao ate bem depois do experimento de Milgram, as ideias estiveramcirculando previamente por quase 10 anos. Pool e Kochen propuseram o problema em termos daprobabilidade (pi) de que dois elementos selecionados aleatoriamente em uma rede devem estar co-nectados por um caminho curto consistindo de i intermediarios. Eles calcularam os valores esperadosde pi para uma variedade de premissas sobre as estruturas de redes locais e estratificacao.

Eles concluiram, assim como Milgram, que o mundo e provavelmente um small world no sentidode que pares selecionados aleatoriamente, em geral, podem estar conectados por uma cadeia de so-mente alguns intermediarios. Contudo, suas premissas sobre a estrutura da rede e independencia deconexoes eram tao restritivas que eles tendiam a colocar muito peso em suas hipoteses.

Outro ponto inicial para investigacoes teoricas do fenomeno small world foi o estudo de redes ten-denciosamente aleatorias, desenvolvidos nas decadas de 1950 e 1960 por Anotol Rapoport e seuscolegas da Universidade de Chicago.

Motivados pelo desejo de entender a propagacao de doencas infecciosas. Solomonoff e Rapoport[SR51] calcularam a fracao esperada da populacao, aleatoriamente mesclada, a ser infectada por umasemente (pequeno grupo). Rapoport entao determinou as fracoes correspondentes a serem infectadasna populacao onde as conexoes da rede exibiram nıveis de aumento na redundancia local

5.3. SMALL WORLDS NO MUNDO REAL 55

sujeita a efeitos como: ancestrais comuns (homophyly), simetria de pontas (symmetry of edges),triad-closure bias ( [Rap53a], [Rap53b], [Rap57], [Rap63]; [FRO63]).

Aproximacoes mais sofisticadas foram desenvolvidas subsequentemente por Fararo e Sunshine [FS64]e, depois, Skvoretz [Skv85]. Entretanto, como ocorreu com Pool e Kochen, todas estas aproximacoesfocaram em alterar a estrutura local da rede para entao apenas demonstrar que as mudancas signi-ficativas na estrutura global resultam de mudancas significativas correspondentes na estrutura local.Mais tarde, Watts em [WS98] mostrou que mudancas muito pequenas, praticamente indetectaveis, naestrutura local podem resultar em mudancas significativamente grandes na estrutura global da rede.Esta e uma importante distincao, pois e em nıvel local - e somente em nıvel local - que indivıduosna rede fazem medicoes.

Em 2003 foi publicado um estudo realizado por Duncan Watts, Peter Sheridan Dodds e Roby Muha-mad [DMW03], neste estudo com o auxılio da internet, em ambito mundial, envolvendo mais de 61mil usuarios de 166 paıses, eles foram convidados a se comunicar por e-mail com uma das pessoasde um conjunto predefinido com 18 pessoas, dentre elas, um inspetor de arquivos da Estonia, umconsultor de tecnologia na India, um policial na Australia e um veterinario do exercito noruegues.A tarefa dos participantes era ajudar a transmitir uma mensagem para seus alvos escolhidos coma ajuda de pessoas que fossem consideradas por eles mais proximas do que eles do alvo. Neste ex-perimento Watts comprovou que os seis graus de separacao e igualmente valido em ambito global,pois foram necessarios neste experimento apenas entre cinco a sete passos intermediarios para quea conexao fosse estabelecida entre o participante e o alvo. Esta experiencia deu origem ao projetosmall world [Sma01]. Este e um projeto da Universidade de Columbia formado por uma equipede sociologos, incluindo Duncan Watts como principal pesquisador, interessados no fenomeno smallworld. Conforme sua propria descricao, o intuito inicial deste projeto e a verificacao global da hipotesesmall world utilizando a tecnologia de e-mails. Alem disso, eles desejam testar mao apenas as propri-edades dos comprimentos das cadeias de conhecimento, mas tambem a distribuicao dos comprimentosconsiderando os efeitos da raca, classe social, nacionalidade, ocupacao e grau de escolaridade. Elespretendem quantificar o impacto das informacoes adicionais do alvo no sucesso da busca e no compri-mento da cadeia e, tambem, investigar a importancia de possıveis indivıduos centrais responsaveis porencaminhar as mensagens aos alvos de forma desproporcional. Ainda ha uma limitacao neste estudopois muitas pessoas do mundo nao possuem acesso a e-mail, porem a populacao de usuarios de e-mail


e estimada em 100 milhoes, o que e suficientemente grande para se obter dados estatısticos relevantes.

5.4 Formalizando o fenomeno small world

Para tornar a nocao de small world precisa, algumas definicoes sao adotadas da teoria de grafos.Por simplicidade, as redes consideradas por Watts [Wat99b] sao grafos conexos, consistindo somentede vertices sem distincao e arestas sem peso e nao orientadas. Todos os grafos devem satisfazer ascondicoes de esparsidade especificadas anteriormente.

De forma geral, estas premissas nao sao realistas, pois muitas redes de interesse em ciencias sociaise naturais sao compostas de relacionamentos ponderados e orientados. Contudo, generalizacoes dasestatısticas dos grafos resultantes para contabilizar estas complexidades adicionais, embora diretasa princıpio, podem depender de uma aplicacao em particular. Portanto para o proposito da cons-trucao de um arcabouco amplamente relevante Watts considerou grafos nao orientados e sem pesonas arestas como um ponto de partida natural.

A primeira estatıstica de interesse, para um dado grafo, e o do comprimento do caminho caracterıstico(L), definido por Watts como o numero medio de arestas que devem ser percorridas no menor ca-minho entre 2 pares de vertices no grafo. Nos termos do experimento de Milgram, L e o tamanhomedio da cadeia sobre todas as origens e destinos possıveis da rede. L e entao a medida da estruturaglobal do grafo, pois, de modo geral, determinar o tamanho do caminho mais curto entre dois verticesrequer informacoes do grafo completo. Variacoes de L tem aparecido em outros contextos.

Em contrapartida, o coeficiente de aglomeracao (C) e a medida da estrutura local do grafo, maisespecificamente, se um vertice v possui kv vizinhos imediatos, entao essa vizinhanca define um sub-grafo onde no maximo kv(kv − 1)/2 arestas podem existir (se a vizinhanca estiver completamenteconectada). Cv e entao a fracao deste maximo que esta compreendida na atual vizinhanca de v, eC e a media desta fracao sobre todos os vertices do grafo. Equivalentemente, C pode ser conside-rado como a probabilidade de dois vertices (u, v) estarem conectados dado que cada um e tambemconectado a um ”amigo mutuo”. Aglomeracao local e variantes tem aparecido na literatura como amedida da estrutura da rede, originalmente em [Dav67].

5.4. FORMALIZANDO O FENOMENO SMALL WORLD 57

Todos os grafos considerados por Watts em [Wat99b] sao caracterizados em termos destas duasestatısticas. Mas para contextualizar os resultados - para decidir o que e ”pequeno” e o que e”grande”, o que e contabilizado como ”aglomerado” e o que nao e, e necessario determinar faixasde valores sobre o qual L e C possam variar, e isto e imposto pelas seguintes regras, segundo Watts:

1. O tamanho da populacao (n) e fixo;

2. O grau medio k dos vertices e fixo tambem, tal que o grafo e esparso (k << n) mas suficiente-mente denso para ter uma larga escala de estruturas possıveis (k >> 1);

3. O grafo deve ser conexo de modo que qualquer vertice possa ser alcancado a partir de outrovertice percorrendo-se um numero finito de arestas.

Fixar n e k permite efetuar comparacoes validas entre diversas estruturas de grafos. Claramente,o maior valor que C pode assumir para qualquer grafo conexo e C = 1, para um grafo completo(k = n− 1). Inversamente, o valor mınimo concebıvel e C = 0 para um grafo vazio (k = 0).

Estes dois grafos possuem propriedades extremas em relacao ao tamanho. Isto, contudo, nao e umacomparacao muito instrutiva e e obvio que a aglomeracao e o tamanho irao mudar quanto maisarestas forem adicionadas para qualquer grafo. Uma questao interessante e como os valores des-tas estatısticas podem mudar simplesmente rearranjando-se um numero fixo de arestas dentre umnumero fixo de vertices.

As condicoes de esparsidade focam sua atencao na area mais interessante sob a perspectiva de umgrande numero de aplicacoes de ciencias sociais e naturais, isto e, a rede e suficientemente bem co-nectada para admitir uma estrutura rica, ainda que cada elemento esteja confinado a operar em umambiente local que abrange somente uma pequena fracao do sistema como um todo.

Finalmente, insistindo que todos os grafos sao conexos, L e garantido como sendo uma estatıstica glo-bal real. Conforme esta consideracao, comparacoes do comprimento dos caminhos sao comparacoesvalidas em uma estrutura global. Tendo em mente estas condicoes, as seguintes questoes sao apre-sentadas por Watts:


1. Qual e o maior grafo aglomerado possıvel e qual e o comprimento de seu caminho caracterıstico?

2. Qual grafo possui o menor comprimento de caminho caracterıstico e qual o seu coeficiente deaglomeracao?

3. O que faz com que estes resultados impliquem sobre o relacionamento entre o coeficiente deaglomeracao e o comprimento do caminho caracterıstico de um grafo esparso?

Considerando primeiramente a aglomeracao, uma percepcao significativa e que, embora um grafoconexo tenha somente o valor maximo de C = 1 quando k = (n− 1), mesmo um grafo muito esparsodeve ter um coeficiente de aglomeracao que e, na pratica, indistinguıvel do caso completo.

O grafo esparso mais aglomerado possıvel, denominado grafo caveman, que consiste de n/(k + 1)”cliques” isolados ou ”cavernas”, isto e, aglomerados de (k+1) vertices no qual todos os verticesestao conectados com os demais vertices mas nao existem arestas entre todos. E facil de visualizarque este grafo possui C = 1 em um par com um grafo completo. Contudo, isso falha em relacaoa outra condicao exigida - que todo grafo deve estar conectado. Felizmente, conectividade global euma propriedade facil de alcancar neste caso, simplesmente extraindo uma aresta de cada ”clique” eusando ela para conectar com um clique da vizinhanca tal que todo clique eventualmente forme umunico laco inquebravel. Este grafo caveman conexo possui um coeficiente de aglomeracao:

Ccaveman ≈ 1− 6(k2 − 1)

, (5.1)

tendo k como sendo suficientemente grande (sem violar k << n; uma derivacao detalhada da equacao5.1 e dada em Watts [Watts [Wat99a], cap.4]).

O grafo caveman conexo nao tem, de fato, o maior coeficiente de aglomeracao possıvel para um certon e k fixos. Por exemplo, a ultima aresta exigida para completar o anel na figura 5.2 nao e exigidapara conectividade e entao pode sobrar em seu ”clique”, isto marginalmente aumenta C.

Pode-se tambem calcular o comprimento do caminho caracterıstico correspondente para n e k grandes

5.4. FORMALIZANDO O FENOMENO SMALL WORLD 59

(veja Watts, cap. 4):Lcaveman ≈

n

2(k + 1), (5.2)

Note que, para n >> k, L deve ser necessariamente grande e tambem cresce linearmente conformen cresce. Portanto, o grafo caveman conexo pode ser usado como um benchmark para um grafogrande e altamente aglomerado.

E claro, redes conexas, esparsas e com um L grande podem ser construıdas, trivialmente, separando-se uma das arestas entre as arestas do aglomerado para formar uma linha de aglomerados ao invesde um anel. Tais mudancas, contudo, nao afetam as propriedades de escala linear.

Outra construcao mais elaborada (tal como um grande e denso aglomerado seguido por uma longalinha de vertices) e composta pela mesma exigencia de regularidade, o que exclui grafos estrela destaconsideracao. Portanto, como limites do modelo, o grafo caveman conexo e, segundo o trabalho deWatts [Wat99b], um limite superior para L plausıvel (embora aproximado).


Figura 5.2: Esquema de uma construcao caveman conexa.

No outro extremo, sem generalizacoes, uma estrutura pode ser construıda para exibir o caminhocaracterıstico de comprimento mınimo para n e k arbitrarios [CCMS74] e [Bol85] e [Bol85]. Umaboa aproximacao teorica para o limite inferior e realizada em um grafo aleatorio [Bol85], no qualkn/2 arestas, de todas as n(n − 1)/w arestas possıveis, sao escolhidas aleatoriamente e com igualprobabilidade. Nao existem formulas precisas para L e C em grafos aleatorios, mas nos limites de n

e k grandes as aproximacoes assintoticas sao:

Laleatorio ∼lnn

ln(k), (5.3)

e

Caleatorio ∼n

k. (5.4)

Note que nao somente Laleatorio � Lcaveman para qualquer n� 1, mas tambem a escala de Laleatorio,

5.5. UMA MODELAGEM PARA SMALL WORLDS 61

ao inves de linear, e logarıtmica em relacao a n. Portanto, quando n aumenta, a discrepancia dotamanho entre os dois extremos se torna consideravelmente crescente (linear em n). Note tambemque a condicao de esparsidade do grafo (k � n) implica que Caleatorio e muito pequeno. Portanto,reconsiderando a interpretacao probabilıstica do coeficiente de aglomeracao, C pode ser determinadoatraves de uma simples medida da ordem do grafo - grafos com C � k/n (como o grafo caveman co-nexo) sao considerados ordenados localmente (no sentido de que os vertices com pelo menos umvertice adjacente mutuo sao adjacentes entre si) e grafos aleatorios sao, naturalmente, desordenados.

A intuicao que pode ser derivada destes resultados e que grafos altamente aglomerados ou ordenadoslocalmente possuem, necessariamente, um caminho caracterıstico de tamanho grande e, sem muitoformalismo, grafos com caminho caracterıstico de tamanho pequeno possuem uma aglomeracao quee ınfima no limite de n grande. Esta e uma intuicao razoavel, mas esta em desacordo com a intuicaode que o mundo pode ser pequeno e continuar sendo altamente aglomerado.

Na ausencia de dados definitivos para o mundo inteiro, um teste alternativo para o problema smallworld e determinar as condicoes mınimas que sao necessaria e suficientes para o mundo ser pequeno.A aproximacao adotada por Watts [Wat99b] introduz uma famılia de grafos que interpolam aproxi-madamente entre os dois extremos discutidos anteriormente e entao examina a regiao intermediariaprocurando por evidencias dos efeitos do small world.

5.5 Uma modelagem para small worlds

No modelo small world proposto por Watts e Strogatz [WS98], um ponto importante a ser consi-derado e que as redes possuem caracterısticas geograficas, ou seja, os vertices de uma rede possuemposicoes e em muitos casos e razoavel assumir que a proximidade geografica e uma regra para decidircomo os vertices estao conectados entre si.

O modelo small world inicia da seguinte ideia: considera-se uma rede construıda em uma rederegular de poucas dimensoes e adicionam-se ou movem-se arestas para criar ”atalhos” com poucadensidade para unir partes remotas da rede.


Modelos small world podem ser construıdos em redes de qualquer dimensao ou topologia, mas osmelhores casos estudados sao os unidimensionais. Se considerarmos uma rede unidimensional de L

vertices com condicoes de limite periodicas, um anel, e unir cada vertice aos seus k vizinhos ou aalgumas redes mais distantes, teremos um sistema com Lk arestas. O modelo small world e criadopegando-se uma pequena fracao das arestas neste grafo e reconectando-as, uma outra alternativacabıvel e adicionar um pequeno numero de arestas a rede original. A reconexao envolve pegar cadauma das arestas da rede e com uma probabilidade p mover um de seus extremos para uma novalocalizacao escolhida uniforme e aleatoriamente na rede, respeitando a regra de que nao sao criadasarestas multiplas (paralelas) ou lacos.

Figura 5.3: Exemplo de rede unidimensional

A figura (a) mostra uma rede unidimensional com conexoes entre todos os pares vertices separadospor k ou poucos vertices intermediarios, neste caso k = 3. Na figura (b) o modelo small world [WS98]e [Wat99a] e criado escolhendo aleatoriamente uma fracao p de arestas no grafo e movendo uma desuas extremidades para uma nova localizacao, escolhida tambem de forma aleatoria. A figura (c) euma pequena variacao no modelo [Mon99] e [NW99] no qual atalhos sao adicionados aleatoriamenteentre os vertices, mas nenhuma aresta e removida da rede.

Este processo de reconexao permite que o modelo small world intercale entre uma rede regular e algosimilar, mas nao identico, a um grafo aleatorio. Quando p = 0, temos uma rede regular. SegundoNewman [New03] nao e difıcil demonstrar que o coeficiente de aglomeracao desta rede regular eC = (3k−3)/(4k−2), do qual tende a 3/4 para k grande. A rede regular, entretanto, nao demonstrao efeito small world. Quando p = 1, cada aresta e reconectada para uma nova localizacao aleatoriae o grafo e praticamente um grafo aleatorio, mas com um coeficiente de aglomeracao muito pequenoC ∼= 2k/L. Como Watts e Strogatz mostraram com simulacoes, existe uma regiao consideravelmente

5.6. GRAFOS ALEATORIOS GEOMETRICOS 63

grande entre estes dois extremos no qual o modelo possui caminhos curtos e alta transitividade.

Para Newman o modelo original proposto por Watts e Strogatz e um tanto quanto barroco [New03].O fato de que somente um dos extremos de cada aresta seja reconectada e nao ambas e por naoexistirem lacos nem arestas multiplas tornam o modelo um pouco difıcil de enumerar ou de calculara media sobre o conjunto de grafos. Para propositos de tratamento matematico, o modelo pode sersimplificado consideravelmente reconectando-se os dois extremos das arestas escolhidas e permitindo-se lacos e arestas multiplas. Em um sistema estes resultados que, verdadeiramente, intercalam entreuma rede regular e um grafo aleatorio.

Outra variante deste modelo foi proposta independentemente por Monasson [Mon99], por Newmane Watts [NW99] e por Ramezanpour, Karimipour e Mashaghi [RKM02]. Nesta variante, nenhumaaresta e reconectada. Ao inves, ”atalhos” unindo pares de vertices escolhidos aleatoriamente saoadicionados na rede de poucas dimensoes. O parametro p determinando a densidade destes ”ata-lhos” e definido de forma similar ao parametro p na versao original do modelo: p e definido comoa probabilidade por aresta na rede em questao de se tornar um atalho em qualquer lugar no grafo.Portanto, o numero total de atalhos e Lkp e o grau e 2Lk(1+p). Esta versao possui uma importantepropriedade de que nenhum vertice se torna desconexo do resto da rede e a distancia entre 2 verticese sempre formalmente finita.

5.6 Grafos aleatorios geometricos

O conteudo desta secao apresenta uma descricao sobre grafos aleatorios geometricos (Geometric Ran-dom Graphs) que, assim como o small world, tambem pode ser usado como modelo para o estudo deredes ad hoc [Hek05].

5.6.1 Modelando redes ad hoc sem fio com grafos aleatorios geometricos

Redes ad hoc sem fio nao podem ser modeladas como grafos aleatorios. Como ja foi mencionadoanteriormente, neste tipo de rede as conexoes sao limitadas pela distancia geometrica dos nos, o quenao ocorre com grafos aleatorios. Devido a conexao depender da distancia entre os nos existe uma


alta probabilidade de que dois vizinhos estejam conectados quando possuirem um vizinho em comum,isto e, as conexoes sao localmente correlacionadas (aglomeracao). A correlacao local aumenta o coe-ficiente de aglomeracao [Hek05]. Como vimos, tal caracterıstica tambem ocorre com o modelo smallworld . Na literatura, grafos com conexoes dependentes da distancia e conexoes correlacionadas entreos nos sao referidos como grafos aleatorios geometricos [NV03].

Hekmat define dois modelos de grafos aleatorios geometricos: pathloss e lognormal [Hek05]. Es-tes modelos sao baseados no modelo de propagacao do radio, basicamente definindo tres nıveis depotencia: de alta, media e pequena escala. Para cada nıvel as ondas de radio possuem caracterısticasdistintas e como a influencia do ambiente na antena e muito significativa ao variar a potencia nestestres nıveis o autor demonstra que e possıvel garantir uma melhor conectividade entre os nos da rede.Neste trabalho o autor considera que sao necessarios modelos mais especıficos e mais proximos domundo real do que o modelo de grafo aleatorio geometrico tradicional, por esta razao ele fornece osmodelos mencionados.

O grafo aleatorio geometrico pathloss e baseado no modelo de propagacao de radio pathloss. Este mo-delo assemelha-se a uma rede altamente aglomerada diferenciando-se devido a estrita dependencia dadistancia. As conexoes entre os nos sao localmente correlacionadas. Este modelo nao e tao proximodo real pois assume uma area de cobertura circular perfeita para todos os nos. Outros estudos base-ados no modelo de radio pathloss podem ser encontrados na literatura [Pen99] [Bet02] [DPS98].

O grafo aleatorio geometrico lognormal, tambem definido por Hekmat, e mais realıstico que o anterior.Para este modelo o autor faz um profundo estudo do modelo de propagacao de radio lognormal queconsidera as variacoes do sinal de radio e observa que neste modelo a probabilidade de conexoesde curta distancia diminui enquanto que para as de longa distancia aumenta. A probabilidade deconexoes de longa distancia afeta o numero de saltos dos caminhos e a conectividade da rede assimcomo no modelo small world com conexoes de longa distancia.

Um outro modelo que considera variacoes estatısticas no sinal de radio, utilizando o modelo deradio lognormal shadowing, e o grafo aleatorio geometrico nao orientado, estudado por Hekmat eMieghem [HM04], no qual a quantidade de conexoes correlacionadas e reduzida e o grafo aleatorio

5.6. GRAFOS ALEATORIOS GEOMETRICOS 65

geometrico tende a se comportar como um grafo aleatorio com conexoes nao correlacionadas, alemdisso, a probabilidade de conexoes de longo alcance e aumentada, ampliando a probabilidade deconectividade para a rede. Neste trabalho a medida de conectividade e dada pelo tamanho de seumaior componente (subgrafo) conexo. Assumindo por grau de um no sendo como seu numero devizinhos, demonstrou-se que uma conectividade completa e obtida com nos de grau alto, enquantoque com um grau de pequeno valor uma grande porcao da rede permanece conectada. Por fim osautores demonstram que seu modelo esta entre uma rede regular altamente aglomerada e um grafoaleatorio.

Conforme este estudo, observa-se que os modelos de grafos aleatorios podem ser utilizados comomodelo adicional ao modelo small world, alem disso, ele reforca a ideia de que conexoes de longadistancia realmente aumentam a conectividade da rede.


Capıtulo 6

Small worlds em RSSFs

Este capıtulo apresenta um estudo aprofundado sobre as pesquisas ja realizadas sobre o uso de smallworlds em redes de sensores sem fio.

6.1 Uso de small worlds em RSSFs

Helmy em ”Small Worlds in Wireless Networks” [Hel03] descreve que redes moveis multi-saltos,incluindo redes ad hoc e de sensores, sao grafos espaciais pois suas ligacoes (arestas) entre os nossao determinadas pela conectividade do radio, ou seja, em funcao da distancia. Conforme os expe-rimentos de Watts espera-se que tais redes, por sua natureza, nao estejam sob o fenomeno small world.

Redes moveis, de um modo geral, sao redes com alto ındice de aglomeracao e os nos vizinhos deum no sao vizinhos entre si e, em geral, o tamanho medio dos caminhos nestas redes e superior secomparado a redes aleatorias. Alem disso, em 1998 Watts e Strogatz [WS98] mostraram que aoadicionar um pequeno numero de contatos de longo alcance em uma rede o tamanho dos caminhosfica sujeito a L ∝ log(n).

Com base nestas consideracoes, Helmy conduziu um interessante experimento avaliando a aplicabili-dade do conceito small world sobre redes moveis multi-saltos. Helmy, em [Hel02] e [Hel03], sugereque o comprimento dos caminhos pode ser reduzido em uma rede sem fio adicionando-se algumas co-nexoes aleatorias. Alem disso, estas conexoes nao precisam ser totalmente aleatorias, mas devem serrestritas a uma pequena fracao do diametro da rede. Com isso, Helmy propoe uma nova arquitetura

67

68 CAPITULO 6. SMALL WORLDS EM RSSFS

para criar um small world em redes sem fio de larga escala. Esta arquitetura e baseada na definicaode contatos para os nos da rede. Os contatos sao utilizados para descoberta de recursos de modo aevitar uma inundacao (flooding) na rede.

Em seus experimentos, Helmy simulou diferentes topologias de RSSFs utilizando 1000 nos espalha-dos em uma area de 1 km x 1 km. Ele avaliou diferentes distribuicoes de nos: aleatoria, normal,assimetrica e grade. Diversos valores de alcance de radio foram escolhidos para fornecer diferentesnumeros de conexoes e diferentes graus medios dos nos. A tabela 6.1 mostra as topologias desteestudo. Para indicar os diferentes casos sera usada a notacao n-tipo, onde n indica o alcance do radioe tipo indica o tipo de distribuicao.

Topologia Alcance Conexoes Topologia Alcance Conexoes55-aleatoria 55 4785 35-grade 35 193665-aleatoria 65 6850 50-grade 50 381165-normal 65 10790 75-grade 75 931055-assimetrica 55 10051 100-grade 100 12872

Tabela 6.1: Topologias simuladas por Helmy.

Experimentos de reconexoes e adicao de novas conexoes foram conduzidos sobre estas redes. Paraa reconexao um no foi escolhido aleatoriamente e uma conexao com um de seus vizinhos foi refeitaconectando aleatoriamente um no qualquer da rede. Para a adicao de conexoes dois nos foram es-colhidos aleatoriamente e uma conexao entre eles foi adicionada. Isso foi efetuado para diferentesnumeros de conexoes e probabilidades de reconexao/adicao. Para toda probabilidade p de reconectarou adicionar uma nova conexao foram medidos a media do comprimento dos caminhos L, o compri-mento maximo dos caminhos m e o coeficiente de aglomeracao C. Para o caso original onde p = 0,sem reconexoes, esses valores foram denotados como L(0), m(0) e C(0), respectivamente. Para ou-tros valores de p temos L(p), m(p) e C(p), respectivamente. No grafico temos as razoes L(p)/L(0),m(p)/m(0) e C(p)/C(0). Estas razoes representam as reducoes no comprimento dos caminhos e naaglomeracao relativas ao aumento da probabilidade de reconexao. Os resultados podem ser vistos nafigura 6.1.

6.1. USO DE SMALL WORLDS EM RSSFS 69

Figura 6.1: Reducao do comprimento dos caminhos e da aglomeracao por probabilidade de reconexao.

Os valores do coeficiente de aglomeracao e do comprimento dos caminhos nos grafos originais (p = 0)sao altos se comparados a grafos aleatorios. Tais valores sao exibidos na tabela 6.2. RSSFs ten-dem a ser altamente aglomeradas, devido a localidade das conexoes (limitadas pela distancia) o queaumenta a probabilidade de que vizinhos de um no estejam conectados entre si. A unica excecaoe para a topologia 35-grade onde C(0) = 0 pois dois nos vizinhos nao compartilham um vizinhoem comum por causa do curto alcance do radio. Outro fator importante e a tendencia consistenteentre os diferentes experimentos e diferentes topologias. Ha uma alta reducao no comprimento doscaminhos reconectando-se de 0.2% a 20% das conexoes existentes, reconexoes alem desta faixa naoresultam em reducoes significativas.

Grafo aleatorio 55-Aleatoria Normal Assimetrica 35-grade 50-gradeC(0) 0.009 0.58 0.568 0.567 0 0.45L(0) 3.3 12.3 6.9 8.92 21.1 14.8m(0) 5 31 21 32 62 31

Tabela 6.2: Aglomeracao, comprimento dos caminhos e comprimento maximo para as redes originais.


Helmy mostra que ao reconectar ou adicionar 0, 2% das conexoes na rede ha uma reducao de 25% emL e para alcancar uma reducao de 25% em C e necessario 9% de reconexoes, concluindo a partir daıque ao reconectar uma pequena fracao das conexoes da rede ha uma alta reducao do comprimentodos caminhos sem afetar a estrutura da rede (aglomeracao). Estes resultados sao consistentes com ofenomeno small world.

Helmy mostra que e possıvel atingir uma boa reducao no grau de separacao de redes sem fio adici-onando poucas (0, 2% a 2%) conexoes aleatorias (ou atalhos). Do ponto de vista pratico, a escolhadestes atalhos aleatoriamente pode resultar em um sobrecusto imprevisıvel. Uma alternativa anali-sada por Helmy e limitar a distancia destes atalhos aleatorios tornando o sobrecusto mais previsıvel.Resultados de seu estudo mostram que ao limitar a distancia dos atalhos em relacao ao diametro darede pode-se alcancar uma reducao maxima no comprimento dos caminhos ou grau de separacao, oque o motivou a criar uma arquitetura baseada em contatos.

Em novos experimentos Helmy efetuou adicao de conexoes fixando tres valores para a quantidade denovas conexoes: 25, 80 e 150 (estes valores atingiram uma reducao de 40% a 60% em L em com-paracao aos experimentos anteriores). Ele limitou a distancia maxima r (em saltos) para a qual osatalhos podem ser escolhidos. Os atalhos sao escolhidos aleatoriamente em uma distancia d, tal que2 < d < r. Neste experimento Helmy variou r de 2 ate o diametro D da rede. Os resultados (exibidosna figura 6.2) mostram uma tendencia consistente: L(p)/L(0) diminui com o aumento de r ate nomaximo uma fracao de D, apos este valor ele satura. A medida de r/D para as topologias estudadasfoi de ∼ 45% (com mınimo de 35% e maximo de 50%). Como os atalhos sao escolhidos no intervalode [2, r] saltos, entao a distancia esperada dos atalhos e dada por rav ∼ 2 + (r − 2)/2 (i.e., 0.2D a0.35D) para alcancar a reducao mais efetiva em L.


Figura 6.2: Reducao do comprimento dos caminhos por distancia maxima de contato r.

O terceiro conjunto de experimentos considera a escolha de atalhos com exatamente r saltos paraavaliar a tendencia no comprimento dos caminhos e na aglomeracao, os resultados podem ser vistosna figura 6.3. Diferente do resultado anterior, nao ha uma saturacao apos uma certa distancia masfoi observado que em uma certa distancia (r/d ∼ 25%−40%) a reducao maxima no comprimento doscaminhos e alcancada e apos estes valores o comprimento dos caminhos aumenta. Estes resultadosmostram que limitando-se a distancia dos atalhos a uma fracao do diametro da rede (∼ D/4) pode-sealcancar a reducao maxima no comprimento dos caminhos ou grau de separacao.

Com estes resultados Helmy propoe o conceito de contatos para melhorar a eficiencia das tecnicasde busca e pesquisa em redes sem fio de larga escala. Os contatos sao atalhos que transformam umarede sem fio em um small world. Ao inves de usar uma inundacao, os nos pesquisam seus contatospara encontrar o recurso procurado. Os contatos podem ser estabelecidos de forma fısica ou logica.Contatos fısicos podem ser alcancados aumentando o alcance do radio (usando energia de transmissaomais alta ou baixa taxa de bits), mas isto pode nao ser bom em uma rede sem fio. Contatos logicossao representados por multiplos saltos fısicos. Neste caso o objetivo e reduzir o comprimento logicodos caminhos e consequentemente reduzir o numero de pesquisas durante a descoberta de recursos.


Figura 6.3: Contatos a r saltos, reducao maxima do comprimento dos caminhos e em r/d ∼ 25%− 40%.

Em [NPGH02] Nitin Nahata, Priyatham Pamu, Saurabh Garg e Ahmed Helmy propoem uma novaarquitetura baseada no conceito de small worlds. Nesta arquitetura e adotada uma abordagemhıbrida no qual os nos usam (a) roteamento pro-ativo para alcancar sua vizinhanca a distancia deum numero limitado em R saltos (tipicamente 3-5 saltos) e (b) pesquisa reativa alem da vizinhancapor meio de contatos. Os contatos atuam como atalhos que tentam transformar a rede em um smallworld reduzindo o grau de separacao. Eles auxiliam no fornecimento de uma visao da rede alemda vizinhanca durante a descoberta de recursos. Cada no mantem o estado para poucos contatos(tipicamente 5-15) alem de sua vizinhanca. Os contatos sao pesquisados periodicamente para validarsua presenca e suas rotas. Para uma descoberta de rotas eficiente um no enviada perguntas aosseus contatos para ampliar o conhecimento de sua vizinhanca. Neste trabalho os objetivos sao: altaescalabilidade para milhares de nos, eficiencia em relacao ao sobrecusto da rede, robustez e operacoesdescentralizadas, alem disso, e pressuposto que nao ha nenhum tipo de informacao geografica. Umadescricao um pouco mais detalhada sobre esta arquitetura pode ser encontrada em [GPNH02].

Outra pesquisa interessante foi realizada recentemente por Cavalcanti, Agrawal, Kelner e Sadok[CAKS04], na qual tambem e abordado o uso do efeito small world em redes ad hoc sem fio. Comouma rede desta natureza nao possui conexoes de longo alcance, essencial em small worlds, eles sugeremo uso de uma fracao de nos da rede equipados com dois radios de diferentes alcances de transmissao,


introduzindo assim as conexoes de longo alcance. Cavalcanti et. al consideram, adicionalmente, queos radios de longo alcance operam em uma banda de frequencia diferente dos que possuem curtoalcance e analisam o impacto disso na conectividade e difusao da rede. Eles concluem que para obtero mesmo nıvel de conectividade da rede sem o uso destes nos especiais seria necessario aumentar oalcance do radio de todos os nos, o que seria muito mais dispendioso em relacao a energia e, portanto,a abordagem do uso de nos especiais traz vantagens significativas que melhoram a difusao na rede.

Uma variacao e proposta por Sharma e Mazumbar em [SM05] onde e utilizada uma infra-estruturalimitada, na forma de fios, para melhorar a eficiencia no uso da energia de redes sem fio. A ideia eutilizar uma rede de sensores hıbrida, cujos fios atuam como atalhos de longa distancia, valendo-seportanto dos benefıcios de small worlds, ou seja, diminuindo o grau de separacao entre os nos da rede.

De acordo com os trabalhos apresentados neste capıtulo temos diferentes formas para aplicar smallworlds: com dois radios, fios e caminhos multi-saltos. Destes trabalhos o de Helmy merece desta-que pois, alem de servir como base para outros trabalhos, nele sao avaliados com profundidade osresultados do efeito small world mostrando que alem de melhorar o roteamento ao adicionar novasconexoes, e possıvel melhorar ainda mais atraves de uma adicao controlada que limita seu alcancea uma fracao do diametro da rede. Em resumo, o estudo realizado sobre small worlds em RSSFsmostra que e possıvel aplicar o efeito na rede resultando em melhorias interessantes.


Capıtulo 7

Redes overlay

Este capıtulo apresenta um breve estudo sobre redes overlay, que sao redes construıdas sobre redesfısicas com o intuito de migrar parte da complexidade de roteamento para a camada da aplicacao[MOL03].

7.1 Uso de redes overlay

Nas redes overlay sao estabelecidas conexoes logicas entre os nos que pertencem a rede. Atraves damonitoracao da rede uma rede overlay pode identificar, dentre os diversos caminhos monitoradospara um certo destinatario, qual e o melhor caminho para se enviar dados de uma aplicacao especıfica.Aplicacoes de redes overlay podem ser encontradas na literatura para diversos tipos de redes e dife-rentes contextos, como em [Fre], [Gnu], [ST02], [Pen03], [ABKM01], [ZK], [KB96], [GM03], [AAG+05]e [DO03].

Dos trabalhos acima mencionados consideramos interessante o trabalho de Doval et. al [DO03] cujarede overlay e baseada no conteudo dos atributos dos nos da rede, alem disso, os vizinhos de umno tambem sao determinados por seu conteudo armazenado. Neste trabalho eles mostram que oprocesso de pesquisa na rede pode ser realizado de forma iterativa, o que reduz a carga da rede etorna o processo de pesquisa determinıstico.

Andersen et. al [ABKM01] apresentaram uma estrategia, via redes overlay, de descoberta, moni-toracao e avaliacao de rotas de uma forma independente de protocolo de roteamento que aumenta a

75

76 CAPITULO 7. REDES OVERLAY

confiabilidade da rede. Neste trabalho eles mostram que e possıvel aplicar o conceito de rede over-lay sem afetar o protocolo de roteamento, ou seja, de forma transparente para a rede.

Augusto et. al, em [AR06], usam redes overlay para a descoberta de rotas por meio da criacao dediretorios dinamicamente para cobrir uma rede ad hoc de modo uniforme, resultando na diminuicaodo tempo de procura por um determinado servico e na reducao do numero de mensagens de controlegerados pela arquitetura. Eles mostram ainda, assim como Andersen, que e possıvel criar esta estru-tura de forma transparente ao protocolo de roteamento, tal benefıcio e fundamentado com base eminumeros outros trabalhos, como pode ser observado em seu artigo.

De acordo com os trabalhos de Andersen e Augusto, uma rede overlay pode ser utilizada como umaestrategia adaptativa para criar uma rede de forma transparente e tornar possıvel sua aplicacao emdiversos protocolos de roteamento e aplicacoes. Devido a estas vantagens, a proposta neste trabalhoe o uso de redes overlay para a criacao de redes small world.

7.2 Redes overlay em redes de sensores sem fio

Macedo et. al [MOL03], baseados no trabalho de Andersen, identificaram que a partir de um pequenonumero de nos mais poderosos, que instanciam nos de uma rede overlay e efetuam monitoracao narede subjacente, podem ser descobertas e usadas rotas alternativas que atendem melhor as necessi-dades da aplicacao, em comparacao as rotas padrao. Eles mostram que esta estrategia e capaz demelhorar a confiabilidade da rede, mesmo na ocorrencia de falhas, sem prejudicar o seu desempenho,alem de melhorar sua capacidade de tolerancia a falhas e garantir a entrega de mensagens. Nestetrabalho, a rede overlay e formada apenas pelos nos lıderes, cuja energia e maior do que nos nosconvencionais e cada no possui uma lista de vizinhos overlay que podem ser utilizados como inter-mediarios em rotas alternativas, no caso de falha das rotas padrao.

Um outro trabalho interessante, realizado por Gui et. al [GM03], apresenta o uso de multicast atravesde redes overlay conseguindo robustez e eficiencia com baixo custo adicional.

Zuniga et. al [ZK] e Katz et. al [KB96] tratam redes overlay como uma solucao para integrar dife-

7.2. REDES OVERLAY EM REDES DE SENSORES SEM FIO 77

rentes tecnologias de redes sem fio de forma transparente, como por exemplo, integrar redes baseadasem IP com RSSFs.

78 CAPITULO 7. REDES OVERLAY

Capıtulo 8

Conclusao

8.1 Consideracoes Finais

Nesta dissertacao realizou-se um estudo aprofundado sobre as caracterısticas de redes de sensoressem fio que influenciam diretamente no roteamento. Foi realizada tambem uma avaliacao detalhadasobre o funcionamento de protocolos de roteamento. Este trabalho agrupou referencias de diversosautores sobre protocolos de roteamento ad hoc, plano, hierarquico e geografico. Estes estudos permi-tiram uma clara compreensao das caracterısticas de RSSFs e de diferentes estrategias de roteamentode modo a fornecer uma base para investigacoes neste contexto. Alem disso, forneceram um resumopara pesquisas na area.

Um outro estudo aprofundado foi realizado sobre o efeito small world. Uma de suas caracterısticase a existencia de poucos intermediarios entre dois nos quaisquer de uma rede sob este efeito. Outrofator importante e que ao se adicionar algumas arestas de longo alcance em uma rede convencionale possıvel diminuir o comprimento de seus caminhos, pois diminui-se o numero de intermediarios. Onumero medio de intermediarios esperado para este modelo e de apenas seis. Esta teoria sugere umaestrategia para melhorar a descoberta de rotas em RSSFs.

Com o objetivo de reforcar os resultados de small worlds um outro modelo abordado de forma su-cinta e o de grafo aleatorio geometrico, cujas conexoes sao limitadas pela distancia geometrica dosnos. Assim como o modelo small worlds, este modelo tambem se encontra entre as redes regulare aleatoria, sendo possıvel determinar caminhos com poucos intermediarios e garantindo uma alta

79

80 CAPITULO 8. CONCLUSAO

conectividade na rede. Portanto, como as conexoes de uma rede ad hoc sao limitadas pelo alcance doradio (distancia geometrica), este e um modelo interessante pois claramente mostra a possibilidadede aplicacao de um modelo similar a small worlds em RSSFs.

Os estudos sobre RSSFs, protocolos de roteamento e small worlds fornecem uma excelente possibi-lidade de pesquisa para melhorar o roteamento em RSSFs. Ao adicionar conexoes de longa distanciaem uma RSSFs os protocolos podem encontrar rotas de uma forma melhorada [Hel02] e [Hel03]. Issoja foi feito anteriormente utilizando dois canais de radio [CAKS04].

Com a necessidade de avaliar a aplicabilidade desta teoria, de modo a mostrar que o small worlds eaplicavel ao caso real, efetuou-se um estudo sobre redes overlay. Este tipo de rede e um assunto queja foi amplamente estudado e este trabalho reuniu a pesquisa de alguns autores incluindo o seu usoem RSSFs com diferentes estrategias. Com isso, concluiu-se que e possıvel implantar small worlds deforma transparente para a rede fısica atraves da criacao de uma rede logica sobre sua infra-estruturaem diversos protocolos de roteamento e aplicacoes.

Ate o momento, este e o primeiro trabalho que combina o uso de duas tecnicas muito pesquisadas naarea de ciencia da computacao, small worlds e redes overlay, conceitos tambem muito exploradosem RSSFs. Esta e a principal contribuicao deste trabalho para pesquisas em areas correlatas.

Nas simulacoes, em busca de resultados praticos, foram encontradas dificuldades no uso da ferra-menta NS2, ferramenta de referencia para simulacoes de redes, especificamente para o caso do uso deconexoes de longa distancia em uma RSSF. Por este motivo, optou-se por um estudo mais aprofun-dado nos trabalhos existentes, obtendo resultados teoricos mais consistentes e melhor fundamentados,ficando as simulacoes para um trabalho futuro.

Dos estudos aqui apresentados conclui-se que ao reconectar uma pequena fracao das conexoes de umaRSSF ha uma alta reducao do comprimento dos caminhos sem afetar sua aglomeracao. Estes resul-tados sao consistentes com small worlds. Portanto small worlds pode ser empregado para melhoraro funcionamento de protocolos de roteamento em RSSFs e uma forma de implanta-lo sem o impactode novos componentes de hardware e atraves de redes overlay. E claro que a criacao desta infra-

8.2. TRABALHOS FUTUROS 81

estrutura adicional possui um certo custo, mas tambem tras vantagens. Claramente os benefıciosestao diretamente relacionados com o tipo do protocolo de roteamento, mais especificamente sobrecomo as rotas sao determinadas, portanto isso deve ser calculado para cada caso. Como exemplo, seo roteamento e determinado pelo numero de saltos, lembrando que small worlds diminui o numerode intermediarios, consequentemente o numero de saltos, entao o protocolo priorizara as rotas smallworlds e portanto seu roteamento sera melhorado. Um outro exemplo, se o protocolo prioriza oroteamento por ordem de chegada dos pacotes e as rotas small worlds fornecem caminhos otimos emrelacao ao tempo, entao o protocolo tambem priorizara as rotas small worlds e seu roteamento seramelhorado. Uma outra abordagem possıvel e a alteracao nos protocolos de roteamento existentespara funcionar como small worlds e explorar mais efetivamente suas vantagens para o caso especıficodo protocolo. Porem, e nitidamente mais vantajoso o uso de small worlds atraves de overlay, poissem alterar o protocolo pode-se aplicar small worlds, isso permite a criacao de uma unica solucaoaplicavel a varios protocolos. Por fim, uma serie de outras ideias podem ser estudadas futuramentea partir do trabalho aqui realizado.

8.2 Trabalhos futuros

Existem duas linhas de pesquisas diretas a partir deste trabalho: o estudo de small worlds puro e ouso de overlay para simular arestas entre nos distantes.

Para a primeira e necessario adequar a ferramenta NS2 para permitir a criacao de arestas de longadistancia, ou atraves de um novo modulo, ou permitindo uma integracao entre redes com e sem fio,pois no NS2 ha uma separacao entre eles. A criacao de um novo modulo devera permitir que umnovo tipo de no seja criado, este novo no devera possuir a capacidade de se conectar com nos dis-tantes. Para, estas conexoes distantes deve-se atribuir pesos, baseados no caso real (soma dos pesosdo caminho multi-saltos correspondente, por exemplo), para calcular os resultados da aplicacao desmall worlds. Ja a integracao entre as redes com e sem fio deve permitir que os protocolos projetadosno NS2 para RSSFs considerem tambem as rotas com fio para suas decisoes de roteamento.

Para a segunda devemos criar arestas overlay que conectam nos distantes atraves de uma novacamada de protocolo que interliga uma fracao dos nos da rede, formando uma rede overlay. Os nosoverlay deverao encaminhar os pacotes recebidos para seus vizinhos na rede overlay. O funciona-

82 CAPITULO 8. CONCLUSAO

mento do protocolo deve ser preservado, ou seja, se um no overlay recebeu um pacote, este deveraser tratado, alem da camada overlay, pela camada do protocolo como se fosse um no comum. Comisso espera-se que muitos casos os protocolos calculem alguns nos distantes como sendo seus vizinhos,principalmente se o criterio for baseado no numero de saltos. Para isso, e claro, quando um pacotetravegar entre vizinhos de uma rede overlay por um caminho multi-saltos o pacote original deveracontabilizar apenas 1 salto, ou seja, apenas saltos logicos sao considerados. Isso pode ser obtidoatraves de um cabecalho adicional nos pacotes de trafegam pela rede overlay.

Com isso pode-se efetuar simulacoes para avaliar os protocolos ja existentes e comparar seu funciona-mento com e sem o efeito small world. Para isso, e necessario avaliar o impacto disto nos algoritmosde roteamento.

Referencias Bibliograficas

[AAG+05] Aberer, K. , Alima, L. O. , Ghodsi, A. , Girdzijauskas, S. , Haridi, S. and Hauswirth, M. .The essence of p2p: A reference architecture for overlay networks. In P2P ’05: Procee-dings of the Fifth IEEE International Conference on Peer-to-Peer Computing (P2P’05),pages 11–20, Washington, DC, USA, 2005. IEEE Computer Society.

[ABKM01] Andersen, D. , Balakrishnan, H. , Kaashoek, M. F. and Morris, R. . Resilient overlaynetworks. In Proc. 18th ACM Symposium on Operating Systems Principles, pages 131–145, Banff, Canada, October 2001.

[AKK04] Al-Karaki, J. N. and Kamal, A. E. . Routing techniques in wireless sensor networks: asurvey. IEEE Wireless Communications, 11(6):6–28, 2004.

[AR06] Augusto, C. H. P. and Rezende, J. F. . Uma abordagem adaptativa e escalavel para desco-berta de servicos em redes ad hoc. In 24 Simposio Brasileiro de Redes de Computadores,volume II, pages 945–960, 2006.

[AY05] Akkaya, K. and Younis, M. . A survey on routing protocols for wireless sensor networks.Ad Hoc Networks, 3(3):325–349, 2005.

[Bet02] Bettstetter, C. . On the minimum node degree and connectivity of a wireless multihopnetwork. In MobiHoc ’02: Proceedings of the 3rd ACM international symposium onMobile ad hoc networking & computing, pages 80–91, New York, NY, USA, 2002. ACMPress.

[Bol85] Bollobas, B. . Random Graphs. Academic press, London, 1985.

[BPR01] Broadwell, P. , Polastre, J. and Rubin, R. . Geomote: Geographic multicast for networ-ked sensors, 2001.

[CAKS04] Cavalcanti, D. , Agrawal, D. , Kelner, J. and Sadok, D. F. H. . Exploiting the small-world effect to increase connectivity in wireless ad hoc networks. In Souza, J. N. , Dini,P. and Lorenz, P. , editors, ICT, volume 3124 of Lecture Notes in Computer Science,pages 388–393. Springer, 2004.

83

84 REFERENCIAS BIBLIOGRAFICAS

[CCMS74] Cerf, V. G. , Cowan, D. D. , Mullin, R. C. and Stanton., R. G. . Random graphs.Networks, 4:335–342, 1974.

[CE95] Corson, M. S. and Ephremides, A. . A distributed routing algorithm for mobile wirelessnetworks. In Wireless Networks, volume 1, pages 61–81. Kluwer Academic Publishers,February 1995.

[Dav67] Davis, J. A. . Clustering and structural balance in graphs. Human Relations, 20:181–187,1967.

[DEA05] Demirkol, I. , Ersoy, C. and Alagoz, F. . Mac protocols for wireless sensor networks: asurvey. IEEE Communications Magazine, 2005. in press.

[DMW03] Dodds, P. S. , Muhamad, R. and Watts, D. J. . An experimental study of search inglobal social networks. Science, 301(5634):827–829, August 2003.

[DO03] Doval, D. and O’Mahony, D. . Overlay networks: A scalable alternative for p2p. IEEEInternet Computing, 7(4):79–82, 2003.

[DPS98] Diaz, J. , Petit, J. and Serna, M. J. . Random geometric problems on [0, 1]2. InRANDOM ’98: Proceedings of the Second International Workshop on Randomizationand Approximation Techniques in Computer Science, pages 294–306, London, UK, 1998.Springer-Verlag.

[FJL00] Frodigh, M. , Johansson, P. and Larsson, P. . Wireless ad hoc networking-The art ofnetworking without a network. Ericsson Review, pages 248–293, 2000.

[FNL04] Figueiredo, C. M. S. , Nakamura, E. F. and Loureiro, A. A. F. . Multi: A hybrid adaptivedissemination protocol for wireless sensor networks. In 1st International Workshop onAlgorithmic Aspects of Wireless Sensor Networks (ALGOSENSORS’04), volume 3121 ofLecture Notes in Computer Science, pages 171–186. Springer, 2004.

[Fre] Freenet. Disponıvel em: http://www.freenet.com.

[FRO63] Foster, C. C. , Rapoport, A. and Orwant, C. J. . A study of large sociogram: Estimationof free parameters. Behavioral Science, 8:56–65, 1963.

[FS64] Fararo, T. J. and Sunshine, M. . A Study of a Biased Friendship Net. Syracuse Univ.Press, Syracuse, New York, 1964.

[Gao00] Gao, J. L. . Energy Efficient Routing for Wireless Sensor Networks. PhD thesis, Depart-ment of Electrical Engineering of University of California Los Angeles (UCLA), August2000.

REFERENCIAS BIBLIOGRAFICAS 85

[GL93] Glover, F. and Laguna, M. . Tabu search. In Reeves, C. , editor, Modern Heuris-tic Techniques for Combinatorial Problems, Oxford, England, 1993. Blackwell ScientificPublishing.

[GM03] Gui, C. and Mohapatra, P. . Efficient overlay multicast for mobile ad hoc networks. InIEEE WCNC’03, March 2003.

[Gnu] Gnutella. Disponıvel em: http://www.gnutella.com.

[GPNH02] Garg, S. , Pamu, P. , Nahata, N. and Helmy, A. . Contact-based architecture for resourcediscovery (card) in large scale manets. CoRR, cs.NI/0208024, 2002.

[Gua90] Guare, J. . Six Degrees of Separation: A Play. Vintage Books, New York, 1990.

[HCB00] Heinzelman, W. R. , Chandrakasan, A. and Balakrishnan, H. . Energy-efficient commu-nication protocol for wireless microsensor networks. In HICSS, 2000.

[Hei00] Heinzelman, W. B. . Application-specific protocol architectures for wireless networks.PhD thesis, Massachusetts Institute of Technology, 2000. Supervisor-Anantha P. Chan-drakasan and Supervisor-Hari Balakrishnan.

[Hek05] Hekmat, R. . Fundamental Properties of Wireless Mobile Ad-hoc Networks. PhD thesis,Delft University of Technology, September 2005.

[Hel02] Helmy, A. . Small Large-Scale Wireless Networks: Mobility-Assisted Resource Discovery.ArXiv Computer Science e-prints, July 2002.

[Hel03] Helmy, A. . Small worlds in wireless networks. IEEE Communications Letters, 7(10):490–492, October 2003.

[HHL06] Haas, Z. J. , Halpern, J. Y. and Li, L. . Gossip-based ad hoc routing. IEEE/ACM Trans.Netw., 14(3):479–491, 2006.

[HKB99] Heinzelman, W. , Kulik, J. and Balakrishnan, H. . Adaptive protocols for informationdissemination in wireless sensor networks. In MOBICOM, pages 174–185, 1999.

[HM04] Hekmat, R. and Mieghem, P. V. . Study of connectivity in wireless ad-hoc networkswith an improved radio model. Ad Hoc and Wireless Networks (WiOPT 04), 2004.

[IGE00] Intanagonwiwat, C. , Govindan, R. and Estrin, D. . Directed diffusion: a scalableand robust communication paradigm for sensor networks. In Mobile Computing andNetworking, pages 56–67, 2000.


[JMH96] Johnson, D. B. , Maltz, D. A. and Hu, Y.-C. . The dynamic source routing protocolfor mobile ad hoc networks for IPv4. In Tomasz Imielinski, and Korth, H. F. , editors,Mobile Computing, volume 353, chapter 5, pages 153–181. Kluwer Academic Publishers,Computer Science Division, Department of Electrical Engineering and Computer Science,University of California, Berkeley, 1996.

[KB96] Katz, R. H. and Brewer, E. A. . The case for wireless overlay networks. In TomaszImielinski, and Korth, H. F. , editors, Mobile Computing, pages 621–650. Kluwer Aca-demic Publishers, Computer Science Division, Department of Electrical Engineering andComputer Science, University of California, Berkeley, 1996.

[KB05] Kim, H. and Biehl, M. . Exploiting the small-worlds of the semantic web to connectheterogeneous, local ontologies. Information Technology and Management, 6(1):89–96,January 2005.

[KGV83] Kirkpatrick, S. , Gelatt, C. D. and Vecchi, M. P. . Optimization by simulated annealing.Science, 220(4598):671–680, 1983.

[KHB02] Kulik, J. , Heinzelman, W. R. and Balakrishnan, H. . Negotiation-based protocols fordisseminating information in wireless sensor networks. Wireless Networks, 8(2-3):169–185, 2002.

[KK00] Karp, B. and Kung, H. T. . GPSR: greedy perimeter stateless routing for wirelessnetworks. In Mobile Computing and Networking, pages 243–254, 2000.

[KM70] Korte, C. and Milgram, S. . Acquaintance linking between white and negro populations:Application of the small world problem. Journal of Personality and Social Psychology,15:101–118, 1970.

[Koc89] Kochen, M. . The Small World, chapter Toward structural sociodynamics, pages 52–64.Ablex Publishing Corporation, Norwood, New Jersey, 1989.

[KW03] Karlof, C. and Wagner, D. . Secure routing in wireless sensor networks: Attacks andcountermeasures. Elsevier’s AdHoc Networks Journal, Special Issue on Sensor NetworkApplications and Protocols, 1(2–3):293–315, September 2003.

[LNR+03] Loureiro, A. A. F. , Nogueira, J. M. S. , Ruiz, L. B. , Mini, R. A. , Nakamura, E. F.and Figueiredo, C. M. S. . Wireless sensors networks (in portuguese). In Proceedings ofthe 21st Brazilian Symposium on Computer Networks (SBRC’03), pages 179–226, Natal,RN, Brazil, May 2003. Tutorial.

[LR02] Lindsey, S. and Raghavendra, C. S. . Pegasis: Power-efficient gathering in sensor in-formation systems. In IEEE Aerospace Conference, volume 3, pages 3–1125 – 3–1130,2002.


[LRS02] Lindsey, S. , Raghavendra, C. and Sivalingam, K. M. . Data gathering algorithms insensor networks using energy metrics. IEEE Trans. Parallel Distrib. Syst., 13(9):924–935,2002.

[MA01] Manjeshwar, A. and Agrawal, D. . Teen: A routing protocol for enhanced efficiency inwireless sensor networks. In IPDPS ’01: Proceedings of the 15th International Paralleland Distributed Processing Symposium, page 189. IEEE Computer Society, 2001.

[MA02] Manjeshwar, A. and Agrawal, D. P. . Apteen: A hybrid protocol for efficient routingand comprehensive information retrieval in wireless sensor networks. In IPDPS ’02:Proceedings of the 16th International Parallel and Distributed Processing Symposium,page 48, Washington, DC, USA, 2002. IEEE Computer Society.

[MCL04] Maia, E. H. B. , Camara, D. and Loureiro, A. A. F. . ICA: a new routing algorithmfor sensor networks (in portuguese). In Proceedings of the 22nd Brazilian Symposium onComputer Networks (SBRC’04), pages 147–160, Gramado, RS, Brazil, May 2004. ISBN85-88442-80-9.

[MCLN04] Macedo, D. F. , Correia, L. H. A. , Loureiro, A. A. F. and Nogueira, J. M. . PROC: UmProtocolo Pro-ativo com Coordenacao de Rotas em Redes de Sensores sem Fio. In 22Simposio Brasileiro de Redes de Computadores, pages 571 – 574, Maio 2004.

[MGLA95] Murthy, S. and Garcia-Luna-Aceves, J. J. . A routing protocol for packet radio networks.In Mobile Computing and Networking, pages 86–95, 1995.

[MGLA96] Murthy, S. and Garcia-Luna-Aceves, J. J. . An efficient routing protocol for wirelessnetworks. Mobile Networks and Applications, 1(2):183–197, 1996.

[MGW04] Mooij, A. J. , Goga, N. and Wesselink, W. . A distributed spanning tree algorithmfor topology-aware networks. In Unger, H. , editor, Proceedings ofthe 2nd conference onDesign, Analysis, and Simulation of Distributed systems (DASD 2004), pages 169–178.The Society for Modeling and Simulation International, 2004. An earlier version appearedas Computer Science Report 03-09, Technische Universiteit Eindhoven, October 2003.

[Mil67] Milgram, S. . The small world problem. Psichology Today, 1(61), 1967.

[MOL03] Macedo, D. F. , Oliveira, L. B. and Loureiro, A. A. F. . Integrando redes overlay emredes de sensores sem fio. In V Workshop de Comunicacao sem Fio (WCSF’03), pages190–198, Sao Lourenco, Brazil, October 2003.

[Mon99] Monasson, R. . Diffusion, localization and dispersion relations on small-world lattices.Eur. Phys. J. B., 12:555–567, 1999. Rev. E 64, 016131 (2001).


[New03] Newman, M. . The structure and function of complex networks. SIAM Review, 45(2):167–256, 2003.

[NFL04] Nakamura, E. F. , Figueiredo, C. M. S. and Loureiro, A. A. . Disseminacao adaptativade dados em redes de sensores sem fio auto-organizaveis. In 22 Simposio Brasileiro deRedes de Computadores, pages 29–42, Maio 2004.

[NI97] Navas, J. C. and Imielinski, T. . GeoCast – geographic addressing and routing. In MobileComputing and Networking, pages 66–76, 1997.

[NPGH02] Nahata, N. , Pamu, P. , Garg, S. and Helmy, A. . Efficient resource discovery for largescale ad hoc networks using contacts. SIGCOMM Comput. Commun. Rev., 32(3):32–32,2002.

[NSSP04] Newsome, J. , Shi, E. , Song, D. and Perrig, A. . The sybil attack in sensornetworks: analysis & defenses. In 3rd IEEE/ACM Information Processing SensorNetworks (IPSN’04), pages 259–268, Berkeley California - USA, 2004.

[NV03] Nemeth, G. and Vattay, G. . Giant clusters in random ad hoc networks. Physical ReviewE (Statistical, Nonlinear, and Soft Matter Physics), 67:110/1?036 110/6, March 2003.

[NW99] Newman, M. E. J. and Watts, D. J. . Renormalization group analysis of the small-worldlattices. Phys. Lett., A(263):341–346, 1999.

[PB94] Perkins, C. and Bhagwat, P. . Highly dynamic destination-sequenced distance-vectorrouting (DSDV) for mobile computers. In ACM SIGCOMM’94 Conference on Commu-nications Architectures, Protocols and Applications, pages 234–244, 1994.

[PC01] Park, V. and Corson, M. S. . Temporally-Ordered Routing Algorithm (TORA). InternetDraft (draft-ietf-tora-spec-04.txt), ETF MANET Working Group, July 2001. Work inProgress.

[Pen99] Penrose, M. D. . On k-connectivity for a geometric random graph. Random Struct.Algorithms, 15(2):145–164, 1999.

[Pen03] Peng, G. . CDN: Content distribution network. Technical report, Experimental ComputerSystems Lab, Department of Computer Science, State University of New York, 2003.

[Per97] Perkins, C. . Ad hoc on demand distance vector (aodv) routing, 1997.

[PK78] Pool, I. S. and Kochen, M. . Contacts and influence. Social Networks, 1(1):5–51, 1978.

[PR02] Pettie, S. and Ramachandran, V. . An optimal minimum spanning tree algorithm. J.ACM, 49(1):16–34, 2002.


[Rap53a] Rapoport, A. . Spread of information through a population with socio-small-world pheno-menon structural bias i. assumption of transitivity. Bulletin of Mathematical Biophysics,15:523–533, 1953.

[Rap53b] Rapoport, A. . Spread of information through a population with socio-small-world pheno-menon structural bias ii. various model with partial transitivity. Bulletin of MathematicalBiophysics, 15:535–546, 1953.

[Rap57] Rapoport, A. . A contribution to the theory of random and biased nets. Bulletin ofMathematical Biophysics, 19:257–271, 1957.

[Rap63] Rapoport, A. . Handbook of Mathematical Psychology, volume 2, chapter MathematicalModels of Social Interaction, pages 493–579. Wiley, New York, 1963.

[RCV+04] Ruiz, L. B. , Correia, L. H. A. , Vieira, L. F. M. , Macedo, D. F. , Nakamura, E. F. ,Figueiredo, C. M. S. , Vieira, M. A. M. , Maia, E. H. B. , Camara, D. , Loureiro, A. A. F., Nogueira, J. M. S. , Jr., D. C. S. and Fernandes, A. O. . Arquiteturas para Redes deSensores Sem Fio. In 22 Simposio Brasileiro de Redes de Computadores, pages 167 –218, Maio 2004.

[RHS03] Ramasubramanian, V. , Haas, Z. J. and Sirer, E. G. . Sharp: a hybrid adaptive routingprotocol for mobile ad hoc networks. In MobiHoc, pages 303–314, 2003.

[Riz99] Rizos, C. . GPS basics. Disponıvel em:http://www.gmat.unsw.edu.au/snap/gps/gps notes.htm#chapter1, 1999.

[RKM02] Ramezanpour, A. , Karimipour, V. and Mashaghi, A. . Generation correlated networksfrom uncorrelated ones. Physical Review E, 2002. Preprint cond-mat/0212469. 67, 046107(2003).

[RNL03] Ruiz, L. B. , Nogueira, J. M. S. and Loureiro, A. A. F. . Functional and informationmodels for the MANNA architecture. In Proceedings of the 5th French Conference onNetworks and Services Management (GRES’03), pages 455–470, Fortaleza, CE, Brazil,February 2003.

[RRP+03] Rao, A. , Ratnasamy, S. , Papadimitriou, C. , Shenker, S. and Stoica, I. . Geographicrouting without location information. In ACM MobiCom Conference, pages 96–108,2003.

[Rui03] Ruiz, L. B. . MANNA: A Management Architecture for Wireless Sensor Networks. PhDthesis, Computer Science Department of the Federal University of Minas Gerais, BeloHorizonte, MG, Brazil, December 2003.


[S+04] Sancak, S. and others, . Sensor wars: Detecting and defending against spam attacks inwsns. IEEE International Conference on Communications, 6:3668– 3672, 2004.

[Sch03] Schiller, J. H. . Mobile communications. Reading, MA, USA, second edition, 2003.

[SGAP00] Sohrabi, K. , Gao, J. L. , Ailawadhi, V. and Pottie, G. . Protocols for self-organizationof a wireless sensor network. Personal Communications, IEEE, 5(7):16–27, 2000.

[Skv85] Skvoretz, J. . Random and biased networks: Simulations and approximations. SocialNetworks, 7:225–261, 1985.

[SM05] Sharma, G. and Mazumdar, R. . Hybrid sensor networks: a small world. In MobiHoc’05: Proceedings of the 6th ACM international symposium on Mobile ad hoc networkingand computing, pages 366–377, New York, NY, USA, 2005. ACM Press.

[Sma01] Small world project. Disponıvel em: http://smallworld.columbia.edu, 2001. ColumbiaUniversity.

[Soh00] Sohrabi, K. . On Low Power Wireless Sensor Networks. PhD thesis, Department ofElectrical Engineering of University of California Los Angeles (UCLA), June 2000.

[SR51] Solomonoff, R. and Rapoport, A. . Connectivity of random nets. Bulletin of Mathema-tical Biophysics, 13:107–117, 1951.

[ST02] Shi, S. and Turner, J. . Routing in overlay multicast networks. In IEEE INFOCOM,June 2002.

[Wat99a] Watts, D. J. . Small Worlds, The Dynamics of Networks Beetween Order and Random-ness. Princeton Univ. Press, Princeton, New Jersey, 1999.

[Wat99b] Watts, D. J. . Networks, dynamics, and the small-world phenomenon. The AmericanJournal of Sociology, 105(2):493–527, Setembro 1999.

[WS98] Watts, D. J. and Strogatz, S. H. . Collective dynamics of ’small-world’ networks. Nature,393(6684):440–442, June 1998.

[WS02] Wood, A. D. and Stankovic, J. A. . Denial of service in sensor networks. Computer,35(10):54–62, 2002.

[YGE01] Yu, Y. , Govindan, R. and Estrin, D. . Geographical and energy aware routing: Arecursive data dissemination protocol for wireless sensor networks. Technical report,UCLA Computer Science Departmen, May 2001.

[ZK] Zuniga, M. and Krishnamachari, B. . Integrating future large-scale wireless sensornetworks with the internet.

Documents

Uso de small worlds no roteamento em redes de sensores sem fio · Palavras-chave: Redes de Sensores Sem Fio, Roteamento, RSSF, Small Worlds, Overlay. iii. iv. Abstract ... hoc ´e