Clique partition based relay placement in WiMAX mesh networks

Zhuofan Liao; Jianxin Wang; Shigeng Zhang; Jiannong Cao

doi:10.1109/GLOCOM.2012.6503503

Clique partition based relay placement in WiMAX mesh networks

Zhuofan Liao, Jianxin Wang, Shigeng Zhang, Jiannong Cao

Research output: Chapter in book / Conference proceeding › Conference article published in proceeding or book › Academic research › peer-review

5 Citations (Scopus)

Abstract

In WiMAX mesh networks based on IEEE 802.16j, when transmission power of the base station (BS) and the number of radios and channels are settled, data rate at the subscriber (SS) is decided by the distance between the SS and its uplink relay station (RS). In this paper, we study the problem of deploying a minimum number of RSs to satisfy all SSs' distance requirements. Firstly, we translate it into a minimum clique partition problem, which is NP-complete. Based on SSs' neighbor information and location information, we then propose two heuristic algorithms based on clique partition, named as MAXDCP and GEOCP, respectively. Simulation results show that, compared with the state-of-the-art MIS and HS algorithms, MAXDCP uses 23.8% fewer relays than MIS with the same time complexity, and GEOCP uses 35% fewer relays than MIS in the same time and 18.5% fewer relays than HS in much less time.

Original language	English
Title of host publication	2012 IEEE Global Communications Conference, GLOBECOM 2012
Pages	2566-2571
Number of pages	6
DOIs	https://doi.org/10.1109/GLOCOM.2012.6503503
Publication status	Published - 1 Dec 2012
Externally published	Yes
Event	2012 IEEE Global Communications Conference, GLOBECOM 2012 - Anaheim, CA, United States Duration: 3 Dec 2012 → 7 Dec 2012

Conference

Conference	2012 IEEE Global Communications Conference, GLOBECOM 2012
Country/Territory	United States
City	Anaheim, CA
Period	3/12/12 → 7/12/12

Keywords

multi-hop relay
placement
WiMAX mesh network

ASJC Scopus subject areas

Electrical and Electronic Engineering

More information

10.1109/GLOCOM.2012.6503503

Cite this

@inproceedings{2e2a2b451fe948ac9aa357a3c728b9c8,

title = "Clique partition based relay placement in WiMAX mesh networks",

abstract = "In WiMAX mesh networks based on IEEE 802.16j, when transmission power of the base station (BS) and the number of radios and channels are settled, data rate at the subscriber (SS) is decided by the distance between the SS and its uplink relay station (RS). In this paper, we study the problem of deploying a minimum number of RSs to satisfy all SSs' distance requirements. Firstly, we translate it into a minimum clique partition problem, which is NP-complete. Based on SSs' neighbor information and location information, we then propose two heuristic algorithms based on clique partition, named as MAXDCP and GEOCP, respectively. Simulation results show that, compared with the state-of-the-art MIS and HS algorithms, MAXDCP uses 23.8% fewer relays than MIS with the same time complexity, and GEOCP uses 35% fewer relays than MIS in the same time and 18.5% fewer relays than HS in much less time.",

keywords = "multi-hop relay, placement, WiMAX mesh network",

author = "Zhuofan Liao and Jianxin Wang and Shigeng Zhang and Jiannong Cao",

year = "2012",

month = dec,

day = "1",

doi = "10.1109/GLOCOM.2012.6503503",

language = "English",

isbn = "9781467309219",

pages = "2566--2571",

booktitle = "2012 IEEE Global Communications Conference, GLOBECOM 2012",

note = "2012 IEEE Global Communications Conference, GLOBECOM 2012 ; Conference date: 03-12-2012 Through 07-12-2012",

}

TY - GEN

T1 - Clique partition based relay placement in WiMAX mesh networks

AU - Liao, Zhuofan

AU - Wang, Jianxin

AU - Zhang, Shigeng

AU - Cao, Jiannong

PY - 2012/12/1

Y1 - 2012/12/1

N2 - In WiMAX mesh networks based on IEEE 802.16j, when transmission power of the base station (BS) and the number of radios and channels are settled, data rate at the subscriber (SS) is decided by the distance between the SS and its uplink relay station (RS). In this paper, we study the problem of deploying a minimum number of RSs to satisfy all SSs' distance requirements. Firstly, we translate it into a minimum clique partition problem, which is NP-complete. Based on SSs' neighbor information and location information, we then propose two heuristic algorithms based on clique partition, named as MAXDCP and GEOCP, respectively. Simulation results show that, compared with the state-of-the-art MIS and HS algorithms, MAXDCP uses 23.8% fewer relays than MIS with the same time complexity, and GEOCP uses 35% fewer relays than MIS in the same time and 18.5% fewer relays than HS in much less time.

AB - In WiMAX mesh networks based on IEEE 802.16j, when transmission power of the base station (BS) and the number of radios and channels are settled, data rate at the subscriber (SS) is decided by the distance between the SS and its uplink relay station (RS). In this paper, we study the problem of deploying a minimum number of RSs to satisfy all SSs' distance requirements. Firstly, we translate it into a minimum clique partition problem, which is NP-complete. Based on SSs' neighbor information and location information, we then propose two heuristic algorithms based on clique partition, named as MAXDCP and GEOCP, respectively. Simulation results show that, compared with the state-of-the-art MIS and HS algorithms, MAXDCP uses 23.8% fewer relays than MIS with the same time complexity, and GEOCP uses 35% fewer relays than MIS in the same time and 18.5% fewer relays than HS in much less time.

KW - multi-hop relay

KW - placement

KW - WiMAX mesh network

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

U2 - 10.1109/GLOCOM.2012.6503503

DO - 10.1109/GLOCOM.2012.6503503

M3 - Conference article published in proceeding or book

SN - 9781467309219

SP - 2566

EP - 2571

BT - 2012 IEEE Global Communications Conference, GLOBECOM 2012

T2 - 2012 IEEE Global Communications Conference, GLOBECOM 2012

Y2 - 3 December 2012 through 7 December 2012

ER -

Clique partition based relay placement in WiMAX mesh networks

Abstract

Conference

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this