×

zbMATH — the first resource for mathematics

Fast size approximation of a radio network in beeping model. (English) Zbl 1437.68013
Summary: In a single-hop radio network, nodes can communicate with each other by broadcasting to a shared wireless channel. In each time slot, all nodes receive feedback from the channel depending on the number of transmitters. In the Beeping Model, each node learns whether zero or at least one node have transmitted. In such a model, a procedure estimating the size of the network can be used for efficiently solving the problems of leader election or conflict resolution. We introduce a time-efficient uniform algorithm for size estimation of single-hop networks. With probability at least \(1 - 1 / f\) our solution returns \((1 + \varepsilon)\)-approximation of the network size \(n\) within \(\mathcal{O} ( \log \log n + \log f / \varepsilon^2 )\) time slots. We prove that the algorithm is asymptotically time-optimal in a class of uniform algorithms.
MSC:
68M10 Network design and communication in computer systems
68M12 Network protocols
68M14 Distributed systems
68W15 Distributed algorithms
68W25 Approximation algorithms
Software:
HyperLogLog
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Afek, Y.; Alon, N.; Bar-Joseph, Z.; Cornejo, A.; Haeupler, B.; Kuhn, F., Beeping a maximal independent set, Distrib. Comput., 26, 4, 195-208 (2013) · Zbl 1311.68024
[2] Baignères, T.; Sepehrdad, P.; Vaudenay, S., Distinguishing distributions using Chernoff information, (International Conference on Provable Security (2010), Springer), 144-165 · Zbl 1286.94043
[3] Bordim, J. L.; Cui, J.; Hayashi, T.; Nakano, K.; Olariu, S., Energy-efficient initialization protocols for ad-hoc radio networks, (Algorithms and Computation (1999), Springer), 215-224 · Zbl 0970.68631
[4] Caragiannis, I.; Galdi, C.; Kaklamanis, C., Basic computations in wireless networks, (Deng, X.; Du, D., Algorithms and Computation, 16th International Symposium. Algorithms and Computation, 16th International Symposium, ISAAC 2005, Sanya, Hainan, China, December 19-21, 2005, Proceedings. Algorithms and Computation, 16th International Symposium. Algorithms and Computation, 16th International Symposium, ISAAC 2005, Sanya, Hainan, China, December 19-21, 2005, Proceedings, Lecture Notes in Computer Science, vol. 3827 (2005), Springer), 533-542 · Zbl 1173.68382
[5] Chakrabarti, A.; Regev, O., An optimal lower bound on the communication complexity of gap-hamming-distance, (Fortnow, L.; Vadhan, S. P., Proceedings of the 43rd ACM Symposium on Theory of Computing. Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June, 2011 (2011), ACM), 51-60 · Zbl 1288.90005
[6] Chassaing, P.; Gerin, L., Efficient estimation of the cardinality of large data sets, (4th Colloquium on Mathematics and Computer Science (2006), DMTCS Proceedings), 419-422 · Zbl 1191.68378
[7] Chen, B.; Zhou, Z.; Yu, H., Understanding RFID counting protocols, (Helal, S.; Chandra, R.; Kravets, R., The 19th Annual International Conference on Mobile Computing and Networking. The 19th Annual International Conference on Mobile Computing and Networking, MobiCom’13, Miami, FL, USA, September 30 - October 04, 2013 (2013), ACM), 291-302
[8] Cichoń, J.; Lemiesz, J.; Szpankowski, W.; Zawada, M., Two-phase cardinality estimation protocols for sensor networks with provable precision, (Proceedings of WCNC’12 (2012), IEEE: IEEE Paris, France)
[9] Cichoń, J.; Lemiesz, J.; Zawada, M., On size estimation protocols for sensor networks, (Proceedings of the 51th IEEE Conference on Decision and Control. Proceedings of the 51th IEEE Conference on Decision and Control, CDC 2012, December 10-13, 2012, Maui, HI, USA. Proceedings of the 51th IEEE Conference on Decision and Control. Proceedings of the 51th IEEE Conference on Decision and Control, CDC 2012, December 10-13, 2012, Maui, HI, USA, Proceedings of 51st Annual Conference on Decision and Control (CDC) (2012), IEEE), 5234-5239
[10] Cornejo, A.; Kuhn, F., Deploying wireless networks with beeps, (DISC (2010)), 148-162 · Zbl 1290.68020
[11] Cover, T. M.; Thomas, J. A., Elements of Information Theory (2006), John Wiley & Sons · Zbl 1140.94001
[12] Flajolet, P.; Fusy, E.; Gandouet, O.; Meunier, F., Hyperloglog: the analysis of a near-optimal cardinality estimation algorithm, (Proceedings of the Conference on Analysis of Algorithms. Proceedings of the Conference on Analysis of Algorithms, AofA’07 (2007)), 127-146 · Zbl 1192.68959
[13] Flajolet, P.; Martin, G. N., Probabilistic counting algorithms for data base applications, J. Comput. System Sci., 31, 2, 182-209 (1985) · Zbl 0583.68059
[14] Giroire, F., Order statistics and estimating cardinalities of massive data sets, Discrete Appl. Math., 157, 2, 406-427 (2009) · Zbl 1169.68054
[15] Greenberg, A. G.; Flajolet, P.; Ladner, R. E., Estimating the multiplicities of conflicts to speed their resolution in multiple access channels, J. ACM, 34, 2, 289-325 (April 1987)
[16] Han, H.; Sheng, B.; Tan, C. C.; Li, Q.; Mao, W.; Lu, S., Counting RFID tags efficiently and anonymously, (INFOCOM 2010. 29th IEEE International Conference on Computer Communications, Joint Conference of the IEEE Computer and Communications Societies. INFOCOM 2010. 29th IEEE International Conference on Computer Communications, Joint Conference of the IEEE Computer and Communications Societies, 15-19 March, 2010, San Diego, CA, USA (2010), IEEE), 1028-1036
[17] Jurdziński, T.; Kutyłowski, M.; Zatopianski, J., Energy-efficient size approximation of radio networks with no collision detection, (Proceedings of COCOON ’02 (2002), Springer-Verlag), 279-289 · Zbl 1077.90513
[18] Kabarowski, J.; Kutyłowski, M.; Rutkowski, W., Adversary immune size approximation of single-hop radio networks, (Theory and Applications of Models of Computation. Theory and Applications of Models of Computation, LNCS, vol. 3959 (2006), Springer), 148-158 · Zbl 1178.68037
[19] Kodialam, M. S.; Nandagopal, T., Fast and reliable estimation schemes in RFID systems, (Gerla, M.; Petrioli, C.; Ramjee, R., Proceedings of the 12th Annual International Conference on Mobile Computing and Networking. Proceedings of the 12th Annual International Conference on Mobile Computing and Networking, MOBICOM 2006, Los Angeles, CA, USA, September 23-29, 2006 (2006), ACM), 322-333
[20] Kodialam, M. S.; Nandagopal, T.; Lau, W. C., Anonymous tracking using RFID tags, (INFOCOM 2007, 26th IEEE International Conference on Computer Communications, Joint Conference of the IEEE Computer and Communications Societies. INFOCOM 2007, 26th IEEE International Conference on Computer Communications, Joint Conference of the IEEE Computer and Communications Societies, 6-12 May, 2007, Anchorage, Alaska, USA (2007), IEEE), 1217-1225
[21] Nakano, K.; Olariu, S., Energy-efficient initialization protocols for single-hop radio networks with no collision detection, IEEE Trans. Parallel Distrib. Syst., 11, 8, 851-863 (2000)
[22] Nakano, K.; Olariu, S., Uniform leader election protocols for radio networks, IEEE Trans. Parallel Distrib. Syst., 13, 5, 516-526 (2002)
[23] Qian, C.; Ngan, H.; Liu, Y.; Ni, L. M., Cardinality estimation for large-scale RFID systems, IEEE Trans. Parallel Distrib. Syst., 22, 9, 1441-1454 (2011)
[24] Shahzad, M.; Liu, A. X., Every bit counts: fast and scalable RFID estimation, (Akan, Ö. B.; Ekici, E.; Qiu, L.; Snoeren, A. C., The 18th Annual International Conference on Mobile Computing and Networking. The 18th Annual International Conference on Mobile Computing and Networking, Mobicom’12, Istanbul, Turkey, August 22-26, 2012 (2012), ACM), 365-376 (2012)
[25] Whang, K. Y.; Zanden, B. T.V.; Taylor, H. M., A linear-time probabilistic counting algorithm for database applications, ACM Trans. Database Syst., 15, 2, 208-229 (1990)
[26] Willard, D. E., Log-logarithmic selection resolution protocols in a multiple access channel, SIAM J. Comput., 15, 2, 468-477 (1986) · Zbl 0612.94001
[27] Zheng, Y.; Li, M., ZOE: fast cardinality estimation for large-scale RFID systems, (Proceedings of the IEEE. Proceedings of the IEEE, INFOCOM 2013, Turin, Italy, April 14-19, 2013 (2013), IEEE), 908-916
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.