Apuntes sobre enrutamiento con nrf24l01

La creación de redes de sensores es toda una ciencia en sí que lleva mas de 10 años desarrollándose en el mundo académico. Un resumen de distintos enfoques lo podemos encontrar en este enlace. Dadas las características del nsf24l01 no todas la soluciones tienen sentido, por eso es necesario escoger las que mas partido saquen del chip.

Decisiones generales

• mejor utilizar los pipes que ofrece el modo Shockburst
• recordemos que tenemos distintos canales radio disponibles
• cada decisión será justificada por el tipo de escenario que tenemos (estático vs dinámico, corto vs largo alcance, numero de nodos etc.)

Escenarios con pipes fijos

En este escenarios los pipes se usan por lo que son: canales de transmisión fijos o semi-fijos. Los pipes tienen la gran ventaja que implementan los ACKs en automatico, pero la gran desventaja que son canales casi unidireccionales, en el sentido que el nodo transmisor es el que tiene que empezar la comunicación siempre.

Escenario super simple: Topología a estrella con 6 hojas

la base se pone como nodo receptor Rx, y los otros nodos (hasta 6) como nodos transmisores (Tx). Cada sensor tiene un pipe asignado distinto. La topologia es estática y a estrella. La base queda siempre recibiendo y los otros siempre transmitiendo. Los TX pueden apagarse cuando quieran. Para comunicaciones de la base a los nodos es necesario usar los ACKs.

Ventajas:

• super sencillo
• ningún overhead
• todo el payload queda disponible para las aplicaciones
• eficiencia energética máxima

Limitaciones:

• no mas que 6 nodos
• todos los nodos en rango
• comunicación empezada siempre por los transmisores

Escenario topologia a árbol con enrutamiento manual

como en el escenario 1, pero hay un tipo de nodo que es "relay", es decir que es Rx y Tx al mismo tiempo. El nodo relay tiene que alternar modo recibir y modo transmitir. Cada vez que recibe algo lo tiene que transmitir a la base o al relay al cual està conectado. Cuando el relay se pone a transmitir, es posible que algún sensor le quisiera enviar algo en el cual caso no encontraría el relay en escucha. Este caso habría que gestionarlo (por ejemplo esperando un tiempo y volviendo a intentarlo). La topologia es de arbol y estatica. Las direcciones de los pipes tienen que ser distintas, si no dos nodos con el mismo pipe intentaran comunicarse a la vez. La base y los nodos relay tienen que estar en escucha siempre. Para comunicaciones de la base a los nodos se pueden usar los ACKs, pero no se pueden seleccionar todos los nodos de manera distinta (dado que solo se pueden direccionar los nodos conectados a la base), asi que queda solo la comunicacion de tipo broadcast.

Ventajas:

• super sencillo
• permite conectar mas de 6 nodos y también nodos no alcanzables desde la base
• overhead mínimo en caso de que un relay no este en escucha
• todo el payload queda disponible para las aplicaciones

Limitaciones:

• enrutamiento estático
• los relays siempre en escucha
• comunicación empezada siempre por los transmisores

Escenario topologia a arbol con enrutamiento automático semi-estático

como en el escenario 2, pero el enrutamiento no es programado en firmware si no que se auto-constituye. Una vez hecho el enrutamiento puede quedarse como estático (grabado en memoria para siempre) o semi-estético (con renovaciones periódicas). Para permitir este escenario es necesario que los nodos sean capaces de descubrirse el uno con el otro y enviarse informaciones sobre el alcance radio de cada uno y su situación energética. Para permitir esta información de "control" una de las opciones es dedicarle un pipe con una dirección común, como si fuera un canal de broadcast general (mejor quitar los ACKs en este caso).

Hay distintos algoritmos distribuidos o centralizados para generar el árbol de enrutamiento que tienen en cuenta distintos parámetros y tienden a optimizar cosas como el gasto energético, la fiabilidad del canal (ver sección mas abajo). Para elegir el algoritmo mejor hace falta un análisis ulterior de las posibilidades teniendo en cuenta las limitaciones intrínsecas del HW que tenemos.

Ventajas:

• permite conectar cualquier numero de nodos y con distintos alcances
• enrutamiento optimo (segun el algoritmo)
• no hace falta configurar nada
• si se separa el canal broadcast de los demas, todo el payload queda disponible para las aplicaciones

Limitaciones:

• los relays siempre en escucha
• comunicación empezada siempre por los transmisores
• un pipe queda dedicado al broadcast
• overhead considerable por tener que implementar el algoritmo de enrutamiento

Topologia mesh con enrutamiento automático dinámico

en este escenario cada mensaje se busca el recorrido hacia la base de manera dinámica, no hay rutas pre-establecidas, y no tiene sentido hablar de topologia, realmente es una red "mesh" donde todos están conectados a todos. Es un escenario apto para topologias extremadamente dinámicas con nodos en movimiento por ejemplo.

Pipes como direcciones MAC

Si en el escenario anterior los pipes son estables y representaban un canal fijo de comunicación entre dos nodos, aquí los pipes son canales temporales, es decir se abren y se cierran según las necesidades. Las direcciones de los pipes pueden ser utilizadas como canales separados en el mismo medio (el aire), por ejemplo asignando un canal común para todos los nodos y canales distintos para cada nodo. Para garantizar comunicaciones bidireccionales cada nodo puede ponerse como transmisor o como receptor, según la necesidad.

