UNIVERSIDADE FEDERAL FLUMINENSE
INSTITUTO DE COMPUTAÇÃO
HAR: Hierarchy-Based Anycast Routing
Protocol for Wireless Sensor Networks
(Niwat Thepvilojanapong, Yoshito Tobe, Kaoru Sezaki)
Prof. Dr. Célio V. N. Albuquerque
Etienne César R. de Oliveira
Mestrando em Computação
[email protected]
Abril de 2005
UNIVERSIDADE FEDERAL FLUMINENSE
INSTITUTO DE COMPUTAÇÃO
Agenda
 Introdução
 Modelo de Rede Proposto
 HAR: Hierarchy-Based Anycast Routing
 Avaliação de Performance
 Conclusão
UNIVERSIDADE FEDERAL FLUMINENSE
INSTITUTO DE COMPUTAÇÃO
Introdução
 Avanços Tecnológicos
 MEMS-based (Micro-Electro-Mechanical Systems)
 Low-Power RF
 Desenho de novos de Sistemas Operacionais
 Aplicações
 Monitoramento de ambientes
 Sistemas de rastreamento
 Detecção de Falhas
 Detecção de Intrusos
 Limitações
 Poder Computacional
 Área de Armazenamento
 Banda de Transmissão
 Gerenciamento de Energia
UNIVERSIDADE FEDERAL FLUMINENSE
INSTITUTO DE COMPUTAÇÃO
Introdução
 Rede de Sensores
 Monitoramento de tarefas específicas
 Envio de dados coletados de forma periódica ou espontânea
 Reconstrução de rotas em caso de falhas individuais ou
coletivas de sensores
 Proposta do HAR
 Simplicidade
 Escalabilidade
 Robustez
UNIVERSIDADE FEDERAL FLUMINENSE
INSTITUTO DE COMPUTAÇÃO
Agenda
 Introdução
 Modelo de Rede Proposto
 HAR: Hierarchy-Based Anycast Routing
 Avaliação de Performance
 Conclusão
UNIVERSIDADE FEDERAL FLUMINENSE
INSTITUTO DE COMPUTAÇÃO
Modelo de Rede Proposto
 Estações Base
 Quantidade reduzida
 Recursos “ilimitados”
 Sensores
 Quantidade significativa
 Recursos limitados
 Antenas omni-direcionais
 Transmissão por RF
 Fixos
 Anycast
 Protocolo Multipoint-to-point
 N → conjunto de sensores
 BS → conjunto de estações base
 (s, d), s Є {N} e d Є {BS}
UNIVERSIDADE FEDERAL FLUMINENSE
INSTITUTO DE COMPUTAÇÃO
Agenda
 Introdução
 Modelo de Rede Proposto
 HAR: Hierarchy-Based Anycast Routing
 Avaliação de Performance
 Conclusão
UNIVERSIDADE FEDERAL FLUMINENSE
INSTITUTO DE COMPUTAÇÃO
HAR: Hierarchy-Based Anycast Routing
 Utilização de árvores hierárquicas
 Raiz – estação base
 Nós internos / Folhas – sensores
 Formato do pacote
 Type
 IDsrc
 IDdst
 IDgrp
 Sequence
 Length
 Data
UNIVERSIDADE FEDERAL FLUMINENSE
INSTITUTO DE COMPUTAÇÃO
Árvores Hierárquicas – Inserção de Nós
1) Construção da Árvore Hieráquica
• BS envia CREQ
• Sensor recebe CREQ
• Sensor cria a PC
• Sensor aguarda Tcreq
• Sensor envia CREP
• Sensor aguarda Tcacp
• BS envia CACP
• Sensor inserido
Área de Alcance
Área de Alcance
S6
S1
2) Sensor envia CREQ
BS
CREQ
CACP
S7
CREP
CREQ
S2
S4
S3
S5
UNIVERSIDADE FEDERAL FLUMINENSE
INSTITUTO DE COMPUTAÇÃO
Árvores Hierárquicas – Inserção de Nós
 Recebimento de CREQs (child request)
 Construção da PC (parental candidate)
 Seleção do nó pai
 Menor crq_time (tempo de recebimento do CREQ pelo nó pai)
 Menor joined_time (tempo de recebimento de um pacote CACP
pelo nó pai)
 Envio de CREP (child reply) para o nó pai eleito
 Aguarda CACP (child acceptance)
 Time-out (tempo de espera > Tcapt)
 Retransmissão do CREQ (até 2 vezes)
 Seleciona outro nó pai
 Nó filho inserido
 Envio de CREQ
