Distributed Average Consensus and Connected Dominating Sets

This paper presents a design and a performance study of distributed average consensus (DAC) mechanisms based upon a connected dominating set (CDS) agent hierarchy. The CDS-based DAC agents are elected in a distributed manner and act as communication and processing proxies to support attached leaf nodes/agents. A basic CDS-based DAC proxy algorithm is presented which can be adapted for use with a variety of consensus approaches in a straightforward manner. We simulate its relative performance against full peer agent operation in terms of both temporal convergence statistics and network overhead estimates. Since network topology and density characteristics play a direct role in communication requirements and temporal convergence behavior, we study the performance of proxy agent consensus across a series of networks with varying density and resiliency characteristics. We also further discuss tradeoffs and issues related to applied use of these design approaches. Overall, we demonstrate that CDS-enhanced proxy performance, as compared to full agent DAC operation, improves convergence delay across many random geometric graph class cases. In addition, we supplement our simulation results with a working implementation in emulation demonstrating additional performance gains when the network is capacity constrained, largely due to the significant smaller set of node connections and network messages involved in the distributed convergence process.