75 WSN Routing Fundamentals
75.1 Learning Objectives
By the end of this chapter series, you will be able to:
- Identify WSN Routing Challenges: Determine why traditional routing protocols fail in sensor networks
- Compare Routing Paradigms: Distinguish data-centric, hierarchical, geographic, and QoS-aware routing approaches
- Evaluate Protocol Trade-offs: Analyze when to use proactive vs reactive routing
- Apply LEACH Clustering: Calculate how cluster head rotation balances energy consumption
For Beginners: WSN Routing Fundamentals
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.
75.2 Prerequisites
Before diving into this chapter, you should be familiar with:
- Wireless Sensor Networks: Understanding WSN architecture, multi-hop communication, and energy constraints provides the foundation for specialized routing protocols
- WSN Overview: Fundamentals: Knowledge of sensor network characteristics, data aggregation, and network topologies is essential for understanding routing decisions
- Routing Fundamentals: Familiarity with basic routing concepts, routing tables, and forwarding mechanisms helps distinguish WSN-specific routing approaches
- Multi-Hop Ad Hoc: Fundamentals: Understanding self-organizing networks and dynamic routing provides context for data-centric and geographic routing strategies
MVU: Minimum Viable Understanding
Core concept: WSN routing differs fundamentally from traditional network routing because it prioritizes energy efficiency over throughput and uses data-centric approaches instead of address-based routing.
Why it matters: Sensors operate on limited batteries for years; inefficient routing drains nodes prematurely, creating coverage gaps. Traditional shortest-path routing fails because it ignores link quality, energy levels, and the many-to-one traffic pattern in sensor networks.
Key takeaway: Choose routing protocols based on your application: Directed Diffusion for event-driven data collection, LEACH for hierarchical aggregation, geographic routing when GPS is available, and always consider link quality metrics (ETX) over simple hop count.
Key Concepts
- Routing Protocol: Algorithm determining paths for data packets to travel from source sensors to destination sinks through multi-hop networks
- Energy-Aware Routing: Protocols that select paths based on node energy levels to balance consumption and extend network lifetime
- Data-Centric Routing: Routing based on data content rather than node addresses, enabling in-network aggregation and filtering
- Hierarchical Routing: Organizing network into clusters with cluster heads aggregating data from members before forwarding to sinks
- Geographic Routing: Protocols using node location information to make forwarding decisions without maintaining routing tables
- Quality of Service (QoS): Meeting application requirements for delivery reliability, latency, and bandwidth in routing decisions
75.3 Chapter Overview
This chapter has been organized into focused sections for easier learning. Work through them in order, or jump to the topic most relevant to your current needs:
75.3.1 1. WSN Routing Introduction
Fundamental concepts and why WSN routing is unique
Routing in Wireless Sensor Networks differs fundamentally from traditional network routing. This section introduces the core concepts, explains data-centric vs address-centric approaches, and provides beginner-friendly explanations.
- Why WSN routing is different from traditional routing
- Data-centric vs address-centric approaches
- Energy-aware routing fundamentals
- Protocol selection decision tree
75.3.2 2. WSN Routing Challenges
Why traditional routing fails in sensor networks
Traditional routing protocols like OSPF and BGP fail in WSNs due to energy constraints, scale, and communication patterns. This section explains the specific challenges and routing requirements.
- Why traditional routing fails (5 key reasons)
- WSN routing requirements
- Common pitfalls to avoid
- Energy efficiency, scalability, and robustness
75.3.3 3. WSN Routing Classification
Protocol categories and tradeoffs
WSN routing protocols are classified into four major families. This section covers the classification, key tradeoffs (proactive vs reactive, flat vs hierarchical), and includes an interactive LEACH clustering demonstration.
- Data-centric, hierarchical, location-based, and QoS-aware protocols
- Proactive vs reactive routing tradeoffs
- Flat vs hierarchical routing comparison
- Single-path vs multi-path routing
- Interactive LEACH clustering demo
75.4 Choosing the Right WSN Routing Protocol: A Decision Framework
75.4.1 Quick Reference: Protocol Selection
| Scenario | Recommended Protocol | Rationale |
|---|---|---|
| Event-driven monitoring | Directed Diffusion | Data-centric, responds to queries |
| Dense deployment (>100 nodes) | LEACH/PEGASIS | Hierarchical aggregation scales |
| GPS-equipped nodes | GPSR/GEAR | Geographic forwarding efficient |
| Real-time alerts | QoS protocols (SPEED) | Latency guarantees |
| Stable topology | Proactive (DSDV) | Routes ready immediately |
| Mobile nodes | Reactive (AODV) | Adapts to changes |
| Code updates | Trickle | Low overhead when consistent |
75.4.2 Detailed Protocol Comparison
| Factor | RPL (IETF standard) | AODV | LEACH | Directed Diffusion | GPSR |
|---|---|---|---|---|---|
| Topology | DAG (tree-like) | Flat mesh | Clustered hierarchy | Flat, data-centric | Flat, location-based |
| Route discovery | Proactive (DIOs) | Reactive (on-demand) | Periodic cluster formation | Interest propagation | Greedy forwarding |
| Energy balance | Rank-based (ETX metric) | No built-in balancing | Rotating cluster heads | Multi-path gradients | No balancing |
| Scalability | Good (1000s of nodes) | Poor (>500 nodes) | Good (hierarchical) | Moderate | Good (stateless) |
| Mobility support | Limited (re-parent) | Good (route repair) | Poor (fixed clusters) | Moderate | Good (greedy) |
| Standards compliance | IETF RFC 6550 | IETF RFC 3561 | Academic | Academic | Academic |
| Best for | IPv6 IoT (6LoWPAN, Thread) | Mobile ad-hoc, small nets | Large static, aggregation | Event queries | Outdoor with GPS |
75.4.3 Interactive Protocol Selector
75.4.4 Decision Flowchart
- Does the network use IPv6/6LoWPAN (Thread, LoRaWAN, etc.)? Yes –> RPL (IETF standard, built into most IoT stacks)
- Are nodes mobile (vehicles, wearables, robots)? Yes –> AODV (reactive, adapts to topology changes)
- Is the network large (>500 nodes) and static with a need for data aggregation? Yes –> LEACH (cluster-based, reduces traffic to sink)
- Do nodes have GPS or known positions? Yes –> GPSR (no routing tables needed, greedy geographic forwarding)
- Is the application event-driven (report only when threshold exceeded)? Yes –> Directed Diffusion (query-driven, named data)
- Default: RPL for standards-based IoT; LEACH for research/academic sensor networks
Putting Numbers to It
Comparing RPL vs. LEACH for a 500-node environmental monitoring WSN: Nodes report temperature every 60 seconds to a single sink. Radio: CC2420 (250 kbps, 17.4 mA TX).
RPL (proactive tree-based): Builds a DODAG (Destination-Oriented Directed Acyclic Graph) with periodic control messages (DIO = DODAG Information Object) every 16 seconds.
- DIO packet size: 48 bytes. Each node broadcasts DIO to neighbors (average degree = 6).
- Control overhead per hour: \(\frac{3600}{16} \times 48 \text{ bytes} \times 6 \text{ neighbors} = 64.8 \text{ KB per node}\)
- Data transmission: 500 nodes × 60 reports/hr × 40 bytes × avg 4 hops = 4.8 MB/hr total network traffic
- Total traffic: 4.8 MB (data) + 32.4 MB (control for 500 nodes) = 37.2 MB/hr
LEACH (hierarchical clustering with rotation): Forms 50 clusters (p=0.1 probability), rotates cluster heads every 20 minutes.
- Cluster formation overhead: 50 CHs broadcast advertisement (20 bytes) every 20 min = 50 KB/hr
- Data: 450 members send to CH (1 hop × 40 bytes), 50 CHs aggregate and send to sink (avg 3 hops × 50 bytes)
- Total traffic: \((450 \times 40) + (50 \times 3 \times 50) = 25.5 \text{ KB per round} \times 60 \text{ rounds/hr} = 1.53 \text{ MB/hr}\)
Energy comparison: RPL’s control overhead dominates (87% of traffic), while LEACH’s aggregation reduces data volume by 94%. For battery lifetime: LEACH extends network operation from 1.2 years (RPL) to 8.5+ years (LEACH) due to reduced transmissions and balanced energy consumption.
For Kids: Meet the Sensor Squad!
Sensor routing is all about finding the best way for messages to travel from sensors to the gateway – like finding the best path through a maze!
75.4.5 The Sensor Squad Adventure: The Big Farm Network
The Sensor Squad had grown! Now there were sensors ALL across Greenfield Farm – by the pond, in the orchard, near the barn, and in the greenhouse. They all needed to send their readings to Farmer Jones at the farmhouse.
“We need a plan!” said Sammy. “We cannot all shout at once – it would be too noisy and use up everyone’s batteries!”
The team came up with FOUR different strategies:
- The Content Plan (Directed Diffusion): Farmer Jones says “tell me if anything is too hot!” and only sensors with hot readings respond.
- The Group Plan (LEACH): Sensors form groups, each group picks a leader who summarizes and sends ONE message.
- The Map Plan (Geographic Routing): Each sensor passes the message to whichever friend is closest to the farmhouse.
- The Speed Plan (Trickle): When there is an update, sensors gossip it quickly. When there is nothing new, they stay quiet.
“The trick,” explained Bella, “is picking the RIGHT plan for the RIGHT job!”
75.4.6 Key Words for Kids
| Word | What It Means |
|---|---|
| Routing | Finding the best path for messages to travel |
| Protocol | A set of rules that sensors follow to send messages |
| Energy-aware | Being smart about not wasting battery power |
| Sink | The destination where all sensor data ends up (like the teacher’s desk) |
75.5 Knowledge Check
75.6 What’s Next
| Topic | Chapter | Description |
|---|---|---|
| Routing Introduction | WSN Routing Introduction | Why WSN routing differs from traditional networking |
| Routing Classification | WSN Routing Classification | Protocol families, tradeoffs, and interactive LEACH demo |
| Directed Diffusion | WSN Routing: Directed Diffusion | Data-centric routing with interests and gradients |
| Data Aggregation | WSN Routing: Data Aggregation | In-network data processing techniques |
| Link Quality | WSN Routing: Link Quality | RSSI, WMEWMA, and MIN-T metrics |
| Trickle Algorithm | WSN Routing: Trickle Algorithm | Network reprogramming protocol |
| Labs and Games | WSN Routing: Labs and Games | Hands-on practice and interactive simulations |
Related Chapters
Deep Dives:
- Wireless Sensor Networks - WSN architecture and multi-hop communication
- Routing Fundamentals - Core routing concepts and algorithms
- WSN Overview: Fundamentals - Energy constraints and duty cycling
Protocols:
- RPL Operation - RPL routing for IoT networks
- 6LoWPAN - Adaptation layer routing
- IoT Protocols - Protocol selection framework
Learning:
- Simulations Hub - Network routing simulators
- Network Design - Topology planning
75.7 How It Works: LEACH Cluster Head Rotation
Understanding how LEACH balances energy consumption across all nodes through randomized cluster head rotation:
Step 1: Cluster Head Election (Beginning of Each Round)
Each node independently decides whether to become a cluster head using probability P:
Threshold T(n) = P / (1 - P × (r mod (1/P)))Where: - P = desired percentage of cluster heads (e.g., 0.05 = 5%) - r = current round number - n = node ID
Each node generates random number [0,1]. If random < T(n), node becomes cluster head for this round.
Step 2: Cluster Head Advertisement
New cluster heads broadcast advertisement messages using CSMA. Non-cluster-head nodes listen and record received signal strength from each cluster head.
Step 3: Cluster Formation
Regular nodes join the cluster head with strongest signal (minimum transmission energy). They send join messages to their chosen cluster head.
Step 4: TDMA Schedule Creation
Each cluster head creates a TDMA schedule for its member nodes, assigning each member a time slot for transmission. This eliminates intra-cluster collisions.
Step 5: Data Collection and Aggregation
- Member nodes: Wake at assigned TDMA slot, transmit data to cluster head (short distance: 25-50m), then sleep
- Cluster head: Receives data from all members, aggregates (min/max/avg), compresses 5:1 ratio
- Transmission to sink: Cluster head sends aggregated summary to base station (long distance: 200-500m)
Step 6: Next Round
After fixed time (e.g., 20 seconds), round ends and protocol repeats from Step 1 with new cluster head election. Over 20 rounds, each node spends ~1 round as cluster head (5% duty cycle).
Energy Distribution Over Time:
| Round | Node A Role | Node A Energy | Node B Role | Node B Energy |
|---|---|---|---|---|
| 1 | Member | 6.25 mJ | Cluster Head | 83 mJ |
| 2 | Member | 6.25 mJ | Member | 6.25 mJ |
| 3 | Cluster Head | 83 mJ | Member | 6.25 mJ |
| … | … | … | … | … |
| 20 | Member | 6.25 mJ | Member | 6.25 mJ |
| Avg | Mixed | 10.1 mJ/round | Mixed | 10.1 mJ/round |
Key Insight: Without rotation, designated cluster heads (consuming 83 mJ/round) exhaust a 1 J coin-cell battery in approximately \(1{,}000 \text{ mJ} / (83 \text{ mJ/round} \times 7 \text{ rounds/day}) \approx 1.7\) years. With rotation (10.1 mJ/round average), the same battery lasts \(1{,}000 \text{ mJ} / (10.1 \text{ mJ/round} \times 7) \approx 14\) years – approximately 8x improvement. The uniform depletion across all nodes means no single node fails early, maximizing coverage lifetime.
75.8 Concept Relationships
| Concept | Relates To | Relationship Type | Significance |
|---|---|---|---|
| Data-Centric Routing | Directed Diffusion | Implementation | Directed Diffusion routes based on data attributes (temperature>30°C) rather than node addresses |
| Hierarchical Routing | LEACH Protocol | Energy Optimization | LEACH extends network lifetime 8x over flat routing through cluster-based aggregation |
| Geographic Routing | GPS Availability | Prerequisite | GPSR requires node location information; without GPS, must use data-centric or hierarchical approaches |
| Energy-Aware Routing | Residual Battery | Path Selection | Routes avoid low-battery nodes even if they offer shortest path, preventing premature node death |
| Reactive Routing | Route Discovery | On-Demand | AODV discovers routes only when needed, reducing overhead in networks with sparse traffic |
| Proactive Routing | Routing Tables | Always Available | RPL maintains routes continuously, enabling immediate transmission but higher control overhead |
| Cluster Head Rotation | Energy Balance | Load Distribution | Random rotation every round ensures no single node bears aggregation burden indefinitely |
75.9 Worked Example: LEACH vs Flat Routing – Energy Savings for 500 Nodes
A precision agriculture deployment has 500 soil sensors reporting to a single base station. Each sensor generates one 50-byte reading every 10 minutes. Compare flat (direct-to-base) routing versus LEACH hierarchical routing to determine which extends network lifetime.
Scenario Parameters
| Parameter | Value |
|---|---|
| Sensors | 500 nodes, uniformly distributed over 1 km2 |
| Base station | Center of field |
| Average distance to base | 350 m (geometric mean for uniform distribution) |
| Transmission energy | 50 nJ/bit + 100 pJ/bit/m2 (free-space model) |
| Receive energy | 50 nJ/bit |
| Data aggregation ratio | 5:1 (5 raw readings compressed to 1 aggregate) |
| Battery | 2x AA = 3,000 mAh at 3V = 32,400 J |
| Message size | 50 bytes = 400 bits |
Flat Routing (Every Node Transmits Directly to Base)
Energy per transmission = 400 × (50 nJ + 100 pJ × 350²)
= 400 × (50 nJ + 12,250 nJ)
= 400 × 12,300 nJ = 4,920 µJ per message
Messages/day: 144 (every 10 min)
Daily energy: 144 × 4,920 µJ = 708,480 µJ = 0.708 J/day
Battery lifetime: 32,400 J / 0.708 J/day = 45,762 days ≈ 125 years (nodes far from base die much sooner)But this average is misleading. Nodes at the edge (500 m from base) consume 2.3x more energy than nodes near the center (200 m). Edge nodes die after ~54 years while center nodes last 125+ years, creating growing coverage holes from the perimeter inward.
LEACH Routing (20 Clusters of 25 Nodes Each)
Intra-cluster transmission (25 m avg distance to cluster head):
400 × (50 nJ + 100 pJ × 25²) = 400 × 112.5 nJ = 45 µJ per message
Cluster head aggregation (receives 24 messages, aggregates 5:1, sends 5 to base):
Receive: 24 × 400 × 50 nJ = 480 µJ
Aggregate: negligible
Transmit to base (350 m avg): 5 × 4,920 µJ = 24,600 µJ
Total CH cost per round: 25,080 µJ
Regular member per round: 45 µJ
Cluster head per round: 25,080 µJ
With rotation (each node is CH for 1/25 of rounds):
Average per node per round: (24/25 × 45) + (1/25 × 25,080) = 43.2 + 1,003.2 = 1,046.4 µJComparison
| Metric | Flat Routing | LEACH | Improvement |
|---|---|---|---|
| Energy per node per round | 4,920 µJ | 1,046 µJ | 4.7x less energy |
| Daily energy per node | 708 mJ | 151 mJ | 4.7x savings |
| Network lifetime (first node death) | ~54 years (edge) | ~589 years (uniform) | 10.9x longer |
| Total daily transmissions to base | 500 | 100 (20 CH x 5 msgs) | 80% fewer |
| Channel congestion at base | High (500 concurrent) | Low (20 CH, scheduled) | 25x less contention |
Key Insight: LEACH’s advantage comes from two mechanisms working together. First, short intra-cluster hops (25 m vs 350 m) exploit the quadratic distance term in the energy model – halving distance reduces transmission energy by 4x. Second, 5:1 aggregation means 80% fewer long-distance transmissions to the base station. The rotating cluster head role distributes the aggregation burden evenly, preventing any single node from draining prematurely.
When LEACH Loses: If sensors generate unique, non-aggregatable data (e.g., individual camera images), the aggregation ratio drops to 1:1 and LEACH’s main advantage disappears. In this case, geographic routing (GPSR) or multi-path routing provides better energy distribution.
75.10 Knowledge Check
Test Your Understanding
Question 1: Which WSN routing protocol family would you choose for a 1000-node agricultural deployment with GPS-equipped sensors measuring soil moisture every hour?
- Data-centric (Directed Diffusion) – for event-driven queries
- Hierarchical (LEACH) – for large-scale aggregation with spatial correlation
- QoS-aware (SPEED) – for guaranteed latency
- Flat routing (AODV) – for simplicity and equal treatment of all nodes
Answer
b) Hierarchical (LEACH) – for large-scale aggregation with spatial correlation. With 1000 nodes, flat routing creates excessive routing table overhead. Soil moisture readings from nearby sensors are correlated (spatial redundancy), making cluster-based aggregation highly effective. LEACH can reduce transmissions by 67% compared to flat routing. GPS is available but not needed for LEACH; geographic routing (GPSR) would also work but does not provide aggregation benefits.
Question 2: A WSN must detect forest fires with latency under 5 seconds. Which routing approach is LEAST suitable?
- Reactive routing with on-demand route discovery
- Proactive routing with pre-computed paths
- QoS-aware routing with latency guarantees
- Hierarchical routing with fast cluster head forwarding
Answer
a) Reactive routing with on-demand route discovery. Reactive protocols like AODV discover routes only when data needs to be sent, introducing 100ms-to-seconds of delay for route discovery (RREQ flooding, RREP propagation). For fire detection with a 5-second deadline, this discovery delay is unacceptable. Proactive routing has routes ready immediately, QoS-aware routing provides explicit latency guarantees, and hierarchical routing provides predictable multi-hop paths through pre-formed clusters.
Question 3: What does “data-centric routing” mean in the context of WSNs?
- Routing that prioritizes data packets over control packets
- Routing based on data content and attributes rather than node addresses
- Routing that stores data at intermediate nodes for later retrieval
- Routing that compresses data before transmission
Answer
b) Routing based on data content and attributes rather than node addresses. In data-centric routing (like Directed Diffusion), sinks express “interests” in data attributes (e.g., “temperature > 30°C in region X”) rather than addressing specific sensor nodes. The network routes matching data back to the sink. This eliminates the need for unique node addresses, enables in-network aggregation, and naturally supports query-response patterns common in sensor applications.
75.11 Try It Yourself: LEACH Cluster Head Election Simulator
Objective: Implement the LEACH cluster head election algorithm and observe how randomized rotation distributes energy load.
Setup: Use Python or JavaScript to simulate a 20-node WSN over 100 rounds.
Code Template (Python):
import random
NUM_NODES = 20
NUM_ROUNDS = 100
P = 0.05 # 5% cluster heads (expect 1 CH per round)
# Track cluster head history for each node
ch_history = [[] for _ in range(NUM_NODES)]
for r in range(NUM_ROUNDS):
# Calculate threshold for this round
for n in range(NUM_NODES):
# Threshold formula
T = P / (1 - P * (r % int(1/P)))
# Generate random number [0,1]
rand_val = random.random()
# Become CH if rand < T
if rand_val < T:
ch_history[n].append(r)
# Count CHs this round
chs_this_round = sum(1 for node in ch_history if r in node)
print(f"Round {r}: {chs_this_round} cluster heads elected")
# Analyze distribution
for n, rounds in enumerate(ch_history):
print(f"Node {n}: Cluster head {len(rounds)} times ({len(rounds)/NUM_ROUNDS*100:.1f}%)")What to Observe:
- Expected CH count: With P=0.05 and 20 nodes, expect ~1 cluster head per round (5% of 20)
- Distribution balance: Over 100 rounds, each node should be CH approximately 5 times (5%)
- Variation: Due to randomness, actual distribution varies (some nodes: 2 times, others: 8 times)
- Energy balance: Calculate average energy assuming member=6.25 mJ, CH=83 mJ per round
Extension Challenges:
- Modify to prevent nodes with <10% battery from becoming CH
- Implement residual-energy-weighted probability (higher energy → higher CH probability)
- Add TDMA schedule creation after CH election
- Simulate data aggregation and measure total transmissions vs. flat routing
Expected Result: All nodes should have similar CH duty cycles (4-6%), demonstrating LEACH’s load balancing.
75.12 Further Reading
Intanagonwiwat, C., et al. (2003). “Directed diffusion for wireless sensor networking.” IEEE/ACM Transactions on Networking, 11(1), 2-16.
Heinzelman, W. R., et al. (2000). “Energy-efficient communication protocol for wireless microsensor networks.” HICSS, 2, 10.
Akyildiz, I. F., et al. (2002). “A survey on sensor networks.” IEEE Communications Magazine, 40(8), 102-114.
Fasolo, E., et al. (2007). “In-network aggregation techniques for wireless sensor networks: A survey.” IEEE Wireless Communications, 14(2), 70-87.
75.13 Summary
WSN routing protocols address the unique constraints of sensor networks: energy scarcity, resource limitations, and many-to-one traffic patterns that make traditional IP routing unsuitable.
Key Takeaways:
- Four paradigms: Data-centric (Directed Diffusion), hierarchical (LEACH), geographic (GPSR), and QoS-aware (SPEED) – each suited to different application requirements
- LEACH rotation: Cluster heads consume 8-10× more energy than members; randomized rotation balances this load and extends network lifetime by approximately 8×
- Protocol selection: Use RPL for standards-based IoT deployments, LEACH for large static networks with spatial correlation, GPSR when GPS is available, and Directed Diffusion for event-driven query applications
- Energy model: The quadratic distance term (\(E_{amp} \times k \times d^2\)) means halving distance reduces amplifier energy by 4×, making short intra-cluster hops far more efficient than direct long-range transmission