Etienne César R. de Oliveira Mestrando em Computação [email protected] Abril de 200 5

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



Agenda

IntroduçãoModelo de Rede PropostoHAR: Hierarchy-Based Anycast RoutingAvaliação de PerformanceConclusã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



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



Agenda




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}



Agenda




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



Árvores Hierárquicas – Inserção de Nós1) Construção da Árvore Hieráquica

CREQ

Área de Alcance• BS envia CREQ

• Sensor cria a PC

BS

• Sensor aguarda Tcreq

• Sensor envia CREP

CREP

• Sensor aguarda Tcacp

• BS envia CACP

CACP

• Sensor inserido

2) Sensor envia CREQ

CREQ

Área de Alcance

S1

S2

S3

S4

S5

S6

S7

• Sensor recebe CREQ



Á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



Árvores Hierárquicas – Inserção de Nós1) Rede em funcionamento

DATA

• Sensores S1 e S2 enviando pacotes 2) Novo sensor ligado• Sensor envia PREQ• Sensor aguarda Tcreq

DATA

CREQ

• Sensor recebe CREQ• Sensor cria a PC• Sensor envia CREP para S5

• Sensor aguarda Tcacp

• Sensor inserido

3) Sensor envia CREQ

Área de Alcance

PREQ

CACP

CREQ

S5

S6

S6

S4

S3

S2

S1

S5

CREQ

• S5 envia CACP para sensor

S7

CREP

S5



Á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 eleitoAguarda CACP (child acceptance)

Time-out (tempo de espera > Tcapt) Nó filho inserido

Sem respostaAguarda pacote CREQEnvio periódíco de PREQ



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



Roteamento Anycast e Mudança de Estados

Anycast Envio de um pacote para um receptor dentro de um grupo

Mudança de Estados



Agenda




Avaliação de Performance

Metodologia50, 70 e 100 sensores fixosÁrea de 250 m2

Capacidade de TX/RX de 19200 bpsTrá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




Taxa de Envio de Pacotes (PDR)




Latência Média




Quantidade de Saltos



Agenda




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âmicasQuantidade de estações base

Consumo de energia Confiabilidade Implementação em um ambiente real



Conclusão

Questões:Periodicidade de envio de CREQs pela BSDeterminação do Tcreq dos sensores

Documents

Etienne César R. de Oliveira Mestrando em Computação [email protected] Abril de 200 5