Roteamento em
Redes de Sensores
Giulian Dalton Luz
[email protected]
Características

Recursos limitados




Topologia dinâmica




Mobilidade
Falha de nós
Sensores inativos em períodos de baixa atividade
Escalabilidade


Quantidade de energia limitada
Capacidade de processamento limitada
Alcance de transmissão pequeno
Necessita de redundância – nós podem falhar
Tempo de vida da rede

O tempo de vida deve ser o maior possível
Protocolos de Roteamento
Técnicas








Plano (Flat)
Comunicação Direta
Múltiplos saltos com energia mínima
(Minimum-Energy Multi-Hop)
Aglomeração (Clustering)
Aglomeração Dinâmica
Inundação (Flooding)
Gradiente
Roteamento Geográfico
Roteamento Plano



Descoberta de vizinhos
Cria agendamento de transmissão e
recepção
Não necessita de nós mestres locais ou
globais
Comunicação Direta




Cada sensor envia dados diretamente a
uma estação base
Recepções ocorrem somente na base
Alto consumo de energia para sensores
distantes da base
Melhor em alguns casos:


nós perto da base
Alto consumo de energia na recepção
Múltiplos saltos com energia mínima


Nós enviam dados a base através de nós
intermediários
Escolha da rota

Escolha de nós minimiza energia de transmissão


Considera somente energia do transmissor ignorando o custo da
energia dos receptores para determinar rotas
Dependendo do custo relativo do amplificador de
transmissão e do equipamento de rádio o consumo
de energia pode ser superior a transmissão direta
Múltiplos saltos com energia mínima
Consumo de energia
BASE
Primeiro nó a morrer
Duração dos nós

O protocolo mais eficiente em relação a energia dependerá
da topologia da rede e dos parâmetros do rádio
Aglomeração

Caracteristicas




Vantagem


Nós são organizados em aglomerados
Cada aglomerado possui uma base local
A base local é responsável por transmitir os dados
a uma base global
Reduz a distância de transmissão dos nós (base
local próxima aos nós)
Desvantagem

Alto consumo de energia na base local
Aglomeração
Comunicação
BASE GLOBAL
Bases Locais
Aglomeração Dinâmica



A escolha da base é aleatória
De tempos em tempos um novo nó toma lugar
da base
Vantagem



Evita o problema da aglomeração convencional onde
nós base tendem a morrer primeiro
Melhora o tempo de vida de rede
Desvantagem

Estabelecimento da rede mais “complexo”
Inundação




Um nó envia uma cópia de seus dados
através da rede para cada um de seus
vizinhos
Quando um nó recebe algum dado ele faz
uma cópia do dado o envia para todos seus
vizinhos, exceto o nó do qual ele recebeu o
dado
Gera muita redundância, dados são enviados
para todos os nós da “vizinhança”
Variação: nó envia os dados para um
subconjunto aleatório de nós (Gossiping)
Inundação

Deficiências de protocolos de
Inundação (Flooding):
Superposição

Implosão

A
(a)
(a)
B
r
C
(a)
(a)
q
s
B
C
(q,r)
D
(r,s)
D

Recursos à cega
Gradiente



Envio de mensagems através da rede
estabelece gradientes
Nós possuem múltiplos gradientes
A resposta de mensagens/novas mensagens
utilizam as rotas gradientes estabelecidas
envio
resposta
Roteamento Geográfico




Natureza física da instalação de uma rede de sensores
torna consultas de escopo geográfico naturais
Se os nós conhecem sua localização a disseminação de
dados ocorre somente para regiões relevantes
Reduz o overhead do controle de roteamento otimizando
o processo de busca baseando-se na informação
geográfica
Ex.: GPSR (Greedy Perimeter Stateless Routing - 2000)
e GEAR (Geographic and Energy aware routing - 2001)
Protocolos de roteamento

Roteamento Plano




Difusão Direcionada (Directed Diffusion)
SAR (Sequential Assignment Routing)
SPIN (Sensor Protocols for Information via
Negotiation)
Adaptive Local Routing Cooperative Signal
Processing




Noncoherent Processing
Coherent Processing
Sensor-MAC
MULTI
Difusão Direcionada



Proposto por Estrin et. al. 1999
O nó nomeia os dados usando um ou
mais atributos
O nó cliente requer os dados através de
interesses


Nós intermediários propagam os
interesses
Interesses estabelecem gradientes de
dados para o nó que expressou interesse
Directed Diffusion
Evento
Fonte
Dados
Gradientes
Interesses
Nó cliente
SAR
Sequential Assignment Routing






Proposto por Sohrabi et al. 2000
Roteamento multi-saltos
Seleção de múltiplos caminhos baseados em tabelas

Evita o overhead em caso de falha
Escolha do caminho baseada em:

Recursos de energia

QoS

Prioridade do pacote
Parâmetros associados a cada caminho:

Métrica de QoS

Estimativa de recurso de energia
SAR calcula a métrica de QoS ponderada

Produto da métrica de QoS e um coeficiente ponderado
associado com a prioridade do pacote
SPIN
Sensor Protocols for Information via Negotiation


Proposto por Kulik et. al. 1999
Negociação de dados

Meta-data




Pode ser o ID de cada sensor, ou uma regiao, etc...
Controle a nível de aplicação
Agregação de dados ocorre em cada nó
A
ADV
B
ADV – anuncia dados (meta-data)
REQ – requer dados específicos (meta-data)
A
REQ
B
A
DATA
B
Mensagens SPIN


Não é obrigatório o nó enviar um
REQ em resposta a um ADV



DATA – dados pedidos
Gerenciamento de recursos

Responsabilidade da aplicação
SPIN
Sensor Protocols for Information via Negotiation
B
G
DATA
ADV
E
E
A
ADV
C
REQ
ADV
D
ADV
Nó sem dado
Nó com dado
F
Nó esperando
para enviar REQ
SPIN
Sensor Protocols for Information via Negotiation

Família de protocolos SPIN

Ponto a ponto



SPIN-PP
SPIN-EC
Broadcast


SPIN-BC
SPIN-RL
SPIN
Sensor Protocols for Information via Negotiation

SPIN-PP





Assume que a energia não é limitada
Assume que pacotes não são perdidos
Nó só conhece seus vizinhos diretos
Estabelecimento da rede de baixo custo
SPIN-EC



Considera a conservação de energia
Igual ao SPIN-PP quando há energia
Minimiza a participação do nó no protocolo
quando há pouca energia

Não enviando REQs para os ADVs que receber
A
B
SPIN
Sensor Protocols for Information via Negotiation

SPIN-BC

Comunicação em um único canal compartilhado




Nós gastam mais energia recebendo dados “inúteis”
Uma única transmissão alcança todos os nós vizinhos
Cada nó só envia um REQ após esperar um tempo
aleatório
Nós em espera cancelam o envio do REQ quando
escutarem que este já foi executado por outro nó.
SPIN
Sensor Protocols for Information via Negotiation

SPIN-RL


Reenvia um REQ se não receber um DATA em um
intervalo de tempo
Ápós enviar um DATA aguarda um tempo antes de
atender um REQ do mesmo dado
Adaptive Local Routing Cooperative
Signal Processing


Proposto por Sohrabi et al. 2000
Noncoherent Processing




Os dados são pré-processados em cada nó
Somente alguns parâmetros são enviados ao nó central
Composto de três fases:
 Fase I: descoberta do alvo, coleta de dados e préprocessamento
 Fase II: declaração de adesão
 Fase III: escolha do nó central
Algoritmos para a escolha do nó central:


Single Winner Election (SWE)
Spanning Tree (ST)
Adaptive Local Routing Cooperative
Signal Processing

Coherent Processing


Após um pré-processamento mínimo os
dados são etiquetados com um
timestamp para serem enviados ao nó
central
Processo de MWE (Multiple Winner
Selection):


Cada nó possue até n candidatos
Limita o número de fontes enviando dados
SMAC – Sensor MAC


Ye et al. 2002
Vários aspectos típicos de protocolos MAC
afetam o consumo de energia:




colisões: além do consumo adicional devido a
retransmissões, aumenta a latência;
escuta inútil (overhearing), de tráfego destinado a
outros nós;
overhead de controle, aumenta linearmente com
densidade de nós, nós em falha também exigem
esforço adicional de reconfiguração;
escuta ociosa, de quadros que nunca chegam
SMAC – Sensor MAC


Distribuído e baseado em
escalonamento e reserva
Evita as quatro fontes de desperdício
anteriormente mencionadas



escuta e adormecimento periódico;
precaução de colisões e overhearing;
troca de mensagens assume que os nós
estão aptos a ligar e desligar seus rádios.
MULTI



Proposto por Figueiredo et al. 2004 (UFMG)
Reúne características dos protocolos:
SID – Source Initiated Dissemination




EF-Tree (Earliest-First Tree)


Constrói e mantém uma árvore para disseminação de dados em
toda a rede (broadcast)
Ideal para cenários onde a rede varia muito


Disseminação iniciada na origem
Usa broadcast para encontrar um caminho até o nó origem
Utiliza gradiente para entrega de dados
Variação de tráfego (comunicação)
Adapta-se entre o SID (pouca comunicação) e o EF-Tree
(comunicação intensa) através de um limiar
Protocolos de roteamento

Roteamento Hierárquico





LEACH (Low Energy Adaptive Clustering
Hierarqy)
ICA – Inter Cluster Routing Algorithm)
TEEN (Threshold sensitive Energy Efficient
Sensor Network Protocol)
APTEEN (Adaptive TEEN)
SHARP – Hybrid Adaptive Routing Protocol
LEACH
Low-Energy Adaptive Clustering Hierarchy




