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

Сегодня 9 января, четверг

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

получить код

Главная /

Главные темы

Тэг «маршрутизация»

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

2013-03-11 11:04:00

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

Имитационная модель канала коллективного доступа

В предыдущей статье мы оценивали вероятность успешного захвата канала в конкурентном окне.

Имитация процессов передачи и приёма кадра

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

Рисунок 1

1.2. Изображённый на рисунке 1 «Таймер» X_iпредназначен для определения моментов времени, соответствующих:

1) времени отсрочки начала передачи очередного пакета (кадра);

2) времени завершения передачи;

3) времени ожидания «квитанции».

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

1.3. «Таймер» X_j– определяет момент начала и завершения передачи квитанции, причём поведение этого таймера всегда детерминировано. Следует отметить, что, как «Таймер» X_i, так и «Таймер» X_i, ведут отсчёт интервалов времени в особых условных единицах – «тиках».

Предположительно, один «тик» имитирует интервал времени, соответствующий длительности одного «слота».

1.4. Автомат, который имитирует процесс управления передачей кадра по радиолучу (X_i, X_j) фактически выполняет функции «диспетчера», взаимодействующим со своим «окружением» с помощью следующих сигналов:

1) сигналов S_тр⁽ⁱ⁾и S_обс⁽ⁱ⁾, обеспечивающих взаимодействие с протоколом «высшего» уровня, который «поставляет» кадры для передачи, причём:

- сигнал S_тр⁽ⁱ⁾соответствует поступлению очередного требования на передачу кадра;

- сигнал S_обс⁽ⁱ⁾, который соответствует запросу очередного требования на обслуживание, когда предыдущая заявка на обслуживание уже выполнена.

2) сигналов S_T⁽ⁱ⁾и S_⁽ⁱ⁾, первый из которых определяет тип интервала времени, а именно:

- времени отсрочки передачи пакета;

- времени завершения передачи пакета;

- времени ожидания квитанции,

а второй – S_⁽ⁱ⁾– завершению отсчёта заданного интервала.

3) сигналов S_прд⁽ⁱ⁾и S_кв⁽^j⁾, обеспечивающих имитацию взаимодействия с «приёмной стороной» (автоматом «Управление приёмом в X_j»). При этом сигнал S_прд⁽ⁱ⁾= 1 оповещает все «станции» X_jо том, что передатчик X_iнаходится в состоянии передачи.

4) и, наконец, сигнала S_зан, запрещающего выход в эфир, формируемого «анализатором занятости канала». Данный анализатор представляет собой тривиальный автомат, реализующий булеву функцию (1):

S_зан = A_1iS_прд⁽¹⁾ v A_2iS_прд⁽²⁾ v . . . v A_NiS_прд^(N)

(1)

где

- A_ki (k=1, 2, . . . , N) – элементы матрицы смежности A=║A_ij║, описывающей граф G=(E,Г), соответствующий текущему состоянию сети;

- S_прд⁽^k⁾(k=1, 2, . . . , N) – значения сигналов, соответствующих состояниям конкурирующих станций: если конкурент X_kведёт передачу, то S_прд⁽^k⁾=1.

- N– число узлов в сети.

Следует отметить, что функция (1) может быть использована только в том случае, если все узлы сети работают на одной и той же частоте. Если же это условие не выполняется, то функция (1) должна быть дополнена действием (2):

S_прд^(k) : = 0, если X_iw_i, X_jw_i, но X_kw_i

(2)

1.5. Хотя функции (1) и (2) и тривиальны, но, по-видимому, требуют пояснений. Для этого рассмотрим следующий пример. Пусть условия радиослышимости описываются графом, который изображён на рисунке 2:

Рисунок 2

Такому графу будет соответствовать матрица A=║A_ij║, которая представлена на рисунке 3:

	X_i	X_j	X_b	X_c	X_d
X_i	0	1	1	1	1
X_j	1	0	0	1	1
X_b	1	0	0	1	0
X_c	1	1	1	0	1
X_d	0	1	0	1	0

Рисунок 3

Теперь предположим, что на частоту w_iпретендуют передатчик X_iи его конкуренты – станции X_bи X_d. Сравнивая пары значений A_kiS_прд⁽^k⁾, получим картину, представленную на рисунке 4:

	A_ki		S_прд⁽^k⁾
