Algorithms for Dynamic Spectrum Access with Learning for Cognitive Radio

Jayakrishnan Unnikrishnan; Venugopal Veeravalli

Source-linked AI summary

Algorithms for Dynamic Spectrum Access with Learning for Cognitive Radio

Jayakrishnan Unnikrishnan, Venugopal Veeravalli

arXiv:0807.2677v4Jul 16, 2008cs.NIcs.LG

TL;DR

The paper studies constrained dynamic spectrum sensing and access in cognitive radio systems with Markovian primary-channel occupancy and partial observations. It derives a greedy policy and reward bound when signal distributions are known, then develops a convergent learning algorithm for unknown distributions. The proposed methods perform close to an analytical upper bound, improve over an existing scheme, and outperform a worst-case naive design while preserving the interference constraint.

Problem
The paper addresses dynamic spectrum sensing and access when cooperative secondary users observe Markovian primary channels only through random signals and must constrain interference.
Method
It derives a greedy channel-selection policy and reward upper bound for known distributions, then learns unknown primary-signal statistics online using a parametric model.
Results
The known-distribution policy performs close to the analytical upper bound and better than an existing scheme, while the learning algorithm outperforms a worst-case naive design.
Takeaways & Limitations
Learning primary-signal statistics can improve cognitive-radio throughput while maintaining the required interference-probability constraint.
Takeaways & Limitations
When the primary transmitter’s mean signal power is high, secondary users cannot efficiently detect vacancies in the primary spectrum.

Abstract

from arXiv · show

We study the problem of dynamic spectrum sensing and access in cognitive radio systems as a partially observed Markov decision process (POMDP). A group of cognitive users cooperatively tries to exploit vacancies in primary (licensed) channels whose occupancies follow a Markovian evolution. We first consider the scenario where the cognitive users have perfect knowledge of the distribution of the signals they receive from the primary users. For this problem, we obtain a greedy channel selection and access policy that maximizes the instantaneous reward, while satisfying a constraint on the probability of interfering with licensed transmissions. We also derive an analytical universal upper bound on the performance of the optimal policy. Through simulation, we show that our scheme achieves good performance relative to the upper bound and improved performance relative to an existing scheme. We then consider the more practical scenario where the exact distribution of the signal from the primary is unknown. We assume a parametric model for the distribution and develop an algorithm that can learn the true distribution, still guaranteeing the constraint on the interference probability. We show that this algorithm outperforms the naive design that assumes a worst case value for the parameter. We also provide a proof for the convergence of the learning algorithm.

I. INTRODUCTION

The paper formulates cooperative cognitive-radio spectrum sensing and access as a constrained POMDP with partially observed Markovian channel occupancy. It develops policies for known and unknown primary-signal distributions, including online learning and comparisons with existing schemes.

IV. THE CASE OF UNKNOWN DISTRIBUTIONS: The learning scheme improves performance over a naive scheme that assumes a worst-case value for the unknown distribution.The paper presents learning unknown statistics as its main contribution for the second problem setting.
III. KNOWN DISTRIBUTIONS: For known primary-signal distributions, the paper derives a greedy channel-selection policy and an analytical upper bound on the expected reward.The cooperative formulation is equivalent in structure to a single-user problem while retaining the interference constraint.
V. SIMULATION RESULTS: Simulations show that the suboptimal POMDP solution performs close to the upper bound and better than an existing scheme.The comparison concerns the expected performance of the proposed access policy under the known-distribution setting.
IV. THE CASE OF UNKNOWN DISTRIBUTIONS: For unknown observation distributions, the paper introduces an online algorithm that learns the primary-signal statistics while maintaining the interference-probability constraint.The second part addresses the more practical case in which secondary users do not know the exact received-signal distribution.
II. PROBLEM STATEMENT: The problem is modeled as constrained spectrum sensing and access, where cooperative secondary users track channel occupancy from random observations whose distributions depend on channel state.The primary channel states evolve according to a Markovian model, and interference with primary transmissions must satisfy a probability constraint.

II. PROBLEM STATEMENT

The system chooses channels for cooperative sensing and access to maximize discounted expected reward while constraining interference with primary transmissions. Because channel states are unobserved, observations and access decisions define a constrained POMDP.

The objective is to select channels for sensing and access so total expected reward is maximized subject to an interference constraint.
Because the primary-channel states are not explicitly known, the resulting optimization is a constrained partially observable Markov decision process.
Primary occupancy is modeled with independent, statistically identical stationary Markov chains whose states indicate free or occupied channels.
The secondary users receive bandwidth B when accessing a free channel and must satisfy a per-slot constraint on interference probability.
The access structure uses current-slot observations and binary hypothesis testing, allowing thresholds to enforce the interference constraint.
Restricting access to the sensed channel converts the constrained problem into an unconstrained channel-selection POMDP after fixing the access rule.

III. DYNAMIC PROGRAMMING

