This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts

for publication in the IEEE ICC 2010 proceedings

RELAX: An Energy Efficient Multipath Routing Protocol for

Wireless Sensor Networks
Bashir Yahya and Jalel Ben-Othman
University of Versailles, PRiSM Laboratory
45 Avenue des Etats-Unis, 78000 Versailles, France
Emails:{baya, jbo}@prism.uvsq.fr

Abstract— This paper presents an energy efficient multipath delivery. In these approaches, multiple copies of data are sent
routing protocol specifically designed for wireless sensor networks along different paths, allowing for resilience to path failures.
(referred as RELAX). RELAX protocol tries to utilize the Both of these uses of multipath routing are applicable to WSNs.
relaxation phenomenon of certain batteries to increase the battery Load balancing can spread energy utilization across nodes in a
lifetime and hence increasing the overall lifetime of the sensor network, potentially resulting in longer lifetimes. Duplicating
network. Relaxation periods enable the battery to recover a data delivery along multiple paths can result in more accurate
portion of its lost power; it has been proven that the intermittent tracking in surveillance applications, at the cost of additional
operation of some alkaline batteries increases its lifespan by about expense in energy [5][6].
28%. RELAX uses a link cost function that depends on current
residual energy, available buffer size, and link quality (in terms of In this paper, we propose RELAX protocol: an energy
Signal-to-Noise ratio) to predict the best next hop during the path efficient multipath routing protocol for WSNs to recover from
construction phase. RELAX routes data across multiple paths to path failures and achieves load balancing through the
balance the energy consumed across multiple nodes and to increase distribution of the traffic across a set of node-disjoint paths in
the throughput as well as minimizing packet end-to-end delay. order to efficiently use the node’s battery power. RELAX
Before transmitting the data, RELAX protocol adds data protocol utilizes the relaxation phenomenon of the sensor node’s
redundancy through a light weight Forward Error Correction battery to increase the battery lifetime and hence increasing the
(FEC) technique to increase the protocol reliability and resiliency overall lifetime of the sensor network. Relaxation periods enable
to path failures. Many simulation experiments have been cried out
the battery to recover a portion of its lost power; it has been
to evaluate the protocol performance. Results show that RELAX
protocol achieves lower energy consumption, lower packet delay,
proven that the intermittent operation of an alkaline battery
higher throughput, and long node lifetime duration compared to increases its lifetime by about 28% [7]. RELAX uses the
other protocols. residual energy, node available buffer size, and Signal-to-Noise
Ratio (SNR) to predict the next hop through the path
Keywords- Multipath Routing; Energy Efficiency; Forward construction phase. RELAX protocol adds data redundancy to
Error Correction;Wireless Sensor Networks, Relaxation Effect; the original data message and uses multiple paths to transmit the
data. Using this technique, failure in one or more paths can be
I. INTRODUCTION recovered without invoking data retransmission. RELAX splits
Routing in sensor networks is a very challenging task and up the transmitted message into number of segments of equal
different from routing in either wired or other wireless networks, size, add XOR-based FEC codes (data redundancy), and then
because of the many special characteristics of WSNs. Due to transmits it across multiple paths simultaneously. This increases
these special characteristics, many routing solutions specifically resiliency to path failures and increases the probability that an
designed for WSNs have been proposed (refer to [1], [2], and [3] enough portion of the packet is received at the destination to
for a surveys on routing in WSNs). In these proposals, the recover the original data message.
unique properties of the WSNs have been taken into account. The remainder of this paper is organized as follow: In section
These routing techniques can be classified according to the II, we describe and discuss some of the related work. We detail
protocol operation into negotiation based, query based, QoS our proposal in section III. Section IV presents the performance
based, and multipath based. The negotiation based protocols evaluation. Finally, we conclude the paper in section V.
have the objective to eliminate the redundant data by include
high level data descriptors in the message exchange. In query II. RELEATED WORK
based protocols, the sink node initiates the communication by
broadcasting a query for data over the network. The QoS based Routing in sensor networks has received a great attention
protocols allow sensor nodes to make a tradeoff between the from the research community, where a large set of proposals are
energy consumption and some QoS metrics before delivering the being made. The literature on multipath routing is vast [5], and
data to the sink node [4]. Finally, multipath routing protocols use in this section we do not give a comprehensive summary of the
multiple paths rather than a single path in order to improve the related work, instead we present and discuss some proposals
network performance in terms of reliability and robustness. related to our protocol.
Multipath routing establishes multiple paths between the source- One of the early proposed multipath routing protocols is the
destination pair. Multipath routing protocols have been Directed Diffusion [8]. Directed diffusion is a data-centric routing
discussed in the literature for several years now [5]. Classical protocol, where all communication is for named data. All sensor
multipath routing has been explored for two reasons. The first nodes are application aware and maintain an interest cache. This
for load balancing; the traffic between the source and destination enables diffusion to achieve energy savings by selecting empirically
is split across multiple disjoint paths. The second use of good paths and by caching and processing data in the network.
multipath routing is to increase likelihood of reliable data However, directed diffusion requires periodic interest broadcast and

