78  WSN Routing: Protocol Classification

In 60 Seconds

WSN routing protocols fall into four families: data-centric (route by content), hierarchical (cluster-based aggregation via LEACH), location-based (geographic forwarding with GPS), and QoS-aware (meeting latency/reliability targets). A 500-node agricultural WSN using flat routing wastes 67% more energy than hierarchical LEACH clustering. Match protocol to constraints: GPS available? Geographic. Need aggregation? Hierarchical. Event queries? Data-centric.

78.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: Compare proactive vs reactive, flat vs hierarchical, and single-path vs multi-path routing decisions
• Apply LEACH Clustering: Calculate how cluster head rotation balances energy consumption across network nodes
• Select Appropriate Protocols: Choose routing protocols based on application requirements and network constraints

For Beginners: WSN Routing: Protocol Classification

Routing in wireless sensor networks determines how data finds its way from sensors to the collection point. Think of water flowing downhill through a network of channels – routing protocols create efficient pathways for data, choosing routes that conserve battery power while ensuring messages arrive reliably.

78.2 Prerequisites

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

• WSN Routing Introduction: Understanding WSN routing fundamentals
• WSN Routing Challenges: Why traditional routing fails in sensor networks

MVU: Minimum Viable Understanding

Core concept: WSN routing protocols fall into four families – data-centric (route by content), hierarchical (cluster-based aggregation), location-based (geographic forwarding), and QoS-aware (meeting latency/reliability targets) – each optimized for different application requirements.

Why it matters: Choosing the wrong protocol family wastes energy, misses deadlines, or fails at scale. A 500-node agricultural WSN using flat routing wastes 67% more energy than hierarchical LEACH clustering.

Key takeaway: Match your protocol to your constraints: GPS available? Use geographic. Need aggregation at scale? Use hierarchical. Event-driven queries? Use data-centric. Strict latency? Use QoS-aware.

For Kids: Meet the Sensor Squad!

There are different ways to pass messages in a sensor network – just like there are different ways to organize a big school project!

78.2.1 The Sensor Squad Adventure: Four Teams, Four Strategies

The Sensor Squad needed to send weather reports to Farmer Jones from all across the farm. But with so many sensors, they needed a plan!

Team 1 - The Content Crew (Data-Centric): “I do not care WHO sent the message,” said Farmer Jones. “Just tell me if ANYTHING is too hot!” So the sensors only sent messages when they had something important to report. This is like raising your hand in class only when you have the answer!

Team 2 - The Cluster Captains (Hierarchical): Sammy organized the sensors into groups. Each group picked a leader who collected everyone’s readings, made a summary, and sent just ONE message. “Instead of 20 messages, I send 1!” said Sammy the group leader.

Team 3 - The Map Readers (Location-Based): Lila knew exactly where everyone was on the farm. “Just pass the message toward the farmhouse! Whoever is closest to it should carry the message next.” Simple – like giving directions using a map!

Team 4 - The Emergency Squad (QoS-Aware): When Max detected a fire, speed mattered! “This message MUST arrive in 2 seconds!” So the Emergency Squad used the fastest possible path, even if it used more energy.

78.2.2 Key Words for Kids

Word	What It Means
Data-centric	Caring about WHAT the message says, not who sent it
Hierarchical	Organizing into groups with leaders who summarize
Location-based	Using a map to pass messages toward the destination
QoS-aware	Making sure important messages arrive on time

Key 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

78.3 Classification of WSN Routing Protocols

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

Figure 78.1: WSN routing protocol classification showing data-centric, hierarchical, location-based, and QoS-aware approaches with examples

78.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

78.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

Putting Numbers to It

LEACH Cluster Head Energy Analysis

In LEACH, cluster heads (CHs) consume significantly more energy than members. Calculate expected energy per node:

Deployment: 100 nodes, desired 5 CHs per round (\(p = 0.05\) probability)

CH energy cost per round:

