Optimal periodic scheduling of sensor networks: A branch and bound approach

A periodic scheduling problem for sensor networks with communication constraints is considered for state estimation. The solvability of the problem is first discussed and a necessary and sufficient condition is presented based on the notion of periodic detectability. Since the calculation of the average prediction error variance requires the computation of the symmetric periodic positive-semidefinite stabilizing (SPPS) solutions to the periodic Riccati equations, a moving approximate cost function is proposed, which gradually converges to the exact cost function. Also, it is shown that the upper bound of the approximation error is independent of the SPPS solutions and converges to zero exponentially. Based on these results, a branch and bound based algorithm is proposed to compute the optimal periodic schedule, and the idea is to iteratively trim the set of schedules that are potentially robust optimal with respect to the approximation error. If the optimal schedule is unique, the algorithm solves the periodic scheduling problem by exploring a finite number of nodes. Moreover, given an arbitrary nonzero suboptimality specification, the algorithm results in a suboptimal schedule set containing all the optimal schedules at a manageable computation effort. A numerical example is presented to illustrate the proposed results.