TY - JOUR
T1 - SpecWatch
T2 - A framework for adversarial spectrum monitoring with unknown statistics
AU - Li, Ming
AU - Yang, Dejun
AU - Lin, Jian
AU - Li, Ming
AU - Tang, Jian
N1 - Funding Information:
This is an extended and enhanced version of the paper [55] that appeared in INFOCOM 2016. This research was supported in part by NSF grants 1443966, 1444059, 1619728, and 1717315. The information reported here does not reflect the position or the policy of the federal government.
Publisher Copyright:
© 2018 Elsevier B.V.
PY - 2018/10/9
Y1 - 2018/10/9
N2 - In cognitive radio networks (CRNs), dynamic spectrum access has been proposed to improve the spectrum utilization, but it also generates spectrum misuse problems. One common solution to these problems is to deploy monitors to detect misbehaviors on certain channel. However, in multi-channel CRNs, it is very costly to deploy monitors on every channel. With a limited number of monitors, we have to decide which channels to monitor. In addition, we need to determine how long to monitor each channel and in which order to monitor, because switching channels incurs costs. Moreover, the information about the misuse behavior is not available a priori. To answer those questions, we model the spectrum monitoring problem as a combinatorial adversarial multi-armed bandit problem with switching costs (MAB-SC), propose an effective framework, and design two online algorithms, SpecWatch-II and SpecWatch-III, based on the same framework. To evaluate the algorithms, we use weak regret, i.e., the performance difference between the solution of our algorithm and optimal (fixed) solution in hindsight, as the metric. We prove that the expected weak regret of SpecWatch-II is O(T2/3), where T is the time horizon. Whereas, the actual weak regret of SpecWatch-III is O(T2/3) with probability 1−δ for any δ ∈ (0, 1). Both algorithms guarantee the upper bounds matching the lower bound of the general adversarial MAB-SC problem. Therefore, they are all asymptotically optimal.
AB - In cognitive radio networks (CRNs), dynamic spectrum access has been proposed to improve the spectrum utilization, but it also generates spectrum misuse problems. One common solution to these problems is to deploy monitors to detect misbehaviors on certain channel. However, in multi-channel CRNs, it is very costly to deploy monitors on every channel. With a limited number of monitors, we have to decide which channels to monitor. In addition, we need to determine how long to monitor each channel and in which order to monitor, because switching channels incurs costs. Moreover, the information about the misuse behavior is not available a priori. To answer those questions, we model the spectrum monitoring problem as a combinatorial adversarial multi-armed bandit problem with switching costs (MAB-SC), propose an effective framework, and design two online algorithms, SpecWatch-II and SpecWatch-III, based on the same framework. To evaluate the algorithms, we use weak regret, i.e., the performance difference between the solution of our algorithm and optimal (fixed) solution in hindsight, as the metric. We prove that the expected weak regret of SpecWatch-II is O(T2/3), where T is the time horizon. Whereas, the actual weak regret of SpecWatch-III is O(T2/3) with probability 1−δ for any δ ∈ (0, 1). Both algorithms guarantee the upper bounds matching the lower bound of the general adversarial MAB-SC problem. Therefore, they are all asymptotically optimal.
KW - Cognitive radio networks
KW - Multi-armed bandit problem
KW - Spectrum monitoring
UR - http://www.scopus.com/inward/record.url?scp=85050153912&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85050153912&partnerID=8YFLogxK
U2 - 10.1016/j.comnet.2018.07.018
DO - 10.1016/j.comnet.2018.07.018
M3 - Article
AN - SCOPUS:85050153912
SN - 1389-1286
VL - 143
SP - 176
EP - 190
JO - Computer Networks
JF - Computer Networks
ER -