978-1-4244-6404-3/10/$26.00 ©2010 IEEE

Authorized licensed use limited to: SRM University. Downloaded on July 14,2010 at 11:45:12 UTC from IEEE Xplore. Restrictions apply.
 This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the IEEE ICC 2010 proceedings

path reinforcement, which cause more energy consumption in sensor node. The operation of the battery depends on different
handling such control traffic. factors. These factors include battery dimension, type of
electrodes, diffusion rate of the active materials in the
In [9], authors proposed an N-to-1 multipath routing protocol
electrolyte, discharge rate, … etc. The battery performance with
that finds different node-disjoint paths between a sink and a
regard to discharge pattern depends on two effects [11]: i) the
source node. Nodes are arranged in a spanning tree structure
capacity effect which depends on the battery actual capacity and
with the sink as the root. The protocol finds multipaths by
the discharge rate; ii) the recovery effect due to the battery
traversing the tree. The multiple paths are used to distribute the
recovery during idle periods (i.e. periods during which the
traffic in order to improve the reliability and security of the data
current drawn is drastically reduced or completely shut off). In
transmission. However, the N-to-1 routing protocol does not
this section we discuss some design issues that can be used to
take into account the node’s energy level in its cost function.
prolong the battery lifetime.
Furthermore, it lacks of an efficient load balancing mechanism
to distribute the traffic in an energy efficient manner. 1) Current Capacity
In [10], authors have proposed an energy efficient multipath The most important factor that greatly effects the lifetime of
routing protocol for WSNs with multiple sink nodes. To make any battery is the amount of current drawn from the battery
decisions for the next hope, the protocol uses a cost function that (discharge rate). Every battery has a specified discharging rate
is a function of residual energy and hop count. After the protocol set by the manufacture. Drawing higher currents than this rate
initialization, the path construction phase is started. The source decreases the battery lifetime significantly. Thus, to avoid
node uni-casts a route request message to each of its neighbors. battery lifetime degradation, the amount of the current drawn
However multiple routes construction and maintenance are should be kept under the manufacture specifications.
costly in terms of energy, because of the high control overhead. 2) Relaxation Phenomenon
Improving energy efficiency in routing protocols mainly is As proven experimentally in [7], the battery relaxation
based on reducing the overhead caused by the control traffic- periods can be used to mitigate (to a certain extent) the effect of
during the routes construction and maintenance phases- as well high discharge rates on the battery lifetime. If the current drawn
as selecting good routes that reduce energy through an from a battery is reduced or completely cut-off, the diffusion and
appropriate cost function. In our proposal we try to minimize the transport of active materials catches up with the depletion caused
energy consumption through distributing and balancing the load by the discharge. This phenomenon is called the relaxation
across the multiple paths. The multiple paths are constructed effect, and enables the battery to recover a portion of its lost
through the use of a cost function that based on multiple criteria, capacity. We try to utilize this effect in prolonging the sensor
such as residual energy, remaining buffer size and signal-to- network lifetime through prolonging the battery lifetime. We
noise ratio. In the next section we detail our proposal. assume that each sensor node in the network is powered by two
alkaline batteries, where each battery supplies power to the
III. DESCRIPTION OF RELAX PROTOCOL sensor node for a certain a mount of time. Operating the sensor
In this section, we first define some assumptions. Then, we node this way gives the battery a chance to recover a portion of
provide the details of multiple paths discovery and refreshment, its lost power during the rest periods, which significantly
as well as the traffic allocation and data transmission. increases the battery lifetime, and hence increasing the lifetime
of the whole sensor network.
A. Assumptions 3) Battery Model
We assume that we have N identical sensor nodes are To study the effect of the relaxation phenomenon of the
distributed randomly in the sensing filed. All nodes have the alkaline batteries on our routing protocol, we need to develop an
same transmission range, and have enough battery power to analytical battery model that captures the real battery
carry their sensing, computing, and communication activities. characteristics including the capacity effect and recovery effect.
Each sensor node is powered through the use of two alkaline We use the model developed by Rakhmatov and Vrudhula [12].
batteries, which are used to operate the sensor node alternatively This model is described by the following equation. Refer to [12]
(i.e. use the first battery for a certain period of time, then shut it for more details.
off and use the second battery, and continue this process each 15
minutes). The network is fully connected and dens (i.e. data can ⎛ ⎛ ⎞⎞
⎜ ⎜ β 2m 2 −
β 2m2 ⎟⎟
be sent from one node to another in a multihop bases). The links ⎜ 10
⎜ − L πe L ⎟⎟
between nodes are bidirectional links. Each node is welling to α = 2 I L ⎜1 + 2∑ ⎜ e − ⎟⎟
⎜ m =1
⎜ L ⎟⎟
participate in the communication process by forwarding data.
⎜ ⎜ π −1+ 1+ π 2 2 ⎟⎟
Furthermore, we assume that the sensor nodes are stationary for ⎝ ⎝ β m ⎠⎠
their lifetime. Additionally, at any time, we assume that each
sensor node is able to compute its residual energy, and its Where, α and β are two parameters used to compute the
available buffer size, as well as record the link quality between battery lifetime; α is related to the battery capacity, and β
itself and its neighboring node in terms of signal-to-noise ratio regards to the non-linear battery behavior during charging and
(SNR). By examining recent link performance data, predications discharging periods, L is the battery lifetime, and I is the
and decisions about path stability may be made. discharging current.
B. Battery Issues To predict the battery lifetime for a given discharge current,
one first needs to estimate α and β from experimental data. For
The lifetime of a sensor node is determined by the lifetime of
alkaline batteries, which are usually employed in WSN devices,
the battery used to supply power to this sensor node. Therefore
prolonging the lifetime of the battery prolongs the lifetime of the we use α = 245,910, and β = 4034. These values are taken from
reference [13].

