Allocating data for broadcasting over wireless channels subject to transmission errors | Wireless Networks
Skip to main content

Allocating data for broadcasting over wireless channels subject to transmission errors

  • Published:
Wireless Networks Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7

Similar content being viewed by others

References

  1. Acharya, S., Alonso, R., Franklin, M., & Zdonik. S. (1995). Broadcast disks: Data management for asymmetric communication environments. In Proceedings of SIGMOD (pp. 199–210).

  2. Ammar, M. H., & Wong, J. W. (1985). The design of teletext broadcast cycles. Performance Evaluation, 5(4), 235–242.

    Article  Google Scholar 

  3. Ammar, M. H., & Wong, J. W. (1987). On the optimality of cyclic transmission in teletext systems. IEEE Transactions on Communications, 35(11), 1159–1170.

    Article  Google Scholar 

  4. 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.

    Article  Google Scholar 

  5. 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.

    Article  Google Scholar 

  6. 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).

  7. 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).

    Google Scholar 

  8. 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).

  9. Imielinski, T., Viswanathan, S., & Badrinath, B. R. (1994). Energy efficient indexing on air. In Proceedings of the SIGMOD (pp. 25–36).

  10. 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).

  11. 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).

  12. 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).

  13. 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).

  14. 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.

    Article  MATH  Google Scholar 

  15. 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).

  16. Stojmenovic, I. (Ed.). (2002). Handbook of wireless networks and mobile computing. Chichester: Wiley.

    Google Scholar 

  17. Turin, W. (1990). Performance analysis of digital transmission systems. New York: Computer Science Press.

    Google Scholar 

  18. 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).

  19. Willig, A. (2005). Redundancy concepts to increase transmission reliability in wireless industrial LANs. IEEE Transactions on Industrial Informatics, 1(3), 173–182.

    Article  Google Scholar 

  20. Yee, W. G. (2001). Efficient data allocation for broadcast disk arrays. Technical Report, GIT-CC-02-20, Georgia Institute of Technology.

  21. 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.

    Article  MathSciNet  Google Scholar 

  22. Zorzi, M., Rao, R., & Milstein, L. B. (1998). Error statistics in data transmission over fading channels. IEEE Transactions on Communications, 46(11), 1468–1477.

    Article  Google Scholar 

Download references

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

Authors

Corresponding author

Correspondence to M. Cristina Pinotti.

Rights and permissions

Reprints 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

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11276-008-0136-z

Keywords