Information Technology Reference
In-Depth Information
Hence, in order to handle the heterogeneous
data, we build an EDF scheduler with
N
queues
where
N
is the number of the flows. However,
when
N
is large, the complexity
O
(log
N
) is large,
which may not be too much of improvement with
respect to the case in which the sorting operation
is per packet (e.g., if
N
is not much smaller than
k
). On the other hand, if we reduce the number
of queues to have a lower complexity, a packet
with tolerable queuing delay
D
may be placed in a
queue with a smaller queuing delay (<
D
), which
introduces certain 'bandwidth inefficiency' result-
ing from assigning packets with higher tolerable
delays to queues with small delays.
Considering the limited processing capability
of the sensors, it is necessary to find a solution so
that each sensor maintains an appropriate number
of queues by trading off admissible complexity
and 'bandwidth inefficiency'. To be more specific,
we define
bandwidth inefficiency
as follows.
Definition 2.
Assume that there is a set of
queues
Q
={
q
1
, q
2
, …, q
K
} in some node with
maximum delays
D
={
d
1
, d
2
, …, d
K
}, respectively,
such that
d
1
<d
2
<…<d
K
. If we consider
d
K+1
=∞, the
bandwidth inefficiency (or simply inefficiency)
with EDF scheduling for this node is
ξ
may be served at a time that
ξ'
expires. Hence,
it is the right choice to put
ξ
in
q
i
. The
maximum
tolerable delay at current node
is estimated by
dividing the remaining alive time by
N
sink
·
N
tx
(as
introduced in Sect. 4.1).
Our EDF scheduling scheme works by measur-
ing the traffic queuing delay and adaptively ad-
justing to the observed variations. Suppose that
during one measured period the observed mini-
mum packet delay is
d
mini-
and the maximum
packet delay
d
max
. The delay between
d
mini-
and
d
max
is divided into
M-1
intervals (
M
> 2) with the end
points being
d
i
=d
mini-
+(
i-1
)(
d
max
-d
mini-
)
/
(
M-1
) for
i=1,2,…, M
. These end points correspond to the
maximum delays of
M
queues
q
1
, q
2
, …, q
M
. A
packet
ξ
is put into
q
i
if its maximum tolerable
delay at this node
d
r
ξ
( )
r
1
.
Suppose that during this observation period, the
numbers of packets within these queues are
N
1
,
N
2
, …, N
M
, respectively. Starting from these
M
queues, an iterative procedure is executed to reduce
the number of queues from
M
to the desired
number
M
d
by combining these queues. Our goal
here is to
minimize the bandwidth inefficiency
while maintaining the desired number of queues
.
Within each iteration, a queue is combined into
another with minimum inefficiency, resulting in
M-M
d
iterations.
As IEEE 802.15.4 has only one bit rate of 250
kbps,
R
ξ
's are all the same. Hence, we can remove
R
ξ
from (4). Moreover, the relative inefficiency
of the packet within a queue is fixed when this
queue is combined into another queue. Therefore,
we can ignore this inefficiency within the queue
and estimate the relative inefficiency between the
queues when we combine the queues with mini-
mized inefficiency. To be more exact, suppose
q
j
(with
N
j
packets and maximum delay
d
j
) is com-
bined into
q
i
(with maximum delay
d
i
and
d
i
< d
j
),
then the
increased inefficiency
for this combina-
tion is defined as
ˆ
( )
satisfies
d
<
d
<
d
i
ξ
i
+
K
∑
∑
( )
r
η
=
R d
⋅
(
−
d
),
(4)
ξ
ξ
i
i
=
1
( )
r
ξ
∈
Ω
,
d
≤
d
<
d
i
ξ
i
+
1
where Ω is the set of packets in these queues,
d
r
ξ
( )
is packet
ξ
's remaining maximum tolerable delay
at current node, and
R
ξ
is the bit rate for sending
ξ
.
Note that the reason for subtracting
d
i
from
d
r
ξ
( )
in (4) is due to the fact of putting
ξ
into
q
i
.
As
d
( )
<
+
1
,
ξ
may expire if it is put into queue
q
j
with
j>i
. On the other hand, if
ξ
is put in
q
j
with
j<i
, then it may increase the risk of other packet's
expiration. For example, packet
ξ'
arrives after
ξ
with
d
r
d
ξ
i
= × − .
The basic idea of our algorithm is as follows:
starting from the current set of queues, we calculate
η
ji
N
(
d
d
)
j
j
i
( ) (
< . Yet,
ξ
must be served before
ξ'
,
causing possible deadline expiration for
ξ'
since
r
d
r
ξ
'
ξ
Search WWH ::
Custom Search