Algorithms for Leader Selection in Stochastically Forced Consensus Networks

We are interested in assigning a pre-specified number of nodes as leaders in order to minimize the mean-square deviation from consensus in stochastically forced networks. This problem arises in several applications including control of vehicular formations and localization in sensor networks. For ne...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on automatic control 2014-07, Vol.59 (7), p.1789-1802
Main Authors: Fu Lin, Fardad, Makan, Jovanovic, Mihailo R.
Format: Article
Language:English
Subjects:
Algorithms
Automatic control
Boolean algebra
Convex functions
Deviation
Greedy algorithms
Heuristic
Laplace equations
Linear programming
Networks
Position (location)
Probability theory
Randomness
Trajectory
Upper bound
Vectors
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We are interested in assigning a pre-specified number of nodes as leaders in order to minimize the mean-square deviation from consensus in stochastically forced networks. This problem arises in several applications including control of vehicular formations and localization in sensor networks. For networks with leaders subject to noise, we show that the Boolean constraints (which indicate whether a node is a leader) are the only source of nonconvexity. By relaxing these constraints to their convex hull we obtain a lower bound on the global optimal value. We also use a simple but efficient greedy algorithm to identify leaders and to compute an upper bound. For networks with leaders that perfectly follow their desired trajectories, we identify an additional source of nonconvexity in the form of a rank constraint. Removal of the rank constraint and relaxation of the Boolean constraints yields a semidefinite program for which we develop a customized algorithm well-suited for large networks. Several examples ranging from regular lattices to random graphs are provided to illustrate the effectiveness of the developed algorithms.
ISSN:0018-9286
1558-2523
DOI:10.1109/TAC.2014.2314223