• Receive from 19 members (avg): \(19 \times 0.3 = 5.7\) mJ
• Aggregate 19 readings: \(19 \times 0.1 = 1.9\) mJ
• Transmit to sink (100m, long-range): \(2.0 \times (1 + 1^2) = 4.0\) mJ
• CH overhead: 0.5 mJ
• Total CH cost: \(5.7 + 1.9 + 4.0 + 0.5 = 12.1\) mJ/round

Member energy cost per round:

• Transmit to CH (20m, short-range): \(0.5 \times (1 + 0.2^2) = 0.52\) mJ
• Total member cost: 0.52 mJ/round

CH rotation fairness:

• Each node is CH with probability \(p = 0.05\)
• Expected energy per node per round: \(0.05 \times 12.1 + 0.95 \times 0.52 = 1.10\) mJ/round

Network lifetime (3000 mAh battery at 3.3V = 35,640 J): \(L = \frac{35,640 \text{ J}}{100 \text{ nodes} \times 1.10 \text{ mJ/round}} = 324,000\) rounds

With 1 round/hour: 37 years. Compare to direct transmission (each node → sink): \(2.0 \times (1 + 1^2) = 4.0\) mJ/round → 9 years. LEACH provides 4× lifetime improvement.

78.4 LEACH Energy Trade-off Calculator

Adjust the LEACH parameters below to see how cluster head probability and battery size affect network lifetime:

viewof p_leach = Inputs.range([0.01, 0.3], {value: 0.05, step: 0.01, label: "CH probability p"})
viewof num_nodes_leach = Inputs.range([20, 500], {value: 100, step: 10, label: "Number of nodes"})
viewof battery_v_leach = Inputs.range([2.0, 5.0], {value: 3.3, step: 0.1, label: "Battery voltage (V)"})
viewof battery_mah_leach = Inputs.range([500, 10000], {value: 3000, step: 100, label: "Battery capacity (mAh)"})
viewof rounds_per_hour = Inputs.range([1, 60], {value: 1, step: 1, label: "Rounds per hour"})

