Paper Info
Title
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 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^2+D) and space complexity O (m) in the learning process, and time complexity O (D m^rho^r) 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
Year
DOI
Venue
2013
10.1109/ICDCS.2014.54
ICDCS
Keywords
DocType
Volume
optimisation,optimal channel access,time complexity,space complexity,cognitive radio,communication complexity,combinatorial mathematics,channel allocation,unknown channel variable,multichannel network,learning process,multihop cognitive radio network,multihop network,online dynamic channel access,linearly combinatorial multiarmed bandits problem,maximum weighted independent set problem
Journal
abs/1308.4751
ISSN
Citations 
PageRank 
1063-6927
5
0.41
References 
Authors
21
7
Name
Order
Citations
PageRank
Yaqin Zhou1303.32
Qiuyuan Huang217617.66
Fan Li385671.71
Xiang-Yang Li46855435.18
Min Liu533540.49
Zhongcheng Li639041.99
Zhiyuan Yin750.41