Optimality of Myopic Sensing in Multichannel Opportunistic Access
Top Cited Papers
- 18 August 2009
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 55 (9), 4040-4050
- https://doi.org/10.1109/tit.2009.2025561
Abstract
This paper considers opportunistic communication over multiple channels where the state (ldquogoodrdquo or ldquobadrdquo) of each channel evolves as independent and identically distributed (i.i.d.) Markov processes. A user, with limited channel sensing capability, chooses one channel to sense and decides whether to use the channel (based on the sensing result) in each time slot. A reward is obtained whenever the user senses and accesses a ldquogoodrdquo channel. The objective is to design a channel selection policy that maximizes the expected total (discounted or average) reward accrued over a finite or infinite horizon. This problem can be cast as a partially observed Markov decision process (POMDP) or a restless multiarmed bandit process, to which optimal solutions are often intractable. This paper shows that a myopic policy that maximizes the immediate one-step reward is optimal when the state transitions are positively correlated over time. When the state transitions are negatively correlated, we show that the same policy is optimal when the number of channels is limited to two or three, while presenting a counterexample for the case of four channels. This result finds applications in opportunistic transmission scheduling in a fading environment, cognitive radio networks for spectrum overlay, and resource-constrained jamming and antijamming.Keywords
Other Versions
This publication has 25 references indexed in Scilit:
- Approximation algorithms for restless bandit problemsJournal of the ACM, 2010
- Monotonicity in Markov Reward and Decision Chains: Theory and ApplicationsFoundations and Trends® in Stochastic Systems, 2006
- Restless bandits, partial conservation laws and indexabilityPublished by Cambridge University Press (CUP) ,2001
- Restless Bandits, Linear Programming Relaxations, and a Primal-Dual Index HeuristicOperations Research, 2000
- ON THE OPTIMALITY OF AN INDEX RULE IN MULTICHANNEL ALLOCATION FOR SINGLE-HOP MOBILE NETWORKS WITH MULTIPLE SERVICE CLASSESProbability in the Engineering and Informational Sciences, 2000
- The Complexity of Optimal Queuing Network ControlMathematics of Operations Research, 1999
- Discrete-Time Controlled Markov Processes with Average Cost Criterion: A SurveySIAM Journal on Control and Optimization, 1993
- On the average cost optimality equation and the structure of optimal policies for partially observable Markov decision processesAnnals of Operations Research, 1991
- On an index policy for restless banditsJournal of Applied Probability, 1990
- Restless bandits: activity allocation in a changing worldJournal of Applied Probability, 1988