Communication Availability in Communications-Based TCSs ◾ 103
6.5 Modeling Data CommunicationSystem
Behavior with DSPNs
e main problem in our proposed CTMC model in Section 6.3 is that we
assume that the time between two successive handos is exponentially distributed.
However, the distance between successive APs and the train speed both may not
follow exponential distribution. In order to show the soundness of the approxima-
tion in our CTMC model, we formulate the data communication system behavior
with DSPNs.
e motivations of selecting the DSPN approach are as follows: (1) As a kind
of SPN, DSPN provides an intuitive and ecient way of describing the link
failure behaviors in WLAN-based data communication systems, especially facili-
tating hando behavior modeling. (2) DSPN allows timed transitions to have an
exponentially distributed time delay or a deterministic timed delay, which can
accurately model the situation when the time between two successive handos is
relatively constant. (3) SPN has been successfully used to analyze system avail-
ability in safety-critical on-demand systems [20] and industry plants [21], among
others.
6.5.1 Introduction to DSPNs
A Petri net is a directed bipartite graph with two types of nodes called places and
transitions, which are represented by circles and rectangles (or bars), respectively
[22]. Arcs connecting places to transitions are referred to as input arcs, whereas
the connections from transitions to places are called output arcs. A nonnegative
integer (the default value is 1) may be associated with an arc, which is referred to as
multiplicity or weight. Places correspond to state variables of the system, whereas
transitions correspond to actions that induce changes of states. A place may con-
tain tokens that are represented by dots in the Petri net. e state of the Petri net
is dened by its marking, which is represented by a vector
Ml
ll
k
=
(, ,...,
)
12
, where
lM
p
kk
= ()
is the number of tokens in place
p
k
. Here,
M()⋅
is a mapping func-
tion from a place to the number of tokens assigned to it. A transition is enabled
if the number of tokens in each of its input places is larger than the weight of its
corresponding input arc. An enabled transition can re, and as many tokens as
the weight of the corresponding input arcs are moved from the input place to the
output place.
SPNs are one kind of Petri nets in which an exponentially distributed time delay
is associated with each transition [22]. Generalized SPNs (GSPNs) extend the mod-
eling power of SPN and divide the transitions into two classes: the exponentially
distributed timed transitions (represented by blank rectangles), which are used to
model the random delays associated with the execution of activities, and immediate
transitions (represented by bars), which are devoted to the representation of logical
104 ◾ Advances in Communications-Based Train Control Systems
actions that do not consume time. DSPN [23] further extends GSPN in that it
allows timed transitions to have an exponentially distributed time delay or a deter-
ministic timed delay (represented by lled rectangles). e ring rate of the timed
transitions may be marking dependent.
6.5.2 DSPN Formulation
In this section, we model the data communication systems with dierent congu-
rations using dierent DSPNs.
For the data communication system with basic conguration, the corresponding
DSPN is shown in Figure6.7. Place
P
active
indicates the number of active link, and
it initially has one token. e system is on service when the only token is in
P
active
.
e tokens in place
P
fading
indicate the number of failed links caused by deep channel
fading, and the tokens in place
P
handoff
indicate the number of failed links caused by
hando.
T
fading
is an exponentially distributed timed transition, which denotes a fad-
ing process. When it res, a token will move from place P
active
to
P
fading
.
T
fading_recover
y
is the corresponding exponentially distributed timed transition that denotes a fad-
ing recovery process. When it res, a token will move from place
P
fading
to P
active
.
Transition
T
handoff
is a deterministic timed transition for service process. When it
res, a token will move from place P
active
to
P
handoff
.
T
handoff_recovery
is the corresponding
exponentially distributed timed transition that denotes a hando recovery process.
When it res, a token will move from place
P
handoff
to
P
active
.
Similarly, the DSPN model for the data communication systems with redun-
dancy congurations is shown in Figure6.8. Compared with the DSPN for basic
conguration, in this DSPN model, place P
active
initially has two tokens. e sys-
tem is on service only if
P
active
has one token inside. e explanation of other places
and transitions in the model is the same as that of the DSPN model for basic
conguration.
For the data communication systems with redundancy and backup link con-
gurations, the corresponding DSPN is shown in Figure 6.9. A place
P
backup
is
addedinto this DSPN model compared to other two models. e tokens in
P
backup
indicate the number of backup link, and there are initially two tokens in P
backup
T
fading
T
handoff
P
handoff
T
handoff_recovery
P
fading
T
fading_recovery
P
active
Figure 6.7 DSPN model for the data communication system with basic
conguration.
Communication Availability in Communications-Based TCSs ◾ 105
which correspond to two active links. When an active link fails due to deep channel
fading or hando, a back link will become active after an exponentially distributed
time. is process is denoted by two transitions
T
b_frecovery
and
T
b_hrecovery
. e expla-
nation of other places and transitions in the model is the same as that of the other
two DSPN models presented earlier.
6.5.3 DSPN Model Solutions
As shown in Figures 6.7 through 6.9, the number of deterministic transitions for
each marking is at most one in our DSPN models. According to [24], if at most one
deterministic transition is allowed to be enabled in each marking, the state prob-
abilities of a DSPN can be obtained analytically rather than by simulation.
e stochastic process
{(
),
0}
Dt t
>
underlying the DSPN is formed by the varia-
tions of the markings over the time domain.
{()}
Dt
is the marking of the DSPN at
time
t
. According to [24], when at most one deterministic transition is enabled in
each marking of the DSPN, the marking process
{(
),
0}
Dt t
>
is a Markov regenera-
tive process (MRGP). We include the proof for completeness next.
Let Ω be the set of all markings of a DSPN. It is also the state space of the mark-
ing process of the DSPN. For example, Ω
=
{1,2
,3}
mmm
is the state space of the
marking process of the DSPN in Figure6.7, where
m1
,
m2
, and
m3
indicate thatthe
23
T
fading
T
handoff
P
handoff
T
handoff_recovery
T
b_hrecovery
T
b_frecovery
P
fading
T
fading_recovery
P
active
P
backup
Figure 6.9 DSPN model for the proposed data communication system with
redundancy and backup link.
T
fading
T
handoff
P
handoff
T
handoff_recovery
P
fading
T
fading_recovery
P
active
Figure6.8 DSPN model for the data communication system with redundancy
and no backup link.
106 ◾ Advances in Communications-Based Train Control Systems
only token in the model is in P
fading
, P
active
, and P
hando
, respectively. Consider a
sequence
{,
>0
}
Tn
n
of epochs when the DSPN is observed. Let
T
0
0=
and dene
{,
>0}Tn
n
recursively as follows:
Suppose
DT
m
n
()=
,
1. If no deterministic transition is enabled in state
m
, dene
T
nl
+
to be the rst
time after
T
n
that a state change occurs. If no such time exists, we set
T
nl+
=∞
.
2. If a deterministic transition is enabled in state
m
, dene
T
nl
+
to be the time
when the deterministic transition res or is disabled.
With the above denition of
{, 0}
Tn
n
>
, let
YD
T
nn
= ()
. We rst show that
{(
,)
,0
}YT n
nn
≥
embedded in the marking process of DSPN is a Markov renewal
sequence, that is,
PY jT TtYiTY TYT
PY jT
nnnnnn n
nn
{, ,, ,,,,}
{,
11 11 00
1
++ −−
++
=−≤=
==
|
1
1110
=} {=
,}
−≤
=≤
=TtYiPY jT tY i
nn
||
(6.10)
e above equation can be explained in the following two cases:
1. No deterministic transition is enabled, that is, all the transitions that are
enabled in state
i
at time
T
n
are exponential transitions. In this case, due to
the memoryless property of the exponential random variable, the future of
the marking process depends only on the current state
i
and does not depend
upon the past history or the time index
n
.
2. Exactly one deterministic transition is enabled in state
i
. ere may be other
exponential transitions enabled in state
i
. In this case,
T
n+
1
is the next time
when the deterministic transition res or is disabled. e joint distribution of
Y
nl
+
and
()
1
TT
nn
+
−
will depend only on the state at time
T
n
. It is thus inde-
pendent of the past history and the time index
n
.
Now considering the marking process after time
T
n
, namely,
{(
), >0
}
DT tt
n
+
. Given
the history
{(
),0< <,() }Du uTDT i
nn
=
, we can see from Equation 6.10 that the sto-
chastic behavior of
{(
)>0,
0}
DT
tt
n
+≥
depends only on
DT i
n
()
=
. erefore,
{( )>0, 0(),0< <,() }
{( )>0, 0()
DT ttDu uTDT i
DT ttDT i
nn
n
nn
+≥ =
+≥ =
|
| }}
{()>0, 0(0) } Dt tDi
≥=
|
(6.11)
where
denotes equality in distribution. Equation 6.11 proves that
{(
), >0
}
Dt t
is
a Markov regenerative process.
Let
t →∞
. We can see
{, 0}Yn
n
≥
is a discrete time Markov chain with transi-
tion probability matrix
K
(∞). It is also called the embedded Markov chain (EMC)
for the DSPN. Matrix
Kt Kt
ij
()
[()]=
is called the kernel and
Kt
ij
()
satises
Communication Availability in Communications-Based TCSs ◾ 107
Kt PY jT tY i
ij
() {, }
11 0
==≤=|
(6.12)
Once we prove that the marking process under a DSPN is an MRP, the distri-
bution
pp
j
= ()
of the steady-state probabilities of the MRGP, which is also the
fraction of time the marking process spends in state
j
, can be calculated by the
following steps:
1. Calculate the kernel
Kt
Kt mn
mn mn
() [()] (,
)
,,
=∈Ω
of the marking process of
DSPN as follows:
a. For state
m
when
ΓΦ
()m
=
,
Kt
mn
mn
m
m
m
t
m
,
()
00
(,)
1>
0
=
=
−
()
−
Λ
Λ
Λ
Λ
λ
e
(6.13)
where:
Γ()
m is the set of deterministic transitions enabled in state
m
ΓΦ
()=m
means that no deterministic transition is enabled in
m
λ
(,
)mn
is the transition rate from marking
m
to
n
Λ
Ω
m
n
mn
=(,)
∈
∑
λ
b. For state
m
when
Γ
()
md=
with
τ
being the ring time of transition
d
,
if
nm∈Ω
ϒ
()
but
nm∉Ω
Γ
()
:
Kt
t
t
mn
Qmt
mn
Qm
mn
,
()
,
()
,
()
<
=
≥
e
e
τ
τ
τ
(6.14)
if
nm∈Ω
Γ
()
but
nm∉Ω
ϒ
()
:
Kt
t
mn t
mn
Qm
mm
mm
,
()
,
()
()=
0<
(,)
τ
τ
τ
e
′
≥
′
′
∈
∑
Ω
∆
(6.15)
if
nm∈Ω
Γ
()
but
nm∈Ω
ϒ
()
:
Kt
t
mn t
mn
Qm
mn
Qm
mm
mm
,
()
,
()
,
()
()=
0<
[] (,)
τ
τ
ττ
ee+
′
≥
′
′
∈
∑
Ω
∆
(6.16)
if
nm∉Ω
Γ
()
but
nm∉Ω
ϒ
()
:
Kt
mn,
()
=0
(6.17)
..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset
3.12.76.164