Impact of Constraints on the Complexity and Performance of Channel Assignment in Multi-Hop Wireless Networks

Authors

  • Chetan Nanjunda Mathur Department of Electrical and Computer Engineering, Stevens Institute ofTechnology, Hoboken, NJ 07030, USA
  • M.A. Haleem Department of Electrical and Computer Engineering, Stevens Institute ofTechnology, Hoboken, NJ 07030, USA
  • K.P. Subbalakshmi Department of Electrical and Computer Engineering, Stevens Institute ofTechnology, Hoboken, NJ 07030, USA
  • R. Chandramouli Department of Electrical and Computer Engineering, Stevens Institute ofTechnology, Hoboken, NJ 07030, USA

DOI:

https://doi.org/10.13052/jcsm2245-1439.1232

Keywords:

scheduling, set covering, graph coloring, wireless ad-hoc networks, NP

Abstract

In this paper we systematically study several channel assignment problems in multi-hop ad-hoc wireless networks in the presence of several constraints. Both regular grids and random topology models are considered in the analysis. We identify three fairness constraints (unfair, fair, and 1-fair), Signal to Interference Ratio (SINR) constraint (to measure the link quality) and balance constraint (for uniform assignment) and study their impact on the complexity of the channel assignment problems. Note that these constraints have an impact on the network capacity, lifetime and connectivity. Although optimal channel assignment for links in a multi-hop wireless network has been shown to be NP complete, the impact of fairness, link quality and balance constraints on the hardness of channel assignment problems is not well studied. In this paper, we show that a class of unfair SINR constrained channel assignment problems can be solved in polynomial time. We show that when fairness is desired the channel assignment problems are NP Complete. We propose two heuristic algorithms that provide 1-fair and fair channel assignments, comment on their complexity and compare their performance with optimal solutions.

Downloads

Download data is not yet available.

Author Biographies

Chetan Nanjunda Mathur, Department of Electrical and Computer Engineering, Stevens Institute ofTechnology, Hoboken, NJ 07030, USA

Chetan Mathur received his Ph.D. in Computer Engineering at Stevens Institute of Technology, New Jersey, USA in 2007. He has an MS in Computer Engineering from Stevens Institute of Technology, New Jersey,USA in 2003. Part of Chetan’s MS thesis was patented by Stevens Institute of Technology. He was born in Bangalore, India in 1981. He received his BE degree in Computer Science from Visveshwaraiah Institute of Technology, Bangalore, India in 2002. Chetan has published several research papers inthe fields of Cryptography, Coding theory and Dynamic spectrum access. He has also received numerous awards including the IEEE best student paper award presented at IEEE Consumer Communications and Networking Conference (CCNC 2006) and the IEEE student travel grant award presented at International Conference on Communications (ICC 2005). He is currently employed in the financial industry.

M.A. Haleem, Department of Electrical and Computer Engineering, Stevens Institute ofTechnology, Hoboken, NJ 07030, USA

M.A. Haleem graduated from Stevens Institute of Technology with a Ph.D.in Electrical and Computer Engineering. His research interests are in the areas of wireless communications and signal processing. He is currently an Assistant Professor at KFUPM, Saudi Arabia.

K.P. Subbalakshmi, Department of Electrical and Computer Engineering, Stevens Institute ofTechnology, Hoboken, NJ 07030, USA

K.P. (Suba) Subbalakshmi is an Associate Professor at Stevens Institute of Technology. Her research interests are in the areas of cognitive radio networks, wireless network security, media forensics as well as social networks. She is the Vice-Chair North America region of IEEE Technical Committee on Cognitive Networks. She has given several key-note addresses, plenary talks and tutorials on DSA security at several international conferences. She has also served as a panelist on cognitive radio network security at international conferences including IEEE Dynamic Spectrum Access: Collaboration between the Technical, Regulatory and Business Communities, IEEE ICC, IEEE Sarnoff Symposium etc. She was a Guest Editor of the EURASIP Journal on Advances in Signal Processing, Special Issue on Dynamic Spectrum Access for Wireless Networks. Her work is/has been supported by the National Science Foundation, National Institute of Justice, DoD agencies as well as the Industry. Suba is also the co-founder of two companies that seek to commercialize some of her research work. One of these is Dynamic Spectrum LLC which commercializes her work inDynamic Spectrum Access Networks.

