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

A logarithmic lower bound for time‐spread multiple‐access (TSMA) protocols

  • Published:
Wireless Networks Aims and scope Submit manuscript

Abstract

Time‐Spread Multiple‐Access (TSMA) protocols are scheduled access protocols for mobile multi‐hop radio networks that guarantee deterministic access to the shared channel regardless of the possibility of radio interference. In scheduled access methods, time is considered to be slotted and time slots are cyclically organized into frames. In general, the shorter the frame, the more efficient the protocol. An Ω(log log n) lower bound is known on the minimum length of the frame of TSMA protocols in networks with n nodes. In this note we improve that lower bound by characterizing the multiple access to the radio channel as a combinatorial problem. The proposed characterization allows us to prove that no TSMA protocols can successfully schedule the transmissions of the nodes of a multi‐hop radio network in frames with less than log n time slots.

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

Similar content being viewed by others

References

  1. S. Boztas, A robust multi-priority topology-independent transmission schedule for packet radio networks, Information Processing Letters 55(5) (15 September 1997) 291–295.

    Article  Google Scholar 

  2. I. Chlamtac and A. Faragó, Making transmission schedule immune to topology changes in multi-hop packet radio networks, IEEE/ACM Transactions on Networking 2(1) (February 1994) 23–29.

    Article  Google Scholar 

  3. I. Chlamtac, A. Faragó and H.Y. Ahn, A topology transparent link attivation protocol for mobile CDMA radio networks, IEEE Journal on Selected Areas in Communications 12(8) (October 1994) 1426–1433.

    Article  Google Scholar 

  4. I. Chlamtac, A. Faragó and H. Zhang, Time-spread multiple-access (TSMA) protocols for multihop mobile radio networks, ACM/IEEE Transactions on Networking 5(6) (December 1997) 804–812.

    Article  Google Scholar 

  5. M. Szegedy and S. Vishwanathan, Locality based graph coloring, in: Proceedings of the 25th Annual ACM Symposium on Theory of computing, San Diego, CA (16-18 May 1993) pp. 201–207.

Download references

Author information

Authors and Affiliations

  1. Center for Advanced Telecommunications Systems and Services, Erik Jonsson School of Engineering and Computer Science, The University of Texas at Dallas, Richardson, TX, 75083, USA

    Stefano Basagni

  2. Dipartimento di Scienze dell’Informazione, Università degli Studi di Milano, Italy

    Danilo Bruschi

Authors
  1. Stefano Basagni
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Danilo Bruschi
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Basagni, S., Bruschi, D. A logarithmic lower bound for time‐spread multiple‐access (TSMA) protocols. Wireless Networks 6, 161–163 (2000). https://doi.org/10.1023/A:1019129328897

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1019129328897

Keywords

Search

Navigation