Sensor selection for hypothesis testing in wireless sensor networks: a Kullback-Leibler based approach

We consider the problem of selecting a subset of p out of n sensors for the purpose of event detection, in a wireless sensor network (WSN). Occurrence of the event of interest is modeled as a binary Gaussian hypothesis test. In this case sensor selection consists of finding, among all (_p ⁿ) combinations, the one maximizing the Kullback-Leibler (KL) distance between the induced p-dimensional distributions under the two hypotheses. An exhaustive search is impractical if n and p are large, as the resulting optimization problem is combinatorial. We propose a suboptimal approach with computational complexity of order O(n³p). This consists of relaxing the 0/1 constraint on the entries of the selection matrices to let the optimization problem search over the set of Stiefel matrices. Although finding the Stiefel matrix is a nonconvex problem, we provide an algorithm that is guaranteed to produce a global optimum for p = 1, through a series of judicious problem reformulations. The case p > 1 is tackled by an incremental, greedy approach. The obtained Stiefel matrix is then used to determine the sensor selection matrix which best approximates its range space. Extensive simulations are used to assess near optimality of the proposed approach. They also show how the proposed approach performs better than exhaustive searches once an upper bound on the computation time is set.