Information Technology Reference
In-Depth Information
the increased inefficiency of combining a queue
with its previous queue. Then, the queue with the
least increased inefficiency is selected to combine
with its previous queue. This is repeated until we
reach
M
d
queues.
For clarity, Figure 6(a)-(d) show the step-by-
step procedure of our algorithm. Suppose we have
five queues
q
1
to
q
5
with the number of packets
being 4, 1, 2, 3, and 2, respectively. Their maxi-
mum delays are
d
1
, d
2
, …, d
5
such that
d
i+1
-d
i
=1
(
i
=1, …, 4). We want to combine these 5 queues
into two while minimizing the inefficiency. As
shown in Figure 6(a), the increased inefficiency
η
's of combining only one queue with correspond-
ing preceding queue is calculated as +1, +2, +3,
+2. For instance, combining
q
4
into
q
3
results in
increased inefficiency of
η
43
=
N
4
(
d
4
-
d
3
)=3×1=3.
Comparing these
η
's, we select
q
2
to join
q
1
, as
shown in Figure 6(b). Then, the
η
's are calcu-
lated as +4, +3, +2. Note that the displacement of
the maximum delay from
q
3
to
q
1
is now
d
3
-d
1
=2.
So, the increased inefficiency of combing
q
3
to
q
1
can be computed as
η
31
=
N
3
(
d
3
-d
1
)=2×2=4. As
+2 is the minimum
η
,
q
5
is combined into
q
4
,
resulting in 3 queues
q
1
, q
3
and
q
4
, as depicted in
Figure 6(c). This iteration goes on until the desired
number of queues is reached. Note that in Figure
6 (c)
η
from the combined
q
4
to
q
3
is evaluated
as
N
4
(d
4
-d
3
)+N
5
(d
5
-d
3
)
=3×1+2×2=7, while
η
from
q
3
to the combined
q
1
is evaluated as
N
3
(d
3
-d
1
)
=2×2=4. In Figure 6(d),
η
from the
combined
q
4
to the combined
q
1
is evaluated as
N
4
(d
4
-d
1
)+N
5
(d
5
-d
1
)
= 3×3+4×2 =17.
At the beginning of each iteration,
χ
is used to
denote the ascending index set of the combined
queues such that
χ
i
represents the
minimum index
of the initial queues
for the
i
i-th combined queue,
i.e.,
χ
i
=min{
j
|
q
j
is combined into the
i
i-th combined
queue}. The
i
i-th combined queue has the maxi-
mum delay as
q
χi
, i.e.,
d
χi
. As our algorithm
merges neighboring queues, this
i
i-th combined
queue contains
q
j
such that
χ
i
≤
j
<
χ
i+1
. Specifi-
cally, at each iteration, the increased inefficiency
to combine queues specified by
χ
i+1
to
χ
i
can be
formulated as,
∑
η
ˆ
=
N d
(
−
d
i
).
(
i
+
1
)
i
k
k
χ
χ
≤ <
k
χ
i
i
1
+
The EDF scheduler merges the neighboring
queues specified by
χ
i
*
and
χ
i
*
+
1
such that
i
*
=
arg min
η
ˆ
,
1
≤ <
i size
( )
χ
(
i
+
1
)
i
where
size(χ)
is the number of elements in set
χ
,
which is updated by removing
χ
i*+1
. The algorithm
then iterates on the new
χ
until the desired num-
ber of combined queues is reached, as shown in
Algorithm 2. The complexity of this algorithm
is
O
(
(M-M
d
)M
).
PERFORMANCE EVALUATION
To evaluate the whole solution presented in Sect.
4, we implemented the protocols on TinyOS and
loaded them into the IMote2/TelosB sensors and
tested in our testbed.
Algorithm 2. Merge M queues to M
d
queues
(M<M
d
)
Initialization:
χ={1,2,…,
M
},
d
1
<d
2
<…<d
M
for
j=M
to
M
d
+
1
do
//Find the combined queue with minimum increased
inefficiency
ˆ
mi
η
= +∞
;
i
χimin+1
=
0
for
i
=1 to
size
(χ) -1
do
ˆ
∑
η
=
N d
(
−
d
i
)
i
k
k
χ
χ
≤ <
+
k
χ
1
i
i
if
ˆ
η
>
η
ˆ
i
then
χimin+1
η
ˆ
=
η
ˆ
i
;
i i
χimin+1
=
χimin+1
end if
end for
//Merge neighboring queues
Remove
χ
i
χimin+1
+
1
from χ
end for
Search WWH ::
Custom Search