Seminar


Date : July 3, 2015, 11:15 a.m. - Room :Salle du conseil

Trouver l’enveloppe polygonale d’un réseau de capteurs sans fil.


M. Ahcene BOUNCEUR - Université de Brest

Possibilité de visio-conférence @IP : 193.55.95.10 Nom du correspondant technique : Nicolas CHAMPEIL Tél correspondant technique : 04 73 40 50 15 / 06 78 34 55 26 nicolas.champeil@isima.fr Tél salle de visio : 04 73 40 50 47 Trouver la frontière d’un réseau de capteurs sans fil (RCSF) fait partie des problématiques les plus importantes aujourd’hui. Cette frontière peut être utilisée, par exemple, pour surveiller une frontière, un endroit sécurisé ou un site sensible d’un pays. Une des méthodes qui peut être utile pour ce type de problèmes est l’algorithme de Jarvis, qui doit être adaptée pour tenir compte des nœuds connectés dans un graphe Euclidien. Pour ce type de réseaux, la complexité est réduite de O(nh) à O(kh^2), où n est le nombre de capteurs, k est le degré maximum d’un capteur dans le réseau et h est le nombre des capteurs de la frontière. L’application de cet algorithme pour les réseaux de capteurs permet à chaque itération de déterminer le nœud frontière voisin du nœud frontière courant. L’avantage de cette procédure est que chaque nœud connaît son voisin en une seule itération. Ensuite, chaque nœud envoie périodiquement un message à son voisin, qui devrait répondre. Si aucune réponse n’est reçue, une situation de défaillance ou d’intrusion sera déclenchée et la restructuration du réseau sera lancée pour trouver une nouvelle frontière. Dans ce travail, nous avons montré que l’application de cet algorithme en présence de sous-graphes spécifiques peut conduire à une situation de blocage. Nous avons également montré comment surmonter cette situation. Pour une implémentation sur des vrais capteurs, la version distribuée de l’algorithme sera présentée. Les algorithmes développés ont été validés à l’aide de la plateforme de conception et de simulation de réseaux de capteurs CupCarbon.