WiMAX Mesh网络中基于团划分的中继部署算法

Relay Placement Algorithms Based on Clique Partition in WiMAX Mesh Networks

集成多跳中继技术的WiMAX Mesh网络中,当发送功率和信道数目一定时,用户接入链路的传输速率直接取决于用户到中继的距离.在满足用户到中继距离要求的条件下,研究最少中继部署问题具有保证网络性能、降低组网成本的意义.文中将该问题转化为最少团划分问题,基于用户邻居信息提出启发式算法MAXDCP,基于用户位置信息提出启发式算法GEOCP.模拟结果表明:与该问题的最新算法MIS相比,在相同时间复杂度下,MAXDCP部署中继的个数平均减少23.8%,GEOCP平均减少35%;与已有PTAS算法HS相比,GEOCP部署中继个数平均减少18.5%,且时间复杂度更低.MAXDCP和GEOCP很好地保证了网络性能、降低了组网成本.

In WiMAX Mesh networks based on IEEE 802.16j, when the transmission power of Base station and the number of radios and channels are settled, the distances between subscribers （SSs） and uplink relays （RSs） directly reflect SSs＇ data rate requests. In this paper, we study the problem of deploying a minimum number of RS to satisfy all SSs＇ distance requirements. We firsly formalize the problem as a minimum clique partition problem, which is NP-complete. Based on SSs＇ neighor information and locations information, we then propose two clique partition heu- ristic algorithms, named as MAXDCP and GEOCP, respectively. Simulation results show that, compared with the existing algorithms MIS and HS, MAXDCP places 23.8% and GEOCP places 35% fewer relays than MIS does with the same time complexity, GEOCP places 18.5% fewer relays than HS does in much less time.