авторефераты диссертаций БЕСПЛАТНАЯ РОССИЙСКАЯ БИБЛИОТЕКА - WWW.DISLIB.RU

АВТОРЕФЕРАТЫ, ДИССЕРТАЦИИ, МОНОГРАФИИ, НАУЧНЫЕ СТАТЬИ, КНИГИ

 
<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ

Pages:   || 2 | 3 | 4 |

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

-- [ Страница 1 ] --

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

Ахмед

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

РАЗРАБОТКА АЛГОРИТМОВ ВЫБОРА ГОЛОВНОГО УЗЛА

В КЛАСТЕРНЫХ БЕСПРОВОДНЫХ СЕНСОРНЫХ СЕТЯХ

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

Автореферат

диссертации на соискание ученой степени

кандидата технических наук

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

2010

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

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

профессор А.Е. Кучерявый

Официальные оппоненты: доктор технических наук,

профессор М.А. Сиверс,

кандидат технических наук,

доцент Ю.В. Семёнов

Ведущая организация: ОАО «Гипросвязь-СПб»

Защита состоится «______» ___________ 2010 г. в _______часов на заседании диссертационного совета Д.219.004.02 при Санкт-Петербургском государственном университете телекоммуникаций им. проф. М.А. Бонч-Бруевича по адресу: 191186, Санкт-Петербург, наб.р.Мойки, 61, ауд. 205.

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

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

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

Ученый секретарь

диссертационного Совета В.Х. Харитонов

к.т.н., доц

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

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

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





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

 Архитектура беспроводной сенсорной-0

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

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

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

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

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

 Кластерная архитектура WSN В-1

Рис. 2. Кластерная архитектура WSN

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

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

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

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

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

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

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

  • разработан новый алгоритм централизованного выбора головного кластерного узла для гомогенных сенсорных сетей CHS и доказано, что предложенный алгоритм обладает улучшенными характеристиками по энергетической эффективности по сравнению с базовым алгоритмом LEACH;
  • разработан новый алгоритм выбора головного кластерного узла для обеспечения наибольшего покрытия в гомогенных сенcорных сетях CHSC и доказано, что предложенный алгоритм обеспечивает лучшие показатели качества обслуживания (k-покрытие) во всем диапазоне значений k, чем базовый алгоритм LEACH.
    При этом обеспечивается также большее значение числа живущих сенсорных узлов во времени;
  • разработан новый алгоритм выбора головного кластерного узла для обеспечения наибольшего покрытия в гетерогенных сенсорных сетях CAC и доказано, что предложенный алгоритм обеспечивает более длительный цикл жизни сенсорной сети и лучшее k-покрытие во всем диапазоне значений k, чем базовый алгоритм LEACH;
  • разработан комбинированный критерий прогнозирования поведения мобильной беспроводной сенсорной сети, включающий в себя критерии связности, покрытия, мобильности и остаточной энергии;
  • разработан новый алгоритм выбора головного кластерного узла для мобильных сенсорных сетей DSA, основанный на комбинированном критерии прогнозирования;
  • доказано, что критерий связности является наиболее сильным из всех рассмотренных критериев в плане обеспечения жизненного цикла беспроводной сенсорной сети;
  • доказано, что алгоритм DSA обеспечивает более длинный жизненный цикл существования беспроводной сенсорной сети, чем базовый алгоритм LEACH-M, как для централизованного расположения шлюза, так и для его расположения вне сети.

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

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

Апробация работы. Основные результаты диссертации докладывались и обсуждались на 64-й Научно-технической конференции СПбНТОРЭС им. А.С. Попова. (С.-Петербург, 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 беспроводных сенсорных сетях, обеспечивающие лучшие показатели качества обслуживания (k-покрытие) во всем диапазоне значений k и большее значение числа живущих узлов во времени по сравнению с базовым алгоритмом LEACH;
  • комбинированный критерий прогнозирования поведения мобильной сенсорной сети, включающий в себя критерии связности, покрытия, мобильности и остаточной энергии;
  • алгоритм выбора головного кластерного узла в мобильных сенсорных сетях DCA, обеспечивающий более длительный жизненный цикл существования беспроводной сенсорной сети, чем базовый алгоритм LEACH-M, как для централизованного расположения шлюза, так и для его расположения вне сети.

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

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

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

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

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

(1)

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

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

После того как кластер сформирован, головной узел широкополосным способом рассылает расписание передачи и запрашивает своих членов кластера о передаче данных на основе известного TDMA подхода. В последующих фазах головной узел является ответственным за агрегирование данных и передачу их на шлюз и в сеть связи общего пользования. Весь сбор данных локализуется в кластере. После определенного времени нахождения в стабильной фазе, сеть снова переходит в стадию формирования. При этом следует отметить, что стадия формирования существенно короче, чем стабильная. В связи с этим 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 и включает в анализ вопроса выбора головного узла в кластере затраты на осуществление взаимодействия. Затраты на осуществление взаимодействия включают в себя остаточную энергию головного узла кластера (ECH-rem), затраты энергии на взаимодействие головного узла с базовой станцией (EtoBS), затраты энергии на взаимодействие членов кластера с головным узлом (EtoCH). В этом состоит принципиальная разница с алгоритмом HEED: алгоритм ERA использует ту же схему выбора головного узла, что и LEACH (случайный выбор), но обеспечивает лучший выбор головного узла за счет использования дополнительных параметров, определенных выше. Уравнения (2) помогают определять затраты кластера при выборе того или иного узла в качестве головного и найти головной узел кластера с максимальной остаточной энергоемкостью. В (2) множество Sc является множеством для головных узлов, множество SN является множеством для членов кластера.

(2)


Pages:   || 2 | 3 | 4 |
 

Похожие работы:







 
© 2013 www.dislib.ru - «Авторефераты диссертаций - бесплатно»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.