NDLI: A Graph-Theoretic Approach to Scheduling in Cognitive Radio Networks

Please wait, while we are loading the content...

A Graph-Theoretic Approach to Scheduling in Cognitive Radio Networks

Content Provider	IEEE Xplore Digital Library
Author	Gozupek, D. Shalom, M. Alagoz, F.
Copyright Year	1993
Abstract	We focus on throughput-maximizing, max-min fair, and proportionally fair scheduling problems for centralized cognitive radio networks. First, we propose a polynomial-time algorithm for the throughput-maximizing scheduling problem. We then elaborate on certain special cases of this problem and explore their combinatorial properties. Second, we prove that the max-min fair scheduling problem is NP-Hard in the strong sense. We also prove that the problem cannot be approximated within any constant factor better than 2 unless P=NP. Additionally, we propose an approximation algorithm for the max-min fair scheduling problem with approximation ratio depending on the ratio of the maximum possible data rate to the minimum possible data rate of a secondary users. We then focus on the combinatorial properties of certain special cases and investigate their relation with various problems such as the multiple-knapsack, matching, terminal assignment, and Santa Claus problems. We then prove that the proportionally fair scheduling problem is NP-Hard in the strong sense and inapproximable within any additive constant less than log(4/3). Finally, we evaluate the performance of our approximation algorithm for the max-min fair scheduling problem via simulations. This approach sheds light on the complexity and combinatorial properties of these scheduling problems, which have high practical importance in centralized cognitive radio networks.
Sponsorship	IEEE Computer Society IEEE Communications Society Association for Computing Machinery (ACM)
Starting Page	317
Ending Page	328
Page Count	12
File Size	1803498
File Format	PDF
ISSN	10636692
Volume Number	23
Issue Number	1
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2015-01-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Scheduling Approximation methods Approximation algorithms Throughput Time-frequency analysis Cognitive radio Linear programming scheduling Algorithmic graph theory approximation algorithms cognitive radio networks dynamic spectrum access resource allocation
Content Type	Text
Resource Type	Article
Subject	Computer Networks and Communications Electrical and Electronic Engineering Computer Science Applications Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Throughput Satisfaction-Based Scheduling for Cognitive Radio Networks

A Spectrum Switching Delay-Aware Scheduling Algorithm for Centralized Cognitive Radio Networks

An Auction Theory Based Algorithm for Throughput Maximizing Scheduling in Centralized Cognitive Radio Networks

Cognitive radio frequency assignment with interference weighting and categorization

Distributed Resource Allocation Based on Queue Balancing in Multihop Cognitive Radio Networks

Dynamic system level frequency spectrum allocation scheme based on cognitive radio technology

Optimal Channel Probing and Transmission Scheduling for Opportunistic Spectrum Access

Dynamic Power Allocation Under Arbitrary Varying Channels—An Online Approach

Spectrum Auction Framework for Access Allocation in Cognitive Radio Networks

A Graph-Theoretic Approach to Scheduling in Cognitive Radio Networks

Similar Documents

Throughput Satisfaction-Based Scheduling for Cognitive Radio Networks

A Spectrum Switching Delay-Aware Scheduling Algorithm for Centralized Cognitive Radio Networks

An Auction Theory Based Algorithm for Throughput Maximizing Scheduling in Centralized Cognitive Radio Networks

Cognitive radio frequency assignment with interference weighting and categorization

Distributed Resource Allocation Based on Queue Balancing in Multihop Cognitive Radio Networks

Dynamic system level frequency spectrum allocation scheme based on cognitive radio technology

Optimal Channel Probing and Transmission Scheduling for Opportunistic Spectrum Access

Dynamic Power Allocation Under Arbitrary Varying Channels—An Online Approach

Spectrum Auction Framework for Access Allocation in Cognitive Radio Networks

A Graph-Theoretic Approach to Scheduling in Cognitive Radio Networks