«Реализация распределенного алгоритма балансировки трафика в сенсорной сети для увеличения времени жизни И.В. Воронин, М.Д. Хоменко...»

Реализация распределенного алгоритма балансировки трафика в

сенсорной сети для увеличения времени жизни

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

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

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

Аннотация

Сенсорные сети все бол ьше занимают сво е место в прил ожениях

мониторинга ра зличных мест и событий. Особенность ю т аких

сетей является необходимость экономить огр аниченный заряд

бат ар еи. Один из способов эко номии – это эфф ективна я

мар шрутизация. Рабо та посвящ ена распред ел енному алгоритму мар шрутизации дл я бал ансировки тра фика в сенсорной сети. Он позволяет продлить время жизни сенсорной сети мо нитор инга, гд е ва жна информация ка ждого узл а.

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

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

Рисунок 1: Построение сети, путем опроса Ст андартный а лгоритм по зволяет ст роить маршрут на о сновании запро сов и ответов. Координато р с ет и (1, рис 1)- отправляет широковещательный запро с HE LLO и принимает от вет ы от Роу теро в (2) Каждый роутер, т акже отправляет широко вещат ельный запро с и полу чает ответы от со с едних уср ойств, это могут быть дру гие роут еры или конечные у ст ройст ва (3). На о снове принятых ответов (силе сигна ла, времени ответ а) выст раивает ся коо рдинатором т аблица мар шрутизации на каждом роутер е. Да лее выбо р мар шрут а о суще ствляет ся в ст андартном а лгоритм е - пу тем опр ед еления ве сового графа с минимальным суммарным значением.

Как пр авило, с енсор ные у злы оборуду ют ся од нотипными уст р ойствами с опр еделенным набором функций. По сле у ст ановки в проце сс е эксп луат ации с енсор ные узлы д олжны с ами организоват ься в комму никационную с еть, где каждый узел использует только те функции, которые необходимы для решения по ст авленной задачи. Мар шрутизация т ак же происходит в автоматиче ском режиме. Помимо первичной мар шрутизации т ребует ся еще регулярно е пере ст ро ение с ети, потому что уст р ойства часто могут выходит ь из ст роя по причинам связанным с внешними или внут ренними факто рами.

Работ а каждого с ен сорного узл а направлена на измерение различных парамет ро в среды, н апример температуры, давл ения, о свещенно сти и других. Тако е разнообразие парамет ров влечет за собо й различны е с феры применения, начиная мониторингом окружающей ср еды, заканчивая во енными применениями.

Сенсорные с ет и выполняют р азличные задачи, котор ые можно грубо разделить на две категор ии. Первая категория задач связана с детекцией событий, котор ые прои сходят очень редко, но т ребуют немедл енного оповещения и/или обнаружения ме стонахождения. Во вто рую кат егорию (монито ринг) вход ят задачи непрерывного измерения, какой либо величины в течение д лительного промежутка вр емени. Зд е сь время задержки может быть равно характерному вр емени и змен ения изм еряемого парамет ра. Мониторинг может проводиться точечно, либо по какой-либо площади. При точечном измерении о сно вная часть у злов играют роль передат чиков, и лишь не значительная часть нодов непо сред ственно о сущ е ствляет монито ринг.

Рисунок 2: Кл ассификация способов сохранения энергии Суще ст вует множе ство спо собо в экономии элект ро энергии узлов. В обзоре приведена их классификация, предст авленная на рису нке

1. Вс е спо собы сох ранения можно разделить на т ри большие группы

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

В данной работе р ассмат р ивает ся разр аботка экономных алго ритмо в мар шру тизации си стем мониторинг а, провер ке разр абот анных а лгор ит мов в применение на пр едприятии. В первой с екции описывают ся изве стные а лгоритмы маршрутизации. Вторая описывает разр абот анный алгоритм маршрут изации, показан спо соб продления времени работы при помощи этого а лгоритма, оцен ено ре ально е время работы с енсорно й с ети бе з обслуживания. Эт а оценка экспер имент а льно провер ена на ре альной с енсо рной сети и позволяет судить о зат рат ах связанных с обслужи ванием распр еделенной с енсорной с ети.

1. Существующие методы маршрутизации в РСС Суще ст вующи е методы мар шрутизации можно разд елить на не сколько кат егорий прямая, иерар хиче ская и маршрут изация в зависимо сти от географиче ского положения. Прямая маршрутизация подр азумевает перед ачу соо бщений от узла к узлу в с ети где, каждый у зел выполняет од инаковую функцию пер едачи и/или рет р анс ляции, в отличие от иерар хиче ско й, где выделяет ся узел с бора и обр аботки информации. Минус прямой маршрут изации в том, что с ети собирающие информацию с какой-то области будут по сылать множе ство избыточной информации, о собенно при значительной плотно сти с енсо рной с ети. Для то го что бы избежать изб ыточно сти информации использу ют специ альные алгоритмы, направленные на получение информации не от узлов, а от опр ед еленной области сет и. Например, в раб оте о пис ан алгоритм SPIN 1, где б азовая ст анция по сы лает запро с к определенному региону с енсорной с ети. Получив запро с, у злы област и выполня ют т ребо вание запро с а, локально обменивают ся данными и по сылают обратно о бобщенный ответ.

При иерархиче ско й же мар шру тизации для сбор а и обработки т ребует ся использовать узлы с большим запасом энер гии, что хотя и позволяет экономить на передачи уже обр абот анных данных значительно меньшего объема зачасту ю не приемлемо ввиду од но родно сти используемых приборо в или других т рудно ст ей. Д ля что бы не использоват ь специа лизиро ванные узлы суще ст вуют не сколько т ехнологий. Например, в работе опис ана технология LE ACH 2, когда функцию сбора пр инимает поочередно не сколько узло в с енсор ной с ети выбираемых по опред еленному а лгор ит му, тем с амым распред еляя нагрузку узла с бора.

Мар шру тизация в зависимо сти от географиче ского положения т ак же еще называет ся геомет риче ская маршрутизация, потому что для нахождения маршрут а использует ся геом ет риче ско е напр авление на базовую ст анцию.

При т акой маршрутизации каждый узел пер едает сообщение сво ему со седу, у которо го географиче ско е положени е ближе к стоку. Помимо маршрутизации в географиче ских коо рдинат ах суще ствует мар шрутизация по виртуа льным коо рдинат ам , котор ые выст раивают ся не только в зави симо ст и от ре ального положения узла, а т ак же и учитывают е сте ственные неровно сти поверхно сти, препят ствия, уровень кана ла пер едачи и др.

SPIN - Sensor Protocols for Information via Negotiation LEACH - Low-Energy Adaptive Clustering Hierarchy Так же су ще ствует мно го потоковая маршрутизация, где до ст авка сообщения от одно го узла возможна по не скольким путям. В по следнее время появляет ся большо е количе ст во р абот по мар шру тизации обзо р, котор ых можно по смот реть в работ ах по запро су у базо во й ст анции. Пер вые работы (н апример ) по мар шру тизации были напр авлены на нахождение кр атчайшего пути, подд ержание его с учетом плохого канала и выхода из ст р оя у злов.

Однако узлы р асположенные на кр атчайшем расстоянии часто быст ро истощают ся что пр иводит к обрывам связи и уменьшени ю вр емени жизни с ети, кото ро е часто понимает ся, как время жизни первого вышедшего из ст роя у зла. По этому в по следних работ ах }