GINSS Jerome - Generation de graphes realistes pour la simulation de reseaux - Resultats

De Ensiwiki
Aller à : navigation, rechercher


Génération de graphes réalistes pour la simulation de réseaux

Labo LIG
Equipe Drakkar
Encadrants franck.rousseau@imag.fr

Etudiant

Jerome GINSS.jpg
Jérôme GINSS
ENSIMAG 2A - SIF (2009/2010)
mailto:Jerome.Ginss@ensimag.imag.fr

Livrables

Rapport du TER
Soutenance du TER

Pré-requis

Protocole Binary Waypoint

Le protocole Binary Waypoint [8] est un protocole de routage développé au sein de l'équipe Drakkar du Laboratoire d'Informatique de Grenoble. Rappelons tout d'abord ce qu'est le routage : dans un réseau de point à point, lorsqu'un point A tente de communiquer avec un point B, le message doit traverser plusieurs autres points du réseau. Le principe du routage consiste à choisir, à chaque point traversé, le "meilleur" voisin pour propager le message. Avec des algorithmes de routage gloutons, lorsqu'un "trou" est rencontré pendant le routage d'un message, il arrive que le message soit perdu [3]. La raison d'être du protocole de routage Binary Waypoint est d'améliorer la capacité à éviter lesdits "trous" avant de les rencontrer dans des réseaux sans fil.

Générateurs de graphes réalistes usuels

Il existe une pléthore de générateurs de graphes dits réalistes, se rangeant dans diverses catégories dont on ne dressera pas le détail sur cette page. Ils se rapprochent dans le fait qu'ils tentent de générer des graphes proches de réseaux que l'on peut rencontrer dans la réalité en faisant intervenir des critères observés sur des graphes réels. Ces critères sont nombreux et varient en complexité. Les générateurs croisent des critères différents et des paramètres spécifiques selon leur stratégie. Parmi les critères les plus couramment appliqués, on trouve cependant :

  • La distribution des degrés du graphe selon des lois Puissance [5] [1]
  • La propriété de petit diamètre [7]
  • Les effets de communauté [9]

Quantum GIS & Topogen

Quantum GIS est un Système d'Information Géographique (SIG). Il est libre, gratuit et extensible par la programmation de plugins. Il permet, entre autres, de gérer la superposition de couches de données géographiques vectorielles, et d'associer des méta-données typées aux éléments vectoriels de chaque couche.
Topogen est un composant du simulateur réseau à évènements discrets WSnet, utilisé au LIG. Topogen permet, entre autres, de mailler de très grands ensembles de points selon une portée (technologie radio) en paramètre [6].

Introduction

Une partie de l'étude des réseaux repose sur le test de protocoles à des fins comparatives. Lorsqu'une idée est proposée, on passe rapidement à des simulations de celle-ci. L'aspect critique de la simulation dans le domaine des réseaux est qu'il faut tenter d'approcher la réalité en concevant des tests à grande échelle avant des expérimentations plus longues et coûteuses à mettre en place. Un réseau étant à la base un graphe, on aboutit rapidement à la question de la génération de graphes pour simuler des protocoles.

Le test du protocole de routage Binary Waypoint a été la motivation principale de ce TER. Dans ce cas de test, on s'est intéressé particulièrement à l'aspect des trous présents dans les graphes supports de tests pour montrer l'intérêt de ce nouveau protocole par rapport aux protocoles de routage existants. En effet, le but était de prouver l'efficacité de Binary Waypoint à éviter les pertes de paquets pouvant être occasionnées par tous types de trous.

Bien que très aboutis et complexes, les générateurs classiques ne permettent pas d'engendrer une variété de trous aux motifs réalistes (e.g. absence de points causée par des éléments comme un fleuve, un lac, du relief, des routes, etc...). Le protocole de routage Binary Waypoint n'avait été, jusque là, testé que sur des trous peu réalistes, dont on donne un exemple sur la figure qui suit.

BinaryWaypoint.png

Il s'agissait donc de réaliser un générateur produisant des graphes aux trous réalistes pour évaluer la capacité de Binary Waypoint à éviter des trous semblables à ceux que l'on trouve dans des réseaux réels.

