logo EDITE Sujets de doctorat

Robustesse et économie d'énergie dans les réseaux de capteurs

Sujet proposé par
Directeur de thèse:
Encadré par
Doctorant: Estelle MARIE
Unité de recherche EA 1395 Centre d'Étude et de Recherche en Informatique et Communications

Domaine: Sciences et technologies de l'information et de la communication

Projet

La problématique de ce sujet prend place dans le contexte des réseaux de capteurs échangeant des informations à l'aide de communications sans fils [1]. Etant donnés n capteurs et une zone de couverture, on cherche d'une part à placer les capteurs de façon à couvrir la zone et d'autre part à relier les capteurs de façon à ce qu'ils puissent tous communiquer deux à deux. Les nœuds de ce type de réseaux sont fortement sujets aux pannes ou à des propagations de fautes (intentionnelles ou non) du fait de leur faible qualité de production et aux conditions dans lesquelles ils sont déployés. Ainsi, l'objectif est d’améliorer la robustesse, c’est-à-dire de garantir le bon fonctionnement du système malgré l'apparition de pannes, de fautes ou la perturbation des liens de communication. La tolérance aux pannes est étudiée au niveau de la conception du réseau. On considérera ici que les pannes sont soit dispersées dans le réseau (pannes non groupées) soit dépendantes. Pour pallier la propagation de fautes, les nœuds du réseau peuvent être identifiés via un code (appelé code identifiant). Dans ce contexte, les réseaux de capteurs sans fils sont soumis à deux contraintes fortes [2, 3] :

1. Connectivité : L'un des points importants est de maintenir la connectivité dans le réseau afin d'acheminer les informations issues des nœuds capteurs en minimisant les interférences dans les zones denses. En présence de pannes, cela peut se traduire par la résolution des problèmes ci-dessous :

- k-chemins disjoints : Une approche classiquement utilisée pour acheminer les informations est d'établir un ensemble de nœuds ayant le rôle d'acheminer les informations. Pour cela, les nœuds doivent s'auto-organiser afin de construire un ensemble de nœuds dominant connexe possédant k chemins disjoints. Ainsi, pour assurer une meilleure robustesse, l'objectif est de garantir, malgré la présence de k pannes, le maintien d'un ensemble dominant connexe pour acheminer des messages à destination de tout nœud [4]. Ce problème peut être vu comme la généralisation du problème de construction d'un arbre de Steiner avec des critères de robustesse [5].

- Codes identifiants robustes minimum : Pour un graphe G = (X, A) non orienté, un sous-ensemble C de X est un code identifiant de G si, pour chaque sommet x de X, l’ensemble des éléments de C dans le voisinage de x augmenté de x est non vide et spécifique à x. Ces codes ont été introduits pour diagnostiquer des fautes dans les systèmes multiprocesseurs [6]. Ce problème a de multiples liens avec des problèmes théoriques de couverture notamment la construction d’un ensemble dominant [7], mais aussi beaucoup d’applications comme le routage dans les réseaux de capteurs [8]. Ce problème a été montré NP-difficile [9, 10]. Nous nous intéresserons à une variante de ce problème, appelée codes identifiants robustes, pour tolérer les pannes ou fautes dans le système [8, 11, 12, 13]. Cette variante considère une topologie dynamique dans laquelle on désire maintenir un code identifiant minimum malgré l’ajout et/ou la suppression de nœuds.

2. Durée de vie du réseau : Un second critère, après la connectivité, est de limiter au maximum les consommations énergétiques sur les capteurs, ce qui permet de plus d’augmenter la durée de vie du réseau. Les pics de consommation d'énergie sont observés lorsqu'un capteur envoie des informations. Cette consommation varie en fonction de la puissance d'émission utilisée. Ainsi, pour minimiser la consommation globale d'énergie, en plus du maintien de la connectivité, l'objectif sera d'étudier la modulation du rayon de communication ou de la topologie du réseau comme cela est fait pour les « systèmes de surveillance », qui constituent une généralisation des codes identifiants [14]. Il faudra aussi tenir compte de l'apparition d'interférences quand le rayon de communication utilisé pour maintenir une bonne connectivité est trop grand. Des travaux ont été menés avec les codes identifiants robustes pour étudier le compromis entre robustesse et consommation énergétique [11, 15]. Ce problème est par ailleurs proche des problèmes de localisation de casernes de pompiers avec un critère de rayon, connus dans littérature sous le nom de localisation simple, p-centre ou p-median [16, 17].

[1] J. Yick, B. Mukherjee, D. Ghosal, “Wireless sensor network survey”, Computer Networks, vol. 52(12), 2008, pp. 2292-2330.

[2] M. Younis, I. F. Senturk, K. Akkaya S. Lee, F. Senel, “Topology management techniques for tolerating node failures in wireless sensor networks: A survey”, Computer Networks, vol. 58, 2014, pp. 254-283.

[3] G. Anastasi, M. Conti, M. Di Francesco, A. Passarella, “Energy conservation in wireless sensor networks: A survey”, Ad Hoc Networks, vol. 7(3), 2009, pp. 537-568.

