437  WSN Routing: Protocol Classification

437.1 Learning Objectives

By the end of this chapter, you will be able to:

  • Classify WSN Routing Protocols: Categorize protocols into data-centric, hierarchical, location-based, and QoS-aware families
  • Evaluate Protocol Trade-offs: Analyze proactive vs reactive, flat vs hierarchical, and single-path vs multi-path routing decisions
  • Apply LEACH Clustering: Understand how cluster head rotation balances energy consumption
  • Select Appropriate Protocols: Choose routing protocols based on application requirements and network constraints

437.2 Prerequisites

Before diving into this chapter, you should be familiar with:

NoteKey Concepts
  • Data-Centric Protocols: Route based on data content (Directed Diffusion, SPIN)
  • Hierarchical Protocols: Cluster-based organization (LEACH, TEEN, PEGASIS)
  • Location-Based Protocols: Geographic forwarding (GPSR, GEAR, GAF)
  • QoS-Aware Protocols: Meeting delay/reliability requirements (SAR, SPEED)
  • Proactive Routing: Pre-computed routes, immediate forwarding
  • Reactive Routing: On-demand route discovery

437.3 Classification of WSN Routing Protocols

WSN routing protocols can be classified into four major families based on their design philosophy and mechanisms.

%% fig-alt: "WSN routing protocol classification showing data-centric, hierarchical, location-based, and QoS-aware approaches with examples"
%%{init: {'theme': 'base', 'themeVariables': {'primaryColor': '#2C3E50', 'primaryTextColor': '#fff', 'primaryBorderColor': '#16A085', 'lineColor': '#16A085', 'secondaryColor': '#E67E22', 'tertiaryColor': '#ECF0F1', 'fontSize': '16px'}}}%%
graph TD
    subgraph "WSN Routing Protocol Classification"
        ROOT["WSN Routing<br/>Protocols"]

        DATA["Data-Centric<br/>Protocols"]
        HIER["Hierarchical<br/>Protocols"]
        LOC["Location-Based<br/>Protocols"]
        QOS["QoS-Aware<br/>Protocols"]

        DATA_EX["Directed Diffusion<br/>SPIN<br/>Rumor routing"]
        HIER_EX["LEACH<br/>TEEN<br/>PEGASIS"]
        LOC_EX["GPSR<br/>GEAR<br/>GAF"]
        QOS_EX["SAR<br/>SPEED<br/>MMSPEED"]
    end

    ROOT --> DATA
    ROOT --> HIER
    ROOT --> LOC
    ROOT --> QOS

    DATA --> DATA_EX
    HIER --> HIER_EX
    LOC --> LOC_EX
    QOS --> QOS_EX

    DATA -.->|"Content-based<br/>addressing"| DATA_CHAR["Attribute-value<br/>queries"]
    HIER -.->|"Cluster-based<br/>organization"| HIER_CHAR["Data aggregation<br/>at cluster heads"]
    LOC -.->|"Geographic<br/>position"| LOC_CHAR["Greedy forwarding<br/>to coordinates"]
    QOS -.->|"Application<br/>requirements"| QOS_CHAR["Delay, reliability,<br/>bandwidth guarantees"]

    style ROOT fill:#2C3E50,stroke:#16A085,stroke-width:3px,color:#fff
    style DATA fill:#16A085,stroke:#2C3E50,stroke-width:3px,color:#fff
    style HIER fill:#E67E22,stroke:#2C3E50,stroke-width:3px,color:#fff
    style LOC fill:#3498DB,stroke:#2C3E50,stroke-width:3px,color:#fff
    style QOS fill:#9B59B6,stroke:#2C3E50,stroke-width:3px,color:#fff
    style DATA_EX fill:#D5F4E6,stroke:#2C3E50,stroke-width:2px
    style HIER_EX fill:#FADBD8,stroke:#2C3E50,stroke-width:2px
    style LOC_EX fill:#AED6F1,stroke:#2C3E50,stroke-width:2px
    style QOS_EX fill:#D7BDE2,stroke:#2C3E50,stroke-width:2px
    style DATA_CHAR fill:#ECF0F1,stroke:#2C3E50,stroke-width:1px
    style HIER_CHAR fill:#ECF0F1,stroke:#2C3E50,stroke-width:1px
    style LOC_CHAR fill:#ECF0F1,stroke:#2C3E50,stroke-width:1px
    style QOS_CHAR fill:#ECF0F1,stroke:#2C3E50,stroke-width:1px

