6. Если
v
является
k
-м опорным узлом, то он начинает широкове-
щательное распространение пакета в пределах
t
k
ретрансляций.
В пп. 1–3 выполняется стандартный «жадный» поиск маршрута, а
в пп. 4–6 реализуется упрощенный вариант бектрекинг-режима [1] для
выхода из локального минимума. Описанная процедура соответству-
ет базовой функциональности протоколов ВК-маршрутизации [1–4], а
отличие в деталях несущественно для целей данного исследования.
Для оценки эффективности ВК-маршрутизации используются сле-
дующие параметры:
•
коэффициент доставки пакетов в режиме «жадной» маршрути-
зации
η
GR
— отношение числа пакетов, дошедших до конечных
узлов-получателей только в режиме «жадной» маршрутизации,
к общему числу пакетов, переданных узлами-отправителями;
•
коэффициент длины маршрутов
η
PS
— среднее значение отно-
шения длины найденных маршрутов к длине кратчайших путей
между узлами. Длина маршрута (пути) — это число соединений,
через которое он проходит.
Исследование характеристик протокола маршрутизации выполне-
но с помощью среды имитационного моделирования OMNeT++ вер-
сии 3.2 и пакета моделей Mobility Framework версии 2.0. Целью тести-
рования является исследование характеристик именно метода марш-
рутизации, поэтому использовались идеальные модели физического
уровня и уровня управления доступом к среде, чтобы исключить вли-
яние на результаты потери пакетов из-за ошибок при передаче, колли-
зий, переполнения буферов и т.п.
Для различных сочетаний параметров сети (общего числа узлов
n
, плотности размещения
ρ
и диаметра
d
) было создано по 5 топо-
логий со случайным размещением узлов на квадратном пространстве
таким образом, чтобы сеть была полностью связной при
r
= 50
м.
Для каждого экземпляра сети со стационарной топологией проводи-
лась серия из 10 запусков со случайными начальными условиями, при
этом случайным образом выбиралось 100 пар узлов–отправителей и
узлов–получателей пакетов (если в сети менее 100 узлов, то все они
обменивались пакетами). Таким образом, общий размер выборки для
каждого набора параметров составляет 495 000 маршрутов.
На приведенных далее графиках указаны средние значения и гра-
ницы доверительных интервалов при уровне значимости 0,05.
Распределение опорных узлов.
Очевидно, что число и располо-
жение опорных узлов оказывает существенное влияние на эффек-
тивность протоколов маршрутизации по виртуальным координатам.
Чем больше опорных узлов, тем точнее виртуальные координаты ап-
проксимируют топологию сети и, следовательно, увеличивается доля
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2009. № 2 115
