Approximation algorithms for minimum broadcast schedule problem in wireless sensor networks

doi:10.1007/s11464-009-0050-4

CSpace > 应用数学研究所

	Approximation algorithms for minimum broadcast schedule problem in wireless sensor networks
	Shang, Weiping 2; Wan, Pengjun 3; Hu, Xiaodong1
	2010
发表期刊	FRONTIERS OF MATHEMATICS IN CHINA
ISSN	1673-3452
卷号	5 期号:1 页码:75-87
摘要	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.
关键词	broadcast schedule approximation algorithm wireless sensor network unit disk graph
DOI	10.1007/s11464-009-0050-4
语种	英语
资助项目	National Natural Science Foundation of China[10531070] ; National Natural Science Foundation of China[10771209] ; National Natural Science Foundation of China[10721101] ; Foundation of Chinese Academy of Sciences[kjcx-yw-s7]
WOS研究方向	Mathematics
WOS类目	Mathematics
WOS记录号	WOS:000273479500007
出版者	HIGHER EDUCATION PRESS
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/9326
专题	应用数学研究所
通讯作者	Hu, Xiaodong
作者单位	1.Chinese Acad Sci, Inst Appl Math, Beijing 100190, Peoples R China 2.Zhengzhou Univ, Dept Math, Zhengzhou 450052, Peoples R China 3.IIT, Dept Comp Sci, Chicago, IL 60616 USA
推荐引用方式 GB/T 7714	Shang, Weiping,Wan, Pengjun,Hu, Xiaodong. Approximation algorithms for minimum broadcast schedule problem in wireless sensor networks[J]. FRONTIERS OF MATHEMATICS IN CHINA,2010,5(1):75-87.
APA	Shang, Weiping,Wan, Pengjun,&Hu, Xiaodong.(2010).Approximation algorithms for minimum broadcast schedule problem in wireless sensor networks.FRONTIERS OF MATHEMATICS IN CHINA,5(1),75-87.
MLA	Shang, Weiping,et al."Approximation algorithms for minimum broadcast schedule problem in wireless sensor networks".FRONTIERS OF MATHEMATICS IN CHINA 5.1(2010):75-87.