Elsevier

Computer Networks

Volume 52, Issue 11, 8 August 2008, Pages 2148-2158
Computer Networks

Joint spectrum allocation and scheduling for fair spectrum sharing in cognitive radio wireless networks

https://doi.org/10.1016/j.comnet.2008.03.010Get rights and content

Abstract

Cognitive radio and Dynamic Spectrum Access (DSA) enable wireless users to share a wide range of available spectrums. In this paper, we study joint spectrum allocation and scheduling problems in cognitive radio wireless networks with the objectives of achieving fair spectrum sharing. A novel Multi-Channel Contention Graph (MCCG) is proposed to characterize the impact of interference under the protocol model in such networks. Based on the MCCG, we present an optimal algorithm to compute maximum throughput solutions. As simply maximizing throughput may result in a severe bias on resource allocation, we take fairness into consideration by presenting optimal algorithms as well as fast heuristics to compute fair solutions based on a simplified max–min fairness model and the well-known proportional fairness model. Numerical results show that the performance given by our heuristic algorithms is very close to that of the optimal solution, and our proportional fair algorithms achieve a good tradeoff between throughput and fairness. In addition, we extend our research to the physical interference model, and propose effective heuristics for solving the corresponding problems.

Introduction

Over the past few years, the world has experienced a very rapid proliferation of wireless devices. The traditional static spectrum access approach, which assigns a fixed portion of the spectrum to a specific license holder or a wireless service for exclusive use, is unable to manage the spectrum efficiently any longer. On one hand, certain parts of the spectrum are heavily used, such as the 2.4 GHz band and the 5 GHz band, which leads to serious interference and therefore poor network throughput. On the other hand, a significant amount of spectrums remain under-utilized or not utilized at all, which has been shown by recent studies and experiments [2].

The most efficient and direct method to solve the above problems is to allow wireless users to share a wide range of available spectrums. Emerging cognitive radio technology and the Dynamic Spectrum Access (DSA) approach enable unlicensed wireless users (a.k.a secondary users) to sense and access the under-utilized spectrum opportunistically even if it is licensed, as long as the licensed wireless users (a.k.a primary users) in such a spectrum band are not interfered. A network composed of wireless users with cognitive radios and dynamic spectrum access capabilities is called a cognitive radio wireless network or a DSA wireless network [2].

How to efficiently and fairly share the available spectrums is a fundamental and challenging problem in cognitive radio wireless networks [2]. In a multihop wireless network, a wireless user usually refers to a transmitter and receiver pair (a wireless link) [11]. The spectrum sharing problem usually involves two coupled problems: the spectrum allocation problem and the scheduling problem. The spectrum allocation problem seeks a solution which allocates available spectrum bands to the users for packet transmissions. The scheduling problem looks for a solution which determines when these users can access the allocated spectrum bands. The objective is to achieve a good tradeoff between throughput and fairness while ensuring interference-free transmission at any time. In this paper, we present optimal algorithms as well as fast heuristic algorithms to solve the joint spectrum allocation and scheduling problems in multihop cognitive radio wireless networks. Specifically, our contributions are summarized as follows:

  • 1.

    We propose a novel Multi-Channel Contention Graph (MCCG) to precisely characterize the impact of interference in a cognitive radio wireless network.

  • 2.

    We study the joint spectrum allocation and scheduling problems, which have never been seriously addressed before in the context of multihop cognitive radio wireless networks. We present optimal algorithms as well as fast heuristic algorithms to solve these problems and evaluate their performance by extensive simulations.

  • 3.

    We take account of both the protocol and the physical interference models [7], making our solutions more comprehensive and more suitable for practical scenarios. If each wireless user is assumed to transmit at a fixed power level, the protocol model can be used to address interference. However, if users have the power control capability, the physical interference model should be considered.

The rest of this paper is organized as follows. We discuss related work in Section 2. The system model is described in Section 3. We define the problems to be studied in Section 4. The proposed spectrum allocation and scheduling algorithms are presented in Section 5. We present numerical results in Section 6 and conclude the paper in Section 7.

Section snippets

Related work

The cognitive radio wireless networks have recently attracted lots of research attention. The most related work is [26], in which Zheng et al. developed a graph-theoretic model to characterize the spectrum access problem and devised a set of heuristics to find high throughput and fair solutions. In [24], the concept of a time-spectrum block was introduced to model spectrum reservation, and protocols were presented to allocate such blocks. A centralized spectrum allocation protocol called

System model

We consider a multihop cognitive radio wireless network composed of static secondary users, each of which refers to a transmitter and receiver pair (i.e., a wireless link). The network can be either a traditional single radio wireless network or an emerging multi-radio wireless network [16] in which each node is equipped with multiple transceivers. The available spectrums are divided into a set of orthogonal spectrum bands, which are also called channels. We assume that a user can dynamically

Problem definition

In this section, we will describe the necessary notations and formally define the optimization problems to be studied.

Suppose that we are given a set of N users indexed from 1 to N and a set of C channels indexed from 1 to C. Then we can identify the set of possible user-channel pairs, denoted as A. Here, a user-channel pair (i,j) is in A if and only if channel j is available to user i. The total number of user-channel pairs is bounded by N·C. We are also given a vector d=[d1,d2,,dN],

Proposed spectrum allocation and scheduling algorithms

