| WSN最短链路调度问题的常数近似算法 |
| |
| 引用本文： | 吕玉华,禹继国,王晨曦.WSN最短链路调度问题的常数近似算法[J].计算机工程,2013,39(7). |
| |
| 作者姓名： | 吕玉华 禹继国 王晨曦 |
| |
| 作者单位： | 曲阜师范大学计算机科学学院,山东日照,276826 |
| |
| 基金项目： | 国家自然科学基金资助项目，山东省自然科学基金资助项目，山东省高校科技计划基金资助项目 |
| |
| 摘 要： | 针对无线传感器网络中的最短链路调度问题,在有界线性功率分配方式下,提出一种基于物理干扰模型的常数近似算法.采用网格划分方法,使每个时间段所对应链路集合中的链路都满足SINR阈值约束,并对算法的有效性和近似比进行理论论证.仿真结果表明,与TONOYAN算法相比,在多数情况下该算法具有更小的时间延迟.
|
| 关 键 词： | 无线传感器网络 链路调度 最大独立集 物理干扰模型 线性功率分配 NP完全 |
Constant Approximation Algorithm for Shortest Link Scheduling Problem in Wireless Sensor Network |
| |
| LV Yu-hua
,
YU Ji-guo
,
WANG Chen-xi.Constant Approximation Algorithm for Shortest Link Scheduling Problem in Wireless Sensor Network[J].Computer Engineering,2013,39(7). |
| |
| Authors: | LV Yu-hua YU Ji-guo WANG Chen-xi |
| |
| Abstract: | |
| |
| Keywords: | Wireless Sensor Network(WSN) link scheduling maximum independent set physical interference model linear power assignment NP-complete problem |
| 本文献已被 万方数据 等数据库收录！ |
|
