# An Efficient Multitask Scheduling Model for Wireless Sensor Networks

Authors: Hongsheng Yin; Honggang Qi; Jingwen Xu; Xin Huang; Anping He
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

The sensor nodes of multitask wireless network are constrained in performance-driven computation. Theoretical studies on the data processing model of wireless sensor nodes suggest satisfying the requirements of high qualities of service (QoS) of multiple application networks, thus improving the efficiency of network. In this paper, we present the priority based data processing model for multitask sensor nodes in the architecture of multitask wireless sensor network. The proposed model is deduced with the M/M/1 queuing model based on the queuing theory where the average delay of data packets passing by sensor nodes is estimated. The model  is validated with the real data from the Huoerxinhe Coal Mine. By applying the proposed priority based data processing model in the multitask wireless sensor network, the average delay of data packets in a sensor nodes is reduced nearly to 50%. The simulation results show that the proposed model can improve the throughput of network efficiently.


---

## Body

## 1. Introduction

Wireless sensor network (WSN) is a basic network for accessing the data information in the sensor layer of the Internet of Things (IOS). WSN is widely applied in various areas [1]. For instance, in military, the troop and equipment can be identified and services can be coordinated to fight with the assistance of WSN. In the aspect of biomedical, human health can be monitored by the surgical sensors implanted in body, which is a typical application of WSN. Moreover, in earthquake prediction, ad hoc deployment of seismic sensors along the volcanic area can detect the development of earthquakes and eruptions [2]. WSN integrates the technologies of information sensing, data processing and transmission, which is a multitask system. Numerous data services are operating on the multitask system, such as the wireless monitoring and information management systems for coalmine safety production. The types of the service data provided by WSN are classified as automatic control command, safety monitoring data, audio and video data, and so on [3]. Usually, the coverage range of wireless sensor network is not very large. Thus, the transmission delay of electromagnetic wave may be neglected. As the sensor nodes are constrained in computation, storage, and energy, it is difficult to meet the requirement of good quality of service (QoS) for more tasks running in a network. Moreover, due to the unreliable wireless channel interfered by noise, QoS of the wireless transmission is often depressed, which is especially significant in multitask wireless network. And therefore, in order to improve the performance of multitask wireless sensor network, it is very important to carry out research on the high-efficient multitask scheduling model for wireless sensor network.TinyOS is an operating system, which is widely used in wireless sensor networks. The operating system adopts First Come First Served (FCFS) scheduling strategy for task scheduling, which is efficient to reduce the requirements of storing space [4, 5]. However, as there are no the priorities among various kinds of service data, some real-time services cannot be timely responded, so that many services are missed, which results in the low throughput of network [6]. For the drawback of TinyOS in the scheduling strategy, the researchers have done many researches for improving the scheduling strategy. The contribution [7] introduced a dual circular-based task scheduling strategy. In this strategy, the single circular queue is substituted with the dual circular queues with different priorities. The tasks are assigned different priorities and then are allocated in the two circular queues according to their priorities. The tasks in different queues are dynamically switched according to their time variations for guaranteeing them to be responded as much as possible. The strategy improves the speed of response to real-time tasks, but the throughput of network is still low. In contribution [8, 9], a priority based soft real-time task scheduling strategy was proposed, which increases the throughput of network but does not satisfy the real-time requirement of some high-priority tasks. For solving the existing problem in [8, 9], the contribution [10] introduced an improving scheduling strategy, EF-RM (emergency task first rate monotonic), which is the preemptive scheduling for both periodical and nonperiodical tasks to ensure the implementation of the important task of priority in TinyOS. The contribution [11] proposed the IS-EDF (idle sleep-earliest deadline first) scheduling strategy, which adjusts the priority of tasks dynamically to ensure that the important task is real-time processed.In this paper, through further research on the relevant contributions mentioned above, we propose the priority queue-based data processing model for multitask network and deduce the theoretical formulas of the QoS of network with the proposed model, including average queue length, delay, and delay jitter. The performance of the proposed models is analyzed and compared by the practical simulation experiments.The rest of this paper is organized as follows: The architecture of multitask wireless sensor network is presented in Section2. Then, the queue theory is introduced in Section 3 first. Subsequently, in Sections 4 and 5, two queue models are described, respectively. The experimental results are shown in Section 6. Finally, we conclude this paper in Section 7.


