Reliable Energy-Aware Routing Protocol for

Heterogeneous WSN Based on Beaconing

Li Ya, Wang Pengjun, Luo Rong, Yang Huazhong, Liu Wei
Department of Electronic Engineering, Tsinghua University, P.R. China
Rohm Building 4-205, Tsinghua University, Beijing, P.R. China
[email protected], [email protected], [email protected], [email protected],
[email protected]

AbstractHeterogeneous WSN(wireless sensor network) is
widely used in environmental monitoring, infrastructure
monitoring, animal monitoring and smart building. Since nodes
in heterogeneous WSN have different power supply and
operational capability, routing protocols could make the most of
the nodes heterogeneity to make the network reliable, robust,
simple and energy-efficient, but by now, protocols designed cant
achieve all these goals. CTP(collection tree protocol) made a good
practice to provide a reliable protocol based on beaconing for
data collection. But it doesnt consider about energy balance and
it doesnt provide an efficient dissemination scheme. In this
paper, we present a novel routing protocol for heterogeneous
WSN based on beaconing. We introduce EARBB(a
Energy-Aware Routing Based on Beaconing) which can provide
a reliable and energy-efficient routing scheme for both
information collection and dissemination with beaconing packets
exchanged between nodes and their neighbour. At the same time,
EARBB also support node-to-node routing scheme besides
node-to-sink routing scheme. Simulation experiments show that
EARBB establish a reliable network which can quickly recover
from node failure. During downstream data transmission, 80%
less packets need to be sent using EARBB than using flooding. Its
average lifetime is at least 20% longer than that of CTP.

Keywordsstatic heterogeneous WSN, energy-aware, routing,
beaconing, reliability, CTP
I. INTRODUCTION
For sensor network used in infrastructure monitoring,
smart home, environment monitoring and animal monitoring,
heterogeneous WSN is always preferred because it can largely
alleviate the workload of the nodes by using some powerful
header nodes.
An efficient routing protocol can make heterogeneous
WSN better to provide a reliable and energy efficient
connectivity between nodes and the sink. When designing a
routing protocol for heterogeneous WSN, five goals should be
considered.
Reliability: Under normal circumstances, more than 90%
end to end packets should be sent successfully.
Robustness: Network can quickly react to the change of
network condition and topology.
Energy-efficiency: minimum energy should be
consumed and energy-consumption should be even among all
nodes.
Bidirectional-support: Both upstream and downstream
routing should be efficient.
Simplicity: Complex protocol requires more hardware
resources and energy consumption.
Many protocols achieve some of these five goals.
LEACH based protocols[1][3] are quite energy efficient and
can support bidirectional transmission because LEACH based
protocols construct single-hop network. However, LEACH
based protocols cant guarantee 100% connectivity between
nodes and header nodes that largely decreases its reliability.
RSNP[4] is a very simple protocol. It provides reliable and
energy efficient upstream link, but its downstream traffic
consumes too much energy and this protocol cant quickly
react to node failure. REAR[5] is another good practice for
heterogeneous WSN. It introduces energy-reservation
mechanism and back-up path mechanism to achieve reliability
and energy efficiency, but REAR reacts slowly to network
condition change.
CTP[6][8] is considered the most reliable and robust
routing protocol among all those routing protocols for
heterogeneous WSN. It is well designed and fully tested.
Adaptive beaconing mechanism makes it very robust while
simple path validation scheme makes it very energy efficient.
Reliability is achieved by single hop Ack, route loop avoid
and packet repetition suppression scheme. But CTP doesnt
support bidirectional transmission and its unbalanced energy
consumption among nodes is a big constraint to the lifetime of
the network.
In this paper, we propose an energy-aware routing
protocol based on beaconing that improves CTP. By
modifying the beaconing scheme, we make the sink maintain
a routing table containing the whole topology of the network.
Thus, the new protocol support bidirectional transmission and
the downstream traffic can be the same robust, reliable and
energy-efficient as the upstream traffic. By introducing a new
path validation metric, the route selection is based on not only
the link quality, but also the residue energy of the route.
Therefore, energy consumption among node is much more
SBN 9788996865032 !09 February !6!9. 20!4 CACT20!4
balanced and the lifetime of the whole network is prolonged.
Overcoming the drawbacks of CTP, the new protocol achieves
all five goals as reliability, robustness, energy-efficiency,
bidirectional-support and simplicity.
II. PROPOSED PROTOCOL
A routing protocol should build and maintain a routing
table that contains the minimum-cost tree from every node to
the sink. The cost metric is a very important parameter to
depict the quality of the route. Once the routing table is
established, minimum-cost route can be selected between
every node and the sink. In this part, the new path validation
metric that helps balance the nodes energy consumption in
the network will be introduced. Then routing table
establishment process will be described.
A. Energy Aware Path Validation
In order to find the minimum cost route for nodes, every
node should evaluate the cost of the route to the sink. To
evaluate the cost of the route, a cost metric should be picked
first. Usually, cost metric is set to be a parameter related to the
packet loss rate. In CTP, expect transmission which is in
proportion to packet loss rate is selected to be the cost
metric[7]. Such cost metric can objectively depict the link
quality of the radio channel. But using such cost metric makes
the nodes in the best quality routes bear most of the
transmission tasks. Therefore, these nodes will quickly
exhaust their energy. The energy consumption is even faster
on those nodes near the sink.
To counter this problem, we assume another cost metric to
evaluate the path quality which is called expect transmission
hops and energy residue (ETHER). Single hop ETHER is
calculated using the following equation.

