Agrégation de données dans les réseaux de capteurs

On considère un ensemble de capteurs (sensors en anglais) déployés dans une région donnée. Ces capteurs sont capables d'effectuer des mesures, par exemple, mesurer la température locale, le taux d'humidité ou la présence de mouvements. En plus de ces capacités, les capteurs son capables de communiquer sans fil les uns avec les autres. On parle alors de réseaux de capteurs (wireless sensor networks, ou WSN en anglais).

L'idée derrière les réseaux de capteurs est de pouvoir surveiller une région de manière quasi-autonome, chaque capteur étant concerné par un petit sous-ensemble de la région. Un noeud spécial, appelé station de base, est chargée de collecter les informations en provenance des capteurs et éventuellement d'informer les opérateurs humains en cas d'alerte.

Infrastructure

Afin de simplifier l'acheminement des informations (routage), on organise les communications sous forme d'un arbre qui couvre tous les noeuds (arbre couvrant) et dont la racine est la station de base, comme illustré ci-dessous.

Arbre couvrant dans un réseau de capteur.

Cet arbre est construit de manière distribuée à l'initiative de la station de base.

Q1. Suivre le tutoriel sur la construction distribuée d'arbre couvrant. Ce tutoriel servira de base pour développer ensuite nos propres algorithmes.

Q2. Créer une nouvelle classe de noeud SensorNode qui hérite de TreeNode (issue du tutoriel). Dans cette nouvelle classe, surcharger la méthode onSelection() pour mettre à jour l'icône du noeud qui est choisi comme station de base (c'est à dire comme racine). La figure ci-dessus correspond au choix Icons.STATION.

Plutôt que de déployer les noeuds manuellement, vous pouvez utiliser ce fichier de topologie et le charger pendant l'exécution via le menu contextuel (bouton droit sur la surface grise) > Load topology.

Q3. Ajouter un champs value de type Integer ainsi qu'une méthode publique sense(), sans arguments ni valeur de retour, qui met à jour cette variable. On se contentera ici de tirer au sort une valeur entre 0 et 255, symbolisant par exemple le relevé d'une température par un capteur. Pour la visualisation, changez la couleur du noeud (setColor()) afin de représenter la valeur qu'il a captée. Le constructeur Color(r, g, b) peut s'avérer pratique ici.

Q4. Nous allons maintenant ajouter une entrée au menu contextuel de la simulation, pour déclencher la méthode sense() sur tous les noeuds en même temps. Pour cela, placez-vous dans la méthode main() (ou plus généralement, là où vous initialisez la topologie), et ajoutez le code suivant, qui créé une entrée "Update values" dans le menu et réagit à son déclenchement en appelant sense() sur tous les noeuds. (Remplacez topology par le nom de votre variable de type Topology, si différent):

    topology.addCommand("Update values");
    topology.addCommandListener(command -> {
        if (command.equals("Update values"))
            for (Node node : topology.getNodes())
                ((SensorNode)node).sense();
    });
    new JViewer(topology);

Agrégation des données

L'objectif de la station de base est de s'informer des valeurs relevées dans le réseau à intervalle régulier, afin de détecter une éventuelle anomalie. Bien entendu, il existe des bonnes et des mauvaises manières de le faire. En particulier, les capteurs ont de fortes contraintes d'économie d'énergie et on essaie donc de minimiser les communications. On se concentre ici sur les procotoles permettant de remonter l'information une seule fois. Si on veut le faire régulièrement, il suffit d'utiliser ces protocoles de manière répétée.

Protocole basique : Le moyen le plus facile, algorithmiquement, serait que chaque capteur envoie la valeur qu'il a relevée à son parent. Chaque valeur reçue par un noeud serait ensuite retransmise à son propre parent, et ainsi de suite jusqu'à la station de base (racine de l'arbre). Autrement dit, chaque valeur est remontée jusqu'à la racine.

Q5. Combien de messages ce protocole engendre dans le pire des cas ? Indice : le pire cas est celui où l'arbre est une chaîne unique. On se contentera d'un ordre de grandeur en fonction de $n$. (Il n'est pas demandé d'écrire du code pour cette question.)

Q5bis (facultatif). Et dans le cas d'un arbre binaire ?

Souvent, il n'est pas nécessaire de connaître chaque valeur captée. Par exemple, dans le cas d'une surveillance de feu de forêt, on peut se contenter de connaître la valeur maximum captée, et si elle dépasse un seuil, chercher alors à collecter plus d'information.

Protocole d'agrégation : Dans un protocole d'agrégation, chaque noeud attend de recevoir la valeur de ses enfants avant d'envoyer quoi que ce soit. Il "agrège", soit au fur et à mesure, soit tout d'un coup, ces valeurs entre elles et agrège aussi sa propre valeur (le tout selon une fonction bien définie, par exemple, la fonction maximum). Une fois terminé, il transmet le résultat à son parent, et ainsi de suite jusqu'à la racine.

Q6. Combien de messages ce protocole engendre-t-il ? Indice : Combien y a-t-il d'arête dans un arbre ? Combien y a-t-il de message par arête de l'arbre ? (on utilise les mots "arête" et "lien" comme synonymes ici)

Q7. Coder ce protocole d'agrégation dans la classe SensorNode en utilisant comme fonction d'agrégation le maximum des valeurs reçues. C'est la question la plus importante de la séance.

Astuce de visualisation: vous pouvez faire en sorte que la valeur captée par un noeud soit affichée lorsque vous passez la souris sur le noeud. Pour cela, il suffit de redéfinir la méthode toString() pour qu'elle renvoie cette valeur à la place de la valeur par défaut (l'identifiant du noeud), ou mieux, les deux à la fois en renvoyant getID() + ": " + value.

Q8. Adapter votre code pour que chaque noeud ayant des enfants colore en rouge le lien par lequel il a reçu la plus grande valeur (seulement si cette valeur est supérieure à celle qu'il a lui-même capté). Que représente l'ensemble des liens en rouge partant de la racine?

Q9. Implémenter les fonctions d'agrégation suivantes en conservant les différentes versions au fur et à mesure (soit en mettant votre code en commentaire de manière propre, soit en copiant votre classe à chaque fois, et en mettant à jour le "node model" votre méthode main()). Adaptez la génération de vos valeur ainsi que vos codes couleurs selon le type de donnée généré (p.ex. s'il s'agit de boolean, on utilise la classe Boolean et seulement couleurs).

Type	Fonction d'agrégation
Integer	Somme()
Boolean	AND()
Boolean	OR()
Boolean	Parité()
Double	Moyenne()

Le résultat final doit correspondre à ce que l'on obtiendrait en appliquant la fonction à l'ensemble de toutes les valeurs. La fonction Moyenne() est un peu plus difficile que les autres de ce point de vue. Ne tombez pas dans le piège.