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
    w_n = MAX;

Illustration of Rule 2

Illustration of Rule 2

Rule 3

The third rule describes situations where nodes with leveraged weight values, which are not cluster centers, attract surrounding nodes with lower weights. This behavior can lead to fragmented clusters without a cluster center. In order to avoid fragmented clusters, the node with higher weight value is supposed to successively decreasing its own weight with the objective to correct the fragmentation by allowing the other nodes to reconfigure acccording the rules. 

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

 

Rule 4

The fourth rule resolves the situation where two cluster centers connect in 1-hop neighborhood and need to decide which cluster center should continue its role as cluster center. In accordance of a certain criterion one cluster center remains while the other clusterhead hierarchized in 1-hop neighborhood to that new cluster center. The choise of the criterion is depending on the application scenario and on the information available. In case of networks, one can assume that each node carries beside the weight also an unique ID number, which an be used in order to resolve the conflict.

if max(W(N(n)) == MAX && w_n == MAX
    w_n = randomly choose a node from set (max(W(N(n)),w_n);
    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.