## 2. Architecture of Multitask Wireless Sensor Network

In the wireless sensor network, a large number of wireless sensor nodes are densely and fully deployed in the network. These wireless sensor nodes are organized into many clusters. Each cluster is composed of a cluster head and multiple sensor nodes. The internal sensor nodes can communicate with each other in the cluster. The external communications between clusters are fulfilled by the cluster heads in these clusters. Moreover, the cluster head is responsible for assigning the time slot for each sensor nodes in its cluster. The data collected from each wireless sensor nodes are first gathered in the cluster heads and then transmitted to a database in the server by the sink nodes through the wired Ethernet. All applications in the network share the data in the database for different functions. The architecture of multitask wireless sensor network is shown in Figure1.Figure 1
Multiapplication system architecture of wireless sensor network.


## 3. Concept of Queuing Theory

Queuing theory is a mathematical method for analyzing the congestion and delays of data packets in a link. With queuing theory, the arrival, service, and depart of data packets can be accurately evaluated so that the data packets can be efficiently scheduled in a link. For describing the proposed model based on the queuing theory easily, we give the following definitions.Definition 1 (inputting distributionA
(
t
)).
In the inputting process, letC
n be the nth data packet arriving at the network node and the arrival time is τ
n; then, t
n
=
τ
n
-
τ
n
-
1, which means the time interval between C
n and C
n
-
1. Assume that τ
0
=
0 and the arriving data packets are independent; then, {
t
n
} is the sequence of independent random variables, written as A
(
t
).Definition 2 (serving distributionB
(
t
)).
In the service process, let the service time of data packetC
n be ν
n. Assume that the services of data packets are independent; then, {
v
n
} is the dependent sequence of random variables, written as B
(
t
).Definition 3 (arrival probability of data packetp
(
n
)).
LetN
(
t
) be the number of data packets in a network node at time t and let p
(
n
) be the arrival probability of n data packets in time interval (
t
1
,
t
2
); then, there is the relation
(1)
p
(
n
)
=
P
{
N
(
t
2
)
-
N
(
t
1
)
=
n
}
,
(
t
2
>
t
1
,
n
≥
0
)
.Definition 4 (arrival rate of data packetλ).
An average number of data packets arrive at a network node in unit time, which reflects how fast the data packets arrive at a network node.1
/
λ is just the average arrival time interval of data packets.Definition 5 (service rate of network nodeμ).
An average number of served data packets depart from a network node in unit time, which reflects how fast the services are in the network node.1
/
μ is just the average time of the data packets severed in a network node.Definition 6 (service intensityρ).
The average service time of each network node in unit time, which is an important indicator for measuring how busy the network nodes, isρ
=
λ
/
μ, 0
≤
ρ
<
1.In the real situation of wireless sensor network, the data packets arrive at sensor nodes continuously. Thus, the number of data packets is regarded as infinite. For simplicity, the arrival times of data packets are assumed to follow M/M/1 queue model. The input process of data packets, that is, the arrival times, is similar to the Poisson stream with parameterλ. The arriving time interval A
(
t
) and service time B
(
t
) follow the negative exponential distribution with parameters λ and μ, respectively, where the service window size is 1. Based on the reasonable assumptions and the definitions on queue theory mentioned above, two queue system models, nonpriority and priority models, are analyzed and compared as follows. And therefore, the high efficient queue model is proposed in this paper.


## 4. Data Processing Model Based on Nonpriority Queue System

