IEEE TRANSACTIONS ON INDUSTRIAL INFORMATICS, VOL. 5, NO. 1, FEBRUARY 2009

3

EARQ: Energy Aware Routing for Real-Time

and Reliable Communication in Wireless

Industrial Sensor Networks

Junyoung Heo, Jiman Hong, and Yookun Cho, Member, IEEE

Abstract—Wireless industrial sensor networks are wireless

sensor networks which have been adapted to industrial applica-
tions. Most techniques for wireless sensor networks can be applied
to wireless industrial sensor networks. However, for industrial
applications of wireless industrial sensor networks, new require-
ments such as real-time, reliable delivery need to be considered.
In this paper, we propose EARQ, which is a novel routing protocol
for wireless industrial sensor networks. It provides real-time, reli-
able delivery of a packet, while considering energy awareness. In
EARQ, a node estimates the energy cost, delay and reliability of a
path to the sink node, based only on information from neighboring
nodes. Then, it calculates the probability of selecting a path, using
the estimates. When packet forwarding is required, it randomly
selects the next node. A path with lower energy cost is likely to be
selected, because the probability is inversely proportional to the
energy cost to the sink node. To achieve real-time delivery, only
paths that may deliver a packet in time are selected. To achieve
reliability, it may send a redundant packet via an alternate path,
but only if it is a source of a packet. Experimental results show that
EARQ is suitable for industrial applications, due to its capability
for energy efficient, real-time, reliable communications.

Index

Terms—Energy

aware

routing,

industrial

control,

real-time and reliable communication, wireless industrial sensor
networks.

I. I

NTRODUCTION

W

IRELESS industrial sensor networks (WISNs) are used
to collect data from a machine equipped with sensor

nodes, and forward data to the sink node; they are generally used
for industrial control applications. The sink node is connected
to a control system that obtains data via the sink node, and con-
trols actuators in a machine, or alerts users as a result of data
analysis. WISNs can provide lower cable costs, and easy setup
and maintenance [1]–[5] for existing industrial applications.

WISNs are useful for factory automation involving a variety

of applications, such as an industrial process control [6], pre-

Manuscript received April 30, 2008; revised August 20, 2008 and October

31, 2008. Current version published March 06, 2009. This work was supported
in part by the Korea Science and Engineering Foundation Grant funded by the
Korea government (MEST) (No. R01-2008-000-12157-0) and in part by the
Soongsil University Research fund. The ICT at Seoul National University pro-
vided research facilities for this study. Paper no. TII-08-04-0047.R2.

J. Heo and Y. Cho are with the School of Computer Science and Engineering,

Seoul National University, Seoul, Korea.

J. Hong is with the School of Computing, Soongsil University, Seoul, Korea

(e-mail: [e-mail]).

Color versions of one or more of the figures in this paper are available online

at http://ieeexplore.ieee.org.

Digital Object Identifier 10.1109/TII.2008.2011052

dictive maintenance of a machine [7], industrial linear posi-
tion [8], etc. Machine vision is an application of computer vi-
sion for industrial process control [6]. Machine vision involves
input/output devices and control networks, which can be re-
placed with WISNs. Machine vision can improve the quality of
manufacturing, by searching for product defects using informa-
tion from WISNs. Predictive maintenance can improve produc-
tivity by monitoring and assessing the health status of a piece
of equipment in a machine [7]. Industrial linear position is an
industrial application for measuring displacements of moving
parts [8].

In WISNs, it is necessary to consider new QoS requirements,

such as real-time, reliable communication [1], [5]–[10]. In
WISNs, sensing data from sensor nodes must be transmitted to
the sink, reliably and in time. Delayed or lost data may cause
industrial applications to malfunction, because the sensing data
is analyzed and appropriate commands are sent to the actuator
of a machine. Machine vision for industrial process control uses
a multimedia stream, which is more affected by jitter or packet
loss than scalar physical phenomena. A delayed packet may be
useless, and it is difficult to obtain meaningful information from
decoding packets if the rate of packet loss exceeds a threshold.
Soft real-time communications are acceptable in WISNs, be-
cause of fault tolerance, which is one of the major advantages
of WISNs. Though some packets are lost or delayed, others
may be transmitted continuously, or transmitted via another
path. Applications such as machine vision require soft real-time
communications for the multimedia stream, where a slight
delay or a small rate of packet loss is tolerable.

Routing protocols for WISNs must be carefully designed,

to consider resource constraints such as low processing power,
small memory and limited energy of sensor nodes [11], [12]. In
addition, WISNs must be scalable and able to tolerate dynamic
network changes. They range from tens to thousands of sensor
nodes. Therefore, the complexity of the routing algorithm must
be independent of the size of the networks or the number of
sensor nodes. They would be impractical if memory utilization
increases as the number of nodes increases. New nodes may be
newly deployed, or some nodes may disappear, due to malfunc-
tions. Therefore, routing algorithms must adapt to dynamic net-
work changes.

WISNs may use routing protocol for wireless mobile ad-hoc

networks or wireless sensor networks (WSNs), because they
have similar wireless networks characteristics. In several studies
[13]–[15], real-time, reliable communication has been studied
for wireless mobile ad-hoc networks. However, there were prob-

1551-3203/$25.00 © 2009 IEEE

Authorized licensed use limited to: Imperial College London. Downloaded on June 07,2010 at 19:37:30 UTC from IEEE Xplore. Restrictions apply.

