Efektywne szukanie stacji w sieciach o topologii kraty

• Autorzy: Rajba, P.

Warianty tytułu

EN

Problem of finding the farthest neighbours for a selected station in a radio network

• Języki publikacji: PL

Abstrakty

PL

W pracy przedstawiono problem znajdowania najbardziej odległych sąsiadów dla wybranej stacji w sieci radiowej, w której stacje (z nadajnikami o jednakowej mocy) sa˛ rozmieszczone na kracie, tj. w punktach o współrzędnych całkowitych. Zaprezentowany algorytm działa w czasie O(R), gdzie R jest zasięgiem stacji.

EN

In this paper we present the problem of finding the farthest neighbours for a selected station in a radio network. The stations (with transmitters having identical range) are localized on a grid, i.e. the vertices have integer origins. The presented algorithm completed its work in time L(R), where R is a radius of the station.

Słowa kluczowe

PL

sieć radiowa; system rozproszony; algorytm losowy; rozgłaszanie

EN

radio network; distributed system; broadcasting; probabilistic algorithm

• Czasopismo: Przegląd Elektrotechniczny
• Rocznik: 2009
• Tom: R. 85, nr 4
• Strony: 108-115
• Opis fizyczny: Bibliogr. 38 poz., rys., wykr.

Twórcy

autor

Rajba, P.

• Uniwersytet Wrocławski,

Bibliografia

