Из выражения (13) следует, что требования к памяти на выполне-
ние алгоритма выбора опорных узлов протокола LCR линейно зависят
от общего числа узлов
n
и квадратично (кубично — при размещении
узлов в трехмерном объеме) от диаметра сети
d
, поэтому требование
масштабируемости не выполняется.
Выводы.
Предложенный алгоритм предназначен для автоматиче-
ского выбора произвольного числа опорных узлов как при начальной
инициализации сети, так и при возможном выходе из строя опорных
узлов в процессе эксплуатации. Указанные варианты функций голосо-
вания позволяют получить равномерное распределение опорных узлов
по площади покрытия сети или распределение по периметру (границе)
сети.
Применение одной из предложенных функций голосования дает
результат, аналогичный полученному с помощью алгоритма автома-
тического выбора опорных узлов [4]. Главное отличие алгоритмов за-
ключается в величине оценок сложности, которые показали:
•
предложенный в настоящей работе алгоритм является оптималь-
ным по времени и памяти;
•
алгоритм из работы [4] является оптимальными по временн ´ой
сложности, а сложность по памяти в значительной степени за-
висит от масштаба сети.
Оптимизированная версия алгоритма может использоваться в при-
ложениях, в которых необходимо только выбрать опорные узлы с опре-
деленным распределением по площади покрытия сети.
Таким образом, предложенный алгоритм обладает гибкостью для
получения различного вида распределений опорных узлов по сети и
является полностью масштабируемым в отличие от существующих
аналогов, поэтому может быть эффективно использован в беспровод-
ных многоячейковых сетях крупных размеров.
СПИСОК ЛИТЕРАТУРЫ
1. F o n s e c a R. Beacon vector routing: scalable point-to-point routing in wireless
sensornets // Proceedings of the 2nd Symposium on Networked Systems Design and
Implementation. – Boston, Massachusetts, USA: 2005.
2. C a r u s o A. GPS free coordinate assignment and routing in wireless sensor networks
// Proceedings of the 24th Annual Joint Conference of the IEEE Computer and
Communications Societies INFOCOM 2005. – Vol. 1. – 2005. – P. 150–160.
3. C a o Q. A scalable logical coordinates framework for routing in wireless
sensor networks // Proceedings of the 25th IEEE International Real-Time Systems
Symposium. – 2004. – P. 349–358.
4. C a o Q., A b d e l z a h e r T. Scalable logical coordinates framework for routing
in wireless sensor networks / // ACM Transactions on Sensor Networks. – 2006. –
Vol. 2. No. 4. – P. 557–593.
28 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2008. № 4
