Анализ модели мобильности источников информации на основе априорных данных о повторяемости маршрутов тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат наук Царев Александр Александрович
Царев Александр Александрович
кандидат наук
2020
- Специальность ВАК РФ05.13.17
- Количество страниц 156
Оглавление диссертации кандидат наук Царев Александр Александрович
Введение
Глава 1 Анализ повседневной человеческой мобильности и проблематика её формализации
1.1 Современное состояние моделирования человеческой мобильности
1.2 Избранные модели человеческой мобильности
1.2.1 Модель мобильности Леви
1.2.2 Модель мобильности SLAW
1.3 Моделирование схожих периодических маршрутов
1.4 Исходные данные по реальной мобильности людей
1.5 Выводы
Глава 2 Имитационная модель человеческой мобильности и сравнение её с
моделью SLAW
2.1 Модификации модели мобильности Леви
2.2 Алгоритм гибридной модели человеческой мобильности
2.3 Сравнение гибридной модели и модели SLAW
2.4 Выводы
Глава 3 Имитационная модель случайного периодического маршрута с учётом
персистентности
3.1 Учёт персистентности ежедневных маршрутов
3.2 Персистентность реальных ежедневных маршрутов и эксперименты по их моделированию
3.3 Выводы
Глава 4 Применение гибридной модели для оценки характеристик процесса
передачи пакетов в сети DTN
4.1 Программа имитационного моделирования человеческой мобильности
4.1.1 Система имитационного моделирования OMNeT++
4.1.2 Фреймворк INET для среды моделирования OMNeT++
4.1.3 Детали тестовой реализации модели SLAW
4.1.4 Генератор случайных чисел с распределением Леви
4.2 Моделирование алгоритмов маршрутизации для DTN сетей
4.2.1 DTN сети и особенности маршрутизации в них
4.2.2 Простые протоколы маршрутизации
4.2.3 Протокол маршрутизации PROPHET
4.3 Архитектура программы для имитационного моделирования DTN сетей
4.4 Экспериментальные результаты для гибридной и SLAW моделей
4.5 Выводы
Заключение
Список литературы
Приложение А. Описание программы имитационного моделирования
Приложение Б. Описание формата файлов dartmouth/cenceme
Приложение В. Результаты анализа и моделирования трасс на всех территориях
Рекомендованный список диссертаций по специальности «Теоретические основы информатики», 05.13.17 шифр ВАК
Разработка алгоритмов передачи потоковых данных на прикладном уровне в сетях беспилотных летательных аппаратов2016 год, кандидат наук Васильев Данил Сергеевич
Разработка адаптивного алгоритма маршрутизации на основе роевого интеллекта пчелиной колонии для самоорганизующихся сетей беспилотных летательных аппаратов2021 год, кандидат наук Леонов Алексей Викторович
Метод иерархической маршрутизации мобильной самоорганизующейся сети доступа2014 год, кандидат наук Романов, Сергей Владимирович
Обеспечение безопасности маршрутизации в самоорганизующихся сетях на основе репутационной модели2023 год, кандидат наук Литвинов Георгий Александрович
Разработка и исследование алгоритмов маршрутизации в беспроводных кластерных сенсорных сетях2023 год, кандидат наук Голубничая Екатерина Юрьевна
Введение диссертации (часть автореферата) на тему «Анализ модели мобильности источников информации на основе априорных данных о повторяемости маршрутов»
ВВЕДЕНИЕ
Большое количество процессов, протекающих в современном обществе и современной техносфере, зависит от взаимодействий между людьми, причём в ряде случаев возможность такого взаимодействия определяется географическим положением (взаимным положением на местности) его участников. Достаточно точное описание особенностей человеческих перемещений позволяет создавать адекватные для практического применения модели мобильности, которые широко применяются в различных областях [1]: например, моделирование эпидемий [2-4], оценка миграционных потоков [5-8], модели типичной активности человека [9, 10], городское планирование [11-13], прогнозирование городского трафика [14, 15], моделирование беспроводных сетей архитектуры MANET [16-18], распространение вирусов мобильных устройств [19, 20] и др.
Из этих нескольких примеров ясно видно, что мобильность людей оказывают важное влияние на многие процессы в обществе и окружающей среде, в частности на процессы передачи информации между людьми, например, с помощью носимых коммуникационных устройств, и точное количественное описание человеческой мобильности часто имеет фундаментальное значение для понимания и анализа характеристик процессов, связанных с перемещением людей, и их влияниям на общество и окружающую среду [1].
Основная проблема состоит в том, что простых записей трассы перемещений людей, которые можно получить с помощью gps датчиков, часто недостаточно, т.к. для конкретных задач важны не сами изменения положений людей во времени, а целевые характеристики взаимодействия людей или характеристики их группового поведения: скопления, миграции, периодичность поведения и прочее. Для того чтобы подобные целевые характеристики было возможно получить, сначала определяются исходные координаты перемещений, а уже потом определяются интересующие зависимости между объектами и формализуются целевые параметры, которые оцениваются с помощью имитационного моделирования перемещений. Для этого строятся имитационные модели на основе реальных данных.
Второй аспект проблемы заключается в том, что на практике часто имеется недостаточно данных о реальных перемещениях, и они могут рассматриваться только как отдельные реализации случайного процесса перемещения людей. В то время как для конкретной прикладной задачи необходимо получить модель, способную воспроизводить много реализаций этого случайного процесса. Статистически представительный ансамбль таких реализаций используется для оценки конечных целевых параметров прикладных задач, отмеченных выше: прогнозирование количества заражённых людей болезнью, поток людей через интересующий инфраструктурный объект, частота доставляемых информационных пакетов в беспроводных сетях архитектуры MANET и т.д.
Актуальность задачи моделирования мобильности людей на некоторой территории обеспечивается потребностью в адекватных моделях для различных областей исследований, перечисленных выше. А из-за их достаточно сложной формализации в аналитическом виде и стохастической природы перемещений людей широко применяется имитационное моделирование, позволяющее сочетать аналитическое описание простых аспектов вместе с эвристическими улучшениями.
Степень разработанности темы исследования.
Возникающие вследствие перемещений людей взаимодействия часто носят временный характер, причём типичное время существования связи часто много меньше времени рассмотрения системы в целом, поэтому традиционное математическое описание множества объектов и связей между ними в виде графа или сети, сталкивается с рядом трудностей при описании динамической природы рёбер (связей).
Существенный вклад в изучение проблемы взаимодействия людей внесли авторы работ [21, 22], т.к. в них описан один из известных подходов - теория временных сетей [21, 22], включающая модели и методы анализа топологической и временной структуры изменяющихся во времени сетей для выяснения их связи с поведением динамических систем, которые они описывают. По отношению к традиционной теории сетей здесь есть принципиальные различия методов анализа и моделирования, поскольку фундаментальные свойства (такие, например, как
транзитивность ребер), не обязательно сохраняются во временных сетях, и поэтому многие из этих методов должны сильно отличаться от таковых для статических сетей. Изучение временных сетей носит очень междисциплинарный характер. Отражая это, даже объект исследования имеет много имен - временные графы, развивающиеся графы, динамические сети, динамические графы, и так далее.
В частности, при применении временных сетей для описания информационного процесса со взаимодействиями и встречами между людьми [21, 22] (так как с прикладной стороны эти встречи нужны для обмена некой информацией), как раз и приходится учитывать отмеченное выше ключевое отличие данного приложения временных сетей от других их приложений. А именно то, что люди перемещаются в пространстве, и на их перемещения влияет много факторов, которые довольно сложно формализовать: ландшафт местности, социальная значимость посещаемых или избегаемых объектов, время и длительность перемещений и много другое.
Даже просто сбор информации о такого рода перемещениях не является простой задачей, однако благодаря достижениям в таких областях, как беспроводная связь и системы глобального позиционирования, исследователи получили больше возможностей собирать информацию о человеческой мобильности. Поэтому в последние годы произошел бурный рост количества доступных геолокационных данных о перемещениях людей, что позволило количественно изучать индивидуальные и коллективные характеристики мобильности и создавать модели, которые могут отражать и воспроизводить пространственно-временные структуры и закономерности в человеческой мобильности.
Один из способов описания мобильности людей, в общем случае, сводится к построению и анализу модели мобильности отдельного человека: на основе такой мобильности формируется временная сеть, и с её помощью изучаются особенности взаимодействия между людьми. Именно такой подход используется в данной диссертационной работе. Другим подходом является моделирование общих потоков населения [1]. В обоих случаях необходимо обязательно учитывать характерные пространственные и временные масштабы процесса перемещений, которые
могут варьироваться от сотен метров до тысяч километров и от часов до лет. По этой причине каждый из этих случаев требует различных структур модели и методов моделирования.
На уровне потоков населения модели описывают совокупную мобильность многих людей и стремятся воспроизвести матрицы «пункт отправления - пункт назначения» путем оценки среднего числа путешественников между любыми двумя пространственными регионами (например, муниципалитетами) в единицу времени (то есть ежедневно в случае коммутирующих потоков, ежегодно в случае миграционных потоков), однако в данной работе мы такой подход не используем.
Что касается моделирования персональной мобильности, то в течение последнего десятилетия было проведено множество эмпирических и теоретических (вычислительных и имитационных) исследований сетевых связей, при этом возникающих. Определённое влияние на моделирование мобильности людей оказали авторы работ [23, 24]: они используют статические сети [23, 24] (однако и они позволили получить много полезных результатов). Временные сети, как было отмечено выше, обеспечивают новую структуру моделирования и анализа данных, принимая во внимание упорядочивание взаимодействий во времени [21, 22].
Поэтому в последние годы, с применением данного подхода, проблеме уделяли внимание авторы работ [5, 25-29], в которых сформированы такие модели, как, например, wifidog [25] и эволюционная мобильность [26], которые нацелены на мониторинг поведения людей в режиме реального времени. Исследования [5, 27-29] сфокусированы на детализированных данных большого количества узлов для временной сети. Однако, доступ к наборам данных о местоположениях перемещений отдельных людей на протяжении долгого времени с высокой точностью все еще затруднён из-за таких причин, как, стоимость сбора данных и конфиденциальность данных.
Индивидуальная мобильность характеризуются определенным уровнем неопределенности, связанной со свободной волей и произволом в действиях отдельных лиц, что приводит к некоторой случайности в траекториях (трассах) перемещений. Поэтому, самые ранние модели такой мобильности заимствуют понятия и
методы из случайных блужданий и броуновского движения. Работы [24, 30] в значительной мере способствовали изучению свойства периодичности в мобильности людей: в нескольких исследованиях [24, 30] подчеркивалось, что отдельные траектории далеко не случайны и обладают заметной степенью регулярности и предсказуемости, которые можно использовать для прогнозирования будущего местонахождения человека и для построения реалистичных генеративных моделей индивидуальной мобильности.
В диссертационной работе проведено исследование современных моделей индивидуальной мобильности и разработана собственная модель индивидуальной мобильности. Для сравнения адекватности и других свойств рассматриваемой модели в приложении к задаче оценки характеристик процесса передачи информации между носимыми мобильными устройствами, а также сравнения с другими моделями подобного рода, с использованием этих моделей проведено исследование характеристик нескольких алгоритмов маршрутизации сообщений в т.н. сетях DTN на некоторой территории.
Сети DTN (Delay Tolerated Network) - это, говоря кратко, сети, в которых узлы или источники информации общаются между собой по беспроводному протоколу связи и могут в процессе передачи информации перемещаться на плоскости в любых направлениях. Во многих случаях источниками в таких сетях являются маломощные передатчики, которые переносятся людьми. Поэтому модель мобильности людей (в данном случае, фактически, информационных источников сети) является составной частью модели информационного процесса передачи пакетов в DTN сети. Применение подобных сетей оправдано в случаях, когда нет инфраструктуры или возможности для работы мобильной или спутниковой связи, а также в случаях военных и спасательных операциях при стихийных бедствиях [1].
Работы авторов [31, 32] содержат фундаментальные результаты по моделированию мобильности людей, с сильными математическими выкладками. Поэтому из существующих моделей, и как пример для сравнения, и как начальная точка для разработки собственной модели, в диссертации используется т.н. модель SLAW (SLAW - Self-Similar Least Action Walk). Эта модель была разработана в
последнее десятилетие [31, 32] и способна адекватно отражать несколько важных особенностей реальной человеческой мобильности одновременно. Она учитывает не только распределение расстояний между соседними путевыми точками (то есть, точками, в которых происходит остановка и изменение направления движения) и распределение времени остановок в таких путевых точках, но и кластеризацию путевых точек на местности, и самоподобный характер расположения этих путевых точек внутри образуемых кластеров. Сравнения, сделанные в [31, 32], показывают, что в отражении указанных особенностей реальных человеческих перемещений, эта модель лучше модели мобильности Леви из [31, 33] (которой тоже будет уделено особое внимание в данной диссертации). Кластеризацию, свойственную реальным трассам человеческих перемещений, модели Леви вообще не отражают. Кроме того, SLAW точнее, чем Леви воспроизводят распределение времени между взаимодействием узлов сети связи (ICT - Inter-Contact Time), считающееся одной из важных характеристикой адекватности моделей мобильности, предназначенных для оценки параметров процессов передачи информации в сетях связи (в частности, в сетях DTN).
Однако работы авторов [31, 32] не могут быть в чистом виде применены для моделирования мобильности, т.к. модель SLAW обладает и некоторыми существенными недостатками, затрудняющими её использование во многих важных для практики ситуациях. А именно, для модели SLAW необходимо задать весьма много параметров: количества путевых точек в каждой локации (прямоугольнике, ограничивающем кластер) на маршруте каждого источника информации, границы локаций, и набор дисперсий распределения путевых точек внутри локации в зависимости от масштаба сетки разбиения территории. А для того, чтобы модель SLAW действительно адекватно отражала моделируемые перемещения, эти параметры вычисляются на основании реальных перемещений людей по данной территории, т.е. используя весьма большой набор исходных данных о моделируемой ситуации. Фактически, для того, чтобы применить модель SLAW для какой-то территории, необходимо иметь большой набор реальных трасс перемещений людей по данной территории. Именно это и ограничивает количество ситуаций, в
которых данная модель может быть использована. Также SLAW не учитывает возможное наличие априорной информации о многодневных перемещениях источников при многодневном моделировании.
Предложенная в диссертации модель не требует предварительного определения количества точек в локациях по маршрутам каждого источника информации, и потому необходимость наличия большого набора реальных данных о моделируемой ситуации отпадает при сохранении полезных свойств модели SLAW. Границы локаций по-прежнему должны быть заданы, но их не обязательно определять из реальных трасс перемещений. Дело в том, что локации соответствуют местам скоплений людей (производственные или учебные корпуса, аттракционы в парке отдыха и т.д.), и их границы могут быть определены исходя из этого. К ограничениям предлагаемой модели можно отнести определённую фиксированную форму локаций (прямоугольник, со сторонами, параллельными осям координат) и её подтверждённое использование (как и модели SLAW) только на локальных территориях, соизмеримых с кампусами университетов.
Кроме того, в предлагаемую модель на более систематической основе, чем в других современных моделях индивидуальной мобильности включён учёт приблизительной повторяемости ежедневных маршрутов, основанный на априорных данных о периодической повторяемости маршрутов, также являющийся важной чертой реальных перемещений людей. Введена количественная характеристика такой приблизительной повторяемости.
Объект исследования: мобильность людей с периодическими (ежедневными) маршрутами.
Предмет исследования: характеристики мобильности людей, влияющие на процесс передачи информации между носимыми ими информационными источниками.
Цель диссертационной работы:
Разработка и анализ модели мобильности источников информации в локальной области с учётом априорных данных о периодической повторяемости маршрутов подвижных источников, позволяющей оценивать характеристики передачи информации.
Задачи диссертационной работы:
1. Провести исследование существующих моделей мобильности людей, в частности, модели блужданий Леви и модели SLAW, выявить их преимущества и недостатки, а также определить направления их усовершенствования. Проанализировать реальные данные о мобильности и собрать из них статистические данные, необходимые для модели SLAW.
2. Построить модель мобильности, не требующую задания количества путевых точек в каждой локации - гибридную модель. Провести сравнительные имитационные эксперименты по моделированию мобильности с помощью SLAW модели и предложенной гибридной модели. В качестве сравнительной характеристики использовать время контакта между источниками (ICT) и длину переходов между путевыми точками.
3. Провести статистический анализ мобильности людей с точки зрения сходства их периодических (ежедневных) маршрутов. Ввести характеристику множества периодических маршрутов, показывающую степень их схожести. Построить имитационную модель маршрута (дополнение гибридной модели) с заданной степенью схожести, учитывающую априорные данные о повторяемости маршрутов, и провести эксперименты по генерации новых маршрутов. Проверить качество генерации посредством сравнения получаемой степени схожести.
4. Применить гибридную модель (дополненную) в задаче маршрутизации пакетов в сети DTN. Реализовать на алгоритмическом уровне ряд популярных протоколов маршрутизации в сети DTN. Провести экспериментальную оценку вероятности доставки информационного пакета, как важнейшей характеристики процесса передачи информации в подобных сетях, при моделировании мобильности
источников моделью SLAW, гибридной моделью, и при их совместном использовании.
Соответствие паспорту специальности:
Диссертация соответствует области исследований специальности 05.13.17 -Теоретические основы информатики по п. 2 «Исследование информационных структур, разработка и анализ моделей информационных процессов и структур».
Методология и методы исследования:
Исследование базируются на принципах системного анализа и общей теории систем, с использованием математического аппарата теории вероятностей и математической статистики.
Научная новизна:
В диссертационной работе впервые получены следующие результаты:
1. Разработана математическая модель (называемая гибридной) ежедневной мобильности людей, сочетающая в себе черты модели случайных блужданий Ле-ви и модели SLAW, и отличающаяся от других возможностью одновременно воспроизводить ряд важных характеристик человеческих перемещений: кластеризацию путевых точек, распределение длин перемещений между путевыми точками, схожесть ежедневных периодических маршрутов, распределение времени между взаимодействиями источников информации (носимых людьми коммуникационных устройств), не требуя задания количества путевых точек в каждой локации индивидуального маршрута.
2. Предложен способ использования гибридной модели для получения необходимой для модели SLAW информации, который, при отсутствии реальных данных, позволяет увеличить количество ситуаций, когда модель SLAW становится применимой.
3. Предложены количественная характеристика приблизительного постоянства дневных маршрутов человеческой мобильности - коэффициент перси-стентности, и метод её расчёта по данным каждодневных перемещений. Предложенная гибридная модель мобильности, учитывающая заданный коэффициент персистентности, позволяет имитировать перемещения для многодневных про-
межутков времени с примерным постоянством ежедневных маршрутов, в добавок к перечисленным в п.1 чертам человеческой мобильности.
4. С помощью разработанной программы имитационного моделирования человеческой мобильности, включающей базовую часть (моделирование многодневной человеческой мобильности) и проблемно-ориентированную составляющую для решения задач маршрутизации в сетях DTN, продемонстрировано (на уровне алгоритмов), что простые протоколы маршрутизации, учитывающие высокую персистентность ежедневных маршрутов, по вероятности доставки не уступают, а часто и превосходят более сложный универсальный протокол PROPHET для режима без дублирования пакетов.
Теоретическая значимость:
Теоретическая значимость состоит во-первых в том, что предлагаемая гибридная модель человеческой мобильности отражает присущую реальным перемещениям кластеризацию и длины переходов с распределением Леви, и при этом не требует для использования в имитационном моделировании указания количеств путевых точек в локациях на индивидуальных маршрутах, в отличие от модели SLAW, практически без потери качества моделирования; во-вторых в том, что применение алгоритма генерации параметров ежедневных индивидуальных маршрутов с учётом коэффициента персистентности позволяет более адекватно отразить примерное постоянство периодических (ежедневных) перемещений человека при моделировании мобильности на длительном промежутке времени.
Практическая значимость:
Практическая ценность исследования заключается в том, что разработанная с использованием предложенной модели программа имитационного моделирования позволяет решать задачу моделирования индивидуальной мобильности на некоторой локальной территории на протяжении нескольких модельных дней без необходимости знания детальной информации о реальных перемещениях на этой территории, которая требуется аналогичной модели SLAW для получения результатов, близких к реальным.
Достоверность полученных результатов:
Достоверность результатов проведенного исследования обеспечивается корректностью математических выводов используемых формул, а также близостью результатов имитационного моделирования к результатам статистического анализа реальных данных.
Защищаемые положения:
1. Предложенная гибридная модель мобильности, сочетающая в себе черты модели случайных блужданий Леви и модели SLAW, не требует задания количеств путевых точек для локаций в маршрутах у каждого источника информации, в отличии от модели SLAW, при сравнимом со SLAW качестве моделирования, превосходящем другие модели.
2. Гибридная модель может быть использована для получения количеств путевых точек для локаций в маршрутах у каждого источника информации, необходимых модели SLAW. Запуск модели SLAW при отсутствии реальных данных становиться возможным, при этом относительное СКО оценки ICT уменьшается до 66% от относительного СКО оценки ICT гибридной моделью, а при наличии реальных данных, возможно уменьшение относительного СКО для ICT до 31% по отношению к оценке SLAW на реальных данных.
3. Введённая мера постоянства ежедневных маршрутов позволяет учитывать это постоянство при моделировании многодневной мобильности, что улучшает качество моделирования многодневной мобильности.
4. Имитационным моделированием алгоритмов маршрутизации в мобильных сетях, толерантных к задержкам, экспериментально продемонстрировано, что простые протоколы маршрутизации, учитывающие высокую персистентность ежедневных маршрутов источников информации, не уступают по вероятности доставки пакета более сложному универсальному протоколу PROPHET (в режиме без дублирования пакетов), а иногда и превосходят его (до 70%).
Публикации:
Всего по теме исследования опубликовано 15 работ, в том числе 3 статьи в изданиях, рекомендованных Высшей аттестационной комиссией при Министерстве науки и высшего образования Российской Федерации, 4 работы опубликованы в трудах Международных и Всероссийских конференций, индексируемых базой Scopus. Имеется свидетельство о государственной регистрации программы для ЭВМ.
Структура диссертации:
В первой главе представлены постановка проблемы и обоснование её актуальности, а также детально сформулированы решаемые в работе задачи, их взаимосвязь, охарактеризованы использованные методы решения. Представлено описание современных моделей мобильности людей с выбором двух наиболее интересных: модель мобильности Леви и модель мобильности SLAW - на основании которых будет построена новая модель мобильности. Также приведено описание реальных данных, использующихся в диссертационной работе и результаты анализа этих данных, подтверждающие факт наличия кластеризации и самоподобия у путевых точек человеческих перемещений, а также наличие распределения вероятностей у расстояний между путевыми точками близкое к распределению вероятностей с тяжёлым хвостом.
Во второй главе представлена гибридная модель человеческой мобильности, которая сочетает в себе особенности модели мобильности Леви и особенности модели мобильности SLAW, но не требует задания количеств путевых точек для локаций в маршрутах у каждого источника информации для своего использования. Гибридная модель состоит из модели для одного дня (модель локации с алгоритмом выбора локации), плюс имитационная модель случайного периодического маршрута с учётом персистентности с использованием которой можно моделировать мобильность гибридной моделью на протяжении многих дней. Показано, что предложенная гибридная модель мобильности воспроизводит такие важные характеристики реальных перемещений, как распределение вероятностей Леви у расстояний между последовательными путевыми точками и кластеризацию путе-
вых точек, наравне с моделью SLAW, считающейся в настоящее время одной из самых адекватных моделей человеческой мобильности. И хотя качество моделирования характеристики ICT у гибридной модели имеет небольшое ухудшение, чем у модели SLAW, использование модели SLAW остаётся проблемным в условиях отсутствия реальных данных, что можно преодолеть путём совместного использования гибридной модели и модели SLAW. Это, по нашему мнению, один из важных и полезных результатов диссертационной работы.
В третьей главе продемонстрировано применение гибридной модели мобильности в ситуации, когда учитываются индивидуальные маршруты пользователей на протяжении нескольких дней, что позволяет приблизить имитацию перемещений к реальной ситуации при многодневном моделировании (человек здесь обозначается пользователем, потому что переносит и использует маломощный передатчик). Наш подход имеет систематический характер (отсутствующий в других работах по данной теме), так как мы вводим количественную меру перси-стентности (схожести, постоянства) ежедневных маршрутов, на основе которой генерируем новые маршруты. Этот подход предназначен для тех ситуаций, когда на практике имеются только данные о мобильности пользователя за один день или за небольшой промежуток времени, и задача состоит в указанной выше аппроксимации мобильности за пределами этого промежутка времени. Представлено детальное исследование персистентности ежедневной человеческой мобильности путём введения специальной характеристики - коэффициента персистентно-сти, и включение его в предлагаемую нами модель. Представлена модель случайного периодического маршрута с заданной степенью схожести, входящая в состав гибридной модели, и результаты моделирования ежедневных маршрутов показывают высокую близость к реальным данным по ряду характеристик: минимальной, максимальной и средней размерностям маршрутов, длине маршрутов и коэффициентам персистентности для больших значений коэффициента перси-стентности. Проведён последовательный учёт повторяемости индивидуальных маршрутов в гибридной модели.
Похожие диссертационные работы по специальности «Теоретические основы информатики», 05.13.17 шифр ВАК
Методы многопутевой маршрутизации с балансировкой нагрузки и обработки информации о местоположении абонентских терминалов в низкоорбитальных спутниковых системах связи с межспутниковыми линиями2020 год, кандидат наук Иванов Валерий Игоревич
Управление информационными потоками в ad hoc сетях на основе адаптивного алгоритма Q-routing2020 год, кандидат наук Шилова Юлия Александровна
Использование нейронных механизмов искусственного интеллекта для кластеризации узлов и маршрутизации данных в беспроводных сенсорных сетях2015 год, кандидат наук Махров, Станислав Станиславович
Модели и алгоритмы обеспечения гарантированной доставки данных в самоорганизующихся беспроводных сенсорных сетях с ячеистой топологией2023 год, кандидат наук Миклуш Виктория Александровна
Разработка моделей и методов маршрутизации в энергоэффективных ячеистых сетях дальнего радиуса действия2021 год, кандидат наук Фам Ван Дай
Список литературы диссертационного исследования кандидат наук Царев Александр Александрович, 2020 год
СПИСОК ЛИТЕРАТУРЫ
1. Barbosa-Filho, H. Human Mobility: Models and Applications / H. Barbosa-Filho, M. Barthelemy, G. Ghoshal, C. R. James, M. Lenormand, T. Louail, R. Menezes, J. J. Ramasco, F. Simini, M. Tomasini // Physics Reports. - 2018. - No. 734. - P. 1-74.
2. Bail Y. Optimizing sentinel surveillance in temporal network epidemiology / Y. Bail, B. Yang, L. Lin, J. L. Herrera, Z. Du, P. Holme // Scientific Reports. - 2017. -Vol. 7, No. 4804. - 10 p.
3. Sallah, K. Mathematical models for predicting human mobility in the context of infectious disease spread: introducing the impedance model / K. Sallah , R. Giorgi, L.Bengtsson, X. Lu, E. Wetter, P. Adrien, S. Rebaudet, R. Piarroux, J. Gaudart // International Journal of Health Geographics. - 2017. - Vol. 16, No. 1. - 11 p.
4. Vespignani, A. Modelling dynamical processes in complex socio-technical systems / A. Vespignani // Nature Physics. - 2012. - Vol. 8, No. 1. - P. 32-39.
5. Yan, X.-Y. Universal model of individual and population mobility on diverse spatial scales / X.-Y. Yan, W.-X. Wang, Z.-Y. Gao, Y.-C. Lai // Nature Communications. - 2017. - Vol. 8, No. 1639. - 9 p.
6. Liang, X. Unraveling the origin of exponential law in intra-urban human mobility / X. Liang, J. Zhao, L. Dong, K. Xu // Scientific Reports. - 2013. - Vol. 3, No. 2983. - 7 p.
7. Peng, C. Collective human mobility pattern from taxi trips in urban area / C. Peng, X. Jin, K.-C. Wong, M. Shi, P. Lio // PloS One. - 2012. - Vol. 7, No. 4. - 8 p.
8. Simini, F. A universal model for mobility and migration patterns / F. Simini, M. C. González, A. Maritan, A. L. Barabási // Nature. - 2012. - Vol. 484, No. 7392. -P. 96-100.
9. Jiang, S. Activity-based human mobility patterns inferred from mobile phone data: A case study of Singapore. / S. Jiang, J. Ferreira, M. C. González // IEEE Trans. Big Data. - 2017. - Vol. 3. - P. 208-219.
10. Schneider, C. M. Unravelling daily human mobility motifs / C. M. Schneider, V. Belik, T. Couronne, Z. Smoreda, M.C. Gonzalez// J R Soc Interface 10:20130246.
[Electronic resource], - 2013. — URL: http://dx.doi.org/10.1098/rsif.2013.0246 (дата обращения 23.02.2020).
11. Lee, M. Morphology of travel routes and the organization of cities / M. Lee, H. Barbosa, H. Youn, P. Holme, G. Ghoshal// Nature Communications. - 2017. - Vol. 8, No. 2229. - 46 p.
12. Leng, B. Evaluating the evolution of subway networks: Evidence from beijing subway network / B. Leng, X. Zhao, Z. Xiong // Europhysics Letters. - 2014. - Vol. 105, No. 5. - 6 p.
13. Barthelemy, M. The structure and dynamics of cities / M. Barthelemy // Cambridge University Press. - 2016. - 265 p.
14. Boyce, D. E. Forecasting Urban Travel: Past, Present and Future / D. E. Boyce, H. C. W. L. Williams // Edward Elgar Publishing. - 2015. - 672 p.
15. Wang, P. Understanding road usage patterns in urban areas / P. Wang, T. Hunter, A. M. Bayen, K. Schechtner, M. C. Gonzalez // Scientific reports. - 2012. -Vol. 2, No. 1001. - 6 p.
16. Bettstetter, C. Mobility modeling in wireless networks: Categorization, smooth movement, and border effects / C. Bettstetter // Mobile Comput. Commun. Rev. - 2001. - Vol. 5, No. 3. - P. 55-66.
17. Hong, S. Step: A spatio-temporal mobility model for humans walks / S. Hong, K. Lee, I. Rhee // IEEE 7th International Conference on Mobile Adhoc and Sensor Systems (MASS 2010), 8-12 November 2010, San Francisco, CA, USA. - 2010. - P. 630635.
18. Foroozani, A. A Novel Human Mobility Model for MANETs Based on Real Data / A. Foroozani, M. Gharib, A. Mohammad A. Hemmatyar // 23rd International Conference on Computer Communication and Networks (ICCCN). - 2014. - P. 1-7.
19. Gao, C. Modeling and restraining mobile virus propagation / C. Gao, J. Liu //IEEE Transactions on Mobile Computing. - 2013. - Vol. 12, No. 3. - P. 529-541.
20. Wang, P. Understanding the spreading patterns of mobile phone viruses / P. Wang, M. C. González, C. A. Hidalgo, A.-L. Barabási // Science. - 2009. - Vol. 324. -P. 1071-1076.
21. Holme, P. Temporal networks / P. Holme, J. Saramäki // Physics Reports. -2012. - Vol. 519, No. 3. - P. 97-125.
22. Song, C. Modelling the scaling properties of human mobility / C. Song, T. Koren, P. Wang, A.-L. Barabasi // NaturePhysics. - 2010. - Vol. 6, No. 10. - P. 818823.
23. Yan, X.-Y. Universal predictability of mobility patterns in cities / X.-Y. Yan, C. Zhao, Y. Fan, Z. Di, W.-X. Wang // Journal of the Royal Society Interface. - 2014. -Vol. 11. - 18 p.
24. Gonzalez, M.C. Understanding individual human mobility patterns / M.C. Gonzalez, C.A. Hidalgo, A.L. Barabasi // Nature. - 2008. - Vol. 453. - P. 779-782.
25. Lenczner, M. CRAWDAD dataset ilesansfil/wifidog (v. 2015-11-06) / M. Lenczner, A. G. Hoen// [Electronic resource]. - 2015. - URL: https://crawdad.org/ilesansfil/wifidog/20151106 (дата обращения 23.02.2020).
26. Madan, A. Sensing the "health state" of a community / A. Madan, M. Cebrian, S. Moturu, K. Farrahi, A. Pentland // Journal IEEE Pervasive Computing. - 2012. -Vol. 11, No. 4. - P. 36-45.
27. Karsai, M. Time-varying networks and the weakness of strong ties / M. Karsai, N. Perra, A. Vespignani // Scientific Reports. - 2014. - Vol. 4, No. 4001. - 7 p.
28. Krings, G. Effects of time window size and placement on the structure of an aggregated communication network / G. Krings, M. Karsai, S. Bernhardsson, V. D. Blondel, J. Saramäki // EPJ Data Science. - 2012. - Vol. 1, No. 4. - 19 p.
29. Karsai, M. Small but slow world: How network topology andburstiness slow down spreading / M. Karsai, M. Kivelä, R. K. Pan, K. Kaski, J. Kertesz, A-L Barabasi, J. Saramäki // Physical Review E. - 2011. - Vol. 83, No. 02510. - 4 p.
30. Liang, B. Predictive Distance-Based Mobility Management for Multidimensional PCS Networks / B. Liang, Z. J. Haas // IEEE/ACM trans. on networking. - 2003.
- Vol. 11, No. 5. - P. 718-732.
31. Rhee, I. On the Levy-Walk Nature of Human Mobility / I. Rhee, M. Shin, S. Hong, K. Lee, S. J. Kim, S. Chong // IEEE/ACM Transactions On Networking. - 2011.
- Vol. 19, No. 3. - P. 630-643.
32. Lee, K. SLAW: Self-Similar Least-Action Human Walk / K. Lee, S. Hong, S. J. Kim, I. Rhee, S. Chong // IEEE/ACM Transactions On Networking. - 2012. -Vol. 20, No. 2. - P. 515-529.
33. Lim, S. Clustered mobility model for scale-free wireless networks / S. Lim, C. Yu, C. R. Das // Proc. IEEELCN 2006, Tampa, FL, Nov. - 2006. - P. 231-238.
34. Karamshuk, D. Human mobility models for opportunistic networks / D. Karamshuk, C. Boldrini, M. Conti, A. Passarella // Communications Magazine, IEEE. -2011. - Vol. 49, No. 12. - P. 157-165.
35. Foroozani, A. A novel human mobility model for MANETs based on real data / A. Foroozani, M. Gharib, A. Mohammad A. Hemmatyar, A. Movaghar // 23rd International Conference on Computer Communication and Networks, IEEE. - 2014. - P. 1-7.
36. Kim, M. Extracting a mobility model from real user traces / M. Kim, D. Kotz, S. Kim // Proceedings IEEE INFOCOM 2006. 25TH IEEE International Conference on Computer Communications. - 2006. - P. 1-13.
37. Brockmann, D. The scaling laws of human travel / D. Brockmann, L. Hufnagel, T. Geisel // Nature. - 2006. - Vol. 439. - P. 462-465.
38. Zhao, M. Design and applications of a smooth mobility model for mobile ad hoc networks / M. Zhao, W. Wang // Military Communications Conference, IEEE. -2006. - P. 1-7.
39. Viswanathan, G. M. Levy flights search patterns of wandering albatrosses / G. M. Viswanathan, V. Afanasyev, S. V. Buldyrev, E. J. Murphy, P. A. Prince, H. E. Stanley // Nature. - 1996. - Vol. 381. - P 413-415.
40. Ramos-Fernandez, G. Levy walk patterns in the foraging movements of spider monkeys / G. Ramos-Fernandez, J. L. Mateos, O. Miramontes, G. Cocho, H. Larralde, B. Ayala-Orozco // Behav. Ecol. Sociobiol. - 2004. - Vol. 55, No. 3. - P. 223-230.
41. Viswanathan, G. M. Optimizing the success of random searches / G. M. Viswanathan, S. V. Buldyrev, S. Havlin, M. G. E. da Luz, E. P. Raposo, H. E. Stanley, // Nature, Oct. - 1999. - Vol. 401. - P. 911-914.
42. Edwards, A. M. Revisiting Levy flight search patterns of wandering albatrosses, bumblebees and deer / A. M. Edwards, R. A. Phillips, N. W. Watkins, M. P. Free-
man, E. J. Murphy, V. Afanasyev, S. V. Buldyrev, M. G. E. da Luz, E. P. Raposo, H. E. Stanley, G. M. Viswanathan // Nature, Oct. - 2007. - Vol. 449. - P. 1044-1048.
43. Groenevelt, R. B. Relaying in mobile ad hoc networks: The Brownian motion mobility model / R. B. Groenevelt, E. Altman, P. Nain // Wireless Networks. - 2006. -Vol. 12, No. 5. - P. 561-571.
44. Bettstetter, C. The node distribution of the random waypoint mobility model for wireless ad hoc networks / C. Bettstetter, G. Resta, P. Santi // IEEE Trans. Mobile Comput. - 2003. - Vol. 2, No. 3. - P. 257-269.
45. Johnson, D. Dynamic source routing in ad hoc wireless networks / D. Johnson, D. Maltz // Mobile Computing. The Kluwer International Series in Engineering and Computer Science, Springer, Boston, MA. - 1996. - Vol. 353. - P. 153-181.
46. Camp, T. A survey of mobility models for ad hoc network research / T. Camp, J. Boleng, V. Davies // Wireless Commun. Mobile Comput. - 2002. - Vol. 2, No. 5. -P. 483-502.
47. Einstein, A. On the motion, required by the molecular-kinetic theory of heat, of particles suspended in a fluid at rest / Ann. Phys. - 1905. - Vol. 17. - P. 549-560.
48. Shlesinger, M. F. Random walks with infinite spatial and temporal moments / M. F. Shlesinger, J. Klafter, Y. M. Wong // J. Stat. Phys. - 1982. - Vol. 27, No. 3. -P. 499-512.
49. Tolety, V. Load reduction in ad hoc networks using mobile servers / V. Tolety // Master's Thesis, Colorado School of Mines, Golden, CO, USA. - 1999. - 46 p.
50. Jardosh, A. Towards realistic mobility models for mobile ad hoc networks / A. Jardosh, E. M. Belding-Royer, K. C. Almeroth, S. Suri // in Proceedings of the 9th Annual International Conference on Mobile Computing and Networking, New York, USA. - 2003. - P. 217-229.
51. Bai, F. Important: a framework to systematically analyze the impact of mobility on performance of routing protocols for adhoc networks / F. Bai, N. Sadagopan, A. Helmy // in INFOCOM 2003. Twenty-Second Annual Joint Conference of the IEEE Computer and Communications. - 2003. - Vol. 2. - P. 825-835.
52. Hong, X. A group mobility model for ad hoc wireless networks / X. Hong, M. Gerla, G. Pei, C. chuan Chiang // MSWiM '99 Proceedings of the 2nd ACM international workshop on Modeling, analysis and simulation of wireless and mobile systems.
- 1999. - P. 53-60.
53. Hsu, W.-J. Modeling spatial and temporal dependencies of user mobility in wireless mobile networks / W.-J. Hsu, T. Spyropoulos, K. Psounis, A. Helmy // IEEE/ACM Trans. Networking. - 2009. - Vol. 17, No. 5. - P. 1564-1577.
54. Lim, S. A realistic mobility model for wireless networks of scale-free node connectivity / S. Lim, C. Yu, C. R. Das // International Journal of Mobile Communications. - 2010. - Vol. 8, No. 3. - P. 351-369.
55. Beran, J. Long-range dependence in variable-bit-rate video traffic / J. Beran, R. Sherman, M. Taqqu, W. Willinger // IEEE Transactions on Communications. - 1995. -Vol. 43, No. 234. - P. 1566-1579.
56. Taqqu, M. S. Estimators for long range dependence: An empirical study / M. S. Taqqu, V. Teverovsky, W. Willinger // Fractals. - 1995. - Vol. 3, No. 4 - P. 785-798.
57. Rhee, I. On the Levy walk nature of human mobility / I. Rhee, M. Shin, S. Hong, K. Lee, S. Chong // Proc. IEEE INFOCOM (Phoenix, AZ, Apr.). - 2008. -P. 924-932.
58. Shlesinger, M. F. Levy dynamics of enhanced diffusion: Application to turbulence / M. F. Shlesinger, G. M. Zaslavsky, J. Klafter // ys. Rev. Lett. - 1987. - Vol. 58. -P. 1100-1103.
59. Shlesinger, M. F. Strange kinetics / M. F. Shlesinger, B. J. West, J. Klafter // Nature. - 1993. - Vol. 363. - P 31-37.
60. Lee, K. Demystifying Levy Walk Patterns in Human Walks / K. Lee, S. Hong, S. J. Kim, I. Rhee, S. Chong // In: Technical Report, CSC, NCSU. [Electronic resource].
- 2008. - URL: https://www.csc.ncsu.edu/research/tech/reports.php (дата обращения 23.02.2020).
61. Lee, K. SLAW: A New Mobility Model for Human Walks / K. Lee, S. Hong, S. J. Kim, I. Rhee, S. Chong // Proceedings of IEEE INFOCOM 2009, April. - 2009. -P. 855-863.
62. Kang, J.H. Extracting Places from Traces of Locations / J. H. Kang, W. Wel-bourne, B. Steward, G. Borriello // Mobile Computing and Communications Review. -2005. - Vol. 9, Num.3. - P. 58-68.
63. Kim, M. Periodic properties of user mobility and access-point popularity / M. Kim, D. Kotz // Pers. Ubiquitous Comput. - 2007. - Vol. 11, No. 6. - P. 465-479.
64. Ekman, F. Working day movement model / F. Ekman, A. Keränen, J. Karvo, J. Ott // Proc. 1st ACM SIGMOBILE Workshop Mobility Models. - 2008. - P. 33-40.
65. Schneider, C. M. Daily travel behavior: lessons from a week-long survey for the extraction of human mobility motifs related information / C. M. Schneider, C. Rud-loff, D. Bauer, M. C. González // Proceeding of UrbComp'13, 2nd ACM SIGKDD International Workshop on Urban Computing, Chicago, Illinois, August 11. ISBN: 978-14503-2331-4. [Electronic resource]. - 2013. - No 3. - URL: https://dl.acm.org/citation.cfm?doid=2505821.2505829 (дата обращения 23.02.2020).
66. Chen, K. DTN-FLOW: Inter-Landmark Data Flow for High-Throughput Routing in DTNs / K. Chen, H. Shen // IEEE/ACM Transactions on Networking, February. -2015. - Vol. 23, No. 1 - P. 212-226.
67. Liu, C. Practical Routing in a Cyclic MobiSpace / C. Liu, J. Wu // IEEE/ACM Transactions on Networking, April. - 2011. - Vol. 19, No. 2. - P 369-382.
68. Kotz, D. CRAWDAD: A community resource for archiving wireless data at-Dartmouth / D. Kotz // Dartmouth College, Hanover, NH. [Electronic resource]. - 2018. - URL: http://www.crawdad.org/index.html (дата обращения 23.02.2020).
69. Rhee, I. CRAWDAD dataset ncsu/mobilitymodels (v. 2009-07-23) / I. Rhee, M. Shin, S. Hong, K. Lee, S. Kim, S. Chong // Community Resource for Archiving Wireless Data at Dartmouth. [Electronic resource]. - 2009. - URL: https://www.crawdad.org/ncsu/mobilitymodels/20090723/ (дата обращения 23.02.2020).
70. Musolesi, М. CRAWDAD dataset dartmouth/cenceme (v. 2008-08-13) / M. Musolesi, K. Fodor, M. Piraccini, A. Corradi, A, Campbell // [Electronic resource]. -2008. - URL: https://crawdad.org/dartmouth/cenceme/20080813/ (дата обращения 23.02.2020).
71. Campbell, A. T. Smartphone Sensing Group / Andrew T. Campbell, Hong Lua, Mu Lin, Ye Xu, Giuseppe Cardone // [Electronic resource]. - 2008 - URL: http://sensorlab.cs.dartmouth.edu/ (дата обращения 23.02.2020).
72*. Privalov, A. Yu. Hybrid Model of Human Mobility for DTN Network Simulation / A. Yu. Privalov, A. A. Tsarev // Proceedings of 30th European Conference on Modelling and Simulation (ECMS2016), OTH, Regensburg. - 2016. - P. 419-424.
73*. Царев, А. А. Сравнение характеристик протоколов маршрутизации в беспроводных DTN сетях для гибридной модели подвижности узлов / А.А. Царев, А.Ю. Привалов // Информационные технологии и нанотехнологии (ИТНТ-2017): материалы III Международной конференции и молодежной школы. Самара. -2017. - С. 1401-1405.
74*. Tsarev, A. A. Characteristics comparison of DTN networks routing protocols using hybrid model of nodes' mobility / A. Yu. Privalov, A. A. Tsarev // In Proceedings of the Mathematical Modeling Session at the International Conference Information Technology and Nanotechnology (MM-ITNT 2017), Samara National Research University, Samara, Russia, 24-27 April. - 2017. - P. 187-190.
75*. Царев, А. А. Шаблон передвижения узлов DTN сети на основе распределения Леви / А. А. Царев, А. Ю. Привалов. // Перспективные информационные технологии (ПИТ 2015), труды Международной научно-технической конференции / под ред. С.А. Прохорова. - Самара: Издательство Самарского научного центра РАН. - 2015. - Том 2. - С. 30-34.
76*. Царев, А. А. Шаблон передвижения узлов DTN сети на основе распределения Леви / А. А. Царев, А. Ю. Привалов // Известия Самарского научного центра Российской академии наук. - 2015. - Т. 17, № 2(5). - С. 1082-1086.
77*. Царев, А. А. Моделирование передвижений узлов DTN сети с использованием принципа наименьшего действия при выборе локаций посещения / А. А. Царев, А. Ю. Привалов // Информационные технологии и нанотехнологии (ИТНТ-2015): материалы I Международной конференции и молодежной школы. -Самара: Издательство Самарского научного центра РАН. - 2015. - С. 254-259.
78*. Tsarev, A. A. Simulation of DTN Nodes' Mobility Using Least Action Principle for Locations Selection / A. Yu. Privalov, A. A. Tsarev // Proceedings of International Conference Information Technology and Nanotechnology(ITNT-2015), Samara, Russia, June 29 - July 1, 2015, CEUR-Workshop web site in a series with ISSN 16130073. - 2015. - Vol. 1490. - C. 219-226.
79. Varga, A. An overview of the OMNeT++ simulation environment / A. Varga, R. Hornig // Proceeding of Simutools'08, The 1st international conference on Simulation tools and techniques for communications, networks and systems, Marseille, France, March. - 2008. - No. 60. - P. 1-10.
80. Till, S. An extension of the OMNeT++ INET framework for simulating realtime ethernet with high accuracy / S. Till, H. D. Kenfack, F. Korf, Th. C. Schmidt // Proceedings of the 4th International ICST Conference on Simulation Tools and Techniques - ICST. Brussel. Belgium. - 2011. - P. 375-382.
81*. Царев, А. А. Совместное использование гибридной модели и модели типа SLAW для моделирования человеческой подвижности / А. А. Царев, А. Ю. Привалов // труды Перспективные информационные технологии (ПИТ 2018) [Электронный ресурс]: труды Международной научно-технической конференции / под ред. С.А. Прохорова. - Самара: Издательство Самарского научного центра РАН. - 2018. - С. 1147-1151.
82*. Царев, А. А. Модель человеческой подвижности для имитационного моделирования беспроводных толерантных к задержкам сетей / А. А. Царев, А. Ю. Привалов // Периодический научно-технический и информационно-аналитический журнал «Инфокоммуникационные технологии». - 2018. - Т. 16, № 3. - С. 298-303.
83*. Царев, А. А. Исследование протоколов маршрутизации в DTN сетях с гибридной моделью подвижности узлов / А. А. Царев, А. Ю. Привалов // Перспективные информационные технологии (ПИТ 2017): труды III Международной научно-технической конференции / под ред. С.А. Прохорова. - Самара: Издательство Самарского научного центра РАН. - 2017. - C. 1026-1030.
84*. Царев, А. А. Исследование влияния характеристик перемещения узлов DTN сети с гибридной моделью мобильности / А. А. Царев, А. Ю. Привалов // Информационные технологии и нанотехнологии (ИТНТ-2018): материалы IV Международной конференции и молодежной школы. Россия, Самара, 24-27 апреля. - 2018. - С. 1433-1441.
85. Jaccard, P. Distribution de la flore alpine dans le Bassin des Dranses et dans quelques regions voisines / P. Jaccard // Bulletin de la Société Vaudoise des Sciences Naturelles. - 1901. - Vol. 140, No 37. - P. 241-272.
86*. Tsarev, A.A. Analysis and simulation of WAN traffic by self-similar traffic model with OMNeT / A. A. Tsarev, A. Yu. Privalov // Proceedings of the 10th International Wireless Communications and Mobile Computing Conference (IWCMC'14). Cyprus, Nicosia, August 4-8. - 2014. - P. 629-634.
87*. Царев, А.А. Модель трафика современных глобальных сетей для системы имитационного моделирования / А. А. Царев, А. Ю. Привалов // Периодический научно-технический и информационно-аналитический журнал «Инфоком-муникационные технологии». - 2015. - Т. 13, № 1. - С. 40-44.
88. Weingartner, E. A performance comparison of recent network simulators / E. Weingartner, H. Lehn, K. Wehrle // Proceedings of IEEE International Conference, ICC '09, Dresden, Germany. - 2009. - P. 1287-1291.
89. С/С++. Программирование на языке высокого уровня / Т.А. Павловская [Текст] // - СПб.: Лидер, 2010. - 461 с.
90. Varga, A. OMNeT++ User Manual. Version 4.6 / A. Varga [Text] // OpenSim Ltd. - 2011. - 420 p.
91. Drytkiewicz, W. A Mobility Framework for OMNeT++ / W. Drytkiewicz, S. Sroka, V. Handziski, A. Köpke, H. Karl // Telecommunication Networks Group, Technische Universität Berlin, January 22. [Electronic resource]. - 2003. - URL: http://www.tkn.tu-berlin.de/fileadmin/fg112/Papers/mobility framework.pdf (дата обращения 23.02.2020).
92. Marsaglia, G. Fast Generation of Discrete Random Variables / G. Marsaglia, W. W. Tsang, J. Wang // Journal of Statistical Software. July. - 2004. - Vol. 11, Iss. 3. - P. 1-11.
93. Fall, K. Delay-Tolerant Network Architecture for Challenged Internets / K. Fall // SIGCOMM, August. - 2003. - P. 27-34.
94. Raj, V. S. DELAY - Disruption Tolerant Network (DTN), its Network Characteristics and Core Applications / V. S. Raj, R. M. Chezian // IJCSMC. - 2013. - Vol. 2, Iss. 9. - P. 256-262.
95. Zhang, P. Hardware Design Experiences in ZebraNet / P. Zhang, C. M. Sadler, S. A. Lyon, M. Martonosi // In Proc. ACM SenSys, Nov. - 2004. - P. 227-238.
96. Partan, J. A Survey of Practical Issues in Underwater Networks / J. Partan, J. Kurose, B. N. Levine // In Proc. ACM WUWNet, Sept. - 2006. - P. 17-24.
97. Gu, Y. Data forwarding in extremely low duty-cycle sensor networks with unreliable communication links / Y. Gu, T. He // in Proc. ACM SenSys. - 2007. - P. 321334.
98. Pérez-Torres, R. Power management techniques in smartphone-based mobility sensing systems: A survey / R. Pérez-Torres, C. Torres-Huitzil, H. Galeana-Zapién // Pervasive and Mobile Computing. - 2016. - Vol. 31. - P. 1-21.
99. Wong, K.-S. Current State of Multicast Routing Protocols for Disruption Tolerant Networks: Survey and Open Issues / K.-S. Wong, T.-C. Wan // Electronics. -2019. - Vol. 8, No. 2. - P. 1-28.
100. Rao, B. B Impact of Mobility on Routing Protocols in MANET using NS2 / B. B. Rao, SK. M. Sharief, K. G. Rao // International Journal of Scientific Research in Computer Science, Engineering and Information Technology. - 2018. - Vol. 3, Iss. 5. -P. 120 - 131.
101. Patel, P. M. A Survey: An Energy Efficient Routing Protocol in Delay Tolerant Networks (DTN) / P. M. Patel, M. H. Mehta // International Journal of Advance Research and Innovative Ideas in Education. - 2016. - Vol. 2, Iss. 6. - P. 809-812.
102. Oliveira, J. The DTN Routing Problem: Exploitation versus Exploration of Solutions / J. de Oliveira, A. C. B. K. Vendramin, A. Munaretto, M. Delgado // 2015 IEEE 81st Vehicular Technology Conference (VTC Spring), Glasgow. - 2015. - P. 1-6.
103. Massri, K. Routing Protocols for Delay Tolerant Networks: A Reference Architecture and a Thorough Quantitative Evaluation / K. Massri, A. Vitaletti, A. Vernata, I. Chatzigiannakis // Journal of Sensor and Actuator Networks. - 2016. - Vol. 5, No. 2. - P. 1-6.
104. Perkins, C. Ad hoc on-demand distance vector routing / C. Perkins, E. Royer // Proceedings. WMCSA '99. Second IEEE Workshop on, New Orleans, LA. - 1999. -P. 90-100.
105. Clausen, T. Optimized Link State Routing Protocol (OLSR) / T. Clausen, P. Jacquet // Project Hipercom, INRIA. October. - 2003. - URL: https://tools.ietf.org/html/rfc3626 (дата обращения 23.02.2020).
106. Burgess, J. MaxProp: Routing for vehicle-based disruption-tolerant networks / J. Burgess, B. Gallagher, D. Jensen, B. N. Levine // Proceedings IEEE INFOCOM 2006. 25TH IEEE International Conference on Computer Communications, Barcelona, Spain. - 2006. - P. 1-11.
107. Juang, P. Energy-efficient computing for wildlife tracking: design tradeoffs and early experiences with ZebraNet / P. Juang, H. Oki, Y. Wang, M. Martonosi, L. S. Peh, D. Rubenstein // SIGOPS Oper. Syst. Rev. - 2002. - Vol. 36, No. 5. - P. 96-107.
108. Chaintreau, A. Impact of human mobility on opportunistic forwarding algorithms / A. Chaintreau, P. Hui, J. Crowcroft, C. Diot, R. Gass, J. Scott // IEEE Transactions on Mobile Computing. - 2007. - Vol. 6, No. 6. - P. 606-620.
109. Amin, V. Epidemic routing for partially connected ad hoc networks / V. Amin, B. David // Technical Report CS-2000-06, Duke University. - 2000. - P. 1-14.
110. Filho, J.G. A systematic technical survey of DTN and VDTN routing protocols / J.G. Filho, A. Patel, B. L. Alcantara Batista, J. Celestino Jr. // Computer Standards & Interfaces. - 2016. - Vol. 48. - P. 139-159.
111. Davis, J. A. Wearable computers as packet transport mechanisms in highly-partitioned ad-hoc networks / J. A. Davis, A. H. Fagg, B. N. Levine // Proceedings Fifth International Symposium on Wearable Computers, Zurich. - 2001. - P. 141-148.
112. Burns, B. MV Routing and Capacity Building in Disruption Tolerant Networks / B. Burns, O. Brock, B. N. Levine // In Proc. IEEE Infocom, March. - 2005. -P. 398-408.
113. Lindgren, A. Probabilistic Routing in Intermittently Connected Networks / A. Lindgren, A. Doria, O. Schel'en // In Proc. SAPIR Workshop, Aug. - 2004. - P. 239254.
114. Small, T. Resource and Performance Tradeoffs in Delay-Tolerant Wireless Networks / T. Small, Z. Haas // In Proc. ACM WDTN, Aug. - 2005. - P. 260-267.
115. Tseng, Y.-C. The Broadcast Storm Problem in a Mobile Ad hoc Network / Y.-C. Tseng, S.-Y. Ni, Y.-S. Chen, J.-P. Sheu // Springer Wireless Networks. - 2002. -Vol. 8, No. 2/3. - P. 153-167.
116. Widmer, J. Network Coding for Efficient Communication in Extreme Networks / J. Widmer, J.-Y. Le Boudec // In Proc. ACM WDTN, Aug. - 2005. - P. 284291.
117. Jain, S. Using Redundancy to Cope with Failures in a Delay Tolerant Network / S. Jain, M. Demmer, R. Patra, K. Fall // In Proc. ACM Sigcomm. - 2005. -P. 109-120.
118. Spyropoulos, T. Spray and Wait: An Efficient Routing Scheme for Intermittently Connected Mobile Networks. / T. Spyropoulos, K. Psounis, C. S. Raghavendra // In Proc. ACM WDTN, Aug. - 2005. - P. 252-259.
119. Jain, S. Routing in a Delay Tolerant Network / S. Jain, K. Fall, R. Patra // In Proc. ACM Sigcomm, Aug. - 2004. - P. 145-158.
120. Jones, E. Practical Routing in Delay-Tolerant Networks / E. Jones, L. Li, P. Ward // In Proc. ACM Chants Workshop, Aug.- 2005. - P. 237-243.
121. Spyropoulos, T. Single-copy routing in intermittently connected mobile networks / T. Spyropoulos, K. Psounis, C. S. Raghavendra // First Annual IEEE Communi-
cations Society Conference on Sensor and Ad Hoc Communications and Networks. -2004. - P. 235-244.
122. Lindgren, A. Probabilistic Routing Protocol for Intermittently Connected Networks / A. Lindgren, A. Doria, E. Davies, S. Grasic // Lulea University of Technology [Electronic resource]. - 2012. - URL: https://tools.ietf.org/html/rfc6693 (дата обращения 23.02.2020).
123. Dubois-Ferriere, H. Age matters: Efficient route discovery in mobile ad hoc networks using encounter ages / H. Dubois-Ferriere, M. Grossglauser, M. Vetterli // In Proc. ACMMobiHoc, Annapolis, MD, Jun. - 2003. - P. 257-266.
124*. Свидетельство о государственной регистрации программы для ЭВМ № 2018665241. Программный комплекс для моделирования протоколов маршрутизации в мобильных сетях, толерантных к задержкам, с использованием различных моделей мобильности / А. Ю. Привалов, А. А. Царев; опубл. 03.12.2018. - 1 с.
125*. Царев, А. А. Влияние моделей подвижности узлов на характеристики DTN сетей / А. А. Царев, Привалов А. Ю. // Перспективные информационные технологии (ПИТ 2016): труды Международной научно-технической конференции / под ред. С.А. Прохорова. - Самара: Издательство, Самарского научного центра РАН. - 2016. - С. 922-925.
126*. Царев, А. А. Сравнение адекватности моделей подвижности путём моделирования протоколов маршрутизации / А. А. Царев, А. Ю. Привалов // Информационные технологии и нанотехнологии (ИТНТ-2016): материалы II Международной конференции и молодежной школы. - Самара. - 2016. - С. 729-735.
ПРИЛОЖЕНИЕ А. ОПИСАНИЕ ПРОГРАММЫ ИМИТАЦИОННОГО
МОДЕЛИРОВАНИЯ
В разделе 4.3 были описано основные важные части имитационной программы по моделированию сети. Приведём теперь описание некоторых компонент программы на базе OMNeT++ более детально.
RealMobility - данный модуль предназначен для воспроизведение перемещений людей по записям из файла с расширением *.txt. На вход ему подаются файлы с трассами. Описание формата файлов с записями перемещений людей приводилось в разделе 1.4.
RegularRealMobility - данный модуль воспроизводит перемещения людей в течение нескольких дней. Так как у нас имеются только данные пользователей за один день (для набора данных ncsu/mobilitymodels [68]), то для того, чтобы иметь возможность сравнивать характеристики DTN сети в случае работы за несколько дней на реальных данных, мы повторяем «проигрывание» перемещений людей несколько раз.
SelfSimLATP - данный модуль реализует модель мобильности SLAW. На вход модулю передаётся набор локаций, по которым будут перемещаться узлы, набор маршрутов для каждого узла (получаются с помощью утилиты RootFinder), параметры генератора Леви для длительности пауз ер,/ и два параметра и р2
для алгоритма LATP (1.10): для выбора локаций и путевых точек. Каждый такой маршрут состоит из набора локаций, в каждой из которых указано, сколько пользователь должен сделать путевых точек в ней. В данном модуле содержится подмодуль SelfSimMap, который разбрасывает заданное количество точек самоподобным образом в каждой локации в процессе работы модели мобильности. Порядок обхода путевых точек и локаций производится по алгоритму LATP (1.10) на основе матрицы дистанций между путевыми точками и на основе матрицы дистанций между центрами локаций.
RegularSelfSimLATP - данный модуль предназначен для моделирования перемещений по модели SLAW в течение нескольких дней. В течение одного дня работает модуль SelfSimLATP. Маршрут за узлом фиксируется один на все дни. Таким образом в новый день конкретный узел перемещается по тому же набору локаций и с теми же количествами точек в них, что и в предыдущий день, но отличается разброс точек внутри локаций и порядки обходов точек и локаций, т.к. все они производятся случайным образом.
LevyHotSpotsLATP - данный модуль реализует гибридную модель мобильности. На вход ему передаётся набор локаций, в которых пользователь будет перемещаться, параметры генератора Леви для прыжков ca,a и для длительности пауз cp,/3 , и параметр p для алгоритма LATP (1.10) для выбора локаций. В процессе работы модели, узел перемещается в локации, формируя кластер путевых точек. Детальное описание работы модели приведено в разделе 2.2.
RegularRootLATP - данная модель предназначена для моделирования перемещений в течение нескольких дней с помощью гибридной модели мобильности. Т.е. в течение дня работает модель LevyHotSpotsLATP, при наступлении нового дня формируется новый маршрут по алгоритму, описанному в разделе 3.1.
SimpleLevy - модуль, реализующий модель мобильности Леви. Входными данными для неё являются параметры генератора Леви для прыжков ca,a и для длительности пауз cp,/3, и размер исходной территории. В начале узел размещается на территории случайным образом (по равномерному распределению). Узлы перемещаются до конца текущего дня.
RegularSimpleLevy - модуль для реализации перемещений по модели Леви в течение нескольких дней. Каждый новый день узел начинает перемещение заново через модуль SimpleLevy.
Для всех модулей указывается количество узлов, длительность модельного дня и количество дней в эксперименте. Все модули умеют сохранять историю перемещений для дальнейшего анализа.
Также в имитационной программе есть другие компоненты, выполняющие служебные функции.
Messages - компонент с описанием сообщений, используемых в моделировании. В программе заведены следующие типы сообщений:
1. FOR_NEW_PACKET - сообщение для создании нового пакета;
2. NEW_PACKET_CREATED - сообщение о созданном новом пакете;
3. RESPONSE_FOR_REQUEST - сообщение о соединении;
4. PACKET - обозначение простого информационного пакета;
5. REQUEST_FOR_ROUTING - заявка на маршрутизацию;
6. PACKET_RECEIVED - сообщение о полученном пакете;
7. ICT_INFO - сообщение с информацией о ICT;
8. DAY_START - сообщение о начале нового «дня» моделирования;
9. MOBILITY_START - сообщение о начале моделирования перемещений;
10.ROUTE_ENDED - сообщение об окончании маршрута;
11.SET_TIMER - установка таймера обновления шансов контакта (для
протокола маршрутизации PROPHET).
В частности, каждое информационное сообщение (из пункта 4) содержит идентификатор узла источника, идентификатора узла назначения, идентификатор последнего транзитного узла, время создания, время получения адресатом, и информация об эвристике маршрутизации, по которой пакет передавался последний раз. Пакеты данного типа моделируют информационный трафик.
HotSpotsCollection - компонент, контролирующий набор локаций в процессе моделирования: загружает, ведёт учёт необходимых данных об общем количестве посещений локаций, и времени, проведённом в локациях и др. На вход данному модулю требуется передать путь с расположением файлов локаций (файлы с расширением *.hts) в файловой системе.
RootsCollection - компонент, контролирующий набор маршрутов (наборов локаций для узла) в процессе моделирования: загружает, ведёт учёт необходимых данных о генерируемых маршрутах и др. На вход данному модулю требуется пе-
редать путь с расположением файлов маршрутов (файлы с расширением *.го^ и путь для сохранения генерируемых маршрутов в файловой системе
Н181:огуСо11ес1:юп -компонент, собирающий статистику о пакетах системы (где и когда появился, каким узлам и когда передавался, и когда произошло уничтожение пакета), о количестве доставленных и недоставленных пакетах. о времени между контактами узлов (1СТ) и о длительности маршрутов (безотносительно к составу маршрута). На вход передаются имена файлов (файлы с расширением *.хт1), в которые будет сохранена данная статистика.
ТгасеБСоПесйоп - компонент, контролирующий набор входных трасс перемещений узлов. На вход данному модулю требуется передать путь с расположением файлов трасс (файлы с расширением *.Ш) в файловой системе. В основном используется моделью Яеа1МоЫШу для воспроизведения перемещений.
Коий^Неипвйс - компонент, реализующий простые протоколы маршрутизации пакета. Реализовано несколько простых протоколов, описанных в разделе 4.2.2.
31а1!811сСо11ес1:ог - модуль, предназначенный для обработки полученных хт1-файлов со статистикой от модуля Н181:огуСо11ес1:юп. В результате получается файл 81а11811с8.хт1 с собранными оценками распределения вероятностей для времени 1СТ, с оценкой вероятности доставки пакета, а также с гистограммой на основе длительностей перемещений узлов в течение дней.
Оепега1:юпКоо1881:га1е§у - модуль, реализующий алгоритм генерирования ежедневных маршрутов для модуля Ке§и1агЯоо1ЬАТР. На вход данному алгоритму передаются оценки распределений вероятностей из файла гоо18_рега81епсе_81а1181:ю8.р81 Данный файл формируется утилитой Регав!апсеСа1-сиЫог. Инициализация первых (эталонных) маршрутов пользователей: в текущей версии первый (он же эталонный) маршрут в виде набора локаций пользователя инициализируется на основании соответствующего файла *.го1 в наборе файлов из коллекции Traces\гootfi1es\ компонентом Яоо1вСо11ес11оп. Коэффициент перси-стентности для определённого набора маршрутов будем указывать в имени файла с маршрутом, и данный файл положим в папку Traces\гootfi1es\ для того, чтобы
модуль RootsCollection мог их прочитать как раньше. Только теперь коэффициент персистентности будем считывать из имени файла и, если его там нет, брать из конфигурации omnet.ini как коэффициент по умолчанию. Отметим, что коэффициент персистентности не может быть меньше нуля. Реализация в программе сбора и учёта статистики о ежедневных маршрутах: файл roots_persistence_statistics.pst, расположенный в корневой папке применяется ко всем узлам по умолчанию. Если для соответствующего узла в папке Trac-es/rootstatistics если свой файл статистики, то коэффициент персистентности и статистика берутся из него. Чтение файлов типа *.rot в котором лежит средний маршрут для пользователя, и в названии которого есть коэффициент персистент-ности, остаётся существовать для обратной совместимости в случае генерирования маршрутов чисто по коэффициенту персистентности.
SelfSimMap - модуль, реализующий алгоритм разбрасывания точек самоподобным образом на территории (как описано в разделе 1.2.2). На вход ему передаётся территория, число точек для данной территории, набор дисперсий. Данный набор дисперсий вычисляется утилитой SelfSimCalculator на основе известных путевых точек, т.е. либо на основе реальных путевых точек, либо на основе путевых точек от гибридной модели мобильности (подробнее в разделе 2.3).
LevyStatic - модуль, реализующий генератор случайных чисел Леви. Используется при работе модулей SelfSimLATP, LevyHotSpotsLATP, SimpleLevy.
FFT - реализация быстрого преобразования Фурье. Используется в генераторе LevyStatic, как описано в разделе 4.1.4.
DevelopmentHelper - компонент со вспомогательными функциями.
В составе имитационной программы также есть компоненты, которые реализованы не на базе OMNeT++, но предназначены для обработки первичных данных с целью получения нужных данных и параметров для запуска моделей мобильности. Кратко о них упоминалось в разделе 4.3. Теперь приведём описание более подробно.
WaypointFinder - проводит вычисление путевых точек пользователей на основе сырых данных (трасс) о перемещениях пользователей, как описано в разде-
ле 1.2.2. Для реализации данного алгоритма, используется структура данных -очередь. В очередь ставятся точки из исходного файла трассы перемещений пользователя. В момент постановки точки в очередь и в момент удаления из очереди автоматически подсчитывается сумма всех X координат стоящих в очереди точек, сумма всех Y координат (для дальнейшего расчёта средних значений координат), сумма времён проведённых во всех точках от головы очереди до предпоследней точки, а также принадлежность каждой стоящей в очереди точки кругу с центром в их средней арифметической всех координат и радиусом R (параметр алгоритма). Точки из файла ставятся в очередь, пока принадлежность кругу не перестанет выполняться. Как только это случилось, проверяется суммарное время стоящих в очереди точек (кроме последней). Если суммарное время больше T, то рассчитываются координаты путевой точки (как среднее значение их координат), время пребывания и количество точек трассы в путевой точке. Далее все точки кроме, кроме последней, удаляются из очереди. Если же время меньше T, то из очереди выбрасывается последняя добавленная точка и проверяется принадлежность кругу, а если принадлежность не выполняется, то выбрасываются последние точка, пока принадлежность кругу не начнёт снова выполняться. После этого возвращаемся к добавлению в очередь новых точек и алгоритм повторяется вновь.
Hotspot - производит вычисление кластеров путевых точек и формирует список локаций. Вычисление кластеров производится по алгоритму, описанному в разделе 1.2.2.
RootFinder - проводит вычисление маршрутов пользователей в виде последовательностей локаций, которые посещал пользователь в процессе перемещений. Маршруты сохраняются в файлы формата *.rot. Эти маршруты далее загружаются модулем RootsCollection и учитываются в моделях мобильности. На вход подаются набор всех локаций и путевые точки узлов.
RepeatCounter - считает количество посещений каждой локации. Вычисленные данные сохраняются в один файл spotcount.cnt для всех проанализированных локаций, переданных на вход утилите.
PersistanceCalculator - утилита, вычисляющая коэффициент персистентности для набора маршрутов, а также статистические данные на основе этих маршрутов. На вход данной утилите подаются наборы маршрутов узлов за несколько дней и на выходе получаем файл roots_persistence_statistics.pst. Подробнее об алгоритме и получаемых данных описано в разделе 3.1.
SelfSimCalculator - используется для вычисления набора дисперсий для каждого уровня разбиения входной территории с путевыми точками. Этот набор потом используется модулем SelfSimMap для распределения точек по территории во время моделирования по модели SLAW. Описание алгоритма приведено в разделе 1.2.2. На вход утилите передаются исходная территория и точки на ней.
DartmouthCencemeDatasetReader - используется для обработки входных данных перемещений пользователей в течении многих дней, что актуально для набора данных dartmouth/cenceme [70], описанного в разделе 1.4. Данная утилита «нарезает» трассу одного пользователя на части длительностью в один день, опираясь на отметки времени в записях (описание формата файла приведено в Приложении Б). Далее на основе этих данных проводилось вычисление коэффициента персистентности и статистических данных с помощью утилиты PersistanceCalcula-tor.
Описание модуля Visualizing
Файл common.sce содержит вспомогательные функции для отображения графиков и сбора файлов. Файл traces_waypoints_hotspots.sce содержит функции для отображения трасс и соответствующих путевых точек в различных комбинациях: отображение одной трассы, отображение нескольких трасс одновременно, отображение путевых точек для одной трассы и для нескольких трасс, а также отображение трассы и соответствующие путевые точки. Файл statistics.sce содержит функции для отображения графиков различных распределений вероятностей.
Для работы с процедурами нужно выполнить скрип common.sce и затем скрипт statistics.sce или traces_waypoints_hotspots.sce в среде SciLab.После чего процедуры станут доступными из командной строки.
Параметры, которые стоит переопределить в скрипте перед выполнением:
1. PATH - указывает путь рабочего каталога, т.е. все функции будут искать файлы или папки в этой директории;
2. SEPARATOR - разделитель для пути, принятый в той или иной операционной системе ('\' или '/');
3. GRAPH_COLOR - цвет первого графика в серии графиков (или, если график один, то параметр определяет его цвет);
4. COLOR_OFFSET - дробление цветового диапазона для окрашивания всех графиков в серии;
5. SHOW_LEGEND - параметр отображения легенды: 1 - показывать легенду, 0 - не показывать легенду.
После переопределения параметров и выполнения скрипта в SciLab можно вводить функции, например:
--> drawTraces('KAIST/KAIST_30sec_001.txt', 'KAIST/KAIST_30sec_002.txt');
--> drawTracesFolder('tracefiles');
--> drawWPFile('waypomtfiles/NewYork_30sec_037.txt.wpt'); --> drawWPFiles('waypointfiles/NewYork_30sec_037.txt.wpt', 'waypoint-files/NewYork_30sec_038.txt.wpt');
--> drawWPFilesFolder('waypomtfiles');
--> drawTraceAndWP('tracefiles/NewYork_30sec_037.txt', 'waypoint-files/NewYork_30sec_037.txt.wpt');
--> drawTraceAndWPFolder('Traces_TimeXY_30sec_txt/KAIST', 'Way-Point_TimeXY_3 0sec_txt/KAIST').
Таблица А.1 - Функции для визуализации графиков. Файлtraces_waypoints_hotspots.sce
Функция Описание
drawTrace(filename) Рисование трассы по имени файла
drawTraces(varargin) Рисование трасс, перечисленных в параметрах
данной функции (произвольное количество)
drawTracesFolder(folder) Рисование трасс, взятых из папки folder
drawWPFile(filename) Рисование путевых точек по имени файла
drawWPFiles(varargin) Рисование файлов с путевыми точками, перечисленных в параметрах данной функции (произвольное количество);
drawWPFilesFolder(folder) Рисование файлов путевых точек, взятых из папки folder
drawTraceAndWP(traceFilen ame, wpFilename) Рисование трассы и соответствующих путевых точек по именам файлов (рисование только одной пары);
drawTraceAndWPFolder(tra ceFolder, wpFolder) Рисование трасс и соответствующих им путевых точек из указанных папок (порядок файлов в этих папка должен совпадать);
drawWPTs(x, y, GRAPH_COLOR) Рисование вектора путевых точек с определённым цветом графика
drawWPTsFolder(folder) Рисование файлов путевых точек, взятых из папки folder
drawAllWPTFolders(folders) Рисование всех указанных папок с наборами путевых точек (входной вектор значений)
drawWPTFolders(varargin) Рисование всех указанных папок с наборами путевых точек (произвольное число параметров)
drawHS(folder) Рисование набора локаций из папки folder
drawHotSpot(filename, GRAPH_COLOR) Рисование локации из файла с заданным цветом графика
printCompareTableHtsRot(ht sFolder, realRtsFolder, genRtsFolder) Отображение таблицы для сравнения данных о локациях по маршрутам. На вход передаётся папка с локациями, реальные и сгенерирован-
140
ные маршруты
[rotFileNames, rotTableList] = getTableRots(rotFolder) Функция извлечения данных из маршрутов в таблицу со столбцами: [«File:», «Xmin:», «Xmax:», «Ymin:», «Ymax:», «T Sum:», «WP Count:»]
printCompareTableHts(varar gin) Отображение таблицы для сравнения данных о локациях. На вход передаётся список папок с локациями и строится таблица для сравнения
htsTable = getTableHts(folder) Функция извлечения данных из списка локаций в таблицу со столбцами: [«File:», «Length:», «Width:», «Square:», «T_Sum:», «WP_Count:»]
Таблица А.2 - Функции для визуализации графиков. Файл statistics.sce
Функция Описание
printPstFolder(folder) Функция отображения таблиц для статистики маршрутов *.pst
drawWPHistograms(varargin ) Рисование всех гистограмм из произвольного числа файлов статистики перемещений узлов (по путевым точкам)
drawNodeHistogramsFolder (folder) Рисование всех гистограмм из одного файла статистики маршрутизации, взятых из папки folder
drawNodeHistograms(vararg in) Рисование всех гистограмм из произвольного числа файлов статистики по маршрутизации
printNodeValuesFolder(folde r) Вывод в таблицу значений из файлов статистики маршрутизации, взятых из папки folder
printNodeValues(varargin) Вывод в таблицу значений из произвольного
числа файлов статистики по маршрутизации
dгawDX(fi1ename) Рисование зависимости дисперсий DX от масштаба
ёга,^о§Ьо§ВХ(Шепате) Рисование зависимости ^^Х) от ^(масштаба)
dгawDXtxt(vaгaгgin) Рисование зависимости DX от масштаба для произвольного числа наборов дисперсий
ПРИЛОЖЕНИЕ Б. ОПИСАНИЕ ФОРМАТА ФАЙЛОВ DARTMOUTH/CENCEME
Файлы данного набора называются «CenceMeLiteLogXX.txt», где XX - это номер узла. Размер файлов довольно велик (до 500 мегабайт), поэтому они сохранены в сжатые архивные файлы. Имена архивов сделаны по шаблону «CenceMeRawDataX.rar», где X - это номер архива, в котором находиться 4-5 файлов с исходных данными. В файлах есть как информационные строки (о конфигурации системы), так и строки с данными. Информационные строки записываются, когда система стартует. Данные строки различаются с помощью ключевых слов INFO или DATA. Есть единственное исключение, когда система стартует: сперва в файл записывается преамбула, которая состоит из трех строк, начинающихся с символа линии. Пример:
NEXT LOG
1217004653781 INFO (3) CenceMeLite: Configuration: 1217004653903 INFO (3) CenceMeLite: CONFIG: 0 * 2 * 1 * 1 * socket://127.0.0.1:8100 * 0 * 0 * 0 * builtin accel-erometer in N95
1217004653919 INFO (3) CenceMeLite: CONFIG: 1 * 501 * 2
* 1 * socket://127.0.0.1:8101 * 0 * 0 * 0 * Symbianbased sound
1217004653925 INFO (3) CenceMeLite: CONFIG: 2 * 3 * 1 * 1 * void * 180000 * 10000 * 0 * builtin GPS in N95
Строки данных различаются с помощью ключевых слов: ACC, ACT, GPS. Строка данных ACC содержит сырые данные акселерометра, и записаны в формате:
Timestamp DATA (0) ACC:
Xacc,Yacc,Zacc*Xacc,Yacc,Zacc*.........
где:
• Timestamp - момент времени, в который данные были записаны в файл;
• Xacc, Yacc, Zacc - данные акселерометра в трёх плоскостях соответственно. Каждая зафиксированная тройка этих значений отделятся друг от друга символом *.
Набор данных также содержит информацию о предполагаемых действиях в формате:
Timestamp DATA (0) ACT: AccSam-
plingStart,AccSamplingEnd,Fact где:
• Timestamp - момент времени, в который данные были записаны в файл;
• AccSamplingStart - момент времени, в который акселерометр начала фиксировать действие;
• AccSamplingEnd - момент времени, в который акселерометр закончил фиксировать действие;
• Fact - идентификатор предполагаемого действия.
Идентификаторы различных фактов следующие:
• Пользователь сидит: 0;
• Пользователь бежит: 1;
• Пользователь идёт: 2;
• Пользователь стоит: 5.
Поля AccSamplingStart и AccSamplingEnd - это время начала и окончания интервала соответственно, в течение которого данные от акселерометра используются для классификации активности в этом интервале.
Строчки с GPS данными может быть трудно обрабатывать, потому что там есть три возможных ситуации, когда GPS строка содержит:
• 0 зафиксированных отсчётов;
• N зафиксированных отсчётов;
• Строка «GPSSkipped: user sitting».
Последнее значение было введено для решения проблемы с питанием: когда пользователь сидит больше 15 минут, то датчик выключается. Эти строки можно заменить, используя последнее известное положение. Строки с GPS данными, со-
держащие координаты, могут содержать до N отсчётов о текущем местоположении. Формат:
Timestamp DATA (0) GPS: alti-
tude,latitude,longitude,hdop,speed*altitude, lati-
tude,longitude,hdop,speed* ..........
В этом случае каждый вектор данных также разделяется символом *.
Время начала эксперимента и длительность: поскольку телефоны были предоставлены пользователям в разное время, следуют использовать временные метки для определения точных временных интервалов.
Все временные метки и временные индикаторы указаны в формате времени языка программирования Java - это время, выраженное с 1970 года в миллисекундах.
ПРИЛОЖЕНИЕ В. РЕЗУЛЬТАТЫ АНАЛИЗА И МОДЕЛИРОВАНИЯ
ТРАСС НА ВСЕХ ТЕРРИТОРИЯХ
Территория (кампус университета)
Путевые точки
1 ООО -
О -
-1 ООО -
,_, -2 ООО -Е,
-3 ООО -
-4 000 -
-5 000 -
-6 000 -
-7 000 -
-8 000 --14
Реальные данные N0811
- - - -¡г
-в 000 X, [м]
Рисунок В.1 - Путевые точки реальных данных для территории КСБи
График изменения дисперсий (логарифмические оси)
1од2( ро\л/(1\1,1))
Рисунок В.2 - График дисперсий путевых точек в логарифмических осях координат для территории КСБи (за один день реальных данных)
ССОР для длины перемещений (логарифмические оси)
1од2( длина, [м])
Рисунок В.3 - Функции CCDF (1.11) для длины перемещений в логарифмических
осях координат для территории КСБи
ССОР для времени взаимодействия узлов (логарифмические оси)
1од2( время между контактами, [с])
Рисунок В.4 - Функции CCDF (1.11) для времени взаимодействия (1СТ) в логарифмических осях координат для территории NCSU
Таблица В.1 - Степень близости функций CCDF для NCSU
Набор данных A(Cr, Ст)
длины перемещений ICT
Реальные данные 0 0
SLAW на реальных данных 0,511 0,622
Гибридная модель 23,451 (| -4489% от SLAW на р.д.) 0,518 (i -16% от SLAW на р.д.)
SLAW на данных от гибридной модели 19,657 (| -3746% от SLAW на р.д.) (i -16% от гибридной) 0,517 (i -16% от SLAW на р.д.) (i -0.2% от гибридной)
График изменения дисперсий (логарифмические оси)
log2( pow(N.I))
Рисунок В.5 - Графики дисперсий путевых точек в логарифмических осях
координат для территории NCSU
Таблица В.2 - Дисперсии наборов точек территории КСБи (при длительности
экспериментов 12 дней)
Набор данных Уровень Параметр Херста Н
1 2 3 4 5 6 7 8 9
Реальные данные 2,7 4,5 14,8 54,0 131,4 459,8 1485,3 3616,1 7991,5 0,67
SLAW на реальных данных 2,7 4,8 13,6 45,1 109,0 310,2 607,9 1129,7 1817,5 0,72
Гибридная модель 2,2 4,8 9,9 24,9 64,6 192,9 438,1 643,2 922,8 0,74
SLAW на данных от гибридной модели 2,2 4,8 9,9 25,3 64,8 191,3 401,6 595,7 877,6 0,74
Размер прямоугольника на уровне (ширина и длина, м.) 7211,3 4750,1 3605,6 2375,0 1802,8 1187,5 901,4 593,8 450,7 296,9 225,4 148,4 112,7 74,2 56,3 37,1 28,2 18,6 —
3 000
2 000 1 000 о
-1 000 ^ -2 000 ^ -3 000 -4 000 -5 000 -6 000 -7 000 -8 000
-14 000 -12 000 -10 000 -8 000 -6 000 -4 000 -2 000 0 2 000
X, [М]
Путевые точки
■ ■ ■ Гибридная модель на реальных данных NCSU
' т
' ■ ■
I ■ Г
1, . _
4г J
Рисунок В.6 - Путевые точки гибридной модели для территории КСБи
3 000 2 000 1 ООО
о
-1 ООО „ -2 000 -3 000 -4 000 -5 000 -6 000 -7 000 -8 000
-14 000 -12 000 -10 000 -8 000 -6 000 -4 000 -2 000 0 2 000
X, [м]
Рисунок В.7 - Путевые точки модели SLAWдля территории NCSU
Таблица В.3 - Оценка вероятности доставки пакета Pr(delivery) для территории NCSU (при длительности экспериментов 12 дней) (в скобках -увеличение или уменьшение относительно PROPHET)
Набор данных Протокол
0,84 (Т -15%) 0,91 (Т -25%) 0,91 (Т -25%) 0,73
Реальные данные 0,6 (Т -13%) 0,71 (Т -34%) 0,71 (Т -34%) 0,53
SLAW на реальных данных 0,87 (Т -2%) 0,86 (Т -1%) 0,86 (Т -1%) 0,85
Гибридная модель 0,82 (Т -5%) 0,76 (I -3%) 0,76 (I -3%) 0,78
SLAW на данных от гибридной модели 0,84 (Т -15%) 0,91 (Т -25%) 0,91 (Т -25%) 0,73
Путевые точки
1 1 1 | | | ■ ■ ■ Модель SLAW на реальных данных NCSU
1 1 1 • 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 .*. 1 ------т ---- 1 -
1 1 1 1 1 1 1 1 1 1 ■ ' '
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 ' j •
-------Г------Т-------1------- 1 1 1 1 1 1 _______1______1 . J_____!_______ ------- -------
1 1 | 1 1 1 1 1 1 1 1 1 1
• 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 и • 1 1 1
1 1 1 1 1 1 1 1 1 —■—1—■—1—■—1—■— __ __ —■— __ __ —■— -■- -■-
Таблица В.4 - Оценка вероятности доставки пакета Predelivery) для территории NCSU (при длительности экспериментов 12 дней) с повтором ежедневных маршрутов (в скобках - увеличение или уменьшение относительно
PROPHET)
Набор данных Протокол
LET MFV LET-MFV PROPHET
Реальные данные 0,84 (Т -15%) 0,91 (Т -25%) 0,91 (Т -25%) 0,73
SLAW на реальных данных 0,57 (Т -18%) 0,66 (Т -37%) 0,66 (Т -37%) 0,48
Гибридная модель 0,85 (Т -6%) 0,89 (Т -11%) 0,89 (Т -11%) 0,8
SLAW на данных от гибридной модели 0,71 (Т -42%) 0,83 (Т -66%) 0,83 (Т -66%) 0,5
Территория Orlando (парк развлечений Disney World)
Путевые точки
8 000
6 000
4 000
2 000 -------tí----------
0 --
— -2 000
-4 000
-6 000
-8 000
10 000 --------1-------+---
-12 000
Реальные данные Orlando
-2 000
2 000
4 000
6 000
8 000
10 000
12 000
14 000
X, [М]
Рисунок В.8 - Путевые точки реальных данных для территории Orlando
График изменения дисперсий (логарифмические оси)
Обратите внимание, представленные выше научные тексты размещены для ознакомления и получены посредством распознавания оригинальных текстов диссертаций (OCR). В связи с чем, в них могут содержаться ошибки, связанные с несовершенством алгоритмов распознавания. В PDF файлах диссертаций и авторефератов, которые мы доставляем, подобных ошибок нет.