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

Yaqin Zhou*, Qiuyuan Huang, Fan Li, Xiang Yang Li, Min Liu, Zhongcheng Li, Zhiyuan Yin

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contribution

9 Citations (Scopus)

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 (MN), 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 (r2+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

Original languageEnglish
Title of host publicationICDCS 2014
Subtitle of host publicationProceedings of the IEEE 34th International Conference on Distributed Computing Systems
Place of PublicationPiscataway, NJ
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Pages461-470
Number of pages10
ISBN (Electronic)9781479951697, 9781479951680
DOIs
Publication statusPublished - 29 Aug 2014
Externally publishedYes
Event2014 IEEE 34th International Conference on Distributed Computing Systems, ICDCS 2014 - Madrid, Spain
Duration: 30 Jun 20143 Jul 2014

Other

Other2014 IEEE 34th International Conference on Distributed Computing Systems, ICDCS 2014
CountrySpain
CityMadrid
Period30/06/143/07/14

Fingerprint Dive into the research topics of 'Almost optimal channel access in multi-hop networks with unknown channel variables'. Together they form a unique fingerprint.

Cite this