# An Improved Task Scheduling Algorithm for Intelligent Control in Tiny Mechanical System

Authors: Jialiang Wang; Hai Zhao; Yuanguo Bi; Xingchi Chen; Ruofan Zeng; Yu Wang
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

Wireless sensor network (WSN) has been already widely used in many fields in terms of industry, agriculture, and military, and so forth. The basic composition is WSN nodes that are capable of performing processing, gathering information, and communicating with other connected nodes in the network. The main components of a WSN node are microcontroller, transceiver, and some sensors. Undoubtedly, it also can be added with some actuators to form a tiny mechanical system. Under this case, the existence of task preemption while executing operating system will not only cost more energy for WSN nodes themselves, but also bring unacceptable system states caused by vibrations. However for these nodes, task I/O delays are inevitable due to the existence of task preemption, which will bring extra overhead for the whole system, and even bring unacceptable system states caused by vibrations. This paper mainly considers the earliest deadline first (EDF) task preemption algorithm executed in WSN OS and proposes an improved task preemption algorithm so as to lower the preemption overhead and I/O delay and then improve the system performance. The experimental results show that the improved task preemption algorithm can reduce the I/O delay effectively, so the real-time processing ability of the system is enhanced.


---

## Body

## 1. Introduction

WSN consists of spatially distributed autonomous sensors to monitor physical or environmental conditions, such as temperature, sound, and pressure. These WSN nodes cooperatively pass their data through the network to a main location. Energy issue and system performance of WSN have always been considered because WSN nodes always work in some harsh environment. Energy is the scarcest resource for WSN nodes, and it finally determines the lifetime of WSNs. Energy consumption of the sensor nodes should be minimized since their limited energy resource determines their lifetime [1]. For the WSN OS used in some practical application of connecting some actuators, the task preemption will inevitably bring I/O delay and even unacceptable system states caused by the vibrations [2]. Nowadays, while WSN nodes formed a tiny mechanical system by adding actuators, how to decrease the system extra overhead and improve the system performance caused by the vibrations becomes very important.Currently, there are many researches about improving system performance for WSN nodes; for example, [3] used error and kernel density approach of sleeping nodes in cluster-based WSNs; [4] used low energy online self-test of embedded processor in dependable WSN nodes. Reference [5] studied low-energy symmetric key distribution in WSN; [6] used a dynamic programming approach for QoS-aware power management in wireless video sensor. Reference [7] used virtual backbone scheduling to maximize the lifetime of WSNs. Reference [8] used hybrid-storage units to extend runtime of low-power WSN nodes. Reference [9] studied distributed tracking with energy management in wireless sensor networks. Reference [10] used joint routing and sleep scheduling to maximize lifetime of WSN. Thus it can be seen that most solutions are implemented by the way of utilizing extra resources. But the innovation for this paper is to improve the lifetime of WSN nodes in terms of real-time operating system itself and the task scheduling algorithm to be exact. The decrease of system overhead and the improvement of system performance are implemented by reducing the overhead of task preemptions. The most important is that this method can be combined with all of the others to achieve better system performance in tiny mechanical system composed of WSN nodes, as this improvement is focused on the real-time operating system itself.


## 2. EDF Task Scheduling Analysis

Compared with fixed priority task scheduling algorithm, dynamic priority algorithm allocates different priorities to every period task, so the task priority is constantly changing. EDF task scheduling algorithm has already been widely used as a classic dynamic priority scheduling algorithm in WSN [11].EDF task scheduling algorithm assigns tasks with different priority according to execution deadline of task, the earlier task execution deadline, and the higher task priority. In a word, system allocates the highest priority to task having the earliest task execution.


### 2.1. Judging Whether the System Is Schedulable

Supposing that system hasn independent and preemptive period tasks τ
i (1
≤
i
≤
n). E
i, D
i, and T
i represent the execution time, relative deadline, and period of task τ
i, respectively. The sufficient condition for EDF task scheduling algorithm in single processor is given by
(1)
∑
i
=
1
n
E
i
min
⁡
(
D
i
,
T
i
)
≤
1
.While taskτ
i (1
≤
i
≤
n) has max block time b
i, the above sufficient condition will be expressed as
(2)
∑
i
=
1
n
E
i
+
b
i
min
⁡
(
D
i
,
T
i
)
≤
1
.If this formula can be met for all tasks, the system is regarded as schedulable. The all below discussions are all based on formula (2).


### 2.2. Task Preemption Optimization about EDF Task Scheduling Algorithm

Use the attribute set(
T
i
,
E
i
) to describe a period task, where T
i is the period of task and E
i is the execution time of the task, while using J
m
,
n to describe one specific job in a task, which means that the task m has n jobs totally. For example, supposing that there are three jobs in the task T
1, the first one is J
1,1, the second one is J
1,2, and the last one is J
1,3.Suppose that there are three period tasksT
1(2, 0.8), T
2(3, 0.4), and T
3(5, 2.1) in the single processor system. For these three tasks, their super period is 30.As Figure1(a) shows, task T
1, T
2, and T
3 are all released at time 0, but their execution deadline is 2, 3, and 5, so task T
1 has the highest priority and it begins to run firstly. At time 0.8, task T
2 begins to run as it has higher priority than task T
3. Till time 1.2, task T
3 begins to run. While at time 2, task T
1 is released again, task T
3 is preempted by task T
1 then. Figure 1(a) shows the whole execution case before optimization for these three tasks during the time period [
0,10
].Execution case of EDF task scheduling before and after optimization.
(a)
(b)Figure1(a) shows that the beginning time for jobs on task T
1, T
2, and T
3 is {
0
,
2
,
4.5
,
6
,
8
}, {
0.8
,
3
,
6.8
,
9.4
}, and {
1.2
,
2.8
,
3.4
,
5.3
,
7.2
,
8.8
}, respectively. We can see from the results that the jobs of task T
3 are preempted 4 times totally, and each time point of preemption is shown as in Figure 1(a).Figure1(b) shows the execution case after optimization during the time period [
0,10
]; the beginning time for jobs of tasks T
1, T
2, and T
3 becomes {
0
,
2.2
,
4.5
,
6
,
8.6
}, {
0.8
,
3
,
6.8
,
9.4
}, and {
1.2
,
3.4
,
5.3
,
7.2
}, respectively. Under this case, task T
3 is preempted 2 times totally, and in the meanwhile, task T
1 and T
2 do not exceed their deadline. This is implemented by postponing the execution of some jobs for task T
1 and T
2, which means that nonpreemptive scopes are added for some jobs in task T
3, and the below discussion will describe the process of implementation in detail.


### 2.3. Extra Overhead Caused by Task Preemption

Pree
i
,
u is a task preemptive set, which describes that task τ
i is executed u times totally. The number of elements for Pree
i
,
u is signed as w
i
,
u, which means the times that task τ
i is preempted totally, so the total amount for all these tasks are given by
(3)
N
pree
(
I
,
t
)
=
∑
i
=
1
n
-
1
∑
u
=
0
⌈
t
/
T
i
⌉
-
1
w
i
,
u
.If a low priority task is preempted by another one, then the extra cost for the preemption isC
pree. While there is no preemption exists and then the extra cost is C
nonpree, for any task, no matter whether it is preempted, the total extra cost for the system is C
pree
-
C
nonpree [11].If the phase position isI for the real-time task set τ
0
,
…
,
τ
n
-
1, the extra overhead caused by task preemption during the time period [
0
,
t
] is described as
(4)
O
preempt
(
I
,
t
)
=
∑
i
=
1
n
-
1
∑
u
=
0
⌈
t
/
T
i
⌉
-
1
w
i
,
u
·
(
C
pree
-
C
nonpree
)
.So we can know that the task preemption will bring extra overhead for the whole system. As saving energy is very important for WSN nodes that formed a tiny mechanism system, how to reduce the task preemption becomes very necessary.


## 2.1. Judging Whether the System Is Schedulable

Supposing that system hasn independent and preemptive period tasks τ
i (1
≤
i
≤
n). E
i, D
i, and T
i represent the execution time, relative deadline, and period of task τ
i, respectively. The sufficient condition for EDF task scheduling algorithm in single processor is given by
(1)
∑
i
=
1
n
E
i
min
⁡
(
D
i
,
T
i
)
≤
1
.While taskτ
i (1
≤
i
≤
n) has max block time b
i, the above sufficient condition will be expressed as
(2)
∑
i
=
1
n
E
i
+
b
i
min
⁡
(
D
i
,
T
i
)
≤
1
.If this formula can be met for all tasks, the system is regarded as schedulable. The all below discussions are all based on formula (2).


## 2.2. Task Preemption Optimization about EDF Task Scheduling Algorithm

Use the attribute set(
T
i
,
E
i
) to describe a period task, where T
i is the period of task and E
i is the execution time of the task, while using J
m
,
n to describe one specific job in a task, which means that the task m has n jobs totally. For example, supposing that there are three jobs in the task T
1, the first one is J
1,1, the second one is J
1,2, and the last one is J
1,3.Suppose that there are three period tasksT
1(2, 0.8), T
2(3, 0.4), and T
3(5, 2.1) in the single processor system. For these three tasks, their super period is 30.As Figure1(a) shows, task T
1, T
2, and T
3 are all released at time 0, but their execution deadline is 2, 3, and 5, so task T
1 has the highest priority and it begins to run firstly. At time 0.8, task T
2 begins to run as it has higher priority than task T
3. Till time 1.2, task T
3 begins to run. While at time 2, task T
1 is released again, task T
3 is preempted by task T
1 then. Figure 1(a) shows the whole execution case before optimization for these three tasks during the time period [
0,10
].Execution case of EDF task scheduling before and after optimization.
(a)
(b)Figure1(a) shows that the beginning time for jobs on task T
1, T
2, and T
3 is {
0
,
2
,
4.5
,
6
,
8
}, {
0.8
,
3
,
6.8
,
9.4
}, and {
1.2
,
2.8
,
3.4
,
5.3
,
7.2
,
8.8
}, respectively. We can see from the results that the jobs of task T
3 are preempted 4 times totally, and each time point of preemption is shown as in Figure 1(a).Figure1(b) shows the execution case after optimization during the time period [
0,10
]; the beginning time for jobs of tasks T
1, T
2, and T
3 becomes {
0
,
2.2
,
4.5
,
6
,
8.6
}, {
0.8
,
3
,
6.8
,
9.4
}, and {
1.2
,
3.4
,
5.3
,
7.2
}, respectively. Under this case, task T
3 is preempted 2 times totally, and in the meanwhile, task T
1 and T
2 do not exceed their deadline. This is implemented by postponing the execution of some jobs for task T
1 and T
2, which means that nonpreemptive scopes are added for some jobs in task T
3, and the below discussion will describe the process of implementation in detail.


## 2.3. Extra Overhead Caused by Task Preemption

