Исследование методов множественного доступа к каналу связи с прослушиванием несущей и разрешением коллизий

Курс: «Компьютерные сети»

ЗАДАНИЕ ПО КУРСОВОМУ ПРОЕКТУ:

«Исследование методов множественного доступа к каналу связи с прослушиванием несущей и разрешением коллизий»

Изучите модель сети «синхронная ALOHA», описанной в приложении I и более подробно  в книге «Сети передачи данных» Д. Бертсекаса и Р. Галлагера (М.: «Мир», 1989).

ЗАДАНИЕ №1.

Приведите подробный вывод формул для описания переходных вероятностей и стационарного состояния цепи Маркова, описывающей переходы из состояния «k-узлов передает в данном окне» в состояние «l-узлов передает в следующем окне».

Для этого:

(а) Убедитесь в том, что стационарные вероятности р_п цепи Маркова, показанной на рис.1, являются решением уравнений

(б) Для п<.т используйте а), чтобы выразить p_n+1 через р₀, p₁,...,р_п.

(в) Выразите p₁ через р₀, а затем р₂ через p₀.

(г) При m = 2найдите выражение для p₀, зависящее от переходных  вероятностей.

Используя выражения  (П1.1-3) для вероятностей передачи i узлами с задолженностями или без задолженностей, и формулы для переходных вероятностей (П1.3) вычислить и отобразить на графиках зависимостей от числа узлов m=2,3,…,7 вероятности что задолженность имеется у двух узлов (вероятность p₂).

ПОЯСНЕНИЕ

Пусть n обозначает число узлов с задолженностью в начале заданного окна. Каждый из этих узлов будет передавать пакет в данном окне независимо от других узлов, с вероятностью q_r. Каждый из m-nостальных узлов будет передавать пакет в данном окне, если один (или более) таких, пакетов поступили во время предыдущего окна. Поскольку моменты поступления распределены по пуассоновскому закону со средним l/m,то вероятность непоступления новых пакетов равна е^-l/m; следовательно, вероятность того, что узел, не имеющий задолженности, передаст пакет в данном окне, равна q_a=1-e^-l/m. Пусть Q_a(i,n) обозначает вероятность того, что i, узлов, не имеющих задолженности, передают пакеты в данном окне, и пусть Q_r(i,п)обозначает вероятность того, что iузлов, имеющих задолженность, передают:

                                          (П1.1)

                                          (П1.2)

               (П1.3)

Варианты значений параметров для расчета:

(используйте последние две цифры номера зачетки)

2. Определим снос в состоянии n (D_n)как среднее изменение задолженности за одно временное окно при старте из состояния n. Таким образом, D_nравно среднему числу новых пакетов, поступивших в систему, минус среднее число успешных передач в окне; среднее число успешных передач равно вероятности успешной передачи, обозначаемой через Р_усп. Таким образом,

                                            (П1.4)

где

                                  (П1.5)

Определим интенсивность попыток G(п) как среднее число попыток передач в окне, когда система находится в состоянии в; имеем

G(п)=(m-n)q_a+nq_r

Если q_aи q_r,. малы. Р_успхорошо аппроксимируется следующей функцией интенсивности попыток:

                                                 (П1.6)

Это приближение можно непосредственно получить из (П1.5), используя приближение (1 -х)^y =е^-xy для малых хв выражениях для Q_a, и Q_r,. Аналогично вероятность пустого окна равна приближенно e^-G(т). Таким образом, число пакетов, передаваемых в окне, хорошо аппроксимируется пуассоновской случайной величиной (как и в первоначальном интуитивном анализе), но параметр (n) зависит от состояния.

ЗАДАНИЕ №2

(а) Покажите, что P_yспиз (П1.5) можно представить в следующем виде:

(б) Используя приближение (1 - х)^y»е^-xyдля малых x, покажите, что при малых q_аи q_r

где G(n) = (т - n) q_a+nq_r.

(в) Заметим, что (1 - х)^y = е^yln(1-x) .  Разложите ln(1 - x)в степенной ряд и покажите, что

Покажите, что это отношение близко к 1, когда х<<1 и x²y << 1.

ЗАДАНИЕ №3

(а) Изобразите графики зависимостей, показанных на рис. П1.4 Приложения 1, в случае когда q_r = l/m, а q_a = 1/me.

Варианты значений параметров для построения графика:

(используйте последние две цифры номера зачетки)

(б) Найдите скорость ухода (т. е. Р_усп) в случае всеобщей задолженности n=т.

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