Distributed network utility maximization using event-triggered barrier methods

Many problems associated with networked systems can be formulated as network utility maximization (NUM) problems. Dual decomposition is a widely used distributed algorithm that solves the NUM problem. This approach, however, uses a step size that is inversely proportional to measures of network size such as maximum path length or maximum neighborhood size. As a result, the number of messages exchanged between nodes by dual decomposition scales poorly with respect to these measures. This paper investigates the use of an event-triggered communication scheme in distributed NUM algorithms. Under event triggering, each agent broadcasts to its neighbors when a local “error” signal exceeds a state dependent threshold. In particular, this paper proposes an event-triggered distributed NUM algorithm based on barrier methods. The paper establishes state-dependent event-triggering thresholds under which the proposed algorithm converges to the optimal solution of the NUM problem. Simulation results suggest that the proposed algorithm reduces the number of message exchanges by up to two orders of magnitude, and is scale-free with respect to the above two measures of network size.