Probabilistyczna generacja selektorów dla algorytmów komunikacji grupowej w sieciach radiowych

• Autorzy: Białogrodzki J.

Warianty tytułu

EN

Randomized generation of selectors for group communication algorithms in radio networks

• Konferencja: XV Krajowa Konferencja Automatyzacji Procesów Dyskretnych, Zakopane, 20-23 września 2006r.
• Języki publikacji: PL

Abstrakty

PL

Selektory to obiekty matematyczne wykorzystywane przez kilka zaawansowanych algorytmów komunikacji grupowej dla sieci radiowych. Należy do nich algorytm Chrobak-Gąsieniec-Rytter (CGR), asymptotycznie najefektywniejszy algorytm rozsyłania dla sieci radiowych o nieznanej topologii. Artykuł proponuje prostą, probabilistyczną metodę konstrukcji odpowiednich rodzin selektorów oraz prezentuje wyniki symulacji CGR mających na celu ustalenie, w jakim stopniu wybór konkretnej rodziny wpływa na efektywność algorytmów.

EN

Selectors are mathematical objects used by several advanced group communication algorithms for radio networks. Those include Chrobak-Gąsieniec-Rytter (CGR) algorithm, which is asimptotically the most efficient broadcasting algorithm for unknown topology radio networks. The article proposes randomized method of appropriate selectors and selector families construction, as well as presents the results of CGR simulations carried out to determine whether the choice of selectors family affects the efficiency of algorithms.

Słowa kluczowe

PL

komunikacja grupowa; sieć radiowa; selektor; algorytm CGR

EN

group communication; radio networks; selector; CGR algorithm

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Zeszyty Naukowe. Automatyka / Politechnika Śląska
• Rocznik: 2006
• Tom: z. 143
• Strony: 11--19
• Opis fizyczny: Bibliogr. 9 poz.

Twórcy

autor

Białogrodzki J.

• Wydział Fizyki Technicznej i Matematyki Stosowanej Politechniki Gdańskiej, 80-952 Gdańsk Wrzeszcz, ul. Gabriela Narutowicza 11/12, tel.: [phone],

Bibliografia

• 1. Białogrodzki J.: Implementacja algorytmów rozsyłania i plotkowania w sieciach radiowych. Politechnika Gdańska 2004. Praca magisterska.
• 2. Brusem D., Del Pinto M.: Lower bounds for the broadcast problem in mobile radio networks. Distributed Computing, 10, 1997, p. 129-135.
• 3. Chlamtac I., Kutten S.: On broadcasting in radio networks - problem analysis and protocol design. IEEE Transactions on Communications, 33, 1985, p. 1240-1246.
• 4. Chlebus B.S., Gąsieniec L., Ostlin A., Robson J.M.: Deterministic radio broadcasting. Proc. 27th International Colloquium on Automata, Languages and Programming (ICALP), 2000, p. 717-728.
• 5. Chlebus B.S., Gąsieniec L., Gibbons A.M., Pelc A., Rytter W.: Deterministic broadcasting in unknown radio networks. Proc. 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2000, p. 861-870.
• 6. Chrobak M., Gąsieniec L., Rytter W.: Fast broadcasting and gossiping in radio networks. Proc. 41st IEEE Symposium on Foundations of Computer Science (FOCS), 2000, p. 575-581.
• 7. De Marco G., Pelc A.: Faster broadcasting in unknown radio networks. 1999. Nie publikowane.
• 8. Gallager R.: A perspective on multiaccess channels. IEEE Transactions on Information Theory, 31, 1985, p. 124-142.
• 9. Indyk P.: Explicit constructions of selectors and related combinatorial structures with applications. Proc. 13th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2002, p. 697-703.