A
, м
2
, а дальность радиосвязи между узлами составляет
r
, м. Тогда
плотность сетевого окружения (среднее число соседей у каждого узла)
равна
ρ
=
nπr
2
/A
узлов. Обозначим через
d
диаметр сети — макси-
мальное расстояние между всевозможными парами узлов, измеренное
как длина кратчайшего пути между ними. Диаметр сети будем оцени-
вать по упрощенной формуле
d
≈
√
A
r
=
πn
ρ
.
(1)
Предположение о распределении узлов на плоскости выбрано ради
наглядности. При имеющем место на практике распределении узлов в
трехмерном пространстве изменяется только вид выражений, описы-
вающих связь
n
,
ρ
и
d
, а остальные рассуждения остаются прежними.
Требуется разработать алгоритм выбора заданного числа опорных
узлов
n
b
(
n
b
≤
n
) из исходного множества узлов
V
. Узлы из полу-
ченного в результате работы алгоритма множества опорных узлов
V
b
(
V
b
⊆
V
) должны быть распределены в пространстве по одному из
двух вариантов:
•
равномерно распределены по сети на максимальном расстоянии
относительно друг друга;
•
распределены по периферии (на границе) сети.
Нельзя утверждать, что указанные распределения опорных узлов
являются наилучшими из всех возможных. Но в работах [4, 5] пока-
зано, что такие распределения снижают число совпадающих вирту-
альных координат и, следовательно, уменьшают вероятность появле-
ния локального минимума. Более подробное исследование влияния
распределения опорных узлов на эффективность маршрутизации по
виртуальным координатам планируется в дальнейших работах.
Алгоритм должен быть распределенным и иметь сложность по
времени и по памяти
O
(
d
)
и
O
(
ρ
)
соответственно при условии, что
n
b
n
и
n
b
не зависит от
n
. Под сложностью по времени понимается
общее время выполнения алгоритма, а под сложностью по памяти —
требование к объему памяти каждого из узлов сети.
При любом протоколе маршрутизации по виртуальным координа-
там (независимо от способа размещения опорных узлов) требуется
время
O
(
d
)
для вычисления узлами своих виртуальных координат и
объем памяти
O
(
ρ
)
для хранения узлами координат своих ближайших
соседей. Следовательно, если время выполнения некоторого алгорит-
ма выбора опорных узлов составляет
O
(
d
)
, используется информация
только о соседних узлах в объеме
O
(
ρ
)
и при этом по завершении
работы алгоритма все виртуальные координаты узлов вычислены, то
18 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2008. № 4
