All Dates/Times are Australian Eastern Standard Time (AEST)

Technical Program

Paper Detail

Paper IDD6-S4-T2.3
Paper Title Online Learning for Shortest Path and Backpressure Routing in Wireless Networks
Authors Omer Amar, Kobi Cohen, Ben-Gurion University of the Negev, Israel
Session D6-S4-T2: Strategy, Games & Networks
Chaired Session: Monday, 19 July, 23:00 - 23:20
Engagement Session: Monday, 19 July, 23:20 - 23:40
Abstract We consider the adaptive routing problem in multihop wireless networks. The link states are assumed to be random variables drawn from unknown distributions, independent and identically distributed across links and time. This model has attracted a growing interest recently in cognitive radio networks and adaptive communication systems. In such networks, devices are cognitive in the sense of learning the link states and updating the transmission parameters to allow efficient resource utilization. This model contrasts sharply with the vast literature on routing algorithms that assumed complete knowledge about the link state means. The goal is to design an algorithm that learns online optimal paths for data transmissions to maximize the network throughput while attaining low path cost over flows in the network. We develop a novel Online Learning for Shortest path and Backpressure (OLSB) algorithm to achieve this goal. We show theoretically that OLSB achieves a logarithmic regret, defined as the loss of an algorithm as compared to a genie that has complete information about the link state means. Simulation results support the theoretical findings and demonstrate strong performance of the OLSB algorithm.