Algoritmo de agrupamiento KHOPCA

Los requisitos previos en la configuración de inicio para la aplicación de las reglas son los siguientes.

• ${\displaystyle \mathrm {N} }$es la red con nodos y enlaces, donde cada nodo tiene un peso${\displaystyle w}$.
• Cada nodo${\textstyle n}$en${\displaystyle \mathrm {N} }$El nodo almacena los mismos valores positivos.${\textstyle MIN}$y${\textstyle MAX}$, con${\textstyle MIN<MAX}$.
• Un nodo${\textstyle n}$con peso${\textstyle w_{n}=MAX}$Se denomina centro de clúster.
• ${\textstyle k}$es${\textstyle MAX}$-${\textstyle MIN}$y representa el tamaño máximo que puede tener un clúster desde el nodo más externo hasta el centro del clúster. Por lo tanto, el diámetro del clúster es${\textstyle k\cdot 2-1}$.
• ${\displaystyle \mathrm {N} (n)}$devuelve los vecinos directos del nodo${\textstyle n}$.
• ${\textstyle W(\mathrm {N} )}$es el conjunto de pesos de todos los nodos de${\displaystyle \mathrm {N} }$.

Las siguientes reglas describen la transición de estado para un nodo.${\textstyle n}$con peso${\textstyle w_{n}}$Estas reglas deben ejecutarse en cada nodo en el orden que se describe aquí.

La primera regla tiene la función de construir un orden dentro del clúster. Esto sucede a través de un nodo.${\textstyle n}$detecta al vecino directo con el peso más alto${\textstyle w}$, que es mayor que el propio peso del nodo${\textstyle w_{n}}$. Si se detecta un vecino directo de este tipo, el nodo${\textstyle n}$cambia su propio peso para que sea el peso del peso más alto dentro del vecindario menos 1. Aplicado de forma iterativa, este proceso crea una estructura de clúster jerárquica de arriba hacia abajo.

si max ( W ( N ( n ))) > w_nw_n = max ( W ( N ( n ))) - 1

La segunda regla trata la situación en la que los nodos de un vecindario están en el nivel de peso mínimo. Esta situación puede ocurrir si, por ejemplo, la configuración inicial asigna el peso mínimo a todos los nodos. Si hay un vecindario con todos los nodos que tienen el nivel de peso mínimo, el nodo${\textstyle n}$se declara a sí mismo como centro del clúster. Incluso si, por coincidencia, todos los nodos se declaran a sí mismos como centros del clúster, la situación de conflicto se resolverá mediante una de las otras reglas.

si max ( W ( N ( n )) == MIN & w_n == MINw_n = MÁX ;

La tercera regla describe situaciones en las que los nodos con valores de ponderación elevados, que no son centros de clúster, atraen a los nodos circundantes con ponderaciones menores. Este comportamiento puede generar clústeres fragmentados sin un centro definido. Para evitar la fragmentación, el nodo con mayor ponderación debe disminuir progresivamente la suya propia con el objetivo de corregirla, permitiendo que los demás nodos se reconfiguren según las reglas.

Si max ( W ( N ( n ))) <= w_n && w_n != MAXw_n = w_n - 1 ;

La cuarta regla resuelve la situación en la que dos centros de clúster se conectan en una vecindad de un salto y necesitan decidir cuál de ellos debe continuar como centro de clúster. Dado un criterio específico (por ejemplo, ID del dispositivo, nivel de batería), un centro de clúster permanece como tal, mientras que el otro se jerarquiza en una vecindad de un salto con respecto a ese nuevo centro de clúster. La elección del criterio específico para resolver la toma de decisiones depende del escenario de aplicación utilizado y de la información disponible.

si max ( W ( N ( n )) == MAX && w_n == MAXw_n = aplicar criterio para seleccionar un nodo del conjunto ( max ( W ( N ( n )), w_n );w_n = w_n - 1 ;

A continuación se ilustra una secuencia ejemplar de transiciones de estado aplicando las cuatro reglas descritas.

KHOPCA opera en una simulación dinámica 2D. La geometría se basa en un grafo geométrico aleatorio; todos los enlaces existentes se representan en esta red.

KHOPCA también funciona en un entorno 3D dinámico. Las conexiones de los clústeres se ilustran con líneas gruesas.