Journal influence
Bookmark
Next issue
An addition to the clustering algorithm of a wireless sensor network
Abstract:The choice of a method for organizing information interaction is one of the urgent scientific tasks when deploying the Internet of things. In turn, the wireless sensor network, which is the physical basis of the Internet of things, has a serious limitation that is the requirement of low power consumption. The life of the network depends on energy consumption - the time during which the network performs its func-tions. The energy of sensory devices is spent on receiving and transmitting data, processing them, and calculating the route. New algorithms are required to reduce the number of data processing operations, route length, and more without losing network functionality. One mechanism that has proven to reduce power consumption is the clustering of a wireless sensor network due to the transfer of part of the functions to the head nodes of the clusters. The bee swarm al-gorithm proposed in the paper develops the idea of searching for the head nodes of wireless sensor network clusters. According to the proposed algorithm, at the beginning of the cycle, the head of the cluster of the current round and potential heads of clusters for the remaining rounds of the cycle are immediately determined. Thus, the phase of choosing the cluster head node, starting from the second round of the cycle, becomes redundant, and the sensor nodes get rid of some of the calculations associ-ated with choosing the head of the cluster. The simulation results show the superiority of the bee swarm algorithm in comparison with the well-known LEACH low power adaptive clustering algorithm in terms of the duration of the wireless sensor network.
Аннотация:В статье предлагается алгоритм, который развивает идею кластеризации беспроводных сенсорных сетей с целью снижения энергопотребления сенсорными узлами. Выбор способа организации информационного взаимодействия является одной из актуальных научных задач при развертывании работы интернета вещей. В свою очередь, беспроводная сенсорная сеть, составляющая физическую основу интернета вещей, имеет серьезное ограничение – требование низкого энергопотребления. От энергопотребления зависит срок службы сети – времени, в течение которого она будет выполнять свои функции. Энергия сенсорных устройств расходуется на прием и передачу данных, их обработку, вычисление маршрута. Требуются новые алгоритмы, направленные на снижение количества операций обработки данных, длины маршрута и т.д. без потери функциональности сети. Одним из таких механизмов является кластеризация беспроводной сенсорной сети, позволяющая снизить энергопотребление за счет передачи части функций на головные узлы кластеров. Предложенный в работе алгоритм роя пчел развивает идею поиска головных узлов кластеров беспроводной сенсорной сети. Согласно ему, в начале цикла определяются сразу глава кластера текущего раунда и потенциальные главы кластеров для остальных раундов цикла. Таким образом, со второго раунда цикла фаза выбора головного узла кластера становится лишней, а сенсорные узлы избавляются от некоторых вычислений, связанных с выбором главы кластера. Результаты имитационного моделирования показали превосходство алгоритма роя пчел в сравнении с известным алгоритмом адаптивной кластеризации с низким потреблением энергии LEACH по показателю продолжительности функционирования беспроводной сенсорной сети.
Authors: Tatarnikova, T.M. (tm-tatarn@yandex.ru) - St. Petersburg State University of Aerospace Instrumentation (Associate Professor, Professor), St. Petersburg, Russia, Ph.D, Bimbetov F. (fbimbetov@gmail.com) - Saint Petersburg Electrotechnical University (Postgraduate Student), St. Petersburg, Russia, Gorina E.V. (elena_rez@mail.ru) - Saint-Petersburg State University of Industrial Technologies and Design, St. Petersburg, Russia | |
Keywords: lifespan of internet of things, energy costs, clusterization, bee swarm algorithm |
|
Page views: 3783 |
PDF version article |
Сети связи пятого поколения 5G и новые типы услуг являются особо актуальной темой исследований последних 5–7 лет [1]. Более того, достигнутые результаты, которые проявились в большом разнообразии новых типов услуг, основанных на концепции интернета вещей, позволили задуматься о плавном переходе к концепции сетей связи 2030 [2]. Стоит отметить, что параллельно с инфокоммуникационными технологиями развивается направление применения искусственного интеллекта в сетях связи. Тема применения искусственного интеллекта в инфокоммуникационных технологиях появилась сравнительно недавно и вызывает все больший интерес, причина которого кроется в необходимости обработки и анализа больших данных, генерируемых умными устройствами интернета вещей [3, 4]. Физическую основу интернета вещей образуют беспроводные сенсорные сети (БСС), одним из самых важных ограничений которых является требование низкого энергопотребления сенсорными узлами. Именно сенсорные узлы реализуют умные функции интернета вещей. Получается, что энергопотребление определяет срок службы БСС, который можно измерить следующими метриками [5]: - количество узлов, которые продолжают функционировать (имеют энергию для работы); - продолжительность функционирования БСС до момента «смерти» ее первого узла; - коэффициент доставки пакетов – отношение числа доставленных адресату пакетов к числу отправленных. Таким образом, если протоколы традицион- ных сетей нацелены на достижение высоких показателей качества обслуживания (Quality of Service, QoS), то протоколы интернета вещей должны быть ориентированы прежде всего на энергосбережение [6]. Постановка задачи Энергия сенсорных устройств расходуется на прием и передачу данных, их обработку, вычисление маршрута и т.д. Таким образом, выбор способа организации информационного взаимодействия является одной из актуальных научных задач при создании БСС. Большинство современных исследований посвящено разработке схем, удовлетворяющих требованиям сокращения числа операций при организации взаимодействия сенсорных узлов. Например, таким механизмом, позволяющим снизить энергопотребление, является класте- ризация БСС благодаря передаче части функ- ций на головные узлы кластеров [7]. БСС стро- ится как совокупность кластеров, на которые разбивается создаваемое ею сенсорное поле. В каждом кластере БСС глава кластера (головной узел) выполняет роль ретранслятора данных, полученных от сенсорных узлов, принадлежащих этому кластеру. Далее собранные данные передаются главой кластера на базовую станцию, которая, в свою очередь, доставляет их в глобальное облако [8]. Такой иерархический принцип организации доставки данных отражен на рисунке 1. Временная диаграмма функционирования кластеризованной БСС приведена на рисунке 2. В каждом раунде работы БСС последовательно выполняются следующие действия: - выбор главы кластера, реализующего функции ретранслятора данных от сенсорных узлов на базовую станцию, на основе метрик евклидова расстояния и уровня остаточной энергии [9]; - формирование кластера на основе метрики евклидова расстояния от сенсорного узла до головного; - передача данных: во-первых, от главы кластера всем своим сенсорным узлам расписания отправки данных и, во-вторых, от сенсорных устройств главе кластера собственно самих данных по методу TDMA (Time Division Multiple Access – множественный доступ с разделением по времени), что гарантирует отсутствие коллизий передачи данных [10]; - агрегация данных в главе кластера – объединение данных, полученных от сенсорных узлов, включая отсеивание некорректных и дублирующих данных [11]; - переход в спящий режим, при котором сенсорные устройства переходят в режим сниженного потребления энергии. Таким образом, продолжительность функционирования БСС складывается из r раундов. Несмотря на наличие механизма кластеризации, исследователи все еще ищут возможности снизить энергопотребление БСС. В статье предлагается один из алгоритмов, который развивает идею кластеризации БСС с целью снижения энергопотребления сенсорными узлами. Описание алгоритма Предлагается не в каждом раунде, а только в начале цикла определять сразу главу кластера текущего раунда и потенциальные главы кластеров на остальные (r–1) раунды цикла. Потенциальные главы кластеров – это сенсорные узлы, близкие к текущему главе кластера по метрике евклидова расстояния и уровню остаточной энергии. Таким образом, фаза выбора головного узла кластера, начиная со второго раунда цикла, становится лишней, а сенсорные узлы избавляются от некоторых вычислений, связанных с выбором главы кластера. Представленный алгоритм основан на роевом интеллекте. Роевой интеллект – это набор алгоритмов, направленных на изучение и описание коллективного поведения децентрализованной самоорганизующейся системы, к числу которых относятся и БСС. Элементы систе- мы – простые агенты с небольшим набором выполняемых операций, в совокупности создающие единый роевой интеллект, способный решать задачи поисковой оптимизации. Каждое перемещение агента характеризуется определенным положением в исследуемой области – координатами XY. На основании их значений вычисляется целевая функция и принимается решение об исследовании близлежащей области. В предлагаемом алгоритме агентами являются пчелы-разведчики и пчелы-фуражиры, хаотично перемещающиеся с постоянным ша- гом в выбранной области целевой функции. Основной целью пчелиной колонии является поиск нектара – оптимального значения целевой функции. Сначала на поиски наибольшего скопления нектара отправляются несколько пчел-разведчиков, которые исследуют местность и выявляют наиболее медоносные участки. Затем пчелы-разведчики возвращаются в улей и сообщают пчелам-фуражирам, где необходимо провести сбор нектара. Пчелы-фуражиры, следуя за пчелой-разведчиком, прилетают не в одну точку, а распределяются в некоторой области, которая располагается недалеко от исходного места скопления нектара. Таким образом, пчелы-фуражиры могут найти и запомнить как наиболее, так и наименее перспективные места. В таблице 1 показана адаптация терминов алгоритма роя пчел к задаче оптимизации. Таблица 1 Адаптация терминов алгоритма роя пчел к задаче оптимизации Table 1 Adapting bee swarm algorithm terms to the optimization problem
Алгоритм состоит из семи шагов. Шаг 1. Ввод исходных данных: количество сенсорных узлов N; число пчел-разведчиков X, лучших участков B, перспективных участков P; радиус окрестности R, в которой пчела выполняет поиск; длина a и ширина b исследуемой области; значение шага передвижения D для исследования плоскости. Шаг 2. Отправка пчел-разведчиков – случайный выбор Х точек на исследуемой плоскости: X = random.uniform(a, b). Шаг 3. Оценка полученных значений целевой функции Х точек и выбор лучших B и перспективных P участков. Шаг 4. Случайный выбор l точек на лучших участках и p точек на перспективных участках (l > p), окрестности каждой точки задаются координатами с радиусом R. Шаг 5. Проверка на пересечение областей и вхождение выбранных точек каждого типа в окрестности друг друга. Для этого используется метрика евклидова расстояния: Шаг 6. Исследование окрестностей каждой из l и p выбранных точек в поиске лучших и перспективных участков. Шаг 7. Повтор шагов 2–6 до тех пор, пока не сработает условие останова. Анализ результатов Работоспособность алгоритма роя пчел и оценка точности поиска лучших и перспективных участков проверены на известных математических функциях. Полученные результаты (табл. 2) свидетельствуют о способности алгоритма роя пчел решать оптимальные и субоптимальные задачи. Результаты имитационного моделирования показывают превосходство алгоритма роя пчел в сравнении с известным алгоритмом адаптивной кластеризации с низким потреблением энергии LEACH (Low-Energy Adaptive Clustering Hierarchy) [9] по показателю продолжительности функционирования БСС. Особенности имитационной модели подробно представлены в [12] с дополнением процедуры роя пчел. Моделирование выполнялось при следующих исходных данных: N = 100; a = 100 м, b = 100 м; средняя длина пакета данных бита; энергия, расходуемая для сбора данных, Ea = 5 нДж; остаточная энергия сенсорного узла E = 0,5 Дж; d = 40 м; продолжительность одного раунда 1 с; скорость передачи данных 9 600 бит/с; энергия генерации одного бита =10 нДж; энергия передачи одного бита данных = 50 нДж. Гибель первого сенсорного узла в БСС с поиском главы кластера алгоритмом LEACH произошла на 645-м раунде, а для БСС с поиском главы кластера по алгоритму роя пчел на 847-м. На рисунке 3 демонстрируется изменение количества действующих сенсорных узлов с течением времени функционирования БСС. Выбор главы кластера по алгоритму роя пчел позволяет экономить энергию и, соответственно, увеличивать продолжительность жизненного цикла БСС. Отметим, что с увеличением числа сенсорных узлов в кластере и числа раундов в цикле функционирования БСС эта экономия будет только расти. На рисунке 4 показано изменение значения коэффициента доставки пакетов данных от сенсорных узлов на головной узел с течением времени функционирования БСС. Очевидно, что коэффициент доставки 100 % в БСС при выборе главы кластера по алгоритму роя пчел остается по времени дольше благодаря полу- ченной экономии энергии, чем при алгоритме LEAСH. Заключение Выбор способа информационного взаимо- действия является одной из актуальных науч- ных задач при организации интернета вещей. В целях рационального расходования энергии, необходимой для функционирования интернета вещей, предложено в начале процедуры кластеризации определять не только главу кластера, но и близкие к нему по значению целевой функции сенсорные узлы. Целевой функцией являются уровень остаточной энергии и метрика евклидова расстояния. Таким образом, фаза выбора головного узла кластера, начиная со второго раунда цикла, становится лишней, а сенсорные узлы избавляются от некоторых вычислений, связанных с выбором главы кластера. Результаты имитационного моделирования показывают преимущество добавления алго- ритма роя пчел в процедуру кластеризации БСС по таким показателям качества БСС, как время гибели первого сенсорного узла, число функционирующих узлов, имеющих достаточно энергии для выполнения свойственных им операций, и коэффициент доставки пакетов данных. Литература 1. Tran T.X., Hajisami A., Pompili D., Pandey P. Collaborative mobile edge computing in 5G networks: New paradigms, scenarios, and challenges. IEEE Communications Magazine, 2017, vol. 55, no. 4, pp. 54–61. DOI: 10.1109/MCOM.2017.1600863. 2. Гольдштейн Б.С., Кучерявый А.Е. Сети связи пост-NGN. СПб: БХВ-Петербург, 2014. 160 c. 3. Киричек Р.В., Парамонов А.И., Прокопьев А.В., Кучерявый А.Е. Эволюция исследований в области беспроводных сенсорных сетей // Информационные технологии и телекоммуникации. 2014. № 4. С. 29–41. URL: http://www.sut.ru/doci/nauka/review/4-14.pdf (дата обращения: 15.01.2022). 4. Татарникова Т.М., Бимбетов Ф., Богданов П.Ю. Выявление аномалий сетевого трафика методом глубокого обучения // Изв. СПбГЭТУ «ЛЭТИ». 2021. № 4. С. 36–41. 5. Krishnamurthy V. POMDP multi-armed bandit formulation for energy minimization in sensor networks. Proc. IEEE ICASSP, 2005, vol. 5, pp. 793–796. DOI: 10.1109/ICASSP.2005.1416423. 6. Татарникова Т.М., Богданов П.Ю., Краева Е.В. Предложения по обеспечению безопасности системы умного дома, основанные на оценке потребляемых ресурсов // Проблемы информационной безопасности. Компьютерные системы. 2020. № 4. С. 88–94. 7. Basford P.J., Johnston S.J., Perkins C.S., Garnock-Jones T., Tso F.P., Pezaros D., Cox S.J. Performance analysis of single board computer clusters. Future Generation Computer Systems, 2020, vol. 102, pp. 278–291. DOI: 10.1016/J.FUTURE.2019.07.040. 8. Жарков С.Н. Стохастическое формирование проактивного множества при кластеризации в мобильных беспроводных сенсорных сетях // T-Comm. 2013. № 5. С. 29–34. 9. Ran G., Zhang H., Gong S. Improving on LEACH protocol of wireless sensor networks using fuzzy logic. J. Inf. Comput. Sci., 2010, no. 7, pp. 767–775. 10. Варгаузин В.А. Радиосети для сбора данных от сенсоров, мониторинга и управления на основе стандарта IEEE 802.15.4 // ТелеМультиМедиа. 2005. № 6. C. 23–27. 11. Викулов А.С., Парамонов А.И. Анализ трафика в сети беспроводного доступа стандарта IEEE 802.11 // Тр. учебных заведений связи. 2017. Т. 3. № 3. С. 21–27. 12. Татарникова Т.М., Богданов П.Ю. Имитационная модель оценки срока службы интернета вещей в условиях атакующих воздействий, источающих энергию узлов // Программные продукты и системы. 2021. № 4. С. 564–571. DOI: 10.15827/0236-235X.136.564-571. References
|
Permanent link: http://swsys.ru/index.php?page=article&id=4898&lang=en |
Print version |
The article was published in issue no. № 2, 2022 [ pp. 222-228 ] |
Perhaps, you might be interested in the following articles of similar topics:
- Имитационная модель оценки срока службы интернета вещей в условиях атакующих воздействий, источающих энергию узлов
- Метод ситуационного прогнозирования появления новых технологий Индустрии 4.0
- Кластеризация документов интеллектуального проектного репозитария на основе FCM-метода
- Применение технологии CUDA для обучения нейронной сети Кохонена
- Информационно-коммуникационная технология комплексного управления деятельностью студентов
Back to the list of articles