Distributed Balancing Under Flow Constraints Over Arbitrary Communication Topologies

• 成果类型: Article
• 署名作者: Hadjicostis, Christoforos N.; Dominguez-Garcia, Alejandro D.
• 署名单位: University of Cyprus; University of Illinois System; University of Illinois Urbana-Champaign
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2020.3036288
• 发表日期: 2021
• 页码: 5637-5650
• 关键词: Network topology; TOPOLOGY; Distributed algorithms; communication networks; optimization; iterative methods; Bidirectional control; Digraph; directed communication topology; distributed balancing; feasible circulation; flow networks

摘要

In this article, we consider a flow network that is described by a digraph, each edge of which can admit a flow within a certain interval, with non-negative end points that correspond to lower and upper flow limits. We propose and analyze a distributed iterative algorithm for solving the so-called feasible circulation problem, which consists of computing flows that are within the given intervals at each edge and balance the total inflow and the total outflow at each node. Unlike previously proposed distributed algorithms that required bidirectional communication between pairs of nodes that share an edge in the flow network, the algorithm we propose can operate over any communication network, assuming the corresponding digraph that describes it is strongly connected. The proposed algorithm allows the nodes to asymptotically compute (with a geometric rate that depends on the specifics of the given flow network and communication topology) a solution to the feasible circulation problem, as long as such a solution exists. An important special case of the setting studied in this article is the case where the digraph of the flow network matches the digraph of the communication network.