Geoscience Reference
In-Depth Information
20.4
The Regenerator Location Problem
Fiber optic cables used today provide large capacity, and technologies like Wave
Division Multiplexing (WDM) are frequently used to increase it further by using
multiple wavelengths to transmit different signals on the same fiber. In practice, this
means that an optical network can transport almost unlimited amounts of bandwidth.
However, optical networks face a fundamental restriction related to the geographical
extent of transmission: an optical signal becomes weaker as it gets farther from its
source, and therefore the distance over which an optical signal can be sent without
loss or errors is limited. To overcome this limitation, regenerating can be done with
some specific equipments (called regenerators) to allow the signal to be sent farther.
These regenerators are located in nodes of the network.
Network design models usually ignore the distance aspects and do not deal with
the placement of the regenerators. Since planners typically work in a hierarchical
fashion, Chen et al. (
2010
) suggested to address the
Regenerator Location Problem
(RLP) at the start of the network design phase, to ensure that regenerators are placed
at nodes of the network so that all nodes of the network may communicate without
worry of losses due to distances.
The problem can be formally defined as follows: given an undirected network
G
D
.V;E/, with a length d
e
associated to each edge e
2
E, and a maximum
distance d
max
that the signal can travel without being regenerated, find a minimum
cardinality subset of nodes L such that for every pair of nodes in V , there exists a
path between the nodes that contains no subpath of length
d
max
without at least
an internal node in L.
Chen et al. (
2010
) showed that the problem is NP-hard and suggested three
constructive heuristics and an improvement procedure. Furthermore, they showed
that RLP is equivalent to a Steiner arborescence problem with a unit degree
constraint. The transformation can be summarized as follow: a new directed graph
H
D
.N;A/ is created with two copies i
1
2
N
1
and i
2
2
N
2
for each node i
2
V ,
and a dummy root node r. The set of nodes in H is thus N
D
N
1
[
N
2
[f
r
g
.The
set of arcs is defined as A
D
A
1
[
A
2
[
A
r
where
for each i
2
V , there is an arc .i
1
;i
2
/
2
A
1
with cost c
i
1
i
2
D
1;
there is an arc .r;i
1
/
2
A
r
from the root to each node i
1
2
N
1
with cost c
ri
1
D
0;
A
2
is constructed by first applying the all pairs shortest path algorithm to graph
G. For edge
f
i;j
g2
E, if the shortest path between i and j has a length
d
max
,
then there are two arcs .i
2
;j
1
/;.j
2
;i
1
/
2
A
2
with costs c
i
2
j
1
D
c
j
2
i
1
D
0.
These correspond to nodes that can communicate directly without adding any
concentrator.
With this transformation, a Steiner arborescence, rooted at r, with unit degree
at the root node and that spans N
1
, has a cost equal to the number of internal
terminal nodes in the arborescence. It can be proved that these internal terminal
nodes correspond to a feasible set of regenerators for RLP, and that conversely, a
feasible Steiner arborescence of cost
j
L
j
can be built from a solution L of RLP.