Authorized licensed use limited to: SRM University. Downloaded on July 14,2010 at 11:45:12 UTC from IEEE Xplore. Restrictions apply.
 This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the IEEE ICC 2010 proceedings

enough information about which of its neighbours can

provide it with the highest quality data. Each sensor
Figure 1. HELLO message structure node maintains and updates its neighbouring table
during this phase. The neighbouring table contains
information about the list of neighbouring nodes of the
sensor node. Figure 1 illustrates the structure of hello
Figure 2. RREQ message structure message. The link quality field is expressed in terms of
signal-to-noise ratio (SNR) for the link between the
source node and its neighbour. Hop count gives the
distance in hops for the message from its originator.

• Primary Path discovery phase: After initialization

phase, each sensor node has enough information to
compute the cost function for the links to its
neighbours. Then, the sink node locally computes its
preferred next hop node using the link cost function,
and sends out a RREQ message to its most preferred
next hop (figure 2 shows the structure of the RREQ
Figure 3. Example of Path Discovery message). Similarly, through the link cost function,
the preferred next hop node of the sink computes
C. Link cost function
locally its most preferred next hop in the direction of
The link cost function is used by the node to select the next the source node, and sends out a RREQ message to its
hop during the path discovery phase. We use a cost function next hop, the operation continues until source node
such as presented in [10] with some changes. Let Nx be the set (see figure 3).
of neighbors of node x. Then our cost function includes an
energy factor, available buffer factor, and interference factor
• Alternative Paths discovery phase: For the second
with appropriate weights (α, β, and γ).
alternate path, the sink sends alternate path RREQ
Next hop = max y ∈ Nx {αEresd, y + βBbuffer, y + γIinterference, xy}, message to its next most preferred neighbour. To avoid
Where, Eresd, y is the current residual energy of node y, where having paths with shared nodes, we limit each node to
y ∈ Nx, Bbuffer, y is the available buffer size of node y, and accept only one RREQ message. For those nodes that
Iinterference, xy is the SNR for the link between nodes x and y. In receive more than one RREQ message, only accept the
this cost function, we only consider the residual energy of node y first RREQ message and reject the remaining messages
but not node x. Because node y consumes energy for data (see figure 3, for an example of path construction. In
reception and transmission if it is selected as a next hop for node this example Node 9 computes its next preferred
x. We do not consider node x, because whatever node y is, node neighbour finds it Node 7. Node 9 generates RREQ
x still needs to spend the same amount of energy on data message and forwards to node 7, but node 7 has been
transmission [10]. included in the primary path, then node 7 simply
The total cost (Ctotal) for a path P consists of a set of K nodes responds to node 9 with an INUSE message indicating
is the sum of the individual link costs l(xy)i, i ∈ K along the path. that node 7 is already selected in a routing path.
Then we have: Immediately node 9, searches its neighbouring table
and computes the next preferred neighbour, which will
K −1
be node 5, and sends out RREQ message to it. Node 5
C total , P = ∑ l ( xy )i accepts the message and continues the operation in the
i =1 direction of the source node).
D. Paths Discovery Phase
E. Route Refreshing
Based on the idea of the directed diffusion [8], the sink node
To keep multiple paths alive, the source node periodically
starts the multiple paths discovery phase to create a set of
floods a KEEPALIVE message (similar to HELEO message
neighbors that able to forward data towards the sink from the
except that the Hop-Count field is replaced by the Next-Hop-ID)
source node. The constructed multipaths are node-disjoint paths
over multiple paths to keep them alive. The frequency of the
(i.e. have no common nodes except the source and the
KEEPALIVE message determines how quickly the routing
destination). In multipath routing, node-disjoint paths are usually
protocol recovers from failures on the primary path.
preferred because they utilize the most available network
resources, and hence are the most fault-tolerant. If an F. Traffic allocation and Data Transmission
intermediate node in a set of node-disjoint paths fails, only the
path containing that node is affected, so there is a minimum After multiple paths have been discovered, the source node
impact to the diversity of the routes. begins to transmit data messages to the sink. To deliver data to
the sink node, we use a subset of the available paths to transfer
The path discovery procedure is executed according to the the message in order to distribute the load over the nodes, and to
following phases: avoid the fast battery drains because of the extensive use of the
• Initialization phase: Each sensor node broadcast a same path to carry a long message for long time. We split up the
HELLO message to its neighbours in order to have message into small parts (N equal sized segments), add error

