Суммарная интенсивность потока сообщений в узел j

                                                           n n

L_j = S  S l_j(k, l)   (j = 0, n).

                                               l=1 k=1

                                                  l¹k

 

L_j используется для оценки времени обработки заголовка сообщения в узле связи j.

 

 

Расчет вероятностей (или коэффициентов) передач для РСеМО СПД

Коэффициенты передач совпадают с вероятностями передач, так как сообщения не попадают в один и тот же канал более одного раза.

                                      L_i0

                                                                                      1                              1

                                                                                       L_i1

       L_i                                                            . . .            L_ij                   . . .                                           L_j

 

                                                                              . . .                             . . .

                                                                 L_in

                                                                                      n                                 n

 

p ₀₀  = 0

 

      n

p _{i 0} = S l_i(k, i) / L_i

     k=1

                                                                               (i, j = 1, n)

        n

p _{0 j} = S l₀(j, l) / L₀

     l=1

 

        n n

p _{i j} = S  S l_{i j}(k, l) / L_i = L_{i j}  / L_i

     k=1 l=1

        l¹k

 

l_i(k, i) - интенсивность потока сообщений, покидающих узел i;

l₀(j, l) - интенсивность потока сообщений, поступающих от абонентов в узел j;

L₀  - суммарная интенсивность потока сообщений от всех абонентов сети.

 

                                                                n

l_j = S l_i *  p _{i j}    (j = 0, n).

                                                    i=0

 

 

Задача оптимизации пропускных способностей в СПД

 

Задача оптимизации заключается в определении пропускных способностей всех каналов связи, обеспечивающих требуемое качество функционирование СПД.

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

Ограничение обычно задается на среднее время доставки сообщения Т <= Т^*, где Т^* - допустимое время доставки сообщения. Иногда ограничение задается в вероятностном виде Р(Т > Т^*) < Р^*.

В качестве критерия эффективности используется стоимость СПД, которая складывается из стоимостей отдельных каналов связи

 

                                                     n

S = S S_i , где S_i - стоимость КС_i.

                                          i=1

 

Стоимость КС_i зависит от пропускной способности V_i и длины КС_i и определяется по формуле

S_i  = k_i * V_i ,

 

где k_i - стоимостной коэффициент, зависящий от типа КС и его длины.

 

Задача оптимизации.

Первая постановка задачи. Определить пропускные способности всех КС, обеспечивающие ограничение на время доставки сообщений при минимальной стоимости сети: V_i (i = 1, n) Þ T <= T ^* при S  - min.

Вторая постановка задачи. Определить пропускные способности всех КС, обеспечивающие ограничение на стоимость сети при минимальном времени доставки сообщений: V_i (i = 1, n) Þ S <= S ^* при Т  - min.

 

 

Первая постановка задачи

Дано:

1) n - количество КС (зависит от топологии, количества УС и типов КС);

2) l₀ - суммарная интенсивность поступления сообщений в сеть от всех абонентов;

3) l₁ , …, l_n - средняя длина сообщений, передаваемых в сети;

4) a₁ , …, a_n - коэффициенты передач для РСеМО, показывающие сколько раз в среднем каждое сообщение попадает в КС_i;

5) T ^* - ограничение на время доставки сообщений;

6) k₁ , …, k_n - стоимостные коэффициенты КС_i.

 

Определить:

V_i (i = 1, n) Þ T <= T ^* при S  - min.

 

Задача решается методом неопределенных множителей Лагранжа. Предположим, что моделью СПД является экспоненциальная однородная РСеМО.

 

Решение:

1. Определение основных соотношений.

 

                                                                    n        n

S = S S_i = S k_i * V_i

                                                       i=1    i=1

 

                                               n                 n

T = å a_i * U_i = å a_i b_i /(1 - r_i )

                                                                                         i=1             i=1

Расчет экспоненциальной РСеМО может быть сведен в соответствии с эквивалентным преобразованием к расчету отдельных узлов (СМО) сети, которые рассматриваются как СМО типа М/М/1. Для М/М/1 U_i = b_i /(1 - l_i* b_i ), где b_i = l_i / V_i, r_i = l_i b_i =a_i l₀ b_i = a_i l₀ l_i / V_i Þ

                                                       n                n

T = U = å a_i * U_i = å a_i l_i / (V_i  -  a_i  l₀ l_i).

                                                                                     i=1             i=1

 

2. Математическая оптимизация с использованием метода неопределенных множителей Лагранжа.

