changed. You can check the current page or check for previous versions at the Internet Archive. Yahoo! is not affiliated with the authors of this page or responsible for its content.
Experimental Evaluation of Topology Control and Synchronization for In-Building Sensor Network Applications
Experimental Evaluation of Topology Control and Synchronization
for In-Building Sensor Network Applications

W. Steven Conner Jasmeet Chhabra Mark Yarvis Lakshman Krishnamurthy
Intel Research & Development
2111 N.E. 25
th
Avenue
Hillsboro OR, 97124
{w.steven.conner, jasmeet.chhabra, mark.d.yarvis, lakshman.krishnamurthy}@intel.com


August 2003


ABSTRACT
While multi-hop networks consisting of 100s or 1000s of inexpen-
sive embedded sensors are emerging as a means of mining data
from the environment, inadequate network lifetime remains a major
impediment to real-world deployment. This paper describes several
applications deployed throughout our building that monitor confer-
ence room occupancy and environmental statistics and provide
access to room reservation status. Because it is often infeasible to
locate sensors and display devices near power outlets, we designed
two protocols that allow energy conservation in a large class of
sensor network applications. The first protocol, Relay Organization
(ReOrg), is a topology control protocol which systematically shifts
the networks routing burden to energy-rich nodes, exploiting het-
erogeneity. The second protocol, Relay Synchronization (ReSync),
is a MAC protocol that extends network lifetime by allowing nodes
to sleep most of the time, yet wake to receive packets. When com-
bined, ReOrg and ReSync lower the duty cycle of the nodes, ex-
tending network lifetime. To our knowledge, this paper presents the
first experimental testbed evaluation of energy-aware topology
control integrated with energy-saving synchronization. Using a 54-
node testbed, we demonstrate an 82-92% reduction in energy con-
sumption, depending on traffic load. By rotating the burden of
routing, our protocols can extend network lifetime by 5-10 times.
Finally, we demonstrate that a small number of wall-powered nodes
can significantly improve the lifetime of a battery-powered network.
1. INTRODUCTION
Networked sensors are creating a new class of applications. Many
of these applications connect users with the real world to help con-
duct scientific field studies [16], raise business bottom lines [26],
and improve everyday life [7]. These networks will consist of 100s
or 1000s of networked sensors and are enabled by small, inexpen-
sive devices such as RFID tags, smart cards, and sensors. In the not
so distant future these devices will be sufficiently small and inex-
pensive to be embedded into the environment and networked using
low-power radios. Sensor networks will be deployed in an ad hoc
manner and use multi-hop networking protocols to ensure full con-
nectivity, fault tolerance, and long operational life, making real-
world information and control ubiquitously available [25].
We have developed experimental applications to solve everyday
problems in our work environment that monitor occupancy of con-
ference rooms, provide conference room status in a ubiquitous
manner, and monitor environmental parameters such as temperature
throughout our building [7]. These are illustrative examples from
Other names and brands may be claimed as the property of others.
the class of in-building sensing applications for which one of the
biggest hurdles towards deployment is energy provisioning. Even
in buildings, where power outlets are relatively abundant, it is not
always feasible to locate sensors near these outlets. While a few
nodes may be wall powered, many require battery power since run-
ning new wires to sensors is expensive and time consuming. This
class of applications requires self-configuring energy-efficient pro-
tocols that allow the network to survive many months, or even
years, when a large number of nodes operate on constrained battery
power. Nodes should be able to spend significant portions of their
time sleeping to save energy, yet still maintain communication [27]
[32].


This paper makes the following contributions. We specify require-
ments for in-building applications based on their characteristics and
real-world deployment challenges. We present the design of a to-
pology control protocol, Relay Organization (ReOrg), which sys-
tematically exploits heterogeneous nodes (wall powered/battery
powered) in the context of real-world applications. ReOrg creates a
network backbone reducing the number of nodes that participate in
network routing. We then describe the design of Relay Synchroni-
zation (ReSync), a MAC protocol that allows nodes to sleep when
not communicating and tunes the communication duty cycle be-
tween individual neighbors based on the backbone created by Re-
Org. We present the elements required to evaluate the performance
of energy conservation protocols in a sensor network testbed, in-
cluding methods to estimate energy consumption, weigh the impact
of various hardware design choices, and fairly evaluate in the pres-
ence of packet loss. We demonstrate these elements in the context
of the ReOrg and ReSync protocols in a 54 node testbed of Berke-
ley motes [12]. To the best of our knowledge, this paper provides
the first experimental testbed study of integrated topology control
and synchronization protocols in a sensor network. Our results
confirm previous simulation studies and provide additional insights.
The experimental evaluation is summarized by several key results.
First, while a topology control protocol increases network overhead,
a better network topology can reduce overall energy consumption
across the network if the MAC protocol allows nodes to sleep. We
demonstrate a savings of as much as 63% with existing hardware
and 83% with improved hardware. Second, by tightly integrating
backbone creation with the MAC protocol, we achieved a reduction
in energy consumption of between 82-92%. A benefit is still ob-
tained after considering packet loss. We further demonstrate that
because our protocols allow nodes to take turns sharing the burden
of packet forwarding, this 82-92% gain can be materialized into a 5-
10 fold increase in network lifetime. Thus, individual nodes are not
necessarily sacrificed to achieve an overall energy reduction. Fi-
nally, we demonstrate that our protocols take advantage of hetero-
geneity to further increase network lifetime. As a result, the lifetime
of a battery-powered network can be increased through the addition
of a small number of wall-powered nodes.
2. IN-BUILDING APPLICATIONS
In-building applications form a large class of sensor network appli-
cations. We have deployed several experimental applications in our
workplace that perform a variety of functions such as monitoring
conference room occupancy, providing conference room occupancy
and reservation status in a ubiquitous manner, and monitoring envi-
ronmental parameters such as temperature. In this section we pro-
vide application details to motivate the network protocol design.
In many modern office complexes, closed-wall offices have been
replaced with high-density cubicles to inspire an atmosphere of
open collaboration and accessibility among people in the building.
However, the lack of private offices means that meetings must be
held in conference rooms. Since most rooms are reserved days or
weeks in advance, it is often not possible to reserve a room with
little or no notice. However, meetings commonly do not last the
entire reservation time, and it is common for users to wander around
a building in search of an empty room for an impromptu meeting.
We have built a system that provides people access to room occu-
pancy status and allows them to find empty rooms from handhelds
and PCs.
Our system consists of a network of sensors deployed in and around
conference rooms. In-room sensors are connected to motion detec-
tors (Figure 1 (a)), which monitor room occupancy status. A gate-
way node receives the sensor data which is aggregated and stored to
provide status information to desktop users over the web. Figure 2
(a) shows a screen shot from a web application that provides live
occupancy information for rooms on a given building floor. Users
of this application can avoid searching for a conference room and
walk directly to an empty room. We have also connected PDAs to
the sensor network, allowing mobile users to obtain the status of
nearby conference rooms directly (Figure 2 (b)). Occupancy infor-
mation is also available via status nodes at the end of the aisles that
indicate the presence of an empty room in that aisle.
In addition to providing live occupancy data, motion detector data
may also be compiled over time for future analysis. Figure 2 (c)
illustrates an application that compares gathered room usage statis-
tics with dat