KHOPCA clustering algorithm

A KHOPCA transition for the given start configuration until termination.

KHOPCA is a clustering algorithm designed for dynamic networks. KHOPCA provides a fully distributed and localized approach to group elements such as nodes in a network according to their distance to each other. KHOPCA (${\textstyle k}$-hop clustering algorithm) operates proactively through a simple set of rules that defines clusters, which are optimal with respect to the applied distance function.

KHOPCA's clustering process explicitly supports joining and leaving of nodes, which makes KHOPCA suitable for highly dynamic networks. However, it has been demonstrated that KHOPCA performs equally in static networks.

Besides applications in ad hoc and wireless sensor networks, applications of KHOPCA can be found in localization and navigation problems, networked swarming, and real-time data clustering.

Set of rules

KHOPCA (k-hop clustering algorithm) operates proactively through a simple set of rules that defines clusters with variable k-hops. A set of local rules describe the state transition between nodes. A node's weight is determined only depending on the current state of its neighbors in communication range. Each node of the network is continuously involved in this process. As result k-hop clusters are formed and maintaned in static as well as dynamic networks.

KHOPCA does not require any predetermined initial configuration. Therefore, a node can potentially choose any weight (between ${\textstyle MIN}$ and ${\textstyle MAX}$) at any time. However, the choice of the initial configuration does influence the convergence time.

Initialization

The prerequisites in the start configuration for the application of the rules are the following.

• $\mathrm {N}$ is the network with nodes and links, whereby each node has a weight $w$.
• Each node ${\textstyle n}$ in $\mathrm {N}$ node stores the same positive values ${\textstyle MIN}$ and ${\textstyle MAX}$, with ${\textstyle MIN<MAX}$.
• A node ${\textstyle n}$ with weight ${\textstyle w_{n}=MAX}$ is called cluster center.
• ${\textstyle k}$ is ${\textstyle MAX}$ - ${\textstyle MIN}$ and represents the maximum size from the most outer node to the cluster center a cluster can have (cluster diameter is ${\textstyle k\cdot 2-1}$).
• $\mathrm {N} (n)$ returns the direct neighbors of node ${\textstyle n}$.
• $W$ is the set of weights with ${\textstyle W(\mathrm {N} )}$ is the the set of weights of all nodes of $\mathrm {N}$.

The following rules describe the state transition for a node ${\textstyle n}$ with weight ${\textstyle w_{n}}$. These rules have to be executed on each node in the here described order.

Rule 1

The first rule describes the construction of a order by a node n assuming the highest neighbor weight ${\textstyle max(W(\mathrm {N} (v)))}$ subtracted by 1. This measure creates a top-to-down hierarchical cluster structure.

if max(W(N(n))) > w_n
    w_n = max(W(N(n))) - 1

File:KHOPCA Rule 1.png

Rule 2

The second rule deals with the situation where isolated nodes are clusterhead-less on the minimum weight level. In that case a node declares itself as clusterhead

if max(W(N(n)) == MIN & w_n == MIN then
    w_n = MAX;

Illustration of Rule 2

Illustration of Rule 2

Rule 3

The third rule covers situations where higher weight nodes that are not clusterhead attract surrounding nodes with less weight. In order to avoid a fragmented cluster, this node successively decreases its weight, finally connecting to an existent cluster. 

if max(W(N(n))) <= w_n && w_n != MAX
    w_n = w_n - 1;

 

Rule 4

The fourth rule describes the situation where two clusterhead meet in 1-hop neighborhood. In accordance of a criterion one clusterhead survives while the other clusterhead dies. In case of rule 4, for deciding which node continues as clusterhead, a unique ID can be used in order to resolve this conflict.

if max(W(N(n)) == MAX && w_n == MAX
    if let ID decide
        w_n = w_n - 1;

Examples

1-D

An exemplary sequence of state transitions applying the described four rules is illustrated below.

Guarantees

It has been demonstrated that KHOPCA terminates after a finite number of state transitions in static networks.