Improved Algorithm for Minimum Data Aggregation Time Problem in Wireless Sensor Networks

doi:10.1007/s11424-008-9139-1

CORC > 数学与系统科学研究院 > 中国科学院数学与系统科学研究院 > 应用数学研究所

	Improved Algorithm for Minimum Data Aggregation Time Problem in Wireless Sensor Networks
	Zhu, Jianming 1; Hu, Xiaodong2
刊名	JOURNAL OF SYSTEMS SCIENCE & COMPLEXITY
	2008-12-01
卷号	21 期号:4 页码:626-636
关键词	Approximation algorithm data aggregation wireless sensor network
ISSN号	1009-6124
DOI	10.1007/s11424-008-9139-1
英文摘要	Wireless sensor networks promise a new paradigm for gathering data via collaboration among sensors spreading over a large geometrical region. Many applications impose delay requirements for data gathering and ask for time-efficient schedules for aggregating sensed data and sending to the data sink. In this paper, the authors study the minimum data aggregation time problem under collision-free transmission model. In each time round, data sent by a sensor reaches all sensors within its transmission range, but a sensor can receive data only when it is the only data that reaches the sensor. The goal is to find the method that schedules data transmission and aggregation at sensors so that the time for all requested data to be sent to the data sink is minimal. The authors propose a new approximation algorithm for this NP-hard problem with guaranteed performance ratio where S is the set of sensors containing source data, is the maximal number of sensors within the transmission range of any sensor, and c is a constant. The authors also conduct extensive simulation, the obtained results justify the improvement of proposed algorithm over the existing one.
资助项目	National Natural Science Foundation of China[70221001] ; 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研究方向	Mathematics
语种	英语
出版者	SPRINGER
WOS记录号	WOS:000260878200010
内容类型	期刊论文
源URL	[http://ir.amss.ac.cn/handle/2S8OKBNM/6717]
专题	应用数学研究所
通讯作者	Zhu, Jianming
作者单位	1.Chinese Acad Sci, Grad Sch, Beijing 100049, Peoples R China 2.Chinese Acad Sci, Inst Appl Math, Beijing 100190, Peoples R China
推荐引用方式 GB/T 7714	Zhu, Jianming,Hu, Xiaodong. Improved Algorithm for Minimum Data Aggregation Time Problem in Wireless Sensor Networks[J]. JOURNAL OF SYSTEMS SCIENCE & COMPLEXITY,2008,21(4):626-636.
APA	Zhu, Jianming,&Hu, Xiaodong.(2008).Improved Algorithm for Minimum Data Aggregation Time Problem in Wireless Sensor Networks.JOURNAL OF SYSTEMS SCIENCE & COMPLEXITY,21(4),626-636.
MLA	Zhu, Jianming,et al."Improved Algorithm for Minimum Data Aggregation Time Problem in Wireless Sensor Networks".JOURNAL OF SYSTEMS SCIENCE & COMPLEXITY 21.4(2008):626-636.