при случайном распределении опорных узлов и
L
2
(
v, t
) =
n
b
i
=1
|
v
i
−
t
i
|
2
(3)
при использовании алгоритма выбора опорных узлов.
Выводы.
Предложено несколько способов повышения эффектив-
ности протоколов маршрутизации по виртуальным координатам, прак-
тическая реализация которых сохраняет низкую сложность по време-
ни и памяти, а также высокую масштабируемость алгоритмов дан-
ного типа. Результаты имитационного моделирования показали, что
рассмотренные методы позволяют значительно повысить долю паке-
тов, доставленных в режиме минимизации виртуального расстояния,
и приблизить длину найденных маршрутов к оптимальной.
На основе проведенного исследования можно сформулировать сле-
дующие рекомендации.
•
При равномерно распределенных по сети или находящихся на
периферии сети опорных узлах существенно снижается вероят-
ность локального минимума по сравнению со случайным назна-
чением узлов. В результате повышается надежность доставки
пакетов и уменьшается длина найденных маршрутов.
•
Распределение опорных узлов по границе сети более предпочти-
тельно, чем равномерное размещение, но разница незначительна.
Требуется более детальное сравнение данных видов распределе-
ний (в частности, в условиях наличия пустот в топологии сети).
•
Размеры доверительных интервалов результатов моделирования
показывают, что характеристики эффективности протокола ВК-
маршрутизации более стабильны при целенаправленном распре-
делении опорных узлов, чем при их случайном выборе.
•
При наличии свободного пространства в таблице сетевого окру-
жения целесообразно сохранять информацию о соседних узлах
2-го уровня для ее использования при выходе из локального ми-
нимума. Эффективность данного подхода повышается по мере
снижения средней плотности размещения узлов, поэтому табли-
цы сетевого окружения могут иметь фиксированный размер при
изменении
ρ
в широких пределах.
•
Порядок нормы виртуального расстояния должен иметь значения
p
∈
(1;
∞
)
, но для снижения вычислительной сложности следует
использовать
p
= 2
.
•
При распределении опорных узлов по периметру или равномер-
ном распределении рассмотренные весовые функции не оказы-
вают влияния на успешность «жадной» маршрутизации, поэто-
му при таких способах назначения опорных узлов наилучшей
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2009. № 2 123