The dynamic program represents uncertainty through channel-occupancy beliefs updated from observations and channel transitions. Because the exact Bellman solution is difficult, the paper adopts a suboptimal channel-selection policy and derives an upper-bound framework under stated Markov assumptions.

The objective maximizes discounted expected rewards over channel selections in the infinite-horizon dynamic program.
The system state is represented by per-channel beliefs, or conditional probabilities that channels are occupied.
Beliefs are initialized from the stationary distribution and updated using the Markov transition matrix and observations from selected channels.
Joint observations from cooperating users can be reduced to scalar log-likelihood ratios for belief updates and access decisions.
The exact Bellman solution is difficult to obtain, so the paper uses a suboptimal channel-selection policy designed to perform well.
The upper-bound derivation uses a Markov assumption that can be relaxed by separately treating cases where the stated inequality does not hold.

A. Greedy policy

The greedy policy chooses the channel with the highest probability of being free, thereby maximizing expected instantaneous reward. The paper identifies it with the QMDP policy and notes conditions under which it can be optimal.

A. Greedy policy: The greedy policy chooses the channel that is most likely to be free based on past observations.
A. Greedy policy: Its expected instantaneous reward for accessing channel a is B(1 − ǫ)(1 − q_a(k)).
A. Greedy policy: The policy is equivalent to the standard suboptimal QMDP solution for this POMDP.
A. Greedy policy: Under conditions where observations reveal the channel state, the greedy policy can be optimal at high signal-to-noise ratio.

B. An upper bound

The paper derives a universal upper bound on the optimal POMDP reward using the QMDP assumption, which treats channel states as known after each observation. The bound is computed through a fully observed dynamic program and upper-bounds the original problem's optimal reward.

The upper-bound value function is evaluated from the transition matrix and the initial belief vector, using stationary initialization when appropriate.The joint channel-state process has 2^L possible states represented by a 2^L × 2^L transition matrix.
The resulting fixed-point calculation determines the expected reward under the fully informed policy and therefore bounds any feasible POMDP solution.The derivation accounts for the state preceding the initial slot and propagates values through the Markov transition process.
Under exact state knowledge, the optimal policy selects the channel most likely to be free and maximizes expected instantaneous reward.The sensing action does not affect future rewards under this assumption.
The upper-bound derivation can be slightly modified when the stated technical assumption does not hold.The paper notes this extension without detailing the modified derivation.
The QMDP assumption yields an analytical upper bound on the optimal reward of the original POMDP.It assumes channel states become known exactly after observations, providing more information than is available in reality.

C. Comparison with [4] for single user problem

The paper compares observation-based tracking with an ACK-based scheme for a single cognitive user. Its formulation uses primary-signal observations, while the comparison scheme updates beliefs from one ACK bit and may require synchronization support.

The proposed approach applies to cooperative users and can also be used by a single cognitive user.Both formulations use partial observations rather than direct revelation of the true channel state.
The ACK-based scheme updates beliefs from the presence or absence of a single ACK signal after each transmission.Its design avoids a control channel because the receiver knows which channel to expect.
ACK synchronization is not reliable with hidden interfering terminals because ACK signals may no longer be error-free.The paper identifies a dedicated low-capacity control channel as a practical remedy.
The observation-based scheme improves transmission-opportunity utilization over the ACK-based scheme while also supporting synchronization through a dedicated control channel.The paper proposes using the control channel for synchronization and primary-channel observations for occupancy tracking.
The comparison assumes independent and identically distributed channel occupancies, whereas the referenced scheme handles correlated and non-identical channels.The proposed scheme can be modified for the more general setting, but with added complexity.

IV. THE CASE OF UNKNOWN DISTRIBUTIONS

For unknown primary-signal distributions, the paper models observations parametrically and develops robust and learning-based greedy access policies. The learning scheme preserves the interference constraint, converges to the true parameter, and improves performance over worst-case design.

A worst-case parameter policy offers a min-max guarantee but can substantially sacrifice reward when the true parameter is not worst-case.The worst-case value is associated with the least accurate belief tracking under the stated condition.
The unknown-distribution setting assumes a parametric model, independent identically distributed channel parameters, and independence from the Markov and noise processes.The treatment focuses on greedy channel-selection policies and allows extension from a single user to cooperating users.
The algorithm represents each channel's parameter and state using joint posterior beliefs updated from observations and access decisions.These beliefs are stored in an L × N × 2 array Q(k), rather than tracking channel-state beliefs alone.
The posterior mass function for each unknown parameter converges to a delta function, enabling learning of the actual parameter realization.The analysis assumes the parameter set is finite, although a compact-set scenario is discussed separately.
The access policy guarantees the interference constraint on average and asymptotically even when conditioned on the correct parameter value.The posterior parameter distribution converges to a point mass at the true value.
The learned-parameter scheme achieves substantial performance improvement over the worst-case approach.The paper reports that the worst-case design causes a severe decline relative to accurately known distribution parameters.