Pree
i
,
u is a task preemptive set, which describes that task τ
i is executed u times totally. The number of elements for Pree
i
,
u is signed as w
i
,
u, which means the times that task τ
i is preempted totally, so the total amount for all these tasks are given by
(3)
N
pree
(
I
,
t
)
=
∑
i
=
1
n
-
1
∑
u
=
0
⌈
t
/
T
i
⌉
-
1
w
i
,
u
.If a low priority task is preempted by another one, then the extra cost for the preemption isC
pree. While there is no preemption exists and then the extra cost is C
nonpree, for any task, no matter whether it is preempted, the total extra cost for the system is C
pree
-
C
nonpree [11].If the phase position isI for the real-time task set τ
0
,
…
,
τ
n
-
1, the extra overhead caused by task preemption during the time period [
0
,
t
] is described as
(4)
O
preempt
(
I
,
t
)
=
∑
i
=
1
n
-
1
∑
u
=
0
⌈
t
/
T
i
⌉
-
1
w
i
,
u
·
(
C
pree
-
C
nonpree
)
.So we can know that the task preemption will bring extra overhead for the whole system. As saving energy is very important for WSN nodes that formed a tiny mechanism system, how to reduce the task preemption becomes very necessary.


## 3. Analysis of I/O Delay for EDF Task Scheduling

For the release time of all jobs in setS, there exists a max I/O delay for certain job [11, 12].


### 3.1. Analysis of I/O Delay Caused by Task Preemption

Supposing that allocated preemptive thresholdPT
i equals E
i and ignoring the restrain of preemptive threshold time, then according to the analysis of time requirement, the max I/O delay for preemptive task scheduling of τ
i is given by
(5)
I
O
L
i
(
a
)
=
max
⁡
{
E
i
,
L
i
(
a
)
-
a
}
,
where a is the release time of job; then, L
i
(
a
) can be calculated by
(6)
L
i
(
0
)
(
a
)
=
0
,
L
i
(
m
+
1
)
(
a
)
=
W
i
(
a
,
L
i
(
m
)
(
a
)
)
+
(
1
+
⌊
a
T
i
⌋
)
C
i
.WhileL
i
(
m
+
1
)
(
a
)
=
L
i
(
m
)
(
a
), the above iterative calculation will end.For taskτ
i, while the release time of its one job is a, the job load of higher priority can be represented as
(7)
W
i
(
a
,
t
)
=
∑
j
≠
i
D
j
≤
a
+
D
i
min
⁡
{
⌈
t
T
j
⌉
,
1
+
⌊
a
+
D
i
-
D
j
T
j
⌋
}
·
E
j
.A preemptive thresholdPT
i (0
≤
PT
i
≤
E
i) is assigned to task τ
i, and the I/O delay should be calculated by the preemptive part and nonpreemptive part, respectively, as below [11].The max I/O delay of preemptive part for taskτ
i is given by
(8)
I
O
L
i
pree
(
a
)
=
max
⁡
{
P
T
i
,
L
i
pree
(
a
)
-
a
}
i
=
1
,
2
,
…
,
n
;
(9)
L
i
pree
(
a
)
=
W
i
(
a
,
L
i
pree
(
a
)
)
+
⌊
a
T
i
⌋
·
E
i
+
PT
i
+
max
⁡
D
j
>
D
i
(
E
j
-
PT
j
)
,
where L
i
pree
(
a
) is the max value of formula (9), and it can be calculated by the initialization value L
i
pree
(
0
)
=
0.The max I/O delay of nonpreemptive part for taskτ
i is represented as
(10)
I
O
L
i
nonp
=
(
E
i
-
PT
i
)
i
=
1
,
2
,
…
,
n
;so the max I/O delay for taskτ
i based on EDF scheduling algorithm is described as
(11)
I
O
L
i
max
⁡
=
I
O
L
i
pree
(
a
)
+
I
O
L
i
nonp
=
max
⁡
{
P
T
i
,
L
i
pree
(
a
)
-
a
}
+
(
E
i
-
P
T
i
)
c
c
c
c
c
c
c
c
c
c
c
c
c
c
c
c
c
c
c
c
c
c
i
=
1,2
,
…
,
n
.WhileP
T
i
≥
L
i
pree
(
a
)
-
a, then
(12)
I
O
L
i
max
⁡
=
P
T
i
+
(
E
i
-
P
T
i
)
=
E
i
.Under this case, the I/O delay is a constant value, and it is irrelevant to task attribute.WhileP
T
i
<
L
i
pree
(
a
)
-
a,
(13)
I
O
L
i
max
⁡
=
I
O
L
i
pree
(
a
)
+
I
O
L
i
nonp
=
L
i
pree
(
a
)
-
a
+
(
E
i
-
P
T
i
)
=
W
i
(
a
,
L
i
pree
(
a
)
)
+
⌊
a
T
i
⌋
·
E
i
+
P
T
i
+
max
⁡
D
j
>
D
i
(
E
j
-
PT
j
)
-
a
+
(
E
i
-
PT
i
)
=
W
i
(
a
,
L
i
pree
(
a
)
)
+
(
1
+
⌊
a
T
i
⌋
)
·
E
i
+
max
⁡
D
j
>
D
i
(
E
j
-
PT
j
)
-
a
.From the above formulas, we can know thatPT
i is the main factor for I
O
L
i
max
⁡, and the next section will describe how to assign PT
i for jobs.


### 3.2. Improved Task Preemption Scheduling Algorithm