where, E is the energy residue of the node. L is the packet loss
rate of the channel. is a constant, here it is recommended
to be 1.5. The ETHER of the route is the sum of ETHER of
each hop along the route. Because energy residue can be
easily got from the power curve of the source, ETHER is very
easy to get.
Since ETHER takes energy residue into account, the route
with less energy residue will not be selected as the best route.
Thus nodes on the route with the best link quality will not run
out of energy so fast. The workload of the network is
distributed more evenly. This solution may slightly influence
the delay and the quality of transmission, but it will largely
prolong the lifetime of the network. According to the
simulation in part 3, the lifetime can be prolonged at least 30%
under different network size.
B. Route Computation and Selection
EARBB adopts the adaptive beaconing scheme[7] which
extends the Trickle algorithm[9]. So the network could
quickly react to network topology and condition change while
consuming least energy on beacon packets transmission. But
EARBB introduces a new route computation and selection
procedure to support efficient bidirectional transmission.
In EARBB, minimum-cost routing tree will be established
as beacon packets exchanged between nodes and their
neighbours. Beacon packets are also exchanged between
nodes and the sink. Beacon frame contains information of the
nodes cost to the sink. The detail of the beacon frame is in
table 1.
The function of P bit and C bit is the same as that in
CTP[7]. PARENT field and ETHER field record the cost from
the node to the sink. ORIGIN field record the nodes own
address. NEIGHBOUR COUNT field, NEIGHBOUR ADDRn
field and ETHERn field record the cost from the node to its
neighbours.
TABLE 1. BEACON FRAME DETAIL
1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6
P C RESERVED PARENT
PARENT ORIGIN
ORIGIN ETHER
ETHER NEIGHBOUR COUNT
NEIGHBOUR ADDR 1
ETHER1
NEIGHBOUR ADDR 2
ETHER1


Every node in the network maintains a cost table that
records the cost between the node and its neighbours as well
as the neighbours cost to the sink. Node in the network also
maintains its own cost to the sink and its parent address. When
node receives beacon packet from its neighbours, it updates
the cost table, calculates the best route according to the new
cost table and then refreshes its own cost to the sink and its
parent address. As beacon packet exchanged between nodes in
the network, every node in the network finds its best route and
its parent. After that, the upstream route tree is formed within
the network.
When a node receives a beacon packet whose ORIGIN
field equals its own address, it immediately forwards the
beacon packet to the sink as a normal data packet through its
route to the sink. When the sink receives the beacon packet, it
updates its route table, which contains nodes address and
their parent address in the network. The sink can find the best
route to the node in the network through the route table.
Figure 1 shows an example of how the sink finds the route
to a specific node in the network. Assume the sinks address is
1 and the route table contains three nodes 2, 3 and 4. The sink
wants to find the route to node 4. It first goes through the
route table to find node 4, then goes through the route table to
find node 4s parent which is node 3. Repeat the above steps
until the sink find the node whose parent is the sink itself. In
this case, it should be the node 2. Now, the sink discovers the
route from the node 4 to the sink. The route is 4-3-2-1. So the
SBN 9788996865032 !!0 February !6!9. 20!4 CACT20!4
route from the sink to the node 4 is just the opposite route
which should be 1-2-3-4. So the route table maintained by the
sink make it possible to find route to any node in the network.