{
  // Energy model constants (from chapter worked example)
  const E_RX = 0.3;          // mJ per reception
  const E_AGG = 0.1;         // mJ per aggregation
  const E_TX_LONG = 2.0;     // mJ base for long-range TX (to sink, d=1 unit=100m)
  const E_TX_SHORT = 0.5;    // mJ base for short-range TX (to CH, d=0.2 unit=20m)
  const E_CH_OVERHEAD = 0.5; // mJ CH coordination overhead

  // Average members per CH
  const avg_members = Math.round((1 - p_leach) / p_leach);

  // CH energy per round
  const ch_rx = avg_members * E_RX;
  const ch_agg = avg_members * E_AGG;
  const ch_tx = E_TX_LONG * (1 + 1 * 1);  // d=1 unit to sink
  const ch_total = ch_rx + ch_agg + ch_tx + E_CH_OVERHEAD;

  // Member energy per round
  const member_tx = E_TX_SHORT * (1 + 0.2 * 0.2);  // d=0.2 units to CH
  const member_total = member_tx;

  // Average per-node energy (weighted by probability)
  const avg_per_node = p_leach * ch_total + (1 - p_leach) * member_total;

  // Battery energy in Joules
  const battery_j = battery_mah_leach * battery_v_leach * 3.6;

  // Network lifetime in rounds
  const lifetime_rounds = battery_j / (num_nodes_leach * avg_per_node / 1000);

  // Direct transmission comparison: every node → sink at d=1
  const direct_per_node = E_TX_LONG * (1 + 1 * 1);  // 4.0 mJ
  const direct_rounds = battery_j / (num_nodes_leach * direct_per_node / 1000);

  const lifetime_hours = lifetime_rounds / rounds_per_hour;
  const lifetime_years = lifetime_hours / 8760;
  const direct_years = (direct_rounds / rounds_per_hour) / 8760;
  const improvement = lifetime_years / direct_years;

  const color = lifetime_years >= 5 ? "#16A085" : lifetime_years >= 2 ? "#E67E22" : "#E74C3C";

  return htl.html`<div style="font-family:Arial,sans-serif;padding:16px;background:#f8fafc;border-radius:8px;border:1px solid #e2e8f0;margin-top:8px">
    <table style="width:100%;border-collapse:collapse;font-size:14px">
      <tr style="background:#2C3E50;color:white">
        <th style="padding:8px;text-align:left">Parameter</th>
        <th style="padding:8px;text-align:right">Value</th>
      </tr>
      <tr style="background:#eaf7f4">
        <td style="padding:6px 8px">Avg members per CH (1/p − 1)</td>
        <td style="padding:6px 8px;text-align:right">${avg_members} nodes</td>
      </tr>
      <tr>
        <td style="padding:6px 8px">CH energy per round</td>
        <td style="padding:6px 8px;text-align:right">${ch_total.toFixed(2)} mJ</td>
      </tr>
      <tr style="background:#eaf7f4">
        <td style="padding:6px 8px">Member energy per round</td>
        <td style="padding:6px 8px;text-align:right">${member_total.toFixed(2)} mJ</td>
      </tr>
      <tr>
        <td style="padding:6px 8px">Avg per-node energy/round (weighted)</td>
        <td style="padding:6px 8px;text-align:right">${avg_per_node.toFixed(3)} mJ</td>
      </tr>
      <tr style="background:#eaf7f4">
        <td style="padding:6px 8px">Battery energy</td>
        <td style="padding:6px 8px;text-align:right">${(battery_j/1000).toFixed(0)} J (${battery_mah_leach} mAh @ ${battery_v_leach}V)</td>
      </tr>
      <tr>
        <td style="padding:6px 8px">LEACH network lifetime</td>
        <td style="padding:6px 8px;text-align:right;font-weight:bold;color:${color}">${lifetime_years.toFixed(1)} years (${Math.round(lifetime_rounds).toLocaleString()} rounds)</td>
      </tr>
      <tr style="background:#fdf3e7">
        <td style="padding:6px 8px">Direct transmission lifetime</td>
        <td style="padding:6px 8px;text-align:right;color:#E67E22">${direct_years.toFixed(1)} years</td>
      </tr>
      <tr style="background:#2C3E50;color:white">
        <td style="padding:8px;font-weight:bold">LEACH improvement over direct</td>
        <td style="padding:8px;text-align:right;font-weight:bold">${improvement.toFixed(1)}× longer lifetime</td>
      </tr>
    </table>
    <p style="margin:8px 0 0;font-size:12px;color:#666">Try p=0.05 (5 CHs per 100 nodes) for the textbook example: ~37-year LEACH vs ~9-year direct.</p>
  </div>`;
}

78.4.1 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

78.4.2 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

---

78.5 Protocol Selection Decision Flow

Figure 78.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.

---

78.6 Routing Tradeoffs

78.6.1 Tradeoff: Proactive vs Reactive Routing

Tradeoff: 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.

Quick Check: Proactive vs Reactive Routing

78.6.2 Tradeoff: Flat Routing vs Hierarchical Routing

Tradeoff: 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%.

78.6.3 Tradeoff: Single-Path vs Multi-Path Routing

Tradeoff: 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).

---

78.7 Interactive: LEACH Clustering Demo

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.

