Approximate online learning algorithms for optimal monitoring in multi-channel wireless networks

We consider the problem of optimally selecting m out of M sniffers and assigning each sniffer one of the K channels to monitor the transmission activities in a multi-channel wireless network. The activity of users is initially unknown to the sniffers and is to be learned along with channel assignment decisions. Even with the full knowledge of user activity statistics, the offline optimization problem is known to be NP-hard. In this paper, we first propose a centralized online approximation algorithm and show that it incurs sub-linear regret bounds over time. A distributed algorithm is then proposed with moderate message complexity. We demonstrate both analytically and empirically the trade-offs between the computation cost and the rate of learning.