Authorized licensed use limited to: SRM University. Downloaded on July 14,2010 at 11:45:12 UTC from IEEE Xplore. Restrictions apply.
 This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the IEEE ICC 2010 proceedings

correction codes (M XOR-based correction codes (data

redundancy)), and then transmit it across multiple paths
simultaneously to increase resiliency to path failures and ensure
that an essential portion of the packet is received at the
destination without incurring excessive delay through data
retransmission. At the sink node, the parts are collected,
reassembled, and the original message is recovered. More
details are given below.

1) Paths Selection
After the completion of paths discovery phase and the paths
have been constructed, we need to select a set of paths from the
N available paths to transfer the traffic from the source to the
destination with a desired bound of data delivery given by α. To
find the number of required paths, we assume that each path is Figure 4. Packet Segmentation (original message and correction codes)
associated with some rate pi (i=1,2, .. n) that corresponds to the
probability of successfully delivering a message to the 3) Message Forwarding and Recovery
destination. Following the work done in [14], the number of After computing the XOR-based correction codes, the
required paths is calculated as: segments of the original message (S1, S2, S3, … Sk) along with the
N N error correction codes (C0, C1, C2, C3, … CM) are sent out across
k = xα . ∑i =1
p i (1 − p i ) + ∑ p i
i =1
the selected multiple paths. In [16], authors have proven that if
M or less segments are lost out of the N + M total data and
overhead (correction codes), the original N message segments
Where xα is the corresponding bound from the standard can be recovered using appropriate linear transformations (in our
normal distribution for different level of α. Table I lists some case through XOR operation). The original message could be
values for xα.. reconstructed as follow:
As the paths are arranged according to their quality during S1 = C0 ⊕ C2
the path construction phase (the first constructed path is the best,
then the second, and so on), we select the first k paths out of the S2 = C0 ⊕ C3
.
N available paths to be used to transfer the gathered data. .
.
SM = C0 ⊕ C1
2) Message Segmentation and FEC Codes Generation
The data message is split up into k equal sized segments (S0, Figure 5 shows the packet segmentation and the fields in
S1, S2, … Sk-1), and over head part of M+1 (where M < k) error each segment. Segment Length (SL) field indicates the length of
correction codes (C0 C1, C2, C3, … CM) of same size as the data each segment. The segments must have a length that is a
segment are added to the original message (see figure 4). The multiple of 8, to allow proper offset specification. Identification
data segments and error correction codes are of the same size (l field (ID) is a unique identifier assigned to each message being
bytes) and should be multiple of 8. Correction codes are fragmented. The field is used by the sink node to reassemble
calculated as a function of the information bits to provide messages without accidentally mixing segments from different
redundant information. We use an XOR-based coding algorithm messages. More Segment (MS), this bit is set to 1 for all
like the one presented in [15]. This algorithm does not require segments except the last one, which has it set to 0. When the
high computation power or high storage space. The correction segment with a value of zero in the MS bit is seen, the receiver
codes are computed as follow: knows that it has received the last segment of the message.
C0= S0 ⊕ S1 ⊕ S2 ⊕ … ⊕ Sk-1 Segment Offset (off), this field solves the problem of sequencing
segments by indicating to the receiver where in the original
C1 = S1 ⊕ S2 ⊕ S3 ⊕ … ⊕ SM message each particular segment should be placed.
C2 = S2 ⊕ S3 ⊕ S4 ⊕ … ⊕ S(M+1) mod k
IV. PERFORMNACE EVALUATION OF RELAX PROTOCOL
C3 = S3 ⊕ S4 ⊕ S5 ⊕ … ⊕ S(M+2) mod k We present and discuss in this section our simulation results
.
. for the performance study of our multipath routing protocol. We
.
CM= SM ⊕ S1 ⊕ S2 ⊕ … ⊕ S(M+i) mod k used NS-2 [17] to implement our protocol and compare it with
the Directed Diffusion [8], and N-to-1 [9] protocols.
Our simulation environment consists of a field of 500m x
Where ⊕ represents exclusive OR operation. 500m containing N sensor nodes (N varies from 50 to 300
nodes) randomly deployed. All nodes are identical with a radio
TABLE I transmission range set to 25m. The sink node is situated at the
SOME VALUES FOR THE BOUND α [14] upper right corner of the simulation field, and the source node is
α 95% 90% 85% 80% 50% situated on the left bottom corner. We investigate the
xα -1.65 -1.28 -1.03 -0.85 0 performance of the RELAX protocol in a multihop network
topology. Table II shows the simulation parameters.

