Information Technology Reference
In-Depth Information
Since each user
n
activates its channel selection update according to the countdown
timer mechanism with a rate of
˄
n
, hence if
a
∈
ʔ
a
, the transition rate from state
a
to state
a
is given as
exp
ʸf
n
(
a
n
,
a
−
n
)
˄
n
|
M
n
|
q
a
,
a
=
exp
ʸf
n
(
a
n
,
a
−
n
)
,exp
(ʸf
n
(
a
n
,
a
−
n
)
)
.
(4.12)
max
{
}
Otherwise, we have
q
a
,
a
0. We show in Theorem
4.2
that the spectrum access
Markov chain is time reversible. Time reversibility means that when tracing the
Markov chain backwards, the stochastic behavior of the reverse Markov chain re-
mains the same. A nice property of a time reversible Markov chain is that it always
admits a unique stationary distribution, which is independent of the initial system
state. This implies that given any initial channel selections the distributed spectrum
access algorithm can drive the system converging to the stationary distribution given
in (
4.9
).
Theorem 4.2
The distributed spectrum access algorithm induces a time-reversible
Markov chain with the unique stationary distribution as given in
(
4.9
)
.
=
The proof is given in Appendix. One key idea of the proof is to show that the
distribution in (
4.9
) satisfies the following detailed balance equations:
q
a
q
a
,
a
=
a
,
a
q
a
q
a
,
a
,
∀
∈
ʩ.
4.4.3
Performance Analysis
According to Theorem
4.2
, we can achieve the SNE that maximizes the potential
function
ʦ
(
a
) of the SGUM game
ʓ
by setting
ʸ
. However, in practice
one has to choose only implement a finite value of
ʸ
. Let
ₒ∞
=
a
∈
ʩ
q
a
ʦ
(
a
)
ʦ
be the expected potential by Algorithm 1 and
ʦ
∗
=
max
a
∈
ʩ
ʦ
(
a
) be the maximum
potential. We show in Theorem
4.3
that, when a large enough
ʸ
is adopted in practice,
the gap between
ʦ
and
ʦ
∗
is very small.
Theorem 4.3
For the distributed spectrum access algorithm, we have that
0
≤
ʸ
n
=
1
ln
ʦ
∗
−
ʦ
1
≤
|
M
n
|
,
where
|
M
n
|
denotes the number of vacant channels of
user n.
Proof
First of all, we must have that
ʦ
∗
≥
ʦ
. According to (
4.7
) and (
4.8
), we then
have that
(
q
a
:
a
∈
ʩ
)
a
∈
ʩ
(
q
a
:
a
∈
ʩ
)
a
∈
ʩ
ʸ
a
∈
ʩ
1
max
q
a
ʦ
(
a
)
≤
max
q
a
ʦ
(
a
)
−
q
a
ln
q
a
,
(4.13)
ʸ
a
∈
ʩ
q
a
ln
q
a
1
1
ʸ
. Since
q
a
is the
which is due to the fact that 0
≤−
≤
ln
|
ʩ
|
max
(
q
a
:
a
∈
ʩ
)
a
∈
ʩ
q
a
ʦ
(
a
), according to (
4.13
),
optimal solution to (
4.8
) and
ʦ
∗
=
we know that
ʸ
a
∈
ʩ
1
ʦ
∗
≤
q
a
ʦ
(
a
)
q
a
ln
q
a
−
