Eng | Rus | Ukr
Компьютерные сети
16.01.2005

<< prev | ^up^ | next >>

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

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

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

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

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

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

Тср= 1/hå(frs/(mrs - frs) Rmin                                (3.6)

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

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

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

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

Алгоритм РП:

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

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

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

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

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

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

Tср =  ;                ½ =

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

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

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

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

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

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

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

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

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

, где lÎ[0;1]

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

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

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

<< prev | ^up^ | next >>

 
     
  Copyright © 2002-2004