опорных узлов должно выполняться автоматически с помощью неко-
торого распределенного (децентрализованного) алгоритма, сложность
(по памяти) которого не должна зависеть от общего числа узлов в сети
для обеспечения масштабируемости системы.
В протоколе Beacon Vector Routing [1] в качестве опорных исполь-
зуется
r
узлов, случайно выбранных в сети. Далее в процессе марш-
рутизации задействуются только
k
из них (
k
≤
r
), которые наиболее
близко расположены к узлу-назначению. Такая схема отличается про-
стотой, но протокол маршрутизации оказывается чувствительным к
полученному случайным образом распределению опорных узлов, по-
этому приходится применять слишком большое общее число опорных
узлов
r
(порядка нескольких десятков), что увеличивает накладные
расходы на хранение и передачу виртуальных координат.
В протоколе Virtual Coordinate Assignment Protocol [2] сделана по-
пытка создать алгоритм, который автоматически будет выбирать в ка-
честве опорных узлы, находящиеся на периферии сети. Однако пред-
ложенный алгоритм рассчитан на выбор только трех опорных узлов,
в то время как на практике необходимо четыре и более.
В первоначальной версии протокола Logical Coordinate Routing
(LCR) [3] предполагалось, что опорные узлы будут вручную разме-
щены на границе (по периметру) сети на этапе развертывания систе-
мы. Ручное назначение опорных узлов усложняет настройку крупной
сети, а в некоторых приложениях и вовсе невозможно, поэтому в по-
следующей работе по LCR [4] разработан алгоритм автоматического
выбора опорных узлов, распределяющий опорные узлы по периферии
сети. Недостатком алгоритма [4] является зависимость сложности по
памяти от масштаба сети.
Таким образом, в известных работах (кроме работы [4]) распре-
деленные алгоритмы не позволяют выбрать произвольное наперед за-
данное число опорных узлов в беспроводной многоячейковой сети. В
настоящей работе указанный недостаток устранен и предложен алго-
ритм для автоматического выбора опорных узлов как при начальной
инициализации сети, так и при возможном выходе из строя одного
или нескольких опорных узлов в процессе эксплуатации системы. В
зависимости от используемой функции голосования результатом ра-
боты алгоритма являются равномерно распределенные по сети или
находящиеся на периферии сети опорные узлы. При этом сложность
алгоритма ниже по сравнению с известным аналогом из работы [4].
Постановка задачи.
Рассмотрим беспроводную многоячейковую
сеть из множества узлов
V
, общее число которых равно
|
V
|
=
n
. Счи-
таем, что топология сети не изменяется, узлы случайно и равномерно
распределены на двумерной плоскости, площадь покрытия сети равна
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2008. № 4 17