Figure 437.1: WSN routing protocol classification showing data-centric, hierarchical, location-based, and QoS-aware approaches with examples {fig-alt=“Tree diagram with WSN Routing Protocols as root branching into four categories: Data-Centric (Directed Diffusion, SPIN, Rumor routing) for attribute-value queries, Hierarchical (LEACH, TEEN, PEGASIS) for cluster-based data aggregation, Location-Based (GPSR, GEAR, GAF) for geographic greedy forwarding, and QoS-Aware (SAR, SPEED, MMSPEED) for delay and reliability guarantees”}

437.3.1 Data-Centric Protocols

  • Interest-based routing: Sinks express “interests” in data attributes
  • Attribute-value addressing: Route based on data content, not node IDs
  • Examples: Directed Diffusion, SPIN, Rumor Routing
  • Best for: Event-driven applications, query-response systems

437.3.2 Hierarchical Protocols

  • Cluster-based organization: Nodes grouped into clusters with elected heads
  • Data aggregation at cluster heads: Reduce transmissions to sink
  • Examples: LEACH, TEEN, PEGASIS
  • Best for: Large-scale networks with spatial data correlation

437.3.3 Location-Based Protocols

  • Geographic position awareness: Nodes know their coordinates (GPS)
  • Greedy forwarding: Route toward destination coordinates
  • Examples: GPSR, GEAR, GAF
  • Best for: Mobile nodes, outdoor deployments with GPS

437.3.4 QoS-Aware Protocols

  • Application requirement awareness: Meet delay, reliability, bandwidth needs
  • Multi-path routing: Provide redundancy for critical data
  • Examples: SAR, SPEED, MMSPEED
  • Best for: Industrial safety, healthcare, real-time monitoring

437.4 Protocol Selection Decision Flow

%% fig-alt: "Decision flowchart for selecting appropriate WSN routing protocol based on application requirements"
%%{init: {'theme': 'base', 'themeVariables': { 'primaryColor': '#2C3E50', 'primaryTextColor': '#fff', 'primaryBorderColor': '#16A085', 'lineColor': '#16A085', 'secondaryColor': '#E67E22', 'tertiaryColor': '#7F8C8D', 'fontSize': '12px'}}}%%
flowchart TD
    START([What does your<br/>WSN application need?])

    Q1{Do nodes have<br/>GPS/location?}
    Q2{Is data<br/>aggregation<br/>beneficial?}
    Q3{Need strict<br/>latency/reliability<br/>guarantees?}
    Q4{Network scale<br/>< 100 nodes?}

    LOC[Location-Based<br/>GPSR, GEAR]
    HIER[Hierarchical<br/>LEACH, TEEN]
    QOS[QoS-Aware<br/>SPEED, SAR]
    DATA[Data-Centric<br/>Directed Diffusion]
    FLAT[Flat Routing<br/>Flooding, Gossiping]

    START --> Q1
    Q1 -->|"Yes"| LOC
    Q1 -->|"No"| Q2

    Q2 -->|"Yes, similar<br/>readings nearby"| HIER
    Q2 -->|"No, each<br/>reading unique"| Q3

    Q3 -->|"Yes, critical app"| QOS
    Q3 -->|"No, best effort"| Q4

    Q4 -->|"Yes, small"| FLAT
    Q4 -->|"No, large"| DATA

    LOC --> LOC_USE["Use Cases:<br/>Outdoor deployments<br/>Mobile nodes<br/>Geographic queries"]
    HIER --> HIER_USE["Use Cases:<br/>Temperature monitoring<br/>Agricultural sensing<br/>High node density"]
    QOS --> QOS_USE["Use Cases:<br/>Industrial alarms<br/>Healthcare alerts<br/>Real-time tracking"]
    DATA --> DATA_USE["Use Cases:<br/>Event detection<br/>Query-driven sensing<br/>Adaptive sampling"]
    FLAT --> FLAT_USE["Use Cases:<br/>Simple deployments<br/>Low traffic<br/>Development/testing"]

    style START fill:#2C3E50,color:#fff
    style Q1 fill:#7F8C8D,color:#fff
    style Q2 fill:#7F8C8D,color:#fff
    style Q3 fill:#7F8C8D,color:#fff
    style Q4 fill:#7F8C8D,color:#fff
    style LOC fill:#3498DB,color:#fff
    style HIER fill:#E67E22,color:#fff
    style QOS fill:#9B59B6,color:#fff
    style DATA fill:#16A085,color:#fff
    style FLAT fill:#7F8C8D,color:#fff

