В описанной процедуре п. 1–3 определяют правила приоритетов,
если несколько узлов в сети назначат себя опорными узлами с одина-
ковыми номерами. Очевидно, что подобные ситуации будут возникать,
так как узлы имеют только локальную информацию при принятии ре-
шения о назначении очередного опорного узла.
В п. 4 выполняется обновление соответствующего компонента век-
тора виртуальных координат по стандартной процедуре, принятой в
протоколах маршрутизации рассматриваемого типа.
Оптимизированный вариант алгоритма.
Из описания алгоритма
следует, что при принятии решения о назначении себя опорным узел
сравнивает свое число “голосов” с максимальным числом “голосов”
среди его соседей. Следовательно, если нет необходимости хранить
информацию о сетевом окружении для других задач (в частности, для
маршрутизации пакетов), то узлу достаточно в ходе локального обме-
на сигнальными пакетами запоминать информацию только о соседнем
узле, имеющем максимальное значение функции голосования. Тогда
требования к объему памяти значительно сокращаются, что будет по-
казано далее.
Примеры работы алгоритма.
На рис. 1,
а, б
наглядно показан ре-
зультат применения функций голосования
f
min
(
v, B
)
и
f
prod
(
v, B
)
для
выбора 16 опорных узлов в сети из примерно 2000 узлов со сред-
ней плотностью размещения 20 узлов. Опорные узлы обозначены с
указанием порядка их выбора. На рис. 1,
в, г
приведен результат для
сети примерно такого же масштаба, но с площадью покрытия в форме
круга.
В первую очередь обе функции голосования стремятся выбрать
максимально удаленные друг от друга узлы, т.е. находящиеся на пери-
ферии сети. Затем функция
f
min
(
v, B
)
задействует узлы из середины
области покрытия, приводя в результате к равномерному распределе-
нию опорных узлов. При использовании функции
f
prod
(
v, B
)
все опор-
ные узлы выбраны среди граничных.
Пример выбора 8 опорных узлов в сети с низкой плотностью при-
веден на рис. 2.
Оценка сложности алгоритма.
Выполним анализ сложности по
времени и памяти распределенной реализации алгоритма.
Очевидно, что временные затраты на выполнение алгоритма будут
зависеть от периода передачи сигнальных пакетов
t
b
(см. выражение
(2)), который является параметром настройки протокола маршрутиза-
ции и определяет скорость его реакции на изменения в топологии сети,
поэтому
t
b
следует рассматривать как постоянную величину, которая
не зависит от размерности задачи.
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2008. № 4 23