As shown in Figure2, the data packets enter the network nodes continuously and are lined up in a queue with the average arrival rate λ. The data packets depart in turn from the queue and data services are scheduled in the scheduler at the average processing rate μ. The node state N at time t is denoted as N
(
t
)
=
(
i
), where i is the number of data packets including the processing data packet, that is, the queue length. It is easy to be proved that {
N
(
t
)
,
t
≥
0
} is birth-death process [12–16].Figure 2
Data processing model for the queuing system without priority.Letp
(
i
;
t
)
=
P
{
N
(
t
)
=
(
i
)
}, where p
(
i
)
=
lim
⁡
t
→
∞
⁡
p
(
i
;
t
)
,
i
≥
0. Referring to Figure 3, if ρ
=
λ
/
μ
<
1, the balance equations are as follows:
(2)
λ
p
(
0
)
=
μ
p
(
1
)
(
λ
+
μ
)
p
(
1
)
=
λ
p
(
0
)
+
μ
p
(
2
)
(
λ
+
μ
)
p
(
2
)
=
λ
p
(
1
)
+
μ
p
(
3
)
⋯
(
λ
+
μ
)
p
(
i
)
=
λ
p
(
i
-
1
)
+
μ
p
(
i
+
1
)
.
Because there is ∑
i
=
0
∞
p
(
i
)
=
1 and p
(
i
)
=
(
1
-
ρ
)
ρ
i holds, so the average length of data packets in network node is. 						(3)
Q
=
∑
i
=
0
∞
i
p
(
i
)
=
∑
i
=
0
∞
i
(
1
-
ρ
)
ρ
i
=
ρ
1
-
ρ
.
And the average waiting queue length of data packets in network node is
(4)
W
=
∑
i
=
0
∞
i
p
(
i
+
1
)
=
∑
i
=
0
∞
i
(
1
-
ρ
)
ρ
i
+
1
=
ρ
2
1
-
ρ
.
According to the Little theorem, the average waiting time of a data packet is expressed as
(5)
T
w
=
W
λ
=
ρ
2
λ
(
1
-
ρ
)
=
ρ
μ
(
1
-
ρ
)
.
And the average residence time of a data packet in network node, that is, delay of a data packet, is
(6)
T
Q
=
T
W
+
1
μ
=
1
μ
(
1
-
ρ
)
=
1
μ
-
λ
And the delay jitter of a data packet in network node, that is, variance of delay, is
(7)
J
Q
=
1
(
μ
-
λ
)
2
.Figure 3
State diagram of birth-death process for queuing system without priority.


## 5. Data Processing Model of Queue with Priority

