пятница, 15 февраля 2013 г.


Формальное представление текущего состояния сети при моделировании.

Итак, рассмотрев основные особенности моделирования протоколов IEEE 802.11, мы переходим к формальному описанию моделируемой сети связи.

Описание структуры сети
Очевидно, что при изучении и имитации процессов движения пакетов по сети, необходимо учитывать, по крайней мере, следующие факторы:
1) распределение радиочастот;
2) изменчивые условия радиослышимости;
3) и, наконец, распределение потоков информации, которое может изменяться при адаптации системы к возникшим ситуациям.
Совокупность радиочастот и потенциальная возможность их использования теми или иными станциями может быть описана гиперграфом H=(Е,W), вершины которого соответствуют узлам сети, а подмножества wk W - используемым частотам. Описание гиперграфа H=(E,W) может быть задано либо в форме списков wk={Xi1, Xi2, . . . , XiN}, либо в виде матрицы инциденций ║Sik║ элемент которой

Например, изображённый на рисунке 1 гиперграф может быть представлен в виде матрицы ║Sik║, представленной на рисунке 2:

Рисунок 1

w1
w2
X1
1
0
X2
1
1
X3
0
1
X4
1
0
X5
1
1
X6
0
1

Рисунок 2
Элементы Xiw1w2 соответствуют узлам, которые могут воспользоваться как частотой w1, так и частотой w2
Условия радиослышимости могут быть описаны неориентированным графом G=(E,Г), вершины которого соответствуют узлам сети. Вершины, которые соответствуют парам слышащих друг друга абонентов, соединяются ребром.
Следует подчеркнуть, что в такой граф включаются далеко не все потенциально возможные соединения. Например, изображенному на рисунке 1 гиперграфу может соответствовать граф, изображённый на рисунке 3:

Рисунок 3
Граф G=(E,Г) может быть описан матрицей смежности - A=║Aij║. Число строк и столбцов такой матрицы должно соответствовать числу узлов в сети. Элементы матрицы ║Aij║ отражают структуру графа G=(E,Г), соответствующего текущему состоянию сети:

Например, изображённому на рисунке 3 графу будет соответствовать матрица, показанная на рисунке 4:

X1
X2
X3
X4
X5
X6
X1

1
0
1
0
0
X2
1

1
1
1
1
X3
0
1

0
0
0
X4
1
1
0

0
0
X5
0
1
0
0

0
X6
0
1
0
0
0

Рисунок 4


Имитация процессов отказов/восстановлений радиолучей

Содержимое матрицы Aij периодически изменяется, что имитирует процесс изменений условий радиослышимости.
Эти вероятности могут быть заданы в виде матрицы P=║Pij║, каждый элемент которой, соответствует потенциально возможному радиолучу, заданному гиперграфом H=(Е,W), а значение этого элемента – вероятности существования этого радиолуча.
При наличии такой матрицы, генерация ситуаций, связанных с отказами/восстановлениями радиолучей может осуществляться с помощью следующего алгоритма:
1) матрица A=║Aij║ «обнуляется»;
2) поочерёдно просматриваются элементы матрицы P, отвечающие условию (1):
i < j
(1)
3) если просматриваемый элемент отвечает условию (2)
0 < Pij < 1
(2)
то
- генерируется случайное число - x, в интервале {0, …, 1};
- проверяется условие (3):
Pij x
(3)
и, если условие (3) выполняется, то в граф G=(E,Г) добавляется две дуги - (Xi,Xj) и (Xj,Xi).
Отметим, что, при выборке ситуаций, изменения структуры сети не считаются необратимыми – генерация новых ситуаций всегда опирается на заданное описание сети – гиперграф H=(Е,W).
Приведённый алгоритм может быть проиллюстрирован следующим примером. Рассмотрим заданный пользователем фрагмент сети, который представлен на рисунке 5:

Рисунок 5
Допустим, что станции X1, X2 и X4 не меняют своей дислокации и связь между ними устойчива, а станция X5 может потерять связь с любой из этих станций, поскольку место её дислокации выбрано неудачно.
Этому фрагменту может быть поставлена в соответствие матрица P, которая представлена на рисунке 6.
X1
X2
X4
X5
X1

1
1
0.5
X2
1

1
0.8
X4
1
1

0
X5
0.5
0.8
0

Рисунок 6
Предположим теперь, что при выполнении приведённого алгоритма, датчик случайных чисел сформировал следующие значения x:
  1. при рассмотрении элемента P15 – число x=0.4;
  2. при рассмотрении элемента P25 – число x=0.6.
При таких значениях x матрица A=║Aij║ будет иметь вид, представленный на рисунке 7, а соответствующий граф G=(E,Г) будет иметь вид, представленный на рисунке 8:


X1
X2
X4
X5
X1

1
1
1
X2
1

1
1
X4
1
1

0
X5
1
1
0


Рисунок 7

Рисунок 8
(Обратим внимание на то, что при рассмотрении величин Pij=1 и Pij=0, случайные числа x не играют никакой роли – если Pij=1, то в граф G=(E,Г) всегда будет включено соответствующее ребро, и наоборот - если Pij=0, то вершины Xi и Xj не будут считаться смежными).
Очевидно, что при использовании рассматриваемого алгоритма (при иных значениях x), может быть построены четыре варианта графа G=(E,Г) - на рисунке 8 приведён только один из них. Но возможны ещё три варианта:
  1. вариант, представленный на рисунке 9 (вероятность появления такой ситуации - P15 (1-P25 ) = 0.1):
Рисунок 9
  1. вариант, представленный на рисунке 10
     (вероятность появления ситуации - P25 (1-P15) = 0.4):
Рисунок 10

  1. и, наконец, вариант, представленный на рисунке 11 (вероятность появления такой ситуации - (1-P25 ) (1-P15 ) = 0.1):
Рисунок 11

2.3. Таким образом, в результате имитации процессов отказов/восстановлений радиолучей, мы можем получить любые структуры, и, имея граф G=(E,Г) - установить возможность успешной доставки пакетов по всем заданным маршрутам. Для этого необходимо иметь план распределения нагрузки в сети, который определён процедурами маршрутизации.
Этот план может быть представлен в виде множества суграфов Ga=(Ea), каждый из которых соответствует конкретному узлу-получателю - .Xa.
Например, для представленного на рисунке 1 примера сети, суграф G1=(E1) может иметь вид, представленный на рисунке 12:

Рисунок 12
Такой суграф может быть описан в виде матрицы смежности – M(a) =║Mij(a)║, элемент которой

Например, представленный на рисунке 12 суграф может быть оформлен в виде матрицы, которая показана на рисунке 13:

X1
X2
X3
X4
X5
X6
X1

0
0
0
0
0
X2
1

0
0
0
0
X3
0
1

0
0
0
X4
1
0
0

0
0
X5
1
0
0
0

0
X6
0
0
0
0
1

Рисунок 13
Имея матрицы M(a) =║Mij(a) и A=║Aij║, можно построить результирующую матрицу B(a)=║Bij(a)║ элементы которой определяются конъюнкцией элементов Mij(a) и Aij, то есть соотношением (4):
Bij(a) = Mij(a) Aij
(4)
Такая матрица позволит установить «реальные» маршруты пакетов к получателю Xa и перечень узлов, в которых эти пакеты будут теряться.

Одной из ключевых моделей при моделировании беспроводных систем связи, является модель распространения радиосигнала и оценка зон действия этих сигналов в рамках выбранной модели распространения.

Комментариев нет:

Отправить комментарий