автореферат диссертации по радиотехнике и связи, 05.12.13, диссертация на тему:Разработка алгоритмов выбора головного узла в кластерных беспроводных сенсорных сетях

00460953?

На правах рукописи

Ахмед

Абд Эльфтах Ахмед Салим

РАЗРАБОТКА АЛГОРИТМОВ ВЫБОРА ГОЛОВНОГО УЗЛА В КЛАСТЕРНЫХ БЕСПРОВОДНЫХ СЕНСОРНЫХ СЕТЯХ

Специальность 05.12.13 - Системы, сета и устройства телекоммуникаций

Автореферат диссертации на соискание ученой степени кандидата технических наук

3 0 СЕН 201 о

Санкт-Петербург 2010

004609537

Работа выполнена в Санкт-Петербургском государственном университете телекоммуникаций им. проф. М.А. Бонч-Бруевича, на кафедре сетей связи.

Научный руководитель:

доктор технических наук, профессор А.Е. Кучерявый

Официальные оппоненты:

доктор технических наук, профессор М.А. Сивере,

кандидат технических наук, доцент Ю.В. Семёнов

Ведущая организация:

ОАО «Гипросвязь-СПб»

Защита состоится

2010 г. в

у* Я

■7 часов на за-

седании диссертационного совета Д.219.004.02 при Санкт-Петербургском государственном университете телекоммуникаций им. проф. М.А. Бонч-Бруевича по адресу: 191186, Санкт-Петербург, наб.р.Мойки, 61, ауд. 205.

С диссертацией можно ознакомиться в библиотеке университета.

Отзыв на автореферат в двух экземплярах, заверенный печатью учреждения, просим направлять по вышеуказанному адресу на имя ученого секретаря диссертационного Совета.

П

Автореферат разослан « 2010 г.

Ученый секретарь диссертационного Совета к.т.н., доц

В.Х. Харитонов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность исследований. Беспроводные сенсорные сети WSN (Wireless Sensor Network) представляют собой самоорганизующиеся сети, состоящие из множества беспроводных сенсорных узлов, распределенных в пространстве и предназначенных для мониторинга характеристик окружающей среды или объектов, расположенных в ней. Пространство, которое покрывается сенсорной сетью, называют достаточно часто сенсорным полем. Собственно беспроводные сенсорные узлы представляют собой миниатюрные устройства с ограниченными ресурсами: зарядом батареи, объемом памяти, вычислительными возможностями и т.д. Однако объединение большого числа этих элементов в сеть обеспечивает возможность получения реальной картины происходящего в рамках этого сенсорного поля. Беспроводные сенсорные узлы могут собирать информацию о наблюдаемых явлениях и передавать ее далее для обработки и анализа. Примерами собираемой информации могут быть данные о температуре, влажности, условиях освещения, сейсмической активности и т.д. Такие данные могут быть использованы как для выявления каких-либо событий, так и для управления ими. В качестве примера можно привести использование сенсоров для автоматического пожаротушения в случае получения тревожных сообщений о возгорании (Ren, 2004).

В целом беспроводные сенсорные сети характеризуют новую эру развития общества и сетей, так называемое и-общество и й-сети (Kim, 2005, Кучерявый 2005, 2006). Не случайно в последнее время в литературе все чаще употребляется название USN (Ubiquitous Sensor Network).

Архитектура беспроводной сенсорной сети изображена на рис. 1.

Кластерная организация (рис. 2) считается эффективной и масштабируемой для решения подобных задач, но лишь при условии рационального выбора головного узла в кластерной сети в конкретный момент времени. Действительно являющийся головным в момент времени 1\ сенсорный узел не обязательно должен быть им же в момент времени /2, ибо существующий головной узел уже может затратить достаточно большое

Рис. 1. Архитектура беспроводной сенсорной сети

количество энергии на передачу сообщений от всех сенсорных узлов кластера к моменту времени t2 Поэтому в момент времени ?2 головным узлом в кластере может быть назначен и иной сенсорный узел, сохранивший к этому времени наибольший энергетический запас.

Одним из самых известных механизмов, обеспечивающих функционирование сенсорных сетей и выбор головных узлов является алгоритм LEACH (Low Energy Adaptive Cluster Hierarchy). Алгоритм LEACH предусматривает вероятностный выбор сенсорного узла на роль головного в начале функционирования сенсорной сети, а впоследствии - ротацию на основе энергетических характеристик сенсорных узлов. Подобное решение продлевает длительность функционирования сенсорных узлов и сети в целом, но, как будет показано далее по результатам моделирования не решает задачи обеспечения лучшего покрытия в течение достаточно длительного времени, поскольку при создании LEACH такая задача и не ставилась.

Существует достаточно много алгоритмов, которые в той или иной степени пытаются улучшить LEACH. Это и алгоритмы, основанные на максимуме остаточной энергии, местоположении узла-кандидата в головной кластерный узел но отношению к другим узлам, информации о топологии сети в текущий момент времени. Алгоритм HEED (Hybrid Energy - Efficient Distribution) использует гибридный критерий для выбора головного узла на основе анализа" остаточной энергии и расположения близлежащих узлов. Все эти алгоритмы направлены, как и LEACH, в первую очередь на максимизацию длительности функционирования сенсорных узлов и сети в целом.

Однако с развитием сенсорных сетей появились и другие задачи, требующие пристального внимания. Например, задача о качестве обслуживания, являющемся важнейшей метрикой для любой сети, в том числе и сенсорной. Действительно, очень важна проблема увеличения срока жизни сенсорной сети. Однако если эта сеть не будет выполнять свои функции в требуемом объеме, то и сама задача увеличения срока жизни сенсорной сети, не удовлетворяющей требованиям по качеству обслуживания, схоластична.

В системах мониторинга одним из важнейших требований является его непрерывность, т.е. обеспечение мониторинга параметров на всем пространстве или на всем процессе. Исходя из сказанного, в настоящей работе поставлена задача разработать алгоритм выбора головного узла кластера, который обеспечивал бы лучшее покрытие заданной для мониторинга области двумерного пространства (плоскости) в течение достаточно длительного периода времени. Этот подход означает в целом оптимизацию как срока жизни сенсорной сети, так и оптимизацию выполнения сенсорной сетью своих функциональных задач с заданным качеством обслуживания в течение достаточно длительного периода времени.

С учетом изложенного разработка новых алгоритмов выбора головных узлов кластера в беспроводных сенсорных сетях представляется актуальной, впрочем как и сам предмет исследования - беспроводные сенсорные сети.

Цель и задачи исследования. Цель диссертации состоит в разработке новых алгоритмов выбора головного узла кластера в беспроводных сенсорных сетях.

Для достижения поставленной цели в диссертации последовательно решены следующие задачи:

• анализ существующих алгоритмов выбора головного узла в кластере сенсорной сети;

• разработка нового алгоритма централизованного выбора головного кластерного узла для гомогенных сенсорных сетей на основе диаграмм Вороного,

• разработка нового алгоритма выбора головного кластерного узла для обеспечения наибольшего покрытия в гомогенных сенсорных сетях;

• разработка нового алгоритма выбора головного кластерного узла для обеспечения наибольшего покрытия в гетерогенных сенсорных сетях;

• разработка нового алгоритма выбора головного кластерного узла для обеспечения наибольшего покрытия в мобильных сенсорных сетях с использованием различных предикторов.

Методы исследования. Для решения поставленных задач используются методы вычислительной геометрии, теории оптимизации, прогнозирования, имитационного моделирования.

Научная новизна. В результате исследований получены следующие новые научные результаты:

• разработан новый алгоритм централизованного выбора головного кластерного узла для гомогенных сенсорных сетей CHS и доказано, что предложенный алгоритм обладает улучшенными характеристиками по энергетической эффективности по сравнению с базовым алгоритмом LEACH;

• разработан новый алгоритм выбора головного кластерного узла для обеспечения наибольшего покрытия в гомогенных сенсорных сетях CHSC и доказано, что предложенный алгоритм обеспечивает лучшие показатели качества обслуживания (¿-покрытие) во всем диапазоне значений к, чем базовый алгоритм LEACH. При этом обеспечивается также большее значение числа живущих сенсорных узлов во времени;

• разработан новый алгоритм выбора головного кластерного узла для обеспечения наибольшего покрытия в гетерогенных сенсорных сетях САС и доказано, что предложенный алгоритм обеспечивает более длительный цикл жизни сенсорной сети и лучшее А-покрытие во всем диапазоне значений к, чем базовый алгоритм LEACH;

• разработан комбинированный критерий прогнозирования поведения мобильной беспроводной сенсорной сети, включающий в себя критерии связности, покрытия, мобильности и остаточной энергии;

• разработан новый алгоритм выбора головного кластерного узла для мобильных сенсорных сетей DSA, основанный на комбинированном критерии прогнозирования;

• доказано, что критерий связности является наиболее сильным из всех рассмотренных критериев в плане обеспечения жизненного цикла беспроводной сенсорной сети;

• доказано, что алгоритм DSA обеспечивает более длинный жизненный цикл существования беспроводной сенсорной сети, чем базовый алгоритм LEACH-M, как для централизованного расположения шлюза, так и для его расположения вне сети.

Личный вклад. Все основные результаты диссертации получены автором лично.

Практическая ценность работы. Результаты диссертационной работы используются в СПбГУТ им. проф. М.А. Бонч-Бруевича при чтении лекций по курсу «Современные проблемы науки в области телекоммуникаций».

