Efficient Online Learning Algorithms for Joint Path and Beam Selection in Multihop Mmwave Networks

To provide high coverage and combat high attenuation, mmWave networks typically require dense deployment of base stations, and adopt a self-backhauled network architecture where data are transmitted via multi-hop links. The unique characteristics of mmWave links (e.g., highly directional beams, sensitivity to blockage) bring challenges to designing an efficient online routing algorithm, where beam selection must be simulta-neously considered. In this paper, we formulate the online joint path and beam selection (JPBS) problem for multihop mmWave networks. We exploit the Unimodal property of the mmWave channel to design a new and efficient combinatorial bandit algorithm for JPBS: Combinatorial Unimodal Lower Confidence Bound based Joint Path and Beam Selection (CULCB-JPBS). We prove a finite-time regret bound of CULCB-JPBS and show that it is independent of the number of beams in each link. Furthermore, our experimental and simulation results show that our proposed learning algorithm can significantly improve the convergence rate and yield much lower regret (thus lower end-to-end delay), compared with existing approaches.