Le groupe optimisation a obtenu plusieurs résultats liés à l’optimisation des réseaux.

De nouveaux algorithmes à plans coupants ont notamment été inventés (algorithme In-Out, et algorithmes de séparation multipoint) et utilisés pour résoudre des problèmes de conception de réseaux.

Un nouveau modèle du trafic a également été proposé : le modèle polyhédral où on suppose que la matrice de trafic varie dans un polytope. Un routage robuste
compatible avec ce modèle se calcule polynomialement. L’équipe optimisation a réussi à améliorer la fameuse borne semi-définie positive pour le problème de coupe maximum en utilisant des techniques spectrales.

Plusieurs problèmes combinatoires ont été étudiés avec une mise en évidence des cas qui se résolvent en temps polynomial (routage avec contraintes, généralisation de la coupe minimum, réseaux unicycliques,…).

D’autres travaux de recherche se sont fortement appuyés sur les processus stochastiques, les chaînes de Markov et les files d’attentes.

Un premier axe a consisté à explorer la modélisation au niveau flot dans les réseaux mobiles transportant des paquets. L’analyse d’un tel système prend la forme d’un processus QBD (Quasi-Birth Death) avec une solution basée sur l’approche « matrix-geometric » pour trouver les probabilités d’états. Ce formalisme permet de retrouver les bases de la théorie d’Erlang dans un contexte de commutation de paquets. Aussi, dans les réseaux sans fils et mobiles, la nature stochastique du medium radio implique différentes formes de diversités : temporelles,
spatiales, fréquentielles, que nous prenons en compte dans une modélisation inter-couche (cross-layer) afin de relier les spécificités des couches basses, notamment MAC et PHY, à la performance de la couche réseau.

Un autre axe s’est intéressé aux méthodes de bornes basées sur la théorie des ordres stochastiques qui sont assez complexes lorsque les processus sont multidimensionnels. Nous travaillons sur l’ordre fort, et aussi sur des ordres plus faibles moins contraignants, permettant d’obtenir des bornes de meilleure qualité.

Un autre groupe d’Armor a étudié les méthodes d’agrégation : lorsqu’on veut concevoir des réseaux de grande taille, il est nécessaire de les scinder en sous-réseaux afin de les gérer plus aisément. Il faut alors regrouper les
noeuds en agrégats. Ce groupe s’est intéressé à la méthodologie de constitution des clusteurs. Aucune méthode multisaut n’est réellement satisfaisante car le problème est NP complet. Le groupe a corrigé, validé et généralisé
l’algorithme Max-Min. Un algorithme d’adressage dans les clusteurs constitués a aussi été proposé. Des modélisations de l’algorithme de formation des clusteurs ont permis de caractériser le nombre moyen de noeuds dans un clusteur et d’autres quantités intéressantes. Ceci a amené le groupe à aborder la théorie de la percolation et à proposer un modèle empirique. De plus des bornes ont été données. La validité du modèle de Voronoï pour la représentation des clusteurs a aussi été évaluée.

Dans l’équipe TIPIC, les études des modélisations probabilistes de Markov ont été poursuivies à travers les modèles de Markov Couples et Triplets introduits dans la communauté scientifique internationale par cette équipe où différents apports des nouvelles variantes de ces modèles ont été proposés et analysés.

En particulier, des chaînes semi-markoviennes cachées par du bruit à mémoire longue, des modèles de Markov triplets avec un processus caché continu et un autre discret et des modèles Markoviens cachés non stationnaires ont été introduits et étudiés, de plus, des liens avec la théorie de l’évidence, et des copules ont été établis. De nouveaux outils théoriques ont également été proposés pour analyser divers algorithmes de Monte Carlo séquentiels, en particulier dans le cadre des chaînes de Markov cachées.

Cette équipe s’est également intéressée à divers problèmes de traitements statistiques du signal faisant appel à des outils mathématiques élaborés. Ainsi par exemple, le problème de la séparation de mélanges instantanés non linéaires a été abordé au travers de techniques purement algébriques, celui de l’analyse de performances de filtrage spatio-temporel a été résolue à l’aide d’une extension du théorème de Szegö aux valeurs propres généralisées qui a été démontrée. L’analyse des algorithmes itératifs en propagation de croyances s’est poursuivi grâce à leur interprétation en tant qu’algorithmes à maximum de vraisemblance sous contraintes en s’appuyant sur la géométrie d’information. La caractérisation des points stationnaires ainsi développée s’avère la duale mathématique au problème de minimisation d’une approximation dite de Bethe de l’énergie libre en physique statistique et ses liens avec une procédure de Gauss-Seidel en analyse numérique ont été approfondis.