Optimization of wireless networks via graph interpolation

A novel framework for the analysis and optimization of wireless networks is presented. The framework is based on the representation as a multi-dimensional graph of the Finite State Machine determining the temporal evolution of the network´s state. Wireless protocols generate graphs with regular multi-scale connectivity structure. Additionally, cost functions measuring network performance metrics present strong regularity on the multi-dimensional state space of the FSM. The framework proposed herein uses the regularity of the graph and cost functions to achieve accurate recovery of the functions measuring the long-term cost incurred by the network from a small number of state observations. The approach takes inspiration from signal processing techniques where the partially know long-term cost is formulated as a downsampled-upsampled signal on a graph. In the graph domain, a low-pass filtering is applied to generate a smooth approximation of the value function from the known samples. The framework finds applications in distributed optimization and online learning.