Полагаем, что затраты ресурсов на выбор узла-инициатора прене-
брежимо малы.
На втором и третьем этапах последовательно выбираются опорные
узлы. Для вычисления всеми узлами расстояния до узла-инициатора
(или опорного узла) в наихудшем случае требуется время, пропорци-
ональное диаметру сети
d
. Следовательно, оценка общих затрат вре-
мени на выполнение алгоритма составляет
T
=
O
(
n
b
d
)
.
Для принятия решения о назначении себя опорным узел должен
хранить информацию о своих непосредственных соседях, число кото-
рых равно
ρ
. Служебная информация о каждом из них занимает объем
O
(
n
b
)
, поэтому общие требования к памяти равны
M
=
O
(
n
b
ρ
)
.
В оптимизированной версии алгоритма узлу достаточно сохранять
только свои собственные координаты, следовательно,
M
opt
=
O
(
n
b
)
.
На практике число опорных узлов
n
b
задается постоянным и не
зависит от общего числа узлов
n
, при этом
n
b
n
. Тогда
n
b
мож-
но считать константой, не зависящей от размерности задачи, поэтому
оценки сложности принимают вид
T
=
O
(
d
) ;
(7)
M
=
O
(
ρ
)
и
M
opt
=
O
(1)
.
Сравнение с алгоритмом Logical Coordinate Routing.
В рабо-
те [4] предложен протокол маршрутизации Logical Coordinate Routing
и дополнительно к нему алгоритм для автоматического выбора про-
извольного числа опорных узлов. Приведем краткое описание этого
алгоритма и сравним его с предложенным в настоящей работе.
Описание алгоритма LCR.
На первом этапе из всего множества уз-
лов случайным образом выбирается подмножество узлов-кандидатов
V
c
⊂
V
, среди которых затем будут назначены опорные узлы. При
этом только один узел может быть узлом-кандидатом в любом сете-
вом окружении в пределах одной элементарной передачи.
Далее узлы-кандидаты начинают передавать сигнальные пакеты
для измерения расстояния относительно друг друга. По истечении
необходимого времени узел-кандидат, имеющий максимальную сумму
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2008. № 4 25
