Information Technology Reference
In-Depth Information
other. Mathematically, the distinct representatives of
Ω
,
Ω
,
⋅⋅⋅
,
Ω
are
z
,
z
,
⋅⋅⋅
,
z
≤ ≤
and
j
≠
. An efficient polynomial-time
algorithm for finding distinct representatives is given in [26].
Our channel assignment method consists of three main steps and they are described in the
following.
Step 1. Transformation
Node
i
requires
z
∈Ω
and
z
≠
for all
1
in
where
i
i
i
j
N
≡
∑
≡
∑
N
channels to the hub and
channels from the hub,
c
d
r
d
i
ij
i
ji
j
=
1
j
=
1
i
rW
i
cW
⎡
⎤
⎡
⎤
so it requires
⎥
fibers to the hub and
⎥
fibers from the hub. Overall, the hub
⎢
⎢
has
incoming fibers and
outgoing fibers, so it has
∑
N
∑
N
∑
N
rW
rW
=
⎡
⎤
=
⎡
⎤
=
⎡
⎤
cW
⎢
⎥
⎢
⎥
⎢
⎥
i
i
j
i
1
i
1
j
1
passive combiners. We first transform
D
to a matrix
D
demultiplexers and
∑
N
⎡
cW
⎤
⎢
⎥
j
j
=
1
which specifies the number of channels required from every demultiplexer to every passive
combiner. This is done as follows: for all
1
≤ ≤
, if
iN
i
r
>
, we divide row
i
into
i
rW
i
rW
⎡
⎤
⎡
⎤
⎥
rows such that each of these
⎥
rows has a row sum of at most
W
and the
⎢
⎢
sum of the
j
th
element of these
i
rW
for all
1
≤≤
; for all
jN
⎡
⎤
d
⎥
rows is equal to
⎢
ij
1
≤≤
, if
jN
j
cW
>
, we divide column
j
into
⎥
columns such that each of these
⎡
j
cW
⎤
⎢
⎥
columns has a column sum of at most
W
and the sum of the
i
th
element of these
⎡
⎤
j
cW
⎢
∑
N
⎥
columns is equal to
d
for all
. Then we add dummy row(s) or
1
≤≤
i
⎡
r
W
⎤
⎡
⎤
j
cW
⎢
⎥
⎢
ij
k
k
=
1
column(s) to
D
such that the resulting
D
has
M
rows and
M
columns where
∑∑
, and add dummy values to some elements in
D
such
that all row sums and column sums are equal to
W
.
Step 2. Solving the Transformed Problem
For the
M
× matrix
D
with equal row sum and column sum, there exists
M
distinct
representatives such that each distinct representative appears in one distinct row and one
distinct column [26]. We apply this property to get a conflict-free channel assignment at each
distinct wavelength based on
D
. Specifically, we form
M
sets
Ω
,
Ω
,
⋅⋅⋅
,
Ω
where
Ω
contains the column numbers of the non-zero elements in row
i
of
D
, and execute the
distinct representatives algorithm [26] to determine
M
distinct representatives
N
N
M
=
max(
rW
,
⎡
c W
⎤
)
⎡
⎤
⎢
⎥
⎢
⎥
i
j
i
=
1
j
=
1
z
,
⋅⋅⋅
,
z
,
z
of these
M
sets. We use these distinct representatives to form a tentative conflict-free
M
λ
: assign a wavelength channel at
λ
to connect demultiplexer
i
to passive
assignment at
z
for all
1
≤≤
. We record this tentative assignment at
iM
λ
by the
assignment
combiner
i
d
′
by 1 for all
{
}
. Then we update
D
by deducting
set
Α=
(
)
(1,
z
),(2,
z
),
⋅⋅⋅
,(
Mz
,
)
1
1
2
M
i
1
≤≤
. The resulting
D
still has equal row sum and column sum. We repeat the above
iM