Almost optimal channel access in multi-hop networks with unknown channel variables

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 communication 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 (M^N), and poor theoretical 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/rho of the optimum averaged throughput where each node has communication complexity O (r²+D) and space complexity O (m) in the learning process, and time complexity O (D mrhor) in strategy decision process for an arbitrary wireless network. Here rho = 1 + epsilon is the approximation ratio to MWIS for a local r-hop network with m