Главные темы. Последние записи с тегом «имитационный». Страница 2

Сегодня 26 декабря, четверг

Какой рейтинг вас больше интересует?

получить код

Главная /

Главные темы

Тэг «имитационный»

Без заголовка

2013-02-15 16:22:00

+ развернуть текст сохранённая копия

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

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

Описание структуры сети

Очевидно, что при изучении и имитации процессов движения пакетов по сети, необходимо учитывать, по крайней мере, следующие факторы:

1) распределение радиочастот;

2) изменчивые условия радиослышимости;

3) и, наконец, распределение потоков информации, которое может изменяться при адаптации системы к возникшим ситуациям.

Совокупность радиочастот и потенциальная возможность их использования теми или иными станциями может быть описана гиперграфом H=(Е,W), вершины которого соответствуют узлам сети, а подмножества w_k W- используемым частотам. Описание гиперграфа H=(E,W) может быть задано либо в форме списков w_k={Xi₁, Xi₂, . . . , Xi_N}, либо в виде матрицы инциденций ║S_ik║ элемент которой

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

Рисунок 1

	w₁	w₂
X₁	1	0
X₂	1	1
X₃	0	1
X₄	1	0
X₅	1	1
X₆	0	1

Рисунок 2

Элементы X_iw₁_w₂соответствуют узлам, которые могут воспользоваться как частотойw₁, так и частотойw₂.

Условия радиослышимости могут быть описаны неориентированным графом G=(E,Г), вершины которого соответствуют узлам сети. Вершины, которые соответствуют парам слышащих друг друга абонентов, соединяются ребром.

Следует подчеркнуть, что в такой граф включаются далеко не все потенциально возможные соединения. Например, изображенному на рисунке 1 гиперграфу может соответствовать граф, изображённый на рисунке 3:

Рисунок 3

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

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

	X₁	X₂	X₃	X₄	X₅	X₆
X₁		1	0	1	0	0
X₂	1		1	1	1	1
X₃	0	1		0	0	0
X₄	1	1	0		0	0
X₅	0	1	0	0		0
X₆	0	1	0	0	0

Рисунок 4

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

Содержимое матрицы A_ijпериодически изменяется, что имитирует процесс изменений условий радиослышимости.

Эти вероятности могут быть заданы в виде матрицы P=║P_ij║, каждый элемент которой, соответствует потенциально возможному радиолучу, заданному гиперграфом H=(Е,W), а значение этого элемента – вероятности существования этого радиолуча.

При наличии такой матрицы, генерация ситуаций, связанных с отказами/восстановлениями радиолучей может осуществляться с помощью следующего алгоритма:

1) матрица A=║A_ij║ «обнуляется»;

2) поочерёдно просматриваются элементы матрицы P, отвечающие условию (1):

i < j

(1)

3) если просматриваемый элемент отвечает условию (2)

0 < P_ij < 1

(2)

то

- генерируется случайное число - x, в интервале {0, …, 1};

- проверяется условие (3):

P_ij  x

(3)

и, если условие (3) выполняется, то в граф G=(E,Г) добавляется две дуги - (X_i,X_j) и (X_j,X_i).

Отметим, что, при выборке ситуаций, изменения структуры сети не считаются необратимыми – генерация новых ситуаций всегда опирается на заданное описание сети – гиперграф H=(Е,W).

Приведённый алгоритм может быть проиллюстрирован следующим примером. Рассмотрим заданный пользователем фрагмент сети, который представлен на рисунке 5:

Рисунок 5

Допустим, что станции X₁, X₂и X₄не меняют своей дислокации и связь между ними устойчива, а станция X₅ может потерять связь с любой из этих станций, поскольку место её дислокации выбрано неудачно.

Этому фрагменту может быть поставлена в соответствие матрица P, которая представлена на рисунке 6.

	X₁	X₂	X₄	X₅
X₁		1	1	0.5
X₂	1		1	0.8
X₄	1	1		0
X₅	0.5	0.8	0