X_i	0	&	1	= 0
X_j	1	&	0	= 0
X_b	1	&	1	= 1
X_c	1	&	0	= 0
X_d	0	&	1	= 0

Рисунок 4

Это означает, что станция X_iспособна уступить канал станции X_b, но никогда не обнаружит каких-либо признаков активности со стороны станции X_d. Но, это - особенность IEEE802.11 ….

1.6. Поведение автомата «Управление передачей» может быть описано диаграммой состояний, представленной на рисунке 5:

Рисунок 5

Данный автомат может находиться в одном из восьми состояний:

St₀– исходное состояние - ожидание заявки на передачу кадра;
St₁– ожидание освобождения канала;
St₂– запуск таймера, обеспечивающего отсчёт времени отсрочки начала передачи пакета, а также момента времени завершения его передачи;
St₃– ожидание собственного «слота»;
St₄– передача пакета в эфир;
St₅– запуск таймера ожидания квитанции;
St₆– ожидание квитанции;
St₇– оповещение о факте неудачной попытке передачи кадра.

Переходы данного автомата из одного состояния в другое осуществляются под воздействием символов входного алфавита - _i, то есть под воздействием конкретных комбинаций входных сигналов. Эти комбинации приведены в таблице 1:

Таблица 1

Символ входного алфавита

Значения входных сигналов

S_тр⁽ⁱ⁾

S_⁽ⁱ⁾

S_кв⁽ⁱ⁾

S_зан⁽ⁱ⁾

λ₀

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

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

2013-03-04 10:07:00

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

Вероятность успешного захвата канала в конкурентном окне

Напомним, ранее мы попытались оценить возможные потери при возникновении коллизий в канале коллективного доступа.

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

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

канал свободен;
время отсрочки исчерпано.

Кроме того, будем считать, что захват одного и того же слота двумя и более станциями неизбежно приведёт к коллизиям.

Общее число ситуаций, которые могут возникнуть при случайном «розыгрыше» слотов, будет равняться числу размещений с повторением из kпо S, и определяться выражением (1):

A_k^S= S^k⁺¹

(1)

где

S – общее число слотов;
k+1 – общее число станций в «клике», включая рассматриваемую станцию «А».

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

Рисунок 1

Число таких ситуаций зависит от числа слотов - Sи числа «конкурентов» - k, и определяется выражением (2):

(S-1)^k

(2)

а вероятность захвата 1-го слота – выражением (3):

P₁= (S-1)^k/ S^k⁺¹

(3)

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

Соответствующий пример приведён на рисунке 2:

Рисунок 2

Вероятность подобной ситуации будет определяться выражением (4):

P₂= (S-2)^k/ S^k⁺¹

(4)

Аналогичным образом может быть определена вероятность успешного использования третьего слота – см. выражение (5):

P₂= (S-3)^k/ S^k⁺¹

(5)

В общем же случае, суммарная вероятность «победы» в конкурентной борьбе, нацеленной на захват канала, будет равняться величине P_зхв, которая может быть определена по формуле (6):

_S-1
P_зхв= P₁+ P₂+ ... + P_S-1 =  (S-i)^k/ S^k+1	(6)
ⁱ⁼¹

Следует отметить, что формула (6) справедлива только при k>0. Очевидно, что, при k>0, последний слот не может быть захвачен и успешно использован двумя и более абонентами. Но если k=0, то последний, S-тый слот может быть также успешно использован, следовательно, величина P_зхвбудет равна единице.

3.2.5. Графики функции (6) при различных значениях величины Sпредставлены на рисунке 3:

Рисунок 3

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

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

Но при этом необходимо ответить на следующий вопрос, - какой способ имитации этих процессов наиболее целесообразен?

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

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

В принципе, такое допущение возможно и может считаться достаточно корректным. Например, при имитации движения пользовательского трафика можно считать, что нагрузка на любой канал не должна превышать 80% его производительности, поскольку в противном случае очереди в узлах будут стремительно расти. Для того, чтобы убедиться в этом, достаточно рассмотреть график, который приведён на рисунке 4:

Рисунок 4

Этот график показывает зависимость времени пребывания пакета в очереди от нагрузки на канал - Ψ=λ/μ, где λ – интенсивность потока заявок, а μ – производительность канала. (при построении графика предполагалось, что поток заявок – Пуассоновский, а время обслуживания – постоянное). Время ожидания показано в условных единицах: одна условная единица – время обслуживания одного пакета.

