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

ABSTRACT

This paper investigates the problem of assigning channels to the stations of a wireless network so that interfering transmitters are assigned channels with a given separation and the number of channels used is minimized. Two versions of the channel assignment problem are considered which are equivalent to two specific coloring problems — called L(2, 1) and L (2, 1, 1) — of the graph representing the network topology. In these problems, channels assigned to adjacent vertices must be at least 2 apart, while the same channel can be reused only at vertices whose distance is at least 3 or 4, respectively. Efficient channel assignment algorithms using the minimum number of channels are provided for specific, but realistic, network topologies, including buses, rings, hexagonal grids, bidimensional grids, cellular grids, and complete binary trees.

REFERENCES

• 1: Roberto Battiti , Alan A. Bertossi , Maurizio A. Bonuccelli, Assigning codes in wireless networks: bounds and scaling properties, Wireless Networks, v.5 n.3, p.195-209, May 1999 [doi>10.1023/A:1019146910724]
• 2: 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]
• 3: A.A. Bertossi and M.C. Pinotti, "Mappings for Conflict-Free Access of Paths in Bidimensional Arrays, Circular Lists, and Complete Trees", Tec. Rep. UTM-563, Depatment of Mathematics, University of Trento, 1999.
• 4: H.L. Bodlaender, T. Kloks, R.B. Tan and J. van Leeuwen, "Approximation ,k-Coloring on Graphs", to appear in Proceedings STA CS ~000.
• 5: Gerard J. Chang , David Kuo, The $L(2,1)$-Labeling Problem on Graphs, SIAM Journal on Discrete Mathematics, v.9 n.2, p.309-316, May 1996 [doi>10.1137/S0895480193245339]
• 6: 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]
• 7: Jerrold R. Griggs , Roger K. Yeh, Labelling graphs with a condition at distance 2, SIAM Journal on Discrete Mathematics, v.5 n.4, p.586-595, Nov. 1992 [doi>10.1137/0405048]
• 8: W.K. Hale, "Frequency Assignment: Theory and Application", Proceedings of the IEEE, Vol. 68, 1980, pp. 1497-1514.
• 9: I. Katzela and M. Naghshineh, "Channel Assignment Schemes for Cellular Mobile Telecommunication Systems: A Comprehensive Survey", IEEE Personal Communications, June 1996, pp. 10-31.
• 10: T. Makansi, "Transmitted Oriented Code Assignment for Multihop Packet Radio", IEEE 7kansactions on Communications, Vol. 35, 1987, pp. 1379-1382.
• 11: S.T. McCormick, "Optimal Approximation of Sparse Hessians and its Equivalence to a Graph Coloring Problem", Mathematical Programming, Vol. 26, 1983, pp. 153-171.
• 12: Denise Sakai, Labeling Chordal Graphs: Distance Two Condition, SIAM Journal on Discrete Mathematics, v.7 n.1, p.133-140, Feb. 1994 [doi>10.1137/S0895480191223178]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization

Additional Classification:
  B. Hardware
  B.4 INPUT/OUTPUT AND DATA COMMUNICATIONS
      B.4.2 Input/Output Devices
          Subjects: Channels and controllers

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

General Terms:
Algorithms, Design, Measurement, Performance, Theory, Verification