Рисунок 6

Предположим теперь, что при выполнении приведённого алгоритма, датчик случайных чисел сформировал следующие значения x:

при рассмотрении элемента P₁₅– число x=0.4;
при рассмотрении элемента P₂₅– число x=0.6.

При таких значениях x матрица A=║A_ij║ будет иметь вид, представленный на рисунке 7, а соответствующий граф G=(E,Г) будет иметь вид, представленный на рисунке 8:

	X₁	X₂	X₄	X₅
X₁		1	1	1
X₂	1		1	1
X₄	1	1		0
X₅	1	1	0

Рисунок 7

Рисунок 8

(Обратим внимание на то, что при рассмотрении величин P_ij=1 и P_ij=0, случайные числа x не играют никакой роли – если P_ij=1, то в граф G=(E,Г) всегда будет включено соответствующее ребро, и наоборот - если P_ij=0, то вершины X_iи X_jне будут считаться смежными).

Очевидно, что при использовании рассматриваемого алгоритма (при иных значениях x), может быть построены четыре варианта графа G=(E,Г) - на рисунке 8 приведён только один из них. Но возможны ещё три варианта:

вариант, представленный на рисунке 9 (вероятность появления такой ситуации - P₁₅(1-P₂₅) = 0.1):

Рисунок 9

вариант, представленный на рисунке 10
(вероятность появления ситуации - P₂₅(1-P₁₅) = 0.4):

Рисунок 10

и, наконец, вариант, представленный на рисунке 11 (вероятность появления такой ситуации - (1-P₂₅) (1-P₁₅) = 0.1):

Рисунок 11

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

Этот план может быть представлен в виде множества суграфов G_a=(E,Г_a), каждый из которых соответствует конкретному узлу-получателю - .X_a.

Например, для представленного на рисунке 1 примера сети, суграф G₁=(E,Г₁) может иметь вид, представленный на рисунке 12:

Рисунок 12

Такой суграф может быть описан в виде матрицы смежности – M⁽^a⁾=║M_ij⁽^a⁾║, элемент которой

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

Тэги: имитационный, маршрутизация, моделирование, связь, сеть, телекоммуникация

Без заголовка

2013-02-13 09:49:00
... /head.png" title="Имитационное моделирование" width="400 ... ее место в имитационной модели сети+ развернуть текст сохранённая копия

Основные особенности моделирования протоколов IEEE 802.11

В предыдущей статье мы рассмотрели модель канала и ее место в имитационной модели сети. Ниже мы сосредоточимся на нескольких основных особенностях протоколов IEEE 802.11.

Известно , что для обеспечения надёжной доставки пакетов, в протоколах IEEE802.11 используется механизм CSMA/CA (Carrier Sense Multiple Acsses withCollisuon Avoidance) – механизм множественного доступа с контролем несущей частоты и предотвращением коллизий.
Основной принцип действия этого механизма достаточно прост и заключается в следующем:

1) перед началом передачи каждое устройство слушает эфир и дожидается, когда канал освободится;

2) канал считается свободным, если, в течение заданного интервала времени - IFS, не обнаружено признаков активности каких-либо других станций;

3) если в течение интервала IFSканал оставался свободным, то рассматриваемое устройство выбирает случайный интервал времени отсрочки, и ещё раз убедившись в том, что канал свободен, передаёт пакет.

Далее, если пакет или кадр предназначен конкретному устройству, то приёмник, успешно приняв пакет, посылает передатчику короткий кадр «квитанции» - ACK (ACKnowledge). При этом если передатчик не принял «квитанции», попытка передачи кадра считается неудачной.

При широковещательной передаче информации квитирование пакетов не производится.

Стандарт IEEE802.11 предусматривает два механизма контроля активности в канале: физический и виртуальный.

Первый из них реализован на физическом уровнеи сводится к определению уровня сигнала в антенне и его сравнению с заданной пороговой величиной.

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

