Exibir código-fonte para Resumo "Estimador de link para redes de sensores sem fio baseada em Contiki"


Resumo do Trabalho de Heddegen 

Heddegem,   Van Ward. Cross Layer Link Estimation For Contiki-based Wireless Sensor Networks. Tese de Mestrado. Vrije Universiteit Brussel. .2009.


<!-- [[Arquivo:Modelo_4B.png|600px|center]] -->

O estimador de link 4B utiliza informações de 3 camadas diferentes do modelo OSI para determinar a qualidade do link. A referência as modelo OSI é, bem como, teoricamente o modelo na qual divide os protocolos de comunicação em sete camadas, na qual as mais baixas são camada física, enlace e de rede. O 4B usa 4 bits de informação dessas camadas, explorando as informações de qualidade de canal da camada física e combina com uma estimação do número de transmissão esperadas de dados da camada de enlace e informações da camada de rede.O Contiki apresenta uma pilha de comunicação de rede leve chamada Rime que fornece, entre outras coisas, uma protocolo de coleta de dados para rotear dados para um dispositivo de coleta. Este protocolo de coleta tem um estimador de link baseado em informações apenas da camada de enlace de dados. O protocolo Collection no Contiki é atualmente equipado com um estimador simples, mas ele beneficia estimadores mais avançados como o 4B.

=Conceitos iniciais=

== Estimador de link ==

Um tópico que é muito estudo é uma maneira na qual um dispositivo seleciona um vizinho para o envio de dados. Além disso, muitos dispositivos vizinhos podem se comunicar e configurar um link, baseando-se na estimação de qual link é melhor. O componente do algoritmo de roteamento que decide isso é chamado estimador de link. O estimador de link é a parte funcional do protocolo de coleta que é responsável por quantificar e calcular os custos do link.

==Estimador de qualidade de link 4B ==
===Categorizando as rede===
Um jeito popular de categorizar as redes sem fio é de acordo com a distância na qual temos WPAN, LAN e WAN. Outro maneira é de acordo com o número de links sem fio que cada dispositivo final é separado de uma estação base ou destino final. De qualquer forma, temos dificuldade para manter uma comunicação confiável à todo tempo.

==Redes sem fio Multi-hop==

Uma rede sem fio de múltiplos saltos é uma rede de computadores e dispositivos no qual são conectados via links de comunicação sem fio. Os links são geralmente implementados com rádios de pacotes digitais. Por cada enlace ter um limite pequeno de comunicações, muitos pares de nós não se comunicam diretamente e devem levar sua informação para frente através de um ou mais nós intermediários. O nó de origem transmite um pacote para um vizinho com o qual consegue se comunicar diretamente, fazendo com a operação tenha sequência até que chegue ao destino final. Essa etapa de envio de um nós ao outro é conhecido por hop. A definição do enlace no qual o pacote trafega é conhecido como caminho ou rota. As rotas são descobertas graças à um protocolo de roteamento na rede.

<!--[[Arquivo:Multi_hop.png|center|500px]] -->

==Protocolos de coleta e estimadores de enlace==

Quase todos os sistemas de redes sem fio contam com pelo menos dois protocolos multi-hop para suas operações básicas: Um protocolo de coleta de dados para  extrair dados de uma rede e um protocolo para enviar dados para uma rede através de um ou mais nós distintos. Todos os protocolos de coleta de dados dados comumente usados fornecem entrega de pacote de dados para um ponto de coleta(gateway) usando uma árvore de roteamento de baixo custo. O custo é geralmente medidos em termos de transmissões esperadas ou ETX: Os nós enviam pacotes na rota que requerem o menor número de transmissões para alcançar um ponto de coleta. Atualmente, os protocolos mais recentes mudaram para uma abordagem mais simples onde cada nó decide em para um único salto todo o tráfego de dados encaminhados criando assim árvores de roteamento para pontos fixos de coleta. A rede constrói isso visando que a rota até um determinado nó recebe um custo, sendo que o ponto de coleta tem valor 0 e os demais nós possuem custo em relação à sua posição mais a soma do custo de todos os nós intermediários necessário para chegar até o gateway.

