такой алгоритм для применения в протоколах маршрутизации по вир-
туальным координатам — оптимальный.
Описание алгоритма.
Для простоты изложения сначала опишем
общую схему алгоритма, состоящую из трех этапов.
Выбор узла-инициатора.
На первом этапе случайным образом вы-
бирается один узел-инициатор, который будет, как и обычный опорный
узел, периодически передавать сигнальные пакеты, чтобы остальные
узлы сети могли вычислить расстояние до него. Здесь и далее под
расстоянием между узлами понимается длина кратчайшего пути в ко-
личестве элементарных передач.
Выбор узла-инициатора может быть выполнен с помощью следу-
ющей известной процедуры. Каждый узел при включении запускает
таймер со случайным значением времени срабатывания. Если до ис-
течения тайм-аута узел не получил информации о том, что в сети уже
есть узел-инициатор, то он сам назначает себя узлом–инициатором.
При этом включение узлов может происходить как одновременно, так
и в разные моменты времени (например, последовательно).
Случайная величина тайм-аута необходима для уменьшения ве-
роятности того, что несколько узлов одновременно назначат себя
узлами–инициаторами. При возникновении такой ситуации конфликт
может быть разрешен различными способами. Например, с учетом
уникальности идентификаторов (адресов) узлов приоритет отдается
узлу с наименьшим (или наибольшим) адресом.
Выполнение первого этапа продолжается в течение интервала вре-
мени
t
, которого должно быть достаточно для вычисления всеми узла-
ми сети длины кратчайшего пути до узла-инициатора. Минимальное
допустимое значение
t
равно задержке распространения сигнального
пакета от узла-инициатора до остальных узлов сети, т.е.
t
=
dt
b
,
(2)
где
t
b
— период передачи сигнальных пакетов.
Выбор первого опорного узла.
По завершении предыдущего этапа
алгоритма все узлы сети знают свое расстояние до узла-инициатора.
Тогда первым опорным узлом
b
1
назначается узел, находящийся на
максимальном расстоянии от узла-инициатора, т.е.
b
1
= argmax
v
∈
V
h
0
(
v
)
,
где
h
0
(
v
)
— расстояние между узлом
v
и узлом-инициатором.
Выбранный узел начинает функционировать в качестве опорного,
а узел-инициатор становится обычным узлом при получении первого
сигнального пакета от
b
1
.
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2008. № 4 19