Апробация работы. Основные результаты диссертации докладывались и обсуждались на 64-й Научно-технической конференции СПбНТОРЭС им. A.C. Попова. (С.-Петербург, 2009), 11-й Международной конференции IEEE по новым технологиям телекоммуникаций «Ubiquitous ICT Convergence Makes Life Better ICACT'2009, (Korea, Phoenix Park, February 2009), Международной конференции IEEE по новейшим достижениям в телекоммуникациях ICUMT 2009 (С.-Петербург, Октябрь 2009), 12-й Международной конференции IEEE ICACT'2010 (Korea, Phoenix Park, February 2010), а также на заседании кафедры «Сети связи».

Публикации. По материалам диссертации опубликовано 6 работ.

Объем и структура. Диссертационная работа состоит из введения, 5 глав, заключения и списка литературы из 57 наименований.

Основные положения, выносимые на защиту:

• алгоритм централизованного выбора головного кластерного узла для гомогенных сенсорных сетей CHS на основе диаграмм Вороного с улучшенными характеристиками энергетической эффективности по сравнению с базовым алгоритмом LEACH;

• алгоритмы выбора головного кластерного узла в гомогенных CHSC и гетерогенных CSC беспроводных сенсорных сетях, обеспечивающие лучшие показатели качества обслуживания (¿-покрытие) во всем диапазоне значений к

и большее значение числа живущих узлов во времени по сравнению с базовым алгоритмом LEACH;

• комбинированный критерий прогнозирования поведения мобильной сенсорной сети, включающий в себя критерии связности, покрытия, мобильности и остаточной энергии;

• алгоритм выбора головного кластерного узла в мобильных сенсорных сетях DCA, обеспечивающий более длительный жизненный цикл существования беспроводной сенсорной сети, чем базовый алгоритм LEACH-M, как для централизованного расположения шлюза, так и для его расположения вне сети.

Во введении обосновывается актуальность исследований, формируются цель и задачи работы.

В первой главе анализируются существующие работы в предметной области. В диссертации проводятся исследования по разработке новых алгоритмов для иерархических беспроводных сенсорных сетей.

Основной проблемой при создании алгоритмов для иерархических беспроводных сенсорных сетей является выбор головного узла кластера. Существует два подхода к выбору головного узла кластера: случайный выбор и предопределенный. Рассмотрим далее алгоритм случайного выбора головного узла, при использовании которого ротация головных узлов может производиться из всех членов кластера с учетом их характеристик в текущий момент времени.

Иерархический алгоритм адаптивной кластеризации с низким потреблением энергии LEACH (Low-Energy Adaptive Clustering Hierarchy) (Heinzelman, 2002) предполагает обеспечение баланса расхода энергии в беспроводной сенсорной сети. Алгоритм LEACH является базовым, и существует много алгоритмов, основанных на нем. Базовая идея LEACH состоит в следующем: сенсорные узлы могут быть случайным образом выбраны как головные на основе предыдущей информации об их функционировании. При этом в кластере каждый сенсорный узел генерирует случайное число от 0 до 1. Каждый сенсорный узел имеет порог п{1еасн), который соответствует предварительно определенному числу головных сенсорных узлов в сети. Если интегрированное случайное число меньше, чем Th(LEACH), то сенсорный узел может стать головным; в противном случае этот узел остается только членом кластера. Вычисление Th(LEACii) является ключевой задачей при реализации алгоритма LEACH.

В (1) р - предопределенный процент головных узлов среди всех сенсорных узлов. Оптимальное значение р оценивается в 5% от общего числа сенсорных узлов.

СОДЕРЖАНИЕ РАБОТЫ

О)

Текущий интервал функционирования сенсорной сети определяется как г, G - число сенсорных узлов, которые не были выбраны головными за последние Ир интервалов. Это уравнение определяет тот факт, что узел, который был головным в последних интервалах функционирования сенсорной сети, не имеет шансов вовсе или имеет минимальные шансы снова стать головным в рассматриваемом интервале. В результате, такой выбор головного узла способствует балансу энергетических возможностей каждого из сенсорных узлов сети. Кроме того, при выборе головного узла другие сенсорные узлы выбирают одного из членов кластера для контроля за мощностью получаемого сигнала (RSS - Received Signal Strength) от головного узла

После того как кластер сформирован, головной узел широкополосным способом рассылает расписание передачи и запрашивает своих членов кластера о передаче данных на основе известного ТОМА подхода. В последующих фазах головной узел является ответственным за агрегирование данных и передачу их на шлюз и в сеть связи общего пользования. Весь сбор данных локализуется в кластере. После определенного времени нахождения в стабильной фазе, сеть снова переходит в стадию формирования. При этом следует отметить, что стадия формирования существенно короче, чем стабильная. В связи с этим LEACH имеет достаточно короткий заголовок.

LEACH является очень эффективным алгоритмом. С его помощью достигается снижение энергозатрат в 7 и более раз по сравнению с прямым взаимодействием сенсорных узлов и от 4 до 8 раз по сравнению с другими алгоритмами маршрутизации (Heinzelman, 2002). В то же время LEACH не дает гарантий по выбору «хорошего» сенсорного узла в качестве головного узла кластера. Поскольку в алгоритме LEACH нет предположения о текущем энергетическом состоянии сенсорного узла, то в качестве головного может быт выбран давно неизбираемый член кластера с неудовлетворительными энергетическими характеристиками.

Гибридный распределенный энергоэффективный алгоритм кластеризации (HEED - Hybrid Energy - Efficient Distributed) (Younis, 2004) является развитием алгоритма LEACH. Для преодоления проблемы выбора «плохого» члена кластера в качестве головного узла в LEACH алгоритм HEED предлагает использовать предопределенный выбор головного узла. В алгоритме LEACH, когда предполагается, что каждый член кластера имеет равновероятные шансы стать головным узлом кластера, сеть может выбрать в качестве головного узел, который будет иметь наихудшие показатели по энергосбережению и соответственно по возможности выхода из строя. Алгоритм HEED ставит вероятность выбора узла головным в зависимости от его существующей энергоспособности и принимает решение в зависимости от энергетических затрат. Кроме того, алгоритм HEED учитывает многоранговую природу взаимосвязей в беспроводных сенсорных сетях для дальнейшего энергосбережения.

HEED использует информацию о текущей энергоемкости сенсорного узла как основной параметр для выбора члена кластера в качестве головного узла. Выбранный в качестве головного узел информирует близлежащие узлы о том,

что он стал головным. Эти сообщения от головных узлов используются сенсорными узлами для выбора себе наилучшего головного узла и, соответственно, кластера. В случае, если головной узел кластера находится достаточно далеко от шлюза с сетью связи общего пользования, он может передать агрегированную информацию через головной узел другого кластера.

Алгоритм осведомленности об остаточной энергии (ERA - Energy Residue Aware) (Chen, 2007) представляет собой еще один алгоритм иерархической маршрутизации. Алгоритм ERA также является развитием алгоритма LEACH и включает в анализ вопроса выбора головного узла в кластере затраты на осуществление взаимодействия. Затраты на осуществление взаимодействия включают в себя остаточную энергию головного узла кластера (Есн-гет)> затраты энергии на взаимодействие головного узла с базовой станцией (Et0Bs)> затраты энергии на взаимодействие членов кластера с головным узлом (Е,оСц). В этом состоит принципиальная разница с алгоритмом HEED: алгоритм ERA использует ту же схему выбора головного узла, что и LEACH (случайный выбор), но обеспечивает лучший выбор головного узла за счет использования дополнительных параметров, определенных выше. Уравнения (2) помогают определять затраты кластера при выборе того или иного узла в качестве головного и найти головной узел кластера с максимальной остаточной энергоемкостью. В (2) множество Sc является множеством для головных узлов, множество Sx является множеством для членов кластера.

(ßcH-res)l = tEcH-rm)i ~ (ßtoBs)i- ' е Sc

(ElumCH-res)i ~ Эпопеи-rem)i ~ (EtoBs)ii, j E SN,V i £ Sc (2)

max l(ECH-res)t + IV i E Sc } j£S„

Алгоритм PEGASIS (Power-Effecient Gatharingin Sensor Information Systems) — эффективная по мощности система сбора информации от сенсоров — не имеет прямого отношения к кластерной организации беспроводных сенсорных сетей, но будет рассмотрен далее для полноты анализа основных алгоритмов маршрутизации в WSN.

Алгоритм PEGASIS (Lindsey, 2002; Lindsey, 2008) предусматривает основанный на LEACH алгоритм организации сенсорных узлов в последовательную цепочку и периодическое обновление первого узла в цепочке так же, как это предусмотрено в кластерных WSN. В алгоритме PEGASIS цепочка формируется таким образом, чтобы сенсорные узлы взаимодействовали только с ближайшими и только один из узлов являлся бы передающим информацию на базовую станцию в каждом из интервалов функционирования сенсорной сети. Для определения ближайших узлов каждый узел использует значение RSS для оценки расстояния до узла и затем выбирает значение мощности сигнала так, чтобы взаимодействовать только с ближайшими узлами.

Построение цепочки позволяет минимизировать расстояние, на которое передается информация, а ротация первого сенсора в цепочке увеличивает длительность функционирования отдельных сенсорных узлов. Такой подход позволяет для беспроводных сенсорных сетей снизить общее

энергопотребление и увеличить длительность функционирования WSN в целом.

Алгоритм PEGASIS лучше алгоритма LEACH на 100-200% в отношении гибели 1, 25, 50 и 100% узлов сенсорной сети и топологий (Lindsey, 2008). Однако цепочки алгоритма PEGASIS создают дополнительные задержки при передаче информации. Кроме того, динамическое изменение топологии в алгоритме PEGASIS требует, чтобы каждый сенсорный узел знал об энергетических возможностях своих ближайших соседних узлов для вычисления маршрута передачи данных. Последнее существенно усложняет заголовок и помимо этого приводит к проблемам при функционировании сенсорной сети в условиях большой нагрузки.

