ЭНЕРГОЭФФЕКТИВНЫЙ МНОГОПУТЕВОЙ ПРОТОКОЛ МАРШРУТИЗАЦИИ В БЕСПРОВОДНОЙ СЕНСОРНОЙ СЕТИ, ОСНОВАННЫЙ НА РЕШЕТКЕ С ИСПОЛЬЗОВАНИЕМ НЕЧЕТКОГО ПОДХОДА
Аннотация и ключевые слова
Аннотация (русский):
Рассмотрены преимущества (возможность использования нескольких альтернативных путей для передачи данных к одному получателю) и недостатки (неспособность сбалансировать потребление электроэнергии) многопутевых протоколов маршрутизации в беспроводной сенсорной сети. Главной целью при разработке предлагаемого многопутевого протокола маршрутизации стало обеспечение его энергоэффективности. Основная идея разработки эффективной беспроводной сенсорной сети - разделение ее на решетки. Концепция, названная многопутевой на основе решетки, реализуется в ходе четырех этапов: формирование решетки; обнаружение соседей; передача данных; обновление энергии. Формирование решетки позволяет определить минимальную сквозную задержку между узлом-источником и узлом-получателем в сети. Предлагаемая техника нечеткого множества обеспечивает выявление энергетической эффективности узлов в беспроводной сенсорной сети. На заключительном этапе протокол находит оптимальный путь передачи данных. Имитационное моделирование системы проведено в программе MatLab. Предложенный протокол маршрутизации позволяет экономить энергию источников питания узлов сети, что способствует увеличению срока службы беспроводной сенсорной сети и обеспечивает качество обслуживания пользователей.