<!--[[Arquivo:Custo_ETX.png|center|500px]] -->

==Pilha Rime==
---Escrever depois----
<!--[[Arquivo:RIME.png|center|500px]] -->


== Announcement primitive ==
O announcement primitive é uma adição recente (primavera de 2009) ao Rime pilha de comunicação. É de importância para este trabalho, porque é usado pelo Contiki coleta o protocolo. Atuam como uma abstração para enviar pequenos dados para o vizinho. Possuem implementação mais eficiente em relação à eficiência energética, uma vez que permitem que os nós os escutem seletivamente. Atualmente o Contiki possuem três deles: 

* polite-announcement, no qual usa broadcasts periódicos para enviar announcements.
* xmac-announcement, que envia announcement para a camada MAC quando está usando o protocolo XMAC MAC .
* Ipp-announcement também envia announcement para a camada MAC.

O polite-announcement será utilizado pelo protocolo collect no contiki. É particularmente adequado quando se utiliza o protocolo de camada MAC contiki nullmac no simulador Cooja. O protocolo de camada MAC nullmac é um protocolo que não executa nenhum controle de acesso ao meio. Ele funciona da seguinte maneira:
Ele é parametrizado por dois valores, um Tstart e Tmax. Quando o valor de announce muda, o announcement envia um pacote com o novo Tstart (Melhorar essa parte depois)

=Protocolo collect do Contiki=

O protocolo collect do Contiki implementa um mecanismo de coleta de dados confiáveis por saltos. O dado é enviado através uma topologia de árvore para um gateway.

Uma apresentação do protocolo collect é dada na figura abaixo. Ela ilustra a resposta do protocolo para alguns eventos como: pacote de dados que chega, um ack ou time-out de um pacote enviado, um pacote announcement que chegou e o envio de mensagem por alguma aplicação que o utiliza.

<!-- [[Arquivo: Collect_protocol.png|center|500px]] -->

==Componentes==
O protocolo consiste em um número de componentes de alto-nivel:

=== Roteamento ===
Os nós se auto-organizam em topologia de árvore, com dados sempre sendo enviado acima da árvore até chegar ao topo do nó. O gateway é definido para ser o topo da árvore, sendo que todos os outros nós são inicialmente nós secundários. 

Gradualmente, os nós atualizam suas posições na árvore. O mecanismo de roteamo para transporte dos dados originam de um nó qualquer em direção ao gateway, tendo sempre essa organização, com suas posições definidas por um valor de 16 bits rtmetric(métrica de rota). O gateway recebe o valor 0 e os demais abaixo tem seu valor dependente dos valores dos nós acima da arvore, incrementando no seu valor o valor de cada um, sendo que o pai de um determinado nó é sempre o melhor nó para comunicar e todo o fluxo de dados é entregue a ele. 

A árvore é criada dinamicamente por atualizações do valor rtmetric conforme eventos particulares vão acontecendo. Com isso, os pacotes announcement enviados para a descoberta do vizinho relatam o valor rtmétrico do nó anunciador. O valor rtmétrico deste vizinho é armazenado na tabela vizinha de cada nó receptor. O próprio valor rtmétrico do nó é então calculado com base no valor rtmétrico do melhor nó vizinho. O nó do melhor vizinho é o nó que fornece o caminho com o menor número de transmissões esperadas para o nó do coletor. Este é o caso para o vizinho que minimiza a soma do vizinho rtmetric e o número esperado de transmissões (ETX) do nó para aquele vizinho.

Uma vez que o processo é estabilizado, o rtmetric de um nó representa o número esperado de transmissão total para um pacote chegar ao gateway.

===Descoberta de vizinho e gerenciamento ===

Em um processo separado, viznhos anunciam seus presenças enviando periodicamente pacotes announcement. Esses announcement são usados para preencher a tabela de vizinhos com vizinhos. 

A descoberta de vizinhos e seu gerenciamento é localizado em um módulo separado no caminho (core/net/rime/neighbor.c). Também é localizada onde a tabela de vizinho é gerenciada.