Для этого запишем функцию Лагранжа

 

G = S + g * (T – T^*) – min, dG/dV_i = 0 (i = 1, n),

 

S - величина, которую минимизируют;

T - величина, на которую задано ограничение;

g - неопределенный множитель Лагранжа, который находится в процессе оптимизации.

 

                                 n                         n

G  = S k_i * V_i + g * (å a_i l_i / (V_i  -  a_i  l₀ l_i) – T^*).

                                                                i=1                     i=1

 

Необходимо минимизировать функцию Лагранжа (T – T^*) Þ 0. Для этого необходимо найти частные производные по V_i.

 

dG/dV_i = k_i - g * (a_i l_i / (V_i  -  a_i  l₀ l_i)² = 0 (i = 1, n)

(система независимых уравнений)

 

 

                                                                                          n

V_i = Ö g * a_i l_i / k_i +  a_i  l₀ l_i, T = T^*, å a_i l_i / Ö g * a_i l_i / k_i = T^*Þ

                                                                                                                                            i=1

                                                                    n

Ö g = 1 / T^*   åÖ k_i a_i l_i

                                                                                 i=1

 

                                                                    n

V_i = 1 / T^* Ö a_i l_i / k_i åÖ k_j a_j l_j +  a_i  l₀ l_i  (i = 1, n),

                                                                   j=1

V_{i min} =  a_i l₀ l_i - пропускная способность, необходимая для обеспечения стационарного режима;

DV_i = V_i - V_{i min} - добавка к V_{i min} для обеспечения T^*;

V_i тем больше, чем меньше T^*, чем больше  a_i и l_i, чем меньше k_i. Для КС_i с большим k_i не выгодно добавлять быстродействие, так как это будет очень дорого.

V_i определяется min значением V_{i min} для обеспечения работы в стационарном режиме и добавкой DV_i для обеспечения заданного ограничения на время доставки сообщения T^*.

Вторая постановка задачи

Дано:

1) n - количество КС (зависит от топологии, количества УС и типов КС);

2) l₀ - суммарная интенсивность поступления сообщений в сеть от всех абонентов;

3) l₁ , …, l_n - средняя длина сообщений, передаваемых в сети;

4) a₁ , …, a_n - коэффициенты передач для РСеМО, показывающие сколько раз в среднем каждое сообщение попадает в КС_i;

5) S ^* - ограничение на стоимость СПД;

6) k₁ , …, k_n - стоимостные коэффициенты КС_i.

 

Определить :

V_i (i = 1, n) Þ S <= S ^* при T  - min.

Решение :

G = T + g * (S – S^*) – min, dG/dV_i = 0 (i = 1, n),

T - величина, которую минимизируют;

S - величина, на которую задано ограничение;

g - неопределенный множитель Лагранжа, который находится в процессе оптимизации.

                                  n                                                 n

G  = å a_i l_i / (V_i  -  a_i  l₀ l_i) + g *(S k_i * V_i– S^*).

                                                                 i=1                                             i=1

 

Необходимо минимизировать функцию Лагранжа (T – T^*) Þ 0. Для этого необходимо найти частные производные по V_i.

 

dG/dV_i = - a_i l_i / (V_i  -  a_i  l₀ l_i)² + g*k_i = 0 (i = 1, n)

(система независимых уравнений)

 

                                                                                   n

V_i = Ö a_i l_i / g k_i +  a_i  l₀ l_i, S = S^*, å k_i (Ö a_i l_i / g k_i +  a_i  l₀ l_i ) = S^*Þ

                                                                                                                                 i=1

                                                          n                   n

1 / Ö g = (S^* - å k_i a_i l₀ l_i) / åÖ k_i a_i l_i

                                                                     i=1                i=1

 

                                           n                                n

V_i = Ö a_i l_i (S^* - å k_j a_j l₀ l_j) /  (Ök_i åÖ k_j a_j l_j) +  a_i  l₀ l_i  (i = 1, n),

                                          j=1                            j=1

V_{i min} =  a_i l₀ l_i - пропускная способность, необходимая для обеспечения стационарного режима;

DV_i = V_i - V_{i min} - добавка к V_{i min} для обеспечения S^*;

(S – S^*) - это избыток распределяемых средств. Чем чаще используется КС_i (чем больше a_i), чем длиннее сообщение l_i, чем меньше стоимостной коэффициент k_i , тем больше средств предоставляется для данного КС_i.