Almost Optimal Channel Access in Multi-Hop Networks With Unknown Channel Variables

Abstract — We consider the problem of online dynamic channel accessing in multi-hop cognitive radio networks. Previous works on online dynamic channel accessing mainly focus on single-hop networks that assume complete conflicts among all secondary users. In the multi-hop multi-channel network settings studied here, there is more general competition among different com-munication pairs. A simple application of models for single-hop case to multi-hop case with N nodes and M channels leads to exponential time/space complexity O(MN), and poor theo-retical guarantee on throughput performance. We thus novelly formulate the problem as a linearly combinatorial multi-armed bandits (MAB) problem that involves a maximum weighted independent set (MWIS) problem with unknown weights. To efficiently address the problem, we propose a distributed channel access algorithm that can achieve 1/ρ of the optimum averaged throughput where each node has communication complexity O(r2 +D) and space complexity O(m) in the learning process, and time complexity O(Dmρ r) in strategy decision process for an arbitrary wireless network. Here ρ = 1+ is the approximation ratio to MWIS for a local r-hop network with m < N nodes, and D is the number of mini-rounds inside each round of strategy decision. I