The HEED (Hybrid Energy Efficient Distributed) clustering algorithm can be divided into three major steps: 1) Tentative cluster head distribution, 2) Iterative CH election and balancing, and 3) Finalization and membership establishment. The algorithm is entirely distributed. All information must be transmitted between nodes, or known locally.
In the first step, each node decides whether or not to become a tentative cluster head based on a weighted probability of some ClusterHeadProbability*(Residual Energy/Max Energy). Essentially, each node has a fixed probability of becoming a cluster head,weighted by a dynamic measurement of the node’s current residual energy. When a node elects to become a tentative cluster head, it broadcasts that information to all nodes within communication range.
In the second step, each node goes through an iterative process of deciding whether or not to become a final cluster head based on the cost of the nodes within its communication range and its own cluster head probability. Each node doubles its probability of becoming a cluster head after each successive iteration in which no decision is made. If a node determines it is the optimal cluster head, it will elect to become a tentative cluster head.Once a node’s probability of becoming a cluster head has reached 1, it will assert itself as a final cluster head. Each node that is not ‘covered’ will repeat this process. A node becomes ‘covered’ when it is within communication range of either a final or tentative cluster head. Any time a node changes state during this phase, the node broadcasts the state change to all neighbors within communication range.
During the final phase of HEED clustering, each node decides to join the least cost cluster head. HEED uses one of two cost functions for determining cluster head membership, least degree and most degree. The goal of least degree is to balance load across all clusters. The goal of most degree is to provide dense clusters.