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),

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

A node can have three possible states: it can be * unclustered
*(not a follower of any cluster),

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

Cmin(t)=

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, **k****1
**and **k****2
**are chosen constants that determine the shapeof
the exponential graph.

If * l *≥ Cmin

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.