R. Chandramouli, Department of Electrical and Computer Engineering, Stevens Institute ofTechnology, Hoboken, NJ 07030, USA

R. Chandramouli (Mouli) is the Thomas Hattrick Chair Professor of Information Systems in the Department of Electrical and Computer Engin-eering (ECE) at Stevens Institute of Technology and Co-Director of the Information Networks and Security (iFINITY) research laboratory. He is aCo-Founder of Dynamic Spectrum, LLC – a startup offering cloud-enabled cognitive radio technologies for various markets including consumer commu-nications, public safety, and the DoD; and Jaasuz.com that provides a suite of advanced text forensics technologies to verify trust in documents. His re-search spans the areas of wireless networking, social media analytics/security and computational psycho-linguistic text mining.

References

E. Arikan. Some complexity results about packet radio networks. IEEE Transactions onInformation Theory, 30(4):681–685, July 1984.

I. Chlamtac and A. Lerner. Fair algorithms for maximal link activation in multihop radionetworks. IEEE Transactions on Communications, COM-35(7):739–746, July 1987.

T. Cormen, C. Leiserson, R. Rivest, and C. Stein. Introduction to Algorithms. McGraw-Hill, second edition, 2002.

A. Ephremides and T. Truong. Scheduling broadcasts in multihop radio networks. IEEETransactions on Communications, 38(4):456–460, April 1990.

P. Gupta and P. Kumar. The capacity of wireless networks. IEEE Transactions onInformation Theory, 46(2):388–404, March 2000.

B. Hajek and G. Sasaki. Link scheduling in polynomial time. IEEE Transactions onInformation Theory, 34(5):910–917, September 1988.

J. L. Hammond and H. B. Russell. Properties of a transmission assignment algorithmfor multi-hop packet radio networks. IEEE Transactions on Wireless Communications,3(4):1048–1052, July 2004.

D.S. Johnson. Approximation algorithms for combinatorial problems. In STOC’73: Pro-ceedings of the Fifth Annual ACM Symposium on Theory of Computing, pages 38–49.ACM Press, New York, 1973.

R. Karp. Reducibility among combinatorial problems. In R.E. Miller and J.W. Thatcher(Eds.), Compexity of Computer Computations, pages 85–103. Plenum Press, New York,1972.

S. Kutten and I. Chlamtac. A spatial reuse tdma.fddma for mobile multi-hop radionetworks. In INFOCOM, 1985.

A. Leon-Garcia and I. Widjaja. Communication Networks: Fundamental Concepts andKey Architectures. McGraw-Hill School Education Group, 1999.

C.G. Prohazka. Decoupling link scheduling constraints in multi-hop packet radionetworks. IEEE Trans. Comput., 38(3):455–458, 1989.

S. Ramanathan. A unified framework and algorithm for channel assignment in wirelessnetworks. Wireless Networks, 5:81–94, 1999.

R. Ramaswami and K. Parhi. Distributed scheduling for broadcasts in a radio network.In INFOCOM, 1989.

M.R.Garey and D.S. Johnson. Computers and Intractability, A Guide to the Theory ofNP-Completeness. Freeman and Company, New York, 2003.

P. V ̈arbrand, D. Yuan, and P. Bjorklund. Resource optimization of spatial TDMA in adhoc radio networks: A column generation approach. In INFOCOM, 2003.

Downloads

Published

2012-04-24

How to Cite

1.
Mathur CN, Haleem M, Subbalakshmi K, Chandramouli R. Impact of Constraints on the Complexity and Performance of Channel Assignment in Multi-Hop Wireless Networks. JCSANDM [Internet]. 2012 Apr. 24 [cited 2024 Apr. 25];1(2-3):161-87. Available from: https://journals.riverpublishers.com/index.php/JCSANDM/article/view/6103

Issue

2012: Vol 1 Iss 2-3

Section

Articles