In the EDF task scheduling algorithm, task is indexed by the relative time slice. For taskτ
i, the bigger the index, the bigger relative time slice. So only the task with big relative time slice can block the task with smaller one and the time requirement of preemptive part for task τ
i having below restriction of preemptive time threshold [11]. Consider
(14)
w
i
pree
(
a
,
P
T
1
,
P
T
2
,
…
,
P
T
n
)
=
W
i
(
a
,
L
i
pree
(
a
)
)
+
⌊
a
T
i
⌋
E
i
+
P
T
i
+
b
i
,
b
i
=
max
⁡
D
j
>
D
i
(
P
T
j
)
.The max execution time of nonpreemptive part isE
j
-
P
T
j for task τ
i, so the necessary condition that task can be schedulable is there is existing a  (
a
∈
S
), which meets the below formula:
(15)
w
i
pree
[
a
,
P
T
1
,
P
T
2
,
…
,
P
T
n
]
+
E
i
-
P
T
i
≤
a
+
D
iasS is the detecting set, and it is given by
(16)
S
=
⋃
p
=
1
n
S
p
,
S
p
=
{
⌈
D
p
T
p
⌉
D
p
+
k
T
p
-
D
i
,
k
∈
N
,
c
c
v
⌈
D
i
-
D
p
T
p
⌉
≤
k
<
⌈
L
+
D
i
-
D
p
T
p
⌉
}
,
where a
∈
S, and it meets the following formula:
(17)
max
⁡
j
=
i
+
1
n
(
E
j
-
P
T
j
)
≤
a
+
D
i
-
W
i
(
a
,
L
i
pree
(
a
)
)
+
⌊
a
T
i
⌋
E
i
+
P
T
i
+
b
i
,
b
i
=
max
⁡
D
j
>
D
i
(
E
j
-
P
T
j
)
.The necessary and sufficient condition for EDF task scheduling is described as(18)
∑
h
=
1
n
E
h
+
b
i
min
⁡
(
D
h
,
T
h
)
≤
1
,
b
i
=
max
⁡
D
j
>
D
i
(
E
j
-
P
T
j
)
.Thenb
i can be calculated by
(19)
b
i
≤
min
⁡
(
D
i
,
T
i
)
(
1
-
∑
h
=
1
n
E
h
min
⁡
⁡
(
D
h
,
T
h
)
)
.To make the taskτ
i schedulable, the min value of P
T
i
+
1 is given by
(20)
P
T
i
+
1
min
⁡
=
E
i
+
1
-
min
⁡
(
D
i
,
T
i
)
·
(
1
-
∑
h
=
1
n
E
h
min
⁡
⁡
(
D
h
,
T
h
)
)
.
So to make all tasks schedulable, the min value of PT
i
+
1 is represented as
(21)
P
T
i
+
1
min
⁡
*
=
max
⁡
j
=
1
i
(
P
T
j
+
1
min
⁡
)
.From the above analyses, system allocates theP
T
1
=
P
T
1
min
⁡
*
=
E
1 to the task τ
1 that has the smallest relative deadline. The PT value of other jobs will also be allocated by formula (21).The system obtains block timeb
i for every task and calculates threshold of tasks whose relative time slices are larger than P
T
j according to b
i and then allocates threshold to task i
=
2,3
,
…
,
n by Algorithm 1.Algorithm 1
(1) Input:n
,
T
i
,
E
i
,
D
i
(
i
=
1
,
2
,
…
,
n
);
(2)PT
1
min
⁡
* = E
1, and allocating preemptive threshold P
T
1
=
E
1 to task τ
1.
(3) Initializingi
=
1;
(4) Calculatingb
i
* by formula (19);
(5) Assigningb
i
+
1
*
,
b
i
+
2
*
,
…
,
b
n
* to b
i
* separately;
(6)i
=
i
+
1, returning to Step (4) till all b
i
* are calculated.
(7)for
i
=
1
,
2
,
…
,
n,
(8) Obtaining all preemptive time threshold by formula (20) and (21).
(9)endfor
(10)for tasks τ
i
(
i
=
1
,
2
,
…
,
n
)
(11) Calculating maxI
/
O delay I
O
L
i
max
⁡, and min I
/
O delay min I
/
O delay.
(12)endfor
(13) Output:P
T
1
,
P
T
2
,
…
,
P
T
n
,
I
O
L
i
max
⁡  and I
O
L
i
min
⁡.Algorithm1 implements an optimization allocation of preemptive time threshold for each job. From the above formula (18) and (19), we can know that the time complexity of this algorithm is O
(
n
).TID
=
{
ti
d
1
,
ti
d
2
,
…
,
ti
d
N
} which corresponds to task release time. If several tasks are released at the same time, then the system uses the task TID having the highest priority.At any given timet, s
i
(
t
)
=
t
-
∑
k
=
1
i
⌈
(
t
-
φ
k
)
/
T
k
⌉
·
E
k is used to express the time difference between system supplying and finishing the all jobs whose priority is no less than job i during time period [
0
,
t
).For any one task set based on EDF task scheduling algorithm, system can calculate the amount of task preemption by task attribute during the time period[
0
,
γ
] according to Algorithm 2.Algorithm 2
(1) Input:n
,
β
,
T
i
,
E
i
,
φ
i
(
i
=
1
,
2
,
…
,
n
);
(2) Initializingξ
i
=
0; p
r
e
e
i
(
β
)
=
0
,
(
i
=
1
,
2
,
…
,
n
)
;
p
r
e
e
(
β
)
=
0;
(3) Constructing TID ={
t
i
d
1
,
t
i
d
2
,
…
,
t
i
d
N
} and Set S
(
r
)
=
{
r
1
,
r
2
,
…
,
r
N
};  // N
≤
∑
i
=
1
n
⌊
τ
-
φ
i
T
i
⌋
+
n
(4)for
k
=
1 to N;
(5) Detecting release time of all tasks;
(6)t
=
r
k;  m
=
t
i
d
k;
(7)if
s
m
(
t
)
-
s
m
(
ξ
m
)
≤
0
then
(8) Ending this loop, and detecting next release time;
(9)endif
(10)if
s
n
(
t
)
-
s
n
(
ξ
n
)
>
0 then
(11) Refreshingξ
i
=
t
(
i
=
m
,
m
+
1
,
…
,
n
);
(12) Ending this loop, and detecting next release time;
(13)endif
(14) System finds the indexλ
=
i in m
+
1
,
m
+
2
,
…
,
n, and makes s
i
-
1
(
t
)
-
s
i
-
1
(
ξ
i
-
1
)
>
0 and
s
i
(
t
)
-
s
i
(
ξ
i
)
≤
0;
(15)if s
λ
(
t
)
-
s
λ
(
ξ
λ
)
≠
0
then
(16)p
r
e
e
λ
(
β
)
=
p
r
e
e
λ
(
β
)
+
1;
(17)endif
(18) Refreshingξ
i
=
t
(
i
=
m
,
m
+
1
,
…
,
λ
-
1
);
(19)endfor
(20) Output:p
r
e
e
i
(
β
)
,
(
i
=
1
,
2
,
…
,
n
);  the amount of task i is preempted
p
r
e
e
(
β
)
=
∑
i
=
1
n
p
r
e
e
i
(
β
);  the amount of all preemptionsThe above algorithms describe the implementation of postponing the execution of some jobs for some tasks; at the meanwhile, nonpreemptive scope is added for some jobs in others tasks, and the below discussion will describe the experiments about the performance test.


