Minimum data aggregation time problem in wireless sensor networks

CSpace > 应用数学研究所

	Minimum data aggregation time problem in wireless sensor networks
	Chen, XJ; Hu, XD; Zhu, JM
	2005
发表期刊	MOBILE AD-HOC AND SENSOR NETWORKS, PROCEEDINGS
ISSN	0302-9743
卷号	3794 页码:133-142
摘要	Wireless sensor networks promise a new paradigm for gathering data via collaboration among sensors spreading over a large geometrical region. Many real-time applications impose stringent delay requirements and ask for time-efficient schedules of data aggregations in which sensed data at sensors are combined at intermediate sensors along the way towards the data sink. The Minimum Data Aggregation Time (MDAT) problem is to find the schedule that routes data appropriately and has the shortest time for all requested data to be aggregated to the data sink. In this paper we study the MDAT problem with uniform transmission range of all sensors. We assume that, in each time round, data sent by a sensor reaches exactly all sensors within its transmission range, and a sensor receives data if it is the only data that reaches the sensor in this time round. We first prove that this problem is NP-hard even when all sensors are deployed a grid and data on all sensors are required to be aggregated to the data sink. We then design a (Delta - 1)-approximation algorithm for MDAT problem, where Delta + 1 equals the maximum number of sensors within the transmission range of any sensor. We also simulate the proposed algorithm and compare it with the existing algorithm. The obtained results show that our algorithm has much better performance in practice than the theoretically proved guarantee and outperforms other algorithm.
语种	英语
WOS研究方向	Computer Science ; Telecommunications
WOS类目	Computer Science, Information Systems ; Computer Science, Theory & Methods ; Telecommunications
WOS记录号	WOS:000234715200014
出版者	SPRINGER-VERLAG BERLIN
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/1295
专题	应用数学研究所
通讯作者	Chen, XJ
作者单位	Chinese Acad Sci, Inst Appl Math, Beijing 100080, Peoples R China
推荐引用方式 GB/T 7714	Chen, XJ,Hu, XD,Zhu, JM. Minimum data aggregation time problem in wireless sensor networks[J]. MOBILE AD-HOC AND SENSOR NETWORKS, PROCEEDINGS,2005,3794:133-142.
APA	Chen, XJ,Hu, XD,&Zhu, JM.(2005).Minimum data aggregation time problem in wireless sensor networks.MOBILE AD-HOC AND SENSOR NETWORKS, PROCEEDINGS,3794,133-142.
MLA	Chen, XJ,et al."Minimum data aggregation time problem in wireless sensor networks".MOBILE AD-HOC AND SENSOR NETWORKS, PROCEEDINGS 3794(2005):133-142.