Теория стохастических моделей.

Элементы теории случайных процессов

Случайный процесс (случайная функция времени)

Случайная функция –случайная величина, зависящая не только от случайного события ω, но и от какого-либо параметра. Если этот параметр – время, то случайная функция называется случайным процессом и обозначается ξ (t,ω).

Величина ξ может быть как скалярной (скалярный случайный процесс), так и векторной (векторный или многомерный случайный процесс). Она может принимать как дискретные значения (процесс с дискретными состояниями), так и пробегать непрерывный ряд значений.

В случае дискретного времени t = 0,1,2,... случайный процесс называют также случайной последовательностью

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

Ограничим функцию прямоугольником (n-мерным параллелепипедом в случае многих измерений), площадь которого S0 можно легко вычислить;

«набросаем» в этот прямоугольник (параллелепипед) некоторое количество точек (N штук), координаты которых будем выбирать случайным образом;

определим число точек (K штук), которые попадут под график функции;

площадь области, ограниченной функцией и осями координат, S даётся следующим выражением S = S0 K / N

Теория перколяций

Пусть есть прямоугольная решетка, состоящая из N*N свободных и занятых узлов.

Пусть вероятность того, что узел занят – p, и, соответственно, вероятность того, что узел свободен (1-p).

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

Образование стягивающего кластера называется перколяцией.

Идея метода Монте-Карло:

  1. Задать значение вероятности занятости узла p.
  1. Разыграть состояние каждого узла при заданном значении p, тем самым построив конкретную реализацию решетки.
  1. Определить, есть ли в этой реализации хотя бы один стягивающий кластер. Если есть, то увеличить счетчик числа стягивающих кластеров Mc на единицу.
  1. Повторить пункты 2-3 M раз.
  1. Получить оценку вероятности образования стягивающего кластера image
  1. Повторить 1-5 для ряда значений вероятности p в интервале от 0 до 1.

При достижении порога перколяции по узлам занятые узлы бесконечной решетки образуют кластеры всех размеров из связанных между собой узлов.
Распределение кластеров по размерам следует степенному закону: число n(s) кластеров, содержащих s занятых узлов, пропорционально s -τ .

Методы перколяции для сетевых алгоритмов

  1. Лавинная маршрутизация на основе перколяции для сенсорных сетей. Предлагается уменьшать вероятность пересылки сообщения по мере удаления от источника. Тем самым резко уменьшается число копий сообщений, а вероятность достижения адресата падает незначительно.
  1. Перколяционная маршрутизация для оптической кластерной сети. Предлагается использовать эффект перколяции для предотвращения образования «узких мест» в коммуникационной сети, связывающей узлы кластера (в качестве топологии кластера рассматривается 3D–решетка).
  1. Перколяционный поиск в сетях со степенным распределением связности. Предлагается алгоритм поиска для пиринговых сетей, использующий встречные процессы внедрения и запроса контента и основанный на свойстве «накопления» информации в «ключевых» узлах с большой степенью связности.
  1. Мобильных сетях, уровень изменений топологии в которых настолько высок, что лавинная доставка данных является единственным способом маршрутизации. В этом случае перколяционная лавина обеспечивает тот же уровень доставки данных что и обычная, экономя при этом трафик.

  1. Применение теории перколяции для оценки общей устойчивости и уязвимостей транспортных сетей