## 3.1. Analysis of I/O Delay Caused by Task Preemption

Supposing that allocated preemptive thresholdPT
i equals E
i and ignoring the restrain of preemptive threshold time, then according to the analysis of time requirement, the max I/O delay for preemptive task scheduling of τ
i is given by
(5)
I
O
L
i
(
a
)
=
max
⁡
{
E
i
,
L
i
(
a
)
-
a
}
,
where a is the release time of job; then, L
i
(
a
) can be calculated by
(6)
L
i
(
0
)
(
a
)
=
0
,
L
i
(
m
+
1
)
(
a
)
=
W
i
(
a
,
L
i
(
m
)
(
a
)
)
+
(
1
+
⌊
a
T
i
⌋
)
C
i
.WhileL
i
(
m
+
1
)
(
a
)
=
L
i
(
m
)
(
a
), the above iterative calculation will end.For taskτ
i, while the release time of its one job is a, the job load of higher priority can be represented as
(7)
W
i
(
a
,
t
)
=
∑
j
≠
i
D
j
≤
a
+
D
i
min
⁡
{
⌈
t
T
j
⌉
,
1
+
⌊
a
+
D
i
-
D
j
T
j
⌋
}
·
E
j
.A preemptive thresholdPT
i (0
≤
PT
i
≤
E
i) is assigned to task τ
i, and the I/O delay should be calculated by the preemptive part and nonpreemptive part, respectively, as below [11].The max I/O delay of preemptive part for taskτ
i is given by
(8)
I
O
L
i
pree
(
a
)
=
max
⁡
{
P
T
i
,
L
i
pree
(
a
)
-
a
}
i
=
1
,
2
,
…
,
n
;
(9)
L
i
pree
(
a
)
=
W
i
(
a
,
L
i
pree
(
a
)
)
+
⌊
a
T
i
⌋
·
E
i
+
PT
i
+
max
⁡
D
j
>
D
i
(
E
j
-
PT
j
)
,
where L
i
pree
(
a
) is the max value of formula (9), and it can be calculated by the initialization value L
i
pree
(
0
)
=
0.The max I/O delay of nonpreemptive part for taskτ
i is represented as
(10)
I
O
L
i
nonp
=
(
E
i
-
PT
i
)
i
=
1
,
2
,
…
,
n
;so the max I/O delay for taskτ
i based on EDF scheduling algorithm is described as
(11)
I
O
L
i
max
⁡
=
I
O
L
i
pree
(
a
)
+
I
O
L
i
nonp
=
max
⁡
{
P
T
i
,
L
i
pree
(
a
)
-
a
}
+
(
E
i
-
P
T
i
)
c
c
c
c
c
c
c
c
c
c
c
c
c
c
c
c
c
c
c
c
c
c
i
=
1,2
,
…
,
n
.WhileP
T
i
≥
L
i
pree
(
a
)
-
a, then
(12)
I
O
L
i
max
⁡
=
P
T
i
+
(
E
i
-
P
T
i
)
=
E
i
.Under this case, the I/O delay is a constant value, and it is irrelevant to task attribute.WhileP
T
i
<
L
i
pree
(
a
)
-
a,
(13)
I
O
L
i
max
⁡
=
I
O
L
i
pree
(
a
)
+
I
O
L
i
nonp
=
L
i
pree
(
a
)
-
a
+
(
E
i
-
P
T
i
)
=
W
i
(
a
,
L
i
pree
(
a
)
)
+
⌊
a
T
i
⌋
·
E
i
+
P
T
i
+
max
⁡
D
j
>
D
i
(
E
j
-
PT
j
)
-
a
+
(
E
i
-
PT
i
)
=
W
i
(
a
,
L
i
pree
(
a
)
)
+
(
1
+
⌊
a
T
i
⌋
)
·
E
i
+
max
⁡
D
j
>
D
i
(
E
j
-
PT
j
)
-
a
.From the above formulas, we can know thatPT
i is the main factor for I
O
L
i
max
⁡, and the next section will describe how to assign PT
i for jobs.


## 3.2. Improved Task Preemption Scheduling Algorithm

