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

Constant Approximation Algorithm for Shortest Link Scheduling Problem in Wireless Sensor Network

作　　者：吕玉华[1] 禹继国[1] 王晨曦[1] 

机构地区：[1]曲阜师范大学计算机科学学院,山东日照276826

出　　处：《计算机工程》2013年第7期110-114,共5页Computer Engineering

基　　金：国家自然科学基金资助项目(11101243;60373012);山东省自然科学基金资助项目(ZR2012FM023;ZR2009GM009;ZR2009AM013);山东省高校科技计划基金资助项目(J10LG09)

摘　　要：针对无线传感器网络中的最短链路调度问题,在有界线性功率分配方式下,提出一种基于物理干扰模型的常数近似算法。采用网格划分方法,使每个时间段所对应链路集合中的链路都满足SINR阈值约束,并对算法的有效性和近似比进行理论论证。仿真结果表明,与TONOYAN算法相比,在多数情况下该算法具有更小的时间延迟。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.

关 键 词：无线传感器网络 链路调度 最大独立集 物理干扰模型 线性功率分配 NP完全 

分 类 号：TP393.03[自动化与计算机技术—计算机应用技术]