计算机工程2013，Vol.39Issue(7)：110-114,5.DOI:10.3969/j.issn.1000-3428.2013.07.025
WSN最短链路调度问题的常数近似算法
Constant Approximation Algorithm for Shortest Link Scheduling Problem in Wireless Sensor Network
摘要
Abstract
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完全Key words
Wireless Sensor Network(WSN)/ link scheduling/ maximum independent set/ physical interference model/ linear power assignment/ NP-complete problem分类
信息技术与安全科学引用本文复制引用
吕玉华,禹继国,王晨曦..WSN最短链路调度问题的常数近似算法[J].计算机工程,2013,39(7):110-114,5.基金项目
国家自然科学基金资助项目(11101243,60373012) （11101243,60373012）
山东省自然科学基金资助项目(ZR2012FM023,ZR2009GM009,ZR2009AM013) （ZR2012FM023,ZR2009GM009,ZR2009AM013）
山东省高校科技计划基金资助项目(J10LG09) （J10LG09）
