79  WSN Routing: Directed Diffusion

In 60 Seconds

Directed Diffusion routes by WHAT data contains, not WHERE it goes: sinks flood “interest” queries, gradients (reverse paths) form naturally, sensors deliver matching data along gradients, and sinks reinforce the best path. This empirical path selection outperforms theoretical shortest-path routing by 30% and eliminates the need for node addressing or routing tables.

79.1 Learning Objectives

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

• Explain Directed Diffusion Phases: Describe interest propagation, gradient establishment, and data delivery mechanisms
• Implement Data-Centric Routing: Design systems that route based on content attributes rather than node addresses
• Analyze Gradient Reinforcement: Evaluate how sinks optimize paths through positive and negative reinforcement

79.2 Prerequisites

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

• WSN Routing Fundamentals: Understanding the classification and challenges of WSN routing
• Wireless Sensor Networks: Knowledge of WSN architecture and communication patterns

MVU: Minimum Viable Understanding

Core concept: Directed Diffusion is a data-centric routing protocol where sinks broadcast “interest” queries that flood the network, establishing gradients (reverse paths) along which matching sensor data flows back – the network routes by WHAT data contains, not WHERE it goes.

Why it matters: Traditional address-based routing requires knowing sensor IDs and maintaining routing tables. Directed Diffusion eliminates this overhead by letting the data itself drive routing, enabling automatic path discovery, multipath redundancy, and in-network aggregation.

Key takeaway: Directed Diffusion operates in four phases: interest propagation (sink floods query), gradient establishment (reverse paths form), exploratory data delivery (test all paths), and reinforcement (sink strengthens the best path). This empirical path selection outperforms theoretical shortest-path by 30%.

For Kids: Meet the Sensor Squad!

Directed Diffusion is like a teacher asking a question and the students who know the answer raising their hands!

79.2.1 The Sensor Squad Adventure: The Question Game

Farmer Jones needed to know if any part of the farm was getting too hot. Instead of asking each sensor individually (that would take forever!), he used a clever trick.

“Hey everyone!” Farmer Jones shouted across the farm. “Is anyone measuring a temperature above 30 degrees?” This was his interest – a question broadcast to everyone.

Each sensor heard the question and remembered which direction it came from (that is a gradient – like arrows pointing back to the farmer). The question passed from sensor to sensor until EVERY sensor on the farm heard it.

Sammy the Temperature Sensor near the greenhouse called back: “Yes! I am measuring 35 degrees!” His message followed the gradient arrows back to Farmer Jones, hopping from friend to friend.

But here is the clever part – the message traveled along MULTIPLE paths at first (exploratory phase). Farmer Jones noticed that the path through Lila was faster and more reliable than the path through Max. So he sent a special message: “Sammy, please send your reports through Lila from now on!” That is called reinforcement – strengthening the best path!

79.2.2 Key Words for Kids

Word	What It Means
Interest	A question broadcast to all sensors (like a teacher asking the whole class)
Gradient	Arrows pointing back to whoever asked the question
Reinforcement	Choosing the best path and saying “use this one!”
Data-centric	Caring about what the message says, not who sent it

79.3 Introduction

Directed Diffusion is a foundational data-centric routing protocol that revolutionized how we think about routing in sensor networks. Rather than routing to specific node addresses, Directed Diffusion routes data based on its content, using a publish-subscribe paradigm where sinks express “interests” in data and sources respond with matching data.

For Beginners: Directed Diffusion - Routing by What, Not Who

Traditional internet routing: “Send this email to bob@192.168.1.50” - Router looks up address in routing table - Forwards packet toward destination address - Doesn’t care what’s inside the packet

Directed Diffusion (data-centric): “I want all temperature readings above 30°C from the northwest field” - Network floods this “interest” to all sensors - Sensors matching the interest send data back - Multiple paths form automatically - Network doesn’t need to know sensor addresses!

Key phases:

1. Interest propagation: Sink broadcasts “I want X” everywhere
2. Gradient setup: Each node records direction toward interested sink
3. Data delivery: Matching sensors send data along gradients
4. Reinforcement: Sink strengthens good paths, weakens bad ones

79.4 Directed Diffusion Protocol

Directed Diffusion Overview

Figure 79.1: Directed diffusion data-centric routing with interest propagation and gradient-based forwarding.

Directed Diffusion uses three main phases: interest propagation, gradient establishment, and data delivery with reinforcement.