A. Known distributions

With known observation distributions, the paper evaluates greedy policies using observations, ACKs, or both under interference constraints. Observation-only access performs close to the upper bound and outperforms ACK-only access, especially under a stringent constraint.

The simulation uses a high discount factor α = 0.999 to approximate the undiscounted problem of practical interest.The observation model uses Gaussian parameters with σ = 1 and SNR values from −5 dB to 5 dB.
The greedy policy selects channels using thresholded observations, with the threshold chosen to satisfy the interference constraint.For the scalar observation model, the log-likelihood ratio is an increasing linear function of the observation.
The observation-only greedy policy performs within 10% of the upper bound and outperforms the ACK-only policy, especially for ζ = 0.01.The figure compares G1, which uses observations, with G2, which uses ACKs.
For ζ = 0.01, observation-only and observation-plus-ACK policies produce almost equal rewards because observations already provide substantial state information.The additional ACK information is insignificant when the interference constraint is low.

B. Unknown distributions

The paper models unknown primary-signal distributions parametrically and develops learning-based access policies that preserve the interference constraint. In simulations, learning substantially improves performance over the worst-case design, especially at high SNR, while convergence delays create a gap from known-parameter performance.

Model and policy: The unknown distribution is modeled with a parameter θa drawn from a finite positive set, with Gaussian observations under the primary-signal hypothesis.The parameterized model makes the log-likelihood ratio linear in the observation and permits threshold-based decisions.
Model and policy: For these distributions, the worst-case policy substitutes the minimum parameter value θ∗ = min Θ into the known-distribution access, selection, and belief-update structures.The resulting worst-case solution is identical in structure to the known-distribution example with µ replaced by θ∗.
Simulation results: Learning yields a significant performance advantage over the worst-case scheme at high SNR values.The worst-case threshold is too conservative, causing missed transmission opportunities.
Simulation results: The learning and known-parameter greedy policies show a significant high-SNR performance gap because posterior probabilities take time to converge.Initial conservative thresholds reduce discounted infinite-horizon reward.
Extension to compact sets: The learning algorithm can be adapted from finite Θ to compact parameter sets by quantizing the parameter range and updating posterior probabilities.When the true value lies between quantized values, the method can select a safer threshold that improves on the worst-case threshold.

VI. CONCLUSIONS AND DISCUSSION

The paper argues that learning primary-signal statistics improves cognitive-radio spectrum access beyond worst-case designs, especially at high SNR, while preserving practical interference constraints. The approach can improve throughput but relies on a reliable state-transition model and dedicated control-channel synchronization.

VI. CONCLUSIONS AND DISCUSSION: The scheme requires dedicated control channels for synchronization despite its throughput advantages.The paper identifies this coordination requirement as a practical cost of the proposed approach.
VI. CONCLUSIONS AND DISCUSSION: For unknown signal distributions in a parameterized family, worst-case parameter design can substantially reduce performance relative to known-distribution operation.The learning scheme addresses this gap while retaining the interference-protection objective described for the sensing and access problem.
VI. CONCLUSIONS AND DISCUSSION: The learning procedure requires a reliable model of the channel state-transition process to provide probabilistic guarantees and ensure convergence.This is an explicit limitation of the learning-based design.
VI. CONCLUSIONS AND DISCUSSION: Learning the primary signal parameter overcomes the performance loss of worst-case sensing and enables better exploitation of spectrum vacancies near the primary transmitter.The learned parameter permits more liberal thresholds when secondary users receive high-SNR primary signals.
VI. CONCLUSIONS AND DISCUSSION: The proposed scheme produces a significant performance improvement in overall cognitive-radio throughput.The conclusion connects improved vacancy detection near the primary transmitter with higher system throughput.

APPENDIX

The appendix proves that the learning algorithm’s posterior distribution converges to the true channel parameter almost surely under stated Markov-chain and observation-model assumptions. The proof reduces the analysis to a channel sensed every slot and then extends the result to the proposed sensing scheme.

Convergence theorem: Theorem A.1 establishes almost-sure convergence of the posterior parameter distribution for every channel under the stated assumptions.The assumptions include condition (16), distinct conditional observation densities, and the sensing scheme introduced in (36).
Proof setup: The proof focuses without loss of generality on the posterior distribution of the first channel’s parameter.The true parameter is represented by µi* in the parameter space Θ, with prior distribution π.
Proof reduction: Because the proposed scheme senses channel 1 at least every ML slots, its posterior is updated frequently enough to inherit convergence from a policy sensing that channel every slot.The argument compares the proposed observations with an ML-times undersampled Markov chain and then uses the every-slot sensing case.
Posterior concentration: Conditioned on the true parameter realization, the posterior probability assigned to that realization converges to one almost surely.The proof applies the observation distributions conditioned on candidate parameter values and concludes the result for every possible true realization.