Characterization of linear network coding for pollution detection

摘要

While linear network coding can improve the throughput significantly in network environment with little additional computational overhead, it is fragile to communication errors and node compromising attacks. To combat the errors in network coding, both error-detection and error-correction based schemes have been proposed. In this paper, we provide a novel methodology to characterize linear network coding through error-control coding. Our main idea is to represent each linear network coding with an error-control coding. We provide comprehensive theoretical analysis on the relationships between linear network coding and error-control coding in both unicast and multicast scenarios. We find that these two codes are essentially identical in algebraic aspects. Our research provides a new approach to understand network coding schemes and also a novel methodology to develop network coding schemes that can combat communication errors and also node compromising attacks.