Figure 437.2: Decision Flow View: This flowchart helps students select the appropriate routing protocol category based on application requirements. Key decision points include: (1) GPS availability enabling geographic routing, (2) data redundancy benefiting from hierarchical aggregation, (3) QoS requirements demanding guaranteed delivery, and (4) network scale determining flat vs. data-centric approaches. Each path leads to specific protocols with example use cases. {fig-alt=“Decision flowchart starting with application needs question, branching on GPS availability to Location-Based routing (GPSR, GEAR) for outdoor/mobile applications, then on data aggregation need to Hierarchical routing (LEACH, TEEN) for temperature/agricultural monitoring, then on QoS requirements to QoS-Aware routing (SPEED, SAR) for industrial/healthcare alerts, then on network scale to either Flat routing for small networks or Data-Centric (Directed Diffusion) for large event detection deployments”}

437.5 Routing Tradeoffs

437.5.1 Tradeoff: Proactive vs Reactive Routing

TipTradeoff: Proactive vs Reactive Routing

Decision context: When selecting a routing protocol for ad-hoc or sensor networks, choosing between proactive (table-driven) and reactive (on-demand) routing affects overhead, latency, and suitability for different traffic patterns.

Factor Proactive Routing (e.g., DSDV, OLSR) Reactive Routing (e.g., DSR, AODV)
Route Availability Immediate (routes pre-computed) Delayed (route discovery needed)
Control Overhead High (periodic updates always) Low when idle, high during discovery
Memory Usage High (full routing tables) Low (only active routes stored)
Initial Latency Zero (routes ready) High (discovery delay: 100ms-seconds)
Topology Changes Slow adaptation (wait for updates) Fast adaptation (discover new routes)
Energy (Low Traffic) Wasteful (updates even when idle) Efficient (no overhead when idle)
Energy (High Traffic) Efficient (no per-packet discovery) Can be high (frequent discoveries)
Best Traffic Pattern Continuous, predictable traffic Sporadic, event-driven traffic
Network Stability Better for stable topologies Better for mobile/dynamic topologies

Choose Proactive Routing when:

  • Traffic is continuous and predictable (regular sensor reporting)
  • Low latency is critical for every packet (real-time monitoring)
  • Network topology is relatively stable (fixed sensor deployments)
  • Memory and periodic energy cost are acceptable tradeoffs
  • Most nodes communicate frequently with the sink

Choose Reactive Routing when:

  • Traffic is sporadic or event-driven (fire alarms, intrusion detection)
  • Nodes are mobile and topology changes frequently (MANETs)
  • Memory is severely constrained (tiny embedded devices)
  • Energy conservation during idle periods is paramount
  • Only a subset of nodes communicate at any time

Default recommendation: Use Proactive Routing (like DSDV or collection tree protocols) for static WSN deployments with regular data collection where predictable latency matters. Use Reactive Routing (like AODV) for mobile ad-hoc networks or event-driven applications where most nodes are idle most of the time. Consider Hybrid Routing (like ZRP) for large networks where proactive routing within local zones and reactive routing between zones balances both concerns.

437.5.2 Tradeoff: Flat Routing vs Hierarchical Routing

WarningTradeoff: Flat Routing vs Hierarchical Routing

Option A (Flat Routing): All nodes are equal peers with identical roles. Each node maintains routes to neighbors and forwards packets hop-by-hop. Simple protocol design, ~50 bytes memory per neighbor. Path discovery: 3-8 hops typical, 150-400ms latency. Energy distribution even but total network energy higher (no aggregation). Scales to ~100-200 nodes before routing table overhead dominates.

Option B (Hierarchical/Cluster-Based Routing): Nodes organized into clusters with designated cluster heads (CHs). CHs aggregate data from 10-30 member nodes, reducing transmissions by 60-80%. Memory overhead: CHs require 200-500 bytes, members only 20-50 bytes. Path to sink: 2-4 hops through CH hierarchy. Scales to 1000+ nodes with multi-level clustering.

Decision Factors:

  • Choose Flat Routing when: Network has <100 nodes, all nodes have similar energy/capability, data from each node is unique and cannot be aggregated, network topology changes frequently (mobile nodes), or deployment requires simplicity over efficiency.
  • Choose Hierarchical Routing when: Network exceeds 200 nodes, sensor data has spatial correlation (neighboring sensors report similar values), energy efficiency is critical (battery-powered for years), sink is far from most sensors (reduces long-range transmissions), or different node classes exist (some mains-powered, some battery).
  • Quantified comparison: 500-node agricultural WSN reporting hourly soil moisture. Flat routing: 500 transmissions to sink per hour, average 4 hops = 2000 total transmissions. Hierarchical (50 clusters): 500 to CHs (1 hop) + 50 aggregated to sink (3 hops) = 650 total transmissions. Energy savings: 67.5%.

437.5.3 Tradeoff: Single-Path vs Multi-Path Routing

WarningTradeoff: Single-Path Routing vs Multi-Path Routing

