Flow Control of Wireless Mesh Networks Using LQR and Factor Graphs

Abstract

Advances in the estimation and more recently the controls communities have leveraged the use of factor graphs to overcome problems of scalability and runtime in dynamical systems. In continuation of that work, we look to use factor graphs to perform LQR control on a wireless mesh network (WMN). Inspired by the communication challenges presented in the DARPA Subterranean Challenge, we look to model a WMN as a dynamical system capable of control. Furthermore, we present WMNLQR, a network flow control algorithm using LQR and factor graphs that is capable of achieving linear runtime growth with respect to both trajectory length and state dimension. To illustrate the real time capabilities of our algorithm, we conduct a thorough analysis of WMNLQR versus four other LQR solvers. We find that even more advanced algorithms utilizing dynamic programming can become intractable for real time centralized control as the state space increasingly grows.

Furthermore, we present a novel decentralized control algorithm, DWMNLQR. This algorithm leverages the physical RF links between communication nodes to assist the message passing process used to solve a factor graph. By exploiting the sparsity of factor graphs, we find that a globally optimum solution can still be achieved despite framing the communication network as a series of connected local subproblems. Specifically, we iteratively compute the LQR solution to each communication node individually, with each node only aware of its local mesh. By eliminating the need to communicate to a centralized control node, DWMNLQR has improved both system robustness and runtime for real world scenarios.