In the EDF task scheduling algorithm, task is indexed by the relative time slice. For taskτ
i, the bigger the index, the bigger relative time slice. So only the task with big relative time slice can block the task with smaller one and the time requirement of preemptive part for task τ
i having below restriction of preemptive time threshold [11]. Consider
(14)
w
i
pree
(
a
,
P
T
1
,
P
T
2
,
…
,
P
T
n
)
=
W
i
(
a
,
L
i
pree
(
a
)
)
+
⌊
a
T
i
⌋
E
i
+
P
T
i
+
b
i
,
b
i
=
max
⁡
D
j
>
D
i
(
P
T
j
)
.The max execution time of nonpreemptive part isE
j
-
P
T
j for task τ
i, so the necessary condition that task can be schedulable is there is existing a  (
a
∈
S
), which meets the below formula:
(15)
w
i
pree
[
a
,
P
T
1
,
P
T
2
,
…
,
P
T
n
]
+
E
i
-
P
T
i
≤
a
+
D
iasS is the detecting set, and it is given by
(16)
S
=
⋃
p
=
1
n
S
p
,
S
p
=
{
⌈
D
p
T
p
⌉
D
p
+
k
T
p
-
D
i
,
k
∈
N
,
c
c
v
⌈
D
i
-
D
p
T
p
⌉
≤
k
<
⌈
L
+
D
i
-
D
p
T
p
⌉
}
,
where a
∈
S, and it meets the following formula:
(17)
max
⁡
j
=
i
+
1
n
(
E
j
-
P
T
j
)
≤
a
+
D
i
-
W
i
(
a
,
L
i
pree
(
a
)
)
+
⌊
a
T
i
⌋
E
i
+
P
T
i
+
b
i
,
b
i
=
max
⁡
D
j
>
D
i
(
E
j
-
P
T
j
)
.The necessary and sufficient condition for EDF task scheduling is described as(18)
∑
h
=
1
n
E
h
+
b
i
min
⁡
(
D
h
,
T
h
)
≤
1
,
b
i
=
max
⁡
D
j
>
D
i
(
E
j
-
P
T
j
)
.Thenb
i can be calculated by
(19)
b
i
≤
min
⁡
(
D
i
,
T
i
)
(
1
-
∑
h
=
1
n
E
h
min
⁡
⁡
(
D
h
,
T
h
)
)
.To make the taskτ
i schedulable, the min value of P
T
i
+
1 is given by
(20)
P
T
i
+
1
min
⁡
=
E
i
+
1
-
min
⁡
(
D
i
,
T
i
)
·
(
1
-
∑
h
=
1
n
E
h
min
⁡
⁡
(
D
h
,
T
h
)
)
.
So to make all tasks schedulable, the min value of PT
i
+
1 is represented as
(21)
P
T
i
+
1
min
⁡
*
=
max
⁡
j
=
1
i
(
P
T
j
+
1
min
⁡
)
.From the above analyses, system allocates theP
T
1
=
P
T
1
min
⁡
*
=
E
1 to the task τ
1 that has the smallest relative deadline. The PT value of other jobs will also be allocated by formula (21).The system obtains block timeb
i for every task and calculates threshold of tasks whose relative time slices are larger than P
T
j according to b
i and then allocates threshold to task i
=
2,3
,
…
,
n by Algorithm 1.Algorithm 1
(1) Input:n
,
T
i
,
E
i
,
D
i
(
i
=
1
,
2
,
…
,
n
);
(2)PT
1
min
⁡
* = E
1, and allocating preemptive threshold P
T
1
=
E
1 to task τ
1.
(3) Initializingi
=
1;
(4) Calculatingb
i
* by formula (19);
(5) Assigningb
i
+
1
*
,
b
i
+
2
*
,
…
,
b
n
* to b
i
* separately;
(6)i
=
i
+
1, returning to Step (4) till all b
i
* are calculated.
(7)for
i
=
1
,
2
,
…
,
n,
(8) Obtaining all preemptive time threshold by formula (20) and (21).
(9)endfor
(10)for tasks τ
i
(
i
=
1
,
2
,
…
,
n
)
(11) Calculating maxI
/
O delay I
O
L
i
max
⁡, and min I
/
O delay min I
/
O delay.
(12)endfor
(13) Output:P
T
1
,
P
T
2
,
…
,
P
T
n
,
I
O
L
i
max
⁡  and I
O
L
i
min
⁡.Algorithm1 implements an optimization allocation of preemptive time threshold for each job. From the above formula (18) and (19), we can know that the time complexity of this algorithm is O
(
n
).TID
=
{
ti
d
1
,
ti
d
2
,
…
,
ti
d
N
} which corresponds to task release time. If several tasks are released at the same time, then the system uses the task TID having the highest priority.At any given timet, s
i
(
t
)
=
t
-
∑
k
=
1
i
⌈
(
t
-
φ
k
)
/
T
k
⌉
·
E
k is used to express the time difference between system supplying and finishing the all jobs whose priority is no less than job i during time period [
0
,
t
).For any one task set based on EDF task scheduling algorithm, system can calculate the amount of task preemption by task attribute during the time period[
0
,
γ
] according to Algorithm 2.Algorithm 2
(1) Input:n
,
β
,
T
i
,
E
i
,
φ
i
(
i
=
1
,
2
,
…
,
n
);
(2) Initializingξ
i
=
0; p
r
e
e
i
(
β
)
=
0
,
(
i
=
1
,
2
,
…
,
n
)
;
p
r
e
e
(
β
)
=
0;
(3) Constructing TID ={
t
i
d
1
,
t
i
d
2
,
…
,
t
i
d
N
} and Set S
(
r
)
=
{
r
1
,
r
2
,
…
,
r
N
};  // N
≤
∑
i
=
1
n
⌊
τ
-
φ
i
T
i
⌋
+
n
(4)for
k
=
1 to N;
(5) Detecting release time of all tasks;
(6)t
=
r
k;  m
=
t
i
d
k;
(7)if
s
m
(
t
)
-
s
m
(
ξ
m
)
≤
0
then
(8) Ending this loop, and detecting next release time;
(9)endif
(10)if
s
n
(
t
)
-
s
n
(
ξ
n
)
>
0 then
(11) Refreshingξ
i
=
t
(
i
=
m
,
m
+
1
,
…
,
n
);
(12) Ending this loop, and detecting next release time;
(13)endif
(14) System finds the indexλ
=
i in m
+
1
,
m
+
2
,
…
,
n, and makes s
i
-
1
(
t
)
-
s
i
-
1
(
ξ
i
-
1
)
>
0 and
s
i
(
t
)
-
s
i
(
ξ
i
)
≤
0;
(15)if s
λ
(
t
)
-
s
λ
(
ξ
λ
)
≠
0
then
(16)p
r
e
e
λ
(
β
)
=
p
r
e
e
λ
(
β
)
+
1;
(17)endif
(18) Refreshingξ
i
=
t
(
i
=
m
,
m
+
1
,
…
,
λ
-
1
);
(19)endfor
(20) Output:p
r
e
e
i
(
β
)
,
(
i
=
1
,
2
,
…
,
n
);  the amount of task i is preempted
p
r
e
e
(
β
)
=
∑
i
=
1
n
p
r
e
e
i
(
β
);  the amount of all preemptionsThe above algorithms describe the implementation of postponing the execution of some jobs for some tasks; at the meanwhile, nonpreemptive scope is added for some jobs in others tasks, and the below discussion will describe the experiments about the performance test.


