Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
1.2.Przykładyzastosowańgrafów
11
fliktgłównywystępowałbyrównieżwtedy,gdybywęzłyv
1iv
3jednocześnienada-
wałydov
2.
-jeżelistacjaodbieraodpewnegonadajnika,tożadeninnynadajnik,wktórego
zasięguznajdujesiętastacja,niemożewtymczasienadawać(jesttotzw.konflikt
drugorzędny).Narysunku1.9bjestprzedstawionykonfliktdrugorzędny:v
1nadajedo
v
2,av
3dov
4,alev
2jestwzasięgutransmisjistacjiv
3.Gdybytatransmisjabyłaprze-
znaczonadostacjiv
2,towystępowałbykonfliktgłówny.Takwięckonfliktygłówne
idrugorzędneróżniąsięadresatemtransmisji.
Rys.1.9.Przykładykonfliktówwpakietowychsieciachradiowych:a)konfliktgłówny;
b)konfliktdrugorzędny
Wceluuniknięciakonfliktówstosujesięmetodykontrolidostępudopasmara-
diowego.TDMA(ang.TimeDivisionMultipleAccess)jestsystememzwielodostępem
czasowym.Czasjestdzielonynaodcinki(szczelinyczasu),powtarzanecyklicznie
wtzw.cykluTDMA.Każdazestacjimaprzydzielonąszczelinęczasową,wtrakcie
którejmożenadawać.Przydziałszczelinmazapewnić,żeniepojawiąsiękonflikty
główneidrugorzędne.LiczbaszczelincykluTDMApowinnabyćzminimalizowana,
gdyżzapewniatowiększąprzepustowośćsieci.
Modelsiecitograf,wktórymwierzchołkiodpowiadająstacjom,awierzchołki
v,usąpołączonełukiem(v,u)wtedy,gdyujestwzasięgustacjiv.Należyzaprojekto-
waćnajkrótszyzmożliwych,wolnyodkonfliktów,cykliczniepowtarzanyharmono-
gramnadawaniastacji.Jakoprzykładrozpatrzmysiećostrukturzepierścieniowej,
złożonązsześciustacji(rys1.10a),osymetrycznychzasięgachstacji,tzn.jeżelista-
cjavleżywzasięgustacjiu,torównieżstacjauleżywzasięgustacjiv.Modeltakiej
siecijestwięcgrafemniezorientowanym.
Rozwiązanie
WceluuniknięciakonfliktówgłównychidrugorzędnychprzekształcimygrafGre-
prezentującysiećwnastępującysposób:wierzchołkiGodległeo2(tj.przedzielone
jednymwierzchołkiem)połączymydodatkowymikrawędziamiprzedstawionymi
przerywanąliniąnarys.1.10b.Otrzymanygrafjesttzw.kwadratemG
2grafuorygi-
nalnego(p.rozdz.10).Zagadnienieminimalizacjiliczbyszczelinczasowychmożna
sprowadzićdozadaniakolorowaniawierzchołkówgrafu,tj.przydziałuminimalnej