viewof leachConfig = {
  const container = htl.html`<div style="display: flex; flex-wrap: wrap; gap: 15px; align-items: center; margin-bottom: 15px; padding: 10px; background: #f8f9fa; border-radius: 8px;">
    <div style="display: flex; align-items: center; gap: 8px;">
      <label style="font-weight: 600; color: #2C3E50;">CH Probability (p):</label>
      <input type="range" id="pValue" min="0.05" max="0.25" step="0.05" value="0.1" style="width: 100px;">
      <span id="pDisplay" style="min-width: 40px; color: #16A085; font-weight: bold;">0.10</span>
    </div>
    <button id="runRoundBtn" type="button" style="padding: 8px 16px; background: #16A085; color: white; border: none; border-radius: 6px; cursor: pointer; font-weight: 600;">Run Round</button>
    <button id="run10RoundsBtn" type="button" style="padding: 8px 16px; background: #E67E22; color: white; border: none; border-radius: 6px; cursor: pointer; font-weight: 600;">Run 10 Rounds</button>
    <button id="resetBtn" type="button" style="padding: 8px 16px; background: #95A5A6; color: white; border: none; border-radius: 6px; cursor: pointer; font-weight: 600;">Reset</button>
  </div>`;

  const pSlider = container.querySelector("#pValue");
  const pDisplay = container.querySelector("#pDisplay");
  pSlider.oninput = () => {
    pDisplay.textContent = parseFloat(pSlider.value).toFixed(2);
  };

  return container;
}

