Просмотр исходного текста страницы Адаптация распределенного алгоритма балансировки трафика в сенсорной сети для увеличения времени жизни сети

И.В. Воронин, М.Д. Хоменко

Институт проблем лазерных и информационных технологий РАН

140700, Московская область, г. Шатура, ул. Святоозерская, д.1

== Введение ==

В связи с развитием электроники и беспроводной связи в XXI веке появилась возможность развития беспроводных распределенных сенсорных сетей (РСС). РСС отличаются от обычных сетей ограниченным энергоресурсом, низкой вычислительной мощностью, необходимостью более плотного расположения и низкой ценой одного узла. Эти отличия от других сетей (например, сотовых) определяют новые цели и задачи применения РСС. Беспроводные сенсорные сети получили широкое применение во многих сферах деятельность человека, и поэтому им сейчас уделяется огромное внимание как со стороны научного сообщества, так и промышленности. На данный момент опубликовано или находится в стадии составления множество научных работ по исследованию проблем установки и функционирования РСС.
 
[[Файл:Схема работы РСС.jpg|thumb|right|Рис. 1. Принципиальная схема работы беспроводной сенсорной сети]]

Типичная сенсорная сеть состоит из множества дешевых, автономных, многофункциональных узлов (мотов), которые распределены в зоне мониторинга. Каждый узел состоит из набора блоков, таких как: сенсор, используемый для получения данных от окружающей среды, блок приема-передачи данных, микроконтроллер для обработки и управления сигналами и источник энергии. Узел обычно питается от автономной батареи с ограниченным энергоресурсом, что приводит к значительным ограничениям в энергопотреблении. Обслуживание сенсорных узлов, замена батарей питания требуют значительных затрат, особенно когда узлы расположены в труднодоступных местах, так что большинство сенсорных сетей работает до истощения батареи и является не подлежащим обслуживанию. Это свойство сенсорных сетей является очень важным при разработке алгоритмов работы и проектировании установки РСС.

Как правило, сенсорные узлы оборудуются однотипными устройствами с определенным набором функций. После установки в процессе эксплуатации сенсорные узлы должны сами организоваться в коммуникационную сеть, где каждый узел использует только те функции, которые необходимы для решения поставленной задачи. Маршрутизация так же происходит в автоматическом режиме. Помимо первичной маршрутизации требуется еще регулярное перестроение сети, потому что устройства часто могут выходить из строя по причинам, связанным с внешними или внутренними факторами. 
Работа каждого сенсорного узла направлена на измерение различных параметров среды, например температуры, давления, освещенности и других. Такое разнообразие параметров влечет за собой различные сферы применения, начиная с мониторинга окружающей среды и заканчивая военным применением. Сенсорные сети выполняют различные задачи, которые можно грубо разделить на две категории. Первая категория задач связана с детекцией событий, которые происходят очень редко, но требуют немедленного оповещения и/или обнаружения местонахождения. Во вторую категорию (мониторинг) входят задачи непрерывного измерения какой-либо величины в течение длительного промежутка времени. Здесь время задержки может быть равно характерному времени изменения измеряемого параметра.
 
Существует множество способов экономии электроэнергии узлов. В обзоре [1] приведена их классификация, представленная на рисунке 2. Все способы сохранения можно разделить на три большие группы. К первой группе относится сохранение энергии при помощи циклов работы, основанное на количестве передаваемой информации и на мобильности. К циклам работы относят контроль топологии и управление энергопотреблением. Контроль топологии направлен на использование или уменьшение избыточных связей в сети в целях экономии ресурса. Управлять потреблением можно путем применения различных энергосберегающих MAC-протоколов и режимов работы устройств. Второй класс способов сохранения энергоресурса основан на количестве передаваемой информации, а также на получении этой информации экономичными способами. Энергия, потраченная на обработку информации, несравнимо меньше   требующейся для ее передачи, поэтому используется внутрисетевая обработка данных, сжатие или предсказание данных. Также используются мобильные стоки или ретрансляторы для экономии электроэнергии узлов сенсорных сетей.
 
В данной работе рассматривается разработка экономичных алгоритмов маршрутизации систем мониторинга, проверка разработанных алгоритмов в плане их применения на предприятии. В первой части описываются известные алгоритмы маршрутизации. Во второй части описывается разработанный алгоритм маршрутизации, показан способ продления времени работы при помощи этого алгоритма, оценено реальное время работы сенсорной сети без обслуживания. Эта оценка экспериментально проверена на реальной сенсорной сети и позволяет судить о затратах, связанных с обслуживанием распределенной сенсорной сети.
 
== Существующие методы маршрутизации в РСС ==

Существующие методы маршрутизации можно разделить на несколько категорий [2]: прямая, иерархическая маршрутизация и маршрутизация в зависимости от географического положения. Прямая маршрутизация подразумевает передачу сообщений от узла к узлу в сети, где каждый узел выполняет одинаковую функцию передачи и/или ретрансляции, в отличие от иерархической, где выделяется узел сбора и обработки информации. Минус прямой маршрутизации в том, что сети, собирающие информацию с какой-то области, будут посылать множество избыточной информации, особенно при значительной плотности сенсорной сети. Для того чтобы избежать избыточности информации, используют специальные алгоритмы, направленные на получение информации не от узлов, а от определенной области сети. Например в работе [3] описан алгоритм SPIN (Sensor Protocols for Information via Negotiation), где базовая станция посылает запрос к определенному региону сенсорной сети. Получив запрос, узлы области выполняют требование запроса, локально обмениваются данными и посылают обратно обобщенный ответ.
 