79.4.1 Interest Propagation

Interest Propagation

Figure 79.2: Interest propagation phase showing how sink queries flood the network

Academic Resource: Cambridge Mobile and Sensor Systems

Interest propagation showing how sink broadcasts interest and nodes forward to establish gradients

Source: University of Cambridge, Mobile and Sensor Systems Course (Prof. Cecilia Mascolo)

The sink initiates data collection by flooding an interest message through the network.

Interest Structure:

Interest = {
  type: "temperature",
  interval: "20ms",           // Desired data rate
  duration: "10 seconds",     // How long to report
  rect: [-100, 100, 200, 400] // Geographic region
}

Interest Propagation Rules:

1. Sink broadcasts interest to all neighbors
2. Each node caches the interest
3. Nodes rebroadcast to their neighbors
4. Creates reverse path gradients toward sink

Putting Numbers to It

Interest propagation overhead calculation: In a 200-node WSN with average node degree (number of neighbors) = 6, the sink broadcasts an interest message (48 bytes including type, interval, duration, region).

Total interest flooding cost: \[\text{Transmissions} = n = 200 \text{ broadcasts (each node forwards once)}\] Total reception events (node×neighbor pairs): \(n \times \text{avg degree} / 2 = 200 \times 6 / 2 = 600\) (using handshake lemma). Each unique broadcast is received by an average of 6 neighbors, but energy is counted per transmission, not per reception.

Airtime per transmission: At 250 kbps (802.15.4 radio): \(t = \frac{48 \text{ bytes} \times 8 \text{ bits/byte}}{250{,}000 \text{ bps}} = 1.54 \text{ ms}\)

Energy per transmission: CC2420 radio at 17.4 mA, 3V: \(E = 1.54 \text{ ms} \times 17.4 \text{ mA} \times 3 \text{ V} = 80.4 \text{ µJ}\)

Total flood energy (transmit side): \(200 \times 80.4 \text{ µJ} = 16.1 \text{ mJ}\) for the entire network (200 transmissions, one per node), or 0.08 mJ per node. Including receive-side energy (each node receives from avg 6 neighbors × 80.4 µJ × 0.5): total ≈ \(16.1 + 24.1 = 40.2 \text{ mJ}\) network-wide. Compare to AODV route discovery requiring an RREQ flood (16.1 mJ) plus unicast RREP for each source: Directed Diffusion’s single shared interest flood covers all sources simultaneously, making it 30–50% more efficient for multi-source deployments.

Figure 79.3: Interest propagation in Directed Diffusion showing sink broadcasting interest that floods through network, nodes caching and rebroadcasting to establish gradients

79.4.2 Gradient Establishment

Gradient Establishment

Figure 79.4: Gradients point toward interested sinks with associated data rates

As interests propagate, each node establishes gradients - directional records pointing toward the sink.

Gradient Properties:

• Direction: Which neighbor sent the interest
• Data rate: Requested sampling interval
• Expiration: When interest times out

Multiple Gradients:

• A node may have multiple gradients to same sink (via different neighbors)
• Different paths can have different data rates
• Enables multipath routing

Figure 79.5: Gradient establishment diagram showing how node maintains gradients for different neighbors with data rates and expiration times pointing toward sink

79.4.3 Data Delivery

Data Delivery Phases

Figure 79.6: Two-phase pull: exploratory data along all gradients, then reinforced paths

When a source has data matching an interest, it sends data along established gradients.

Data Delivery Process:

1. Source generates matching data
2. Sends data along all gradients (initially)
3. Data propagates hop-by-hop toward sink
4. Each intermediate node forwards based on its gradients

Two-Phase Data Delivery:

1. Exploratory phase: Low-rate data along all gradients to discover paths
2. Reinforced phase: High-rate data along best path(s) after sink reinforces

Putting Numbers to It

Quantifying two-phase pull overhead vs. benefit: A source has 3 gradient paths to the sink with exploratory data rate = 1 event per 2 seconds, reinforced rate = 10 events per second.

Exploratory phase (10 seconds): Source sends 5 events per path × 3 paths = 15 total transmissions. Energy: \(15 \times 50 \text{ µJ} = 750 \text{ µJ}\).

Path evaluation at sink: Of 15 exploratory packets, sink receives 14 (1 lost on Path C). Latencies: Path A = 42 ms, Path B = 68 ms, Path C = 51 ms. Sink reinforces Path A (lowest latency, 100% delivery).

