Sequential Learning for Multi-Channel Wireless Network Monitoring With Channel Switching Costs
Authors:
- 12 September 2014
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Signal Processing
- Vol. 62 (22) , 5919-5929
Abstract
We consider the problem of optimally assigning p sniffers to K channels to monitor the transmission activities in a multichannel wireless network with switching costs. The activity of users is initially unknown to the sniffers and is to be learned along with channel assignment decisions to maximize the benefits of this assignment, resulting in the fundamental tradeoff between exploration and exploitation. Switching costs are incurred when sniffers change their channel assignments. As a result, frequent changes are undesirable. We formulate the sniffer-channel assignment with switching costs as a linear partial monitoring problem, a superclass of multiarmed bandits. As the number of arms (sniffer-channel assignments) is exponential, novel techniques are called for, to allow efficient learning. We use the linear bandit model to capture the dependency amongst the arms and develop a policy that takes advantage of this dependency. We prove that the proposed Upper Confident Bound-based (UCB) policy enjoys a logarithmic regret bound in time t that depends sublinearly on the number of arms, while its total switching cost grows in the order of O(loglog(t)).Keywords
Funding Information
- US National Science Foundation (CNS-1117560)
- Natural Sciences and Engineering Research Council of Canada (NSERC) Discovery Grants
- Alberta Innovates Technology Futures (AITF)
This publication has 26 references indexed in Scilit:
- Linearly Parameterized BanditsMathematics of Operations Research, 2010
- Tuning Bandit Algorithms in Stochastic Environments2007
- Regret Minimization Under Partial MonitoringMathematics of Operations Research, 2006
- A survey on the bandit problem with switching costsDe Economist, 2004
- Fine-grained network time synchronization using reference broadcastsACM SIGOPS Operating Systems Review, 2002
- Characterizing user behavior and network performance in a public wireless LANACM SIGMETRICS Performance Evaluation Review, 2002
- Sample mean based index policies byO(logn) regret for the multi-armed bandit problemAdvances in Applied Probability, 1995
- Asymptotically efficient allocation rules for the multiarmed bandit problem with multiple plays-Part II: Markovian rewardsIEEE Transactions on Automatic Control, 1987
- Asymptotically efficient adaptive allocation rulesAdvances in Applied Mathematics, 1985
- Some aspects of the sequential design of experimentsBulletin of the American Mathematical Society, 1952