Information Technology Reference
In-Depth Information
where
q
a
is the probability that channel selection profile
a
is adopted. Obviously, the
optimal solution to problem (
4.7
) is to choose the optimal channel selection profiles
with probability one. It is known from the Markov approximation approach in [
6
] that
problem (
4.7
) can be approximated by the following convex optimization problem:
(
q
a
≥
0:
a
∈
ʩ
)
a
∈
ʩ
ʸ
a
∈
ʩ
1
max
q
a
ʦ
(
a
)
−
q
a
ln
q
a
s.t.
a
∈
ʩ
q
a
=
1,
(4.8)
where
ʸ
is the parameter that controls the approximation ratio. Note that the approx-
imation in (
4.8
) can guarantee the asymptotic optimality. This is because that when
ʸ
ₒ∞
, the problem (
4.8
) boils down to exactly the same as problem (
4.7
). That is,
when
ʸ
, the optimal solutions that maximize the potential function
ʦ
(
a
) will
be selected with probability one. Moreover, the approximation in (
4.8
) enables us
to obtain the close-form solution, which facilitates the distributed algorithm design
later. More specifically, by the KKT conditions [
7
], the optimal solution to problem
(
4.8
)isgivenas
ₒ∞
exp (
ʸʦ
(
a
))
a
∈
ʩ
exp (
ʸʦ
(
q
a
=
a
))
.
(4.9)
ˆ
Based on (
4.9
), we then design a self-organizing algorithm such that the asyn-
chronous channel selection updates of the users form a Markov chain (with the
system state as the channel selection profile
a
of all users). As long as the Markov
chain converges to the stationary distribution as given in (
4.9
), we can approach the
Nash equilibrium channel selection profile that maximizes the potential function by
setting a large enough parameter
ʸ
.
4.4.2
Markov Chain Design for Distributed Spectrum Access
Motivated by the seminal work on the adaptive CSMA mechanism [
8
], we propose a
distributed spectrum access algorithm in Algorithm 1 such that each user
n
updates
its channel selection according to a timer value that follows the exponential distri-
bution with a rate of
˄
n
. Note that the study in [
8
] focuses on the network utility
maximization, while in this paper we consider the social group utility maximization,
which results in significant differences in analysis.
Appealing to the property of exponential distributions, we have that the probability
that more than one users generate the same timer value and update their channels
simultaneously equals zero. Since one user will activate for the channel selection
update at a time, the direct transitions between two system states
a
and
a
are feasible
if these two system states differ by one and only one user's channel selection. We
also denote the set of system states that can be transited directly from the state
a