In this model, the data packets entering the network node are classified into two queues with different priorities at the average ratesλ
1 and λ
2 by the classifier, as shown in Figure 4. In the scheduler, according to the service rule given by the priority decision module, the services are obtained at the average processing rates μ
1 and μ
2. The priority decision module decides the processing sequence of data packets for the scheduler. It employs the preemptive priority service rule, which allows that the services of low-priority data packets are interrupted and free up resource for serving the high-priority data packets. The data packets with the same priority will be serviced according to the FCFS rule.Figure 4
Data processing model for the queuing system with priority.The data packet with priority is denoted by C1 and the data packet without priority is denoted by C2. The data packets C1 and C2 arrive at the network node in independent Poisson distribution with the parametersλ
1 and λ
2, respectively, and their service times follow the negative exponential distribution with the parameters μ
1 and μ
2. The system utilization is denoted by ρ, which is the time rate of service busy. That is the proportion of time that the scheduler busies. λ is the average arrival rate of all data packets and μ is the average processing rate for all data packets. The relations between these parameters can be expressed as λ
=
λ
1
+
λ
2, ρ
=
ρ
1
+
ρ
2, ρ
=
λ
/
μ, ρ
1
=
λ
1
/
μ
1, and ρ
2
=
λ
2
/
μ
2.The state of network node at timet is denoted as N
(
t
)
=
(
i
,
j
). If the number of data packets C1 is i and the number of data packets C2 is j, it is easy to prove that {
N
(
t
)
,
t
≥
0
} is the birth-death process [12–16]. The state diagram of birth-death process for queuing system with priority is shown in Figure 5.State diagram of birth-death process for queuing system with priority.
(a)
state(
i
,
0
) as center
(b)
State(
0
,
j
) as center
(c)
State(
0,0
) as center
(d)
State(
i
,
j
) as centerLet(8)
p
(
i
,
j
;
t
)
=
P
{
N
(
t
)
=
(
i
,
j
)
}
,
p
(
i
,
j
)
=
lim
⁡
t
→
∞
p
(
i
,
j
;
t
)
i
,
j
≥
0
According to the states in Figure 5, if ρ
=
ρ
1
+
ρ
2
=
λ
1
/
μ
1
+
λ
2
/
μ
2
≤
1, then the following equations hold:
(9)
(
λ
1
+
λ
2
)
p
(
0,0
)
=
μ
1
p
(
1,0
)
+
μ
2
p
(
0,1
)
(
λ
1
+
λ
2
+
μ
1
)
p
(
i
,
0
)
=
μ
1
p
(
i
+
1,0
)
+
λ
1
p
(
i
-
1,0
)
i
>
0
,
(
λ
1
+
λ
2
+
μ
2
)
p
(
0
,
j
)
=
λ
2
p
(
0
,
j
-
1
)
+
μ
1
p
(
1
,
j
)
+
μ
2
p
(
0
,
j
+
1
)
j
>
0
,
(
λ
1
+
λ
2
+
μ
1
)
p
(
i
,
j
)
=
λ
1
p
(
i
-
1
,
j
)
+
λ
2
p
(
i
,
j
-
1
)
+
μ
1
p
(
i
+
1
,
j
)
i
,
j
>
0
.
The process of solving the equations (9) can be referred to [12–16], which solves p
(
i
,
j
) through the inverse solving method with the following generating function ψ
(
u
,
z
):
(10)
ψ
(
u
,
z
)
=
(
1
-
ρ
1
-
ρ
2
)
(
1
-
z
)
ω
(
z
)
[
ρ
1
u
ω
(
z
)
-
1
]
{
(
μ
1
/
μ
2
)
[
1
-
ω
(
z
)
]
z
-
(
1
-
z
)
ω
(
z
)
}
,
where ω
(
z
)
=
(
λ
1
+
μ
1
+
λ
2
(
1
-
z
)
-
[
λ
1
+
μ
1
+
λ
2
(
1
-
z
)
]
2
-
4
λ
1
μ
1
)
/
2
λ
1. The solution of function p
(
i
,
j
) is solved by the differential generating function ψ
(
u
,
z
); that is,
(11)
p
(
i
,
j
)
=
1
i
!
j
!
·
∂
i
+
j
ψ
(
u
,
z
)
∂
u
i
∂
z
j
|
u
=
z
=
0
.
Let the probabilities of i C1 data packets and j C2 data packets in network node be p
i
• and p
•
j, respectively. Their probabilities of generating functions are ψ
(
u
,
1
) and ψ
(
1
,
z
).By formula (10), let z
→
1, using the L’Hospital Rule; we can get
(12)
ψ
(
u
,
1
)
=
1
-
ρ
1
1
-
ρ
1
u
=
∑
i
=
0
∞
(
1
-
ρ
1
)
ρ
1
i
u
i
.
Thus, p
i
•
=
(
1
-
ρ
1
)
ρ
1
i, which is the same as the M/M/1 queue system with only one kind of client. As a result, it shows that the existence of C2 data packets has no effect on the C1 data packets, which is in accord with the practical situation of network. Similarly, the average length of C1 data packet queue and the average length of C1 data packet waiting queue can be got as
(13)
Q
1
=
ρ
1
1
-
ρ
1
,
W
1
=
ρ
1
2
1
-
ρ
1
.
And the average waiting time and average residence time of single C1 data packet are
(14)
T
W
1
=
ρ
1
μ
1
(
1
-
ρ
1
)
(15)
T
Q
1
=
1
μ
1
(
1
-
ρ
1
)
=
1
μ
1
-
λ
1
.
The delay jitter of a C1 data packet in the network node that is the delay variance is as follows:
(16)
J
Q
1
=
1
(
μ
1
-
λ
1
)
2
.
Then, by formula (10), we get
(17)
ψ
(
1
,
z
)
=
(
1
-
ρ
1
-
ρ
2
)
(
1
-
z
)
ω
(
z
)
[
ρ
1
ω
(
z
)
-
1
]
{
(
μ
1
/
μ
2
)
[
1
-
ω
(
z
)
]
z
-
(
1
-
z
)
ω
(
z
)
}
.
Derivate formula (17) by z and then let z
=
1; the average queue length of C2 data packets can be deduced as
(18)
Q
2
=
∑
j
=
0
∞
j
p
•
j
=
ρ
2
1
-
ρ
1
-
ρ
2
[
1
+
μ
2
ρ
1
μ
1
(
1
-
ρ
1
)
]
.
Thus, the average residence time of a C2 data packet is
(19)
T
Q
2
=
Q
1
T
Q
1
+
Q
2
λ
2
=
ρ
1
μ
1
(
1
-
ρ
1
)
2
+
1
μ
2
(
1
-
ρ
1
-
ρ
2
)
[
1
+
μ
2
ρ
1
μ
1
(
1
-
ρ
1
)
]
.


