KHOPCAクラスタリングアルゴリズム
3D 環境で実行される KHOPCA。

KHOPCAは、もともと動的ネットワーク向けに開発された適応型クラスタリングアルゴリズムです。KHOPCA（ホップクラスタリングアルゴリズム）は、ネットワーク内のノードなどの要素を、互いの距離に応じてグループ化する、完全に分散された局所的なアプローチを提供します。 [1] [2] KHOPCAは、適用された距離関数に関して最適なクラスターを定義する単純なルールセットを通じて、プロアクティブに動作します。 け {\textstyle k}

KHOPCAのクラスタリングプロセスは、ノードの参加と離脱を明示的にサポートしているため、KHOPCAは非常に動的なネットワークに適しています。しかし、KHOPCAは静的なネットワークでも動作することが実証されています。[2]

アドホックおよびワイヤレス センサー ネットワークでのアプリケーションの他に、KHOPCA は、位置特定およびナビゲーションの問題、ネットワーク化された群集、およびリアルタイムのデータ クラスタリングと分析にも使用できます。

アルゴリズムの説明

KHOPCA（ホップクラスタリングアルゴリズム）は、可変ホップ数のクラスターを定義するシンプルなルールセットを通じてプロアクティブに動作します。ローカルルールセットは、ノード間の状態遷移を記述します。ノードの重みは、通信範囲内の隣接ノードの現在の状態のみに基づいて決定されます。ネットワークの各ノードは、このプロセスに継続的に関与します。その結果、静的ネットワークと動的ネットワークの両方でホップクラスターが形成され、維持されます。 け {\textstyle k} け {\textstyle k} け {\textstyle k}

KHOPCAは、事前に決定された初期設定を必要としません。したがって、ノードは任意の重み（ から の間）を選択できます。ただし、初期設定の選択は収束時間に影響します。 M 私 北 {\textstyle MIN} M あ X {\textstyle MAX}

初期化

ルールを適用するための開始構成の前提条件は次のとおりです。

  • 北 {\displaystyle \mathrm {N} } はノードとリンクを持つネットワークであり、各ノードには重みがあります。 わ {\displaystyle w}
  • ノード内の各ノードには、 と同じ正の値と が格納されます。 n {\textstyle n} 北 {\displaystyle \mathrm {N} } M 私 北 {\textstyle MIN} M あ X {\textstyle MAX} M 私 北 < M あ X {\textstyle MIN<MAX}
  • 重みを持つノードはクラスター中心と呼ばれます。 n {\textstyle n} わ n ＝ M あ X {\textstyle w_{n}=MAX}
  • け {\textstyle k} は-であり、最外郭ノードからクラスター中心までのクラスターの最大サイズを表します。したがって、クラスターの直径は となります。 M あ X {\textstyle MAX} M 私 北 {\textstyle MIN} け ⋅ 2 − 1 {\textstyle k\cdot 2-1}
  • 北 （ n ） {\displaystyle \mathrm {N} (n)} ノードの直接の隣接ノードを返します。 n {\textstyle n}
  • W （ 北 ） {\textstyle W(\mathrm {N} )} は、 のすべてのノードの重みの集合です。 北 {\displaystyle \mathrm {N} }

以下の規則は、重み を持つノードの状態遷移を記述します。これらの規則は、ここで記述されている順序で各ノード上で実行する必要があります。 n {\textstyle n} わ n {\textstyle w_{n}}

ルール1

KHOPCAルール1

最初のルールは、クラスター内の順序を構築する機能を持ちます。これは、ノードが自身の重みよりも高い重みを持つ直近のノードを検出することで実現されます。このような直近のノードが検出された場合、ノードは自身の重みを、近傍内の最も重みの高いノードの重みから1を引いた値に変更します。このプロセスを繰り返し適用することで、上から下への階層的なクラスター構造が作成されます。 n {\textstyle n} わ {\textstyle w} わ n {\textstyle w_{n}} n {\textstyle n} 

最大( W ( N ( n ))) > w_nの場合   
    w_n =最大値( W ( N ( n ))) - 1

ルール2

KHOPCAルール2

2つ目のルールは、近傍ノードの重みが最小値になっている状況に対応します。例えば、初期設定ですべてのノードに最小値が設定されている場合に、この状況が発生する可能性があります。すべてのノードが最小値になっている近傍ノードが存在する場合、そのノードは自身をクラスターの中心として宣言します。偶然にもすべてのノードが自身をクラスターの中心として宣言した場合でも、衝突状況は他のルールのいずれかによって解決されます。 n {\textstyle n} 

最大( W ( N ( n ) ) == MIN & w_n == MINの場合       
    w_n = MAX ;

ルール3

KHOPCAルール3

3つ目のルールは、クラスタ中心ではない、重み値がレバレッジされたノードが、周囲の重み値が低いノードを引き寄せる状況を記述しています。この動作は、クラスタ中心のない断片化されたクラスタにつながる可能性があります。断片化されたクラスタを回避するために、重み値の高いノードは、他のノードがルールに従って再構成できるようにすることで断片化を修正することを目的として、自身の重みを徐々に減らしていくことが想定されています。

max ( W ( N ( n ))) <= w_n && w_n != MAX の場合       
    w_n = w_n - 1 ;

ルール4

KHOPCAルール4

4つ目のルールは、2つのクラスタセンターが1ホップ近隣で接続し、どちらのクラスタセンターがクラスタセンターとしての役割を継続するかを決定する必要がある状況に対応します。特定の基準（例：デバイスID、バッテリー残量）が与えられた場合、一方のクラスタセンターはそのまま残り、もう一方のクラスタセンターは1ホップ近隣でその新しいクラスタセンターに階層化されます。この意思決定を解決するための特定の基準の選択は、使用されるアプリケーションシナリオと利用可能な情報によって異なります。

最大( W ( N ( n )) == MAX && w_n == MAX の場合       
    w_n = set ( max ( W ( N ( n )), w_n )からノードを選択するための基準を適用します。          
    w_n = w_n - 1 ;

例

1D

説明した 4 つのルールを適用した状態遷移の例示的なシーケンスを以下に示します。

2D

KHOPCAは動的2Dシミュレーションで動作します。ジオメトリは幾何学的ランダムグラフに基づいており、既存のすべてのリンクがこのネットワークに描画されます。

3D

KHOPCAは動的な3D環境でも動作します。クラスターの接続は太線で示されます。

保証

KHOPCAは静的ネットワークにおいて有限回数の状態遷移後に終了することが実証されている。[2]

参考文献

  1. ^ Brust, Matthias R.; Frey, Hannes; Rothkugel, Steffen (2007-01-01). 「モバイルネットワークにおける適応型マルチホップクラスタリング」.第4回モバイル技術、アプリケーション、システム国際会議および第1回モバイル技術におけるコンピュータと人間の相互作用に関する国際シンポジウム議事録. Mobility '07. ニューヨーク、ニューヨーク州、米国: ACM. pp.  132– 138. doi :10.1145/1378063.1378086. ISBN 9781595938190. S2CID  33469900。
  2. ^ abc Brust, Matthias R.; Frey, Hannes; Rothkugel, Steffen (2008-01-01). 「モバイルハイブリッドワイヤレスネットワークのための動的マルチホップクラスタリング」.第2回ユビキタス情報管理・通信国際会議議事録. ICUIMC '08. ニューヨーク、ニューヨーク州、米国: ACM. pp.  130– 135. doi :10.1145/1352793.1352820. ISBN 9781595939937. S2CID  15200455。
「https://en.wikipedia.org/w/index.php?title=KHOPCA_clustering_algorithm&oldid=1250833727」から取得