Different Approximation Algorithms for Channel Scheduling in Wireless Networks
Joint Authors
Fu, Bin
Ni, Qiufen
Huang, Chuanhe
Pardalos, Panos M.
Ye, Jia
Source
Issue
Vol. 2020, Issue 2020 (31 Dec. 2020), pp.1-13, 13 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2020-11-16
Country of Publication
Egypt
No. of Pages
13
Main Subjects
Telecommunications Engineering
Abstract EN
We introduce a new two-side approximation method for the channel scheduling problem, which controls the accuracy of approximation in two sides by a pair of parameters f,g.
We present a series of simple and practical-for-implementation greedy algorithms which give constant factor approximation in both sides.
First, we propose four approximation algorithms for the weighted channel allocation problem: 1.
a greedy algorithm for the multichannel with fixed interference radius scheduling problem is proposed and an one side O1-IS-approximation is obtained; 2.
a greedy O1,O1-approximation algorithm for single channel with fixed interference radius scheduling problem is presented; 3.
we improve the existing algorithm for the multichannel scheduling and show an EOd/ε time 1−ϵ-approximation algorithm; 4.
we speed up the polynomial time approximation scheme for single-channel scheduling through merging two algorithms and show a 1−ϵ,O1-approximation algorithm.
Next, we study two polynomial time constant factor greedy approximation algorithms for the unweighted channel allocation with variate interference radius.
A greedy O1-approximation algorithm for the multichannel scheduling problem and an O1,O1-approximation algorithm for single-channel scheduling problem are developed.
At last, we do some experiments to verify the effectiveness of our proposed methods.
American Psychological Association (APA)
Ni, Qiufen& Huang, Chuanhe& Pardalos, Panos M.& Ye, Jia& Fu, Bin. 2020. Different Approximation Algorithms for Channel Scheduling in Wireless Networks. Mobile Information Systems،Vol. 2020, no. 2020, pp.1-13.
https://search.emarefa.net/detail/BIM-1192520
Modern Language Association (MLA)
Ni, Qiufen…[et al.]. Different Approximation Algorithms for Channel Scheduling in Wireless Networks. Mobile Information Systems No. 2020 (2020), pp.1-13.
https://search.emarefa.net/detail/BIM-1192520
American Medical Association (AMA)
Ni, Qiufen& Huang, Chuanhe& Pardalos, Panos M.& Ye, Jia& Fu, Bin. Different Approximation Algorithms for Channel Scheduling in Wireless Networks. Mobile Information Systems. 2020. Vol. 2020, no. 2020, pp.1-13.
https://search.emarefa.net/detail/BIM-1192520
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-1192520