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

Hidden terminal interference is caused by the (quasi-) simultaneous tr ansmission of two stations that cannot hear each other, but are both r eceived 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 tot ally avoided only by means of code division multiple access (CDMA) sch emes, In this paper, we investigate the problem of assigning orthogona l codes to stations so as to eliminate the hidden terminal interferenc e, Since the codes share the fixed channel capacity allocated to the n etwork in the design stage, their number must not exceed a given bound . In this paper, we seek for assignments that minimize the number of c odes used, We show that this problem is NP-complete, and thus computat ionally intractable, even for very restricted but very realistic netwo rk topologies. Then, we present optimal algorithms for further restric ted topologies, as well as fast suboptimal centralized and distributed heuristic algorithms, The results of extensive simulation set up to d erive the average performance of the proposed heuristics on realistic network topologies are presented.