Для снижения задержки был предложен иерархический алгоритм PEGASIS (Lindsey, 2002). В этом алгоритме в качестве целевой функции для минимизации используется «энергия х метрика задержки». Алгоритм иерархический PEGASIS использует CDMA для кодирования сигналов и пространственного разделения сенсорных узлов. Алгоритм строится в виде иерархического дерева, причем каждый выбранный узел какого-либо уровня передает данные на узел верхнего уровня иерархии. Этот метод позволяет обеспечить параллельную передачу данных и уменьшить задержки сигналов до значений 0(igN), где N — число узлов.

Алгоритм циклической очередности выбора головного узла в кластере RRCH (Round-Robin Cluster Head) (Nam, 2007) предполагает формирование кластера только единовременно. После фиксации кластера для выбора головного узла в нем на протяжении его функционирования используется известный метод циклической очередности. Так же как и в LEACH, каждый из членов кластера имеет возможность стать головным узлом, головной узел задает расписание для членов кластера и т.д.

С учетом простоты процесса формирования кластера RRCH избегает потерь энергии при рекластеризации. Естественно, что с точки зрения энергетических параметров RRCH имеет при этом лучшие результаты, чем LEACH. Однако жесткая фиксация кластера приводит к тому, что в целом один из кластеров может перестать выполнять свои функции с надлежащим качеством обслуживания быстрее, чем в LEACH, в котором как раз рекластеризация и приводит к возможности распределить ресурсы равномерно между всеми кластерами одной сенсорной сети.

Отметим, что в целом проблеме качества обслуживания при использовании тех или иных алгоритмов маршрутизации в беспроводных сенсорных сетях до последнего времени не уделялось должного внимания. И это естественно, поскольку проблема состояла в основном в создании сенсорных сетей. В настоящее же время рынок сенсорных сетей растет настолько интенсивно, что уже в этом году его объем превысит 50 млрд. $. Повсеместное и масштабное применение сенсорных сетей, в том числе для задач мониторинга климата в целом, параметров окружающей среды и т.д., ставит задачу обеспечения качества обслуживания в сенсорных сетях как одну из важнейших.

Исходя из сказанного, разработка новых алгоритмов для выбора головного узла в беспроводных сенсорных сетях в настоящее время должна проводиться с учетом требований по качеству обслуживания, что и осуществляется в последующих главах диссертации.

Вторая глава посвящена разработке алгоритма выбора головного узла для гомогенных WSN с использованием алгоритма Вороного.

Диаграммы Вороного (Aurenhammer, 1991), также известные как мозаики Дирихле, представляют собой одну из фундаментальных структур данных в вычислительной геометрии. Рассмотрим сначала особенности диаграмм Вороного как геометрической конструкции.

Беспроводные сенсорные сети являются гомогенными, если все их сенсорные узлы имеют одинаковые память, вычислительные возможности, мощность батареи, измеряемые параметры и телекоммуникационные возможности. В противном случае сенсорные сети называются гетерогенными.

Областью покрытия (или областью детектирования) сенсора в некотором сенсорном поле называется область, в которой любое событие из этого поля может быть детектировано сенсором ¡¡. Набор сенсоров AV(sj является близлежащим к сенсору s,, если все сенсоры этого набора размещены в области покрытия s,. Сетевым покрытием сенсора st в сенсорном поле является такая область, в которой сенсор s, может обеспечивать взаимосвязь с любым сенсором этой области. Набор сенсоров SNfo) является близлежащим к сенсору s¡, если все сенсоры этого набора размещены в области сетевого покрытия Si.

Пусть s = s„} - конечное множество из п фрагментов на плоскости. Диаграмма Вороного для S, обозначаемая Vor(S), является фрагментом плоскости, содержащей s в составе п ячеек vc{s,\is isn таких, что каждая ячейка Вороного включает только один фрагмент s,, причем любая точка, расположенная в vcближе к s,, чем любой другой фрагмент в S.

На рис. 3 триангуляция Делоне (жирные линии) поверх диаграммы Вороного (пунктирные линии) представляет возможную беспроводную сенсорную сеть в виде выпуклого многоугольника. Конечные точки ребер ячейки Вороного образуют вершины Вороного. Диаграмма Вороного для множества S является объединением ячеек Вороного для всех фрагментов, входящих в S. Триангуляция Делоне, обозначенная далее dt(S), дуальна с диаграммой Вороного. Граф dt(S) имеет ребра между двумя фрагментами, если и только если их ячейки Вороного имеют части ребра.

Некоторые теоремы по связности и покрытию для диаграмм Вороного будут полезны далее при разработке алгоритма выбора головного узла:

поверх диаграммы Вороного для беспроводной сенсорной

• Пусть г есть радиус покрытия сенсорной окружностью и к > з. Выпуклая область А гарантирует ¿-покрытие, если точно к гомогенных сенсоров расположены в ней и если ширина А не превосходит г.

• Пусть к>з. Пересечение ¿-покрытия сенсорными окружностями не пустое, если и только если пересечение любых трех из этих к окружностей не является пустым. Иллюстрация к этой теореме приведена на рис.4, а.

• Пусть г есть радиус покрытия сенсорной окружностью я к>з. Сенсорное поле является ¿-покрытым, если любой релеевский треугольник (Нетге1тап, 2002) области шириной г в сенсорном поле содержит по крайней мере к активных сенсорных узлов.

• Пусть к > з. Поле является гарантированно ¿-покрытым, если для любого фрагмента поля, в котором есть по крайней мере один смежный фрагмент, такое пересечение (линза) содержит по крайней мере к активных сенсоров (рис. 4, Ь)

Рис. 4. Пересечение трех сенсорных окружностей (а) и смежные фрагменты поля (Ь)

Алгоритм выбора головного узла кластера CHS:

for each round a slicing grid do

2 3

for each cluster do

CHL = {}

4

Select s, where s, with six slices

5

6 7

CHL = CHL u st end for

Sink translate packet include chl for each senor sf do

8

9: 10 U 12

13

14

15

16 17

if s, e CHL then

Remove s, from chl Update chl Forward chl

else

Forward chl

end if end for end for

Пусть все сенсоры имеют одинаковые покрытия и сетевое покрытие радиусов есть г и И соответственно. Тогда достаточно легко построить сеть, которая покроет заданное поле. Для этой цели предлагается структура сенсорного поля, разделенная на релеевские треугольники со стороной г, такие, что два смежных фрагмента пересекаются, сложенные как линзы. В результате получаем релеевскую решетку, изображенную на рис. 5. Алгоритм выбора приведен на с. 10.

Моделирование осуществляется на языке С#.ЫЕТ. Сеть из 100 сенсорных узлов размещается в зоне размером 200x200 м2. Размещение сенсорных узлов с координатами (х, у) проводится случайным образом в соответствии с равномерным распределением.

Далее для простоты будем называть такой способ построения сенсорной сети случайным. При неравномерном распределении построение сенсорной сети связано с тем, что какие-либо узлы сенсорной сети группируются в определенной ее части вместе, что может обеспечить большее покрытие именно в этой части сенсорного поля. Будем называть такое построение сети неравномерным.

На рис. 6 представлены обзоры отображений процесса моделирования на С#.№,Т для предложенного алгоритма СШ, а в табл. 1 - параметры, используемые при моделировании.

Рис. 6. Экранные формы

Таблица 1

Параметры и их значения для моделирования__

Параметр Обозначение Значение

Первичная энергия на узел Е V

Гх/ То: ЕеЫс 50 пЦЬИ

Постоянное усиление ч* 10 рЦЬп/т2

Мультисетевая постоянная 0.0013 р¡/ЬН/т2

Потери на участках (экспоненциальные) п 2

Порог энергии головного узла % ю-■»

Размер пакета К 30 Ьу^е5

Скорость пакета в 1 раскеЬ/5

* ДА.Д

УуУУУУ V у^.ул:

.Л А 7\ДЛЛ ЛЛ ДА/

А'Л А Л1 А "Л "А Д "Л Л"

■' ч/ V V у _V_\

Рис. 5. Релеевская решетка для сенсорного поля

Продолжение табл. 1

Параметр Обозначение Значение

Широкополосная зона вещания R 70 т

Радиус сенсора г 15 т

Радиус кластера 2 г

Перечень и значения параметров являются типовыми и применялись для оценки эффективности алгоритма LEACH и др.

Сравнительные характеристики приведены на рис. 7, анализ которого показывает существенное преимущество разработанного алгоритма CHS над

базовым алгоритмом

LEACH. Действительно, в одной и той же сенсорной сети при использовании базового алгоритма LEACH энергия в 200 Дис расходуется менее чем за 2*104 с, в то время как в предложенном алгоритме это время составляет около ЗТО4 с.

В третьей главе разработан новый алгоритм выбора головного узла в кластере для решения проблем покрытия CHSC (Cluster Head Selection for Coverage), который является распределенным кластерным алгоритмом и может быть использован для однородных сенсорных сетей, где наиболее важным параметром является полное покрытие в течение достаточно длительного времени. Предложенный алгоритм основывается на периметрическом покрытии и выборе наилучшего кандидата на уровень головного узла кластера из всех сенсорных узлов, входящих в рассматриваемую сеть. Примером сетей, где полное покрытие является критичным параметром качества обслуживания являются сети мониторинга, например мониторинга климата.

Предлагаемый алгоритм назван CHSC (Cluster Head Selection for Coverage) - выбор головного узла в кластере для покрытия. В алгоритме CHSC вводится понятие кластерного радиуса г.,.

На рис. 8 изображена однородная кластерная сенсорная сеть, покрывающая полностью некую плоскость А. Как уже отмечалось выше, любой из обычных сенсорных узлов (на рис. 8 изображен как член кластера) может стать головным, как впрочем и наоборот. Параметр гсл в определенной степени вносит упорядоченность в структуру кластерной сенсорной сети на рис. 8. При этом любой сенсорный узел в пределах своего кластера обращается к головному узлу напрямую (one-hop), в то время как передача информации от головного узла к шлюзу может быть и многошаговой (multi-hop).

Алгоритм CHSC вначале собирает информацию об остаточной энергии

Вяерпи (джоули)

Рис. 7. Отображение процесса моделирования для CHS

для всех сенсорных узлов (если остаточная энергия Е^-З-го сенсорного узла равна 0, то этот узел, естественно, исключается из дальнейшего функционирования в сенсорной сети). Информация об остаточной энергии рассылается каждым сенсорным узлом в области где - радиус

действия сенсорного узла в сети для выполнения функций мониторинга. После получения информации от всех соседей каждый сенсорный узел выполняет алгоритм СРС для проверки периметрического покрытия. Принимая во внимание, что сенсорные узлы находятся в статическом положении, ближайшие узлы должны обменяться информацией о своем местоположении только один раз - в начале жизненного цикла сенсорной сети.

Рис. 8. Однородная кластерная сеть и параметр ъ алгоритма СШС

Каждый из сенсорных узлов ожидает окончания активизации сети и затем может объявить себя новым головным узлом в кластере для исходящих соединений. Это происходит в том случае, если за время активации сенсорный узел не получил никаких информационных сообщений от любых других узлов, объявивших себя головными. При объявлении себя головным узлом сенсорный узел рассылает это информационное сообщение всем сенсорным узлам, находящимся в пределах расстояния Принятие решения об объявлении себя головным узлом осуществляется на основе возможности обеспечения лучшего покрытия и наличия достаточной энергии > где Е,], - пороговое значение необходимой энергии для головного узла в кластере). Информационное сообщение содержит информацию о местонахождении нового головного узла кластера. После получения сообщения от нового головного узла кластера все сенсорные узлы в пределах гс( исключают себя из дальнейшего рассмотрения на роль головного узла.

Каждый сенсорный узел содержит таблицу всех головных узлов, от которых он получил информационное сообщение об объявлении себя головным, на доступном для узла расстоянии. Эта информация используется сенсорным узлом для принятия решения о том, членом какого кластерного узла этот узел будет. Иногда может случиться, что два сенсорных узла с подходящими характеристиками объявляют себя головными в пределах одного

и того же -; Тогда головной узел в конечном итоге определяется по наибольшей остаточной энергии.

Алгоритм выбора головного узла для покрытия CHSC:_

1: 5 = {s : Ei s) > Oj, £('j>residual energy of sensor node s

2: 5CH = {)

3: CL(_sJ = {] //The members of cluster head 4: while 5 - {} do

5: if (CPC(j,) -- Ture) and (Eis,) > £,„) then 6: Sen = Sen u

7: ,V(i) = is : d(s,s¡)<ге!}

8: Cl(sj) - АЧ0 U

9: S = 5 \ AXs;)

