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

Relay Placement Algorithms Based on Clique Partition in WiMAX Mesh Networks

作　　者：廖卓凡[1,2] 王建新[1] 张士庚[1] 

机构地区：[1]中南大学信息科学与工程学院,长沙410083 [2]长沙理工大学计算机与通信工程学院,长沙410004

出　　处：《计算机学报》2013年第5期937-946,共10页Chinese Journal of Computers

基　　金：国家自然科学基金面上项目(61073036);国家自然科学基金青年项目(61103203);国家自然科学基金创新群体科学基金项目(70921001);新世纪优秀人才支持计划(NCET-10-0798)资助~~

摘　　要：集成多跳中继技术的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.

关 键 词：WIMAX MESH网络 中继 多跳 部署 团划分 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]