Тогда, рассматривая этот график можно прийти к следующему заключению: при Ψ=0.8 средняя величина очереди на канал равна двум. И можно допустить, что ситуации, при которых на один и тот же канал будут претендовать более 2-х станций, не представляют интереса, поскольку строить сети с «бесконечными» очередями не имеет смысла.
Далее мы рассмотрим имитационную модель канала коллективного доступа.

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

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

2013-02-25 12:26:00

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

Оценка возможных потерь при возникновении коллизий

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

Вероятность доставки пакета при абсолютно случайном доступе

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

Но с другой стороны такая схема доступа, в силу своей простоты, весьма привлекательна и допускается IEEE802.11. Более того, есть основания предполагать, что она будет устойчиво работать в сетях с малой нагрузкой. Остаётся ответить на вопрос, – с какой?

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

P(T_ij) = 1 - exp (- λ_∑^(ij) T_ij)

(1)

где

- λ_∑⁽^ij⁾ – плотность суммарного потока пакетов, поступающих от «конкурентов» станции X_i;

- T_ij- время передачи пакета по направлению (X_i, X_j);

Следует отметить, что формула (1) справедлива только в том случае, если «фоновый» поток λ_∑⁽^ij⁾ является простейшим, то есть подчиняется закону распределения Пуассона. Однако, ориентация на данный закон может быть обоснована его следующими свойствами:

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

Имея значения величин λ_∑⁽^ij⁾и T_ijможно вычислить вероятность успешной передачи пакета по любому радиолучу.

Для того чтобы получить эту вероятность следует действовать следующим образом.

Допустим, что в одну и ту же зону радиослышимости входят три станции, чему соответствует граф, изображённый на рисунке 1:

Рисунок 1

Каждой дуге такого графа (X_i, X_j) может быть поставлен в соответствие поток - λ_ij(будем считать, что такие потоки известны).

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

P_ij^усп= [1 – P(T_ij)] = exp (- λ_∑⁽^ij⁾ T_ij)

(2)

При этом, величина λ_∑⁽^ij⁾будет зависеть от «окружения» передающей и приёмной станций. Для рассматриваемого примера будем иметь:

λ_∑⁽¹²⁾ = λ_∑⁽¹³⁾ = λ₂₁+ λ₂₃+ λ₃₁+ λ₃₂ – «фоновый» поток для (X₁,X₂) и (X₁,X₃);
λ_∑⁽²¹⁾ = λ_∑⁽²³⁾ = λ₁₂+ λ₁₃+ λ₃₁+ λ₃₂ – «фоновый» поток для (X₂,X₁) и (X₂,X₃);
λ_∑⁽³¹⁾ = λ_∑⁽³²⁾ = λ₁₂+ λ₁₃+ λ₃₁+ λ₃₂ – «фоновый» поток для (X₃,X₁) и (X₃,X₂).

Пользуясь соотношением (2), можно найти ориентировочное значение величины P_ij^усп при любом распределении потоков.

Для этого достаточно следующих исходных данных:

1) матрицы Λ⁽^w⁾=║λ_ij⁽^w⁾║, задающей потоки между всеми парами узлов рассматриваемой зоны «w»;

2) времени передачи пакета - величины T_ij.

Если считать, что все пакеты имеют одинаковую длину и скорости их передачи одинаковы, то величина P_ij^успможет быть представлена в виде функции e^-^α, где α=λ_∑T_ij.

График такой функции представлен на рисунке 2.

Рисунок 2

Данный график показывает, что даже относительно небольшой «фоновый» поток, может снизить вероятность успешной передачи пакета до неприемлемой величины. С другой стороны, даже при предельной нагрузке, 37% пакетов могут быть успешно переданы с первой попытки.

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

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

Например (см. рисунок 3), если основная нагрузка на канал ляжет направление (X₁, X₂):

Рисунок 3

а поток α_∑⁽¹⁾будет отвечать условию (3)

α_∑⁽¹⁾ = α₂₁+ α₂₃+ α₃₁+ α₃₂≤ 0.02

(3)

то система может оказаться весьма эффективной.

К аналогичным результатам приведёт другой вариант распределения нагрузки, при котором 98% нагрузки будут соответствовать направлениям, инцидентным единственному узлу – X₁(см. рисунок 4):

Рисунок 4

Но если все величины α_ij будут равны между собой, то канал окажется в наиболее тяжёлых условиях. Причём, с ростом числа абонентов канала, требования к ограничению потока будут всё более и более жёсткими. Поэтому такой режим доступа вряд ли найдёт широкое применение.

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

Далее мы попробуем оценить вероятность успешного захвата радиоканал в конкурентном окне.

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

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

2013-02-21 18:18:00

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

Оценка зон действия радиосигналов

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

Очевидно, что это обстоятельство должно учитываться при составлении графа G=(E,Г), описывающего условия радиослышимости.

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

D = 10^[(^FSL^{/ 20) – (33 / 20)}^lgF^]

(1)

где

- F– центральная частота передачи (МГц);

- FSL– потери в свободном пространстве, которые определяется с помощью выражения (2):

FSL = P_t_,дБВт+ G_t_,дБи+ G_r_,дБи– P_min_,дБВт– L_t_,дБ– L_r_,дБ– SOM

(2)

где

- P_t_,дБВт – мощность передатчика;

- G_t_,дБи- коэффициент усиления передающей антенны;

- G_r_,дБи- коэффициент усиления приёмной антенны;

– P_min_,дБВт- чувствительность приёмника на используемой скорости передачи;

– L_t_,дБ- потери сигнала в коаксиальном кабеле и разъёмах передающего тракта;

– L_r_,дБ- потери сигнала в коаксиальном кабеле и разъёмах приёмного тракта.

Все перечисленные величины берутся из паспортных данных используемых приёмных и передающих устройств.

Параметр SOM(SystemOperatingMargin) - учитывает возможные факторы, отрицательно на дальность связи, такие как:

- температурный дрейф чувствительности приёмника и выходной мощности передатчика;

- всевозможные атмосферные явления: туман, снег, дождь;

- рассогласование антенн приёмника и передатчика с антенно-фидерным трактом.

Параметр SOMобычно берётся равным 10 дБ– при инженерных расчётах считается, что такой запас в энергетике связи вполне достаточен.

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

В этом случае, пользователь будет в состоянии оценить возможность радиосвязи между любой парой абонентов – если действительное расстояние D_ijбольше соответствующего расчетного значения (см. выражение (1)), то следует считать, что связь между станциями X_iи X_jотсутствует и вероятность существования соответствующего радиолуча – P_ij, приравнивается нулю.

Как уже отмечалось, радиоволна в процессе её распространения в пространстве занимает объём в виде эллипсоида вращения с максимальным радиусом в середине пролёта, который называется зоной Френеля. Естественные преграды - земля, холмы, деревья и искусственные препятствия - здания, холмы и т.д., которые попадают в это пространство, ослабляют сигнал.

Обычно блокирование 20% зоны Френеля вносит незначительное затухание в канал. При блокировании свыше 20% затухание сигнала будет уже заметным, поэтому будем считать, что следует избегать соответствующих мест дислокации станций. Тогда, при подготовке исходных данных для моделирования, можно считать целесообразным следующее предположение: если величина R отвечает неравенству (3)

R > 17,3 [D_iD_j / F (D_i + D_j)]^-2

(3)

где

D_i – расстояние от антенны станции X_i до самой высшей точки предполагаемого препятствия (см. рисунок 1);
D_i – аналогичное расстояние от антенны станции X_j;
F – средняя частота передачи;

то следует считать, что P_ij=0. В противном случае - P_ij=1.

Рисунок 1

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

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

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

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:

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

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

Главная / Главные темы / Тэг «маршрутизация»

X₁

X₂

X₃

X₄

X₅

X₆

X₁

X₂

Блограйдеров
14502

Блогов
219930
(+0 сегодня)

Сообществ
1311
(+0 сегодня)

ЖЖ все стерпит
по количеству голосов (152) в категории «Истории»

Категория «Программы»

Взлеты Топ 5


+557	564	Виктор Имантович Алкснис
+548	625	Все для людей
+520	561	krodico
+519	560	sich
+500	511	Выводы простого человека

Падения Топ 5


-2	15	dandr
-6	11	Записки океанолога
-7	12	Internet business in Ukraine
-8	10	Markup
-9	4	Linux-дистрибутив Ubuntu (Xubuntu, Kubuntu, Edubuntu)

Загрузка...