Directed Diffusion

Universidade Federal do Rio de JaneiroGrupo de Teleinformática e Automação

CPE 825 - Roteamento em Redes de Computadores

Danilo Michalczuk Taveira

Introdução

• Nós sensores– Recursos limitados

• Processamento• Memória• Energia

– Comunicação sem-fio• Alcance limitado• Múltiplos saltos

• Rede de Sensores– Nós sensores coordenados

Directed Diffusion

• Protocolo para redes de sensores– Tarefas de sensoriamento

• Tipo de eventos• Área de interesse• Mensagens de interesse

– Nós intermediários• Direcionam interesses• Enviam dados sobre eventos

Directed Diffusion

• Elementos principais– Interesses

• Propagar tarefas• Tipo de evento de interesse• Área de interesse• Criam gradientes

– Gradientes• Vizinhos com interesse

– Dados• Representam eventos

Esquema de Nomes

• Formato das mensagens– Pares de atributos e valores

• Interesses– Tipo de evento– Intervalo entre eventos– Estampa de tempo do instante de criação– Estampa de tempo do instante de expiração

• Dados– Tipo de evento observado– Localização do nó– Estampa de tempo– Valor e confiança do valor medido

Interesses e Gradientes

• Geração dos interesses– Tarefa programada por um operador

• Guardada na tabela de tarefas– Nó sorvedouro

• Gera os interesses iniciais• Recebe os dados de interesse

• Propagação dos interesses– Estabelecem os gradientes– Interesses iniciais

• Intervalo de eventos maior• Interesses exploratórios• Enviados periodicamente

−Perda de pacotes

Propagação de Interesses

Área de Interesse

Nó sorvedouro

InteresseGradiente

Tabela de Interesses

• Entrada corresponde a interesse– Agrupamento de interesses

• Mesmo tipo• Áreas não disjuntas• Redução do número de estados

– Estampa de tempo do último interesse– Duração– Gradientes

• Nó emissor do interesse• Taxa de eventos• Duração

Manutenção da Tabela de Interesses

• Recebimento de um interesse– Não existe na tabela

• Nova entrada de interesse−Gradiente para o nó de origem

– Existe na tabela• Verificação dos gradientes• Não existe gradiente para o nó

−Novo gradiente– Atualização dos campos do interesse e gradiente

• Remoção de um interesse– Último gradiente expira

Propagação dos Interesses

• Reenvio dos interesses para vizinhos– Todos os vizinhos

• Inundação da rede– Seletivamente

• Nós na direção da área de interesse−Informação sobre localização dos vizinhos

• Uso de informações anteriores−Vizinhos que enviaram dados sobre área de

interesse• Interesses sem informação sobre sorvedouro

– Formação de loops

Propagação dos Dados

• Nós geram dados– Evento observado– Nó na área de interesse– Interesse para o tipo de evento

• Propagação dos dados– Nós no gradiente para o interesse– Unicast

• Remoção de loops– Cache de mensagens de dados recentes

• Não encaminha duplicatas• Mede taxa de eventos

−Reencaminhamento seletivo

Reforço dos Caminhos

• Interesses exploratórios– Eventos exploratórios => Baixa taxa

• Reforço positivo– Aumentar a taxa de eventos– Interesse com intervalo menor

• Mudança da taxa dos gradientes−Todos os gradientes com taxa menor => Reforço

– Escolha dos vizinhos para reforço• Todos os vizinhos

−Múltiplos caminhos• Vizinho remetente do último evento

−Menor atraso

Propagação de Interesses

Área de Interesse

Nó sorvedouro

InteresseGradienteDados

Reparo Local

• Caminhos podem falhar– Erros de transmissão– Falta de energia– Reparo local

• Iniciado por nó presente no caminho• Reforço positivo de outros vizinhos

Reforço Negativo

• Diminuir a taxa de um caminho– Reduzir múltiplos caminhos– Diminuir consumo de energia

• Reforço negativo– Passivo

• Gradientes expiram– Ativo

• Mensagem especial para reforço negativo– Realizado em cadeia– Determinação dos vizinhos

• Tempo T sem receber eventos• N eventos recebidos através de outros nós

– Remoção de loops

Reforço Negativo

Área de Interesse

Nó sorvedouro

InteresseGradienteDados

Conclusão

• Protocolo para redes de sensores– Redes de propósito específicos– Dados e interesses– Nós intermediários

• Definem o encaminhamento e destinos– Informação sobre localização

• Sistemas de Posicionamento Global (GPS)– Sincronização dos relógios

Directed Diffusion

Universidade Federal do Rio de JaneiroGrupo de Teleinformática e Automação

CPE 825 - Roteamento em Redes de Computadores

Danilo Michalczuk Taveira