## 4. Experimental Platform

In order to test the performance of the improved task scheduling algorithm, we used the hardware platform of Webit&NEU [13] and its operating system Webit&NEU OS which were implemented by our China Liaoning Province Embedded Technique Key Laboratory.


### 4.1. Hardware Platform

Webit&NEU (Atmega128L Processor) uses the basic structure of Webit2.0. It can collect and handle the data collected from the CC2520 and store the core data to data memory.Webit2.0 (AT90S8515 Processor) is an embedded Internet device that has implemented the function about making the standard industry device that can access the Internet. Webit2.0 has successfully been developed by our China Liaoning Province Embedded Technique Key Laboratory and has been manufactured by our China Shenyang Neu-Era Information Technology Stock CO., LTD. The most important is that Webit2.0 has also achieved the China’s product patent (numbers ZL 00 2 52482.1 and ZL 01 2 29725.9) [14].


### 4.2. Software Platform

A real-time operating system must have the ability to respond to external events fast. In order to coordinate and execute tasks effectively, Webit&NEU OS system provides the following services: interrupt handlers, intertask communication facilities, task synchronization, internal memory management, timing services, task priority assignment, and so on as Table1 shows [15, 16]. Webit&NEU OS supports up to 16 tasks, which is committed to achieve low cost application in the IoT. These tasks have 8 different priorities of 0–7. The bigger the value, and higher the priority.Table 1
The structure of Webit&NEU OS kernel.
Function module
Implementation of system calls
(a) Task management services
(i) CREATE TASK: Creating and scheduling a system task dynamically.(ii) DELETE TASK: Deleting a specific system task.(iii) GET FUNCTION ID: Obtaining task’s function ID (00H to 0FFH).(iv) SUSPEND TASK: Suspending a task of being executed.
(b) Intertask communication services
(i) ALLOCATE: Allocating buffer space where a task creates a message    for sending.(ii) SEND MESSAGE: Sending a message to the specific destination.(iii) WAIT MESSAGE: Causing a task to wait for receiving a message.(iv) DEALLOCATE: Returning a buffer allocated to the system buffer.
(c) Internal memory management services
(i) GET MEMORY: Getting the address of a block of internal memory with specific length is currently available in the system.(ii) RELESE MEMORY: Returning a block of memory of specific length to the system memory pool.
(d) Interrupt-handling services
(i) DISABLE INTERRUPT: Disabling specific interrupts.(ii) ENABLE INTERRUPT: Reenabling disabled interrupts.(iii) SYNCHRONIZE: Synchronizing tasks with interrupts.
(e) Timing services
(i) SET INTERVAL: Setting a time interval when the interval event has occurred.(ii) WAIT TIME: Waiting for interval event or timeout to occur.All of these functions implemented by the unique design of system call can easily execute real-time applications. System call is a program supported to user by operating system, while users need to implement certain system function; then, what they need to do is to call the accordingly system call in the application program; thus, it is very convenient for users to use the system kernel.All the system calls are written in AVR assembly language. One of the important advantage for AVR assembly language is that it can flexibly and easily manage a certain storage location in memory, even its certain bit of the storage location, so system can effectively handle task, interruption, message, timing, and so on.All of these functions can easily implement real-time applications, so the Webit&NEU OS system can well be used to effectively manage data collection, wireless communication in the field of WSN, and it has successfully been developed by our China Liaoning Province Embedded Technique Key Laboratory.


## 4.1. Hardware Platform

Webit&NEU (Atmega128L Processor) uses the basic structure of Webit2.0. It can collect and handle the data collected from the CC2520 and store the core data to data memory.Webit2.0 (AT90S8515 Processor) is an embedded Internet device that has implemented the function about making the standard industry device that can access the Internet. Webit2.0 has successfully been developed by our China Liaoning Province Embedded Technique Key Laboratory and has been manufactured by our China Shenyang Neu-Era Information Technology Stock CO., LTD. The most important is that Webit2.0 has also achieved the China’s product patent (numbers ZL 00 2 52482.1 and ZL 01 2 29725.9) [14].


## 4.2. Software Platform

