GRID BASED ENERGY EFFICIENT MULTIPATH ROUTING PROTOCOL IN WIRELESS SENSOR NETWORK USING FUZZY APPROACH
Authors:
1.
Astrakhan State Technical University
2.
Astrakhan State Technical University
Type:
Article
Pages:
from 65
to 73
Status:
Published
Received:
05.10.2016
Accepted:
25.10.2016
Published:
25.10.2016
Subject area:
VAC 05.12.2013 Системы, сети и устройства телекоммуникаций
VAC 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
VAC 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
VAC 05.13.10 Управление в социальных и экономических системах
VAC 05.13.18 Математическое моделирование, численные методы и комплексы программ
VAC 05.13.19 Методы и системы защиты информации, информационная безопасность
UDK 519.242
GRNTI 20.01 Общие вопросы информатики
GRNTI 28.01 Общие вопросы кибернетики
GRNTI 49.01 Общие вопросы связи
GRNTI 50.01 Общие вопросы автоматики и вычислительной техники
GRNTI 82.01 Общие вопросы организации и управления
VAC 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
VAC 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
VAC 05.13.10 Управление в социальных и экономических системах
VAC 05.13.18 Математическое моделирование, численные методы и комплексы программ
VAC 05.13.19 Методы и системы защиты информации, информационная безопасность
UDK 519.242
GRNTI 20.01 Общие вопросы информатики
GRNTI 28.01 Общие вопросы кибернетики
GRNTI 49.01 Общие вопросы связи
GRNTI 50.01 Общие вопросы автоматики и вычислительной техники
GRNTI 82.01 Общие вопросы организации и управления
Language:
Russian
Keywords:
wireless sensor network, multipath routing, routing protocol, energy saving, fuzzy set approach
Abstract (English):
The advantages (ability to use several alternative ways to transfer data to one recipient) and disadvantages (inability to balance electricity consumption) of multipath routing protocols in the wireless sensor network. The main objective in the development of the proposed multipath routing protocol was to ensure its efficiency. The basic idea of the development of efficient wireless sensor network is to divide it into the grids. The concept, called multipath grating, is implemented in four steps: forming a grid; neighbor detection; data transfer; energy update. Formation of the grid helps to determine the minimum through-delay between the source node and the receiving node in the network. The proposed technique of a fuzzy set provides for identification of energy efficiency of nodes in the wireless sensor network. At the final stage the protocol finds the best way to transfer data. Simulation modeling of the system is conducted in MatLab program. The proposed routing protocol saves energy of power supply units, increasing the service life of wireless sensor network and providing the quality of service to users.
The advantages (ability to use several alternative ways to transfer data to one recipient) and disadvantages (inability to balance electricity consumption) of multipath routing protocols in the wireless sensor network. The main objective in the development of the proposed multipath routing protocol was to ensure its efficiency. The basic idea of the development of efficient wireless sensor network is to divide it into the grids. The concept, called multipath grating, is implemented in four steps: forming a grid; neighbor detection; data transfer; energy update. Formation of the grid helps to determine the minimum through-delay between the source node and the receiving node in the network. The proposed technique of a fuzzy set provides for identification of energy efficiency of nodes in the wireless sensor network. At the final stage the protocol finds the best way to transfer data. Simulation modeling of the system is conducted in MatLab program. The proposed routing protocol saves energy of power supply units, increasing the service life of wireless sensor network and providing the quality of service to users.
Keywords:
wireless sensor network, multipath routing, routing protocol, energy saving, fuzzy set approach
wireless sensor network, multipath routing, routing protocol, energy saving, fuzzy set approach
Введение В настоящее время все большее распространение получают сети связи с гетерогенной топологической структурой, под которой понимается наличие в системе передачи и обработки информации проводной и беспроводной составляющей. Широкое использование беспроводных составляющих приводит к усложнению топологических структур подобных сетей и, как следствие, к увеличению факторов, влияющих на эффективность определения и поддержания актуальности оптимальных, по заданным критериям, маршрутов передачи данных. Последние достижения в области беспроводных сенсорных сетей (БСС) привели к созданию новых протоколов маршрутизации, специально предназначенных для сенсорных сетей. Одна из задач при разработке таких протоколов - наличие сведений об уровне энергии узлов. В целом алгоритмы маршрутизации пакетов используются для обмена сообщениями между сенсорными узлами, которые находятся вне определенного радиодиапазона, тогда как обмен сообщениями между сенсорами в рамках конкретного радиодиапазона может осуществляться с использованием одного перехода. Однако один переход в сенсорной сети не рекомендуется из-за затрат энергии при большой дальности передачи. Все это обусловило появление многоскачковой передачи, при которой пакеты данных передаются от источника к месту назначения через множество промежуточных узлов или маршрутизаторов и затраты энергии на передачу данных на малые расстояния значительно меньше. Общая цель всех методов маршрутизации в БСС - увеличение надежности и продление срока службы сенсорной сети без влияния на время и качество доставки данных. Существует много способов классификации протоколов маршрутизации. Почти все протоколы маршрутизации в БСС могут быть классифицированы на основе сетевой структуры и на основе работы протокола [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 r.
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.
