81  Link Quality Based Routing

In 60 Seconds

Link quality estimation is the foundation of reliable WSN routing. The ETX (Expected Transmission Count) metric identifies that links in the “gray zone” (10-25m for 802.15.4) have packet reception rates of 10-90%, causing massive retransmissions. WMEWMA filtering with alpha=0.3 smooths noisy RSSI readings, and routing around gray zone links – even if they appear shorter – reduces end-to-end retransmissions by 40-60%.

81.1 Learning Objectives

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

• Evaluate Link Quality: Use link quality metrics to improve routing reliability and performance
• Implement WMEWMA: Configure Window Mean with Exponentially Weighted Moving Average for link estimation
• Calculate ETX/MIN-T: Compute Expected Transmission Count for path selection
• Avoid Gray Zone Links: Identify and route around unreliable intermediate-distance links

For Beginners: Link Quality Based Routing

When you connect to WiFi, your phone automatically picks the strongest signal. WSN routing does the same, but more precisely: instead of just measuring signal strength (RSSI), it measures the actual packet delivery rate and counts how many transmissions a path needs on average. A shorter path with a weak link (50% delivery rate) often loses to a longer path with strong links (90% delivery rate) – this chapter explains the ETX metric that makes this comparison mathematically rigorous.

81.2 Prerequisites

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

• WSN Routing Challenges: Understanding why hop count is insufficient for WSN routing
• Data Aggregation: How aggregation reduces transmissions and why reliable paths matter
• Wireless Sensor Networks: WSN radio characteristics and communication patterns

MVU: Minimum Viable Understanding

Core concept: Hop count is a poor routing metric for WSNs because lossy wireless links require retransmissions. ETX (Expected Transmission Count) and MIN-T metrics account for actual link quality, choosing paths that minimize total transmissions rather than just hops.

Why it matters: A 2-hop path with 50% link quality requires 8 total transmissions (including retries), while a 3-hop path with 90% quality needs only 3.69 – using ETX saves 54% energy compared to hop-count routing.

Key takeaway: Always use link quality metrics (ETX or MIN-T) over hop count. Measure link quality with WMEWMA for balanced responsiveness and stability. Avoid “gray zone” links (10-90% delivery rate) that are unpredictably unreliable.

For Kids: Meet the Sensor Squad!

Not all paths are equal! Some roads are smooth and some are bumpy – the Sensor Squad needs to pick the GOOD roads!

81.2.1 The Sensor Squad Adventure: The Bumpy Road Problem

Sammy needed to send a message to the farmhouse. He had two choices:

Path A (Short but Bumpy): 2 stops, but the roads were muddy. Half the time, messages got stuck and had to be sent AGAIN!

Path B (Longer but Smooth): 3 stops, but the roads were clean. Messages got through 9 out of 10 times!

“Path A is shorter!” said Max. “Use that one!”

“Wait,” said Lila. “Let us count how many times we ACTUALLY have to send the message.”

• Path A: 2 hops, but each one needs about 2 tries = 4 total sends
• Path B: 3 hops, each needs about 1.1 tries = 3.3 total sends

“Path B actually uses LESS energy even though it is longer!” realized Sammy. “The bumpy roads on Path A waste so much energy on retries!”

“That is why we use ETX – Expected Transmission Count,” explained Bella. “It counts the REAL number of sends needed, not just the number of stops!”

81.2.2 Key Words for Kids

Word	What It Means
Link quality	How good or reliable a wireless connection is (like how smooth a road is)
ETX	The expected number of times you need to send a message before it gets through
RSSI	How strong the radio signal is (like how loud someone’s voice sounds)
Gray zone	A distance where the signal is sometimes good and sometimes bad – very unreliable!

Key Concepts

• Routing Protocol: Algorithm determining the path a packet takes through the multi-hop WSN to reach the sink
• Convergecast: N-to-1 routing pattern where all sensor data flows toward a single sink along a tree structure
• Routing Table: Per-node data structure mapping destination addresses to next-hop neighbors
• Energy-Aware Routing: Protocol selecting paths based on node residual energy to balance consumption and maximize lifetime
• Link Quality Indicator (LQI): Metric quantifying the reliability of a wireless link — higher LQI means more reliable packet delivery
• Routing Tree: Spanning tree structure rooted at the sink used by hierarchical routing protocols
• Multi-path Routing: Maintaining multiple disjoint paths to improve reliability and enable load balancing

81.3 Introduction

