HUMAN MOBILITY MODEL FOR SIMULATION MODELING OF WIRELESS DELAY TOLERANT NETWORKS

Full Text

Введение Толерантные к задержкам сети (DTN-сети), являющиеся частным случаем сетей MANET - беспроводных децентрализованных самоорганизующихся сетей, состоящих из мобильных устройств, в настоящее время представляют одно из бурно развивающихся направлений в области систем связи и передачи информации. Вследствие большой сложности подобного вида систем основным инструментом для оценки их характеристик на этапе проектирования является имитационное моделирование, и проблема построения адекватной модели чрезвычайно важна. Архитектуры DTN - это подход к построению сетей, толерантных к задержкам и частым обрывам связи [1]. Типичной для них является ситуация, когда между отправителем и получателем информации вообще никогда не возникает канала связи, и потому их основной принцип - это «Store-Carry-Forward» («Сохранил - Перенес - Передал»). Очевидно, что ключевое значение для характеристик данного типа сетей имеют характеристики подвижности сетевых узлов. Поэтому при моделировании такого рода сетей адекватность используемой модели мобильности узлов является решающим фактором, влияющем на качество моделирования и на ценность получаемых при этом результатов. Одной из лучших в смысле адекватности моделей абонентской мобильности в настоящее время считается модель SLAW (Selfsimilar Least Action Walks), предложенная в [2]. Она предназначена для ситуаций, когда узлами DTN сети являются носимые людьми мобильные устройства с малым радиусом действия встроенного приемопередатчика, и хорошо описывает такие важные черты человеческой мобильности, как распределение Леви для длин переходов, кластеризация точек остановок и самоподобный характер распределения точек остановок на плоскости ([2], [3]). Это приводит к тому, что распределение вероятностей для времени между контактами пары узлов (ICT - Inter-Contact Time), являющейся одной из главных характеристик, по которой судят об адекватности модели подвижности для моделирования работы сети DTN, у нее одна из самых близких к измеренной на реальных сетях. Однако у модели типа SLAW имеется существенный практический недостаток: для ее запуска требуется весьма большое количество информации, которую можно получить только с реально работающей сети, которую надо смоделировать. В данной работе мы предлагаем гибридную модель подвижности, которая сочетает черты модели SLAW и модели случайных блужданий Леви. Предложенная модель практически не требует информации, которую можно получить только с работающей сети, и при этом приближает распределение вероятностей ICT лишь немного хуже, чем SLAW. Кроме того, работу гибридной модели можно использовать для получения необходимой для модели SLAW информации, при этом результаты запуска SLAW с полученными таким образом параметрами тоже оказываются лишь немного хуже, чем при использовании реальных данных. В следующем разделе мы опишем модель SLAW и предлагаемую гибридную модель, так как у них много общего. Модели абонентской мобильности Для разумного упрощения описания модели, реальное движение объекта (человека) представляется как совокупность прямолинейных переходов и пауз между ними. Паузы происходят в так называемых путевых точках. Известно [4], что расстояние между точками реальных перемещений, а также время паузы в путевых точках, имеют распределения вероятностей, близкие к распределению Леви. Плотность распределения Леви с числовыми параметрами и в элементарных функциях не выражается, ее Фурье-образ есть [5] . (1) Модель движения, где узел каждый шаг выбирает направление согласно равномерному распределению по углу, длину перехода и время паузы после перехода согласно распределению Леви, называется случайным блужданием Леви, она является одной из популярных моделей человеческой мобильности [5]. Однако кластеризацию и самоподобное расположение путевых точек эта модель не отражает. Модель SLAW отражает указанные черты, но требует наличия данных о реальных перемещениях узлов на территории, занимаемой моделируемой сетью. Сначала необходимо преобразовать данные о реальной мобильности, представляющие, как правило, отметки GPS координат узлов через равные промежутки времени (как правило, 30 с), в последовательность путевых точек и переходов между ними. Будем считать, что у нас есть данные о реальной мобильности нескольких узлов. Для каждого из них они преобразуются в путь, состоящий из путевых точек и переходов. В одну путевую точку объединяются все отметки из трассы реальной мобильности, которые находятся в круге радиусом 5 м, и время от момента первой, попавшей в путевую точку отметки до последней, считается временем, проведенным в путевой точке. Отметки, не попавшие ни в одну путевую точку (у которых в радиусе 5 м нет других отметок) считаются принадлежащим переходу, и игнорируются, так как переход считается прямолинейным между соседними по времени путевыми точками. Это обычная обработка, которую производят перед построением большинства моделей мобильности. Именно после такой обработки говорят о распределении Леви для расстояний между соседними точками и для времени остановки в путевой точке. Параметры этих распределений используются в разных моделях, в том числе SLAW и предлагаемой гибридной модели. Перейдем к обработке, характерной для моделей SLAW. После того, как путевые точки для всех узлов сети сформированы, из них всех, без разбора принадлежности тому или иному узлу, формируются локации. Каждая локация - это минимальный прямоугольник со сторонами, параллельными координатным осям, описанный вокруг транзитивного замыкания путевых точек с радиусом R, равным радиусу действия приемопередатчика узла (как правило, и в данной работе тоже, R = 100 м). Транзитивное замыкание - это множество точек, формируемых по следующему правилу: точка, находящаяся на расстоянии не более R от точки, принадлежащей транзитивному замыканию, сама принадлежит этому замыканию. Смысл выделения локаций напрямую связан с предназначением модели для моделирования сетей мобильных устройств. Локации - это кластеры путевых точек, возникающие в местах скопления пользователей, при этом между узлами, находящимися в разных локациях, существование канала связи заведомо невозможно. Для каждой локации модели SLAW необходимо знать число путевых точек в ней, а также данные о самоподобном характере распределения этих точек внутри локаций - так называемый график частичных дисперсий. Строится он следующим образом: каждая сторона прямоугольника, ограничивающего локацию, делится пополам, и образуются четыре равных части (N = 4 для каждой подобласти). Количество путевых точек в каждой четвертине считается элементом выборки, для которой вычисляется эмпирическая дисперсия. Далее эти числа усредняются по всем локациям, и получается частичная дисперсия первого уровня (l = 1). После этого каждая четвертая часть локации также делится на четыре части, и для каждой локации получается выборка из 16 элементов, и усредненная по всем локациям эмпирическая дисперсия этих выборок дает частичную дисперсию второго уровня (l = 2), и т.д. Всего таких уровней восемь. После получения всех этих данных модель SLAW начинает работу с распределения модельных путевых точек по локациям и определения порядка их обхода. Из экономии места мы не будем описывать соответствующие алгоритмы, они детально описаны в [6]. Заметим, что в результате смоделированные путевые точки расставляются внутри локаций не только с сохранением распределения Леви с нужными параметрами для расстояний между ними, но и с сохранением самоподобия в их позициях внутри локации. Кроме того, существует алгоритм поиска следующей локации, когда в текущей все точки пройдены. Все это обеспечивает весьма близкое к реальному распределение ICT. Очевидно, что для SLAW требуется очень много информации о реальной мобильности на данной территории, что делает проблематичным ее использование, когда такая информация отсутствует. В данной работе мы предлагаем гибридную модель, для которой информации требуется гораздо меньше. Для нее требуется только параметры распределения Леви для расстояния между путевыми точками, и набор ограничивающих локации прямоугольников. Заметим, что локации можно определять не только в результате обработки реальных данных, но и из внешних соображений. Можно угадать места скопления пользователей по назначению зданий и помещений внутри здания, можно использовать данные об интенсивности трафика через точки доступа существующих беспроводных сетей (типа Wi-Fi) и т.д. При запуске гибридная модель начинает работу со стартовой путевой точки, случайным образом выбранной внутри первой локации. От нее она делает шаг случайного блуждания Леви с нужными параметрами, и проверяет, попадает ли следующая путевая точка в локацию или нет. Если да, то делается следующий шаг случайного блуждания Леви и т.д. Если же нет, то направление такого «слишком длинного» шага изменяется так, чтобы попытаться «удержать» точку внутри локации. Нетрудно видеть, что самый длинный шаг можно удержать внутри локации, если делать его в направлении самого дальнего от текущей путевой точки угла ограничивающего локацию прямоугольника. Если после такого изменения направления точка осталась внутри локации, то все продолжается по-прежнему. Если же даже при таком повороте новая путевая точка все равно оказывается вне локации, и такая ситуация случилась в данной локации первый раз, то такой слишком длинный шаг игнорируется, и все продолжается как прежде. Однако, когда это случается второй раз, то начинает работу алгоритм смены локации, который полностью совпадает с алгоритмом смены локации у SLAW (игнорирование первого выхода за пределы локации - это эвристика, улучшающая качество моделирования, и найденная экспериментальным путем). Результаты имитационного моделирования Таким образом, предлагаемая модель внутри локации ведет себя как модель случайного блуждания Леви, но с неравномерным распределением направлений шагов, а при переходах между локациями - как модель SLAW. Поэтому она и названа гибридной моделью. Для сравнения результатов моделирования на основе гибридной модели, модели SLAW и модели Леви, они были реализованы в среде имитационного моделирования OMNeT++ [7] с помощью фреймворка INET [8] (подробнее см. в [9]). Использовались данные о реальной мобильности с территории кампуса института KAIST (Korea Advanced Institute of Science and Technology). Эти данные взяты с общедоступного ресурса CRAWDAD [10] Дартмутского колледжа. Указанный ресурс был создан сотрудниками колледжа для коллекционирования различных статистических данных о мобильных сетях. Трассы на данной территории записывались 92 участниками, которые были случайным образом отобраны из студентов кафедры информатики. Каждую неделю 2 или 3 случайно выбранных студента носили GPS-приемники на протяжении всей своей дневной активности. Рисунок 1. Функции CCDF длины перемещений Рисунок 2. Функции CCDF для ICT Рисунок 3. Графики дисперсий путевых точек Результаты прогона описанных выше моделей на одной и той же территории, в сравнении с результатами, полученными по данным реальной мобильности на этой же территории, приведены на рисунке 1, где представлены графики функций CCDF для длины перемещений узлов сети DTN. На рисунке 2 представлены графики CCDF для времени между контактами пары узлов ICT, а на рисунке 3 - графики дисперсий путевых точек для каждого уровня разбиения. Там же приведены результаты запуска модели SLAW, когда нужные для нее данные получены путем запуска гибридной модели. Видно, что и гибридная модель и SLAW на данных гибридной модели лишь незначительно уступают в точности воспроизведения как распределения Леви для расстояний между путевыми точками, так и ITC по сравнению с результатами SLAW на реальных данных. По данным риунка 3 видно, что гибридная модель, наряду с моделью SLAW, воспроизводит самоподобное поведение путевых точек, близкое к реальным данным, в то время, как модель Леви, крайне плохо моделирует набор дисперсий по отношению к реальной ситуации. Аналогичные результаты были получены и для других территорий, данные о которых так же, как и для территории KAIST, доступны в [10]. Заключение Предложена гибридная модель человеческой подвижности, отражающая такие важные черты абонентской мобильности, как распределение Леви расстояния между путевыми точками и кластеризацию путевых точек. Для построения она требует значительно меньше информации, чем модель типа SLAW, незначительно уступая ей по качеству. Продемонстрирована возможность использования гибридной модели для получения информации, недостающей для запуска SLAW. Запуск SLAW на этих данных также незначительно уступает по качеству моделирования запуску SLAW на реальных данных.

About the authors

Alexander Aleksandrovich Tsarev

Samara National Research University

Email: al-xandr1@yandex.ru

Alexander Yurievich Privalov

Samara National Research University

Email: privalov1967@gmail.com

References

Supplementary files