4

IEEE TRANSACTIONS ON INDUSTRIAL INFORMATICS, VOL. 5, NO. 1, FEBRUARY 2009

lems in applying these studies to WISNs, because the scala-
bility of WISNs or constraints of sensor nodes were not con-
sidered. There have been studies about real-time, reliable com-
munication in WSNs [16]–[22]. Most of these studies do not
provide simultaneous real-time, reliable and energy aware com-
munication. The aforementioned WISNs require simultaneous
real-time, reliable and energy aware communication. Therefore,
it is necessary to design a routing protocol that can provide real-
time, reliable communication, and energy awareness in WISNs.

In this paper we propose EARQ, which is designed to achieve

the aforementioned requirements in WISNs. It provides real-
time, reliable delivery of a packet, while considering energy.
Especially, EARQ can set the packet reliability.

1

Redundant

packets can be used to prevent packet loss in real-time com-
munications. However, the number of packets in networks in-
creases, due to redundant packets. Due to the increased number
of packets, there can be congestion or increased energy expen-
diture. Therefore, setting the reliability of a packet is essen-
tial, so that the user can achieve a trade-off between energy and
reliability.

EARQ estimates the expected values of the energy cost, delay

and reliability of a path to the sink node. These values are com-
puted using only information from neighboring nodes. Based
on these values, EARQ selects a path that requires low energy,
low delay and provides high reliability. For an even distribution
of energy expenditure, sometimes EARQ selects a non-optimal
path in terms of energy expenditure, but can still deliver a packet
in time.

This paper provides a simple approximation of the minimum

delay, given the density of sensor nodes and radio range. The
minimum delay is important, because a deadline shorter than
the minimum delay will result in numerous packets missing the
deadline. When applications of WISNs are designed, the system
designer should consider the minimum delay, and ensure that
the deadline is the same as or longer than the minimum network
delay [23].

The remainder of the paper is organized as follows. Section II

presents related works. Section III describes the proposed
routing protocol, EARQ. Section IV presents the performance
of EARQ compared to the previous protocols. Finally, con-
cluding remarks are provided in Section V.

II. R

ELATED

W

ORKS

Many studies on energy efficient routing for WSNs have been

proposed [24]–[29]. These studies only considered the energy
efficiency of routing, and did not consider the need to ensure
real-time, reliable packet delivery. Only a couple of studies con-
sidered a deadline or the reliability of a packet in wireless com-
munication. These studies can be classified into two categories,
according to their focus: MAC layer [30] and network layer
[16]–[22].

2

The former does not consider the end-to-end delay

between the source and the sink, whereas the latter does. These
two categories of studies may be used to complement each other,
because they consider real-time transmission in different do-
mains. The proposed protocol belongs to the latter.

1

The rate of successful transmission of a packet.

2

Some of them are cross layer protocols.

He et al. proposed an end-to-end real-time communication

protocol, SPEED [16]. SPEED ensures a desired delivery speed
via a combination of feedback control and nondeterministic
geographic forwarding. By this means, it achieved real-time
communication. However, it did not consider energy expendi-
ture. Felemban et al. proposed MMSPEED [20], which is an
extended version of SPEED. MMSPEED can accommodate
different deadlines and packet reliabilities. However, MM-
SPEED is similar to SPEED in that it does not consider energy
efficiency.

In [17] and [18], Akkaya et al. proposed a routing protocol

that finds a least-cost and delay-constrained path for real-time
packets. They assumed that every node knows the position of
all nodes and the cost of links among nodes in WSNs. The pro-
tocol finds the path by executing Dijkstra’s shortest path algo-
rithm. However, these characteristics of the routing protocol do
not support the scalability of WSNs. Ammari et al. provided a
theoretical explanation of the trade-off between energy savings
and delay [19]. They calculated the delay and energy expendi-
ture for various transmission ranges, using algorithms similar to
those in [17].

Mahapatra [21] et al. proposed an energy aware QoS routing

protocol for real-time packets. The concept of providing
real-time communication is very similar to SPEED [16] and
MMSPEED [20]. However, to achieve energy efficiency, they
selected the next node in the neighbor table, according to the
priority calculated by considering both the delay and the energy
expenditure. To achieve reliable communication, they always
sent a redundant back-up packet.

EAR-RT [22] is a real-time routing protocol based on EAR

[27] and EAR-DPS [29]. EAR [27] and EAR-DPS [29] find
multiple paths from the source to destination nodes. Each neigh-
boring node is assigned a probability of being selected to for-
ward a packet. The probability is inversely proportional to the
sum of the residual energy of a neighboring node and the energy
for transmitting a packet to a neighboring node. Therefore, paths
that require lower energy are more likely to be selected. EAR
prevents any particular path from being selected continuously to
prevent energy loss of the optimal path. EAR-RT used this con-
cept to provide energy awareness in real-time routing. EAR-RT
randomly selects the next nodes among candidate nodes that
may deliver a packet in time.

EAR-RT is the preliminary result of the work presented in this

paper. Compared to EAR-RT, EARQ neither requires a separate
setup phase, nor utilizes overhearing characteristics of wireless
networks.

3

In addition, EARQ provides reliable delivery of a

packet, as well as real-time delivery. EARQ also requires MAC
support.

III. P

ROPOSED

R

OUTING

P

ROTOCOL

In this section, the EARQ protocol is presented. EARQ is

