Wireless Sensor Network, 2010, 2, 441-446
doi:10.4236/wsn.2010.26055 Published Online June 2010 (http://www.SciRP.org/journal/wsn)
Practical Considerations for Wireless Sensor
Network Algorithms
Gertjan Halkes, Koen Langendoen
Faculty of Electrical Engineering, Mathematics and Computer Science,
Delft University of Technology, Delft, The Netherlands
Received April 1, 2010; revised April 28, 2010; accepted May 6, 2010
Abstract
Many researchers from different backgrounds have found interesting research challenges that arise from the
physical constraints and envisaged applications in Wireless Sensor Networks (WSNs). The WSN community
that has formed over the years is divided into two sub-communities: the systems sub-community and the
theory sub-community. However, there seems to be no connection between the two. Algorithms developed
from a theoretic perspective are rarely implemented on real hardwares. In this paper we identify the most
important reasons why these algorithms are disregarded by the systems sub-community, and provide pointers
to remedy the lack of connection.
Keywords: Theory, Practice, Algorithms
1. Introduction
Wireless Sensor Networks (WSNs) exploit the possibili-
ties that miniaturization provide by creating small and
cheap devices that can communicate wirelessly and pro-
vide a way to bring the real world into the realm of com-
puting. Using WSNs many new applications come within
reach, for example monitoring of real-world events in
remote and poorly accessible places [1,2].
The distributed nature of WSNs and research chal-
lenges arising from the constraints dictated by economics
and physics have attracted many researchers from dif-
ferent backgrounds such as distributed systems, net-
working and signal processing. These different back-
grounds also have their impact on the WSN community.
The WSN community that has formed over the years is
divided into two sub-communities: the systems sub-com-
munity and the theory sub-community. However, there
seems to be no connection between the two sub-com-
munities. Algorithms developed from a theory perspec-
tive are rarely implemented on real hardware. In this
context we are reminded of the following quote that
summarizes the essence of our observations:
In theory, there is no difference between theory and
practice. But, in practice, there is.
Jan L. A. van de Snepscheut
With this paper we intend to make a start at removing
the difference between theory and practice.
We identify the most important reasons why algo-
rithms created from a theory perspective are disregarded
by the systems community. By studying the papers from
major theory and systems conferences we conclude that
there are three main issues that make implementation of
many algorithms developed from a theory perspective
infeasible or undesirable. Firstly, the unreliability of the
underlying wireless network is often ignored. Secondly,
energy consumption is not always taken into account
when designing and evaluating an algorithm. Lastly, al-
gorithms are sometimes organised in rounds which ham-
pers implementation on real hardware. We also provide
recommendations on how to design algorithms such that
the systems community will more often use them.
The rest of the paper is organised as follows: in Sec-
tion 2 we give an overview of the different perspectives
on WSNs that influence the design of algorithms and
protocols from the two sub-communities. Then, in Section
3 we provide the results of our study of a representative
collection of papers from WSN conferences. In Sections
4 through 6 we analyse the main issues we identified in
greater detail and provide recommendations for each of
them. Finally, in Section 7 we conclude the paper.
2. Main Perspectives on Wireless Sensor
Networks
To understand the origin of the gap between the theory
and systems sub-communities, we start by looking at the

442 G. HALKES ET AL.
characteristics that the sub-communities use when de-
scribing WSNs.
From the theory perspective a WSN is very much like
a classical distributed system. What sets WSNs apart is
that the network connectivity is dictated by physical
proximity instead of having a fully connected network.
Of course the subject of the algorithms is different as
well because of the different application areas. Algo-
rithms for WSNs mostly focus on subjects like localiza-
tion, information dissemination, distributed calculation
of statistics and metrics on measured data, and distrib-
uted consensus. Naturally this is not an exhaustive list of
all the characteristics taken into account by researchers
within the theory sub-community. However, these are the
common characteristics that can be found in virtually all
research papers, either explicitly stated or left implicit.
The systems perspective is dominated by the harshness
of reality and the laws of physics. An important charac-
teristic is that WSN nodes are running of batteries or
ambient energy sources. Furthermore, it is intended that
sensor networks can be left to operate for years without
any human intervention. This means that energy is a
scarce resource and energy efficiency is key in designing
protocols and algorithms. As the radio is and will remain
the largest consumer of energy in the node it is important
to communicate only when necessary. A second impor-
tant characteristic is that wireless communication is in-
herently unreliable and unstable. However unfortunate,
this is a result of the laws of physics and therefore has to
be dealt with. This does mean that every protocol and
algorithm needs to be designed to cope with unreliable
communication.
3. Problem Analysis
To assess the impact of the two different perspectives on
WSNs, we analyzed papers from major theory sub-com-
munity conferences and from important systems confer-
ences for comparison. From this analysis we compiled a
list of issues that complicate the implementation of the
presented algorithms in the real world. Below is an ex-
tract from the list we compiled:
 Communication is assumed to be reliable.
 Energy consumption in the form of communi-
cation is not taken into account, or not analyzed
precisely enough.
 Algorithms are organized in synchronous rounds.
 Each node has a known and stable set of
neighbors.
 The propagation model is assumed to be a Unit
Disk Graph (UDG) and calculations are made
based on this assumption.
 Algorithms include manipulations of large ma-
trices, which is infeasible on sensor node proc-
essors.
 Large messages are exchanged between nodes,
which require several packets in WSNs.
Table 1. Percentages of papers in studied theory and sys-
tems conferences per implementation issuea.
Theory Systems
Communication assumed reliable 47 (61%) 8 (17%)
Energy cost insufficiently accounted 47 (61%) 14 (30%)
Rounds-based organisation 19 (25%) 1 (2%)
Number of papers 77 47
(aThe papers were taken from the IPSN 2005-2007 and DCOSS 2005-
2006 conferences (theory), and from the SenSys 2005-2006 and EWSN
2006-2007 conferences (systems).)
Some of these issues can be dealt with without touch-
ing the workings of an algorithm, while other issues touch
on fundamental assumptions underlying the design of
that algorithm. The first three items of the above list fall
into the latter category and those are the issues we focus
on in this paper.
In Table 1 we have listed the occurrences of the three
issues in the theory and systems conference proceedings
we studied. It should be noted that the separation of the-
ory and systems papers does not exactly follow the con-
ference foci. In theory conferences there are usually a
few systems-type papers, and vice versa. Although this
cross pollination somewhat dilutes the numbers, it is
clear that the issues complicating implementation are far
more prevalent in theory papers than in systems papers.
Adapting algorithms that have been designed without
considering these issues can be done, but is exceedingly
difficult [3]. Therefore, we now provide a more detailed
description of the issues and recommendations on how
they can be avoided.
4. Communication Reliability
To implement any algorithm that involves more than a
single node, nodes will have to communicate. At the
lowest layer the only primitive that is available is a local
broadcast to a node's “neighbors”. That is, the radio can
be used to send bits to other nodes that are sufficiently
close by to receive them.
However, physical proximity is far from the only fac-
tor that determines whether the bits will actually reach
the intended recipients. Obstacles of many kinds can
distort and reflect the signals and prevent proper recep-
tion (see Figure 1). Examples of such objects are of
course walls and other built structures, trees and plants,
but also humans, animals and vehicles. Note that the ob-
stacles may be mobile, which will make for changing
signal conditions and therefore changing channel reli-
ability. So, even though two nodes may have no trouble

G. HALKES ET AL. 443
0
0.2
0.4
0.6
0.8
1
1.2
0 5 10 15 20 25 30 35 40
Received fraction
Distance (meter)
0
0.2
0.4
0.6
0.8
1
1.2
0 5 10 15 20 25 30 35 40
Received fraction
Distance (meter)
Figure 1. Reception rates in an office corridor at different
distances from a sending node on two consecutive days
(taken from [5]).
communicating one moment, communication could be
completely impossible the next moment.
Other factors that influence reception include tem-
perature, humidity, and other transmitters, all of which
vary over time (see Figure 1 for an example). It is clear
that all these factors taken together make it impossible to
predict whether a given signal will reach the intended
recipient. Indeed, several experimental studies have shown
the unreliability of the channel [4-7].
Given the unreliable channel, one of the MAC proto-
col's tasks is to increase the reliability of the channel as a
means of communication. Paradoxically, although the radio
channel is a broadcast medium it is easier to increase the
reliability of unicast radio transmissions than it is to in-
crease the reliability of broadcast transmissions (see be-
low). But even for unicast communication it is not possi-
ble to achieve 100% reliability. This means that proto-
cols and algorithms have to take into account that any
communication step may fail, especially when using broad-
cast messages. Also, it is worth noting that any increase
in reliability comes at the cost of increased energy con-
sumption, for example in the form of retransmissions.
4.1. Increasing Reliability
Although 100% reliability is impossible to achieve, there
are possibilities to increase the reliability of the links in
use. Topology control algorithms are a good example
[3,4,6]. By only using the links that meet some quality
criterion it is possible to remove much of the unreliabil-
ity. However, link instability caused by quickly changing
channel conditions such as collisions, interference from
other devices and moving obstacles can not be elimi-
nated this way.
An important thing to realize is that topology control
is not free. A topology control algorithm needs to assess
the quality of links, and the only way to do that is to ob-
serve messages sent over the link. In many cases the al-
gorithm will send its own messages to do so. These costs
need to be taken into account when assuming the pres-
ence of a topology control algorithm.
Almost all of the papers that assume reliable commu-
nication use broadcast messages in the algorithm. How-
ever, increasing the reliability of broadcast communica-
tions is a very difficult problem. First of all, in order to
determine whether a message arrived, a node needs to
know all the nodes a message is to arrive at. Therefore,
each node has to know its neighbors. Again a topology
control algorithm can provide this information; at a price.
Second, all nodes that have received a message need to
acknowledge the reception. Each one of these messages
costs energy, and because all receiving nodes will want
to acknowledge the message at the same time channel
contention will be high. Third, if not all nodes have re-
ceived the broadcast, some form of retransmission scheme
has to be employed, which is not trivial and will also cost
even more energy.
Another option for increasing the reliability of broad-
casts is to send a unicast message to each neighbor sepa-
rately (repeated send). This is of course a very costly
solution, which again requires knowledge of a node’s
neighbors. Furthermore, if a node has many neighbors it
will take a long time to reach all of them.
4.2. Handling Unreliability
Recommendation 1: Design algorithms such that
unreliable communication is not disruptive.
From the previous discussion it is clear that 100% re-
liable communication is not achievable. Table 2 sum-
marizes what types of communication are available in
WSNs. Many research papers from the theory sub-
community assume, either explicitly or implicitly, that
reliable communication is provided by the communica-
tion subsystem. Worse, most of these papers assume re-

444 G. HALKES ET AL.
Table 2. Available communication types in WSNs.
Reliable Unreliable
Unicast +/–a +
Broadcast – +
(aReliability vs. energy trade-off.)
liable broadcast. Clearly, this mismatch between as-
sumed and provided level of service makes straightfor-
ward implementation of the algorithms impossible.
Although it may be difficult to take unreliable commu-
nication into account from the start of algorithm design,
an analysis of the algorithm’s performance with message
loss is essential. This can include an analysis of perform-
ance degradation, or an analysis of the increased cost to
obtain the same quality of result. Before any implementa-
tion on real hardware it is vital to know if and how well
the algorithm will be able to cope with message loss.
5. Energy Efficiency
From a systems perspective an important aspect of
WSNs is the limited amount of energy. As the radio is
the most important source of energy consumption, a lot
of research is focused on limiting the time the radio is
turned on [8,9]. Part of this problem is solved by the
MAC layer orchestrating the communication in such a
way that the radio can be turned off most of the time.
However, this only reduces the overhead associated with
radio communication. The sending of messages itself
still costs energy. It is up to the higher layers to limit the
number of messages sent as much as possible.
The focus on energy efficiency is not always found in
algorithm papers. Five categories of papers can be dis-
tinguished in this context, ordered by level of detail:
 papers that ignore communication cost all to-
gether (Theory: 39% vs. Systems: 26%),
 papers that provide an order estimate of the
number of messages sent (22% vs. 4%),
 papers that provide an analysis of the number
of messages sent (12% vs. 6%),
 papers that provide simulation or real-imple-
mentation results on the number of messages
sent (17% vs. 38%), and
 papers that provide energy consumption figures
from a simulator or a real implementation (10%
vs. 26%).
For compiling Table 1 we have considered the first
two categories insufficient for accounting energy con-
sumption.
At first sight the last category may seem the most de-
sirable, but this is deceptive. The exact energy consump-
tion resulting from the use of an algorithm is very de-
pendant on the underlying MAC protocol and radio
hardware. WSN-specific MAC-protocols are highly op-
timized for a particular scenario and the associated traffic
pattern. Using a different MAC protocol can easily in-
crease or reduce the energy consumption with a signifi-
cant factor. For example, for data gathering traffic an
optimized MAC protocol like DMAC [10] uses signifi-
cantly less energy than most general-purpose MAC pro-
tocols. Measuring the energy consumption in Joules is
however useful for low-level protocols.
Recommendation 2: Analyze the impact of unreli-
able communication on the algorithm’s performance.If we want to find the best way to analyze energy effi-
ciency, we first have to look at what we want to do with
this information. In the end, energy efficiency is simply a
metric to compare and rank different algorithms. To com-
pare different algorithms with respect to energy effi-
ciency, what is required is a precise analysis of the num-
ber of messages sent.
Recommendation 3: Specify an algorithm's energy
efficiency by analyzing the number of messages sent,
differentiating between unicast and broadcast messages.
As mentioned previously, different MAC protocols
have different energy consumption profiles. The most
important differences stem from the distinction between
broadcast and unicast messages. Some protocols are op-
timized for energy-efficient unicast traffic and a broad-
cast message can consume as much energy as several
unicast messages, e.g., WiseMAC [11]. Other protocols
are more geared towards broadcast, which makes unicast
approximately as expensive as broadcast, e.g., B-MAC
[12]. Figure 2 shows the energy consumption profiles
for several state of the art MAC protocols. Note that the
graphs do not indicate energy efficiency, only the ratio
between unicast and broadcast energy consumption.
Another reason to separate unicast messages from
broadcast messages is that many MAC protocols include
retransmissions for unacknowledged unicast messages,
while broadcast messages are only sent once. These
MAC level retransmission schemes make it even harder
to compare the cost of unicast messages with the cost of
broadcast messages.
These considerations lead to the conclusion that a
thorough analysis of the communication cost should sep-
arate broadcast and unicast messages.
6. Algorithm Organization
Even when an algorithm designer has taken message loss
and energy consumption into account in the design of his
algorithm, it may still be next to impossible to implement
the algorithm on real hardware. The single most common
cause is that the algorithm is designed based on the com-
munication-round paradigm. There are synchronous and

G. HALKES ET AL. 445
0
0.2
0.4
0.6
0.8
1
1.2
2 4 6 8 10 12 14 16 18 20
Unicast/Broadcast energy ratio
# Neighbors
B-MAC
Crankshaft
LMAC
WiseMAC
Figure 2. Energy consumption profiles for different MAC
protocols, expressed as the ratio between the energy spent
for sending one unicast message and the energy spent for
one broadcast message. The use of overhearing-avoidance
techniques makes unicast messages cheaper than broadcast
messages when there are many neighbors.
asynchronous versions of this paradigm, but both are
problematic in the context of WSNs. In this section we
will detail the problems with both versions.
6.1. Synchronous Communication Rounds
The use of synchronous communication rounds is very
common in classical distributed systems. Each calcula-
tion and communication round is executed by each node
simultaneously. This synchrony is easily achievable on
stable and reliable networks such as the Internet and lo-
cal networks of grid computers. However, implement-
ing an algorithm based on synchronous communication
rounds on WSNs is very difficult for several reasons.
First of all, an algorithm has to be started. This may
seem like a trivial operation, but certainly is not. To start
an algorithm, all nodes will have to agree to start at the
same time. Reaching agreement can only be done through
communication, which, as we have seen in Section 4, is
unreliable. Hence, starting a synchronous algorithm can
not be done reliably. The same problem arises in estab-
lishing when a round has ended. Using a timer will not
help either because it is impossible to bound the time
required to finish the communication for a single round.
A second problem in using an algorithm based on
communication rounds is that each round will cause a
peak load in the network. This peak load will decrease
reliability of network communication and disrupt traffic
from concurrently running algorithms and applications.
A final problem is what to do when nodes join the
network. Although for many of the algorithms this sim-
ply means that a node will only be able to participate in
the next run (not round) of the algorithm. For algorithms
that manage the network structure such as clustering al-
gorithms or topology control algorithms it may mean that
a node will not be able to participate in the network for a
long time.
6.2. Asynchronous Communication Rounds
The communication-rounds paradigm can also be imple-
mented asynchronously. This can be done by including the
round number in each message. Once a node has re-
ceived all messages from its neighbors, it can proceed to
the next round. To start the algorithm a single, perhaps
designated, node can simply start its first round. When a
node receives a message that indicates that it belongs to
the first round, the receiving node will also send its mes-
sage for the first round. However, implementing this asyn-
chronous approach is not without problems in WSNs.
The most important issue is that a node will have to
know all its neighbors to be able to determine when to
start the next round. Furthermore, the neighbor set is not
necessarily stable. As a result, the algorithm may never
terminate because a node will not receive messages from
all the nodes it expects messages from. Instability of the
neighbor set may be caused by communication unreli-
ability, node failure and node mobility.
6.3. Reactive Organization
Recommendation 4: Design algorithms that react to
other nodes’ messages, rather than using the concept
of rounds.
Given the problems in implementing a rounds-based
algorithm detailed above, it is obvious that a different
organization is preferable. One simple organization that
does not suffer from the round starting problem is an
organization where a node simply reacts asynchro-
nously to messages from neighboring nodes. When a
round should be started, a single node can simply decide
that a new run of the algorithm is required and send the
first message.
This organization does introduce several new prob-
lems for naive implementations, but these are easily
solved. For example, it is not a good idea to react to a
received message by immediately sending a message as
well. This will make for high contention conditions dur-
ing the execution of an algorithm, which needs to be
avoided. Adding a random delay before sending a re-
sponse to a neighbor’s message will also allow reacting
to other neighbors with a single message. To prevent
deadlock and starvation, the delay should not be reset on
receiving another message.
A second problem is the termination of an algorithm.
The number of executed rounds can no longer be used to
terminate an algorithm. Convergence is a good option for
termination in asynchronous algorithms, and is actually
also often used in rounds-based algorithms. Another op-
tion is to bound the maximum number of messages sent
for one algorithm run.
It is important to keep in mind that communication is

446 G. HALKES ET AL.
not 100% reliable. Although in synchronous round-based
algorithms this is necessarily a problem, this need not be
a problem in asynchronous algorithms because further
iterations of an algorithm should compensate for the
missing values.
We are aware that an asynchronous algorithm is hard-
er to analyze with respect to both the number of mes-
sages sent per algorithm run, as well as convergence and
stability properties. This is the price to be paid for creat-
ing an implementable algorithm.
7. Conclusions
In this paper we have identified three common causes for
the lack of interest from the WSN systems sub-comm-
unity for the algorithms developed by the theory sub-
community. Firstly, the unreliability of the underlying
network is often ignored. Secondly, energy consumption
of the algorithm is not always taken into account when
designing and evaluating the algorithm. Lastly, algo-
rithms are sometimes organized in rounds which hamper
implementation on real hardware.
To close the gap between the theory and systems sub-
communities, we provide the following recommendations:
1) Design algorithms such that unreliable communication
is not disruptive. 2) Analyze the impact of unreliable
communication on the algorithm’s performance. 3) Spe-
cify an algorithm’s energy efficiency by analyzing the
number of messages sent, differentiating between unicast
and broadcast messages. 4) Design algorithms that react
to other nodes’ messages, rather than using the concept
of rounds.
Although we realize it is sometimes more feasible to
analyze algorithms in an abstracted environment, this
does mean that the results are not directly applicable to
real-life sensor-networks. The results for the abstracted
environment can be used as a first step to a complete
working algorithm, but unfortunately the step to reality is
often overlooked.
8. Acknowledgements
We would like to thank Andreas Meier for his comments
and proof-reading.
9. References
[1] A. Mainwaring, J. Polastre, R. Szewcyk, D. Culler and J.
Anderson, “Wireless Sensor Networks For Habitat Mon-
itoring,” Proceedings of 1st ACM International Workshop
on Wireless Sensor Networks and Application (WSNA),
Atlanta, September 2002, pp. 88-97.
[2] K. Martinez, J. K. Hart and R. Ong, “Environmental sen-
sor networks,” IEEE Computer, Vol. 37, No. 8, 2004, pp.
50-56.
[3] M. Dyer, J. Beutel and L. Thiele, “S-XTC: A Signal-
Strenght Based Topology Control Algorithm for Sensor
Networks,” Proceedings of 8th International Symposium
on Autonomous Decentralized Systems (ISADS’07), Se-
dona, March 2007, pp. 508-518.
[4] S. Lin, J. Zhang, G. Zhou, L. Gu, T. He and J. A. Stank-
ovic, “ATPC: Adaptive Transmission Power Control for
Wireless Sensor Networks,” Proceedings of 4th ACM
Conference on Embedded Networked Sensor Systems
(SenSys’06), Boulder, November 2006, pp. 223-236.
[5] N. Reijers, G. Halkes and K. Langendoen, “Link Layer
Measurements in Sensor Networks,” Proceedings of 1st
IEEE Conference on Mobile Ad-Hoc and Sensor Systems
(MASS’04), Fort Lauderdale, October 2004, pp. 24-27.
[6] A. Woo, T. Tong and D. Culler, “Taming the Underlying
Challenges of Reliable Multihop Routing in Sensor Net-
works,” Proceedings of 1st ACM Conference on Embed-
ded Networked Sensor Systems (SenSys’03), Los Angeles,
November 2003, pp. 14-27.
[7] J. Zhao and R. Govindan, “Understanding Packet Deliv-
ery Performance in Dense Wireless Sensor Networks,”
Proceedings of 1st ACM Conference on Embedded Net-
worked Sensor Systems (SenSys’03), Los Angeles, No-
vember 2003, pp. 1-13.
[8] A. Cerpa and D. Estrin, “ASCENT: Adaptive Self-Con-
figuring Sensor Networks Topologies,” IEEE Transac-
tions on Mobile Computing, Vol. 3, No. 3, 2004, pp.
272-285.
[9] K. Langendoen and G. Halkes, “Energy-Efficient Me-
dium Access Control,” In: R. Zurawski, Ed., Embedded
Systems Handbook, CRC Press, 2005, pp. 1-34.
[10] G. Lu, B. Krishnamachari and C. Raghavendra, “An
Adaptive Energy-Efficient and Low-Latency MAC for
Data Gathering in Sensor Networks,” International Work-
shop on Algorithms for Wireless, Mobile, Ad Hoc and
Sensor Networks (WMAN), Santa Fe, April 2004, pp.
224-231.
[11] A. El-Hoiydi and J.-D. Decotignie, “WiseMAC: An Ultra
Low Power MAC Protocol for Multi-Hop Wireless Sensor
Networks,” Proceedings of 1st International Workshop on
Algorithmic Aspects of Wireless Sensor Networks (ALGO-
SENSORS’04), Turku, July 2004, pp. 18-31.
[12] J. Polastre, J. Hill and D. Culler, “Versatile Low Power
Media Access for Wireless Sensor Networks,” Proceed-
ings of 2nd ACM Conference on Embedded Networked
Sensor Systems (SensSys’04), Baltimore, November 2004,
pp. 95-107.