In this section, we will first introduce a novel graph model, Multi-Channel Contention Graph (MCCG), to characterize the impact of interference under the protocol model. Based on it, we will present algorithms to solve the problems defined in Section 4. Then we will discuss the extension to the physical interference model.

Numerical results

In our simulation, we considered multihop cognitive radio wireless networks with stationary nodes randomly located in a region. We randomly chose N users (links) from a network in each run. For the protocol model, the transmission range and corresponding interference range of each user were set to 250m and 500m [16] for all channels, respectively. For the physical model, we set the thermal noise power N0=-90dBm, the SINR threshold β=10dB and the maximum transmission power Pmax=300mW [17]. The

Conclusions

In this paper, we have studied the joint spectrum allocation and scheduling in cognitive radio wireless networks. Specifically, under the protocol interference model, we proposed a novel Multi-Channel Contention Graph (MCCG) to characterize the impact of interference. We have formally defined the MASS problem, the MMASS problem, and the PASS problem. For each problem, we presented an optimal algorithm and a fast heuristic algorithm based on the MCCG. In addition, we proposed fast and effective

Jian Tang is an assistant professor in the Department of Computer Science at Montana State University. He received his Ph.D. degree in Computer Science from Arizona State University in 2006. His research interests are in the areas of wireless networking and mobile computing. He has served on the technical program committees of many international conferences such as ICC’2007, Globecom’2007, IPCCC’2007 and QShine’2007. He also served as a publicity co-chair of International Conference on

References (26)

  • D. Johnson et al.

    On generating all maximal independent sets

    Information Processing Letters

    (1988)
  • M. Alicherry, R. Bhatia, L. Li, Joint channel assignment and routing for throughput optimization in multi-radio...
  • I.F. Akyildiz et al.

    NeXt generation/dynamic spectrum access/cognitive radio wireless networks: a survey

    Elsevier Journal of Computer Networks

    (2007)
  • M.S. Bazaraa et al.

    Linear Programming and Network Flows

    (2005)
  • S. Boyd et al.

    Convex Optimization

    (2004)
  • V. Brik, E. Rozner, S. Banarjee and P. Bahl, DSAP: a protocol for coordinated spectrum access, Proceedings of IEEE...
  • L. Cao and H. Zheng, Distributed spectrum allocation via local bargaining, Proceedings of IEEE Secon’2005, pp....
  • P. Gupta et al.

    The capacity of wireless networks

    IEEE Transactions on Information Theory

    (2000)
  • M. Halldorsson et al.

    Low-degree graph partitioning via local search with applications to constraint satisfaction, max cut, and 3-coloring

    Journal of Graph Algorithms and Applications

    (1997)
  • Y.T. Hou, Y. Shi, H.D. Sherali, Rate allocation in wireless sensor networks with network lifetime requirement, in:...
  • Y.T. Hou, Y. Shi, H.D. Sherali, Optimal spectrum sharing for multi-hop software defined radio networks, in: Proceedings...
  • J. Huang, R.A. Berry, M.L. Honig, Spectrum sharing with distributed interference compensation, in: Proceedings of IEEE...
  • IEEE 802.11a Working Group, Wireless LAN MAC and PHY Specifications – Amendment 1: High-Speed Physical Layer in the...
  • Jian Tang is an assistant professor in the Department of Computer Science at Montana State University. He received his Ph.D. degree in Computer Science from Arizona State University in 2006. His research interests are in the areas of wireless networking and mobile computing. He has served on the technical program committees of many international conferences such as ICC’2007, Globecom’2007, IPCCC’2007 and QShine’2007. He also served as a publicity co-chair of International Conference on Autonomic Computing and Communication Systems (Autonomics’2007).

    Satyajayant Misra received his integrated M.Sc. (Tech) Information Systems and M.Sc.(Hons) Physics in June 2003 from the Birla Institute of Technology and Sciences (BITS), Pilani. He is currently a Ph.D. student in the Department of Computer Science and Engineering at Arizona State University. His research interests include identifying security, privacy, and reliability issues in wireless sensors and ad hoc networks and formulating efficient solutions to handle them.

    Guoliang Xue is a Full Professor in the Department of Computer Science and Engineering at Arizona State University. He received the Ph.D. degree in Computer Science from the University of Minnesota in 1991 and has held previous positions at the Army High Performance Computing Research Center and the University of Vermont. His research interests include efficient algorithms for optimization problems in networking, with applications to fault tolerance, robustness, and privacy issues in networks ranging from WDM optical networks to wireless ad hoc and sensor networks. He has published over 150 papers in these areas. His research has been continuously supported by federal agencies including NSF and ARO. He is the recipient of an NSF Research Initiation Award in 1994 and an NSF-ITR Award in 2003. He is an Associate Editor of Computer Networks (COMNET), the IEEE Network Magazine, and Journal of Global Optimization. He has served on the executive/program committees of many IEEE conferences, including INFOCOM, SECON, IWQOS, ICC, GLOBECOM and QShine. He is the General Chair of IEEE IPCCC’2005, a TPC co-Chair of IPCCC’2003, HPSR’2004, IEEE Globecom’2006 Symposium on Wireless Ad Hoc and Sensor Networks, IEEE ICC’2007 Symposium on Wireless Ad Hoc and Sensor Networks, and QShine’2007. He is a senior member of IEEE.

    This research was supported in part by NSF Grants CNS-0721880, CNS-0721803, CCF-0431167 and ARO Grant W911NF-04-1-0385. The information reported here does not reflect the position or the policy of the federal government.

    View full text