Une résolution exacte pour l'optimisation de l'énergie dans les réseaux de capteurs sans-fil
1 : Parallélisme, Réseaux, Systèmes d'information, Modélisation
(PRISM)
-
Website
CNRS : UMR8144, Université de Versailles Saint-Quentin-en-Yvelines (UVSQ)
45 avenue des Etats-Unis Bâtiment Descartes 78035 Versailles CEDEX -
France
2 : Université Paris 10, Paris Ouest Nanterre La Défense
(UP10)
-
Website
Université Paris X - Paris Ouest Nanterre La Défense
200 avenue de la République - 92001 Nanterre cedex -
France
Les réseaux de capteurs permettent de surveiller des zones géographiques souvent difficiles d'accès, et trouvent des applications dans de nombreux domaines (surveillance de feu, collecte de données biologiques, ...). De par l'autonomie limitée de chaque capteur et puisqu'il est souvent difficile d'aller les chercher un par un pour les recharger, l'énergie apparaît comme une ressource critique pour les réseaux de capteurs.
Dans ce travail, étant donné un placement aléatoire des capteurs dans une zone géographique donnée, nous cherchons à déterminer une configuration de leurs puissances d'émission minimisant la dépense énergétique globale liée à la diffusion d'un message dans le réseau, tout en conservant une contrainte de connexité. Afin de pouvoir garantir l'emploi futur (après avoir fixé les puissances d'émission de chaque capteur) d'algorithmes distribués basés sur une topologie de communication bidirectionnelle, la contrainte de connexité retenue ici est la suivante : entre tout couple de capteurs, il doit exister au moins un chemin composé exclusivement de liens bidirectionnels.
Les méthodes usitées dans la littérature exploitent majoritairement la programmation mathématique. Ce travail propose une nouvelle approche du problème basée sur une méthode de séparation-évaluation ad-hoc évitant ainsi la traditionnelle relaxation lagrangienne du problème. Le calcul de la fonction d'évaluation ad-hoc de notre travail nous amène à résoudre en temps polynomial le problème relaxé par l'emploi d'une contrainte de connexité plus souple tout en conservant l'aspect combinatoire du problème. La complexité de notre fonction d'évaluation est en O(nm) avec n le nombre de capteurs et m le nombre de couples de capteurs capables de communiquer entre eux à leur puissance d'émission maximum. Un raffinement nous permet par ailleurs de calculer notre fonction d'évaluation avec une complexité en O(n^2).
Les premiers résultats de l'étude nous montrent que le cas des problèmes de taille n=25 peut être traité en quelques millièmes de secondes.
| Subject : | : | typdoc_1455 |
| Language of text | : | French |
| Topics | : | Network optimization and telecom applications |
| Keywords | : | réseaux de capteurs ; énergie ; branch & bound ; borne inférieure ; théorie des graphes |
| PDF version | : |  PDF version |