a kind of proactive routing protocol that aims to maintain an
ongoing routing table. As in other kinds of proactive routing,
EARQ constructs and maintain a routing table with information
from neighboring nodes. A beacon message is used to exchange

3

In wireless communications, when two nodes communicate with each other,

the neighboring nodes of a sender may hear the packet being transmitted.

Authorized licensed use limited to: Imperial College London. Downloaded on June 07,2010 at 19:37:30 UTC from IEEE Xplore. Restrictions apply.

HEO et al.: EARQ: ENERGY AWARE ROUTING FOR REAL-TIME AND RELIABLE COMMUNICATION

5

information related to routing among neighboring nodes. The
actual path is decided while transmitting a packet.

There are two types of messages: beacon messages and data

packets. A beacon message is exchanged among neighboring
nodes to construct and maintain a routing table. Upon receiving
a beacon message, a routing table is constructed or updated by
calculating expected values of energy cost, delay and reliability.
When a path to the sink node becomes known to a node, the node
begins to send a periodic beacon message.

The source node sends data packets to the sink after con-

structing the routing table. Each intermediate node forwards a
data packet to a neighboring node that can deliver the packet
in time. A neighboring node for forwarding a packet is selected
based on the expected delay and probability. This probability
is inversely proportional to the expected energy cost of neigh-
boring nodes. Therefore, a path that may expend less energy
than other paths is most likely to be selected. To ensure reliable
packet delivery, if the expected reliability of the selected node
does not satisfy the required reliability, the source node selects
an additional neighboring node to forward the packet.

A. Beacon Message and Routing Table

Every node exchanges a beacon message to construct and

maintain a routing table of a node. A beacon message

4

contains

expected values such as energy cost

, time delay

, re-

liability

, and residual energy

of a node .

is the

expected energy cost of sending a packet from node to the sink
node.

is the expected time of sending a packet from node to

the sink node.

is the expected reliability of sending a packet

from node

to the sink node. The reliability is the probability

of sending a packet to the sink node without error.

,

, and

at the sink node and the expected

values of the sink node are constant [22]. The beacon message
also contains the position of node . EARQ assumes that every
node knows its own position and that of the sink node. The lo-
cation information can be obtained by GPS or localization pro-
tocols for estimating the location of a node [31]–[33].

The expected values of a node may change as the residual en-

ergy of a node decreases and the state of the network changes
dynamically. Once a node obtains a path to the sink node, it
broadcasts a periodic beacon message to its neighboring nodes,
to inform them of the change of expected values. Because the
expected values of the sink node are constant, the sink node only
sends a beacon message while initiating network setup and re-
ceiving an empty beacon message. An empty beacon message
is a beacon message that contains nothing. Whenever a node
receives an empty beacon message from another node, it re-
sponds to the node with a beacon message. A new node collects
routing information by broadcasting empty beacon messages to
its neighboring nodes. It constructs its own routing table with a
beacon message from its neighboring nodes.

When a node receives a beacon message from a neighboring

node, it only adds the neighboring node to the routing table if the
neighboring node is closer to the sink node than it is. If the neigh-

4

The beacon message is similar to the Hello message in other routing

protocols.

Fig. 1. Neighboring nodes in Routing Table of node

i in WISNs for manufac-

turing machines.

boring node is already in the routing table, it only updates the ex-
pected values of the neighboring node. Fig. 1 shows an example of
neighboring nodes in the routing table of node . Nodes in the area

are neighboring nodes of node . They can communicate with

node via a wireless channel. Area

may not be a perfect circle,

because each node may have a different wireless communication
range or there may be things interfering with wireless commu-
nication, such as the machine shown in the figure. In a wireless
industrial environment, this kind of noise source must be consid-
ered [5]. Area

is a circle for which the center is at the sink node

and the radius is the distance between node and the sink node.
Nodes in area

are closer to the sink node than node because

node is at the edge of area . The neighboring nodes located at
the intersection of areas

and

(shaded area of the figure) can

be added to the routing table of node .

When the expected values of neighboring nodes are updated

by a beacon message, the routing probability

is updated

and

,

, and

are recalculated. When node

receives a

beacon message from neighboring node , node updates these
expected values as follows [22].

• The beacon message contains

,

,

, and

where

is the expected energy cost of sending a packet

from node to the sink node via node .

is the expected

time delay of sending a packet from node to the sink node
via node .

is the expected reliability of sending a

packet from node to the sink node via node .

,

,

and

are the energy cost, average time, and link strength

for single hop communication between node and node ,
respectively.

• For node

in

—which is the routing table of node

is the probability that node selects node

to forward

a packet. Therefore, a neighboring node with a lower en-
ergy cost is more likely to be selected.

Authorized licensed use limited to: Imperial College London. Downloaded on June 07,2010 at 19:37:30 UTC from IEEE Xplore. Restrictions apply.

6

IEEE TRANSACTIONS ON INDUSTRIAL INFORMATICS, VOL. 5, NO. 1, FEBRUARY 2009

• Here, the expected values of node

can be obtained as

follows:

is the energy cost of sending a packet from node

to

node

directly.

is the average time of sending a packet

from node

to node

directly. This includes the propagation

delay, the queuing delay, the retransmission delay, etc.

is the

average strength of the link between node and node . These
values can be obtained as follows:

is the distance between node and node .

is the residual

energy in the battery of node , which is normalized to its initial
energy.

and

are weighting factors [27], [29].

