Déploiement et caractérisation de la topologie d’un réseau distribué pour la gestion routière

Les approches centralisées ne peuvent pas faire face à la complexité croissante des réseaux de circulation urbains [TSS07]. Comme vu en introduction, l’utilisation d’un réseau décentralisé permettrait – a priori – d’améliorer la gestion de la cir- culation localisée sur une ou plusieurs intersections. Si un centre de contrôle global semble nécessaire aujourd’hui, l’application de technologies distribuées permettrait néanmoins d’acquérir plus d’autonomie. En effet, chaque élément du réseau distribué peut collaborer avec ses voisins proches et peut prendre des décisions localement. Cette approche a l’avantage de pouvoir répondre rapidement à des événements sur le terrain (p. ex., accidents), en s’affranchissant d’une connexion avec un centre de contrôle pouvant entraîner des temps de latence significatifs.Le succès des systèmes embarqués nous permet aujourd’hui de déployer un réseau dense de capteurs communiquant en sans fil. De plus, l’utilisation de liens sans fil permet de s’affranchir de connexions filaires, ce qui facilite l’installation des capteurs et réduit les coûts. Le déploiement d’un tel réseau à grande échelle permettrait, en outre, de fournir une infrastructure fixe favorisant le développement des applications véhiculaires, qui ont besoin d’utilisateurs pour former une infrastructure propre.

Toutefois, actuellement, peu de réseaux de ce type sont réellement déployés à l’échelle d’une ville. De tels déploiements se feront à un rythme très lent jusqu’à ce que la technologie elle-même prouve son efficacité. Dans ce chapitre, nous étudions les graphes issus de tels réseaux, et cherchons notamment à caractériser leur topologie, les graphes de connectivité qui en découlent, ainsi que leur rapprochement à des modèles de graphes aléatoires génériques. Cette étude peut servir de base pour les protocoles et l’évaluation de la performance des applications. Sur la base de quelques stratégies de déploiement que nous expliquons dans la section 3. 3, nous créons des graphes de communication qui résultent de la mise en place de capteurs sur plus deLe déploiement de systèmes distribués sur une large zone pose généralement des problèmes de couverture. Leurs éléments ne sont en effet pas systématiquement re- liés les uns aux autres, ce qui peut entrainer un partitionnement important. Les recherches dans les réseaux ad-hoc, maillés et de capteurs ont en effet montré que la topologie du réseau a un effet important sur ses performances [IA04 ; VS09 ; Puc+11 ; DHMP14]. La densité du réseau a un effet sur la congestion locale et sur la consom- mation d’énergie des nœuds. Elle influe notamment sur le protocole MAC. La densité des dispositifs est également un atout qui augmente la tolérance aux pannes : les me- sures et les chemins de communication impactés par une panne peuvent être relayés à un dispositif voisin. Le diamètre du réseau (c-à-d. l’excentricité maximale de ses nœuds) a un effet sur le retard de bout en bout. Enfin, le partitionnement du réseau définit si le réseau distribué peut travailler en autonomie ou doit être interconnecté à un réseau cellulaire ou filaire.

Dans la littérature, plusieurs études confirment le fait que les propriétés structu- relles du réseau ont un fort impact sur les performances des algorithmes, quels que soient les aspects du processus de communication. Ishizuka et Aida [IA04] examinent l’effet d’une topologie de capteurs sur la tolérance aux fautes et sur la probabilité de détection d’événement. Leurs simulations montrent en particulier que le place- ment initial des capteurs a un effet significatif sur la fiabilité du réseau. Vassiliou et Sergiou [VS09] étudient la performance de plusieurs algorithmes de contrôle de congestion pour des réseaux de capteurs sans fil sur de simples topologies, qui sont les mêmes que Ishizuka et Aida [IA04]. Ils montrent en particulier que les perfor- mances des algorithmes sont affectées par la topologie des réseaux considérés, ceci à cause des délais de transmission ou du taux de livraison. Puccinelli et al. [Puc+11] évaluent l’impact de la topologie sur le processus de collecte de données sur un ré- seau de capteurs, en utilisant des résultats expérimentaux. Leur conclusion est que la topologie doit être considérée afin d’évaluer complètement un protocole. Ducrocq et al. [DHMP14] évaluent l’impact de la topologie réseau sur le routage géographique. Ils montrent notamment que différentes topologies peuvent conduire à une différence allant jusqu’à 25% sur le taux de livraison et la longueur moyenne d’une route, et jusqu’à plus de 100% sur les coûts de transmission globaux.