Proposto por Henzeilman et. al. 2000
Coleta de dados é centralizada e feita
periodicamente.
Apropriado para redes proativas
Nós se organizam em aglomerados




Cada aglomerado possui um nó como base local (clusterhead)
Cada nó decide qual será sua base local (menor custo de
comunicação)
Rotação aleatória de bases locais para nós com maior
energia
Agregação de dados local (na base local)
LEACH
Low-Energy Adaptive Clustering Hierarchy

Cada base local cria um agendamento (TDMA) de
comunicação para seus nós no aglomerado




Cada aglomerado utiliza um código CMDA diferente
para evitar colisões
Alto consumo de energia nas bases locais



Rádio dos nós podem ficar desligados
Evita colisão nas transmissões
Porém o número de bases locais é mínimo (5%)
Bases locais são aleatórias
Maior duração da rede (tempo de vida)
ICA
Inter Cluster Routing Algorithm





Proposto por Habib et al. 2004
Mesmas regras de formação do LEACH
No início a base envia posição geográfica aos nós
(broadcast)
Nós conhecem sua posição geográfica e a da base
Diferenças



Nós estão ligados as bases locais mais próximas
geograficamente
Dados não são enviados diretamente a base global
Envia dados a outra base local na direção da base global
TEEN
Threshold sensitive Energy
Efficient sensor Network protocol


Proposto por Manjeshwat et al. 2001
Projetado para redes reativas


Nós sentindo o meio continuamente
Na troca da base local, esta difunde também
dois valores limiares:

Hardware Threshold (HT)


limiar no qual o valor continuamente sentido deve ser
transmitido
Software Threshold (ST).

variação mínima que justifique o valor ser transmitido
após a primeira vez
TEEN
Threshold sensitive Energy
Efficient sensor Network protocol

Nós só transmitem dados sensoriados quando
houver mudança significativa (ST)



Transmissão consome bem mais energia que
sensoriamento
Pode utilizar de escalonamento TDMA ou de
CMDA para evitar colisões
Desvantagem

Se HT não é alcançado, jamais o nó transmitirá
APTEEN (Adaptive TEEN)


Proposto por Manjeshwat et al. 2002
No momento da troca da base local o
procedimento é similar ao TEEN, só que
acrescido do seguintes parâmetros:


Agendamento - atribuindo um slot TDMA
para cada nó;
CountTime (CT) - o tempo máximo entre
duas comunicações sucessivas
SHARP
Hybrid Adaptive Routing Protocol







Proposto por Ramasubramanian et al. 2003
Ponto de equilíbrio entre protocolos reativos e próativos
Ajusta o grau de propagação de informações pela rede
Alguns nós determinam zonas pró-ativas
Nós a um certo raio deste são definidos como pertencentes
a zona pró-ativa
Nós fora destas zonas utilizam protocolos reativos
Zonas são definidas automativamente pelo protocolo
SHARP
Hybrid Adaptive Routing Protocol
`Zona Pró-Ativa
Comunicação
Pró-Ativa
Comunicação
Reativa
Comparação
Hierárquica
Plana
escalonamento baseado em reserva
escalonamento baseado em contenção
evita colisões
não evita colisões
"duty cycle" reduzido devido ao
adormecimento dos nós
"duty cycle" variável controlando o
adormecimento dos nós
agregação de dados nos
clusterheads
nós intermediários no caminho multi-hop
agrega dados dos vizinhos
roteamento simples, mas não
ótimo
roteamento complexo, mas ótimo
Comparação
Hierárquica
Plana
requer sincronização local e global
enlaces formados "on-the-fly" sem
sincronização
overhead de formação de cluster
rotas formadas apenas nas regiões que
tenha dados para transmissão
dissipação uniforme de energia,
mas não pode ser controlada
dissipação de energia depende do tráfego
alocação justa de canal
justiça não é garantida
baixa latência já que clusterheads
estão sempre disponíveis
latência ao acordar nós intermediários e
em estabelecer caminhos multi-saltos
Outros protocolos







ARC – Adaptive Rate Control – 2001
T-MAC – Time-Out-MAc – 2003
B-MAC - BackOff MAC – 2002
DE-MAC – Distributed Energy Aware MAC – 2003
TRAMA – Traffic Adaptive Multiple Access – 2003
STORM/AD – Self-Organizing Topology Discovery
and Maintenance/Adaptive Difusion – 2004
TynyOS Beaconing – 2004
Outros protocolos




PROC – Proactive Routing with Coordination –
2004
Geographic Routing without Localtion Information
– 2003
GEOMote - Geographic Multicast for Nw. sensors –
2004
Push Diffusion e One-Phase Pull - 2003