Reinforced phase (3,600 seconds = 1 hour): Source sends 10 events/sec × 3,600 sec = 36,000 events only on Path A. Energy: \(36{,}000 \times 50 \text{ µJ} = 1{,}800 \text{ mJ}\).

Comparison to always-multipath: If source continued sending on all 3 paths at full rate: \(36{,}000 \times 3 = 108{,}000\) transmissions = 5,400 mJ. Reinforcement saves 3,600 mJ (67% energy savings) by focusing on the best path after empirical testing. The 750 µJ exploratory overhead is negligible (<0.04% of total energy).

79.4.4 Gradient Reinforcement

Academic Resource: Two-Phase Pull Operation

Gradient reinforcement showing sink selecting best path and increasing data rate

Source: University of Cambridge, Mobile and Sensor Systems Course

The sink can reinforce preferred paths by sending reinforcement messages.

Positive Reinforcement:

• “Send me data faster via this path”
• Increases gradient data rate
• Used for good-quality, low-latency paths

Negative Reinforcement:

• “Slow down or stop on this path”
• Decreases gradient data rate
• Used for poor or redundant paths

Figure 79.7: Gradient reinforcement process showing sink receiving data via multiple paths, evaluating quality, and reinforcing the best path while letting others expire

79.5 Worked Example: Directed Diffusion for Wildfire Detection

Scenario: 200 temperature sensors deployed across a 2 km × 2 km forest grid. A fire monitoring station (sink) needs to detect temperatures above 60°C anywhere in the forest. Sensors have 100 m radio range and run on AA batteries.

Phase 1: Interest Propagation

Sink broadcasts:

Interest = {
  type: "temperature",
  threshold: "> 60°C",
  interval: "500ms",
  duration: "3600 seconds",
  rect: [0, 0, 2000, 2000]
}

Propagation takes up to 28 hops to reach the farthest corner (diagonal of 2 km × 2 km grid = 2,828 m, divided by 100 m range). At 5 ms per-hop forwarding delay: 140 ms to flood the entire network. Each of the 200 nodes stores the interest and creates a gradient pointing toward the neighbor that forwarded it.

Total flooding cost: 200 nodes x 1 broadcast each x 48 bytes = 9,600 bytes. At 250 kbps (802.15.4): 0.31 seconds of airtime across the network.

Phase 2: Gradient Setup

Node 147 (near a campfire) detects 72C. It has 3 gradients toward the sink: - Via Node 146: 8 hops, gradient data rate = 1 event/500ms - Via Node 132: 9 hops, gradient data rate = 1 event/500ms - Via Node 148: 10 hops, gradient data rate = 1 event/500ms

Phase 3: Exploratory Data Delivery

Node 147 sends low-rate data (1 event/2000ms) along ALL three paths simultaneously:

Data = {source: 147, type: "temperature", value: 72.3,
        timestamp: 1706000000, seq: 1}

Path	Hops	Delivery Time	Packets Lost
Via 146	8	42ms	0/10
Via 132	9	68ms (congested hop)	2/10
Via 148	10	51ms	1/10

Phase 4: Reinforcement

Sink evaluates: Path via 146 has lowest latency (42ms) AND zero loss. Sink sends positive reinforcement:

Reinforce = {target: 147, via: 146, new_rate: "1 event/500ms"}

Result: Node 147 now sends high-rate data only via Node 146. The other two paths expire after their gradient timeout (30s).

Energy comparison vs. shortest-path routing:

Metric	Shortest Path (AODV)	Directed Diffusion
Route discovery	RREQ broadcast flood (200 nodes) + per-source unicast RREP	1 interest flood for all sources
Path quality	Theoretical (hop count)	Empirical (measured)
Delivery ratio	87% (lossy intermediate links)	96% (best path selected)
Energy for 1 hour	18.4 mJ per source node	12.8 mJ per source node
Failure recovery	Re-flood RREQ (400ms)	Switch to backup gradient (5ms)

The 30% energy improvement comes from two factors: (1) interest flooding is cheaper than per-source route discovery, and (2) empirical path selection avoids high-loss links that theoretical metrics miss.

79.5.1 Protocol Benefits

1. Robustness:

• Multiple paths exist naturally
• Path failure leads to use of alternative gradient
• No explicit route repair needed

2. Data Aggregation:

