Content deleted Content added
Speng dahl (talk | contribs) mNo edit summary |
Speng dahl (talk | contribs) mNo edit summary |
||
Line 6:
Besides applications in ad hoc and [[wireless sensor network]]s, KHOPCA can be used in localization and navigation problems, networked [[Swarm intelligence|swarming]], and real-time data clustering.
==
KHOPCA (<math display="inline">k</math>-hop clustering algorithm) operates proactively through a simple set of rules that defines clusters with variable <math display="inline">k</math>-hops. A set of local rules describes 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, <math display="inline">k</math>-hop clusters are formed and maintained in static as well as dynamic networks.
KHOPCA does not require any predetermined initial configuration. Therefore, a node can potentially choose any weight (between <math display="inline">MIN</math> and <math display="inline">MAX</math>) at any time. However, the choice of the initial configuration does influence the convergence time.
=== Initialization and set of rules ===
==== Initialization ====
The prerequisites in the start configuration for the application of the rules are the following.
* <math>\Nu</math> is the network with nodes and links, whereby each node has a weight <math>w</math>.
Line 21 ⟶ 23:
The following rules describe the state transition for a node <math display="inline">n</math> with weight <math display="inline">w_n</math>. These rules have to be executed on each node in the order described here.
==== Rule 1 ====
[[File:KHOPCA rule 1.png|thumb|KHOPCA rule 1]]
The first rule has the function of constructing an order within the cluster. This happens through a node <math display="inline">n</math> detects the direct neighbor with the highest weight <math display="inline">w</math>, which is higher than the node's own weight <math display="inline">w_n</math>. If such a direct neighbor is detected, the node <math display="inline">n</math> changes its own weight to be the weight of the highest weight within the neighborhood subtracted by 1. Applied iteratively, this process creates a top-to-down hierarchical cluster structure.<syntaxhighlight lang="java" line="1">
Line 27 ⟶ 29:
w_n = max(W(N(n))) - 1
</syntaxhighlight>
==== Rule 2 ====
[[File:KHOPCA rule 2 a.png|thumb|KHOPCA 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 <math display="inline">n</math> declares itself as cluster center. Even if coincidently all nodes declare themselves as cluster centers, the conflict situation will be resolved by one of the other rules.<syntaxhighlight lang="java" line="1">
Line 33 ⟶ 35:
w_n = MAX;
</syntaxhighlight>
==== Rule 3 ====
[[File:KHOPCA rule 3 a.png|thumb|KHOPCA 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 acccording to the rules. <syntaxhighlight lang="java" line="1">
Line 40 ⟶ 42:
</syntaxhighlight>
==== Rule 4 ====
[[File:KHOPCA rule 4 a.png|thumb|KHOPCA 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. <syntaxhighlight lang="java" line="1">
| |||