Traditional routing protocols use hop count as the primary metric. However, in WSNs with unreliable wireless links, the shortest path may not be optimal.

---

81.4 Problems with Hop Count

81.4.1 1. Ignores Link Quality

A 3-hop path with reliable links is better than a 2-hop path with 50% loss: - Retransmissions on bad links waste energy - Total transmissions often higher on “shorter” paths

81.4.2 2. Doesn’t Account for Asymmetry

Forward and reverse links may have different quality: - Data might reach the next hop successfully - But ACKs fail on the poor reverse link - Results in unnecessary retransmissions

81.4.3 3. Assumes Spherical Communication Range

Reality shows highly irregular communication patterns: - Obstacles create dead zones - Interference varies by location - Fading effects unpredictable

Figure 81.1: Comparison of hop count routing (chooses 2-hop path with poor links) vs link quality routing (chooses 3-hop path with reliable links)

---

81.5 RSSI (Received Signal Strength Indicator)

Figure 81.2: RSSI measurements while driving showing signal strength variability in mobile scenarios

Figure 81.3: RSSI measurements for stationary nodes showing temporal variations and environmental effects

RSSI measures the power of a received radio signal. It provides a basic indication of link quality.

81.5.1 Characteristics

• Higher RSSI generally means better link quality
• Varies with distance, obstacles, interference
• Highly dynamic in mobile scenarios
• Can be measured passively

81.5.2 Limitations

• Temporal variations (fading)
• Spatial variations (multipath)
• Doesn’t directly indicate packet delivery rate
• Requires calibration for different hardware

---

81.6 Link Estimation with WMEWMA

Figure 81.4: WMEWMA (Window Mean with Exponentially Weighted Moving Average) for link quality estimation

Figure 81.5: Routing based on link estimation using ETX and other quality metrics

Academic Resource: Cambridge Mobile and Sensor Systems

Link estimation based routing showing how path quality metrics (ETX, packet delivery ratio) influence routing decisions

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

WMEWMA (Window Mean with Exponentially Weighted Moving Average) combines short-term and long-term link quality assessment.

81.6.1 Components

1. Snooping: Monitor broadcast packets from neighbors, track sequence numbers to detect losses

2. Window Mean (WM): Count packets received in recent window (e.g., last 30 packets)

3. EWMA: Exponentially weighted moving average smooths estimates over time

81.6.2 Formula

EWMA(t_x) = α × MA(t_x) + (1 - α) × EWMA(t_{x-1})

Where: - MA(t_x): Number of packets received in window t_x - α ∈ (0, 1): Weight parameter (higher = more responsive) - Typical: α = 0.6, window = 30 packets

Putting Numbers to It

WMEWMA responsiveness with α = 0.6: A link initially has EWMA = 27 (out of 30 packets received). The link degrades, and the next window receives only 18 packets.

Updated EWMA: \[\text{EWMA}_{\text{new}} = 0.6 \times 18 + (1 - 0.6) \times 27 = 10.8 + 10.8 = 21.6\]

The estimate dropped from 27 to 21.6 (20% decrease) in one window period. With α = 0.3 (less responsive): \[\text{EWMA}_{\text{new}} = 0.3 \times 18 + 0.7 \times 27 = 5.4 + 18.9 = 24.3\]

Lower α (0.3) only drops to 24.3 (10% decrease) – more stable but slower to detect degradation.

Link quality threshold decision: If the routing protocol requires ETX < 2 (equivalent to EWMA ≥ 15 out of 30), then α = 0.6 triggers route change after 1 window when EWMA drops to 21.6 (still above threshold), while α = 0.3 delays reaction. However, if degradation was transient (interference burst), α = 0.3 avoids unnecessary route churn. Trade-off: High α = fast adaptation + route instability. Low α = stability + slow failure detection.

81.6.3 Why WMEWMA Works

The combination provides: - WM (Window Mean): Fast response to sudden link degradation - EWMA: Stability against transient fluctuations - Minimum of both: Conservative estimate that responds quickly to failures while filtering noise

---

81.7 MIN-T (Minimum Transmission) Metric

MIN-T estimates the expected number of transmissions required to successfully deliver a packet over a path, accounting for retransmissions.

81.7.1 Formula for Link Cost

Cost(link) = 1 / (P_forward × P_backward)

Where: - P_forward: Forward link delivery probability - P_backward: Backward link delivery probability (for ACKs)

81.7.2 Path Cost

Cost(path) = Σ Cost(link_i) for all links in path

