Dynamic Sensor Scheduling Based on Node Partitioning of Graphs

1. Problem Statement

The paper addresses the challenge of dynamic sensor scheduling in sensor networks. In many applications (e.g., traffic or infrastructure monitoring), sensors suffer from battery depletion and failure if they are activated continuously. To mitigate this, sensors are grouped into disjoint subsets and activated sequentially (sensor scheduling).

The core problem is to partition the set of $N$ sensor nodes into $M$ disjoint subsets such that two critical requirements are met simultaneously:

1. Accurate Reconstruction: Each subset must be capable of accurately reconstructing the entire global signal from its local measurements.
2. Load Balancing: The sensing load must be distributed evenly across all sensors over time to prevent concentrated energy consumption.

Limitations of Existing Methods:

• Sampling Set Selection: Typically selects only one optimal subset, failing to address load balancing.
• Node Clustering: Groups nodes by similarity (e.g., community detection), but nodes in the same cluster often have redundant measurements, making it difficult to reconstruct signals from other clusters.
• Existing Partitioning Methods (SRel, SFrob): Often rely on heuristic ranking or restrictive assumptions (e.g., exact bandlimitedness) and are designed for static scenarios, failing to adapt when signal statistics change over time.

2. Methodology

The proposed approach reformulates graph node partitioning as a multiple sampling subset selection problem based on Graph Signal Processing (GSP) and Sampling Theory under a Subspace Prior.

A. Static Graph Node Partitioning

The authors assume the signal lies in a known subspace $\mathcal{A}$ (generated by a matrix $A$). The goal is to find disjoint subsets $M_1, \dots, M_M$ that minimize the average reconstruction error across all subsets.

1. Objective Function:
   The problem is initially formulated to minimize the trace of the inverse of the sampling operator's Gram matrix for all subsets:
   $$\min_{M_k} \sum_{k} \text{tr}((S_k^\top A A^\top S_k)^{-1})$$
   where $S_k$ is the sampling operator for subset $k$.

2. Approximation and Relaxation:

   • Since the inverse calculation is computationally expensive and the problem is NP-hard, the authors approximate the inverse using a second-order Neumann series.
   • The binary selection vector is relaxed to a continuous variable $m \in [0, 1]^N$.
   • The constraint that subsets are disjoint and of equal size is handled via a Difference-of-Convex (DC) formulation. The objective function becomes the difference of two convex functions.

3. Solver:
   The relaxed problem is solved using the Proximal DC Algorithm (PDCA). This algorithm guarantees convergence to a critical point. The final continuous solution is binarized via thresholding to obtain the discrete node subsets.

B. Online Sensor Scheduling

To handle time-varying signal statistics (dynamic scenarios), the method is extended to an online setting:

1. Sequential Partitioning: The graph is partitioned into $M$ subsets based on the current signal subspace. Sensors in these subsets are activated sequentially over $M$ time steps.
2. Signal Reconstruction: At each time step, the full signal is reconstructed using the current subspace and the measurements from the active subset.

C. Online Dictionary Learning (Subspace Tracking)

Since the true signal subspace is often unknown and time-varying, the authors propose a weighted dictionary learning scheme to estimate the subspace $\{A_t\}$ from historical reconstructed signals.

• Confidence Matrix: A key innovation is the introduction of a confidence matrix $W_t$. This matrix weights the data fidelity term based on the sampling history. Measurements from sampled nodes are given high confidence, while reconstructed values for unsampled nodes (which may contain errors) are down-weighted.
• Optimization: The subspace $A_t$ and expansion coefficients $D_t$ are updated alternately. The confidence weighting prevents error propagation from inaccurate reconstructions, allowing stable learning without needing a pre-trained initial subspace (cold-start capability).

3. Key Contributions

1. Novel Formulation: The first formulation of graph node partitioning as a DC optimization problem aimed at minimizing the average reconstruction error across multiple disjoint subsets, rather than just selecting a single optimal subset.
2. Theoretical Guarantees: Unlike heuristic methods, the proposed PDCA-based solver provides theoretical convergence guarantees to a critical point.
3. Relaxed Assumptions: The method utilizes a generalized subspace prior, removing the strict "bandlimited" assumption required by previous methods (like SFrob), making it applicable to full-band signals.
4. Robust Online Adaptation: The introduction of a confidence-weighted dictionary learning mechanism allows the system to adapt to time-varying signal subspaces in real-time without relying on pre-training or assuming smooth temporal changes.
5. Superior Performance: Demonstrated ability to balance load while maintaining high reconstruction accuracy in both synthetic and real-world scenarios.

4. Experimental Results

The authors validated the method using synthetic data and real-world global sea surface temperature data.

• Static Partitioning (Synthetic Data):

  • Compared against SRel (topology-based) and SFrob (bandlimited-based).
  • Result: The proposed method achieved 2–5 dB lower Mean Squared Error (MSE) than existing methods. It successfully reconstructed signals even when existing methods failed in specific local regions due to poor node selection.

• Online Partitioning (Synthetic Data):

  • Compared against static partitioning with static/dynamic subspaces.
  • Result: The proposed method significantly outperformed static partitioning. It successfully tracked time-varying signal subspaces, maintaining low MSE, whereas static methods suffered from rapidly increasing errors as the signal changed.

• Real-World Data (Sea Surface Temperature):

  • Applied to a graph of 256 sensors across global oceans.
  • Result: The proposed method achieved the lowest average MSE (-16.52 dB) compared to SRel (-12.32 dB) and SFrob (-11.85 dB).
  • Ablation Study: Confirmed that the confidence matrix (Configuration 1) is crucial. Learning from reconstructed signals with confidence weighting outperformed learning from raw noisy measurements or unweighted reconstructed signals.

5. Significance

This paper provides a robust theoretical and practical framework for dynamic sensor scheduling. By moving beyond static selection and heuristic clustering, it offers a mathematically grounded solution that ensures:

• Robustness: Sensors are not overused, extending network lifespan.
• Adaptability: The system automatically adjusts to changing environmental conditions (signal statistics) without manual reconfiguration.
• Accuracy: It maintains high-fidelity signal reconstruction even with sparse, sequential sampling.

The integration of DC optimization for partitioning and confidence-weighted dictionary learning for subspace tracking represents a significant advancement in Graph Signal Processing, particularly for resource-constrained, dynamic sensor network applications.