Distributed Flow Network Balancing With Minimal Effort

Abstract

The flow network balancing problem, i.e., the problem of balancing the incoming and outgoing flows for each vertex of a directed graph, has been widely investigated with several distributed solutions being proposed in recent years. Flow balancing is crucial in several application domains, ranging from water and traffic networks to complex network synchronization and distributed adaptive networked control. In this paper, we focus on finding the solution for the flow network balancing problem that is optimal in a minimal effort sense. More specifically, we aim at modifying a given set of (unbalanced) flows so that we obtain a balanced solution. We assume that there is a (possibly heterogenous) cost associated to the unit variation of each flow, as well as lower and upper bounds on the peredge flows. More in detail, we first establish a necessary and sufficient optimality condition for network balancing and then propose a distributed protocol, demonstrating its convergence toward the global optimal solution. Simulation results are provided to corroborate the effectiveness of the proposed distributed algorithm.