Authorized licensed use limited to: SRM University. Downloaded on July 14,2010 at 11:45:12 UTC from IEEE Xplore. Restrictions apply.
 This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the IEEE ICC 2010 proceedings

TABLE II RELAX becomes more stable than other protocols. N-to-1

SIMULATION PARAMETERS protocol is the most costly protocol, because the route length
Network field 500m X 500m increases as the network increases, which causes a large set of
Number of Sensor 50 - 300 nodes to consume its power dramatically. This is due to that fact
Number of Sinks/Number of Sources 1/1 that N-to-1 protocol does not take into account the node’s energy
Transmission Range 25m level during routes construction. When compared to directed
Packet Size (Data + Over head) Up to 1024bytes
diffusion, RELAX improves energy savings by 9% to 37%.
Transmit Power 15 mW
Receive Power 13 mW
Idle Power 12 mW
2) Average Delivery Ratio
Sleep mode Power 0.015 mW Figure 6 shows the delivery ratio. As the network size gets
Initial Battery Power 500 Joules large, there are more available nodes, and hence more routes to
MAC layer IEEE 802.11 forward data, resulting in increasing the delivery ratio. N-to-1
Max Buffer Size 256 K-bytes and RELAX protocols show good performance in comparison
M (number of Correction codes) k/2 with Directed Diffusion. Because multiple paths are used at the
N (Paths used to transfer the data) k same time to transfer data packets. RELAX protocol
Weights (α, β, and γ) respectively 3/1/3 outperforms the N-to-1 protocol, because RELAX employs an
Simulation time 5000 seconds error correction scheme which contributes in increasing the
Relaxation Period 15 minutes [8] delivery ratio in the case of path failures by reconstructing the
original message using the generated XOR-codes.
0.1 1
RELAX
Average Energy Cons umption per Node