// Main LEACH Simulation
leachSimulation = {
  const width = 600;
  const height = 450;
  const numNodes = 20;
  const sinkPos = { x: width / 2, y: 30 };

  // Energy costs (in arbitrary units)
  const E_TX_SHORT = 0.5;   // Transmit to nearby CH
  const E_TX_LONG = 2.0;    // Transmit to sink (direct)
  const E_RX = 0.3;         // Receive data
  const E_AGGREGATION = 0.1; // Aggregation cost
  const E_CH_OVERHEAD = 0.5; // Extra CH coordination overhead

  // Initialize nodes
  let nodes = [];
  let round = 0;
  let directEnergy = 0;
  let leachEnergy = 0;
  let history = [];

  function initNodes() {
    nodes = [];
    for (let i = 0; i < numNodes; i++) {
      nodes.push({
        id: i,
        x: 50 + Math.random() * (width - 100),
        y: 80 + Math.random() * (height - 130),
        energy: 100,
        isClusterHead: false,
        clusterId: -1,
        chCount: 0,
        lastCHRound: -100
      });
    }
    round = 0;
    directEnergy = 0;
    leachEnergy = 0;
    history = [];
  }

  initNodes();

  function distance(n1, n2) {
    return Math.sqrt((n1.x - n2.x) ** 2 + (n1.y - n2.y) ** 2);
  }

  function runRound() {
    const p = parseFloat(document.querySelector("#pValue")?.value || 0.1);
    round++;

    // Reset cluster assignments
    nodes.forEach(n => {
      n.isClusterHead = false;
      n.clusterId = -1;
    });

    // Phase 1: Cluster Head Election (LEACH probability)
    const aliveNodes = nodes.filter(n => n.energy > 0);
    const r = round;

    aliveNodes.forEach(n => {
      const roundsSinceCH = r - n.lastCHRound;
      const threshold = roundsSinceCH >= Math.round(1/p) ? p / (1 - p * ((r - 1) % Math.round(1/p))) : p;

      if (Math.random() < threshold && n.energy > 10) {
        n.isClusterHead = true;
        n.clusterId = n.id;
        n.chCount++;
        n.lastCHRound = round;
      }
    });

    // Ensure at least one CH
    const clusterHeads = nodes.filter(n => n.isClusterHead && n.energy > 0);
    if (clusterHeads.length === 0 && aliveNodes.length > 0) {
      const healthiest = aliveNodes.reduce((a, b) => a.energy > b.energy ? a : b);
      healthiest.isClusterHead = true;
      healthiest.clusterId = healthiest.id;
      healthiest.chCount++;
      healthiest.lastCHRound = round;
    }

    // Phase 2: Cluster Formation (join nearest CH)
    const currentCHs = nodes.filter(n => n.isClusterHead && n.energy > 0);

    aliveNodes.forEach(n => {
      if (!n.isClusterHead) {
        let nearestCH = null;
        let minDist = Infinity;
        currentCHs.forEach(ch => {
          const d = distance(n, ch);
          if (d < minDist) {
            minDist = d;
            nearestCH = ch;
          }
        });
        if (nearestCH) {
          n.clusterId = nearestCH.id;
        }
      }
    });

    // Phase 3: Data Transmission & Energy Consumption
    let roundLeachEnergy = 0;
    let roundDirectEnergy = 0;

    currentCHs.forEach(ch => {
      const members = nodes.filter(n => n.clusterId === ch.id && !n.isClusterHead && n.energy > 0);

      // Members transmit to CH
      members.forEach(m => {
        const d = distance(m, ch) / 100;
        const txEnergy = E_TX_SHORT * (1 + d * d);
        m.energy -= txEnergy;
        roundLeachEnergy += txEnergy;

        // CH receives
        ch.energy -= E_RX;
        roundLeachEnergy += E_RX;
      });

      // CH aggregates and transmits to sink
      if (members.length > 0) {
        ch.energy -= E_AGGREGATION * members.length;
        roundLeachEnergy += E_AGGREGATION * members.length;
      }

      const dToSink = distance(ch, sinkPos) / 100;
      const chTxEnergy = E_TX_LONG * (1 + dToSink * dToSink);
      ch.energy -= chTxEnergy + E_CH_OVERHEAD;
      roundLeachEnergy += chTxEnergy + E_CH_OVERHEAD;
    });

    // Direct transmission comparison (all nodes transmit directly to sink)
    aliveNodes.forEach(n => {
      const d = distance(n, sinkPos) / 100;
      const directTxEnergy = E_TX_LONG * (1 + d * d);
      roundDirectEnergy += directTxEnergy;
    });

    leachEnergy += roundLeachEnergy;
    directEnergy += roundDirectEnergy;

    // Clamp energy
    nodes.forEach(n => {
      if (n.energy < 0) n.energy = 0;
    });

    history.push({
      round: round,
      leachEnergy: leachEnergy,
      directEnergy: directEnergy,
      aliveNodes: nodes.filter(n => n.energy > 0).length,
      numCHs: currentCHs.length
    });

    render();
  }

  // Create SVG
  const svg = d3.create("svg")
    .attr("width", width)
    .attr("height", height + 130)
    .style("background", "#f8fafc")
    .style("border-radius", "8px")
    .style("border", "1px solid #e2e8f0");

  function getEnergyColor(energy) {
    if (energy <= 0) return "#95A5A6";
    if (energy < 25) return "#E74C3C";
    if (energy < 50) return "#E67E22";
    if (energy < 75) return "#F1C40F";
    return "#16A085";
  }

  function render() {
    svg.selectAll("*").remove();

    // Title
    svg.append("text")
      .attr("x", width / 2)
      .attr("y", 20)
      .attr("text-anchor", "middle")
      .attr("font-size", "14px")
      .attr("font-weight", "bold")
      .attr("fill", "#2C3E50")
      .text(`LEACH Clustering - Round ${round}`);

    // Draw sink
    svg.append("rect")
      .attr("x", sinkPos.x - 15)
      .attr("y", sinkPos.y - 10)
      .attr("width", 30)
      .attr("height", 20)
      .attr("fill", "#2C3E50")
      .attr("rx", 4);

    svg.append("text")
      .attr("x", sinkPos.x)
      .attr("y", sinkPos.y + 5)
      .attr("text-anchor", "middle")
      .attr("font-size", "10px")
      .attr("fill", "white")
      .text("SINK");

    // Get current cluster heads
    const clusterHeads = nodes.filter(n => n.isClusterHead && n.energy > 0);
    const clusterColors = d3.schemeCategory10;

    // Draw nodes
    nodes.forEach((n, i) => {
      const chIndex = clusterHeads.findIndex(ch => ch.id === n.clusterId);
      const borderColor = n.isClusterHead ? "#2C3E50" : (chIndex >= 0 ? clusterColors[chIndex % 10] : "#95A5A6");

      svg.append("circle")
        .attr("cx", n.x)
        .attr("cy", n.y)
        .attr("r", n.isClusterHead ? 14 : 10)
        .attr("fill", getEnergyColor(n.energy))
        .attr("stroke", borderColor)
        .attr("stroke-width", n.isClusterHead ? 3 : 2);

      if (n.isClusterHead && n.energy > 0) {
        svg.append("text")
          .attr("x", n.x)
          .attr("y", n.y + 4)
          .attr("text-anchor", "middle")
          .attr("font-size", "10px")
          .attr("font-weight", "bold")
          .attr("fill", "white")
          .text("CH");
      }
    });

    // Stats panel
    const statsY = height + 10;
    const aliveCount = nodes.filter(n => n.energy > 0).length;
    const avgEnergy = d3.mean(nodes, n => n.energy).toFixed(1);

    svg.append("text")
      .attr("x", 20)
      .attr("y", statsY)
      .attr("font-size", "12px")
      .attr("font-weight", "bold")
      .attr("fill", "#2C3E50")
      .text("Energy Consumption:");

    const maxEnergy = Math.max(leachEnergy, directEnergy, 1);
    const barWidth = 200;

    svg.append("rect")
      .attr("x", 20)
      .attr("y", statsY + 10)
      .attr("width", (leachEnergy / maxEnergy) * barWidth)
      .attr("height", 18)
      .attr("fill", "#16A085")
      .attr("rx", 3);

    svg.append("text")
      .attr("x", 25 + (leachEnergy / maxEnergy) * barWidth)
      .attr("y", statsY + 23)
      .attr("font-size", "11px")
      .attr("fill", "#2C3E50")
      .text(`LEACH: ${leachEnergy.toFixed(1)}`);

    svg.append("rect")
      .attr("x", 20)
      .attr("y", statsY + 35)
      .attr("width", (directEnergy / maxEnergy) * barWidth)
      .attr("height", 18)
      .attr("fill", "#E74C3C")
      .attr("rx", 3);

    svg.append("text")
      .attr("x", 25 + (directEnergy / maxEnergy) * barWidth)
      .attr("y", statsY + 48)
      .attr("font-size", "11px")
      .attr("fill", "#2C3E50")
      .text(`Direct: ${directEnergy.toFixed(1)}`);

    if (directEnergy > 0) {
      const savings = ((directEnergy - leachEnergy) / directEnergy * 100).toFixed(1);
      svg.append("text")
        .attr("x", 20)
        .attr("y", statsY + 70)
        .attr("font-size", "12px")
        .attr("font-weight", "bold")
        .attr("fill", savings > 0 ? "#16A085" : "#E74C3C")
        .text(`Energy Savings: ${savings}%`);
    }

    // Node stats
    svg.append("text")
      .attr("x", 320)
      .attr("y", statsY)
      .attr("font-size", "12px")
      .attr("font-weight", "bold")
      .attr("fill", "#2C3E50")
      .text("Network Status:");

    const stats = [
      `Alive Nodes: ${aliveCount}/${numNodes}`,
      `Avg Energy: ${avgEnergy}%`,
      `Current CHs: ${clusterHeads.length}`
    ];

    stats.forEach((stat, i) => {
      svg.append("text")
        .attr("x", 320)
        .attr("y", statsY + 18 + i * 16)
        .attr("font-size", "11px")
        .attr("fill", "#34495E")
        .text(stat);
    });
  }

  // Initial render
  render();

  // Button handlers
  const runRoundBtn = document.querySelector("#runRoundBtn");
  const run10RoundsBtn = document.querySelector("#run10RoundsBtn");
  const resetBtn = document.querySelector("#resetBtn");

  if (runRoundBtn) {
    runRoundBtn.onclick = () => {
      const aliveCount = nodes.filter(n => n.energy > 0).length;
      if (aliveCount > 0) {
        runRound();
      }
    };
  }

  if (run10RoundsBtn) {
    run10RoundsBtn.onclick = () => {
      for (let i = 0; i < 10; i++) {
        const aliveCount = nodes.filter(n => n.energy > 0).length;
        if (aliveCount > 0) {
          runRound();
        }
      }
    };
  }

  if (resetBtn) {
    resetBtn.onclick = () => {
      initNodes();
      render();
    };
  }

  return svg.node();
}

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

