Виртуальные координаты узла представляют собой вектор, элемен-
тами которого являются значения минимального числа элементарных
передач (hop) между данным узлом и фиксированным набором опор-
ных узлов. Опорные узлы отличаются от обычных только тем, что
периодически начинают процесс широковещательной передачи спе-
циальных сигнальных пакетов, а обычные узлы эти пакеты только
ретранслируют. Анализируя полученные сигнальные пакеты, все уз-
лы (как обычные, так и опорные) вычисляют набор значений длин
кратчайших путей между ними и опорными узлами.
Виртуальные координаты используются для вычисления виртуаль-
ного расстояния между узлами с помощью некоторой метрики. Про-
цесс маршрутизации заключается в последовательной минимизации
виртуального расстояния до узла–получателя пакета («жадная» марш-
рутизация). При обнаружении локального минимума (ситуация, при
которой очередной узел не имеет узла-соседа, расположенного бли-
же к узлу-назначению) протоколы используют различные варианты
бектрекинг-режима, которые полностью или с высокой вероятностью
гарантируют доставку пакета ценой увеличения длины пути.
Теоретический фундамент ВК-маршрутизации в основном скла-
дывается из методов теории графов и вложения метрических про-
странств, поскольку описанная процедура вычисления виртуальных
координат является частным случаем вложения Липшица метриче-
ского пространства, соответствующего связному неориентированному
графу сети. Данной проблеме посвящено множество теоретических
исследований, но цель настоящей работы заключается в повышении
эффективности протоколов ВК-маршрутизации способами, имеющи-
ми простую практическую реализацию и низкую алгоритмическую
сложность.
В первую очередь на характеристики протокола ВК-маршрутизации
влияют метрика виртуальных расстояний, а также число и располо-
жение (распределение) опорных узлов по площади покрытия сети. В
настоящей работе с помощью имитационного моделирования иссле-
дуется влияние этих факторов на эффективность маршрутизации и
рассмотрено несколько способов ее повышения:
•
целенаправленное распределение опорных узлов, а не случай-
ное;
•
использование информации о соседних узлах 2-го уровня;
•
выбор порядка и весовой функции для метрики виртуального
расстояния.
Модель сети и условия моделирования.
Рассмотрим беспровод-
ную многоячейковую сеть, состоящую из множества узлов
V
, общ ее
число которых
n
, при этом
n
b
из них являются опорными узлами
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2009. № 2 113
