Sequential Learning for Multi-channel Wireless Network Monitoring with Channel Switching Costs
IEEE Transactions on Signal Processing, (September 2014)Abstract
We consider the problem of optimally assigning p sniffers to K channels to
monitor the transmission activities in a multi-channel 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 trade-off 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 super-class of multi-armed 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 the proposed Upper Confident Bound-based
(UCB) policy enjoys a logarithmic regret bound in time t that depends
sub-linearly on the number of arms, while its total switching cost grows with log(log(t)).