De Ensiwiki.

Sommaire

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

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).