A multi-hop resource scheduling algorithm for IEEE 802.16j relay networks

I. Hsien Liu, Chuan Gang Liu, Chien Tung Lu, Yi Tsen Kuo, Jung Shian Li

Research output: Contribution to journalArticle

3 Citations (Scopus)

Abstract

The IEEE 802.16j standard defines both transparent and non-transparent relay transmission mode. The present study formulates and optimizes the relay resource scheduling problem for the case of a non-transparent relay network. It is shown that the resource scheduling problem is NP-Complete. A method is proposed for optimizing the position of the zone boundary adaptively during the resource scheduling process in order to maximize the system throughput. In addition, a low time complexity algorithm designated as MRRS (multi-hop relay resource scheduling) is proposed to obtain an approximate solution for the NP-Complete scheduling problem. In the proposed algorithm, the zone boundary is adjusted adaptively in accordance with the user distribution and the channel state information in such a way as to improve the utilization of the available slots. The simulation results show that MRRS achieves a higher throughput than existing relay resource scheduling algorithms (GenArgMax and Eliminate-Repeat) with no significant loss in fairness. In addition, it is shown that the performance improvement provided by MRRS increases as the hop-count is increased.

Original languageEnglish
Pages (from-to)164-179
Number of pages16
JournalComputer Networks
Volume67
DOIs
Publication statusPublished - 2014 Jul 4

Fingerprint

Scheduling algorithms
Scheduling
Throughput
Channel state information
Computational complexity

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications

Cite this

Liu, I. Hsien ; Liu, Chuan Gang ; Lu, Chien Tung ; Kuo, Yi Tsen ; Li, Jung Shian. / A multi-hop resource scheduling algorithm for IEEE 802.16j relay networks. In: Computer Networks. 2014 ; Vol. 67. pp. 164-179.
@article{6a3cdcceca8a4d72bf7660031386da84,
title = "A multi-hop resource scheduling algorithm for IEEE 802.16j relay networks",
abstract = "The IEEE 802.16j standard defines both transparent and non-transparent relay transmission mode. The present study formulates and optimizes the relay resource scheduling problem for the case of a non-transparent relay network. It is shown that the resource scheduling problem is NP-Complete. A method is proposed for optimizing the position of the zone boundary adaptively during the resource scheduling process in order to maximize the system throughput. In addition, a low time complexity algorithm designated as MRRS (multi-hop relay resource scheduling) is proposed to obtain an approximate solution for the NP-Complete scheduling problem. In the proposed algorithm, the zone boundary is adjusted adaptively in accordance with the user distribution and the channel state information in such a way as to improve the utilization of the available slots. The simulation results show that MRRS achieves a higher throughput than existing relay resource scheduling algorithms (GenArgMax and Eliminate-Repeat) with no significant loss in fairness. In addition, it is shown that the performance improvement provided by MRRS increases as the hop-count is increased.",
author = "Liu, {I. Hsien} and Liu, {Chuan Gang} and Lu, {Chien Tung} and Kuo, {Yi Tsen} and Li, {Jung Shian}",
year = "2014",
month = "7",
day = "4",
doi = "10.1016/j.comnet.2014.03.030",
language = "English",
volume = "67",
pages = "164--179",
journal = "Computer Networks",
issn = "1389-1286",
publisher = "Elsevier",

}

A multi-hop resource scheduling algorithm for IEEE 802.16j relay networks. / Liu, I. Hsien; Liu, Chuan Gang; Lu, Chien Tung; Kuo, Yi Tsen; Li, Jung Shian.

In: Computer Networks, Vol. 67, 04.07.2014, p. 164-179.

Research output: Contribution to journalArticle

TY - JOUR

T1 - A multi-hop resource scheduling algorithm for IEEE 802.16j relay networks

AU - Liu, I. Hsien

AU - Liu, Chuan Gang

AU - Lu, Chien Tung

AU - Kuo, Yi Tsen

AU - Li, Jung Shian

PY - 2014/7/4

Y1 - 2014/7/4

N2 - The IEEE 802.16j standard defines both transparent and non-transparent relay transmission mode. The present study formulates and optimizes the relay resource scheduling problem for the case of a non-transparent relay network. It is shown that the resource scheduling problem is NP-Complete. A method is proposed for optimizing the position of the zone boundary adaptively during the resource scheduling process in order to maximize the system throughput. In addition, a low time complexity algorithm designated as MRRS (multi-hop relay resource scheduling) is proposed to obtain an approximate solution for the NP-Complete scheduling problem. In the proposed algorithm, the zone boundary is adjusted adaptively in accordance with the user distribution and the channel state information in such a way as to improve the utilization of the available slots. The simulation results show that MRRS achieves a higher throughput than existing relay resource scheduling algorithms (GenArgMax and Eliminate-Repeat) with no significant loss in fairness. In addition, it is shown that the performance improvement provided by MRRS increases as the hop-count is increased.

AB - The IEEE 802.16j standard defines both transparent and non-transparent relay transmission mode. The present study formulates and optimizes the relay resource scheduling problem for the case of a non-transparent relay network. It is shown that the resource scheduling problem is NP-Complete. A method is proposed for optimizing the position of the zone boundary adaptively during the resource scheduling process in order to maximize the system throughput. In addition, a low time complexity algorithm designated as MRRS (multi-hop relay resource scheduling) is proposed to obtain an approximate solution for the NP-Complete scheduling problem. In the proposed algorithm, the zone boundary is adjusted adaptively in accordance with the user distribution and the channel state information in such a way as to improve the utilization of the available slots. The simulation results show that MRRS achieves a higher throughput than existing relay resource scheduling algorithms (GenArgMax and Eliminate-Repeat) with no significant loss in fairness. In addition, it is shown that the performance improvement provided by MRRS increases as the hop-count is increased.

UR - http://www.scopus.com/inward/record.url?scp=84899755814&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84899755814&partnerID=8YFLogxK

U2 - 10.1016/j.comnet.2014.03.030

DO - 10.1016/j.comnet.2014.03.030

M3 - Article

AN - SCOPUS:84899755814

VL - 67

SP - 164

EP - 179

JO - Computer Networks

JF - Computer Networks

SN - 1389-1286

ER -