Error Probability Bounds for M-ary Relay Trees

Zhenliang Zhang, Edwin K. P. Chong, Ali Pezeshki, William Moran, Howard Caygill

TL;DR

This paper analyzes the performance of distributed detection systems organized as M-ary relay trees. The authors derive tight bounds on error probabilities, revealing that the "majority dominance" rule is optimal for odd M but sub-optimal for even M, impacting how quickly decisions become accurate as more sensors are added.

What Problem Does This Paper Address?

Imagine a network of sensors trying to detect a phenomenon (e.g., a target presence). These sensors don't all report directly to a central "fusion center." Instead, they form a tree structure. Leaf nodes are the sensors, and internal nodes are "relay nodes" that combine information from their children before passing it up the tree. The goal is for the fusion center at the root to make an accurate decision.

Previous work has looked at simpler architectures like parallel sensor networks (all report to the center) or tandem networks (a chain). Tree structures offer a middle ground, balancing communication load and decision accuracy. However, understanding the error performance of these M-ary (meaning each relay node combines M messages) trees, especially with different fusion rules, remained an open question. This paper specifically investigates the "majority dominance" rule, where a node decides based on whether more than half of its inputs are '1' or '0'. They aim to understand how the error probability at the fusion center behaves as the number of sensors (N) grows, and how this behavior differs based on whether M is odd or even.

Methods

The core of the paper involves deriving recursive formulas for Type I (false alarm) and Type II (missed detection) error probabilities. They start by analyzing how these probabilities change as information is fused at each relay node. For the majority dominance rule, they derive functions (denoted f(a) and g(a)) that describe the new error probabilities after fusion.

A key technique is analyzing the ratio of error probabilities between successive levels of the tree. This allows them to establish upper and lower bounds on how much the error probability shrinks at each step. By applying these bounds recursively up the tree to the fusion center, they derive explicit bounds for the overall Type I and Type II error probabilities as functions of the number of sensors (N). They then extend this to derive bounds for the total error probability. The analysis is split into two cases: when M (the number of children per node) is odd and when it is even, as the majority dominance rule behaves differently in these scenarios.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Majority Dominance is M-Dependent: The "majority dominance" rule, a simple and intuitive way to combine binary decisions, is surprisingly sensitive to whether M is odd or even.
  • Optimality for Odd M: When M is odd, the majority dominance rule is essentially optimal. It allows the error probability to decay as fast as theoretically possible for this type of tree structure.
  • Sub-Optimality for Even M: When M is even, the majority dominance rule is sub-optimal. The error probability decays slower than it could, leaving a gap between the best possible performance and what this rule achieves. This is particularly evident for M=2 (binary trees), where the error probability doesn't even improve after fusion with this rule.
  • Explicit Bounds: The paper provides concrete mathematical bounds for error probabilities, not just asymptotic behavior. This allows for a precise understanding of performance for any given number of sensors.
  • Decay Rate Characterization: The bounds reveal that error probabilities decay sub-exponentially, meaning they get smaller but not as quickly as in simpler parallel architectures. The rate of decay is characterized by terms involving N and M.

Key Results

  • Tight Upper and Lower Bounds: The paper derives explicit upper and lower bounds for Type I and Type II error probabilities at the fusion center, expressed as functions of the number of sensors (N) and the branching factor (M).
  • Odd M: For odd M, the error probability decay exponent is shown to be approximately $N \log_M \left(\frac{M+1}{2}\right)$. This is considered near-optimal.
  • Even M: For even M, the decay exponent is also approximately $N \log_M \left(\frac{M+1}{2}\right)$, but the analysis shows a gap between the upper and lower bounds, indicating sub-optimality of the majority dominance rule. For M=2, the error probability doesn't improve with fusion.
  • Total Error Probability: Bounds for the total error probability are also derived, showing a similar sub-exponential decay.

Limitations and Future Work

  • Focus on Majority Dominance: The analysis is primarily focused on the majority dominance rule. The paper acknowledges that other fusion rules exist and might perform differently, especially for even M.
  • Balanced Trees: The analysis assumes balanced M-ary relay trees. The behavior of unbalanced trees or more general network topologies is not discussed.
  • Sensor/Link Failures: While the paper mentions prior work on sensor and link failures, this specific study assumes perfect sensors and communication links. Extending the analysis to include these failure modes for M-ary trees would be a natural next step.
  • Generalization: The paper raises questions about how failure affects detection performance in M-ary relay trees and what can be said about unbalanced trees or more complex graph topologies. These are identified as interesting avenues for future research.

Summary updated

Abstract

We study the detection error probabilities associated with an M-ary relay tree, where the leaves of the tree correspond to identical and independent sensors. Only these leaves are sensors. The root of the tree represents a fusion center that makes the overall detection decision. Each of the other nodes in the tree is a relay node that combines M summarized messages from its immediate child nodes to form a single output message using the majority dominance rule. We derive tight upper and lower bounds for the Type I and II error probabilities at the fusion center as explicit functions of the number of sensors in the case of binary message alphabets. These bounds characterize how fast the error probabilities converge to 0 with respect to the number of sensors.
BibTeX
@misc{zhang2012error,
  author = {Zhenliang Zhang and Edwin K. P. Chong and Ali Pezeshki and William Moran and Howard Caygill},
  title = {{Error Probability Bounds for M-ary Relay Trees}},
  year = {2012},
  eprint = {1202.1354},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1202.1354},
}
Figure