10: end if

11: end while

12: for every s^ in do

13: 7s e Cl(s,j do s, send JOIN message to cluster head _12: end for__

Моделирование осуществляется на языке C#NET. На рис. 9 показаны экранные формы, получаемые в процессе моделирования.

Сенсорные узлы предполагаются однородными по своим свойствам. В процессе моделирования реализуются два сценария: первый посвящен анализу влияния эффекта изменения параметра г,, на число головных кластерных узлов и длительность полного покрытия при использовании алгоритма CHSC, а второй сценарий - сравнению предложенного алгоритма CHSC с известным базовым алгоритмом LEACH.

Рис. 9. Экранные формы

В обоих случаях в качестве плоскости а используется квадрат 200x200 м, число сенсоров в момент начала жизни сети составляет 400. Шлюз с сетью связи общего пользования расположен в центре сети.

Рис. 10. Среднее число головных узлов (кластеров) в зависимости от гс

На рис. 10 представлена зависимость среднего числа головных узлов в сети от параметра гс1. Как видим, при значении гс, в 20 м число головных узлов (кластеров) в сети очень велико, а именно шестьдесят, - но при этом обеспечивается и наилучшее покрытие во времени. На рис. 11 длительность полного покрытия при значении гс, в 20 м более чем в 2 раза больше, чем длительность полного покрытия при гс, в 50 м. Заметим, что при гс1 = 20 м средняя численность узлов в кластере около 7, включая головной.

о бооо

5 4000

20 30 40 SO SO

Радиус кластера

Рис. П. Длительность полного покрытия в зависимости от гс1

Для сравнения алгоритмов LEACH и предложенного алгоритма CHSC принято значение гс1 = 40м (среднее из рассмотренных выше).

На рис. 12 приведено сравнение LEACH и CHSC по длительности к-покрытия (к = 100, 90, 80) сети. Как видим, предложенный алгоритм значительно увеличивает длительность существенного покрытия сети.

Длительность покрытия больше и при к = ! 00%, а в случаях к = 90% и к = 80% длительность ¿-покрытия при использовании CHSC превосходит длительность ¿-покрытия при использовании LEACH в несколько раз.

„хЮ*

и о

в 1.5 л

п

ад

К 1

н

КС

fisfl gen-LEACH

MRS CHSC

такая число

Процент покрытия

Рис. 12. Сравнение ¿-покрытия при использовании LEACH и CHSC

Одновременно улучшается важная характеристика, как долговременно живущих сенсорных узлов.

На рис. 13 приведено сравнение числа живущих узлов при использовании LEACH и CHSC в зависимости от числа циклов моделирования.

Четвертая глава посвящена разработке алгоритма выбора головного узла в кластере для гетерогенных сенсорных Рис. 13. Гетерогенная беспроводная сетей. Пример гетерогенной сети приведен сенсорная сеть на рис. 13.

Приведем алгоритм для нахождения полного периметрического покрытия

(Full Perimeter Coverage Nodes - FPCN):_

1: S = {si ■■ E(s;) > 0}, £(Sj) residual energy of sensor node s,. 2: fc-. a set of sensors candidate to be cluster bead. у. fc = s

{Removing the sensors which belong to Case 1(b)} 4: for every s, in fc do 5: /VS(S[) = {sj-. 4rea(s,) n Area(sj) * 0) 6: for every s, in NS(s,) do 7: if (Area(s,) с Area(S/)) then

8: s, become not sensing node.

9: FC = fc\ s,

10: end if 11: end for 12: end for

{ Removing the sensors which not perimeter coverage } 13: for every s, in FC do _14: for every s, in JVS(s,) do_

15: Determine the angle of s^s is arch, denoted by [altL,ajj,] that is perimeter-covered by Sj.

16

17

18

19

20

21 22

23

24

Place the points ajM and ajj, on the line segment |0,2ir] end for

sort all these points in an ascending order into a list L.

Mark each point as a left or right boundary of a coverage range.

Traverse the line segment [0,2k] by visiting each element in the sorted list L

from the left to right and determine the perimeter-coverage of s,.

if line with cutting (i.e., L with empty element) then

FC = FC \Sj. end if end for

Алгоритм FPCN определяет набор узлов, который состоит из полностью периметрически покрытых сенсорных узлов. Алгоритм выбора кластерного узла для покрытия (Cluster head Selection for Coverage - CSC) использует этот набор для выбора головного узла.

После получения обновленной информации от всех близлежащих узлов, каждый сенсорный узел s, останавливается, если его сенсорное поле покрыто другим сенсорным узлом s,. Если не все сенсорное поле покрыто, то каждый сенсор определяет угол сегмента s( для каждого сенсора из списка [ам, ам] и место точек аи и ajJt на линейном сегменте [o,2it], как это показано на рис. 14, и сортируют все эти точки по порядку в лист L.

После этого каждая точка маркируется как левая или правая в радиусе покрытия, и получаем траверс линейного сегмента [о,2тг] из листа L слева направо.

В изложенном подходе полностью периметрически покрытые сенсорные узлы являются лучшими кандидатами на функции головного кластерного узла, поскольку такие узлы могут поддерживать наибольшее число членов кластера.

-0 Головной Viti

? Ч \ , ,.

/' Ч V 4.VHU Кластер*

• :'Ч

V

•Л s _ .

Р—<У

: Я" -Ж

/

\ С)

Оч

I

/

/

/

Рис. 14. Кластерный радиус гс1 как туннельный параметр

Далее предложим метод, названный CSC. Как уже отмечалось выше, метод и алгоритм CSC основаны на туннельном параметре га, который определятся как минимальное расстояние между любыми двумя головными узлами кластера в сети. Используя этот параметр, CSC позволяет достаточно

17

точно распределить кластерные узлы по сети. Параметр гс, может быть мягко настроен при изменении передающей мощности головных узлов кластера. В CSC сенсорные узлы взаимосвязаны непосредственно с выбранными юлииными кластерными узлами, в то время как маршрутизация данных от головного узла кластера к шлюзу может быть многошаговой (multi-hop), как

это показано на рис. 14._

Алгоритм CSC:_

1: S = {s: E(s) > 0), E(s) residual energy of sensor node s. 2: Sc„={}, a set of cluster head nodes. 3: CAf(s,)={}, a set of cluster members. 4: while FC * {} do

5: if (s, e FC and E(s¡) > Ech), E,h - threshold energy for node to be cluster head then

6: SCH ~ Sch u si 7: rci = 2xr¡ 8: CM(sl) = {s:d(s.sl)<rc¡}

9: s = s\N(s,) 10: end if 11: end while 12: for every s, in SCH do

13: s, sends Announce message to all s e CM(s,) 14: All s 6 CM(s,) sends JOIN message to s,

15: end for_

В начале функционирования CSC каждый сенсор широковещательно распространяет пакет информации о его остаточной энергии для всех близлежащих узлов. Для избежания коллизий этих пакетов, узлы используют информацию о пространстве перед передачей пакета (аналогично вектору резервирования в WiFi). После получения информации от всех близлежащих сенсорных узлов включается алгоритм FPCN. С учетом того что сенсорные узлы статичны, близлежащие узлы должны подтвердить свое местоположение только однажды в начале жизненного цикла сенсорной сети.

Каждый сенсор ожидает некоторое время (время активации), прежде чем он решит объявить себя новым головным кластерным узлом или не решит. Если в течение времени активации сенсорный узел не получает сообщений о том, что какой-либо узел уже объявил себя головным, то данный узел сам объявляет себя головным, рассылая соответствующие сообщения всем узлам в пределах тс1. Сообщение содержит информацию о местоположении нового головного сенсорного узла. После получения сообщения от нового головного узла кластера все сенсорные узлы в области действия гс, исключают себя из дальнейших претендентов на роль головного узла.

Каждый сенсор создает таблицу всех головных узлов кластера, от которых он получил сообщение. Эта информация используется далее сенсорным узлом для принятия решения о членстве в том или ином кластере. В случае, если два сенсорных узла с одинаковыми затратами на передачу информации, действующие в одной и той же области га определяют себя головными узлами, побеждает тот узел, у которого выше энергетические

возможности.

На рис. 15 приведено сравнение жизненного цикла CSC и базового LEACH, где под жизненным циклом понимается время до гибели первого узла. Как видим, CSC обеспечивает существенно лучшие характеристики, чем базовый LEACH.

Рис. 15. Жизненный цикл CSC и базового LEACH (до гибели первого узла)

На рис. 16 показано сетевое покрытие в течение времени для CSC и базового LEACH. Как видно из рис. 16, CSC обеспечивает существенно лучшие характеристики покрытия, чем LEACH.

Покрытие (%)

Рис. 16. Сравнение CSC и базового LEACH по i-покрытию

В пятой главе разработан алгоритм кластеризации на основе предикторов для мобильных беспроводных сенсорных сетей.

В последние годы появился новый вид сенсорных сетей - мобильные сенсорные сети MSN (Mobile Sensor Networks). Эти сети сохранили все особенности беспроводных сенсорных сетей WSN и к этим особенностям добавилась еще мобильность. Кластерная архитектура нашла применение и в WSN, поэтому поиск наилучших вариантов организации кластера и выбора головного узла для MSN является сегодня актуальной задачей. В главе

предложен алгоритм кластеризации для MSN на основе использования предикторов. Предложенный алгоритм представляется адекватным для выбора головного узла кластера и организации кластеров в мобильных беспроводных сенсорных сетях.

Основное различие между базовым алгоритмом LEACH-M и подходом к созданию нового алгоритма в диссертации состоит в том, что предлагаемый алгоритм обеспечивает существенное увеличение жизненного цикла сети и стабильность сформированного кластера за счет использования комбинированного критерия прогнозирования.

В главе предложен комбинированный критерий прогнозирования, включающий в себя критерии связности, покрытия, мобильности, остаточной энергии. Кроме того, используются три эвристических предиктора.

В этом разделе рассмотрим три эвристических предиктора, которые будут использованы при моделировании. Комбинированный критерий прогнозирования СС должен быть предсказан в текущее время tc в соответствии с историей этого критерия нее = [(cc1,t1).ccc2,t2),...,(cc„,t„)], где < с2 <...< t„. Для этого могут быть использованы:

• простой точечный предиктор SPP (Single Point Predictor). Этот предиктор всегда предсказывает следующее значение как предыдущую величину НСС:

РСС = SPP(tc) = СС„; (3)

• линейный экстраполяционный предиктор LEP (Linear Extrapolation Predictor). Для него используется следующая формула:

РСС = LEP(tc) = J^(CC„ - CCn-t) + CCn.t; (4)

• гибридный предиктор HP (Hybrid Predictor). Гибридный предиктор представляет собой смесь точечного и экстраполяционного предикторов:

(ССп, п is odd;

РСС = |гт^(ССп-ССп.1) + СС„.1, niseven (5)

Гибридный предиктор, как правило, использует линейное предсказание, но в отдельных случаях может учитывать скачкообразные изменения процесса.

Рассмотрим новый алгоритм кластеризации DCA (Distributed Clustering Algorithm), разработанный в рамках диссертации.

Прежде чем перейти к рассмотрению алгоритма, сделаем следующие предположения:

• все сенсоры гомогенны с одинаковыми характеристиками;

• топология сети изменяется, и сенсорные узлы могут перемещаться со скоростью от 0 до 2 м/с;

• сенсорные узлы осуществляют свою активность без централизованного управления.

Введем параметр, называемый кластер-хоп. Кластер-хоп определяется как максимальное число сенсорных узлов между головным узлом кластера и периферийными узлами, включая последние. Этот динамический параметр определяет процедуру формирования кластера и служит как входной параметр для процесса формирования кластера.

DCA содержит две фазы: информационное обновление и формирование кластера.

В фазе информационного обновления каждый сенсорный узел вычисляет свои предикторы комбинированного критерия РСС. Далее, базируясь на значении кластер-хопа , осуществляется процесс распространения РСС. Во время фазы формирования кластера сенсорные узлы уже имеют взвешенный взгляд на свою близость и информацию о РСС.

Программа моделирования была написана на языке C#.NET. Сенсорные узлы распределялись неравномерно случайным образом на плоскости. Предполагалось также, что сенсорные узлы имеют достаточно мощности, чтобы можно было покрыть расстояния до узла - получателя информации.

Для последующих исследований было выбрано 2 сценария. В первом сценарии исследуются вопросы эффективности DCA при использовании различных предикторов SPP, LEP и HP. Во втором сценарии предложенный алгоритм сравнивается с известным LEACH-M (Kim, 2005). Для оценки эффективности алгоритмов используется метрика жизненного цикла сети -интервал времени между началом функционирования и гибелью последнего из живущих сенсорных узлов.

Рис. 17. Эффективность критериев в DCA

В первом сценарии сенсорные узлы случайно распределены на плоскости размером . Число узлов в сети составляет 100. Целью моделирования

является проверка эффективности критерия связности (а=1, ß=0, у=0 и Ç=0), критерия покрытия (а=0, ß=l, у=0 и i;=0), энергетического критерия (а=0, ß=0, у=1 и £,=0) и критерия мобильности (а=0, ß=0, у=0 и Ç=l) в алгоритме DCA при использовании SPP, LEP и HP предикторов.

На рис.17 изображен жизненный цикл сенсорной сети для различных критериев в условиях использования различных предикторов. Как видим, критерий связности наилучшим образом подходит для обеспечения жизненного цикла сенсорной сети.

Во втором сценарии сенсорные узлы случайным образом расперделсны

на плоскости 200м х 200м и число сенсоров изменяется от 200 до 400 с шагом 50. Будем считать также, что а = /3 = у = < = о,25 в сравнении с ЬЕАСН-М в случае, когда шлюз расположен в центре сети.

Рис. 18. Жизненный цикл сети с использованием различных версий DSA в сравнении с LEACH-M в случае, когда шлюз расположен в центре сети

На рис. 18 шлюз расположен в центре сети. Простые расчеты могут показать, что в этом случае достигается минимальное значение Евклидова расстояния между узлами и шлюзом. На рис.18 сравнивается жизненный цикл DCA с различными предикторами (LEP, HP, SPP) с жизненным циклом сети при использовании классического алгоритма LEACH-M.

Как видим, алгоритм DCA увеличивает жизненный цикл сети при использовании всех предложенных предикторов по сравнению с алгоритмом LEACH-M. Объяснение этому состоит в том, что LEACH-M использует случайный выбор головного узла (и как следствие - размера кластера), что может приводить к более быстрой гибели отдельных сенсорных узлов. В алгоритме же DCA головной узел выбирается с учетом множества критериев, что и обеспечивает хорошее распределение головных функций среди сенсорных узлов.

И в случае, когда шлюз расположен вне сети, алгоритм DSA обеспечивает более длительный жизненный цикл сети, чем алгоритм LEACH-M. Анализ зависимостей на рис.18 и 19 показывает также, что простой предиктор SPP обеспечивает наибольший по длительности жизненный цикл сенсорной сети во всех рассмотренных случаях.

300

Размер сети

400

Рис. 19. Жизненный цикл сети для различных версий DSA в сравнении с LEACH в случае, когда шлюз расположен вне сети

ЗАКЛЮЧЕНИЕ

Исследования, проведенные в диссертационной работе, позволили получить следующие основные результаты:

1. Анализ развития беспроводных сенсорных сетей, интенсивный рост их внедрения показывают, что одной из наиважнейших становится задача обеспечения качества обслуживания при функционировании WSN, что требует разработки новых алгоритмов выбора головного узла в кластере.

2. Для выбора головного узла в кластере возможно и целесообразно использовать методы вычислительной геометрии: диаграммы Вороного и триангуляцию Делоне.

3. На основе диаграммы Вороного и триангуляции Делоне разработан новый алгоритм централизованного выбора головного узла кластера сенсорной сети CHS, в котором для процедуры выбора базовая станция в каждом интервале случайным образом генерирует фрагмент решетки, содержащей смежные повторяющиеся релеевские треугольники.

4. Сравнение предложенного в диссертации алгоритма CHS с базовым алгоритмом LEACH па основе моделирования в системе С#. NET показало, что новый алгоритм обладает лучшими характеристиками по энергетической эффективности.

5. В системах мониторинга для обеспечения качества обслуживания (QoS) необходимо обеспечить покрытие сенсорной сетью заданной области пространства в течение достаточно длительного времени.

6. Исследованы вопросы покрытия по периметру, и на основе этого исследования предложен новый алгоритм выбора головного узла в однородной кластерной сети. По результатам моделирования предложенного алгоритма CHSC на языке C#.NET и сравнения его с базовым алгоритмом LEACH дока-

зано, что предложенный алгоритм обеспечивает не только лучшее ¿-покрытие, но и большее число живущих узлов во времени.

7. Предложен метод выбора головного сенсорного узла, основанный на туннельном параметре гс|, который определяется как минимальное расстояние между любыми двумя головными узлами кластера в сети. На основе использования FPCN и параметра гс1 разработан новый алгоритм выбора головного узла в кластере CSC.

8. Разработанный алгоритм выбора головного узла кластера CSC обеспечивает более длинный жизненный цикл и существенно лучшее ¿-покрытие во всем диапазоне значений к, чем базовый алгоритм LEACH.

9. Для выбора головного узла кластера в мобильных беспроводных сенсорных сетях предложено использовать методы прогнозирования. При этом в качестве критерия прогнозирования предложен комбинированный критерий, включающий в качестве параметров связность, покрытие, мобильность и остаточную энергию.

10. В качестве предикторов для комбинированного критерия прогнозирования предложено использовать точечный предиктор и гибридный предиктор, представляющий собой комбинацию двух предшествующих. Для реализации комбинированного критерия прогнозирования с использованием упомянутых выше предикторов в диссертации разработан распределенный алгоритм кластеризации DCA.

11. Разработана модель сенсорной сети и программа моделирования на языке C#.NET. На основе результатов моделирования доказано, что наилучшим предиктором для алгоритма DCA является простой точечный предиктор и в то же время при использовании любого из предложенных предикторов алгоритм DCA обеспечивает существенно более длинный жизненный цикл беспроводной сенсорной сети, чем алгоритм LEACH-M, кшс для централизованного расположения шлюза, так и для случая расположения шлюза вне сети.

ПУБЛИКАЦИИ

1. Салим А., Кучерявый А. Е. Выбор головного узла кластера в однородной беспроводной сенсорной сети. Электросвязь. 2009. № 8.

2. Салим А., Кучерявый А. Е. Выбор головных узлов в однородной беспроводной сенсорной сети для обеспечения полного покрытия // 64-я Научно-техническая конференция, посвященная Дню радио. Апрель, 2009. СПб., 2009.

3. Салим А., Кучерявый А. Е. Диаграммы Вороного для беспроводных сенсорных сетей // 64-я Научно-техническая конференция, посвященная Дню радио. Апрель, 2009. СПб., 2009.

4. Salim A., Koucheryavy A. Cluster head selection for homogeneous Wireless Sensor Networks // Advanced Communication Technology, 2009. ICACT

2009. 11th International Conference IEEE, Volume: 03, pages: 2141-2146, Phoenix Park, Korea, ISSN: 1738-9445, ISBN: 978-89-5519-138-7, INSPEC Accession Number: 10601033 Current Version Published: 2009-04-03.

5. Salim A., Koucheryavy A. Cluster-based perimeter-coverage Technique for Heterogeneous Wireless Sensor Networks // ICUMT 2009 International Conference IEEE on Ultra Modem Telecommunications, Saint-Petersburg, (Russian), 2009.

6. Salim A., Koucheryavy A. Prediction-based Clustering Algorithm for Mobile Wireless Sensor Networks, in: Advanced Communication Technology,

2010. ICACT 2010.12th International Conference IEEE, Phoenix Park (Korea), 2010.

Подписано к печати 09.09.2010 Тираж 80 экз. Объем 1,5 печ.л. Заказ № 26

Тип. СПбГУТ, 191186, СПб., наб.реки Мойки,61

ВВЕДЕНИЕ

Глава 1. Анализ существующих работ в предметной области диссертации

1.1. Алгоритмы маршрутизации в беспроводных сенсорных сетях

1.1.1 Классификация алгоритмов маршрутизации в WSN.

1.2. Существующие работы в области иерархических алгоритмов.

1.2.1 Алгоритм случайного выбора головного узла

1.2.2. Алгоритм с предопределённым выбором головного узла HEED. •••

1.2.3. Алгоритм случайного выбора головного узла ERA.

1.2.4. Алгоритмы PEGASIS и иерархический PEGASIS.

1.2.5. Алгоритм RRCH.

Глава 2. Централизованный алгоритм выбора головного узла для гомогенных

2.1. Диаграммы Вороного

2.1.1. Выпуклая оболочка

2.1.2. Диаграммы Вороного

2.2. Диаграммы Вороного для WSN

2.3. Выбор головного узла в кластере

2.3.1. Алгоритм выбора головного узла

2.4. Результаты моделирования

Глава 3. Выбор головного узла кластера в однородной беспроводной сенсорной сети

3.1. Покрытое

3.2. Покрытие по периметру.

3.3. Алгоритм выбора головного узла в кластерной сенсорной сети.

3.4. Результаты моделирования.

Глава 4. Алгоритм выбора головного узла в кластере для гетерогенных беспроводных сенсорных сетей

4.1. Предположения и периметрическое покрытие

4.1.1. Предположения

4.1.2. Периметрическое покрытие

4.2. Предлагаемый алгоритм

4.2.1. Алгоритм для нахождения полного периметрического покрытия.

4.2.2. Алгоритм выбора головного узла для обеспечения покрытия.

4.3. Результаты моделирования

4.3.1. Первый сценарий.

4.3.2. Второй сценарий.

Глава 5. Алгоритм кластеризации на основе предикторов для мобильных беспроводных сенсорных сетей

5.1. Мобильные сенсорные сети.

5.2.Комбинированный критерий прогнозирования

5.2.1. Критерий связности

5.2.2. Критерий покрытия.

5.2.3. Критерий мобильности.

5.2.4. Критерий остаточной энергии.

5.3. Предикторы.

5.4. Распределённый алгоритм кластеризации

5.4.1. Фаза 1: информационное обновление.

5.4.2. Фаза 2: Формирование кластера.

5.5. Результаты моделирования.

5.5.1. Первый сценарий.

5.5.2. Второй сценарий.

Актуальность исследования и состояние предмета исследования

Беспроводные сенсорные сети WSN (Wireless Sensor Network) представляют собой самоорганизующиеся сети, состояние из множества беспроводных сенсорных узлов, распределённых в пространстве и предназначенных для мониторинга характеристик окружающей среды или объектов, расположенных в ней. Пространство, которое покрывается сенсорной сетью, называют достаточно часто сенсорным полем. Собственно беспроводные сенсорные узлы представляют собой миниатюрные устройства с ограниченными ресурсами: зарядом батареи, объемом памяти, вычислительными возможностями и т.д. Однако, объединение большого числа этих элементов в сеть обеспечивает возможность получения реальной картины происходящего в рамках этого сенсорного поля.

Беспроводные сенсорные узлы могут собирать информацию о наблюдаемых явлениях и передавать её далее для обработки и анализа. Примерами собираемой информации могут быть данные о температуре, влажности, условиях освещения, сейсмической активности и т.д. Такие данные могут быть использованы как для выявления каких-либо событий, так и для управления ими. В качестве примера, можно привести использование сенсоров для автоматического пожаротушения в случае получения тревожных сообщений о возгорании (Ren, 2004).

В целом, беспроводные сенсорные сети характеризуют новую эру развития общества и-сетей, так называемое «-общество и и-сети (Kim, 2005, Кучерявый 2005, 2006). Не случайно, в последнее время в литературе всё чаще употребляется название USN (Ubiquitous Sensor Network).

В связи с изложенным, исследование, направленное на разработку новых алгоритмов для повышения эффективности функционирования беспроводной сенсорной сети, представляется актуальным.

Выбор конкретных решений для сенсорных узлов при распределении беспроводной сенсорной сети в первую очередь зависит от функциональных возможностей, размера, затрат, энергетических характеристик и в настоящее время при начале достаточно широкого внедрения сенсорных сетей - от обеспечения требуемого качества обслуживания.

Рис. 1 - Сенсорные узлы

Примеры конструкций современных сенсорных узлов приведены на рис. 1, а на рис. 2 рассматривается типовая архитектура сенсорного узла. Типовая архитектура сенсорного узла включает в себя следующие элементы: один или несколько сенсоров, собирающих информацию об окружающей среде и/или её составляющих, центральный процессор и память, радиопередатчик, устройство электропитания. К

Рис. 2 — Типовая архитектура сенсорного узла

Создание сенсорной сети из беспроводных сенсорных узлов, будь-то разнообразные задачи мониторинга окружающей среды, периметрической защиты, контроля перевозок и т.д., требует как выбора архитектуры сети, так и протоколов взаимодействия элементов этой сети между собой и с внешними (например, сетями следующего поколения , NGN - Next Generation Network) сетями.

В настоящее время можно выделить несколько характеристик архитектуры беспроводных сенсорных сетей, что будет использовано в диссертации далее для разработки алгоритмов:

• Гомогенные или гетерогенные Беспроводная сенсорная сеть может быть построена на однотипных или разнотипных сенсорных узлах. Гомогенной сетью, соответственно, является сеть, в которой все сенсорные узлы имеют подобные измерительные и вычислительные возможности. Поскольку сенсорная сеть может содержать тысячи сенсорных узлов, построение сенсорной сети как гомогенной выглядит экономически обоснованным решением, естественно тогда, когда это возможно. В гетерогенной сети различные сенсорные узлы могут обладать различной энергоёмкостью, измеряемым набором параметров, вычислительными возможностями. Примером гетерогенной сенсорной сети может являться сеть мониторинга, в которой ряд сенсоров реализует функции видеонаблюдения, а остальные - аудиоконтроль.

• Случайное или детерминированное размещение сенсорных узлов.

Сенсорные узлы могут быть случайным образом разбросаны по некоторой территории (как это показано на рис.3) или предварительно размещены в соответствии с планом построения сети. Естественно, что алгоритмы распределения данных между сенсорными узлами в первом и втором случае могут быть существенно различны.

Рис.3 - Пример сенсорной сети, в которой сенсорные узлы размещаются случайным образом

• Статичность или мобильность. Беспроводные сенсоры могут быть статичными или мобильными. Сенсорная сеть может быть построена как на основе первых, так и вторых, а также любой их комбинации.

Необходимость совместного функционирования автономных узлов, зачастую недоступных для замены, адаптация к динамически изменяемым условиям внешней среды и задачам являются фундаментальными направлениями для исследовательских работ в области беспроводных сенсорных сетей так же, как и решение проблем динамически изменяющейся топологии или требований по низкому энергопотреблению. Конфигурация сенсорной сети должна иметь возможность видоизменяться (самоорганизующаяся сеть) в зависимости от текущего положения в пространстве, возможностей электропотребления, деталей решаемых задач. Поскольку сенсорные узлы взаимодействуют с окружающей средой, они должны иметь возможность динамически приспосабливаться к решению конкретной задачи. Мобильность узлов, их отказы, критичные изменения во внешней среде требуют высокой степени динамичности от сенсорной сети в целом. Поэтому, топология конкретной сенсорной сети или её части может изменяться многократно в течение срока её функционирования. Фрагменты беспроводной сенсорной сети в связи с этим нуждаются в современных алгоритмах, которые должны быть робастными и адекватными к изменяющимся условиям.

Сенсорные узлы конструируются так, чтобы потреблять как можно меньше энергии, поскольку они могут функционировать в недружественной внешней среде и замена источника питания может быть невозможна как таковая. Поэтому, сенсорный узел может выйти из строя как по причине критичной ситуации во внешней среде, так и вследствие потери возможности энергоснабжения. Однако, как уже отмечалось выше, сенсорная сеть содержит тысячи сенсорных узлов и наиболее важным свойством сенсорной сети в целом должно быть выполнение сетью своих функций даже при выходе из строя какого-то максимально возможного числа сенсорных узлов. В связи с изложенным, необходимо создавать такие алгоритмы управления сенсорными узлами, чтобы минимизировать энергопотребление. Число пакетов информации, передаваемых, принимаемых, обрабатываемых каждым сенсорным узлом должно быть таким, чтобы расход энергии был минимизирован.

Другой проблемой при построении беспроводных сенсорных сетей является то, что расстояние, на которое сенсорный узел передаёт информацию, может быть существенно меньше, чем в традиционных радиосистемах. Мощность передатчика должна быть мала (это способствует и низкому энергопотреблению) и архитектура беспроводной сенсорной сети должна тогда представлять собой сеть с распределёнными интеллектуальными ресурсами. Такие сети, как уже выше отмечалось, относятся к самоорганизующимся. Распространенным примером самоорганизующихся сетей служат сети MANET (Mobile Ad Hoc Network). Сколь близки WSN к таким сетям? Для ответа на этот вопрос рассмотрим основные соответствия и различия для обоих классов сетей (Li, 2007; Fro-digh, 2000; Akyildiz, 2002; Frenk, 2005).

Сети WSN и MANET подобны в следующем:

• обе являются распределёнными неинфраструктурными беспроводными сетями,

• маршрутизация между узлами может быть многоранговой (multi-hop),

• узлы обеих сетей как правило питаются от батарей и, следовательно, необходимы усиленные меры по энергосбережению,

• обе сети используют радиоканалы в нелицензируемом спектре, что может приводить к интерференции с техническими средствами других радиотехнологий,

• самоуправление необходимо вследствие распределённой природы обоих классов сетей.

Сети WSN и MANET отличаются следующим:

• узлы MANET всегда существуют во взаимодействии с человеком (например, Лаптоп, PDA, мобильный терминал и т.д.), в то время как сенсорные узлы ориентированы на взаимодействие не с человеком, а с окружающей средой,

• сенсорные узлы как правило интегрированы в окружающую среду для сбора информации, в то время как узлы MANET - как мобильные станции,

• число узлов в сенсорных сетях так же, как и их плотность во много раз больше, чем в MANET,

• вследствие особенностей применения беспроводных сенсорных узлов, например, для контроля за вулканической деятельностью или за пожарами, частота выхода из строя узлов WSN (в зависимости от приложения) может быть существенно выше, чем в MANET, что I приводит к необходимости наличия гибких механизмов реконфигурации сети,

• в отдельных случаях сенсорные узлы должны быть мобильными, но в большинстве приложений они статичны, в отличие от MANET,

• для ряда приложений вместо идентификатора индивидуального сенсорного узла (например, адреса) реальное местоположение является более важным атрибутом, что подчеркивает целевую направленность сенсорной сети на решение задач определенного приложения,

• WSN зачастую рассчитаны на вполне определённого пользователя сети, возможно, единственного (например, оператор сети по сбору информации о климатических условиях в теплице), в то время как MANET является многопользовательской сетью,

• узлы MANET как правило находятся непосредственно у человека или близко к нему и, естественно, достаточно просто перевести их в режим сохранения энергии, в то время как для узлов WSN это действия должно осуществляться без участия человека. Сравнение соответствий и различий MANET и WSN показывает необходимость разработки для WSN специальных протоколов и алгоритмов для обеспечения функционирования беспроводной сенсорной сети.

Как уже отмечалось выше, беспроводные сенсорные сети могут использоваться повсеместно. Рассмотрим далее для примера ряд приложений беспроводных сенсорных сетей:

• Наблюдения за внешней средой. Сенсорные сети могут быть использованы для мониторинга изменения климата (Кучерявый, Салим, 2009), пожароопасности в лесных массивах, контроля температуры, влажности, освещённости в сельском хозяйстве и т.д.

• Военный мониторинг. На рис. 4. приведён пример использования сенсорных сетей в военной области. Сенсорные Узлы Валовая Станция ft

Командный Узел л-''

Командный Узел

-I Г

• О- /

4' , t о z1»

Командный Узел ws* , » \ О

О / *

I i О 9 О Ф

Ч О X

Командный Узел

Рис. 4. Пример исследования сенсорной сети в военной отрасли

• Мониторинг зданий. Достаточно важные задачи по мониторингу жилого фонда, систем водоснабжения и т.д. составляют значительную часть приложений сенсорных сетей.

• Контроль здоровья. Сенсорные узлы могут размещаться не только в зданиях, в лесах и т.д., но и на и в теле человека и иных биомасс. Одно из новых важнейших приложений сенсорных сетей получило название MBAN (Medicine Body Area Network) и изучается в рабочей группе IEEE 802.15.6.

Список приложений можно было бы продолжить, но уже рассмотренных вполне достаточно для того, чтобы сформировать архитектуру беспроводной сенсорной сети, изображенную на рис. 5. Для связи с сетью связи общего пользования (NGN, Internet) используется шлюз, поскольку в сенсорных сетях для взаимодействия сенсорных узлов применяется специальный энергосберегающий протокол Zig Bee, не относящейся к категории TCP/IP протоколов.

Рис. 5 - Архитектура сенсорной сети 9

Кластерная организация считается эффективной и масштабируемой для решения подобных задач, но лишь при условии рационального выбора головного узла в кластерной сети в конкретный момент времени. Действительно, являющийся головным в момент времени ti сенсорный узел не обязательно должен быть им же в момент времени t2, ибо существующий головной узел уже может затратить достаточно большое количество энергии на передачу сообщений от всех сенсорных узлов кластера к моменту времени t2. Поэтому, в момент времени t2 головным узлом в кластере может быть назначен и иной сенсорный узел, сохранивший к этому времени наибольший энергетический запас.

Одним из самых известных механизмов, обеспечивающих функционирование сенсорных сетей и выбор головных узлов является алгоритм LEACH (Low Energy Adaptive Cluster Hierarchy). Алгоритм LEACH предусматривает вероятностный выбор сенсорного узла на роль головного в начале функционирования сенсорной сети, а впоследствии ротацию на основе энергетических характеристик сенсорных узлов. Подобное решение, естественно, продлевает длительность функционирования сенсорных узлов и сети в целом, но как будет показано далее по результатам моделирования не решает задачи обеспечения лучшего покрытия в течение достаточно длительного времени. И, это в общем-то естественно, поскольку при создании LEACH такая задача и не ставилась.

Существует достаточно много алгоритмов, которые в той или иной степени пытаются улучшить LEACH. Это и алгоритмы, основанные на максимуме остаточной энергии, местоположении узла-кандидата в головной кластерный узел по отношению к другим узлам, информации о топологии сети в текущей момент времени. Алгоритм HEED (Hybrid Energy - Efficient Distribution) использует гибридный критерий для выбора головного узла на основе анализа остаточной энергии и расположения близлежащих узлов. Все эти алгоритмы направлены как и LEACH в первую очередь на максимизацию длительности функционирования сенсорных узлов и сети в целом.

Однако, с развитием сенсорных сетей появились и другие задачи, требующие пристального внимания. Например, задача о качестве обслуживания, являющимся важнейшей метрикой для любой сети, в том числе и сенсорной. Действительно, очень важна проблема увеличения срока жизни сенсорной сети. Однако, если эта сеть не будет выполнять свои функции в требуемом объеме, то и сама задача увеличения срока жизни сенсорной сети, не удовлетворяющей требованиям по качеству обслуживания, схоластична.

В системах мониторинга одним из важнейших требований является его непрерывность, т.е. обеспечение мониторинга параметров на всем пространстве или процессе. Исходя из сказанного, в настоящей работе мы поставили перед собой цель разработать алгоритм выбора головного узла кластера, который обеспечивал бы лучшее покрытие заданной для мониторинга области двумерного пространства (плоскости) в течение достаточно длительного периода времени. Этот подход означает в целом оптимизацию как срока жизни сенсорной сети, так и оптимизацию выполнения сенсорной сетью своих функциональных задач с заданным качеством обслуживания в течение достаточно длительного периода времени.

С учётом изложенного разработка новых алгоритмов выбора головных узлов; кластера в беспроводных сенсорных сетях представляется актуальной, впрочем как и сам предмет исследования - беспроводные сенсорные сети.

Клш

I \ 1 л ч

Г~Л ^ V Кластер 3

- / ° о\

Д \ I ГЛ ^ ! I

0^ - I ж

Кластер 2

3 Сенсор

Рис. 6. Кластерная архитектура Цель и задачи исследования

С учетом изложенного цель диссертации состоит в разработке новых алгоритмов выбора головного узла кластера в беспроводных сенсорных сетях.

Для достижения поставленной цели в диссертации последовательно решены следующие задачи:

• анализ существующих алгоритмов выбора головного узла в кластере сенсорной сети,

• разработка нового алгоритма централизованного выбора головного кластерного узла для гомогенных сенсорных сетей на основе диаграмм Вороного,

• разработка нового алгоритма выбора головного кластерного узла для обеспечения наибольшего покрытия в гомогенных сенсорных сетях,

• разработка нового алгоритма выбора головного кластерного узла для обеспечения наибольшего покрытия в гетерогенных сенсорных сетях,

• разработка нового алгоритма выбора головного кластерного узла для обеспечения наибольшего покрытия в мобильных сенсорных сетях с использованием различных предикторов.

Методы исследования

Для решения поставленных задач используются методы вычислительной геометрии, теории оптимизации, прогнозирования, имитационного моделирования.

Научная новизна

В результате исследований получены следующие новые научные результаты:

• разработан новый алгоритм централизованного выбора головного кластерного узла для гомогенных сенсорных сетей CHS и доказано, что предложенный алгоритм обладает улучшенными характеристиками по энергетической эффективности по сравнению с базовым алгоритмом LEACH,

• разработан новый алгоритм выбора головного кластерного узла для обеспечения наибольшего покрытия в гомогенных сенсорных сетях CHSC и доказано, что предложенный алгоритм обеспечивает лучшие показатели качества обслуживания (Аг-покрытие) во всем диапазоне значений к, чем базовый алгоритм LEACH. При этом, обеспечивается также большее значение числа живущих сенсорных узлов во времени,

• разработан новый алгоритм выбора головного кластерного узла для обеспечения наибольшего покрытия в гетерогенных сенсорных сетях

CSC и доказано, что предложенный алгоритм обеспечивает более длительный цикл жизни сенсорной сети и лучшее ^-покрытие во всем диапазоне значений к, чем базовый алгоритм LEACH,

• разработан комбинированный критерий прогнозирования поведения мобильной беспроводной сенсорной сети, включающий в себя критерии связности, покрытия, мобильности и остаточной энергии,

• разработан новый алгоритм выбора головного кластерного узла для мобильных сенсорных сетей DCA, основанный на комбинированном критерии прогнозирования,

• доказано, что критерий связности является наиболее сильным из всех рассмотренных критериев в плане обеспечения жизненного цикла беспроводной сенсорной сети,

• доказано, что алгоритм DCA обеспечивает более длинный жизненный цикл существования беспроводной сенсорной сети, чем базовый алгоритм LEACH-M как для централизованного расположения шлюза, так и для расположения шлюза вне сети.

Личный вклад

Все основные результаты диссертации получены автором лично.

Практическая ценность работы

Результаты диссертационной работы используются в СПбГУТ им.проф. М.А. Бонч-Бруевича при чтении лекций по курсу «Современные проблемы науки в области телекоммуникаций».

Апробация работы

Основные результаты диссертации докладывались и обсуждались на 64-ой и 65-ой научно-технических конференциях СПбНТОРЭС им. A.C. Попова. (2009, 2010 С.Петербург), 11-ой Международной конференции IEEE по новым технологиям телекоммуникаций «Ubiquitous ICT Convergence Makes Life Better ICACT'2009, Korea, Phoenix Park, February 2009), Международной конференции IEEE по новейшим достижениям в телекоммуникациях ICUMT 2009 (С.Петербург, Октябрь 2009), 12-ой Международной конференции IEEE по новым технологиям телекоммуникаций «Ubiquitous ICT Convergence Makes Life Better ICACT'2010, Korea, Phoenix Park, February 2010), а также на заседании кафедры «Сети связи».

