Алгоритм кластеризации KHOPCA

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

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

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

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

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

KHOPCA не требует какой-либо заранее определенной начальной конфигурации. Следовательно, узел потенциально может выбрать любой вес (между ${\textstyle MIN}$ и ${\textstyle MAX}$ ). Однако выбор начальной конфигурации влияет на время сходимости.

Инициализация

Предварительные условия в начальной конфигурации для применения правил следующие.

$\mathrm {N}$ это сеть с узлами и ссылками, в которой каждый узел имеет вес $w$ .
Каждый узел ${\textstyle n}$ в $\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}$ .
$\mathrm {N} (n)$ возвращает прямых соседей узла ${\textstyle n}$ .
${\textstyle W(\mathrm {N} )}$ представляет собой набор весов всех узлов $\mathrm {N}$ .

Следующие правила описывают переход состояния узла. ${\textstyle n}$ с весом ${\textstyle w_{n}}$ . Эти правила должны выполняться на каждом узле в порядке, описанном здесь.

Правило 1

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

if max(W(N(n))) > w_n
    w_n = max(W(N(n))) - 1

Правило 2

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

if max(W(N(n)) == MIN & w_n == MIN
    w_n = MAX;

Правило 3

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

if max(W(N(n))) <= w_n && w_n != MAX
    w_n = w_n - 1;

Правило 4

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

if max(W(N(n)) == MAX && w_n == MAX
    w_n = apply criterion to select a node from set (max(W(N(n)),w_n);
    w_n = w_n - 1;

Примеры

1Д

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

2D

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

3D

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

Гарантии

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

Ссылки

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

[1] Бруст, Матиас Р.; Фрей, Ханнес; Роткугель, Штеффен (1 января 2007 г.). «Адаптивная многоскачковая кластеризация в мобильных сетях». Материалы 4-й международной конференции по мобильным технологиям, приложениям и системам и 1-го международного симпозиума по взаимодействию компьютера и человека в мобильных технологиях . Мобильность '07. Нью-Йорк, штат Нью-Йорк, США: ACM. стр. 132–138. дои : 10.1145/1378063.1378086 . ISBN 9781595938190 . S2CID 33469900 .

[:0-2] Jump up to: ^а ^б ^с Бруст, Матиас Р.; Фрей, Ханнес; Роткугель, Штеффен (1 января 2008 г.). «Динамическая многоскачковая кластеризация для мобильных гибридных беспроводных сетей». Материалы 2-й международной конференции по повсеместному управлению информацией и коммуникациям . ICUIMC '08. Нью-Йорк, штат Нью-Йорк, США: ACM. стр. 130–135. дои : 10.1145/1352793.1352820 . ISBN 9781595939937 . S2CID 15200455 .

[1]

[2]