SINR模型下链路调度问题的启发式算法

Heuristic Algorithms for Link Scheduling Problem under SINR Model

在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.