Link throughput of multi-channel opportunistic access with limited sensing

We aim to characterize the maximum link throughput of a multi-channel opportunistic communication system. The states of these channels evolve as independent and identically distributed Markov processes (the Gilbert-Elliot channel model). A user, with limited sensing and access capability, chooses one channel to sense and access in each slot and collects a reward determined by the state of the chosen channel. Such a problem arises in cognitive radio networks for spectrum overlay, opportunistic transmissions in fading environments, and resource-constrained jamming and anti-jamming. The objective of this paper is to characterize the optimal performance of such systems. The problem can be generally formulated as obtaining the maximum expected long-term reward of a partially observable Markov decision process or a restless multi-armed bandit process, for which analytical characterizations are rare. Exploiting the structure and optimality of the myopic channel selection policy established recently, we obtain a closed-form expression of the maximum link throughput for two-channel systems and lower and upper bounds when there are more than two channels. These results allow us to study the rate at which the optimal performance of an opportunistic system increases with the number of channels and to obtain the limiting performance as the number of channels approaches to infinity.