При иерархической же маршрутизации для сбора и обработки требуется использовать узлы с большим запасом энергии, что зачастую неприемлемо ввиду однородности используемых приборов или других трудностей, хотя этот способ и позволяет экономить на передаче уже обработанных данных значительно меньшего объема. Чтобы не использовать специализированные узлы, существуют различные технологии. Например, в работе [4] описана технология LEACH (Low-Energy Adaptive Clustering Hierarchy), при которой функцию сбора принимает поочередно несколько узлов сенсорной сети, выбираемых по определенному алгоритму, тем самым распределяя нагрузку узла сбора.
 
Маршрутизация в зависимости от географического положения также еще называется геометрическая маршрутизация, потому что для нахождения маршрута используется геометрическое направление на базовую станцию. При такой маршрутизации каждый узел передает сообщение своему соседу, у которого географическое положение ближе к стоку. Помимо маршрутизации в географических координатах существует маршрутизация по виртуальным координатам [5], которая выстраивается не только в зависимости от реального положения узла, но и учитывает естественные неровности поверхности, препятствия, уровень канала передачи и др.

Также существует многопотоковая маршрутизация, где доставка сообщения от одного узла возможна по нескольким путям. В последнее время появляется большое количество работ по маршрутизации по запросу у базовой станции, обзор которых можно посмотреть в работах [2,5]. Первые работы по маршрутизации (например, [6,7]) были направлены на нахождение кратчайшего пути, поддержание его с учетом плохого канала и выхода из строя узлов. Однако узлы, расположенные на кратчайшем расстоянии, часто быстро истощаются, что приводит к обрывам связи и уменьшению времени жизни сети, которое часто понимается как время жизни первого вышедшего из строя узла. Поэтому в последних работах [8-11] формулируется задача максимизации времени жизни сенсорной сети, которая решается тем или иным методом линейного программирования. 

== Алгоритм маршрутизации с балансировкой трафика ==

Сеть представляется как граф G(N,M) c N узлами и M гранями, который демонстрирует набор существующих узлов и возможные связи между ними. Каждый i-й узел изначально имеет запас энергии E<sub>i</sub>. Каждая грань ij имеет цену e<sub>ij</sub>, которая соответствует энергии для  передачи одного пакета данных от узла i к узлу j. Считается, что есть K направлений передачи, а информация генерируется со скоростью Q<sub>c</sub> и передается по каналу связи ''c'' со скоростью q<sub>c</sub>.
 
Время жизни каждого узла будет равняться в такой системе:

[[Файл:Время жизни каждого узла сети.png]]

Тогда время жизни всей системы определим как:

[[Файл:Время жизни всей системы.png]]

Задача максимизации времени жизни будет выглядеть так:

Maximize Т<sub>sys</sub>. 

== Список литературы ==

[1] Giuseppe Anastasi, Marco Conti, Mario Di Francesco, Andrea Passarella. «Energy conservation in wireless sensor networks: A survey», Ad Hoc Networks 7 (2009), pp. 537–568.

[2] Jamal N. Al-Karaki, Ahmed E. Kamal. «Routing techniques in wireless sensor networks: a survey», Wireless Communications, vol. 11, №6 (2004), pp. 6 – 28.

[3] J. Kulik, W.R. Heinzelman and H. Balakrishnan. «Negotiation-Based Protocols for Disseminating Information in Wireless Sensor Networks», Wireless Networks, vol. 8, (2002), pp. 85-169.

[4] Heinzelman W., Chandrakasan A., Balakrishnan H. «Energy-efficient communication protocol for wireless microsensor networks» // Proceedings of the 33rd Hawaii international conference on system sciences. Maui (USA), 2000. P. 8020–8029.

[5] Баскаков С.С. «Маршрутизация по виртуальным координатам», диссертация кандидата наук (2011), 218 стр.

[6] A. Michail and A. Ephremides. «A distributed routing algorithm for supporting connection-oriented service in wireless networks with time-varying connectivity». In Proceedings Third IEEE Symposium on Computers and Communications, ISCC'98, pages 587-591, Athens, Greece, June 1998.

[7] K. Arisha, M. Youssef, M. Younis. «Energy-aware TDMA-based MAC for sensor networks», in: Proc. IEEE Workshop on Integrated Management of Power Aware Communications, Computing and Networking (IMPACCT 2002), New York City, USA, May 2002.

[8] Chang J. and Tassiulas L. «Fast approximate algorithms for maximum lifetime routing in wireless ad-hoc networks». In: IFIP-TC6 Networking 2000, LNCS, Vol. 1815. Springer.

[9] Arvind Sankar and Zhen Liu. «Maximum Lifetime Routing in Wireless Ad-hoc Networks», INFOCOM 2004. Twenty-third Annual Joint Conference of the IEEE Computer and Communications Societies, vol.2, pp. 1089 – 1097.
 
[10] Ritesh Madan and Sanjay Lall. «Distributed Algorithms for Maximum Lifetime Routing in Wireless Sensor Networks», Global Telecommunications Conference, 2004. GLOBECOM '04. IEEE, Vol.2, pp. 748 – 753, 29 Nov - 3 Dec 2004.

[11] Park J., Sahni S. «An online heuristic for maximum lifetime routing in wireless sensor networks» // IEEE transactions on computers, 2006, vol. 55, no. 4, рр. 1048–1056.

[[Категория:WSN]]