Leader selection
Home
Problem formulation
Paper
Talk
Download
Feedback
Examples
Random network
2D lattice
C-shaped network

A random network

random_network 

We consider the selection of noise-corrupted leaders in a network with 100 randomly distributed nodes in a unit square. A pair of nodes communicate with each other if their distance is not greater than 0.2 units. This scenario may arise in sensor networks with prescribed omnidirectional (i.e., disk shape) sensing range.

Matlab code

random_network_publish
% Generate 100 nodes randomly distributed in a square of Length x Length units
n = 100;

% load the position data
load position.mat
Length = 1;

% Or generate a new set of position data
% position = Length*rand(n,2);

% radius that determines the neighbors of nodes
r = Length/5;

% draw neighbors and compute the incidence matrix of neighboring nodes
[Eg,idx] = neighbors(n,position,r);

% form the graph Laplacian
L = Eg*Eg';

% kappa is taken as the diagonal of L
kappa = diag(L);

% Start solving the leader selection problem

kval = 1:1:40;

% pre-allocate memory for data collection
Jlow = zeros(size(kval));
Jup = zeros(size(kval));
LSgreed = zeros(n,length(kval));

for i = 1:length(kval)

    Nl = kval(i);    
    flag = 1; % for noise-corrupted leader selection formulation
    [Jlow(i),Jup(i),LSgreed(:,i)] = leaders(L,Nl,kappa,flag);

end

Computational results

Download Matlab code random_network_example.m to reproduce these figures.

Performance bounds

lower_upper_bounds 

Bounds on the global optimal value of the noise-corrupted leader selection problem ({rm LS1}) for the random network example.

Greedy algorithm vs. degree heuristics

degree_greedy 

Greedy algorithm (i.e., one-leader-at-a-time algorithm followed by the swap procedure) significantly outperforms degree heuristics (that selects leaders with the largest number of neighbors) for the random network example. To gain some insight into the selection of leaders, we compare results obtained using the greedy algorithm with degree heuristics.

degree_k5 

Selection of 5 noise-corrupted leaders using degree heuristics.

The selected leaders based on degree heuristics turn out to be in the proximity of each other.

The mean-square deviation from consensus with this set of leaders is J = 27.8.

noise_corrupted_k5 

Selection of 5 noise-corrupted leaders using greedy algorithm.

The greedy algorithm selects leaders that, in addition to having large degrees, are far from each other. As a result, the selected leaders can influence more followers and thus more effectively improve performance of the network.

The mean-square deviation from consensus with this set of leaders is J = 19.0.

degree_k5 

Selection of 40 noise-corrupted leaders using degree heuristics.

The mean-square deviation from consensus with this set of leaders is J = 15.0.

noise_corrupted_k40 

Selection of 40 noise-corrupted leaders using greedy algorithm.

The leader sets obtained using the greedy algorithm and degree heuristics are almost complements of each other. While the degree heuristics clusters the leaders around the center of the network, the greedy algorithm distributes the leaders around the boundary of the network.

The mean-square deviation from consensus with this set of leaders is J = 9.5.