Quality of Information Maximization for Wireless Networks via a Fully Separable Quadratic Policy

An information collection problem in a wireless network with random events is considered. Wireless devices report on each event using one of multiple reporting formats. Each format has a different quality and uses different data lengths. Delivering all data in the highest quality format can overload system resources. The goal is to make intelligent format selection and routing decisions to maximize time-averaged information quality subject to network stability. Lyapunov optimization theory can be used to solve such a problem by repeatedly minimizing the linear terms of a quadratic drift-plus-penalty expression. To reduce delays, this paper proposes a novel extension of this technique that preserves the quadratic nature of the drift minimization while maintaining a fully separable structure. In addition, to avoid high queuing delay, paths are restricted to at most two hops. The resulting algorithm can push average information quality arbitrarily close to optimum, with a trade-off in queue backlog. The algorithm compares favorably to the basic drift-plus-penalty scheme in terms of backlog and delay. Furthermore, the technique is generalized to solve linear programs and yields smoother results than the standard drift-plus-penalty scheme.