Nothing Special   »   [go: up one dir, main page]
Skip to main content
SpringerLink
Log in

On the distributed construction of a collision-free schedule in multi-hop packet radio networks

  • Published:
Telecommunication Systems Aims and scope Submit manuscript

Abstract

This paper introduces a protocol that distributively constructs a collision-free schedule for multi-hop packet radio networks in the presence of hidden terminals. As a preliminary step, each wireless station computes the schedule length after gathering information about the number of flows in its neighbourhood. Then, a combination of deterministic and random backoffs are used to reach a collision-free schedule. A deterministic backoff is used after successful transmissions and a random backoff is used otherwise. It is explained that the short acknowledgement control packets can easily result in channel time fragmentation and, to avoid this, the use of link layer delayed acknowledgements is advocated and implemented. The performance results show that a collision-free protocol easily outperforms a collision-prone protocol such as Aloha. The time that is required for the network to converge to a collision-free schedule is assessed by means of simulation.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /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 excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

Notes

  1. This simulator includes all the assumptions and idealities discussed in the previous sections and it is available for download at www.jaumebarcelo.info/barcelo2011emp/simulator.py. Contact the first author for more details and the scripts required to generate the plot.

References

  1. Andreev, K., & Boyko, P. (2010). Simulation study of VoIP performance in IEEE 802.11 wireless mesh networks. In MACOM (pp. 139–150).

    Google Scholar 

  2. Arikan, E. (1984). Some complexity results about packet radio networks. IEEE Transactions on Information Theory, 30(4), 681–685.

    Article  Google Scholar 

  3. Barcelo, J., Bellalta, B., Cano, C., & Oliver, M. (2008). Learning-BEB: avoiding collisions in WLAN. In Eunice.

    Google Scholar 

  4. Barcelo, J., Bellalta, B., Cano, C., Sfairopoulou, A., & Oliver, M. (2009). Carrier sense multiple access with enhanced collision avoidance: a performance analysis. In ACM IWCMC.

    Google Scholar 

  5. Barcelo, J., Bellalta, B., Cano, C., Sfairopoulou, A., Oliver, M., & Zuidweg, J. (2009). Traffic prioritization for carrience sense multiple access with enhanced collision avoidance. In MACOM.

    Google Scholar 

  6. Barcelo, J., Bellalta, B., Sfairopoulou, A., Cano, C., & Oliver, M. (2009). CSMA with enhanced collision avoidance: a performance assessment. In: IEEE VTC spring.

    Google Scholar 

  7. Barcelo, J., Lopez-Toledo, A., Cano, C., & Oliver, M. (2010). Fairness and convergence of CSMA with enhanced collision avoidance. In ICC.

    Google Scholar 

  8. Barcelo, J., Bellalta, B., Cano, C., Sfairopoulou, A., & Oliver, M. (2011). Towards a collision-free WLAN: dynamic parameter adjustment in CSMA/E2CA. Eurasip Journal on Wireless Communications and Networking.

  9. Barcelo, J., Bellalta, B., Oliver, M., & Banchs, A. (2011). Collision free operation in ad-hoc networks. In MACOM.

    Google Scholar 

  10. Chambers, B. (2002). The grid roofnet: a rooftop ad hoc wireless network. Ph.D. thesis, Massachusetts Institute of Technology.

  11. Choi, J., Yoo, J., Choi, S., & Kim, C. E. (2005). An enhancement of the IEEE 802. 11 DCF via distributed reservation. IEEE Transactions on Mobile Computing, 4(4), 378–390.

    Article  Google Scholar 

  12. Cicconetti, C., Lenzini, L., & Mingozzi, E. (2008). Scheduling and dynamic relocation for IEEE 802.11 s mesh deterministic access. In IEEE SECON (pp. 19–27).

    Google Scholar 

  13. Duffy, K. R., Bordenave, C., & Leith, D. J. (2011). Decentralized constraint satisfaction. CoRR abs/1103.3240.

  14. Fang, M., Malone, D., Duffy, K., & Leith, D. (2011). Decentralised learning MACs for collision-free access in WLANs. arXiv:1009.4386v2.

  15. Gurewitz, O., Mancuso, V., Shi, J., & Knightly, E. (2009). Measurement and modeling of the origins of starvation of congestion-controlled flows in wireless mesh networks. IEEE/ACM Transactions on Networking, 17(6), 1832–1845.

    Article  Google Scholar 

  16. He, Y., Yuan, R., Sun, J., & Gong, W. (2009). Semi-random backoff: towards resource reservation for channel access in wireless LANs. In IEEE ICNP (pp. 21–30).

    Google Scholar 

  17. Hiertz, G., Denteneer, D., Max, S., Taori, R., Cardona, J., Berlemann, L., & Walke, B. (2010). IEEE 802.11 s: the WLAN mesh standard. IEEE Wireless Communications Magazine, 17(1), 104–111.

    Article  Google Scholar 

  18. Hui, K., Li, T., Guo, D., & Berry, R. (2011). Exploiting peer-to-peer state exchange for distributed medium access control. In IEEE ISIT (pp. 2368–2372). New York: IEEE.

    Google Scholar 

  19. Jain, R. (1991). The art of computer systems performance analysis. New York: Wiley.

    Google Scholar 

  20. Kar, K., Sarkar, S., & Tassiulas, L. (2004). Achieving proportional fairness using local information in Aloha networks. IEEE Transactions on Automatic Control, 49(10), 1858–1863.

    Article  Google Scholar 

  21. Kelly, F. (1997). Charging and rate control for elastic traffic. European Transactions on Telecommunications, 8(1), 33–37.

    Article  Google Scholar 

  22. Khan, Z., Lehtomaki, J., Mustonen, M., & Matinmikko, M. (2011). Sensing order dispersion for autonomous cognitive radios. In CROWNCOM (pp. 191–195). New York: IEEE.

    Google Scholar 

  23. Krasilov, A., Lyakhov, A., & Safonov, A. (2011). Interference, even with MCCA channel access method in IEEE 802.11s mesh networks. In MASS (pp. 752–757).

    Google Scholar 

  24. Martorell, G., Riera, F., Femenias, G., Barcelo, J., & Bellalta, B. (2012). On the performance evaluation of CSMA/E2CA protocol with open loop ARF-based adaptive modulation and coding. In European wireless.

    Google Scholar 

  25. Mueller, K. (2004). SimPy documentation. http://simpy.sourceforge.net/ Online; accessed 05 December, 2011.

  26. Oliver, M., Zuidweg, J., & Batikas, M. (2010). Wireless commons against the digital divide. In IEEE ISTAS.

    Google Scholar 

  27. Ramanathan, S., & Lloyd, E. (1993). Scheduling algorithms for multihop radio networks. IEEE/ACM Transactions on Networking, 1(2), 166–177.

    Article  Google Scholar 

  28. Sommer, P., & Wattenhofer, R. (2009). Gradient clock synchronization in wireless sensor networks. In ACM/IEEE IPSN.

    Google Scholar 

  29. Tian, X., Chen, X., Ideguchi, T., & Okuda, T. (2008). Improving protocol capacity by scheduling random access on WLANs. Telecommunications Systems, 37, 19–28.

    Article  Google Scholar 

  30. Tobagi, F. (1987). Modeling and performance analysis of multihop packet radio networks. Proceedings of the IEEE, 75(1), 135–155.

    Article  Google Scholar 

  31. Yi, Y., De Veciana, G., & Shakkottai, S. (2010). MAC scheduling with low overheads by learning neighborhood contention patterns. IEEE/ACM Transactions on Networking.

Download references

Acknowledgements

The authors are thankful to the anonymous reviewers for their constructive comments that helped to substantially improve the final version of this manuscript. This work has been partially funded by the Spanish Government (grant TEC2008-0655) and the European Commission (grant CIP-ICT PSP-2011-5). The views expressed in this article are solely those of the authors and do not represent the views of the Spanish Government or the European Commission.

Author information

Authors and Affiliations

  1. Universidad Carlos III de Madrid, Madrid, Spain

    Jaume Barcelo

  2. Universitat Pompeu Fabra, Barcelona, Spain

    Boris Bellalta, Cristina Cano, Azadeh Faridi & Miquel Oliver

Authors
  1. Jaume Barcelo
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Boris Bellalta
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Cristina Cano
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Azadeh Faridi
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Miquel Oliver
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jaume Barcelo.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Barcelo, J., Bellalta, B., Cano, C. et al. On the distributed construction of a collision-free schedule in multi-hop packet radio networks. Telecommun Syst 56, 285–298 (2014). https://doi.org/10.1007/s11235-013-9836-5

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11235-013-9836-5

Keywords

Search

Navigation