Different Approximation Algorithms for Channel Scheduling in Wireless Networks

Joint Authors

Fu, Bin
Ni, Qiufen
Huang, Chuanhe
Pardalos, Panos M.
Ye, Jia

Source

Mobile Information Systems

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)

Fu, Bin…[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