KHOPCAクラスタリングアルゴリズム

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

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

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

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

KHOPCA では、事前に決定された初期設定は必要ありません。したがって、ノードは潜在的に任意の重み ( ～の間) を選択できます。ただし、初期設定の選択は収束時間に影響します。 ${\textstyle MIN}$${\textstyle MAX}$

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

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

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

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

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

2 番目のルールは、近隣のノードが最小の重みレベルにある状況に対処します。この状況は、たとえば、初期構成ですべてのノードに最小の重みが割り当てられている場合に発生する可能性があります。すべてのノードが最小の重みレベルを持つ近隣がある場合、そのノードは自身をクラスター センターとして宣言します。偶然にすべてのノードが自身をクラスター センターとして宣言した場合でも、競合状況は他のルールの 1 つによって解決されます。${\textstyle n}$

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

3 番目のルールは、クラスターの中心ではない、重み付けされた値を持つノードが、より低い重みを持つ周囲のノードを引き付ける状況について説明します。この動作により、クラスターの中心のない断片化されたクラスターが発生する可能性があります。断片化されたクラスターを回避するために、重み値の高いノードは、他のノードがルールに従って再構成できるようにすることで断片化を修正することを目的として、自身の重みを連続的に減らす必要があります。

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

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

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

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

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

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

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