is a set of

packetstobetransmittedtonode during

.

isupdatedevery

.

is the delay of transmitting a packet to node from

node directly.Itincludesthepropagationdelay,thequeuingdelay
and the retransmission delay.

is one if a packet is trans-

mitted to node successfully. Otherwise,

is zero. EARQ

obtains

and

from the MAC layer.

To measure

in the MAC layer [16], [20], [21],

a sender time-stamps a data packet before the packet en-
ters the network output queue. The receiver replies with an
ACK packet with the time-stamp

and ACK processing

time

at the receiver side. When the sender receives

the ACK packet,

can be calculated as follows:

. If the packet

needs to be retransmitted in the MAC layer, the period for the
waiting ACK is added to

.

Fig. 2 presents a graphical example of expected values. The

nodes in the region indicated by the dotted line are neighboring
nodes in the routing table of node . Each neighboring node
( , , , and

) has its own expected values for sending a packet

to the sink node.

,

,

, and

for each neighboring

node

can be expressed as matrix

Fig. 2. Example of values for single hop communication between node

i and

its neighboring nodes, and expected values of the neighboring nodes.

Here, the expected values of node are

B. Node Selection for Forwarding a Packet

When a node finds a path to the sink node, and a data packet is

ready, a sensor node begins to send data packets received from
other nodes, or its own data packets obtained from sensing. The
deadline and reliability, , of a packet may be predefined by user
or determined by nodes at every transmission. The deadline is
a relative deadline, which is the tolerable delay of delivering a
data packet to the sink node. The reliability,

, included in a

packet is the desired reliability, which is between zero and one.

means that no degree of reliability is required, whereas

means that a high degree of reliability is required. The

laxity,

, which indicates the residual time until

the deadline, is embedded in a data packet and recalculated at
every node along a path to the sink node. EARQ selects the next
node to forward a packet, based on the laxity of a packet and the
expected values of neighboring nodes.

A path to the sink node is constructed during packet trans-

mission. A node —including the source node—selects the next
node, according to the following rules.

1) Select nodes in the routing table which can deliver a packet

within the required deadline

If the

,

is used as

for simplicity of the

algorithm: (

).

2) Calculate the probability

based on the

. For every

node

in

3) Randomly select the next node by the probability,

[22].

If a node

is a source node and

of the selected node

Authorized licensed use limited to: Imperial College London. Downloaded on June 07,2010 at 19:37:30 UTC from IEEE Xplore. Restrictions apply.

HEO et al.: EARQ: ENERGY AWARE ROUTING FOR REAL-TIME AND RELIABLE COMMUNICATION

7

Fig. 3. Deployment of sensor nodes.

is less than the required reliability,

, randomly select one

additional next node by the probability,

.

The selection algorithm based on probability prevents energy

loss of nodes on the optimal path with the least energy cost,
by distributing the load to other nodes on a non-optimal path.
A maximum of two packets are sent to achieve reliability, ac-
cording to the third rule. This is because the algorithm is simple,
and if there was more than two paths this may result in conges-
tion of networks, due to too many redundant packets [21].

C. Considerations for Selecting the Deadline

The packet delay generally depends on the number of hops

to the sink node. In other words, the density and size of the net-
work affects the packet delay. A deadline selected at random
without considering these network characteristics endangers ap-
plications of WISNs. Therefore, the density and size of the net-
work must be considered while selecting a deadline. In this sec-
tion, we describe the means to select an appropriate deadline,
given the density and the size of the network.

When sensor nodes are deployed at a fixed interval, as in

Fig. 3(a), the expected number of hops to the sink node depends
on the radio range,

, and the distance to the sink node,

. If

the distance to the sink node is

, the expected number of hops

is

. However, in most applications, it is difficult to de-

ploy sensor nodes at a fixed interval.

To generalize the problem, we assumed that sensor nodes are

randomly deployed according to a Poisson process [34] with
density

per unit area

. The probability that the number

of sensor nodes,

, is

in

is

The expected number of sensor nodes

is

If

is 0.01 and

is

, there may be one sensor node in

the area.

We partitioned the space between the source node and sink

node into small regions with a fixed area, as shown in Fig. 3(b).
One region is shaded in the figure. This region is determined to
satisfy the following conditions.

1) The region has at least one sensor node.
2) The maximum distance between sensor nodes in two ad-

joining regions is equal to radio range,

. Equivalently,

the diagonal of two adjoining regions is

, as shown in

Fig. 3(b).

If the aforementioned conditions are met, sensor nodes in two
adjoining regions can communicate with each other. If the max-
imum width of the region is obtained, the minimum number of
hops to the sink node can also be obtained.

The area of a region is

. A smaller

increases the width of a region

(

) but decreases the area of a region, and the expected

number of sensor nodes in a region. Based on the assumption
of deploying sensor nodes according to a Poisson process, the
expected number of nodes in the region is

The density, , and the radio range,

, are constant and we can

obtain the minimum

satisfying condition 1)

Because

increases monotonously in a given range of ,

we can obtain the minimum

by solving

The width of a region is

and the expected number of

regions to the sink node is

where

is the distance to the sink node. The expected number

of hops to the sink node is one less than the expected number of
regions

We can obtain the expected delay to the sink node by multi-
plying

by the average delay of single hop communication.

The expected delay to the sink node may be used as the approx-
imate minimum deadline.

For example, there are networks for which the area is

and the number of sensor nodes is 100. The sink node is

