431  Mobile Sink Path Planning and Data MULE Coordination

431.1 Learning Objectives

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

  • Design Mobile Sink Systems: Build path planning and optimization for data collection
  • Apply TSP-Based Tour Planning: Implement optimal visiting sequences for sensor networks
  • Configure Adaptive Path Planning: Handle runtime events like buffer overflows and priority data
  • Coordinate Data MULEs: Schedule multiple mobile data collectors for efficient coverage
  • Implement Multi-MULE Strategies: Deploy partitioned, opportunistic, and auction-based coordination

431.2 Prerequisites

Required Chapters: - WSN Production Deployment - Production framework basics - WSN Stationary Mobile Fundamentals - Core mobility concepts

Technical Background: - Mobile sink architectures - Energy consumption in mobile systems - Data collection strategies

Estimated Time: 18 minutes

431.3 Mobile Sink Path Planning Strategies

Mobile sinks must balance latency, energy consumption, and data collection completeness.

431.3.1 Path Planning Objectives

Strategy Latency Energy (Sink) Energy (Sensors) Complexity Best For
Random Walk High (hours) High (inefficient) Low (opportunistic) Low Unstructured environments
Fixed Route Medium (predictable) Low (optimized) Low (scheduled wake) Low Regular monitoring
TSP Tour Low (optimized) Medium (good path) Low (single visit) High Time-critical data
Adaptive Variable Medium Medium Very High Dynamic priorities
Multi-Sink Very Low (parallel) High (multiple vehicles) Low (load balanced) High Large-scale systems

431.3.2 Traveling Salesman Problem (TSP) Tours

For data collection from stationary sensors, mobile sink computes optimal visiting order.

Problem Formulation: - Given: N sensor locations {s1, s2, …, sn} - Find: Tour minimizing total distance while visiting all sensors - Constraint: Return to base station

Optimization Variants:

  1. Minimum Latency Tour: Visit high-priority sensors first
    • Weight edges by data urgency: dij x (1 + priorityj)
    • Result: Critical sensors serviced quickly
  2. Energy-Constrained Tour: Limit tour length to sink battery budget
    • Partial tours if cannot visit all nodes
    • Return to base for recharge, then continue
  3. Deadline-Aware Tour: Ensure data collected before expiry
    • Some sensors have time-sensitive data (e.g., event detection)
    • Schedule visits to meet deadlines

Example - Wildlife Camera Network: - 50 cameras monitoring migration route - Mobile ATV collects images weekly - TSP tour: 42 km vs random walk: 68 km (38% reduction) - Tour time: 3.5 hours vs 5.5 hours - Battery: 60% remaining vs 15% (safety margin)

431.3.3 Adaptive Path Planning

Dynamic environments require runtime path adjustments.

Graph diagram

Graph diagram
Figure 431.1: Adaptive planning adjusts mobile sink routes in response to network events and changing priorities.

Fig-alt: Adaptive path planning feedback loop showing initial TSP tour execution, event detection for sensor failures, buffer overflows, or low battery, triggering replanning to skip failed sensors, prioritize urgent nodes, or return to base for recharge, then continuing with updated tour.

Trigger Conditions for Replanning:

  1. High-Priority Event: Sensor detects fire, intrusion, equipment failure
    • Immediate deviation to event location
    • Collect detailed data, verify alert
    • Return to planned tour
  2. Buffer Overflow Warning: Sensor reports buffer >80% full
    • Risk of data loss if not serviced soon
    • Insert into tour before overflow
  3. Energy Depletion Alert: Node battery critically low
    • Last chance to collect accumulated data
    • High priority visit
  4. Obstacle Detection: Planned path blocked (road closed, terrain impassable)
    • Recompute feasible path
    • May skip unreachable sensors

Algorithm - Greedy Insertion Heuristic:

Current tour: [Base -> A -> B -> C -> D -> Base]
New high-priority node: E

For each edge in tour (A-B, B-C, C-D, D-Base):
    cost_insert = distance(prev, E) + distance(E, next) - distance(prev, next)
    Select minimum cost insertion point

Result: [Base -> A -> E -> B -> C -> D -> Base]

Real-World Example - Disaster Response: - Hurricane aftermath monitoring (Florida, 2023) - 100 sensors in evacuation zone - Planned tour: 8-hour systematic sweep - Hour 3: Sensor #47 detects gas leak (high priority) - Replanning: Insert #47 next (15 min detour), complete original tour - Result: Gas leak confirmed in 20 minutes vs 5 hours (planned visit)

431.4 Data MULE Coordination

Multiple mobile collectors require coordination to avoid redundant visits and coverage gaps.

431.4.1 Multi-MULE Strategies

Graph diagram

Graph diagram
Figure 431.2: MULE coordination strategies: partitioned zones assign fixed regions to each MULE, while auction-based coordination allows sensors to select the best MULE dynamically based on distance and availability.

Fig-alt: Multi-MULE coordination showing two strategies. Partitioned zones assigns three MULEs to separate geographic zones (green). Auction-based coordination shows a sensor (orange) receiving bids from two MULEs and selecting the one with fastest ETA (10 min) for data collection.

