Algo3.cpp

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

struct Node {
    int x;
    int y;
    double residualEnergy;
};

struct Cluster {
    vector<Node> nodes;
    int size;
    int BS_x;
    int BS_y;
};


double calculateDistance(const Node& p1, const Node& p2) {
    return sqrt(pow(p1.x - p2.x, 2) + pow(p1.y - p2.y, 2));
}


double calculateClusteringFactor(double distanceMean, double distanceVariance) {
    return 1 / (distanceMean + 0.5 * distanceVariance);
}


vector<vector<Node>> clusterSetup(const vector<Node>& objects, int k) {
    vector<vector<Node>> clusters;
    for (const auto& obj : objects) {
        clusters.push_back({obj}); 
    }
    
    int kPrime = clusters.size();
    
    while (kPrime > k) {
        double maxClusteringFactor = -1;
        pair<int, int> mergeIndices;
        
        for (int i = 0; i < kPrime; ++i) {
            for (int j = i+1; j < kPrime; ++j) {
                if (i != j) {
                    vector<double> distanceSet;
                    for (const auto& p1 : clusters[i]) {
                        for (const auto& p2 : clusters[j]) {
                            distanceSet.push_back(calculateDistance(p1, p2));
                        }
                    }

                    double distanceMean = 0;
                    for(int i=0; i<distanceSet.size(); i++){
                        distanceMean = distanceMean + distanceSet[i];
                    }
                    distanceMean = distanceMean / distanceSet.size();

                    double distanceVariance = 0;
                    for (const auto& distance : distanceSet) {
                        distanceVariance += pow(distance - distanceMean, 2);
                    }
                    distanceVariance /= distanceSet.size();

                    double clusteringFactor = calculateClusteringFactor(distanceMean, distanceVariance);
                    
                    if (clusteringFactor > maxClusteringFactor) {
                        maxClusteringFactor = clusteringFactor;
                        mergeIndices = {i, j};
                    }
                }
            }
        }
        
        if (maxClusteringFactor > -1) {
            clusters[mergeIndices.first].insert(clusters[mergeIndices.first].begin(), clusters[mergeIndices.second].begin(), clusters[mergeIndices.second].end());
            clusters.erase(clusters.begin() + mergeIndices.second);
            kPrime--;
        }
    }
    
    return clusters;
}


double calculateGCH(const Node& node, const Node& clusterCenter, const Node& baseStation, double alpha, double beta) {
    double distanceToCenter = calculateDistance(node, clusterCenter);
    double distanceToBS = calculateDistance(node, baseStation);
    double GH = (node.residualEnergy) / (alpha * distanceToCenter + beta * distanceToBS);
    return GH;
}


Node electClusterHead(const vector<Node>& nodes, const Node& baseStation, double alpha, double beta) {
    Node clusterCenter = {0, 0, 0};
    int numNodes = nodes.size();
    
   
    for (const auto& node : nodes) {
        clusterCenter.x += node.x;
        clusterCenter.y += node.y;
    }
    clusterCenter.x /= numNodes;
    clusterCenter.y /= numNodes;
    
    double maxGCH = -1;
    Node selectedCH;
    
   
    for (const auto& node : nodes) {
        double gch = calculateGCH(node, clusterCenter, baseStation, alpha, beta);
        if (gch > maxGCH) {
            maxGCH = gch;
            selectedCH = node;
        }
    }
     return selectedCH;
}

/////////////////////////////////////////////////////////////////////////////

bool isLargeCluster(int numNodes, int k,double A, double Eelec, double EDA,int n) {
   double avgEnergyConsumption = (numNodes / k - 1) * Eelec + (numNodes / k) * EDA + Eelec + A * Eelec;
    return numNodes > 1.5 *(n/k) + 0.5 * (A / (Eelec + EDA));
}

Node selectPCH(const vector<Node>& nodes, const Node& clusterCenter, const Node& baseStation, double alpha, double beta) {
   
    Node PCH;
    double maxObjective = -1;
    for (const auto& node : nodes) {
        double objective = calculateGCH(node,clusterCenter, baseStation, alpha, beta);
        if (objective > maxObjective) {
            maxObjective = objective;
            PCH = node;
        }
    }
    return PCH;
}

Node selectSCH(const vector<Node>& nodes, const Node& clusterCenter, const Node& baseStation, double alpha, double beta, Node& PCH) {
 
    Node SCH;
    double maxObjective = -1;
    for (const auto& node : nodes) {
        if (node.x == PCH.x && node.y == PCH.y) continue; 
        double objective = calculateGCH(node,clusterCenter,baseStation,alpha, beta);
        if (objective > maxObjective) {
            maxObjective = objective;
            SCH = node;
        }
    }
    return SCH;
}

int main() {
    // Example usage:
    vector<Node> objects = {{1, 20, 100}, {13, 4, 200}, {5, 9, 150}, {7, 8, 100}, {19, 10, 170}, {1, 2, 500}, {3, 4, 600}, {5, 6, 700},
                                    {11, 22, 550}, {13, 14, 250}, {15, 6, 350}};

    // Define optimal number of clusters 
    int k = 2;

    vector<vector<Node>> result = clusterSetup(objects, k);

    Node baseStation = {30, 22, 0}; // Example base station location
    double alpha = 0.5; // Example alpha value
    double beta = 0.5; // Example beta value
    double A = 1.0; 
    double Eelec = 2.0; 
    double EDA = 3.0; 
    int n = objects.size();
 
    // Print clusters
    for (const auto& cluster : result) {
        cout << "Cluster:";
        for (const auto& Node : cluster) {
            cout << " (" << Node.x << ", " << Node.y << ")";
        }
        cout << endl;

    Node clusterCenter = {0, 0, 0}; // Initialize cluster center
    int numberNodes = cluster.size();
    
    // Calculate cluster center position
    for (const auto& node : cluster) {
        clusterCenter.x += node.x;
        clusterCenter.y += node.y;
    }
    clusterCenter.x /= numberNodes;
    clusterCenter.y /= numberNodes;
    
    double maxGCH = -1;

        // check if large
        if (isLargeCluster(cluster.size(), k, A, Eelec, EDA,n)) {
        
        double alpha = 0.5, beta = 0.5;
        Node PCH = selectPCH(cluster ,clusterCenter,baseStation, alpha, beta);
        Node SCH = selectSCH(cluster,clusterCenter,baseStation, alpha, beta, PCH);
        
        // Print results
        cout << "P-CH: (" << PCH.x << ", " << PCH.y << ")" << endl;
        cout << "S-CH: (" << SCH.x << ", " << SCH.y << ")" << endl;
    }

    else {
    // Print clusters

        Node ch = electClusterHead(cluster, baseStation, alpha, beta);
        cout << "Cluster Head: (" << ch.x << ", " << ch.y << ")" << endl;
    }
    }
    return 0;
}