Figure 1. Downstream route discovery procedure
The downstream data packet header structure is shown in
table 2. The header contains all node address along the route
in sequence. When node on the route receive a downstream
data packet, it delete its own address in the header and
forwards the packet to the next hop, thus guarantee that the
first address in the header is the address of the next hop.
TABLE 2. DOWNSTREAM DATA PACKET
1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6
HOPS COUNT
RELAY NODE1 ADDRESS
RELAY NODE2 ADDRESS

RELAY NODEn ADDRESS
DATA PAYLOAD

Since EARBB adopt route loop avoidance and duplicate
suppression mechanism[7] in CTP, EARBB is very reliable
and robust. As the new route discovery scheme is introduced,
EARBB support bidirectional transmission.
C. Node to Node route discovery
EARBB is able to support node to node communication.
This is useful under many situations.
Since Beacon packet includes details about the
connectivity between node and its neighbours, after all the
nodes send beacon packet to the sink, the sink becomes aware
of the whole topology of the network. So the sink can find the
best route between two ordinary nodes.
Using the footer part of the beacon packet, the sink
establishes a matrix to describe the topology of the
whole network. n equals to the network size. The element in
the i for column j record the ETHER values from node i to
node j. Once the matrix is established, the sink can find the
best route between any two nodes using Dijkstra Algorithm.
Any node which needs to frequently communicate to
another node in the network can request the sink for the route.
Then the sink computes the best route according to the
topology matrix and sends the route information back to the
node. The node sending the request stores the route
information and then it is able to communicate to the node it
is interested in through the best route.
III. SIMULATION
A. Simulation Platform
We use TOSSIM[10] as the simulation platform for the
test of the proposed protocol. TOSSIM is a useful simulation
tool for TinyOS applications. TOSSIM can do packet-level
simulation and its able to simulate the behaviour of a whole
network of different size.
B. Reliability Test
To test the overall performance of EARBB, a 20-minute
long simulation of a network with 50 nodes is conducted. A
comparison with CTP is made. For EARBB condition 1, the
sink is made to transmit a downstream packet to a random
node in the network every 500ms and other node in the
network is made to transmit an upstream packet every 500ms
to the sink. For EARBB condition 2, the sink is made to
transmit a downstream packet to a random node in the
network every 500ms and other nodes do not send upstream
packet at all. For CTP, node in the network is made to transmit
an upstream packet every 500ms to the sink. During
simulation, 30% of the nodes in the network are down at 10
minutes. Figure 2 shows the delivery ratio for both protocols.
The simulation result indicates that EARBB is almost as
reliable as CTP. EARBB can quickly recover from node
failure just as CTP does. The downstream transmission of
EARBB reacts a little bit slower than upstream transmission
of EARBB because the sink need more time to update the
topology change than ordinary node.
C. Energy Efficiency Comparison
It is stated in part 1 that CTP has a problem of energy
consumption distribution. EARBB solves this problem by
introducing energy aware path validation mechanism.

Figure 2. Delivery ratio test result
To test the energy efficiency of EARBB, Simulation under
different network size is made. Network size varies from 10
0 2 4 6 8 10 12 14 16 18 20
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
Time
D
e
l
i
v
e
r
y

R
a
t
i
o


EARBB condition 1
EARBB condition 2
CTP
SBN 9788996865032 !!! February !6!9. 20!4 CACT20!4
nodes to 80 nodes, 10 as interval. To simplify the energy
consumption evaluation model, assume the packet sending
and receiving quantity as the energy metric. Moreover, assume
every node can total send or receive packets of 4GB. In the
simulation, each node in the network sends an upstream
packet every 500ms. When 10% of the nodes run out of
energy, the network is broken down. Figure 3 shows the result
of the simulation.

