Information Technology Reference
In-Depth Information
It has been demonstrated that finding a feasible multicast tree with two independ-
ent additive path constraints is NP-complete. Obviously, since the delay and cost are
independent, a bandwidth-delay constrained least-cost multicast routing is a problem
of NP-complete.
Let
(
)
F
T
(
s
,
D
)
be a function that return fitness of a multicast tree
T
(
s
,
D
)
.
(
)
sT
is a bandwidth-delay-constrained
tree, then, it must return the cost of a tree as its fitness value. Also,
F
T
(
s
,
D
)
(
,
D
)
has the property that, if the
(
)
TF
must
be able to estimate how close is an infeasible solution, which does not satisfy con-
straints, is from the feasible region of search space by handling constraints. The most
common approach to handle constraints is to use penalties in
(
s
,
D
)
(
)
TF
.
According to these properties, we propose the following relation to evaluate solutions:
(
s
,
D
)
α
(
)
(
(
(
)
)
)
∏
F
T
(
s
,
D
)
=
Φ
Delay
P
s
,
d
−
Δ
∑
d
C
(
e
)
d
∈
D
(20)
e
∈
T
(
s
,
D
)
(
(
(
)
)
)
∏
×
Ψ
Bandwidth
P
s
,
d
−
β
d
d
∈
D
where
are penalty functions. For an addi-
tional illustration, an example is shown in Figure 5. The solution obtained using the
HS algorithm with ∆ = 25 is shown in bold lines in Figure 6.
is a positive real factor,
Φ
(⋅
)
and
Ψ
(⋅
)
α
Fig. 5.
Schematic of 15 node network
Search WWH ::
Custom Search