UNIVERSIDADE FEDERAL FLUMINENSE
INSTITUTO DE COMPUTAÇÃO
Árvores Hierárquicas – Inserção de Nós
1) Rede em funcionamento
• Sensores S1 e S2 enviando pacotes
2) Novo sensor ligado
• Sensor envia PREQ
DATA
• Sensor aguarda Tcreq
Área de Alcance
• Sensor recebe CREQ
• Sensor cria a PC
S6
• Sensor envia CREP para S5
CREQ• Sensor aguarda T
cacp
• S5 envia CACP para sensor
• Sensor inserido
3) Sensor envia CREQ
CREQ
S5
S6
S1
CREQ
PREQ
CREP
S2
DATA
S5
S7
S3
CACP
S4
UNIVERSIDADE FEDERAL FLUMINENSE
INSTITUTO DE COMPUTAÇÃO
Árvores Hierárquicas – Inserção de Nós
 Envio de PREQs (parent request) em broadcast
 Recebimento de CREQ enviados em unicast
 Construção da PC (parental candidate)
 Seleção do nó pai
 Menor crq_time (tempo de recebimento do CREQ pelo nó pai)
 Menor joined_time (tempo de recebimento de um pacote CACP pelo nó
pai)
 Envio de CREP (child reply) para o nó pai eleito
 Aguarda CACP (child acceptance)
 Time-out (tempo de espera > Tcapt)
 Nó filho inserido
 Sem resposta
 Aguarda pacote CREQ
 Envio periódíco de PREQ
UNIVERSIDADE FEDERAL FLUMINENSE
INSTITUTO DE COMPUTAÇÃO
Tratamento de Falhas
 On-demand
 Acknowledgement do protocolo MAC
 Seleção de candidatos a partir da tabela PC
 Envio de CREQ
 Recebimento de CACP
 Tabela PC vazia ou sem resposta ao CREQ
 Envio de PREQ
 Prevenção de loop (descarte pelos nós filhos e netos)
 Recebimento de CREQ
 Envio CREP
 Recebimento de CACP
 Tabela PC vazia e sem resposta ao CREQ e ao PREQ
 Envio de PQRY aos filhos
 Resposta de PREP
 Selecão aleatória de um candidado a nó pai
 Envio de REV em unicast
 Filho seleciona um novo nó pai
 Filhos sem candidatos ou sem resposta PREP
 Envio de REV a um nó de forma aleatória
UNIVERSIDADE FEDERAL FLUMINENSE
INSTITUTO DE COMPUTAÇÃO
Roteamento Anycast e Mudança de Estados
 Anycast
 Envio de um pacote para um receptor dentro de um grupo
 Mudança de Estados
UNIVERSIDADE FEDERAL FLUMINENSE
INSTITUTO DE COMPUTAÇÃO
Agenda
 Introdução
 Modelo de Rede Proposto
 HAR: Hierarchy-Based Anycast Routing
 Avaliação de Performance
 Conclusão
UNIVERSIDADE FEDERAL FLUMINENSE
INSTITUTO DE COMPUTAÇÃO
Avaliação de Performance
 Metodologia
 50, 70 e 100 sensores fixos
 Área de 250 m2
 Capacidade de TX/RX de 19200 bps
 Tráfego CBR associado ao UDP:
 128 bps (0,25 pps)
 256 bps (0,5 pps)
 512 bps (1 pps)
 1024 bps (2 pps)
 Tcreq=0,1s e Tcapt=0,3s
UNIVERSIDADE FEDERAL FLUMINENSE
INSTITUTO DE COMPUTAÇÃO
Avaliação de Performance
 Taxa de Envio de Pacotes (PDR)
UNIVERSIDADE FEDERAL FLUMINENSE
INSTITUTO DE COMPUTAÇÃO
Avaliação de Performance
 Latência Média
UNIVERSIDADE FEDERAL FLUMINENSE
INSTITUTO DE COMPUTAÇÃO
Avaliação de Performance
 Quantidade de Saltos
UNIVERSIDADE FEDERAL FLUMINENSE
INSTITUTO DE COMPUTAÇÃO
Agenda
 Introdução
 Modelo de Rede Proposto
 HAR: Hierarchy-Based Anycast Routing
 Avaliação de Performance
 Conclusão
UNIVERSIDADE FEDERAL FLUMINENSE
INSTITUTO DE COMPUTAÇÃO
Conclusão
 Performance superior




Taxa de Envio de Pacotes (PDR)
Latência Média
Quantidade de Saltos
Escalabilidade
 Redes maiores
 Maior quantidade de sensores
 Maior área
 Redes dinâmicas
 Quantidade de estações base
 Consumo de energia
 Confiabilidade
 Implementação em um ambiente real
UNIVERSIDADE FEDERAL FLUMINENSE
INSTITUTO DE COMPUTAÇÃO
Conclusão
 Questões:
 Periodicidade de envio de CREQs pela BS
 Determinação do Tcreq dos sensores