Integer weight balancing in directed graphs in the presence of communication delays

Abstract

A digraph with positive weights on its edges is weight-balanced if, for each node, the sum of the weights of the incoming edges equals the sum of the weights of the outgoing edges. Weight-balanced digraphs play an important role in a variety of cooperative control problems and, in this work, we propose an iterative distributed algorithm which solves the integer weight balancing problem in a given strongly connected digraph, in the presence of arbitrary (time-varying, inhomogeneous, but) bounded time delays that might affect communication transmissions. The algorithm is shown to converge after a finite number of iterations that we explicitly bound. Furthermore, we prove that the resulting weight balanced digraph is unique regardless of the specific delays that links suffer during the execution of the algorithm. © 2015 IEEE.