Hypothesis Testing In Multi-Hop Networks.
Sadaf Salehkalaibar, Michèle Wigger, Ligong Wang · 2017
Coding and testing schemes for binary hypothesis testing over three kinds of multi-hop networks are presented and their achievable type-II error exponents as functions of the available communication rates are characterized. The schemes are based on cascade source coding techniques and \emph{unanimous-decision forwarding}, where terminals decide only on the null hypothesis if all previous terminals have decided on this hypothesis, and where they forward their decision to the next hop. The achieved exponent-rate region is analyzed by extending Han's approach to account for the unanimous-decision forwarding strategy and for the more complicated code constructions. The proposed coding and testing schemes are shown to attain the optimal type-II error exponent region for various instances of testing against independence on the single-relay multi-hop network, one instance of the $K$-relay multi-hop network, and one instance of a network with two parallel multi-hop networks that share a common receiver. For the basic single-relay multi-hop network, the proposed scheme is further improved by means of binning. This improved scheme is again analyzed by extending Han's approach, and is shown to be optimal when testing against conditional independence under some Markov condition. For completeness, the paper also presents the previously missing analysis of the Shimokawa, Han and Amari binning scheme for the point-to-point hypothesis testing setup.