81.7.3 Example Calculation

Link	P_forward	P_backward	Cost
A→B	0.9	0.9	1/(0.9×0.9) = 1.23
B→C	0.5	0.5	1/(0.5×0.5) = 4.0

Total path cost: 1.23 + 4.0 = 5.23 expected transmissions

---

81.8 ETX (Expected Transmission Count)

ETX is equivalent to MIN-T and is the standard metric used in many WSN protocols.

81.8.1 Calculation

ETX_link = 1 / (PRR_forward × PRR_reverse)
ETX_path = Σ ETX_link for all links

81.8.2 Path Comparison Example

Path	Hops	Link PRRs	ETX per Link	Total ETX
A	2	50%, 50%	4.0, 4.0	8.0
B	3	90%, 90%, 90%	1.23, 1.23, 1.23	3.69

Path B wins despite being longer (fewer expected transmissions = less energy).

---

81.9 Worked Example: ETX-Based Path Selection

Worked Example: ETX-Based Routing Path Selection

Scenario: An industrial monitoring WSN tracks vibration levels on factory equipment. A sensor node S needs to route critical alarm data to the gateway G. Two candidate paths exist with different link qualities measured via probe packets.

Given:

Path	Hops	Link Qualities (PRR)	Transmission Energy
Path A	2	S-R1: 95%, R1-G: 90%	25 mJ per TX
Path B	3	S-R2: 85%, R2-R3: 80%, R3-G: 75%	25 mJ per TX
Path C	2	S-R4: 60%, R4-G: 55%	25 mJ per TX

Steps:

1. Calculate ETX for each path (assuming symmetric links: ETX = 1/PRR²):

2. Path A ETX calculation:

   • Link S-R1: ETX = 1 / (0.95 × 0.95) = 1 / 0.9025 = 1.11
   • Link R1-G: ETX = 1 / (0.90 × 0.90) = 1 / 0.81 = 1.23
   • Path A Total ETX = 1.11 + 1.23 = 2.34 transmissions

3. Path B ETX calculation:

   • Link S-R2: ETX = 1 / (0.85)² = 1.38
   • Link R2-R3: ETX = 1 / (0.80)² = 1.56
   • Link R3-G: ETX = 1 / (0.75)² = 1.78
   • Path B Total ETX = 1.38 + 1.56 + 1.78 = 4.72 transmissions

4. Path C ETX calculation (shortest by hop count):

   • Link S-R4: ETX = 1 / (0.60)² = 2.78
   • Link R4-G: ETX = 1 / (0.55)² = 3.31
   • Path C Total ETX = 2.78 + 3.31 = 6.09 transmissions

5. Calculate expected energy consumption:

   • Path A: 2.34 TX × 25 mJ = 58.5 mJ
   • Path B: 4.72 TX × 25 mJ = 118.0 mJ
   • Path C: 6.09 TX × 25 mJ = 152.3 mJ

Result:

Metric	Path A (2 hops)	Path B (3 hops)	Path C (2 hops)
ETX	2.34 (best)	4.72	6.09
Energy	58.5 mJ (best)	118.0 mJ	152.3 mJ
First-attempt success	85.5%	51.0%	33.0%

Path A is optimal despite having the same hop count as Path C. The high link quality saves 93.8 mJ per packet (62% energy reduction) compared to Path C.

Key Insight: Hop-count routing would see Paths A and C as equivalent (both 2 hops), potentially selecting the inferior Path C. ETX-based routing correctly identifies that link quality dominates path selection.

---

81.10 Interactive: ETX and WMEWMA Calculator

Explore how link quality affects path selection and how WMEWMA estimates evolve over time.

viewof etx_hop1 = Inputs.range([0.10, 1.00], {value: 0.90, step: 0.05, label: "Path A: Hop 1 PRR"})

viewof etx_hop2 = Inputs.range([0.10, 1.00], {value: 0.90, step: 0.05, label: "Path A: Hop 2 PRR"})

viewof etx_hop3_enable = Inputs.checkbox(["Add Hop 3 to Path A"])

viewof etx_hop3 = Inputs.range([0.10, 1.00], {value: 0.90, step: 0.05, label: "Path A: Hop 3 PRR (if enabled)"})

viewof etx_b_hop1 = Inputs.range([0.10, 1.00], {value: 0.50, step: 0.05, label: "Path B: Hop 1 PRR"})

viewof etx_b_hop2 = Inputs.range([0.10, 1.00], {value: 0.50, step: 0.05, label: "Path B: Hop 2 PRR"})

