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.

A logarithmic lower bound for time-spread multiple access protocols / S. Basagni, D. Bruschi. - In: WIRELESS NETWORKS. - ISSN 1022-0038. - 6:2(2000), pp. 161-163. [10.1023/A:1019129328897]

A logarithmic lower bound for time-spread multiple access protocols

D. Bruschi
Ultimo
2000

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.
Combinatorial mathematics; Communication channels (information theory); Optimization; Problem solving; Radio interference; Time division multiple access; Multi-hop radio networks; Time spread multiple access protocols; Mobile radio systems
Settore INF/01 - Informatica
Article (author)
File in questo prodotto:
File Dimensione Formato  
art%3A10.1023%2FA%3A1019129328897.pdf

accesso riservato

Tipologia: Publisher's version/PDF
Dimensione 58.46 kB
Formato Adobe PDF
58.46 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/258616
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 7
  • ???jsp.display-item.citation.isi??? 7
social impact