Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

In the Code Division Multiple Access (CDMA) framework, collisions that can occur in wireless networks are eliminated by assigning orthogonal codes to stations, a problem equivalent to that of coloring graphs associated to the physical network. In this paper we present new upper and lower bounds for two versions of the problem (hidden and primary collision avoidance – HP-CA – or hidden collision avoidance only – H-CA). In particular, optimal assignments for special topologies and heuristics for general topologies are proposed. The schemes show better average results with respect to existing alternatives. Furthermore, the gaps between the upper bound given by the heuristic solution, the lower bound obtained from the maximum-clique problem, and the optimal solution obtained by branch and bound are investigated in the different settings. A scaling law is then proposed to explain the relations between the number of codes needed in Euclidean networks with different station densities and connection distances. The substantial difference between the two versions HP-CA and H-CA of the problem is investigated by studying the probabilistic distribution of connections as a function of the distance, and the asymptotic size of the maximum cliques.

REFERENCES

• 1: N. Abrahmson, The ALOHA system Another alternative for computer communications, in: Proc. of FJCC (1970) pp. 281-285.
• 2: R. Battiti and M. Protasi, Reactive local search for the maximum clique problem, Technical Report TR-95-052, ICSI, Berkeley, CA (1995).
• 3: M. Bellare , O. Goldreich , M. Sudan, Free bits, PCPs and non-approximability-towards tight results, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.422, October 23-25, 1995
• 4: Alan A. Bertossi , Maurizio A. Bonuccelli, Code assignment for hidden terminal interference avoidance in multihop packet radio networks, IEEE/ACM Transactions on Networking (TON), v.3 n.4, p.441-449, Aug. 1995 [doi>10.1109/90.413218]
• 5: Daniel Brélaz, New methods to color the vertices of a graph, Communications of the ACM, v.22 n.4, p.251-256, April 1979 [doi>10.1145/359094.359101]
• 6: I. Chlamtac and S. Kutten, On broadcasting in radio networks Problem analysis and protocol design, IEEE Transactions on Communications (December 1985).
• 7: I. Chlamtac and S. Kutten, A spatial reuse TDMA/FDMA for mobile multi-hop radio networks, in: Proc. of IEEE INFOCOM (March 1985).
• 8: I. Chlamtac , S. S. Pinter, Distributed nodes organization algorithm for channel access in a multihop dynamic radio network, IEEE Transactions on Computers, v.36 n.6, p.728-737, June 1987 [doi>10.1109/TC.1987.1676965]
• 9: I. Cidon , M. Sidi, Distributed Assignment Algorithms for Multihop Packet Radio Networks, IEEE Transactions on Computers, v.38 n.10, p.1353-1361, October 1989 [doi>10.1109/12.35830]
• 10: D. Johnson and M. Trick (eds.), Cliques, Coloring, and Satisfiability:Second DIMACS Implementation Challenge,DIMACSSeriesin Discrete Mathematics and Theoretical Computer Science, in press.
• 11: Limin Hu, Distributed code assignments for CDMA Packet Radio Network, IEEE/ACM Transactions on Networking (TON), v.1 n.6, p.668-677, Dec. 1993 [doi>10.1109/90.266055]
• 12: S.M. Korman, The graph-coloring problem, in: Combinatorial Optimization,eds. N. Christophides, P. Toth and C. Sandi (Wiley, New York, 1979) pp. 211235.
• 13: Marek Kubale , Boguslaw Jackowski, A generalized implicit enumeration algorithm for graph coloring, Communications of the ACM, v.28 n.4, p.412-418, April 1985 [doi>10.1145/3341.3350]
• 14: T. Makansi, Transmitted-oriented code assignment for multihop packet radio, IEEE Transactions on Communications 35 (1987) 13791382.
• 15: A. Mehrotra and M.A. Trick, A column generation approach to graph coloring, Technical report series, Graduate School of Industrial Administration, Carnegie Mellon University (1995).
• 16: R. Nelson and L. Kleinrock, Spatial TDMA: a collision-free multihop channel access protocol, IEEE Transactions on Communications 33 (1985) 934944.
• 17: M.J. Post, A.S. Kershenbaum and P.E. Sarachik, Scheduling multihop CDMA networks in the presence of secondary conflicts, Algorithmica 4 (1989) 365394.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

General Terms:
Design