438  WSN Routing: Directed Diffusion

438.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: Understand how sinks optimize paths through positive and negative reinforcement

438.2 Prerequisites

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

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

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

438.4 Directed Diffusion Protocol

Artistic visualization of directed diffusion routing showing interest propagation from sink to sources with gradient establishment and data delivery along reinforced paths

Directed Diffusion Overview
Figure 438.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.

438.4.1 Interest Propagation

Interest propagation in directed diffusion showing how the sink broadcasts interest messages that flood through the network establishing reverse path gradients

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

Cambridge lecture slide showing directed diffusion interest propagation where sink floods interest query containing type=four-legged-animal, interval=20ms, duration=10s, rect=[-100,100,200,400], with nodes forwarding and caching interests to establish data collection paths

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

%% fig-alt: "Interest propagation in Directed Diffusion showing sink broadcasting interest that floods through network, nodes caching and rebroadcasting to establish gradients"
%%{init: {'theme': 'base', 'themeVariables': {'primaryColor': '#2C3E50', 'primaryTextColor': '#fff', 'primaryBorderColor': '#16A085', 'lineColor': '#16A085', 'secondaryColor': '#E67E22', 'tertiaryColor': '#ECF0F1', 'fontSize': '16px'}}}%%
sequenceDiagram
    participant S as Sink
    participant N1 as Node 1
    participant N2 as Node 2
    participant N3 as Node 3
    participant SRC as Source

    Note over S: Interest: "temperature > 30°C<br/>interval=20ms, duration=10s"

    S->>N1: Interest broadcast
    S->>N2: Interest broadcast
    N1->>N2: Forward interest
    N1->>N3: Forward interest
    N2->>N3: Forward interest
    N2->>SRC: Forward interest
    N3->>SRC: Forward interest

    Note over N1,SRC: All nodes cache interest<br/>Create gradients toward sink

    Note over SRC: Source matches interest!<br/>(has temperature > 30°C)

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

438.4.2 Gradient Establishment

Gradient establishment in directed diffusion showing how received interests create directional gradients pointing toward the sink with associated data rates

Gradient Establishment
Figure 438.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

%% fig-alt: "Gradient establishment diagram showing how node maintains gradients for different neighbors with data rates and expiration times pointing toward sink"
%%{init: {'theme': 'base', 'themeVariables': {'primaryColor': '#2C3E50', 'primaryTextColor': '#fff', 'primaryBorderColor': '#16A085', 'lineColor': '#16A085', 'secondaryColor': '#E67E22', 'tertiaryColor': '#ECF0F1', 'fontSize': '16px'}}}%%
graph TD
    subgraph "Node A's Gradient Table"
        SINK["Sink (Interest source)"]

        GRAD1["Gradient 1:<br/>via Neighbor B<br/>Rate: 1 event/20ms<br/>Expires: 10s"]

        GRAD2["Gradient 2:<br/>via Neighbor C<br/>Rate: 1 event/20ms<br/>Expires: 10s"]

        DATA["Incoming Data<br/>from sources"]
    end

    DATA -->|"Forward via<br/>any gradient"| GRAD1
    DATA -->|"Alternative<br/>path"| GRAD2

    GRAD1 -->|"Path 1"| SINK
    GRAD2 -->|"Path 2"| SINK

    style SINK fill:#E67E22,stroke:#2C3E50,stroke-width:3px,color:#fff
    style GRAD1 fill:#16A085,stroke:#2C3E50,stroke-width:2px,color:#fff
    style GRAD2 fill:#3498DB,stroke:#2C3E50,stroke-width:2px,color:#fff
    style DATA fill:#2C3E50,stroke:#16A085,stroke-width:2px,color:#fff

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

438.4.3 Data Delivery

Two-phase pull model in directed diffusion showing initial exploratory data flow along all gradients followed by reinforced high-rate data on optimal paths

Data Delivery Phases
Figure 438.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

438.4.4 Gradient Reinforcement

Cambridge lecture slide illustrating directed diffusion two-phase pull where sink initially receives low-rate exploratory data via multiple paths, evaluates latency and quality, then sends reinforcement message to strengthen the best path requesting higher data rate

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

%% fig-alt: "Gradient reinforcement process showing sink receiving data via multiple paths, evaluating quality, and reinforcing the best path while letting others expire"
%%{init: {'theme': 'base', 'themeVariables': {'primaryColor': '#2C3E50', 'primaryTextColor': '#fff', 'primaryBorderColor': '#16A085', 'lineColor': '#16A085', 'secondaryColor': '#E67E22', 'tertiaryColor': '#ECF0F1', 'fontSize': '16px'}}}%%
sequenceDiagram
    participant SRC as Source
    participant P1 as Path 1 (fast)
    participant P2 as Path 2 (slow)
    participant SINK as Sink

    Note over SRC,SINK: Phase 1: Exploratory data (low rate)

    SRC->>P1: Data (rate: 1/20ms)
    SRC->>P2: Data (rate: 1/20ms)
    P1->>SINK: Data arrives (latency: 50ms)
    P2->>SINK: Data arrives (latency: 200ms)

    Note over SINK: Evaluate paths:<br/>Path 1 better (lower latency)

    SINK->>P1: REINFORCE (rate: 1/5ms)

    Note over SRC,SINK: Phase 2: Reinforced data (high rate)

    SRC->>P1: Data (rate: 1/5ms)

    Note over P2: Gradient expires<br/>(not reinforced)

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

438.4.5 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

Question 1: Why does Directed Diffusion initially send data along multiple gradients before reinforcement?

Explanation: Directed Diffusion’s two-phase pull operates as follows: (1) Exploratory phase: Source sends low-rate data along ALL gradients. This tests actual path performance (latency, loss rate, reliability) rather than theoretical metrics. Why? Link quality in WSN varies unpredictably - a path that looks “shortest” by hop count might have lossy links. (2) Evaluation at sink: Sink receives data via multiple paths and measures empirical quality: Which path delivered first? Which path had fewer losses? Which path shows consistent performance? (3) Reinforcement phase: Sink sends reinforcement message along the empirically best path: “Increase data rate to 1 event/5ms on this path.” Source and intermediate nodes adjust, focusing traffic on the proven path. (4) Path maintenance: Non-reinforced gradients expire naturally. If reinforced path fails, sink can reinforce a different gradient from the exploratory phase or issue new interest. Why this matters: (1) No false assumptions: Unlike hop-count routing that assumes all links are equal, Directed Diffusion tests actual conditions. (2) Adaptation: If best path degrades, sink can reinforce alternative. (3) Minimal overhead: Exploratory phase uses low data rate (1/20ms), so testing multiple paths costs little. (4) Real WSN benefit: Studies show 30% better delivery rate vs. single-path protocols by selecting paths based on measured performance rather than estimated metrics.

Question 2: In Directed Diffusion, what triggers the sink to send a reinforcement message?

Explanation: Reinforcement is sink-initiated based on observed performance: (1) Data reception: Sink receives exploratory data packets from multiple paths (recall: source sends to all gradients initially). (2) Performance evaluation: Sink measures for each path: arrival time (latency), packet sequence (detect losses), data freshness (timestamp comparison). (3) Decision: Sink identifies superior path based on application needs (lowest latency for real-time, lowest loss for reliability). (4) Reinforcement: Sink sends “positive reinforcement” message back along the chosen path, requesting higher data rate. This message travels hop-by-hop, updating gradient data rates at each node. Why sink-initiated?: (1) End-to-end view: Only sink knows which path actually delivered data successfully. Intermediate nodes see local view only. (2) Application awareness: Sink knows application requirements (latency-critical? reliability-critical?) and can select path accordingly. (3) Flexibility: Sink can reinforce multiple paths for redundancy or load balancing if needed. Reinforcement message content: “Reinforce gradient to [neighbor] with data rate [1 event/5ms]”. Each intermediate node updates its gradient table and forwards reinforcement toward source.

438.5 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

438.6 What’s Next?

The next chapter explores Data Aggregation techniques that work with data-centric routing to reduce transmissions and save energy.

Continue to Data Aggregation →