Optimizarea retelelor multipunct
Formularea problemei
Se examinează RTD
centralizate specifice R abonat, teleprelucrare D: mesajele se transmit de la
staţii-terminal la centru şi invers; centrul poate fi concentrator, nod de
comunicaţie al RTD magistrale, staţie-server de prelucrare a D. Pentru a reduce
costurile la canale de comunicaţie se pot folosi canale TD punct la punct si
canale multipunct. La unul multipunct se pot conecta mai multe staţii, şi doar
2 noduri.
Problema optimizării
Cunoaştem
amplasarea geografică a staţiilor, rata fluxului D (date) între fiecare staţie şi
centru, costul canalelor: determinăm schema de conectare optimală a staţiilor
prin canale multipunct cu centrul; minimizăm costul sumar al canalelor în R (retea)
conform restricţiilor: durata reţinerii pachetelor în R, asigurarea fiabilităţii
(2 căi independente de TD (transfer date) între oricare pereche de noduri – inel, plasă; nr. de
staţii deconectate la defectarea unui nod să nu depăşească o mărime anume – R
de concentratoare şi multipunct).
Algoritmi
Optimali –
soluţionare exactă a problemei: Chandy-Russel;
Euristici – nu
garantează obţinerea soluţiei optime, dar realizează o căutare orientată a ei;
mai puţine calcule, se deosebeşte de soluţia optimală cu 5-10%: Essau, Williams, Prim, Kruskal, Kershenbaum-Chou;
Essau-Williams – determinarea celor mai îndepărtate de centru
noduri şi conectarea lor cu cele mai apropiate de ele noduri;
Prim – din contra, determinarea celor mai apropiate de centru noduri şi
conectarea lor la cele mai apropiate de ele noduri;
Kruskal – în R se introduc consecutiv cele mai ieftine segmente de canale;
Kershenbaum-Chou – euristic, este o modificare a Kruskal:
introducerea consecutivă a segmentelor in ordinea creşterii diferenţei dintre
costul segmentelor şi ponderea nodurilor ce se conectează la acestea;
Chandy-Russel – din mulţimea de soluţii admise ce satisfac
restricţia privind rata limită a fluxului sumar de D pe canal se selectează
anumite submulţimi de dimensiuni mai mici şi se verifică dacă una din ele
asigură atingerea cu hotarul de jos privind valoarea criteriului optim
determinata de arborele minim; dacă e atins hotarul atunci soluţia optimă s-a
obţinut.
R-retea
T-tranfer
D-date