located in the center of the networks. The radio range is

.

The density of sensor nodes, , may be 0.01, because there are
100 sensor nodes in

. The

maximum distance between a source node and the sink node is
about

. The minimum

is about 0.348,

and

is 6. If the average delay of single hop communication

is

, we can set the deadline of a packet as

.

Authorized licensed use limited to: Imperial College London. Downloaded on June 07,2010 at 19:37:30 UTC from IEEE Xplore. Restrictions apply.

8

IEEE TRANSACTIONS ON INDUSTRIAL INFORMATICS, VOL. 5, NO. 1, FEBRUARY 2009

TABLE I

S

IMULATION

P

ARAMETERS

IV. E

XPERIMENTAL

R

ESULTS

GloMoSim [35] was used to evaluate the performance of

EARQ. This is a very fast, effective, discrete-event simulator
for simulating wireless communications. It has a detailed
propagation model, radio, and MAC layers. Table I describes
the detailed simulation parameters. We used the two-ray path
loss model for the radio propagation model in the simulations.
The two-ray model considers both the direct path and the
ground reflection path [36]. In the simulations, we used the
signal-to-noise ratio threshold (SNRT) model for the signal
reception model. If signal-to-noise ratio (SNR) of a packet ex-
ceeds the threshold, it receives the packet error-free. Otherwise,
the packet is dropped [37].

We used IEEE 802.11 DCF for the MAC layer pro-

tocol. EARQ and other protocols compared in the paper
are table-driven routing protocols for static wireless networks
such as wireless industrial sensor networks. The relative
performance of these protocols for such networks is largely in-
dependent of MAC layer protocols such as CSMA, MACA, and
802.11 DCF [38]. Therefore, simulation with a single common
MAC protocol is sufficient for the performance comparison of
the routing protocols in these networks.

Every sensor node sent data to the sink node at an interval

of one second. Every node sent a beacon message at an interval
of 10 s. In EAR and EARQ, we used the energy cost function

, where

and

.

The simulation was performed with three types of packet:

1) packets with a deadline;
2) packets with a reliability requirement;
3) packets with both a deadline and a reliability requirement.

The deadline used in the simulations with the first and third

packet type was

. This was determined based on the den-

sity of sensor nodes, the size of the field, the radio range and
the average delay of single hop communication. We explained
the method for determining the deadline in Section III-C. In the
simulations of EARQ with the second and third packet type,
the reliability,

, was 1.0, 0.9, 0.8, and 0.7. To evaluate the

energy awareness of EARQ, we compared EARQ with EAR
[27] for each type of packet. To compare EARQ with other
real-time routing protocols, a simulation of SPEED [16] was
performed with the first type of packet. To compare the protocol
with other QoS routing protocols, a simulation of EQoS [21] and
MMSPEED [20] was performed with the third type of packet.
SPEED and MMSPEED [20] protocols use the speed, instead
of a deadline. For the SPEED and MMSPEED protocols, we set

Fig. 4. Performance of EARQ according to frequency of beacon messages.

Fig. 5. Ratio of packets which missed the deadline, considering deadline only.

the speed as

. We obtained the speed by dividing the av-

erage distance (

) between nodes by the deadline

.

Exchanging beacon messages increases network traffic and

hogs the bandwidth for data packets. When beacon messages are
exchanged too frequently, this degrades EARQ performance. By
contrast, when beacon messages are exchanged too infrequently,
the nodes’ states are not updated in time. To select an appro-
priate frequency, we simulated EARQ with various frequencies.
The number of nodes in this simulation was 100. Fig. 4 shows
the result. We selected 10 s as the frequency of beacon mes-
sages, according to the result.

A. Experiments on Packets Considering Deadline Only

Fig. 5 shows the ratio of packets which missed the dead-

line, for EARQ, EAR, and SPEED, when only the deadline of a
packet is considered. As shown in the figure, EARQ and SPEED
delivered more packets in time than EAR, regardless of the den-
sity of nodes. There was little difference between EARQ and
SPEED. As the density of nodes increased, the average number
of hops to the sink node also increased. This resulted in an in-
crease of the missed deadline ratio.

EARQ is more suitable than EAR for transmitting real-time

packets, as shown in Fig. 5. However, it may be impractical if

Authorized licensed use limited to: Imperial College London. Downloaded on June 07,2010 at 19:37:30 UTC from IEEE Xplore. Restrictions apply.

HEO et al.: EARQ: ENERGY AWARE ROUTING FOR REAL-TIME AND RELIABLE COMMUNICATION

9

Fig. 6. Average energy expenditure of nodes, considering deadline only.

Fig. 7. Ratio of lost packets, considering reliability only.

more energy is expended by EARQ than EAR, because energy
is the most important resource in sensor nodes. Fig. 6 shows
the average energy expenditure of nodes. The average energy
expenditure of nodes in EARQ is similar to that of EAR. As
shown in Figs. 5 and 6, EARQ delivers packets in time, while
expending less energy than SPEED.

B. Experiments on Packets Considering Reliability Only

Fig. 7 shows the ratio of lost packets for EARQ and EAR,

when only the reliability of a packet is considered in EARQ.
Compared to EAR, EARQ delivered more packets to the sink
node successfully. In EARQ, as the reliability,

, increased,

the number of lost packets decreased. As the density of nodes
decreased, the distance among nodes increased, and the proba-
bility of constructing a path to the sink node decreased. There-
fore, the ratio of lost packets decreased as the density of nodes
increased.