3) Average Delay
0.09 Directed Diffusion

0.08 N-to-1 M R 0.8

0.07
Figure 7 shows the average delay of the compared protocols.
Delivery Ratio

0.06 0.6
0.05 The average delay for all tested protocol increases as the
0.04
0.03
0.4
network size increases, but still RELAX protocol shows good
performance even for large network sizes compared to the other
RELAX
0.02 0.2
Directed Diffusion

protocols. Many studies have concluded that average delay

0.01 N-to-1 M R
0
0
50 100 150 200 250 300
50 100 150 200
Number of Nodes
250 300
Number Of Nodes increases as a result of increased energy savings. Thus a
Figure 5. Average Energy Consumption Figure 6. Average Delivery Ratio minimum tradeoff with delay should be made to reduce the
energy expenditure.
0.2 350

B. Impact of Packets Generation Rate

RELA X
0.18 Directed Diffusion

0.16 N-to-1 M R 300

In this simulation set of experiments, we fix the number of

A v e r a g e N o d e life tim e

0.14
Delay (in seconds)

250
0.12
0.1 200 nodes in the field to 200 nodes, and change the packets
generation rate at the source node from 10 to 100 packets/sec.
0.08
0.06 150
0.04
0.02 100 RELAX
The results are averaged over several simulation runs.
N-ro-1M R
0 Directed Diffusion
50
50 100 150 200 250 300
Number of Nodes 50 100 150 200
Number of Nodes
250 300
1) Average Energy Consumption
Figure 7. Average Delay Figure 8. Average Node Lifetime Figure 9 shows the results for the energy consumption. From
the figure, we observe that our protocol consumes less energy
The performance metrics used in the evaluation are the than other protocols. The N-to-1 protocol shows bad
energy consumption, delivery Ratio, average delay and the performance in comparison to our protocol, because it does not
average node lifetime. The average energy consumption is the take into account the node’s energy level during the paths
average of the energy consumed by the nodes participating in discovery phase. Furthermore, at higher rates it shows dramatic
message transfer from source node to the sink node. The increase in energy consumption because it lakes of an efficient
delivery ratio is the number of packets generated by the source load balancing mechanism for traffic allocation. Contrary, we
to the number of packets received by the sink node. The average observe that RELAX maintains low energy consumption even at
delay is the time required to transfer data from source node to higher traffic rates. Such results demonstrate that our protocol is
the sink node. The node lifetime is the time till that node dies stable in terms of energy consumption and is slightly affected by
out. We study the impact of network size and packets arrival rate the increase in the traffic rate.
on these performance metrics. Simulation results are averaged
over several simulation runs. 2) Delivery Ratio
Figure 10 shows the packet delivery ratio of the three
A. Imapct of Network Size . protocols. We observe that our RELAX protocol outperforms
In this simulation experiment, we fix the packets arrival rate other protocols. This is because of the uses of multiple paths to
at 50 packets/sec, and change the number of nodes in the field forward data to the sink node; as well this better performance is
from 50 to 300 nodes in step of 50 nodes each time. The results contributed by employing the XOR-based FEC module, which is
are averaged over several simulation runs. implemented in the RELAX protocol. Also, we note that the N-
to-1 protocol is almost comparable to our RELAX protocol at
1) Average Energy Consumption lower traffic rates. As the traffic rate increases, RELAX shows
Figure 5 shows the results for the energy consumption. From better performance than N-to-1 protocol, this is due to the lake of
the figure, we note that there is a save in energy of RELAX an efficient mechanism to distribute the traffic across multiple
protocol over other protocols. As the network size increases, paths in the N-to-1 protocol.

