Skip to Main content Skip to Navigation
Conference papers

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.
Complete list of metadata
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s Connect in order to contact the contributor
Submitted on : Tuesday, December 11, 2012 - 2:46:12 PM
Last modification on : Wednesday, August 7, 2019 - 12:19:20 PM
Long-term archiving on: : Tuesday, March 12, 2013 - 6:15:30 AM


Explicit agreement for this submission


  • HAL Id : hal-00763780, version 1



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. ⟨hal-00763780⟩



Record views


Files downloads