Travail réalisé

Principe

Dans le cadre de ce TER, on a proposé une approche nouvelle pour générer des graphes aux trous réalistes : non pas basée sur des modèles et des critères (Générateurs de graphes réalistes usuels), mais sur un vaste échantillon de données. L'application de cette idée a consisté à exploiter la structure de réseau matérialisée par les points d'accès réseau de toute une ville. Cependant, il serait difficile d'obtenir une carte de ces points d'accès en l'état.

  1. A partir d'une carte 3D des bâtiments d'une ville, la première passe consiste à induire le nombre et la position de ces points dans chaque bâtiment, sur la base de leur topologie et de quelques paramètres aléatoires. Cette tâche est réalisée par le plugin que j'ai développé pour Quantum GIS, dont je ne présente l'interface que dans mon rapport.
  2. Nous obtenons alors un très grand nuage de points, dont la structure approche celle d'un réseau sans fil métropolitain potentiel. La seconde passe consiste à mailler le réseau en fonction de la portée que l'on affecte aux nœuds (on crée un lien entre 2 points qui peuvent s'atteindre). On réalise cette tâche sous Topogen après avoir exporté les points générés dans le format adéquat depuis mon plugin.

Exemple de génération de graphe sur le campus

Génération de points sur le campus (Quantum GIS)
Maillage du nuage selon une portée de 50 mètres (Topogen)
Maillage du nuage selon une portée de 130 mètres (Topogen)

Exemple de génération de graphe sur toute la ville de Grenoble

Génération de points à l'échelle de Grenoble (Quantum GIS)
Maillage du nuage selon une portée de 50 mètres (Topogen)
Maillage du nuage selon une portée de 130 mètres (Topogen)

Conclusion

Si le défaut de la méthode empirique est certainement de devoir rassembler des données en grand nombre, l'avantage est que les graphes produits et leurs trous (rivières, relief, routes, étendues sans bâtiments, ...) sont intrinsèquement réalistes.

Notons enfin que ce TER est extensible. Nous retiendrons, entre autres, la possibilité d'ajouter des méta-données sur les bâtiments en entrée. Dans le cadre de ce TER, j'ai seulement disposé d'une carte 3D des bâtiments, mais le SIG utilisé permet de charger des méta-données pour chaque bâtiment. Avec des informations comme les densités de population ou les indices de développement humain, on pourrait par exemple approximer le nombre et la position des points avec davantage de réalisme encore.

Références contextuelles

[1] Emergence of Scaling in Random Networks. Science, p.509–512, 1999, A.-L.Barabasi, R.Albert
[2] Information diffusion on realistic networks. 9ème Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (2007) 35-38, J.-P.Cointet, C.Roth
[3] Bounds on Hop Distance in Greedy Routing Approach in Wireless Ad Hoc Networks , International Journal of Wireless and Mobile Computing Volume 1, Issue 2, p.131-140, 2006, ISSN:1741-1084, S.De, A.Caruso, T.Chaira, S.Chessa
[4] On the evolution of random graphs. Publication of the Mathematical Institute of the Hungarian Acadamy of Science, 5:17–61, 1960, P.Erdos, A.Rényi
[5] On power-law relationships of the Internet topology. Cambridge, Massachusetts, United States, p.251 – 262, 1999, ISBN:1-58113-135-6, M.Faloutsos, P.Faloutsos, C.Faloutsos
[6] Impact of the Physical Layer Modeling on the Accuracy and Scalability of Wireless Network Simulation. The Society for Modeling and Simulation International, vol.85, num.9, p.574–588, 2009, E.B.Hamida, G.Chelius, J.-M.Gorce
[7] Diameter of the World Wide Web. Nature Magazine, vol.401, 1999, p.130-131, R.Albert, H.Jeong, A.-L.Barabási
[8] Binary Waypoint Geographical Routing in Wireless Mesh Networks. In Proceedings of ACM MSWiM 2008. Vancouver, Canada, 27-31 October 2008, E.Schiller, P.Starzetz, F.Rousseau, A.Duda
[9] Collective dynamics of ‘small-world’ networks. Nature Magazine, vol.393, p.440-442, 1998, D.J.Watts, S.H.Strogatz