Department of Computer Science at UH

University of Houston

Department of Computer Science

In Partial Fulfillment of the Requirements for the Degree of
Master of Science

Pallavi Arora

Will defend her thesis

Sequential Learning for Optimal Monitoring of Multi-Channel Wireless Networks

Abstract

We consider the problem of optimally assigning p sniffers to 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 while maximizing the benefits of this assignment, resulting in the fundamental trade-off between exploration versus exploitation. We formulate it as the 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 two policies that take advantage of this dependency. Both policies enjoy logarithmic regret bound of timeslots with a term that is sub-linear in the number of arms.

We also extended our work to consider the presence of switching cost associated with changes.

Date: Friday, July 22, 2011
Time: 11:00 AM
Place: 376-PGH
Faculty, students, and the general public are invited.
Advisor: Prof. Rong Zheng