Information Technology Reference
In-Depth Information
Starting
Node (SN)
S
1
S
2
S
3
S
n
• • • •
P
1
P
2
P
3
P
n
T
1
T
2
T
3
T
n
Finishing
Node (FN)
Figure 5.3
An example of a super task-flow graph (STFG) consisting of
n
sensors.
5.4 An overview of Scheduling Algorithms
There are a number of algorithms for scheduling tasks, subject to a number of
different goals, such as the reduction in overall execution of the tasks, or the
utilization of minimal resources during the execution of the tasks. Here we
present two algorithms: ASAP and as ALAP to schedule all the tasks within
the WSN. These two algorithms are mainly employed to determine the earli-
est and latest boundaries within those tasks to be scheduled [7]. The objective
is to assign either the earliest state or latest state to a node taking into consid-
eration its predecessor or successor nodes.
In Figure 5.4, we illustrate the ASAP scheduling algorithm according to
Gajski et al. [7], where it assigns an ASAP label
F
i
to each node
v
i
of STFG,
thereby scheduling the starting execution of
v
i
with the earliest possible state
(time = 0). In lines 1-4, all nodes are initialized, and the function Pred
vi
deter-
mines all nodes, which are immediate predecessors of the node
v
i
. The vector
F
contains the earliest starting execution times for all nodes. In lines 5-9, all
the residual nodes, which have predecessor nodes, will be assigned starting
times for execution. In line 7, the function
all-nodes-scheduled
returns true if all
the nodes in set Pred
vi
are scheduled. In line 8, the function MAX determines
the node with the longest execution value (finishing execution time—starting
execution time) from the set of predecessor nodes for
v
i
.
