Detailed description of ACE
As in real situation, we have considered that nodes are randomly scattered over a wide area (see figure 5.1(a)). In the algorithm we first define the communication distance as the similarity for clustering. The communication distance is the maximum distance at which the centre node referred to as cluster-head can communicate with its member nodes. All nodes that fall within this communication distance with the cluster-head is grouped together
to form a cluster, which is more or less circular in shape with the radius equal to communication distance. Each cluster shall have only one cluster head and a bunch of nodes as followers. Although, one cluster may overlap the other which means a node can be within the communication distance of more than one cluster head, it shall choose only one cluster head and belong to just one cluster. Thus, at the end of the clustering process each node belongs to exactly one cluster.
The distance measure used here is the Euclidian distance. It is evident that a node can have three possible states namely unclustered (not a follower of any cluster), clustered (follower of one or more clusters) and a cluster-head also called as cluster leader; see figure 5.1(b) for details.
During the protocol, nodes respond immediately to communications from other nodes, but will only initiate actions at random intervals. Each time that an action can be initiated for a node is called a node's iteration. The duration of the random time interval between iterations (the iteration interval) is uniformly random distributed.
A node can have three possible states: it can be unclustered (not a follower of any cluster), clustered (a follower of one or more clusters) or it may be a cluster-head. In the beginning of the protocol, all nodes are unclustered. Each node waits for its next iteration before deciding on what action to take on that iteration. When a node's iteration arrives, its available choice of actions depends on what state it is currently in.
As we run the algorithm, if a node A
is found unclustered at the start of the iteration, it will
find out how many nodes it would receive as followers unfailingly if it
volunteers itself as a cluster-head of a new cluster. It will be equal to
number of unclustered neighbors and are referred to as loyal followers in ACE
by Haowen Chan and Adrian Perrig. A loyal follower is a follower of only one
cluster and number of loyal follower is denoted by
l. Node A
knows how long it has been since it started the protocol; call
this time t. It then computes the spawning threshold function
Cmin(t).In the protocol, an unclustered node will spawn a new cluster by
declaring itself a cluster head whenever it finds that it can gain at least
Cmin(t) followers if it were to become a cluster-head. The function Cmin(t) is
called the spawning threshold function and is dependent on the time that has
passed since the protocol was initiated for that node. In general Cmin(t)
should decrease as the algorithm proceeds. This causes fewer clusters to form
near the beginning of the algorithm. Hence an exponentially decreasing
function for Cmin(t) is used.
In this formula, t is the time passed since the protocol began and cI is the duration of the protocol as described earlier, d is the time estimated average degree (number of neighbors) of a node in the network, and is pre-calculated prior to deployment, k1 and k2 are chosen constants that determine the shape of the exponential graph.
In this formula, t is the time passed since the protocol began and cI is the duration of the protocol as described earlier, d is the time estimated average degree (number of neighbors) of a node in the network, and is pre-calculated prior to deployment, k1 and k2 are chosen constants that determine the shapeof the exponential graph.
If l ≥ Cmin(t) ) then A will spawn a new cluster. It does so by generating a random cluster ID and broadcasting a RECRUIT message. A's neighbors will contest for the cluster-head. If there is, then the existing cluster-head will
POLL all its neighbors to find out the best candidate for the new cluster-head.
The best candidate leader for a cluster is the node with the largest potential number of loyal followers in its neighbor set. By counting only loyal followers and not counting nodes that lie on the overlap of two or more clusters, the best candidate node is generally in the direction of least overlap with other clusters. If the best candidate for cluster-head is A itself, then A does nothing. Otherwise, suppose the best candidate is some node B. A will now MIGRATE the cluster onto the new cluster-head B. It does so by issuing a PROMOTE message to B. On receiving the PROMOTE message, B will issue a RECRUIT message with A's cluster ID. This is similar to spawning a new cluster except that an existing cluster ID is used instead of generating a new one. The effect of this is that the neighbors of B that were not in the cluster will now be added to the cluster (with B as the cluster-head), while the existing members of the cluster that are B's neighbors will realize that B is being promoted and thus update B as their new cluster-head.
Once A observes B's RECRUIT message, it will then issue an ABDICATE message to its neighbors. The effect of this will be that common neighbors of A and B will have seen B’s RECRUIT message before and thus ignore the message; neighbors of A, who are not neighbors of B, will leave the cluster. The net effect of this sequence of actions is that leadership passes from A to B and the cluster as a whole migrates from being centered about node A to being centered about B.
If a node is clustered then it does nothing during its iteration. It merely waits a random iteration interval for its next iteration to arrive.
Each node runs the protocol for at least a time cI where c is the desired average number of iterations per node and I is the expected length of the iteration interval. After a node has completed its iteration, if it still has not passed time cI counting from when it started running the protocol, then it will wait another random iteration interval until its next iteration.
After a node has passed time cI since it started running the protocol, it is ready to terminate the protocol. If the node is a cluster-head, it terminates immediately and informs its neighbors that it is done. If the node is a clustered node, it waits until all its cluster-heads have terminated before choosing one at random to become its final cluster-head. After termination, the node will respond with “N/A” to leadership polls from clusters that have migrated into its range to indicate its unwillingness to return to the protocol.