{
  const linksA = etx_hop3_enable.length > 0
    ? [etx_hop1, etx_hop2, etx_hop3]
    : [etx_hop1, etx_hop2];
  const linksB = [etx_b_hop1, etx_b_hop2];

  const etxA = linksA.reduce((sum, p) => sum + 1/(p*p), 0);
  const etxB = linksB.reduce((sum, p) => sum + 1/(p*p), 0);
  const e2eA = linksA.reduce((prod, p) => prod * p, 1);
  const e2eB = linksB.reduce((prod, p) => prod * p, 1);

  const winner = etxA <= etxB ? "Path A" : "Path B";
  const hopWinner = linksA.length <= linksB.length ? "Path A" : "Path B";
  const hopEtxAgree = winner === hopWinner;

  return html`<div style="background: var(--bs-light, #f8f9fa); padding: 1rem; border-radius: 8px; border-left: 4px solid ${etxA <= etxB ? '#16A085' : '#3498DB'}; margin-top: 0.5rem;">
  <table style="width:100%; border-collapse:collapse;">
    <tr style="background:#e9ecef"><th style="padding:6px;text-align:left">Metric</th><th>Path A (${linksA.length} hops)</th><th>Path B (${linksB.length} hops)</th></tr>
    <tr><td style="padding:4px">Hop count</td><td>${linksA.length} ${linksA.length <= linksB.length ? "(shorter)" : "(longer)"}</td><td>${linksB.length} ${linksB.length < linksA.length ? "(shorter)" : ""}</td></tr>
    <tr><td style="padding:4px"><strong>ETX (expected TX)</strong></td><td style="color:${etxA <= etxB ? '#16A085' : '#E74C3C'};font-weight:bold">${etxA.toFixed(2)} ${etxA <= etxB ? "← BEST" : ""}</td><td style="color:${etxB < etxA ? '#16A085' : '#E74C3C'};font-weight:bold">${etxB.toFixed(2)} ${etxB < etxA ? "← BEST" : ""}</td></tr>
    <tr><td style="padding:4px">End-to-end PRR</td><td>${(e2eA*100).toFixed(1)}%</td><td>${(e2eB*100).toFixed(1)}%</td></tr>
  </table>
  <p style="margin-top:0.5rem; color:${hopEtxAgree ? '#16A085' : '#E67E22'}">
  <strong>${hopEtxAgree ? "Hop count and ETX agree" : "Hop count disagrees with ETX!"}</strong>
  ${!hopEtxAgree ? ` Hop count prefers ${hopWinner} but ETX selects ${winner}. Adding the extra hop on ${winner} costs ${Math.abs(linksA.length-linksB.length)} hop(s) but saves ${Math.abs(etxA-etxB).toFixed(2)} expected retransmissions.` : ` Both metrics select ${winner}.`}
  </p>
  </div>`;
}

---

81.11 Common Pitfalls

Pitfall: Choosing Shortest Path Without Link Quality Assessment

The Mistake: Implementing hop-count based routing in WSN deployments, assuming “fewer hops = better performance,” then experiencing 30-50% packet loss because the shortest path traverses marginal wireless links.

Why It Happens: Traditional networking education emphasizes shortest path algorithms (Dijkstra, Bellman-Ford). Teams apply this intuition without realizing that a “2-hop” path with 90% link quality outperforms a “1-hop” path with 50% link quality. Hop count ignores the retransmission cost of poor links.

The Fix: Use link quality metrics like ETX (Expected Transmission Count) or MIN-T instead of hop count:

• ETX = 1/(forward_delivery_rate × reverse_delivery_rate)
• A 3-hop path with ETX=3.3 beats a 2-hop path with ETX=8.0
• Measure link quality during network formation using probe packets
• Update metrics periodically to adapt to changing conditions

Pitfall: Gray Zone Links

The Problem: Links at intermediate distances (the “gray zone”) have highly variable quality: - Sometimes work (60% delivery) - Sometimes fail (30% delivery) - Unpredictable behavior

Why It Happens: At the edge of transmission range: - Signal strength varies with environmental conditions - Small movements cause large quality changes - Interference effects magnified

The Fix:

• If measured PRR is between 10-90%, consider the link unreliable
• Prefer links with PRR > 90% (clearly good) or < 10% (clearly avoid)
• Use hysteresis: don’t switch routes for small quality differences
• Require stable measurements over time (20+ packets minimum)

---

