УДК 004.94
DOI: 10.15587/1729-4061.2022.252988
Разработка модификации метода построения энергоэффективных сенсорных сетей с использованием статических и динамических датчиков
В. Я. Петривский, В. Л. Шевченко, С. П. Евсеев, А. В. Милов, А. А. Лаптев, А. С. Бычков, В. А. Федориенко, М. В. Ткаченко, О. А. Курченко,
И. Р. Опирский
У зв’язку з поширенням використання сенсорів та сенсорних мереж у за- дачах покриття території актуальними критеріями є максимізація покриття та мінімізація енерговитрат. Саме одночасна відповідність мережі даним критеріям є актуальною проблемою у сучасному технологічному світі. Запро- поновано модифікацію методу побудови енергоефективних сенсорних мереж шляхом введення додаткового критерію мінімізації кількості сенсорів та об- меження кількості використаних сенсорів, який дозволяє зменшити енергови- трати сенсорних мереж на 19 %. У отриманій оптимізаційній задачі критері- ями оптимальності виступають функції мінімізації площі непокритої тери- торії, значення енергоспоживання та кількості датчиків. Оптимальне рішення формується у вигляді пар значень радіусу покриття та рівня перетину зон по- криття з використанням яких досягається максимізація покриття з мініміза- цією енерговитрат та кількості використаних сенсорів. Для розв’язання пос- тавленої проблеми використано метод згортки параметрів та генетичний ал- горитм. У випадку динамічних датчиків проблема полягає у відшуканні такої траєкторії руху датчику, яка забезпечує максимальний обліт території, але є мінімальної довжини. Для знаходження необхідної траєкторії запропоновано сітковий алгоритм. Представлений алгоритм полягає у розбитті території на вузли та оцінці значення покритої території датчиком у даному вузлі. Після формування оцінок використано пошук гамільтонового шляху. Розглянуто ви- падок багатозв’язності території з можливістю перетворення її до од- нозв’язної. Запропоновано схему знаходження параметрів енергоефективного покриття території з використанням статичних та динамічних сенсорів.
Ключові слова: сенсорна мережа, покриття території, енергоефектив- ність сенсорних мереж, оптимальна траєкторія обльоту.
1. Введение
Сенсоры и сенсорные сети широко распространены во всех сферах челове- ческой деятельности. Использование датчиков (сенсоров) обеспечивается их преимуществами, такими как небольшой размер, различные измеряемые значе- ния, простота разработки программного обеспечения, небольшое энергопо- требление, мобильность, срок службы. Также многие задачи, такие как сбор, анализ, идентификация и измерение данных, могут быть решены с использова- нием датчиков [1, 2]. Кроме того, датчики являются неотъемлемой частью тех- нологий Интернет вещей и Интернет всего [3, 4].
Not
a reprint
На практике ключевыми критериями при построении сенсорных сетей в задаче мониторинга являются охват территории, энергоэффективность и общая стоимость сети. Максимальное покрытие территории достигается путем разме- щения дополнительных датчиков и увеличением радиуса покрытия датчиков.
Увеличением радиуса покрытия приводит к увеличению энергопотребления, а увеличения количества датчиков приводит к возрастанию общей стоимости се- ти и ее обслуживания. При использовании динамических сенсоров максималь- ное покрытие достигается путем облета всей территории. Также в данном слу- чае сенсор тратит запас аккумулятора не только на сбор информации, но и на движение. Очевидно, что минимизация длины траектории полета уменьшит энергопотребление датчика и существенно повысит строк автономного исполь- зования. Также следует отметить уменьшение размера сенсоров, следствием чего есть уменьшение размера аккумулятора устройства. В свою очередь воз- растает цена высокотехнологических сенсоров.
В настоящее время существует ряд исследований посвященных построе- нию сенсорных сетей с учетом критериев максимизации покрытия, общей сто- имости сети, энергоэффективности сетей. Но в большинстве из них учитывает- ся только один из критериев и не учитывается возможность изменения радиуса покрытия во время движения датчика. Именно разработка метода нахождения оптимальных параметров сети, в котором одновременно учтены критерии мак- симизации покрытия, минимизации энергопотребления и количества сенсоров, изменение радиуса покрытия во время движения является актуальной научной задачей. Решение описанной задачи позволит находить параметры сенсорных сетей, использование которых будет обеспечивать максимальное покрытие тер- ритории с минимальными энергозатрататами, что, в свою очередь, повысит строк использования сети.
2. Анализ литературных данных и постановка проблемы
В статье [5] предлагается метод оптимального покрытия территории дат- чиками разного радиуса действия. Для решения этой проблемы авторы моди- фицировали метод наименьших квадратов. Критерием оптимальности является максимальное покрытие территории с минимальным пересечением зон покры- тия. Но в статье не учитывается энергопотребление датчиков, и уменьшение пересечения зон покрытия может привести к образованию непокрытых участ- ков. Оптимизации размещения датчиков для решения проблемы критического покрытия сети с целями точности и стоимости предложено в исследовании [6].
Незатронутым остается вопрос энергоэффективности покрытия. Алгоритм по- крытия территории произвольной геометрии датчиками с радиусом охвата пу- тем аппроксимации территории ортогональным многоугольником представлен в работе [7]. Недостатком является расположение датчиков без возможности пересечения зон покрытия, следствием чего будет невозможность передачи ин- формации между сенсорами и наличие непокрытых зон.
В статье [8] рассматривается проблема энергоэффективного регулярного покрытия плоской территории датчиками с двумя выбранными радиусами наблюдения. В статье улучшены известные результаты по качеству покрытий, а
For reading
only
также оптимизируется общее потребление энергии на мониторинг и передачу данных между элементами сенсорной сети. Но остался нерешенным вопрос возможности регуляции радиусов покрытия и области пересечения датчиков. В исследовании [9] предложен метод минимизации энергопотребления сенсорной сети путем регуляции радиусов покрытия. Недостатками предложенного мето- да являются использование фиксированного значения уровня пересечения зон покрытия и уменьшение общего покрытия сети.
Подход к минимизации энергопотребления мобильных датчиков путем регу- лировки радиусов покрытия описано в статье [10]. Авторы не учитывают макси- мизацию покрытия территории при движении сенсоров. В работе [11] представле- но алгоритмы построения траектории полета датчика минимальной длинны при максимальном накоплении информации, но не учитывается облет всей террито- рии и упускаются труднодоступные участки. Предложенный в статье [12] метод кластеризации основан на методе средней точки с учетом остаточной энергии и расстояния между узлами. Но предложений подход не обеспечивает максималь- ное покрытие территории. Поиск траектории полета датчика как задача коммиво- яжера представлена в статье [13]. Предложенный подход не обеспечивает покры- тие всей территории. В работе [14] для эффективного сбора данных на основе сто- ка была рассмотрена траектория мобильного стока на основе кривой Мура. При этом не учитывается радиус покрытия сенсора, следствием чего будет облет уже покрытых участков территории. Алгоритм построения траектории движения дат- чика на основе управления псевдоформой представлен в работе [15]. В предло- женном алгоритме не учтен радиус покрытия датчика и возможность захвата об- ласти за пределами необходимой территории.
Таким образом, неразрешенной задачей при построении сенсорных сетей является одновременный учет критериев максимизации покрытия, минимиза- ции энергопотребления сенсорной сети, уменьшение количества датчиков, а также поиска оптимальной траектории полета датчика с учетом покрытия тер- ритории. Предложенный подход модификации метода построения энергоэф- фективных сенсорных сетей позволяет максимизировать площадь покрытия, минимизировать энергопотребление сети, а также сократить количество ис- пользуемых сенсоров.
3. Цели и задачи исследования
Целью исследования является разработка модификации метода построения энергоэффективных сенсорных сетей с использованием статических и динами- ческих датчиков. Такой подход позволяет минимизировать количество задей- ствованных датчиков при использовании статических сенсоров, а также нахож- дение оптимальной траектории облета территории при использовании динами- ческих датчиков. Это даст возможность строить сенсорные сети и траектории облета территории, которые соответствуют критериям максимизации покрытия и минимизации энергопотребления.
Для достижения поставленной цели необходимо решение следующих задач:
– разработать модифицированный метод построения сенсорной сети в условиях максимизации покрытия при минимизации энергопотребления;
Not
a reprint
– разработать метод построения траектории движения динамических дат- чиков с учетом минимизации энергопотребления;
– разработать алгоритм нахождения параметров энергоэффективной сен- сорной сети с использованием статических и динамических датчиков.
4. Материалы и методы исследования
Для решения задачи разработки метода построения сенсорной сети в усло- виях максимизации покрытия при минимизации энергопотребления с учетом ограничения количества сенсоров был взят за основу метод, что представлен в работе [16]. Использованный метод заключается в решении нелинейной много- критериальной оптимизационной задачи нахождения радиуса покрытия и зон пересечения датчиков, при которых достигается максимальное покрытие терри- тории при минимальном энергопотреблении. Для решения сформулированной проблемы использовано метод линейной свертки критериев, который предпо- лагает преобразование набора имеющихся частных критериев в один суперкри- терий путем суммирования критериев с весовыми коэффициентами, сумма ко- торых равна единице [18]. Также было использовано генетический алгоритм, что используется для решения задач оптимизации и моделирования путем слу- чайного подбора, комбинирования и вариации искомых параметров с использо- ванием механизмов, аналогичных естественному отбору в природе [19].
При поиске оптимального пути в задаче разработки метода построения траектории движения датчиков с учетом минимизации энергопотребления был использован поиск гамильтонового пути. В теории графов гамильтонов путь – это путь, который является путем без петель, проходящим через каждую вер- шину графа ровно один раз [20]. В случае, когда начальные и конечные точки совпадают, будем искать гамильтонов цикл. Для нахождения гамильтонового пути был использован метод ветвей и границ.
5. Методы и алгоритмы построения энергоэффективных сенсорных сетей с использованием статических и динамических датчиков
5. 1. Разработка модифицированного метода построения сенсорной сети в условиях максимизации покрытия при минимизации энергопотребления
Рассматривается некоторая территория, которую нужно покрыть датчика- ми, то есть построить сенсорную сеть. Среди всех характеристик сенсоров (размер, форма, координаты, радиус покрытия, объем батареи, значение изме- рения) учитывались только координаты и радиус покрытия. В результате каж- дый датчик можно представить следующим образом (1):
, ,
,i i i i i
s s x y r (1)
где xi, yi – координаты датчика, ri– радиус охвата, 1≤i≤n, n – количество датчиков.
Для нахождения покрытия территории используем метод, представленный в статье [16], что сформулирован в виде оптимизационной задачи следующего вида:
For reading
only
, min,min,
E r
Z r c (2)
0 r rmax, (3)
max
min ,
c c r (4)
где E(r) – энергопотребление, Z(r,c) – площадь непокрытой территории, r – ра- диус охвата, c – пересечение зон охвата.
Энергопотребление согласно [16] будет равно:
2.E r r (5)
Функция Z(r,c) в уравнении (2) представлена как площадь непокрытой тер- ритории сенсорами с радиусом охвата r и уровнем пересечения зон покрытия в следующем виде:
,
, ,Z r c Z r Z r c (6)
где Zcovered=πr2.
Значение площади пересечения рассчитывалось с использованием подхо- да, представленного в статье [17]:
, r22
, sin
,
,Z r c m K r c K r c (7)
где r – радиус охвата датчика, c – уровень пересечения зон охвата, rmax – макси- мальное значение радиуса охвата, cmin – минимальное значение пересечения ра- диусов охвата, K(r, c)=2arccos(α/r), α=r–c/2, m – количество пересечений.
Схематически уровень пересечения зон покрытия c и площадь непокрытой Z(r,c) можно представить следующим образом (рис. 1).
Недостатком рассматриваемого метода есть возможность использования не- ограниченного количества датчиков. На практике количество доступных для ис- пользования датчиков есть фиксированным, и очевидно, что экономически вы- годно использование минимального количества сенсоров. С учетом этого в систе- му (2) введем функцию количества сенсоров, которая будет вычисляться как целая часть деления площади всей территории на площадь покрытия одного сенсора:
2, Ts
N r r (8)
Not
a reprint
где Ts – площадь территории для покрытия.
Рис. 1. Уровень пересечения зон покрытия c и функция Z(r,c)
Обозначим как Nmax число доступных к использованию датчиков и будем учитывать это значение как дополнительное ограничение при решении задачи.
Таким образом, метод (2)–(7) модифицирован с учетом минимизации ко- личества используемых сенсоров и ограничением количества доступных сенсо- ров и сформулирован в виде задачи:
min, , min,
min,
E r Z r c N r
(9)
0 r rmax, (10)
max min c c r или
c=const, (11)
For reading
only
max0 N r N . (12)
В уравнении (9) E(r) является функцией энергопотребления (5), Z(r,c) есть функцией непокрытой территории (6), а N(r) – это функция количества сенсо- ров (8), Nmax – количество доступных для использования сенсоров. В сформули- рованной задаче учтены критерии минимизации энергопотребления, площади непокрытой территории и количества используемых сенсоров. Также учтено ограничение количества доступных к использованию датчиков, возможность регуляции радиусов покрытия и уровня пересечения зон покрытия.
Используя метод свертки параметров, задача минимизации энергопотреб- ления при максимальном охвате с учетом пересечения зон покрытия датчиков представлена в следующем виде:
, 1
, 2
3
,F r c Z r c E r N r (13)
0 r rmax, (14)
max min c c r или
c=const, (15)
max0 N r N . (16)
1 2 3 1,
(17)
0 1 1, 0 2 1,0 3 1, (18) где r – радиус охвата датчика, c – уровень пересечения зон охвата, rmax – макси- мальное значение радиуса охвата, cmin – минимальное значение пересечения ра- диусов охвата, Nmax – количество доступных сенсоров, α1, α2, α3 – экспертные оценки значимости параметров.
Решением сформулированной задачи в форме (9)–(12) или (13)–(18) будет множество парето-оптимальных сочетаний радиусов покрытия и уровня пере- сечения радиусов покрытия, с использованием которых достигается макси- мальное покрытие территории при минимальном энергопотреблении.
Таким образом, алгоритм метода построения сенсорной сети в условиях максимизации покрытия при минимизации энергопотребления с учетом огра- ничения количества сенсоров схематически может быть представлен следую- щим образом (рис. 2).
Not
a reprint
Начало
Использование метода свертки параметров
Использование генетического
алгоритма Загрузка территории
Автоматическое вычисление площади территории
Конец Загрузить территорию с файла
Площадь территории
Радиус покрытия, уровень пересечения, количество доступных сенсоров
Использовать метод свертки
Выбор параметров покрытия Построение сети
Нет
Да
Нет
Да
Применение ограничения количества сенсоров
Рис. 2. Блок-схема построения сенсорной сети в условиях максимизации по- крытия при минимизации энергопотребления с учетом ограничения количества
сенсоров
For reading
only
На первом этапе необходимо ввести площадь территории, максимальный радиус покрытия, уровень пересечения зон покрытия и количество доступных для использования сенсоров. Можно также загрузить изображение территории из файла и использовать автоматический захват пределов территории и вычис- ление площади. Далее необходимо выбрать метод решения задачи: генетиче- ский алгоритм или метод свертки параметров. Результатом будет множество парето-оптимальных сочетаний радиусов покрытия и уровня пересечения ради- усов покрытия. Среди полученных результатов необходимо выбрать решение, которое удовлетворяет пользователя, и построить соответствующие покрытие территории.
5. 2. Разработка метода построения траектории движения динамиче- ских датчиков с учетом минимизации энергопотребления
Рассмотрено использование динамических датчиков. В случае динамических сенсоров максимальное покрытие будет означать максимальное покрытие терри- тории во время облета, и, как следствие, задачу поиска оптимальной траектории полета датчика. Так как датчик тратит запас аккумулятора на движение, критери- ем оптимальности будет минимизация длинны траектории. Другим критерием оп- тимальности будет максимизация покрытой территории. Таким образом, была сформулирована задачу построения оптимальной траектории движения датчика с учетом минимизации энергопотребления в следующем виде:
max,min,
L x
S x (19)
1 1
,
n n ij iji j
L x c x (20)
2
1
,
n i i out ii
S x R x S x (21)
1
1,
n ij i
x j1, ,n (22)
1
1,
n ij j
x i1, ,n (23)
1
2,
i j ij
u u n x n i j, 2, ,n i j, (24)
Not
a reprint
1, еслиследуем с точки в точку , 0, еслинеследуем с точки в точку ,
ij
i j
x i j (25)
1, если точка принадлежит маршруту, 0, если точка не принадлежит маршруту.
i
i
i (26)
В постановке задачи (19)–(26) S(x) является суммой площади покрытия датчика в каждой точке маршрута xi. Элементы суммы вычисляются как разни- ца между общей площадью покрытия сенсора в данной точке с радиусом R(xi) и площадью покрытой за пределами территории Sout(xi). Значение Sout(xi) вычисля- ется с помощью подхода предложенного в работе [17]. Условие (22) означает только один выход из точки, а условие (23) означает только один вход в точку, то есть каждая точка посещается только один раз. Ограничение (24) является особым условием, обеспечивающим замкнутость маршрутов и отсутствие под- циклов, не связанных между собой. Величины cij – это расстояние между точ- ками, через которые должна пролегать траектория. Расстояние между точками вычислялось как евклидовое расстояние.
Для решения поставленной задачи и построения оптимальной траектории перенесем территорию на координатную плоскость XOY таким образом, чтобы территория соприкасалась с осями OX и OY в одной точке к каждой оси. После перенесения на координатную плоскость, после чего плоскость была покрыта равномерной сеткой с шагом, равным радиусу охвата r. Для дальнейшего ис- пользования территория была обозначена как T.
На следующем этапе узлы сетки были пронумерованы начиная с единицы вдоль оси OX и сформирован вектор A, элементы которого являются соответ- ствующими узлами сетки. Значение элементов вектора будут равны площади территории si, которую покрывает сенсор в данной точке или нулю в случае, узел сетки не принадлежит территории T:
, ,
0, .
i i
i
i
s a T
a a T (27)
Значения si вычислялись с использованием теоремы Пика [21]. Для ис- пользования теоремы Пика необходимо дополнительно построить сетку с ма- лым шагом в квадрате, описанном вокруг данной позиции сенсора. Точки дан- ного квадрата будут иметь координаты (xc–R, yc–R), (xc–R, yc+R), (xc+R, yc+R), (xc+R, yc–R) соответственно.
Также значения элементов вектора A будут равными нулю в случае, когда значение покрытой площади в данном узле сетки меньше определенного экс- пертного значение минимально допустимой площади покрытия, которое обо- значено как Smin:
For reading
only
min
, ,
0, .
i i
i
i i
s a T
a a T s S (28)
В случае наличия возможности регуляции радиуса покрытия датчика зна- чение минимального и максимального радиуса охвата датчика обозначено как rmin и rmax. В случае, когда при поточном радиусе охвата датчик покрывает зону за пределами рассматриваемой территории, был использован радиус охвата, при котором покрытая датчиком зона не выходит за пределы рассматриваемой территории. При построении траектории использован максимальный из допу- стимых радиусов. Регуляция радиуса охвата также будет уменьшать энергопо- требление датчика. В таком случаи, кроме вектора узлов, сформирован вектор радиусов покрытия R, элементы которого будут равны rmin≤ri≤rmax.
На следующем этапе была сформирована матрица переходов между узлами P. Элементы данной матрицы pij будут равными единице в случае, когда значение ai>0 и aj>0. В случае, когда ai=0 или aj=0 значение pij будет равным нулю:
1, 0 0,
0, 0 0.
i j
ij
i j
a a
p a a (29)
Алгоритм формирования матрицы переходов можно представить следую- щей схемой (рис. 3).
После формирования матрицы P задача заключается в отыскании гамильто- нового пути [20], то есть пути, проходящего через каждый узел только один раз.
Рассмотрен случай многосвязной области. В таком случае траектория, по- строенная с использованием описанного выше алгоритма, будет покрывать не всю область, что рассматривается. Для обеспечения полноты покрытия область была приведена к односвязной путем объединения областей. Данное объедине- ние проводилось с помощью дополнительных переходов между узлами путем добавления одной связи между ближайшими узлами для каждой пары одно- связных областей. На рис. 4, а представлена двусвязная область. Для превраще- ния ее в односвязную (рис. 4, б)необходимо добавить переход между узлом 103 и 113, то есть значения соответствующих элементов матрицы переходов сде- лать равными единице: p39,45=1 и p45,39=1. Схематично это можно изобразить следующим образом (рис. 4).
На рис. 4 красными точками обозначены узлы сетки, переходы между уз- лами обозначены красными стрелками. Согласно описанному алгоритму, пред- ставленная территория не будет односвязной (рис. 4, а). Для обеспечения одно- связности области необходимо добавить связь между узлами сетки под номе- рами 103 и 113 (рис. 4, б).
Таким образом, алгоритм сеточного метода схематически может быть представлен следующим образом (рис. 5).
Not
a reprint
Да Начало
Перенесение территории на координатную плоскость
Построение сетки
Формирование вектора узлов
Формирование вектора радиусов
Формирование матрицы переходов Можно регулировать
радиус покрытия
Конец
Нет
Формирование вектора радиусов покрытия
Рис. 3. Блок-схема алгоритма формирования матрицы переходов
На первом этапе работы алгоритма сформирована матрица переходов меж- ду узлами согласно алгоритму, представленному на рис. 2. После проверки и, при необходимости обеспечения односвязности области, ищется гамильтонов путь от первого узла к последнему.
Результатом работы алгоритма будет вектор узлов в последовательности облета. При необходимости движения сенсора по циклической траектории узел начала и узел конца должны совпадать.
For reading
only
а б
Рис. 4. Пример приведения двусвязной области к односвязной путем добавления связи между узлами 103 и 113: а – двусвязная область; б – односвязная область
Начало
Формирование матрицы переходов
Область односвязная
Обеспечение односвязности области
Поиск гамильтонового
пути Конец
Нет Да
Рис. 5. Блок-схема сеточного алгоритма
Not
a reprint
5. 3. Разработка алгоритма нахождения параметров энергоэффективной сенсорной сети с использованием статических и динамических датчиков
Практическая реализация модифицированного метода построения энер- гоэффективных сенсорных сетей и метода построения траектории движения датчиков с учетом минимизации энергопотребления позволяет пользователю развертывать энергоэффективные сенсорные сети и находить оптимальные тра- ектории облета территории.
Исходными данными при использовании статических сенсоров будут изображение территории, максимальный радиус покрытия, максимальный уро- вень пересечения зон покрытия, количество доступных к использованию сенсо- ров. Результатом будет набор пар парето-оптимальных значений радиуса по- крытия и уровня пересечения, при использовании которых достигается энер- гоэффективное покрытие территории сенсорами.
В случае динамических датчиков исходными данными будут изображение территории, максимальный радиус покрытия датчика, стартовые координаты и площадь минимального допустимого покрытия территории сенсором. Как ре- зультат, пользователь будет получать координаты энергоэффективной траекто- рии и значение радиуса покрытия в каждом узле траектории.
Алгоритм нахождения параметров энергоэффективного покрытия террито- рии статическими и динамическими датчиками можно представить следующим образом (рис. 6).
На первом этапе необходимо узнать координаты границы территории и ее площадь. В свою очередь, территория может быть любого размера и любой фор- мы. Для дальнейшего построения покрытия территории необходимо спроециро- вать территорию на координатную плоскость. Для этого в случае, если террито- рия изображена на белом фоне или фон отсутствует, предложен алгоритм авто- матического поиска границ территории. С заданной точностью (значение по умолчанию 1 пиксель) алгоритм, начиная с левого верхнего угла загруженного изображения, перебирает все пиксели слева направо. Если цвет следующего счи- тываемого пикселя не совпадает с цветом предыдущего, эта точка фиксируется как левая граничная точка и записывается в массив LeftPoints и обход останавли- вается. Далее начинается обход справа налево, чтобы найти правую граничную точку, которая запишется в массив RightPoints. После обхода всего изображения получили два массива LeftPoints и RightPoints соответственно. Для формирова- ния массива координат границ и сохранения направления обхода территории в полученном массиве первому элементу присваивается первый элемент массива LeftPoints, следующими элементами будут элементы массива RightPoints. После добавления всех элементов массива RightPoints к результирующему массиву до- бавляются все элементы массива LeftPoints в обратном порядке. В результирую- щем массиве первый и последний элементы должны совпадать, чтобы много- угольник был замкнутым. Схематически работу предложенного алгоритма мож- но изобразить следующим образом (рис. 7).
Следующим этапом будет выбор типа сенсоров: статические или динами- ческие. Далее, в случае динамических датчиков необходимо задать параметры радиуса покрытия, начальные координаты и значение минимально допустимой
For reading
only
площади покрытия территории датчиком. В случае статических датчиков поль- зователю необходимо задать радиус покрытия, уровень пересечения и количе- ство доступных датчиков.
Начало
Конец
Захват границы территории
Радиус покрытия
Сенсоры статичиские
Стартовые координаты, площадь минимального
покрытия
Уровень пересечения зон покрытия, количество
доступных датчиков
Нахождение параметров энергоэффективной сети
Нет Да
Рис. 6. Блок-схема алгоритма нахождения параметров энергоэффективной сен- сорной сети с использованием статических и динамических датчиков
а б
Рис. 7. Пример заполнения и обхода массивов точек LeftPoints и RightPoints: а – захват области; б – направление обхода массивов
Not
a reprint
После ввода необходимых параметров пользователь получит результат, в виде параметров, использование которых обеспечит построение энергоэффек- тивной сенсорной сети при максимизации покрытия территории.
6. Обсуждение результатов исследования нахождения параметров сенснорной сети на основе статических и динамических датчиков
Для нахождения оптимального значения покрытия территории использо- ван предложенный метод автоматического захвата и подсчета площади терри- тории. Исходные данные: площадь – 258754 м2, сенсоры с максимальным ради- усом охвата – r=50 м, количество датчиков – 40–50 штук. Результат нахожде- ния оптимальных параметров сети, при которых достигается максимальное по- крытие при минимальном энергопотреблении, представлен на рис. 8.
Рис. 8. Параметры сенсорной сети, которые обеспечивают энергоэффективное покрытие территории
Анализ рис. 8 показал, что среди представленных пар значений радиусов покрытия датчиков и значение уровня пересечения зон покрытия только семь
For reading
only
подходят при условии ограничения количества датчиков. Исходные значения количества датчиков Ninp, энергопотребления исходной сети Einp, оптимальное количество датчиков Nopt, энергопотребления результирующей сети Eopt, а также уменьшение энергопотребления представлено в табл. 1.
Таблица 1
Исходные и оптимальные характеристики сенсорной сети
R Ninp Einp Nopt Eopt Уменьшение энергопотребления
50 39 97500 32 80000 18 %
48,3 43 100314,3 35 81651,15 19 %
46,2 47 100318,7 38 81108,72 19 %
45 49 99225 40 81000 18 %
44,6 50 99458 41 81555,56 18 %
44 52 100672 42 81312 19 %
41 60 100860 49 82369 18 %
Согласно табл. 1, ограничение количества сенсоров в сети привело к уменьшению энергопотребления сети на 18–19 %.
В следующем эксперименте необходимо найти оптимальную траекторию при облете заданной территории. Также известна изначальная траектория движения сенсора, которая выбиралась экспертами. Радиус покрытия датчика равен 10 м.
а
Not
a reprint
б
Рис. 9. Траектории облета территории: а – входные данные; б – результат робо- ты алгоритма
Анализируя рис. 9, можно сделать вывод, что длина траектории, получен- ной в результате работы предложенного алгоритма (рис. 9, а), меньше длины траектории, составленной экспертом (рис. 9, б). Уменьшение значения энерго- потребления при использовании предложенного алгоритма представлено на рис. 10.
Значение энергопотребления вычислялось как энергопотребление датчика во время полета. Подсчеты велись в условных единицах и с предположением, что сенсор использует одну условную единицу энергопотребления на 10 метров полета. Энергопотребление при облете территории по входной траектории рав- но 76,51 условных единиц, а при результирующей траектории 42,54 условных единицы. Представленный график свидетельствует о том, что с использованием предложенного подхода нахождения оптимальной траектории движения датчи- ка достигается уменьшение энергопотребления при облете территории в 1,8 раза. Соответственно с этим, время автономного использования датчика увеличилось в 1,8 раза, что есть существенным выигрышем.
Полученные результаты показывают, что условия максимизации покрытия при минимизации энергопотребления удовлетворяются при очень близких зна- чениях параметров радиуса покрытия и уровня пересечения зон покрытия (рис. 8). Это обусловлено минимизацией непокрытой территории. При учете минимизации и ограничения количества используемых датчиков оптимальные
For reading
only
параметры сети близки или равны к максимально допустимым значениям ради- уса покрытия и уровня пересечения зон покрытия (рис. 8).
Энергопотребление при облете территории
0 10 20 30 40 50 60 70 80 90
Входная траектория Полученая траектория Энергопотребление при облете территории
Рис. 10. Энергопотребление датчика при входной и результирующей траектории При построении траектории движения во время облета территории удалось существенно снизить энергопотребление (рис. 10). В свою очередь, это увели- чило строк автономной работы датчика. Для применения результатов исследо- вания и корректного построения траектории движения сенсора необходимыми условиями будут:
1. Площадь территории значительно больше площади покрытия сенсора;
2. Граница территории является замкнутой кривой.
Среди нюансов нужно учитывать, что при покрытии нескольких отдель- ных несвязанных между собой участков территории алгоритм нужно применять для каждого участка отдельно. Следует отметить, что радиус покрытия и воз- можность регулировки радиуса покрытия влияют на форму и длину траектории, а также на снижения энергопотребления. Среди недостатков следует отметить смену направления движение сенсора только под прямым углом (рис. 9). В ка- честве направлений дальнейшего развития исследования следует рассматривать увеличение количества направлений движения датчика и возможность парал- лельного использования нескольких сенсоров во время построения траектории.
Предложенная схема практической реализации развертывания сенсорных сетей содержит выбор типа датчиков (статических или динамических). От вы-
Not
a reprint
бранного типа сенсоров зависит метод, который используется при дальнейшем построении покрытия. В дальнейших исследованиях следует рассматривать возможность одновременного использования статических и динамических сен- соров при построении покрытия территории.
7. Выводы
1. Разработан модифицированный метод построения сенсорной сети в условиях максимизации покрытия при минимизации энергопотребления. Отли- чительной особенностью полученного в результате модификации метода, кроме ограничения количества датчиков, является критерий минимизации количества используемых сенсоров, который учитывается вместе с критериями минимиза- ции непокрытой территории и минимизации энергопотребления. Решения по- ставленной задачи обеспечивает построение энергоэффективных сенсорных сетей максимального покрытия территории с использованием минимального количества датчиков и уменьшением энергопотребления на 19 %.
2. Разработан метод построения траектории движения датчиков с учетом минимизации энергопотребления, который позволяет минимизировать длину траектории с регулировкой радиусов покрытия динамического сенсора в каж- дой точке траектории. Такой подход позволяет минимизировать энергозатраты сенсора во время движения и обеспечивает максимальное покрытие труднодо- ступных участков.
3. Разработан алгоритм развертывания сенсорных сетей на основе опти- мальности энергопотребления, что позволяет сформировать оптимальные па- раметры сети, а также автоматизировать процесс захвата границы территории с загруженного изображения с точностью в один пиксель. Среди особенностей разработанного алгоритма следует отметить возможность использования как статических, так и динамических датчиков, автоматизирований захват границы территории, минимальный набор исходных параметров, возможность выбора пользователем необходимых параметров сети среди полученных результатов при построении покрытия.
Литература
1. Grimes, C., Dickey, E., Pishko, M. (Eds.) (2005). Encyclopedia of Sen- sors: 10-Volume Set. Vols. 1–10. The Pennsylvania State University, University Park. URL: http://www.aspbs.com/eos.html
2. Blaauw, F. J., Schenk, H. M., Jeronimus, B. F., van der Krieke, L., de Jonge, P., Aiello, M., Emerencia, A. C. (2016). Let’s get Physiqual – An intuitive and generic method to combine sensor technology with ecological momentary assess- ments. Journal of Biomedical Informatics, 63, 141–149. doi:
https://doi.org/10.1016/j.jbi.2016.08.001
3. Internet of Everything изменит мир к лучшему (2012). URL:
https://www.g-news.com.ua/news/10-it/-/13936-internet-of-everything-izmenit-mir- k-luchshemu.html
For reading
only
4. Warneke, B., Last, M., Liebowitz, B., Pister, K. S. J. (2001). Smart Dust:
communicating with a cubic-millimeter computer. Computer, 34 (1), 44–51. doi:
https://doi.org/10.1109/2.895117
5. Егоров, Л. Л., Кологривов, В. А., Мелихов, С. В. (2009). Алгоритм расчета зон покрытия базовых станций сотовой связи. Доклады ТУСУРа, 19, 15–21.
6. Wu, H., Liu, Z., Hu, J., Yin, W. (2020). Sensor placement optimization for critical-grid coverage problem of indoor positioning. International Journal of Dis- tributed Sensor Networks, 16 (12), 155014772097992. doi: https://doi.org/
10.1177/1550147720979922
7. Данилюк, С. Л. (2016). Концептуальні підходи до вирішення задачі оптимального розміщення сенсорів в області екологічного моніторингу. Су- часні інформаційні технології у сфері безпеки та оборони, 1 (25), 45–48.
8. Астраков, С. Н., Ерзин, А. И., Залюбовский, В. В. (2009). Сенсорные сети и покрытие плоскости кругами. Дискретн. анализ и исслед. опер., 16 (3), 3–
19.
9. Petrivskyi, V., Shevchenko, V., Bychkov, O., Brazhenenko, M. (2020).
Information Technology of the Increasing Sensors Term of Use Considering Their Movement. 2020 IEEE XVIth International Conference on the Perspective Technolo- gies and Methods in MEMS Design (MEMSTECH). doi: https://doi.org/
10.1109/memstech49584.2020.9109431
10. Петрівський, В. Я., Шевченко, В. Л., Бражиненко, М. Г. (2019).
Збільшення часу роботи датчиків шляхом регулювання енерговитрат. Системи Обробки Інформації, 3 (158), 36–41.
11. Luo, C., Chen, W., Li, D., Wang, Y., Du, H., Wu, L., Wu, W. (2021).
Optimizing flight trajectory of UAV for efficient data collection in wireless sensor networks. Theoretical Computer Science, 853, 25–42. doi: https://doi.org/10.1016/
j.tcs.2020.05.019
12. Haider, S. K., Jiang, A., Almogren, A., Rehman, A. U., Ahmed, A., Khan, W. U., Hamam, H. (2021). Energy Efficient UAV Flight Path Model for Clus- ter Head Selection in Next-Generation Wireless Sensor Networks. Sensors, 21 (24), 8445. doi: https://doi.org/10.3390/s21248445
13. Amar, M. A., Khaznaji, W., Horchani, L. (2020). PTSP Solution Strate- gy for Motion Trajectory of UAV in Ubiquitous Sensor Network. Procedia Computer Science, 176, 3191–3199. doi: https://doi.org/10.1016/j.procs.2020.09.130
14. Ghosh, N., Sett, R., Banerjee, I. (2017). An efficient trajectory based rout- ing scheme for delay-sensitive data in wireless sensor network. Computers & Electrical Engineering, 64, 288–304. doi: https://doi.org/10.1016/j.compeleceng.2017.06.003
15. Miles, J., Kamath, G., Muknahallipatna, S., Stefanovic, M., Kubichek, R.
F. (2013). Optimal trajectory determination of a single moving beacon for efficient localization in a mobile ad-hoc network. Ad Hoc Networks, 11 (1), 238–256. doi:
https://doi.org/10.1016/j.adhoc.2012.05.009
16. Petrivskyi, V. Y., Shevchenko, V. L., Bychkov, O. S., Loza, V. M.
(2020). Information technology of territory covering by sensors with the constant in- tersection level and cost minimization. Collection of Scientific Works of the Military
