Алгоритм кластеризации KHOPCA - KHOPCA clustering algorithm - Wikipedia

KHOPCA работает в трехмерной среде.

KHOPCA адаптивный алгоритм кластеризации изначально разработан для динамических сетей. KHOPCA (${\textstyle k}$алгоритм кластеризации -hop) обеспечивает полностью распределен и локализованный подход к группировке элементов, таких как узлы в сети, в соответствии с их расстоянием друг от друга.^[1][2] KHOPCA действует проактивно с помощью простого набора правил, который определяет кластеры, оптимальные с точки зрения применяемой функции расстояния.

Процесс кластеризации KHOPCA явно поддерживает присоединение и выход узлов, что делает KHOPCA подходящим для высокодинамичных сетей. Однако было продемонстрировано, что KHOPCA также работает в статических сетях.^[2]

Помимо приложений в специальных и беспроводные сенсорные сети, KHOPCA может использоваться в задачах локализации и навигации, сетевых роение, и в реальном времени кластеризация и анализ данных.

Описание алгоритма

KHOPCA (${\textstyle k}$-hop алгоритм кластеризации) работает проактивно с помощью простого набора правил, который определяет кластеры с переменной ${\textstyle k}$-магазины. Набор локальных правил описывает переход состояний между узлами. Вес узла определяется только в зависимости от текущего состояния его соседей в зоне действия связи. Каждый узел сети постоянно участвует в этом процессе. В результате, ${\textstyle k}$Кластеры -hop формируются и поддерживаются как в статических, так и в динамических сетях.

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

KHOPCA правило 1

Первое правило имеет функцию построения порядка внутри кластера. Это происходит через узел ${\textstyle n}$ обнаруживает прямого соседа с наивысшим весом ${\textstyle w}$, что больше собственного веса узла ${\textstyle w_{n}}$. Если такой прямой сосед обнаружен, узел ${\textstyle n}$ изменяет свой собственный вес на вес самого высокого веса в пределах окрестности, вычитаемый на 1. При итеративном применении этот процесс создает иерархическую структуру кластера сверху вниз.

1если Максимум(W(N(п))) > w_n2    w_n = Максимум(W(N(п))) - 1

Правило 2

KHOPCA правило 2

Второе правило касается ситуации, когда узлы в окрестности имеют минимальный вес. Такая ситуация может произойти, если, например, исходная конфигурация присваивает минимальный вес всем узлам. Если существует окрестность, в которой все узлы имеют минимальный уровень веса, узел ${\textstyle n}$ заявляет о себе как кластерный центр. Даже если по совпадению все узлы объявляют себя центрами кластера, конфликтная ситуация будет разрешена одним из других правил.

1если Максимум(W(N(п)) == MIN & w_n == MIN2    w_n = МАКСИМУМ;

Правило 3

KHOPCA правило 3

Третье правило описывает ситуации, когда узлы с усиленными значениями веса, которые не являются центрами кластеров, привлекают окружающие узлы с более низким весом. Такое поведение может привести к фрагментированным кластерам без центра кластера. Чтобы избежать фрагментированных кластеров, предполагается, что узел с более высоким значением веса будет последовательно уменьшать свой собственный вес с целью исправления фрагментации, позволяя другим узлам перенастраиваться в соответствии с правилами.

1если Максимум(W(N(п))) <= w_n && w_n != МАКСИМУМ2    w_n = w_n - 1;

Правило 4

KHOPCA правило 4

Четвертое правило разрешает ситуацию, когда два центра кластера соединяются в соседстве с 1 переходом и необходимо решить, какой центр кластера должен продолжать выполнять свою роль центра кластера. Учитывая какой-либо конкретный критерий (например, идентификатор устройства, мощность батареи), один центр кластера остается, в то время как другой центр кластера иерархизирован в 1-шаговой окрестности этого нового центра кластера. Выбор конкретного критерия для принятия решения зависит от используемого сценария приложения и от доступной информации.

1если Максимум(W(N(п)) == МАКСИМУМ && w_n == МАКСИМУМ2    w_n = подать заявление критерий к Выбрать а узел из набор (Максимум(W(N(п)),w_n);3    w_n = w_n - 1;

Примеры

1-D

Примерная последовательность переходов состояний с применением описанных четырех правил проиллюстрирована ниже.

2-D

KHOPCA действует в динамическом 2-D моделировании. Геометрия основана на геометрическом случайном графе; все существующие ссылки нарисованы в этой сети.

3-D

KHOPCA также работает в динамической 3-D среде. Кластерные соединения показаны жирными линиями.

Гарантии

Было продемонстрировано, что KHOPCA завершается после конечного числа переходов состояний в статических сетях.^[2]

Рекомендации

1. Brust, Matthias R .; Фрей, Ханнес; Роткугель, Штеффен (01.01.2007). «Адаптивная многоскачковая кластеризация в мобильных сетях». Материалы 4-й Международной конференции по мобильным технологиям, приложениям и системам и 1-го Международного симпозиума по взаимодействию человека с компьютером в мобильных технологиях. Мобильность '07. Нью-Йорк, Нью-Йорк, США: ACM: 132–138. Дои:10.1145/1378063.1378086. ISBN  9781595938190.
2. Brust, Matthias R .; Фрей, Ханнес; Роткугель, Штеффен (01.01.2008). «Динамическая многоскачковая кластеризация для мобильных гибридных беспроводных сетей». Материалы 2-й Международной конференции по универсальному управлению информацией и коммуникациям. ICUIMC '08. Нью-Йорк, Нью-Йорк, США: ACM: 130–135. Дои:10.1145/1352793.1352820. ISBN  9781595939937.