Публикации

По материалам диссертации опубликовано 6 работ.

Объем и структура

Диссертационная работа состоит из введения, 5 глав, заключения и списка литературы из 57 наименований.

Выводы

1. Для выбора головного узла кластера в мобильных беспроводных сенсорных сетях предложено использовать методы прогнозирования. При этом, в качестве критерия прогнозирования предложен комбинированный критерий, включающий в качестве параметров связность, покрытия, мобильность и остаточную энергию.

2. В качестве придикторов для комбинированного критерия прогнозирования предложено использовать точечный предиктор и гибридный предиктор, представляющий собой комбинацию двух предшествующих.

3. Для реализации комбинированного критерия прогнозирования с использованием упомянутых выше предикторов в диссертации разработан распределённый алгоритм кластеризации DCA.

4. Разработана модель сенсорной сети и программа моделирования на языке C#.NET. На основе результатов моделирования доказано, что наилучшим предиктором для алгоритма DCA является простой точечный предиктор и в тоже время при использовании любого из предложенных предикторов алгоритм DCA обеспечивает существенно более длинный жизненный цикл беспроводной сенсорной сети, чем алгоритм LEACH-M, как для централизованного расположения шлюза, так для случая расположения шлюза вне сети.

Заключение

Исследования, проведённые в диссертационной работе, позволили получить следующие основные результаты:

1. Анализ развития беспроводных сенсорных сетей, интенсивный рост их внедрения показывают, что одной из наиважнейших становится задача обеспечения качества обслуживания при функционировании WSN, что требует разработки новых алгоритмов выбора головного узла в кластере.

2. Для выбора головного узла в кластере возможно и целесообразно использовать методы вычислительной геометрии: диаграммы Вороного и триангуляцию Делоне.

3. На основе диаграммы Вороного и триангуляции Делоне разработан новый алгоритм централизованного выбора головного узла кластера сенсорной сети CHS, в котором для процедуры выбора базовая станция в каждом интервале случайным образом генерирует фрагмент решётки, содержащей смежные повторяющиеся релеевские треугольники.

4. Сравнение предложенного в диссертации алгоритма CHS с базовым алгоритмом LEACH на основе моделирования в системе С#. NET показало, что новый алгоритм обладает лучшими характеристиками по энергетической эффективности.

5. В системах мониторинга для обеспечения качества обслуживания (QoS) необходимо обеспечить покрытие сенсорной сетью заданной области пространства в течение достаточно длительного времени.

6. Исследованы вопросы покрытия по периметру и на основе этого исследования предложен новый алгоритм выбора головного узла в однородной кластерной сети. По результатам моделирования предложенного алгоритма CHSC на языке C#.NET и сравнения его с базовым алгоритмом LEACH доказано, что предложенный алгоритм обеспечивает не только лучшее k-покрытие, но и большее число живущих узлов во времени.

