基于SINR的无线网状网络最大链路调度算法

SINR based Maximum Link Scheduling in Wireless Mesh Networks

在无线网状网络(Wireless Mesh Networks,WMN)中,链路调度是一个关乎网络吞吐量和时延有关的重要基本问题.对于一个给定的通信请求链路集合L={l 1,l 2,…l n},最大链路调度(Maximum Link Scheduling,MLS)问题旨在找到L中的最大数量的子集合S,从而可以成功地调度集合S中的链路.大多数现有的研究工作没有考虑双向传输背景下的链路调度问题,而双向传输更加贴近真实的网络场景.该文提出了一种基于SINR(Signal to Interference and Noise Ratio)双向传输的最大链路调度常数因子算法(SINR based Maximum Link Scheduling Algorithm,SMLSA).通过理论分析和仿真验证了该算法的正确性和有效性,与已有的工作相比,网络容量提高了约25%~40%.

In the Wireless Mesh Networks(WMN),link scheduling is a fundamental problem related to throughput capacity and delay.For a given set of communication requests L={l 1,l 2,…l n},the Maximum Link Scheduling(MLS)problem aims to find the largest possible subset S of L,so that all of the links in S can be scheduled simultaneously.Most of the existing results did not consider bidirectional transmission setting for link scheduling,which is more realistic in wireless mesh networks.In this paper,under SINR(Signal to Interference and Noise Ratio)and bidirectional transmission model,we propose a constant factor approximation algorithm SMLSA(SINR based Maximum Link Scheduling Algorithm,SMLSA)for MLS.By the theoretical analysis and simulation,the correctness and effectiveness of SMLSA are verified.Compared with the existing results,the capacity of SMLSA is improved about 25%to 40%.