81.12 Knowledge Check

Quiz: Link Quality Based Routing

---

81.13 Real-World Deployment: ETX Routing in Urban Environmental Monitoring

Case Study: CitySense Network in Cambridge, Massachusetts

Background: The CitySense project, a collaboration between Harvard University and BBN Technologies, deployed 100 wireless sensor nodes across Cambridge, MA to monitor air quality (CO, NO2, O3, particulate matter) and microclimate conditions. The network operated from 2007-2012 using multi-hop routing across an urban environment with buildings, trees, and vehicular traffic.

The Link Quality Challenge:

Urban environments create severe gray-zone problems. The CitySense deployment measured link characteristics across 100 nodes:

Distance Range	Number of Links	Average PRR	PRR Variance	Classification
0-15 m	342	97%	2%	Reliable
15-30 m	518	71%	24%	Gray zone
30-50 m	289	38%	31%	Gray zone
50-80 m	156	12%	15%	Unreliable
> 80 m	43	3%	4%	Dead

Key Finding: 58% of all measured links fell in the gray zone (15-50 m), confirming that urban WSN deployments cannot rely on hop count routing.

ETX vs Hop Count: Measured Comparison:

The team ran both routing strategies simultaneously on subsets of the network for 6 months:

Metric	Hop Count Routing	ETX Routing	Improvement
End-to-end delivery rate	72%	94%	+31%
Average retransmissions per packet	4.2	1.8	-57%
Average path length (hops)	2.1	2.9	+38% longer
Energy per delivered packet	105 mJ	45 mJ	-57%
Network lifetime (first node death)	4.3 months	8.1 months	+88%

Why ETX Chose Longer Paths: Hop count routing consistently selected 2-hop paths through gray-zone links (15-30 m spacing in the urban grid). ETX routing added an extra hop but stayed within reliable range, selecting 3-hop paths through sub-15 m links. The extra hop cost 33% more baseline energy, but avoiding retransmissions saved 57% total energy.

WMEWMA Tuning in Practice: The deployment tested three alpha values for WMEWMA filtering:

Alpha	Responsiveness	Stability	Route Flapping Rate	Best For
0.1	Slow (10+ min to detect failure)	Very stable	0.2 changes/hour	Static deployments
0.3	Moderate (2-3 min)	Good	1.1 changes/hour	Urban monitoring (chosen)
0.7	Fast (30 sec)	Poor	4.8 changes/hour	Mobile/vehicular

The team selected alpha=0.3 because urban environmental conditions change slowly (hourly weather shifts, daily traffic patterns) but occasional sudden events (delivery truck parking next to a node, rain starting) required detection within a few minutes.

Practical Lesson: Link quality varies by time of day in urban environments. The CitySense network measured a 15-20% PRR drop during morning and evening rush hours (7-9 AM, 5-7 PM) due to vehicular traffic causing multipath reflections and body absorption. ETX routing automatically shifted paths during these periods without manual intervention, demonstrating the value of continuous link quality monitoring over static deployment-time measurements.

🏷️ Label the Diagram

Code Challenge

81.14 Summary

This chapter explored link quality metrics as the foundation for effective WSN routing:

Key Takeaways:

1. Hop Count Fails: In lossy WSNs, shortest path by hop count often requires the most total transmissions due to retransmissions on poor links
2. ETX/MIN-T Metrics: Expected Transmission Count accounts for both forward delivery and ACK success rates, providing accurate path cost estimation
3. WMEWMA Estimation: Combining Window Mean (fast response) with EWMA (stability) provides the best of both worlds for link quality estimation
4. Gray Zone Avoidance: Links with 10-90% delivery rate are unpredictably unreliable – prefer clearly good (>90%) or clearly bad (<10%) links
5. Asymmetric Links: Forward and backward link quality often differ; MIN-T accounts for both because lost ACKs trigger retransmissions just like lost data packets

---

Match the Link Quality Concept

Order the Steps: ETX-Based Route Selection Process

81.15 What’s Next?

Topic	Chapter	Description
Trickle Algorithm	Trickle Algorithm	Efficient network reprogramming via polite gossip protocol
WSN Routing Fundamentals	WSN Routing Fundamentals	Overview of WSN routing challenges and protocol classification
Directed Diffusion	Directed Diffusion	Data-centric routing with interests and gradients
Data Aggregation	Data Aggregation	In-network data processing techniques to reduce transmissions
Labs and Games	Labs and Games	Hands-on practice and interactive routing simulations