Data collected by sensor nodes in a WSN is typically propagated toward a base station
(gateway) that links the WSN with other networks where the data can be visualized, analyzed,
and acted upon. In small sensor networks where sensor nodes and a gateway are in
close proximity, direct (single-hop) communication between all sensor nodes and the gateway
may be feasible. However, most WSN applications require large numbers of sensor
nodes that cover large areas, necessitating an indirect (multi-hop) communication approach.
That is, sensor nodes must not only generate and disseminate their own information, but also
serve as relays or forwarding nodes for other sensor nodes. The process of establishing paths
from a source to a sink (e.g., a gateway device) across one or more relays is called routing
and is a key responsibility of the network layer of the communication protocol stack. When
the nodes of a WSN are deployed in a deterministic manner (i.e., they are placed at certain
predetermined locations), communication between them and the gateway can occur using
predetermined routes. However, when the nodes are deployed in a randomized fashion (i.e.,
they are scattered into an environment randomly), the resulting topologies are nonuniform
and unpredictable. In this case, it is essential for these nodes to self-organize, that is, they
must cooperate to determine their positions, identify their neighbors, and discover paths to
the gateway device. This chapter introduces the main categories of routing protocols and
data dissemination strategies and discusses state-of-the-art solutions for each category
7.1 Overview
The key responsibility of the network layer is to find paths from data sources to sink devices
(e.g., gateways). In the single-hop routing model (left graph in Figure 7.1), all sensor nodes
are able to communicate directly with the sink device. This direct communication model is
the simplest approach, where all data travels a single hop to reach the destination. However,
in practical settings, this single-hop approach is unrealistic and a multi-hop communication
model (right graph in Figure 7.1) must be used. In this case, the critical task of the
network layer of all sensor nodes is to identify a path from the sensor to the sink across multiple
other sensor nodes acting as relays. This design of a routing protocol is challenging
due to the unique characteristics of WSNs, including resource scarcity or the unreliability
of the wireless medium. For example, the limited processing, storage, bandwidth, and
energy capacities require routing solutions that are lightweight, while the frequent dynamic
changes in a WSN (e.g., topology changes due to node failures) require routing solutions
Figure 7.1 Single-hop routing model (left) versus multi-hop routing model (right).
that are adaptive and flexible. Further, unlike traditional routing protocols for wired networks,
protocols for sensor networks may not be able to rely on global addressing schemes
(e.g., IP addresses on the Internet).
There are various ways to classify routing protocols.
Figure 7.2 presents three different
classifications based on the network structure or organization, the route discovery process,
and the protocol operation (Al-Karaki and Kamal 2004). With respect to network organization,
most routing protocols fit into one of three classes. Flat-based routing protocols
consider all nodes of equal functionality or role. In contrast, in hierarchical-based routing
protocols, different nodes may assume different roles in the routing process, that is, some
nodes may forward data on behalf of others, while other nodes only generate and propagate
their own sensor data. Location-based routing protocols rely on the location information
from nodes to make routing decisions. Routing protocols are responsible for identifying or
discovering routes from a source or sender to the intended receiver. This route discovery
process can also be used to distinguish between different types of routing protocols. Reactive
protocols discover routes on-demand, that is, whenever a source wants to send data
to a receiver and does not already have a route established. While reactive route discovery
Figure 7.2 Categories of routing protocols.
incurs delays before actual data transmission can occur, proactive routing protocols establish
routes before they are actually needed. This category of protocols is also often described
as table-driven, because local forwarding decisions are based on the contents of a routing
table that contains a list of destinations, combined with one or more next-hop neighbors
that lead toward these destinations and costs associated with each next hop option. While
table-driven protocols eliminate the route discovery delays, they may be overly aggressive
in that routes are established that may never be needed. Further, the time interval between
route discovery and actual use of the route can be very large, potentially leading to outdated
routes (e.g., a link along the route may have broken in the meantime). Finally, the
cost of establishing a routing table can be significant, for example, in some protocols it
involves propagating a node’s local information (such as its list of neighbors) to all other
nodes in the network. Some protocols exhibit characteristics of both reactive and proactive
protocols and belong to the category of hybrid routing protocols. Finally, routing protocols
also differ in their operation, for example, negotiation-based protocols aim to reduce
redundant data transmissions by relying on the exchange of negotiation messages between
neighboring sensor nodes before actual data transfers occur. The SPIN family of protocols
(Section 7.5) belongs to this category. Multipath-based protocols use multiple routes simultaneously
to achieve higher performance or fault tolerance. Query-based routing protocols
are receiver-initiated, that is, sensor nodes send data in response to queries issued by the
destination node. The goal of QoS-based routing protocols is to satisfy a certain Qualityof-
Service (QoS) metric (or a combination of multiple metrics), such as low latency, low
energy consumption, or low packet loss. Finally, routing protocols also differ in the way
they support in-network data processing. Coherent-based protocols perform only a minimum
amount of processing (e.g., eliminating duplicates, time-stamping) before sensor data
is sent to receivers and data aggregators. However, in noncoherent-based protocols, nodes
may perform significant local processing of the raw data before it is sent to other nodes for
further processing.
Further, when sensor data is explicitly sent to one or more receivers, routing is considered
node-centric. Most routing protocols focus on unicast routing, that is, forwarding of sensor
data to exactly one receiver. Multicast and broadcast routing approaches, on the other hand,
disseminate data to multiple or all nodes, respectively. Data-centric routing is used when
nodes are not explicitly addressed, but instead receivers are implicitly described by certain
attributes. For example, a query issued by the gateway device may request temperature
readings and only sensors that can collect such information respond to the query