摘要
在SINR模型下研究了无线网络中与链路调度密切相关的两个重要的NP-完全问题:最大链路独立集(Maximum Independent Set of Links,MISL)和最大带权链路独立集(Maximum Weighted Independent Set of Links,MWISL),给出了对这两个问题有好的实际性能保障的有效启发式算法,从理论上证明了算法的正确性,并通过仿真验证了算法的有效性。对于MISL问题,在MTIR算法(Yang等人于2010年提出)的基础上,得到了性能更优的启发式算法MTBR;对于MWISL问题给出的有效启发式算法,比近似算法PMWISL(Wan等人于2011年提出)的性能有了较大的提高。
Two important NP-complete problems, Maximum Independent Set of Links (MISL) and Maximum Weighted Independent Set of Links (MWlSL), which are closely related to link scheduling in wireless networks are studied. Effective heuristic algorithms with prac-tically good performance are proposed for these problem. Theoretical analysis shows the correctness and the simulation proves the effec-tiveness for the proposed algorithms. For MISL, give an algorithm with better performance based on MTIR proposed by Yang (2010) et al. For MWISL,obtain an effective heuristic algorithm which is better than PMWISL proposed by Wan (2011) et al.
出处
《计算机技术与发展》
2015年第2期93-98,共6页
Computer Technology and Development
基金
国家自然科学基金资助项目(61373027
11101243)
山东省自然科学基金(ZR2012FM023
ZR2012FQ011)
山东省中青年科学家奖励基金(BS2009DX024
BS2010DX013)
山东省高校科技计划(J10LG09
J10LG09
J12LN06)