Теориялық бөлім. Егер желі екі иерархиялық деңгейінен құрылған болса оны

Егер желі екі иерархиялық деңгейінен құрылған болса оны орталықтандырылған деп атайды:

- концентраторларға жалғанатын терминалдар Т_i;

- орталық ЭЕМ жалғанатын концентраторлар К_j.

Терминалдар мен концентраторлар орналасуы мен сандары белгілі. Оларды байланыстыратын желіні құру қажет.

Синтез есебінің оңайлатылған варианты

Осы желіні бір деігейлі желімен ауыстыру көмегімен оңайлатып, яғни біріншіден терминаладрды концентраторларға жалғап, одан кейін концентраторларды ЭЕМ-на. Есептің келесі қойылуын қарастырайық: берілген генераторлар көпшілікті (ақпарат көзі) S_i, i=1,..., n, ақпарат қабылдағышпен S_o минималды бағалы желімен байланыстыру. Ақпарат көздері S_i өзара жалғасуы мүмкін.

S_i және S_j, байланыстыру бағалары C_ij, өткізу қабілеттіктері r_ij, ақпарат көздерінің интенсивтіліктері а_i және сток интенсивтілігі

а_о= - а_i

берілген.

Негізгі мәліметтер кестелерде берілген.

Егер барлық жолдар үшін өткізу қабілетіктер бірдей болса (S_i, S_j), r_ij =R саны беріледі.

2 –кесте. Жалғанулар бағалары

Сij	S0	S1	-	Sn
S1	C10	-	-	C1n
S2	C20	C21	-	C2n
-	-	-	-	-
Sn	Cn0	Cn1	-	-

3 – кесте. Өткізу қабілеттіліктері

rij	S0	S1	- -	Sn
S1	r10	-	- -	r1n
S2	r20	r21	- -	r2n
-	-	-	- -	-
Sn	rn0	rn1	- -	-

Ежи – Вильямс алгоритмі

Алгоритм негізінде алытсалған түйіндерді анықтап көршілес түйіндермен байланыстыру жатады.

0 қадам. Белгіленулер жүйесі есептеледі.

t_ij= C_ij- C_io барлық үшін i, j N, i j (2.1)

t_ij параметрі i және j түйіндерді байланыстыру бағасын сипаттайды.

1 қадам. Минималды t_ij таңдалады

{t_ij}= t_kl.

Егер t_kl <0, 2 қадам есептеледі, егер t_kl 0- 4 қадам.

2 қадам. Келесі шарттарды а_k>0 (ақпаратты беру керек пе?) және а_k r_kl; (а_k+ а_l) r_lo (бос өткізу қабілеттігі бар ма).

Шарттар орындалса 3 қадамы есептеледі, қарсы жағдайда t_kl тең болады, 1 қадамды орындау қажет.

3 қадам. Егер t_kl <0, S_k және S_l қосылады және көрсеткіштер есептеледі:

а_k¹=0 а_l¹= a_l+a_k

r_kl=r- а_k

F¹ =F+ С_kl.

4 қадам. Егер минималды t_kl 0, S_k түйіні S₀ қосылады.

Дата добавления: 2015-07-11