KHOPCA clustering algorithm: Difference between revisions

Revision as of 14:25, 20 July 2016

Latest revision as of 19:56, 12 October 2024

(24 intermediate revisions by 12 users not shown)

Line 1:

[[File:KHOPCA 3D example 1.png|thumb|KHOPCA running in a 3-D environment.]]

{{Orphan|date=July 2016}}

'''KHOPCA''' is aan adaptive [[clustering algorithm]] designedoriginally developed for dynamic networks. KHOPCA (<math display="inline">k</math>-hop clustering algorithm) provides a fully [[Distributed computing|distributed]] and localized approach to group elements such as nodes in a network according to their distance tofrom each other.<ref>{{Cite journalbook|lastlast1=Brust|firstfirst1=Matthias R.|last2=Frey|first2=Hannes|last3=Rothkugel|first3=Steffen|date=2007-01-01|title=Adaptive Multi-hop Clustering in Mobile Networks|url=http://doi.acm.org/10.1145/1378063.1378086|journal=Proceedings of the 4th Internationalinternational Conferenceconference on Mobilemobile Technologytechnology, Applicationsapplications, and Systemssystems and the 1st Internationalinternational Symposiumsymposium on Computer Humanhuman Interactioninteraction in Mobilemobile technology Technology|chapter=Adaptive multi-hop clustering in mobile networks |date=2007-01-01|series=Mobility '07|___location=New York, NY, USA|publisher=ACM|pages=132–138|doi=10.1145/1378063.1378086|isbn=9781595938190|s2cid=33469900 }}</ref><ref name=":0">{{Cite journalbook|lastlast1=Brust|firstfirst1=Matthias R.|last2=Frey|first2=Hannes|last3=Rothkugel|first3=Steffen|date=2008-01-01|title=DynamicProceedings Multi-hopof Clusteringthe for2nd Mobileinternational Hybridconference Wirelesson Networks|url=http://doi.acm.org/10.1145/1352793.1352820|journal=ProceedingsUbiquitous ofinformation themanagement 2Ndand Internationalcommunication Conference|chapter=Dynamic onmulti-hop Ubiquitousclustering Informationfor Managementmobile andhybrid wireless Communicationnetworks |date=2008-01-01|series=ICUIMC '08|___location=New York, NY, USA|publisher=ACM|pages=130–135|doi=10.1145/1352793.1352820|isbn=9781595939937|s2cid=15200455 }}</ref> KHOPCA (<math display="inline">k</math>-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 performsalso equallyperforms in static networks.<ref name=":0" />

[[File:KHOPCA 3D example 1.png|thumb|KHOPCA in a 3-D environment.]]

'''KHOPCA''' is a [[clustering algorithm]] designed for dynamic networks. KHOPCA provides a fully [[Distributed computing|distributed]] and localized approach to group elements such as nodes in a network according to their distance to each other.<ref>{{Cite journal|last=Brust|first=Matthias R.|last2=Frey|first2=Hannes|last3=Rothkugel|first3=Steffen|date=2007-01-01|title=Adaptive Multi-hop Clustering in Mobile Networks|url=http://doi.acm.org/10.1145/1378063.1378086|journal=Proceedings of the 4th International Conference on Mobile Technology, Applications, and Systems and the 1st International Symposium on Computer Human Interaction in Mobile Technology|series=Mobility '07|___location=New York, NY, USA|publisher=ACM|pages=132–138|doi=10.1145/1378063.1378086|isbn=9781595938190}}</ref><ref name=":0">{{Cite journal|last=Brust|first=Matthias R.|last2=Frey|first2=Hannes|last3=Rothkugel|first3=Steffen|date=2008-01-01|title=Dynamic Multi-hop Clustering for Mobile Hybrid Wireless Networks|url=http://doi.acm.org/10.1145/1352793.1352820|journal=Proceedings of the 2Nd International Conference on Ubiquitous Information Management and Communication|series=ICUIMC '08|___location=New York, NY, USA|publisher=ACM|pages=130–135|doi=10.1145/1352793.1352820|isbn=9781595939937}}</ref> KHOPCA (<math display="inline">k</math>-hop clustering algorithm) operates proactively through a simple set of rules that defines clusters, which are optimal with respect to the applied distance function.

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 [[Cluster analysis|data clustering and analysis]].

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.<ref name=":0" />

== Algorithm description ==

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.

== 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 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, k-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 ===

Line 18 ⟶ 16:

* Each node <math display="inline">n</math> in <math>\Nu</math> node stores the same positive values <math display="inline">MIN</math> and <math display="inline">MAX</math>, with <math display="inline">MIN < MAX</math>.

* A node <math display="inline">n</math> with weight <math display="inline">w_n=MAX</math> is called cluster center.

* <math display="inline">k</math> is <math display="inline">MAX</math> - <math display="inline">MIN</math> and represents the maximum size a cluster can have from the most outer node to the cluster center. aThe cluster can have (cluster diameter is therefore <math display="inline">k\cdot2-1</math>).

* <math>\Nu(n)</math> returns the direct neighbors of node <math display="inline">n</math>.

* <math>W</math> is the set of weights with <math display="inline">W(\Nu)</math> is the the set of weights of all nodes of <math>\Nu</math>.

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 hereorder described orderhere.

=== Rule 1 ===

[[File:KHOPCA rule 1.png|thumb|Illustration of KHOPCA rule 1.]]

The first rule ishas inthe chargefunction toof constructconstructing aan order within the cluster. This happens bythrough 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 detected 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">

if max(W(N(n))) > w_n

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

</syntaxhighlight>

=== Rule 2 ===

[[File:KHOPCA rule 2 a.png|thumb|Illustration of 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 coincidentlycoincidentally all nodes declare themselves as cluster centers, the conflict situation will be resolved by one of the other rules.<syntaxhighlight lang="java" line="1">

if max(W(N(n)) == MIN & w_n == MIN

w_n = MAX;

</syntaxhighlight>

=== Rule 3 ===

[[File:KHOPCA rule 3 a.png|thumb|Illustration of 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 decreasingdecrease its own weight with the objective to correct the fragmentation by allowing the other nodes to reconfigure acccordingaccording to the rules. <syntaxhighlight lang="java" line="1">

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

w_n = w_n - 1;

Line 43:

=== Rule 4 ===

[[File:KHOPCA rule 4 a.png|thumb|Illustration of 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. InGiven accordanceany ofspecific acriterion certain(e.g., criteriondevice 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 isto dependingresolve the decision-making depends on the used application scenario and on the available information available. In case of networks, one can assume that each node carries besides the weight also an unique ID number, which can be used in order to resolve the conflict.<syntaxhighlight lang="java" line="1">

if max(W(N(n)) == MAX && w_n == MAX

w_n = randomlyapply choosecriterion to select a node from set (max(W(N(n)),w_n);

w_n = w_n - 1;

</syntaxhighlight>

Line 52:

== Examples ==

=== 1-D1D ===

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

[[File:KHOPCA 1D example 1.png|frameless]]

=== 2-D2D ===

KHOPCA acting in a dynamic 2-D2D simulation. The geometry is based on a geometric random graph; all existing links are drawn in this network.

[[File:KHOPCA 2D k3a.jpg|frameless]]

=== 3-D3D ===

KHOPCA also works in a dynamic 3-D3D environment. The cluster connections are illustrated with bold lines.

[[File:KHOPCA 3D example 12.png|frameless]]

== Guarantees ==

Line 73:

{{Reflist}}

{{Uncategorized|date=July 2016}}

[[Category:Clustering algorithms]]

[[Category:Algorithms]]

{{DEFAULTSORT:KHOPCA clustering algorithm}}

[[Category:ClusteringGraph algorithms]]

__INDEX__