расстояний между ним и остальными узлами-кандидатами, назначает
себя первым опорным узлом.
Пока число выбранных опорных узлов
k
меньше необходимого
n
b
,
итерационно выполняются следующие действия:
•
опорные узлы обмениваются друг с другом значениями расстоя-
ний между ними и оставшимися узлами-кандидатами;
•
для каждого оставшегося узла-кандидата
c
∈
V
c
выбранные
опорные узлы
b
i
(при
1
≤
i
≤
k
) вычисляют значение функции
голосования вида
f
LCR
(
c
) =
k
i
=1
h
(
c, b
i
)
,
(8)
где
h
(
c, b
i
)
— расстояние между узлом-кандидатом
c
и
i
-м опор-
ным узлом;
•
опорные узлы назначают узел-кандидат с максимальным значе-
нием функции голосования (8)
(
k
+ 1)
-м опорным узлом.
Видно, что в алгоритме LCR используется функция голосования,
аналогичная
f
prod
(
v, B
)
(см. выражение (4)), поэтому полученные рас-
пределения опорных узлов примерно одинаковые. Отличие в располо-
жении опорных узлов возможно из-за того, что в предложенном алго-
ритме опорным узлом может быть любой узел
v
∈
V
, а в алгоритме
LCR — только узлы из множества
V
c
⊂
V
.
Таким образом, алгоритм LCR отличается от предложенного сле-
дующим:
•
непосредственный выбор опорных узлов выполняется не из
всего множества обычных узлов, а из их подмножества (среди
узлов-кандидатов);
•
решение о назначении очередного опорного узла принимают
действующие опорные узлы;
•
для принятия решения по следующему опорному узлу необхо-
дим обмен данными между выбранными опорными узлами.
Выполним сравнение алгоритмов по указанным критериям слож-
ности.
Оценка сложности алгоритма LCR.
К сожалению, в работе [4] не
приведена оценка сложности алгоритма выбора опорных узлов в про-
токоле LCR, поэтому выполним оценку затрат времени и памяти для
этого алгоритма. Предположим, что затраты на формирование множе-
ства узлов-кандидатов
V
c
и на передачу информации между опорными
узлами в процессе выбора пренебрежимо малы.
Полученные оценки сложности равны
T
LCR
=
O
(
d
)
26 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2008. № 4