Все устройства сети получают информацию о текущей передаче и могут определить, сколько времени канал будет занят.

Как только станция фиксирует момент окончания передачи кадра, она обязана отсчитать межкадровый интервал IFS.

Если в процессе отсчёта этого интервала канал остаётся свободным, то начинается отсчет слотов – коротких интервалов времени фиксированной длины, число которых ограничено. Номер слота выбирается как случайное число, равномерно распределённое в интервале [0, CW] то есть в интервале конкурентного окна.

Рассмотрим этот процесс на примере, представленном на рисунке 1:

Рисунок 1

Пусть станция «А» выбрала для передачи слот 3. Тогда, после завершения интервала ожидания квитанции - T_IFS, она будет проверять состояние канала в начале каждого слота. Если канал свободен, то из значения таймера отсрочки вычитается единица, и, когда его значение станет равным нулю, начинается передача кадра. Если же в начале какого-либо слота канал окажется занятым, то вычитание единицы не производится, и таймер «замораживается». В этом случае станция «А» осуществляет следующую попытку захвата канала, изменяя только алгоритм выбора слота для передачи.

Как и в предыдущей попытке, данная станция следит за каналом и при его освобождении выдерживает паузу T_IFS. При освобождении канала, станция «А» использует значение «замороженного» таймера в качестве номера слота и выполняет описанную выше процедуру проверки свободных слотов с вычитанием единиц, начиная с «замороженного» значения.

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

В частности, (см. рисунок 1), процесс передачи кадра может быть представлен как последовательность следующих событий:

- освобождение канала;

- начало передачи кадра;

- завершение передачи.

Интервал времени между событиями «освобождение канала» и «начало передачи кадра» может быть представлен как сумма двух величин: T_IFS и T_отср.

В свою очередь, величина T_IFS может быть определена как константа, а величина T_отср (при идеальном стечении обстоятельств) – может быть определена с помощью простейшего выражения (1.1):

	X₁	X₂	X₃	X₄	X₅	X₆
X₁		0	0	0	0	0
X₂	1		0	0	0	0

T_отср = n_ср T_сл

(1.1)

где

- n_ср – среднее значение числа на интервале [0, CW] ,которое в реальности выбирается случайным образом;

- T_сл – условная единица времени («тик»), соответствующая промежутку времени, затрачиваемому на один слот.

Интервал времени между началом и завершением передачи кадра может быть определён как функция от длины пакета. Причём, при вычислении этого интервала, должны быть учтены особенности передачи данных, которые присущи IEEE 802.11 при использовании каналов высокой производительности.

Например, в спецификациях IEEE802.11bи IEEE 802.11g, время передачи кадра складывается из двух составляющих:

1) времени передачи преамбулы и заголовка физического уровня - T_заг, которые передаются с низкой скоростью – V_заг=1 Мбит/c, которое определяется произведением (1.2):

T_заг= L_заг V_заг

(1.2)

где L_заг– длина заголовка в битах;

2) времени передачи MAC-части кадра – T_MAC, которая может передаваться с более высокой скоростью - V_MAC=5.5 или 11 Мбит/c, и составлять величину (1.3):

T_MAC= L_MAC V_MAC

(1.3)

где L_MAC– длина MAC-части

Имея величины T_заг и T_MAC можно вычислить время передачи кадра, выраженное в условных единицах – «тиках». Для этого достаточно воспользоваться выражением (1.4):

T_прд= (T_заг + T_MAC) / T_сл

(1.4)

1.2.5. Однако, в общем случае, причинно-следственные связи между подобными событиями не так уж и просты - при составлении формального описания процессов передачи кадров, следует учитывать поведение приёмных и передающих станций в более сложных ситуациях, а именно:

- при возникновении коллизий, когда на один и тот же канальный ресурс претендуют две или более станций;

- при отсутствии радиослышимости между отдельными станциями;

- при наличии радиопомех.

Причём, необходимость учёта подобных явлений связана не только со спецификой каналов и устройств Wi-Fi вообще, но и с другими, пока ещё не разрешёнными проблемами. Наиболее сложная из них – проблема скрытых станций, суть которой заключается в следующем.

В беспроводных сетях возможны ситуации, когда два станции – «A» и «B» удалены и не слышат друг друга, но обе попадают в зону охвата третьей станции – «C». Такая ситуация изображена на рисунке 2:

Рисунок 2

Если, при таких условиях, станции «A» и «B» начнут передачу в направлении станции «С», то они не смогут обнаружить конфликтную ситуацию и определить, почему пакеты не проходят.

В доступных реализациях IEEE 802.11 эта проблема решена, но лишь частично. Для того, чтобы предотвратить коллизии, в них предусмотрена возможность обмена очень короткими служебными кадрами - RTS и CTS.

Первый из них – RTS(RequestToSend– запрос на передачу), отправляется источником кадра (например, станцией «А») и оповещает станцию «С» о необходимости передачи кадра заданной длины. Второй – CTS (Clear To Send – свободна для передачи), формируется станцией «С» и оповещает все смежные станции о том, что, в соответствующий промежуток времени, эфир будет занят, и предоставлен станции «А». Получив такой кадр, станция «А» получает право доступа к каналу, а конкурирующая с ней станция «B» должна «уступить» эфир до завершения работы станции «А».

Следует отметить, что, даже при наличии такого механизма, риск коллизий не исключён, но будет существенно снижен. Это достигается тем, что RTS- и CTS-кадры гораздо короче, чем кадр данных. Например, максимальная длина кадра данных в IEEE 802.11 равна 2346 байт, длина RTS-кадра – 20 байт, а длина CTS-кадра – 14 байт.

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

Существует ещё одна, схожая проблема. В сети Wi-Fi могут сосуществовать две спецификации протоколов IEEE802.11 – IEEE802.11bи IEEE802.11g. Частично, эти спецификации совместимы, поскольку, на одних скоростях передачи, они используют один и тот же метод модуляции, на других – нет. Для того чтобы убедиться в этом, достаточно заглянуть в таблицу 1.1:

Таблица 1.1

Тэги: имитационный, маршрутизация, моделирование, связь, сеть, телекоммуникация

Без заголовка

2013-02-12 10:28:00
... .png" title="Имитационное моделирование" width ... тему имитационного моделирования беспроводных ...
+ развернуть текст сохранённая копия

Модель канала и её место в имитационной модели сети.

Продолжая тему имитационного моделирования беспроводных сетей связи, необходимо отметить, что современные беспроводные сети базируются на совокупности двух технологий – беспроводной передачи информации и сетевого взаимодействия.

Причём и те, и другие технологии стандартизированы и отвечают требованиям эталонной модели взаимодействия открытых систем – МВОС, утверждённой ещё в 1984 году.

Согласно этой модели, (см. рисунок 1), все протоколы взаимодействия систем подразделяются на семь уровней – физический, канальный (звена данных), сетевой, транспортный, сеансовый, представительский и прикладной.

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

1) на канальном уровне - подуровней управления доступом к среде MAC (Media Access Control) и логической передачи данных LLC (Logical Linc Control);

2) на физическом уровне – подуровней PLCP (Physical Layer Convergence Procedure– определение состояния физического уровня) и PMD (Physical Medium Dependent – подуровень, зависящий от среды передачи).

Как эти подуровни соотносятся между собой и с вышестоящими уровнями МВОС, показано на рисунке 1:

Рисунок 1

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

Причём предоставленная самой себе среда может пребывать в устойчивом состоянии, но её организация - то есть состояние связей между станциями, может меняться, как под влиянием внешних воздействий на среду например, шумов, так и внутренних воздействий на элементы среды, которые описываются протоколами «нижних» уровней. В свою очередь реакции «среды» на эти воздействия должны рассматриваться как управляющие воздействия.

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