Authorized licensed use limited to: SRM University. Downloaded on July 14,2010 at 11:45:12 UTC from IEEE Xplore. Restrictions apply.
 This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the IEEE ICC 2010 proceedings

0.1
RELAX
1 Through computer simulation, we have evaluated and
0.09
studied the performance of our routing protocol and compared it
N-t o-1M R
A v e r a g e E n e r g y C o n s u m p tio n

Direct ed Dif fusion

0.08 0.8

with Directed Diffusion, and N-to-1 routing protocols.

P ac k e t D e liv e r y R a tio
0.07
( J o u le /Pa c k e t)

0.06 0.6
0.05
0.04
Simulation results have shown that our protocol achieves more
energy savings, lower average delay, higher delivery ratio, and
0.4
0.03
0.02
0.01
0.2 RELAX

N-to-1 M R long node lifetime duration than other protocols.

Directed Diff usion
0

As a future work, we are intended to deeply analyze the

0
0 10 20 30 40 50 60 70 80 90 100
10 20 30 40 50 60 70 80 90 100
Packet Arrival Rate (packets/sec)

Figure 9. Average Energy Consumption

Packet Arrival Rate (packets/sec)

Figure 10. Delivery Ratio

performance of our protocol and study other performance
metrics, like the impact of the node failure, the impact of the
0.8

0.7
RELAX

Directed Diffusion
400
path length, the impact of node mobility…etc.
350
A v e r ag e D e la y ( in s e c o nd s )

N-to-1 M R
0.6

ACKNOWLEDGMENT
300
0.5 Av e rag e N o de life tim e 250
0.4

0.3
200 The work presented in this paper was supported by DGE-
0.2
150

