![]() | ||
KHOPCA is a clustering algorithm designed for dynamic networks. KHOPCA (
Contents
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 also performs in static networks.
Besides applications in ad hoc and wireless sensor networks, KHOPCA can be used in localization and navigation problems, networked swarming, and real-time data clustering and analysis.
Algorithm description
KHOPCA (
KHOPCA does not require any predetermined initial configuration. Therefore, a node can potentially choose any weight (between
Initialization
The prerequisites in the start configuration for the application of the rules are the following.
The following rules describe the state transition for a node
Rule 1
The first rule has the function of constructing an order within the cluster. This happens through a node
Rule 2
The second rule deals with the situation where nodes in a neighborhood are on the minimum weight level. This situation can happen if, for instance, the initial configuration assigns the minimum weight to all nodes. If there is a neighborhood with all nodes having the minimum weight level, the node
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 decrease its own weight with the objective to correct the fragmentation by allowing the other nodes to reconfigure according to the rules.
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. Given any specific criterion (e.g., device ID, battery power), one cluster center remains while the other cluster center is hierarchized in 1-hop neighborhood to that new cluster center. The choice of the specific criterion to resolve the decision-making depends on the used application scenario and on the available information.
1-D
An exemplary sequence of state transitions applying the described four rules is illustrated below.
2-D
KHOPCA acting in a dynamic 2-D simulation. The geometry is based on a geometric random graph; all existing links are drawn in this network.
3-D
KHOPCA also works in a dynamic 3-D environment. The cluster connections are illustrated with bold lines.
Guarantees
It has been demonstrated that KHOPCA terminates after a finite number of state transitions in static networks.