Clique partition based relay placement in WiMAX mesh networks

Zhuofan Liao, Jianxin Wang, Shigeng Zhang, Jiannong Cao

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

4 Citations (Scopus)


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 languageEnglish
Title of host publication2012 IEEE Global Communications Conference, GLOBECOM 2012
Number of pages6
Publication statusPublished - 1 Dec 2012
Externally publishedYes
Event2012 IEEE Global Communications Conference, GLOBECOM 2012 - Anaheim, CA, United States
Duration: 3 Dec 20127 Dec 2012


Conference2012 IEEE Global Communications Conference, GLOBECOM 2012
Country/TerritoryUnited States
CityAnaheim, CA


  • multi-hop relay
  • placement
  • WiMAX mesh network

ASJC Scopus subject areas

  • Electrical and Electronic Engineering

Cite this