<< prev | ^up^ | next >>

3.4. Задача РП(распределение потоков).

Имеется коммуникационная сеть:

                                    Задана структура сети G = (X,E), матрица Н =  

и пропускные способности всех КС  Надо

найти такой МП-поток F = , для которого

задержка минимальна:

Т_ср= 1/h_å(f_rs/(m_rs - f_rs) Rmin                                (3.6)

при условии, что F = [f_rs] - МП поток, совместимый с матрицей Н  и f_rs < m_rs

Л. Клейнрок  получил условие оптимальности текущего потока F^*= [f_rs^*]:

,  где v_rs - поток по кратчайшим путям в метрике l_rs =

3.4.1. Метод отклонения потоков:

Алгоритм РП:

Включает два этапа:

1)   предварительный;

2)   основной - состоит из однотипных итераций по оптимизации текущего потока.

Предварительный этап состоит в нахождении начального допустимого потока.

Основной этап (k+1) итерации:

1) Находим условные длины каналов или дуг: l_rs = ½

T_ср =  ;                ½ =

2)   Находим кратчайшие пути вданной метрике: пусть - кратчайший путь между i и j, длина этого пути: l( ), для этого используем специальный алгоритм.

3)   Находим поток V_k= [v_rs^k] по кратчайшим путям, для чего используем специальный алгоритм.

4)   Находим оценочные коэффициенты для старого и нового потоков:

 - для старого потока

b_k= - для нового потока по кратчайшим путям.

Условие оптимальности потока

5)   Проверяем условие:

если £e, где  e- заданная точность, то конец - поток F(k)- оптимальный, иначе на шаг 6)

6)   Состовляем комбинацию нового и старого потоков:

, где lÎ[0;1]

Ищем такое  l^*, для которого Т_ср (F¢(l)) Rmin - любым методом одномерной оптимизации, например,  Фибоначчи.

7)   F(k+1) =(F¢(l^*))

k=k+1 Rпереход к следующей итерации