Clique Partition Based Relay Placement in WiMAX Mesh Networks
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, the authors study the problem of deploying a minimum number of RSs to satisfy all SSs' distance requirements. Firstly, they translate it into a minimum clique partition problem, which is NP-complete. Based on SSs' neighbor information and location information, they then propose two heuristic algorithms based on clique partition, named as MAXDCP and GEOCP, respectively.