100
PUMA project.
0.1
REFERENCES
RELAX
50 N-to-1 M R
0 Directed Diffusion
0
10 20 30 40 50 60 70
Packets Arrival Rate (packets/sec)
80 90 100
10 20 30 40 50 60 70 80 90 100 [1] J. N. Al-Karaki, A. E. Kamal, “Routing Techniques in Wireless Sensor
Packet arrival rate (packets/sec)
Networks: A Survey“, IEEE Journal of Wireless Communications,
Figure 11. Average Delay Figure 12. Average Node Lifetime Volume 11, Issue 6, Dec. 2004 Page(s): 6 - 28
[2] K. Akkaya, M. Younis, “A Survey on Routing for Wireless Sensor
3) Average Delay Networks”, Journal of Ad Hoc Networks, Vol. 3, Pages:325-349, 2005.
Figure 11 shows the average delay of the compared [3] A. Martirosyan, A. Boukerche, R. W. N. Pazzi: A Taxonomy of Cluster-
protocols. From the results, as expected, it is clear that the Based Routing Protocols for Wireless Sensor Networks. ISPAN 2008:
RELAX protocol outperforms other protocols by having the 247-253
shortest delay. This better performance is contributed by routing [4] A. Martirosyan, A. Boukerche, R. W. N. Pazzi: Energy-aware and quality
of service-based routing in wireless sensor networks and vehicular ad hoc
data across multiple paths and by the bulletin error correction networks. Annales des Télécommunications 63(11-12): 669-681 (2008)
scheme, which increases the resiliency of the protocol to path
[5] J. Tsai, T. Moors, “A Review of Multipath Routing Protocols: From
failures and increases the probability that an enough portion of Wireless Ad Hoc to Mesh Networks”, In Proc. of ACoRN Early Career
the packet is received at the destination to recover the original Researcher Workshop on Wireless Multihop Networking, Jul. 17-18, 2006
data packet without incurring excessive delay through data [6] D. Ganesan, R. Govindan, S. Shenker, D. Estrin, “Highly-resilient,
retransmissions. energy-efficient multipath routing in wireless sensor networks”, ACM
SIGMOBILE Mobile Comp. and Comm. Review, 5(4):11–25, 2001.
4) Average Node Lifetime [7] S. Castillo, N. K. Samala, K. Manwaring, B. Izadi, D. Radhakrishnan,
“Experimental Analysis of Batteries under Continous and Intermittent
To study the effect of using two batteries in each node, we Operations”, in the Proceedings of the International Conference on
use lifetime duration of a sensor node as a metric. Figures (8 and Embedded Systems and Application, pages 18-24, June 2004.
12) show the influence of network size and packet arrival rate on [8] C. Intanagonwiwat, R. Govindan, D. Estrin “Directed Diffusion: A
the average lifetime duration of sensor nodes. As we observe, Scalable and Robust Communication Paradigm for Sensor Networking.”,
each routing protocol shows a tendency of decrease in the nodes Proc. of ACM MobiCom’00, Boston, MA,USA, Augsut 2000, pp. 56-67.
lifetime with the increase in network size or the packets arrival [9] W. Lou, “An efficient N-to-1 mutlipath routing protocol in wireless sensor
rate. As expected RELAX protocol outperforms other protocols networks”, Proceedings of IEEE international Conference on Mobile Ad-
hoc and Sensor Systems (MASS), Washington, DC, November 2005.
and maintains long lifetime durations. This is because of the
utilization of the relaxation effect of the batteries. [10] Y. M. Lu, V. W. S. Wong, “An energy multipath routing protocol for
wireless sensor networks”, International Journal of communication
system, 2007, Volume 20, pages747-766.
V. CONCLUSION [11] K. Lahiri, A. Raghunathan, S. Dey, D. Panigrahi, “Battery-driven system
In this paper, we have presented the RELAX protocol; an desgin: a new frontier in low power desgin,” in the proceedings of the
energy efficient multi-path routing protocol specifically designed VLSID’02, 2002, pages 1-7.
for wireless sensor networks. Multipath routing together with the [12] D. Rakhmatov, S. Vrudhula, “An Analytical High Level Battery Model
XOR-based FEC technique are used to recover from node for Use in Energy Management of Portable Electronic Systems,” in the
Proceedings of the ICCAD, 2001, pages 1 – 6.
failures without invoking network-wide flooding for path-
[13] Panasonic, Panasonic Alkaline Batteries Data Sheet. Available from
discovery. This feature is very important in sensor networks <http://www.panasonic.com/industrial/battery/oem/chem/alk/index.htm>
since flooding reduces network lifetime. [14] S. Dulman, T. Nieberg, J. Wu, P. Havinga, “Trade-off between Traffic
Our RELAX protocol uses the residual energy, node Overhead and Reliability in Multipath Routing for Wireless Sensor
available buffer size, and signal-to-noise ratio to predict the next Networks”, In the Proc. of WCNC-2003, pp. 1918 – 1922, March 2003.
hop through the paths construction phase. RELAX splits up the [15] Z. Xiong; Z. Yang; W. Liu; Z. Feng, “A Lightweight FEC Algorithm for
Fault Tolerant Routing in Wireless Sensor Networks”, In Proceedings of
transmitted message into a number of segments of equal size, WiCOM 2006, Volume , Issue , 22-24 Sept. 2006.
add correction codes, and then transmit it over multiple paths
[16] E. Ayanoglu et al., “Diversity Coding for Transparent self-healing and
simultaneously to increase the probability that an essential Fault-Tolerant Communication Networks,” IEEE Trans. Comm., vol 41,
portion of the packet is received at the destination without no. 11, Nov 1993.
incurring excessive delay. RELAX protocol utilizes the [17] The Network Simulator-ns-2, http://www.isi.edu/nsnam/ns/
relaxation effect of the battery (which powering the sensor node)
to increase the battery lifetime and hence increasing the overall
lifetime of the sensor network.

Authorized licensed use limited to: SRM University. Downloaded on July 14,2010 at 11:45:12 UTC from IEEE Xplore. Restrictions apply.