CAJ | 학술논문

在SINR模型下研究了无线网络中与链路调度密切相关的两个重要的NP-完全问题：最大链路独立集( Maximum Independent Set of Links,MISL)和最大带权链路独立集( Maximum Weighted Independent Set of Links,MWISL),给出了对这两个问题有好的实际性能保障的有效启发式算法,从理论上证明了算法的正确性,并通过仿真验证了算法的有效性。对于MISL问题,在MTIR算法( Yang等人于2010年提出)的基础上,得到了性能更优的启发式算法MTBR；对于MWISL问题给出的有效启发式算法,比近似算法PMWISL( Wan等人于2011年提出)的性能有了较大的提高。
재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 ( MWISL) ,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.