Data Collected by Sensor Nodes in a WSN Is Typically Propagated Toward a Base Station
Network Layer
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
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
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.
7.2 Routing Metrics
Wireless sensor networks and their applications vary widely in their constraints and
characteristics, which must be taken into consideration in the design of a routing protocol.
For example, most WSNs will be constrained in terms of their available energy, processing
power, and storage capacities. Sensor networks can vary widely in scale, the geographic
areas they cover, and their position-awareness. Global addressing schemes (such as IP
addresses used on the Internet) may be unavailable and even nonfeasible, particularly in
networks with heterogeneous nodes and node mobility. Finally, from the application’s
perspective, sensor data may be collected in various different approaches. In time-driven
schemes (e.g., environmental monitoring), nodes propagate their collected sensor data
periodically to a sink or gateway device. In event-driven schemes (e.g., wildfire detection),
nodes only report their collected information when events of interest occur. Finally, in
query-driven schemes, it is the responsibility of the sink to request data from sensors when
needed. Regardless of the scheme used in the network, the design of a routing protocol is
driven by the resources available in the network and the needs of the applications. Toward
this end, routing metrics are used to express a variety of objectives of a routing protocol with
respect to the consumption of these resources or the performance an application perceives.
This section provides a brief overview of commonly used routing metrics in WSNs.
7.2.1 Commonly Used Metrics
7.2.1.1 Minimum Hop
The most common metric used in routing protocols is minimum hop (or shortest hop), that
is, the routing protocol attempts to find the path from the sender to the destination that
requires the smallest number of relay nodes (hops). In this simple technique, every link has
the same cost and a minimum-hop routing protocol selects the path that minimizes the total
cost of data propagation from source to destination. The basic idea behind this metric is that
using the shortest path will result in low end-to-end delays and low resource consumptions,
because the smallest possible number of forwarding nodes will be involved. However, since
the minimum-hop approach does not consider the actual resource availability on each node,
the resulting route is probably nonoptimal in terms of delay, energy, and congestion avoidance.
Nevertheless, the minimum-hop metric is being used in many routing protocols due
to its simplicity and its isotonicity, that is, its ability to ensure that the order of weights of
two paths is preserved even when they are appended or prefixed by a common third path.
7.2.1.2 Energy
Undoubtedly the most crucial aspect of routing in WSNs is energy efficiency. However,
there is not one unique energy metric that can be applied to the routing problem; instead,
there are various different interpretations of energy efficiency, including (Singh et al. 1998):
1. Minimum energy consumed per packet: This is the most natural concept of energy efficiency,
that is, the goal is to minimize the total amount of energy expended for the
propagation of a single packet from the source to the destination. The total energy is then
the sum of the energy consumed by each node along a route for receiving and transmitting
the packet. Figure 7.3 shows an example of a small sensor network, where a source
node wishes to transmit a packet to a destination node using a route that minimizes the
packet’s energy overheads. The number on each link indicates the cost of propagating
the packet over this link. As a consequence, the packet will travel via nodes A–D–G
(with a total cost of 5). Note that this is different from the minimum-hop route (B–G).
2. Maximum time to network partition: A network partitions into several smaller subnetworks
when the last node that links two parts of the network expires or fails. As a
consequence, a subnetwork may not be reachable, rendering the sensor nodes within the
subnetwork useless. Therefore, the challenge is to reduce the energy consumption on
nodes that are crucial to maintaining a network where every sensor node can be reached
via at least one route. For example, a minimal set of nodes, whose removal will cause a
network to partition, can be found using the max-flow–min-cut theorem. Once a routing
protocol has identified these critical nodes, it can attempt to balance the traffic load such
that premature expiration of these nodes is prevented. In Figure 7.3, node D is such a
node, for example, if node D’s battery becomes depleted, nodes F, I, and J would not be
reachable from any other node in the network.
3. Minimum variance in node power levels: In this scenario, all nodes within the network
are considered equally important and the challenge is to distribute the energy consumption
across all nodes in the network as equally as possible. The goal of such an approach
could be to maximize the lifetime of the entire network, for example, instead of some
nodes expiring sooner than others and thereby continuously decreasing the network size,
one could aim at keeping as many nodes alive as long as possible. In the ideal (but practically
impossible) case, all nodes would expire at exactly the same time.
4. Maximum (average) energy capacity: In this approach, the focus is less on the energy
cost of packet propagation, but instead on the energy capacity (i.e., the current battery
charge level) of the nodes.Arouting protocol that uses this metric would then favor routes
that have the largest total energy capacity from source to destination. In Figure 7.3, the
numbers in parentheses below the nodes indicate the nodes’ remaining energy capacity.
In this example, a routing protocol could select path C–E–G, which has the largest total
capacity (i.e., 8). A routing protocol that uses this metric must be carefully designed to
avoid the pitfall of choosing unnecessarily long routes in order to maximize the total
energy capacity. A variation of this metric is to maximize the average energy capacity,
which can avoid this problem.
5. Maximum minimum energy capacity: Finally, instead of maximizing the energy capacities
of the entire path, the primary routing goal could be to select the path with the largest
minimum energy capacity. This technique also favors routes with larger energy reserves,
but also protects low-capacity nodes from premature expiration. In Figure 7.3, a protocol
using this metric would choose B–G, since the minimum capacity along this route is 2,
which is larger than the minimum capacities of all other possible routes.
These different formulations of energy awareness lead to very different protocol implementations
that differ in their results (i.e., the selected routes) and their overheads. For
example, to determine the minimum energy consumed per packet, the cost for receiving
and transmitting a packet may be based on a cost function with the packet size as input. On
the other hand, energy capacities change over time and therefore a routing protocol using a
capacity-based metric must obtain these capacities from other nodes from time to time.
7.2.1.3 Quality-of-Service
The term Quality-of-Service (QoS) refers to defined measures of performance in networks,
including end-to-end latency (or delay) and throughput, but also jitter (variation in latency)
and packet loss (or error rate). The choice of a QoS metric depends on the type of
application. Sensor networks performing target detection and tracking will require low
end-to-end transmission delays for their time-sensitive sensor data, while data-intensive
networks (e.g., multimedia sensor networks) may require high throughput. The Expected
Transmission Time (ETT) is a common metric to express latency and is defined as
(Draves et al. 2004):
ETT = ETT ×
S
B
(7.1)
where S is the average size of a packet and B is a link’s bandwidth. It expresses the expected
time necessary to successfully transmit a packet at the MAC layer. To capture packet loss as
a routing metric, the Expected Transmission Count (ETX) can be used, which is defined as
the number of transmissions necessary to successfully deliver a packet over a wireless link
(Couto et al. 2003). Very often multiple QoS metrics (e.g., end-to-end latency and packet
loss rate) are combined, for example, the bandwidth-delay product refers to the product of
a link’s bandwidth and its end-to-end delay. Which metrics are chosen affects the design
of the network at different levels, including the network (routing) and MAC layers. Most
WSNs must strike a balance between satisfying the application-specific QoS requirements
and the goal of energy efficiency in the network as whole.
7.2.1.4 Robustness
Many sensor applications may wish to use routes that stay stable and reliable for long periods
of time. Toward this end, a node can measure or estimate the link quality to each of its
neighbors and then select a next hop neighbor that increases the probability of a successful
transmission. However, this metric is rarely used alone. A routing protocol could identify
several minimum-hop paths and then select the one with the highest total or average link
quality along these paths. In networks with mobile nodes, a routing protocol could also use
the link stability metric, which measures how likely it is that a link will be available in
the future. These metrics can be used to bias route selection toward more robust paths and
stationary nodes.
7.3 Flooding and Gossiping
An old and simple strategy to disseminate information into a network or to reach a node
at an unknown location is to flood the entire network. A sender node broadcasts packets
to its immediate neighbors, which will repeat this process by rebroadcasting the packets to
their own neighbors until all nodes have received the packets or the packets have traveled
for a maximum number of hops. With flooding, if there exists a path to the destination (and
assuming lossless communication), the destination is guaranteed to receive the data. The
main advantage of flooding is its simplicity, while its main disadvantage is that it causes
heavy traffic. Therefore, measures must be taken to ensure that packets do not travel through
the network indefinitely. For example, maximum-hop counts are used to limit the number
of times a packet is forwarded. It should be set large enough so that every intended receiver
can be reached, but also small enough to ensure that packets do not travel too long in the
network. Further, sequence numbers in packets (combined with the address of the source)
can be used to uniquely identify a packet. When a node receives a packet that it has already
forwarded (i.e., with the same destination–source pair and the same sequence number),