---

78.8 Knowledge Check

Test Your Understanding

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

1. WSN radios are incompatible with IP protocols due to different physical layers
2. IP routing requires expensive licenses not affordable for large sensor deployments
3. Traditional routing assumes wired infrastructure incompatible with wireless operation
4. IP routing’s overhead (routing tables, periodic updates, address management) exceeds sensor node resources

Answer

d) IP routing’s overhead exceeds sensor node resources. OSPF maintains topology databases requiring ~100KB for 1000 nodes (sensor nodes have 4-32KB RAM total), runs O(N^2) Dijkstra computations on 8-32 MHz CPUs, and floods link-state advertisements consuming significant energy. IPv4 address overhead (8 bytes routing per packet) can exceed the sensor data itself (2 bytes). WSNs need data-centric, energy-aware approaches.

Question 2: A 500-node agricultural WSN reports hourly soil moisture. With flat routing, each node transmits to the sink averaging 4 hops (2000 total transmissions). With hierarchical routing using 50 clusters, how many total transmissions occur?

1. 500 - same number since every node must report
2. 650 - 500 to cluster heads (1 hop) + 50 aggregated to sink (3 hops each)
3. 100 - dramatic compression reduces to 1/5 of original
4. 2050 - hierarchical adds overhead compared to flat routing

