Protokoly s omezenými kolizemi (limited-contention protocols)
- kombinují malé zpožděné ALOHA při nízké zátěži s efektivním využitím
kanálu při vysoké zátěži.
Aby byla pravděpodobnost kolize nízká, musí být soupeřících stanic
velmi málo.
Dá se odvodit, že pro optimálně stanovenou pravděpodobnost vysílání je
pravděpodobnost úspěchu při soutěžení ((k-1)/k)^(k-1), kde k je počet
stanic.
Z průběhu této funkce je zřejmé, že pravděpodobnost úspěchu je rozumná,
pokud o slot soutěží max. 5 stanic.
Stanice se tedy rozdělí do disjunktních skupin, jen první skupina
smí
soutěžit
o první slot, druhá o druhý, ...
Otázka, kolik stanic nechat soutěžit o jeden slot: extrémy:
1->žádné
kolize, všechny->aloha Nutnost přiřazovat počty stanic soupeřících o
Adaptive Tree Walk Protocol
Stanice se uvažují jako listy binárního stromu, v prvním slotu smí
vysílat všechny stanice, pokud není kolize, OK, pokud je, smí o další
slot soutěžit jen stanice v levém podstromu kořene, pokud bez kolize,
další rámec vyhrazen i
stanicím v pravém podstromu kořene, jinak stanicím levého podstromu
levého stromu. Prohledávání do hloubky, až se najdou všechny stanice
snažící se vysílat.
Každý slot je vyhrazen určitému uzlu ve stromu. Jestliže byl slot
prázdný nebo se úspěšně přenesl rámec, prohledávání do hloubky se
zastaví, protože byly nalezeny všechny stanice podstromu, které chtěly
vysílat (jinak by došlo ke kolizi).
Problém, ve které úrovni stromu začít s přidělováním slotu (nemá smysl
přiřadit kořen jednomu slotu, protože by byl stejně skoro vždy
zkolidovaný). Počáteční úroveň, na kolik soutěžících skupin (podstromů)
rozdělit, se optimalizuje podle zátěže:
Každý uzel na úrovni i (root je úroveň 0) má pod sebou 2^(-i)*100%
procent uzlů. Pokud je q připravených stanic ve stromě rozložených
rovnoměrně, očekávaný počet stanic pod uzlem v úrovni i je 2^(-i)*q.
Hledáme úroveň, kde tento očekávaný počet bude 1, řešíme rovnici
2^(-i)*q=1, tedy i=log2(q).