Approximation algorithms for minimum broadcast schedule problem in wireless sensor networks |
| |
Authors: | Weiping Shang Pengjun Wan Xiaodong Hu |
| |
Affiliation: | 1.Department Of Mathematics,Zhengzhou University, Zhengzhou 450052, China; 2.Department of ComputerScience, Illinois Institute of Technology, Chicago, IL 60616, USA; 3.Institute of AppliedMathematics, Chinese Academy of Sciences, Beijing 100190, China; |
| |
Abstract: | A wireless sensor network usually consists of a large number of sensor nodes deployed in a field. One of the major communication operations is to broadcast a message from one node to the rest of the others. In this paper, we adopt the conflict-free communication model and study how to compute a transmission schedule that determines when and where a node should forward the message so that all nodes could receive the message in minimum time. We give two approximation algorithms for this NP-hard problem that have better theoretically guaranteed performances than the existing algorithms. The proposed approach could be applied to some other similar problems. |
| |
Keywords: | broadcast schedule approximation algorithm wireless sensor network unit disk graph |
本文献已被 万方数据 SpringerLink 等数据库收录! |
| 点击此处可从《Frontiers of Mathematics in China》浏览原始摘要信息 |
|
点击此处可从《Frontiers of Mathematics in China》下载全文 |