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
Search WWH ::




Custom Search