[4] F. Dai, J. Wu, “On constructing k-connected k-dominating sets in wireless ad-hoc and sensor networks”, Journal of Parallel and Distributed Computing, vol. 66 (7), 2006, pp. 947–958.

[5] L. Blin, M. Potop-Butucaru, S. Rovedakis, “super-stabilizing log(n)-approximation algorithm for dynamic Steiner trees”, Theorical Computer Science, vol. 500, 2013, pp 90-112.

[6] M. G. Karpovsky, K. Chakrabarty, L. B. Levitin, “A new class of codes for identification of vertices in graphs”, IEEE Transactions on Information Theory, vol. 44(2), 1998, pp. 599–611.

[7] M. Laifenfeld, A. Trachtenberg, “Identifying Codes and Covering Problems”, IEEE Transactions on Information Theory, vol. 54(9), 2008, pp. 3929-3950.

[8] M. Laifenfeld, A. Trachtenberg, R. Cohen, D. Starobinski, “Joint Monitoring and Routing in Wireless Sensor Networks Using Robust Identifying Codes”, Mobile Networks and Applications, vol. 14(4), 2009, pp. 415-432.

[9] D. Auger, I. Charon, O. Hudry, A. Lobstein, “Complexity results for identifying codes in planar graphs”, International Transactions in Operational Research, vol. 6, 2010, pp. 691-710.

[10] I. Charon, O. Hudry, A. Lobstein, “Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard”, Theoretical Computer Science, vol. 290, 2003, pp. 2109-2120.

[11] S. Ray, R. Ungrangsi, F. De Pellegrini, A. Trachtenberg, D. Starobinski, “Robust location detection in emergency sensor networks”, Proceedings of the IEEE INFOCOM, 2003, pp. 1044–1053.

[12] I. Charon, I. Honkala, O. Hudry, A. Lobstein, “Minimum Sizes of Identifying Codes in Graphs Differing by One Vertex”, Cryptography and Communications - Discrete Structures, Boolean Functions and Sequences, vol. 5, 2013, pp. 119-136.

[13] I. Charon, I. Honkala, O. Hudry, A. Lobstein, “Minimum Sizes of Identifying Codes in Graphs Differing by One Edge”, Cryptography and Communications - Discrete Structures, Boolean Functions and Sequences, vol. 6 (2), 2014, pp. 157-170.

[14] D. Auger, I. Charon, O. Hudry, A. Lobstein, “Watching systems in graphs: an extension of identifying codes”, Discrete Applied Mathematics, vol. 161, 2013, pp. 1674–1685.

[15] M. Laifenfeld, A. Trachtenberg, “Disjoint identifying codes for arbitrary graphs”, IEEE International Symposium on Information Theory, 2005, pp. 4-9

[16] S. Elloumi, A. Plateau, “A computational study for the p-median Problem”, Electronic Notes in Discrete Mathematics, vol. 36, 2010, pp. 455-462.

[17] S. Elloumi, “A tighter formulation of the p-median problem”, Journal of Combinatorial Optimization, vol. 19(1), 2010, pp. 69-83.

[18] F. Al-Turjman, H. Hassanein, M. Ibnkahla, “Optimized relay repositioning for wireless sensor networks applied in environmental applications”, Proceedings of the IEEE International Wireless Communications and Mobile Computing, 2011.

[19] A. Alfadhly, U. Baroudi, M. Younis, “Optimal node repositioning for tolerating node failure in wireless sensor actor network”, Proceedings of the 25th Biennial Symposium on Communication, 2010.

Enjeux

L'objectif sera dans un premier temps d'optimiser la topologie du réseau dans un contexte statique puis dynamique.

Dans le contexte statique, tous les nœuds du réseau ont une position fixe. Le problème d'optimisation qui nous intéresse consiste à concevoir un réseau robuste avec une consommation énergétique minimale. Son originalité réside dans la prise en compte à la fois des aspects de localisation, de la garantie de la k-connectivité et dans l'utilisation des codes identifiants.

Dans le cas dynamique, le réseau est composé de nœuds fixes (capteurs simples) et de nœuds mobiles (stations) dont le déplacement a un coût en énergie. L'objectif sera alors de chercher à garantir les mêmes propriétés que dans le cas statique, en tirant partie de la mobilité des stations, c'est-à-dire en planifiant un déplacement des stations qui minimise les coûts de déplacements [18, 19]. L'idée originale ici est de tenir compte de la possibilité de mobilité de certains nœuds dans la phase de conception du réseau afin d'améliorer la robustesse de la phase de déploiement.

Les différentes étapes à réaliser durant la thèse sont :

1. Un état de l'art des modèles et approches de résolution utilisés dans les contextes statique et dynamique.

2. Proposition de modélisations de diverses variantes du problème avec étude de complexité pour les contextes statique et dynamique.

3. Étude de méthodes de résolution pour les modèles proposés.

Remarques additionnelles

Ce projet de thèse fera suite à un sujet de stage de Master proposé par Agnès Plateau et Stéphane Rovedakis qui continueront à être actifs dans l'encadrement de la thèse.