• [1] Angel O., Benjamini I., Ofek E., Wieder U. Routing complexity of faulty networks, Random Structures & Algorithms, Vol. 32, Issue 1 (2008) 71–87
• [2] Alon N., Bar-Noy A., Linial N., Peleg D., A lower bound for radio broadcast, Journal of Computer and System Sciences, Vol. 43, No. 2 (1991), 290–298.
• [3] Bar-Yehuda R., Goldreich O., Itai A., On the timecomplexity of broadcast in multi-hop radio networks: an exponential gap between determinism and randomization, Journal of Computer and System Sciences, Vol. 45, No. 1 (1992), 104–126.
• [4] Basagni S., Bruchi D., Chlamtec I., A mobilitytransparent deterministic broadcast mechanism for ad hoc networks, IEEE/ACM Trans. on Networking 7(1999), 799–807.
• [5] Bordim J.L., Cui J., Hayashi T., Nakano K., Olariu S. Energy-Efficient Initialization Protocols for Ad-hoc Radio 114 PRZEGLĄD ELEKTROTECHNICZNY (Electrical Review), ISSN 0033-2097, R. RR NR 4/2009 Networks, Algorithms and Computation, Volume 1741 (1999),215–224
• [6] Bruschi D., Del Pinto M., Lower bounds for the broadcast problem in mobile radio networks, Distr. Comp. 10 (1997), 129–135.
• [7] Caragiannis I., Kaklamanis C., Kanellopoulos P., New results for energy-efficient broadcasting in wireless networks, ISAAC, LNCS 2518 (2002), 332–343.
• [8] Chlamtac I., Weinstein O., The wave expansion approach to broadcasting in multihop radio networks, IEEE Trans. on Communications 39 (1991), 426–433.
• [9] Chlebus B.S., Gąsieniec L., Gibbons A., Pelc A.,Rytter W., Deterministic broadcasting in unknown radio networks, Distributed Computing 15 (2002), 27–38.
• [10] Chlebus B.S., Gąsieniec L., Östlin A., Robson J. M., Deterministic Radio Broadcasting, Proceedings of the 27th International Colloquium on Automata, Languages and Programming (2000), 717–728.
• [11] Chrobak M., Gąsieniec L., Rytter W., Fast broadcasting and gossiping in radio networks, Proceedings of the 41st Annual Symposium on Foundations of Computer Science (2000), 575–581.
• [12] Clementi A.E. F., Monti A., Silvestri R., Distributed broadcast in radio networks of unknown topology, Theoretical Computer Science, Vol. 302 No. 1–3 (2003), 337–364.
• [13] Clementi A.E. F., Monti A., Silvestri R., Selective families, superimposed codes, and broadcasting on unknown radio networks, Proceedings of the twelfth annual ACM-SIAM Symposium on Discrete Algorithms (2001), 709–718.
• [14] Czumaj A., Rytter W., Broadcasting Algorithms in Radio Networks with Unknown Topology, In Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (2003), 492–501.
• [15] Dessmark A., Pelc A., Broadcasting in geometric radio network, Journal of Discrete Algorithms, Vol, 5, Issue 1 (2007) 187–201
• [16] Draves R., Padhye J., Zill B. Routing in multi-radio, multi-hop wireless mesh networks, Proceedings of the 10th annual international conference on Mobile computing and networking (2004) 114–128
• [17] Elkin M., Kortsarz G., An improved algorithm for radio broadcast, ACM Transactions on Algorithms, Vol. 3, Issue 1, 8 (2007).
• [18] Elkin M., Kortsarz G., Polylogarithmic Additive Inapproximability of the Radio Broadcast Problem, SIAM Journal on Discrete Mathematics, Vol. 19, No. 4 (2005) 881–899.
• [19] Elkin M., Kortsarz G. Logarithmic inapproximability of the radio broadcast problem, Journal of Algorithms, Vol. 52, Issue 1 (2004), 8–25
• [20] Gaber I., Mansour Y., Broadcast in radio networks, Proc. 6th Ann. ACM-SIAM Symp. on Discrete Algorithms (1995), 577–585.
• [21] Gandhi R., Mishra A., Par thasarathy S. Minimizing Broadcast Latency and Redundancy in Ad Hoc Networks, Networking, IEEE/ACM Transactions on, Vol. 16, Issue 4 (2008) 840–851
• [22] Gąsieniec L., Peleg D., Xin Q. Faster communication in known topology radio networks, Distributed Computing, Vol, 19, No. 4 (2007) 289–300
• [23] Hadzilacos V., Toueg S., Fault-tolerant broadcasts and related problems, Distributed Systems (1993), 97–145.
• [24] Indyk P., Explicit constructions of selectors and related combinatorial structures, with applications, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms (2002) 697–704.
• [25] Jurdzinski T., Stachowiak G. Probabilistic Algorithms for the Wakeup Problem in Single-Hop Radio Networks, Proceedings of the 13th International Symposium on Algorithms and Computatio (2002) 535–549
• [26] Kowalski D., Pelc A., Deterministic broadcasting time in radio networks of unknown topology, Proc 43rd Ann. IEEE Sump. on Foundations of Computer Science (2002), 63–72.
• [27] Kowalski D., Pelc A., Broadcasting in undirected ad hoc radio networks, Proc. 22-nd ACM Symposium on Principles of Distributed Computing (2003), 73–82.
• [28] Kowalski D., Pelc A., Faster deterministic broadcasting in ad hoc radio networks, Proc. 20-th Annual Symposium on Theoretical Aspects of Computer Science (2003), LNCS 2607, 109–120.
• [29] Kowalski D., Pelc A., Centralized deterministic broadcasting in undirected multi-hop radio network, In Approximation, Randomization, and Combinatorial Optimization, (2004) Springer-Verlag, 171–182.
• [30] Kowalski D., Pelc A., Optimal Deterministic Broadcasting in Known Topology Radio Networks, Distributed Computing, Vol. 19, No. 3 (2007) 185–195
• [31] Kushilevitz E., Mansour Y., A Lower Bound for Broadcast in Radio Networks, SIAM Journal on Computing, Vol. 27 3 (1998), 702–712.
• [32] DeMarco G., Pelc A., Deterministic Broadcasting Time with Partial Knowledge of the Network, ISAAC, LNCS 1969 (2000), 374–385.
• [33] Murthy S., Garcia-Luna-Aceves J. J. A routing protocol for packet radio networks, Proceedings of the 1st annual international conference on Mobile computing and networking (1995) 86–95
• [34] Nosarzewska M., Evaluation de la difference entre l’aire d’une région plane convexe et le nombre des points aux coordomnées entières couverts par elle, Colloq. Math., 1 (1948), 305–311.
• [35] Rajba P., Fast broadcasting in grid networks, w przygotowaniu.
• [36] Williams B., Camp T., Comparison of broadcasting techniques for mobile ad hoc networks, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking and computing (2002).
• [37] Xu Y. Deterministic Gossiping Algorithm for Radio Networks, Algorithmica, Vol. 36, No. 1 (2008) 93–96
• [38] Zhang Q., Agrawal D. P., Dynamic probabilistic broadcasting in MANETs, Journal of Parallel and Distributed Computing, Vol. 65, Issue 2 (2005), 220–23