Fig. 8 shows the energy expenditure of EARQ and EAR. The

number of redundant packets for the backup path depended on
the reliability,

. As the number of redundant packets increased,

Fig. 8. Average energy expenditure of nodes, considering reliability only.

Fig. 9. Ratio of packets that missed the deadline or were lost, considering both
deadline and reliability.

the energy expenditure also increased. Therefore, as the relia-
bility,

, increased, the energy expenditure increased.

C. Experiment on Packets Considering Both Deadline
and Reliability

Fig. 9 shows the ratio of packets that missed the deadline or

were lost, when both the deadline and reliability of a packet
were considered. EARQ

showed a better result than

EAR, EQoS, and MMSPEED. The result for EQoS was similar
to that for EARQ

, and the result for MMSPEED was

similar to that for EARQ

. The reason that EQoS and

MMSPEED are inferior to EARQ is that they select a next node
based only on the distance to the sink node and the deadline of
a packet, without considering different delays and error rates of
a link between nodes.

Fig. 10 shows the average energy expenditure. EARQ showed

better results than EQoS and MMSPEED. In EQoS and MM-
SPEED, every packet is sent twice at the source node, because
they do not consider the reliability of a path to the sink node.
However, EARQ estimates the reliability of a path to the sink
node and only sends a packet twice if the selected neighbor does
not satisfy the reliability,

, of a packet. In this simulation, about

Authorized licensed use limited to: Imperial College London. Downloaded on June 07,2010 at 19:37:30 UTC from IEEE Xplore. Restrictions apply.

10

IEEE TRANSACTIONS ON INDUSTRIAL INFORMATICS, VOL. 5, NO. 1, FEBRUARY 2009

Fig. 10. Average energy expenditure of nodes, considering both deadline and
reliability.

Fig. 11. Expected number of packets delivered in time to the sink node suc-
cessfully with 1 mWhr.

55% of packets were sent twice, in the case where the reliability,

.

Fig. 11 shows the expected number of packets delivered to the

sink node successfully with 1 mWhr. The figure shows the en-
ergy efficiency of each protocol. In addition, the figure shows the
trade-off between energy and QoS in EARQ. EARQ which does
not consider reliability

is only better than others if

energy efficiency is considered. However, if a desired reliability,

, is required, EARQ which considers reliability is useful, and

the reliability,

, can be selected according to the energy expen-

diture requirements.

V. C

ONCLUSION AND

F

UTURE

W

ORK

Dynamic and easily maintained industrial control applica-

tions can be achieved by applying WISNs to industrial con-
trol in manufacturing plants. Industrial control requires real-
time, reliable transmission of sensing data and commands. De-
layed or lost data may lead to incorrect or delayed responses
to the sensing data. Therefore, as well as existing requirements
of WSNs, new requirements such as real-time, reliable delivery
must be considered while designing applications for WISNs
controlling data transmission.

This paper proposed EARQ, an energy aware routing pro-

tocol for real-time, reliable communication in WISNs. EARQ
provides real-time communication without compromising the
energy awareness of the existing energy aware routing protocol,
EAR. It selects a path that expends less energy than others,
among paths that deliver a packet in time. Sometimes, it selects
a path that expends more energy than the optimal path, because
the path is selected at random, according to a probability. This
enables even distribution of energy expenditure to sensor nodes.
In addition, EARQ provides efficient, reliable communication,
because it only sends a redundant packet via an alternate path
if the reliability of a path is less than a predefined value. The
deadline, which is the maximum tolerable packet delay, must be
carefully selected. The deadline must be the same as or longer
than the minimum network delay. This paper estimated the min-
imum delay, to select a deadline given the density of sensor
nodes and radio range. Simulation results showed that EARQ
performs better than existing QoS routing protocols, in terms of
reducing the number of packets that missed deadlines or were
lost, while considering energy awareness.

QoS routing for heterogeneous (hybrid) wireless/wired

industrial sensor networks will be studied in a future work. In
practical environments, networks can comprise various net-
works such as WLAN, Zigbee, Bluetooth, and wired networks.
They may be connected to the Internet [39]. Each protocol uses
a different MAC layer protocol and has differing characteristics.
Therefore, a new protocol that ensures a tolerable end-to-end
delay for real-time communications in such hybrid networks is
necessary.

R

EFERENCES

[1] M. Sveda, P. Benes, R. Vrba, and F. Zezulka, “Introduction to indus-

trial sensor networking,” in Handbook of Sensor Networks: Compact
Wireless and Wired Sensing Systems

.

Boca Raton, FL: CRC, 2005,

pp. 25–35.

[2] A. Weaver, “Survey of industrial information technology,” in Proc.

Annu. Conf. IEEE Industrial Electronics Society (IECON)

, 2001, vol.

3, pp. 2056–2061.

[3] T. Brooks, “Wireless technology for industrial sensor and control net-

works,” in Proc. Sensor for Industry Conf., 2001, pp. 73–77.

[4] A. Willig, K. Matheus, and A. Wolisz, “Wireless technology in indus-

trial networks,” Proc. IEEE, vol. 93, no. 6, pp. 1130–1151, Jun. 2005.

[5] I. Howitt, W. W. Manges, P. T. Kuruganti, G. Allgood, J. A. Gutierrez,