Strategy Coordination Coverage Energy Latency Best For
Partitioned Static zones Guaranteed Balanced Predictable Structured deployments
Opportunistic None (independent) Redundant Unbalanced Variable Sparse networks
Auction-Based Bidding protocol Optimized Near-optimal Low Dynamic environments
Leader-Follower Central control Complete Leader-dependent Low Small MULE teams

431.4.2 Partitioned Zones Strategy

Divide network into regions, assign one MULE per region.

Implementation: - Geographic partitioning (Voronoi cells) - Each MULE responsible for all sensors in its zone - No inter-MULE communication required

Example: 400-node farm, 4 MULEs, 100 nodes each

Pros: - Simple, no coordination overhead - Predictable coverage and latency - Easy troubleshooting (clear responsibility)

Cons: - Load imbalance if zones have different node densities - Single point of failure per zone - Cannot adapt to MULE failures

431.4.3 Auction-Based Coordination

Sensors “advertise” data urgency, MULEs “bid” based on capability.

Protocol Flow: 1. Sensors broadcast data urgency (buffer level, priority) 2. MULEs receive advertisements within communication range 3. Each MULE calculates bid: distance, battery, current schedule 4. Sensor selects MULE with best bid (lowest cost, fastest service) 5. Selected MULE adds sensor to tour

Example Protocol:

Sensor S broadcasts: "100 KB data, priority=HIGH, buffer=85%"
MULE M1: "Distance=500m, ETA=10min, battery=60%"
MULE M2: "Distance=1200m, ETA=25min, battery=90%"
Sensor S selects: M1 (faster service despite lower battery)
M1 adds S to tour, navigates to location, collects data

Advantages: - Dynamic adaptation to changing conditions - Load balancing across MULEs - Graceful degradation when MULEs fail

Challenges: - Communication overhead for bidding - May require repeated auctions - Convergence time in dense networks

431.4.4 Opportunistic Collection

MULEs operate independently, collecting data when encountering sensors.

Best For: - Human-carried devices (smartphones) - Vehicles with unpredictable routes (taxis, delivery trucks) - Sparse networks where coordination impractical

Trade-offs: - High latency variability - Potential redundant collection (multiple MULEs visit same sensor) - No guaranteed coverage

Example - Urban Bus Network: - 50 buses with data collection hardware - 500 sensors along bus routes - Each sensor opportunistically uploads when bus passes - Average latency: 4-6 hours (bus route frequency) - Cost: Zero dedicated mobility (existing infrastructure)

431.4.5 Leader-Follower Coordination

Central controller (leader) assigns tasks to MULEs (followers).

Architecture:

     Central Controller
     /      |      \
   MULE1  MULE2  MULE3
     |      |      |
  [Sensors in assigned area]

Protocol: 1. Controller receives sensor status updates 2. Controller computes optimal MULE assignments 3. Controller sends route instructions to MULEs 4. MULEs execute assigned routes 5. MULEs report completion, controller reassigns

Advantages: - Global optimization (controller sees entire network) - Can handle MULE failures (reassign to remaining MULEs) - Prioritization based on network-wide view

Challenges: - Single point of failure (controller) - Communication overhead to/from controller - Latency for centralized decision-making

431.5 Practical Considerations

431.5.1 MULE Selection Criteria

When choosing mobile data collectors, consider:

Factor Ground Robot UAV/Drone Vehicle (Bus/Tractor) Human Carrier
Speed 0.5-2 m/s 10-30 m/s 5-20 m/s 1-2 m/s
Range 2-5 km 10-30 km Unlimited 1-3 km
Payload 1-10 kg 0.5-2 kg 50+ kg 1-5 kg
Terrain Limited Excellent Road-only Moderate
Cost $2K-20K $1K-10K Existing $0 (labor)
Control Autonomous Autonomous/Pilot Driver Volunteer
Best Use Warehouses, factories Agriculture, disaster Urban sensing Participatory

431.5.2 Energy Budget Allocation

Mobile collectors must budget energy between:

  1. Movement (typically 70-80%):
    • Ground robots: 5-20W locomotion
    • UAVs: 100-500W flight
    • Vehicles: N/A (fuel-powered)
  2. Communication (10-20%):
    • Collecting data from sensors
    • Uploading to base station
    • Coordination with other MULEs
  3. Computation (5-10%):
    • Path planning
    • Data aggregation
    • Navigation/localization

Example - UAV Data Collection: - Total battery: 5000 mAh @ 22.2V = 111 Wh - Flight power: 300W (22 min flight time) - Communication: 5W during hover - Computation: 10W continuous - Practical mission: 15 min flight + 5 min data collection + reserve

431.6 Summary

This chapter covered mobile sink path planning and multi-MULE coordination:

Key Takeaways:

  1. Path Planning Strategies: TSP tours reduce travel distance 30-40% vs random walks, while adaptive planning handles runtime events like buffer overflows and priority alerts.

  2. Greedy Insertion: When high-priority events occur, insert the urgent node into the current tour at the minimum-cost position to minimize detour.

  3. Multi-MULE Coordination: Choose partitioned zones for simplicity, auction-based for dynamic environments, or opportunistic for existing infrastructure (buses, vehicles).

  4. Energy Budgeting: Mobile collectors spend 70-80% of energy on movement, making path efficiency critical for mission success.

431.7 What’s Next?

Continue with best practices, decision frameworks, and comprehensive knowledge checks for production WSN deployments.

Continue to Production Best Practices ->