11 марта 2016г.
Аннотация.
КубГу, РФ, г.Краснодар
Ключевые слова: оппортунистическая сеть, графовая грамматика, поток сообщений, случайный граф, маршрутизация, длина пути, ad hoc сеть.
Рассматриваются динамические одноранговые сети, представленных в виде связных неориентированных графов. Основной задачей является исследование внутренних характеристик, определение зависимостей, влияющих на нагрузку и время выполнения внутренних процессов, таких сетей по сравнению с сетями с постоянной инфраструктурой.
PROBABILISTIC ANALYSIS OF FLOWS IN OPPORTUNISTIC NETWORKS MANAGED BY DYNAMICS OF GRAPH GRAMMARS
Mikov A.I., Nguyen N.D.
Keywords: opportunistic network, graph grammar, stream of messages, random graph, routing, path length Dynamic ad hoc networks are represented as connected undirected graph. The main objective is to study the
internal characteristics, determining dependencies that affect the load and the execution of internal processes, such networks in comparison with networks with permanent infrastructure.
В настоящее время особое место в изучении компьютерных сетей является исследование динамических беспроводных самоорганизующихся сетей ad hoc. Они являются гибким инструментом информационного обмена в тех ситуациях (местностях), когда отсутствует постоянная сетевая инфраструктура. Общей проблемой мобильных беспроводных сетей является возможная потеря связности графа сети [6] из-за исключения ребер графа, представляющих связи между соседними узлами сети. Это исключение происходит за счет того, что пара узлов уже не может обмениваться сообщениями, поскольку расстояние между ними превосходит критический порог. Вместе с тем другая пара перемещающихся узлов сети может оказаться на расстоянии, меньшем критического, что отражается в возникновении нового ребра в графе. Таким образом, граф сети является динамическим, изменяющимся. Возможной математической моделью такого графа является графовая грамматика [4], правила которой применяются к некоторому начальному графу. В результате образуется последовательность S графов Gi.
Как решить проблему передачи информации между двумя произвольными узлами v и u, если один из
графов Gi несвязен? Если в Gi отсутствует маршрут между v и u, то такая передача может быть отложена до тех пор, пока в последовательности графов S не появится граф Gk с требуемым маршрутом. Но такое решение не всегда приемлемо: ожидание может быть либо слишком большим, либо граф Gk не появится никогда.
Решением является создание оппортунистической сети. Маршрутизация в ней основывается не на отыскании маршрута между v и u в графе Gi , а на отыскании последовательности фрагментов маршрута (субмаршрутов) в последовательности графов S. Это решение предполагает, что сообщение проходит максимально возможный путь (в частном случае – весь путь) в текущем графе Gi , затем следующую часть пути в графе Gi+1 , следующую часть пути в графе Gi+2 и т.д. Оппортунистический алгоритм маршрутизации предполагает буферизацию сообщений в узлах и, возможно, рассылку копий сообщений для более эффективного поиска субмаршрутов.
В данном исследовании проводится сравнительный анализ вероятностных характеристик информационных потоков в ad hoc сетях с динамической инфраструктурой по сравнению с сетями со статической топологией.
Рассмотрим компьютерные ad hoc сети в виде математической модели. Основное представление, моделирование таких систем, а также принцип работы множества внутренних процессов внутри них описано в [1,2]. Известно, что при работе таких систем происходит обработка первичных и вторичных потоков сообщений, порождаемые «отправителями» и «получателями» соответственно. Главная проблема заключается в том, что эти потоки сообщений могут «потерять» своего «получателя» за счет изменений в инфраструктуре сети и за счет этого может увеличиться время их обработки.
Генерация графа, создание и обработка потоков сообщений происходит по [3]. Т. к. ранее рассматривались только сети со статичной топологией, то очевидно, что при симуляции каждое ребро должно иметь параметры: время существования ребра и время отсутствия ребра. Интервалы времени ti между событиями в потоке генерируемых узлом сообщений, а также появления и удаления ребра описываются функциями распределения вероятностей Ai(x), E(x) и F(x). При моделировании эти распределения считаются равномерными на некоторых интервалах от 0.1 до a,b,c,d соответственно. Следует отметить, что если в какой-либо момент времени ti,с ообщение, которое должно добраться до какой-либо вершины vi 𝜖 V, теряет путь до него, то это сообщение остается в текущем узле, ожидая появления пути до конечной точки. Причем это сообщение не мешает обработке и отправлению других сообщений, проходящих через текущий узел. Также не маловажным является параметр структуры сети Pv , который является вероятностью наличия ребра между двумя произвольными узлами при генерации реализации случайного графа.
Рассмотрим случай, когда a=b=c=d=Pv =0.4, т.е. все распределения являются равномерными на интервале от
1.1 до 0.4. При моделировании используем для анализа следующие характеристики:
1) Среднее время обработки сообщения в потоке Mx - средняя разность времени появления сообщения в системе и времени выхода этого сообщения из нее
2) Среднее время моделирования Mb – момент времени, когда последнее сообщение последнего потока было обработано
3) Среднее количество промежуточных узлов прошедших каждым сообщением потока Mg – количество узлов, которые нужно пройти для ее обработки системой
Все эти характеристики вычислялись более чем по 10 000 наборам реализации графа и каждый вновь генерируемый граф обрабатывает более 1000 сообщений в зависимости от количества узлов в системе. В первую очередь следует сравнить зависимость этих характеристик от изменения количества узлов |V| в динамической сети и в статической сети (Рисунок 1).
По графикам видно,
что имея 5 вершин
в системе характеристики обеих сетей практически равны друг другу, только после того, как сеть имеет более чем 10 вершинами, при параметрах a=b=c=d=0.4, обработка сообщений, время моделирования для динамических сетей становится
более трудоемким по времени,
нежели для статических сетей. Это обуславливается тем, что в связи с потерями
путей у сообщений, при удалении какого- либо ребра,
«теряя» узла получателя, им приходится находиться в очереди в узле до того момента, пока не появится новый
путь к узлу «получателю», или же пройти «обходной» путь, даже если он будет длиннее,
по рисунку, в 2 раза с точки зрения количества
узлов, проходимые этим сообщением. Также можно отметить, что чем больше масштаб сети, тем больше в ней сообщений
для обработки, что также влияет на временные
затраты, но по результатам [5] количество сообщений в сети пренебрежительно мало влияет на среднее время работы и обработки сообщений.
Можно заметить, что данные, полученные из динамической сети при |V| > 15 почти в 4.5 раза превышают данные статических сетей. Поскольку параметры
c, d определяют изменение
топологии сети с течением
времени, то
соответственно
нужно проанализировать, как будут вести себя характеристики при уменьшении и увеличении этих параметров, причем оставим a = b=Pv = 0,4, количество вершин также будет числом постоянным |V| = 25.
В данном случае нужно проанализировать поведение Mx, Mb
в зависимости от поведения параметров
c и
d. Здесь следует рассмотрение 2 варианта:
1) с = d. Среднее время видимости
vi ребра будет равно среднему времени
его отсутствия. Такой анализ имеет место быть, поскольку неизвестно, что произойдет с характеристическими данными,
ведь возрастание этих параметров по величине ведет
за собой увеличение обработки сообщений по времени
и вообще увеличивает время моделирования, за счет того, что некоторые сообщения могут «прождать» достаточное количество времени в зависимости от величины d. На Рисунке
2 видно, что изменения характеристик Mx, Mb незначительны по сравнению с объемом
обрабатываемых данных при изменении параметров c и d, при c = d.
2)
с >
d, с < d – рассмотрим
этот
случай, как изменение среднего времени отсутствия ребер
d, относительно постоянного среднего
времени видимости c = 0,4, при a = b = Pv = 0,4. Очевидно, что при c > d характеристики
Mx, Mb будут меньше при постоянном c, нежели при c < d, поскольку при увеличении параметра d увеличивается и время ожидания
появления соответствующего ребра. Это наглядно показано на Рисунок
3.
Также можно заметить, что при с > d характеристики изменяются в сторону уменьшения, это объясняется тем, что при таком параметре
c, потокам сообщений
хватает больше времени на обработку
нежели при с < d. И соответственно можно утверждать, что при
d c → 0 : Mx, Mb (динамической сети) →
Mx, Mb (статической сети).
Нельзя
также оставлять без
внимания параметр Pv , от которого
зависит не только нагруженность сети, но и инфраструктура самой сети. Заранее можно сказать, что
чем
больше величина Pv , тем
больше путей
для обработки потоков сообщений будет в системе, соответственно время обработки потоков,
а также симуляции будет меньше. Но неизвестно насколько изменятся эти данные в динамической сети по сравнению с данными статической системы. Рассмотрим Рисунок 4 для c = d = 0.4, поведение
Mx, Mb
и Mg
с изменением параметра Pv . Стоит заметить, то мы можем использовать c = d = 0.4, поскольку ранее доказано, что характеристики не меняются для всех наборов
c = d
Из графиков
видно, что все полученные характеристики Mx, Mb динамической сети больше статичной приблизительно в 3.5 раза, а Mg в 2
раза при |V| = 25. При
этом рассмотрев сети с количеством узлов равным 25 и опираясь на рис. 1 можно сделать вывод, что при увеличении количества вершин в системе разница
не будет превышать в 4.5 раза по характеристикам Mx, Mb, и в 2.5 раза для Mg.
Исходя из вышеизложенного, можно сделать
следующие выводы:
1) При постоянных параметрах a=b=c=d характеристики Mx, Mb, Mg динамической сети больше чем данные статичной сети не более чем в 4.5 раза
2) При изменении параметров c=d, при постоянных a=b изменений Mx, Mb, Mg не значительно, то есть пренебрежимо мало. То есть поведение
системы не изменяется при параметрах c=d.
3) Поведение системы и ее характеристик в зависимости от параметров c и d, можно выразить следующим образом: d c → 0 : Mx, Mb
(динамической сети) → Mx, Mb (статической сети).
4) Вне зависимости от того, какие значение принимают параметры
a,b,c,d,|V|, отношение
между характеристиками динамической сети и статичной, Mx, Mb
не превышает в 4.5 раза, а Mg
в
2.5 раза.
Работа была частично
поддержана грантом
РФФИ №14-01-00157.
Список литературы
1.
Замятина Е.Б., Миков А.И., Михеев Р.А. Особенности моделирования распределенных информационных систем. //Вестник Пермского университета. Серия: Математика. Механика.
Информатика. 2013, № 4, С. 107-118.
2.
Миков А.И., Храмцова А.В., Анализ характеристик случайных темпоральных графов мобильных ad hoc сетей. //Информатизация
и связь. 2015. № 2. С. 64-68.
3.
Миков А.И., Нгуен Н.З. Анализ маршрутизации ограниченных потоков сообщений
в случайных ad hoc сетях. //Известия ЮФУ. Технические науки, 2015,
№2 (163), С.61-70.
4.
Mikov A.I., Borisov A.
Connectivity control in ad hoc systems:
a graph grammar.
//Information models and analyses, 2013, Т. 2, № 1, С.
37-45.
5.
Миков А.И., Нгуен Н.З. Задача анализа ограниченных случайных
потоков сообщений с ответами в одноранговых сетях. //Информатизация и связь. 2015. № 1. С. 65-68.
6. Миков А.И. Связность автономных беспроводных компьютерных сетей в местностях
с плохой инфраструктурой. //Экологический вестник научных центров
Черноморского экономического сотрудничества, 2014, № 1, С. 70-75.
