ближайшими соседями друг друга. Вследствие этого будут локальные
минимумы, выход из которых приведет к существенному увеличению
длины маршрута, что показано на рис. 1,
б
для сети с аналогичны-
ми топологией и расположением опорных узлов: размер сети
50
×
50
(2 500 узлов), опорные узлы находятся в точках
(1
,
1)
,
(50
,
1)
,
(25
,
25)
и
(25
,
50)
. На рис. 1,
б
для каждого узла сети приведены значения вир-
туального расстояния, вычисленного по виртуальным координатам с
помощью евклидовой нормы, до узла-назначения в точке
(1
,
50)
. Вид-
но, что образовано несколько областей локальных минимумов и воз-
можно движение пакетов в неправильном направлении, так как узлы
в точках
(1
,
50)
и
(50
,
50)
неразличимы для алгоритма маршрутизации
из-за совпадения виртуальных координат.
Изменением распределения опорных узлов по сети можно значи-
тельно улучшить ситуацию. На рис. 1,
в
приведена топология сети,
как на рис. 1,
а
, но в качестве опорных выбраны узлы в точках
(1
,
1)
,
(5
,
1)
,
(1
,
5)
и
(5
,
5)
. В результате в сети отсутствуют узлы с одина-
ковыми виртуальными координатами и функция расстояния до узла-
назначения не имеет локальных минимумов (рис. 1,
г
).
В большинстве практических ситуаций невозможно вручную под-
бирать «хорошее» распределение опорных узлов в конкретных усло-
виях эксплуатации, поэтому рассматриваются следующие типы рас-
пределения опорных узлов:
•
случайное распределение по сети;
•
равномерное распределение по сети на максимальном расстоя-
нии относительно друг друга;
•
распределение по периферии (на границе) сети.
Случайный выбор опорных узлов является наиболее простым в ре-
ализации и часто используемым вариантом (например, [1]). Но в этом
случае нет гарантии, что опорные узлы будут «хорошо» распределены
по площади покрытия сети, поэтому при малом
n
b
протокол марш-
рутизации оказывается чувствителен к полученному распределению
опорных узлов. Тогда приходится увеличивать общее число опорных
узлов, что нежелательно.
Задействовать в качестве опорных узлы, находящиеся на границе
сети, предлагается во многих работах (например, [2, 3]), при этом в
работах [2, 5] предложены алгоритмы автоматического выбора произ-
вольного наперед заданного числа опорных узлов. Результатом работы
алгоритмов являются равномерно распределенные по сети или нахо-
дящиеся на периферии опорные узлы. Примеры целенаправленного
назначения опорных узлов показаны на рис. 2 с обозначением их по-
рядковых номеров.
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2009. № 2 117