Разумеется, что поведение рассматриваемой «среды» должно быть представлено в упрощенном виде – в виде модели поведения канала, достаточной для получения конкретных значений вероятностей и времён доведения пакетов при любых ситуациях в сети.

Подобное упрощение может быть достигнуто за счёт замены отдельных подмножеств состояний канала и канального оборудования на ключевые точки - «макро состояния», причём такая замена не должна приводить к искажениям наиболее важных причинно-следственных связей.

Поэтому, модель канала должна отражать наиболее важные особенности протоколов «нижних» уровней.
В следующей части мы обсудим основные особенности моделирования протоколов IEEE 802.11.

Тэги: 802.11, wi-fi, имитационный, маршрутизация, моделирование, связь, сеть, телекоммуникация

Без заголовка

   2013-02-11 09:28:00
... color: #0b5394;">Имитационное моделирование беспроводных ... имитационной модели, которая ...
+ развернуть текст   сохранённая копия

Имитационное моделирование беспроводных сетей связи.

Проблемы построения и использования имитационных моделей сетей связи и её элементов могут ставиться и решаться в самых различных аспектах. Разработка имитационной модели, которая обеспечивает возможность оценки вероятностей и качества предоставления услуг связи в сети с произвольной топологией, является нетривиальной задачей.
Такая модель должна обеспечивать:
1) возможность ввода и корректировки формального описания топологии сети;
2) имитацию предложенных алгоритмов назначения и корректировки маршрутов, (в том числе имитацию процедур формирования и рассылки служебных пакетов);
3) имитацию движения пользовательских пакетов в соответствии с предложенными процедурами маршрутизации;
4) получение следующих характеристик сети:
- вероятности доставки пакетов, поступивших в сеть;
- среднего времени обслуживания пакета в сети (без учёта его пребывания в очереди);
- среднего время пребывания пакета в очередях;

Причём, в данной имитационной модели может быть использована любая модель канала, которая удобна для необходимых экспериментальных исследований. Главное, чтобы данная модель соответствовала всем чертам оригинала, которые существенны для круга изучаемых явлений.
В частности, каналы и каналообразующие средства cети могут быть представлены как некие «чёрные ящики», с известной номенклатурой входных воздействий и соответствующих реакций на данные воздействия.
Такой подход обеспечивает возможность объективного изучения систем, построенных на базе реальных технических средств, внутренняя структура которых неизвестна, либо слишком сложна для точной имитации их поведения.
Рассмотрению возможных вариантов формального описания поведения таких технических средств посвящен этот цикл статей.

В следующей части мы расскажем о модели канала и ее месте в имитационной модели сети.


Тэги: имитационный, моделирование, связь, сеть

Без заголовка
   2013-02-07 18:44:00
... передачи информации, системы имитационного моделирования сетей связи ...
+ развернуть текст   сохранённая копия

Здравствуйте и разрешите представиться!

Это блог компании Смарт Текнолоджис. Мы занимаемся разработкой в сфере телекоммуникаций.
Все, что связанно с сетевыми технологиями представляет для нас огромный интерес.

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

Тонкости языков программирования, мощь методологий разработки программных проектов, сложность архитектур распределенных программных систем, строгость алгоритмов и методов оптимизации заставляют нас постоянно уделять им повышенное внимание и учиться, учиться, учиться…

А мы не против!

И конечно в нашей стране не мы одни идем этим не простым путем. Именно из осознания этого и родился это блог. В нем мы постараемся освещать вопросы, которые показались нам наиболее интересными и непростыми. И если хотя бы один пост окажется полезными студенту, инженеру, ученому или просто случайному читателю, мы будем считать, что все это не зря.

Тэги: алгоритм, имитационный, маршрутизация, моделирование, программирование, смарт, текнолоджис, телекоммуникация

Страницы: 1 2 3

Главная / Главные темы / Тэг «имитационный»