7. Предложен метод выбора головного сенсорного узла, основанный на туннельном параметре rci, который определяется как минимальное расстояние между любыми двумя головными узлами кластера в сети. На основе использования FPCN и параметра rci разработан новый алгоритм выбора головного узла в кластере CSC.

8. Разработанный алгоритм выбора головного узла кластера CSC обеспечивает более длинный жизненный цикл и существенно лучшее k-покрытие во всём диапазоне значений к, чем базовый алгоритм LEACH.

9. Для выбора головного узла кластера в мобильных беспроводных сенсорных сетях предложено использовать методы прогнозирования. При этом, в качестве критерия прогнозирования предложен комбинированный критерий, включающий в качестве параметров связность, покрытие, мобильность и остаточную энергию.

10.В качестве предикторов для комбинированного критерия прогнозирования предложено использовать точечный предиктор и гибридный предиктор, представляющий собой комбинацию, двух предшествующих. Для реализации комбинированного критерия прогнозирования с использованием упомянутых выше предикторов в диссертации разработан распределённый алгоритм кластеризации DCA.

11 .Разработана модель сенсорной сети и программа моделирования на языке C#.NET. На основе результатов моделирования доказано, что наилучшим предиктором для алгоритма DCA является простой точечный предиктор и в тоже время при использовании любого из предложенных предикторов алгоритм DCA обеспечивает существенно более длинный жизненный цикл беспроводной сенсорной сети, чем алгоритм LEACH-M, как для централизованного расположения шлюза, так для случая расположения шлюза вне сети.

По результатам исследования опубликовано 8 работ. Результаты исследования используются при чтении лекций по курсу «Современные проблемы науки в области телекоммуникаций» в СПбГУТ им. проф. М.А. Бонч-Бруевича.