How to form clusters correctly while implementing the work "Energy Centroid Clustering Algorithm"?

I have been implementing the work titled "Energy centroid clustering algorithm to enhance the network lifetime of wireless sensor networks". However, even after following the psuedocodes I am not able to form clusters correctly initially. The Cluster Heads are one below the other rather than being distributed in the sensing region.

The above images are of my implementation. Below is the image as given in the paper.

I have problems in correctly interpreting the Psuedocode-2 given in the paper.

Also, what values of a sensor node's transmission radius are assumed?

What should be the default compression ratio after data aggregation by the Cluster Head, as it is not given in the paper?

Any help would be highly appreciated.

[William Rose]

@Anubhav, I recommend that you email the authors at the addresses givene in the paper.

[William Rose]

@Anubhav,

I agree that the transmission radius is not specified in the paper. We need the tranmission radius to compute the number of clusters with eq.1. The authors specify that there are four clusters. Therefore I would simply assume there are four clusters, and don't worry about how they got that result.

You can estimate the approximate transmission radius from equation 1, given the specified gemoetry and given that there are 4 clusters. The mean value of the maximum sensor-to-sink distance is about 106 m (see simulation below). Therefore, from eq.1, with number of clusters=4, the transmission radius is about 53 m. The number of clusters must be an integer, and the maximum sensor-to-sink distance varies from trial to trial, so the actual transmission radius could be in the range of about 48 to 60 m.

M=50;                                       % number of trials
dMax=zeros(1,M);                            % maximum sensor-to-sink distance on each trial
N=100;                                      % number of sensors
for i=1:M
    X=100*rand(1,N); Y=100*rand(1,N);       % sensor locations (m)
    Xs=50; Ys=100;                          % sink location (m)
    dMax(i)=max(((X-Xs).^2+(Y-Ys).^2).^0.5); % max distance from sensor to sink
end
fprintf('Max.Sensor-Sink Distance (%d trials): min=%.1f, mean=%.1f, max=%.1f.\n',...
    M,min(dMax),mean(dMax),max(dMax))

Max.Sensor-Sink Distance (50 trials): min=99.8, mean=106.1, max=111.1.

Answer 1

[William Rose]

@Anubhav,

I agree that pseudocode 2 is not clear. In particular, it is not obvious how the sensors are to be partitioned into C clusters. The pseudocode seems to me to imply that the initial partition shoudl be based on distance from sensors to sink. But this will result in C radial bands of sensors. This does not seem desireable and it is not what their example (Fig. 6) looks like.

I would do k-means clustering. I would not be suprised if they did the same.

Example:

N=100; % number of sensors
C=4; % number of clusters
sensorXY=100*rand(N,2);    % sensor x,y (m)
[idx,Ccl]=kmeans(sensorXY,C);  % k-means clustering, Ccl=cluster centroid locations

% next: find cluster heads: sensor in each cluster that is closest to the cluster centroid
cHidx=zeros(1,C); % allocate array for indices of cluster heads
for i=1:C
    [~,cHidx(i)]=min((sensorXY(:,1)-Ccl(i,1)).^2+(sensorXY(:,2)-Ccl(i,2)).^2);
end

% plot result
figure
gscatter(sensorXY(:,1),sensorXY(:,2),idx)           % sensors
hold on
scatter(sensorXY(cHidx,1),sensorXY(cHidx,2),75,'k') % cluster heads
voronoi(Ccl(:,1),Ccl(:,2))                          % cluster boundaries
xlabel('X'); ylabel('Y'); title('Sensor Clusters')
legend('1','2','3','4','Head','Centroid',Location='south')

●