Answer

b) 650 total transmissions. Each of 500 nodes transmits to its cluster head (1 hop = 500 transmissions). Each of 50 cluster heads aggregates 10 readings and transmits to the sink (average 3 hops = 150 transmissions). Total = 500 + 150 = 650, compared to 2000 for flat routing. Energy savings: 67.5%.

Question 3: When should you choose reactive routing (like AODV) over proactive routing (like DSDV)?

1. When traffic is continuous and predictable with regular sensor reporting
2. When low latency is critical for every single packet
3. When traffic is sporadic/event-driven and nodes are mobile with frequently changing topology
4. When network topology is stable and most nodes communicate frequently

Answer

c) When traffic is sporadic/event-driven and nodes are mobile with frequently changing topology. Reactive routing discovers routes on demand, avoiding the periodic update overhead of proactive routing during idle periods. This saves significant energy when most nodes are silent most of the time (e.g., fire alarms, intrusion detection). Proactive routing wastes energy maintaining routes that are rarely used.

---

Common Pitfalls

1. Building Routing Tables Without Energy Awareness

Shortest-hop routing concentrates relay load on nodes near the sink, depleting them 10-100× faster than edge nodes. Always incorporate residual energy into route metric (e.g., ETX × energy factor) to balance consumption and prevent premature network partitioning.

2. Forgetting to Handle Routing Table Staleness

WSN topology changes as nodes die or move — routing tables become stale within hours in dynamic deployments. Implement periodic route discovery with a timeout proportional to expected node lifetime, and use link-quality metrics that decay when no recent transmissions are observed.

3. Using Flooding for Data Collection in Dense Networks

Flooding generates O(n²) messages in a 100-node network — a single data collection round produces 10,000 transmissions. Use directed diffusion or tree-based convergecast to reduce collection overhead to O(n) messages.

🏷️ Label the Diagram

Code Challenge

78.9 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

---

78.10 Worked Example: Routing Protocol Selection for Pipeline Monitoring WSN

Worked Example: Choosing Between Flat, Hierarchical, and Geographic Routing for 2,000-Node Pipeline Network

Scenario: An oil company monitors a 500 km pipeline with 2,000 vibration/pressure sensors spaced 250 meters apart. Sensors are solar-powered with 2,000 mAh backup batteries. The base station sits at the pipeline control center (one end). Data must reach the base station within 5 seconds. Budget constraint: sensors cannot be replaced for 7 years.

