Algorithmique de la mobilité
Il s'agit du projet de fin de module AlgoMob 2017, à réaliser en groupe de 2, 3 ou 4 étudiants (à constituer vous-même).
Un réseau de capteur est déployé et une station de base (ordinateur) récolte les informations captées par l'intermédiaire d'un arbre couvrant. On ne cherche pas ici à optimiser l'algorithme de collecte (ni à utiliser les valeurs captées), mais on s'intéresse à prolonger la durée de vie du réseau aussi longtemps que possible. À chaque fois qu'un noeud capte une valeur, il l'envoie à son parent, qui le retransmet au sien et ainsi de suite jusqu'à la station de base (racine de l'arbre). Chaque transmission de message par un capteur lui coûte une unité de batterie, et le capteur tombe en panne s'il atteint 0.
Vidéo 1: Algorithme naïf pour recharger les capteurs
Votre objectif est d'empêcher les capteurs de tomber en panne. Plusieurs moyens sont à votre disposition pour ce faire, le principal étant d'utiliser des robots mobiles capables de les recharger en WPT (Wireless Power Transfer).
Plus précisément, vous avez le droit de :
Vous n'avez pas le droit de :
Ces deux listes évolueront en fonction de vos questions/idées.
Le code qui vous est fourni correspond à celui de la vidéo ci-dessus, où les robots se déplacent aléatoirement pour recharger les capteurs (algorithme naïf). Il s'agira surtout de modifier les classes Robot, Sensor et BaseStation.
WaypointNodeVous connaissez déjà cette classe. La classe Robot donnée plus bas hérite de cette classe pour simplifier les déplacements. Il n'est pas obligatoire de conserver cet héritage, du moment que vous respecter la limite de vitesse établie.
import io.jbotsim.core.Node;
import io.jbotsim.core.Point;
import java.util.LinkedList;
import java.util.Queue;
public class WaypointNode extends Node {
Queue<Point> destinations = new LinkedList<>();
double speed = 1;
public void addDestination(double x, double y){
destinations.add(new Point(x, y));
}
public void setSpeed(double speed) {
this.speed = speed;
}
@Override
public void onClock() {
if (!destinations.isEmpty()) {
Point dest = destinations.peek();
if (distance(dest) > speed) {
setDirection(dest);
move(speed);
} else {
setLocation(dest);
destinations.poll();
onArrival();
}
}
}
public void onArrival(){ // to be overridden
}
}
Robotimport io.jbotsim.core.Node;
import io.jbotsim.ui.icons.Icons;
public class Robot extends WaypointNode {
@Override
public void onStart() {
setSensingRange(30);
setIcon(Icons.ROBOT);
setIconSize(16);
onArrival();
}
@Override
public void onSensingIn(Node node) {
if (node instanceof Sensor)
((Sensor) node).battery = 255;
}
@Override
public void onArrival() {
addDestination(Math.random()*600, Math.random()*400);
}
}Sensorimport io.jbotsim.core.Color;
import io.jbotsim.core.Message;
import io.jbotsim.core.Node;
public class Sensor extends Node {
Node parent = null;
int battery = 255;
@Override
public void onMessage(Message message) {
// "INIT" flag : construction of the spanning tree
// "SENSING" flag : transmission of the sensed values
// You can use other flags for your algorithms
if (message.getFlag().equals("INIT")) {
// if not yet in the tree
if (parent == null) {
// enter the tree
parent = message.getSender();
getCommonLinkWith(parent).setWidth(4);
// propagate further
sendAll(message);
}
} else if (message.getFlag().equals("SENSING")) {
// retransmit up the tree
send(parent, message);
}
}
@Override
public void send(Node destination, Message message) {
if (battery > 0) {
super.send(destination, message);
battery--;
updateColor();
}
}
@Override
public void onClock() {
if (parent != null) { // if already in the tree
if (Math.random() < 0.02) { // from time to time...
double sensedValue = Math.random(); // sense a value
send(parent, new Message(sensedValue, "SENSING")); // send it to parent
}
}
}
protected void updateColor() {
setColor(battery == 0 ? Color.red : new Color(255 - battery, 255 - battery, 255));
}
}BaseStationimport io.jbotsim.core.Message;
import io.jbotsim.core.Node;
import io.jbotsim.ui.icons.Icons;
public class BaseStation extends Node {
@Override
public void onStart() {
setIcon(Icons.STATION);
setIconSize(16);
// Initiates tree construction with an empty message
sendAll(new Message(null, "INIT"));
}
}MainVoici le code de la classe qui contient la méthode main(). Vous pouvez la modifier, mais seulement pour vos tests, car cette classe n'est pas à rendre !
import io.jbotsim.core.LinkResolver;
import io.jbotsim.core.Node;
import io.jbotsim.core.Topology;
import io.jbotsim.ui.JViewer;
public class Main {
public static void main(String[] args) {
// Create topology with clock not started
Topology tp = new Topology();
// Forbid communication between robots and sensors
tp.setLinkResolver(new LinkResolver(){
@Override
public boolean isHeardBy(Node n1, Node n2) {
if ((n1 instanceof Robot && n2 instanceof Sensor) ||
(n1 instanceof Sensor && n2 instanceof Robot))
return false;
else
return super.isHeardBy(n1, n2);
}
});
// Add sensors
tp.setDefaultNodeModel(Sensor.class);
String filename = "path-to/sensors.tp"; // to be adapted
String data = tp.getFileManager().read(filename);
tp.getSerializer().importFromString(tp, data);
// Add base station
tp.addNode(100, 80, new BaseStation());
// Add two robots
tp.addNode(90, 40, new Robot());
tp.addNode(60, 80, new Robot());
new JViewer(tp);
tp.start();
}
}Vous pouvez utiliser ce fichier de topologie, qui est le même que dans la vidéo. Ce fichier est susceptible de changer lors de l'évaluation.
L'algorithme sera évalué sur la base du premier moment où un noeud tombe en panne, pour une vitesse de robot et une fréquence de captage donnée. Pour l'instant, ces valeurs sont respectivement à 1 et à 0.02 (c.f. classes Robot et Sensor), mais elles sont susceptibles de changer d'ici l'évaluation. Une bonne pratique est de tenter d'augmenter la fréquence de captage autant que vous pouvez lors de vos tests en conservant une vitesse de 1.
L'évaluation détaillée du projet (rapport, barème, etc.) sera précisée plus tard.
Si un capteur tombe en panne (à cause de la batterie ou d'une autre raison), un bonus sera accordé aux groupes qui arrivent à détecter cela et à modifier l'arbre couvrant pour éviter ce capteur.
Je mettrai ici les réponses à vos questions, pour en faire profiter tout le monde.