A descoberta de vizinhos é organizada utilizando as primitivas de anunciamento do Rime. Essas primitivas enviam periodicamente pacotes em um canal lógico separado. Esses aunciamentos são caracterizados por uma tupla com id e valor que são disseminados para os vizinhos locais. Os pacotes de anunciamento não atravessam a pilha Rime completamente, pois é interceptada pela camada MAC. A camada MAC então notifica qualquer processo de registro, baseado no ID de anunciamento, sobre os anunciamentos que chegam. 

O protocolo de coleta utiliza anunciamentos que chegam para popular a tabela de vizinhos. O anúncio especifica o endereço do vizinho remetente, o ID (que é configurado para o número do canal, mas sem uso adicional), enquanto o valor representa a métrica de roteamento usada para criação e roteamento de árvore. Como a tabela do vizinho é limitada em tamanho (atualmente configurada para 8 vizinhos), é importante que os vizinhos "antigos" não ocupem a tabela por muito tempo. Deste modo, um temporizador desencadeia um varrimento periódico (isto é, a cada segundo) da tabela vizinha e remove todos os vizinhos que não foram ouvidos durante as últimas 120 digitalizações (isto é, aproximadamente 120 segundos).

=== Estimação de link ===

Com base em confirmações de nível de link para pacotes de dados enviados pelo nó, o valor ETX de cada vizinho na tabela vizinha é atualizado em cada ACK ou time-out. O valor ETX para cada nó vizinho é armazenado na tabela de vizinho, e são calculados cada vez que um pacote é enviado para um vizinho.
Quando o pacote enviado é reconhecido, o número de transmissões que foi requisitado para entregar o pacote é reportado para o estimador de link. Cada uma das últimas 8 transmissões são mantidas na tabela. O valor ETX do nó para o vizinho é a média sobre essas 8 transmissões. Se o tempo limite da transmissão esgota (time-out), o valor ETX é reportado e adicionado para o histórico atual.

=== Filtragem de pacotes duplicados e pacote "envelhecido" ===

Pacotes enviados do nó até alcançar seu gateway. Para proteção contra pacotes duplicados, um nó verifica um pacote duplicado através de um histórico limitado de envios. Se um envio é recente, o pacote é descartado. Adicionalmente, para prevenir que pacote fiquem trafegando pela rede para sempre, o pacote é descartado caso exceda um certo número de salto.

<!--[[Arquivo:Gerencia.png|center| 600px]] -->

== Atributos do protocolo ==
O seguintes atributos são utilizados por um pacote enviado usando o protocolo collect:

* EPACKT_ID - Cada pacote originado de um nó recebe um ID de 4-bit(também chamado de número de sequência). Juntamente com o endereço de origem armazenado no atributo ESENDER, ele identifica exclusivamente o pacote.
* ESENDER - O endereço do nó que inicializou o envio do pacote.
* HOPS - Esse atributo representa a contagem atual de salto. Inicialmente recebe o valor 1 e é incrementado a cada salto.
* TTL - o time-to-live representa o número máximo de saltos que o pacote pode realizar. É inicializado com valor 10 e decrementado à cada salto. Se um nó recebe um TTL igual à 1, o pacote é descartado.
*MAX_REXMIT - Usado pela camada Rime unicast (runicast). Esse valor representa o número máximo de niveis de transmissão para enviar ou encaminhar o pacote para o vizinho. Se o número máximo de transmissões for alcançado, o pacote ultrapassou o time-out, com isso é descartado, o dado ETX de vizinho é atualizado e o valor rtmetric é atualizado também.

Note que não temos atributos de endereço de destino já que, para o protocolo, todo dado é enviado para o gateway. 

<!--[[Arquivo:Atributos.png|center|500px]]

== Operação (Inicialização, envio e recepção) ==

===Inicialização===
Quando o protocolo é inicializado (chamando collect_open), a conexão runicast é inicializada, o rtmetric de todos os nós são inicializados e a descoberta de vizinhos é iniciada em um canal separado.

Para o protocolo operar corretamente, a aplicação deve definir um nó para ser o gateway através do collect_set_sink no nó.

===Enviando mensagem===
Para enviar o dado para o gateway, uma aplicação chama a função collect_send. O algoritmo opera da seguinte maneira:

* Primeiro, todas os atributos específicos de coleta são definidos.
* Então, o nó envia o pacote para o "pai" usando unicast. O runicast envia um pacote para um vizinho, isto é, ele tentará entregar uma mensagem para o vizinho, tentando por um número máximo de vezs até que receba um ack. Se for realizado, ele notifica a camada acima, caso contrário a camada acima é notificada com time-out. O nó pai é determinado a cada pedido do melhor vizinho da tabela de vizinhos. Se um melhor vizinho não for encontrado, o pacote é descartado e o nó ativa a escuta(por um determinado tempo) por anúncios para detectar vizinhos.
* Quando o pacote enviado é obtido pelo pai (node_packet_send é chamado) ou há um time-out (node_packet_timedout é chamado), o rtmetric do nó e o ETX do pai é atualizado.

===Enviado Mensagens===
Os dois tipos de pacotes são recebidos: Pacotes de dado e pacotes de anúncio.

Pacote de dados:
Quando um nó recebe um pacote de dados de coleta(Via runicast no qual chama a função node_packet_received) sempre acontece:
*Primeiro, filtro de pacotes duplicados é executado: O pacote é verificado com os últimos dois pacotes encaminhados. Se o ID (atributo EPACKET_ID) e o endereço originador da mensagem(atributo ESENDER) forem iguais, o pacote é descartado.
* Se o nó que recebe o pacote não é o gateway, faz algumas operações para encaminhá-lo. Se TTL igual 1, pacote é descartado. O contador de salto é incrementado e o TTL decrementado. O pacote é encaminhado para o pai usando a camada runicast. A seleção do pai é idêntico ao que foi descrito nas mensagens enviadas.

Pacotes de anúncio:
Quando um nó recebe um pacote de anúncio(received_announcement é chamado) o vizinho que enviou é verificado na tabela de vizinhos. Se não estiver presente, é adicionado na tabela.Caso contrário, o valor rtmetric do vizinho é atualizado. Se a tabela estiver cheia, o pior vizinho da tabela é excluido e substituido pelo novo vizinho. 


=Estimado de enlace sem fio 4B=
O estimador de enlace no protocolo collect do Contiki baseia seus cálculos em informações somente da camada de enlaces, isto é, ack ou time-out da camada de enlace.

O 4B fornece uma interface bem definida para combinar informações das camadas fisica, enlace e rede para estimação. 4B usa ETX como métrica de qualidade.

No 4B, a interface fornece 4 bits de informações compiladas de diferentes camadas:
* Um "bit branco" da camada fisica, denotando a baixa probabilidade de erro de decodificação no pacote recebido. Se o bit branco é setado, a qualidade média é alta. Se não for setado, então a qualidade média pode ou não ter sido alto durante a recepção. Como um principio básico, a qualidade média é considerada alto quando o LQI do pacote estiver acima de 90%. O LQI é uma caracterização da potência e/ou qualidade do pacote recebido, conforme o IEEE 802.15.4 Standard.
* Um bit ack na camada de enlace, indicando se um ack é recebido para um pacote enviado. Se o bit é setado, o ack foi recebido pela transmissão da camada de enlace de dados. Caso não for, o pacote pode ou não ter sido recebido com sucesso.
* Um bit pin da camada rede, indicando se o estimador pode remover o vizinho que entrou na tabela de vizinho. A camada de rede seta o bit pin para aquelas entradas que não deve ser removida na tabela. Isso faz sentido por exemplo, o vizinho do gateway: Eles querem manter o gateway na tabela de vizinhos à todo custo.
* Um bit compare da camada de rede, indicando se o valor de métrica do vizinho no qual um pacote foi recebido é melhor, isto é, mais baixo que o valor da métrica de um ou mais  na tabela de vizinho. Se o bit for setado, a rede sinaliza que o caminho através desse vizinho é melhor que um caminho através de pelo menos um vizinho na tabela vizinha.

=Implementação do 4B=

Nessa sessão iremos ver o detalhe das operações do estimador 4B, mostrar como ele é diferente do protocolo collect, e discutir algumas implementações do Contiki. Uma modificação no runicast será introduzida para corrigir uma falha no runicast atual.