Figure 3. Lifetime of the network
The figure shows that EARBB prolongs the lifetime of the
network by at least 20%. And the effect is even greater when
network size become larger. That illustrates the effectiveness
of the new path validation mechanism of EARBB.
D. Downstream Transmission Test

Figure 4. Downstream transmission simulation result
In order to test the performance of downstream
transmission of EARBB, a simulation is conducted to
compare the efficiency of downstream transmission of
EARBB, flooding and REAR protocol. The network size is 50
nodes and the node will send packet under different speed.
The sink sends a packet to a specific node every 500ms. For
REAR, assume that the route tree is updated every 2 minutes.
The simulation period will be 20 minutes and the total packet
quantity will be the metric to evaluate the efficiency of the
protocols. Figure 4 shows the result of the simulation.
It is obvious that the downstream transmission of EARBB
is much more efficient than flooding and REAR. Flooding
protocol need to send at least 80% more packets to
disseminate information than EARBB and since EARBB need
less packet transmission to maintain the routing tree, thus its
more efficient than REAR too.
IV. CONCLUSION
CTP is a very good practice for heterogeneous network. It
is fully tested under various platforms. Its very reliable,
robust and energy efficient. But CTP is constrained by its
energy consumption distribution and single direction
transmission. In this paper, an energy aware routing protocol
based on beaconing is proposed to counter the problems that
CTP has. New path validation mechanism prolongs the
lifetime of the network and new beaconing schedule support
efficient downstream transmission and node to node
transmission. In the future, the new protocol is expected to
implement on the Micaz hardware platform to perform some
hardware tests.
REFERENCES
[1] Heinzelman W. Chandrakasan A. Balakrishnan H.,energy-Efficient
Communication Protocol for Wireless Microsensor Networks,
Proceedings of the 33rd Hawaii International Conference on System
Sciences, January 2000.
[2] Meenakshi Sharma, Kalpana Sharma. An Energy Efficient Extended
LEACH (EEE LEACH), 2012 International Conference on
Communication Systems and Network Technologies, 2012
[3] Arezoo Yektaparast, Fatemeh-Hoda Nabavi, Adel Sarmast. An
Improvement on LEACH Protocol(Cell-LEACH), Advanced
Communication Technology (ICACT), 2012 14th International
Conference on, Feb. 2012.
[4] Scow Guther, CertCo, Wireless Relay Networks, IEEE Network,
November 1997.
[5] Ke Liu, Nael Abu-Ghazaleh, Reliable Energy Aware Routing in
Wireless Sensor Networks, Proceedings of the Second IEEE
Workshop on Dependability and Security in Sensor Networks and
Systems, 2006.
[6] R. Fonseca, O. Gnawali, K. Jamieson, S. Kim, P. Levis, and A. Woo.
TEP 123: The Collection Tree Protocol, Aug. 2006
[7] Kyle Jamieson, David Moss and Philip Levis. Collection
Tree Protocol, Proceedings of the 7th ACM Conference on
Embedded Networked Sensor Systems, 2009.
[8] Joakim Flathagen, Erlend Larsen, Paal E. Engelstad, etc. O-CTP:
Hybrid Opportunistic Collection Tree Protocol for Wireless Sensor
Networks, Local Computer Networks Workshops (LCN Workshops),
2012 IEEE 37th Conference on, Oct. 2012.
[9] P. Levis, N. Patel, D. Culler, and S. Shenker. Trickle: A selfregulating
algorithm for code maintenance and propagation in wireless sensor
networks. In Proc. of the USENIX NSDI Conf., San Francisco, CA,
Mar. 2004
[10] http://tinyos.stanford.edu/tinyos-wiki/index.php/TOSSIM, Sept, 2013
10 20 30 40 50 60 70 80
0.5
1
1.5
2
x 10
7
Network Size
L
i
f
e
t
i
m
e
(
s
)


CTP
EARBB
100bps 1kbps 10kbps
0
1
2
3
4
5
6
7
x 10
6
Packet Sending Speed
T
o
t
a
l

P
a
c
k
e
t

Q
u
a
n
t
i
t
y
(
B
y
t
e
)


EARBB
flooding
REAR
SBN 9788996865032 !!2 February !6!9. 20!4 CACT20!4