28-03-2014, 12:40 PM
On Hierarchical Routing in Wireless Sensor Networks
Hierarchical Routing.pdf (Size: 246.47 KB / Downloads: 15)
ABSTRACT
Hierarchical routing is a promising approach for point-to-
point routing with very small routing state. While there are
many theoretical analyses and high-level simulations demon-
strating its benefits, there has been little work to evaluate it
in a realistic wireless sensor network setting. Based on nu-
merous proposed hierarchical routing infrastructures, we de-
velop a framework that captures the common characteristics
of the infrastructures and identifies design points where the
infrastructures differ. We then evaluate the implementation
of the framework in TOSSIM and on a 60-node testbed. We
demonstrate that from the practical perspective hierarchical
routing is also an appealing routing approach for sensor net-
works. Despite only logarithmic routing state, it can offer
low routing stretch: the average of ∼1.25 and the 99-th per-
centile of 2. Moreover, a hierarchical routing infrastructure
can be autonomously bootstrapped and maintained by the
nodes. By exploring the design points within our framework,
the hierarchy maintenance protocol can optimize different
metrics, such as the latency of bootstrapping and repairing
the hierarchy after failures or the traffic volume, depending
on the application requirements. Finally, we also identify a
number of practical issues which we believe the applications
employing hierarchical routing should be aware of.
INTRODUCTION
A plethora of recently proposed wireless sensor network
(WSN) applications as well as a new dedicated IETF work-
ing group [27] evidence that point-to-point routing is impor-
tant functionality for future low-power wireless systems [7].
In such systems, a point-to-point routing infrastructure di-
rectly affects scalability, efficiency, and reliability.
RELATED WORK
Although point-to-point routing is a well-studied problem,
WSNs pose novel challenges, in particular, severely limited
effective node bandwidth and memory. These challenges
constrain the use of shortest-path routing protocols, such as
DSR [10] and AODV [20], in large WSNs as the control traf-
fic and state of such protocols do not scale well. Routing
protocols for large WSNs thus aim at minimizing the node
state and the traffic for infrastructure maintenance. This is
achieved with the following techniques: geographic routing,
graph embedding, compact routing, or hierarchical routing.
In the first technique [11, 14, 17], a node’s routing ad-
dress corresponds to the node’s geographic coordinates, and
the node’s routing table consists of the coordinates of the
node’s neighbors (i.e., the nodes within the radio range of
the present node). In this way, the routing infrastructure re-
quires only O(1) state per node. However, practical, effi-
cient geographic routing is essentially still an open research
question due to the cases in which greedy forwarding toward
the destination fails. Because of real-world issues, such as
geographic localization errors or physical obstacles prevent-
ing radio communication, special solutions are necessary to
handle such cases [12]. These solutions involve protocols
for planarizing the neighborhood graph using cross-link de-
tection (CLDP) [12] or for building hull trees [16].
HR ALGORITHM
HR has many variants, all based on the same basic princi-
ples [6, 26]. We have analyzed a number of HR infrastruc-
tures proposed to date to choose an addressing and routing
algorithm that, in our opinion, is well suited for implemen-
tation on resource-constrained sensor nodes. In the end, we
have selected an algorithm commonly known as landmark
routing [2, 15, 26], which we describe next. In addition to
delivering all the aforementioned properties of hierarchical
routing, the selected algorithm has many proposed protocols
for bootstrapping and maintaining the routing infrastructure,
which allows us to illustrate various trade-offs.
Implementation Remarks
As the implementation platform for our framework we have
chosen TinyOS 2.0 and assumed a standard protocol stack.
At the top, an application layer receives routing requests
from a PC and periodically reports back the state of the HR
infrastructure and the delivery status of the requests. We
have not implemented node-id-to-label resolution, and in-
stead, when routing, source nodes obtain destination labels
with out-of-band means. This is because naming in WSNs is
typically data centric, and thus, obtaining the destination ad-
dress is often application specific. If necessary, the node-id-
to-label mapping can be implemented as a distributed hash
table on top of the cluster hierarchy [2, 3, 15].
DISCUSSION AND CONCLUSIONS
The results obtained with the embedded implementations
of our framework indicate that hierarchical routing is indeed
an appealing point-to-point routing paradigm for large low-
power wireless networks. There are, however, some issues.
First, performance results reported for high-level simula-
tions should be considered with caution, as we demonstrated
that they can diverge significantly, in terms of both routing
state and routing stretch, from the results with a more real-
istic communication model. Such divergence can have pro-
found impact on a few systems aspects of WSNs using HR.
Examples of such aspects include provisioning node memory
for the routing infrastructure and ensuring certain quality of
service with respect to the routing latency.