• Intermediate nodes can aggregate data
• Reduces redundant transmissions
• Enabled by data-centric naming

3. Energy Efficiency:

• Reinforcement focuses traffic on good paths
• Weak paths expire naturally
• In-network processing reduces transmissions

4. Adaptivity:

• New interests can be issued anytime
• Network adapts to changing conditions
• No global topology knowledge needed

---

Quiz: Directed Diffusion

79.6 Interactive: Directed Diffusion Overhead Calculator

Compare the energy cost of interest flooding against the savings from empirical path reinforcement.

viewof dd_nodes = Inputs.range([20, 500], {value: 200, step: 10, label: "Network size (nodes)"})

viewof dd_paths = Inputs.range([2, 6], {value: 3, step: 1, label: "Gradient paths per source"})

viewof dd_rate = Inputs.range([1, 50], {value: 10, step: 1, label: "Reinforced data rate (events/sec)"})

viewof dd_duration_hr = Inputs.range([1, 24], {value: 1, step: 1, label: "Reporting duration (hours)"})

{
  const E_tx_packet = 50e-6; // J per packet transmission (50 µJ)
  const exploratory_rate = 0.5; // events/sec during exploratory phase (10s)
  const exploratory_duration = 10; // seconds

  // Interest flood cost: each node broadcasts once
  const flood_cost_J = dd_nodes * E_tx_packet;

  // Exploratory phase: source sends at low rate along all paths
  const exploratory_pkts = exploratory_rate * exploratory_duration * dd_paths;
  const exploratory_cost_J = exploratory_pkts * E_tx_packet;

  // Reinforced phase: source sends at full rate on 1 path only
  const reinf_duration_s = dd_duration_hr * 3600;
  const reinf_pkts = dd_rate * reinf_duration_s;
  const reinf_cost_with_J = reinf_pkts * E_tx_packet;

  // Without reinforcement: source sends on all paths at full rate
  const reinf_cost_without_J = reinf_pkts * dd_paths * E_tx_packet;

  const savings_J = reinf_cost_without_J - reinf_cost_with_J;
  const total_overhead_J = flood_cost_J + exploratory_cost_J;
  const net_savings_J = savings_J - total_overhead_J;
  const savings_pct = ((savings_J / reinf_cost_without_J) * 100).toFixed(1);

  return html`<div style="background: var(--bs-light, #f8f9fa); padding: 1rem; border-radius: 8px; border-left: 4px solid #3498DB; margin-top: 0.5rem;">
  <p><strong>Interest flood cost:</strong> ${(flood_cost_J * 1000).toFixed(2)} mJ (${dd_nodes} nodes × 50 µJ)</p>
  <p><strong>Exploratory overhead:</strong> ${(exploratory_cost_J * 1000).toFixed(3)} mJ (${exploratory_pkts.toFixed(0)} packets, negligible)</p>
  <p><strong>Total discovery overhead:</strong> ${(total_overhead_J * 1000).toFixed(2)} mJ</p>
  <hr/>
  <p><strong>Sending on all ${dd_paths} paths (no reinforcement):</strong> ${(reinf_cost_without_J * 1000).toFixed(0)} mJ over ${dd_duration_hr}h</p>
  <p><strong>Sending on 1 reinforced path:</strong> ${(reinf_cost_with_J * 1000).toFixed(0)} mJ over ${dd_duration_hr}h</p>
  <p style="color: #16A085;"><strong>Energy savings from reinforcement:</strong> ${(savings_J * 1000).toFixed(0)} mJ (${savings_pct}% reduction)</p>
  <p style="color: #E67E22;"><strong>Net savings after overhead:</strong> ${(net_savings_J * 1000).toFixed(0)} mJ — reinforcement overhead is recouped within seconds of operation</p>
  </div>`;
}

---

79.7 When to Use Directed Diffusion: Decision Framework

Directed Diffusion excels in specific deployment scenarios but is unsuitable for others. Understanding these boundaries prevents misapplication.

Worked Example: Choosing Between Directed Diffusion and Tree-Based Routing

Scenario: An environmental agency deploys 500 sensors across a 2 km² wetland to monitor water quality. The agency needs two types of data: (A) periodic reports every 30 minutes from all sensors, and (B) event-driven alerts when chemical levels exceed thresholds.

Analysis for Periodic Reports (Type A):

