A C-shaped network

Cshaped_network 

We consider the selection of noise-free leaders in a network with 200 randomly distributed nodes in a C-shaped region within a unit square. A pair of nodes communicates with each other if their distance is not greater than 0.1 units. This example was used in Srirangarajan, Tewfik, and Luo ’08 as a benchmark for testing algorithms for the sensor localization problem.

Matlab code

Cshaped_network_publish
% A C-shaped network example for noise-free leader selection problem.

n = 200;
Length = 1;
load position_cshape

% % Otherwise generate random nodes in a C-shaped region
% ind = 1;
% while 1
%     pos_temp = Length*rand(1,2);
%     if pos_temp(1) <= Length/5 || pos_temp(2) >= Length*(4/5) || pos_temp(2) <= Length*(1/5)
%         position(ind,:) = pos_temp; %#ok<SAGROW>
%         ind = ind + 1;
%     end
%     if ind == n+1
%         break;
%     end
% end

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

% 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:10;

% 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 = 2; % for the noise-free leader selection formulation
    [Jlow(i),Jup(i),LSgreed(:,i)] = leaders(L,Nl,kappa,flag);

end

Computational results

Download Matlab code Cshaped_network_example.m to reproduce these figures.

Performance bounds

lower_upper_bounds 

Bounds on the global optimal value of the noise-free leader selection problem ({rm LS2}) for the C-shaped network example.

Selection of leaders

Cshaped_noisefree_k3 

Selection of 3 noise-free leaders using greedy algorithm (i.e., one-leader-at-a-time algorithm followed by the swap procedure).

Cshaped_noisefree_k9 

Selection of 9 noise-free leaders using greedy algorithm.

Greedy algorithm selects leaders that have large degrees and that are geographically far from each other. Similar leader selection strategies have been observed in the random network example.

For the C-shaped network, we note that the noise-free ({rm LS2}) and the noise-corrupted ({rm LS1}) formulations lead to almost identical selection of leaders.