## 6. Simulation Experiments and Discussion

The proposed multitask schedule model can be used in many network applications. In coalmine, there are many monitoring and information management systems for its safety and production, which are the typical multitask wireless sensor network applications. In this kind of monitoring systems, the usual detecting period is 20 seconds and the number of monitoring nodes is usually more than 200. Thus, the proposed model applied in the gas warning system needs to process the data of thousands of sensor nodes. Moreover, the network delay and processing time need to be considered in practice applications.In this experiment, we use the practical data from Huoerxinhe Coal Mine, China, which lay the gas warning wireless network with the same system structure as in Figure1. In this network, the backbone network is optical fiber Ethernet, based on which network is partitioned into many zones. In each zone, a number of wireless sensor nodes are evenly laid out. Various monitoring data, such as gas concentration, CO concentration, CO2 concentration, and so on are detected in real time by the sensor nodes. These data will be collected to the Sink node in the zone. Subsequently, all data are transferred to the server by the sink nodes in each zone. The transfer capability of Sink nodes is the bottleneck of the capability of the network system. In the test data set from Huoerxinhe Coal Mine, a Sink node is able to send 200 UDP packets per second, from which 90 UDP packets arrive at the target node. Each UDP packet contains 85 bytes. The parameters λ, λ
1, λ
2, μ, μ
1, and μ
2 in formula (6), (15), and (19) are decided according to the field test.If the priority processing rule is not employed, that is, the sink node employs the data processing model based on queue system without priority, theλ
=
90 packets/s and μ
=
200
/
s. According to formula (6), the average delay of each packet is 9.1 ms. If the priority processing rule is employed, that is, the sink node employs the data processing model based on queue system with priority, the data are distinguished with different priorities. Taking the coal monitoring system as an example, the gas concentration and monitoring control command are with higher priority and others are with lower priority.According to the statistics, the probability of C1 occurrence is 0.10 and the probability of C2 occurrence is 0.90. Meanwhile,μ
1
=
μ
2
=
200 packets/s, λ
=
90 packets/s, λ
1
=
9 packets/s, and λ
2
=
81 packets/s. Thus, according to formulas (15) and (19), the average delay of C1 packets is 5.2 ms and the average delay of C2 packets is 9.7 ms.The theoretical analysis shows that compared with the data processing model based on queue system without priority, the average delay of data packets processed with the model based on queue system with priority is reduced up to 43%. However, the average delay of data packets without priority is slightly reduced only 6.6%.For observing the queue and service process of data packets in network nodes with the proposed model, we use MatLab to simulate the model. The model parametersλ, λ
1, λ
2, μ, μ
1, and μ
2 are set in accordance with the theoretical analysis. The simulation results are shown in Figures 6, 7, 8, and 9, which show the same results with theoretical analysis. In fact, operation practice of multitask wireless sensor network in Huoerxinhe Coal Mine also confirmed our theoretical analysis and simulation experiments.The curve of the time and queue length in the queuing model without priority.
(a)
(b)Figure 7
Theoretical and simulation curves of the average waiting time in the queuing model without priority.The curves of the time and queue length in the queuing model with priority.
(a)
(b)Figure 9
The curves of the average waiting time in the queuing models with priority and without priority.


## 7. Conclusions

In this paper, two data processing models with and without priority are proposed for multitask wireless sensor networks. The proposed models are established from the M/M/1 queue model. The average delay theory of data packets based on the proposed models is also deduced. The practical data from Huoerxinhe Coal Mine are used for testing the performances of the proposed two models applied in the coal safety monitoring system, which is a typical wireless sensor network application. The simulation results show that the average delay of data packets processed with the proposed model is significantly reduced. Compared with the average delay of data packets without priority, the proposed model can be applied to the multitask wireless sensor network harmonically.



---

*Source: 969523-2014-03-30.xml*