и
M
LCR
=
O
(max(
M
1
, M
2
))
,
где
M
1
=
n
c
,
(9)
M
2
=
⎧⎨
⎩
(
n
b
−
1)(
n
c
−
n
b
+ 1)
при
n
b
<
n
c
2
+ 1
;
n
2
c
4
при
n
b
≥
n
c
2
+ 1
.
(10)
Выражение (9) описывает требования к объему памяти узла-
кандидата, а формула (10) — требования к памяти опорного узла.
Необходимый запас памяти равен наибольшему значению среди них,
так как в качестве кандидата или опорного может быть выбран любой
узел сети.
С учетом формулы (1) число узлов-кандидатов
n
c
=
|
V
c
|
в сети
можно оценить следующим образом:
n
c
=
A
πr
2
=
n
ρ
=
1
π
d
2
.
(11)
При
n
b
n
получаем
T
LCR
=
O
(
d
)
(12)
и
M
LCR
=
O
n
ρ
=
O d
2
.
(13)
Сравнение алгоритмов по критериям сложности.
Согласно выра-
жениям (7) и (12) временные затраты на выполнение автоматическо-
го выбора опорных узлов для обоих алгоритмов линейно зависят от
диаметра сети
d
, т.е. размера сети в элементарных передачах. Следо-
вательно, по времени выполнения оба алгоритма являются оптималь-
ными для протоколов маршрутизации по виртуальным координатам.
По требованиям к ресурсам памяти предложенный в настоящей
работе алгоритм полностью обладает свойством масштабируемости,
так как затраты памяти зависят только от плотности сетевого окруже-
ния
ρ
, а не от общего числа узлов
n
или диаметра сети
d
. Алгоритм
использует минимально необходимую для протокола маршрутизации
информацию, поэтому по требованиям к памяти он также является
оптимальным.
При использовании оптимизированного варианта алгоритма затра-
ты памяти составляют
O
(1)
, т.е. не зависят ни от плотности размеще-
ния, ни от общего числа узлов.
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2008. № 4 27