and J. M. Conrad, “Wireless industrial sensor networks: Framework for
QoS assessment and QoS management,” ISA Trans., vol. 45, no. 3, pp.
347–359, 2006.

[6] I. F. Akyildiz, T. Melodia, and K. R. Chowdhury, “A survey on wire-

less multimedia sensor networks,” Comput. Netw., vol. 51, no. 4, pp.
921–960, 2007.

[7] L. Krishnamurthy, R. Adler, P. Buonadonna, J. Chhabra, M. Flanigan,

N. Kushalnagar, L. Nachman, and M. Yarvis, “Design and deployment
of industrial sensor networks: Experiences from a semiconductor plant
and the north sea,” in Proc. Int. Conf. Embedded Networked Sensor
Systems (SenSys)

, 2005, pp. 64–75.

[8] M. Kohvakka, M. Hannikainen, and T. D. Hamalainen, “Wireless

sensor network implementation for industrial linear position me-
tering,” in Proc. Euromicro Conf. Digital System Design (DSD), 2005,
pp. 267–275.

[9] H.-J. Korber, H. Wattar, and G. Scholl, “Modular wireless real-time

sensor/actuator network for factory automation applications,” IEEE
Trans. Ind. Informat.

, vol. 3, no. 2, pp. 111–119, May 2007.

[10] S. Vitturi, I. Carreras, D. Miorandi, L. Schenato, and A. Sona, “Experi-

mental evaluation of an industrial application layer protocol over wire-
less systems,” IEEE Trans. Ind. Informat., vol. 3, no. 4, pp. 275–288,
Nov. 2007.

[11] I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, “Wire-

less sensor networks: A survey,” Comput. Netw., vol. 38, no. 4, pp.
393–422, 2002.

[12] J. Al-Karaki and A. Kamal, “Routing techniques in wireless sensor

networks: A survey,” IEEE Wireless Commun., vol. 11, no. 6, pp. 6–28,
Dec. 2004.

Authorized licensed use limited to: Imperial College London. Downloaded on June 07,2010 at 19:37:30 UTC from IEEE Xplore. Restrictions apply.

HEO et al.: EARQ: ENERGY AWARE ROUTING FOR REAL-TIME AND RELIABLE COMMUNICATION

11

[13] C. R. Lin, “QoS routing in ad hoc wireless networks,” in Proc. Annu.

IEEE Conf. Local Computer Networks (LCN)

, 1998, pp. 31–41.

[14] Q. Xue and A. Ganz, “Ad hoc QoS on-demand routing (aqor) in mo-

bile ad hoc networks,” J. Parallel Distrib. Comput., vol. 63, no. 2, pp.
154–165, 2003.

[15] T. Facchinetti, L. Almeida, G. C. Buttazzo, and C. Marchini,

“Real-time resource reservation protocol for wireless mobile ad hoc
networks,” in Proc. IEEE Int. Real-Time Systems Symp. (RTSS), 2004,
pp. 382–391.

[16] T. He, J. A. Stankovic, C. Lu, and T. Abdelzaher, “SPEED: A stateless

protocol for real-time communication in sensor networks,” in Proc. Int.
Conf. Distributed Computing Systems (ICDCS)

, 2003, pp. 46–55.

[17] K. Akkaya and M. Younis, “An energy-aware QoS routing protocol for

wireless sensor networks,” in Proc. Int. Conf. Distributed Computing
Systems (ICDCS)

, 2003, pp. 710–715.

[18] K. Akkaya and M. Younis, “Energy-aware delay-constrained routing

in wireless sensor networks,” Int. J. Commun. Syst., vol. 17, no. 6, pp.
663–687, 2004.

[19] H. M. Ammari and S. K. Das, “Trade-off between energy savings and

source-to-sink delay in data dissemination for wireless sensor net-
works,” in Proc. ACM Int. Symp. Modeling, Analysis and Simulation
of Wireless and Mobile Systems (MSWiM)

, 2005, pp. 126–133.

[20] E. Felemban, C.-G. Lee, and E. Ekici, “MMSPEED: Multipath multi-

speed protocol for QoS guarantee of reliability and timeliness in wire-
less sensor networks,” IEEE Trans. Mobile Comput., vol. 5, no. 6, pp.
738–754, Jun. 2006.

[21] A. Mahapatra, K. Anand, and D. P. Agrawal, “QoS and energy aware

routing for real-time traffic in wireless sensor networks,” Comput.
Commun.

, vol. 29, no. 4, pp. 437–445, 2006.

[22] J. Heo, S. Yi, G. Park, Y. Cho, and J. Hong, “EAR-RT: Energy aware

routing with real-time guarantee for wireless sensor networks,” in
Lecture Notes in Computer Science

.

New York: Springer, 2006, vol.

3994, pp. 946–953.

[23] G. Cena, I. Bertolotti, A. Valenzano, and C. Zunino, “Evaluation of

response times in industrial WLANs,” IEEE Trans. Ind. Informat., vol.
3, no. 3, pp. 191–201, Aug. 2007.

[24] W. R. Heinzelman, A. Chandrakasan, and H. Balakrishnan, “Energy-

efficient communication protocol for wireless microsensor networks,”
in Proc. Hawaii Int. Conf. System Sciences (HICSS), 2000, pp. 10–20.

[25] C. Schurgers and M. B. Srivastava, “Energy efficient routing in wire-

less sensor networks,” in Proc. IEEE Military Communications Conf.
(MILCOM)