Ключевые слова:
беспроводная сенсорная сеть, многопутевая маршрутизация, протокол маршрутизации, энергосбережение, техника нечеткого множества
Текст
Введение В настоящее время все большее распространение получают сети связи с гетерогенной топологической структурой, под которой понимается наличие в системе передачи и обработки информации проводной и беспроводной составляющей. Широкое использование беспроводных составляющих приводит к усложнению топологических структур подобных сетей и, как следствие, к увеличению факторов, влияющих на эффективность определения и поддержания актуальности оптимальных, по заданным критериям, маршрутов передачи данных. Последние достижения в области беспроводных сенсорных сетей (БСС) привели к созданию новых протоколов маршрутизации, специально предназначенных для сенсорных сетей. Одна из задач при разработке таких протоколов - наличие сведений об уровне энергии узлов. В целом алгоритмы маршрутизации пакетов используются для обмена сообщениями между сенсорными узлами, которые находятся вне определенного радиодиапазона, тогда как обмен сообщениями между сенсорами в рамках конкретного радиодиапазона может осуществляться с использованием одного перехода. Однако один переход в сенсорной сети не рекомендуется из-за затрат энергии при большой дальности передачи. Все это обусловило появление многоскачковой передачи, при которой пакеты данных передаются от источника к месту назначения через множество промежуточных узлов или маршрутизаторов и затраты энергии на передачу данных на малые расстояния значительно меньше. Общая цель всех методов маршрутизации в БСС - увеличение надежности и продление срока службы сенсорной сети без влияния на время и качество доставки данных. Существует много способов классификации протоколов маршрутизации. Почти все протоколы маршрутизации в БСС могут быть классифицированы на основе сетевой структуры и на основе работы протокола [1]. В БСС протоколы маршрутизации классифицируют по трем направлениям - в соответствии с установленными путями маршрутизации, сетевой структурой и функционированием протокола (рис. 1). Рис. 1. Классификация протоколов маршрутизации в беспроводной сенсорной сети Как видно из рис. 1, сетевая структура может быть датацентрической, иерархической и на основе местоположения сенсорных узлов. В датацентрической маршрутизации всем узлам, как правило, назначаются равные роли или функциональности. Приемник посылает запросы в отдаленные районы и ждет данные от сенсоров, расположенных в выбранной области. Первым датацентрическим протоколом был протокол SPIN, который устраняет избыточные данные и экономит энергию путем согласования данных между узлами в БСС. В иерархической маршрутизации каждый узел в сети имеет свои собственные роли и обязанности. Узлы с высоким уровнем энергии используются для обработки и отправки данных, с низким - для детектирования окружающей среды. Вследствие этого создается иерархия низко- и высокоэнергетических узлов. Создание кластеров и присвоение специальных задач головным кластерным узлам может влиять на масштабируемость, срок службы и эффективность использования энергии в сети. Иерархическая маршрутизация является двухуровневой, где один уровень используется для выбора головного кластерного узла, а другой - для маршрутизации. Протокол иерархической кластеризации с адаптивным низким энергопотреблением, протокол LEACH, является одним из наиболее популярных иерархических алгоритмов маршрутизации для БСС. В протоколах, основанных на местоположении, расположения сенсорных узлов используются для маршрутизации данных в сети. Большинство протоколов маршрутизации в БСС требуют информацию о местоположении сенсорных узлов, на основе которой может быть рассчитано расстояние между двумя конкретными узлами, для того чтобы оценить затраты энергии. Местоположение можно определить и с помощью технологии GPS-отслеживания, поскольку информация о местоположении узлов, пространственно развернутых в некоторой области, может быть использована при маршрутизации данных энергетически эффективным способом. Протоколы маршрутизации БСС подразделяются также на многопутевые, на основе запросов, на основе согласования, на основе качества обслуживания, последовательные и непоследовательные, в зависимости от работы протокола с разработкой компромиссов между экономией энергии и экономией затрат на соединение. Предлагаемый протокол маршрутизации с сохранением и балансировкой энергии позволяет экономить энергию источников питания узлов сети, что способствует увеличению срока ее службы. Состояние проблемы Y.-H. Wang et al. [2] предложили протокол маршрутизации HMRP - иерархический многопутевой протокол маршрутизации, представляющий собой уровневую сеть, в которой существуют многопутевые маршруты к приемному узлу через некоторые передающие узлы. Каждый узел определяет свои родственные узлы-кандидаты для передачи детектированных данных к приемнику. С помощью родственных кандидатов сенсорный узел может посылать данные каждый раз по новому маршруту. Протокол позволяет передающим узлам объединять все полученные пакеты в течение короткого периода времени и передавать к следующему узлу только один объединенный пакет. Механизм объединения данных содержится в узлах отдельно от оконечных узлов, что уменьшает потребление энергии в сети. Протокол увеличивает срок службы сети, в отличие от кластерных или древовидных протоколов. Основное преимущество протокола HMRP заключается в том, что он уменьшает загрузку маршрута в сети путем распределения потребления энергии. Протокол HMRP сохраняет не всю информацию о пути - он сохраняет только таблицу информации о кандидатах, а также поддерживает все позиции приемного узла. B. Yahya и J. Ben-Othman [3] предложили надежный и энергоэффективный многопутевой протокол маршрутизации - REER. Свою основную цель при разработке данного протокола авторы видели в предсказании лучшего следующего перехода путем фазы проектирования пути с помощью остаточной энергии, доступного размера буфера узла и отношения сигнала к шуму. Существуют два способа распределения трафика. Первый включает в себя один путь для передачи сообщения данных. Если задержка канала (пути) падает ниже порогового значения, то он переходит на следующий альтернативный путь. Второй способ включает в себя дробление передаваемого сообщения на количество сегментов равного размера. Эти сегменты основаны на кодах прогрессивной коррекции ошибок и передаются по нескольким путям одновременно. Многопутевую маршрутизацию, наряду с технологией прогрессивной коррекции ошибок, используют для восстановления вышедших из строя узлов, не задействуя сеть глобального распространения для обнаружения пути. В сенсорной сети эта концепция имеет большое значение потому, что распространение данных будет сокращать срок службы сети. С помощью сообщений HELLO и RREQ устанавливается путь между приемным узлом и узлом-источником. Затем периодически передается сообщение KEEPALIVE, чтобы удерживать несколько путей в рабочем состоянии. Приемный узел инициирует этап обнаружения пути. K.-Y. Shin et al. [4] был предложен событийный протокол REAR - надежный протокол маршрутизации с осведомленностью об энергии. Протокол работает в основном на платформе реальной сенсорной сети и поддерживает многопутевые маршруты. Это позволяет каждому сенсорному узлу подтвердить успешность передачи данных к узлу датчика назначения, т. е. обеспечивается передача пакетов с подтверждением получения данных. Протокол подсчитывает остаточную емкость энергии каждого сенсорного узла для создания надежных путей маршрутизации от источника к месту назначения. Узел источника транслирует сообщение с запросом на многопутевой маршрут, чтобы найти маршрут к месту назначения. Узел, получивший это сообщение, проверяет свой текущий уровень энергии и направляет сообщение на следующий подходящий узел. Узлы с бóльшим уровнем энергии будут пересылать это сообщение быстрее, чем узлы с мèньшим уровнем энергии. Следовательно, с точки зрения энергоэффективности при построении пути маршрутизации от источника к месту назначения будут выбраны узлы с бóльшим уровнем энергии. Это способствует увеличению срока службы сети при выборе альтернативного пути от источника к месту назначения, когда значение энергии первого пути узла достигает своего порог. Таким образом обеспечивается устойчивая передача данных. O. Banimelhem и D. Khasawneh [5] предложили многопутевой протокол маршрутизации на основе качества обслуживания (протокол GMCAR) с предотвращением перегрузки на основе решетки, который основан главным образом на гарантированной сквозной задержке. Протокол делит область зондирования на решетки, каждая из которых состоит из сенсорных узлов и одного главного узла. Главные узлы помогают в сборе данных от неглавных узлов в той же решетке. Главный узел может совершать передачу собранных данных на другие главные узлы для достижения приемного узла. В [5] рассматриваются множественные диагональные пути для соединения главного узла и приемного узла и путь сохраняется в таблице маршрутизации в качестве записей маршрутизации этого узла. Решения о маршрутизации рассматриваются на основе плотностей решетки и количества переходов. Протокол поддерживает также предотвращение перегрузки, если перегруженные участки свободны для передачи, когда происходит перегрузка. Протокол GMCAR увеличивает энергоэффективность и срок службы сети, повышая пропускную способность сети и сводя к минимуму задержки. Методика нечеткого множества Понятие «нечеткое множество», которое расширило классическое понятие множества, было введено Л. А. Заде в 1965 г. [6] и заключается в следующем: Пусть X есть пространство точек с общим элементом X, обозначенным как х. Таким образом, X = {х}. Нечеткое множество А в X характеризуется функцией принадлежности fA (x), которая связана с каждой точкой в X действительного числа в интервале [0, 1], со значениями fA (x) в точке х, представляющей степень принадлежности х к А. Таким образом, чем ближе значение fA (x) к единице, тем выше степень принадлежности х в А. Значение 0 представляется как ЛОЖЬ, 1 - как ИСТИНА. Нечеткое множество полезно при моделировании неопределенностей. Таким образом, нечеткое множество определяется с точки зрения функции принадлежности, которая является отображением универсального множества U в интервале [0, 1]. Предлагаемая методика Многопутевой протокол маршрутизации, основанный на решетке с использованием нечеткого подхода, является реактивным протоколом, в котором маршруты к месту назначения от источника находятся по требованию. Большинство энергоэффективных протоколов являются энергосберегающими, однако они не учитывают энергетическую балансировку. Эти протоколы рассматривают кратчайший путь от источника к месту назначения, чтобы свести к минимуму потребление энергии, но не смогут правильно работать в случае энергетической балансировки. Предлагаемый нами протокол маршрутизации с энергосбережением для БСС на основе решетки позволяет сбалансировать и сэкономить потребление энергии при помощи методики нечеткого множества. Основная идея разработки эффективной БСС - ее разделение на решетки. Для каждой конкретной области решетки представительский узел выступает в качестве лидера для передачи данных на другие узлы. Узел-лидер не осуществляет, однако, никакой агрегации или объединения. Внутри каждой решетки один из сенсорных узлов выбирается в качестве главного узла, который несет ответственность за получение данных, сгенерированных любым узлом в этой решетке, и отправку данных от других главных узлов к соседним решеткам. Таблица маршрутизации главного узла имеет несколько диагональных путей, которые могут соединяться в приемном узле и храниться в виде записей маршрутизации этого узла. В многопутевой маршрутизации на основе решетки узлы размещаются в случайном порядке в области зондирования. Физическая сеть разделена на логическую решетку сети, в которой каждая решетка состоит из различных развернутых узлов либо может не содержать ни одного узла. Приемный узел является единственным, называемым узлом базовой станции, который находится в неподвижном состоянии и может находиться в любом месте сети. Другие узлы в решетке также неподвижны. Сенсорные узлы могут собирать данные с области зондирования и могут передавать их на приемный узел, который является узлом назначения. Путь, по которому данные передаются от узла-источника к узлу назначения, может состоять из изменяющихся промежуточных узлов, т. е. используется метод многоскачковости. Узлы должны иметь достаточную энергию для передачи данных от одного узла к другому в пределах дальности их связи. Если энергия узлов истощается на выбранном пути, то тут же должен быть выбран альтернативный путь и не должно быть какого-либо сбоя соединения между узлом-источником и узлом назначения. Эта концепция названа многопутевой на основе решетки. Она состоит из четырех этапов: - формирование решетки; - обнаружение соседей; - передача данных; - обновление энергии. Формирование решетки. Сенсорная сеть разделяется на логические квадраты в форме решеток заданного размера. Узлы, как упоминалось выше, развертываются случайным образом. Глобальная система определения местоположения GPS используется для определения местоположения каждого узла в решетке. Если решетка содержит один узел, то он становится главным узлом другого узла с большим идентификатором, выбранным в качестве главного узла. После выборов каждый главный узел передает свой статус другим узлам в этой решетке и отвечает, посылая их идентификаторы обратно к главному узлу, чтобы получить возможность соединения между узлами одной решетки. Максимальный размер решетки G должен быть R = 2, где R - дальность передачи сенсора. На рис. 2 приведен пример формирования решетки БСС и размещения в ней узлов. Данная сеть содержит в себе 66 сенсорных узлов. Рис. 2. Решетка беспроводной сенсорной сети Обнаружение соседей. На втором этапе осуществляется оценивание соседнего узла, в ходе которого все узлы находят свои соседние узлы в этой сети. Соседние узлы могут быть в пределах решетки либо вне ее границ. Приемный узел инициализирует сеть путем ее заполнения широковещательным сообщением. Каждый узел, который принимает первоначальный широковещательный пакет данных, делает записи в своей «Таблице соседей», включая информацию об ID-соседе, энергетическом уровне и количестве переходов. Эти узлы повторно отправляют пакет на другие узлы с необходимыми изменениями, такими как увеличение поля «Количество переходов» (1), изменение поля «Адрес источника» (узел указывает свой адрес (2)) и изменение поля «Уровень энергии» (узел указывает свой уровень энергии (3)). Каждый узел в сети ретранслирует широковещательное сообщение всем своим соседям только один раз. Когда первоначальное широковещательное сообщение отправлено через сеть, каждый узел становится осведомленным о количестве переходов и уровне энергии своих соседей. Приемный узел периодически посылает широковещательное сообщение по сети, так что узлы добавляют новых соседей, присоединившихся к сети, в «Таблицу соседей» и удаляют соседей, которые не смогли быть активными членами сети. Передача данных. На третьем этапе применяется методика нечеткого множества. Когда узел обнаруживает какое-либо событие, он инициирует процесс маршрутизации. Одна из наиболее сложных проблем в реактивных протоколах - процесс выбора следующего шага. Нами ниже предлагается новый сценарий для решения этой проблемы. Проблема состоит из двух нечетких множеств: А и B. Множество А является нечетким множеством энергетических уровней всех соседей: A = {e1, e2, …, en}. Из данного множества можно найти набор остаточной энергии каждого узла. Множество А имеет функцию принадлежности mА(ei), которая может быть определена следующим образом: , (1) где λ - управляющий параметр для ограничения коэффициента использования энергии в интервале [0, 1]; ei - энергетический уровень i-го соседа. Энергетический порог α можно выразить следующей формулой: . (2) Параметр Аα, используемый для удаления соседних узлов с неприемлемым уровнем энергии, находится по формуле (3) Множество B является нечетким множеством всех переходов соседей: B = {h1, h2, …, hn}. Функция принадлежности mB(hi) определяется выражением (4) где n - количество соседей; hi - число переходов i-го соседа; maxhop - самый длинный возможный путь. Теперь получим следующее уравнение, определяющее решение узла при выборе соседа для последующего перехода: при . (5) Обновление энергии. Заключительный этап основан на установке исходного узла. Протокол определяет возможный путь для передачи данных от узла-источника к узлу назначения. Таким способом вычисляется полная энергия, доступная для каждого узла на этом пути. В зависимости от этого находится оптимальный путь, содержащий в себе узлы с наибольшими значениями уровней энергии. После передачи данных от исходного узла к узлу назначения происходит обновление уровня энергии, и, следовательно, следующая передача может быть лучше без больших энергетических затрат. Все соседи узла-отправителя получают пересылаемой пакет данных с помощью метода прослушивания канала. Затем они уточняют уровень энергии узла-отправителя в своей «Таблице соседей» методом совмещения передачи прямых и обратных пакетов. Узлы могут быть использованы несколькими соседями для маршрутизации данных, в этом случае значение энергии, записанное в «таблице соседей» обоих соседних узлов будет идентичным за счет метода прослушивания. Имитационное моделирование Моделирование представленной системы осуществлялось с помощью программного пакета MatLab. Модель нечеткоуправляемой системы для построения путей в сенсорной сети показана на рис. 3. Входными определяющими параметрами модели являются остаточная энергия узла БСС и количество переходов каждого узла до базовой станции. Выходной параметр С является вероятностью становления узла БСС узлом, участвующим в формировании маршрута для передачи данных от источника к базовой станции. Рис. 3. Модель нечеткоуправляемой системы Лингвистические переменные для параметра А (остаточная энергия) обозначим как «Низкая», «Средняя» и «Высокая». Переменные для параметра В (количество переходов) - «Малое», «Среднее», «Много». Функции принадлежности mА(ei) и mB(hi) проиллюстрированы на рис. 4 и 5. Рис. 4. Функции принадлежности mА(ei) Рис. 5. Функции принадлежности mB(hi) На рис. 6 представлена графическая поверхность входов-выходов моделируемой системы. Рис. 6. Поверхность входов-выходов Согласно рис. 6, наибольшая вероятность стать соседним узлом, участвующим в формировании маршрута сети для передачи данных, имеется у узлов с наибольшим уровнем остаточной энергии и средним либо выше среднего количеством переходов до базовой станции. Заключение Энергоэффективность является одним из главных факторов при разработке эффективного протокола маршрутизации беспроводной сенсорной сети. Сохранение и балансировка энергии позволяют повысить срок службы узлов беспроводной сенсорной сети. Предлагаемый новый многопутевой протокол маршрутизации, основанный на решетке и технике нечеткого множества, при передаче данных потребляет меньше энергии, чем разработанные ранее протоколы, что позволит увеличить энергоэффективность беспроводной сенсорной сети, ее надежность и срок службы. Результаты имитационного моделирования системы, реализованного в программном пакете MatLab, наглядно иллюстрируют выбор узлов, сочетающих в себе различные уровни входных параметров, для построения маршрута в беспроводной сенсорной сети.
Список литературы

1. Sohraby K., Minoli D., Znati T. Wireless Sensor Network, Technology, Protocols and Applications. John Wiley & Sons, New Jersey, 2007. 233 р.

2. Wang Y.-H., Tsai Ch.-H., Mao H.-J. HMRP: Hierarchy-Based Multipath Routing Protocol for Wireless Sensor Networks // Tamkang Journal of Science and Engineering. 2006. No. 3. P. 255-264.

3. Yahya B., Ben-Othman J. REER: Robust and Energy Efficient Multipath Routing Protocol for Wireless Sensor Networks // Global Telecommunications Conference. 2009. P. 1-7.

4. Shin K.-Y., Song J., Kim J. W. Reliable Energy Aware Routing Protocol (REAR) // Advanced Communication Technology, The 9th International Conference. 2007. No. 1. P. 525-530.

5. Banimelhem O., Khasawneh D. GMCAR: Grid-based multipath with congestion avoidance routing protocol in wireless sensor network // Ad Hoc Networks. 2012. Vol. 10 (7). P. 1346-1361.

6. Zadeh L. A. Fuzzy sets // Information and Control. 1965. No. 8. P. 338-353.