TY - JOUR

T1 - Finite-Time Distributed Flow Balancing

AU - Hadjicostis, Christoforos N.

AU - Dominguez-Garcia, Alejandro D.

AU - Rikos, Apostolos I.

N1 - Funding Information:
The work of C. N. Hadjicostis was supported in part by the European Commission's Horizon 2020 research and innovation programme under Grant 739551 (KIOS CoE).
Publisher Copyright:
© 1963-2012 IEEE.

PY - 2022/12/1

Y1 - 2022/12/1

N2 - We consider a flow network that is described by a digraph, each edge of which can admit a flow within a certain interval, with nonnegative end points that correspond to lower and upper flow limits. We propose and analyze a distributed iterative algorithm for solving, in finite time, the so-called feasible circulation problem, which consists of computing flows that are admissible (i.e., within the given intervals at each edge) and balanced (i.e., the total in-flow equals the total out-flow at each node). The algorithm assumes a communication topology that allows bidirectional message exchanges between pairs of nodes that are physically connected (i.e., nodes that share a directed edge in the physical topology) and is shown to converge to a feasible and balanced solution as long as the necessary and sufficient circulation conditions are satisfied with strict inequality. In case, the initial flows and flow limits are commensurable (i.e., they are integer multiples of a given constant), then the proposed algorithm reduces to a previously proposed finite-time balancing algorithm, for which we provide an explicit bound on the number of steps required for termination.

AB - We consider a flow network that is described by a digraph, each edge of which can admit a flow within a certain interval, with nonnegative end points that correspond to lower and upper flow limits. We propose and analyze a distributed iterative algorithm for solving, in finite time, the so-called feasible circulation problem, which consists of computing flows that are admissible (i.e., within the given intervals at each edge) and balanced (i.e., the total in-flow equals the total out-flow at each node). The algorithm assumes a communication topology that allows bidirectional message exchanges between pairs of nodes that are physically connected (i.e., nodes that share a directed edge in the physical topology) and is shown to converge to a feasible and balanced solution as long as the necessary and sufficient circulation conditions are satisfied with strict inequality. In case, the initial flows and flow limits are commensurable (i.e., they are integer multiples of a given constant), then the proposed algorithm reduces to a previously proposed finite-time balancing algorithm, for which we provide an explicit bound on the number of steps required for termination.

KW - Balancing

KW - distributed algorithms

KW - distributed balancing

KW - feasible circulation

KW - finite-time

KW - flow networks

UR - http://www.scopus.com/inward/record.url?scp=85122055578&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85122055578&partnerID=8YFLogxK

U2 - 10.1109/TAC.2021.3137150

DO - 10.1109/TAC.2021.3137150

M3 - Article

AN - SCOPUS:85122055578

SN - 0018-9286

VL - 67

SP - 6926

EP - 6933

JO - IEEE Transactions on Automatic Control

JF - IEEE Transactions on Automatic Control

IS - 12

ER -