Adaptive Shortest-Path Routing under Unknown and Stochastically Varying Link States

Abstract : We consider adaptive shortest-path routing in wireless networks. In this problem, we aim to optimize the quality of communication between a source and a destination through adaptive path selection. Due to the randomness and uncertainties in the network dynamics, the state of each communication link varies over time according to a stochastic process with unknown distributions. The link states are not directly observable. The aggregated end-to-end cost of a path from the source to the destination is revealed after the path is chosen for communication. The objective is an adaptive path selection algorithm that minimizes regret defined as the additional cost over the ideal scenario where the best path is known a priori. This problem can be cast as a variation of the classic multi-armed bandit (MAB) problem with each path as an arm and arms dependent through common links. We show that by exploiting arm dependencies, a regret polynomial with the network size can be achieved while maintaining the optimal logarithmic order with time. This is in sharp contrast with the exponential regret order with the network size offered by a direct application of the classic MAB policies that ignores arm dependencies. Furthermore, our results are obtained under a general model of link state distributions (including heavy-tailed distributions). These results find applications in cognitive radio and ad hoc networks with unknown and dynamic communication environments.
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.232-237, 2012
Liste complète des métadonnées

https://hal.inria.fr/hal-00763780
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mardi 11 décembre 2012 - 14:46:12
Dernière modification le : lundi 28 mai 2018 - 11:20:14
Document(s) archivé(s) le : mardi 12 mars 2013 - 06:15:30

Fichier

p232-liu.pdf
Accord explicite pour ce dépôt

Identifiants

  • HAL Id : hal-00763780, version 1

Collections

Citation

Keqin Liu, Qing Zhao. Adaptive Shortest-Path Routing under Unknown and Stochastically Varying Link States. WiOpt'12: Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks, May 2012, Paderborn, Germany. pp.232-237, 2012. 〈hal-00763780〉

Partager

Métriques

Consultations de la notice

62

Téléchargements de fichiers

115