Multichannel opportunistic access by overhearing primary ARQ messages

We consider the scenario of a cognitive radio network overlaying on top of a legacy primary network by overhearing feedback signals over primary channels. The considered problem can be cast into a restless multiarmed bandit (RMAB) problem that is of fundamental importance in decision theory. It is well known that the optimal policy of the RMAB problem is PSPACE-hard to obtain due to its exponential computation complexity. A natural alternative is to consider an easily implementable myopic policy that maximizes immediate reward but ignores the impact of the current strategy on future reward. In this paper, we perform an analytical study on the structure, optimality, and performance of the myopic policy for the considered RMAB problem. The myopic policy is shown to have a simple queue structure, and then, its optimality is established for accessing N-1 of N channels and conjectured for the general case. The performance of the myopic policy is analyzed, which, based on the structure of the myopic policy and the domination theory, characterizes the lower and upper bounds of the throughput of a multichannel opportunistic communication system.