• Traffic pattern: All 500 sensors reporting to 2 sinks every 30 minutes
• With Directed Diffusion: Sinks broadcast interest every 30 minutes, creating 500 x avg_hops = ~2,500 gradient entries. Exploratory phase adds overhead per cycle.
• With RPL (tree-based): Single DODAG construction, then persistent forwarding paths. No per-query overhead.
• Winner: RPL – for predictable periodic data, building a routing tree once and reusing it is more efficient than rediscovering gradients each cycle.

Analysis for Event-Driven Alerts (Type B):

• Traffic pattern: Sparse, unpredictable. Only 2-10 sensors trigger per day when chemical spills occur.
• With Directed Diffusion: Sink publishes standing interest “chemical_level > threshold”. Only triggered sensors send data along existing gradients. No wasted routing for silent sensors.
• With RPL: All 500 sensors maintain routes to sink permanently, consuming energy for tree maintenance even when most never generate alerts.
• Winner: Directed Diffusion – for event-driven, query-specific data, the interest/gradient model avoids maintaining unnecessary routes.

Hybrid Decision: Use RPL for periodic telemetry (Type A) and Directed Diffusion for event queries (Type B). This dual-stack approach is used in practice by platforms like TinyDB (UC Berkeley) that layer query-based routing on top of tree-based collection.

Deployment Characteristic	Directed Diffusion	Tree-Based (RPL/CTP)	Flat Flooding (SPIN)
Best for	Event-driven queries, named data	Periodic data collection	Small networks (< 30 nodes)
Network size	50-500 nodes	10-10,000 nodes	< 50 nodes
Traffic pattern	Sparse, query-driven	Continuous, periodic	Infrequent, any-to-any
In-network aggregation	Native (gradient-based)	Possible but add-on	Not supported
Multiple sinks	Efficient (natural gradient merge)	Requires multi-DODAG	N/A
Overhead in steady state	Low (gradients expire naturally)	Moderate (tree maintenance)	High (metadata broadcasts)
Path recovery after failure	Fast (multiple gradients exist)	Moderate (parent selection)	Fast (re-advertise)
Real-world adoption	Research/specialized (TinyDB, Cougar)	Dominant in IoT (Contiki, RIOT)	Academic only

Why Directed Diffusion Lost to RPL in Practice: Despite its elegant design, Directed Diffusion was largely superseded by RPL (RFC 6550) for three reasons: (1) RPL handles the dominant IoT traffic pattern (many-to-one periodic reporting) more efficiently, (2) RPL integrates with IPv6/6LoWPAN while Directed Diffusion requires custom naming, and (3) RPL has production-quality implementations in Contiki and RIOT OS while Directed Diffusion remained primarily academic. However, Directed Diffusion’s core ideas – data-centric naming, in-network processing, and gradient-based forwarding – directly influenced RPL’s design and remain relevant for content-centric networking (CCN/NDN) research.

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

79.8 Summary

Directed Diffusion introduced key concepts that influenced many subsequent WSN routing protocols:

Key Takeaways:

1. Data-Centric Routing: Route based on content attributes, not node addresses
2. Interest Propagation: Sinks broadcast queries that establish reverse-path gradients
3. Gradient-Based Forwarding: Data follows gradients back toward interested sinks
4. Two-Phase Pull: Exploratory phase tests paths, reinforcement phase optimizes
5. Adaptive Path Selection: Empirical path quality determines routing, not theoretical metrics

---

79.9 What’s Next?

Topic	Chapter	Description
Data Aggregation	WSN Routing: Data Aggregation	In-network data processing techniques that complement data-centric routing
Link Quality	WSN Routing: Link Quality	RSSI, WMEWMA, and MIN-T metrics for reliable path selection
Trickle Algorithm	WSN Routing: Trickle Algorithm	Efficient network reprogramming and code dissemination
Labs and Games	WSN Routing: Labs and Games	Hands-on practice and interactive routing simulations
Routing Fundamentals	WSN Routing Fundamentals	Overview of WSN routing challenges and classification

Match the Directed Diffusion Concept

Order the Directed Diffusion Protocol Phases

---

Related Chapters

• WSN Routing Fundamentals - Overview of WSN routing challenges and classification
• WSN Routing: Data Aggregation - In-network data processing techniques
• WSN Routing: Link Quality - RSSI, WMEWMA, and MIN-T metrics
• WSN Routing: Trickle Algorithm - Network reprogramming protocol
• WSN Routing: Labs and Games - Hands-on practice and interactive simulations