Распределенная реализация алгоритма.
Согласно распределен-
ной реализации алгоритма каждый узел
v
∈
V
выполняет одинаковый
набор действий, т.е. какого-либо централизованного управления не
требуется. Именно этот вариант алгоритма предназначен для приме-
нения на практике.
Инициализация.
После включения каждый узел
v
∈
V
выполняет
следующую последовательность операций:
•
присвоение вектору виртуальных координат начального значе-
ния
v
=
{
v
i
=
∞}
n
b
i
=1
;
•
запуск процесса «локальный обмен сигнальными пакетами» с
периодом
t
b
;
•
запуск процесса «выбор опорных узлов» с периодом
t
bs
.
Процесс “локальный обмен сигнальными пакетами”
заключается
в том, что каждый узел с периодом
t
b
передает широковещательный
пакет, в котором содержатся его собственные координаты и координа-
ты узлов из его таблицы сетевого окружения (таблица со служебной
информацией о ближайших соседях узла). В ходе такого обмена узлы
поддерживают в актуальном состоянии информацию о соседних уз-
лах и обновляют свои виртуальные координаты по описанной далее
процедуре.
Процесс “выбор опорных узлов”
заключается в том, что с перио-
дом
t
bs
узел проверяет необходимость назначения одного из опорных
узлов. Значение
t
bs
должно быть порядка величины (2), чтобы хватило
времени на вычисление всеми узлами сети расстояния до последнего
выбранного опорного узла.
Если узел
v
уже является опорным или узлом-инициатором, то
текущая итерация процесса прекращается.
Если
|
B
(
v
)
|
=
n
b
, т.е. узлу
v
известны все опорные узлы и они
находятся в активном состоянии, то данная итерация алгоритма также
завершается.
Если узлу
v
не известно ни одного опорного узла, т.е.
|
B
(
v
)
|
= 0
,
то он назначает себя узлом-инициатором процесса выбора опорных
узлов. На этом текущая итерация алгоритма завершается.
Если узел-инициатор или один (или более) опорных узлов уже
присутствуют в сети, то порядковый номер очередного выбираемого
опорного узла равен
k
= min
{
i
: 1
≤
i
≤
n
b
, i
∈
B
(
v
)
}
.
Далее узел
v
вычисляет свое число “голосов” на получение статуса
опорного узла с номером
k
:
p
(
v, B
(
v
)) =
⎧⎨
⎩
h
0
(
v
)
при
k
= 1
;
f
(
v, B
(
v
))
при
1
< k
≤
n
b
.
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2008. № 4 21
