Content deleted Content added
Speng dahl (talk | contribs) mNo edit summary |
m Moving Category:Algorithms in graph theory to Category:Graph algorithms per Wikipedia:Categories for discussion/Log/2024 October 4 |
||
(23 intermediate revisions by 12 users not shown) | |||
Line 1:
[[File:KHOPCA 3D example 1.png|thumb|KHOPCA running in a 3-D environment.]]▼
'''KHOPCA''' is
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
▲[[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>)
▲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.
* <math>\Nu(n)</math> returns the direct neighbors of node <math display="inline">n</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
=== Rule 1 ===
[[File:KHOPCA rule 1.png|thumb|
The first rule
if max(W(N(n))) > w_n
w_n = max(W(N(n))) - 1
</syntaxhighlight>
=== Rule 2 ===
[[File:KHOPCA rule 2 a.png|thumb|
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
if max(W(N(n)) == MIN & w_n == MIN
w_n = MAX;
</syntaxhighlight>
=== Rule 3 ===
[[File:KHOPCA rule 3 a.png|thumb|
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
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|
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.
if max(W(N(n)) == MAX && w_n == MAX
w_n =
w_n = w_n - 1;
</syntaxhighlight>
Line 52:
== Examples ==
===
An exemplary sequence of state transitions applying the described four rules is illustrated below.
[[File:KHOPCA 1D example 1.png|frameless]]
===
KHOPCA acting in a dynamic
[[File:KHOPCA 2D k3a.jpg|frameless]]
===
KHOPCA also works in a dynamic
[[File:KHOPCA 3D example
== Guarantees ==
Line 73:
{{Reflist}}
[[Category:Clustering algorithms]]▼
{{DEFAULTSORT:KHOPCA clustering algorithm}}
|