Digital Signal Processing Reference
In-Depth Information
Suppose that the arrival of messages at each user, say user
i
, is modeled as a sequence
of i.i.d. Bernoulli random variables, {
A
i
[
m
]}
m
=0
, with rate λ
i
packets per time slot. Let
B
i
,
i
= 1,
…
,
N
, be the buffer at user
i
that stores the packets awaiting transmission and
assume that there is no limit on the occupancy of the buffer. The number of packets in
the buffer
B
i
at the beginning of the
m
th
time slot is denoted by
Q
i
[
m
], which is referred
to as the
queue state
. Let {
~
i
[
m
]}
m
=0
be a sequence of Bernoulli random variables with
~
i
[
m
] ∈{0,1} and probability
p
i
= Pr(
~
i
[
m
] = 1), where
~
i
[
m
] = 1 indicates the event
that user
i
attempts a transmission in the
m
th
time slot regardless of whether it has a
packet to transmit. The event that user
i
actually transmits is then denoted by
V
i
[
m
] =
~
i
[
m
] · χ
N
(
Q
i
[
m
]), where
is the set of natural numbers 1, 2, 3, …, and χ
E
(
x
) is the indi-
cator function, defined as
=
, ∈
, ∉.
1
0
x
x
E
E
χ
E
(
x
The evolution of the queue states can then be written as
+
Qm
[
+= −
1
]
([]
Qm Dm
[
])
+ ,∀=, , ,
Am
[]
i
1
N
(11.1)
i
i
i
i
where
∏
1
Dm HmVm
[]
=
[][]
−
V
j
m
[]
i
i
i
ji
≠
is the departure process and (
x
)
+
= max{
x
,0}. It follows that
Q
i
[
m
+ 1] is independent of
Q
i
[
m
- 1] if given the values of {
Q
i
[
m
], ∀
i
}, and thus
Q
[
m
] = [
Q
1
[
m
],
…
,
Q
N
[
m
]] for
m
= 0,
1, 2, …, forms a discrete-time Markov chain.
In the discussions on MAC protocols, we are often concerned with the maximal stable
throughput of the system, which is defined as the maximum arrival rate that each user
can accommodate without causing the queues to become unstable.
Definition 11.1
The system is stable under the arrival rates (
λ
1
, λ
2
,
…
, λ
N
)
if there exists a set of transmis-
sion probabilities p
1
,
p
2
,
…
,
p
N
such that
limPr{
Qm xGx
[]
<=
}
(
)
and
lim
G x
()
=,∀.
1
i
i
i
i
m
→∞
x
→∞
Our goal is then to characterize the possible values of arrival rates for which the sys-
tem remains stable, which is defined as the
stability region
of the system. However, find-
ing the stability region of the slotted ALOHA system has been a difficult task. Over the
past 30 years, only the stability region of a two-user [27] or three-user [28] system has
been completely characterized, although inner and outer bounds have been derived for
the case where
N
> 3. In the following, we shall compare the two-user stability region of
Search WWH ::
Custom Search