Рис. 1. Примеры “плохого” (
а, б
) и “хорошего” (
в, г
) распределения опорных
узлов:
а, в
— топология сети;
б, г
— расстояние до узла–назначения
пакетов, доставленных в режиме минимизации расстояния, но при
этом накладные расходы на хранение и передачу служебной инфор-
мации равны
O
(
ρn
b
)
и
O
(
n
b
)
соответственно. Поэтому более важным
с практической точки зрения является способ назначения опорных
узлов из исходного множества
V
, так как «хорошее» распределение
опорных узлов позволяет значительно повысить эффективность «жад-
ной» маршрутизации при фиксированном
n
b
. Продемонстрируем это
на примерах.
На рис. 1,
а
показана топология сети из 25 узлов в виде решетки
размером
5
×
5
c 4 опорными узлами, указаны адреса узлов и их вир-
туальные координаты. Опорными назначены узлы с адресами
1
,
5
,
13
и
23
, находящиеся в точках
(1
,
1)
,
(5
,
1)
,
(3
,
3)
и
(3
,
5)
соответственно.
Такое распределение опорных узлов является неудачным, так как в
сети есть несколько пар узлов (например, узлы
17
и
19
,
21
и
25
), кото-
рые получили одинаковые виртуальные координаты, но не являются
116 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2009. № 2
