Hidden terminal interference is caused by the (quasi-) simultaneous transmission of two stations that cannot hear each other, but are both received by the same destination station. This interference lowers the system throughput and increases the average packet delay. Some random access protocols that reduce this interference have been proposed, e.g., BTMA protocol. However, the hidden terminal interference can be totally avoided only by means of code division multiple access (CDMA) schemes. In this paper, we investigate the problem of assigning orthogonal codes to stations so as to eliminate the hidden terminal interference. Since the codes share the fixed channel capacity allocated to the network in the design stage, their number must not exceed a given bound. In this paper, we seek for assignments that minimize the number of codes used. We show that this problem is NP-complete, and thus computationally intractable, even for very restricted but very realistic network topologies. Then, we present optimal algorithms for further restricted topologies, as well as fast suboptimal centralized and distributed heuristic algorithms. The results of extensive simulation set up to derive the average performance of the proposed heuristics on realistic network topologies are presented.

CODE ASSIGNMENT FOR HIDDEN TERMINAL INTERFERENCE AVOIDANCE IN MULTIHOP PACKET RADIO NETWORKS

BONUCCELLI, MAURIZIO ANGELO
1995-01-01

Abstract

Hidden terminal interference is caused by the (quasi-) simultaneous transmission of two stations that cannot hear each other, but are both received by the same destination station. This interference lowers the system throughput and increases the average packet delay. Some random access protocols that reduce this interference have been proposed, e.g., BTMA protocol. However, the hidden terminal interference can be totally avoided only by means of code division multiple access (CDMA) schemes. In this paper, we investigate the problem of assigning orthogonal codes to stations so as to eliminate the hidden terminal interference. Since the codes share the fixed channel capacity allocated to the network in the design stage, their number must not exceed a given bound. In this paper, we seek for assignments that minimize the number of codes used. We show that this problem is NP-complete, and thus computationally intractable, even for very restricted but very realistic network topologies. Then, we present optimal algorithms for further restricted topologies, as well as fast suboptimal centralized and distributed heuristic algorithms. The results of extensive simulation set up to derive the average performance of the proposed heuristics on realistic network topologies are presented.
1995
Bertossi, Aa; Bonuccelli, MAURIZIO ANGELO
File in questo prodotto:
Non ci sono file associati a questo prodotto.

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/11568/20892
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 173
  • ???jsp.display-item.citation.isi??? 121
social impact