New graph model for channel assignment in ad hoc wireless networks

Access Full Text

New graph model for channel assignment in ad hoc wireless networks

For access to this article, please select a purchase option:

Buy article PDF
£12.50
(plus tax if applicable)
Add to cart
Buy Knowledge Pack
10 articles for £75.00
(plus taxes if applicable)
Add to cart

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Name:*
Email:*
Your details
Name:*
Email:*
Department:*
Why are you recommending this title?
Select reason:
 
 
 
 
 
IEE Proceedings - Communications — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

© IEE
Published

The channel assignment problem in ad hoc wireless networks is investigated. The problem is to assign channels to hosts in such a way that interference among hosts is eliminated and the total number of channels is minimised. Interference is caused by direct collisions from hosts that can hear each other or indirect collisions from hosts that cannot hear each other, but simultaneously transmit to the same destination. A new class of disk graphs (FDD: interFerence Double Disk graphs) is proposed that include both kinds of interference edges. Channel assignment in wireless networks is a vertex colouring problem in FDD graphs. It is shown that vertex colouring in FDD graphs is NP-complete and the chromatic number of an FDD graph is bounded by its clique number times a constant. A polynomial time approximation algorithm is presented for channel assignment and an upper bound 14 on its performance ratio is obtained. Results from a simulation study reveal that the new graph model can provide a more accurate estimation of the number of channels required for collision avoidance than previous models.

Inspec keywords: optimisation; computational complexity; polynomial approximation; channel allocation; number theory; adjacent channel interference; ad hoc networks; graph colouring

Other keywords: ad hoc wireless network; interference double disk graph model; FDD; clique number; vertex colouring problem; channel assignment; polynomial time approximation algorithm; collision avoidance; NP-complete; chromatic number; interference edge

Subjects: Optimisation techniques; Interpolation and function approximation (numerical analysis); Combinatorial mathematics; Radio links and equipment; Electromagnetic compatibility and interference

References

    1. 1)
      • Malesinska, E.: ‘List coloring and optimization criteria for a channel assignment problem’. Proc. ACM Int. Conf. on Mobile Computing and Networking, 1995, pp. 210–217.
    2. 2)
      • W.K. Hale . Frequency assignment: Theory and applications. Proc. IEEE , 1497 - 1514
    3. 3)
      • E. Malesinska , S. Piskorz , G. Weissenfels . (1998) On the chromatic number of disk graphs, networks.
    4. 4)
      • Tiourine, S.R., Hurkens, C.A.J., Lenstra, J.K.: `An overview of algorithmic approaches to frequency assignment problems', In Calma Symp. on Combinatorial Algorithms for Military Applications, 1995, p. 53–62.
    5. 5)
    6. 6)
      • Nesargi, S., Prakash, R.: `Distributed wireless channel allocation in networks with mobile base stations', In INFOCOM (2), 1999, p. 592–600.
    7. 7)
      • Prakash, R., Shivaratri, N.G., Singhal, M.: `Distributed dynamic channel allocation for mobile computing', In Symp. on Principles of Distributed Computing, 1995, p. 47–56.
    8. 8)
      • D.W. Matula , L.L. Beck . Smallest-last ordering and clustering and graph coloring algorithms. J. ACM (JACM) , 3 , 417 - 427
    9. 9)
      • K.I. Aardal , C.A.J. Hurkens , J.K. Lenstra , S.R. Tiourine . Algorithms for frequency assignment problems (extended abstract). CWI Quarterly , 1 - 8
    10. 10)
      • B.N. Clark , C.J. Colbourn , D.S. Johnson . Unit disk graphs. Discrete Math. , 165 - 177
    11. 11)
      • Metzger, B.H.: `Spectrum management technique', Presentation at 38th National ORSA Meeting, 1970, Detroit, MI, USA.
    12. 12)
      • M.B. Cozzens , F.S. Roberts . T-colorings of graphs and the channel assignment problem. Congressus Numerantium , 191 - 208
    13. 13)
      • K. Aardal , C. van Hoesel , A. Koster , C. Mannino , A. Sassano . (2000) Models and solution techniques for the frequency assignment problem, 4QR.
    14. 14)
      • Peeters, R.: `On coloring j-unit sphere graphs', In FEW512, Department of Economics, Tilburg University, The Netherlands, 1991.
    15. 15)
      • T. Park , C.Y. Lee . Application of the graph coloring algorithm to the frequency assignment problem. J. Oper. Res. Soc. Jpn. , 258 - 265
    16. 16)
    17. 17)
      • Wan, P.-J., Yi, C.-W., Jia, X., Kim, D.: ‘Approximation algorithms for conflict-free channel assignment in wireless ad hoc networks' Wirel. Commun. Mob. Comput., to be published.
    18. 18)
      • R. Murphey , P. Pardalos , M. Resende . (1999) Frequency assignment problems.
    19. 19)
      • F. Comellas , J. Ozón . Graph coloring algorithms for assignment problems in radio networks. Appl. Neural Netw. Telecommun. , 49 - 56
    20. 20)
      • A. Graf , M. Stumpf , G. Weissenfels . On coloring unit disk graphs. Algorithmica , 277 - 293
http://iet.metastore.ingenta.com/content/journals/10.1049/ip-com_20059053
Loading

Related content

content/journals/10.1049/ip-com_20059053
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading