Содержание к диссертации
Введение
Глава 1. Анализ современных представлений о беспроводных сенсорных сетях 13
1.1 Архитектура беспроводных сенсорных сетей 16
1.1.1 Состав БСС 16
1.1.2 Топология БСС 20
1.1.3 Масштабирование БСС 23
1.1.4 Самоорганизация БСС 25
1.1.5 Архитектура сенсорных узлов 25
1.2 Протоколы и стандарты, используемые для организации беспроводных сенсорных сетей 29
1.2.1 Протоколы физического уровня 29
1.2.2 Протоколы уровня звена данных 31
1.2.3 Протоколы сетевого уровня и протоколы маршрутизации 33
1.2.4 Протоколы транспортного уровня 35
1.2.5 Протоколы верхних уровней 36
1.3 Приложения беспроводных сенсорных сетей 38
1.4 Выводы главы 1 41
Глава 2. Модели трафика сенсорных узлов 42
2.1 Модель трафика для приложений с периодической отправкой данных 44
2.2 Модели трафика для приложений с управляемой событием отправкой данных 45
2.3 Моделирование источника трафика беспроводной сенсорной сети слежения за линейно движущейся целью 51
2.3.1 Описание имитационной модели 51
2.3.2 Теоретическая модель 53
2.3.3 Результаты имитационного моделирования 56
2.3.3.1 Распределение длин ON-интервалов 56
2.3.3.2 Распределение длин OFF-интервалов 58
2.4 Выводы главы 2 64
Глава 3. Методы анализа характеристик трафика в беспроводных сенсорных сетях
3.1 Определение средней интенсивности трафика и среднеквадратического отклонения данной величины 66
3.2 Определение характеристик функции распределения трафика 67
3.3 Определение степени самоподобия и долговременной зависимости трафика 73
3.3.1 Анализ нормированного размаха (R/S-анализ) 75
3.3.2 Метод Хигучи 78
3.3.3 Анализ дисперсии агрегированных рядов 81
3.3.4 Методы Виттла 82
3.3.5 Метод анализа периодограмм 84
3.3.6 Вейвлет-анализ 85
3.4 Модель анализа характеристик трафика на шлюзе БСС 87
3.5 Выводы Главы 3 89
Глава 4. Исследование характеристик агрегированного трафика сенсорной сети слежения за целью 90
4.1 Обзор исследований характеристик агрегированного трафика БСС 90
4.2 Описание беспроводной сенсорной сети слежения за целью 91
4.3 Описание имитационной модели 93
4.4 Зависимость трафика на шлюзе сети от параметров движения цели 95
4.4.1 Случайное движение цели 95
4.4.1.1 Влияние средней длины OFF-интервала 96
4.4.1.2 Влияние средней длины ON-интервала 102
4.4.1.3 Влияние формы распределения длин ON и OFF-интервалов 104
4.4.1.4 Влияние скорости передачи данных в течение ON-интервала 108
4.4.2 Линейное движение цели 111
4.4.2.1 Влияние скорости движения цели 111
4.4.2.1 Влияние скорости передачи данных в течение ON-интервала 113
4.5 Рекомендации по планированию, проектированию и расчету беспроводных сенсорных сетей слежения за целью 118
4.6 Метод генерации трафика с заданной степенью самоподобия и долговременной зависимости 120
4.7 Выводы главы 4 122
Заключение 123 Список сокращений и условных обозначений 125
Словарь терминов 127
Список литературы 130
Список иллюстративного материала
- Самоорганизация БСС
- Моделирование источника трафика беспроводной сенсорной сети слежения за линейно движущейся целью
- Определение степени самоподобия и долговременной зависимости трафика
- Зависимость трафика на шлюзе сети от параметров движения цели
Самоорганизация БСС
В то же время, если предположить, что к сенсорным узлам некой БСС не предъявляется специфических требований, касающихся стоимости, размера, энергопотребления и, соответственно, вычислительных мощностей и памяти устройства, то использование стека TCP/IP в таких БСС выглядит вполне оправданным. В этом случае необходимости в высокоуровневом шлюзе БСС нет, существует только необходимость преобразования протоколов физического уровня и уровня звена данных (см. Рисунок 2).
Существует достаточно много исследований возможности использования протоколов TCP/IP для БСС. Например, в [7] приводится несколько идей, которые могут позволить использовать протоколы TCP/IP даже в сенсорных узлах, не обладающих значительными вычислительными мощностями и большим запасом электроэнергии, в частности, сжатие UPD-заголовков, выбор узлом ІР-адреса исходя из месторасположения узла, маршрутизация на основе широковещательной рассылки UDP-пакетов и т.д. Также в [7] утверждается, что для реализации необходимых протоколов в сенсорном узле достаточно иметь всего нескольких сотен байт памяти. В [8] авторы приводят модификацию протокола TCP с распределенным хранением пакета в узлах, через которые он проходит по пути от источника к получателю, с целью уменьшения пути повторной пересылки пакета в случае, если пакет был сброшен. Такая модификация протокола TCP делает его более приемлемым для беспроводных сетей, где вероятность ошибки в канале выше, чем в проводных сетях (для которых изначально разрабатывался протокол TCP), поэтому проверка пакета по порядковому номеру и контрольной сумме только в конечном узле и повторная пересылка из узла-источника, а не из промежуточных узлов, может быть неоптимальной стратегией передачи.
Пример автономной сенсорной сети для домохозяйства, построенной на базе протоколов IP и TCP, приведен в [9]. В [10] также приводится пример БСС для обнаружения вторжений, использующей данные протоколы.
Дополнительным фактором, который может расширить границы применимости протоколов стека TCP/IP в БСС является устойчивая тенденция к уменьшению габаритов, стоимости и энергопотребления вычислительных устройств при увеличении их вычислительной мощности и объема памяти. Сохранение данной тенденции может в будущем позволить реализовывать на базе сенсорных узлов протоколы, гораздо более сложные, чем это представляется возможным сейчас.
Таким образом, все вышеперечисленные данные свидетельствуют о том, что тенденцией развития БСС вполне вероятно может стать отказ от использования специфичных протоколов для БСС и переход к максимальному использованию протоколов стека TCP/IP. В таком случае необходимость в шлюзе БСС, преобразующим протоколы от сетевого уровня и выше, фактически пропадает, и, соответственно, приобретает актуальность сценарий сопряжения БСС с сетью Интернет, приведенный на рисунке 2.
Немаловажной функцией БСС является также обработка данных, полученных от сенсорных узлов, и предоставление их конечному потребителю. Данные функции могут выполняться в том же устройстве, что реализует функцию коллектора данных и преобразования протоколов (см. Рисунок 1), так и быть вынесена на отдельное оборудование за пределы БСС. Кроме того, в составе БСС могут находится устройства, ответственные за предварительное агрегирование данных.
Агрегирование данных в промежуточных узлах БСС, которое также по сути является формой обработки данных, позволяет решать ряд проблем, связанных с энергопотреблением узлов. Значительная часть электроэнергии тратиться сенсорным узлом именно на передачу данных [11], а не на сам процесс получения данных из окружающей среды и их обработку, в связи с этим логичным путем уменьшения энергопотребления узла видится уменьшение объема передаваемых данных путем их предварительной обработки в промежуточных узлах связи. Кроме того, было показано, что для БСС, в которых данные от сенсорного узла к шлюзу или конечному потребителю данных передаются посредством других узлов (см. раздел 1.1.2), характерно неравномерное распределение сетевой нагрузки и, соответственно, энергетических затрат узлов, которое зависит от степени близости сенсорного узла к шлюзу [12].
Само по себе агрегирование данных в промежуточных узлах возможно по причине того, что при достаточно плотном расположении сенсорных узлов на сенсорном поле данные от соседних узлов часто будут совпадать. Это дает возможности для объединения таких частично совпадающих данных и, таким образом, уменьшения объема передаваемой узлом информации [13]. За прошедшие годы было разработано достаточно больше количество технологий и алгоритмов агрегирования трафика, с некоторыми из них можно познакомиться в [14].
В беспроводных сетях связи существует два режима взаимодействия узлов: инфраструктурный (или управляемый) и ad hoc (или целевой) режимы [1]. Для более традиционных беспроводных и проводных сетей связи характерен инфраструктурный режим, где обмен информацией между двумя узлами всегда происходит посредством инфраструктурных элементов (точек доступа для беспроводных сетей, коммутаторов и маршрутизаторов — для беспроводных).
Данный режим работы не подходит для большинства БСС, так как режим и местность развертывания БСС чаще всего не предполагают наличия какой-либо инфраструктуры. Так, БСС могут располагаться на труднодоступных территориях, или территориях где отсутствуют сети передачи данных или электропитания. Во многих сценариях развертывания БСС предполагается, что они будут размещены на местности минимально трудозатратным методом (например, путем разбрасывания с борта самолета или вертолета). Кроме того, следует отметить, что обычно размер площади радиопокрытия сенсорного узла невелик (это диктуется соображениями экономии электроэнергии), поэтому при использовании инфраструктурного режима, пришлось бы достаточно часто располагать инфраструктурные элементы сети (точки доступа), что, с учетом вышеописанных особенностей БСС, представляется возможным далеко не всегда.
По этим причинам для построения БСС используется ad hoc режим функционирования сети, при котором сенсорные узлы связываются друг с другом напрямую, без участия точек доступа. Этот подход, кроме преимуществ более простого развертывания сети, дает также возможность строить так называемые multihop, или многоинтервальные сети. В таких сетях данные между источником и получателем могут передаваться не только напрямую, но и при необходимости через промежуточные узлы (см. Рисунок 3).
Моделирование источника трафика беспроводной сенсорной сети слежения за линейно движущейся целью
Одной из проблем анализа нормированного размаха является конечность анализируемого набора данных, в то время как условие (18) выполняется при и—»оо.
Кроме того, при малых значениях t достоверность вычисления размаха отклонений вызывает сомнения в силу небольшого размера блока данных, используемых для расчета. Для преодоления этого недостатка необходимо отбрасывать несколько точек, соответствующих наименьшим значениям t, при построении линейной аппроксимирующей функции. Однако неочевидно, какое именно количество точек должно быть отброшено для достижения наибольшей точности оценки параметра Хёрста.
В некоторых источниках указывается, что R/S-анализ не подходит для точной оценки коэффициента Хёрста ряда данных и может служить лишь качественным, но не количественным индикатором самоподобности ряда данных
Другим методом оценки параметра Хёрста, использующим связь самоподобия с фрактальной размерностью, является метод Хигучи, описанный в [53].
Фрактальная размерность кривой дает представление о степени «изрезанности» данной кривой, то есть о том, насколько увеличивается ее измеряемая длина с уменьшением измерительного отрезка. Расчет этой характеристики можно показать на примере строгого фрактала (например, кривой Коха):
Теоретически фрактальная размерность и параметр Хёрста характеризуют различные параметры временного ряда. Фрактальная размерность — локальная характеристика степени «изрезанности» ряда в данной точке, в то время как коэффициент Хёрста является глобальной характеристикой временного ряда. В то же время большим количеством эмпирических наблюдений, а также некоторыми аналитическими моделями (например, Броуновским движением) было подтверждено следующее выражение, связывающее локальную и глобальную характеристику процесса:
Несмотря на то, что в той же работе [54] приведены примеры процессов, для которых данное соотношение не выполняется, оценку параметра Хёрста посредством вычисления топологической размерности имеет смысл применять в комплексе с другими методами оцени степени самоподобия, с целью уточнения и проверки результата. В то же время к полученной данным методом оценке по описанной выше причине стоит относиться с некоторой степенью критичности.
Полученные усредненные значения длин дуг Цк) и соответствующе им значения к необходимо отметить в логарифмических осях. Полученные точки необходимо аппроксимировать линейной функцией, построенной с помощью метода наименьших квадратов. Угловой коэффициент полученной линии, умноженный на -1, будет в соответствии с формулой (25) являться оценкой фрактальной размерности изначального временного ряда D.
Таким образом, рассчитав дисперсию рядов, полученных агрегированием исходного ряда с разным шагом т, отметив в логарифмических полученные значения дисперсии по отношению к числу т и аппроксимировав полученные точки линейной функцией по методу наименьших квадратов, мы получим функцию, угловой коэффициент которой будет равен оценке параметра Хёрста.
Методы Виттла — семейство методов вычисления коэффициента Хёрста, анализирующее, в отличие от предыдущих трех представленных методов, не временные отсчеты исследуемого сигнала, а его функцию спектральной плотности.
Другой особенностью данных методов является использование для нахождения оценки параметра Хёрста оптимизации (минимизации разницы между теоретической функцией с неизвестными параметрами и практическими данными), а не графического метода, как в предыдущих случаях.
Для оценки коэффициента Хёрста по методу Виттла в первую очередь необходимо преобразовать анализируемый временной ряд X = Xi, Х2, ..., XN В значения его спектральной функции 1(D) С ПОМОЩЬЮ следующего выражения:
Метод Виттла в основном его понимании подразумевает, что вид функции спектральной плотности f(v;rj) для заданного временного ряда известен, и необходимо только найти такие ее параметры (вектор параметров rf), такие, чтобы разница между функцией f(v;rj) и значениями спектральной функции I(v) исходного сигналах , была минимальной:
Существует ряд способов увеличения надежности такой оценки, один из которых называется агрегированным методом Виттла и используется для анализа достаточно длинных временных рядов. Суть данного метода заключается в разбиении изначального временного ряда на несколько новых рядов, при этом, если изначальный временной ряд обладал свойством самоподобия, то при достаточно частом делении полученные отрезки будут близки к фрактальному гауссовскому шуму, поэтому из можно будет исследовать с помощью описанного ранее метода Виттла, приняв, что/(у; rj) берется из модели фрактального гауссовского шума [56].
Определение степени самоподобия и долговременной зависимости трафика
На сетевом уровне использовался протокол IP вместо более подходящего для БСС 61оWPAN, так как выбранный 4 года назад для проведения моделирования программный пакет Network Simulator-2 не поддерживает протокол 6I0WPAN, а для более новой и поддерживающей данный протокол версии программного пакета Network Simulator-З производителями не была обеспечена обратная совместимость со скриптами, написанными для Network Simulator-2. В качестве протокола маршрутизации был выбран AODV как протокол, разработанный специально для ad hoc сетей и широко использующийся для создания БСС.
На прикладном уровне были реализованы две модели отправки трафика: а) Для моделирования случайного движения цели: ON-OFF-модель с длинами интервалов ON и OFF, распределенными в соответствии с законом Парето. Средние значения длин интервалов ON и OFF, а также параметр формы распределения а и скорость передачи пакетов в течение ON-интервала в процессе исследования менялись для выяснения влияния данных параметров на характеристики трафика в сети. б) Для моделирования линейного движения цели — разработанная автором и описанная в разделе 2.3 модель для БСС слежения за линейно движущейся целью. В процессе исследования менялась скорость движения цели, а также скорость передачи данных в течение ON-интервала. Для обоих моделей была установлена фиксированная длина одного пакета, передаваемого в течение ON-интервала, равная 20 байтам.
Представленная имитационная модель может служить как самостоятельной БСС для небольшой территории слежения, так и кластером более крупной БСС.
Имитационная модель была реализована с помощью программного пакета Network Simulator-2. Листинг шаблона имитационной модели приведен в приложении Б. Последующая обработка производилась с помощью скрипта на языке Python с использованием библиотек Random, Numpy, Scipy, Matplotlib. Листинг скрипта приведен в Приложении В. 4.4 Зависимость трафика на шлюзе сети от параметров движения цели
При аппроксимации трафика каждого сенсорного узла моделью ON-OFF с распределением длин ON и OFF интервалов в соответствии с распределением Парето (подходящей для случая, когда цель движется по случайной траектории, см. раздел 2.2), может существовать несколько параметров модели, которые можно менять. Во-первых, это средние длины ON и OFF-интервалов, а также параметр формы распределения Парето, которое аппроксимирует длительности данных интервалов. Кроме того, скорость передачи данных в течение ON-интервала (или, с учетом допущения, что длины всех пакетов приблизительно одинаковы, — число пакетов, отправляемых в секунду) также может значительно влиять на характеристики суммарного трафика БСС.
При имитационном моделировании были выбраны из соображений здравого смысла приведенные в таблице 1 значения перечисленных выше параметров.
Значения по умолчанию для параметров модели ON-OFF с длинами интервалов ON и OFF, распределенными в соответствии с распределением Парето. Параметр Значение по умолчанию Длительность ON-интервала 10 секунд Длительность OFF-интервала 50 секунд Параметр формы распределения Парето для ON и OFF-интервалов 1,6 Число пакетов, передаваемых в секунду в течение ON-интервала 1 пакет в секунду Каждый из указанных в таблице 1 параметров в процессе моделирования менялся (при сохранении неизменными остальных параметров) для определения влияния данного параметра на итоговые характеристики трафика на шлюзе. Ниже представлено описание зависимостей характеристик трафика данных, сигнального и общего трафика на шлюзе БСС (среднего числа пакетов, приходящих в секунду, степени самоподобия трафика) от перечисленных выше параметров.
В данном сценарии моделирования средняя длина ON-интервалов составляла 10 секунд, параметр формы распределения длин ON и OFF-интервалов а был равен 1,6, скорость передачи данных в течение ON-интервалов составляла 160 бит/с (один 20-байтный пакет в секунду), а средняя длительность OFF-интервалов менялась от 5 до 100 секунд.
OFF-интервал характеризует промежуток времени, в течение которого цель находится на пределами сенсорной области узла и, соответственно, узел не передает данные (шлюзу. Логично предположить, что с увеличением длительности OFF-интервала интенсивность потока трафика должна снижаться. Это предположение подтверждается результатами имитационного моделирования: среднее число пакетов, приходящих на шлюз в секунду для представленной модели снижается от 17,5 20-байтовых пакетов в секунду при средней длительности OFF-интервалов, равной 5 секундам, до 3,5 пакетов в секунду при средней длительности OFF-интервалов, равной 60 секунда и больше (см. Рисунок 38). Каждая точка данного и последующих графиков является результатом усреднения данных, полученных в 10 независимых экспериментах Среднеквадратическое отклонение полученных в экспериментах данных можно найти в Приложении Г.
Учитывая характер снижения интенсивности, можно отметить, что при проектировании БСС следует избегать слишком маленького (менее 50-60 секунд) времени нахождения цели вне сенсорной области узла (например, с осторожностью следует увеличить число одновременно сканируемых целей, если характер их движения — случайный).
Зависимость трафика на шлюзе сети от параметров движения цели
На основании приведенных в предыдущем разделе результатов комплексной оценки характеристик трафика на шлюзе БСС слежения за целью создан следующий комплекс рекомендаций по планированию, проектированию и расчету БСС слежения за целью.
Так как моделирование было разделено на две части, исходя из использовавшейся модели трафика каждого сенсорного узла, рекомендации приводятся отдельно для БСС слежения за случайно движущейся целью и БСС слежения за линейно движущейся целью.
Для модели ON-OFF с распределением длин ON и OFF интервалов в соответствии с распределением Парето (подходящей для моделирования трафика каждого сенсорного узла при случайном движении цели) было показано, что значительное влияние на суммарный трафик оказывают такие параметры, как средняя длительность ON-интервала и средняя длительность OFF интервала. Форма распределения длительностей ON и OFF интервалов, напротив, не оказывает значительного влияния на характеристики трафика на шлюзе БСС.
Исходя из результатов данной части имитационного моделирования можно сформулировать следующие рекомендации, касающиеся планирования БСС: следует обращать внимание на параметры БСС слежения за случайно движущейся целью, которые могут влиять на длительность ON-интервалов (например, скорость движения цели) и длительность OFF-интервалов (например, число целей). При коротких OFF-интервалах и, особенно, длительных ON-интервалах следует ожидать не только возрастания интенсивность трафика, приходящего на шлюз БСС, но и увеличения степени самоподобия и долговременной зависимости этого трафика, что может негативно сказаться на качестве обслуживания в БСС.
Во второй части имитационного моделирования использовалась разработанная автором модель трафика сенсорных узлов при линейном движении цели, основанная на ON-OFF модели, в которой длительности OFF-интервалов имеют распределение с длинными хвостами, в то время как длительности ON интервалов имеют короткий левый хвост и практически отсутствующий правый хвост.
Результаты второй части имитационного моделирования показали, что для случая линейно движущейся цели скорость цели не оказывает значительного влияния на интенсивность и степень самоподобия и долговременной зависимости трафика, поступающего на шлюз БСС.
Кроме того, обе части имитационного моделирования показали, что увеличение скорости передачи данных в течение ON-интервалов (числа передаваемых в секунду пакетов) значительно увеличивает не только интенсивность трафика, поступающего на шлюз БСС, но и степень самоподобия и долговременной зависимости такого трафика. Таким образом, передача данных со скоростью более 160-320 бит/с (или одного-двух 20-байтных пакетов) может значительно ухудшить показатели качества обслуживания БСС.
Значительная зависимость степени самоподобия трафика (в том числе трафика данных) на шлюзе сенсорной сети от скорости (частоты) передачи пакетов в течение ON-интервала дает возможность предложить простой в реализации способ генерации трафика с заданной степенью самоподобия и долговременной зависимости. Предлагаемый метод основан на агрегации потоков от источников, реализующих ON-OFF модель с длинами ON и OFF интервалов, распределенных в соответствии с законом Парето. Ключевым моментом предложенного метода является изменение скорости (частоты) передачи данных в течение ON-интервалов, от которой зависит степень самоподобия и долговременной зависимости генерируемого трафика.
В настоящий момент существует несколько подходов к генерации трафика со свойствами самоподобия и долговременной зависимости. Так, в [64] приводится подход к генерации самоподобного трафика на основе фрактального Гауссовского шума. Расширение данного подхода с использованием вейвлетов Добеши описано в [65]. Генерация фрактального гауссовского шума с использованием быстрого преобразования Фурье приведена в [66] и некоторое улучшение данного подхода — в [67]. Данные методы, однако, достаточно сложны для реализации, а также в некоторых случаях требуют значительных вычислительных ресурсов.
Предлагаемый в данной работе метод, в отличие от приведенных выше, основан не на аналитических моделях, а на практическом сценарии генерации трафика. Данный сценарий подразумевает наличие N узлов, каждый из которых генерирует трафик в соответствии с ON-OFF моделью, где средние длительности ON и OFF-интервалов равны ONcp и OFFcp соответственно, а распределение длительностей ON и OFF-интервалов соответствует закону Парето с коэффициентом формы а. В течение ON-интервалов данные узлы передают пакеты размером М байт и числом к пакетов в секунду. При этом агрегация потоков трафика от данных источников, в соответствии с результатами, приведенными в разделе 4.4, даст поток, обладающий свойством самподобия и долговременной зависимости.
Следует отметить, что в работе [68] приводится математическое обоснование того, что подобный агрегированный трафик действительно будет обладать свойством самоподобия. Отличие предлагаемого метода генерации трафика от описываемого в [68] заключается в использовании скорости передачи данных в течение ON-интервалов для получения требуемой степени самоподобия и долговременной зависимости.
Изменять степень самоподобия и долговременной зависимости в предлагаемом методе можно при помощи изменения величины к — числа пакетов, передаваемых каждым из узлов в секунду в течение ON-периодов: чем больше число к, тем выше степень самоподобия и долговременной зависимости получаемого агрегированного потока.
Для примера в таблице 3 показано соотношение между числом к и параметром Хёрста (мерой самоподобия и долговременной зависимости) для комплексной модели, описанной в данной главе: 24 узла-источника, ONcp=\0 секундам и OFFcp=50 секундам, а=1,6 и размера пакета 48 байт (20 байт данных и 28 байт служебной информации).