Cada pipe en principio esta asociado a un solo nodo receptor. Dado que los paquetes enviados en un pipe son leídos por todos los nodos en realidad son paquetes broadcast con una dirección concreta (los nodos receptores que no tengan esa dirección configurada no recogerán el paquete).

Este mecanismo se presta bien para redes mesh.

Algoritmos de creación de redes

LEACH

Es un algoritmo muy simple que optimiza el consumo energetico. presentación, paper, pagina wiki

Características:

• basado en la creación de clusters, o sea topología de arbol, lo cual implica el enrutamiento
• supone que los nodos pueden ajustar la potencia de transmisión
• cada cluster tiene un cluster head, o CH, o sea un nodo padre. La idea es que las hojas usan poca potencia de transmisión para llegar a un CH, y los CH usan mucha potencia para llegar a la base
• se pueden implementar clusters jerárquicos (clusters de clusters) pero el algoritmo no dice como
• hay una versión centralizada del mismo algoritmo (donde la base decide el enrutamiento optimo)

Algoritmo:

• Fase de creación de los clusters:
  • cada nodo decide si quiere ser cluster según un mecanismo probabilistico
  • este mecanismo tiene en cuenta si el nodo ha sido cluster ya (baja la probabilidad) y la energía disponible (mas energía mas alta la probabilidad)
  • los que han decidido ser cluster head envían un mensaje broadcast
  • en esta fase puede haber colisiones, entonces se aconseja algún mecanismo CSMA
  • los que no son cluster deciden cual es su mejor CH basándose en la potencia recibida
  • elegido el CH se le envía un mensaje para juntarse a la red (sigue utilizandose un CSMA)
  • los CH ahora saben quienes son sus hojas, organizan un TDMA entre sus nodos y les envían una respuesta (siempre con CSMA)
• Fase a régimen:
  • los nodos envían coordenados según el TDMA: las hojas encienden la radio cuando es su momento de transmitir solo y envían su paquete
  • para evitar interferencias entre nodos en clusters cercanos se sugiere el uso de CDMA (las llaves se pueden enviar durante la fase de establecimiento del TDMA)
  • los CH están en escucha todo el tiempo, pero se reservan un slot de tiempo para agregar todos los datos recibidos y enviarlos a la base (o a un super-CH)
  • durante el agregación de los datos se puede eliminar redudancia (es decir comprimir la información)

Adaptaciones posibles para el nrf24l01:

• todos los mensajes de broadcast se pueden enviar a una pipe con dirección común (quitando los ACKs)
• los nodos tendran que identificarse para saber quien es quien. La base podria tener una direccion especial
• si estamos en el escenarios con pipes fijos, cada cluster head no podrá aceptar mas que 5 nodos: o sea a la petición de join de los nodos hojas tiene que seguir una confirmación. Si el CH rechaza la petición del nodo hoja, este nodo tendrá que seguir proponiéndose a otros CH hasta que no encuentre un CH que le acepte. Si no encuentra ninguno disponible y si tiene acceso a la base puede hacerse CH el mismo
• al enviar la confirmacion, el CH puede adjuntar el numero de pipe al cual el nodo puede conectarse
• en este caso de pipes fijos habrá que asociar pipes distintos por cada CH para que no haya interferencia entre nodos
• el TDMA y el CDMA pueden ser opcionales, dependiendo de la cantidad de datos que uno se espera, o se puede implementar uno solo de los dos mecanismos
• una alternativa para el control de acceso múltiple es utilizar distintos canales radio, por ejemplo cada cluster head puede escoger un canal radio que resulte estar mas libre y comunicarlo a los nodos hojas para que lo utilicen (pero el canal de broadcast seguirá siendo el mismo para todos)
• si se asegura que cada nodo hoja se conecte con una cierta frecuencia, aunque no tenga nada que decir, se asegura también la bi-direccionalidad y que se pueda regenerar la red en cualquier momento (por ejemplo si algún nodo se añade de repente o si un CH muere)

Modificaciones necesarias para el caso cluster jerarquico:

• Cada cluster head tiene que estar conectado a otro cluster head, a parte la base.
• Entonces cada cluster head se comporta como nodo hoja a su vez escogiendo su CH con mayor potencia de transmisión.
• Para evitar que los CH se conecten en malla (en el cual caso generarían un loop que no sale nunca a la base) en el mensaje de join al CH habrá que añadir la cadena de nodos que se llevan conectados. Por ejemplo tengo 3 nodos conectados en cadena: n1->n2->n3, cuando n3 se quiere conectar a n4 le envía toda la cadena, n4 acepta pero antes de conectarse a otro CH averigua que no este en la lista, o sea que no sea ni n1, ni n2, n3.
• Un nodo CH siempre aceptara primero los nodos hoja y luego se conectara a otro CH.
• Puede haberse el caso que un nodo CH no encuentra otro CH que le acepte, porque los otros CH estan todos llenos o porque están en una cadena de nodos conectados a el. Es un caso un poco complejo (y poco probable) que se puede resolver de distintas maneras:
  • se deshace todo y se empieza desde cero, a través de un mensaje para ello. Dado que las probabilidades de ser CH cambiaran es de esperarse que cambie la topologia.
  • el nodo huérfano puede pedir a otro nodo en zona que no sea CH que le haga de CH. Para ello es necesario crear un paquete apósito para que invitar a todos los nodos hoja en la zona a mostrarse. El nodo huérfano podría pedir a la hoja que tenga mas potencia recibida de convertirse en CH. La hoja, recién convertida a CH, seguiria conectada a su CH. En el caso desafortunadisimo en que ninguna hoja quede disponible habrá que rehacerlo todo desde cero.