A real-time operating system must have the ability to respond to external events fast. In order to coordinate and execute tasks effectively, Webit&NEU OS system provides the following services: interrupt handlers, intertask communication facilities, task synchronization, internal memory management, timing services, task priority assignment, and so on as Table1 shows [15, 16]. Webit&NEU OS supports up to 16 tasks, which is committed to achieve low cost application in the IoT. These tasks have 8 different priorities of 0–7. The bigger the value, and higher the priority.Table 1
The structure of Webit&NEU OS kernel.
Function module
Implementation of system calls
(a) Task management services
(i) CREATE TASK: Creating and scheduling a system task dynamically.(ii) DELETE TASK: Deleting a specific system task.(iii) GET FUNCTION ID: Obtaining task’s function ID (00H to 0FFH).(iv) SUSPEND TASK: Suspending a task of being executed.
(b) Intertask communication services
(i) ALLOCATE: Allocating buffer space where a task creates a message    for sending.(ii) SEND MESSAGE: Sending a message to the specific destination.(iii) WAIT MESSAGE: Causing a task to wait for receiving a message.(iv) DEALLOCATE: Returning a buffer allocated to the system buffer.
(c) Internal memory management services
(i) GET MEMORY: Getting the address of a block of internal memory with specific length is currently available in the system.(ii) RELESE MEMORY: Returning a block of memory of specific length to the system memory pool.
(d) Interrupt-handling services
(i) DISABLE INTERRUPT: Disabling specific interrupts.(ii) ENABLE INTERRUPT: Reenabling disabled interrupts.(iii) SYNCHRONIZE: Synchronizing tasks with interrupts.
(e) Timing services
(i) SET INTERVAL: Setting a time interval when the interval event has occurred.(ii) WAIT TIME: Waiting for interval event or timeout to occur.All of these functions implemented by the unique design of system call can easily execute real-time applications. System call is a program supported to user by operating system, while users need to implement certain system function; then, what they need to do is to call the accordingly system call in the application program; thus, it is very convenient for users to use the system kernel.All the system calls are written in AVR assembly language. One of the important advantage for AVR assembly language is that it can flexibly and easily manage a certain storage location in memory, even its certain bit of the storage location, so system can effectively handle task, interruption, message, timing, and so on.All of these functions can easily implement real-time applications, so the Webit&NEU OS system can well be used to effectively manage data collection, wireless communication in the field of WSN, and it has successfully been developed by our China Liaoning Province Embedded Technique Key Laboratory.


## 5. Performance Analysis of Improved EDF Scheduling Algorithm

For system loadU
=
0.05,0.1,0.15
,
…
,
0.9, the system generates 18 period task sets totally, and each set includes 6 period tasks generated at random. Table 2 shows the case of task preemption comparison before and after algorithm optimization.Table 2
Case of task preemption comparison before and after algorithm optimization.
System loadU
0.05
0.1
0.15
0.2
0.25
0.3
0.35
0.4
0.45
0.5
0.55
0.6
0.65
0.7
0.75
0.8
0.85
0.9
Before optimization
4
6
9
11
15
18
24
29
34
37
45
49
56
61
72
80
91
99
After optimization
2
3
5
6
8
10
13
16
19
21
26
28
33
36
44
50
59
66
Preemption optimization rate
50.0%
50.0%
44.4%
45.5%
46.7%
44.4%
45.8%
44.8%
44.1%
43.2%
42.2%
42.9%
41.1%
41.0%
38.9%
37.5%
35.2%
33.3%From the experimental results, we can know that the optimization scope ranges from 50.0% to 33.3%; with the increase of system load, the preemption optimization rate decreases correspondingly, which means that system can get better optimization while system load is lower [17–19].We used the tools of logic analyzer (TLA603), arbitrary waveform generator (AWG2021), and digital storage oscilloscope (TDS1012). In the test programs, we added some control codes by transforming the value of high and low levels of pulses through I/O pin while task is preempted.The I/O pin of Webit&NEU is connected to the digital storage oscilloscope (TDS1012). While there are the task preemptions happening, the system will alter the current value of pulses when certain task is about to be preempted; accordingly, the system will also change the current value of pulses again while the preempted task begins to execute again. So from the waveform of the experimental results in the digital storage oscilloscope, we can obtain the whole timeT
w for the whole process. Besides, we can also get the whole execution time of the preemption task T
e. So I/O delay time T
I
/
O
delay can be calculated by T
I
/
O
delay
=
T
w
-
T
e.Under the case of different system load, we obtained the I/O delay according to the above method, and the experimental results are shown in Figure2.Figure 2
I/O delay comparison before and after algorithm optimization.As Figure2 shows, while the system load is 0.05, system can achieve the best optimization rate of 50.8%; however, even the system load is 0.9 and the optimization rate can still reach 31.6%. Obviously, the proposed improved task scheduling algorithm can well decrease the I/O delay for the real-time operating system. The system I/O delay is obviously reduced because of the decrease of task preemption, which also means that the system overhead is also reduced. Consequently system real-time ability is enhanced, and at the meanwhile, energy consumption is also obviously decreased [20].Table3 shows the system kernel code size of Webit5.0 OS (the fifth version operation system for Webit2.0), Webit&NEU OS, and μC/OS-II separately. Because Webit&NEU OS supports only up to 16 tasks, it is committed to low cost application in the IoT, so its kernel code size is smaller than μC/OS-II who manages up to 64 tasks. This is just the design goal of light-weight operating systems for Webit&NEU OS.Table 3
Comparison of system kernel size (KB).
Operating system
System kernel code size
Webit&NEU OS
3.856
Webit&NEU OS with improved algorithm
4.031
µCOS-II
About 12As the code memory of Atmega128L is 128 KB, the code size of Webit&NEU OS with improved algorithm (4.031 KB) is 4.34% larger than Webit&NEU OS’s (3.856 KB); its size only occupies 3.15% of the whole code memory, so it still leaves enough space for user applications.


## 6. Conclusions

Compared with other current common solutions to increase the lifetime of WSN nodes, this paper aims to improve the lifetime and system performance by optimizing task scheduling algorithm when WSN nodes are applied to actuator applications. On the premise that these jobs can be executed within their execution deadline, system postpones executing some jobs to ensure that more jobs can better be executed, which can reduce task preemption greatly. By executing the improved task scheduling algorithm in the platform of Webit&NEU and Webit&NEU OS both designed and implemented by our laboratory, the experimental results show that the system I/O delay and overhead are decreased effectively and the occurrences of unacceptable system states caused by vibrations are also reduced, due to the reduction of task preemption in tiny mechanical system composed of WSN nodes.



---

*Source: 307869-2014-04-22.xml*