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

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

Thème général

  • simulation réseau (WSNet, ns2, simulateur maison)
  • graphes, représentation, XML
  • système d'information géographique (SIG)

Compétences attendues

  • algorithmique
  • programmation (Java, C, Python ou autre)
  • réseaux (un peu)

Contexte du travail

Une partie de l'étude des réseaux repose sur la simulation de protocoles afin de valider les propositions à grande échelle et de les comparer aux travaux précédents et d'anticiper leur comportement en vue d'un déploiement. Un réseau étant à la base un graphe, on se trouve donc confronté à la génération de graphes sur lesquels évaluer les travaux étudiés. Ue possibilité consiste à générer des graphes aléatoires, cependant leurs caractéristiques ne reflètent que très peu la réalité. Certains algorithmes ont été proposés pour générer des graphes aux propriétés proches des graphes réels étudiés (average node degree, coefficient de clustering, small-world, etc.). Nous proposons une approche un peu différente pour essayer de générer des graphes réalistes, qui consiste à les générer à partir de données de l'environnement étudié (bâtiment, ville) en utilisant divers paramètres disponibles (topologie, densité de population, etc.).

Sujet

L'objectif de ce projet est de développer un module permettant de générer des graphes basés sur des données réalistes. Il faudra également s'intéresser au format de sortie à utiliser pour pouvoir utiliser ces graphes dans divers simulateurs. Pour les expérimentations nous disposerons de données réelles sur la ville de Grenoble.

On pourra par exemple envisager un plugin pour le SIG* Qgis [1] et ce développement se ferait alors en Python à l'aide du framework existant [2]. Une étude préliminaire déterminera si un autre environnement est plus adapté, notamment un système développé par une autre équipe du LIG (Java dans ce cas).

Résultats attendus

  • Une implémentation fonctionnelle.
  • Des premiers tests de simulation du protocole Binary Waypoint Routing sur de tels graphes réalistes.

Références

[1] http://www.qgis.org/

[2] http://wiki.qgis.org/qgiswiki/DevelopingPluginsWithPython