Abstract
Broadcasting is an efficient and scalable way of transmitting data over wireless channels to an unlimited number of clients. In this paper the problem of allocating data to multiple channels is studied, assuming flat data scheduling per channel and the presence of unrecoverable channel transmission errors. The objective is that of minimizing the average expected delay experienced by the clients. Two different channel error models are considered: the Bernoulli model and the simplified Gilbert–Elliot one. In the former model, each packet transmission has the same probability to fail and each transmission error is independent from the others. In the latter one, bursts of erroneous or error-free packet transmissions due to wireless fading channels are modeled. Particular cases are detected where optimal solutions can be found in polynomial time. For general cases, simulations show that good sub-optimal solutions can be found on benchmarks whose item popularities follow Zipf distributions.
Similar content being viewed by others
References
Acharya, S., Alonso, R., Franklin, M., & Zdonik. S. (1995). Broadcast disks: Data management for asymmetric communication environments. In Proceedings of SIGMOD (pp. 199–210).
Ammar, M. H., & Wong, J. W. (1985). The design of teletext broadcast cycles. Performance Evaluation, 5(4), 235–242.
Ammar, M. H., & Wong, J. W. (1987). On the optimality of cyclic transmission in teletext systems. IEEE Transactions on Communications, 35(11), 1159–1170.
Anticaglia, S., Barsi, F., Bertossi, A. A., Iamele, L., & Pinotti, M. C. (2008). Efficient heuristics for data broadcasting on multiple channels. Wireless Networks, 14(2), 219–231.
Ardizzoni, E., Bertossi, A. A., Pinotti, M. C., Ramaprasad, S., Rizzi, R., & Shashanka, M. V. S. (2005). Optimal skewed data allocation on multiple channels with flat broadcast per channel. IEEE Transactions on Computers, 54(5), 558–572.
Bar-Noy, A., Bhatia, R., Naor, J. S., & Schieber, B. (1998). Minimizing service and operation costs of periodic scheduling. In Proceedings of the Ninth ACM-SIAM Symposium on Discrete Algorithms (SODA) (pp. 11–20).
Bertossi, A. A., Pinotti, M. C., & Rizzi, R. (2007). Scheduling data broadcasts on wireless channels: Exact solutions and heuristics. In T. Gonzalez (Ed.), Handbook of approximation algorithms and metaheuristics, Chapter 73. Boca Raton: Taylor & Francis Books (CRC Press).
Breslau, L., Cao, P., Fan, L., Phillips, G., & Shenker, S. (1999). Web caching and Zipf-like distributions: Evidence and implications. In Proceedings of the IEEE INFOCOM (pp. 126–134).
Imielinski, T., Viswanathan, S., & Badrinath, B. R. (1994). Energy efficient indexing on air. In Proceedings of the SIGMOD (pp. 25–36).
Kenyon, C., & Schabanel, N. (1999). The data broadcast problem with non-uniform transmission time. In Proceedings of the Tenth ACM-SIAM Symposium on Discrete Algorithms (SODA) (pp. 547–556).
Kenyon, C., Schabanel, N., & Young, N. (2000). Polynomial time approximation scheme for data broadcast. In Proceedings of the ACM Symposium on Theory of Computing (STOC) (pp. 659–666).
Koutsakis, P. (2005). Scheduling and call admission control for burst-error wireless channels. In Proceedings of the 10th IEEE Symposium on Computers and Communications (ISCC) (pp. 767–772).
Lo, S.-C., & Chen, A. L. P. (2000). Optimal index and data allocation in multiple broadcast channels. In Proceedings of the Sixteenth IEEE International Conference on Data Engineering (ICDE) (pp. 293–302).
Peng, W. C., & Chen, M. S. (2003). Efficient channel allocation tree generation for data broadcasting in a mobile computing environment. Wireless Networks, 9(2), 117–129.
Prabhakara, K. A., Hua, K. A., & Oh, J. (2000). Multi-level multi-channel air cache designs for broadcasting in a mobile environment. In Proceedings of the Sixteenth IEEE International Conference on Data Engineering (ICDE) (pp. 167–176).
Stojmenovic, I. (Ed.). (2002). Handbook of wireless networks and mobile computing. Chichester: Wiley.
Turin, W. (1990). Performance analysis of digital transmission systems. New York: Computer Science Press.
Vaidya, N., & Hameed, S. (1997). Log time algorithms for scheduling single and multiple channel data broadcast. In Proceedings of the Third ACM-IEEE Conference on Mobile Computing and Networking (MOBICOM) (pp. 90–99).
Willig, A. (2005). Redundancy concepts to increase transmission reliability in wireless industrial LANs. IEEE Transactions on Industrial Informatics, 1(3), 173–182.
Yee, W. G. (2001). Efficient data allocation for broadcast disk arrays. Technical Report, GIT-CC-02-20, Georgia Institute of Technology.
Yee, W. G., Navathe, S., Omiecinski, E., & Jermaine, C. (2002). Efficient data allocation over multiple channels at broadcast servers. IEEE Transactions on Computers, 51(10), 1231–1236.
Zorzi, M., Rao, R., & Milstein, L. B. (1998). Error statistics in data transmission over fading channels. IEEE Transactions on Communications, 46(11), 1468–1477.
Acknowledgements
This work has been supported by ISTI-CNR under the BREW research grant. The C++ code used in the simulations was written by G. Spagnardi.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Barsocchi, P., Bertossi, A.A., Pinotti, M.C. et al. Allocating data for broadcasting over wireless channels subject to transmission errors. Wireless Netw 16, 355–365 (2010). https://doi.org/10.1007/s11276-008-0136-z
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11276-008-0136-z