Allocating dynamic time-spectrum blocks in cognitive radio networks

ABSTRACT

A number of studies have shown the abundance of unused spectrum in the TV bands. This is in stark contrast to the overcrowding of wireless devices in the ISM bands. A recent trend to alleviate this disparity is the design of Cognitive Radios, which constantly sense the spectrum and opportunistically utilize unused frequencies in the TV bands. In this paper, we introduce the concept of a time-spectrum block to model spectrum reservation, and use it to present a theoretical formalization of the spectrum allocation problem in cognitive radio networks. We present a centralized and a distributed protocol for spectrum allocation and show that these protocols are close to optimal in most scenarios. We have implemented the distributed protocol in QualNet and show that our analysis closely matches the simulation results.

REFERENCES

• 1: FCC, Unlicensed Operation in the TV Broadcast Bands Notice of Proposed Rulemaking (NPRM), ET Docket No. 04-186, May, 2004.
• 2: IEEE 802.11a-1999 IEEE Standard Part 11: wireless LAN Medium Access Control (MAC)and Physical Layer (PHY) specifications: high-speed physical layer in the 5 GHz band.
• 3: IEEE 802. 22 WRAN WG, www.ieee802.org/22/.
• 4: QualNet, http://www.qualnet.com/.
• 5: Shared Spectrum Company, www.sharedspectrum.com.
• 6: Arunesh Mishra , Vivek Shrivastava , Dheeraj Agrawal , Suman Banerjee , Samrat Ganguly, Distributed channel management in uncoordinated wireless environments, Proceedings of the 12th annual international conference on Mobile computing and networking, September 23-29, 2006, Los Angeles, CA, USA [doi>10.1145/1161089.1161109]
• 7: G. Bianchi. Performance Analysis of the IEEE 802.11 Distributed Coordination Function. IEEE JSAC 18(3), 2000.
• 8: Milind M. Buddhikot , Paul Kolodzy , Scott Miller , Kevin Ryan , Jason Evans, DIMSUMNet: New Directions in Wireless Networking Using Coordinated Dynamic Spectrum Access, Proceedings of the Sixth IEEE International Symposium on World of Wireless Mobile and Multimedia Networks, p.78-85, June 13-16, 2005 [doi>10.1109/WOWMOM.2005.36]
• 9: T. ElBatt and A. Ephremides. Joint Scheduling and Power Control for Wireless Ad Hoc Networks. IEEE Transactions on Wireless Communications 3(1), 2004.
• 10: Zuyuan Fang , Brahim Bensaou , Yu Wang, Performance evaluation of a fair backoff algorithm for IEEE 802.11 DFWMAC, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland [doi>10.1145/513800.513807]
• 11: A. Graf, M. Stumpf, and G. Weissenfels. On Coloring Unit Disk Graphs. Algorithmica 20, 1998.
• 12: P. Gupta and P. R. Kumar. The Capacity of Wireless Networks. IEEE Transactions on Information Theory (2):388--404, 2000.
• 13: Gurashish Brar , Douglas M. Blough , Paolo Santi, Computationally efficient scheduling with the physical interference model for throughput improvement in wireless mesh networks, Proceedings of the 12th annual international conference on Mobile computing and networking, September 23-29, 2006, Los Angeles, CA, USA [doi>10.1145/1161089.1161092]
• 14: J. Proakis, Digital Communications, McGraw Hill, 2001.
• 15: Jungmin So , Nitin H. Vaidya, Multi-channel mac for ad hoc networks: handling multi-channel hidden terminals using a single transceiver, Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, May 24-26, 2004, Roppongi Hills, Tokyo, Japan [doi>10.1145/989459.989487]
• 16: J. Zhao, H. Zheng, G. Yang. Distributed Coordination in Dynamic Spectrum Allocation Networks. In Dyspan 2005
• 17: Sven O. Krumke , Madhav V. Marathe , S. S. Ravi, Models and approximation algorithms for channel assignment in radio networks, Wireless Networks, v.7 n.6, p.575-584, November 2001 [doi>10.1023/A:1012311216333 ]
• 18: L. Ma, X. Han, C. Shen. Dynamic open spectrum sharing MAC protocol for wireless ad hoc networks. In IEEE Dyspan 2005
• 19: M. Marathe, H. Breu, H. HuntIII, S. S. Ravi, and D. Rosenkrantz. Simple Heuristics for Unit Disk Graphs. Networks 25, 1995.
• 20: T. Moscibroda, R. Wattenhofer, and Y. Weber. Protocol Design Beyond Graph-Based Models. In ACM HotNets 2006
• 21: Paramvir Bahl , Ranveer Chandra , John Dunagan, SSCH: slotted seeded channel hopping for capacity improvement in IEEE 802.11 ad-hoc wireless networks, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA [doi>10.1145/1023720.1023742]
• 22: P. Kyasanur, J. So, C. Chereddi, and N. H. Vaidya. Multi-Channel Mesh Networks:Challenges and Protocols. In IEEE Wireless Communications, April 2006
• 23: Q. Zhao, L. Tong, Swami, A. Decentralized cognitive mac for dynamic spectrum access. In IEEE Dyspan 2005
• 24: R. Maheshwari, H. Gupta, S. Das. MAC Protocol for Multiple Channels. In IEEE SECON 2006
• 25: S. Ramanathan , Errol L. Lloyd, Scheduling algorithms for multi-hop radio networks, Conference proceedings on Communications architectures & protocols, p.211-222, August 17-20, 1992, Baltimore, Maryland, United States
• 26: Thomas Moscibroda and Roger Wattenhofer. The Complexity of Connectivity in Wireless Networks. In IEEE Infocom 2006
• 27: V. Brik, E. Rozner, S. Banerjee, and P. Bahl. DSAP: A Protocol for Coordinated Spectrum Access. In IEEE Dyspan 2005
• 28: Weizhao Wang , Yu Wang , Xiang-Yang Li , Wen-Zhan Song , Ophir Frieder, Efficient interference-aware TDMA link scheduling for static wireless networks, Proceedings of the 12th annual international conference on Mobile computing and networking, September 23-29, 2006, Los Angeles, CA, USA [doi>10.1145/1161089.1161119]
• 29: S.-L. Wu , C.-Y Lin , Y.-C. Tseng , J.-P. Sheu, A New Multi-Channel MAC Protocol with On-Demand Channel Assignment for Multi-Hop Mobile Ad Hoc Networks, Proceedings of the 2000 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '00), p.232, December 07-07, 2000
• 30: Y. Yuan, P. Bahl, R. Chandra, P. A. Chou, J. I. Ferrell, T. Moscibroda, S. Narlanka, and Y. Wu. KNOWS: Kognitive Networking Over White Spaces. In IEEE Dyspan 2007.

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:
Algorithms, Theory

Keywords:
adaptive channel-width, cognitive radio networks, interval coloring, spectrum allocation