Во многих задачах в области БСС необходимо наличие в сети
определенного числа опорных узлов (beacon, landmark, anchor). Ак-
туальной задачей является маршрутизация пакетов. Для решения этой
задачи с помощью одного из наиболее современных методов — геогра-
фической маршрутизации по виртуальным координатам узлов [1–4] —
требуются опорные узлы.
Виртуальные координаты узла представляют собой вектор, элемен-
тами которого являются значения минимального числа элементарных
передач (hop) между данным узлом и фиксированным набором опор-
ных узлов. Опорные узлы отличаются от обычных только тем, что
периодически начинают процесс широковещательной передачи спе-
циальных сигнальных пакетов, а обычные узлы эти пакеты только
ретранслируют. Анализируя полученные сигнальные пакеты все узлы
(как обычные, так и опорные) вычисляют набор значений длин крат-
чайших путей между ними и опорными узлами. Этот набор называется
виртуальными координатами узла.
Виртуальные координаты используются для вычисления виртуаль-
ного расстояния между узлами с помощью некоторой метрики (напри-
мер, евклидовой нормы). Заметим, что виртуальное расстояние между
узлами не имеет явной физической интерпретации из-за неортого-
нальности системы виртуальных координат. Процесс географической
маршрутизации заключается в последовательной минимизации вирту-
ального расстояния до узла-назначения (получателя пакета). При об-
наружении локального минимума (ситуация, при которой очередной
узел не имеет узла-соседа, расположенного ближе к узлу-назначению)
протоколы используют различные варианты бектрекинг-режима, ко-
торый полностью или с высокой вероятностью гарантирует доставку
пакета ценой увеличения длины пути.
В первую очередь на эффективность протокола маршрутизации по
виртуальным координатам влияют выбранная метрика виртуальных
расстояний, а также число и расположение (распределение) опорных
узлов на площади покрытия сети. В настоящей работе рассматривается
вопрос размещения опорных узлов.
Проблема выбора опорных узлов заключается в поиске такого их
размещения, при котором как можно большая часть пакетов будет до-
ставлена в режиме минимизации виртуального расстояния (greedy –
“жадная” маршрутизация), так как найденные в этом режиме марш-
руты имеют длину, близкую к оптимальной (кратчайшей). При этом
желательно задействовать как можно меньшее число опорных узлов
для снижения накладных расходов на хранение и передачу служеб-
ной информации. Кроме того, в самоорганизующейся сети назначение
16 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2008. № 4
