ISSN 0236-235X (P)
ISSN 2311-2735 (E)

Journal influence

Higher Attestation Commission (VAK) - К1 quartile
Russian Science Citation Index (RSCI)

Bookmark

Next issue

4
Publication date:
09 September 2024

An addition to the clustering algorithm of a wireless sensor network

Date of submission article: 09.02.2022
UDC: 004.056.5
The article was published in issue no. № 2, 2022 [ pp. 222-228 ]
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

Font size:       Font:

Сети связи пятого поколения 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. Проверка на пересечение областей и вхождение выбранных точек каждого типа в окрестности друг друга. Для этого используется метрика евклидова расстояния:

 

Рис. 3. Зависимость числа действующих 
сенсорных узлов от продолжительности 
функционирования БСС

Fig. 3. The dependence of the number 
of functioning sensory nodes 
on the WSN functioning duration

 

Рис. 4. Зависимость значения коэффициента доставки пакетов данных от
продолжительности функционирования БСС

Fig. 4. The dependence of the data packet deliv-ery coefficient value on the WSN functioning duration
Шаг 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 % в БСС при Таблица 2
Результаты поиска лучших и перспективных участков на тестовых функциях
Table 2
Search results for the best and promising areas in test functions

Функция	Математическая нотация функции	Результаты поиска:
○ перспективные участки,
• лучшие участки	Значе-ние по-грешно-сти	Время поиска, с
Синус	 
 	2,7×10-5	8×10-7
Парабола	 
 	5×10-4	6×10-7
Розенбро-ка	 
 	4×10-3	4×10-7
Бута	 
 	4×10-4	6×10-7
Изома	 
	 	2×10-3	5×10-7

выборе главы кластера по алгоритму роя пчел остается по времени дольше благодаря полу- ченной экономии энергии, чем при алгоритме 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

  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. Goldstein B.S., Kucheryavyy A.E. Post-NGN Communication Networks. St. Petersburg, 2014, 160 p. (in Russ.).
  3. Kirichek R.V., Paramonov A.I., Prokopyev A.V., Kucheryavyy A.E. The investigation evolution in the wireless sensor networks area. Telecom IT, 2014, no. 4, pp. 29–41. Available at: http://www.sut.ru/doci/
    nauka/review/4-14.pdf
    (accessed January 15, 2022) (in Russ.).
  4. Tatarnikova T.M., Bimbetov F., Bogdanov P.Yu. Identifying network traffic anomalies by deep learning. Izv. SPbETU «LETI», 2021, no. 4, pp. 36–41 (in Russ.).
  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. Tatarnikova T.M., Bogdanov P.Yu., Kraeva E.V. Smart home security proposals based on assessment of consumption resources. Information Security Problems. Computer Systems, 2020, no. 4, pp. 88–94
    (in Russ.).
  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. Zharkov S.N. Stochastic generation proactive set clustering in mobile wireless sensor networks.
    T-Comm, 2013, no. 5, pp. 29–34 (in Russ.).
  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. Vargauzin V.A. Radio networks for data collection from sensors, monitoring and control based on the IEEE 802.15.4 standard. TeleMultiMedia, 2005, no. 6, pp. 23–27 (in Russ.).
  11. Vikulov A.S., Paramonov A.I. IEEE 802.11 WLAN traffic analysis. Proc. Telecommunication Universities, 2017, vol. 3, no. 3, pp. 21–27 (in Russ.).
  12. Tatarnikova T.M., Bogdanov P.Yu. A simulation model for estimating the service life of the Internet of Things under the conditions of attacking effects emitting the node energy. Software & Systems, 2021, no. 4, pp. 564–571. DOI: 10.15827/0236-235X.136.564-571 (in Russ.).

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: