×

Maximizing the overall end-user satisfaction of data broadcast in wireless mesh networks. (English) Zbl 1419.68022

Summary: We study the problem of broadcasting a common, possibly large, content into a wireless mesh network consisting of \(N\) end-users and of one or multiple access points that act as gateways to Internet. Each end-user is characterized by a maximum possible reception rate that depends on the distance and on the interface used to communicate with the associated access point. The end-user satisfaction is proportional to the actual rate received. The overall end-user satisfaction is the sum of the satisfaction of each end-user. Our goal is to maximize the overall end-user satisfaction under the constraint that the access points can retransmit at different rates the same common content at most \(K\) times. We show that the problem can be solved by serving the end-users according to a suitable \(K\) segmentation, which is a \(K\) partition of the end-users that preserves a specific end-user order. When the access points and the end-users have a unique interface, the optimal segmentation can be found in \(O(N(K + \log N))\) time by exploiting the convex Monge property of the satisfaction function. When both access points and end-users are equipped with multiple interfaces, the problem becomes computationally intractable, even for a single access point. Polynomial time algorithms are then devised for optimally solving some meaningful particular cases.

MSC:

68M10 Network design and communication in computer systems
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
90B18 Communication networks in operations research
90C39 Dynamic programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aggarwal, A.; Klawe, M.; Moran, S.; Shor, P.; Wilber, R., Geometric applications of a matrix-searching algorithm, Algorithmica, 2, 1-4, 195-208 (1987) · Zbl 0642.68078
[2] Athanassopoulos, S.; Caragiannis, I.; Kaklamanis, C.; Papaioannou, E., Energy-efficient communication in multi-interface wireless networks, Theory Comput. Syst., 52, 2, 285-296 (2013) · Zbl 1260.68018
[3] Bein, Wolfgang; Golin, Mordecai J.; Larmore, Lawrence L.; Zhang, Yan, The Knuth-Yao quadrangle-inequality speedup is a consequence of total monotonicity, ACM Trans. Algorithms, 6, 1, 17:1-17:22 (December 2009)
[4] Burkard, Rainer E.; Klinz, Bettina; Rudolf, Rüdiger, Perspectives of Monge properties in optimization, Discrete Appl. Math., 70, 2, 95-161 (1996) · Zbl 0856.90091
[5] Carrano, R. C.; Magalhaes, L. C.S.; Saade, D. C.M.; Albuquerque, C. V.N., IEEE 802.11s multihop mac: a tutorial, IEEE Commun. Surv. Tutor., 13, 1, 52-67 (2011)
[6] Chiu, Hon Sun; Yeung, K. L.; Lui, King-Shan, Maximizing broadcast load in multi-channel multi-interface wireless mesh networks, (Global Telecommunications Conference, 2008. IEEE GLOBECOM 2008. IEEE (Nov. 2008)), 1-5
[7] Chou, Chun Tung; Qadir, J.; Lim, Joo Ghee, Advances and challenges with data broadcasting in wireless mesh networks, IEEE Commun. Mag., 45, 11, 78-85 (November 2007)
[8] D’Angelo, G.; Di Stefano, G.; Navarra, A., Flow problems in multi-interface networks, IEEE Trans. Comput., 63, 2, 361-374 (2014) · Zbl 1364.68052
[9] Garey, M. R.; Johnson, D. S., Computers and Intractability, A Guide to the Theory of NP-Completeness (1979), W.H. Freeman and Company: W.H. Freeman and Company New York · Zbl 0411.68039
[10] Graham, R. L.; Knuth, D. E.; Patashnik, O., Concrete Mathematics (1994), Addison-Wesley: Addison-Wesley Reading, Massachusetts · Zbl 0836.00001
[11] Handler, G.; Zang, I., A dual algorithm for the constrained shortest path problem, Networks, 10, 293-310 (1980)
[12] Klasing, R.; Kosowski, A.; Navarra, A., Cost minimization in wireless networks with a bounded and unbounded number of interfaces, Networks, 53, 3, 266-275 (2009) · Zbl 1178.68039
[13] Kosowski, A.; Navarra, A.; Pajak, D.; Pinotti, M. C., Maximum matching in multi-interface networks, Theor. Comput. Sci., 507, 52-60 (2013) · Zbl 1302.05143
[14] Kosowski, A.; Navarra, A.; Pinotti, M. C., Exploiting multi-interface networks: connectivity and cheapest paths, Wirel. Netw., 16, 4, 1063-1073 (2010)
[15] Liu, B. H.; Chou, C. T.; Misra, A.; Jha, S., Rate-diversity and resource-aware broadcast and multicast in multi-rate wireless mesh networks, Mob. Netw. Appl., 13, 38-53 (2008)
[16] Liu, Tehuang; Liao, Wanjiun, Capacity-aware routing in multi-channel multi-rate wireless mesh networks, (Communications, 2006. ICC ’06. IEEE International Conference on, vol. 5 (June 2006)), 1971-1976
[17] Liu, Tehuang; Liao, Wanjiun, Interference-aware QoS routing for multi-rate multi-radio multi-channel IEEE 802.11 wireless mesh networks, IEEE Trans. Wirel. Commun., 8, 1, 166-175 (Jan. 2009)
[18] Qadir, J.; Chou, C. T.; Misra, A.; Lim, J. G., Localized minimum-latency broadcasting in multi-radio multi-rate wireless mesh networks, (WOWMOM (2008)), 1-12
[19] Qadir, J.; Chou, C. T.; Misra, A.; Lim, J. G., Minimum latency broadcasting in multiradio, multichannel, multirate wireless meshes, IEEE Trans. Mob. Comput., 8, 11, 1510-1523 (2009)
[20] Xin, Qin; Zhang, Yan, Optimal fault-tolerant broadcasting in wireless mesh networks, (High Performance Switching and Routing, 2008. HSPR 2008. International Conference on (May 2008)), 151-157
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.