×

Latency-optimal communication in wireless mesh networks. (English) Zbl 1282.68081

Summary: Wireless mesh networking is an emerging communication paradigm to enable resilient, cost-efficient and reliable services for the future-generation wireless networks. We study the minimum-latency communication primitive of gossiping (all-to-all communication) in known topology wireless mesh networks (WMNs), i.e., where the schedule of transmissions is pre-computed in advance based on full knowledge about the size and the topology of the WMN. Each mesh node in the WMN is initially given a message and the objective is to design a minimum-latency schedule such that each mesh node distributes its message to all other mesh nodes. The problem of computing a minimum-latency gossiping schedule for a given WMN is NP-hard, hence it is only possible to get a polynomial approximation algorithm. In this paper, we show a deterministic approximation algorithm that can complete gossiping task in \(O(D+\frac{\Delta\log n}{\log\Delta})\) time units in any WMN of size \(n\), diameter \(D\), and maximum degree \(\Delta\). This is an asymptotically optimal schedule in the sense that there exists a WMN topology, specifically a \(\Delta\)-regular tree, in which the gossiping task cannot be accomplished in less than \(\varOmega\left(D+\frac{\Delta\log n}{\log\Delta}\right)\) units of time. Our algorithm also improves on currently best known gossiping schedule of length \(O\left(D+\frac{\Delta\log n}{\log\Delta-\log\log n}\right)\).

MSC:

68M10 Network design and communication in computer systems
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
68W25 Approximation algorithms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Akyildiz, I. F.; Wang, X.; Wang, W., Wireless mesh networks: a survey, Comput. Netw., 47, 4, 445-487 (2005) · Zbl 1152.68319
[2] Alon, N.; Bar-Noy, A.; Linial, N.; Peleg, D., A lower bound for radio broadcast, J. Comput. System Sci., 43, 290-298 (1991) · Zbl 0753.68006
[3] Chlamtac, I.; Kutten, S., On broadcasting in radio networks-problem analysis and protocol design, IEEE Trans. Commun., 33, 1240-1246 (1985) · Zbl 0579.94029
[4] Cicalese, F.; Manne, F.; Xin, Q., Faster centralized communication in radio networks, Algorithmica, 54, 2, 226-242 (2009) · Zbl 1165.90005
[5] Chlamtac, I.; Weinstein, O., The wave expansion approach to broadcasting in multihop radio networks, IEEE Trans. Commun., 39, 426-433 (1991)
[6] Elkin, M.; Kortsarz, G., Improved broadcast schedule for radio networks, (Proc. 16th ACM-SIAM Symp. on Discrete Algorithms (2005)), 222-231 · Zbl 1297.68041
[7] Gąsieniec, L.; Potapov, I., Gossiping with unit messages in known radio networks, (Proceedings of 2nd IFIP TCS (2002)), 193-205
[8] Gąsieniec, L.; Potapov, I.; Xin, Q., Efficient gossiping in known radio networks, (Proc. 11th SIROCCO. Proc. 11th SIROCCO, LNCS, vol. 3104 (2004)), 173-184 · Zbl 1085.68512
[9] Gąsieniec, L.; Peleg, D.; Xin, Q., Faster communication in known topology radio networks, (Proc. 24th Annual ACM SIGACT-SIGOPS PODC (2005)), 129-137 · Zbl 1314.68155
[10] Kowalski, D.; Pelc, A., Optimal deterministic broadcasting in known topology radio networks, Distrib. Comput., 19, 3, 185-195 (2007) · Zbl 1266.68231
[11] Kowalski, D.; Rokicki, M., Multi-channel assignment for communication in radio networks, (Proceedings of First International ICST Conference on Theory and Practice of Algorithms in Computer Systems. Proceedings of First International ICST Conference on Theory and Practice of Algorithms in Computer Systems, TAPAS 2011 (2011)), 181-192 · Zbl 1325.90020
[12] Manne, F.; Xin, Q., Faster radio broadcast in planar graphs, J. Netw., 3, 2, 9-16 (2008)
[13] Manne, F.; Xin, Q., Optimal gossiping with unit size messages in known radio networks, (Proc. 3rd Workshop on Combinatorial and Algorithmic Aspects of Networking, CAAN 2006. Proc. 3rd Workshop on Combinatorial and Algorithmic Aspects of Networking, CAAN 2006, LNCS, vol. 4235 (2006)), 125-134 · Zbl 1137.68321
[14] Sen, A.; Huson, M. L., A new model for scheduling packet radio networks, (Proc. 15th Joint Conf. of IEEE Computer and Communication Societies. Proc. 15th Joint Conf. of IEEE Computer and Communication Societies, INFOCOM 1996 (1996)), 1116-1124
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.