Option A (Single-Path Routing): Each source maintains one optimal path to the sink. Path selection based on minimum hop count, ETX, or energy metric. Memory: 4-8 bytes per destination (next-hop only). Packet overhead: 0 bytes (implicit routing). Link failure: requires route rediscovery (100-500ms delay), packets dropped during recovery. Typical packet loss during transition: 5-15%.

Option B (Multi-Path Routing): Each source maintains 2-4 disjoint paths to the sink. Packets sent on primary path; backup paths used on failure or for load balancing. Memory: 16-32 bytes per destination. Packet overhead: 2-4 bytes (path identifier). Link failure: instant failover to backup path (<10ms). Achieves 99.5%+ delivery reliability even with 10% link failure rate.

Decision Factors:

  • Choose Single-Path when: Memory is severely constrained (<1KB RAM), packet delivery delays are acceptable (non-critical monitoring), links are stable and reliable (>95% PRR), or energy conservation outweighs reliability (very long-lived deployments).
  • Choose Multi-Path when: Application requires high reliability (>99% delivery rate), links are unstable or intermittent (industrial interference, mobile nodes), latency-critical applications cannot tolerate route rediscovery delay, or sink redundancy exists (multiple gateways can receive data).
  • Quantified comparison: Industrial monitoring with 15% background packet loss. Single-path: 85% delivery, recovery time 250ms on link failure. Multi-path (2 paths): 97.8% delivery (both paths must fail simultaneously), failover time 5ms. For 1000 packets/hour: 150 lost (single) vs 22 lost (multi-path).

437.6 Interactive: LEACH Clustering Demo

Explore how LEACH (Low-Energy Adaptive Clustering Hierarchy) balances energy consumption through randomized cluster head rotation. Watch energy depletion over multiple rounds and compare with direct transmission.

How LEACH Works:

  1. Cluster Head Election: Each round, nodes independently decide to become cluster heads (CH) based on probability p. Nodes that were recently CH have lower probability, ensuring rotation.

  2. Cluster Formation: Non-CH nodes join the nearest cluster head to minimize transmission distance.

  3. Data Aggregation: Members send data to their CH (short-distance, low energy). CHs aggregate data and transmit once to the sink (long-distance, high energy).

  4. Energy Balancing: By rotating the CH role, no single node bears the aggregation burden throughout network lifetime.

Observe:

  • Color gradient shows node energy levels (green=healthy, red=depleted)
  • CH markers show current cluster heads and cluster regions
  • Energy bars compare LEACH vs. direct transmission
  • Run multiple rounds to see how CH role distributes and energy depletes evenly

437.7 Knowledge Check

Question: Why do WSN routing protocols often avoid using traditional IP-based routing (like OSPF or BGP)?

Explanation: WSN constraints vs. traditional routing: (1) Memory overhead: OSPF maintains topology database for entire network. 1000-node network requires ~100KB routing table. Sensor nodes typically have 4-32KB RAM total - insufficient! (2) Computation: OSPF runs Dijkstra’s shortest path algorithm requiring O(N^2) operations. Sensor CPUs (8-32 MHz) can’t efficiently compute large topologies. (3) Communication overhead: OSPF floods link-state advertisements (LSAs) periodically and on topology changes. In dense WSN (100s-1000s nodes), LSA flooding would consume significant bandwidth and energy. (4) Address management: IP requires unique addresses for every node. IPv4 addresses (4 bytes) + routing (4 bytes) = 8 bytes overhead per packet. When sensor data is 2 bytes, overhead is 4x! IPv6 even worse (16-byte addresses). (5) Energy-awareness: Traditional routing optimizes for performance (throughput, latency), not energy.

WSN-specific optimizations: Data-centric addressing (content not node ID), implicit addressing (relative position instead of global ID), in-network aggregation (reduce packets), energy-aware metrics (avoid low-battery nodes).

437.8 Summary

This chapter classified WSN routing protocols and explored key design tradeoffs:

Key Takeaways:

  1. Four Protocol Families: Data-centric, hierarchical, location-based, and QoS-aware protocols each address different application needs

  2. Proactive vs Reactive: Proactive for stable networks with continuous traffic; reactive for mobile/event-driven applications

  3. Flat vs Hierarchical: Hierarchical clustering (LEACH) dramatically reduces energy for large-scale networks with spatial data correlation

  4. Single-Path vs Multi-Path: Multi-path routing provides reliability at the cost of memory and complexity

  5. LEACH Mechanism: Rotating cluster heads balances energy consumption and extends network lifetime

437.9 What’s Next?

The next chapter dives deep into Directed Diffusion, a foundational data-centric routing protocol that uses interest propagation and gradients to establish efficient data paths.

Continue to Directed Diffusion →