, 2001, pp. 357–361.

[26] D. Ganesan, R. Govindan, S. Shenker, and D. Estrin, “Highly-resilient,

energy-efficient multipath routing in wireless sensor networks,” SIG-
MOBILE Mobile Comput. Commun. Rev.

, vol. 5, no. 4, pp. 11–25,

2001.

[27] R. Shah and J. Rabaey, “Energy aware routing for low energy ad hoc

sensor networks,” in Proc. IEEE Wireless Communications and Net-
working Conf. (WCNC)

, 2002, pp. 350–355.

[28] J.-H. Chang and L. Tassiulas, “Maximum lifetime routing in wireless

sensor networks,” IEEE/ACM Trans. Netw., vol. 12, no. 4, pp. 609–619,
Aug. 2004.

[29] G. Park, S. Yi, J. Heo, W. C. Choi, G. Jeon, Y. Cho, and C. Shim,

“Energy aware routing with dynamic probability scaling,” in Lecture
Notes in Computer Science

.

New York: Springer, 2005, vol. 3642,

pp. 662–670.

[30] C. Lu, B. Blum, T. Abdelzaher, J. Stankovic, and T. He, “RAP: A

real-time communication architecture for large-scale wireless sensor
networks,” in Proc. IEEE Real-Time and Embedded Technology and
Applications Symp. (RTAS)

, 2002, pp. 55–66.

[31] T. He, C. Huang, B. M. Blum, J. A. Stankovic, and T. Abdelzaher,

“Range-free localization schemes for large scale sensor networks,” in
Proc. Annu. Int. Conf. Mobile Computing and Networking

, 2003, pp.

81–95.

[32] Y. Zhang and L. Cheng, “Place: Protocol for location and coordinate

estimation: A wireless sensor network approach,” Comput. Netw., vol.
46, no. 5, pp. 679–693, 2004.

[33] K. Yedavalli, B. Krishnamachari, and L. Venkatraman, “Fast/fair mo-

bile localization in infrastructure wireless sensor networks,” SIGMO-
BILE Mobile Comput. Commun. Rev.

, vol. 11, no. 1, pp. 29–40, 2007.

[34] S. Ross, Stochastic Processes.

New York: Wiley., 1983.

[35] X. Zeng, R. Bagrodia, and M. Gerla, “GloMoSim: A library for parallel

simulation of large-scale wireless networks,” ACM SIGSIM Sim. Dig.,
vol. 28, no. 1, pp. 154–161, 1998.

[36] T. S. Rappaport, Wireless Communications, Principles and Practice.

Englewood Cliffs, NJ: Prentice-Hall, 1996.

[37] M. Takai, J. Martin, and R. Bagrodia, “Effects of wireless physical layer

modeling in mobile ad hoc networks,” in Proc. ACM Int. Symp. Mobile
Ad Hoc Networking & Computing (MobiHoc)

, 2001, pp. 87–94.

[38] E. Royer, S.-J. Lee, and C. Perkins, “The effects of MAC protocols on

ad hoc network communication,” in Proc. IEEE Wireless Communica-
tions and Networking Conf. (WCNC)

, 2000, pp. 543–548.

[39] S. Eberle, “Adaptive internet integration of field bus systems,” IEEE

Trans. Ind. Informat.

, vol. 3, no. 1, pp. 12–20, Feb. 2007.

Junyoung Heo

received the B.E. degree in computer

engineering from Seoul National University, Seoul,
Korea, in 1998, where he is currently, he is pursuing
the Ph.D. degree.

He has been with School of Computer Science

and Engineering, Seoul National University, since
2002. From 1998 to 2002, he worked as a Software
Engineer for Nadatel and SPSoft/Inzen in Korea.
His research interests include operating systems,
wireless sensor networks, embedded systems, and
fault tolerance.

Jiman Hong

received the B.S. degree in computer

science from Korea University, Seoul, Korea, in 1994
and the M.E. and Ph.D. degrees in computer engi-
neering from Seoul National University in 1997 and
2003, respectively.

He has been with School of Computing, Soongsil

University, Seoul, Korea, since 2007, where currently
he is an Assistant Professor. From 2004 to 2007, he
was an Assistant Professor of Kwangwoon Univer-
sity, Seoul. From 2000 to 2003, he served as a Chief
of Technical Officer in the R&D center of GmanTech

Incorporated Company, Seoul. His research interests include embedded oper-
ating systems, fault tolerance computing systems, distributed computing sys-
tems, and sensor network systems.

Yookun Cho

(M’91) received the B.E. degree from

Seoul National University, Seoul, Korea, in 1971 and
the Ph.D. degree in computer science from the Uni-
versity of Minnesota at Minneapolis in 1978.

He has been with the School of Computer Science

and Engineering, Seoul National University, since
1979, where he is currently a Professor. He was
a Visiting Assistant Professor at the University
of Minnesota during 1985 and a director of the
Educational and Research Computing Center at
Seoul National University from 1993 to 1995. His

research interests include operating systems, algorithms, system security, and
fault-tolerant computing systems.

Dr. Cho was president of the Korea Information Science Society during 2001.

He was a member of the program committee of the IPPS/SPDP ’98 in 1997 and
the International Conference on High Performance Computing from 1995 to
1997.

Authorized licensed use limited to: Imperial College London. Downloaded on June 07,2010 at 19:37:30 UTC from IEEE Xplore. Restrictions apply.