Современные технологии производства полупроводниковых приборов, а также прогресс беспроводной связи сделали возможным создание и широкое использование сетей со сложной структурой, в том числе Ad-Hoc сетей и беспроводных сенсорных сетей [1][2]. Использование таких сетей в различных сферах деятельности человека во многих случаях является экономически более выгодным, чем использование традиционных систем. В настоящее время для таких сетей разработано большое количество алгоритмов и протоколов [3], причем некоторые из них являются кандидатами в стандартные. Тем не менее, внедрение сенсорных и Ad-Hoc сетей до сих пор связано с большим количеством проблем, одной из которых является отсутствие технологий оценки их качества.

Введение

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

• Низкая стоимость. Массовое производство электронных устройств значительно дешевле производства, установки и настройки многокомпонентного комплекса, решающего аналогичную задачу.
• Быстрота развертывания. Беспроводная сеть готова к работе практически сразу же после размещения и включения всех устройств.
• Высокая эффективность. Благодаря возможности одновременного применения большого количества устройств,  беспроводная сеть обеспечивает высокую эффективность при решении практически любых задач, особенно таких как сбор данных и мониторинг [2].

В настоящее время разработано множество технологий, позволяющих свести к минимуму работу по настройке и обслуживанию беспроводных сетей [6][9]. Например, разработаны источники питания, извлекающие необходимую для работы энергию прямо из окружающей среды. Также разработаны алгоритмы и протоколы, обеспечивающие автоматическое конфигурирование таких сетей в реальном времени [8].

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

1.                        Параметры сенсорных сетей

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

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

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

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

• Физические свойства окружающей среды относительно наблюдаемого параметра.
• Особенности системы измерения контролируемого параметра.

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

2.                        Специализированные критерии оценки качества беспроводных сетей со сложной структурой

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

Критерий суммарной средней задержки:

N – количество устройств.

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

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

Критерий максимальной задержки:

- время работы системы.

- время доставки данных от узла i до базовой станции в момент времени t.

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

Критерий средней задержки:

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

3.                        Имитационная модель беспроводной  сети

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

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

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

• Модель топологии.
• Модель сетевой нагрузки.

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

Модель топологии сенсорной сети

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

Будем считать, что между устройствами и с координатами и существует прямая связь в том и только в том случае, если расстояние между ними меньше значения .

– связный неориентированный граф с взвешенными ребрами.

- базовая станция. E – множество ребер графа. Каждому радиоканалу между сенсорами и соответствует одно и только одно ребро . Вес каждого ребра определим как вероятность ошибки на канале. Вероятность ошибки на канале определим следующим образом:

Здесь - случайная величина, имеющая логнормальное распределение с - параметром, определяющим характеристики радиопередающих устройств. - параметры среды передачи данных.

Модели сетевой нагрузки

Беспроводные сети в настоящий момент являются универсальной технологией доставки самых различных данных. Самыми распространенными моделями источников сетевого трафика сегодня являются VoIP, HTTP и FTP. Такие модели с большой достоверностью воспроизводят трафик современных сетей общего назначения. Однако сетевая нагрузка беспроводных сетей со сложной структурой имеет свои особенности  и определяется спецификой применения отдельно взятой сети. Такие сети применяются обычно для отслеживания физических параметров окружающей среды. Появление на узле сети полезных данных, требующих доставки, полностью определяется двумя составляющими:

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

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

Периодический источник данных

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

- период появления данных.

- объем данных.

Здесь и являются константами, зависящими только от настроек сенсоров. Такая модель характерна, например, для систем сбора статистических данных.

Источник случайных данных с непрерывным контролем

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

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

Таким образом, модель источника данных будет определяться следующим образом:

-период появления данных.

- случайная величина, распределенная по экспоненциальному закону с .

- среднее значение периода появления новых данных.

- время реакции на изменение параметра.

- объем данных.

Источник случайных данных с периодическим контролем

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

Модель источника данных будет определяться следующим образом:

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

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

- время между двумя последовательными замерами контролируемого параметра.

- объем данных.

Вероятность появления данных в момент времени будет определяться следующим образом:

.

Здесь - начальный момент времени.

В остальные моменты времени вероятность появления данных равна нулю.

Источник множественных пространственно-локализованных данных

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

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

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

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

- объем данных.

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

Для имитационного моделирования беспроводной сети со сложной структурой использовалась система моделирования сетей DaSSF [12].

DaSSF (Dartmouth SSF) – это реализованная на C++ система SSF (Scalable Simulation Framework). SSF – унифицированный, объектно-ориентированный API (Application Programming Interface) для дискретно-событийной симуляции больших сложных систем. Реализация DaSSF основана на высокопроизводительном ядре, обладающем большим запасом производительности параллельных вычислений. DaSSF подходит для моделирования больших расширяемых систем.

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

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

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

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

Особенности передачи данных беспроводными устройствами определяет стандарт IEEE 802.11 [11]. Для имитации канального уровня была реализована DCF (Distributed Coordination Function) [4][5] как метод доступа к среде. Также были программно реализованы источники данных, описанные в данной работе.

Для добавления новых источников данных и протоколов маршрутизации были разработаны базовые классы "Источник данных", "Протокол маршрутизации", "Топология".

4.                        Методика оценки протоколов маршрутизации для беспроводной сенсорной сети

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

1. Выбор критерия качества.
2. Определение основных характеристик сети: количество устройств, среднее количество "соседних" устройств, битовая скорость передачи.
3. Выбор модели источника полезных данных. Для новых моделей необходима программная реализация.
4. Программная реализация рассматриваемого протокола.
5. Сравнение протокола по результатам имитационного моделирования с базовыми протоколами на основе выбранного критерия оценки.

Выводы

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

Список литературы

1. Карабуто А. "Сенсорные сети". "Компьютерра" №29-30 от 24 августа 2004 г.
2. "Instrumenting the World" http://www.intel.com./research/exploratory/instrument_world.htm
3. Xiaoyan Hong, Kaixin Xu, Mario Gerla. "Scalable routing protocols for mobile ad hoc networks" University of California at Los Angeles, Network, IEEE, Volume 16, Issue 4, Jul/Aug 2002 Page(s):11 - 21.
4. "Medium Access Control for Wireless Sensor Networks" http://www.isi.edu/scadds/projects/smac/
5. "The MAC level (link layer)" http://www.hpl.hp.com/personal/Jean_Tourrilhes/Linux/Linux.Wireless.mac.html
6. W. Steven Conner, Jasmeet Chhabra, Mark Yarvis, Lakshman Krishnamurthy. "Experimental Evaluation of Topology Control and Synchronization for In-Building Sensor Network Applications" Mobile Networks and Applications Volume 10, Number 4 August 2005.
7. Дорошенко А.Е., Жереб К.А. Шевченко Р.С. "О моделировании сенсорных сетей средствами высокого уровня"", Проблеми програмування, 2006, №2-3. Спеціальний випуск
8. Rajesh Krishnan "Efficient self-organization of large wireless sensor networks", Boston University, 2004.
9. А. Е. Куприянов "Стек протоколов защищенной вероятностной маршрутизации в беспроводных сенсорных сетях", Сборник трудов конф. «Современные информационные технологии и ИТ-образование», М.: МАКС Пресс, 2005.
10. Никольский В.В., Никольская Т.И. Электродинамика и распространение радиоволн, М.: Наука, 1989 г., 543 с.
11. IEEE Computer Society, L. M. S. Wireless LAN medium access control (MAC) and physical layer (PHY) specification, 1997.
12. J. Liu and D. M. Nicol. DaSSF 3.1 User's Manual, April 2001.