Effects of Graph Topology on Performance of Distributed Algorithms for Networked Control and Sensing

We consider distributed collaborative control andsensing as they frequently arise in networked control systems.The algorithms are constrained to use local information. Weshow by experiments that the performance of such distributed,local information based algorithms, can depend dramaticallyon the structure of the underlying topology (connectivitypattern) of the agents. We investigate the speed of convergence,accuracy, robustness and resiliency of such algorithms includingconsensus problems. We consider several graphs that can beused to represent collaborative control and communicationpatterns. We first show that small world topologies offer severaladvantages from a perspective of a favorable tradeoff betweenperformance of collaborative behaviors vs costs of collaborativebehaviors (or equivalently constraints for collaboration). Second,we show that a two level hierarchy consisting of carefullylocated and controlled ’leaders’ at the higher level and therest of the agents at the lower level, can provide a veryefficient communication pattern with substantial improvementof performance. We close with a description of the possibletopologies for this two tier structure and their performance.