Step 1: Evaluate Flat Routing (e.g., Directed Diffusion)

Parameter	Value
Max hop count to base station	2,000 hops (worst case, sensor at far end)
Per-hop latency	~5 ms (typical radio transmission)
End-to-end latency (worst case)	2,000 x 5 ms = 10 seconds (exceeds 5-second requirement)
Route table size per node	2,000 entries x 8 bytes = 16 KB (manageable)
Energy hotspot problem	Nodes near the base station relay ALL traffic from 2,000 upstream nodes. Node #1 relays 2,000x more messages than node #2000.
Node #1 daily energy for relaying	2,000 nodes x 48 msg/day x 0.05 mJ/msg = 4,800 mJ = 4,800/3,600 = 1.33 mAh/day
Node #1 battery life (relay only)	2,000 mAh / 1.33 mAh = 1,500 days (4.1 years) – fails before 7-year target

Flat routing verdict: Fails on both latency (10s > 5s limit) and energy (4.1 years < 7-year target) due to the linear topology funneling all traffic through nodes near the base station.

Step 2: Evaluate Hierarchical Routing (e.g., LEACH-style clustering)

Parameter	Value
Cluster size	50 sensors per cluster, 40 clusters
Cluster head (CH) aggregates 50 readings into 1 summary	50:1 data reduction
CH-to-CH multi-hop to base station	40 hops maximum
End-to-end latency	50 ms aggregation + 40 x 5 ms = 250 ms (well within 5 seconds)
CH relay load (worst case, CH #1)	40 aggregated messages (not 2,000 raw messages)
CH rotation period	Every 24 hours (solar recharges during day)
Energy balance	Each node serves as CH for 1/50 of the time. Average relay load is evenly distributed.
Estimated network lifetime	8-10 years (meets 7-year target)

Step 3: Evaluate Geographic Routing (e.g., GPSR)

Parameter	Value
Requires GPS on each node	+$3/node x 2,000 = $6,000 additional cost
GPS power consumption	25 mA during fix (30 seconds/day) = 0.21 mAh/day
Advantage	No route tables needed. Forward to geographically closest neighbor toward base station.
Problem	Pipeline is linear – geographic “closest to base” is always the same next-hop, degenerating into flat routing with the same hotspot problem.

Geographic routing verdict: Not suitable for linear topologies. Geographic routing excels in 2D deployments (e.g., field monitoring) where alternative paths exist. A pipeline’s 1D topology offers no geographic diversity.

Result: Hierarchical routing (LEACH variant with solar-aware CH rotation) is the clear winner.

Criterion	Flat	Hierarchical	Geographic
Latency	10s (fail)	250 ms (pass)	10s (fail, same as flat)
Energy balance	Node #1 dies at 4.1 yr (fail)	Balanced, 8-10 yr (pass)	Same as flat (fail)
Scalability to 2,000 nodes	Poor (hotspot)	Good (40 CHs)	Poor (linear topology)
Verdict	Reject	Select	Reject

Key insight: Topology shape determines routing protocol suitability. Hierarchical routing is essential for linear topologies (pipelines, roads, rivers) because it breaks the hotspot problem through aggregation.

78.11 Knowledge Check

Quiz: WSN Routing: Protocol Classification

Match Routing Protocol Families to Their Characteristics

Order the Routing Protocol Selection Process

78.12 What’s Next?

Topic	Chapter	Description
Directed Diffusion	WSN Routing: Directed Diffusion	Data-centric routing with interest propagation and gradients
Data Aggregation	WSN Routing: Data Aggregation	In-network data processing to reduce transmissions
Link Quality Routing	WSN Routing: Link Quality	RSSI, WMEWMA, and MIN-T metrics for path selection
Trickle Algorithm	WSN Routing: Trickle Algorithm	Network reprogramming with polite gossip protocol