Joint spectrum allocation and scheduling for fair spectrum sharing in cognitive radio wireless networks☆
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 . Here, a user-channel pair is in if and only if channel j is available to user i. The total number of user-channel pairs is bounded by . We are also given a vector ,
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 and [16] for all channels, respectively. For the physical model, we set the thermal noise power , the SINR threshold and the maximum transmission power [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)
- 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...
- et al.
NeXt generation/dynamic spectrum access/cognitive radio wireless networks: a survey
Elsevier Journal of Computer Networks
(2007) - et al.
Linear Programming and Network Flows
(2005) - 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....
- et al.
The capacity of wireless networks
IEEE Transactions on Information Theory
(2000) - 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:...
Cited by (88)
Research on spectrum scheduling based on discrete artificial bee colony algorithm
2021, Journal of Physics: Conference SeriesChannel scheduling by spectrum channel white space filling in cognitive radio networks
2020, Proceedings of CONECCT 2020 - 6th IEEE International Conference on Electronics, Computing and Communication TechnologiesEconomic-Robust Transmission Opportunity Auction for D2D Communications in Cognitive Mesh Assisted Cellular Networks
2018, IEEE Transactions on Mobile Computing
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.