Data Gathering Schedule for Minimal Aggregation Time in Wireless Sensor Networks

doi:10.1080/15501320701585527

CSpace > 应用数学研究所

	Data Gathering Schedule for Minimal Aggregation Time in Wireless Sensor Networks
	Chen, Xujin; Hu, Xiaodong; Zhu, Jianming
	2009
发表期刊	INTERNATIONAL JOURNAL OF DISTRIBUTED SENSOR NETWORKS
ISSN	1550-1329
卷号	5 期号:4 页码:321-337
摘要	Data aggregation promises a new paradigm for gathering data via collaboration among wireless sensors deployed over a large geographical region. Many real-time applications impose stringent delay requirements and ask for time-efficient schedules of data gathering in which data sensed at sensors are aggregated at intermediate sensors along the way towards the data sink. The Minimal Aggregation Time (MAT) problem is to find the schedule that routes data appropriately and has the shortest time for all requested data to be aggregated and sent to the data sink. In this article we consider the MAT problem with collision-free transmission where a sensor can not receive any data if more than one sensors within its transmission range send data at the same time. We first prove that the MAT problem is NP-hard even if all sensors are deployed on a grid. We then propose a ( - 1)-approximation algorithms for the MAT problem, where is the maximum number of sensors within the transmission range of any sensor. By exploiting the geometric nature of wireless sensor networks, we obtain some better theoretical results for some special cases. We also simulate the proposed algorithm. The numerical results show that our algorithm has much better performance in practice than the theoretically proved guarantees and outperforms other existing algorithms.
关键词	Wireless Sensor Networks Data Aggregations Convergecast Collision-free Transmission Unit Disk Graphs Approximation Algorithm
DOI	10.1080/15501320701585527
语种	英语
资助项目	NSF of China[10531070] ; NSF of China[70221001] ; Chinese Academy of Sciences[kjcx-yw-s7]
WOS研究方向	Computer Science ; Telecommunications
WOS类目	Computer Science, Information Systems ; Telecommunications
WOS记录号	WOS:000274753000003
出版者	TAYLOR & FRANCIS INC
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/7689
专题	应用数学研究所
通讯作者	Hu, Xiaodong
作者单位	Chinese Acad Sci, Inst Appl Math, Beijing 100080, Peoples R China
推荐引用方式 GB/T 7714	Chen, Xujin,Hu, Xiaodong,Zhu, Jianming. Data Gathering Schedule for Minimal Aggregation Time in Wireless Sensor Networks[J]. INTERNATIONAL JOURNAL OF DISTRIBUTED SENSOR NETWORKS,2009,5(4):321-337.
APA	Chen, Xujin,Hu, Xiaodong,&Zhu, Jianming.(2009).Data Gathering Schedule for Minimal Aggregation Time in Wireless Sensor Networks.INTERNATIONAL JOURNAL OF DISTRIBUTED SENSOR NETWORKS,5(4),321-337.
MLA	Chen, Xujin,et al."Data Gathering Schedule for Minimal Aggregation Time in Wireless Sensor Networks".INTERNATIONAL JOURNAL OF DISTRIBUTED SENSOR NETWORKS 5.4(2009):321-337.