Optimal Sampling Strategies for Minimum Latency Routing with Imperfect Link State

Abstract : Since dynamic wireless networks evolve over time, optimal routing computations need to be performed frequently on time-varying network topologies. However, it is often infeasible or expensive to gather the current state of links for the entire network all the time. We provide a thorough analytical characterization of the effect of various link-state sampling strategies operating under a limited sampling budget on the performance of the minimum-latency routing policy in a special class of dynamic networks. We show that for a two-state Markov link-dynamics model parameterized by probabilities p; q, if links are more likely to turn on than off at each time instant (p > q), a "depth-first" sampling strategy is optimal, whereas a "breadth-first" sampling strategy is optimal if links are more likely to turn off than on (p < q)--under the Cut Through (CuT) latency model, i.e., when the packet-forwarding latency is negligible compared to the time scale of the link dynamics. We precisely characterize the optimallatency spatial-sampling schedules for one-shot interrogation. We also present numerical simulation results on comparing various spatio-temporal sampling schedules under an overall sampling rate constraint, and initial results on comparisons of optimal schedules under a Store-and-Advance (SoA) packet-forwarding latency model.
Type de document :
Communication dans un congrès
WiOpt'12: Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks, May 2012, Paderborn, Germany. pp.81-88, 2012
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00763366
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : lundi 10 décembre 2012 - 15:59:32
Dernière modification le : mercredi 12 décembre 2012 - 10:29:04
Document(s) archivé(s) le : lundi 11 mars 2013 - 12:41:20

Fichier

p81-guha.pdf
Accord explicite pour ce dépôt

Identifiants

  • HAL Id : hal-00763366, version 1

Collections

Citation

Saikat Guha, Prithwish Basu, Howard Tripp, Timothy Freeman, Dmitriy Katz, et al.. Optimal Sampling Strategies for Minimum Latency Routing with Imperfect Link State. WiOpt'12: Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks, May 2012, Paderborn, Germany. pp.81-88, 2012. 〈hal-00763366〉

Partager

Métriques

Consultations de la notice

61

Téléchargements de fichiers

88