Minimum multicast time problem in wireless sensor networks

CSpace > 应用数学研究所

	Minimum multicast time problem in wireless sensor networks
	Zhu, Jianming; Chen, Xujin; Hu, Xiaodong
	2006
发表期刊	WIRELESS ALGORITHMS, SYSTEMS, AND APPLICATIONS, PROCEEDINGS
ISSN	0302-9743
卷号	4138 页码:490-501
摘要	Given an undirected graph representing a network of processors, and a source node needs to broadcast a message to all other nodes in the graph, the minimum broadcast time problem is to find a scheme that accomplishes the broadcast in a minimum number of time steps under the constraint that at each time round, any node can send the message to at most one of its neighbors in the network. This NP-complete problem has been extensively studied in literature. In this paper, we consider a generation of the minimum broadcast problem, the minimum multicast time problem, in unit disk graphs which model wireless sensor networks. The goal is to multicast a message from the source node to a set of specified sensor nodes of the network in a minimum number of time rounds. We prove that this problem is NP-complete, and give an O(1)-approximation algorithm for it. Our simulation results show that the practical performance of the proposed algorithm is much better than the theoretically proved approximation ratio.
语种	英语
WOS研究方向	Computer Science ; Telecommunications
WOS类目	Computer Science, Theory & Methods ; Telecommunications
WOS记录号	WOS:000240084000047
出版者	SPRINGER-VERLAG BERLIN
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/2495
专题	应用数学研究所
通讯作者	Zhu, Jianming
作者单位	Chinese Acad Sci, Inst Appl Math, Beijing 100080, Peoples R China
推荐引用方式 GB/T 7714	Zhu, Jianming,Chen, Xujin,Hu, Xiaodong. Minimum multicast time problem in wireless sensor networks[J]. WIRELESS ALGORITHMS, SYSTEMS, AND APPLICATIONS, PROCEEDINGS,2006,4138:490-501.
APA	Zhu, Jianming,Chen, Xujin,&Hu, Xiaodong.(2006).Minimum multicast time problem in wireless sensor networks.WIRELESS ALGORITHMS, SYSTEMS, AND APPLICATIONS, PROCEEDINGS,4138,490-501.
MLA	Zhu, Jianming,et al."Minimum multicast time problem in wireless sensor networks".WIRELESS ALGORITHMS, SYSTEMS, AND APPLICATIONS, PROCEEDINGS 4138(2006):490-501.