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.
|Titolo:||A logarithmic lower bound for time-spread multiple access protocols|
BRUSCHI, DANILO MAURO (Ultimo)
|Parole Chiave:||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 Scientifico Disciplinare:||Settore INF/01 - Informatica|
|Data di pubblicazione:||2000|
|Digital Object Identifier (DOI):||10.1023/A:1019129328897|
|Appare nelle tipologie:||01 - Articolo su periodico|