Timely Data Delivery in a Realistic Bus Network

Résumé : Bus et arrêts avec capacités de transmission WiFi peuvent constituer l'épine dorsale d'un réseau urbain tolérant aux délais, qui exploite les transmissions à courte portée, le stockage temporaire des données aux arrêts, et la mobilité prévisible de bus pour délivrer des informations non en temps réel. Cet article étudie le problème de savoir comment router les données à partir de la source jusqu'à la destination afin de maximiser la probabilité de livraison dans un délai donné. Nous supposons que nous connaissons les horaires de bus, mais nous prenons en compte le caractère aléatoire de la mobilité des bus, dû aux conditions de circulation ou au temps nécessaire pour l'embarquement et le débarquement des passagers. En ce sens, le présent document est l'un des premiers à aborder un scénario de mobilité quasi-déterministe. Nous proposons un modèle stochastique simple pour les arrivées de bus aux arrêts, motivé par une étude des traces réelles recueillies dans un vaste réseau urbain avec 250 lignes de bus et environ 7500 arrêts de bus. Une représentation graphique succincte de ce modèle nous permet de concevoir un algorithme de routage optimal (conformément à notre modèle) utilisant une seule copie des données, puis de l'étendre au cas où plusieurs copies des mêmes données sont permises. Grâce à une vaste étude de simulation, nous comparons l'algorithme de routage optimal avec trois autres approches : minimiser le temps attendu de traversement du graphe, maximiser la probabilité de livraison sur un horizon temporel infini, et un algorithme heuristique récemment proposé basé sur les fréquences de bus. Nous montrons que, en général, notre algorithme optimal surpasse les trois autres, mais il se réduit essentiellement à minimiser le temps de traversement quand les transmissions sont toujours couronnées de succès, ou à maximiser la probabilité de livraison sur un horizon temporel infini lorsque les transmissions échouent fréquemment. Pour les transmissions fiables et des valeurs des délais «raisonnables», l'extension multi-copie nécessite seulement 10 copies pour atteindre quasiment la même performance que celle du flooding, particulièrement coûteux en terme de nombre de transmissions et utilisation de buffers.
Type de document :
Rapport
[Research Report] RR-7344, INRIA. 2010
Liste complète des métadonnées

Littérature citée [44 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00547254
Contributeur : Giovanni Neglia <>
Soumis le : mercredi 15 décembre 2010 - 18:48:05
Dernière modification le : samedi 27 janvier 2018 - 01:31:42
Document(s) archivé(s) le : mercredi 16 mars 2011 - 04:04:17

Fichier

acer10inria_rr7344.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00547254, version 1

Collections

Citation

Utku Acer, Paolo Giaccone, David Hay, Giovanni Neglia, Saed Tarapiah. Timely Data Delivery in a Realistic Bus Network. [Research Report] RR-7344, INRIA. 2010. 〈inria-00547254〉

Partager

Métriques

Consultations de la notice

303

Téléchargements de fichiers

333