Approximation algorithm for minimal convergecast time problem in wireless sensor networks

doi:10.1007/s11276-009-0207-9

CSpace > 应用数学研究所

	Approximation algorithm for minimal convergecast time problem in wireless sensor networks
	Shang, Weiping 2; Wan, Pengjun 3; Hu, Xiaodong1
	2010-07-01
发表期刊	WIRELESS NETWORKS
ISSN	1022-0038
卷号	16 期号:5 页码:1345-1353
摘要	In this paper we consider how to collect data from sensors deployed in the Euclidean plane in a time-efficient way. We assume that all sensors could adjust their transmission ranges and aggregate data received from other sensors. We adopt a collision-free transmission model using proper schedules for data transmission. We study the problem of finding the schedule under which data from all sensors could be transmitted to the data sink in the minimal time. We propose an approximation algorithm for this NP-hard problem whose performance ratio is bounded by a constant. This significantly improves the existing approximation algorithm that does not have a constant performance ratio.
关键词	Convergecast Latency Wireless sensor networks Approximation algorithm
DOI	10.1007/s11276-009-0207-9
语种	英语
资助项目	National Natural Science Foundation of China[10531070] ; National Natural Science Foundation of China[10771209] ; National Natural Science Foundation of China[10721101] ; Chinese Academy of Sciences[kjcx-yw-s7]
WOS研究方向	Computer Science ; Engineering ; Telecommunications
WOS类目	Computer Science, Information Systems ; Engineering, Electrical & Electronic ; Telecommunications
WOS记录号	WOS:000278968500009
出版者	SPRINGER
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/9662
专题	应用数学研究所
通讯作者	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 algorithm for minimal convergecast time problem in wireless sensor networks[J]. WIRELESS NETWORKS,2010,16(5):1345-1353.
APA	Shang, Weiping,Wan, Pengjun,&Hu, Xiaodong.(2010).Approximation algorithm for minimal convergecast time problem in wireless sensor networks.WIRELESS NETWORKS,16(5),1345-1353.
MLA	Shang, Weiping,et al."Approximation algorithm for minimal convergecast time problem in wireless sensor networks".WIRELESS NETWORKS 16.5(2010):1345-1353.