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

https://hal.inria.fr/hal-00763780
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

File

p232-liu.pdf
Explicit agreement for this submission

Identifiers

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

Share

Metrics

Record views

32

Files downloads

149