WSN最短链路调度问题的常数近似算法

摘要

Link scheduling is an important issue in Wireless Sensor Network(WSN).For the problem of Shortest Link Scheduling(SLS),this paper gives a constant approximation algorithm with linear power assignment under the physical interference model.All links of each link set in corresponding time slot meet the SINR threshold constraint with grid partition.The effectiveness of the algorithm and the approximate ratio are discussed through theoretical analysis.Simulation experimental results show that the algorithm has less time delay than TONOYAN algorithm.%针对无线传感器网络中的最短链路调度问题,在有界线性功率分配方式下,提出一种基于物理干扰模型的常数近似算法.采用网格划分方法,使每个时间段所对应链路集合中的链路都满足SINR阈值约束,并对算法的有效性和近似比进行理论论证.仿真结果表明,与TONOYAN算法相比,在多数情况下该算法具有更小的时间延迟.